运筹学第四章运输问题

第四章 运输问题

主要内容：1、运输问题及其数学模型； 2、表上作业法；

3、运输问题的进一步讨论。

重点与难点：表上作业法的原理、求解步骤，产销不平衡运输问题的求解方法。

要 求：理解运输问题的基本概念及表上作业法的原理，掌握表上作业法确定初始可行解、最优解的判别与改进的方法。

§1 运输问题及其数学模型

一、运输问题

引例，设有m个生产地

Ai

，可供应（产量）分别为

ai,i1,2,,m

;有n个销地

Bj,

其需

要量分别为

bj,j1,2,,n

。已知从

Ai到Bj运输单位物资的运价（单价）为cij

，试问如何调运

物资才能使总费用最小？

设用

xij

表示从

Ai到Bj的运量，可将这些数据汇总于下表：

产销平衡表

单价运价表

注：有时将两表合二为一。

m

n

i

m

（1）若各产地的总产量等于各销地的总销量，即运输问题）；

a

i1



b

j1

n

i

j，则称之为产销平衡的运输问题（或平衡

（2）若所有产地的总产量不等于所有销地的总销量，即不平衡的运输问题）；

a

i1



b

j1

j

，则称之为产销不平衡的运输问题（或

（3）若在运输途中，还存在中间转运点（转运点即是产地，又是销地），则称之为有转运的运输问题（或扩大的运输问题）。

二、平衡运输问题的数学模型

在产销平衡的条件下，要求得总运费最小，可建立以下数学模型：

m

n

ij

minz

c

i1

j1

xij

m

xijbj,j1,2,,ni1n

xijaii1,2,,mj1

x0ij

该运输问题也属于线性规划问题，包括： （1）

mn个决策变量；

n

i

（2）m+n个约束条件；

m

由于有

a

i1



b

j1

j，所以模型只有m+n–1个独立约束条件，基变量中含有m+n–1个变量；

（3）系数矩阵的秩

rank(A)mn1

（4）系数矩阵为

(mn)mn阶矩阵，该系数矩阵中对应于变量

x121



x1n1

1

1



1



1

1

1



1

1



1

1

x21

x22



x2n



xm1

xij

xm2

的系数向量

Pij

，其分量中除

第i个和第m+j个为1以外，其余的都为零。

x111A

1

xmn



1







1

1

1

§2 表上作业法

求解步骤：

（1）找出初始可行解，即在

mn产销平衡表上给出mn1个数字格；

（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解，如已是最优解，则停止计算； （3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整； （4）重复（2）、（3）直至得到最优解为止。 例1 某公司有

A1、A2、A3三个工厂生产一种产品，每日的产量分别为7T、4T、9T。该公司把这些产品

运往四个销点，各销点的日销量为

B1--3T、B2--6T、B3--5T、B4--6T。已知从各工厂到各销售点的单位产品

的运价见下表。问该公司应如何调运产品，在满足各销点需要量的前提下，使总运费最少？

单位运价表 单位：元/T

（二） （一）最小元素法

思路：就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，直到给出初始基可行解为止。 以例1为例进行讨论：

第一步：从单位运价表中找出最小运价为1，表示先将

A2的产品供应给B1。因a2b1，A2除满足B1

全部需要外，还多余1T产品。在

A2与B1的交叉格处填上3，并将B1列的运价划去。

第二步：在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并将A2行的运价划去。

第三步：在未划去的元素中划出最小运价3，直到单位运价表上的所有元素都划去为止，最后在产销平衡表上得到一个调运方案，空格为非基变量。

单位运价表 单位：T

产销平衡表 单位：T

注意：

（1）在用最小元素法确定初始方案时，在产销平衡表上每填一个数，在单位运价表上划去一行或一列（当产大于销时；划去元素所在列；当产小于销时，划去元素所在行）。运价表中有m行和n列，需要划m+n条线，填最后一个数划去一行和一列，这样共填上mn1个数。

