1、1,第3章 運輸問題,線性規(guī)劃續(xù),2,主要內(nèi)容,運輸問題的特點及模型描述 網(wǎng)絡(luò)圖 線性規(guī)劃模型 表上作業(yè) 表上作業(yè)法 平衡運輸問題 不平衡運輸問題,3,一、運輸問題的特點及模型,原問題：產(chǎn)地到銷地之間運送貨物的最佳路徑 特點： 多個產(chǎn)地和多個銷地； 每個產(chǎn)地的產(chǎn)量不同，每個銷地的銷量也不同； 各產(chǎn)銷兩地之間的運價不同。 目標 合理組織調(diào)運，既滿足各銷地的要求，又使總的運輸費用（或里程、時間等）最小。,4,運輸問題,設(shè)有同一種貨物從m個出發(fā)地1，2，m運往n個到達地1，2，n。第i個出發(fā)地的供應(yīng)量（Supply）為si（si0），第j個到達地的需求量（Demand）為 dj（dj0）。 每單位貨

2、物從產(chǎn)地 i 運到銷地 j 的運價為Cij。求一個使總運費最小的運輸方案。 1 2 3 n 供應(yīng) 1 c11 c1n s1 2 c21 成本 c2n s2 cij m cm1 cmn sm 需求 d1 dn ,出 發(fā) 地,到達地,5,運輸問題,引例：設(shè)某電視機廠有三個分廠，生產(chǎn)同一種彩色電視機，供應(yīng)該廠在市內(nèi)的四個門市部銷售。已知三個分廠的日生產(chǎn)能力分別是50，60，50臺，四個門市部的日銷量分別為40，40，60，20臺。從各個分廠運往各門市部的運費如下表所示，試安排一個運費最低的運輸計劃。,6,單位：元/臺,7,2,3,2,1,3,4,1,s2=60,s3=50,d1=40,d2=40,d

3、3=60,d4=20,s1=50,供應(yīng)量,供應(yīng)地,運價,需求量,需求地,9,12,9,6,7,3,7,7,6,5,9,11,運輸問題網(wǎng)絡(luò)圖,8,運輸問題線性規(guī)劃模型,設(shè)xij為由第i個工廠運到第j個門市部的電視機臺數(shù)，cij為由第i個工廠運到第j個門市部的運費，則原運輸問題的線性規(guī)劃模型為：,9,供應(yīng)地約束,需求地約束,mn個變量，m+n個條件,運輸問題的表格表示,xij,cij,10,11,運輸問題,三類運輸問題： 產(chǎn)銷平衡： 產(chǎn)大于銷： 產(chǎn)小于銷：,12,運輸問題,產(chǎn)銷平衡的運輸問題模型 令xij為 從i地運到j(luò)地的數(shù)量 Min Z = （Cij0) （i= 1,2,m) 供應(yīng)約束 (j=

4、 1,2,n) 需求約束 xij0，i=1,1,m; j=1,2,n 由 cij、si、dj 組成的 （m+1)(n+1) 矩陣稱為運輸矩陣,13,約束方程共有m+n個，由于si=dj，因此約束方程只有m+n-1個方程是線性獨立的。因此運輸問題的基本可行解有m+n-1個分量。,14,引例方程組中方程的線性獨立問題： x1+x2+x3=3 2x1+x2+x4=6 3x1+2x2+x3+x4=9 系數(shù)的增廣矩陣為： 1 1 1 0 3 1 1 1 0 3 2 1 0 1 6 2 1 0 1 6 3 2 1 4 9 0 0 0 0 0,15,運輸問題,產(chǎn)大于銷時約束條件,（j= 1,2,n),產(chǎn)小于

5、銷時約束條件,（i= 1,2,m),（i= 1,2,m),（j= 1,2,n),產(chǎn)銷不平衡的運輸問題模型,16,不平衡的運輸問題,17,平衡運輸問題的表上作業(yè)法,(一)運輸問題初始可行解的獲得 西北角法從西北角的第一格開始安排運輸計劃 具體步驟,18,平衡運輸問題的表上作業(yè)法,具體步驟 取其相應(yīng)的供應(yīng)量和需求量中的最小值作為初始基本可行解的第一個分量 如果第一個工廠的生產(chǎn)量大于第一個銷售點的需求，那么就由第一個工廠全部滿足第一個銷售點的需要，工廠商品的剩余部分運八第二個銷售點； 如果第一個工廠的生產(chǎn)量小于第一個銷售點的需求量，則先將第一個工廠的全部產(chǎn)品運往第一個銷售點，不足的需求由第二個補足。

