運(yùn)籌學(xué)第三章：運(yùn)輸問(wèn)題

運(yùn)籌學(xué)張銘鑫

機(jī)汽學(xué)院工業(yè)工程

2006年4月前兩章討論了一般線性規(guī)劃的解法，但在實(shí)際工作中，往往碰到有些線性規(guī)劃問(wèn)題，它們的約束方程組的系數(shù)矩陣具有很特殊的結(jié)構(gòu)，這就有可能找到比單純形法更為簡(jiǎn)便的求解方法，本章討論的運(yùn)輸問(wèn)題就是這樣一類特殊的線性規(guī)劃問(wèn)題?！?運(yùn)輸問(wèn)題

（3.1運(yùn)輸問(wèn)題的提出）§3運(yùn)輸問(wèn)題

3.1運(yùn)輸問(wèn)題在經(jīng)濟(jì)活動(dòng)中，經(jīng)常碰到大宗物資的調(diào)運(yùn)問(wèn)題。如煤、鋼鐵、木材、糧食等物資，在全國(guó)有若干生產(chǎn)基地，根據(jù)已有的交通網(wǎng)，制定調(diào)運(yùn)方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，而總運(yùn)費(fèi)最省。

這類問(wèn)題的一般提法是：設(shè)某物資有m個(gè)產(chǎn)地A1,A2,…,Am,其產(chǎn)量分別為a1,a2,…,am,有n個(gè)銷地B1,B2,…,Bn,其銷量分別是b1,b2,…,bn，已知產(chǎn)地Ai到銷地Bj的單位運(yùn)費(fèi)是Cij，這些數(shù)據(jù)可用產(chǎn)銷平衡表和單位運(yùn)價(jià)表表示如下：若總產(chǎn)量等于總銷量(產(chǎn)銷平衡),試確定總運(yùn)費(fèi)最省的調(diào)運(yùn)方案.建模:設(shè)xij表示從產(chǎn)地Ai到銷地Bj的運(yùn)量(i=1,2,…m;j=1,2,…n),則運(yùn)輸問(wèn)題的數(shù)學(xué)模型如下：

運(yùn)輸數(shù)學(xué)模型銷地產(chǎn)地

B1B2…Bn

產(chǎn)量

A1A2┇Am

a1a2┇am銷量b1，b2，…，bn銷地產(chǎn)地B1B2…Bn

A1A2┇Am

C11C12…C1nC21C22…C2n………………Cm1Cm2…Cmn產(chǎn)銷平衡表

單位運(yùn)價(jià)表

X11X12…X1nX21X22…X2n………………Xm1Xm2…Xmn運(yùn)輸數(shù)學(xué)模型系數(shù)矩陣1記

則

顯然，模型是具有m×n個(gè)變量，m+n個(gè)約束的線性規(guī)劃，可以用一般的單純形法求解，但是當(dāng)m與n較大時(shí)，模型的規(guī)模比較大，計(jì)算比較困難。為了進(jìn)一步研究針對(duì)運(yùn)輸問(wèn)題的特殊解法，下面考察它的約束系數(shù)矩陣。系數(shù)矩陣2記

則

A是m+n行，m×n列的矩陣，它比較稀疏，除有2m×n個(gè)1以外，其余元素皆為0，變量xij對(duì)應(yīng)的系數(shù)列向量Pij中，除第i個(gè)和第m+j個(gè)為1外，其余全是0，即Pij=(0...1...1...0)T=ei+em+j系數(shù)矩陣2A是m+n行，m×n列的矩陣，它比較稀疏，除有2m×n個(gè)1以外，其余元素皆為0，變量xij對(duì)應(yīng)的系數(shù)列向量Pij中，除第i個(gè)和第m+j個(gè)為1外，其余全是0，即Pij=(0...1...1...0)T=ei+em+j銷地產(chǎn)地

B1B2B3產(chǎn)量

A1A2a1a2銷量b1，b2，b3X11X12X13X21X22X23系數(shù)矩陣的秩記

則

