2024年3月17日发(作者：市禹)

第二次 运输问题

1．运输问题的一般提法

设有

m

个产地

A

1

,A

2

,



,A

m

，将生产的物资联合运往

n

个销地

B

1

,B

2

,



,B

n

；各产地

A

i

的

产量为

a

i

，各销地

B

j

的销量为

b

j

；从

A

i

产地到

B

j

销地的单位运价为

c

ij

，问如何组织运输，可使

总的运费最少？

如果总的产量



a

i



总的销量



b

j

，则称它为产销平衡运输问题

i1

m

n

j1

2．产销平衡运输问题的数学模型

引入决策变量：用

x

ij

表示从

A

i

产地运到

B

j

销地的物资数量

确定目标函数：使总运输费用最少

minZ



c

ij

x

ij

i1j1

mn

写出约束条件：从

A

i

产地运出的物资数量应等于

A

i

产地的物资供应量

即



x

j1

n

ij

a

i

i1,2,,m

运到

B

j

销地的物资数量应等于

B

j

销地的需求量

即



x

i1

m

ij

b

j

j1,2,,n

x

ij

取值非负。

说明：

① 运输问题是一线性规划问题；

②

x

ij



a

i

b

j

d

（其中

d



a

i





b

j

）是运输问题的一个可行解，从而它有基本可行解；

i1j1

mn

又

x

ij

min



a

i

,b

j



，故运输问题的任一可行解都是有限的，即可行域有界；因此运输

问题必有有限最优解且最优解同样可在基本可行解处得到。

③ 针对

m

个产地

n

个销地的产销平衡运输问题，其约束条件中共有

mn

个方程，但这

mn

个方程中，任一方程都可以通过其余

mn1

方程得到。因此真正有效的方程个

数是

mn1

个，我们可以将多余的一个方程划掉。这样以来，运输问题的基本可行解

中只含

mn1

个基变量。

④ 当

m

和

n

取值较大时，引入的决策变量较多，采用表格单纯形法计算量较大，通常采用

表上作业法求解运输问题。

3．求初始调运方案（初始基本可行解）

1）左上角方法：从表格中左上角方格所对应的决策变量开始分配运输量，分配时让它取尽可

能大的取值。

2）最小元素法：从表格中最小单位运价所对应的决策变量开始分配运输量，分配时让它取尽

可能大的取值。

3）沃格尔（Vogel）法：

（ⅰ）首先计算每一行和每一列的次小单位运价与最小单位运价之间的差值，并分别称之

为相应的行罚数和列罚数；

（ⅱ）将各行的行罚数写在运输表格的右侧一列，将各列的列罚数写在运输表格下侧一行；

（ⅲ）确定最大罚数值所在的行或列，从该行或该列最小单位运价所对应的决策变量开始

分配运输量，分配时让它取尽可能大的取值。

销地

B

3

B

2

B

4

B

1

供应量

产地

A

1

A

2

2

1

8

9

3

4

10

4

2

7

2

5

9

5

7

21

21

A

3

需求量

3 8 4 6

分配完之后，划掉表格中的一行或一列，得新的运输表格，再重复上述步骤。

用以上三种方法得到的初始基本可行解，它们对应的目标函数值，以沃格尔法为最小，最小

元素法次之，以左上角方法为最大。

4．最优方案的判别及调运方案的改进

（1） 闭回路概念

凡是能排成如下形式的变量集合

x

i

1

j

1

,x

i

1

j

2

,x

i

2

j

2

,x

i

2

j

3

,x

i

3

j

3

,x

i

3

j

4

,,x

i

s

j

s

,x

i

s

j

1

（其中

i

1

,i

2

,



,i

s

互不相同，

j

1

,j

2

,



,j

s

也互不相同）就称为一个闭回路。

闭回路中出现的变量称为闭回路的顶点，相邻两个顶点的连线称为闭回路的边。

现将闭回路的顶点在运输表格中画出来，同时将相邻顶点用直线段连接起来，就可

以得到一条封闭折线。

闭回路的特点：ⅰ）表中的各行各列至多只有闭回路的两个顶点；

ⅱ）闭回路的边要么是水平的，要么是铅直的。

（2） 用闭回路方法计算非基变量的检验数

以非基变量

x

ij

所在的方格为起点，作一闭回路；（除起点

x

ij

之外，要求闭回路的

其它顶点必须是基变量）然后在闭回路上作运输量是一个单位的调整，并计算由此引起

的总运费的改变量。

该改变量称为非基变量

x

ij

的检验数。

销地

产地

B

1

B

2

B

3

B

4

供应量