6、,19,產(chǎn) 地,銷地,x11,x12,x22,x23,x33,x346個變量構(gòu)成一個基本初始可行解。,40,10,30,30,30,20,10,30,30,30,20,20,西北解法的特點 優(yōu)點：簡單易行，容易得到基本初始可行解； 缺點：沒有考慮運費的因素，因此距離最優(yōu)解較遠。,21,最小元素法（最小費用法）：“就近供應(yīng)” 從單位運價表中選取最低運價的空格開始供求分配： 當供應(yīng)量大于需求量，取值為需求量，劃去該空格所在的列 當供應(yīng)量小于需求量，取值為供應(yīng)量，劃去該空格所在的行 重復(fù)上述步驟，直到把所有的空格都劃去為止。 如果這樣選出的空格共有m+n-1個，則構(gòu)成一個初始基本可行解。,22,初始

7、可行解的獲得,前例中： 最小元素法求初始解,20,10,30,20,40,40,20,30,10,40,10,0,0,0,0,0,0,0,伏格爾法 思路：一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調(diào)運時，運費增加越多，因而，對差額最大處，就應(yīng)當采用最小運費調(diào)運。,23,步驟： 1. 分別計算各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行； 2. 從行或列差額中選出最大者，選擇它所在行或列中的最小元素； 3. 對表中未劃去的元素再分別計算出各行、各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。重復(fù)第1、2

8、步。直至給出初始解為止。,24,例：P80（表3-3，3-4）。表中B2列是最大差額所在列，B2列中最小元素為4，可確定A3的產(chǎn)品先供應(yīng)B2的需要。同時將運價表的B2列數(shù)字劃去。,25,26,27,28,伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟相同。伏格爾法給出的初始解比最小元素法給出的初始解更接近最優(yōu)解。,29,30,最優(yōu)解檢驗,(二)最優(yōu)解檢驗 依舊是根據(jù)檢驗數(shù)ij的值來判斷其是否為最優(yōu)解。方法有兩種： 位勢法 閉回路法,31,位勢法：假設(shè)每一行都有一個位勢，記為ui,每一列有一個位勢，記為vj，它們有如下關(guān)系： 如果xij是基變量，則有 cij-ui-vj=0 如果是

9、非基變量，則有： cij-ui-vj=ij 由于基變量有m+n-1個，位勢有m+n個，我們可以從m+n個位勢變量中任設(shè)其中一個為任意值，就可以求出其他位勢值，進而求得檢驗數(shù)ij 。,32,位勢的計算過程如下： 設(shè)u1=0 由c11-u1-v1=0v1=c11=9 由c12-u1-v2=0v2=c12=12 由c22-u2-v2=0u2=c22-v2=-9 由c23-u2-v3=0v3=c23-u2=16 由c33-u3-v3=0u3=c33-v3=-7 由c34-u3-v4=0v4=c34-u3=18,33,進一步，求得各非基變量的檢驗數(shù)： 13 =c13-u1-v3=9-0-16=-7 14

10、 =c14-u1-v4=6-0-18=-12 21 =c21-u2-v1=7-(-9)-9=7 24 =c24-u2-v4=7-(-9)-18=-2 31 =c31-u3-v1=6-(-7)-9=4 32 =c32-u3-v2=5-(-7)-12=0 具體計算過程在表中進行,34,位勢及檢驗數(shù)的計算,注：格子中，帶數(shù)字為基本可行解，不帶數(shù)字為檢驗數(shù),0,40,10,30,30,30,20,-9,-7,18,16,12,9,-12,-7,7,4,0,-2,35,閉回路法 一個可以作為表上作業(yè)法初始方案的表中，共有m+n-1個實格和mn-(m+n-1)個空格。從一個空格出發(fā)，沿水平或豎直方向前進，

11、遇到一個適當?shù)膶嵏駮r按與前進方向垂直的方向前進，再遇到適當?shù)膶嵏駮r再轉(zhuǎn)向前進，這樣繼續(xù)轉(zhuǎn)向和前進若干次后必然回到原來出發(fā)的那個空格，這就形成一條由水平線段和豎直線段所組成的封閉折線，稱之為閉回路。,36,閉回路的性質(zhì)： m+n-1個變量構(gòu)成基變量的充要條件是它不含閉回路 在m+n-1個基變量(實格，也稱為基格)中加入任何一個非基變量，則加入空格后的m+n個格子必含有惟一的閉回路,37,在閉回路中，轉(zhuǎn)向之處稱為頂點。從空格算起第奇數(shù)轉(zhuǎn)向的稱為奇數(shù)頂點，第偶數(shù)次轉(zhuǎn)向的稱為偶數(shù)頂點。 定義空格所對應(yīng)的非基變量xij的檢驗數(shù)為： ij=奇數(shù)頂點的運價之和-偶數(shù)頂點的運價之和 其中 表示對“奇數(shù)頂點”上

