典型例題運(yùn)籌學(xué)運(yùn)輸問(wèn)題

1、典型例題運(yùn)籌學(xué)運(yùn)輸問(wèn)題3.1 運(yùn)輸問(wèn)題的典例和數(shù)學(xué)模型一、典例： 某食品公司經(jīng)營(yíng)糖果業(yè)務(wù)，公司下設(shè)三個(gè)工廠A1、A2、A3，四個(gè)銷(xiāo)售門(mén)市部B1、B2、B3、B4。每天各自的生產(chǎn)量、銷(xiāo)售量及調(diào)運(yùn)時(shí)的單位運(yùn)輸費(fèi)用情況。問(wèn)：如何調(diào)運(yùn)可使總費(fèi)用最??？生產(chǎn)量：A17噸， A2 4噸， A3 9噸銷(xiāo)售量：B1 3噸，B2 6噸，B3 5噸，B4 6噸產(chǎn)地單位運(yùn)價(jià)銷(xiāo)地B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 1052021/112調(diào)運(yùn)示意圖A1A2A3B1B2B3B47噸4噸9噸3噸6噸5噸6噸x11x12x13x14x21x22x23x24x31x32x33x34產(chǎn)

2、地銷(xiāo)地2021/113二、建立模型設(shè) xij第i產(chǎn)地到第j銷(xiāo)地之間的調(diào)運(yùn)量，那么有Min z = cij xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,3；j=1,2,4)產(chǎn)量限制銷(xiāo)量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=62021/114一般模型表示： 設(shè)有個(gè)m產(chǎn)地、n個(gè)銷(xiāo)地，其中第i個(gè)產(chǎn)地的產(chǎn)量為ai，第j個(gè)銷(xiāo)地的銷(xiāo)量為bj，且ai=bj。假設(shè)第i個(gè)產(chǎn)地到第j個(gè)銷(xiāo)地每調(diào)運(yùn)單位物資的運(yùn)費(fèi)為cij，那么使總費(fèi)用最少的調(diào)運(yùn)模型為

3、：Min z = cij xijni=1j=1m2021/115三、模型的特點(diǎn)1.變量數(shù)：mn個(gè)2.約束方程數(shù)：m+n個(gè) 最大獨(dú)立方程數(shù)：m+n-13.系數(shù)列向量構(gòu)造：Pij=0110第i個(gè)分量第m+j個(gè)分量2021/116x11 x12 x1n x21 x22 x2n , xm1 xm2 xmn1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1i=1i=2i=mj=1j=2j=n2021/117 3.2 運(yùn)輸問(wèn)題的表上作業(yè)算法和程序求解表上

4、作業(yè)法步驟: 初始方案最優(yōu)性檢驗(yàn)改進(jìn)方案一、初始方案確實(shí)定1.最小元素法2.Vogel法二、最優(yōu)性檢驗(yàn)1.閉回路法2.位勢(shì)法三、方案改進(jìn)方法在閉回路內(nèi)改進(jìn)。2021/118產(chǎn)地銷(xiāo)地A1 A2 A3B1 B2 B3 B4產(chǎn)地銷(xiāo)地A1 A2 A3B1 B2 B3 B4產(chǎn)地銷(xiāo)地A1 A2 A3B1 B2 B3 B4產(chǎn)量銷(xiāo)量3 11 3 10 1 9 2 8 7 4 10 5 6343133 6 5 67 4 93 6 5 67 4 9產(chǎn)量銷(xiāo)量363521(1)(2)(1)(-1)(10)(12)z=c11-c13+c23-c21=1=11z=c12-c14+c24-c22=2=12(0)(2)(2)

5、(9)(1)(12)單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表2021/119產(chǎn)地銷(xiāo)地A1 A2 A3B1 B2 B3 B47 4 9產(chǎn)量銷(xiāo)量3 6 5 6635213產(chǎn)地銷(xiāo)地A1 A2 A3B1 B2 B3 B4行兩最小元素之差列兩最小元素之差3 11 3 10 1 9 2 8 7 4 10 5 0 1 12 5 1 3 0 1 22 - 1 30 1 -2 - 1 27 6 - - 1 2Vogel法:產(chǎn)銷(xiāo)平衡表2021/1110產(chǎn)地銷(xiāo)地A1 A2 A3B1 B1 B3 B4 3 10 1 8 4 5 位勢(shì)法:(3)(9)(7)(-2)(1)(-2)2.計(jì)算行位勢(shì)和列位勢(shì)；令u1=1，那么依cij=ui+vj

6、計(jì)算各ui和vj 3.計(jì)算空格處位勢(shì)；ij=ui+vj行位勢(shì)列位勢(shì) 12-1-42894.計(jì)算空格處檢驗(yàn)數(shù)：ij=cij- ij1.數(shù)字格處上添上對(duì)應(yīng)的運(yùn)價(jià)；銷(xiāo)地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 產(chǎn)地單位運(yùn)價(jià)表位勢(shì)表:2021/1111產(chǎn)地銷(xiāo)地A1 A2 A3B1 B1 B3 B47 4 9產(chǎn)量銷(xiāo)量3 6 5 6635213(0)(2)(2)(9)(1)(12)檢驗(yàn)數(shù)表2021/1112程序求解：(1) 使用LINDO程序求解: 同求解LP模型。(2) 使用EXCEL求解： 2021/11133.3 產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題及其應(yīng)用Min z

