运筹学----运输问题的分解

资源库

第一节运输问题及其数学模型第二节运输问题第三节用表格工作法求解运输问题的进一步探讨第四节应用题例四节： 2021-10-26 23-1运输问题及其数学模型1、运输问题的数学模型

假设某物品有m个产地A1、A2、…、Am； 各产地产量分别为a1、a2、…、am； 有n个焦点B1、B2、…、Bn。 各销售地的销售额分别为b1、b2、…、bn； 假设从产地ai (I=1，2，…，m )到销售地BJ ) j=1，2，…，n )的运输单位物品的运输价格为cij。 如何运输这些物品才能使总运费降至最低？ 这个问题是多产地多销地的单品种物品运输问题。 把这个问题总结成一个表，叫做运费表。 (见下一页)返回第三章目录

2021-10-26 3表3-1运费表销售地

产地B1 B2 Bm产量A1 x11c11x12

c12 … x1nc1na1A2 x21c21

x22

c22 )…x2NC2na2)…

)…) ) )。

……

Am xm1cm1xm2

cm2 … xmncmnam销量b1 b2 bn

变量xij (I=1，2，m； j=1，2，…，n )是从产地Ai向销售地Bj发货的物品数量。===

最小

IjaB1==minj

据i ja b1 1

把产销平衡运输问题称为产销平衡运输问题2021-10-26 4产销平衡运输问题的数学模型

这是一个线性规划问题，可以用单纯形法求解。 但是，由于含有很多变量，所以求解非常不方便。 即使求解一个m=3，n=4的单纯运输问题，变量的数量也能达到19个。 因此，必须寻找更简单的解决方法。

=======

==

==

x i m j nx b j nx a i mz c xi jjmi

i jnj

i j iminj

i j i j

0； 1，2， 1，2， 1，2， 1，2，min

11

1 1

生产量约束、销售量约束、非负约束、总运输费极小化从某个产地运到各销售地的物品数量之和等于从该产地的产量、各产地运到某个销售地的物品数量之和等，该销售地的销售量非负条件

2021-10-26 5二、运输问题数学模型特点1 .运输问题有运输问题有限最优解的数学模型。 如果把变量分开的话，由于在运输问题的数学模型中目标函数取最小值，所以该值不会无限大，在实际问题中这种情况是不可能发生的。 因此，运输问题有有限最优解。 整理运输问题数学模型的约束条件，其系数矩阵的结构形式如下

i m j nQa bx

i ji j

=，=1，2，=1，2，其中，====

njjmii

Q a b1 1

是运输问题的可行解

2021-10-26 62 .运输问题约束条件的系数矩阵1111111111111111111121222122

nmmmnxxxxxxxxxxm行n行() t

Ai j=0，0，1，0，0，1，0，0I第“m j”个系数串向量的结构：

也就是说，除第I个和第(m )个成分为1以外的成分都等于0。 2021-10-26 7运输问题的特点：

(1)约束系数矩阵的元素等于0或1； )2)约束条件系数矩阵的各列有两个非零元素，对应各变量在最初的m个约束方程中出现一次，在接下来的n个约束方程中也出现一次。 如果是产销平衡运输问题，(3)所有结构约束条件都是等式约束； )4)各产地产量之和等于各销售地销售量之和。

例1将某物品存放在两个仓库A1和A2中，然后运送到三个使用地B1、B2、B3。 建立了其间运输距离(或单位运输价格)最小的运输问题数学模型，如表3-2小眼数据所示：总运输量)或总运输价格。 2021-10-26 8表3-2

大头针

产地B1 B2 B3产量A13 4 210

A2

3 5 34

销售额3 5 6

x11x12x13x21x22x23

=== = =

=，06534

10

min 3 4 2 3 5 3

1 1 1 2 1 3 2 1 2 2 2 31 3 2 31 2 2 21 1 2 1

2 1 2 2 2 31 1 1 2 1 3

11121322223 xxxxxxxxxxxxxxxxxxxx

x x xx x x

