第四章-運(yùn)輸問題(Transportation-Problem)培訓(xùn)講學(xué)課件

運(yùn)輸問題(TransportationProblem)運(yùn)輸規(guī)劃的數(shù)學(xué)模型表上作業(yè)法產(chǎn)銷不平衡的運(yùn)輸問題有轉(zhuǎn)運(yùn)的運(yùn)輸問題7/22/20231一、運(yùn)輸問題的數(shù)學(xué)模型例：某運(yùn)輸問題的資料如下：單位銷地運(yùn)價(jià)產(chǎn)地B1B2B3B4產(chǎn)量A1291029A213425A384257銷量38467/22/202327/22/20233運(yùn)輸問題數(shù)學(xué)模型的一般形式

已知某產(chǎn)品有m個(gè)生產(chǎn)地點(diǎn)Ai（i=1,2,…，m），其供應(yīng)量(產(chǎn)量)分別為ai（i=1，2，…，m），有n個(gè)銷地Bj（j=1,2,…,n），其需要量分別為bj（j=1,2,…,n），從Ai到Bj運(yùn)輸單位物資的運(yùn)價(jià)(單價(jià))為cij，這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運(yùn)價(jià)表中，見表4-1，表4-2。有時(shí)可把這兩表合二為一。7/22/20234表4-1產(chǎn)銷平衡表銷地產(chǎn)地B1

B2┉Bn產(chǎn)量

A1A2┆Am

a1a2┆am銷量b1b2┈bn

7/22/20235表4-2單位運(yùn)價(jià)表7/22/20236運(yùn)輸問題數(shù)學(xué)模型的一般形式若用xij表示從Ai到Bj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，其數(shù)學(xué)模型為7/22/20237運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)1.運(yùn)輸問題有有限個(gè)最優(yōu)解2.運(yùn)輸問題約束條件的特點(diǎn)：運(yùn)輸問題的數(shù)學(xué)模型包含m×n個(gè)變量，(m+n)個(gè)約束方程，其系數(shù)矩陣的結(jié)構(gòu)比較松散且特殊。7/22/20238運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)

該系數(shù)矩陣中對應(yīng)于某一變量的系數(shù)向量，其分量中除第i個(gè)和第m+j個(gè)為1以外，其余的都為零，在約束條件中，前m個(gè)約束條件的含義是：由某一產(chǎn)地運(yùn)往各銷地的產(chǎn)品數(shù)量之和等于該產(chǎn)地的產(chǎn)量；后n個(gè)約束條件的含義是：由各產(chǎn)地運(yùn)往某一銷地的產(chǎn)品數(shù)量之和等于該銷地的銷量。7/22/20239運(yùn)輸問題的對偶問題運(yùn)輸問題的對偶問題可按照前面寫線性規(guī)劃問題的對偶問題的方法給出（略）7/22/202310運(yùn)輸問題的解運(yùn)輸問題也是一個(gè)線性規(guī)劃問題，其求解時(shí)仍然可以先找一個(gè)基可行解，進(jìn)行解的最優(yōu)性檢驗(yàn)，若不是最優(yōu)，就進(jìn)行迭代，繼續(xù)檢驗(yàn)和調(diào)整直到最優(yōu)，因此要求每步得到的解都是基可行解，需滿足(1)滿足所有約束條件；(2)基變量對應(yīng)的系數(shù)列向量線性無關(guān)；(3)解中非零變量的個(gè)數(shù)不能大于m+n-1個(gè)，原因是運(yùn)輸問題中雖有m+n個(gè)約束條件，但由于總產(chǎn)量等于總銷量，故只有m+n-1個(gè)約束條件是線性獨(dú)立的；(4)保持基變量的個(gè)數(shù)在迭代過程中為m+n-1個(gè)。7/22/202311第2節(jié)表上作業(yè)法表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡化方法，其實(shí)質(zhì)是單純形法,但具體計(jì)算和術(shù)語有所不同，其步驟可歸納為：(1)找出初始基可行解：即在(m×n)產(chǎn)銷平衡表上用西北角法或最小元素法、Vogel法給出m+n-1個(gè)數(shù)字，稱為數(shù)字格，它們就是初始基變量的取值。(2)求各非基變量的檢驗(yàn)數(shù)，即在表上計(jì)算空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。(3)確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。(4)重復(fù)(2)，(3)直到得到最優(yōu)解為止。7/22/202312例題單位銷地運(yùn)價(jià)產(chǎn)地產(chǎn)量311310719284741059銷量3656產(chǎn)銷平衡例：某食品公司下屬的A1、A2、A3，3個(gè)廠生產(chǎn)方便食品，要運(yùn)輸?shù)紹1、B2、B3、B4，4個(gè)銷售點(diǎn)，數(shù)據(jù)如下：求最優(yōu)運(yùn)輸方案。7/22/202313一初始基可行解的確定確定初始基可行解的方法很多，有西北角法，最小元素法和沃格爾(Vogel)法等，一般希望的方法是既簡便，又盡可能接近最優(yōu)解。下面分別予以介紹：1.

