運輸單純形法

1、設平衡運輸問題的數(shù)學模型為：8/27/2022運輸單純形法也稱為表上作業(yè)法，是直接在運價表上求最優(yōu)解的一種方法，它的步驟是： 第一步：求初始基行可行解（初始調(diào)運方案），常用的方法有最小元素法、元素差額法（Vogel近似法）、左上角法。 第二步：求檢驗數(shù)并判斷是否得到最優(yōu)解，常用求檢驗的方法有閉回路法和位勢法，當非基變量的檢驗數(shù)ij全都非負時得到最優(yōu)解，若存在檢驗數(shù)lk0，說明還沒有達到最優(yōu)，轉第三步。 第三步：調(diào)整運量，即換基，選一個變量出基，對原運量進行調(diào)整得到新的基可行解，轉入第二步。8/27/20223.3.1初始基可行解1.最小元素法 最小元素法的思想是就近優(yōu)先運送，即最小運價Cij對

2、應的變量xij優(yōu)先賦值然后再在剩下的運價中取最小運價對應的變量賦值并滿足約束，依次下去，直到最后一個初始基可行解。8/27/2022【例3.3】求表36所示的運輸問題的初始基可行解。表36 銷 地產(chǎn)地B1B2B3產(chǎn)量A186730A243545A374825銷 量6030101008/27/2022 銷 地產(chǎn)地B1B2B3產(chǎn)量A186730A243545A374825銷 量603010100【解】30151025208/27/2022【例3.4】求表37給出的運輸問題的初始基本可行解。 B1B2B3B4aiA1311447A277384A3121069bj365620表378/27/2022【

3、解】B1B2B3B4aiA1311447A277384A3121069bj365620360416在x12、x22、x33、x34中任選一個變量作為基變量，例如選x12表388/27/2022初始基本可行解可用下列矩陣表示表38中，標有符號 的變量恰好是3+41=6個且不包含閉回路，是一組基變量，其余標有符號的變量是非基變量， 8/27/20222元素差額法（Vogel近似法）最小元素法只考慮了局部運輸費用最小，對整個產(chǎn)銷系統(tǒng)的總運輸費用來說可能離最優(yōu)值較遠。有時為了節(jié)省某一處的運費，而在其它處可能運費很大。元素差額法對最小元素法進行了改進，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果

4、差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案， 15 15 15 15前一種按最小元素法求得，總運費是Z1=108+52+151=105，后一種方案考慮到C11與C21之間的差額是82=6，如果不先調(diào)運x21，到后來就有可能x110，這樣會使總運費增加較大，從而先調(diào)運x21，再是x22，其次是x12這時總運費Z2=105+152+51=85Z1。 基于以上想法，元素差額法求初始基本可行解的步驟是：8/27/2022 基于以上想法，元素差額法求初始基本可行解的步驟是： 第一步：求出每行次小運價與最小運價之差，記為ui，i=1,2,m；同時求出每列次小運價與最小運價之差，記

5、為vj，j=1，2，n；第二步：找出所有行、列差額的最大值，即L=maxui，vi，差額L對應行或列的最小運價處優(yōu)先調(diào)運； 第三步：這時必有一列或一行調(diào)運完畢，在剩下的運價中再求最大差額，進行第二次調(diào)運，依次進行下去，直到最后全部調(diào)運完畢，就得到一個初始調(diào)運方案。 用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。8/27/2022【例5】用元素差額法求表39運輸問題的初始基本可行解。B1B2B3B4aiA15891215A2672425A311013820bj201052560表398/27/2022 銷地產(chǎn)地B1B2B3B4aiuiA158 912153A217 24251A3

6、610 13 8202bj201052560vj4174【解】 求行差額 ui, i=1,2,3及列差額vj,j=1,2,3,4.計算公式為 ui= i行次小運價i行最小運價 vj= j列次小運價j例最小運價58/27/2022 銷地產(chǎn)地B1B2B3B4aiuiA158 91215A217 2425A3610 13 820bj201052560vj54143322008/27/2022 銷地產(chǎn)地B1B2B3B4aiuiA158 91215A217 2425A3610 13 820bj201052560vj52002442201058/27/2022基本可行解為總運費Z=108+201+52+2

7、08=270。求運輸問題的初始方案還有很多方法，如左上角法、右上角法等。常用的方法是Vogel近似法、最小元素法。8/27/20223.3.2求檢驗數(shù)求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為ij由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu)（即為最優(yōu)解）。求檢驗數(shù)的方法有兩種，閉回路法和位勢法。1閉回路法求檢驗數(shù) 求某一非基變量的檢驗數(shù)的方法是：在基本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點上交替標上代數(shù)符號+、-、+、-、，以這些符號分別乘以相應的運價，其代數(shù)和

