設平衡運輸問題的數學模型為：4/8/2025表上作業法也稱為運輸單純形法，是直接在運價表上求最優解的一種方法，它的步驟是：第一步：求初始基行可行解（初始調運方案），常用的方法有最小元素法、元素差額法（Vogel近似法）、左上角法。第二步：求檢驗數并判斷是否得到最優解，常用求檢驗的方法有閉回路法和位勢法，當非基變量的檢驗數λij全都非負時得到最優解，若存在檢驗數λlk<0，說明還沒有達到最優，轉第三步。第三步：調整運量，即換基，選一個變量出基，對原運量進行調整得到新的基可行解，轉入第二步。4/8/20253.3.1初始基可行解1.最小元素法最小元素法的思想是就近優先運送，即最小運價Cij對應的變量xij優先賦值然后再在剩下的運價中取最小運價對應的變量賦值并滿足約束，依次下去，直到最后一個初始基可行解。4/8/2025【例3】求表3－6所示的運輸問題的初始基可行解。表3－6銷地產地B1B2B3產量A186730A243545A374825銷量6030101004/8/2025B1B2B3可發量A186730A243545A374825未滿足量603010100000【解】301510252015452020000產地銷地4/8/2025【例4】求表3－7給出的運輸問題的初始基本可行解。

B1B2B3B4aiA1311447A277384A3121069bj365620表3－74/8/2025【解】

B1B2B3B4aiA1311447A277384A3121069bj3656203××60×××4×16在x12、x22、x33、x34中任選一個變量作為基變量，例如選x12表3－84/8/2025初始基本可行解可用下列矩陣表示表3－8中，標有符號的變量恰好是3+4－1=6個且不包含閉回路，是一組基變量，其余標有符號×的變量是非基變量，4/8/20252．運費差額法（Vogel近似法）最小元素法只考慮了局部運輸費用最小，對整個產銷系統的總運輸費用來說可能離最優值較遠。有時為了節省某一處的運費，而在其它處可能運費很大。運費差額法對最小元素法進行了改進，考慮到產地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調運，否則會增加總運費。例如下面兩種運輸方案，15151515前一種按最小元素法求得，總運費是Z1=10×8+5×2+15×1=105，后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先調運x21，到后來就有可能x11≠0，這樣會使總運費增加較大，從而先調運x21，再是x22，其次是x12這時總運費Z2=10×5+15×2+5×1=85<Z1。4/8/2025基于以上想法，運費差額法求初始基本可行解的步驟是：第一步：求出每行次小運價與最小運價之差，記為ui，i=1,2,…,m；同時求出每列次小運價與最小運價之差，記為vj，j=1，2，…，n；第二步：找出所有行、列差額的最大值，即L=max{ui，vi}，差額L對應行或列的最小運價處優先調運；第三步：這時必有一列或一行調運完畢，在剩下的運價中再求最大差額，進行第二次調運，依次進行下去，直到最后全部調運完畢，就得到一個初始調運方案。用運費差額法求得的基本可行解更接近最優解，所以也稱為近似方案。4/8/2025【例5】用運費差額法求表3—9運輸問題的初始基本可行解。

B1B2B3B4aiA15891215A2672425A311013820bj201052560表3—94/8/2025銷地產地B1B2B3B4aiuiA1

5

8

9

12153A2

1

7

2

4251A36

10

13

8202bj201052560

vj4174

【解】求行差額ui,i=1,2,3及列差額vj,j=1,2,3,4.計算公式為

ui=i行次小運價—i行最小運價

vj=j列次小運價—j例最小運價5××4/8/2025銷地產地B1B2B3B4aiuiA1

5

8

9

1215A2

1

7

2

425A36

10

13

820bj201052560

vj

5××414—332200×××4/8/2025銷地產地B1B2B3B4aiuiA1

5

8

9

1215A2

1

7

2

425A36

10

13

820bj201052560

vj

5××200×××—2—44—220×1054/8/2025基本可行解為總運費Z=10×8+20×1+5×2+20×8=270。求運輸問題的初始方案還有很多方法，如左上角法、右上角法等。常用的方法是Vogel近似法、最小元素法。4/8/20253.3.2求檢驗數求出一組基可行解后，判斷是否為最優解，仍然是用檢驗數來判斷，記xij的檢驗數為λij由第一章知，求最小值的運輸問題的最優判別準則是：所有非基變量的檢驗數都非負，則運輸方案最優（即為最優解）。求檢驗數的方法有兩種，閉回路法和位勢法。1．閉回路法求檢驗數求某一非基變量的檢驗數的方法是：在基本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點上交替標上代數符號+、-、+、-、…，以這些符號分別乘以相應的運價，其代數和就是這個非基變量的檢驗數。4/8/2025【解】用最小元素法得到下列一組基本可行解【例6】求下列運輸問題的一個初始基本可行解及其檢驗數。矩陣中的元素為運價Cij，矩陣右邊的元素為產量ai

