清華大學(xué)運(yùn)籌學(xué)3運(yùn)輸問題

第三章

運(yùn)輸問題1/73第一節(jié)

運(yùn)輸問題及其數(shù)學(xué)模型第二節(jié)

表上作業(yè)法第三節(jié)

進(jìn)一步討論第一節(jié)

運(yùn)輸問題及其數(shù)學(xué)模型2/73一、問題的提出欠土B1欠土B2欠土B3欠土B4余方量多土

A13x1111x123x1310x147多土

A21x219x222x238x244多土

A37x314x3210x335x349需量3653/73620

20[例2]平整某場(chǎng)地，有三處高，需削平，有四處低，需填高。已算出高處總余方量恰好滿足低處總需方量。12種運(yùn)價(jià)也已算出，在右上角方格內(nèi)。問：如何調(diào)度，才花費(fèi)最少？4/73Min

z=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5s.t.x11+x12+x13+x14x21+x22+x23+x24=7=4x31+x32+x33+x34

=9x11x12x13+x21+x31=3+x22+x32=6+x23+x33=5x14+x24

+x34=6xij≥0，1≤i≤3,

1≤j≤4，i和j

皆為正整數(shù)。供應(yīng)點(diǎn)m=3個(gè)，用戶有n=4個(gè)。運(yùn)輸問題數(shù)學(xué)模型Min

z=CXs.t.

AX=bX≥0X=(x11,

x12,

x13,x14,

x21,

x22,x23,

x24,

x31,

x32,x34)T

C=(c11,

c12,

c13,

c14,

c21,

c22,

c23,

c24,

c31,c34)b=(s1,

s2,

s3,

d1,

d2,

d3,

d4)Ts1,s2和s3分別是三個(gè)供應(yīng)點(diǎn)供應(yīng)量,d1,d2,d3和別是四個(gè)用戶需求量。當(dāng)s1+s2+s3=d1+d2+d3+d4時(shí)，是供求平衡運(yùn)輸問題，否則，是供求不平衡運(yùn)輸問題。先5/73討論前者。x31

x32

x33

x34x11

x12

x13

x14

x21

x22

x23

x241

1

1

1A

=

11

1

1

111

1

1

111111111

1

1A

是(m+n)×(m×n)矩陣，又可寫成：A

=