z x x x x x x解题思路：

(1)假设变量)分析制约)3)目标的明确化)4)模型的建立)5)变量的解决)6)分析方案)7)决定论66-6=010-6=43

4-3=13-3=011-1=05-1=444-4=04-4=00明显

x11=3、x12=1、x13=6、x22=4、x21=0、x23=0是该运输问题的可行解。 目标函数值z=452021-10-26 9

3-2用表格工作法求解运输问题

这是一种解决运输问题的简便有效的方法，其解决过程在运输表上进行，是一种迭代法，其步骤如下。 1 .首先按照某种计划进行初始解(初始运输方案)； 2 .对现行解进行最优性判别3 .如果不是最优解，用表对其进行调整和改进，得出新解；

4 .重新判别并改进，直到得到运输问题的最优解※在迭代过程中,得出的所有解都要求是运输问题的基可行解。

例2 某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售地出售，各工厂的生产量，各销售地的销售量（假定单位均为吨）以及各工厂到各销售地的单位运价（元/吨）示于表3-4中，要求研究产品如何调运才能使总运费最小？返回第三章目录

2021-10-26 10

一、确定运输问题的初始基可行解（初始调运方案）1. 最小元素法：销地

产地 B1 B2 B3 B4 产量A14 12 4 1116

A2

2 10 3 910A3

8 5 11 622

销量 8 14 12 14 488 2 102-2=0 -8=2 212-2=1010 16-10=610-10=03

14

14-14=022-14=848

8-8=014-8=656

6-6=0

8-8=0 6-6=061 6

该运输问题一个初始可行解为：

x13=10, x14=6, x21=8, x23=2, x32=14, x34=8.总运费＝ 4×10＋11 ×6＋2 ×8＋3×2＋5 ×14＋6 ×8 ＝ 2462021-10-26 11用西北角法确定运输问题的初始可行解销地

产地 B1 B2 B3 B4 产量A14 12 4 1116

A2

2 10 3 910A3

8 5 11 622

销量 8 14 12 14 482.西北角法8

8-8=01

16-8=8 8 8-8=014－8=626

6－6=010-6=434 4-4=012-4=848

8-8=0

22-8=14514 66

初始可行解为：x11=8 ,x12=8 ,x22=6 ,x23=4 ,x33=8 ,x34=14 .总运输费用 z＝8×4＋ 8×12＋ 6×10＋ 4×3＋ 8×11＋ 14×6＝3722021-10-26 12

用沃格尔法确定运输问题的初始可行解销地

产地 B1 B2 B3 B4 产量 行罚数1 2 3 4 5A1

4 12 4 11 16A22 10 3 910A3

8 5 11 622

销量 8 14 12 14 48列罚数12345011

2 5 1 314012

2 1 3801

2 1 2876

1 2

12 00224

3. 沃格尔法

该运输问题的可行解为：

x13=12 ,x14=4 ,x21=8 ,x24=2 ,x32=14 ,x34=8 ,其他变量等于0。

总运输费 z＝244080

0 62040400

2021-10-26 13确定初始可行解的三种方法比较最小元素法：z＝246西北角法：z＝372沃格尔法：z＝244沃格尔法解出的目标函数值最小，最小元素法次之，西北角法最大；一般说来，沃格尔法得出的解质量最好，在运输问题中，常用来作最优解的近似解。二、解的最优性检验

2021-10-26 141.最小元素法

解题思想：为了减少运费,应优先考虑单位运价最小(或运距最短)的供销业务,最大限度地满足其供销量。解题步骤：.

(1) , min( ), min( , )0 00 0 0 0 0 0i j

i j i j i j i jA Bi j c c x a b的物品量由 供应给对所有 和 找出 = 并将 =.(2) ,

0 0 0 00 0 0 0j j j ii j i iB b b ax a A−=

这个产地，且 的需求量 减少为若 则 的可供物品已用完，以后不再考虑.(3) ,

0 0 0 00 0 0 0i i i ji j j jA a a bx b B−=

