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

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

2、加工廠到第j個門市部調(diào)運糖果的數(shù)量， （i=1，2，3；j=1，2，3，4） 則總費用為：,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、運輸問題,產(chǎn)地 提供物資的地點 用A1,A2,Am表示，或用i=1，2，,m 表示； 銷地 需要物資的地點 用B1,B2,Bn表示，或用j=1,2,

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

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

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

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

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

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

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

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

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