運(yùn)輸方程的總數(shù)是m+n個(gè)，它的系數(shù)矩陣A的秩是m+n-1?？梢?jiàn)，運(yùn)輸問(wèn)題的基可行解中，基變量的個(gè)數(shù)應(yīng)為m+n-1個(gè)。由于運(yùn)輸問(wèn)題的數(shù)學(xué)模型具有以上特點(diǎn)，所以求解運(yùn)輸問(wèn)題時(shí)，可以采用比較簡(jiǎn)單的計(jì)算方法―表上作業(yè)法。3.2表上作業(yè)法表上作業(yè)法的思想和單純形法類似，即首先確定一個(gè)初始方案，找出一個(gè)基可行解，然后根據(jù)判別準(zhǔn)則來(lái)檢查這個(gè)初始方案是不是最優(yōu)的，如果不是最優(yōu)的，那么對(duì)該方案進(jìn)行調(diào)整，直到求出最優(yōu)方案為止。下面介紹它的計(jì)算步驟。3.2.1確定初始基可解確定初始基可行解的方法很多，我們介紹兩種：最小元素法和伏格爾法。

1.最小元素法基本思想就是就近供應(yīng)，即從運(yùn)價(jià)表中最小運(yùn)價(jià)開始確定調(diào)運(yùn)量，然后次小，一直到找出初始調(diào)運(yùn)方案為止。3.2表上作業(yè)法例1某公司經(jīng)銷甲產(chǎn)品。它下設(shè)三個(gè)工廠。每日的產(chǎn)量分別是A1為7噸，A2為4噸，A3為9噸，該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各銷售點(diǎn)每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為表3－3所示，試確定總運(yùn)費(fèi)最省的調(diào)運(yùn)方案。1.最小元素法（1）表3－3單位運(yùn)價(jià)表

銷地產(chǎn)地B1B2B3B4A1A2A3317119432101085銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3749銷量3656表3－4產(chǎn)銷平衡表

3114633運(yùn)費(fèi)Z＝1×3＋4×6＋3×4＋1×2＋3×10＋3×5＝86314633

用最小元素法確定初始可行解：x13=4,x14=3x21=3,x23=1x32=6,x33=3z=3*4+10*3+1*3+2*1+4*6+5*3=861.最小元素法（復(fù)件1）1.最小元素法（2）表3－3單位運(yùn)價(jià)表

銷地產(chǎn)地

B1B2B3B4A1A2A3317119432101085銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3749銷量3656表3－4產(chǎn)銷平衡表

314633

用最小元素法所得初始調(diào)運(yùn)方案如表3－4黃字所示。稱產(chǎn)銷平衡表中填有數(shù)字的格為數(shù)字格，沒(méi)填數(shù)字的格稱為空格。由最小元素法可知，在產(chǎn)銷平衡表上每填一個(gè)數(shù)字，就劃去一行或一列，表中共有m行n列，用m+n-1條線就可劃去運(yùn)價(jià)表所有元素，相應(yīng)地在產(chǎn)銷平衡表上就形成m+n-1個(gè)數(shù)字格。前面已經(jīng)說(shuō)明了運(yùn)輸問(wèn)題的約束系數(shù)矩陣A的秩恰為m+n-1，理論上可以證明，這些數(shù)字所對(duì)應(yīng)的變量相當(dāng)于基變量，而空格對(duì)應(yīng)的變量相當(dāng)于非基變量，用最小元素法得到的初始調(diào)運(yùn)方案構(gòu)成一個(gè)初始基可行解。1.最小元素法（特別注意）表3－3單位運(yùn)價(jià)表

銷地產(chǎn)地

B1B2B3B4A1A2A3317119432101085銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1A2A3749銷量3656表3－4產(chǎn)銷平衡表

314633特別注意：數(shù)02.伏格爾法

2.伏格爾法

最小元素法的缺點(diǎn)是：為了節(jié)省一處的運(yùn)費(fèi)，有時(shí)可能造成在其它的地方多化幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一個(gè)產(chǎn)地的產(chǎn)品如果不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小的運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，說(shuō)明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)來(lái)調(diào)運(yùn)。

伏格爾法的計(jì)算步驟：

第一步：計(jì)算單位運(yùn)價(jià)表上各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，填入表的最右列和最下行。

第二步：從行或列差額中選出最大值，選擇它所在行或列中的最小元素.滿足最小運(yùn)費(fèi)調(diào)運(yùn),劃去已得到滿足的行或列的運(yùn)價(jià)。