12、的元素取和， 表示對“偶數(shù)頂點”上的元素取和。 現(xiàn)在用前例的初始方案表作為例子加以說明。,38,利用閉回路法求檢驗數(shù),40,10,30,30,30,20,-12,6+3+9-12-7-11=-12,7,7+12-9-3=7,4,0,-2,-7,39,最優(yōu)判定法則,表上作業(yè)法的最優(yōu)判定法則是：一個可以直接作為表上作業(yè)法的初始方案的調(diào)運方案，如果它所有的檢驗數(shù)均為非負數(shù)，則這個方案是最優(yōu)的。,40,檢驗數(shù)的含義,檢驗數(shù)ij的意義： 對任意空格施行如下變換(稱為變換E)：在它閉回路的奇轉(zhuǎn)角點上增加1單位物資，而在偶轉(zhuǎn)角點上減少1單位物資。易見，經(jīng)變換E后方案仍是平衡的。 一般地， ij就是施行變換E

13、時總運費的增加量。如果某一空格的ij 0，那么對施行變換E時空格變?yōu)閷嵏?，總運費將減少(- ij)單位。,41,檢驗數(shù)的含義,-12,7,4,0,-2,-7,40,10,30,30,30,20,21=(7+12)-(3+9) =7,13=(9+3)-(12+7) =-7,41,42,閉回路調(diào)整,對存在負檢驗數(shù)的方案必須進行調(diào)整，調(diào)整方法如下： (1)選取調(diào)入空格。任何檢驗數(shù)為負數(shù)的空格都可作為調(diào)入空格。如果有多個檢驗數(shù)為負的空格，一般選取絕對值最大的格。 (2)選取調(diào)出實格。調(diào)出實格在調(diào)整后的新方案中將成為空格。調(diào)出實格可選擇這樣的實格：在調(diào)入空格閉回路的各個偶轉(zhuǎn)角點中運量最小的格。如果有多個

14、這樣的實格，任選其一。 (3)調(diào)整。設(shè)所選調(diào)出實格的運量為P(稱為調(diào)整量)，則在調(diào)入空格閉回路的各偶轉(zhuǎn)角點的運量都減少P，各奇轉(zhuǎn)角點的運量都增加P，得到新方案。 (4)計算新方案檢驗數(shù)后判定是否為最優(yōu)方案，若還不是，重復(fù)上述步驟。,43,40,10,30,30,30,20,-12,-7,7,4,0,-2,44,40,40,20,40,10,5,-5,-8,0,-2,10,12,10,45,40,40,20,40,10,5,-5,-8,0,-2,10,12,46,40,40,20,40,10,-3,3,8,0,6,10,4,10,20,30,0,-5,-3,9,8,12,6,47,30,40,2

15、0,40,-3,3,8,0,6,4,10,20,48,0,30,40,20,40,-2,0,6,9,5,6,3,5,0,3,7,10,20,3,40,10,30,49,此時，所有空格內(nèi)的檢驗數(shù)都已非負，表明上述解就是最優(yōu)解。 即：x13=30,x12=20,x22=40,x23=20,x31=40,x33=10 這種最優(yōu)方案的運費為： Zmin=9*30+6*20+3*40+7*20+6*40+9*10 =980,50,由于非基變量的檢驗數(shù)為0，以該格的變量為換入變量，繼續(xù)迭代還可以求得另一組最優(yōu)解：,51,0,40,20,-2,0,6,9,5,6,3,5,0,3,7,20,3,40,10,3

16、0,52,相應(yīng)的運費為：930620330730640510980,0,30,30,-2,0,6,9,5,6,3,5,3,7,20,3,40,0,30,10,0,53,解的退化問題,基本可行解中的一個或數(shù)個分量為0。此時，基本可行解的非零分量數(shù)目少于m+n-1個，無法再用位勢法或閉回路法計算檢驗數(shù)。,54,解的退化問題,解決的辦法：將退化為零的兩個空格中的任一個填入一個零，把它當成退化的基本解，然后按以前的步驟進行迭代計算。 應(yīng)當注意的是，零要加在不可估值的空格中： 可估值空格：能構(gòu)成閉回路 不可估值空格：不能構(gòu)成閉回路,55,20,10,20,產(chǎn)地,銷地,-4,30,20,產(chǎn)地,銷地,0,3