（2）当在产销平衡表上填上某个数时，行和列都平衡，需在单位运价表上划去一行和一列（这就出现了退化问题），为保持mn1个基变量，需在行或列的任一空格处填上零，表示该基变量取值为零。

（二）伏格尔法

思路：一产地的产品，假如不能按最小运费就近供应，就考虑次小运费，这样就要有一差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就采用最小运费调运。

第一步：计算各行和各列的最小运费和次小运费的差额

第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素，在上表中，B2列是最大差额所在列，

B2列中最小元素为4，可确定A3的产品先供应B2的需要，同时将运价表中的B2列数字划去。

单位运价表

产销平衡表

第三步：对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第一、二步，直到给出初始解为止。最后结果见下表。

产销平衡表

注意：

（1）伏格尔法与最小元素法除确定供求关系的原则不同外，其余相同； （2）伏格尔法给出的初始解更接近最优解。

二、最优解的判别

判别方法：计算空格检验数下面介绍两种求空格检验数的方法：

（一）闭回路法

在给出调运方案的表上，从每一空格出发找一条闭回路。它是以某一空格为起点。用水平或垂直线向前划，每碰到一数字格转90度后，继续前进，直到回到开始空格为止。

对用最小元素法确定的方案：

ij

cijcBB

1

pij

，当

ij0时，为最优解。

x11x13x23x21x11x12x14x34x32x12

x22x23x13x14x34x32x22

11c11c13c23c21112c12c14c34c322

2224

c22c23c13c14c34c321c24c14c13c231

31c31c34c14c13c23c211033c33c34c14c1312

240



不是最优解，需要调整。

（二）位势法（对偶变量法）

设

u1,u2,,um;v1,v2,,vn

是对应运输问题的对偶变量，其中

ui

--行位势，

vj--列位势。

检验数

ijcij(uivj)

所有基变量的检验数ij0

cij(uivj)0 即uiv

由此求出

第一步：在按最小元素法给出的初始解的数字处填入单位运价

j

cij

ui,vj，再计算

ij。

u,vij。 第二步：在表上增加一行一列，填入

对基变量有

u1u1u2u2u3u3

v33

u2

v410u3

v11v1



v32v2

令u10得

vv243v45v4

ij

1529310

第三步：计算空格的



ijcij(uivj)

可直接在表上进行

三、调整----闭回路法

当



ij

路，确定调整量

(min(1,3)1)（其原理与单纯形法中按

检验表：

规则确定换出变量相同），然后，按闭回

路上的正、负号，加入或减去此值，得到新的调运方案。

新调运方案：

对上表求空格的检验数，见上表。 因为所有



ij>0，所以此解为最优解，总费用的最小值z=85

ij0，且有某一个ij=0，则此问题有无穷多最优解，

（两个最优解X1

的组合X1(1)X2，也一定是最优解）。

（1）若对某方案所有

基变量，其值为0；若有某个有“-”标记的数为0，调整量为零，把此格作为空格，原空格处填入零。

如：

§3 产销不平衡问题

m

注意：

,X2

（2）在用闭回路法调整时，若有两个具有“-”标记的数同时为最小值，把其中一个作为调出变量，另一个仍为

调整后变为 调整后变为 1、若产大于销

i1

m

aaibj，需增加一个假想的销地，各产地到此的运价都为零，该地的销量为i

j1i1

n

m

n

i



b j。j1

n

2、若产小于销

a

i1



b

j1

j

，需增加一个假想的产地，由此到各销地的运价都为零，该地的产量为

n

bjj1

m



i1

ai。 

例2 设有三个化肥厂供应四个地区同一种化肥，其产、销量和运价如下表，试求出总的运费最节省的化肥调拨方案。

运价单位：万元/万吨

解：

产销平衡表和单位运价表：

初始调拨方案：

判别：计算空格ij。 最优方案：