不再考虑这个销地，且 的可供量由 减少为如果 则销地 的需求已全部得到满足，以后

(4) 在余下的供销点的供销关系中,继续安排调运,直到安排完成所有供销任务,得到一个完整的方案为止。确定初始基可行解（初始调运方案）2021-10-26 152.西北角法

解题思想:优先满足运输表中西北角(即左上角)上空格的供销量需求.解题步骤:

(1). 最先填xij= min(ai,bj),即( Ai,Bj)；(2). 若 xij= ai ，则 Ai 行不在考虑,且 Bj 列剩下 bj-ai 来填左上角其它空格.(3). 若 xij= bj ，则 Bj 列不再考虑,且 Ai 行剩下 ai-bj 来填左上角其它空格.

(4). 如此继续完成调运,最后得出一个初始方案。用西北角法确定运输问题的初始可行解2021-10-26 163. 沃格尔法

解题思想：

对于每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价,并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，若罚数的值很大，不按最小运价组织运输就会造成很大的损失；故应尽量按最小单位运价按排运输。解题步骤：（1）先计算运输表中每一行和每一列的罚数值，并称为行罚数和列罚数。（2）将行罚数填入位于运输表右侧行罚数栏的左边第一列的相应格子中；列罚数填入位于运输表下边列罚数栏的第一行的相应格子中。（3）找出该列和该行的列罚数和行罚数中的最大值；根据最大罚数值的位置在运输表中运价最小的格中填入一个尽可能大的运输量，并划去对应的一行或一列。（4）继续找其它列和行的列罚数和行罚数；找出其它运输量；已划去的不再找。直到最后按排完，即得到一个初始运输方案。用沃尔沃法确定运输问题的初始可行解2021-10-26 17二、解的最优性检验

得到了初始可行解后，应对其进行判别是否是最优解,常用方法有：闭回路法和对偶变量法。1.闭回路法

解题思想：对运输表中的解的各非基变量即某空格(Ai,Bj)进行检验;

高等职业学校

产地 B1 B2 B3 B4 产量A14 12 10 46

11 16A2 8

2 10 23 9 10A38

14 5 11 86 22

销量 8 14 12 14 4810 12-11

12

s11=c11-c21+c23-c14=4-2+3-4=1

s31=c31-c34+c14-c13+c23-c21=8-6+11-4+3-2=10s12=c12-c32+c34-c14=12-5+6-11=2

s22=c22-c32+c34-c14+c13-c23=10-5+6-11+4-3=1s33=c33-c34+c14-c13=11-6+11-4=12s24=c24-c14+c13-c23=9-11+4-3=-1由于s24＝−1＜0所以，上表中的解不是最优解。

2021-10-26 192.对偶变量法（位势法）:

解题思想：用u1,u2,…,um分别表示与前m个约束相对应的对偶变量，用v1,v2,…,vn分别表示与后n个约束相 对 应 的 对 偶 变 量 ， 即 对 偶 变 量 向 量 ：Y=(u1,u2,…,um,v1,v2,…,vn)将运输问题的数学模型写成对偶规划：==

+ 

 =  + = =i j的符号不限

i j i jminj

i i j ju vj ni m

u v C

Z a u b v,

1,2,...,1,2,...,max1 1

 = == →= →=



==

= =

x i m j nx b vx a uz c xi jj jm

i

i jinj

i j iminj

i j i j

0 ; 1,2,..., ; 1,2,...,min11

1 1

2021-10-26 20 ( )1

i j i j i j i j B j i j j i j i j= c − z = c −C B P = c −YP = c − u +v−s

经过整理得出运输问题变量xij的检验数为：==

+ 

 =  + = =i j的符号不限

i j i jminj

i i j ju vj ni m

u v C

Z a u b v,

1,2,...,1,2,...,max1 1

如果所有的sij≥0，则所求得的可行解是最优解，如果存在sij＜0，则所求得的可行解不是最优解，需要改进。2021-10-26 21



+ =+ =+ =

