運(yùn)籌學(xué)胡運(yùn)權(quán)第五版課件第三章

1、第三章 運(yùn)輸問(wèn)題,Transportation Problem,3.1 運(yùn)輸問(wèn)題的典例和數(shù)學(xué)模型,例 某食品公司經(jīng)營(yíng)糖果業(yè)務(wù)，公司下設(shè)三個(gè)加工廠A1、A2、A3，四個(gè)銷售門市部B1、B2、B3、B4。已知每天各自的生產(chǎn)量、銷售量及調(diào)運(yùn)時(shí)的單位糖果的運(yùn)輸費(fèi)用等情況。 問(wèn)：如何調(diào)運(yùn)可使總費(fèi)用最??？,生產(chǎn)量：A17噸，A24噸，A39噸 銷售量：B13噸，B26噸，B35噸，B46噸,加工廠,單位運(yùn)價(jià),門市部,B1 B2 B3 B4,A1,A2,A3,3 11 3 10,1 9 2 8,7 4 10 5,單位：元/噸,解：用cij表示從第i個(gè)加工廠到第j個(gè)門市部的單位糖果的運(yùn)價(jià)， 設(shè)xij表示第i個(gè)

2、加工廠到第j個(gè)門市部調(diào)運(yùn)糖果的數(shù)量， （i=1，2，3；j=1，2，3，4） 則總費(fèi)用為：,min z = cijxij,3,4,i=1,j=1,x11+x12+x13+x14=7,x11+x21+x31=3,xij0,(i=1,2, 3；j=1,2,3,4),產(chǎn)量限制,銷量限制,x21+x22+x23+x24=4,x31+x32+x33+x34=9,x12+x22+x32=6,x13+x23+x33=5,x14+x24+x34=6,s.t.,1、運(yùn)輸問(wèn)題,產(chǎn)地 提供物資的地點(diǎn) 用A1,A2,Am表示，或用i=1，2，,m 表示； 銷地 需要物資的地點(diǎn) 用B1,B2,Bn表示，或用j=1,2,

3、n 表示； 產(chǎn)量 每個(gè)產(chǎn)地提供物資的數(shù)量，用a1, a2, , am 表示； 銷量 每個(gè)銷地需要物資的數(shù)量，用b1, b2, , bn 表示； 單位物資運(yùn)價(jià) 從產(chǎn)地i到銷地j單位物資的運(yùn)價(jià)為cij,一般滿足產(chǎn)銷平衡：,與物資調(diào)運(yùn)有關(guān)的問(wèn)題。,2、已知條件,已知條件的表格形式,產(chǎn)銷平衡表 單位運(yùn)價(jià)表,本例中：,對(duì)于m產(chǎn)n銷運(yùn)輸問(wèn)題，設(shè)xij表示產(chǎn)地 i 運(yùn)往銷地 j 的物資數(shù)量，則其數(shù)學(xué)模型如下：,3、運(yùn)輸問(wèn)題的數(shù)學(xué)模型,注：運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題。,4、模型的特點(diǎn),已知運(yùn)輸問(wèn)題有m個(gè)產(chǎn)地、n個(gè)銷地， （1）決策變量的個(gè)數(shù)：mn （2）約束方程的個(gè)數(shù)：m+n 其中線性獨(dú)立方程的個(gè)數(shù)：m+n

4、-1 基變量的個(gè)數(shù)：m+n-1 非基變量的個(gè)數(shù)：mn-(m+n-1),5、運(yùn)輸問(wèn)題解的情況,3.2 表上作業(yè)法,初始調(diào)運(yùn)方案 的確定,結(jié)束,Y,調(diào)整方案 使目標(biāo)函數(shù)值更小,N,基本原理：,2-1 初始方案的確定,1、 最小元素法,例 用最小元素法確定初始方案。,就近供應(yīng)“找便宜”,有多少 要多少 運(yùn)多少,得到初始調(diào)運(yùn)方案表：,（1） 有數(shù)字格（基格） 填寫了調(diào)運(yùn)量的格子，對(duì)應(yīng)解中的基變量。（用白圈表示）,（2） 空格 未填寫調(diào)運(yùn)量的格子，對(duì)應(yīng)解中的非基變量，其對(duì)應(yīng)變量在該方案中取值為0。（用藍(lán)圈表示）,在調(diào)運(yùn)方案表中，12個(gè)格子分成兩類：,例 用最小元素法確定初始方案。,注意： 在調(diào)運(yùn)方案表中

