数学建模运输问题附源代码

数学建模运输问题附源代码第一页，共一百三十四页，编辑于2023年，星期三3-1运输问题问题的提出

从m个发点A1,A2,…..Am向n个收点B1,B2…..Bn发送某种货物。Ai发点的发量为ai，Bj收点的收量为bj。由Ai

运往Bj

单位货物的运费为Cij，由Ai

运往Bj

货物的运量为Xij。问如何调配，才能使运费最省？第二页，共一百三十四页，编辑于2023年，星期三

当发点的发量总和为

ai，收点的收量总和为

bj相等时，称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。若没有特别说明，均假定运输问题为平衡的运输问题。第三页，共一百三十四页，编辑于2023年，星期三销地产地12…

m12…n销量产量a1a2am

…

b1b2…bn

c21c22…c2ncm1cm2…cmnc11c12…c1n

…

cij

为运价第四页，共一百三十四页，编辑于2023年，星期三销地产地12…

m销量产量a1a2am

…

x21x22…x2nxm1xm2…xmn

x11x12…x1n

…

xij

为运量b1b2…bn12…n第五页，共一百三十四页，编辑于2023年，星期三运输问题的数学模型：MinS=cijxij

ij

xij=ai(i=1,2…..m)

j

xij=bj(j=1,2……n)i

xij0(i=1,2…..m;j=1,2……n)第六页，共一百三十四页，编辑于2023年，星期三运输问题数学模型系数阵为：第七页，共一百三十四页，编辑于2023年，星期三且共有m+n个约束方程。并成立：所以模型最多只有m+n-1个独立约束方程,系数矩阵的秩≤m+n-1第八页，共一百三十四页，编辑于2023年，星期三运输问题的图表形式第九页，共一百三十四页，编辑于2023年，星期三运输问题解的结构

由于

ai=bj成立

ij其m+n个约束方程并不是独立的。实际上只有m+n-1个是独立的。即约束方程系数矩阵的秩为m+n-1。第十页，共一百三十四页，编辑于2023年，星期三3-2运输问题的求解确定初始方案西北角法例1第十一页，共一百三十四页，编辑于2023年，星期三（1）从图的西北角开始，填入a1与b1较小的值，b1=2，即从A1运给B1

（2吨）B1已经满足，划去b1列，并将a1=4-2=2第十二页，共一百三十四页，编辑于2023年，星期三（2）向a1，b1较大方向移动一格（或向右，或向下）此时向右移动一格（A1，B2）B2需要4吨，而A1只有2吨，A1已发完，划去A1行，并把b2改成（4-2）=2。第十三页，共一百三十四页，编辑于2023年，星期三（3）继续进行第十四页，共一百三十四页，编辑于2023年，星期三（4）继续进行第十五页，共一百三十四页，编辑于2023年，星期三（5）继续进行第十六页，共一百三十四页，编辑于2023年，星期三（6）继续进行第十七页，共一百三十四页，编辑于2023年，星期三（7）得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，总运费=6*2+5*2+4*2+7*3+5*1+8*3=80（元）第十八页，共一百三十四页，编辑于2023年，星期三2最小元素法第十九页，共一百三十四页，编辑于2023年，星期三（1）从最小元素开始（3）即A1优先满足B33个单位，B3已经满足，划去B3列，第二十页，共一百三十四页，编辑于2023年，星期三（2）再从最小元素开始（4）即A1优先满足B41个单位，A1已经满足，划去A1行，第二十一页，共一百三十四页，编辑于2023年，星期三（3）再从最小元素开始（4）即A2优先满足B12个单位，B1已经满足，划去B1列，第二十二页，共一百三十四页，编辑于2023年，星期三（4）再从最小元素开始（4）即A2优先满足B24个单位，B2A2已经满足，划去B2列A2

行。第二十三页，共一百三十四页，编辑于2023年，星期三（4）最后把A3满足B43个单位，得到初始方案。。第二十四页，共一百三十四页，编辑于2023年，星期三（5）得到初始方案：X13=3，X14=1，X21=2，X22=4，X32=0，X34=3总运费=3*3+4*1+4*2+4*4+8*3=61（元）第二十五页，共一百三十四页，编辑于2023年，星期三3.差值法（伏格法）