s s s si j i ji j i ji j i ju v cu v cu v c.....................2 2 2 2

1 1 1 1解题步骤：

(一）在运输表右边增加一位势列ui；在下边增加一位势行vj；(二）计算位势

(三）计算检验数： sij=cij-(ui+vj)由于基变量的检验数sij＝0，故对这组基变量可以写出方程组：这个方程组有（m+n-1)方程，（m+n）个变量，所以它的解不是唯一解。这个方程组的解称为位势。2021-10-26 22例3 用位势法对前例运输问题作最优性检验。销地

产地 B1 B2 B3 B4 产量 uiA14 12 10 46

11 16 u1A2 82 10 23 910 u2A38

14 5 11 8622 u3

销量 8 14 12 14 48vjv1v2v3v4

（1）在运价表上增加一位势列 ui 和位势行 vj ，（上表）（2）建立位势方程组，计算位势。10

-4

2 9 3 10

（3）计算检验数。sij＝cij－（ui+vj)1102

1

12-1

由于s24= -1＜0，所以上表得出的可行解不是最优解。需要改进

2021-10-26 23建立位势方程组，计算位势u2＝0 ， v1＝2v3＝3 ， u1＝1v4＝10 ，u3＝－4v2＝9

+ =+ =+ =+ =+ =+ =6532

114

3 43 22 32 11 41 3u vu vu vu vu vu v

任意指定某一位势等于一个较小的整数或零，如 u2＝0将计算结果填入运输表的位势列和位势行。2021-10-26 24三.解的改进1.改进原因

对运输问题来说,若某空格的检验数sij为负，说明将这个非基变量变为基变量时运费会减小，因而这个解不是最优解,还需要改进；2.改进方法

在运输表中，找出sij＜0的空格对应的闭回路Lij，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其它顶点的运输量,以得到另一个更好的基可行解。2021-10-26 253.改进步骤：

(1) 以xij为换入变量，找出它在运输表中的闭回路；(2) 以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺时针或逆时针方向前进，对闭回路上的顶点依次编号；(3) 在闭回路上的所有偶数顶点中，找出运输量最小(minxij)的顶点(格子)，以该格中的变量为换出变量；(4) 以min xij为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减少这一数值，从而得出一新的运输方案。该方案的总运费比原运输方案的总运费减少，改变量等于sij(min xij)。（5）对得到的新解进行最优性判别。重复上述步骤，直到得到最优解为止。2021-10-26 26

例 4 对例2用最小元素法得出的解进行改进（2）计算检验数，对解的最优性进行判断。销地产地 B1 B2 B3 B4 产量A1

4 121046

11 16A2 82 10 23 910A38

14 5 11 8622

销量 8 14 12 14 48（-2） （+2）（12+2） （4-2）1 2

122109

（1）因为s24＜0，所以，以此格 ——（A2，B4）为顶点寻找一个闭回路，进行解的改进。

∵sij≥0, ∴最优解为：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8z＝12×4＋4 ×11＋8×2＋2×9＋14×5＋8×6＝2442021-10-26 27四、需要说明的几个问题

1.若运输问题的某一基可行解中，有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取sij＜0中最小者对应的变量为换入变量。

2.当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重最优解。3.当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时，需同时划去运输表的一行和一列，即出现退化。退化是时有发生的，为使迭代进行下去，退化时在同时划去的一行或一列中的某个格中填入0，表示该格变量取值为0的基变量，使迭代过程中基可行解的分量恰好为( m + n –1 )个。2021-10-26 28§3-3 运输问题的进一步讨论一、产销不平衡的运输问题

解题思想：把产销不平衡的运输问题转化为产销平衡问题。

= = ==



 ==

= == =0

, 1,2,...,, 1,2,...,min1 .1

1

1 11 1i jmi

i j jnj

i j iminj

i j i jminj

i jx

x b j nx a i mz c xa b其数学模型为：

（）如果 时，即总产量大于总销量返回第三章目录2021-10-26 29

可假想一个销地Bn+1，其销量为bn+1，其实质没有运输，只是就地储藏。设调运假想销地的物品数量为xi,n+1；故其单位运价ci,n+1＝0;且

= = += ==

= −



 =+==+== =+0

, 1,2,..., 1, 1,2,...,min111111

1 11i jjmi

i jinj

i jminj

i j i jnjjmi

n ix

x b j nx a i mz c x

b a b ；则产销不平衡就变为产销平衡问题此式对应的运输表见下页。

2021-10-26 30产量大于销量的运输表销地

产地

B1 B2 … BnBn+1（储存） 产量A1 x11c11x12

c12 …… x1nc1nx1,n+10

a1

A2 x21c21x22

c22 …… x2nc2nx2,n+10

a2

┆ ┆

… ┆… ┆… ┆… ┆… ┆Am xm1cm1xm2

cm2 …

… xmncmnxm,n+10am

销量 b1 b2 … bn  = =−njjmi

aib1 12021

-10-26 31

( )2如果总销量大于总产量，则增加一个假想产地，它的产量等于总销量与总产量之差。销地

产地B1B2…B

n 产量A1

x11c11x12c12……x

1nc1na1A2

x21c21x22c22……x

2nc2na

2┆┆…┆…┆…┆…┆Amxm1

c

m1xm2c

m2……

xmncmnamA

m+1(假想产地）00…

…0销量b1b2

…bnx

m+1,1xm+1,2xm+1,n==−

miinjjba11

提升教学质量

B1 B3产地销地A2A1

B1 B2 B3产地销地

（a)无转运（a)包含转运