2024年3月17日发(作者：市禹)

第二次 运输问题

1．运输问题的一般提法

设有

m

个产地

A

1

,A

2

,



,A

m

，将生产的物资联合运往

n

个销地

B

1

,B

2

,



,B

n

；各产地

A

i

的

产量为

a

i

，各销地

B

j

的销量为

b

j

；从

A

i

产地到

B

j

销地的单位运价为

c

ij

，问如何组织运输，可使

总的运费最少？

如果总的产量



a

i



总的销量



b

j

，则称它为产销平衡运输问题

i1

m

n

j1

2．产销平衡运输问题的数学模型

引入决策变量：用

x

ij

表示从

A

i

产地运到

B

j

销地的物资数量

确定目标函数：使总运输费用最少

minZ



c

ij

x

ij

i1j1

mn

写出约束条件：从

A

i

产地运出的物资数量应等于

A

i

产地的物资供应量

即



x

j1

n

ij

a

i

i1,2,,m

运到

B

j

销地的物资数量应等于

B

j

销地的需求量

即



x

i1

m

ij

b

j

j1,2,,n

x

ij

取值非负。

说明：

① 运输问题是一线性规划问题；

②

x

ij



a

i

b

j

d

（其中

d



a

i





b

j

）是运输问题的一个可行解，从而它有基本可行解；

i1j1

mn

又

x

ij

min



a

i

,b

j



，故运输问题的任一可行解都是有限的，即可行域有界；因此运输

问题必有有限最优解且最优解同样可在基本可行解处得到。

③ 针对

m

个产地

n

个销地的产销平衡运输问题，其约束条件中共有

mn

个方程，但这

mn

个方程中，任一方程都可以通过其余

mn1

方程得到。因此真正有效的方程个

数是

mn1

个，我们可以将多余的一个方程划掉。这样以来，运输问题的基本可行解

中只含

mn1

个基变量。

④ 当

m

和

n

取值较大时，引入的决策变量较多，采用表格单纯形法计算量较大，通常采用

表上作业法求解运输问题。

3．求初始调运方案（初始基本可行解）

1）左上角方法：从表格中左上角方格所对应的决策变量开始分配运输量，分配时让它取尽可

能大的取值。

2）最小元素法：从表格中最小单位运价所对应的决策变量开始分配运输量，分配时让它取尽

可能大的取值。

3）沃格尔（Vogel）法：

（ⅰ）首先计算每一行和每一列的次小单位运价与最小单位运价之间的差值，并分别称之

为相应的行罚数和列罚数；

（ⅱ）将各行的行罚数写在运输表格的右侧一列，将各列的列罚数写在运输表格下侧一行；

（ⅲ）确定最大罚数值所在的行或列，从该行或该列最小单位运价所对应的决策变量开始

分配运输量，分配时让它取尽可能大的取值。

销地

B

3

B

2

B

4

B

1

供应量

产地

A

1

A

2

2

1

8

9

3

4

10

4

2

7

2

5

9

5

7

21

21

A

3

需求量

3 8 4 6

分配完之后，划掉表格中的一行或一列，得新的运输表格，再重复上述步骤。

用以上三种方法得到的初始基本可行解，它们对应的目标函数值，以沃格尔法为最小，最小

元素法次之，以左上角方法为最大。

4．最优方案的判别及调运方案的改进

（1） 闭回路概念

凡是能排成如下形式的变量集合

x

i

1

j

1

,x

i

1

j

2

,x

i

2

j

2

,x

i

2

j

3

,x

i

3

j

3

,x

i

3

j

4

,,x

i

s

j

s

,x

i

s

j

1

（其中

i

1

,i

2

,



,i

s

互不相同，

j

1

,j

2

,



,j

s

也互不相同）就称为一个闭回路。

闭回路中出现的变量称为闭回路的顶点，相邻两个顶点的连线称为闭回路的边。

现将闭回路的顶点在运输表格中画出来，同时将相邻顶点用直线段连接起来，就可

以得到一条封闭折线。

闭回路的特点：ⅰ）表中的各行各列至多只有闭回路的两个顶点；

ⅱ）闭回路的边要么是水平的，要么是铅直的。

（2） 用闭回路方法计算非基变量的检验数

以非基变量

x

ij

所在的方格为起点，作一闭回路；（除起点

x

ij

之外，要求闭回路的

其它顶点必须是基变量）然后在闭回路上作运输量是一个单位的调整，并计算由此引起

的总运费的改变量。

该改变量称为非基变量

x

ij

的检验数。

销地

产地

B

1

B

2

B

3

B

4

供应量