24320-電子教案-第3章運(yùn)輸問題(TP).ppt

1、第3章 運(yùn)輸問題（TP）,學(xué)習(xí)目標(biāo), 了解運(yùn)輸問題模型的特點(diǎn)。 掌握產(chǎn)銷平衡運(yùn)輸問題的表上作業(yè)法。 學(xué)會(huì)產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化。 學(xué)習(xí)表上作業(yè)法在物流管理中的典型應(yīng)用。,3.1 運(yùn)輸問題的模型, 有時(shí)候?yàn)榱藭鴮懞啽悖\(yùn)輸問題也被寫做TP（Transportation Problem）。, 對某種物資，設(shè)有m個(gè)產(chǎn)地A1, A2, Am，稱它們?yōu)榘l(fā)點(diǎn)，其對應(yīng)產(chǎn)量為a1, a2, am，稱它們?yōu)楫a(chǎn)量；另有n個(gè)銷地B1, B2, Bn，稱它們?yōu)槭拯c(diǎn)，其對應(yīng)銷量為b1, b2, bn，稱它們?yōu)殇N量。 又知，從產(chǎn)地（發(fā)點(diǎn)）Ai運(yùn)至銷地（收點(diǎn)）Bj，該種物資每單位的運(yùn)價(jià)為ci j（ci j0）。, 試問：

2、應(yīng)如何安排調(diào)運(yùn)方案，在滿足一定要求的前提下，使總運(yùn)費(fèi)最低？ 根據(jù)上述參量的意義列出產(chǎn)量、銷量和運(yùn)價(jià)，如表3.1所示。, 表中：ai的單位為噸、千克、件等；bj的單位為噸、千克、件等；cij的單位為元/噸、元/千克、元/件等；即ai, bj, cij的單位類別應(yīng)該一致（i=1, 2, m；j=1, 2, n）。, 表的右下角 表示各產(chǎn)地產(chǎn)量的總和，即總產(chǎn)量或總發(fā)量； 表示各銷地銷量的總和，即總銷量或總收量。, 這時(shí)有兩種可能：, 下面先討論產(chǎn)銷平衡問題，再討論產(chǎn)銷不平衡問題。 令xij表示某物資從發(fā)點(diǎn)Ai到收點(diǎn)Bj的調(diào)撥量（運(yùn)輸量），可以列出產(chǎn)銷平衡表，如表3.2所示。, 將表3.1與表3.2合

3、在一起，得到一個(gè)新表，這一新表被稱為運(yùn)輸表（或稱為產(chǎn)銷矩陣表），如表3.3所示。, 根據(jù)產(chǎn)銷矩陣表，求上述問題的解等于求下面數(shù)學(xué)模型的解。 xij（i=1, 2, , m；j=1, 2, , n）,從上述這一特殊的線性規(guī)劃（LP）問題，可以得到下列三條結(jié)論。 （1）該問題的基變量有m+n1個(gè)。 （2）該問題一定有最優(yōu)解。 （3）如果ai和bj全是整數(shù)，則該問題一定有整數(shù)最優(yōu)解。,3.2 運(yùn)輸問題的表上作業(yè)法,3.2.1 產(chǎn)銷平衡運(yùn)輸問題的表上作業(yè)法 利用表上作業(yè)法求解運(yùn)輸問題時(shí)，與單純形法類似，首先要求出一個(gè)初始方案（即線性規(guī)劃問題的初始基本可行解）。, 一般來講這個(gè)方案不一定是最優(yōu)的，因此需