8、就是這個非基變量的檢驗數(shù)。8/27/2022【解】用最小元素法得到下列一組基本可行解【例7】求下列運輸問題的一個初始基本可行解及其檢驗數(shù)。矩陣中的元素為運價Cij ，矩陣右邊的元素為產(chǎn)量ai ，下方的元素為銷量bj 。10 60 40 308/27/2022矩陣中打“”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗數(shù)。求11，先找出x11的閉回路 ，對應的運價為再用正負號分別交替乘以運價有直接求代數(shù)和得8/27/2022同理可求出其它非基變量的檢驗數(shù)：這里340，說明這組基本可行解不是最優(yōu)解。只要求得的基變量是正確的且數(shù)目為m+n1，則某個非基變量的閉回路存在且唯一，因而檢驗數(shù)唯一。8

9、/27/20222位勢法求檢驗 位勢法求檢驗數(shù)是根據(jù)對偶理論推導出來的一種方法。設平衡運輸問題為設前m個約束對應的對偶變量為ui,i=1,2,m，后n個約束對應的對偶變量為vj,j=1,2,n則運輸問題的對偶問題是8/27/2022加入松馳變量ij將約束化為等式ui+vj+ij=cij記原問題基變量XB的下標集合為I，由第二章對偶性質知，原問題xij的檢驗數(shù)是對偶問題的松弛變量ij當（i，j） 時ij=0，因而有解上面第一個方程，將ui、vj代入第二個方程求出ij。8/27/2022【例8】用位勢法求例7給出的初始基本可行解的檢驗數(shù)?！窘狻康谝徊角笪粍輚1、u2、u3及v1、v2、v3、v4。

10、 10 60 40 30令u1=0得到位勢的解為8/27/2022再由公式 求出檢驗數(shù)，其中Cij是非基變量對應的運價。計算結果與例7結果相同。8/27/20223.3.3調(diào)整運量前面講過，當某個檢驗數(shù)小于零時，基可行解不是最優(yōu)解，總運費還可以下降，這時需調(diào)整運輸量，改進原運輸方案，使總運輸減少，改進運輸方案的步驟是：第一步：確定進基變量；第二步：確定出基變量，在進基變量xik的閉回路中，標有負號的最小運量作為調(diào)整量，對應的基變量為出基變量，并打上“”以示作為非基變量。第三步：調(diào)整運量。在進基變量的閉回路中標有正號的變量加上調(diào)整量，標有負號的變量減去調(diào)整量，其余變量不變，得到一組新的基可行解，

11、然后求所有非基變量的檢驗數(shù)重新檢驗。8/27/2022【例9】求下列運輸問題的最優(yōu)解。45 65 50 30 銷地產(chǎn)地B1B2B3B4aiA1 589270A2364780A3 101214 540bj45655030190【解】用最小元素法求得初始基本可行解如下：3045354025158/27/2022 銷地產(chǎn)地B1B2B3B4aiA1 589270A2364780A3 101214 540bj45655030190304535402515求非基變量的檢驗數(shù),用閉回路法得：8/27/2022 銷地產(chǎn)地B1B2B3B4aiA1 589270A2364780A3 101214 540bj456

12、55030190304535402515因為有4個檢驗數(shù)小于零，所以這組基本可行解不是最優(yōu)解。對應的非基變量x11進基.對應的非基變量x11進基.x11的閉回路是標負號的變量是x12、x33、x21，取運量最小值x33最小，x33是出基量，調(diào)整量=158/27/2022 銷地產(chǎn)地B1B2B3B4aiA1 589270A2364780A3 101214 540bj45655030190在x11的閉回路上x11、x32、x23分別加上15，x12、x33、x21分別減去15，并且在x33處打上記號“”作為基變量，其余變量不變，調(diào)整后得到一組新的基可行解：3030502540158/27/2022 銷地產(chǎn)地B1B2B3B4aiA1 589270A2364780A3 101214 540bj45655030190303050254015重新求所有非基變量的檢驗數(shù)得：13=3，22=0，24=7，31=1，33=4，34=1x34進基、 x14出基。調(diào)整運量得到下表： 8/27/2022再求非基變量的檢驗數(shù)：13=3，14=1，22=0，24=8，31=1，33=4所有檢驗數(shù)ij 0因而得到最優(yōu)解最小運費 銷地產(chǎn)地B1B2B3B4aiA1