運籌學(xué)3.運輸問題

1、1第三章第三章 運輸問題運輸問題本章主要內(nèi)容本章主要內(nèi)容： 運輸問題的數(shù)學(xué)模型運輸問題的數(shù)學(xué)模型 運輸問題的求解運輸問題的求解表上作業(yè)法表上作業(yè)法 運輸問題應(yīng)用運輸問題應(yīng)用建模建模2 第一節(jié)第一節(jié) 運輸問題的數(shù)學(xué)模型運輸問題的數(shù)學(xué)模型 第二節(jié)第二節(jié) 表上作業(yè)法表上作業(yè)法 第三節(jié)第三節(jié) 產(chǎn)銷不平衡的運輸問題產(chǎn)銷不平衡的運輸問題 第四節(jié)第四節(jié) 應(yīng)用舉例應(yīng)用舉例3第一節(jié)第一節(jié) 運輸問題的數(shù)學(xué)模型運輸問題的數(shù)學(xué)模型一、數(shù)學(xué)模型一、數(shù)學(xué)模型的運量。則的運量。則到到表示表示設(shè)設(shè)jiijBAx232221131211556646xxxxxxMinZ 3 , 2 , 1; 2 , 1; 02001501503

2、00200.231322122111232221131211 jixxxxxxxxxxxxxtsij例例1 1銷地銷地產(chǎn)地產(chǎn)地B1B2B3aiA1646200A2655300bj150150200500產(chǎn)地：貨物發(fā)出的地點產(chǎn)地：貨物發(fā)出的地點銷地：貨物接收的地點銷地：貨物接收的地點產(chǎn)量：各產(chǎn)地的可供貨量產(chǎn)量：各產(chǎn)地的可供貨量銷量：各銷地的貨物需求量銷量：各銷地的貨物需求量運輸問題就是研究如何組織調(diào)運，既滿足各銷運輸問題就是研究如何組織調(diào)運，既滿足各銷售地的需求，又使得總運費最小。售地的需求，又使得總運費最小。4二、運輸問題的一般數(shù)學(xué)模型二、運輸問題的一般數(shù)學(xué)模型 設(shè)設(shè)xij表示產(chǎn)地表示產(chǎn)地 i

3、 運往銷地運往銷地 j 的物資量，的物資量，cij表示對應(yīng)的單位運費表示對應(yīng)的單位運費 令令a1, a2, , am表示各產(chǎn)地產(chǎn)量表示各產(chǎn)地產(chǎn)量, b1, b2, , bn表示各銷地的銷量表示各銷地的銷量 有有m個地區(qū)生產(chǎn)某種物資，有個地區(qū)生產(chǎn)某種物資，有n個地區(qū)需要該類物資個地區(qū)需要該類物資產(chǎn)銷平衡表產(chǎn)銷平衡表單位運價表單位運價表 銷地銷地產(chǎn)地產(chǎn)地1 2 n 1 2 m a1 a2 am銷量銷量b1 b2 bn 銷地銷地產(chǎn)地產(chǎn)地 1 2 n 1 2 mc11 c12 c1nc21 c22 c2n.cm1 cm2 cmn5 0 , 2 , 1 , 2 , 1.1111ijjmiijnjiijm

4、injijijxnjbxmiaxtsxwMinZ銷銷量量約約束束產(chǎn)產(chǎn)地地約約束束cij xij產(chǎn)量約束產(chǎn)量約束一般滿足產(chǎn)銷平衡：一般滿足產(chǎn)銷平衡：11mnijijab 產(chǎn)量約束：由某一產(chǎn)地運往各個銷售地的物品數(shù)產(chǎn)量約束：由某一產(chǎn)地運往各個銷售地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量。量之和等于該產(chǎn)地的產(chǎn)量。銷量約束：由各個產(chǎn)地運往某一銷售地的物品數(shù)銷量約束：由各個產(chǎn)地運往某一銷售地的物品數(shù)量之和等于該銷售地的銷量。量之和等于該銷售地的銷量。6產(chǎn)大于銷產(chǎn)大于銷 njjmiiba11 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 銷地銷地產(chǎn)

