產銷不平衡的運輸問題及其應用

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

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

上

作

業(yè)

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

是確定初始調運方案（西北角法、最小元素法或Vogel法）

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

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

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

產地銷地A1A2┊AmB1 B2 ┈

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

０┆０銷量產量b1 b2 ┈

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

將表一所示的產大于銷的運輸問題轉換成產銷平衡的運輸問題甲乙丙丁戊產量（ai）A31131007B192804C74105012銷量（bj）36563B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：

例2

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

可以這樣設想，假想一個產地，并令其產量剛好等于總銷量與總產量的差；那么，銷大于產的運輸問題同樣可以轉換成產銷平衡的運輸問題假想一個產地，相當于在原產銷關系表上增加一行。

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

產地銷地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+10 0 ┈ 0銷量產量b1 b2 ┈

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

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

－∑ai

，Cm+1，j=0二、一些變形和推廣銷量不確定（有最高需求和最低需求）設銷地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

需求量不確定的運輸問題先作如下分析：

（1）總產量為180，B1，…，B4的最低需求量

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

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

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

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

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

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

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

20

202020

20

202020

202020

20

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

M11.1011.25

11.40035

M

M 11.00

11.15030單位：萬元供應需求10 15 25

2030M MM

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

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

16 16 13 22 17 17

14 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供應需求產量銷量50605050

30

20

70

30

10

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

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