最小元素法此方法的基本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小，…，一直到給出初始基可行解為止。以上例進(jìn)行討論得下表：7/22/202314B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633總的運(yùn)輸費(fèi)用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元7/22/2023152.西北角法（或左上角法）：此法是純粹的人為規(guī)定，沒有理論依據(jù)和實(shí)際背景，但它易操作，特別適合在計(jì)算機(jī)上編程計(jì)算，因而受歡迎。方法如下：365674934490656404902562029005620090036360000000340002200036總的運(yùn)費(fèi)＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元7/22/2023163.沃格爾法最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，有時(shí)造成在其他處要多花幾倍的運(yùn)費(fèi)。沃格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因而對差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。

沃格爾法的步驟是：

第一步：在原表中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表4-17/22/202317表4-1第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表4-1中B2列是最大差額所在列。B2列中最小元素為4，可確定A3的產(chǎn)品先供應(yīng)B2的需要。得表4-2：7/22/202318同時(shí)將運(yùn)價(jià)表中的B2列數(shù)字劃去。如表4-3所示（表4-3）：表4-27/22/202319第三步：對表4-3中未劃去的元素再分別計(jì)算出各行、各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，重復(fù)第一、二步，直到給出初始解為止。用此法給出上例的初始解列于表4-4（下表）。

7/22/202320說明由以上可見：沃格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟相同。沃格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。本例用沃格爾法給出的初始解就是最優(yōu)解。7/22/202321二最優(yōu)解的判別最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。檢查的方法與單純形方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào)整。下面介紹兩種求檢驗(yàn)數(shù)的方法：1.閉回路法；2.位勢法7/22/2023221閉回路法在給出調(diào)運(yùn)方案的計(jì)算表上，如上例表，從每一空格出發(fā)找一條閉回路。它是以某空格為起點(diǎn)，用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時(shí)可以轉(zhuǎn)90°后，繼續(xù)前進(jìn)，直到回到起始空格為止。閉回路如圖(a),(b),(c)等所示。

7/22/202323閉回路法計(jì)算檢驗(yàn)數(shù)的經(jīng)濟(jì)解釋為：在已給出初始解的表中，可從任一空格出發(fā)，如(A1，B1)，若讓A1的產(chǎn)品調(diào)運(yùn)1噸給B1。為了保持產(chǎn)銷平衡，就要依次作調(diào)整：

在(A1，B3)處減少1噸，(A2，B3)處增加1噸，(A2，B1)處減少1噸，即構(gòu)成了以(A1，B1)空格為起點(diǎn)，其他為數(shù)字格的閉回路，如下表虛線所示。在這表中閉回路各頂點(diǎn)所在格的右上角數(shù)字是單位運(yùn)價(jià)7/22/202324可見這調(diào)整的方案使運(yùn)費(fèi)增加

