四章運(yùn)輸問題

1、第四章運(yùn)輸問題I、基本要求教學(xué)目標(biāo)了解運(yùn)輸問題的基本原理，掌握運(yùn)輸問題表上作業(yè)法的計(jì)算方法。 能夠進(jìn)行 產(chǎn)銷平衡與產(chǎn)銷不平衡的運(yùn)輸問題的優(yōu)化安排。重點(diǎn)問題運(yùn)輸問題表上作業(yè)法的計(jì)算方法。II、基本內(nèi)容第一節(jié)運(yùn)輸問題的基本原理和表上作業(yè)法一、運(yùn)輸問題的基本原理二、運(yùn)輸問題表上作業(yè)法第二節(jié)運(yùn)輸問題優(yōu)化實(shí)例一、產(chǎn)銷平衡的運(yùn)輸問題二、產(chǎn)銷不平衡的運(yùn)輸問題III 學(xué)時(shí)分配表序號(hào)教學(xué)內(nèi)容課時(shí)分配1運(yùn)輸問題的基本原理和表上作業(yè)法22運(yùn)輸問題優(yōu)化實(shí)例2合計(jì)4IV、教學(xué)方法本章主要采取講授課外練習(xí)相結(jié)合的方法教學(xué)。第一節(jié)運(yùn)輸問題的概念和模型一、運(yùn)輸問題的概念一般運(yùn)輸問題，就是為解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干

2、個(gè)銷地， 在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的情 況下，確定使總運(yùn)輸費(fèi)用最小的方案的數(shù)學(xué)問題。二、運(yùn)輸問題數(shù)學(xué)模型例4.1某公司從兩個(gè)產(chǎn)地Al、A將物品運(yùn)往三個(gè)銷地Bi、B2、B3,各產(chǎn)地 的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示， 問：應(yīng) 如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？表4.1商品產(chǎn)銷調(diào)運(yùn)表BiB2B3產(chǎn)量Ai646200A655300銷量150150200解：兩個(gè)產(chǎn)地的總產(chǎn)量為：200+300=500 三個(gè)銷地的總銷量為150+150+200=500 總產(chǎn)量=總銷量，故稱產(chǎn)銷平衡問題。設(shè)Xj為從產(chǎn)地A運(yùn)往銷地B的運(yùn)輸量，得到下列運(yùn)輸量表:

3、表4.2商品運(yùn)量表BiB2B3產(chǎn)量AixiiX12X13200AX21X22X23300銷量150150200500根據(jù)題意可寫出如下數(shù)學(xué)模型:s.t.X11+ X12 + X13 = 200x21 + X22+ x23 = 300X11 + X21 = 150X12 + X22 = 150X13 + X23 = 200（滿足產(chǎn)地產(chǎn)量約束條件 （滿足產(chǎn)地產(chǎn)量約束條件 （滿足銷地銷量約束條件 （滿足銷地銷量約束條件 （滿足銷地銷量約束條件) ) ) ) )Min f = 6x11+4x12+6x13+6x21+5x22+5x23XjA0(i=1,2; j=1,2,3)。若設(shè)A1, A2,Am表示

4、某物資的m個(gè)產(chǎn)地；B1,B2,Bn表示某物資的n個(gè)銷地；Si表示產(chǎn)地Ai的產(chǎn)量；dj表示銷地Bj的銷量；q表示把物資從產(chǎn)地 Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)則可得如下運(yùn)價(jià)表（表4-3)。則稱該運(yùn)輸問題為產(chǎn)銷平衡問題，其一般線性規(guī)劃模型如下：設(shè)Xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，根據(jù)這個(gè)運(yùn)輸問題的要求，可 以建立一般運(yùn)輸變量表（表 4.4）。m nMin f八 ' 臚耳i d j =1s.t ' Xj _Si(i =1,2,m)j 4m、'Xij mdi(j =1,2;,n)i 4Xij _0（i =1,2- ,m; j =1,2,n）第二節(jié)運(yùn)輸問題的表上作業(yè)法一、確定基本

5、初始可行解例：某食品公司下屬的 A、A、A 3個(gè)廠生產(chǎn)方便食品，要運(yùn)送到B、B2、Ba、B 4個(gè)銷售點(diǎn)，數(shù)據(jù)如下：表4.5某食品公司商品供銷調(diào)運(yùn)資料表BB2B3產(chǎn)量aiA311310 :7A19284A374105 :9銷量bj365620求最優(yōu)運(yùn)輸方案。解：確定初始可行解主要有西北解法、最小元素法和伏格爾（Vogl ）近似法等方法。下面，我們根據(jù)教材的介紹，簡(jiǎn)述西北解法和最小元素法。（一）西北角法從西北角（左上角）格開始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然 后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷量）已滿足，貝腫把該行 （列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。如

6、上例：在變量格的左上角填入運(yùn)輸費(fèi)用，右下角準(zhǔn)備填入基變量值，劃 去的格用括號(hào)“ ”標(biāo)注（準(zhǔn)備將來填寫檢驗(yàn)數(shù)）。其求解過程如下表所示:表4.6西北角法求初始基本可行解肖地 產(chǎn)地、BB3產(chǎn)量A1331143100A1922280A7410356(9) 0銷量ooo020（產(chǎn)銷平衡）第一步:首先，從表的西北角（左上角）開始，給該單元格的變量Xn盡可能大的數(shù)值。因?yàn)槔浔硎緩漠a(chǎn)地A運(yùn)往銷地B的產(chǎn)品的數(shù)量，已知A1產(chǎn)量是7,B1的需求量是3,可以滿足Bi的全部需求，所以令 心=min73 =3其次，修改第1行的“產(chǎn)量”數(shù)據(jù)和第1列的“銷量”數(shù)據(jù)：因?yàn)楫a(chǎn)地 A 運(yùn)往銷地Bi3個(gè)單位，因此應(yīng)從當(dāng)前產(chǎn)量中減去