每次从当前运价表上，计算各行各列中两个(最小与次小）运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案。第二十六页，共一百三十四页，编辑于2023年，星期三第二十七页，共一百三十四页，编辑于2023年，星期三第二十八页，共一百三十四页，编辑于2023年，星期三第二十九页，共一百三十四页，编辑于2023年，星期三第三十页，共一百三十四页，编辑于2023年，星期三第三十一页，共一百三十四页，编辑于2023年，星期三第三十二页，共一百三十四页，编辑于2023年，星期三第三十三页，共一百三十四页，编辑于2023年，星期三第三十四页，共一百三十四页，编辑于2023年，星期三第三十五页，共一百三十四页，编辑于2023年，星期三差值法初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，费用=3*3+4*1+4*2+4*1+5*3+6*3=58（元）第三十六页，共一百三十四页，编辑于2023年，星期三西北角法得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，总运费=6*2+5*2+4*2+7*3+5*1+8*3=80（元）第三十七页，共一百三十四页，编辑于2023年，星期三最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3总运费=3*3+4*1+4*2+4*4+8*3=61（元）第三十八页，共一百三十四页，编辑于2023年，星期三西北角法得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，总运费=6*2+5*2+4*2+7*3+5*1+8*3=80（元）最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3，总运费=3*3+4*1+4*2+4*4+8*3=61（元）差值法初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，总运费=3*3+4*1+4*2+4*1+5*3+6*3=58（元）第三十九页，共一百三十四页，编辑于2023年，星期三例：分别用西北角法、最小元素和伏格尔法求产销平衡运输问题的初始基可行解

第四十页，共一百三十四页，编辑于2023年，星期三解（1）西北角法

Z=399第四十一页，共一百三十四页，编辑于2023年，星期三（2）最小元素

Z=240第四十二页，共一百三十四页，编辑于2023年，星期三（3）伏格尔法

Z=240第四十三页，共一百三十四页，编辑于2023年，星期三求最优方案1闭回路在初始调运方案表中，从任意空格出发，沿着纵向或横向行进，遇到适当填有数据的方格90度转弯，继续行进，总能回到原来空格。这个封闭的曲线称为闭回路。可以证明：每个空格对应着唯一的闭回路。第四十四页，共一百三十四页，编辑于2023年，星期三

第四十五页，共一百三十四页，编辑于2023年，星期三如下表：第四十六页，共一百三十四页，编辑于2023年，星期三如下表：第四十七页，共一百三十四页，编辑于2023年，星期三如下表：第四十八页，共一百三十四页，编辑于2023年，星期三第四十九页，共一百三十四页，编辑于2023年，星期三第五十页，共一百三十四页，编辑于2023年，星期三第五十一页，共一百三十四页，编辑于2023年，星期三第五十二页，共一百三十四页，编辑于2023年，星期三第五十三页，共一百三十四页，编辑于2023年，星期三第五十四页，共一百三十四页，编辑于2023年，星期三第五十五页，共一百三十四页，编辑于2023年，星期三第五十六页，共一百三十四页，编辑于2023年，星期三第五十七页，共一百三十四页，编辑于2023年，星期三第五十八页，共一百三十四页，编辑于2023年，星期三第五十九页，共一百三十四页，编辑于2023年，星期三第六十页，共一百三十四页，编辑于2023年，星期三求检验数

要判断一个调运方案是否已是最优，就要判断方案所对应的基础可行解是否最优。在单纯形法中，根据非基变量（空格）的检验数来判别的。若检验数中没有负值，则已求得最优。如何根据初始调运表求得检验数？第六十一页，共一百三十四页，编辑于2023年，星期三（1）闭回路法

空格Xij的检验数=（第奇数次拐角点运价之和减去第偶数次拐角点运价之和）第六十二页，共一百三十四页，编辑于2023年，星期三空格X21的检验数=4-6+5-4=-1B1B2B3B4产量A16

05

03

4

4A24

-1

4

07

05

06A37658

03销量

2

4

3

4第六十三页，共一百三十四页，编辑于2023年，星期三空格X14的检验数=4-5+4-5=-2B1B2B3B4产量A16

05

03

4

4A24

-1

4

0705

06A37658

03销量

2

4

3

4第六十四页，共一百三十四页，编辑于2023年，星期三空格X31的检验数=7-6+5-4+5-8=-1B1B2B3B4产量A16

05

03

4

-24A24

-14

07

05

06A37658

03销量

2

4

3

4第六十五页，共一百三十四页，编辑于2023年，星期三检验数都为负值，原方案不是最优解B1B2B3B4产量A16

05

03

-54

-2

4A24

-14

07

05

06A37

-16

-15

-58

03销量

2

4

3

4第六十六页，共一百三十四页，编辑于2023年，星期三（2）位势法

设变量ui和vj(i=1,2,…m;j=1,2,…n)是运输问题的m+n个约束条件的对偶变量，B是含有一个人工变量xa的（m+n)×(m×n)初始基矩阵，ca=0.称ui与vj为相应的各行与各列的位势。Y=CBB-=(u1,…,um,v1,…,vn),pij=ei+em+j,CBB-Pij=ui+vj，