第四章 运输问题 第48页

第四章 运输问题

主要内容：1、运输问题及其数学模型； 2、表上作业法；

3、运输问题的进一步讨论。

重点与难点：表上作业法的原理、求解步骤，产销不平衡运输问题的求解方法。

要 求：理解运输问题的基本概念及表上作业法的原理，掌握表上作业法确定初始可行解、最优解的判别与改进的方法。

§1 运输问题及其数学模型

一、运输问题

引例，设有m个生产地

Ai

，可供应（产量）分别为

ai,i1,2,,m

;有n个销地

Bj,

其需

要量分别为

bj,j1,2,,n

。已知从

Ai到Bj运输单位物资的运价（单价）为cij

，试问如何调运

物资才能使总费用最小？

设用

xij

表示从

Ai到Bj的运量，可将这些数据汇总于下表：

产销平衡表

单价运价表

注：有时将两表合二为一。

m

n

i

m

（1）若各产地的总产量等于各销地的总销量，即运输问题）；

a

i1



b

j1

n

i

j，则称之为产销平衡的运输问题（或平衡

（2）若所有产地的总产量不等于所有销地的总销量，即不平衡的运输问题）；

a

i1



b

j1

j

，则称之为产销不平衡的运输问题（或

（3）若在运输途中，还存在中间转运点（转运点即是产地，又是销地），则称之为有转运的运输问题（或扩大的运输问题）。

二、平衡运输问题的数学模型

在产销平衡的条件下，要求得总运费最小，可建立以下数学模型：

m

n

ij

minz

c

i1

j1

xij

m

xijbj,j1,2,,ni1n

xijaii1,2,,mj1

x0ij

该运输问题也属于线性规划问题，包括： （1）

mn个决策变量；

n

i

（2）m+n个约束条件；

m

由于有

a

i1



b

j1

j，所以模型只有m+n–1个独立约束条件，基变量中含有m+n–1个变量；

（3）系数矩阵的秩

rank(A)mn1

（4）系数矩阵为

(mn)mn阶矩阵，该系数矩阵中对应于变量

x121



x1n1

1

1



1



1

1

1



1

1



1

1

x21

x22



x2n



xm1

xij

xm2

的系数向量

Pij

，其分量中除

第i个和第m+j个为1以外，其余的都为零。

x111A

1

xmn



1







1

1

1

§2 表上作业法

求解步骤：

（1）找出初始可行解，即在

mn产销平衡表上给出mn1个数字格；

（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解，如已是最优解，则停止计算； （3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整； （4）重复（2）、（3）直至得到最优解为止。 例1 某公司有

A1、A2、A3三个工厂生产一种产品，每日的产量分别为7T、4T、9T。该公司把这些产品

运往四个销点，各销点的日销量为

B1--3T、B2--6T、B3--5T、B4--6T。已知从各工厂到各销售点的单位产品

的运价见下表。问该公司应如何调运产品，在满足各销点需要量的前提下，使总运费最少？

单位运价表 单位：元/T

（二） （一）最小元素法

思路：就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，直到给出初始基可行解为止。 以例1为例进行讨论：

第一步：从单位运价表中找出最小运价为1，表示先将

A2的产品供应给B1。因a2b1，A2除满足B1

全部需要外，还多余1T产品。在

A2与B1的交叉格处填上3，并将B1列的运价划去。

第二步：在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并将A2行的运价划去。

第三步：在未划去的元素中划出最小运价3，直到单位运价表上的所有元素都划去为止，最后在产销平衡表上得到一个调运方案，空格为非基变量。

单位运价表 单位：T

产销平衡表 单位：T

注意：

（1）在用最小元素法确定初始方案时，在产销平衡表上每填一个数，在单位运价表上划去一行或一列（当产大于销时；划去元素所在列；当产小于销时，划去元素所在行）。运价表中有m行和n列，需要划m+n条线，填最后一个数划去一行和一列，这样共填上mn1个数。