7、3,將其改寫為4（7-3=4）;銷地 Bi從產(chǎn)地A運(yùn)來了 3個(gè)單位，因此應(yīng)從當(dāng)前的需求量中減去 3,將其改寫為0， 即該地需求量已飽和。第三,由于銷地B需求量已滿足,不需再供應(yīng),因此,Bi列的剩余變量x21和x31 應(yīng)取值0,即這兩個(gè)單元格不再賦值，在其右下角加注“ ”，表示該兩格已被劃 去。第二步：從第二個(gè)左上角xi2開始。首先，由于第1行的產(chǎn)量（供應(yīng)量）還剩4個(gè)單 位，銷地B的需求量是6個(gè)單位，故應(yīng)令x12 = min4,® =4其次，修改第1行的“產(chǎn)量”數(shù)據(jù)和第2列的“銷量”數(shù)據(jù)：第 1行產(chǎn)地 A1當(dāng)前的產(chǎn)量是4,再供應(yīng)銷地R4個(gè)單位以后沒有剩余了，故應(yīng)修改為 0;銷 地B2原

8、需求量是6個(gè)單位，從A調(diào)來4個(gè)單位后，尚需2個(gè)單位，故應(yīng)修改為2。第三，由于第1行產(chǎn)地A的產(chǎn)量已供應(yīng)完畢，第1行剩余的兩個(gè)變量X13和X14 應(yīng)取值0,即這兩個(gè)單元格不再斌值，對(duì)其右下角加注“ ”，表示該兩格已被劃 去。第三步：從第三個(gè)左上角X22開始。首先，由于第2行的產(chǎn)量（供應(yīng)量）是4個(gè)單位,銷地B2的當(dāng)前需求量是2個(gè)單位，故應(yīng)令x22二min4,2 =2其次，修改第2行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第2列的“銷量（需求量）” 數(shù)據(jù)：第2行產(chǎn)地A的產(chǎn)量是4,供應(yīng)銷地B2個(gè)單位以后還剩余2個(gè)單位，故 應(yīng)修改為2;銷地 B當(dāng)前需求量是2個(gè)單位，從 A調(diào)來2個(gè)單位后，需求量已 滿足，故應(yīng)修改為0。第

9、三，由于銷地B2需求量已滿足,不需再供應(yīng),因此,B2列的剩余變量x32應(yīng)取值0,即這個(gè)單元格不再賦值，對(duì)其右下角加注“ ”，表示該單元格已被劃去。 第四步：從第四個(gè)左上角X23開始。首先，由于第2行的當(dāng)前產(chǎn)量（供應(yīng)量）是2個(gè) 單位，銷地B3的需求量是5個(gè)單位，故應(yīng)令x23二min5,2 =2其次，修改第2行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第3列的“銷量（需求量）” 數(shù)據(jù)：第2行產(chǎn)地A的當(dāng)前產(chǎn)量是2 ,再供應(yīng)銷地Bs2個(gè)單位以后無剩余，故 應(yīng)修改為0;銷地B3當(dāng)前需求量是5個(gè)單位，從 A2調(diào)來2個(gè)單位后，尚需3個(gè) 單位，故應(yīng)修改為3。第三，由于第2行產(chǎn)地A的產(chǎn)量（供應(yīng)量）已供應(yīng)完畢，第2行剩余的-個(gè)

10、變量X24應(yīng)取值0,即這個(gè)單元格不再賦值,對(duì)其右下角加注“ ”，表示該單元 格已被劃去。第五步：從第五個(gè)左上角X33開始。首先，由于第3行的產(chǎn)量（供應(yīng)量）是9個(gè)單位,銷地B3的當(dāng)前需求量是3個(gè)單位，故應(yīng)令x33=min9,3=3其次，修改第3行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第3列的“銷量（需求量）” 數(shù)據(jù)：第3行產(chǎn)地A的產(chǎn)量是9,供應(yīng)銷地B33個(gè)單位以后剩余6個(gè)單位，故應(yīng) 修改為6;銷地B3當(dāng)前需求量是3個(gè)單位，從A3調(diào)來3個(gè)單位后，需求已飽和， 故應(yīng)修改為0。第六步：從第六個(gè)左上角X34開始。首先，由于第3行產(chǎn)地 A3的產(chǎn)量（供應(yīng)量）還剩6個(gè)單位，銷地B4的需求量是6個(gè)單位，故應(yīng)令x34二min

11、6,6 =6其次，修改第3行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第4列的“銷量（需求量）” 數(shù)據(jù)：第3行產(chǎn)地A的當(dāng)前產(chǎn)量是6 ,再供應(yīng)銷地B36個(gè)單位以后無剩余，故 應(yīng)修改為0;銷地B4需求量是6個(gè)單位，從 A3調(diào)來6個(gè)單位后，需求已飽和， 故應(yīng)修改為0。由于這時(shí)表中已沒有未被劃掉的元素了，故求解已經(jīng)完成。填入的數(shù)據(jù)為6個(gè)，等于行數(shù)加列數(shù)減1,即3+4-仁6。該問題的一個(gè)基本可行解為：X11=3， X12 二 4，x22= 2，x23= 2，X33- 3，X34二 6，其余的兀素Xjj= 0。表4.7最小元素法求初始基本可行解銷地產(chǎn)地、BB3產(chǎn)量Ai311310043A192 18（1） 031A741

12、05(9) 063銷量000020（產(chǎn)銷平衡）（二）最小元素法最小元素法的所謂元素，是指單位運(yùn)輸價(jià)格。最小元素法的基本思路是：運(yùn)輸價(jià)格最便宜的優(yōu)先調(diào)運(yùn)。即從運(yùn)輸問題數(shù)據(jù)表（或單位運(yùn)輸價(jià)格表）中尋找最小數(shù)值，并以這個(gè)數(shù)值所對(duì)應(yīng)的變量 Xj作為第一個(gè)基變量，在該變量格內(nèi)的右下角填入允許取得的最大數(shù)。然后一直按此方法繼續(xù)下去，若某行（列）的產(chǎn)量（銷量）已滿足，則該行（列）的其他變量 Xj只能取0值或說“把該行（列）的其他格劃去，直到取得一個(gè)基本可行解為止。下面，我們?nèi)砸郧袄Y料說明 最小元素法的求解過程。解：把變量格的左上角填入運(yùn)輸價(jià)格，右下角準(zhǔn)備填寫基變量的值，劃去的 格用中括號(hào)“ ”來標(biāo)注（準(zhǔn)備

