《運(yùn)籌學(xué)》第三章-運(yùn)輸問(wèn)題課件

第3章運(yùn)輸問(wèn)題1精選2021版課件3.1運(yùn)輸問(wèn)題的典例和數(shù)學(xué)模型

3.2運(yùn)輸問(wèn)題的求解方法：表上作業(yè)法3.3幾類(lèi)特殊的運(yùn)輸問(wèn)題3.4運(yùn)輸問(wèn)題的應(yīng)用2精選2021版課件

運(yùn)輸問(wèn)題：根據(jù)已有的交通網(wǎng)，如何制定運(yùn)輸方案，使得這些物資被運(yùn)送到各個(gè)銷(xiāo)售地，并保證某個(gè)指標(biāo)最優(yōu)(例如總運(yùn)費(fèi)最小)。3精選2021版課件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)量：A1——7噸，A2——4噸，A3——9噸銷(xiāo)售量：B1——3噸，B2——6噸，B3——5噸，B4——6噸產(chǎn)地單位運(yùn)價(jià)銷(xiāo)地B1B2B3B4A1A2A3

311 3 10

1 9 2 8

7 4 10 54精選2021版課件調(diào)運(yùn)示意圖A1A2A3B1B2B3B47噸4噸9噸3噸6噸5噸6噸x11x12x13x14x21x22x23x24x31x32x33x34產(chǎn)地銷(xiāo)地5精選2021版課件二、建立模型設(shè)xij——第i產(chǎn)地到第j銷(xiāo)地之間的調(diào)運(yùn)量，則有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij

0,(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=66精選2021版課件單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表7精選2021版課件一般模型表示

(ai=bj)8精選2021版課件三、模型的特點(diǎn)1.變量數(shù)：m

n個(gè)2.約束方程數(shù)：m+n個(gè)最大獨(dú)立方程數(shù)：m+n-13.系數(shù)列向量結(jié)構(gòu)：Pij=——第i個(gè)分量——第m+j個(gè)分量0110………9精選2021版課件x11x12······x1nx21x22······x2n,············,xm1xm2······xmn11······100······0············00······000······011······1············00······000······000······0············11······110······010······0············10······001······001······0············01······000······100······1············00······1i=1i=2i=mj=1j=2j=n···························································································································································································10精選2021版課件關(guān)于運(yùn)輸模型的幾個(gè)結(jié)論：(1)設(shè)有m個(gè)產(chǎn)地，n個(gè)銷(xiāo)地且產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，則基變量數(shù)是m+n-1；(2)若變量組B包含有閉回路，則B中變量對(duì)應(yīng)的列向量線性相關(guān)；(3)m+n-1個(gè)變量組構(gòu)成基變量的充要條件是它不包含任何閉回路。11精選2021版課件初始基可行解新的基可行解最優(yōu)否？STOPYN

3.2運(yùn)輸問(wèn)題的求解方法：表上作業(yè)法單純形法求解思路12精選2021版課件表上作業(yè)法步驟:

初始運(yùn)輸方案

最優(yōu)性檢驗(yàn)

改進(jìn)運(yùn)輸方案一、初始方案的確定1.最小元素法2.Vogel法二、最優(yōu)性檢驗(yàn)1.閉回路法2.位勢(shì)法三、方案改進(jìn)方法在閉回路內(nèi)改進(jìn)。13精選2021版課件3產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量311310192874105634133656749單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表最小元素法14精選2021版課件例產(chǎn)地銷(xiāo)地A1A2B1B215151020產(chǎn)量銷(xiāo)量2851最小元素法：z=8×10+2×5+1×15=105Vogel法：z=10×5+15×2+5×1=85Vogel法15精選2021版課件產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4749產(chǎn)量銷(xiāo)量3656635213產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4行兩最小元素之差列兩最小元素之差31131019287410501125130122-1301-2-1276---12Vogel法產(chǎn)銷(xiāo)平衡表16精選2021版課件針對(duì)最小元素法和vogel法，需要說(shuō)明的幾點(diǎn)：(1)任何運(yùn)輸問(wèn)題都有基可行解，且有最優(yōu)解；(2)如果供應(yīng)量和需求量都是整數(shù)，那么一定可以得到整數(shù)形式的最優(yōu)解;(4)

若在中途同時(shí)有行列要求得到滿足，將同時(shí)劃掉一行一列，最后數(shù)字格個(gè)數(shù)將少于m+n-1個(gè)。為使數(shù)字格的個(gè)數(shù)恰好等于m+n-1，在同時(shí)劃去的行列中，任選（或選其價(jià)格系數(shù)最小元素對(duì)應(yīng)的）空格，填上數(shù)字0作為特殊的數(shù)字格（即基變量）。(3)用最小元素法和vogel法得到的是運(yùn)輸問(wèn)題的一個(gè)基可行解，數(shù)字格對(duì)應(yīng)基變量；17精選2021版課件例產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量273118469431052030251015201050單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表10251510018精選2021版課件產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量31131019287410563431336567493656749產(chǎn)量銷(xiāo)量363521(1)(2)(1)(-1)(10)(12)△z=c11-c13+c23-c21=1=11△z=c12-c14+c34-c32=2=12(0)(2)(2)(9)(1)(12)單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表閉回路法19精選2021版課件注:只要求的基變量是正確的，并且數(shù)目為m+n-1個(gè)，那么每個(gè)非基變量的閉回路存在且唯一，因此，檢驗(yàn)數(shù)唯一。20精選2021版課件產(chǎn)地銷(xiāo)地A1A2A3B1B1B3B4位勢(shì)法4132.計(jì)算行位勢(shì)和列位勢(shì)；令v1=1，則依cij=ui+vj計(jì)算各ui和vj3.計(jì)算空格處位勢(shì)；

ij=ui+vj行位勢(shì)ui列位勢(shì)vj

110-42894.計(jì)算空格處檢驗(yàn)數(shù)：

ij=cij-

ij1.數(shù)字格處上添上對(duì)應(yīng)的運(yùn)價(jià)；銷(xiāo)地A1A2A3B1B1B3B4311310192874105產(chǎn)地單位運(yùn)價(jià)表位勢(shì)表:2105(2)(9)(8)(9)(-3)(-2)21精選2021版課件產(chǎn)地銷(xiāo)地A1A2A3B1B1B3B4749產(chǎn)量銷(xiāo)量36566343(-1)3(1)(2)(1)(10)1(12)檢驗(yàn)數(shù)表注：位勢(shì)法求檢驗(yàn)數(shù)的依據(jù)是對(duì)偶理論。22精選2021版課件注:對(duì)于同一組基變量，所求的檢驗(yàn)數(shù)是唯一的；(2)在最優(yōu)解表中，有非基變量（即空格)的檢驗(yàn)數(shù)為0，根據(jù)線性規(guī)劃單純形法原理知，應(yīng)有無(wú)窮多最優(yōu)解，即有多解。運(yùn)輸問(wèn)題表上作業(yè)法求多解的方法：任選一檢驗(yàn)系數(shù)為0的空格入基，進(jìn)行方案改進(jìn)，可得新的最優(yōu)解；(3)在進(jìn)行調(diào)運(yùn)方案改進(jìn)時(shí)，若沿閉合回路出現(xiàn)多個(gè)可作為調(diào)出變量的數(shù)字格（即閉回路上的數(shù)字格最小值有多個(gè)），此時(shí)，任選一個(gè)為調(diào)出變量，其余的填0，保證調(diào)整后的調(diào)運(yùn)方案中仍有m+n-1個(gè)數(shù)字格。23精選2021版課件5例：產(chǎn)地銷(xiāo)地A1A2A3B1B1B3B4749產(chǎn)量銷(xiāo)量3656635213(0)(2)(2)(9)(1)(12)產(chǎn)地銷(xiāo)地A1A2A3B1B1B3B4749產(chǎn)量銷(xiāo)量36566331224精選2021版課件4(1)產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量632233665659(2)(1)(-1)(10)(12)例：6產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量63033665659

225精選2021版課件練習(xí)產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量10120111279202141618515151015255單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表26精選2021版課件最小元素法產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量10120111279202141618515151015255單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡選2021版課件Vogel法產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)地銷(xiāo)地A1A2A3B1B2B3B4產(chǎn)量銷(xiāo)量10120111279202141618515151015255單位運(yùn)價(jià)表產(chǎn)銷(xiāo)平衡表867792125-6119102-15-6-91013-10510028精選2021版課件注:表上作業(yè)法適用于下列情形：cij≥0；minz；產(chǎn)銷(xiāo)平衡。表上作業(yè)法步驟29精選2021版課件3.3幾類(lèi)特殊的運(yùn)輸問(wèn)題一、產(chǎn)銷(xiāo)不平衡問(wèn)題1

產(chǎn)

銷(xiāo)2

銷(xiāo)