，下方的元素為銷量bj。106040304/8/2025矩陣中打“×”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗數。求λ11，先找出x11的閉回路，對應的運價為再用正負號分別交替乘以運價有直接求代數和得4/8/2025同理可求出其它非基變量的檢驗數：這里λ34<0，說明這組基本可行解不是最優解。只要求得的基變量是正確的且數目為m+n－1，則某個非基變量的閉回路存在且唯一，因而檢驗數唯一。4/8/20252．位勢法求檢驗位勢法求檢驗數是根據對偶理論推導出來的一種方法。設平衡運輸問題為設前m個約束對應的對偶變量為ui,i=1,2,…,m，后n個約束對應的對偶變量為vj,j=1,2,…,n則運輸問題的對偶問題是4/8/2025加入松馳變量λij將約束化為等式ui+vj+λij=cij記原問題基變量XB的下標集合為I，由第二章對偶性質知，原問題xij的檢驗數是對偶問題的松弛變量λij當（i，j）

時λij=0，因而有解上面第一個方程，將ui、vj代入第二個方程求出λij。4/8/2025【例7】用位勢法求例7給出的初始基本可行解的檢驗數。【解】第一步求位勢u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位勢的解為4/8/2025再由公式求出檢驗數，其中Cij是非基變量對應的運價。計算結果與例7結果相同。4/8/2025【例8】求下表所示運輸方案的檢驗數。銷地產地B1B2B3B4aiuiA1

5

8

9

1215A2

1

7

2

425A36

10

13

820bj201052560

vj

5200586120-4-420105位勢法的表上形式9-0-6[3]7-(-4)-8[3]4-(-4)-12[-4]6-(-4)-5[5]10-(-4)-8[6]13-(-4)-6[11]4/8/20253.3.3調整運量前面講過，當某個檢驗數小于零時，基可行解不是最優解，總運費還可以下降，這時需調整運輸量，改進原運輸方案，使總運輸減少，改進運輸方案的步驟是：第一步：確定進基變量；第二步：確定出基變量，在進基變量xik的閉回路中，標有負號的最小運量作為調整量θ，θ對應的基變量為出基變量，并打上“×”以示作為非基變量。第三步：調整運量。在進基變量的閉回路中標有正號的變量加上調整量θ，標有負號的變量減去調整量θ，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗數重新檢驗。4/8/2025【例9】求下表所示的運輸問題的最優解。表3－6

B1B2B3產量A186730A243545A374825銷量603010100產地銷地4/8/2025B1B2B3產量A186730A243545A374825銷量603010100【解】3015102520＋－＋－[-1]前面已得到此題的初始可行解，現在接著做下去。用閉回路法求檢驗數如下：產地銷地4/8/2025

B1B2B3產量A186730A243545A374825銷量60301010030151020[-1]＋－＋－[2]25產地銷地【解】前面已得到此題的初始可行解，現在接著做下去。用閉回路法求檢驗數如下：4/8/2025B1B2B3產量A186730A243545A374825銷量60301010030151020[-1][2]25＋－＋－[-2]產地銷地【解】前面已得到此題的初始可行解，現在接著做下去。用閉回路法求檢驗數如下：4/8/2025B1B2B3產量A186730A243545A374825銷量60301010030151020[-1][2]25＋－＋－[-2]產地銷地[2]【解】前面已得到此題的初始可行解，現在接著做下去。用閉回路法求檢驗數如下：4/8/2025B1B2B3A1867A2435A374830151020[-1][2]25[-2]產地銷地[０]因為有２個負檢驗數，所以這組基本可行解不是最優解。取非基變量x32進基,用閉回路法調整如下閉回路如上圖，標負號的運量是：x31=25、x22=30，取其最小值25作為調整量，在閉回路上x21、x32分別加上25，x31、x22分別減去25，調整后得到一組新的基可行解。＋－＋25－

405

4/8/2025B1B2B3產量A186730A243545A374825銷量603010100540102520[-1][2]＋－＋－[2]再檢驗（表中括號中的數字為檢驗數）4/8/2025B1B2B3產