13、將來填寫檢驗(yàn)數(shù)）。第一步：首先，從運(yùn)價(jià)最小（C2i=1）的變量x21開始分配運(yùn)輸量，并使x21取盡可能大 的數(shù)值。因?yàn)閤21表示從產(chǎn)地A往銷地Bi運(yùn)送產(chǎn)品的數(shù)量，已知Bi的需求量是3 個(gè)單位，而A的產(chǎn)量是4個(gè)單位，可以滿足B的全部需求，所以令X21 =mi n（4,3） =3。其次，修改第2行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第1列的“銷量（需求量）” 數(shù)據(jù)：因?yàn)楫a(chǎn)地A的產(chǎn)量是4個(gè)單位，供應(yīng)B3個(gè)單位后尚剩余1個(gè)單位，故應(yīng) 將4修改為1;銷地B1的需求量是3個(gè)單位，已從產(chǎn)地A得到滿足，不再需要供 應(yīng)，因此應(yīng)將3修改為0。第三，由于銷地B1的需求量已得到滿足，第1列的其余兩個(gè)變量x,1和X31均應(yīng)取0值

14、，分別加注 第二步：首先，給運(yùn)價(jià)最?。–23=2）的變量X23分配運(yùn)輸量，并使X23取盡可能大的數(shù) 值。因?yàn)?表示從產(chǎn)地A往銷地E3運(yùn)送產(chǎn)品的數(shù)量，已知B3的需求量是5個(gè)單 位，而A的當(dāng)前產(chǎn)量只有1個(gè)單位，所以令x23 =min（1,3）=1其次，修改第2行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第3列的“銷量（需求量）” 數(shù)據(jù)：因?yàn)楫a(chǎn)地 A的當(dāng)前產(chǎn)量是1個(gè)單位，供應(yīng) E3后已無剩余，故應(yīng)將1修改 為0;銷地B3的需求量是5個(gè)單位，已從產(chǎn)地 A得到1個(gè)單位，因此應(yīng)將5修 改為4。第三，由于產(chǎn)地A的產(chǎn)量已分配完畢，第2行尚未分配的兩個(gè)變量X22和X24 均應(yīng)取0值，分別加注“ ”表示劃去。第三步：首先，給運(yùn)價(jià)

15、最?。℅a=3）的變量X13分配運(yùn)輸量，并使X13取盡可能大的數(shù) 值。因?yàn)閄13表示從產(chǎn)地A往銷地B3運(yùn)送產(chǎn)品的數(shù)量，已知B3當(dāng)前的需求量是4 個(gè)單位，而A的產(chǎn)量是7個(gè)單位，所以令x13二min（7,4）=4其次，修改第1行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第3列的“銷量（需求量）” 數(shù)據(jù)：因?yàn)楫a(chǎn)地A的產(chǎn)量是7個(gè)單位，供應(yīng)B4個(gè)單位后剩余3,故應(yīng)將7修改 為3;銷地B3的當(dāng)前需求量4個(gè)單位，已從產(chǎn)地A得到滿足，因此應(yīng)將4修改為 0。第三，由于銷地R的需求量已得到滿足，不再需要分配，所以第 3列尚未分配的變量X33應(yīng)取0值，加注“ ”表示劃去。第四步:首先，給運(yùn)價(jià)最小（G2=4）的變量x32分配運(yùn)輸量，

16、并使x32取盡可能大的數(shù) 值。因?yàn)閤32表示從產(chǎn)地A往銷地R運(yùn)送產(chǎn)品的數(shù)量，已知 R的需求量是6個(gè)單位，A的產(chǎn)量是9個(gè)單位，所以令x32=min（9,6） = 6其次，修改第3行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第2列的“銷量（需求量）” 數(shù)據(jù)：因?yàn)楫a(chǎn)地A的產(chǎn)量是9個(gè)單位，供應(yīng)R6個(gè)單位后剩余3個(gè)單位，故應(yīng)將 9修改為3;銷地B2的需求量是6個(gè)單位，從產(chǎn)地A得到6個(gè)單位后已滿足，因 此應(yīng)將6修改為0。第三，由于銷地E 2的需求量已得到滿足，所以第2列尚未確定分配的變量X12應(yīng)取0值，加注“ ”表示劃去。第五步：首先，給運(yùn)價(jià)最?。℅4=5）的變量X34分配運(yùn)輸量，并使X34取盡可能大的數(shù) 值。因?yàn)閄34

17、表示從產(chǎn)地A往銷地B運(yùn)送產(chǎn)品的數(shù)量，已知 b的當(dāng)前需求量是6個(gè)單位，A的當(dāng)前產(chǎn)量是3個(gè)單位，所以令x34二min（3,6） = 3。其次，修改第3行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第4列的“銷量（需求量）” 數(shù)據(jù)：因?yàn)楫a(chǎn)地Ab的當(dāng)前產(chǎn)量是3個(gè)單位，供應(yīng) B2 3個(gè)單位后已無剩余，故應(yīng) 將3修改為0;銷地B4的需求量是6個(gè)單位，從產(chǎn)地A得到3個(gè)單位后還需要3 個(gè)單位，因此應(yīng)將6修改為3。第六步：首先，給運(yùn)價(jià)最?。–4=10）的變量X14分配運(yùn)輸量，并使X14取盡可能大的 數(shù)值。因?yàn)閤14表示從產(chǎn)地Ai往銷地B運(yùn)送產(chǎn)品的數(shù)量，已知B4的當(dāng)前需求量是3個(gè)單位，A的當(dāng)前產(chǎn)量是3個(gè)單位，所以令 4二min（3

18、,3） = 3。其次，修改第1行的“產(chǎn)量（供應(yīng)量）”數(shù)據(jù)和第4列的“銷量（需求量）” 數(shù)據(jù)：因?yàn)楫a(chǎn)地 Ai的當(dāng)前產(chǎn)量是3個(gè)單位，供應(yīng) B 3個(gè)單位后已無剩余，故應(yīng) 將3修改為0;銷地 B的當(dāng)前需求量是3個(gè)單位，從產(chǎn)地 A】得到3個(gè)單位后已 飽和，因此應(yīng)將3修改為0。至此，基本可行解計(jì)算表中已無未被分配或劃去的變量，故求解結(jié)束。這時(shí)的基本可行解為：X21 =3， X23 =1，為3 =4， X32 =6， X34 =3， X14 =3，其余的元素 Xj =0。二、基本可行解的最優(yōu)性檢驗(yàn)檢查的方法與單純形方最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目標(biāo)要求極小，