5、地產(chǎn)地1 2 n 1 2 m a1 a2 am銷量銷量b1 b2 bn7產(chǎn)小于銷（銷大于產(chǎn)）產(chǎn)小于銷（銷大于產(chǎn)） njjmiiba11 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 銷地銷地產(chǎn)地產(chǎn)地1 2 n 1 2 m a1 a2 am銷量銷量b1 b2 bn8定理定理1 運輸問題的數(shù)學(xué)模型必有最優(yōu)解。運輸問題的數(shù)學(xué)模型必有最優(yōu)解。 首先，運輸問題一定有可行解；其次，任何單位運價cij0，從而對于任一可行解，必有目標(biāo)函數(shù)值大于或等于零，即目標(biāo)函數(shù)有下界。所以，求解運輸問題時，不需要進行無最優(yōu)解的判別。1112112122221

6、211211112222212nnmmmnmmmnnmnnxxxaxxxaxxxaxxxbxxxbxxxb產(chǎn)量平衡產(chǎn)量平衡（m個）個）銷量平衡銷量平衡（n個）個）9在例在例1 1中，運輸問題的系數(shù)矩陣為：中，運輸問題的系數(shù)矩陣為：1.1.一般情況下一般情況下, ,運輸問題運輸問題決策變量決策變量xij的的系數(shù)列向量為系數(shù)列向量為: :三、變量三、變量xij的系數(shù)列向量的特征的系數(shù)列向量的特征 000000000000001111111111100100 )(Ar111213212223xxxxxx0110ijimjiPeemj 位位置置位位置置4132 2.2.系數(shù)矩陣的元素等于系數(shù)矩陣的元素

7、等于0 0或或1 1。101112112122221211211112222212nnmmmnmmmnnmnnxxxaxxxaxxxaxxxbxxxbxxxb3.3.運輸問題系數(shù)矩陣的秩為運輸問題系數(shù)矩陣的秩為m+n-1。3.3.運輸問題基變量的個數(shù)為運輸問題基變量的個數(shù)為m+n-1。111. 概念概念例例21)1)數(shù)字格數(shù)字格2)空格空格3)3)閉回路閉回路四、閉回路四、閉回路銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620閉回路：閉回路：以某空格為起點，用水平或垂直線向前劃，當(dāng)碰到某以某空格為起點，用水平或垂直線向前劃，當(dāng)碰到某恰當(dāng)?shù)臄?shù)字

8、格后，轉(zhuǎn)恰當(dāng)?shù)臄?shù)字格后，轉(zhuǎn)90900 0繼續(xù)前進，直到回到起始空格為止。繼續(xù)前進，直到回到起始空格為止。12銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620（1 1）每個頂點都是轉(zhuǎn)角；）每個頂點都是轉(zhuǎn)角；（2 2）每行或每列有且僅有兩個頂點；）每行或每列有且僅有兩個頂點；（3 3）每個頂點的連線都是水平的或垂直的；）每個頂點的連線都是水平的或垂直的；（4 4）除起點外，其余各頂點都是數(shù)字格。）除起點外，其余各頂點都是數(shù)字格。13銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj36562014銷地銷地產(chǎn)地

9、產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj36562015 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj36562016 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj36562017 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620182.2.閉回路與變量所對應(yīng)的系數(shù)列向量組線性相關(guān)性的關(guān)系閉回路與變量所對應(yīng)的系數(shù)列向量組線性相關(guān)性的關(guān)系結(jié)論結(jié)論1 1 運輸問題一組變量構(gòu)成閉回路的充要條件是這組運輸問題一組變量構(gòu)成閉回路的

