產(chǎn)銷不平衡的運(yùn)輸問題及其應(yīng)用

第三章運(yùn)輸問題3.1運(yùn)輸問題及其數(shù)學(xué)模型

3.2表上作業(yè)法3.3產(chǎn)銷不平衡的運(yùn)輸問題及其應(yīng)用表

上

作

業(yè)

法得到最優(yōu)方案算出的總運(yùn)價分析實(shí)際問題列出產(chǎn)銷平衡表及單位運(yùn)價表求檢驗(yàn)數(shù)（閉回路法或位勢法）

是確定初始調(diào)運(yùn)方案（西北角法、最小元素法或Vogel法）

找出絕對值最大的負(fù)的檢驗(yàn)數(shù)用閉回路調(diào)整，得出新的調(diào)運(yùn)方案否循環(huán)所有檢驗(yàn)數(shù)≥0求

解步驟3.3產(chǎn)銷不平衡運(yùn)輸問題及其應(yīng)用一、產(chǎn)銷不平衡問題1產(chǎn)銷2銷產(chǎn)二、一些變形和推廣三、有轉(zhuǎn)運(yùn)的運(yùn)輸問題在實(shí)際問題中，產(chǎn)大于銷意味著某些產(chǎn)品被積壓在倉庫中。可以這樣設(shè)想，如果把倉庫也看成是一個假想的銷地，并令其銷量剛好等于總產(chǎn)量與總銷量的差；那么，產(chǎn)大于銷的運(yùn)輸問題就轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題

假想一個銷地，相當(dāng)于在原產(chǎn)銷關(guān)系表上增加一列。由于假想的銷地代表的是倉庫，實(shí)際上沒有產(chǎn)生運(yùn)輸，所以假想列所對應(yīng)的運(yùn)價應(yīng)取為“0”。至此，我們又將銷大于產(chǎn)的運(yùn)輸問題轉(zhuǎn)換成了產(chǎn)銷平衡的運(yùn)輸問題。一、產(chǎn)銷不平衡的問題1、產(chǎn)大于銷的運(yùn)輸問題

產(chǎn)地銷地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnBn+1０

０┆０銷量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)maibj相當(dāng)于：增加一個假想銷地產(chǎn)銷問題單位運(yùn)價表產(chǎn)量約束銷量約束m+n+1個約束條件m×(n+1)個決策變量表一甲乙丙丁產(chǎn)量（ai）A3113107B19284C7410512銷量（bj）3656解此運(yùn)輸問題的總產(chǎn)量為23、總銷量為20，所以假設(shè)一個銷地戊并令其銷量剛好等于總產(chǎn)量與總銷量的差“3”。取假想的戊列所對應(yīng)的運(yùn)價都為“0”，可得下表所示的產(chǎn)銷平衡運(yùn)輸問題。例1

將表一所示的產(chǎn)大于銷的運(yùn)輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題甲乙丙丁戊產(chǎn)量（ai）A31131007B192804C74105012銷量（bj）36563B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因?yàn)橛校?/p>

例2

求下列表中極小化運(yùn)輸問題的最優(yōu)解。所以是一個產(chǎn)大于銷的運(yùn)輸問題。表中A2不可達(dá)B1，用一個很大的正數(shù)M表示運(yùn)價C21。虛設(shè)一個銷量為b5=180－160=20的銷地B5，Ci5=0，i=1，2，3，4。表的右邊增添一列這樣可得新的運(yùn)價表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表為計算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運(yùn)出。2.銷大于產(chǎn)的運(yùn)輸問題

可以這樣設(shè)想，假想一個產(chǎn)地，并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差；那么，銷大于產(chǎn)的運(yùn)輸問題同樣可以轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題假想一個產(chǎn)地，相當(dāng)于在原產(chǎn)銷關(guān)系表上增加一行。

由于假想的產(chǎn)地與各銷地之間并不存在實(shí)際的運(yùn)輸，所以假想的產(chǎn)地行所有的運(yùn)價都應(yīng)該是“0”至此，我們又將銷大于產(chǎn)的運(yùn)輸問題轉(zhuǎn)換成了產(chǎn)銷平衡的運(yùn)輸問題。

產(chǎn)地銷地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+10 0 ┈ 0銷量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)mbjai銷產(chǎn)問題單位運(yùn)價表相當(dāng)于：增加一個假想產(chǎn)地產(chǎn)量約束銷量約束m+n+1個約束條件(m+1)×n個決策變量表二甲乙丙丁產(chǎn)量（ai）A3113107B19284C741059銷量（bj）11656解此運(yùn)輸問題的總產(chǎn)量為20、總銷量為28，所以假設(shè)一個產(chǎn)地D并令其產(chǎn)量剛好等于總銷量與總產(chǎn)量的差“8”。令假想的D行所對應(yīng)的運(yùn)價都為“0”，可得下表所示的產(chǎn)銷平衡運(yùn)輸問題。例3