19、因此，當(dāng)所有的檢驗(yàn)數(shù)都 大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào)整。下面介紹兩種求檢驗(yàn)數(shù)的方法：閉回路法和位勢(shì)法（一）閉回路法為了方便，我們以表4.7給出的初始基本可行解方案為例，考察初始方案的 任意一個(gè)非基變量，比如X24。根據(jù)初始方案，產(chǎn)地 A2的產(chǎn)品是不運(yùn)往銷地B4 的。如果現(xiàn)在改變初始方案，把 A的產(chǎn)品運(yùn)送1個(gè)單位給B4，那么為了保持 產(chǎn)銷平衡，就必須使X 14或X 34減少1個(gè)單位；而如果X 14減少1個(gè)單位，第 1行的運(yùn)輸量就必須增加1個(gè)單位，例如X13增加1個(gè)單位，那么為了保持產(chǎn) 銷平衡，就必須使X23減少1個(gè)單位。這個(gè)過程就是尋找一個(gè)以非基變量 X24為

20、起始頂點(diǎn)的閉回路一 X 24，X14， X13，X23 ，這個(gè)閉回路的其他頂點(diǎn)均為基變量（對(duì)應(yīng)著填上數(shù)字的格）。容易計(jì) 算出上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 8 - 10 + 3- 2 = -1 ，即總的運(yùn)費(fèi) 減少1個(gè)單位，這就說明原始方案不是最優(yōu)方案，可以進(jìn)行調(diào)整以得到更好的可以證明，如果對(duì)閉回路的方向不加區(qū)別（即只要起點(diǎn)及其他所有頂點(diǎn)完全 相同，而不區(qū)別行進(jìn)方向），那么以每一個(gè)非基量為起始頂點(diǎn)的閉回路就存在而 且唯一。因此，對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。表4.8中用多邊形畫出的是以非基變量 X22為起始頂點(diǎn)的閉回路。表4.8以非基變量X22為起始頂點(diǎn)的閉回路銷地產(chǎn)

21、地B1B2B3B4產(chǎn)量A1311310743A21928431|A374105963銷量365620（產(chǎn)銷平衡）可以計(jì)算出以非基變量X22為起始頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為9-2 + 3- 10 + 5- 4 = 1即總的運(yùn)費(fèi)增加1個(gè)單位，這就說明這個(gè)調(diào)整不能改善目標(biāo)值。從上面的討論可以看出，當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí)，有若干個(gè)基變量 的取值受其影響。這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì)算出它們對(duì)目標(biāo)函數(shù)的綜 合影響，其作用與線性規(guī)劃單純形方法中的檢驗(yàn)數(shù)完全相同。 故也稱這個(gè)綜合影 響為該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)。上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為 二24 = -1 ， 22

22、 = 1。閉回路方法原理就是通過尋找閉回路來找到非基變量的檢驗(yàn)數(shù)。如果規(guī)定作為起始頂點(diǎn)的非基變量為第 1個(gè)頂點(diǎn)，閉回路的其他頂點(diǎn)依次為 第2個(gè)頂點(diǎn)、第3個(gè)頂點(diǎn)那么就有：G =（閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和）-（閉回路上的偶數(shù)次頂點(diǎn)單 位運(yùn)費(fèi)之和），其中ij為非基變量的下角指標(biāo)。按上述作法，可計(jì)算出表1的所有非基變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號(hào)內(nèi)，如圖4.9所示。二 11=3-1+2-3=1,亍2=11-4+5-10=2匚22=9-4+5-10+3-2=1；24=8-10+3-2=-16=7-5+10-3+2-1=10匚 33=10-3+10-5=12表4.9初始基本可行解及檢驗(yàn)數(shù)肖

23、地產(chǎn)地'B1B2B3B4產(chǎn)量A131112341037A21391218-14A3710461012539銷量365620（產(chǎn)銷平衡）顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)， 現(xiàn)行的調(diào)運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都 會(huì)產(chǎn)生困難。（二）位勢(shì)法第一步，計(jì)算位勢(shì)值所謂位勢(shì)法，就是對(duì)運(yùn)輸表上的每一行賦予一個(gè)數(shù)字Ui ,對(duì)每一列賦予一個(gè)數(shù)字Vj ,使它們的和等于其所對(duì)應(yīng)單元格的運(yùn)輸價(jià)格,即：Ui+Vj=Cj （i=1,2,m;j=1,2,n）這些Ui和Vj分別稱為第i行和第j列的位

24、勢(shì)，它們的數(shù)值是相互關(guān)聯(lián)的，填 寫時(shí)可任意給定其中的一個(gè)數(shù)值。下面，我們?nèi)杂们袄?jì)算位勢(shì)值。第一步，作位勢(shì)計(jì)算表。仿照前面已計(jì)算制作的調(diào)運(yùn)方案表作一新表，將表 中調(diào)運(yùn)量數(shù)值換成相應(yīng)的運(yùn)輸價(jià)格數(shù)值（見下表）：表4.10運(yùn)輸問題表上作業(yè)位勢(shì)計(jì)算表銷地 產(chǎn)地、B1B2B3B4UiA13105A2124A3450Vj-34-25第二步，計(jì)算位勢(shì)值。假設(shè)從基變量Xu開始，給定U1=5，則應(yīng)有:U1+V4=C14=10，所以 V4=C14-u 1=10-5=5;U1+V3=C13=3， 所以 V3=C13-u 1=3-5=-2 ;U3+V4=C34=5， 所以 U3=C34-V4=5-5=0 ；U2+V3

