数学建模运输问题课件

运

输

问

题

模

型Transportation公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：B₁—3吨，

B₂—6吨，B₃—5吨，

B₄—6

吨。已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示，该食品公司应如何调运，在满足各门市部销售需要的情况下，

使总的运费支出为最少。一

.

问

题

的

提

出某

食

品

公

司

主

要

经

营

糖

果

。

它下面设有三个加工厂，每天的糖果生产量分别为：A₁—7

吨

，A₂—4

吨

，A₃—9

吨。门市部加

工B₁B₂B₃B₄A₁311310A₂1928A₃74105二

.

问

题

的

概

述在线性规划中研究这样一类问题：有某种物资需要调运，

这种物资的计量单位可以是重量，

包装单位或其他。地点可以供应该种物资(统称产地，用

i=1,.,m表示);有

n

个地点需要该种物资(统称销地，用j=1,..,n表示)。又知m

个产地的可供量(统称产量)为a₁,a₂,…a

(统写为a;);n

个销地的需要量(统称销量)为b₁

,b₂,…,b,,(统写为

b;)。从第

i个产地到第

j

个销地的单位物资运价为c。上面这些数据通常用产销平衡表和单位运价表来表示。有m

个已

知

：销地产地12●

●

●N产量1

2…a₁a₂:am销量b₁b₂·b,₁销地产地1

2

1

2·

·C11

C12-

·-

C1nC21

C22..-

C2nCm1

Cm2

...

Cm!T1●产销平衡表

单位运价表有时候把两个表写在一起：mM-销地产地12●●n产量1

Ma₁a₂:am销量b₁b₂·b,,销地产地122·

·

·C11

C12

…

C1nC21

C22

…C2n●●Cm1

Cm2

…CmN··2销地产地1

2

N产量1

2·

·C₁1

C₁2

…

C₁nC21

C22

…Czn:Cm1

Cm2

…Cmna₁a₂:am销

量b₁b₂…

b₂1:·Mm销

地产

地1

2

N产量2·

·C11

C12

…

C1nC₂1

C22

…C2n●·

●

●●

●

●Cml

Cm2

…Cmn…销

量b₁b₂…

b₁₂销

地产

地12

...

n产量X11

X12

…

X1nX₂1

X₂₂…X₂n●Xm₁Xm₂…Xmna₁a₂●am销

量b₁b₂

…

b₂min1m

nZnz&(1lo,mm方>西=-1,n三

.

运

输

问

题

模

型设

x;

代表从第

i个产地调运给

第

j

个销地的物资数量。在产销平衡的条件下，要求解

运输问题使总的运费支出最小，

则有如下的运输问题数学模型：12·

·

·)IMM1运输问题的数学模型包含m×n

个变量，(m+n)

个

约

束

条

件

。如果用单纯形法求解，先要在每个约束条件左端加上一个人工变量，因此即使象食品公司调运糖果这样简单的数学问题，变量数就有3×4+3+4=19个之多，计算起来非常繁杂。运输问题的数学模型结构比较特殊，它的约束条件变量的系数矩阵具有如下的形式：11n说

明

：销地产地1

2产量12…X11

X12··

X1nX₂1

X2₂

…X2n●a1a₂:n1Cm2

·

Cm'1

b₂

b,,产

销

不

平

衡

的

运

输

问

题1.

产大于销

1

)

数

学

模

型Xij

≤

a;(i

=1,

…

,m

)b;(j=1,…,n)X

ij≥

0X

ijj=1mi=1s.t.…●销地产地12

.

N

n+1产量12C11

C12

…

C1n

0C₂1C22

…

C2m

0a₁a₂IMCm1

Cm2··…Cmn·销量b₁b₂…

b,

库

存而在单位运价表中从各产地到假想销地的单位运价为C;n+i=O就转化为一个产销平衡的运输问题。

具体做法如下：2)求解方法：转化为产销平衡问题产大于销时，增加一个假想的销地

j=n+1

(库存),该销地的总需求量为0…●●··…销地产地1

2产量1X11

X12…

X₁na12X₂

1X₂2●…X₂na₂:MXmiXm₂…Xmnam销

量b₁b₂…b

a;(i

=1,…≤

b;(j=1,

…≥

02.销大于产1)数学模型(2a<之min

Z=2,

∑,m

),n)XijSij●……销

地产

地1

2

..

n产

量C11C21Cm10C12C22●Cm20…..C1n…C2n…Cmn0a₁a₂:am短

缺销

