設(shè)平衡運(yùn)輸問題的數(shù)學(xué)模型為：2/6/2023課件表上作業(yè)法也稱為運(yùn)輸單純形法，是直接在運(yùn)價(jià)表上求最優(yōu)解的一種方法，它的步驟是：第一步：求初始基行可行解（初始調(diào)運(yùn)方案），常用的方法有最小元素法、元素差額法（Vogel近似法）、左上角法。第二步：求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解，常用求檢驗(yàn)的方法有閉回路法和位勢(shì)法，當(dāng)非基變量的檢驗(yàn)數(shù)λij全都非負(fù)時(shí)得到最優(yōu)解，若存在檢驗(yàn)數(shù)λlk<0，說(shuō)明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。第三步：調(diào)整運(yùn)量，即換基，選一個(gè)變量出基，對(duì)原運(yùn)量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。2/6/2023課件3.3.1初始基可行解1.最小元素法最小元素法的思想是就近優(yōu)先運(yùn)送，即最小運(yùn)價(jià)Cij對(duì)應(yīng)的變量xij優(yōu)先賦值然后再在剩下的運(yùn)價(jià)中取最小運(yùn)價(jià)對(duì)應(yīng)的變量賦值并滿足約束，依次下去，直到最后一個(gè)初始基可行解。2/6/2023課件B1B2B3可發(fā)量A186730A243545A374825未滿足量603010100000【解】301510252015452020000產(chǎn)地銷地2/6/2023課件【例4】求表3－7給出的運(yùn)輸問題的初始基本可行解。

B1B2B3B4aiA1311447A277384A3121069bj365620表3－72/6/2023課件【解】

B1B2B3B4aiA1311447A277384A3121069bj3656203××60×××4×16在x12、x22、x33、x34中任選一個(gè)變量作為基變量，例如選x12表3－82/6/2023課件2．運(yùn)費(fèi)差額法（Vogel近似法）最小元素法只考慮了局部運(yùn)輸費(fèi)用最小，對(duì)整個(gè)產(chǎn)銷系統(tǒng)的總運(yùn)輸費(fèi)用來(lái)說(shuō)可能離最優(yōu)值較遠(yuǎn)。有時(shí)為了節(jié)省某一處的運(yùn)費(fèi)，而在其它處可能運(yùn)費(fèi)很大。運(yùn)費(fèi)差額法對(duì)最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運(yùn)價(jià)和次小運(yùn)價(jià)之間的差額，如果差額很大，就選最小運(yùn)價(jià)先調(diào)運(yùn)，否則會(huì)增加總運(yùn)費(fèi)。例如下面兩種運(yùn)輸方案，15151515前一種按最小元素法求得，總運(yùn)費(fèi)是Z1=10×8+5×2+15×1=105，后一種方案考慮到C11與C21之間的差額是8－2=6，如果不先調(diào)運(yùn)x21，到后來(lái)就有可能x11≠0，這樣會(huì)使總運(yùn)費(fèi)增加較大，從而先調(diào)運(yùn)x21，再是x22，其次是x12這時(shí)總運(yùn)費(fèi)Z2=10×5+15×2+5×1=85<Z1。2/6/2023課件基于以上想法，運(yùn)費(fèi)差額法求初始基本可行解的步驟是：第一步：求出每行次小運(yùn)價(jià)與最小運(yùn)價(jià)之差，記為ui，i=1,2,…,m；同時(shí)求出每列次小運(yùn)價(jià)與最小運(yùn)價(jià)之差，記為vj，j=1，2，…，n；第二步：找出所有行、列差額的最大值，即L=max{ui，vi}，差額L對(duì)應(yīng)行或列的最小運(yùn)價(jià)處優(yōu)先調(diào)運(yùn)；第三步：這時(shí)必有一列或一行調(diào)運(yùn)完畢，在剩下的運(yùn)價(jià)中再求最大差額，進(jìn)行第二次調(diào)運(yùn)，依次進(jìn)行下去，直到最后全部調(diào)運(yùn)完畢，就得到一個(gè)初始調(diào)運(yùn)方案。用運(yùn)費(fèi)差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。2/6/2023課件【例5】用運(yùn)費(fèi)差額法求表3—9運(yùn)輸問題的初始基本可行解。

B1B2B3B4aiA15891215A2672425A311013820bj201052560表3—92/6/2023課件銷地產(chǎn)地B1B2B3B4aiuiA1

5

8

9

1215A2

1

7

2

425A36

10

13

820bj201052560

vj

5××414—332200×××2/6/2023課件銷地產(chǎn)地B1B2B3B4aiuiA1

5

8

9

1215A2

1

7

2

425A36

10

13

820bj201052560

vj

5××200×××—2—44—220×1052/6/2023課件基本可行解為總運(yùn)費(fèi)Z=10×8+20×1+5×2+20×8=270。求運(yùn)輸問題的初始方案還有很多方法，如左上角法、右上角法等。常用的方法是Vogel近似法、最小元素法。2/6/2023課件【解】用最小元素法得到下列一組基本可行解【例6】求下列運(yùn)輸問題的一個(gè)初始基本可行解及其檢驗(yàn)數(shù)。矩陣中的元素為運(yùn)價(jià)Cij，矩陣右邊的元素為產(chǎn)量ai