第三步：然后計(jì)算未被劃去的行或列，重新計(jì)算差額，重復(fù)第一步和第二步，直到給出一個(gè)初始的基可行解為止。3.2表上作業(yè)法用伏格爾法確定初始解601125130122

13201

2

12376

12531z=3*1+6*4+5*3+2*10+1*8+3*5=85返回3.2.2最優(yōu)性檢驗(yàn)3.2.2最優(yōu)性檢驗(yàn)在求出問(wèn)題的一個(gè)可行方案后，就應(yīng)該判斷這個(gè)方案是不是最優(yōu)的。為了進(jìn)行最優(yōu)性判別，下面先給出檢驗(yàn)樹的概念。對(duì)于空格(i,j)，調(diào)整其它有關(guān)數(shù)字格的運(yùn)量，則稱這一系列的變化導(dǎo)致的總運(yùn)費(fèi)變化值為該空格的檢驗(yàn)數(shù)，記作σij。當(dāng)一個(gè)空格的檢驗(yàn)數(shù)大于零，說(shuō)明將該空格變?yōu)閿?shù)字格會(huì)使總運(yùn)費(fèi)增加；反之，如果該空格檢驗(yàn)數(shù)為負(fù)值，說(shuō)明將該空格變?yōu)閿?shù)字格會(huì)使總運(yùn)費(fèi)降低。因此有以下判別準(zhǔn)則：

定理：如果一個(gè)可行方案的所有空格檢驗(yàn)數(shù)都大于或等于零，則方案是最優(yōu)方案。對(duì)于一個(gè)可行方案，只要求出所有空格的檢驗(yàn)數(shù)，就可以判別該方案是否為最優(yōu)方案，那么如何求得一個(gè)空格的檢驗(yàn)數(shù)呢？下面給出兩種計(jì)算檢驗(yàn)數(shù)的方法。

3.2表上作業(yè)法＋1

1.閉回路法1.閉回路法

為了確定空格(i,j)的檢驗(yàn)數(shù)，可以先找出以該空格為一個(gè)頂點(diǎn),其余頂點(diǎn)全是數(shù)字格的閉回路。所謂閉回路，就是從該空格出發(fā)，沿水平或垂直方向前進(jìn)，遇到合適的數(shù)字格后轉(zhuǎn)90˙，繼續(xù)前進(jìn)，如果能夠回到出發(fā)點(diǎn)，則稱這個(gè)封閉折線為閉回路。然后假定給(i,j)格一個(gè)單位運(yùn)量，調(diào)整閉回路上其余數(shù)字格的運(yùn)量，使產(chǎn)銷平衡，則閉回路上總費(fèi)用的變化值就等于(i,j)格的檢驗(yàn)數(shù)。

可以證明，在任何可行方案中，以空格(i,j)為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路存在而且唯一。數(shù)

數(shù)

數(shù)

數(shù)

數(shù)

－1

＋1

－1

＋1

－1

用閉回路法求檢驗(yàn)數(shù)(空格11)3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133閉回路法求檢驗(yàn)數(shù)＋1

－1

＋1

－1

σ11＝(+1)×3+(-1)×3+(+1)×2+(-1)×1=1用閉回路法求檢驗(yàn)數(shù)(空格12－錯(cuò))3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133閉回路法求檢驗(yàn)數(shù)用閉回路法求檢驗(yàn)數(shù)(空格12－對(duì))3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133閉回路法求檢驗(yàn)數(shù)＋1

－1

＋1

－1

σ12＝(+1)×11+(-1)×10+(+1)×5+(-1)×4=2用閉回路法求檢驗(yàn)數(shù)(空格12－對(duì))3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133閉回路法求檢驗(yàn)數(shù)＋1

－1

＋1

－1

σ22＝(+1)×9+(-1)×2+(+1)×3+(-1)×10+(+1)×5+(-1)×4=1－1

＋1

用閉回路法求檢驗(yàn)數(shù)(空格12－對(duì))3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133閉回路法求檢驗(yàn)數(shù)＋1

－1

＋1

－1

σ24＝(+1)×8+(-1)×2+(+1)×3+(-1)×10=-1用閉回路法求檢驗(yàn)數(shù)(空格12－對(duì))3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133閉回路法求檢驗(yàn)數(shù)＋1

－1

＋1

－1