=cij-CBB-Pij=cij-(ui+vj)当为基变量检验数时，ui+vj=

cij对于基变量Xij有：ui+vj=CijM+n-1个方程，m+n个未知数，可令u1=0.第六十七页，共一百三十四页，编辑于2023年，星期三（2）位势法对初始调运方案，定义一组新的变量（对偶）ui和vj(i=1,2,…m;j=1,2,…n)对于基变量Xij有：ui+vj=Cij称ui与vj为相应的各行与各列的位势。对于非基变量Xij有：=cij-CBB-Pij=cij-（ui+vj）第六十八页，共一百三十四页，编辑于2023年，星期三例：u1+v1=6u1+v2=5u2+v2=4u2+v3=7u2+v4=5u3+v4=8有七个变量，但只有六个方程，有一个自由变量，一般令u1=0B1B2B3B4uiA16

05

03

-54

-2

0A24

-14

07

05

0-1A37

-16

-15

-58

02vj

6

5

8

6第六十九页，共一百三十四页，编辑于2023年，星期三调整方案从一个方案调整到最优方案的过程，就是单纯形法的过程。选择检验数（一般取最小）为负值的空格所对应的变量为进基变量，在进基变量的回路中，比较含（-1）拐角点的运量，选择一个具有最小运量的基变量作为出基变量，并调整运量=min(含（-1）的运量)第七十页，共一百三十四页，编辑于2023年，星期三选择（A1，B3）（检验数最大）调整，最小运量=min(2,3)=2B1B2B3B4产量A16

25

2（-1）3

（+1）

4

4A24

4

2（+1）

7

3（-1）5

16A37658

33销量

2

4

3

4第七十一页，共一百三十四页，编辑于2023年，星期三B1B2B3B4产量A16

25

3

24

4A24

4

47

15

16A37658

33销量

2

4

3

4第七十二页，共一百三十四页，编辑于2023年，星期三最小运量=min(2,3)=2,奇数点减去2，偶数点加上2，得到新的方案。总运费=6*2+3*2+4*4+7*1+5*1+8*3=70（元）原方案运费为80（元）B1B2B3B4产量A16

25

3

24

4A24

4

47

15

16A37658

33销量

2

4

3

4第七十三页，共一百三十四页，编辑于2023年，星期三继续求检验数。B1B2B3B4uiA16

05

5

3

04

3

0A24

-64

07

05

04A37

-66

-15

-58

07vj

6

0

3

1第七十四页，共一百三十四页，编辑于2023年，星期三继续调整运量。B1B2B3B4产量A16

2（-1）5

3

2（+1）4

4A24

（+1）

4

47

1（-1）5

16A37658

33销量

2

4

3

4第七十五页，共一百三十四页，编辑于2023年，星期三继续调整运量。最小运量=1总运费=6*1+3*3+4*1+4*4+5*1+8*3=64（元）B1B2B3B4产量A16

15

3

34

4A24

1

4

47

5

16A37658

33销量

2

4

3

4第七十六页，共一百三十四页，编辑于2023年，星期三继续计算检验数。B1B2B3B4uiA16

05

-1

3

04

-3

0A24

04

07

6

5

0-2A37

06

-15

18

01vj

6

6

3

7

第七十七页，共一百三十四页，编辑于2023年，星期三继续调整运量。最小运量=1B1B2B3B4产量A16

15

3

34

4A24

1

4

47

5

16A37658

33销量

2

4

3

