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

第3章

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

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

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

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

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

試問(wèn)：應(yīng)如何安排調(diào)運(yùn)方案，在滿(mǎn)足一定要求的前提下，使總運(yùn)費(fèi)最低？43.1運(yùn)輸問(wèn)題的模型53.1運(yùn)輸問(wèn)題的模型根據(jù)上述參量的意義列出產(chǎn)量、銷(xiāo)量和運(yùn)價(jià)，如表3.1所示3.1運(yùn)輸問(wèn)題的模型表中：ai、bj、cij的單位為噸、千克、件等，即ai,bj,cij的單位類(lèi)別應(yīng)該一致（i

=

1,2,…,m；j

=

1,2,…,n）。表的右下角

表示各產(chǎn)地產(chǎn)量的總和，即總產(chǎn)量或總發(fā)量；

表示各銷(xiāo)地銷(xiāo)量的總和，即總銷(xiāo)量或總收量。這時(shí)有兩種可能：

總產(chǎn)量=總銷(xiāo)量即產(chǎn)銷(xiāo)平衡問(wèn)題總產(chǎn)量≠總銷(xiāo)量即產(chǎn)銷(xiāo)不平衡問(wèn)題63.1運(yùn)輸問(wèn)題的模型先討論產(chǎn)銷(xiāo)平衡問(wèn)題，再討論產(chǎn)銷(xiāo)不平衡問(wèn)題。令xij表示某物資從發(fā)點(diǎn)Ai到收點(diǎn)Bj的調(diào)撥量（運(yùn)輸量），可以列出產(chǎn)銷(xiāo)平衡表，如表3.2所示。73.1運(yùn)輸問(wèn)題的模型將表3.1與表3.2合在一起，得到一個(gè)新表，這一新表被稱(chēng)為運(yùn)輸表（或稱(chēng)為產(chǎn)銷(xiāo)矩陣表），如表3.383.1運(yùn)輸問(wèn)題的模型根據(jù)產(chǎn)銷(xiāo)矩陣表，求上述問(wèn)題的解等于求下面數(shù)學(xué)模型的解。

xij（i

=

1,2,…,m；j

=

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

+

n

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

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

已知:一家糖果公司有三個(gè)加工廠(chǎng)（A1，A2，A3），公司要把這三個(gè)工廠(chǎng)生產(chǎn)的糖果運(yùn)往四個(gè)銷(xiāo)售地區(qū)（B1，B2，B3，B4）。已知每個(gè)工廠(chǎng)的產(chǎn)量、每個(gè)銷(xiāo)售地點(diǎn)的銷(xiāo)量、各工廠(chǎng)到各銷(xiāo)售地點(diǎn)1噸糖果的運(yùn)價(jià)（單位運(yùn)價(jià)）。3運(yùn)輸問(wèn)題（TP）單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表單位：百元/t12CijB1B2B3B4A1311310A21928A374105XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656A1A2A3B1B2B3B47t4t9t3t6t5t6t產(chǎn)地銷(xiāo)地x11x12x34第i個(gè)產(chǎn)地第j個(gè)銷(xiāo)地運(yùn)輸量Xij…3運(yùn)輸問(wèn)題（TP）兩個(gè)重要表格單位運(yùn)價(jià)表單位：百元/tCijB1B2B3B4A1311310A21928A374105運(yùn)輸問(wè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銷(xiāo)量3656產(chǎn)量約束產(chǎn)銷(xiāo)平衡表銷(xiāo)量約束XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656產(chǎn)銷(xiāo)平衡表XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656+++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656+++=+++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656+++=+++=+++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656++=++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656++=++=++=XijB1B2B3B4產(chǎn)量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349銷(xiāo)量3656++=++=++=++=Xij≥0Xij≥03運(yùn)輸問(wèn)題（TP）133.1運(yùn)輸問(wèn)題的模型有三家工廠(chǎng)，都將產(chǎn)品運(yùn)往三個(gè)不同的商店（見(jiàn)下圖）。每個(gè)工廠(chǎng)以產(chǎn)品件數(shù)表示出每周生產(chǎn)能力見(jiàn)下表1。每家商店平均需求量見(jiàn)下表2。工廠(chǎng)1工廠(chǎng)3工廠(chǎng)2商店1商店3商店2

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

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

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

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

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

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

（對(duì)工廠(chǎng)3的供應(yīng)約束）163.1運(yùn)輸問(wèn)題的模型對(duì)每家商店來(lái)說(shuō)，也需要一個(gè)邏輯關(guān)系式來(lái)說(shuō)明每個(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

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

Xij≥0且為整數(shù)i=1，2，3;j=1，2，3173.1運(yùn)輸問(wèn)題的模型運(yùn)輸問(wèn)題模型分析一般形式：某種物資有m個(gè)產(chǎn)地Ai，產(chǎn)量（供應(yīng)量）是ai（i=1，2，…，m），有n個(gè)銷(xiāo)地Bj，銷(xiāo)量（需求量）是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)大于銷(xiāo)-

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）銷(xiāo)大于產(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)輸問(wèn)題的模型產(chǎn)銷(xiāo)平衡-

ai=bj注意！這種模型具有特殊的形式：所有決策變量的約束條件，其系數(shù)均等于1；而且，每個(gè)決策變量?jī)H出現(xiàn)于兩個(gè)約束條件之中。這些特性表明，解這類(lèi)線(xiàn)性最優(yōu)化模型的單純形法中有一種特殊的方法可用來(lái)解這個(gè)問(wèn)題——這是解這類(lèi)模型的特別有效的一種方法。而且上述特性還表明，可以給這類(lèi)線(xiàn)性最優(yōu)化模型以一種象網(wǎng)絡(luò)模型式的形象化的說(shuō)明。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)輸問(wèn)題的模型（2）產(chǎn)銷(xiāo)不平衡問(wèn)題——總產(chǎn)量小于總銷(xiāo)量的運(yùn)輸問(wèn)題例2—有三個(gè)化肥廠(chǎng)供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。等量化肥在這些地區(qū)使用效果相同。相關(guān)數(shù)據(jù)如下表，試分析總運(yùn)費(fèi)最節(jié)省的化肥調(diào)運(yùn)方案。A1A2A3最低需求（萬(wàn)噸）最高需求（萬(wàn)噸）

B1B2B3B4