σ31＝(+1)×7+(-1)×5+(+1)×10+(-1)×3+(+1)×2+(-1)×1=10－1

＋1

用閉回路法求檢驗(yàn)數(shù)(空格12－對(duì))3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133閉回路法求檢驗(yàn)數(shù)＋1

－1

＋1

－1

σ33＝(+1)×10+(-1)×5+(+1)×10+(-1)×3=12表3－15空格閉回路檢驗(yàn)數(shù)(11)(12)(22)(24)(31)(33)(11)－(13)－(23)－(21)－(11)(12)－(14)－(34)－(32)－(12)(22)－(23)－(13)－(14)－(34)－(32)－(22)(24)－(23)－(13)－(14)－(24)(31)－(34)－(14)－(13)－(23)－(21)－(31)(33)－(34)－(14)－(13)－(33)121-11012表3－15用閉回路法求檢驗(yàn)數(shù)(空格24)3111310銷地產(chǎn)地

B1B2B3B4產(chǎn)量A17A24A39銷量365692874105364133＋1

－1

＋1

－1

空格閉回路檢驗(yàn)數(shù)(24)(24)－(23)－(13)－(14)－(24)-1σ24＝(+1)×8+(-1)×2+(+1)×3+(-1)×10=－12.位勢(shì)法

用閉回路法求檢驗(yàn)數(shù)時(shí)，需要找出每個(gè)空格所在的閉回路，產(chǎn)銷點(diǎn)很多時(shí)，計(jì)算量非常大。下面介紹一種求檢驗(yàn)數(shù)簡(jiǎn)便的方法－位勢(shì)法。設(shè)Y=(u1,u2,…,um,v1,v2,…,vn)是運(yùn)輸問(wèn)題的m+n個(gè)約束條件對(duì)應(yīng)的對(duì)偶變量,決策變量xij(數(shù)字格)對(duì)應(yīng)的列向量Pij=ei+em+j，對(duì)于一個(gè)基可行解，由單純形法得知所有基變量xij(數(shù)字格)的檢驗(yàn)數(shù)等于0，即0=Cij-CBB-1Pij=Cij-YPij=Cij-(ui+vj)，所以由m+n-1個(gè)數(shù)字格對(duì)應(yīng)的Cij=(ui+vj)及u1＝0，即可確定所有ui,vj的值。

稱u1,u2,…,um,v1,v2,…,vn分別為產(chǎn)銷平衡表各行與各列的位勢(shì)。因?yàn)榉腔兞康模崭瘢z驗(yàn)數(shù)σij=Cij-YPij=Cij-(ui+vj)，所以，只要計(jì)算出所有的位勢(shì)值，就能求出各空格的檢驗(yàn)數(shù)?？梢宰C明，在任何可行方案中，以空格(i,j)為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路存在而且唯一。2.位勢(shì)法用位勢(shì)法求檢驗(yàn)數(shù)3146330103-1-5921--2--1-1----1012----Cij=(ui+vj),確定所有ui,vj的值.令u1=0,由(1,3)數(shù)字格運(yùn)價(jià)3=u1+v3，可得v3=3；先由m+n-1個(gè)數(shù)字格對(duì)應(yīng)的再按公式σij=Cij-(ui+vj)計(jì)算空格的檢驗(yàn)數(shù),結(jié)果見(jiàn)表格中紅色數(shù)字,例σ11=C11-(u1+v1)=3-(0+2)=13.位勢(shì)法方案的調(diào)整―閉回路法

當(dāng)空格的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，說(shuō)明當(dāng)前平衡表給出的調(diào)運(yùn)方案不是最優(yōu)的，可以進(jìn)行調(diào)整，使總運(yùn)輸費(fèi)用減少。調(diào)整方法如下：1°為了使方案有較大改進(jìn)，先確定最小檢驗(yàn)數(shù)，即min{σij|σij<0}=σLK2°找出以空格(L,K)為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路,規(guī)定空格(L,K)為閉回路的第一個(gè)頂點(diǎn)，閉回路上其它頂點(diǎn)依次為第二個(gè)頂點(diǎn)，第三個(gè)頂點(diǎn)，…(順時(shí)針或逆時(shí)針均可)。取閉回路上偶數(shù)序號(hào)頂點(diǎn)的最小運(yùn)量為調(diào)整運(yùn)量θ.