25、=C23=2，以 U2=C23-V 3=2-（-2）=4 ；U2+V1=C21=1， 所以 V1=C21-U2=1-4=-3 ;U3+V2=C32=4， 所以 V2=C32-U3=4-0=4 ；第二步，計(jì)算非基變量的檢驗(yàn)數(shù)現(xiàn)在，我們來計(jì)算各空格（非基變量）的檢驗(yàn)數(shù)。令二4代表空格（A,B4）的檢驗(yàn)數(shù)，由閉回路計(jì)算可知：二4= C24-C 14+C13-C23=C24-（U 1+V4）+（U l+V3）-（ U 2+V3）= C 24- U 2-V 4 ；同理：C31 = C31-C 34+C14-C 13+C23-C 21=C31-（U 3+V4）+ （U 計(jì)V4）-（U l+V3）+ （U

26、2+V3）-（U 2+Vl）=C 31-U 3-V 1總結(jié)以上兩例可知：Cj是空格（A,Bj）所對(duì)應(yīng)的單位運(yùn)輸價(jià)格；（Ui+Vj）恰 好就是該空格所在行的位勢(shì)和所在列的位勢(shì)之和，于是，我們可概括出任一空格檢驗(yàn)數(shù)的計(jì)算公式為：Cij =Cij -U i -V j，如二24=C24- U 2-V 4，:二31= C 31- U 3-V 1 o依據(jù)上述資料，根據(jù)該計(jì)算公式可求得：11= C 11 U1 V1=3-5-（-3）=112= C 12 U1 V2=11-5-4=2C22= c 22 - U2 - V2=9-4-4=1C24= C 24 U2 V4=8-4-5=-1二31= c 31 - U

27、3 - V1=7-0-（-3）=10-33= C 33 U3 - V3=10-0-（-2）=12由于檢驗(yàn)數(shù)還有負(fù)數(shù)，所以這個(gè)可行解不是最優(yōu)解，需要找新的基本可行解， 使費(fèi)用不高于當(dāng)前的基本可行解。三、求新的基本可行解當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基本可行解不是最優(yōu)解。在這種情況下，應(yīng)該對(duì)基本可行解進(jìn)行調(diào)整，即找到一個(gè)新的基本可行解使目標(biāo)函 數(shù)值下降，這一過程通常稱為換基（或主元變換）過程。在運(yùn)輸問題的表上作業(yè)法 中，換基的過程是如下進(jìn)行：首先,選負(fù)檢驗(yàn)數(shù)中最小者6，那么Xrk為主元，作為進(jìn)基變量（本例為X24 ） o在本例中只有一個(gè)負(fù)檢驗(yàn)數(shù)二24=-1其次,以Xrk為起點(diǎn)找一條閉回

28、路，除Xrk外其余頂點(diǎn)必須為基變量格（如本 例以X24為起點(diǎn)的閉回路）。這里所謂閉回路，是指從一個(gè)非基變量所在格出發(fā)， 沿水平或垂直方向前進(jìn)，遇到代表基變量的填入數(shù)字的格才向左或向右90°繼續(xù)前進(jìn)，直到回到出發(fā)的那個(gè)格。如本例從X24出發(fā)，垂直向上，遇X14向左900繼續(xù)前進(jìn)，遇X13后再轉(zhuǎn)彎900 垂直向下前進(jìn)，遇X23后再向右900轉(zhuǎn)彎，最后回到變量X24所在格（見下表）：表4.11初始調(diào)運(yùn)方案調(diào)整表產(chǎn)地、B1B2B3B4產(chǎn)量A14(+1)3(-1)7A231(-1)(+1)4A3639銷量365620（產(chǎn)銷平衡）第三，為閉回路的每一個(gè)頂點(diǎn)編序號(hào)，Xrk為1，沿一個(gè)方向（順時(shí)針或

29、逆時(shí)針）依次給各頂點(diǎn)標(biāo)號(hào)。如本例X24為1，X14為2，X13為3，X23為4。第四，取閉回路偶數(shù)頂端調(diào)運(yùn)量的最小值作入基變量值本例為：X24=min（3,1）=1第五，為保持產(chǎn)銷平衡，把所有閉回路上偶數(shù)頂端的調(diào)運(yùn)量都減去一個(gè)入基變量值，所有閉回路上奇數(shù)頂端的調(diào)運(yùn)量都加上一個(gè)入基變量值（見上表），這樣便得到調(diào)整后的方案。調(diào)整后的方案如下表所示：表4.12調(diào)整后的調(diào)運(yùn)方案表產(chǎn)地B1B2B3B4產(chǎn)量A1527A2314A3639銷量3656通過調(diào)整得到的最優(yōu)方案是：Ai產(chǎn)地運(yùn)5噸到銷地B3,運(yùn)2噸給銷地B4；A2產(chǎn)地運(yùn)3噸到銷地B1,運(yùn)1噸給銷地B;A3產(chǎn)地運(yùn)6噸到銷地B2,運(yùn)3噸給銷地B; 這時(shí)

30、總運(yùn)費(fèi)最低，其運(yùn)費(fèi)為85百元，即：最優(yōu)方案運(yùn)費(fèi)=5X 3+2X 10+3X 1+1 X 8+6X 4+3X 5=85。本例只有一個(gè)負(fù)檢驗(yàn)數(shù)，故求解至此就結(jié)束，如果有若干負(fù)檢驗(yàn)數(shù)，則需 重復(fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解。四、產(chǎn)銷不平衡問題的處理 在實(shí)際中遇到的運(yùn)輸問題常常不是產(chǎn)銷平衡的，而是下列的一般運(yùn)輸問題模型：m nMin f _ qXjji j dns.t 送 Xij 蘭 s(i =1,2,m)j m m' Xij <dj(j =1,2,n)i AXij -0(i =1,2,m; j =1,2,n)我們已經(jīng)介紹過，可以通過增加虛設(shè)產(chǎn)地或銷地（加、減松弛變量）把問

31、題 轉(zhuǎn)換成產(chǎn)銷平衡問題，下面分別來討論。（一）產(chǎn)量大于銷量的情況mn考慮7 s八dj的運(yùn)輸問題，得到的數(shù)學(xué)模型為i ±j 3Minm nf _ Cj Xjjij Ts.t 瓦 Xij 蘭 s(i =1,2,m)j 4mXj 乞 dj(j =1,2廠，n)i 4Xj _0(i =1,2, ,m; j =1,2廠,n)只要在模型中的產(chǎn)量限制約束(前m個(gè)不等式約束)中引入m個(gè)松馳變量Xi (i=1,2，,m)即可，變?yōu)椋簄Z Xj +Xg = s(i =1,2,m)j 4然后，虛設(shè)一個(gè)銷地Bn 1，它的銷量為：mnbn 1 S 二 dji =1j =1這里松馳變量Xn卅可以視為從產(chǎn)地A運(yùn)往

