3.1-運輸問題的模型解析

第3章

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

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

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

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

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

試問：應(yīng)如何安排調(diào)運方案，在滿足一定要求的前提下，使總運費最低？43.1運輸問題的模型53.1運輸問題的模型根據(jù)上述參量的意義列出產(chǎn)量、銷量和運價，如表3.1所示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ā)量；

表示各銷地銷量的總和，即總銷量或總收量。這時有兩種可能：

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

xij（i

=

1,2,…,m；j

=

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

+

n

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

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

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

10x14

+

x21+9x22+2x23+

8x24

+7x31+

4x32+10x33+

5x34總運費最少MinZ=∑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運輸問題（TP）133.1運輸問題的模型有三家工廠，都將產(chǎn)品運往三個不同的商店（見下圖）。每個工廠以產(chǎn)品件數(shù)表示出每周生產(chǎn)能力見下表1。每家商店平均需求量見下表2。工廠1工廠3工廠2商店1商店3商店2

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

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

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

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

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

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

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

對商店2必須有X12+X22+X32=60

對商店3必須有X13+X23+X33=30

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

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

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

B1B2B3B4