1、調運問題-圖上作業法適用于解決產銷/供需平衡條件下的多個供應點對多個需求點的物資調運基本思路：破圈法編制初始方案。打破每一回路中距離最長的一段，并在交通圖上，從破開的線段端點開始，依照就近調運原則和右 手原則，用箭頭“一”標出物資流向：即箭頭“一”始終在以輸出地為起點、以輸入地為終點的交通路線的右邊。以圓圈加 數字的形式將運輸量標注在箭頭“一”旁邊。檢驗：每一回路的內、外圈長如果均不大于該回路的半圈長，該方案已經最優；否則進行調整。調整：找出有問題圈中的最小運量邊，斷開此邊，重新編制調運方案。重復步驟23，直到每一回路都達到最優。該調運方案即為最優。例題：某制造企業有專門為產品生產工廠提供零部

2、件和半成品的零部件制造廠，共有S1、S2、S3、S4、S5、S6、S7七 個零部件制造廠和D1、D2、D3、D4、D5、D6、D7七個產品生產工廠。各零部件制造廠的產量（橢圓框內數字）、各生 產工廠的零部件需求量（矩形框內數字）以及他們的位置和相互距離如圖1所示。其中產量和需求量單位為噸，距離單位 為公里，請利用圖上作業法確定最佳的零部件調運方案。解：1.在唯一的回路中，距離為85的一段最長，斷開此段。并以供方190開始編制初始調運方案，標注如圖21002.對該回路進行檢驗：內圈長=0，外圈長=70+80+70+75+60=355，該回路總長=355+85=440，半圈長=440/2=220內

3、圈長半圈長，外圈長半圈長，需要對外圈進行調整。3.在初始方案中，外圈的最小運量為10,斷開此段，重新編制調運方案。第一次調整后的調運方案如圖3所示:4.對新方案進行檢驗：內圈長=85，外圈長=70+80+70+60=2803.在初始方案中，外圈的最小運量為10,斷開此段，重新編制調運方案。第一次調整后的調運方案如圖3所示:4.對新方案進行檢驗：內圈長=85，外圈長=70+80+70+60=280，該回路總長=355+85=440，半圈長=440/2=220內圈長半圈長，外圈長半圈長，需要對外圈進行第二次調整。當前，外圈的最小運量為40，斷開此段，重新編制調運方案。第二次調整后的調運方案如圖4所

4、示:對第二次調整后的新方案進行檢驗：內圈長=85+75=160，外圈長=70+70+60=200，該回路總長=355+85=440，半圈長=440/2=220內圈長半圈長，外圈長半圈長。該方案達到最優。練習題：如右圖，A表示配送點，B表示客戶點，請制定調配方案。調運問題-表上作業法適用于解決產銷/供需平衡條件下的多個供應點對多個需求點的物資調運步驟分三步:首先用最小元素法、西北角法、伏格爾法求出初始可行解，再采用閉合回路法或位勢法判斷是否最優，最 后采用I閉合回路調整法調整變量直至最優解。最小元素法從運價最小的格開始，在格內的右下角填上允許取得的最大運輸量。該運輸量取該最小元素對應的產地的供應

5、量與銷 地的需求量的最小值，然后將對應供應量和需求量分別減去該最小值，并在運價表中劃去差為0的供應量或需求量對應的行 或列（若供應量和需求量的差均為0，則只能劃去其中任意一行或一列，但不能同時劃去行和列）如此按運價從小到大順序 填數（從單位配送價格最小到最大順序逐一使供需量平衡）。重復此步驟直至得到一個基本可行解。注:應用西北角法和最小元素法，每次填完數，都只劃去一行或一列，只有最后一個例外（同時劃去一行和一列）。當填上 一個數后行、列同時飽和時，也應任意劃去一行（列），在保留的列（行）中沒被劃去的格內標一個0。（即：表格中一般 要有（m+n-1）個數字格，即“產地個數+銷地個數一1”。但有時

6、，在分配運量時則需要同時劃去一行和一列，這時需要補一 個0，以保證有（m+n-1 ）個數字格。一般可在劃去的行和列的任意空格處加一個0即可。）閉回路法1、檢驗檢驗每一個空格對應的檢驗數，采用閉合回路法。即從表上任一個空格出發，沿水平或垂直方向前進，每遇到一個適當 有調運量數字的格子（該格子有利于回到原空格，可以穿過不適當的數字格）轉90，繼續前進直到回到原空格。這樣形成 的一條由水平和垂直線段組成的封閉折線稱為閉回路。除起點是空格外，其余所有的拐角點都是填有調運量的。為確定空格k.tk.t.一k.t（）的檢驗數，便可以從空格（）出發作閉回路，并對該回路的頂點進行編號，即 第一個項點，所經過的頂

7、點依次為第二個、第三個。則閉回路上奇數頂點的單位運價之和減去偶數頂點的單位運價之和所得到的差,，就是空格（:_。當所有空格的檢驗數都大于等于0,則就是最優解，否則還需要繼續改進。2、改進改進的方法采用閉合回路調整法，調整在負榆驗數的絕對值最大的那個空格對應的閉回路中進行，調整量q取該閉回 路中偶數號拐彎處運輸量的最小值，即q = min （所有偶數號拐彎處的運輸量）所有奇數號拐彎處運輸量都加上q，所有偶 數號拐彎處運輸量都減去q，并取某一運輸量為0的拐彎處作為空格（若有兩處以上運輸量為0，則只能取其中任意一個拐 彎處作為空格，其它的0代表該處的運輸量）。然后再次使用閉合回路法檢驗所有空格的檢驗

8、數，所有檢驗數大于0則就是最優解，否則再繼續改進，直至最優。例某物資要從產地A1, A2, A3調往銷地B1, B2, B3，運輸供需數量及價格表如下所示:B1B2B3供應量A150408020A230109050A360302080需求量504060150試用最小元素法編制初始調運方案，并求最優調運方案和最小運輸總費用。 解：1、用最小元素法編制的初始調運方案如下表所示：B1B2B3供應量A150(20)408020A230(10)10(40)9050A360(20)3020(60)80需求量5040601502、對空格找閉回路，計算檢驗數：li2 = 4010+30 50=10, li3 = 80 20 + 60 50 = 70,l =90 20+60 30=100, l =30 60 + 30 10= 1002332初始調運方案中存在負檢驗數，需要調整，調整量為q=min (20, 40) =203、調整后的第二個調運方案如下表所示：B1B2B3供應量A150(20)408020A230(30)10(20)9050A36030(20)20(60)80需求量5040601504、對空格再找閉回路，計算檢驗數：l12 = 4010+30 50=10, l13 = 80