3.1-運(yùn)輸問題的模型解析

第3章

運(yùn)輸問題（TP）學(xué)習(xí)目標(biāo)了解運(yùn)輸問題數(shù)學(xué)模型及其特點(diǎn)。

掌握產(chǎn)銷平衡運(yùn)輸問題的表上作業(yè)法。

學(xué)會(huì)產(chǎn)銷不平衡運(yùn)輸問題的轉(zhuǎn)化。

學(xué)習(xí)表上作業(yè)法在物流管理中的典型應(yīng)用。23運(yùn)輸問題（TP）運(yùn)輸問題的模型3.1運(yùn)輸問題的表上作業(yè)法3.2產(chǎn)銷不平衡的運(yùn)輸問題3.3運(yùn)輸問題的應(yīng)用案例3.4運(yùn)輸問題的Excel處理3.53運(yùn)輸問題（TP）3有時(shí)候?yàn)榱藭鴮懞?jiǎn)便，運(yùn)輸問題也被寫做TP（TransportationProblem）。例：對(duì)某種物資，設(shè)有m個(gè)產(chǎn)地A1,A2,…,Am，稱它們?yōu)榘l(fā)點(diǎn)，其對(duì)應(yīng)產(chǎn)量為a1,a2,…,am，稱它們?yōu)楫a(chǎn)量；另有n個(gè)銷地B1,B2,…,Bn，稱它們?yōu)槭拯c(diǎn)，其對(duì)應(yīng)銷量為b1,b2,…,bn，稱它們?yōu)殇N量。

又知，從產(chǎn)地（發(fā)點(diǎn)）Ai運(yùn)至銷地（收點(diǎn)）Bj，該種物資每單位的運(yùn)價(jià)為cij（cij≥0）。

試問：應(yīng)如何安排調(diào)運(yùn)方案，在滿足一定要求的前提下，使總運(yùn)費(fèi)最低？43.1運(yùn)輸問題的模型53.1運(yùn)輸問題的模型根據(jù)上述參量的意義列出產(chǎn)量、銷量和運(yùn)價(jià)，如表3.1所示3.1運(yùn)輸問題的模型表中：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)銷平衡問題總產(chǎn)量≠總銷量即產(chǎn)銷不平衡問題63.1運(yùn)輸問題的模型先討論產(chǎn)銷平衡問題，再討論產(chǎn)銷不平衡問題。令xij表示某物資從發(fā)點(diǎn)Ai到收點(diǎn)Bj的調(diào)撥量（運(yùn)輸量），可以列出產(chǎn)銷平衡表，如表3.2所示。73.1運(yùn)輸問題的模型將表3.1與表3.2合在一起，得到一個(gè)新表，這一新表被稱為運(yùn)輸表（或稱為產(chǎn)銷矩陣表），如表3.383.1運(yùn)輸問題的模型根據(jù)產(chǎn)銷矩陣表，求上述問題的解等于求下面數(shù)學(xué)模型的解。

xij（i

=

1,2,…,m；j

=

1,2,…,n）93.1運(yùn)輸問題的模型從上述這一特殊的線性規(guī)劃（LP）問題，可以得到下列三條結(jié)論。該問題的基變量有m

+

n

?1個(gè)。該問題一定有最優(yōu)解。如果ai和bj全是整數(shù)，則該問題一定有整數(shù)最優(yōu)解。1011A1A2A3B1B2B3B47t4t9t3t6t5t6t

問題：如何安排調(diào)運(yùn)方案，在滿足各銷售地點(diǎn)需要的情況下，使總的運(yùn)費(fèi)最少?？偖a(chǎn)量：7t+4t+9t=20t總銷量：3t+6t+5t+6t=20t總產(chǎn)量=總銷量：產(chǎn)銷平衡問題產(chǎn)地銷地已知：各個(gè)產(chǎn)地到各個(gè)銷地1噸糖果的運(yùn)價(jià)

已知:一家糖果公司有三個(gè)加工廠（A1，A2，A3），公司要把這三個(gè)工廠生產(chǎn)的糖果運(yùn)往四個(gè)銷售地區(qū)（B1，B2，B3，B4）。已知每個(gè)工廠的產(chǎn)量、每個(gè)銷售地點(diǎn)的銷量、各工廠到各銷售地點(diǎn)1噸糖果的運(yùn)價(jià)（單位運(yùn)價(jià)）。3運(yùn)輸問題（TP）單位運(yùn)價(jià)表產(chǎn)銷平衡表單位：百元/t12CijB1B2B3B4A1311310A21928A374105XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656A1A2A3B1B2B3B47t4t9t3t6t5t6t產(chǎn)地銷地x11x12x34第i個(gè)產(chǎn)地第j個(gè)銷地運(yùn)輸量Xij…3運(yùn)輸問題（TP）兩個(gè)重要表格單位運(yùn)價(jià)表單位：百元/tCijB1B2B3B4A1311310A21928A374105運(yùn)輸問題的數(shù)學(xué)模型MinZ=3x11+11x12+3x13+

10x14

+

x21+9x22+2x23+

8x24

+7x31+

4x32+10x33+