量b₁b₂…

b从假想产地到各销地的单位运价为Cm+1=O就转化为产销平衡的运输问题。具体做法如下：2

)

求

解

方

法

：

转

化

为

产

销

平

衡

问

题销大于产时，在产销平衡表中增加一个假想的产地

i=m+1,该地产量为在单位运价表中，12·

·

·mm+1··●应用实例设有A₁

、A₂

、A₃三个产地生产某种物资，产量分别为7、5、7吨，

B₁

、B₂

、B₃

、B₄四个销地需要该物资，销量分别为2、3、4、6吨。又知各产销地之间的单位运价见下表，试决定总运费最少的调运方案。解

：产地总产量为19吨，销地总销量为15吨，这是一个产大于销的运输问题。首先转化为产销平衡的运输问题，其产销平衡表和单位运价表分别见下两表。销地产地B₁B₂B₃B₄A₁21134A₂10359A₃7812销地

产地B₁B₂B₃

B₄

库存产量A₁A₂A₃23433225

7销量2

3

4

6

4销

地

产

地B₁B₂B₃

B₄A₁A₂A₃21071138351492A₁-7吨，A₂—5吨，A₃—7吨。B₁—2吨

，B₂—3吨，

B₃—4吨，

B₄—6吨。销地

产地B₁B₂B₃B₄

库

存产量销地产地B₁

B₂

B₃

B₄

库

存用表上作业法计算，求

得

最

优

调

运

方

案

为

：销量2

3

4

6

47A₁AA

3A₁A₂

A₃1138210700049235757销

地

产

地B₁BB₄产

量A₁A₂A₃X11X21X31X12X22X32X13X₂3X33X14X24X347

5

7销

量2

63销地产

地B₁B₂B₃B4A₁21134A₂10359A₃7812Globaloptimalsolution

found

at

iteration:8Objective

value:35.00000XXS.tXXXX十十

十

十

十

≥LINGO求

解十十

十

十

十十

二

二

二

二XXXXXX23463111121314jXXXXXi

=

1

j=133313233343221222324≤

7mmCX三34jj销地厂家B₁

’B₁

”

B₂B₃

B₄

’

B₄

”产量(万台)A₁A₂649M64903310M1291306IM10M6M10010121010销量6

4

14

6

5

7销地厂家B₁B₂B₃B₄产量(万台)A₁6312610A₂439

12A₃10131010最

低

需

求

(

万

台

)1405最

高

需

求

(

万

台

)1014612各地区的年销售量以及

各地区的单位运价如

右

表

，试求出总的运费最省的

电视机调拨方案。设有三个电视机厂供应四个地区某种型号的电视机。

各厂家的年产量、销

地厂家B₁

’

B₁

"

B₂

B₃

B₄

’

B₄

”产量(万台)A₁A₂A₃A104

4

42563410121010销量4

6

14

6

5

3+4Global

optimal

solution

found

at

iteration:

8Objective

value:

172.0000总运价：172元

Lingo求解销地厂家B₁

’

B₁

"

B₂B₃B₄

’

B₄

”产量(

万

台

)A₁A₂A₃A106

2

42

5

36

410121010销量6

4

14

6

5

3+4销地厂家B₁

B₂

B₃

B₄产量

(万台)A₁A₂A₃6493

12

63

9

—10

13

10101210最

便

需

求

(

瓦

台

)

+

最

高

需

求

(

万

台

)4x⁸+2x₂2⁰+20

个

P

R销地厂家12341X11

X12X13X142X₂1

X₂23X31

X32X33X

34X

0XGEP7号

1Lingo求解+1000x2₄+9x₃₁+10x₃₂+13x₃₂+10xmin

Z

二

6x

11

+35销地厂家B₁B₂B₃B₄产

量

(万台)A₁6312610A₂43912A₃910131010最

低

需

求

(

万

台

)61405最

高

需

求

(

万

台

)10146不

限销地厂

家B₁B₂B₃B₄产量

(万台)A₁1010A₂8412A₃2810最

低

需

求

(

万

台

)61405最

高

需

求

(

万

台

)10146不

限Globaloptimalsolution

found

at

iteration:16Objectivevalue:

172.0000中转调运问题1.已知甲、

乙两处分别有100吨和85吨同种物资外运，A

、B

、C

三处各需要物资55,

60,70吨。物资可以直接运到目的地，也可以经某些中转点转运。已知各处之间的单位运价如下表，试确定一个最优的调运方案。ABCA8C0108140121140ABC甲乙101514121218甲乙甲

