运筹学 第四章 运输问题

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

运输问题运输问题及其数学模型 运输问题的表上作业法 运输问题的进一步讨论

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

4.1 运输问题及其数学模型例1:某部门有3个生产同类产品的工厂(产地),生产的产品 由4个销售点(销地)出售，各工厂的生产量、各销售点的销售

量(假定单位均为t)以及各工厂到各销售点的单位运价(元/t)示于下表中 要求研究产品如何调运才能使总运费最小单位 销地 运价 产地

B1

B2

B3

B4

产量

A1 A2 A3

销量

2 1 8 3

9 3 4 8

10 4 2 4

2 2 5 6

9 5 7

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

运输问题网络图供应地 s1=9 供 应 量 A12 9 10

运价

需求地 B1 d1=3

s2=5 s3=7

A2

A3

2 1 3 4 2 8 4 2 5

B2 d2=8B3 d3=4

需 求 量

B4 d4=6

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

设 x ij 为运量 目标函数： min Z 2 x 11 9 x 12 10 x 13 7 x 14 x 21 3 x 22 4 x 23 2 x 24 8 x 31 4 x 32 2 x 33 5 x 34 x 11 x 12 x 13 x 14 9 x x 22 x 23 x 24 5 21 x 31 x 32 x 33 x 34 7 x 11 x 21 x 31 3 约束条件： x x 22 x 32 8 12 x x x 4 13 23 33 x 14 x 24 x 34 6 x 0 ( i 1 .2 .3 , j 1 .2 .3 .4 ) ij

产量约束

销量约束

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

运输问题的一般提法是：设某种物资有 m 个产地 A1 , A 2 , ,A m , 各产地的产量是 a 1 , a 2 , , a m ; 有 n 个销地 B 1 , B 2 , , B n ,

各销地的销量是 b1 , b 2 , , b n . 假定从产地A i ( i 1, 2 , , m )

到销地 B j ( j 1, 2 , , n ) 运输单位物品的运价是 c ij ,问怎样调运这些物品才能使总运费最小？

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

运价表销地

产地

B1c 11

B2c 12 x12 c 21 c 22 x 22

Bnc1 nx1 n c2nx2n

产 量a1

A1 A2

x11

x 21

a2

cm1cm 2 xm 2 x mn c mn

am

Am销 量

x m1

b1

b2

bn

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

假 设 ： a i 0, b j 0, c ij 0

当产销平衡时，其模型如下：min Z

ci 1 j 1

m

n

ij

x ij

x ij a i x ij b j x 0 ij

(

a

i

b

j

)

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

当产大于销时，其模型是：min Z

ci 1 j 1

m

n

ij

x ij

x ij a i x ij b j x 0 ij

(

a

i

b

j

)

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

当产小于销时，其模型是：m in Z

c

ij

x ij

x ij a i x ij b j x ij 0

( ai

b

j

)

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

运输问题数学模型的特点

1、平衡运输问题必有可行解，也 必有最优解；证明 记

ai 1

m

i

bj 1

n

j

d.

则令x ij a ib j d

( i 1, 2 , , m ; j 1, 2 , , n )

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

则 x ij 为运输问题的一个可行解。事实上：

j 1

n

x ij

j 1

n

a ib j d

ai d

bj 1

n

j

ai

( i 1, 2 , , m )

i 1

m

x ij

i 1

m

a ib j d

bj d

i 1

m

ai b j

( j 1, 2 , , n

)

又因 a i 0 , b j 0 . 所以 x ij 0 . 故 [ x ij ] 是一组可行解。

又因为总费用不会为负值(存在下界)。这说明，运输问题

既有可行解，又必然有下界存在，因此一定有最优解存在。

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

运输问题数学模型的特点

2、运输问题约束条件的系数矩阵

对运输问题数学模型的结构约束加以整理，可 知其系数矩阵具有下述形式：

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

x11 , x12 , , x1 n ; x 21 , x 22 , x 2 n , , , , , x m 1 , x m 2 , x mn

m行

n行

1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1

1 1

(4-1)

1.运输问题是一个具有m×n个变量和n+m个等型约束的线性规划问题。

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

p ij e i e m j

( i 1, 2 , , m ; j 1, 2 , , n )

p ij

0 0 0 1 1 0 0 0 0 ei e m 1 0 1 0 0 0 ( m n ) 1 ( m n ) 1 ( m n ) 1

j

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

2.运输问题约束方程组的系数矩阵是一个只有0和1两个数值 的稀疏矩阵,其中1的总数为 2×m×n 个。

3、约束条件系数矩阵的每一列有两个非零元素，这对应于

每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

4、约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总 数是m+n-1 证明：因A的前m行对应元素的和与后n行对应元素的和相等， 恰好都是： E 1 (1,1, ,1) m n 所以A的行向量是线性相关 的。从而 r(A)≤m+n.

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

去掉A的第一行，并取如下m+n-1列，得到m+n-1阶子式D | p 1 1 p 1 2 0 0 0 1 0 0 0 0 0 0 1 0 p 1 n p 2 1 p 3 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 pm1 | 0 0 1 1 0 0 1 0

所以 r(A)=m+n-1.

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

对于产销平衡运输问题，除了上述特点外，还有以下特点：

1 所有结构约束条件都是等式约束

2 各产地产量之和等于各销地销量之和

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

运输问题数学模型的特点3、运输问题的解运输问题是一种线性规划问题。前面讲述的单纯形法是 求解线性规划问题十分有效的一般方法，因而可用单纯

形法求解运输问题。但是当用单纯形法求解运输问题时，先得在每个约束条件 中引入一个人工变量，这样一来，即使对于m=3、n=4这样 简单的运输问题，变量数目也会达到19个之多。

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

因此，我们利用运输问题数学模型的特点，引入了表上作

业法来求解运输问题

运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论

4.2 用表上作业法求解运输问题表上作业法的基本思想：

先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图 所示。