运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论
运输问题运输问题及其数学模型 运输问题的表上作业法 运输问题的进一步讨论
运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论
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)
…… 此处隐藏670字 ……
形法求解运输问题。但是当用单纯形法求解运输问题时，先得在每个约束条件 中引入一个人工变量，这样一来，即使对于m=3、n=4这样 简单的运输问题，变量数目也会达到19个之多。
运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论
因此，我们利用运输问题数学模型的特点，引入了表上作
业法来求解运输问题
运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论
4.2 用表上作业法求解运输问题表上作业法的基本思想：
先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图 所示。