10、充要條件是這組變量所對應(yīng)的系數(shù)列向量線性相關(guān)變量所對應(yīng)的系數(shù)列向量線性相關(guān)例如，閉回路（例如，閉回路（x11, x21, x23, x13） 000000000000001111111111100100111213212223PPPPPP銷地銷地產(chǎn)地產(chǎn)地B1B2B3aiA1646200A2655300bj150150200500192.2.閉回路與變量所對應(yīng)的系數(shù)列向量組線性相關(guān)性的關(guān)系閉回路與變量所對應(yīng)的系數(shù)列向量組線性相關(guān)性的關(guān)系結(jié)論結(jié)論2 2 運輸問題的一個可行解是基可行解的充要條件是：運輸問題的一個可行解是基可行解的充要條件是：1 1）數(shù)字格的個數(shù)為）數(shù)字格的個數(shù)為m+n-1個；個；2

11、 2） 這這m+n-1個數(shù)字格不構(gòu)成閉回路。個數(shù)字格不構(gòu)成閉回路。（x11, x21, x23, x12） 000000000000001111111111100100111213212223PPPPPP結(jié)論結(jié)論3 3 對每一個空格處，有且僅有一條閉回路。對每一個空格處，有且僅有一條閉回路。銷地銷地產(chǎn)地產(chǎn)地B1B2B3aiA1646200A2655300bj15015020050020一、表上作業(yè)法的步驟一、表上作業(yè)法的步驟第二節(jié)第二節(jié) 表上作業(yè)法表上作業(yè)法最優(yōu)性檢驗最優(yōu)性檢驗結(jié)結(jié) 束束Y調(diào)調(diào) 整整N確定初始確定初始基可行解基可行解在在m mn n維產(chǎn)銷維產(chǎn)銷平衡表上找到平衡表上找到m+n-1

12、m+n-1個數(shù)字格個數(shù)字格0?ij 確定進基確定進基變量和出變量和出基變量基變量21 表上作業(yè)法步驟：初始方案、最優(yōu)性檢驗、改進方案表上作業(yè)法步驟：初始方案、最優(yōu)性檢驗、改進方案一、初始方案的確定一、初始方案的確定1.1.最小元素法最小元素法2.2.伏格爾法伏格爾法二、最優(yōu)性檢驗二、最優(yōu)性檢驗1.1.閉回路法閉回路法2.2.位勢法位勢法三、改進方案三、改進方案 在閉回路內(nèi)改進在閉回路內(nèi)改進221.1.最小元素法最小元素法( (就近供應(yīng)就近供應(yīng)) )就進供應(yīng)，即從單位運價表中最小的運價開始確定供銷就進供應(yīng)，即從單位運價表中最小的運價開始確定供銷關(guān)系，然后次小，一直到求出初始基可行解為止。關(guān)系，然

13、后次小，一直到求出初始基可行解為止。例例3 3865310334214613 Z二、初始基可行解的確定二、初始基可行解的確定銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj36562023例例3 3865310334214613 Z銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620最小元素法給出的初始解是運輸問題的基可行解。最小元素法給出的初始解是運輸問題的基可行解。242.2.伏格爾法（伏格爾法（VogelVogel）第一步：求出每行次小運價與最小運價之差；同時求第一步：求出每行次小運價與最小運價之差；

14、同時求出每列次小運價和最小運價之差；出每列次小運價和最小運價之差；第二步：找出所有行、列差額的最大值，差額最大值第二步：找出所有行、列差額的最大值，差額最大值所對應(yīng)的行或列中的最小運價處先調(diào)運；所對應(yīng)的行或列中的最小運價處先調(diào)運；第三步：這時必有一列或一行調(diào)運完畢，劃去該列或第三步：這時必有一列或一行調(diào)運完畢，劃去該列或該行，在剩下的運價中再求最大差額，進行第二次調(diào)該行，在剩下的運價中再求最大差額，進行第二次調(diào)運，依次進行下去，直到最后全部調(diào)運完畢，得到一運，依次進行下去，直到最后全部調(diào)運完畢，得到一個調(diào)運方案。個調(diào)運方案。一產(chǎn)地的產(chǎn)品假如不能夠按照最小運價就近供應(yīng)，就一產(chǎn)地的產(chǎn)品假如不能夠按