4、要給出一個(gè)判別準(zhǔn)則，并對初始方案進(jìn)行調(diào)整、改進(jìn)。, 每進(jìn)行一次調(diào)整，我們就得到一個(gè)新的方案（基本可行解），而這個(gè)新方案一般比前一個(gè)方案要合理些，也就是對應(yīng)的目標(biāo)函數(shù)z值比前一個(gè)方案要小些。 經(jīng)過若干次調(diào)整，我們就得到一個(gè)使目標(biāo)函數(shù)達(dá)到最小值的方案最優(yōu)方案（最優(yōu)解），而這些過程都可在產(chǎn)銷矩陣表（運(yùn)輸表）上進(jìn)行，故稱為表上作業(yè)法。, 例3.1 設(shè)有3個(gè)產(chǎn)煤基地A1、A2、A3，4個(gè)銷煤基地B1、B2、B3、B4，產(chǎn)地的產(chǎn)量、銷地的銷量以及從各產(chǎn)地至各銷地煤炭的單位運(yùn)價(jià)列于表3.4中，試求出使總運(yùn)費(fèi)最低的煤炭調(diào)撥方案。,（1）列出運(yùn)輸問題的產(chǎn)銷矩陣表。, 其中：xij為產(chǎn)地Ai到銷地Bj的運(yùn)量（i=

5、1, 2, 3；j1, 2, 3, 4），而將Ai到Bj的單位運(yùn)價(jià)cij用小型字寫在每格的右上角，以便直觀地制定和修改調(diào)運(yùn)方案。 從表3.5的數(shù)據(jù)可知，例3.1是個(gè)滿足產(chǎn)銷平衡條件的產(chǎn)銷平衡問題。,（2）初始方案確定的方法最小元素法。, 這樣，我們便得到這樣問題的一個(gè)初始基本可行解，即 x11=0 x12=0 x13=4 x14=3 x21=3 x22=0 x23=1 x24=0 x31=0 x32=6 x33=0 x34=3, 它所對應(yīng)的目標(biāo)函數(shù)z值為 z=30+110+34+103+13+90+21+ 80+70+46+100+53=86（萬元）, 因此，在應(yīng)用最小元素法確定初始方案時(shí)，必

6、須注意以下兩點(diǎn)。, 當(dāng)選定最小元素（不妨假定為cst）后，如果發(fā)現(xiàn)該元素所在行的產(chǎn)地的產(chǎn)量as恰好等于它所在列的銷地的銷量bt（即as=bt），這時(shí)，可在產(chǎn)銷矩陣表上xst處填上一個(gè)數(shù)as，并畫上圈。, 為了保證調(diào)運(yùn)方案中畫圈的數(shù)字為m+n1個(gè)，只能在s行的其他格子里都打上“”（或在t列的其他格子里都打上“”），不可以同時(shí)把s行和t列的其他格子里都打上“”。, 當(dāng)最后只剩下一行（或一列）還存在沒有填數(shù)和打“”的格子時(shí)，規(guī)定只允許填數(shù)，不允許打“”，其目的也是為了保證畫圈數(shù)字的個(gè)數(shù)恰為m+n1個(gè)。, 在特殊情況下可填“0”并畫上圈，這個(gè)“0”應(yīng)與其他畫圈的數(shù)字同樣看待。 （不限于最后一行或最后一