4第七十八页，共一百三十四页，编辑于2023年，星期三得到新的调运方案，总运费=3*3+4*1+4*2+4*4+8*3=61（元）B1B2B3B4产量A16

5

3

34

1

4A24

2

4

47

5

06A37658

33销量

2

4

3

4第七十九页，共一百三十四页，编辑于2023年，星期三继续计算检验数B1B2B3B4uiA16

65

5

3

04

0

0A24

04

07

3

5

01A37

06

25

-28

04vj

0

0

3

4

第八十页，共一百三十四页，编辑于2023年，星期三B1B2B3B4产量A16

5

3

34

1

4A24

2

4

47

5

06A37658

33销量

2

4

3

4继续调整运量。最小运量=3第八十一页，共一百三十四页，编辑于2023年，星期三B1B2B3B4产量A16

5

3

04

44A24

2

4

47

5

06A3765

38

3销量

2

4

3

4总运费=4*4+4*2+4*4+5*3=55（元）第八十二页，共一百三十四页，编辑于2023年，星期三计算检验数：空格的检验数全为非负，此时是最优解。最优调运方案：X21=2，X22=4，X14=4，X33=3。最小运费55（元）。第八十三页，共一百三十四页，编辑于2023年，星期三例2：产销平衡表为：

销地产地B1B2B3B4产量A13

11

3

10

7A21

9

2

8

4A374105

9销量

3

6

5

6第八十四页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4产量A13

11

3

4

10

3

7A21

39

2

18

4A374

6105

39销量

3

6

5

6（1）用最小元素法求初始基可行解表（1）第八十五页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4uiA13

111

23

0

10

0

0A21

09

12

08

-1-1A37104

010

125

0-5vj

2

9

3

10（2）用位势法求检验数表（2）第八十六页，共一百三十四页，编辑于2023年，星期三（2）检验数=-1＜0，用闭回路调节

销地产地B1B2B3B4产量A13

11

3

4+1

10

3-1

7A21

39

2

1-18

（+1）

4A374

6105

39销量

3

6

5

6表（3）第八十七页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4产量A13

11

3

5

10

2

7A21

39

2

8

1

4A374

6105

39销量

3

6

5

6（3）用闭回路调节得表（4）第八十八页，共一百三十四页，编辑于2023年，星期三（2）用位势法再求表（4）的检验数

销地产地B1B2B3B4uiA13

011

23

0

10

0

0A21

09

22

18

0-2A3794

010

125

0-5vj

3

9

3

10表（5）非基变量，有无穷多最优解第八十九页，共一百三十四页，编辑于2023年，星期三表（5）中空格的检验数全为非负，此时是最优解。最优调运方案为表（4），最小费用为85元。

销地产地B1B2B3B4产量A13

11

3

5

10

2

7A21

39

2

8

1

4A374

6105

39销量

3

6

5

6第九十页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4产量A13（+1）

11

3

5

10（-1）

2

7A21（-1）

39

2

8（+1）

1

4A374

6105

39销量

3

6

5

6第九十一页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4产量A13

211

3

5

10

7A21

19

2

8

3

4A374

6105

39销量

3

6

5

6为另一最优解第九十二页，共一百三十四页，编辑于2023年，星期三例3

某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服务，生产和需求情况如下：第九十三页，共一百三十四页，编辑于2023年，星期三从炼油厂运往第j个销售区每公升汽油平均运费（单位：角/公升），应如何调运，使运费最省。销地产地1234567产量1652636335237586922534865585154744747440销量25201025101510第九十四页，共一百三十四页，编辑于2023年，星期三解：平衡问题，用最小元素法求初始方案为：销地产地1234567产量1652

10

63633523

7586922534865585154744747440销量25201025101510第九十五页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

63633523

758692102534865585154744747440销量25201025101510第九十六页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6310633523

758692102534865585154744747440销量25201025101510第九十七页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6310633523

15758692102534865585154744747440销量25201025101510第九十八页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6310633523

15758692

10253410865585154744747440销量25201025101510第九十九页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6310633523

157586921025341086558515474

204747440销量25201025101510第一百页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6310633523

1575869210253410865

558515474

204747440销量25201025101510第一百零一页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6

1575869210253410865

558515474204747440销量25201025101510第一百零二页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6

1575869210253410865

5585154742047547440销量25201025101510第一百零三页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1652