(+1)×3+(-1)×3+(+1)×2+(-1)×１=1(元)

將“1”這個(gè)數(shù)填入(A1，B1)格，這就是檢驗(yàn)數(shù)。按以上所述，可找出所有空格的檢驗(yàn)數(shù)，見下表。7/22/202325B1B2B3B4產(chǎn)量A17A24A39銷量365600000121-112100當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時(shí)，說明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)。閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都會產(chǎn)生困難。7/22/202326

運(yùn)輸問題的約束條件共有m+n個(gè)，其中：m是產(chǎn)地產(chǎn)量的限制；n是銷地銷量的限制。其對偶問題也應(yīng)有m+n個(gè)變量，據(jù)此：σij=cij－(ui+vj),其中前m個(gè)計(jì)為ui（i=1.2…m）,前n個(gè)計(jì)為vj（j=1.2…n）由單純形法可知，基變量的σij＝

0∴cij－(ui+vj)＝0因此ui,vj可以求出。⑵.位勢法7/22/202327仍以上面的例子說明。

第一步：按最小元素法給出表的初始解，然后做下表：即在對應(yīng)表的數(shù)字格處填入單位運(yùn)價(jià)：7/22/202328第二步：在上表中增加一行一列，在列中填入ui，在行中填入vj，得下表：先令u1=0，然后按ui+vj=cij，i，j∈B相繼地確定ui，vj。由上表可見，當(dāng)u1=0時(shí)，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10時(shí)，由u3+v4=5可得u3=-5，以此類推可確定所有的ui，vj的數(shù)值。

7/22/202329第三步：按σij=cij-(ui+vj),i,j∈N計(jì)算所有空格的檢驗(yàn)數(shù)。如

σ11=c11-(u1+v1)=3-(0+2)=1，σ12=c12-(u1+v2)=11-(0+9)=2

這些計(jì)算可直接在上表中進(jìn)行。

為了方便，特設(shè)計(jì)計(jì)算表，如下表所示在此表中還有負(fù)檢驗(yàn)數(shù)，說明未得最優(yōu)解，還可以改進(jìn)。7/22/202330亦即：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表B1B2B3B4A1293100A21829－1A3－34－25－529310u2+v1=1

u2+v3=2

u3+v2=4u1+v4=10

u1+v3=3u3+v4=5令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3v4＝10(ui+vj)7/22/202331按σij=cij－(ui+vj)計(jì)算檢驗(yàn)數(shù)，并以σij≥0檢驗(yàn)，或用(ui+vj)

－cij

≤0檢驗(yàn)。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)－B1B2B3B4A11200A2010－1A3100120＝表中還有負(fù)數(shù)，說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整。σij7/22/202332三解的改進(jìn)閉回路調(diào)整法當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基本可行解不是最優(yōu)解。在這種情況下，應(yīng)該對基本可行解進(jìn)行調(diào)整，即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下降，具體步驟為：（1）選負(fù)檢驗(yàn)數(shù)中最小者rk，那么xrk

為主元，作為進(jìn)基變量（上頁圖中x24）;（2）以xrk