比较以上两图。显然，包含转运的运输问题复杂得多。2021-10-26 33

假定m个产地A1,A2,…,Am和n个销地B1,B2,…,Bn都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个。ai ：第i个产地的产量（净供应量）；bj ：第j个销地的销量（净需要量）；

xij ：第i个发送地运到第j个接收地的物品数量；cij ：由第i个发送地运到第j个接收地的单位运价；ti ：第i个地点转运物品的数量；ci ：第i个地点转运单位物品的费用；

则有：am+1=am+2=,…,am+n=0，b1=b2=,…,=bm=0a b Qm nj mj

mi

 i

=  =+

=1 = +1则

如为平衡运输问题，n个销地的净产量等于零。m个产地地的净销量等于零。

2021-10-26 34有转运的运输问题模型：

 = + = + + ++ + + + + + = +=+ + + + + + == + + ++ + + + + + ==+ + + + + + = += +− + +− + +− + +− + ++=+=+=

 

0, , 1,2,.., ( )1, 2,...,

... ...1,2,...,... ...1, 2,...,... ...1,2,...,... ...min1 2 1, 1, ,1 2 1, 1, ,1 2 , 1 , 1 ,1 2 , 1 , 1 ,1 1 1x i j m n i jj m m m n

x x x x x b tj m

x x x x x ti m m m nx x x x x ti mx x x x x a tz c x c t

i j

j j j j j j m n j j jj j j j j j m n j ji i i i i i i m n ii i i i i i i m n i im ni

i im ni jim nj iji j i j

由第i个产地发送到各个地方的物品数量之和，等于该产地的产量加上经它转运的物品数量。由第i个发送地发送到各个地方的物品数量之和，等于经它转运的物品数量。由各地运到第j地的物品数量之和，等于转运量。

由各地运到第j地的物品数量之和，等于净需要量加上转运量。令xii=Q-t

i或xjj=Q-tj ，则ti=Q-xii, tj

=Q-xjj经整理得：2021-10-26 35 = +

= + = + + += == = + + += + == +



 +

=+=+=+=+=+=+=x i j m n

x Q b j m m m nx Q j mx Q i m m m nx Q a i mz c x c Qi j

m ni

i j jm ni

i jm nji jm nji j im ni

m njm ni

i j i j i

0, , 1,2,...,, 1, 2,...,, 1,2,...,, 1, 2,...,, 1,2,...,min1111

1 1 1