3.方案的調(diào)整－閉回路法＋1

數(shù)

數(shù)

數(shù)

－1

＋1

－1

(L,K)

3

2

θ=min{2,3}=2

3

0

-1

3.位勢(shì)法方案的調(diào)整―閉回路法

當(dāng)空格的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，說(shuō)明當(dāng)前平衡表給出的調(diào)運(yùn)方案不是最優(yōu)的，可以進(jìn)行調(diào)整，使總運(yùn)輸費(fèi)用減少。調(diào)整方法如下：1°為了使方案有較大改進(jìn)，先確定最小檢驗(yàn)數(shù)，即min{σij|σij<0}=σLK2°找出以空格(L,K)為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路,規(guī)定空格(L,K)為閉回路的第一個(gè)頂點(diǎn)，閉回路上其它頂點(diǎn)依次為第二個(gè)頂點(diǎn)，第三個(gè)頂點(diǎn)，…(順時(shí)針或逆時(shí)針均可)。取閉回路上偶數(shù)序號(hào)頂點(diǎn)的最小運(yùn)量為調(diào)整運(yùn)量θ.

閉回路法(步驟1)＋1

數(shù)

數(shù)

數(shù)

－1

＋1

－1

(L,K)

2

2

θ=min{2,2}=2

2

0

0

3.位勢(shì)法方案的調(diào)整―閉回路法

當(dāng)空格的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，說(shuō)明當(dāng)前平衡表給出的調(diào)運(yùn)方案不是最優(yōu)的，可以進(jìn)行調(diào)整，使總運(yùn)輸費(fèi)用減少。調(diào)整方法如下：1°為了使方案有較大改進(jìn)，先確定最小檢驗(yàn)數(shù)，即min{σij|σij<0}=σLK2°找出以空格(L,K)為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路,規(guī)定空格(L,K)為閉回路的第一個(gè)頂點(diǎn)，閉回路上其它頂點(diǎn)依次為第二個(gè)頂點(diǎn)，第三個(gè)頂點(diǎn)，…(順時(shí)針或逆時(shí)針均可)。取閉回路上偶數(shù)序號(hào)頂點(diǎn)的最小運(yùn)量為調(diào)整運(yùn)量θ.

閉回路法(步驟2)＋1

數(shù)

數(shù)

數(shù)

－1

＋1

－1

(L,K)

2

2

θ=min{2,2}=2

2

0

0

3.位勢(shì)法方案的調(diào)整―閉回路法

