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

数学建模运输问题附源代码第1页，课件共134页，创作于2023年2月3-1运输问题问题的提出

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

运往Bj

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

运往Bj

货物的运量为Xij。问如何调配，才能使运费最省？第2页，课件共134页，创作于2023年2月

当发点的发量总和为

ai，收点的收量总和为

bj相等时，称此运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。若没有特别说明，均假定运输问题为平衡的运输问题。第3页，课件共134页，创作于2023年2月销地产地12…

m12…n销量产量a1a2am

…

b1b2…bn

c21c22…c2ncm1cm2…cmnc11c12…c1n

…

cij

为运价第4页，课件共134页，创作于2023年2月销地产地12…

m销量产量a1a2am

…

x21x22…x2nxm1xm2…xmn

x11x12…x1n

…

xij

为运量b1b2…bn12…n第5页，课件共134页，创作于2023年2月运输问题的数学模型：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)第6页，课件共134页，创作于2023年2月运输问题数学模型系数阵为：第7页，课件共134页，创作于2023年2月且共有m+n个约束方程。并成立：所以模型最多只有m+n-1个独立约束方程,系数矩阵的秩≤m+n-1第8页，课件共134页，创作于2023年2月运输问题的图表形式第9页，课件共134页，创作于2023年2月运输问题解的结构

由于

ai=bj成立

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

（2吨）B1已经满足，划去b1列，并将a1=4-2=2第12页，课件共134页，创作于2023年2月（2）向a1，b1较大方向移动一格（或向右，或向下）此时向右移动一格（A1，B2）B2需要4吨，而A1只有2吨，A1已发完，划去A1行，并把b2改成（4-2）=2。第13页，课件共134页，创作于2023年2月（3）继续进行第14页，课件共134页，创作于2023年2月（4）继续进行第15页，课件共134页，创作于2023年2月（5）继续进行第16页，课件共134页，创作于2023年2月（6）继续进行第17页，课件共134页，创作于2023年2月（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（元）第18页，课件共134页，创作于2023年2月2最小元素法第19页，课件共134页，创作于2023年2月（1）从最小元素开始（3）即A1优先满足B33个单位，B3已经满足，划去B3列，第20页，课件共134页，创作于2023年2月（2）再从最小元素开始（4）即A1优先满足B41个单位，A1已经满足，划去A1行，第21页，课件共134页，创作于2023年2月（3）再从最小元素开始（4）即A2优先满足B12个单位，B1已经满足，划去B1列，第22页，课件共134页，创作于2023年2月（4）再从最小元素开始（4）即A2优先满足B24个单位，B2A2已经满足，划去B2列A2

行。第23页，课件共134页，创作于2023年2月（4）最后把A3满足B43个单位，得到初始方案。。第24页，课件共134页，创作于2023年2月（5）得到初始方案：X13=3，X14=1，X21=2，X22=4，X32=0，X34=3总运费=3*3+4*1+4*2+4*4+8*3=61（元）第25页，课件共134页，创作于2023年2月3.差值法（伏格法）