7、列）。, 例如，在表3.7中，第一步的最小元素為c31=1，在x31處填上數(shù)字min(13, 19)=13，并在x11、x21處打上“”。, 第二步的最小元素為c32=2，可在x32處填上數(shù)字min(6, 6)=6，并在x12、x22處打上“”（或在x33、x34處打上“”），由上面的注意（1）可知，不能同時(shí)在x12、x22、x33、x34處都打上“”。, 繼續(xù)運(yùn)用前面所述的方法，再經(jīng)過兩步計(jì)算，可得到表3.8。,（3）調(diào)運(yùn)方案的檢驗(yàn)閉回路法。, 利用閉回路法檢驗(yàn)?zāi)痴{(diào)運(yùn)方案是否最優(yōu)，可按下列步驟進(jìn)行。 求檢驗(yàn)數(shù)。 根據(jù)檢驗(yàn)數(shù)進(jìn)行判別。, 將所有打“”處的檢驗(yàn)數(shù)填入表中，得到檢驗(yàn)數(shù)表，如表3.1

8、2所示。,3.2.2 產(chǎn)銷平衡運(yùn)輸問題的表上作業(yè)法步驟,第一步，求初始調(diào)運(yùn)方案，采用最小元素法，保證有調(diào)運(yùn)量的格子個(gè)數(shù)（基變量個(gè)數(shù)）等于m+n1。 第二步，求檢驗(yàn)數(shù)。 第三步，調(diào)整。, 例3.2 某工地有3個(gè)高地A1、A2、A3和4個(gè)洼地B1、B2、B3、B4，希望用高地的土有計(jì)劃地填平洼地。 設(shè)各個(gè)高地的出土量和各個(gè)洼地的填土量如表3.14所示，各個(gè)高地與各個(gè)洼地之間的距離如表3.15所示，試用表上作業(yè)法制定最合理的調(diào)運(yùn)方案。, 解 （1）將運(yùn)量表與距離表合并為產(chǎn)銷矩陣表，如表3.16所示。（2）用最小元素法求出初始調(diào)運(yùn)方案，如表3.17所示。（3）利用閉回路法求得檢驗(yàn)數(shù)表，如表3.18所示

9、。,（4）在檢驗(yàn)數(shù)表中，較大，所以過調(diào)運(yùn)方案（表3.17）的x21處作出它的閉回路，進(jìn)行調(diào)整得到調(diào)運(yùn)方案，如表3.19所示。,（5）求調(diào)運(yùn)方案的檢驗(yàn)數(shù)表，如表3.20所示。, 因?yàn)檎{(diào)運(yùn)方案檢驗(yàn)數(shù)表中的檢驗(yàn)數(shù)有負(fù)數(shù)，必須進(jìn)行調(diào)整。,（6）因?yàn)?3=50，所以過調(diào)運(yùn)方案（表3.19）的x13處作出它的閉回路，進(jìn)行調(diào)整得到調(diào)運(yùn)方案，如表3.21所示。,（7）再求出方案的檢驗(yàn)數(shù)表，如表3.22所示。, 由于檢驗(yàn)數(shù)全部為正數(shù)，所以調(diào)運(yùn)方案為最優(yōu)方案。,（8）目標(biāo)函數(shù)值為,min z=2010+255+102+153+204+105=520（土方千米）,3.2.3 利用位勢法求檢驗(yàn)數(shù), 當(dāng)一個(gè)運(yùn)輸問題的產(chǎn)

10、地和銷地個(gè)數(shù)很多時(shí)，用這個(gè)方法計(jì)算檢驗(yàn)數(shù)的工作十分繁重。 下面介紹一種簡便的求檢驗(yàn)數(shù)的方法位勢法。, 表3.23（同表3.6）給出了例3.1利用最小元素法確定的初始調(diào)運(yùn)方案。, 第一步是在表3.23中添加新的一列ui列（i的個(gè)數(shù)等于產(chǎn)地的個(gè)數(shù)）和新的一行vj行（j的個(gè)數(shù)等于銷地的個(gè)數(shù)），如表3.24所示。, 表3.24中的ui和vj分別稱為第i行和第j列的位勢（i=1, 2, , m；j=1, 2, , n），并規(guī)定它們與表中畫圈數(shù)字所在的格對應(yīng)的單位運(yùn)價(jià)有如下關(guān)系：, 第二步是確定ui和vj的數(shù)值。 由于ui與vj的數(shù)值相互之間是有關(guān)聯(lián)的，所以只要任意給定其中的一個(gè)，則可根據(jù)關(guān)系式（3-3）

11、很容易地將其他所有位勢的數(shù)值求出。, 例如，在表3.24中，先令v1=1，則有 u2+v1=1u2=0 u2+v3=2v3=2 u1+v3=3u1=1 u1+v4=10v4=9 u3+v4=5u3=4 u3+ v2=4v2=8, 把這些數(shù)分別填入表3.24的ui列和vj行，得到表3.25。, 第三步是求出位勢，可以根據(jù)下面的原理求“”處格子的檢驗(yàn)數(shù)（即非基變量的檢驗(yàn)數(shù)）。, 例3.3 對于表3.19所示的調(diào)運(yùn)方案，利用位勢法求檢驗(yàn)數(shù)。, 解 （1）在表3.19中添加新的ui列和vj行得表3.26。 （2）令u1=5，對于各個(gè)有圈數(shù)字所在格的單位運(yùn)價(jià)，按照關(guān)系式cij=(ui+vj)，依次求出各