為起點(diǎn)找一條閉回路，除xrk外其余頂點(diǎn)必須為基變量格（上頁圖中的回路）;7/22/202333解的改進(jìn)閉回路調(diào)整法（3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號，xrk為1，沿一個(gè)方向（順時(shí)針或逆時(shí)針）依次給各頂點(diǎn)標(biāo)號；（4）求=Min{xijxij對應(yīng)閉回路上的偶數(shù)標(biāo)號格}=xpq，那么確定xpq為出基變量，為調(diào)整量；（5）對閉回路的各奇標(biāo)號頂點(diǎn)調(diào)整為：xij+，對各偶標(biāo)號頂點(diǎn)調(diào)整為：xij-，特別xpq-=0，xpq變?yōu)榉腔兞俊Ｖ貜?fù)(2)、(3)步，直到所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解。7/22/202334接上例：B1B2B3B4產(chǎn)量A17A24A39銷量3656313463（＋1）（＋1）（－1）（－1）7/22/202335B1B2B3B4產(chǎn)量A1527A2314A3639銷量36566563銷量9A34A27A1產(chǎn)量B4B3B2B1313463（＋1）（＋1）（－1）（－1）7/22/202336B1B2B3B4A10200A20210A390120經(jīng)檢驗(yàn)所有σij≥0得到最優(yōu)解，最小運(yùn)費(fèi)為85元。v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表10393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)7/22/202337⑴.無窮多最優(yōu)解：產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。如上例：（1.1）中的檢驗(yàn)數(shù)是0，經(jīng)過調(diào)整，可得到另一個(gè)最優(yōu)解：可在最優(yōu)表中以(1，1)為調(diào)入格，作閉回路(1，1)+-(1，4)--(2，4)+-(2，1)--(1，1)+確定θ=min(2,3)=2。經(jīng)調(diào)整后得到另一最優(yōu)解，見下表：

四、需要說明的幾個(gè)問題7/22/2023387/22/202339

⑵退化：表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)，在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證有(m+n-1)個(gè)數(shù)字格。一般可在劃去的行和列的任意空格處加一個(gè)0即可。在用閉回路法調(diào)整時(shí)，在閉回路上出現(xiàn)兩個(gè)和兩個(gè)以上的具有(-1)標(biāo)記的相等的最小值。這時(shí)只能選擇其中一個(gè)作為調(diào)入格。而經(jīng)調(diào)整后，得到退化解。這時(shí)另一個(gè)數(shù)字格必須填入一個(gè)0，表明它是基變量。當(dāng)出現(xiàn)退化解后，并作改進(jìn)調(diào)整時(shí)，可能在某閉回路上有標(biāo)記為(-1)的取值為0的數(shù)字格，這時(shí)應(yīng)取調(diào)整量θ=0。7/22/202340第三節(jié)產(chǎn)銷不平衡的運(yùn)輸問題

前面所講表上作業(yè)法，都是以產(chǎn)銷平衡為前提條件的，但是實(shí)際問題中產(chǎn)銷往往是不平衡的，這就需要設(shè)法把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。一、總產(chǎn)量大于總銷量即此時(shí)，運(yùn)輸問題的數(shù)學(xué)模型可寫為7/22/202341要求解此問題，需要先將原問題變成平衡問題，可以假設(shè)一個(gè)銷地Bn+1(即實(shí)際問題中考慮產(chǎn)地的存量)，即：7/22/202342單位運(yùn)價(jià)表中的單位運(yùn)價(jià)二、銷大于產(chǎn)：同樣假設(shè)一個(gè)產(chǎn)地即可，變化同上。7/22/202343B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例題：然后用表上作業(yè)法求解即可（略）7/22/202344已知某運(yùn)輸問題的資料如下表所示B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125表中的發(fā)量、收量單位為：噸，運(yùn)價(jià)單位為：元/噸試求出最優(yōu)運(yùn)輸方案.練習(xí)：7/22/202345解：用最小元素法求初始方案B1B2B3B4發(fā)量A112315A210212A313013收量1013125B1B2B3B4A153A211A324運(yùn)費(fèi)為108元/噸2、用位勢法判斷：B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表7/22/202346B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5v4＝37/22/202347B1B2B3B4ui

A1530A211－2A3241vj

3153B1B2B3B4ui

A131530A21－131－2A342641vj

3153(ui+vj)7/22/202348B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－131A34264cij－B1B2B3B4A1－1500A204－10A3－1010＝表中還有負(fù)數(shù)，說明沒有得到最優(yōu)解，調(diào)整運(yùn)輸方案。σij(ui+vj)7/22/202349B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的運(yùn)送方案B1B2B3B4A153A212A