當(dāng)空格的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，說(shuō)明當(dāng)前平衡表給出的調(diào)運(yùn)方案不是最優(yōu)的，可以進(jìn)行調(diào)整，使總運(yùn)輸費(fèi)用減少。調(diào)整方法如下：1°為了使方案有較大改進(jìn)，先確定最小檢驗(yàn)數(shù)，即min{σij|σij<0}=σLK2°找出以空格(L,K)為一個(gè)頂點(diǎn)，其余頂點(diǎn)全是數(shù)字格的閉回路,規(guī)定空格(L,K)為閉回路的第一個(gè)頂點(diǎn)，閉回路上其它頂點(diǎn)依次為第二個(gè)頂點(diǎn)，第三個(gè)頂點(diǎn)，…(順時(shí)針或逆時(shí)針均可)。取閉回路上偶數(shù)序號(hào)頂點(diǎn)的最小運(yùn)量為調(diào)整運(yùn)量θ.3°閉回路上偶數(shù)序號(hào)頂點(diǎn)的運(yùn)量均減θ，奇數(shù)序號(hào)頂點(diǎn)運(yùn)量均加θ，不在閉回路上的運(yùn)量不變。調(diào)整中，如果偶數(shù)序號(hào)頂點(diǎn)中僅有一個(gè)數(shù)字格的運(yùn)量等于θ，則調(diào)整后，該格變?yōu)榭崭瘢蝗绻紨?shù)序號(hào)頂點(diǎn)中有兩個(gè)以上的數(shù)字格運(yùn)量等于調(diào)整量θ，則調(diào)整后，僅讓其中一個(gè)數(shù)字格變?yōu)榭崭瘢渌{(diào)整后要記“0”，表示該格為數(shù)字格。經(jīng)過(guò)這樣調(diào)整，就可以得到一個(gè)含有m+n-1個(gè)數(shù)字格的新的調(diào)運(yùn)方案。閉回路法(步驟3)如例1的初始方案經(jīng)檢驗(yàn)，存在一個(gè)負(fù)檢驗(yàn)數(shù)σ24＝－1，該方案不是最優(yōu)方案,在平衡表上找出閉回路。閉回路法調(diào)整例1方案－1銷地產(chǎn)地B1B2B3B4產(chǎn)量A1437A2314A3639銷量3656＋1

－1

＋1

－1

θ=min{1,3}=1如例1的初始方案經(jīng)檢驗(yàn)，存在一個(gè)負(fù)檢驗(yàn)數(shù)σ24＝－1，該方案不是最優(yōu)方案,在平衡表上找出閉回路。閉回路法調(diào)整例1方案－2銷地產(chǎn)地

B1B2B3B4產(chǎn)量A1527A2314A3639銷量3656z=5*3+2*10+3*1+1*8+6*4+3*5=85用位勢(shì)法求檢驗(yàn)數(shù)356320103-2-5930--2--21----912----對(duì)數(shù)字格，用式Cij

=（Ui+Vj）計(jì)算Ui和Vj

；對(duì)空格，用式ij=Cij

-（Ui+Vj），計(jì)算其檢驗(yàn)數(shù)。1z=5*3+2*10+3*1+1*8+6*4+3*5=853.3產(chǎn)銷不平衡的運(yùn)輸問(wèn)題（產(chǎn)大于銷）前面討論的運(yùn)輸問(wèn)題的理論和方法，都是以產(chǎn)銷平衡,即：為前提的。但是在實(shí)際問(wèn)題中產(chǎn)銷往往是不平衡的。對(duì)于產(chǎn)銷不平衡的運(yùn)輸問(wèn)題，可以把它們轉(zhuǎn)化成產(chǎn)銷平衡問(wèn)題，然后再用表上作業(yè)法求解。

1.產(chǎn)大于銷的情況，即由于總產(chǎn)量大于總銷量，就要考慮多余的物資在哪些產(chǎn)地就地貯存的問(wèn)題。將各產(chǎn)地的倉(cāng)庫(kù)設(shè)成一個(gè)假想銷地Bn+1，該地總需求量為再令運(yùn)價(jià)表中各地到虛設(shè)銷地Bn+1的單位運(yùn)Ci,n+1=0,i=1,2...m,則該問(wèn)題就轉(zhuǎn)化成一個(gè)產(chǎn)銷平衡問(wèn)題，可以用表上作業(yè)法求解了.在最優(yōu)解中，產(chǎn)地Ai到虛擬銷地Bn+1的運(yùn)量,實(shí)際上就是產(chǎn)地Ai就地貯存的多余物資數(shù)量。3.3產(chǎn)銷不平衡的運(yùn)輸問(wèn)題3.3產(chǎn)銷不平衡的運(yùn)輸問(wèn)題（銷大于產(chǎn)）

2.供不應(yīng)求的情況，即與產(chǎn)大于銷類似，當(dāng)銷大于產(chǎn)時(shí)，可以在產(chǎn)銷平衡表中虛設(shè)一個(gè)產(chǎn)地Am+1，該產(chǎn)地的產(chǎn)量為

再今虛擬產(chǎn)地Am+1到各銷地的單位運(yùn)價(jià)Cm+1,j=0,j=1,2,…n,則問(wèn)題可以轉(zhuǎn)化為一個(gè)產(chǎn)銷平衡運(yùn)輸問(wèn)題。在最優(yōu)解中，虛擬產(chǎn)地Am+1到銷地Bj的運(yùn)量實(shí)際上就是最后分配方案中銷地Bj的缺貨量。在產(chǎn)銷不平衡問(wèn)題中，如果某產(chǎn)地不允許將多余物資就地貯存，或不允許缺貨，則今相應(yīng)運(yùn)價(jià)Ci,n+1或Cm+1,j=M(M是相當(dāng)大的正數(shù))。3.3產(chǎn)銷不平衡的運(yùn)輸問(wèn)題

例2設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥，各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送化肥的單位運(yùn)價(jià)表如表3－25所示，試求總運(yùn)費(fèi)最省的花費(fèi)調(diào)運(yùn)方案。例2-1需求地區(qū)化肥廠IIIIIIIV產(chǎn)量ABC1614191313202219231725－506050最低需求最高需求3050707003010不限解：化肥廠總產(chǎn)量是50+60+50=160萬(wàn)噸；如果滿足其最低需求，需求總量是30+70+10=110萬(wàn)噸；這時(shí)情況屬于產(chǎn)大于銷；如果滿足其最高需求，因?yàn)榈谒膫€(gè)地區(qū)的最高需求是“不限”的，所以這種情況是屬于銷大于產(chǎn)。

