清华大学运筹学3运输问题

第三章

运输问题1/73第一节

运输问题及其数学模型第二节

表上作业法第三节

进一步讨论第一节

运输问题及其数学模型2/73一、问题的提出欠土B1欠土B2欠土B3欠土B4余方量多土

A13x1111x123x1310x147多土

A21x219x222x238x244多土

A37x314x3210x335x349需量3653/73620

20[例2]平整某场地，有三处高，需削平，有四处低，需填高。已算出高处总余方量恰好满足低处总需方量。12种运价也已算出，在右上角方格内。问：如何调度，才花费最少？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

皆为正整数。供应点m=3个，用户有n=4个。运输问题数学模型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分别是三个供应点供应量,d1,d2,d3和别是四个用户需求量。当s1+s2+s3=d1+d2+d3+d4时，是供求平衡运输问题，否则，是供求不平衡运输问题。先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个元素为1的m+n维单位向量。第二节

表上作业法8/73一、确定初始可行解最小元素法西北角法（不讲）Vogel法（不讲）最小元素法举例说明。9/73欠土B1欠土B2欠土B3欠土B4余方量多土

A13x1111x123x1310x147多土

A2139x222x238x244-3=1多土

A37x314x3210x335x349需量3-3=06510/73620

20从A2运往B1的费用最低，先将A2的土运往B1，B1需求量是3，满足后，A2还有剩余。B1的需求既然已经满足，以后不再考虑。划去第一列B1B2B3B4余方量A13x1111x123x1310x147A2139x22218x241-1=0A37x314x3210x335x349需量065-1=411/73620

20剩下的，从A2运往B3的费用最低，B3需要5，A2只能满足1。A2以后不再考虑。划去第二行。B1B2B3B4余方量A13x1111x123410x147-4=3A2139x22218x240A37x314x3210x335x349需量064-4=012/73620

20剩下的，从A1运往B3的费用最低，将A1的土运往

B3，B3需求量是4，从A1运来4，就满足了，以后不再考虑。划去第三列。B1B2B3B4余方量A13x1111x123410x143A2139x22218x240A37x314610x335x349-6=3需量06-6=0013/73620

20剩下的，从A3运往B2的费用最低，B2需求量是6，可从A3处满足，以后不再考虑。划去第二列。B1B2B3B4余方量A13x1111x123410x143A2139x22218x240A37x314610x33533-3=0需量00014/736-3=320

20剩下的，从A3运往B4的费用最低，B4需求量是6，可从A3处得到3，以后不再考虑A3

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

20B4需3，A1剩3，可满足。划去第一行和第四列。非负数字格叫基格，对应基变量(m+n-1个)。其他格叫非基格，对应非基变量(mn-m-n+1个)，非基变量均取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初始基可行解是否最优，即z是否达到了最小值？用非基变量检验数判断。检验数有几种算法。1.迴路法计算检验数σij

=cij

-CBB-1Pij，为此，考察非基变量同基变量的关系。B=

(P13,

P14,

P21,

P23,

P32,

P34,

e7)先看非基变量x11，非基格11与基格13、基格23、基格21构成迴路。再看如下关系：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其对偶问题是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)对于基变量xij，检验数σ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三、解的改进30/731.以x24为换入变量以非基格24为第一个顶点，沿迴路找运输量最小的偶数顶点，将该格换出，并以其运输量为调整量Δ=min{xij|基格ij是偶数顶点}。沿迴路调整各格中运输量，奇数格加Δ，偶数格减Δ。调整后，再计算检验数。若所有的σij≥0，已得到最优解。否则，重复以上步骤，直到取得最优解。Δ=min{x23，x14}

=min{1，3}=1B1B2B3B4A1x11x124+13-1A23x221-1x230+1x24A3x316x33331/73重新计算检验数σ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，已经得到最优解。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四、须注意之点34/73若有多个非基变量检验数小于零，一般取最小者对应的非基变量换入。若有非基变量检验数等于零，说明有多重解，应当将其全部求出。当同时划掉一行和一列时，会出现退化解。这时，应在该行和该列相交的格中填数字0，确保有

m+n-1个基格（基变量）。第三节

进一步讨论35/73■36/73■37/73花都乐园清泉供应量临清厂2x117x124x1325武清厂3x216x225x2335需求量10251550

60[例1]有两个砖厂，供三个城市使用。产量、需求量和单位运费列于下表。问：如何调度，才使运费最少？38/73花都乐园清泉建委供应量临清厂2x117x124x130x1425武清厂3x216x225x230x2435需求量1025151060假设滞销的砖由该地区建委收购，留在砖厂，以备将来使用。这样，建委就成了第四个用户。39/73以下用最小元素法确定初始基可行解花都乐园清泉建委

