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

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

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

上

作

業(yè)

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

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

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

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

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

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

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

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

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

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

例2

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

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

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

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

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

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

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

－∑ai

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

，這時(shí)可把看作Bk’和Bk”兩個(gè)銷(xiāo)地，Bk’需求量bk’

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

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

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

20+50+35+45=150，這時(shí)屬產(chǎn)大于銷(xiāo)；（2）B1，…，B4的最高需求是60+70+35+45=210，這時(shí)屬銷(xiāo)大于產(chǎn)（3）虛設(shè)一個(gè)產(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)價(jià)用大M表示，A5到的運(yùn)價(jià)為零。得到下表的產(chǎn)銷(xiāo)平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到這樣的平衡表后，計(jì)算得到最優(yōu)方案表2。表2

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

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

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

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

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

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

20

202020

20

202020

202020

20

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

M11.1011.25

11.40035

M

M 11.00

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

2030M MM

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

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

30

20

70

30

10

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

某餐館承辦宴會(huì)，每晚連續(xù)舉行，共舉行五次。宴會(huì)上需用特殊的餐巾，根據(jù)參加的人數(shù)，預(yù)計(jì)每晚的需要量為：第一天1000條，第二天700條，第三天800條，第四天1200條，第五天1500條，五天之后，所有的餐巾作廢。宴會(huì)中用過(guò)的餐巾經(jīng)過(guò)洗滌處理后可以重復(fù)使用，這樣可以降低使用成本。已知每條新餐巾需要1元的費(fèi)用，送洗時(shí)可選擇兩種方式：快洗僅需要一天時(shí)間，每條洗滌費(fèi)用為0.2元，慢洗需要兩天時(shí)間，每條洗滌費(fèi)用0.1元。問(wèn)：如何安排，可使總費(fèi)用最低？運(yùn)輸問(wè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