例2例2-2需求地區(qū)化肥廠IIIIIIIV產(chǎn)量ABC1614191313202219231725－506050最低需求最高需求3050707003010不限解：既滿足其最低需求，又同時(shí)盡可能滿足其最高需求。確定“不限量”。前三個(gè)銷售地最低需求的總和30+70+0=100,總產(chǎn)量現(xiàn)在是160萬(wàn)噸，

第四個(gè)銷售地最多銷售160-100=60，所以,“不限量”＝60。最高需求量50+70+30+60=210,化肥廠總產(chǎn)量是50+60+50=160,銷量大于產(chǎn)量。為了求得平衡,假想增加一個(gè)化肥廠D,其年產(chǎn)量為210-160=50.產(chǎn)銷不平衡問(wèn)題，就轉(zhuǎn)化為一個(gè)產(chǎn)銷平衡的問(wèn)題。例2-3需求地區(qū)化肥廠IIIIIIIV產(chǎn)量ABC1614191313202219231715－506050最低需求最高需求305070700301060需求地區(qū)化肥廠產(chǎn)量ABCD50605050銷量I′I″3020II70III30IV′

IV″1050

1613221717

14141319151519192023MMM0M0M0例2(最優(yōu)解)需求地區(qū)化肥廠產(chǎn)量ABCD3020502003010302050605050銷量I′I″3020II70III30IV′

IV″1050

根據(jù)表上作法求解，得到最優(yōu)方案如表3-28所示。

我們注意，產(chǎn)銷平衡表中m=4,n=6,m+n-1=4+6-1=9，正好表中最優(yōu)解也有9個(gè)基變量。由于在變量個(gè)數(shù)相等的情況下，表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡(jiǎn)單得多，所以在解決實(shí)際問(wèn)題時(shí)，人們常常盡可能把某些線性規(guī)劃問(wèn)題化為運(yùn)輸問(wèn)題的數(shù)學(xué)模型，下面來(lái)介紹幾個(gè)典型的例子。

例3某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10,1525,20臺(tái)同一規(guī)格的柴油機(jī)，已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如下表，又知如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季度不交貨，每臺(tái)每季度的存儲(chǔ)維護(hù)費(fèi)用為0.15萬(wàn)元，試安排全年生產(chǎn)計(jì)劃，使總費(fèi)用最低。3.4應(yīng)用舉例3.4應(yīng)用舉例季度生產(chǎn)能力單位成本IIIIIIIV25臺(tái)35臺(tái)30臺(tái)10臺(tái)10.8萬(wàn)元11.1萬(wàn)元11.0萬(wàn)元11.3萬(wàn)元例3某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10,1525,20臺(tái)同一規(guī)格的柴油機(jī)，已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如下表，又知如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季度不交貨，每臺(tái)每季度的存儲(chǔ)維護(hù)費(fèi)用為0.15萬(wàn)元，試安排全年生產(chǎn)計(jì)劃，使總費(fèi)用最低。例3（解）季度生產(chǎn)能力單位成本IIIIIIIV25臺(tái)35臺(tái)30臺(tái)10臺(tái)10.8萬(wàn)元11.1萬(wàn)元11.0萬(wàn)元11.3萬(wàn)元解：產(chǎn)量25+35+30+10=100臺(tái)；需求量10+15+25+20=70臺(tái)。由于每個(gè)季度生產(chǎn)出來(lái)的柴油機(jī)不一定當(dāng)季交貨，所以設(shè)xij為第i季度生產(chǎn)的用于第j季度交貨的柴油機(jī)數(shù)。例3需求量10+15+25+20=70臺(tái)，