32、銷地Bn卅的運(yùn)輸量，由于實(shí)際并不運(yùn)輸，它們的運(yùn)輸費(fèi)用Cin .1 =0(i=1,2,m),于是這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn) 銷平衡的問題。例4.5 某公司從兩個(gè)產(chǎn)地 A、A將物品運(yùn)往三個(gè)銷地 B、B2、B3,各產(chǎn)地 的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？表4.16運(yùn)輸費(fèi)用表產(chǎn)地B1B2B3產(chǎn)量A13151278Ar 11292245銷量533625(產(chǎn)銷不平衡)解：這里，總產(chǎn)量78+45=123,總銷量為53+36+25=114產(chǎn)銷不平衡，因此,應(yīng)該虛設(shè)一個(gè)銷地，于是得到虛設(shè)銷地的產(chǎn)銷平衡運(yùn)輸費(fèi)用表4.17。1. 用最小元素法求初始基

33、本可行解將運(yùn)輸費(fèi)用表中的運(yùn)輸價(jià)格放在各相應(yīng)單元格的左上角，右下角準(zhǔn)備填寫 基變量值，劃去的單元格用“ ”表示。表4.17運(yùn)輸費(fèi)用表產(chǎn)地B1B2B3呂產(chǎn)量A131512078Ar 11:2922 :045銷量5336259123(產(chǎn)銷平衡)表4.18最小元素法初始基本可行解地產(chǎn)地7BB2B3B4產(chǎn)量A1315120(78)(53)(45)836259(9)0A114529220(45)0銷量(53)(8)0(36)0(25)0(9)0123（產(chǎn)銷平衡）第一步,令x21 = min45,53 = 45 ,將銷地B的銷量53改為8 ,將產(chǎn)地A的產(chǎn)量45改為0;由于產(chǎn)地A的產(chǎn)量已分配完，故劃去第2行剩

34、余單元格（即劃去X22、x23、X24 ）（以注“ ”表示劃去）第2步，令x,3二min78,2$ =25,將銷地B3的銷量25改為0,將產(chǎn)地Ai的產(chǎn) 量78改為53;第3步，令冷=min53,8 =8,將銷地Bi的銷量8改為0,將產(chǎn)地A的產(chǎn)量53 改為45。第4步，令x,2 =min45,36 =36,將銷地B2的銷量36改為0,將產(chǎn)地Ai的產(chǎn) 量45改為9。第5步，令&二min9,9二9，將銷地印的銷量9改為0,將產(chǎn)地A的產(chǎn)量9 改為0。2. 用閉回路法檢驗(yàn)基本可行解是否最優(yōu)解非基變量X22的閉回路為：X22-； X21-；心一；x12 ，其檢驗(yàn)數(shù)22 =29-11+13-15=1

35、6;非基變量X23的閉回路為：他一X1L X21 ，其檢驗(yàn)數(shù)-23 =22-12+13-11=12。非基變量x24的閉回路為：x24； x14-；冷；x21，其檢驗(yàn)數(shù)二24 =0-0+13-11=2。由于檢驗(yàn)數(shù)無負(fù)數(shù)，所以，此基本可行解就是最優(yōu)解。其解為：冷=8， X|2 = 36， x13 = 25， x14 = 9 （虛設(shè)），x21 = 45。即從產(chǎn)地A調(diào)8個(gè)單位到銷地B，調(diào)36個(gè)單位到銷地B2,調(diào)25個(gè)單位到 銷地Ba,調(diào)9個(gè)單位到銷地B,（實(shí)際上等于庫存9個(gè)單位）；從產(chǎn)地A2調(diào)45個(gè)單 位到銷地B。這時(shí)運(yùn)費(fèi)最少，其運(yùn)輸費(fèi)用是：運(yùn)輸費(fèi)用=8X 13+36X 15+25X 12+45X 1

36、1=1439課堂練習(xí)：已知A、A、A三個(gè)產(chǎn)地的產(chǎn)量依次是 3500、3250和3750,要 供應(yīng)的B、B2> R、B4四個(gè)銷地的需求量依次是 1500、2000、2500和3500,并 知各產(chǎn)地運(yùn)往各銷地單位產(chǎn)品的運(yùn)輸價(jià)格如下表所示，試確定調(diào)運(yùn)費(fèi)用最少的運(yùn)輸方案。運(yùn)輸價(jià)格表銷地 產(chǎn)地'BBB3B4產(chǎn)量A151822263500A212516233250A14P 192024 n3750銷量1500200025003500（產(chǎn)銷不平衡）解：1.虛設(shè)銷地R將此問題轉(zhuǎn)化成產(chǎn)銷平衡問題。 列產(chǎn)銷平衡運(yùn)輸問題求解表如下：2.求初始基本可行解第一步，令x31=min375Q150CJ =15

37、00;將產(chǎn)地 A的產(chǎn)量改為2250,銷地B1的銷量改為0 ;由于銷地的銷量已滿足，第1列其它單元格應(yīng)劃去（注“口”。第二步，令x23二min3250,250C =2500;將產(chǎn)地A的產(chǎn)量改為750,銷地B3的銷量改為0 ;由于銷地B3的銷量已滿足，第3列其它單元格應(yīng)劃去（注“口”。第三步，令x12 =min3500,200C =2000;將產(chǎn)地A的產(chǎn)量改為1500,最小元素法初始基本可行解B1B2RBB5產(chǎn)量A151822260(3500)(1500)-1 1200035001000(1000)0A212516230(3250)(750)0811025007501A141920240(3750

38、) (2250)150033225010銷(1500)(2000)(2500)(3500)(1000)10500量000(2750)(500)00銷地B2的銷量改為0 ;由于銷地B2的銷量已滿足，第2列其它單元格應(yīng)劃去（注第四步，令x24二min750,350Q =750;將產(chǎn)地A的產(chǎn)量改為0,銷地B4的銷 量改為2750;由于產(chǎn)地A的產(chǎn)量已分配完，劃去第2行尚未分配的單元格（X25）， 表示不再分配。第五步，令x34二min 2250,275（ =2250;將產(chǎn)地A3的產(chǎn)量改為0,銷地B4 的銷量改為500;由于產(chǎn)地A的產(chǎn)量已分配完，劃去第 3行尚未分配的單元格(X35)，表示不再分配。第六