17、0,20,產(chǎn)地,銷地,20,30,0,產(chǎn)地,銷地,56,2,3,5,1,1,4,0,0,不可估值空格,可估值空格,產(chǎn)地,銷地,57,平衡運輸問題解題步驟小結(jié),列出關(guān)于供給、需求及運費的表格 尋找初始基本可行解 西北角法 最小費用法 伏格爾法 求檢驗數(shù) 位勢法 閉回路法 解的最優(yōu)性檢驗 對解進行閉回路調(diào)整（如果必要）,58,產(chǎn)銷不平衡運輸問題的表上作業(yè),產(chǎn)大于銷：設(shè)立虛擬的銷地 產(chǎn)小于銷：設(shè)立虛擬的產(chǎn)地,59,運輸模型的活用,例1.62 求以下運輸問題的初始解,這是一個產(chǎn)大于銷 的問題，差額為5。 表上作業(yè)是假想一個 銷地B0,需求量為5， 從A1,A2到B0的運價 為0。這樣就將此轉(zhuǎn) 化為產(chǎn)銷

18、平衡問題。,60,產(chǎn)大于銷,61,計算過程：,4,2,2,1,5,2,1,6,5,0,3,1,2,1,-3,2,2,3,62,產(chǎn)小于銷,例：某農(nóng)場獲得大豐收，四塊土地A1、A2、A3、A4的產(chǎn)量分別2、3、4、6千噸。現(xiàn)在準備把這批糧食貯藏到B1,B2,B3等3個倉庫里，已知這三個倉庫的最大容量分別為7、5、7千噸，每塊土地和各倉庫的距離如下表所示，試求出最合理的調(diào)運方案。(距離以公里為單位),63,64,產(chǎn)小于銷,65,4,3,2,3,3,2,2,3,5,3,2,2,66,4,3,2,3,3,2,2,0,2,2,-2,2,1,0,1,8,7,7,8,0,-1,5,2,67,2,5,2,3,1

19、,4,2,0,68,2,5,2,3,1,4,2,69,得最優(yōu)調(diào)運方案： x11=2, x22=3, x32=2, x33=2, x41=1, x43=5, x51=4,70,例：設(shè)有三個化肥廠，供應(yīng)四個地區(qū)的農(nóng)用化肥。除第四個地區(qū)不宜用第三個廠生產(chǎn)的化肥外，假定各廠的化肥在這些地區(qū)使用的效果是一樣的。各化肥廠的年產(chǎn)量、各地區(qū)的年需要量以及各化肥廠到各地區(qū)運送化肥的單價如下表，試求總費用最少的化肥調(diào)撥方案。,71,72,解，這個問題要解決如下幾個難點： 第四個地區(qū)的最大需求量應(yīng)該等于各廠在供給其他地區(qū)的最低需求后的最大剩余量： 160-(30+70+0)=60 產(chǎn)量小于最大需求量，應(yīng)該設(shè)立一個虛

20、擬的產(chǎn)地（第四個產(chǎn)地），其產(chǎn)量為供需之間的缺口： 210-160=50 由于第一個地區(qū)存在最低需求和最高需求，我們將其需求量視為兩個部分，第一個為必須滿足的，意味著該部分的需求不能從虛擬產(chǎn)地獲得，因此我們設(shè)從虛擬產(chǎn)地向第一地區(qū)第一部分供給的運輸費用為大M，而第二個部分則既可從實產(chǎn)地獲得，也可以從虛產(chǎn)地獲得。其他地區(qū)類似處理，得下表：,73,74,50,20,30,10,10,30,10,50,0,2,2,0,M+3,3,M+4,-1,22,M-22,4,-M+22,-M+20,-2,2,1,75,50,20,30,20,30,10,50,0,M-18,2,-M+20,M+3,M-17,M+4,

21、M-21,M+2,-2,M-16,2,-2,-M+22,M-19,M-20,0,76,50,20,30,20,30,10,50,0,2,2,M+3,3,M+4,-1,M+2,M-22,4,2,-2,2,1,0,0,2,M-20,77,50,20,30,20,30,10,50,0,2,2,M+1,1,M+2,-3,M,M-20,4,2,2,1,0,0,2,M-20,78,50,20,20,0,10,20,30,5,5,M+1,1,M+2,M,M-20,7,2,4,3,30,-1,M-23,30,3,79,50,20,20,0,10,20,30,4,4,M+3,3,M+2,M,M-22,7,2,4,2,30,M-22,30,2,1,80,下面是將需求地4看成一個整體來求解的情形 原因：虛產(chǎn)地的最大產(chǎn)量是50萬噸，而第四個地區(qū)的最大需求量是60萬噸，所以該地區(qū)至少可以從其他三個實產(chǎn)地獲得10萬噸，以滿足該地區(qū)的最低需求量（也即最低需求量能夠得到滿