，下方的元素為銷量bj。106040302/6/2023課件矩陣中打“×”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗(yàn)數(shù)。求λ11，先找出x11的閉回路，對(duì)應(yīng)的運(yùn)價(jià)為再用正負(fù)號(hào)分別交替乘以運(yùn)價(jià)有直接求代數(shù)和得2/6/2023課件同理可求出其它非基變量的檢驗(yàn)數(shù)：這里λ34<0，說(shuō)明這組基本可行解不是最優(yōu)解。只要求得的基變量是正確的且數(shù)目為m+n－1，則某個(gè)非基變量的閉回路存在且唯一，因而檢驗(yàn)數(shù)唯一。2/6/2023課件加入松馳變量λij將約束化為等式ui+vj+λij=cij記原問題基變量XB的下標(biāo)集合為I，由第二章對(duì)偶性質(zhì)知，原問題xij的檢驗(yàn)數(shù)是對(duì)偶問題的松弛變量λij當(dāng)（i，j）時(shí)λij=0，因而有解上面第一個(gè)方程，將ui、vj代入第二個(gè)方程求出λij。2/6/2023課件【例7】用位勢(shì)法求例7給出的初始基本可行解的檢驗(yàn)數(shù)。【解】第一步求位勢(shì)u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位勢(shì)的解為2/6/2023課件再由公式求出檢驗(yàn)數(shù)，其中Cij是非基變量對(duì)應(yīng)的運(yùn)價(jià)。計(jì)算結(jié)果與例7結(jié)果相同。2/6/2023課件3.3.3調(diào)整運(yùn)量前面講過(guò)，當(dāng)某個(gè)檢驗(yàn)數(shù)小于零時(shí)，基可行解不是最優(yōu)解，總運(yùn)費(fèi)還可以下降，這時(shí)需調(diào)整運(yùn)輸量，改進(jìn)原運(yùn)輸方案，使總運(yùn)輸減少，改進(jìn)運(yùn)輸方案的步驟是：第一步：確定進(jìn)基變量；第二步：確定出基變量，在進(jìn)基變量xik的閉回路中，標(biāo)有負(fù)號(hào)的最小運(yùn)量作為調(diào)整量θ，θ對(duì)應(yīng)的基變量為出基變量，并打上“×”以示作為非基變量。第三步：調(diào)整運(yùn)量。在進(jìn)基變量的閉回路中標(biāo)有正號(hào)的變量加上調(diào)整量θ，標(biāo)有負(fù)號(hào)的變量減去調(diào)整量θ，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗(yàn)數(shù)重新檢驗(yàn)。2/6/2023課件【例9】求下表所示的運(yùn)輸問題的最優(yōu)解。表3－6

B1B2B3產(chǎn)量A186730A243545A374825銷量603010100產(chǎn)地銷地2/6/2023課件B1B2B3產(chǎn)量A186730A243545A374825銷量60301010030151020[-1][2]25＋－＋－[-2]產(chǎn)地銷地【解】前面已得到此題的初始可行解，現(xiàn)在接著做下去。用閉回路法求檢驗(yàn)數(shù)如下：2/6/2023課件B1B2B3產(chǎn)量A186730A243545A374825銷量60301010030151020[-1][2]25＋－＋－[-2]產(chǎn)地銷地[2]【解】前面已得到此題的初始可行解，現(xiàn)在接著做下去。用閉回路法求檢驗(yàn)數(shù)如下：2/6/2023課件B1B2B3A1867A2435A374830151020[-1][2]25[-2]產(chǎn)地銷地[０]因?yàn)橛校矀€(gè)負(fù)檢驗(yàn)數(shù)，所以這組基本可行解不是最優(yōu)解。取非基變量x32進(jìn)基,用閉回路法調(diào)整如下閉回路如上圖，標(biāo)負(fù)號(hào)的運(yùn)量是：x31=25、x22=30，取其最小值25作為調(diào)整量，在閉回路上x21、x32分別加上25，x31、x22分別減去25，調(diào)整后得到一組新的基可行解。＋－＋25－

405

2/6/2023課件B1B2B3產(chǎn)量A186730A243545A374825銷量603010100540102520[-1][2]＋－＋－[2]再檢驗(yàn)（表中括號(hào)中的數(shù)字為檢驗(yàn)數(shù)）2/6/2023課件B1B2B3產(chǎn)量A186730A243545A374825銷量603010100540102520[-1][2][4]＋－＋－[2]＋－再檢驗(yàn)（表中括號(hào)中的數(shù)字為檢驗(yàn)數(shù)）2/6/2023課件B1B2B3產(chǎn)量A186730A243545A374825銷量603010100540102520[-1][2][4]＋－[2]＋－5

4515檢驗(yàn)數(shù)l12=-1,方案需調(diào)整，下面用閉回路法調(diào)整2/6/2023課件B1B2B3產(chǎn)量A186730A243545A374825銷量60301010025451015再計(jì)算一次檢驗(yàn)數(shù)（表中括號(hào)中的數(shù)字