15、照最小運價就近供應(yīng)，就考慮次小運價。最小運價和次小運價的差額越大，說考慮次小運價。最小運價和次小運價的差額越大，說明不能按最小運價調(diào)運時，運費增加越多。明不能按最小運價調(diào)運時，運費增加越多。252.2.伏格爾法（伏格爾法（VogelVogel）85538335461132 Z例例4 4銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620011012 2 5 1 32-1301-2-1201-2-1- 26在以上兩種方法中，有幾點需要注意：在以上兩種方法中，有幾點需要注意： 這兩種方法得出的解均為初始可行解。這兩種方法得出的解均為初始可行解。 一般

16、由伏格爾法得出的解比最小元素法得出的解一般由伏格爾法得出的解比最小元素法得出的解更接近最優(yōu)解。更接近最優(yōu)解。 在以上方法過程中，不可同時劃去行和列。在以上方法過程中，不可同時劃去行和列。271.1.閉回路法閉回路法 例例5 5注注: 1)數(shù)字格檢數(shù)字格檢驗數(shù)均為驗數(shù)均為0顯然該問題至此尚未達到最優(yōu)解。顯然該問題至此尚未達到最優(yōu)解。三、求檢驗數(shù)并進行最優(yōu)解的判定三、求檢驗數(shù)并進行最優(yōu)解的判定銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620121-110121133211 121110542 偶偶奇奇空格檢驗數(shù)空格檢驗數(shù)ijijijcc)2解。解

17、。時，運輸問題達到最優(yōu)時，運輸問題達到最優(yōu)當(dāng)所有當(dāng)所有最優(yōu)性判別準(zhǔn)則：最優(yōu)性判別準(zhǔn)則：0 ij2811(32)(13)1 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj3656202912(115)(410)2 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj3656203022(953)(4102)1 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj3656203124(83)(210)1 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A374105

18、9bj3656203231(7102)(531)10 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj3656203333(1010)(53)12 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620342.2.位勢法位勢法例例6 6 由最小元素法得出初始解由最小元素法得出初始解, ,如下表如下表ijjicvu 對對數(shù)數(shù)字字格格而而言言計計算算）行行勢勢、列列勢勢的的定定義義與與注注：:13）行勢、列勢可不唯一，但檢驗數(shù)是一致的。）行勢、列勢可不唯一，但檢驗數(shù)是一致的。銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA

19、13113107A219284A3741059bj3656200),()2 ijjiijijvuc數(shù)字格數(shù)字格檢驗數(shù)的計算：空格檢驗數(shù)的計算：空格35 ), 1;, 1( , 0.)(1111njmixbxaxtsxcMinZLijjmiijinjijminjijij 無約束無約束jiijjinjjjmiiivucvutsvbuaMaxZD,.)(110)()()(),(,)()(),()0(0)0()0()0()0()0(0)0( ijjiijjiijjiijcvuxDLvuxDLvux）（）（的的最最優(yōu)優(yōu)解解的的充充要要條條件件是是、是是、則則的的可可行行解解、是是、結(jié)結(jié)論論：設(shè)設(shè)位勢法的

20、理論依據(jù)（互補松弛定理）位勢法的理論依據(jù)（互補松弛定理）36位勢法的理論依據(jù)位勢法的理論依據(jù)運輸問題運輸問題min0fCXAXbX 設(shè)設(shè)B B為一可行基，則相為一可行基，則相應(yīng)的基可行解的各變應(yīng)的基可行解的各變量的檢驗數(shù)為量的檢驗數(shù)為運輸問題的對偶問題運輸問題的對偶問題maxzYbYACY 不不受受限限制制11(,)mnYuuvv 由對偶理論有由對偶理論有 Y=CBB-1ijijijcYp ijimjpee 11(,)()ijijijijmnijijijcYpcuuvvpcuv 基變量的檢驗數(shù)等于基變量的檢驗數(shù)等于0()0( , )ijijijijcuvuvci jI即即1ijijBijcC

21、Bp （I：基變量下標(biāo)集基變量下標(biāo)集）37位勢法的計算過程位勢法的計算過程 令令u1=0 按按ui+vj=cij相相繼確定其他數(shù)繼確定其他數(shù)字格的字格的ui和和vj 計算空格的檢驗數(shù)。如計算空格的檢驗數(shù)。如 11=3-(0+2)=1因為因為24=-10,因而該問題至此尚未達到最優(yōu)解因而該問題至此尚未達到最優(yōu)解.銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1311310A21928A374105uivj0310-1-529121-1101238位勢法的步驟位勢法的步驟 對于每一個基變量（數(shù)字格）都按照公式對于每一個基變量（數(shù)字格）都按照公式 ui+vj=cij 列列出一個位勢方程，形成位勢方程組（出一個位

22、勢方程，形成位勢方程組（m+n-1個）；個）； 任意決定其中一個位勢的數(shù)值，然后求出其他位勢的任意決定其中一個位勢的數(shù)值，然后求出其他位勢的數(shù)值；數(shù)值； 按照公式按照公式 計算非基變量（空格處）計算非基變量（空格處）的檢驗數(shù)（的檢驗數(shù)（mn-(m+n-1)個）。個）。()ijijijcuv 39 從最小負(fù)檢驗數(shù)所對應(yīng)的空格進行調(diào)整從最小負(fù)檢驗數(shù)所對應(yīng)的空格進行調(diào)整例例7 7 對由最小元素法得出的初始解進行調(diào)整對由最小元素法得出的初始解進行調(diào)整調(diào)整方法：調(diào)整方法：1）找出負(fù)檢驗）找出負(fù)檢驗數(shù)所在空格處的數(shù)所在空格處的閉回路閉回路2）在閉回路上找到）在閉回路上找到偶數(shù)點所對應(yīng)的基偶數(shù)點所對應(yīng)的基變

23、量的最小值變量的最小值514; 110; 213; 011 即即再再按調(diào)整后的解由位勢法計算空格的檢驗數(shù)按調(diào)整后的解由位勢法計算空格的檢驗數(shù)四、調(diào)整四、調(diào)整銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1311310A21928A374105121-11012 x23 x14 x24 x133 3）以此最小值）以此最小值為為調(diào)整量，在奇數(shù)格加調(diào)整量，在奇數(shù)格加上該調(diào)整量，在偶數(shù)上該調(diào)整量，在偶數(shù)格上減去該調(diào)整量格上減去該調(diào)整量換入變量：換入變量：x24換出變量：換出變量：x23401.1.由最小元素法求得初始基可行解由最小元素法求得初始基可行解865310334214613 Z五、典型運輸問題解題步驟示例

24、五、典型運輸問題解題步驟示例銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA13113107A219284A3741059bj365620412.2.由位勢法求檢驗數(shù)由位勢法求檢驗數(shù) 令令u1=0 按按ui+vj=cij相相繼確定其他數(shù)繼確定其他數(shù)字格的字格的ui和和vj 計算空格的檢驗數(shù)計算空格的檢驗數(shù)因為因為24=-10,因而該問題至此尚未達到最優(yōu)解因而該問題至此尚未達到最優(yōu)解.銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1311310A21928A374105uivj0310-1-529121-11012()ijijijcuv 如如11=3-(0+2)=1423.3.從最小負(fù)檢驗數(shù)所對應(yīng)的空格進行調(diào)整從最小

25、負(fù)檢驗數(shù)所對應(yīng)的空格進行調(diào)整調(diào)整方法：調(diào)整方法：1）找出閉回路）找出閉回路2）使最小負(fù)檢驗數(shù)）使最小負(fù)檢驗數(shù)所對應(yīng)的空格達到所對應(yīng)的空格達到最大的調(diào)整量最大的調(diào)整量1514; 110; 213; 011 即即銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1311310A21928A374105121-1101243 令令u1=0 按按ui+vj=cij相相繼確定其他數(shù)繼確定其他數(shù)字格的字格的ui和和vj 計算空格的檢驗數(shù)。如計算空格的檢驗數(shù)。如11=3-(3+0)=0因為所有的因為所有的ij0,至此該問題已經(jīng)達到最優(yōu)解至此該問題已經(jīng)達到最優(yōu)解.855346811310235 Z最最優(yōu)優(yōu)解解4.4.再按調(diào)整

26、后的解由位勢法計算空格的檢驗數(shù)再按調(diào)整后的解由位勢法計算空格的檢驗數(shù)銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1311310A21928A374105 uivj0310-2-539022 912144表上作業(yè)法的步驟：表上作業(yè)法的步驟：（1 1）編制調(diào)運表（產(chǎn)銷平衡表、單位運價表）編制調(diào)運表（產(chǎn)銷平衡表、單位運價表）（2 2）在調(diào)運表上求出初始基可行解）在調(diào)運表上求出初始基可行解（3 3）用位勢法或閉回路法計算非基變量的檢驗數(shù)，若所）用位勢法或閉回路法計算非基變量的檢驗數(shù)，若所有非基變量的檢驗數(shù)均大于等于有非基變量的檢驗數(shù)均大于等于0 0，則已得到問題的最，則已得到問題的最優(yōu)解優(yōu)解（4 4）選取小于）

27、選取小于0 0的檢驗數(shù)中的最小者所對應(yīng)的非基變量的檢驗數(shù)中的最小者所對應(yīng)的非基變量作為進基變量，用閉回路法進行基可行解的轉(zhuǎn)換，得作為進基變量，用閉回路法進行基可行解的轉(zhuǎn)換，得到新的基可行解，轉(zhuǎn)入步驟（到新的基可行解，轉(zhuǎn)入步驟（3 3）。）。45可能出現(xiàn)的幾種情況可能出現(xiàn)的幾種情況（1 1）無窮多最優(yōu)解無窮多最優(yōu)解 某一個非基變量（空格處）的檢驗數(shù)為某一個非基變量（空格處）的檢驗數(shù)為0 0；銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1311310A21928A374105 022 912146可能出現(xiàn)的幾種情況可能出現(xiàn)的幾種情況（2 2）退化退化 同時劃去一行和一列；同時劃去一行和一列； 在用閉回路法調(diào)

28、整時，同時有兩個或兩個以上的偶在用閉回路法調(diào)整時，同時有兩個或兩個以上的偶數(shù)頂點具有最小值數(shù)頂點具有最小值銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4aiA1311457A277384A3121069bj36562047一、原理一、原理 njjmiiijjmiijinjijbanjmixbxax1111), 1;, 1( ,000有有解解的的充充要要條條件件是是：定定理理：方方程程組組第三節(jié)第三節(jié) 產(chǎn)銷不平衡的運輸問題產(chǎn)銷不平衡的運輸問題48證明：證明： njjnjmiijminjijmiijmiijinjijijijbxxabxaxxx111)0(11)0(11)0(1)0()0()0(,01而而則則是

29、是方方程程組組的的解解，且且設(shè)設(shè)）先先證證必必要要性性（jmiijinjjinjjinjijjiijijjijinjjmiinjjmiibxababaxbaxiixbabaibaba 1)0(111)0()0()0(11110000000,)2(同同理理。則則，令令）又又若若（是是方方程程組組的的解解。則則，則則，由由于于）若若（記記若若再再證證充充分分性性49結(jié)論：結(jié)論： 1. 1. 運輸問題有可行解運輸問題有可行解 產(chǎn)銷平衡產(chǎn)銷平衡 2. 2. 運輸問題有可行解運輸問題有可行解 運輸問題有最優(yōu)解運輸問題有最優(yōu)解 3. 3. 運輸問題有最優(yōu)解運輸問題有最優(yōu)解 產(chǎn)銷平衡產(chǎn)銷平衡500,),(.

30、11,11,1111111111 ninininjjmiinjjmiinnnnjjmiicBAxbababBBba的的運運量量，且且到到表表示示從從，的的需需要要量量為為銷銷地地則則虛虛設(shè)設(shè)一一個個銷銷地地銷銷若若產(chǎn)產(chǎn)二、產(chǎn)銷不平衡問題的處理二、產(chǎn)銷不平衡問題的處理 銷地銷地產(chǎn)地產(chǎn)地1 2 n n+1 1 2 m a1 a2 am銷量銷量b1 b2 bn bn+151 1111111,2,. .1,2,10m nijijijnijijmijjiijMinZc xxaimstxbjnx 地地 束束量量 束束產(chǎn)量約束產(chǎn)量約束銷量約束銷量約束m+n+1個約束條件個約束條件m(n+1)個決策變個決策變

31、量量 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 520,),(.2,11,11111111111 jmjmjmnjjmiimiinjjmmmnjjmiicBAxbaabaAAba的的運運量量，且且到到表表示示從從，的的產(chǎn)產(chǎn)量量為為：則則虛虛設(shè)設(shè)一一個個產(chǎn)產(chǎn)地地銷銷若若產(chǎn)產(chǎn)二、產(chǎn)銷不平衡問題的處理二、產(chǎn)銷不平衡問題的處理 銷地銷地產(chǎn)地產(chǎn)地1 2 n 1 2 mm+1 a1 a2 amam+1銷量銷量b1 b2 bn53 1111111,2,1. .1,2,0mnijijijnijijmijjiijMinZc xxaimstxb

32、jnx 地地 束束量量 束束產(chǎn)量約束產(chǎn)量約束銷量約束銷量約束m+n+1個約束條件個約束條件(m+1)n個決策變個決策變量量 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 54例例8 8 求下面運輸問題的最優(yōu)解求下面運輸問題的最優(yōu)解 這是一個產(chǎn)大于銷的運輸問題，增加一個假想的銷這是一個產(chǎn)大于銷的運輸問題，增加一個假想的銷售地，可以將其轉(zhuǎn)化為產(chǎn)銷平衡問題。售地，可以將其轉(zhuǎn)化為產(chǎn)銷平衡問題。銷地銷地產(chǎn)地產(chǎn)地甲甲乙乙丙丙丁丁戊戊產(chǎn)量產(chǎn)量12341021820102065873930107106455629銷量銷量4462455 假設(shè)假設(shè)

33、“己己”的虛擬銷量為的虛擬銷量為2 2，各實際產(chǎn)地到其的運費為，各實際產(chǎn)地到其的運費為0 0。如下表所示：。如下表所示：用用表上作業(yè)法可以求出最優(yōu)解。表上作業(yè)法可以求出最優(yōu)解。銷地銷地產(chǎn)地產(chǎn)地甲甲乙乙丙丙丁丁戊戊己己產(chǎn)量產(chǎn)量123410218201020658739301071064500005629銷量銷量44624222注：用最小元素法時，某列單位運價為注：用最小元素法時，某列單位運價為0，應(yīng)該最后考慮，應(yīng)該最后考慮56例例9 9 產(chǎn)銷不平衡問題（書產(chǎn)銷不平衡問題（書P90P90例例2 2） 在產(chǎn)銷平衡表中增加一個假想的化肥廠在產(chǎn)銷平衡表中增加一個假想的化肥廠D D，年產(chǎn)量為年產(chǎn)量為505

34、0萬噸；將需求分兩種情況的地區(qū)，實際按兩個地區(qū)看待。萬噸；將需求分兩種情況的地區(qū)，實際按兩個地區(qū)看待。需求地區(qū)需求地區(qū)化肥廠化肥廠IIIIIIIV產(chǎn)量產(chǎn)量（萬噸）（萬噸）ABC1614191313202219231715-506050最低需求（萬噸）最低需求（萬噸）最高需求（萬噸）最高需求（萬噸）305070700301060 160110,21057這樣可將該問題化為產(chǎn)銷平衡問題：這樣可將該問題化為產(chǎn)銷平衡問題：需求地區(qū)需求地區(qū)化肥廠化肥廠IIIIIIIIVIV產(chǎn)量產(chǎn)量（萬噸）（萬噸）ABCD161419M1614190131320M22192301715MM1715M050605050銷量（萬噸）銷量（萬噸）30207030105021058根據(jù)表上作業(yè)法計算，可得該