5x34總運(yùn)費(fèi)最少M(fèi)inZ=∑cijxij目標(biāo)函數(shù)XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656產(chǎn)量約束產(chǎn)銷平衡表銷量約束XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656產(chǎn)銷平衡表XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656+++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656+++=+++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656+++=+++=+++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656++=++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656++=++=++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷量3656++=++=++=++=Xij≥0Xij≥03運(yùn)輸問題（TP）133.1運(yùn)輸問題的模型有三家工廠，都將產(chǎn)品運(yùn)往三個(gè)不同的商店（見下圖）。每個(gè)工廠以產(chǎn)品件數(shù)表示出每周生產(chǎn)能力見下表1。每家商店平均需求量見下表2。工廠1工廠3工廠2商店1商店3商店2

商店123需求量（件/周）506030工廠123供應(yīng)量（件/周）507020表1表2143.1運(yùn)輸問題的模型但是，由于運(yùn)貨距離不同，各個(gè)工廠運(yùn)往各商店的貨物的運(yùn)輸費(fèi)用是不同的。費(fèi)用如下表，我們的問題是確定由哪家工廠運(yùn)送多少件產(chǎn)品到哪家商店。能否列出線性最優(yōu)化模型？決策存在什么樣的約束條件？模型評(píng)價(jià)涉及什么樣的準(zhǔn)則？有那些決策變量？由工廠每件產(chǎn)品運(yùn)往各商店的費(fèi)用（元）

12313232105831310153.1運(yùn)輸問題的模型1、模型建立決策變量—有待確定的是從每家工廠i（i=1，2，3）運(yùn)輸多少件產(chǎn)品到每家商店j（j=1，2，3）去。因此，方便的辦法是用雙下標(biāo)來表示決策變量即Xij。目標(biāo)函數(shù)—利用運(yùn)輸費(fèi)用表中的數(shù)據(jù)，我們希望其值為最小的是：MinZ=由工廠1運(yùn)出產(chǎn)品的總費(fèi)用(3X11+2X12+3X13)

+由工廠2運(yùn)出產(chǎn)品的總費(fèi)用(10X21+5X22+8X23)

+由工廠3運(yùn)出產(chǎn)品的總費(fèi)用(X31+3X32+10X33)即：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33約束條件—需要把決策變量的約束條件當(dāng)作方案生成源。對(duì)工廠1必須有X11+X12+X13≤50

（對(duì)工廠1的供應(yīng)約束）對(duì)工廠2必須有X21+X22+X23≤70

（對(duì)工廠2的供應(yīng)約束）對(duì)工廠3必須有X31+X32+X33≤20

（對(duì)工廠3的供應(yīng)約束）163.1運(yùn)輸問題的模型對(duì)每家商店來說，也需要一個(gè)邏輯關(guān)系式來說明每個(gè)星期運(yùn)到的產(chǎn)品總數(shù)應(yīng)等于每周的需求量。對(duì)商店1必須有X11+X21+X31=50

對(duì)商店2必須有X12+X22+X32=60

對(duì)商店3必須有X13+X23+X33=30

于是，用于解此問題的線性最優(yōu)化模型是：

Xij≥0且為整數(shù)i=1，2，3;j=1，2，3173.1運(yùn)輸問題的模型運(yùn)輸問題模型分析一般形式：某種物資有m個(gè)產(chǎn)地Ai，產(chǎn)量（供應(yīng)量）是ai（i=1，2，…，m），有n個(gè)銷地Bj，銷量（需求量）是bj（j=1，2，…，n）。從運(yùn)到到的單位運(yùn)價(jià)為cij（i=1，2，…，m；j=1，2，…，n），如何安排運(yùn)輸可使總運(yùn)費(fèi)最小？產(chǎn)大于銷-

ai

≥bjMinZ=

CijXij

xij≤ai

（i=1，2，…，m）

xij=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；

j=1，2，…，n）銷大于產(chǎn)-

ai

≤bjMinZ=

CijXij

xij=ai

（i=1，2，…，m）

xij≤bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；

j=1，2，…，n）183.1運(yùn)輸問題的模型產(chǎn)銷平衡-

ai=bj注意！這種模型具有特殊的形式：所有決策變量的約束條件，其系數(shù)均等于1；而且，每個(gè)決策變量?jī)H出現(xiàn)于兩個(gè)約束條件之中。這些特性表明，解這類線性最優(yōu)化模型的單純形法中有一種特殊的方法可用來解這個(gè)問題——這是解這類模型的特別有效的一種方法。而且上述特性還表明，可以給這類線性最優(yōu)化模型以一種象網(wǎng)絡(luò)模型式的形象化的說明。MinZ=

CijXij

xij=ai

（i=1，2，…，m）

xij=bj

（j=1，2，…，n）

xij≥0（i=1，2，…，m；j=1，2，…，n）jjii193.1運(yùn)輸問題的模型（2）產(chǎn)銷不平衡問題——總產(chǎn)量小于總銷量的運(yùn)輸問題例2—有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。等量化肥在這些地區(qū)使用效果相同。相關(guān)數(shù)據(jù)如下表，試分析總運(yùn)費(fèi)最節(jié)省的化肥調(diào)運(yùn)方案。A1A2A3最低需求（萬噸）最高需求（萬噸）

B1B2B3B4