產(chǎn)二、需求量不確定三、中轉(zhuǎn)問(wèn)題30精選2021版課件Minz=cij·xijni=1j=1m一、產(chǎn)銷(xiāo)不平衡問(wèn)題1

產(chǎn)

銷(xiāo)(

ai>bj)Minz=cij·xij+

0xi,n+1ni=1j=1mi=1m31精選2021版課件產(chǎn)地銷(xiāo)地A1A2┊AmB1 B2 ┈

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

０┆０產(chǎn)＞銷(xiāo)問(wèn)題單位運(yùn)價(jià)表銷(xiāo)量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)m

aibj32精選2021版課件Minz=cij·xijni=1j=1m2

銷(xiāo)

產(chǎn)(

bj>ai)Minz=cij·xij+

0xm+1,jni=1j=1mj=1n33精選2021版課件產(chǎn)地銷(xiāo)地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+1銷(xiāo)＞產(chǎn)問(wèn)題單位運(yùn)價(jià)表0 0 ┈ 0銷(xiāo)量產(chǎn)量b1 b2 ┈

bna1a2┊a(chǎn)m

bj

ai34精選2021版課件例：有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)地AⅠ

Ⅱ

Ⅲ

Ⅳ產(chǎn)量最低需求1613221714131915192023―單位運(yùn)價(jià)表5060503070010單位：萬(wàn)元/萬(wàn)噸設(shè)xij--第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量二、需求量不確定BC最高需求507030不限35精選2021版課件ABCⅠ

Ⅰ

Ⅱ Ⅲ Ⅳ

Ⅳ

16 16 13 22 17 1714 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供應(yīng)需求產(chǎn)量銷(xiāo)量50605030 20 70 30 10 50產(chǎn)銷(xiāo)平衡表D50注：M表示無(wú)窮大正數(shù)，最低需求不能由D生產(chǎn)地提供。36精選2021版課件最優(yōu)方案：需求產(chǎn)地Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’產(chǎn)量A5050B20103060C3020050D302050銷(xiāo)量30207030105037精選2021版課件練習(xí)產(chǎn)地銷(xiāo)地AⅠ

Ⅱ

Ⅲ最高發(fā)量467-78單位運(yùn)價(jià)表6040400BC銷(xiāo)量708050D最低發(fā)量8040不限5054645-38精選2021版課件三、中轉(zhuǎn)問(wèn)題在前面的例題中，若既可以從Ai運(yùn)到Bj，也可以經(jīng)過(guò)中間站T1、T2、T3、T4或者Ai、Bj轉(zhuǎn)運(yùn)，稱為擴(kuò)大的運(yùn)輸問(wèn)題。幾點(diǎn)說(shuō)明：1.所有的產(chǎn)地、銷(xiāo)地、中間站均視作產(chǎn)地、銷(xiāo)地；2.不能出現(xiàn)循環(huán)倒運(yùn)現(xiàn)象，允許自身往自身最多調(diào)運(yùn)一次，運(yùn)價(jià)為cii=0；3.轉(zhuǎn)運(yùn)量可定位總的產(chǎn)量之和；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)量之和。39精選2021版課件A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130產(chǎn)銷(xiāo)產(chǎn)量銷(xiāo)量27242920202020202020202020202020202023262526產(chǎn)銷(xiāo)平衡表40精選2021版課件3.4運(yùn)輸問(wèn)題的應(yīng)用41精選2021版課件

例：某工廠按合同規(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.342精選2021版課件模型：設(shè)xij

第i季度生產(chǎn)，用于第j季度交貨的數(shù)量。obj.minz=

cijxiji=1j=1

44x11+x12+x13+x14

25

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20xij

0,(i=1,····,4;j=1,····,4)供應(yīng)：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：43精選2021版課件單位費(fèi)用表：ⅠⅡⅢⅣⅠ Ⅱ Ⅲ Ⅳ10.8 10.95 11.10 11.25

M

11.1011.25

11.40

M

M 11.00

11.15

M M M

11.30單位：萬(wàn)元供應(yīng)需求44精選2021版課件例:某餐館承辦宴會(huì)，每晚連續(xù)舉行，共舉行五次。宴會(huì)上需用特殊的餐巾，根據(jù)參加的人數(shù)，預(yù)計(jì)每晚的需要量為：第一天1000條，第二天700條，第三天800條，第四天1200條，第五天1500條，五天之后，所有的餐巾作廢。宴會(huì)中用過(guò)的餐巾經(jīng)