39、步，令Xgmin1500,50CJ =500;將產(chǎn)地A的產(chǎn)量改為1000,銷地B 的銷量改為0。第七步，令x15二min1000,100C =1000;將產(chǎn)地 A的產(chǎn)量改為0 ,銷地B5 的銷量改為0。得初始基本可行解為：x12 = 2000, x14 = 500 , x15 =1000 (虛設(shè))，x23 = 2500 , x24 = 750 , x31 =1500X34 = 2250。3. 用閉回路法對(duì)初始基本可行解進(jìn)行檢驗(yàn)以非基變量x11為起點(diǎn)的閉回路為心一；x14-； x34-； x31 ,檢驗(yàn)數(shù)；11 =15 -26 24 -14 - -1 ;以非基變量x21為起點(diǎn)的閉回路為X21 r

40、 X24 X34 x31 ,檢驗(yàn)數(shù)；21 =21 -23 24 -14 = 8;以非基變量x22為起點(diǎn)的閉回路為x22>x12>x14>x24,檢驗(yàn)數(shù)二 22 =25-18 26 -23 = 10 ;以非基變量X32為起點(diǎn)的閉回路為X32 -； X34 -； X|4 -； X12 ,檢驗(yàn)數(shù)；二2 =19 _24 26 _18=3;以非基變量X13為起點(diǎn)的閉回路為X13r X14r X24r X23 ,檢驗(yàn)數(shù)；13 =22 _26 23_16 =3;以非基變量X33為起點(diǎn)的閉回路為X33 “ X23X24 " X34 ,檢驗(yàn)數(shù)33 =20-16 23 -24 =3。以

41、非基變量X25為起點(diǎn)的閉回路為X25 “ X15 X14 X24 ,檢驗(yàn)數(shù)；25 =0_0 26 _23 = 3。以非基變量X35為起點(diǎn)的閉回路為X35>X15>X14>X34,檢驗(yàn)數(shù)25 =0-0 * 26 - 24 二 2 o將檢驗(yàn)數(shù)填入相應(yīng)的非基變量單元格的中括弧中。由于檢驗(yàn)數(shù)1 =-1說明此基本可行解不是最優(yōu)解，還需要進(jìn)行調(diào)。4. 通過調(diào)整求最優(yōu)解以閉回路Xu > X4 > X34 > x“的偶數(shù)頂點(diǎn)上調(diào)運(yùn)量的最小數(shù)為調(diào)整量，即以min 500,1500 =500為調(diào)整量。在此閉回路的奇數(shù)頂點(diǎn)上都加一個(gè)調(diào)整量，偶數(shù) 頂點(diǎn)上都減去一個(gè)調(diào)整量。銷地 產(chǎn)地

42、B1B3B5產(chǎn)量A+5002000500-50010003500A25007503250A1500-5002250+5003750銷量1500200025003500100010500調(diào)整后的調(diào)運(yùn)方案如下:產(chǎn)地 銷地、B1B2B4產(chǎn)量A1500200010003500A25007503250A100027503750銷量1500200025003500100010500由于只有一個(gè)檢驗(yàn)數(shù)為負(fù)數(shù)且已調(diào)整了其相應(yīng)的調(diào)運(yùn)量，故此方案已為最優(yōu) 解，其解為：x11 =500，x12 = 2000, , & 二 1000 （虛設(shè)），x23 二 2500 , x24 = 750 , x31 = 10

43、00，X34 = 2750 o即從產(chǎn)地A1調(diào)往銷地B500個(gè)單位、B2 2000個(gè)單位、B51000個(gè)單位（虛設(shè)）; 從產(chǎn)地 A調(diào)往銷地B3 2500個(gè)單位、B4750個(gè)單位；從產(chǎn)地 As調(diào)往銷地Bi 1000 個(gè)單位、B2750個(gè)單位。這樣既可滿足銷售需要，又可使運(yùn)輸費(fèi)用最少。這時(shí)運(yùn) 輸費(fèi)用是：運(yùn) 輸費(fèi)用=500 X 15+2000 X 18+2500 X 16+750 X 23+1000 X 14+2750 X 24=180750（二）銷量大于產(chǎn)量的情況mn考慮7 S八dj的運(yùn)輸問題，得到的數(shù)學(xué)模型為i ±j ziMinm nf HCj Xiji d j=1ns.tXij =s(

44、i =1,2, ,m)j 4 mXj 乞 dj(j =1,2廠，n)i 4Xj _0(i =1,2, ,m; j =1,2廠,n)只要在模型中的銷量限制約束(后 n個(gè)不等式約束)中引入n個(gè)松馳變量Xm ij (j=1,2，,n )即可，變?yōu)?mv XijXm .ij =dj( j =1,2,n)i =1然后，虛設(shè)一個(gè)產(chǎn)地Am 1 ,它的銷量為:nmam d dj -.二.Sj£i A這里松馳變量Xm1j可以視為從產(chǎn)地Am1運(yùn)往銷地Bj的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)Cm .ij =0 (j=1,2，,n ).于是這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn) 銷平衡的問題。例4.6某公司從Ai、

45、A將物品運(yùn)往三個(gè)銷地B、B2、B3，各產(chǎn)地的產(chǎn)量、各 銷地的銷量和各產(chǎn)地運(yùn)往銷地每件物品的運(yùn)費(fèi)如表 4.19所示，冋應(yīng)如何調(diào)運(yùn)可 使總運(yùn)輸費(fèi)用最??？表4.19運(yùn)輸費(fèi)用表產(chǎn)地7BB2B3產(chǎn)量A13151278A211292245銷量533665(產(chǎn)銷不平衡)解：1.虛設(shè)產(chǎn)地構(gòu)建產(chǎn)銷平衡運(yùn)輸費(fèi)用表這里總產(chǎn)量是78+45=123,總銷量為53+36+65=154,產(chǎn)銷不平衡，因此應(yīng)該增加一個(gè)虛設(shè)的產(chǎn)地，得到表4.20所示的產(chǎn)銷平衡的運(yùn)輸費(fèi)用表表4.20虛設(shè)產(chǎn)地后的運(yùn)輸費(fèi)用及調(diào)運(yùn)量分配表銷地產(chǎn)地B1B2B3產(chǎn)量A131512(78)(13 )(5) 08565A2114529162212(45)0A0