每次从当前运价表上，计算各行各列中两个(最小与次小）运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案。第26页，课件共134页，创作于2023年2月第27页，课件共134页，创作于2023年2月第28页，课件共134页，创作于2023年2月第29页，课件共134页，创作于2023年2月第30页，课件共134页，创作于2023年2月第31页，课件共134页，创作于2023年2月第32页，课件共134页，创作于2023年2月第33页，课件共134页，创作于2023年2月第34页，课件共134页，创作于2023年2月第35页，课件共134页，创作于2023年2月差值法初始方案如下：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（元）第36页，课件共134页，创作于2023年2月西北角法得到初始方案：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（元）第37页，课件共134页，创作于2023年2月最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3总运费=3*3+4*1+4*2+4*4+8*3=61（元）第38页，课件共134页，创作于2023年2月西北角法得到初始方案：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（元）第39页，课件共134页，创作于2023年2月例：分别用西北角法、最小元素和伏格尔法求产销平衡运输问题的初始基可行解

第40页，课件共134页，创作于2023年2月解（1）西北角法

Z=399第41页，课件共134页，创作于2023年2月（2）最小元素

Z=240第42页，课件共134页，创作于2023年2月（3）伏格尔法

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

第45页，课件共134页，创作于2023年2月如下表：第46页，课件共134页，创作于2023年2月如下表：第47页，课件共134页，创作于2023年2月如下表：第48页，课件共134页，创作于2023年2月第49页，课件共134页，创作于2023年2月第50页，课件共134页，创作于2023年2月第51页，课件共134页，创作于2023年2月第52页，课件共134页，创作于2023年2月第53页，课件共134页，创作于2023年2月第54页，课件共134页，创作于2023年2月第55页，课件共134页，创作于2023年2月第56页，课件共134页，创作于2023年2月第57页，课件共134页，创作于2023年2月第58页，课件共134页，创作于2023年2月第59页，课件共134页，创作于2023年2月第60页，课件共134页，创作于2023年2月求检验数

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

空格Xij的检验数=（第奇数次拐角点运价之和减去第偶数次拐角点运价之和）第62页，课件共134页，创作于2023年2月空格X21的检验数=4-6+5-4=-1B1B2B3B4产量A16

05

03

4

4A24

-1

4

07

05

06A37658

03销量

2

4

3

4第63页，课件共134页，创作于2023年2月空格X14的检验数=4-5+4-5=-2B1B2B3B4产量A16

05

03

4

4A24

-1

4

0705

06A37658

03销量

2

4

3

4第64页，课件共134页，创作于2023年2月空格X31的检验数=7-6+5-4+5-8=-1B1B2B3B4产量A16

05

03

4

-24A24

-14

07

05

06A37658

03销量

2

4

3

4第65页，课件共134页，创作于2023年2月检验数都为负值，原方案不是最优解B1B2B3B4产量A16

05

03

-54

-2

4A24

-14

07

05

06A37

-16

-15

-58

03销量

2

4

3

4第66页，课件共134页，创作于2023年2月（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.第67页，课件共134页，创作于2023年2月（2）位势法对初始调运方案，定义一组新的变量（对偶）ui和vj(i=1,2,…m;j=1,2,…n)对于基变量Xij有：ui+vj=Cij称ui与vj为相应的各行与各列的位势。对于非基变量Xij有：=cij-CBB-Pij=cij-（ui+vj）第68页，课件共134页，创作于2023年2月例：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第69页，课件共134页，创作于2023年2月调整方案从一个方案调整到最优方案的过程，就是单纯形法的过程。选择检验数（一般取最小）为负值的空格所对应的变量为进基变量，在进基变量的回路中，比较含（-1）拐角点的运量，选择一个具有最小运量的基变量作为出基变量，并调整运量=min(含（-1）的运量)第70页，课件共134页，创作于2023年2月选择（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第71页，课件共134页，创作于2023年2月B1B2B3B4产量A16

25

3

24

4A24

4

47

15

16A37658

33销量

2

4

3

4第72页，课件共134页，创作于2023年2月最小运量=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第73页，课件共134页，创作于2023年2月继续求检验数。B1B2B3B4uiA16

05

5

3

04

3

0A24

-64

07

05

04A37

-66

-15

-58

07vj

6

0

3

1第74页，课件共134页，创作于2023年2月继续调整运量。B1B2B3B4产量A16

2（-1）5

3

2（+1）4

4A24

（+1）

4

47

1（-1）5

16A37658

33销量

2

4

3

4第75页，课件共134页，创作于2023年2月继续调整运量。最小运量=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第76页，课件共134页，创作于2023年2月继续计算检验数。B1B2B3B4uiA16

05

-1

3

04

-3

0A24

04

07

6

5

0-2A37

06

-15

18

01vj

6

6

3

7

第77页，课件共134页，创作于2023年2月继续调整运量。最小运量=1B1B2B3B4产量A16

15

3

34

4A24

1

4

47

5

16A37658

33销量

2

4

3

4第78页，课件共134页，创作于2023年2月得到新的调运方案，总运费=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第79页，课件共134页，创作于2023年2月继续计算检验数B1B2B3B4uiA16

65

5

3

04

0

0A24

04

07

3

5

01A37

06

25

-28

04vj

0

0

3

4

第80页，课件共134页，创作于2023年2月B1B2B3B4产量A16

5

3

34

1

4A24

2

4

47

5

06A37658

33销量

2

4

3

4继续调整运量。最小运量=3第81页，课件共134页，创作于2023年2月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（元）第82页，课件共134页，创作于2023年2月计算检验数：空格的检验数全为非负，此时是最优解。最优调运方案：X21=2，X22=4，X14=4，X33=3。最小运费55（元）。第83页，课件共134页，创作于2023年2月例2：产销平衡表为：

销地产地B1B2B3B4产量A13

11

3

10

7A21

9

2

8

4A374105

9销量

3

6

5

6第84页，课件共134页，创作于2023年2月

销地产地B1B2B3B4产量A13

11

3

4

10

3

7A21

39

2

18

4A374

6105

39销量

3

6

5

6（1）用最小元素法求初始基可行解表（1）第85页，课件共134页，创作于2023年2月

销地产地B1B2B3B4uiA13

111

23

0

10

0

0A21

09

12

08

-1-1A37104

010

125

0-5vj

2

9

3

10（2）用位势法求检验数表（2）第86页，课件共134页，创作于2023年2月（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）第87页，课件共134页，创作于2023年2月

销地产地B1B2B3B4产量A13

11

3

5

10

2

7A21

39

2

8

1

4A374

6105

39销量

3

6

5

6（3）用闭回路调节得表（4）第88页，课件共134页，创作于2023年2月（2）用位势法再求表（4）的检验数

销地产地B1B2B3B4uiA13

011

23

0

10

0

0A21

09

22

18

0-2A3794

010

125

0-5vj

3

9

3

10表（5）非基变量，有无穷多最优解第89页，课件共134页，创作于2023年2月表（5）中空格的检验数全为非负，此时是最优解。最优调运方案为表（4），最小费用为85元。

销地产地B1B2B3B4产量A13

11

3

5

10

2

7A21

39

2

8

1

4A374

6105

39销量

3

6

5

6第90页，课件共134页，创作于2023年2月

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

11

3

5

10（-1）

2

7A21（-1）

39

2

8（+1）

1

4A374

6105

39销量

3

6

5

6第91页，课件共134页，创作于2023年2月

销地产地B1B2B3B4产量A13

211

3

5

10

7A21

19

2

8

3

4A374

6105

39销量

3

6

5

6为另一最优解第92页，课件共134页，创作于2023年2月例3

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

10

63633523

7586922534865585154744747440销量25201025101510第95页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

63633523

758692102534865585154744747440销量25201025101510第96页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6310633523

758692102534865585154744747440销量25201025101510第97页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6310633523

15758692102534865585154744747440销量25201025101510第98页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6310633523

15758692

10253410865585154744747440销量25201025101510第99页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6310633523

157586921025341086558515474

204747440销量25201025101510第100页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6310633523

1575869210253410865

558515474

204747440销量25201025101510第101页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6

1575869210253410865

558515474204747440销量25201025101510第102页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6

1575869210253410865

5585154742047547440销量25201025101510第103页，课件共134页，创作于2023年2月销地产地1234567产量1652

10

6

153106335231575869210253410865

5585154742047547

15440销量25201025101510第104页，课件共134页，创作于2023年2月销地产地1234567产量1

10

15

10352

15

10253

10

5154

20

5

1540销量25201025101510用最小元素法得初始基可行解为：表（1）第105页，课件共134页，创作于2023年2月用位势法计算检验数。销地产地1234567

ui1652

0

603063023

07586920-234

0865

0585-1474047047

041vj5326364第106页，课件共134页，创作于2023年2月销地产地1234567

ui16

1522

0

6030603-1023

0765584659520-234

086655

0538352-1471404170407

04-11vj5326364检验数为：检验数0，故表（1）不是最优解＜第107页，课件共134页，创作于2023年2月闭回路调节销地产地1234567产量1

10

15-1

10

+1352

15+1

10-125310-1

5+1154

20

5

1540销量25201025101510第108页，课件共134页，创作于2023年2月销地产地1234567产量1

10

5

1010

352

25

0253

15154

20

5

1540销量25201025101510闭回路调节为：表（2）第109页，课件共134页，创作于2023年2月再用位势法计算表（2）检验数。销地产地1234567

ui16

2522

0

60306030023

0745483649420-134

186655

0538353-1472404170407

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

m销量产量a1a2am

…

c21c22…c2ncm1cm2…cmnc11c12…c1n

…

12…nn+1000b1b2…bnbn+1

产大于销第114页，课件共134页，创作于2023年2月产小于销销地产地12…

m销量产量a1a2am

…

c21c22…c2ncm1cm2…cmnc11c12…c1n

…

12…nb1b2…bn

m+100…0am+1第115页，课件共134页，创作于2023年2月

销地产地B1B2B3B4产量A12

11

3

4

7A210

3

5

9

5A37812

7销量

2

3

46

1915例4：运输问题产销表为：第116页，课件共134页，创作于2023年2月例4：产销平衡表为：

销地产地B1B2B3B4B5产量A12

11

3

40

7A210

3

5

90

5A378120

7销量

2

3

464第117页，课件共134页，创作于2023年2月（1）用vogel求初始基可行解

销地产地B1B2B3B4B5产量A12

211

3

40

3

27A210

3

3

5

90

25A3781

4

20

3

7销量

2

3

464第118页，课件共134页，创作于2023年2月

销地产地B1B2B3B4B5产量A1

2

327A2

3

25A3

4

37销量

2

3

464初始基可行解为第119页，课件共134页，创作于2023年2月

销地产地B1B2B3B4B5uiA1

2

011

83

040

000A210

83

05

290

5

00A37

78

71

020

0

2-2vj

2

3

340（2）用位势法求检验数，第120页，课件共134页，创作于2023年2月检验数均为非负，故初始基可行解即为最优解，如下：

销地产地B1B2B3B4B5产量A1

2

327A2

3

25A3

4

37销量

2

3

464第121页，课件共134页，创作于2023年2月需求地化肥厂1234产量(万吨）11613221750214131915603192023M50最低需求量（万吨)3070010最高需求量（万吨)507030不限表1-36例5第122页，课件共134页，创作于2023年2月

需求地化肥厂1234产量(万吨）11613221750214131915603192023M50最低需求量（万吨)3070010最高需求量（万吨)50703060例：因总产量为160，故4需求地最多分配60吨。第123页，课件共134页，创作于2023年2月

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