（2）当在产销平衡表上填上某个数时，行和列都平衡，需在单位运价表上划去一行和一列（这就出现了退化问题），为保持mn1个基变量，需在行或列的任一空格处填上零，表示该基变量取值为零。

（二）伏格尔法

思路：一产地的产品，假如不能按最小运费就近供应，就考虑次小运费，这样就要有一差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就采用最小运费调运。

第一步：计算各行和各列的最小运费和次小运费的差额

第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素，在上表中，B2列是最大差额所在列，

B2列中最小元素为4，可确定A3的产品先供应B2的需要，同时将运价表中的B2列数字划去。

单位运价表

产销平衡表

第三步：对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第一、二步，直到给出初始解为止。最后结果见下表。

产销平衡表

注意：

（1）伏格尔法与最小元素法除确定供求关系的原则不同外，其余相同； （2）伏格尔法给出的初始解更接近最优解。

二、最优解的判别

判别方法：计算空格检验数下面介绍两种求空格检验数的方法：

（一）闭回路法

在给出调运方案的表上，从每一空格出发找一条闭回路。它是以某一空格为起点。用水平或垂直线向前划，每碰到一数字格转90度后，继续前进，直到回到开始空格为止。

对用最小元素法确定的方案：

ij

cijcBB

1

pij

，当

ij0时，为最优解。

x11x13x23x21x11x12x14x34x32x12

x22x23x13x14x34x32x22

11c11c13c23c21112c12c14c34c322

2224

c22c23c13c14c34c321c24c14c13c231

31c31c34c14c13c23c211033c33c34c14c1312

240



不是最优解，需要调整。

（二）位势法（对偶变量法）

设

u1,u2,,um;v1,v2,,vn

是对应运输问题的对偶变量，其中

ui

--行位势，

vj--列位势。

检验数

ijcij(uivj)

所有基变量的检验数ij0

cij(uivj)0 即uiv

由此求出

第一步：在按最小元素法给出的初始解的数字处填入单位运价

j

cij

ui,vj，再计算

ij。

u,vij。 第二步：在表上增加一行一列，填入

对基变量有

u1u1u2u2u3u3

v33

u2

v410u3

v11v1



v32v2

令u10得

vv243v45v4

ij

1529310

第三步：计算空格的



ijcij(uivj)

可直接在表上进行

三、调整----闭回路法

当



ij

路，确定调整量

(min(1,3)1)（其原理与单纯形法中按

检验表：

规则确定换出变量相同），然后，按闭回

路上的正、负号，加入或减去此值，得到新的调运方案。

新调运方案：

对上表求空格的检验数，见上表。 因为所有



ij>0，所以此解为最优解，总费用的最小值z=85

ij0，且有某一个ij=0，则此问题有无穷多最优解，

（两个最优解X1

的组合X1(1)X2，也一定是最优解）。

（1）若对某方案所有

基变量，其值为0；若有某个有“-”标记的数为0，调整量为零，把此格作为空格，原空格处填入零。

如：

§3 产销不平衡问题

m

注意：

,X2

（2）在用闭回路法调整时，若有两个具有“-”标记的数同时为最小值，把其中一个作为调出变量，另一个仍为

调整后变为 调整后变为 1、若产大于销

i1

m

aaibj，需增加一个假想的销地，各产地到此的运价都为零，该地的销量为i

j1i1

n

m

n

i



b j。j1

n

2、若产小于销

a

i1



b

j1

j

，需增加一个假想的产地，由此到各销地的运价都为零，该地的产量为

n

bjj1

m



i1

ai。 

例2 设有三个化肥厂供应四个地区同一种化肥，其产、销量和运价如下表，试求出总的运费最节省的化肥调拨方案。

运价单位：万元/万吨

解：

产销平衡表和单位运价表：

初始调拨方案：

判别：计算空格ij。 最优方案：

第四章 运输问题 第48页