每臺(tái)每季度的存儲(chǔ)維護(hù)費(fèi)用為0.15萬(wàn)元。例3（分析產(chǎn)量）季度生產(chǎn)能力單位成本IIIIIIIV25臺(tái)35臺(tái)30臺(tái)10臺(tái)10.8萬(wàn)元11.1萬(wàn)元11.0萬(wàn)元11.3萬(wàn)元解：設(shè)第一個(gè)季度生產(chǎn)X1臺(tái)，X1包括X11用于當(dāng)季度交貨，也可以供給第二季度X12，然后還可以用于第三季度交貨X13，最后供給第四個(gè)季度X14。X1=X11+X12+X13+X14≤25X2=X22+X23+X24≤35

X3=X33+X34≤30X4=X44≤10例3需求量10+15+25+20=70臺(tái)，

每臺(tái)每季度的存儲(chǔ)維護(hù)費(fèi)用為0.15萬(wàn)元。例3（分析銷量）季度生產(chǎn)能力單位成本IIIIIIIV25臺(tái)35臺(tái)30臺(tái)10臺(tái)10.8萬(wàn)元11.1萬(wàn)元11.0萬(wàn)元11.3萬(wàn)元解：X11是為滿足第一季度銷量而生產(chǎn)的，第二個(gè)季度的銷量由兩部分供應(yīng)X12和X22。X12是第一個(gè)季度為第二個(gè)季度生產(chǎn)的，X22是第二個(gè)季度本身為滿足銷量生產(chǎn)的，所以X11=10X12+X22=15X13+X23+X33=25X14+X24+X34+X44=20例3建立產(chǎn)銷平衡表

各季度都生產(chǎn)產(chǎn)品，都可看作是產(chǎn)地；各季度都有銷售，都可看作是銷地。又因?yàn)檫@是一個(gè)產(chǎn)大于銷的運(yùn)輸問(wèn)題，需增加虛擬銷地D，銷售D的銷量=總產(chǎn)量－總銷量＝100－70=30。所以產(chǎn)銷平衡表如下：

例3（產(chǎn)銷平衡表）銷地產(chǎn)地IIIIIIIVD產(chǎn)量IIIIIIIV25353010銷量1015252030例3建立單位運(yùn)價(jià)表

已知每臺(tái)生產(chǎn)成本如下表，每臺(tái)每季度的存儲(chǔ)維護(hù)費(fèi)用為0.15萬(wàn)元。例3（單位運(yùn)價(jià)表）季度生產(chǎn)能力單位成本IIIIIIIV25臺(tái)35臺(tái)30臺(tái)10臺(tái)10.8萬(wàn)元11.1萬(wàn)元11.0萬(wàn)元11.3萬(wàn)元銷地產(chǎn)地IIIIIIIVDIIIIIIIV10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.300000例3最優(yōu)解決方案

用最小元素法寫出初始調(diào)運(yùn)方案，然后再進(jìn)行最優(yōu)性檢驗(yàn)，接著進(jìn)行方案的調(diào)整，最后得出最優(yōu)解，例3（最優(yōu)解決方案）銷地產(chǎn)地IIIIIIIVD產(chǎn)量IIIIIIIV101552010103025353010銷量1015252030例4某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F間四條航線的貨物運(yùn)輸任務(wù)。各航線的起點(diǎn)、終點(diǎn)、日航班數(shù)如下：表3-33

例4（表3-33，3-34）航線起點(diǎn)終點(diǎn)日航班數(shù)1234EBADDCFB3211

假定各航線使用的船只相同，各城市間的航程天數(shù)如下：表3-34

到從ABCDEFABCDEF0121477103138823015551413150172078517037852030又知每條船每次裝卸貨時(shí)間各需1天，問(wèn)該公司至少應(yīng)配備多少船？例4某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F間四條航線的貨物運(yùn)輸任務(wù)。各航線的起點(diǎn)、終點(diǎn)、日航班數(shù)如下：表3-33

例4（分析港口）航線起點(diǎn)終點(diǎn)日航班數(shù)1234EBADDCFB3211起點(diǎn)可以認(rèn)為是需要船只的，終點(diǎn)可以提供船只的。

需要船只的港口是A、B、E；可以提供船的是C、D、F。

例4某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F間四條航線的貨物運(yùn)輸任務(wù)。各航線的起點(diǎn)、終點(diǎn)、日航班數(shù)如下：表3-33

例4（分析