46、203103(31)0銷量(53)(8)0(36)(31)(65)0154 （產(chǎn)銷平衡）2.求基本初始可行解第一步,令Xr =min 45,5可=45,將產(chǎn)地A?的產(chǎn)量45改為0,將銷地B的銷 量53改為8,由于產(chǎn)地A的產(chǎn)量已分配完,劃去第2行尚未分配的單元格（注“ ”）；第二步，令$ =min 78,65 =65，將產(chǎn)地A的產(chǎn)量78改為13,將銷地比的銷量65改為0,由于銷地B3的銷量已滿足，劃去第3列尚未分配（或劃去）的單元格（注“ ”）；第三步，令Xu =min13,8 =8,將產(chǎn)地A的產(chǎn)量13改為5,將銷地的銷量8 改為0,由于銷地B的銷量已滿足，劃去第1列尚未分配（或劃去）的單元格（

47、注“ ”）；第四步，令X12=min5,36=5,將產(chǎn)地A的產(chǎn)量5改為0,將銷地B?的銷量36改為31;第五步，令心二min31,31 =31,將產(chǎn)地A的產(chǎn)量31改為0,將銷地B?的銷量31改為0。3.用閉回路法對(duì)初始基本可行解進(jìn)行檢驗(yàn)以非基變量X31為起點(diǎn)的閉回路為X31 X11 - X12 X32 ,檢驗(yàn)數(shù) 嘉=0-13 15-0 =2 ;以非基變量X22為起點(diǎn)的閉回路為X22 “ X12rX21 ,檢驗(yàn)數(shù)二 22 =29-15 13-11 =16 ;以非基變量X23為起點(diǎn)的閉回路為X23r X13r X“r X21 ,檢驗(yàn)數(shù)二 23 =22 -12 13 -11 =12 ;以非基變量X3

48、3為起點(diǎn)的閉回路為X33X32 ,檢驗(yàn)數(shù)-33 =0 -12 15-0 =3。將各檢驗(yàn)數(shù)填入調(diào)運(yùn)量分配表中相應(yīng)的非基變量單元格的中括號(hào)（“口”中。由于所有檢驗(yàn)數(shù)已無負(fù)數(shù)，所以，此基本可行解已是最優(yōu)解。最優(yōu)調(diào)運(yùn)方 案如下表所示：表4.21最優(yōu)調(diào)運(yùn)方案表銷地產(chǎn)地BB2B3產(chǎn)量A856578A4545A31銷量5336 （其中虛設(shè)31,實(shí) 際調(diào)運(yùn)量5）65即由A產(chǎn)地向銷地Bi調(diào)運(yùn)8個(gè)單位、B2調(diào)運(yùn)5個(gè)單位、B3調(diào)運(yùn)65個(gè)單位； 由A2產(chǎn)地向銷地Bi調(diào)運(yùn)45個(gè)單位；由虛設(shè)的 A產(chǎn)地向銷地B2調(diào)運(yùn)31個(gè)單位， 即從運(yùn)輸費(fèi)用最少的角度考慮，產(chǎn)量缺口應(yīng)安排在銷地 B2。這時(shí)，運(yùn)輸總費(fèi)用 是：運(yùn)輸費(fèi)用=8X

49、13+5X 15+12X 65+45X 1仁 1454第三節(jié)運(yùn)輸問題的應(yīng)用例4.7 有A1、A2、A3三個(gè)生產(chǎn)某種物資的基地，五個(gè)地區(qū) B1、B2、B3 B4、B5對(duì)這種物資有需求。現(xiàn)將該種物資從三個(gè)產(chǎn)地運(yùn)往五個(gè)需求地區(qū)，各產(chǎn) 地的產(chǎn)量和各需求地區(qū)的需要量及運(yùn)輸價(jià)格如下表所示。其中B2地區(qū)的115單位必須滿足。問應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。勘?.22運(yùn)輸價(jià)格及運(yùn)量表需求地生產(chǎn)地B1B2B3B4B5產(chǎn)地aiA1101520204050A22040153030100A330r 35405525130需求量bj25115603070（產(chǎn)銷不平衡）解：由于產(chǎn)量小于需求量，因此需要虛設(shè)一個(gè)產(chǎn)地A4,它

50、的產(chǎn)量是:（25+115+60+30+70 -（50+100+130）=20,但虛設(shè)產(chǎn)量由于不能真正運(yùn)輸，故其 運(yùn)輸費(fèi)用為0。又因?yàn)锽2的115單位必須滿足，所以不能有物資從A4運(yùn)往B2地區(qū)，于是 取相應(yīng)的運(yùn)輸價(jià)格為M（M是一個(gè)充分大的正數(shù)），以保證在求最小費(fèi)用的前提 下，該變量的值為0。于是，根據(jù)題意可建立如下產(chǎn)銷平衡運(yùn)輸價(jià)格和運(yùn)量表。表4.23產(chǎn)銷平衡運(yùn)輸價(jià)格和運(yùn)量表生產(chǎn)地B1B2B3B4B5產(chǎn)地aiA1101520204050A22040153030100A33035405525130A40M00020需求量bjP 25P 115603070300（產(chǎn)銷平衡）解：1.求初始基本可行解表4.24基本初始可行解計(jì)算表需求地 生產(chǎn)地B1B2B3B4B5產(chǎn)地aiA11015202040(50)2525-10=1525+10=3530-535A22040153030(100)(40)+10010-10=0(10)0-15 6030A33035405525(130)(40)0090-10=80303040+10=50A40M0 0020M20-5 -100需求量bj(25)0(115)(90)0(60)0(30)0(70)(30)(20)0第一步，令心=min50,25 =25,將產(chǎn)地A的產(chǎn)量50改為25,