10

6

153106335231575869210253410865

5585154742047547

15440销量25201025101510第一百零四页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1

10

15

10352

15

10253

10

5154

20

5

1540销量25201025101510用最小元素法得初始基可行解为：表（1）第一百零五页，共一百三十四页，编辑于2023年，星期三用位势法计算检验数。销地产地1234567

ui1652

0

603063023

07586920-234

0865

0585-1474047047

041vj5326364第一百零六页，共一百三十四页，编辑于2023年，星期三销地产地1234567

ui16

1522

0

6030603-1023

0765584659520-234

086655

0538352-1471404170407

04-11vj5326364检验数为：检验数0，故表（1）不是最优解＜第一百零七页，共一百三十四页，编辑于2023年，星期三闭回路调节销地产地1234567产量1

10

15-1

10

+1352

15+1

10-125310-1

5+1154

20

5

1540销量25201025101510第一百零八页，共一百三十四页，编辑于2023年，星期三销地产地1234567产量1

10

5

1010

352

25

0253

15154

20

5

1540销量25201025101510闭回路调节为：表（2）第一百零九页，共一百三十四页，编辑于2023年，星期三再用位势法计算表（2）检验数。销地产地1234567

ui16

2522

0

60306030023

0745483649420-134

186655

0538353-1472404170407

0401vj4326363检验数0，故表（2）是最优解，总运费=480000（元）第一百一十页，共一百三十四页，编辑于2023年，星期三最优方案如下，最小运费=480000元第一百一十一页，共一百三十四页，编辑于2023年，星期三有非基变量的检验数=0，有无穷多组解，另外一个解如下：第一百一十二页，共一百三十四页，编辑于2023年，星期三产销不平衡运输问题当时，假想一个销地Bn+1（仓库），销量为运费Cin+1=0,i=1,2,…,m＞当时,假想一个产地An+1，产量为运费Cn+1j=0,j=1,2,…,n＜第一百一十三页，共一百三十四页，编辑于2023年，星期三销地产地12…

m销量产量a1a2am

…

c21c22…c2ncm1cm2…cmnc11c12…c1n

…

12…nn+1000b1b2…bnbn+1

产大于销第一百一十四页，共一百三十四页，编辑于2023年，星期三产小于销销地产地12…

m销量产量a1a2am

…

c21c22…c2ncm1cm2…cmnc11c12…c1n

…

12…nb1b2…bn

m+100…0am+1第一百一十五页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4产量A12

11

3

4

7A210

3

5

9

5A37812

7销量

2

3

46

1915例4：运输问题产销表为：第一百一十六页，共一百三十四页，编辑于2023年，星期三例4：产销平衡表为：

销地产地B1B2B3B4B5产量A12

11

3

40

7A210

3

5

90

5A378120

7销量

2

3

464第一百一十七页，共一百三十四页，编辑于2023年，星期三（1）用vogel求初始基可行解

销地产地B1B2B3B4B5产量A12

211

3

40

3

27A210

3

3

5

90

25A3781

4

20

3

7销量

2

3

464第一百一十八页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4B5产量A1

2

327A2

3

25A3

4

37销量

2

3

464初始基可行解为第一百一十九页，共一百三十四页，编辑于2023年，星期三

销地产地B1B2B3B4B5uiA1

2

011

83

040

000A210

83

05

290

5

00A37

78

71

020

0

2-2vj

2

3

340（2）用位势法求检验数，第一百二十页，共一百三十四页，编辑于2023年，星期三检验数均为非负，故初始基可行解即为最优解，如下：

销地产地B1B2B3B4B5产量A1

2

327A2

3

25A3

4

37销量

2

3

464第一百二十一页，共一百三十四页，编辑于2023年，星期三需求地化肥厂1234产量(万吨）11613221750214131915603192023M50最低需求量（万吨)3070010最高需求量（万吨)507030不限表1-36例5第一百二十二页，共一百三十四页，编辑于2023年，星期三

需求地化肥厂1234产量(万吨）11613221750214131915603192023M50最低需求量（万吨)3070010最高需求量（万吨)50703060例：因总产量为160，故4需求地最多分配60吨。第一百二十三页，共一百三十四页，编辑于2023年，星期三

需求地1234产量化肥厂IIIIII(万吨）116161322171750214141319151560