將表二所示的銷大于產(chǎn)的運(yùn)輸問題轉(zhuǎn)換成產(chǎn)銷平衡的運(yùn)輸問題甲乙丙丁產(chǎn)量（ai）A3113107B19284C741059D00008銷量（bj）11656產(chǎn)銷不平衡問題小結(jié)（變成產(chǎn)銷平衡問題）當(dāng)總產(chǎn)量>總銷量時，可增加一個假想銷地Bn+1,銷量＝∑ai－∑bj，Ci,n+1=0，當(dāng)總產(chǎn)量<總銷量時，可增加一個假想產(chǎn)地Am+1,產(chǎn)量＝∑bj

－∑ai

，Cm+1，j=0二、一些變形和推廣銷量不確定（有最高需求和最低需求）設(shè)銷地Bk的最低需求為bk’，最高需求為bk”

，這時可把看作Bk’和Bk”兩個銷地，Bk’需求量bk’

，Bk”的需求量bk”-bk’例2中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～210例4

需求量不確定的運(yùn)輸問題先作如下分析：

（1）總產(chǎn)量為180，B1，…，B4的最低需求量

20+50+35+45=150，這時屬產(chǎn)大于銷；（2）B1，…，B4的最高需求是60+70+35+45=210，這時屬銷大于產(chǎn)（3）虛設(shè)一個產(chǎn)地A5，產(chǎn)量是210－180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。（4）將B1與B2各分成兩部分的需求量是20，的需求量是40，的需求量分別是50與20，因此必須由A1，…，A4供應(yīng)，可由A1、…、A5供應(yīng)。（5）上述A5不能供應(yīng)某需求地的運(yùn)價用大M表示，A5到的運(yùn)價為零。得到下表的產(chǎn)銷平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到這樣的平衡表后，計算得到最優(yōu)方案表2。表2

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

表中：x131=0是基變量,說明這組解是退化基本可行解,空格處的變量是非基變量。B1，B2，B3，B4實(shí)際收到產(chǎn)品數(shù)量分別是50，50，35和45個單位。B1B2B3B4產(chǎn)量A11613221750

A21413191560A3192023M50最低需求3070010最高需求507030不限例5：設(shè)某種材料有A1、A2、A3三個生產(chǎn)廠家，其產(chǎn)品供應(yīng)B1、B2、B3、B4四個城市，假定等量的材料在這些城市的使用效果相同，已知各建材廠的年產(chǎn)量、各城市的年需求量以及各廠到各城市運(yùn)送單位建材的運(yùn)價如表所示，求使運(yùn)費(fèi)最少的調(diào)運(yùn)方案？B1B2B3B4產(chǎn)量A11613221750

A21413191560A3192023M50最低需求3070010最高需求507030不限B1’B1’’B2B3B4’B4’’銷量302070301050A1A2A3A4產(chǎn)量50605050161419M1614190131320M22192301715MM1715M0三、有轉(zhuǎn)運(yùn)的運(yùn)輸問題幾點(diǎn)說明：1.所有的產(chǎn)地、銷地、中間站均視作產(chǎn)地、銷地；2.所有中轉(zhuǎn)站的轉(zhuǎn)運(yùn)量等于總的產(chǎn)量之和；3.不能出現(xiàn)循環(huán)倒運(yùn)現(xiàn)象，允許自身往自身最多調(diào)運(yùn)一次，運(yùn)價為Cij=0；4.實(shí)際產(chǎn)地產(chǎn)量為轉(zhuǎn)運(yùn)量與該產(chǎn)地實(shí)際產(chǎn)量之和，實(shí)際銷地銷量為轉(zhuǎn)運(yùn)量與實(shí)際銷量之和。三、有轉(zhuǎn)運(yùn)的運(yùn)輸問題1、運(yùn)輸表的構(gòu)成1）產(chǎn)地：原產(chǎn)地、中間轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)物資的銷地2）銷地：原銷地、中間轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)物資的產(chǎn)地3）設(shè)各轉(zhuǎn)運(yùn)站轉(zhuǎn)運(yùn)物資的數(shù)量均為∑ai這樣專職轉(zhuǎn)運(yùn)站的產(chǎn)量和銷量均為∑ai而原產(chǎn)地Ai的產(chǎn)量均為（ai+∑ai）原銷地Bj的銷量均為（

bj+∑ai）4)將各條線路實(shí)際的運(yùn)輸單位列成單位運(yùn)價表，其中不可能的運(yùn)輸其單位運(yùn)價用M表示。例6

擴(kuò)大的運(yùn)輸問題例：在前面的糖果例題中，若既可以從Ai運(yùn)到Bj，也可以經(jīng)過中間站T1、T2、T3、T4或者Ai、Bj轉(zhuǎn)運(yùn)，稱擴(kuò)大的運(yùn)輸問題。A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130產(chǎn)銷產(chǎn)量銷量2724292020