12、位勢值填入表3.26。,（3）利用打“”處的單位運(yùn)價(jià)，根據(jù)式（3-4），即可間接求得相應(yīng)的檢驗(yàn)數(shù)表，如表3.27所示。,3.2.4 確定初始方案的其他方法,1西北角法,2沃格爾法,3.3 產(chǎn)銷不平衡的運(yùn)輸問題, 對于產(chǎn)銷不平衡的運(yùn)輸問題，可將其分為總供給量（總產(chǎn)量）大于總需求量（總銷量）（即 ）和總需求量（總銷量）大于總供給量（總產(chǎn)量）（即 ）兩種情形。, 對于這兩種情形，通過按具體情況虛設(shè)收點(diǎn)或虛設(shè)發(fā)點(diǎn)（其收量或發(fā)量是其總量的差數(shù)），并按實(shí)際意義確定各新增格子上的單位運(yùn)價(jià)，均可將它們轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題。, 例3.4 求下面運(yùn)輸問題的最優(yōu)調(diào)撥方案，其產(chǎn)銷運(yùn)價(jià)表如表3.30所示。, 將其轉(zhuǎn)

13、化為了一個(gè)平衡的運(yùn)輸問題，如表3.31所示。, 例3.5 設(shè)有3個(gè)化肥廠A1、A2和A3供應(yīng)4個(gè)地區(qū)B1、B2、B3和B4的化肥，且等量的化肥在這些地區(qū)使用效果相同，各化肥廠年產(chǎn)量、各地年需求量以及化肥的單位運(yùn)價(jià)如表3.32所示，其中（A3，B4）處的M表示運(yùn)價(jià)非常高。 試求使總運(yùn)費(fèi)最低的調(diào)撥方案。, 其余類似處理，可得平衡的產(chǎn)銷矩陣表。,3.4 運(yùn)輸問題的應(yīng)用案例, 例3.6 （最大元素法應(yīng)用案例）某公司進(jìn)口一批商品，共有900萬件。 計(jì)劃在A1港卸貨100萬件，A2港卸貨400萬件，A3港卸貨400萬件，然后再運(yùn)往B1、B2、B3 3個(gè)城市進(jìn)行銷售。, 已知3個(gè)城市的需要量分別為300萬件

14、、200萬件、400萬件，從港口運(yùn)往各城市每萬件的銷售利潤由表3.37給出，問應(yīng)如何因地制宜安排調(diào)運(yùn)計(jì)劃，才使總銷售利潤最多。, 解 該問題是求總銷售利潤最多的解，所以用最大元素法來進(jìn)行研究。 下面利用最大元素法進(jìn)行求解，首先制作一個(gè)產(chǎn)銷矩陣表，如表3.38所示。,3.5 運(yùn)輸問題的Excel處理,3.5.1 運(yùn)輸問題模型的特點(diǎn), 通常，對于運(yùn)輸問題模型可有以下3條結(jié)論： （1）運(yùn)輸問題的基變量有m+n1個(gè)。 （2）運(yùn)輸問題一定有最優(yōu)解。 （3）如果ai和bj全是整數(shù)，則運(yùn)輸問題一定有整數(shù)最優(yōu)解。,3.5.2 運(yùn)輸問題的Excel處理, 首先在工作表的頂端部分輸入運(yùn)輸費(fèi)用、原始供給和目的地需求等相關(guān)數(shù)據(jù)，然后在工作表的底端部分設(shè)計(jì)線性規(guī)劃模型。 所有的線性規(guī)劃問題都含有4種要素：決策變量、目標(biāo)函數(shù)、左側(cè)值約束條件和右側(cè)值約束條件。, 對于運(yùn)輸問題而言，決策變量是從起點(diǎn)運(yùn)到目的地的總數(shù)量；目標(biāo)函數(shù)是所有運(yùn)輸費(fèi)用的總和；左側(cè)值約束條件是從每個(gè)起點(diǎn)運(yùn)輸?shù)漠a(chǎn)品數(shù)