CH3---单纯形法求运输问题
- 格式：pdf
- 大小：48.68 KB
- 文档页数：12
8
第三章
运输问题
例：
销地 产地 A1 A2 A3 销量
B1 3 3
B2
B3 4 1
B4 3 3 6
产量 7 4 9
6 6
5
销地 产地 A1 A2 A3 vi
B1 1 v1
B2
B3 3 2
B4 10 5 v4
ui u1 u2 u3
4 v2
v3
ui 和 v j 分别称为第 i 行和第 j 列的位势。 u2 + v1 = 1 u 2 + v3 = 2 u1 + v3 = 3 u1 + v 4 = 10 u3 + v4 = 5 u3 + v2 = 4
2-2
闭回路的性质
1．闭回路各顶点对应的列向量线性相关。
2．对任一空格，必有一组数格，形成一个以它们为顶点的闭回路，且该 闭回路是唯一的。
闭回路的找法：以某一空格为起点，用水平或垂直线向前划，每碰到一数 格后转 90°后，继续前进，直到回到起始空格为止。
2-3 最优性检验与方案调整 求检验数有两种方法：闭回路法，位势法。
令
v1 = 1 ，可解得其他位势的数值。
9
第三章
运输问题
销地 产地 A1 A2 A3 vi
B1 （2） 1 （-3） 1
B2 （9） （8） 4 8
B3 3 2 （-2 ） 2
B4 10 （9） 5 9
ui 1 0 -4
销地 产地 A1 A2 A3
B1 1 10
B2 2 1
B3
B4 -1
12
2-4 表上作业法与单纯形法 表上作业法计算步骤、过程与单纯形法相同，但具体计算时不必画出单纯 形表，而是是在产销平衡表上进行。
b1 Λ bn ) T
1 1 ( m + n ) ( m ⋅n )
1 1 1 Λ 1
Ο
a1 a2
Μ
1 1 Λ 1 1
Ο
am b1 b2
Μ
1 1
Ο
1
1
bn
0 0 0 Μ Μ Μ 1 1 0 pij = Μ = Μ + Μ = ei + em+ j 1 0 1 Μ Μ Μ 0 0 0
B1
B2
B3
B4
B5
2 10 7
11 3 8
3 5 1
4 9 2
0 0 0
3
6
5
6
4
11
第三章
运输问题
销 地 产地 A1 A2 A3 销量 B1 2 3 3 6 4 5 3 6 B2 B3 B4 3 B5 2 2 4
产 量 7 4 9
12
销地 产地 A1 A2 A3
B1 B2 3 1 7 11 9 4
B3 3 2 10
B4 10 8 5
3
6
5
6
2-1 初始方案的确定 1．最小元素法
5
第三章
运输问题
销地 产地 A1 A2 A3 销量
B1 3 3
B2 B3 B4 4 1 6 6 5 3 3 6
产 量 7 4 9
同时划去一行和一列，补 0
i =1 m
∑c x
j =1
n
ij ij
满足
∑ xij = ai
j=1
m
n
（i=1，…，m）
∑x
i =1
ij
= bj
（j=1，…，n）
xij ≥ 0
min z = c11x11 + Λ + c1n x1n + c 21x21 + Λ + c243; Λ + cm n
有时把两个表写在一起。
总产量 ∑ ai ＝
i =1 m
m
总销量 ∑ bi
i =1 n
n
：产销平衡 ：产销不平衡 ：产销不平衡
总产量 ∑ ai ＜
i =1 m
总销量 ∑ bi
i =1 n
总产量 ∑ ai ＞
i =1
总销量 ∑ bi
i =1
现只考虑产销平衡的情况。
2
第三章
运输问题
如果用 xij 代表从第 i 个产地调运给第 j 个销地的物资的单位数量，那末在 产销平衡的条件下，使总的运费支出最小，可以表为以下数学形式： min z = ∑
3
第三章
运输问题
线性规划中的 X，A，b，C：
C = (c11 Λ c1n c21 Λ c 2n
X = (x11 Λ x1n x21 Λ x2n
Λ Λ
x m1 Λ x m n
Λ Λ
c m1 Λ c m n
) )
T
b = (a1 Λ a m
1 1 Λ A= 1 1 Ο
（j=1，…，n）
例：
销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 产量 7 5 7 2 3 4 6 销地 产地 A1 A2 A3 2 10 7 11 3 8 3 5 1 4 9 2 B1 B2 B3 B4
销 地 产地 A1 A2 A3 销量
B1
B2
B3
B4
B5
产 量 7 4 9
销 地 产地 A1 A2 A3
第三章
运输问题
第三章
运输问题
运输问题可用单纯形法求解，但有更直观、更简单的方法。 1．运输问题的典例和数学模型 2．表上作业法 3．产销不平衡的运输问题及其应用
§1．运输问题的典例和数学模型
【例 1】 某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂， 每天的糖果生产量分别为 :A1—7t，A2 一 4t，A3 一 9t。该公司把这些糖果分 别运往四个地区的门市部销售，各地区每天的销售量为：B1 一 3t，B2 一 6t， B3 一 5t，B4 一 6t。已知从每个加工厂到各销售门市部每吨糖果的运价如表所 示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运 费支出力最少。
§3．产销不平衡的运输问题及其应用
销 地 产地 1 2 ： m 销量
1
2
… n
产 量 a1 a2 ： am
b1
b2
… bn
10
第三章
运输问题
1．总产量 ∑ ai ＞
i =1
m
总销量 ∑ bi
i =1
n
产大于销
假设增加一个销售点 Bn+1 表示库存，令
bn +1 = ∑ ai − ∑ b j ( > 0 )
2．伏格尔（Vogel）法 找出每行和每列最小的两个元素之差，再从差值最大的行或列中找出 最小运价
销地 产地 A1 A2 A3 销量
B1 3 3
B2 B3 B4 产量 5 6 6 5 2 1 3 6 7 4 9
6
第三章
运输问题
最小元素法和 Vogel 法给出的是运输问题的基可行解
在得到的调运方案中： 有数字的格（数格） —— 基变量取值 没有数字的格（空格）—— 非基变量 运输问题中，基变量有（m＋n－1）个，故数格应有（m＋n－1）个
1．闭回路法
7
第三章
运输问题
例：
销地 产地 A1 A2 A3 销地 产地 A1 A2 A3 销量
B1 1 10
B2 2 1
B3
B4 -1
12
B1 3 3
B2
B3 5
B4 产量 2 1 3 6 7 4 9
6 6
5
注意 —— 可能出现退化的基可行解
2．位势法
σij = cij − (u i + v j )
i =1 j =1 m n
， c i , n +1 = 0
（i=1，…，m）
则变成产销平衡问题。
2．总产量 ∑ ai ＜
i =1
m
总销量 ∑ bi
i =1
n
产小于销
假设增加一个产地 Am+1 ，令
a m +1 = ∑ b j − ∑ a i ( > 0 )
j =1 i =1 n m
， c m +1 , j = 0
1
第三章
运输问题
产销平衡表 销地 1 产地 1 2 ： m 销量 2 … n 产 量 a1 a2 ： am
b1
b2
… bn
从第 i 个产地到第 j 个销地的单位物资运价为 cij 。
单位运价表 销地 产地 1 2 ： m 1 c11 c21 cm1 2 c12 c22 cm2 … n c1n c2n cmn
Rank（A）是否等于 m+n ？
4
第三章
运输问题
q1 Μ qm 设 A= ，则在产销平衡的运输问题中，有 qm+1 Μ q m+n
q1 + Λ + qm = qm+1 + Λ + qm+ n = (1 Λ Λ 1)( m•n)
门市部 B1 加工厂 A1 A2 A3 3 1 7
B2 11 9 4
B3 3 2 10
B4 10 8 5
某种物资需要调运，已知有 m 个地点可以供应该种物资( 通称产地，用 i=1，…，m 表示)，有 n 个地点需要该种物资(通称销地，用 j=1，…，n 表示)， 又知这 m 个产地的可供量(通称产量)为 a1，a2，… am(记为 ai)，n 个销地的需 要量(通称销量)分别为 b1，b2，…，bn(记为 bj)。
x11 + x12 + Λ + x1n = a1
第三章
运输问题
例：
销地 产地 A1 A2 A3 销量
B1 3 3
B2
B3 4 1
B4 3 3 6
产量 7 4 9
6 6
5
销地 产地 A1 A2 A3 vi
B1 1 v1
B2
B3 3 2
B4 10 5 v4
ui u1 u2 u3
4 v2
v3
ui 和 v j 分别称为第 i 行和第 j 列的位势。 u2 + v1 = 1 u 2 + v3 = 2 u1 + v3 = 3 u1 + v 4 = 10 u3 + v4 = 5 u3 + v2 = 4
2-2
闭回路的性质
1．闭回路各顶点对应的列向量线性相关。
2．对任一空格，必有一组数格，形成一个以它们为顶点的闭回路，且该 闭回路是唯一的。
闭回路的找法：以某一空格为起点，用水平或垂直线向前划，每碰到一数 格后转 90°后，继续前进，直到回到起始空格为止。
2-3 最优性检验与方案调整 求检验数有两种方法：闭回路法，位势法。
令
v1 = 1 ，可解得其他位势的数值。
9
第三章
运输问题
销地 产地 A1 A2 A3 vi
B1 （2） 1 （-3） 1
B2 （9） （8） 4 8
B3 3 2 （-2 ） 2
B4 10 （9） 5 9
ui 1 0 -4
销地 产地 A1 A2 A3
B1 1 10
B2 2 1
B3
B4 -1
12
2-4 表上作业法与单纯形法 表上作业法计算步骤、过程与单纯形法相同，但具体计算时不必画出单纯 形表，而是是在产销平衡表上进行。
b1 Λ bn ) T
1 1 ( m + n ) ( m ⋅n )
1 1 1 Λ 1
Ο
a1 a2
Μ
1 1 Λ 1 1
Ο
am b1 b2
Μ
1 1
Ο
1
1
bn
0 0 0 Μ Μ Μ 1 1 0 pij = Μ = Μ + Μ = ei + em+ j 1 0 1 Μ Μ Μ 0 0 0
B1
B2
B3
B4
B5
2 10 7
11 3 8
3 5 1
4 9 2
0 0 0
3
6
5
6
4
11
第三章
运输问题
销 地 产地 A1 A2 A3 销量 B1 2 3 3 6 4 5 3 6 B2 B3 B4 3 B5 2 2 4
产 量 7 4 9
12
销地 产地 A1 A2 A3
B1 B2 3 1 7 11 9 4
B3 3 2 10
B4 10 8 5
3
6
5
6
2-1 初始方案的确定 1．最小元素法
5
第三章
运输问题
销地 产地 A1 A2 A3 销量
B1 3 3
B2 B3 B4 4 1 6 6 5 3 3 6
产 量 7 4 9
同时划去一行和一列，补 0
i =1 m
∑c x
j =1
n
ij ij
满足
∑ xij = ai
j=1
m
n
（i=1，…，m）
∑x
i =1
ij
= bj
（j=1，…，n）
xij ≥ 0
min z = c11x11 + Λ + c1n x1n + c 21x21 + Λ + c243; Λ + cm n
有时把两个表写在一起。
总产量 ∑ ai ＝
i =1 m
m
总销量 ∑ bi
i =1 n
n
：产销平衡 ：产销不平衡 ：产销不平衡
总产量 ∑ ai ＜
i =1 m
总销量 ∑ bi
i =1 n
总产量 ∑ ai ＞
i =1
总销量 ∑ bi
i =1
现只考虑产销平衡的情况。
2
第三章
运输问题
如果用 xij 代表从第 i 个产地调运给第 j 个销地的物资的单位数量，那末在 产销平衡的条件下，使总的运费支出最小，可以表为以下数学形式： min z = ∑
3
第三章
运输问题
线性规划中的 X，A，b，C：
C = (c11 Λ c1n c21 Λ c 2n
X = (x11 Λ x1n x21 Λ x2n
Λ Λ
x m1 Λ x m n
Λ Λ
c m1 Λ c m n
) )
T
b = (a1 Λ a m
1 1 Λ A= 1 1 Ο
（j=1，…，n）
例：
销地 产地 A1 A2 A3 销量 B1 B2 B3 B4 产量 7 5 7 2 3 4 6 销地 产地 A1 A2 A3 2 10 7 11 3 8 3 5 1 4 9 2 B1 B2 B3 B4
销 地 产地 A1 A2 A3 销量
B1
B2
B3
B4
B5
产 量 7 4 9
销 地 产地 A1 A2 A3
第三章
运输问题
第三章
运输问题
运输问题可用单纯形法求解，但有更直观、更简单的方法。 1．运输问题的典例和数学模型 2．表上作业法 3．产销不平衡的运输问题及其应用
§1．运输问题的典例和数学模型
【例 1】 某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂， 每天的糖果生产量分别为 :A1—7t，A2 一 4t，A3 一 9t。该公司把这些糖果分 别运往四个地区的门市部销售，各地区每天的销售量为：B1 一 3t，B2 一 6t， B3 一 5t，B4 一 6t。已知从每个加工厂到各销售门市部每吨糖果的运价如表所 示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运 费支出力最少。
§3．产销不平衡的运输问题及其应用
销 地 产地 1 2 ： m 销量
1
2
… n
产 量 a1 a2 ： am
b1
b2
… bn
10
第三章
运输问题
1．总产量 ∑ ai ＞
i =1
m
总销量 ∑ bi
i =1
n
产大于销
假设增加一个销售点 Bn+1 表示库存，令
bn +1 = ∑ ai − ∑ b j ( > 0 )
2．伏格尔（Vogel）法 找出每行和每列最小的两个元素之差，再从差值最大的行或列中找出 最小运价
销地 产地 A1 A2 A3 销量
B1 3 3
B2 B3 B4 产量 5 6 6 5 2 1 3 6 7 4 9
6
第三章
运输问题
最小元素法和 Vogel 法给出的是运输问题的基可行解
在得到的调运方案中： 有数字的格（数格） —— 基变量取值 没有数字的格（空格）—— 非基变量 运输问题中，基变量有（m＋n－1）个，故数格应有（m＋n－1）个
1．闭回路法
7
第三章
运输问题
例：
销地 产地 A1 A2 A3 销地 产地 A1 A2 A3 销量
B1 1 10
B2 2 1
B3
B4 -1
12
B1 3 3
B2
B3 5
B4 产量 2 1 3 6 7 4 9
6 6
5
注意 —— 可能出现退化的基可行解
2．位势法
σij = cij − (u i + v j )
i =1 j =1 m n
， c i , n +1 = 0
（i=1，…，m）
则变成产销平衡问题。
2．总产量 ∑ ai ＜
i =1
m
总销量 ∑ bi
i =1
n
产小于销
假设增加一个产地 Am+1 ，令
a m +1 = ∑ b j − ∑ a i ( > 0 )
j =1 i =1 n m
， c m +1 , j = 0
1
第三章
运输问题
产销平衡表 销地 1 产地 1 2 ： m 销量 2 … n 产 量 a1 a2 ： am
b1
b2
… bn
从第 i 个产地到第 j 个销地的单位物资运价为 cij 。
单位运价表 销地 产地 1 2 ： m 1 c11 c21 cm1 2 c12 c22 cm2 … n c1n c2n cmn
Rank（A）是否等于 m+n ？
4
第三章
运输问题
q1 Μ qm 设 A= ，则在产销平衡的运输问题中，有 qm+1 Μ q m+n
q1 + Λ + qm = qm+1 + Λ + qm+ n = (1 Λ Λ 1)( m•n)
门市部 B1 加工厂 A1 A2 A3 3 1 7
B2 11 9 4
B3 3 2 10
B4 10 8 5
某种物资需要调运，已知有 m 个地点可以供应该种物资( 通称产地，用 i=1，…，m 表示)，有 n 个地点需要该种物资(通称销地，用 j=1，…，n 表示)， 又知这 m 个产地的可供量(通称产量)为 a1，a2，… am(记为 ai)，n 个销地的需 要量(通称销量)分别为 b1，b2，…，bn(记为 bj)。
x11 + x12 + Λ + x1n = a1