7、= cij xijni=1j=1m一、產(chǎn)銷(xiāo)不平衡問(wèn)題1產(chǎn)銷(xiāo)Min z= cijxij+0 xi,n+1ni=1j=1mi=1m2021/1114產(chǎn)地銷(xiāo)地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 產(chǎn)銷(xiāo)問(wèn)題單位運(yùn)價(jià)表銷(xiāo)量產(chǎn)量b1b2bna1 a2 amaibj2021/1115Min z= cij xijni=1j=1m2銷(xiāo)產(chǎn)Min z= cijxij +0 xm+1,jni=1j=1mj=1n2021/1116產(chǎn)地銷(xiāo)地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnAm+1銷(xiāo)產(chǎn)問(wèn)題單位運(yùn)價(jià)表0 0 0銷(xiāo)量

8、產(chǎn)量b1b2bna1 a2 ambjai2021/1117 例一：某工廠按合同規(guī)定必須于當(dāng)年的每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。該廠的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的本錢(qián)如表示。又如果生產(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))單位本錢(qián)(萬(wàn)元/臺(tái))二、應(yīng)用模型2021/1118模型：設(shè) xij第i季度生產(chǎn)，用于第j季度交貨的數(shù)量。obj. min z= cij xiji=1j=1 4 4x11+x12+x13+x1425 x22+x23+x2435 x33+x3430 x

9、4410 x11 =10 x12+x22 =15x13+x23+x33 =25x14+x24+x34+x44=20 xij 0 ,(i=1,4;j=1,4)供給：需求：2021/1119單位費(fèi)用表： M 11.10 11.25 M M 11.00 M MM 單位：萬(wàn)元供給需求2021/1120例二： 某餐館承辦宴會(huì)，每晚連續(xù)舉行，共舉行五次。宴會(huì)上需用特殊的餐巾，根據(jù)參加的人數(shù)，預(yù)計(jì)每晚的需要量為：第一天1000條，第二天700條，第三天800條，第四天1200條，第五天1500條，五天之后，所有的餐巾作廢。宴會(huì)中用過(guò)的餐巾經(jīng)過(guò)洗滌處理后可以重復(fù)使用，這樣可以降低使用本錢(qián)。每條新餐巾需要1元的

10、費(fèi)用，送洗時(shí)可選擇兩種方式：快洗僅需要一天時(shí)間，每條洗滌費(fèi)用為0.2元，慢洗需要兩天時(shí)間，每條洗滌費(fèi)用0.1元。問(wèn)：如何安排，可使總費(fèi)用最低？2021/1121建立模型：設(shè) xj第j天使用新毛巾的數(shù)量；yij第i天送第j天使用快洗 餐巾的數(shù)量；zij第i天送第j天使用慢洗餐巾的數(shù)量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14+z24+y34=1200第五天：x5+z15+z25+z35+y45=1500需求約束供給約束新購(gòu)餐巾： x1+x2+x3+x4+x55200第一天送洗：y12+z13+z14+z151000第二天送洗：y2

11、3+z24+z25700第三天送洗：y34+z35800第四天送洗：y451200 xj0，yij0，zij0，i=1,4；j=1,5Min z=xj+ij+ij2021/1122新 購(gòu) 第一天第二天第三天第四天111110 M0.20.10.10.10MM0.20.10.10MMM0.20.10供給需求產(chǎn)量銷(xiāo) 量5200 1000 700 800 1200MMM0.20.101000700800120015003700產(chǎn)銷(xiāo)平衡表2021/1123例三： 有A、B、C三個(gè)化肥廠供給四個(gè)地區(qū)、的農(nóng)用化肥，三個(gè)工廠每年各自的產(chǎn)量為A-50萬(wàn)噸，B-60萬(wàn)噸，C-50萬(wàn)噸。四個(gè)地區(qū)的需求量分別是地區(qū)

12、最高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)地A1A2A3B1 B2 B3 B4產(chǎn)量銷(xiāo)量16 13 22 17 14 13 19 15 19 20 23 單位運(yùn)價(jià)表50 60 5030-50 70 0-30 10-單位：萬(wàn)元/萬(wàn)噸設(shè) xij-第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量2021/1124A B C D 161613221717 14141319151519192023 M MM0M0M0供給需求產(chǎn)量銷(xiāo) 量50 60 50 50 302070301050產(chǎn)銷(xiāo)平衡表2021/1125三、

13、擴(kuò)大的運(yùn)輸問(wèn)題例：在前面的例題中，假設(shè)既可以從Ai運(yùn)到Bj，也可以經(jīng)過(guò)中間站T1、T2、T3、T4或者Ai、Bj轉(zhuǎn)運(yùn)，稱(chēng)擴(kuò)大的運(yùn)輸問(wèn)題。幾點(diǎn)說(shuō)明：1.所有的產(chǎn)地、銷(xiāo)地、中間站均視作產(chǎn)地、銷(xiāo)地；2.轉(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)量之和。2021/1126A1 A2 A3T1 T2 T3 T4B1 B2 B3 B4A1 A2 A3T1 T2 T3 T4B1 B2 B3 B40 1 3 1 0 - 3 - 02 1 4 3 3 5 - 2 1 - 2 33 11 3 10 1 9 2 8 7 4 10 52 3 1 1 5 - 4 - 2 3 2 33 1 7 11 9 4 3 2 10 10 8