5、，每次填入一個(gè)數(shù)字，都在滿足供需關(guān)系下劃去相應(yīng)的一列或一行。 若填入的一個(gè)數(shù)字既滿足產(chǎn)量要求又滿足銷量要求，則應(yīng)同時(shí)劃去這一列和這一行，并在劃去的所在列或行的任一個(gè)空格內(nèi)填入一個(gè)0，以保持有數(shù)字格的總數(shù)不變（即基變量的個(gè)數(shù)不變）。,2. 沃格爾法（Vogel）,例,每行兩個(gè)最小元素之差,每列兩個(gè)最小元素之差,“找大差”,注意：由沃格爾法得出的解比最小元素法得出的解更接近最優(yōu)解。,2-2 最優(yōu)性檢驗(yàn)與方案的調(diào)整,1、閉回路的概念,在調(diào)運(yùn)方案表中以一個(gè)空格和若干個(gè)有數(shù)字格作為頂點(diǎn)，以及水平、垂直連線圍成的封閉回路，稱為該空格對(duì)應(yīng)的閉回路。,例如 分別找出下列空格的閉回路。,空格（A1,B1）的閉回

6、路,空格（A2,B2）的閉回路,空格（A1,B2）的閉回路,空格（A2,B4）的閉回路,空格（A3,B1）的閉回路,空格（A3,B3）的閉回路,注意：調(diào)運(yùn)表中每個(gè)空格有且只有一個(gè)閉回路。,2、利用閉回路計(jì)算檢驗(yàn)數(shù),令空格（Ai,Bj）對(duì)應(yīng)的非基變量的值為1，沿著閉回路，相應(yīng)頂點(diǎn)的基變量的值依次-1，+1，-1，+1，得到新可行解。 將新可行解與原可行解相比，得到的運(yùn)費(fèi)變化量稱為該空格處的檢驗(yàn)數(shù)，記做ij。 即,例 求下列調(diào)運(yùn)方案表中各個(gè)空格的檢驗(yàn)數(shù)。,空格（A1,B1）的閉回路,表示新方案的費(fèi)用要增加1元,空格（A2,B2）的閉回路,表示新方案的費(fèi)用要增加1元,空格（A1,B2）的閉回路,表示

7、新方案的費(fèi)用要增加2元,空格（A3,B1）的閉回路,表示新方案的費(fèi)用要增加10元,空格（A3,B3）的閉回路,表示新方案的費(fèi)用要增加12元,空格（A2,B4）的閉回路,表示新方案的費(fèi)用要減少1元,綜上，得到檢驗(yàn)數(shù)表如下：,注意：有數(shù)字格（基變量）的檢驗(yàn)數(shù)為0。,例 已知運(yùn)輸問(wèn)題的調(diào)運(yùn)方案如下，用閉回路法求檢驗(yàn)數(shù)表。,解：檢驗(yàn)數(shù)表為,3、利用檢驗(yàn)數(shù)表判斷最優(yōu)性,（1）若有負(fù)檢驗(yàn)數(shù)，則該方案需要改進(jìn)； （2）若空格的檢驗(yàn)數(shù)全為正數(shù)，則該問(wèn)題有唯一最優(yōu)方案； （3）若檢驗(yàn)數(shù)全非負(fù)，且有空格的檢驗(yàn)數(shù)為0，則該問(wèn)題有無(wú)窮多最優(yōu)解。,在檢驗(yàn)數(shù)表中，確定絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的空格，利用該空格的閉回路在滿

8、足供需關(guān)系下調(diào)整各頂點(diǎn)的運(yùn)量，得到費(fèi)用更小的調(diào)運(yùn)方案。,4、改進(jìn)方案的方法-閉回路法,例,調(diào)整方法：,1,2,1,-1,10,12,（1）找出絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的閉回路,（2）使所對(duì)應(yīng)的空格達(dá)到最大的調(diào)整量1,此時(shí)x23=0，可看成非基變量。,注：格子右上角數(shù)字為單位物資運(yùn)價(jià)，左下角數(shù)字為檢驗(yàn)數(shù)，圓圈內(nèi)數(shù)字為調(diào)運(yùn)物資數(shù)量。,得到新的調(diào)運(yùn)方案：,該方案就是用沃格爾法得到的初始方案。,其檢驗(yàn)數(shù)表為,故該方案為最優(yōu)方案，且有無(wú)窮多最優(yōu)方案，Zmin=85元。,5、用位勢(shì)法求檢驗(yàn)數(shù),（2）計(jì)算行位勢(shì)ui和列位勢(shì)vj 不妨令u1=1，則依cij=ui+vj 計(jì)算各ui和vj,（3）計(jì)算空格處位勢(shì)和