(P11,

P12,

P13,

P14,

P21,

P22,

P23,

P24,

P31,

P32,

P33,6/73Pij=

ei

+

em+j7/73ei

和em+j

分別是第i和第m+j個(gè)元素為1的m+n維單位向量。第二節(jié)

表上作業(yè)法8/73一、確定初始可行解最小元素法西北角法（不講）Vogel法（不講）最小元素法舉例說明。9/73欠土B1欠土B2欠土B3欠土B4余方量多土

A13x1111x123x1310x147多土

A2139x222x238x244-3=1多土

A37x314x3210x335x349需量3-3=06510/73620

20從A2運(yùn)往B1的費(fèi)用最低，先將A2的土運(yùn)往B1，B1需求量是3，滿足后，A2還有剩余。B1的需求既然已經(jīng)滿足，以后不再考慮。劃去第一列B1B2B3B4余方量A13x1111x123x1310x147A2139x22218x241-1=0A37x314x3210x335x349需量065-1=411/73620

20剩下的，從A2運(yùn)往B3的費(fèi)用最低，B3需要5，A2只能滿足1。A2以后不再考慮。劃去第二行。B1B2B3B4余方量A13x1111x123410x147-4=3A2139x22218x240A37x314x3210x335x349需量064-4=012/73620

20剩下的，從A1運(yùn)往B3的費(fèi)用最低，將A1的土運(yùn)往

B3，B3需求量是4，從A1運(yùn)來4，就滿足了，以后不再考慮。劃去第三列。B1B2B3B4余方量A13x1111x123410x143A2139x22218x240A37x314610x335x349-6=3需量06-6=0013/73620

20剩下的，從A3運(yùn)往B2的費(fèi)用最低，B2需求量是6，可從A3處滿足，以后不再考慮。劃去第二列。B1B2B3B4余方量A13x1111x123410x143A2139x22218x240A37x314610x33533-3=0需量00014/736-3=320

20剩下的，從A3運(yùn)往B4的費(fèi)用最低，B4需求量是6，可從A3處得到3，以后不再考慮A3

。劃去第三行。15/73B1B2B3B4余方量A13x1111x12341033-3=0A2139x22218x240A37x314610x33530需量0003-3=020

20B4需3，A1剩3，可滿足。劃去第一行和第四列。非負(fù)數(shù)字格叫基格，對(duì)應(yīng)基變量(m+n-1個(gè))。其他格叫非基格，對(duì)應(yīng)非基變量(mn-m-n+1個(gè))，非基變量均取0。16/73z=3x13+10x14+x21+2x23+4x32+5x34=3×4+10×3+3+2×1+4×6+5×3=12+30+3+2+24+15=86初始基可行解是否最優(yōu)，即z是否達(dá)到了最小值？用非基變量檢驗(yàn)數(shù)判斷。檢驗(yàn)數(shù)有幾種算法。1.迴路法計(jì)算檢驗(yàn)數(shù)σij

=cij

-CBB-1Pij，為此，考察非基變量同基變量的關(guān)系。B=

(P13,

P14,

P21,

P23,

P32,

P34,

e7)先看非基變量x11，非基格11與基格13、基格23、基格21構(gòu)成迴路。再看如下關(guān)系：P11

-P13+P23-P21=

e1+e4-e1-e6+e2+e6-e2-e4

=0B1B2B3B4A1x11x1243A23x221x24A3x316x33

17/733因此有，P11

=P13-P23+P21σ11

=c11-CBB-1P11

=c11-CBB-1(P13-P23+P21)

=c11

-CB(e1-e4+e3)=c11-(c13,

c14,

c21,

c23,

c32,

c34,

0)(ee4+e3)=c11-(c13-c23+c21)=3-

(3-2+1)=1B=

(P13,

P14,

P21,

P23,

P32,

P34,

e7)B1B2B3B4A13x11x12343A213x2221x24A3x316x33

18/733同樣，P12

=P14-P34+P32σ12

=c12

-CBB-1P12

=c12

-CBB-1(P14-P34+P32)

=c12

-C(e2-e6+e5)=c12-(c13,

c14,

c21,

c23,

c32,

c34,

0)(ee6+e5)=c12-(c14-c34+c32)=11-

(10-5+4)=

2B=

(P13,

P14,

P21,

P23,

P32,

P34,

e7)B1B2B3B4A1x1111x124103A23x221x24A3x3146x33

19/7353同樣，P22

=P23-P13+P14-P34+P32σ22

=c22

-CBB-1(P23-P13+P14-P34+P32)

=c22

-CB

(e4-e1+e3-e6+e5)=c12-(c13,

c14,

c21,

c23,

c32,

c34,

0)e6+e5)=c12-(c23-c13+c14-c34+c32)=9-(2-3+10-5+4B=

(P13,

P14,

P21,

P23,

P32,

P34,

e7)B1B2B3B4A1x11x1234103A239x2221x24A3x3146x33

20/7353σ24

=c24

-(c23-c13+c14)=8-(2-3+10)=

-1B1B2B3B4A1x11x1234103A23x22218x24A3x316x33

21/733σ31

=c31

-(c21-c23+c13-c14+c34)=7-(1-2+3-10+5)=B1B2B3B4A1x11x1234103A213x2221x24A37x316x33

22/7353σ33

=c33

-(c13-c14+c34)=10-(3-10+5)=

12B1B2B3B4A1x11x1234103A23x221x24A3x31610x33

23/7353■24/73Min

z=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x+5x3425/73s.t.

x11+x12+x13+x14

=7

u1x21+x22+x23+x24=4

u2x31+x32+x33+x34

=9

u3x11x12+x21+x31=3v1+x22+x32=6v2x13x14+x23+x24+x34=6+x33

=5

v3v4其對(duì)偶問題是26/73Max

w=7u1+4u2+9u3+3v1+6v2+5v3+6v4s.t.

u1+v1

≤3=c11u1+v2≤11=c12u1+v3≤3=c13u1+v4≤10=c14u2+v1≤1=c21u2+v2≤9=c22u2+v3≤2=c23u2+v4≤8=c24u3+v1≤7=c31u3+v2≤4=c32u3+v3≤10=c33u3+v4≤5=c3427/73令YT=(u1,u2,…,um,v1,v2,…,vn)則σij

=cij

-CBB-1Pij=cij

-YTPij=cij

-(u1,

u2,…,

um,

v1,

v2,

…,

vn)(ei+em+j=cij

-(ui+vj)對(duì)于基變量xij，檢驗(yàn)數(shù)σij

=0，即ui+vj=cij若從中求得ui和vj，就能利用σij

=cij

-(ui+vj)求基變量的σij。先看基變量u1+v3=3,令u1=0，v3=3u1+v4=10,

v4=10，u2+v3=2,

u2=-1，u2+v1=1,

v1=2，u3+v4=5,

u3=-5，u3+v2=4,

v2=9，B1B2B3B4A13x1111x1234103A2139x22218x24A37x314610x33

28/753

3再看非基變量σ11=c11-u1-v1=3-0-2=1,

σ12=c12-u1-v2=11-0-9=σ22=c22-u2-v2=9+1-9=1,

σ24=c24-u2-v4=8+1-10=σ31=c31-u3-v1=7+5-2=10,

σ33=c33-u3-v3=10+5-3u1=0，v3=3,

v4=10，u2=-1，v1=2，u3=-5，v2=9，B1B2B3B4A13x1111x1234103A2139x22218x24A37x314610x33

29/753

3三、解的改進(jìn)30/731.以x24為換入變量以非基格24為第一個(gè)頂點(diǎn)，沿迴路找運(yùn)輸量最小的偶數(shù)頂點(diǎn)，將該格換出，并以其運(yùn)輸量為調(diào)整量Δ=min{xij|基格ij是偶數(shù)頂點(diǎn)}。沿迴路調(diào)整各格中運(yùn)輸量，奇數(shù)格加Δ，偶數(shù)格減Δ。調(diào)整后，再計(jì)算檢驗(yàn)數(shù)。若所有的σij≥0，已得到最優(yōu)解。否則，重復(fù)以上步驟，直到取得最優(yōu)解。Δ=min{x23，x14}

=min{1，3}=1B1B2B3B4A1x11x124+13-1A23x221-1x230+1x24A3x316x33331/73重新計(jì)算檢驗(yàn)數(shù)σ11

=c11-(c14-c24+c21)=3-10+8-1=0σ12

=c12-c14+c34-c32=11-10+5-4=2σ22

=c22-c24+c34-c32=9-8+5-4=2

σ23

=c23-c24+c14-c13=2-8+10-3=1σ31

=c31-c21+c24-c34=7-1+8-5=9

σ33

=c33-c13+c14-c34=10-3+10-5=12x113x12115

321031x22

9x23

218x31

764x33

1032/73

3533/73所有的σij≥0，已經(jīng)得到最優(yōu)解。z=3x13+10x14+x21+8x24+4x32+5x34=3×5+10×2+3+×1+4×6+5×3=15+20+3+8+24+15=85B1B2B3B4余方量A1x11x12527A23x22x2314A3x316x3339需量365620

20四、須注意之點(diǎn)34/73若有多個(gè)非基變量檢驗(yàn)數(shù)小于零，一般取最小者對(duì)應(yīng)的非基變量換入。若有非基變量檢驗(yàn)數(shù)等于零，說明有多重解，應(yīng)當(dāng)將其全部求出。當(dāng)同時(shí)劃掉一行和一列時(shí)，會(huì)出現(xiàn)退化解。這時(shí)，應(yīng)在該行和該列相交的格中填數(shù)字0，確保有

m+n-1個(gè)基格（基變量）。第三節(jié)

進(jìn)一步討論35/73■36/73■37/73花都樂園清泉供應(yīng)量臨清廠2x117x124x1325武清廠3x216x225x2335需求量10251550

60[例1]有兩個(gè)磚廠，供三個(gè)城市使用。產(chǎn)量、需求量和單位運(yùn)費(fèi)列于下表。問：如何調(diào)度，才使運(yùn)費(fèi)最少？38/73花都樂園清泉建委供應(yīng)量臨清廠2x117x124x130x1425武清廠3x216x225x230x2435需求量1025151060假設(shè)滯銷的磚由該地區(qū)建委收購(gòu)，留在磚廠，以備將來使用。這樣，建委就成了第四個(gè)用戶。39/73以下用最小元素法確定初始基可行解花都樂園清泉建委

供應(yīng)量臨清廠x11x12x13x1425武清廠x21x22x231035-10需求量10251510-10=06027403650花都樂園清泉建委

供應(yīng)量臨清廠10x12x13x1425-10武清廠x21x22x231025需求量

10-102515400/736027403650花都樂園清泉建委供應(yīng)量臨清廠2107x124150x1415-15武清廠3x216x225001025需求量02515-15=0060花都樂園清泉建委供應(yīng)量臨清廠2107x124150x140武清廠3x216255001025-25=0需求量025-25=00410/07360σ12

=c12-c13+c23-c22=7-4+5-6=2σ21

=c21-c11+c13-c23=3-2+4-5=0均大于0，已經(jīng)到最優(yōu)解。σ14

=c14-c24+c23-c13=0-0+5-4=1，Min

z=2×10+4×15+6×25=23042/73花都樂園清泉建委供應(yīng)量臨清廠2107x124150x140武清廠3x21625500100需求量000060花溪桃園樂泉愿搬人家王村8x117x124x13150張屯3x215x229x23250住宅套數(shù)200100200500

400[例2]政府計(jì)劃將兩個(gè)老區(qū)500戶搬到三個(gè)新建小。愿意搬的人家、住宅套數(shù)和每戶拆遷費(fèi)列于下表。問：如何調(diào)度，才使拆遷費(fèi)最少（假定每戶一套）？43/73假設(shè)剩下的100套由市住房辦保管，用作臨時(shí)安置新增人口。不需拆遷費(fèi)?；ㄏ覉@樂泉拆遷戶王村8x117x124x13150張屯3x215x229x23250市住房辦0x310x320x33100住宅套數(shù)200100200500

50044/73花溪桃園樂泉愿搬戶王村8x117x124x13150張屯3x215x229x23250住房辦01000x320x33100-100住宅數(shù)200-100100200400

400用最小元素法確定初始基可行解145/73花溪桃園樂泉愿搬戶王村8x117x124x13150張屯31005x229x23250-100住房辦01000x320x330住宅數(shù)100-100100200300

300用最小元素法確定初始基可行解246/73愿搬戶王村x11

x12150150-150張屯100x22x23150住房辦100x32x330住宅數(shù)0100

200-150150

150花溪

桃園

樂泉8

7435900047/73用最小元素法確定初始基可行解3花溪

桃園

樂泉愿搬戶王村x11x121500張屯100100x23150-100住房辦100x32x330住宅數(shù)0100-100508

7

435

900

048/73用最小元素法確定初始基可行解4花溪桃園樂泉愿搬戶王村8x117x1241500張屯3100510095050-50住房辦01000x320x330住宅數(shù)0050-50用最小元素法確定初始基可行解549/73花溪桃園樂泉王村8x117x124150張屯31005100950住房辦01000x320x3350/73判斷是否最優(yōu)：σ11

=c11-c13+c23-c21=8-4+9-3=10σ12

=c12-c13+c23-c22=7-4+9-5=7σ32

=c32-c31+c21-c22=0-0+3-5=

-2σ33

=c33-c31+c21-c23=0-0+3-9=

-6z=4×150+3×100+5×100+9×50=1850花溪桃園樂泉王村8x117x124150張屯100

3+50100

550-50

9住房辦100

0-500x320+50

0換基：非基變量x33

換入，確定調(diào)整量Δ=min{x31,x23}=min{100,50}=50，調(diào)整如下：51/73花溪桃園樂泉王村8x117x124150張屯315051009x23住房辦0500x32050重新計(jì)算檢驗(yàn)數(shù)σ11

=c11-c13+c33-c31=8-4+0-0=4σ12

=c12-c13+c33-c31+c21-c22=7-4+0-0+3-5=1

σ23

=c23-c33+c31-c21=9-0+0-3=6σ32

=c32-c31+c21-c22=0-0+3-5=

-2z=4×150+3×150+5×100=155052/73花溪桃園樂泉王村8x117x124150張屯150

3+505100-509x23住房辦050-5000+50050再換基：非基變量x32換入，確定調(diào)整量Δ=min{x31,x22}=min{50,100}=50，調(diào)整如下：53/73花溪桃園樂泉王村x11

8x12

71504張屯2003505x23

9住房辦x31

050050054/73重新計(jì)算檢驗(yàn)數(shù)σ11

=c11-c13+c33-c32+c22-c21=8-4+0-0+5-3=6σ12

=c12-c13+c33-c32=7-4+0-0=3σ23

=c23-c33+c32-c22=9-0+0-5=

4σ31

=c31-c21+c22-c32=0-3+5+0=

2，所有的σij>0，已得到最優(yōu)解。Min

z=4×150+3×200+5×50=1450[習(xí)題3.7第2題]B1B2B3B4B5產(chǎn)量A13x117x126x134x140x155A22x214x223x232x240x252A34x313x328x335x340x356銷量3322310

1355/73[習(xí)題3.7第2題]A1B13x11B27x12B36x13B44x14B503產(chǎn)量5-2=2A2x212x224x233x2420x252A3438506銷量x313x323x332x342x353-3=010

1356/73B1B2B3B4B5產(chǎn)量A1x11x13x1432A22x232-2=0A3x31x32x33x34

x356銷量

3-2=13220

10

1337x12602344x22380x24

x250[習(xí)題3.7第2題]42557/73B1B2B3B4B5產(chǎn)量A11x13x1432-1=1A22x230A3x313x33x34

x356-3=3銷量

1-1=00220

10

1337x12602344x22380x24

x250[習(xí)題3.7第2題]42558/73[習(xí)題3.7第2題]B1B2B3B4B5產(chǎn)量A1317x126x1341031-1=0A2224x223x232x240x250A34x31338x33510x353-1=2銷量0021-1=0010

1359/73[習(xí)題3.7第2題]B1B2B3B4B5產(chǎn)量A1317x126x1341030A2224x223x232x240x250A34x313382510x352-2=0銷量002-2=00010

1360/73計(jì)算檢驗(yàn)數(shù)σ12

=c12-c14+c34-c32=7-4+5-3=561/73σ13

=c13-c14+c33-c33=6-4+5-8=

-1σ22

=c22-c21+c11-c14+c35-c32=4-2+3-4+5-3=3σ23

=c23-c33+c34-c14+c11-c21=3-8+5-4+3-2=

-3σ24

=c24-c21+c11-c14=2-2+3-4=

-1σ25

=c25-c15+c11-c21=0-0+3-2=1σ31

=c31-c34+c14-c11=4-5+4-3=0σ35

=c35-c15+c14-c34=0-0+4-5=

-1令x23換入。然后，沿計(jì)算σ23的回路調(diào)整運(yùn)輸量。[習(xí)題3.7第2題]B1B2B3B4B5產(chǎn)量A131+17x126x1341-103A222-14x223x23+12x240x25A34x313382-151+10x35銷量62/73[習(xí)題3.7第2題]B1B2B3B4B5產(chǎn)量A1327x126x134x1403A2214x22312x240x25A34x313381520x35銷量63/73再計(jì)算檢驗(yàn)數(shù)σ12

=c12-c11+c21-c23+c33-c32=7-3+2-3+8-3=864/73σ13

=c13-c23+c32-c11=6-3+2-3=

2σ14

=c14-c34+c33-c23+c21-c11=4-5+8-3+2-3=

3σ22

=c22-c32+c33-c23=4-3+8-3=6σ24

=c24-c23+c33-c34=2-3+8-5=

2σ25

=c25-c15+c11-c21=0-0+3-2=1σ31

=c31-c33+c23-c21=4-8+3-2=

-3σ35

=c35-c15+c11-c21+c23-c33=0-0+3-2+3-8=

-4令x35換入。然后，沿計(jì)算σ35的回路調(diào)整運(yùn)輸量。[習(xí)題3.7第2題]B1B2B3B4B5產(chǎn)量A132+17x126x134x1403-1A221-14x2231+12x240x25A34x313381-1520x35+1銷量σ35

=c35-c15+c11-c21+c23-c33=0-0+3-2+3-8=

-465/73[習(xí)題3.7第2題]B1B2B3B4B5產(chǎn)量A1337x126x134x1402A2204x22322x240x25A34x31338x335201銷量66/73第三次計(jì)算檢驗(yàn)數(shù)σ12

=c12-c15+c35-c32=7-0+0-3=467/73σ13

=c13-c11+c21-c23=6-3+2-3=

2σ14

=c14-c15+c35-c34=4-0+0-5=

-1σ22

=c22-c21+c11-c15+c35-c32=4-2+3-0+0-3=2σ24

=c24-c34+c35-c15+c11-c21=2-5+0-0+3-2=

-2σ25

=c25-c15+c11-c21=0-0+3-2=1σ31

=c31-c35+c15-c11=4-0+0-3=

1令x24換入。然后，沿計(jì)算σ24的回路調(diào)整運(yùn)輸量。[習(xí)題3.7第2題]B1B2