注意：在上式中，对所有i＝j，cij＝－ci。由于目标函数中是常数,故不影响求最优解。

其对应的表如下有转运问题的运输表有转运问题的运价表

+=

m niciQ1

2021-10-26 36有转运问题的运输表接收发送

产 地 销 地发送量

1 … m m+1 … m+n产地

1 x11 … x1m x1,m+1 … x1,m+n Q+a1┆ ┆ … ┆ ┆ … ┆ ┆m xm1 … xmm xm,m+1 … xm,m+n Q+am销地

m+1 xm+1,1 … xm+1,m xm+1,m+1 … xm+1,m+n Q┆ ┆ … ┆ ┆ … ┆ ┆m+n xm+n,1 … xm+n,m xm+n,m+1 … xm+n,m+n Q接收量 Q … Q Q+bm+1 … Q+bm+n表3-17

2021-10-26 37有转运问题的运价表接收发送

产 地 销 地发送量

1 … m m+1 … m+n产地

1 -c1 … c1m c1,m+1 … c1,m+n Q+a1┆ ┆ … ┆ ┆ … ┆ ┆m cm1 … -cm cm,m+1 … cm,m+n Q+am销地

m+1 cm+1,1 … cm+1,m -cm+1 … cm+1,m+n Q┆ ┆ … ┆ ┆ … ┆ ┆m+n cm+n,1 … cm+n,m cm+n,m+1 … -cm+n Q接收量 Q … Q Q+bm+1 … Q+bm+n表3-18

2021-10-26 38

例6 有一个运输系统包括二个产地（①、②）、二个销地（④、⑤）及一个中间转运站（③），各产地的产量和各销地销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。解：

a1=10, a2=40, a3=a4=a5=0b1=b2=b3=0, b4=30, b5=20Q=10+40=30+20=50c1=4, c2=1, c3=3, c4=3, c5=51

2345105243402

145536305

3

20

以M表示足够大的正数，可得该问题的运输表3-192021-10-26 39表3-19接收

发送

产 地 转运 销 地发送量1 2 3 4 5产地1

-4 5 3 2 M602

5 -1 2 M 490转运 3

3 2 -3 5 550销地4

2 M 5 -3 6505

M 4 5 6 -550

接收量 50 50 50 80 70例6图2021-10-26 40表3-20接收发送

产 地 转运 销 地发送量1 2 3 4 5产地1 50

-4 5 3102 M60

2550

-1 220M

20490

转运 33 250-3 50

5

50销地4

2 M 550-3 6505

M 4 5 650-550

接收量 50 50 50 80 702021-10-26 41表3-21接收发送

产 地 转运 销 地发送量1 2 3 4 5产地1 50

-4 5 3102 M60

2550

-1 220M

20490

转运 33 250-30

5 550销地4

2 M 550-3 6505

M 4 5 650-550

接收量 50 50 50 80 702021-10-26 42表3-22接收发送

产 地 转运 销 地发送量1 2 3 4 5产地1 50

-4 5 3102 M60

25

50-1202 M204

90

转运 33 230-320

5 550销地4

2 M 550-3 6505

M 4 5 650-550

接收量 50 50 50 80 70Excel求解2021-10-26 43§3-4 运用问题举例

例题一：某公司承担4条航线的运输任务，已知：（1）各条航线的起点城市和终点城市及每天的航班数见表3-28；（2）各城市间的航行时间见表3-29；（3）所有航线都使用同一种船只，每次装船和卸船时间均为1天。问该公司至少应配备多少条船才能满足所有航线运输的需要？表3-28航线 起点城市 终点城市 每天航班数1 E D 3

2 B C 23 A F 14 D B 1表3-29 各城市间的航行时间返回第三章目录2021-10-26 44

表3-29 各城市间的航行时间（天）解：所需船只可分为两部分：

（1）各航线航行、装船、卸船所占用的船只，对各航线逐一分析，所需船只数列入表3-30中，累计共需91条船。至从