9、ui+vj,（4）計(jì)算空格處檢驗(yàn)數(shù)ij=cij -（ui+vj）,（1）列一張只含有數(shù)字格單位運(yùn)價(jià)cij的表；,注意： 行位勢(shì)、列位勢(shì)可能不唯一，但檢驗(yàn)數(shù)是相同的。,產(chǎn)地,銷地,A1 A2 A3,B1 B1 B3 B4,3 10 1 8 4 5,(3),(9),(7),(-2),(1),(-2),行位勢(shì),列位勢(shì),1,2,-1,-4,2,8,9,銷地,A1 A2 A3,B1 B1 B3 B4,3 11 3 10 1 9 2 8 7 4 10 5,產(chǎn)地,單位運(yùn)價(jià)表,位勢(shì)表,產(chǎn)地,銷地,A1 A2 A3,B1 B1 B3 B4,7 4 9,產(chǎn)量,銷量,3 6 5 6,6,3,5,2,1,3,調(diào)運(yùn)方案

10、表,A1 A2 A3,B1 B1 B3 B4,0,2,2,9,1,12,檢驗(yàn)數(shù)表,ij,檢驗(yàn)數(shù)表：,故該方案為最優(yōu)方案，且該問(wèn)題有無(wú)窮多最優(yōu)方案。 總費(fèi)用Zmin=85元。,2-3 小結(jié),（1）分析問(wèn)題，列出產(chǎn)銷平衡表和單位運(yùn)價(jià)表。 （2）利用最小元素法或沃格爾法求初始調(diào)運(yùn)方案。 注：沃格爾法是近似最優(yōu)解。 （3）用閉回路法或位勢(shì)法求檢驗(yàn)數(shù)表。 注：位勢(shì)法比較簡(jiǎn)單。 （4）判斷最優(yōu)性 若無(wú)負(fù)檢驗(yàn)數(shù)，則該方案為最優(yōu)方案，計(jì)算相應(yīng)的總運(yùn)費(fèi)，結(jié)束； 否則，利用絕對(duì)值最大的負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的閉回路調(diào)整方案，并轉(zhuǎn)入（3）。,1、表上作業(yè)法的前提：產(chǎn)銷平衡,2、表上作業(yè)法的步驟,已知某運(yùn)輸問(wèn)題的資料如下表：,

11、表中的發(fā)量、收量單位為：噸，運(yùn)價(jià)單位為：元/噸， 試求出最優(yōu)運(yùn)輸方案。,練習(xí),解：1、用最小元素法求初始方案,用沃格爾法求初始方案,總費(fèi)用z=107元,總費(fèi)用z=85元,2、用位勢(shì)法求由沃格爾法得到的方案的檢驗(yàn)數(shù),3、結(jié)論： 表中無(wú)負(fù)檢驗(yàn)數(shù)且有非基變量的檢驗(yàn)數(shù)為0，本問(wèn)題有無(wú)窮多最優(yōu)方案。,一個(gè)最優(yōu)調(diào)運(yùn)方案為：,綜上所述， 總費(fèi)用Zmin=85元。,3.3 產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其應(yīng)用,一、原理,注：該銷地的作用相當(dāng)于多余物資就地庫(kù)存。,注：當(dāng)銷地需要?jiǎng)傂晕镔Y時(shí)，相應(yīng)單價(jià)為M； 當(dāng)銷地需要彈性物資時(shí)，相應(yīng)單價(jià)為0。,例 求解下列運(yùn)輸問(wèn)題。,解：產(chǎn)銷 虛設(shè)一個(gè)銷地B5，建立產(chǎn)銷平衡的運(yùn)輸問(wèn)題：,產(chǎn)銷,產(chǎn)=銷,二、應(yīng)用舉例,用表上作業(yè)法求得最優(yōu)方案為：,總運(yùn)價(jià)zmin=35元。,例 有A、B、C三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)、的農(nóng)用化肥，三個(gè)工廠每年各自的產(chǎn)量為A-50萬(wàn)噸，B-60萬(wàn)噸，C-50萬(wàn)噸。四個(gè)地區(qū)的需求量分別是地區(qū)最高50萬(wàn)噸，最低30萬(wàn)噸，地區(qū)為70萬(wàn)噸，地區(qū)為30萬(wàn)噸