乙010120销地产地甲乙ABC产量甲乙0101014121201512181015010814121401212181140185185130125115销量85100185185185甲乙ABC产量B

C8510055130851004525115185185130125115销量85100185185185ABC甲乙10151412121810085556070ABCA

BC0108140121140ABC甲

乙101514121218甲乙甲乙010120甲—A:55

吨，

甲—C

:45吨；乙—B60吨2

5

吨

—C用

Lingo

求

解甲乙AB

CAGlobaloptimalsolution

found

at

iteration:

3Objective

value:

2235.000Globaloptimalsolutionfoundatiteration:

10Objective

value:

2210.000ABC甲乙3025607010085556070ABC甲

乙10151412121810085556070进一步讨论：不考虑中转调运。用L

i

n

g

o求

解2.某食品公司主要经营糖果。它下面设有三个加工厂，每

天

的

糖

果

生

产

量

分

别

为

：A₁—7吨，A₂—4吨，

A₃—9吨。公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量分别为：B₁—3吨，

B₂—6吨

，B₃—5吨，

B₄—6吨。假

设

有

四

个

中

转

站

，每个加工厂生产的糖果在运往销地的过程中

可以在产地、中转站和销地之间转运。已知各产地、销地和中转站之间的单位运价如表所示，

试确定总运费最少的调运方案。门市部加

工B₁B₂B₃B₄A₁311310A₂1928A₃74105产

地中

转

地销

地A₁A₂A₃T₁T₂T₃T₄B₁B₂B₃B₄产地A₂A₃013103023115(43237119432101085中转站T₁T₂T₃T₄3-2-

23013210113102乙

118销地B₁B₂B₃B₄311310810568622

14

乙2

121N

N0117193010032035583124-8241124224244-71AN44962577(销

地

产

地A₁A₂A₃T₁T₂T₃T₄B₁B₂B₃B₄产量A₁A₂A₃013103031

5)-

23233

1119432101085202020T₂T₃T₄42(

)1321①131022120415826

720202020B₁B₂B₃B₄31131019281052862

7821262102103乙

117141514销

量1316112020202020202020A₁—7

吨，

A,

4吨，A₃—9吨

B₁—3吨

，B₂—6

吨

，B₃—5

吨，

B₄—6

吨总产量：20吨

用Lingo

求

解

总销量：20吨4

23063585424412401412-1-4442212377113Globaloptimalsolutionfoundatiteration:41Objectivevalue:

68.00000Variable

Value

Reduced

CostVOLUME(WH1,C1)

13.00000

0.000000VOLUME(WH1,C2)

7.000000

0.000000VOLUME(WH2,C2)9.000000

0.000000VOLUME(WH2,C8)11.00000

0.000000VOLUME(WH3,C3)11.00000

0.000000VOLUME(WH3,C6)

9.000000

0.000000VOLUME(WH4,C4)

20.00000

0.000000VOLUME(WH5,C5)20.00000

0.000000VOLUME(WH6,C6)

11.00000

0.000000VOLUME(WH6,C8)4.000000

0.000000VOLUME(WH6,C10)

5.000000

0.000000VOLUME(WH7,C7)

20.00000

0.000000VOLUME(WH8,C8)

5.000000

0.000000VOLUME(WH8,C9)

6.000000

0.000000VOLUME(WH8,C11)

6.000000

0.000000VOLUME(WH9,C9)

14.00000

0.000000VOLUME(WH10,C10)

15.00000

0.000000VOLUME(WH11,C11)14.00000

0.000000销地

产地A₁A₂A₃T₁T₂T₃T₄B₁B₂B₃B₄产量A₁A₂A₃13137

93113543233117119432101085202020T₁T₂T₃T₄335221203112乙

11552674620202020B₁B₂B₃B₄3113101928105878

264

26141536131417141514销量1316112020202020202020Globaloptimalsolutionfoundatiteration:41

Objective

value:

68.00000直接调运：85元2013

22204

6N

A219588142812211141142422311-----44271销

地

产

地A₁A₂A₃T₁T₂T₃T₄B₁B₂B₃B₄A₁A₂A₃137

911911T₁T₂T₃T₄2020112045B₁B₂B₃B₄861415614B₁—

3吨，B₂—

6吨，B₃—

5吨，B₄—

6吨(6)(6)A₁—

7吨，A₂—

4吨，A₃—

9吨(9

5)(4+7)(7(设备生产计划)某公司