A B C D E FA 0 1 2 14 7 7B 1 0 3 13 8 8C 2 3 0 15 5 5D 14 13 15 0 17 20E 7 8 5 17 0 3F 7 8 5 20 3 0返回表3-282021-10-26 45

表3-30 各航线航行、装船、卸船所占用的船只（2）各港口之间调度所需船只数。这由每天到达港口的船只数与它所需发出的船只数不相等而产生。各港口城市每天到达船只数、需求船只数及其差额如表3-31中。航线 装船天数 卸船天数 航行天数 小 计 航班数 所需船只1 1 1 17 19 3 572 1 1 3 5 2 103 1 1 7 9 1 94 1 1 13 15 1 15

表3-31 各港口城市每天到达、需求及差额船只数城市 A B C D E F

每天到达 0 1 2 3 0 1每天需要 1 2 0 1 3 0余缺数 -1 -1 2 2 -3 1航线2021-10-26 46

将船由多余的港口调往需用船只的港口为空船行驶，应采用合理的调度方案，以使“调运量”最小。为此，建立表3-32所示的运输问题，其单位运价取为相应一对港口城市的航行时间(天数)。表3-32 船只调度运输表至

从

A B E 多余船只C2 3 52

D

14 13 17 2F7 8 31

缺少船只数 1 1 3

用表上作业法求解可得两个最优解：xCE=2,xDA=1,xDB=1,xFE=1 和xCA=1,xCE=1,xDB=1,xDE=1,xFE=1。按这两个方案调运多余船只，其目标函数值等于40；说明各港口之间调度所需船只至少为40艘。所以，在不考虑维修.储备等情况下，该公司至少要配备131条船，才能满足4条航线正常运输的需要。2021-10-26 47例题二：某企业和用户签定可供设备交货合同，已知该企业各季度的生产能力.每台设备的生产成本和每季度的交货量如表3-23，若生产出的设备当季度不交货，每台设备每季度需支付保管维护费0.1万元，试问在遵守合同的条件下，企业应如何安排生产计划，才能使年消耗费用最底？解：用xij表示第i季度生产第j季度交货的设备台数，由于生产能力的限制，需满足以下条件

表3-23季 度工厂生产能力

（台） 交货量（台） 每台设备生产成本（万元）1 25 15 12.0

2 35 20 11.03 30 25 11.54 20 20 12.52021-10-26 48第i季度生产第j季度交货的每台设备所消耗的费用cij，等于生产成本加上保管维护费用之和，如下表所示（3-24）

+ + + =+ + =+ ==

+ 

+ + 

+ + + 20

25201520303525

14 24 34 4413 23 3312 221144

33 34

22 23 24

11 12 13 14x x x xx x xx x

xx

x x

x x x

x x x x

根据合同规定，需满足

+ + + =+ + =+ ==

20252015

14 24 34 4413 23 3312 221144

x x x xx x xx xx

根据合同规定，需满足交货季j生产季i

1 2 3 4

1 12.0 12.1 12.2 12.32 11.0 11.1 11.23 11.5 11.64 12.5

2021-10-26 49

如用ai表示该企业第i季度的生产能力，bj表示第j季度的交货量，则可将这一问题转化成数学模型为：

= = ==

= =0

, 1,2,3,4, 1,2,3,4min41414141

i jji

i jij

i ji j

i j i jx

x b jx a iz c x

应该注意，在该问题中，当j＜i时应使xij=0。为实现这一要求，在该数学模型中，当j＜i时，取cij＝M，此处M为一充分大的正数。又因为它是产量大于销量的不平衡运输问题，为使其能够用表上作业法求解，应在运输表中增加一假想交货期d.经过整理，就变成一个产销平衡的运输问题，可得表3-25。最后可用表上作业法求解得出最后的方案，同学们自己去完成。2021-10-26 50表3-25 运 输 表交货季生产季 1 2 3 4 d 生产量1

12.0 12.1 12.2 12.3 0252

M 11.0 11.1 11.2 0353

M M 11.5 11.6 0304

M M M 12.5 020交货量 15 20 25 20 30