20

202020

20

202020

202020

20

2023262526產(chǎn)銷平衡表例7A、B兩個化肥廠每年各生產(chǎn)磷肥900萬噸、600萬噸，這些化肥要通過公路運(yùn)到三個港口，然后再裝船運(yùn)往其他各地，已知三個港口C、D、E每年能承擔(dān)的船運(yùn)量分別為700、400、300萬噸，兩個工廠及三個港口之間均有公路相通，且已知單位運(yùn)價如表所示，為按需要把磷肥運(yùn)到各港口，怎樣安排運(yùn)輸才能使運(yùn)費(fèi)最少？ABCDEA029107B2071010C97034D1010302E710420ABCDEA029107B2071010C97034D1010302E710420P發(fā)量收量240021001500150015001500150022001900180010000000例一：某工廠按合同規(guī)定必須于當(dāng)年的每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需要存儲維護(hù)費(fèi)用0.15萬元。要求在完成合同的情況下，做出使全年生產(chǎn)費(fèi)用最小的決策。季度生產(chǎn)能力(臺)單位成本(萬元/臺)ⅠⅡⅢⅣ2535301010.811.111.011.3運(yùn)輸問題案例1數(shù)學(xué)模型：設(shè)xij第i季度生產(chǎn)，用于第j季度交貨的數(shù)量。目標(biāo)函數(shù)：

minz=cijxiji=1j=1

44x11+x12+x13+x1425

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20xij0,(i=1,····,4;j=1,····,4)供應(yīng)：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：季度生產(chǎn)能力(臺)單位成本(萬元/臺)ⅠⅡⅢⅣ2535301010.811.111.011.3某工廠按合同規(guī)定必須于當(dāng)年的每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。合同要求交貨不得超過生產(chǎn)力產(chǎn)>銷數(shù)學(xué)模型：季度生產(chǎn)能力(臺)單位成本(萬元/臺)ⅠⅡⅢⅣ2535301010.811.111.011.3每臺每積壓一個季度需要存儲維護(hù)費(fèi)用0.15萬元。單位運(yùn)價表：ⅠⅡⅢⅣ銷量ⅠⅡ Ⅲ ⅣD產(chǎn)量10.8 10.95 11.1011.25025

M11.1011.25

11.40035

M

M 11.00

11.15030單位：萬元供應(yīng)需求10 15 25

2030M MM

11.30010當(dāng)i>j時，必須xij=0，令cij=M(很大的正數(shù))，加以懲罰產(chǎn)>銷

例二有A、B、C三個化肥廠供應(yīng)四個地區(qū)Ⅰ、Ⅱ、Ⅲ、Ⅳ的農(nóng)用化肥，三個工廠每年各自的產(chǎn)量為A--50萬噸，B--60萬噸，C--50萬噸。四個地區(qū)的需求量分別是Ⅰ地區(qū)最高50萬噸，最低30萬噸，Ⅱ地區(qū)為70萬噸，Ⅲ地區(qū)為30萬噸以下，Ⅳ地區(qū)不低于10萬噸。問：如何調(diào)運(yùn)，可使總的調(diào)運(yùn)費(fèi)用最??？單位調(diào)運(yùn)費(fèi)用如下表所示。產(chǎn)地銷地A1A2A3B1B2B3B4產(chǎn)量銷量1613221714131915192023―單位運(yùn)價表50605030-50700-3010-單位：萬元/萬噸設(shè)xij--第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量運(yùn)輸問題案例2銷產(chǎn)上限50運(yùn)輸問題案例2ABCDⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ

16 16 13 22 17 17

14 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供應(yīng)需求產(chǎn)量銷量50605050

30

20

70

30

10

50修正運(yùn)價表產(chǎn)地銷地A1A2A3B1B2B3B4產(chǎn)量銷量1613221714131915192023―單位運(yùn)價表50605030-50700-3010-單位：萬元/萬噸設(shè)xij--第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量銷產(chǎn)

某餐館承辦宴會，每晚連續(xù)舉行，共舉行五次。宴會上需用特殊的餐巾，根據(jù)參加的人數(shù)，預(yù)計每晚的需要量為：第一天1000條，第二天700條，第三天800條，第四天1200條，第五天1500條，五天之后，所有的餐巾作廢。宴會中用過的餐巾經(jīng)過洗滌處理后可以重復(fù)使用，這樣可以降低使用成本。已知每條新餐巾需要1元的費(fèi)用，送洗時可選擇兩種方式：快洗僅需要一天時間，每條洗滌費(fèi)用為0.2元，慢洗需要兩天時間，每條洗滌費(fèi)用0.1元。問：如何安排，可使總費(fèi)用最低？運(yùn)輸問題案例3設(shè)xj—第j天使用新毛巾的數(shù)量；yij—第i天送第j天使用快洗餐巾的數(shù)量；zij—第i天送第j天使用慢洗餐巾的數(shù)量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14