1、第第4章章 運(yùn)輸問題運(yùn)輸問題p第1節(jié) 運(yùn)輸問題的數(shù)學(xué)模型p第2節(jié) 表上作業(yè)法p第3節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法p第4節(jié) 應(yīng)用舉例2第1節(jié) 運(yùn)輸問題的數(shù)學(xué)模型v已知有m個(gè)生產(chǎn)地點(diǎn)Ai,i=1,2,，m。可供應(yīng)某種物資，其供應(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à)表中，見表3-1，表3-2。有時(shí)可把這兩表合二為一。 銷地產(chǎn)地1 2 n產(chǎn)量 12m A 1A2Am銷量B1 B2 BNn 第1節(jié) 運(yùn)輸問題的數(shù)學(xué)模型0)23(, 2 , 1) 1

2、3(, 2 , 1. .min1111ijnjijijmijijminjijijxmiaxnjbxtsxcz4v若用xij表示從Ai到Bj的運(yùn)量，那么在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案的數(shù)學(xué)模型為第1節(jié) 運(yùn)輸問題的數(shù)學(xué)模型行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112115v這就是運(yùn)輸問題的數(shù)學(xué)模型。它包含mn個(gè)變量，(m+n)個(gè)約束方程，其系數(shù)矩陣的結(jié)構(gòu)比較松散，且特殊。第1節(jié) 運(yùn)輸問題的數(shù)學(xué)模型njminjmiimiijnjijjaxxb1111116該系數(shù)矩陣中對應(yīng)于變量xij的系數(shù)向量Pij，其分量中除

3、第i個(gè)和第m+j個(gè)為1以外，其余的都為零。即 Pij=(0, ,1,0,0,1,0,0)T=ei+em+j對產(chǎn)銷平衡的運(yùn)輸問題，由于有以下關(guān)系式存在：第2節(jié) 表上作業(yè)法 表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡化方法，其實(shí)質(zhì)是單純形法。但具體計(jì)算和術(shù)語有所不同。可歸納為： (1) 找出初始基可行解。即在(mn)產(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) 確定換入變量和換出變量，找出新的基可行解。

4、在表上用閉回路法調(diào)整。 (4) 重復(fù)(2)，(3)直到得到最優(yōu)解為止。 7第2節(jié) 表上作業(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īng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。 8第2節(jié) 表上作業(yè)法 解：解：先作出這問題的產(chǎn)銷平衡表和單位運(yùn)價(jià)表，見表3-3，表3-4 銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 7 4 9 銷量 3 6

5、 5 6 9表3-4 產(chǎn)銷平衡表表3-3 單位運(yùn)價(jià)表 2.1 確定初始基可行解minjjidba1110與一般線性規(guī)劃問題不同，產(chǎn)銷平衡的運(yùn)輸問題總是存在可行解。因有必存在xij0，i=1，m，j=1，n，這就是可行解。又因0 xijmin(aj，bj)，故運(yùn)輸問題必存在最優(yōu)解。2.1 確定初始基可行解11確定初始基可行解的方法很多，有西北角法，最小元素法和伏格爾(Vogel)法。一般希望的方法是既簡便，又盡可能接近最優(yōu)解。下面介紹兩種方法： 1. 最小元素法基本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小。一直到給出初始基可行解為止。以例1進(jìn)行討論。第一步：從表3-3

6、中找出最小運(yùn)價(jià)為1，這表示先將A2的產(chǎn)品供應(yīng)給B1。因a2b1，A2除滿足B1的全部需要外，還可多余1噸產(chǎn)品。在表3-4的(A2，B1)的交叉格處填上3。得表3-5。并將表3-3的B1列運(yùn)價(jià)劃去。得表3-6。2.1 確定初始基可行解12表 3-5 和表3-62.1 確定初始基可行解銷 地 加工廠 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 13第二步：在表3-6未劃去的元素中再找出最小運(yùn)價(jià)2，確定A2多余的1噸供應(yīng)B3，并給出表3-7，表3-8。2.1 確定初始基可行解銷 地 加工廠 B1 B2 B3 B4 產(chǎn)量 A1 A2 A3 3 6 4

7、 1 3 3 7 4 9 銷量 3 6 5 6 14第三步：在表3-8未劃去的元素中再找出最小運(yùn)價(jià)3；這樣一步步地進(jìn)行下去，直到單位運(yùn)價(jià)表上的所有元素劃去為止，最后在產(chǎn)銷平衡表上得到一個(gè)調(diào)運(yùn)方案，見表3-9。這方案的總運(yùn)費(fèi)為86元。 2.1 確定初始基可行解15用最小元素法給出的初始解是運(yùn)輸問題的基可行解，其理由為：v(1) 用最小元素法給出的初始解，是從單位運(yùn)價(jià)表中逐次地挑選最小元素，并比較產(chǎn)量和銷量。當(dāng)產(chǎn)大于銷，劃去該元素所在列。當(dāng)產(chǎn)小于銷，劃去該元素所在行。然后在未劃去的元素中再找最小元素，再確定供應(yīng)關(guān)系。這樣在產(chǎn)銷平衡表上每填入一個(gè)數(shù)字，在運(yùn)價(jià)表上就劃去一行或一列。表中共有m行n列，總

8、共可劃(n+m)條直線。但當(dāng)表中只剩一個(gè)元素時(shí)，這時(shí)當(dāng)在產(chǎn)銷平衡表上填這個(gè)數(shù)字時(shí)，而在運(yùn)價(jià)表上同時(shí)劃去一行和一列。此時(shí)把單價(jià)表上所有元素都劃去了，相應(yīng)地在產(chǎn)銷平衡表上填了(m+n-1)個(gè)數(shù)字。即給出了(m+n-1)個(gè)基變量的值。2.1 確定初始基可行解1111jmijieeP11jix11jiP16用最小元素法給出的初始解是運(yùn)輸問題的基可行解，其理由為：v(2) 這(m+n-1)個(gè)基變量對應(yīng)的系數(shù)列向量是線性獨(dú)立的。證若表中確定的第一個(gè)基變量為它對應(yīng)的系數(shù)列向量為:因當(dāng)給定 的值后，將劃去第i1行或第j1列，即其后的系數(shù)列向量中再不出現(xiàn)ei1或em+j1，因而 不可能用解中的其他向量的線性組合

9、表示。類似地給出第二個(gè)，第(m+n-1)個(gè)。這(m+n-1)個(gè)向量都不可能用解中的其他向量的線性組合表示。故這(m+n-1)個(gè)向量是線性獨(dú)立的。 2.1 確定初始基可行解17 用最小元素法給出初始解時(shí)，有可能在產(chǎn)銷平衡表上填入一個(gè)數(shù)字后，在單位運(yùn)價(jià)表上同時(shí)劃去一行和一列。這時(shí)就出現(xiàn)退化。關(guān)于退化時(shí)的處理將在2.4節(jié)中講述。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1 16A2 10A3 22銷量 814 12 14484285101112346911 821014 86課堂練習(xí)課堂練習(xí)總費(fèi)用 z= =104+611+82+23+145+86=24634i=1 j=1cijijx2.1 確定初始基可行解1

10、9 2. 伏格爾法 最小元素法的缺點(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)。2.1 確定初始基可行解20v伏格爾法的步驟是：v第一步：在表3-3中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表3-10。2.1 確定初始基可行解21v第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表3-10中B2列是最大差額所在列。B2列中最小元素為4，可確定A3

11、的產(chǎn)品先供應(yīng)B2的需要。得表3-112.1 確定初始基可行解銷 地 加工廠 B1 B2 B3 B4 行差額 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 2 列差額 2 1 3 22v同時(shí)將運(yùn)價(jià)表中的B2列數(shù)字劃去。如表3-12所示。2.1 確定初始基可行解23v第三步：對表3-12中未劃去的元素再分別計(jì)算出各行、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。重復(fù)第一、二步。直到給出初始解為止。用此法給出例1的初始解列于表3-13。2.1 確定初始基可行解24v由以上可見：伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟相同。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。v本例用伏格爾法給出的初始解就是最優(yōu)解。沃格爾法 罰數(shù)=次小費(fèi)用-最小費(fèi)用 找出最大的罰數(shù)行或列所對應(yīng)的最小費(fèi)用優(yōu)先安排。 重復(fù)計(jì)算步驟1和2 銷地產(chǎn)地B1B2B3B4