供应量临清厂x11x12x13x1425武清厂x21x22x231035-10需求量10251510-10=06027403650花都乐园清泉建委

供应量临清厂10x12x13x1425-10武清厂x21x22x231025需求量

10-102515400/736027403650花都乐园清泉建委供应量临清厂2107x124150x1415-15武清厂3x216x225001025需求量02515-15=0060花都乐园清泉建委供应量临清厂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，已经到最优解。σ14

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

z=2×10+4×15+6×25=23042/73花都乐园清泉建委供应量临清厂2107x124150x140武清厂3x21625500100需求量000060花溪桃园乐泉愿搬人家王村8x117x124x13150张屯3x215x229x23250住宅套数200100200500

400[例2]政府计划将两个老区500户搬到三个新建小。愿意搬的人家、住宅套数和每户拆迁费列于下表。问：如何调度，才使拆迁费最少（假定每户一套）？43/73假设剩下的100套由市住房办保管，用作临时安置新增人口。不需拆迁费。花溪桃园乐泉拆迁户王村8x117x124x13150张屯3x215x229x23250市住房办0x310x320x33100住宅套数200100200500

50044/73花溪桃园乐泉愿搬户王村8x117x124x13150张屯3x215x229x23250住房办01000x320x33100-100住宅数200-100100200400

400用最小元素法确定初始基可行解145/73花溪桃园乐泉愿搬户王村8x117x124x13150张屯31005x229x23250-100住房办01000x320x330住宅数100-100100200300

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

x12150150-150张屯100x22x23150住房办100x32x330住宅数0100

200-150150

150花溪

桃园

乐泉8

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

桃园

乐泉愿搬户王村x11x121500张屯100100x23150-100住房办100x32x330住宅数0100-100508

7

435

900

048/73用最小元素法确定初始基可行解4花溪桃园乐泉愿搬户王村8x117x1241500张屯3100510095050-50住房办01000x320x330住宅数0050-50用最小元素法确定初始基可行解549/73花溪桃园乐泉王村8x117x124150张屯31005100950住房办01000x320x3350/73判断是否最优：σ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

换入，确定调整量Δ=min{x31,x23}=min{100,50}=50，调整如下：51/73花溪桃园乐泉王村8x117x124150张屯315051009x23住房办0500x32050重新计算检验数σ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换入，确定调整量Δ=min{x31,x22}=min{50,100}=50，调整如下：53/73花溪桃园乐泉王村x11

8x12

71504张屯2003505x23

9住房办x31

050050054/73重新计算检验数σ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，已得到最优解。Min

z=4×150+3×200+5×50=1450[习题3.7第2题]B1B2B3B4B5产量A13x117x126x134x140x155A22x214x223x232x240x252A34x313x328x335x340x356销量3322310

1355/73[习题3.7第2题]A1B13x11B27x12B36x13B44x14B503产量5-2=2A2x212x224x233x2420x252A3438506销量x313x323x332x342x353-3=010

1356/73B1B2B3B4B5产量A1x11x13x1432A22x232-2=0A3x31x32x33x34

x356销量

3-2=13220

10

1337x12602344x22380x24

x250[习题3.7第2题]42557/73B1B2B3B4B5产量A11x13x1432-1=1A22x230A3x313x33x34

x356-3=3销量

1-1=00220

10

1337x12602344x22380x24

x250[习题3.7第2题]42558/73[习题3.7第2题]B1B2B3B4B5产量A1317x126x1341031-1=0A2224x223x232x240x250A34x31338x33510x353-1=2销量0021-1=0010

1359/73[习题3.7第2题]B1B2B3B4B5产量A1317x126x1341030A2224x223x232x240x250A34x313382510x352-2=0销量002-2=00010

1360/73计算检验数σ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换入。然后，沿计算σ23的回路调整运输量。[习题3.7第2题]B1B2B3B4B5产量A131+17x126x1341-103A222-14x223x23+12x240x25A34x313382-151+10x35销量62/73[习题3.7第2题]B1B2B3B4B5产量A1327x126x134x1403A2214x22312x240x25A34x313381520x35销量63/73再计算检验数σ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换入。然后，沿计算σ35的回路调整运输量。[习题3.7第2题]B1B2B3B4B5产量A132+17x126x134x1403-1A221-14x2231+12x240x25A34x313381-1520x35+1销量σ35

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

-465/73[习题3.7第2题]B1B2B3B4B5产量A1337x126x134x1402A2204x22322x240x25A34x31338x335201销量66/73第三次计算检验数σ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换入。然后，沿计算σ24的回路调整运输量。[习题3.7第2题]B1B2