Ling Xueling
运输,指派和转运问题,实际上都可以用
L.P,模型加以描述,所以可以认为它们是
L.P,的特例单列一章的原因在于：应用面极广,实践性很强,而特有的数学结构使得人们设计出了特别有效的方法对此类模型进行求解本章的重点在：掌握表格化方法 求解 运输,
指派,转运问题的模型 。
第六章 运输、指派和转运问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
1,运输问题的概念问题 －－从 m 个起运点 （ origin） 到 n 个目的地 （
destination） 的 货物 和 服务 的 分配 计划起运点特征 －－可供量有限,无法 （ 不能 ） 超过目的地特征 －－需求量有限,满足即可分配 －－因为不同路径往往成本不相同,才有优化的必要优化目标 －－成本最低,运费最小,或利润最大 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
P&T 公司分销问题,地图
C A N N E R Y 1
B e l l i n g h a m
C A N N E R Y 2
E u g e n e
W A R E H O U S E 1
S a c r a m e n t o
W A R E H O U S E 2
S a l t L a k e C i t y
W A R E H O U S E 3
R a p i d C i t y
W A R E H O U S E 4
A l b u q u e r q u e
C A N N E R Y 3
A l b e r t L e a
Ling Xueling
P&T 公司分销问题,运输量与成本数据
300 车合计
85 车Albuquerque300 车合计
70 车Rapid City100 车Albert Lea
65 车Salt Lake City125 车Eugene
80 车Sacramento75 车Bellingham
分配量仓库产量罐头加工厂
685388682995Albert Lea
791690416352Eugene
$867$654$513$464Bellingham
罐头加工厂
AlbuquerqueRapid CitySalt Lake CitySacramento从 \ 到仓库
Ling Xueling
P&T 公司分销问题,无算法的方案
851500Albert Lea
055655Eugene
00075Bellingham
罐头加工厂
AlbuquerqueRapid CitySalt Lake CitySacramento从 \ 到仓 库
决策模型：就近原则（观察运输成本）
– Bellingham加工厂离仓库最远，将其产品运到最近仓库 Sacramento；
若 Bellingham加工厂有剩余，则送到 Salt Lake City。
– Albuquerque仓库离加工厂最远，从距其最近的 Albert Lea加工厂产品送货；
若 Albert Lea加工厂有剩余，则送到 Rapid City。
–Eugene加工厂的产品满足其它仓库的剩余需求。
总运输成本 = 75($464) + 5($352) + 65($416) + 55($690) + 15($388) + 85($685) = $165,595
Ling Xueling
P&T 公司分销问题,还有成本更低的方案吗?
总运输成本 = 20($513) + 55($867) + 80($352) + 45($416) + 70($388) + 35($685)
= $152,535
降低 $13060,约 8%!
P & T 公司配送问题单位成本 目的地（仓库）
萨克拉门托 盐湖城 赖皮特城 奥尔巴古出发地 贝林翰 $464 $513 $654 $867
( 罐头工厂 ) 尤基尼 $352 $416 $690 $791
艾尔贝·李 $995 $682 $388 $685
运输量 目的地（仓库）
卡车装载 萨克拉门托 盐湖城 赖皮特城 奥尔巴古 总运出量出发地 贝林翰 0 20 0 55 75
( 罐头工厂 ) 尤基尼 80 45 0 0 125
艾尔贝·李 0 0 70 30 100
总运入量 80 65 70 85
= = = =
需求量 80 65 70 85
Ling Xueling
一,运输问题及其常规解法
2,例子
1） 有关数据
Foster 公司在全国不同地方有三家工厂 O1,O2,O3,四家地区零售中心 D1,D2,D3,D4,未来 3 个月供需数据如下工厂 三个月 销售中心 三个月生产能力 需求预测
O1 5000 D1 6000
O2 6000 D2 4000
O3 2500 D3 2000
13500 D4 1500
13500
第一节 运输问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
2） 可用运输路径 （ 由 结点,弧 构成的网络图 ）
第一节 运输问题凌晨,凌晨,
1
2
3
1
2
3
4
5 0 0 0
6 0 0 0
2 5 0 0
6 0 0 0
4 0 0 0
2 0 0 0
1 5 0 0
a r c s
n od e s
n e t w or k
源结点目的结点
Ling Xueling
一,运输问题及其 常规 解法
3） 各路径单位运输成本数据 (Cij 数据－－弧之 权 )
目的地起运点 D1 D2 D3 D4
O1 3 2 7 6
O2 7 5 2 3
O3 2 5 4 5
4 ） 假定 ( 以后再逐步放松 )
（ 1） 三家工厂的生产成本一样,仅仅运输成本可变
（ 2） ( 隐含假定 ) 。
第一节 运输问题凌晨,凌晨,
ji DO
Ling Xueling
一,运输问题及其常规解法
3,模型 ( 运输问题的 L.P.)
建模一般原则,为每一 弧 指定一个 变量,为每一 结点 指定一个 约束式
1） 决策变量 xij －－ 从 Oi 到 Dj 的运输量
2） o.f,Min
3） 约束 供方－－,?” 需方－－,＝,。
第一节 运输问题凌晨,凌晨,
jiij xc
Ling Xueling
一,运输问题及其常规解法
3,模型 ( 运输问题的 L.P.)
min ∑∑ c i j x i j
s.t.
x11 + x12 + x13 + x14 ≤ 5000 O1
x21 + x22 + x23 + x24 ≤ 6000 O2
x31 + x32 + x33 + x34 ≤ 2500 O3
x11 + x21 + x31 = 6000 D1
x12 + x22 + x32 = 4000 D2
x13 + x23 + x33 = 2000 D3
x14 + x24 + x34 = 1500 D4
xi j ≥ 0
第一节 运输问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
4,计算机求解及其特点
x11 = 3500 x12 = 1500 x22 = 2500
x23 = 2000 x24 = 1500 x31 = 2500
其余 xij = 0 o.f,= 39500
注意：最优解值都是 整数 ！ 巧合？
5,定理若所有起运点的供货量和目的地的需求量都是 整数的话,运输,指定,转运问题的解也总是 整 数值 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
6,特殊情况及其处理
1）
（ 1） S > D,不必修改模型,过剩供给会在最优解中以松弛 反应出来
（ 2） S < D,必须修改模型,（ a） 引入一个虚拟起运点其供给量 ＝ D － S （ b） 从虚拟起点到任意一个目的地 Dj 之运输成本指定为 0 （ 不影响 o.f,）
2） 求最大化若 cij 表示的是单位利润和收入,只需相应改变 o.f,即可
3） 有的路径无法使用：取消相关的 xij 即可 。
第一节 运输问题凌晨,凌晨,
ji DO
Ling Xueling
一,运输问题及其常规解法
7,运输问题一般 L.P,模型供 方结点需 方结点第一节 运输问题凌晨,凌晨,
0
).,,,,,2,1(
).,,,,,2,1(
..
m i n
1
1
ij
m
i
jij
n
j
iij
ijij
x
njDx
miOx
ts
xc
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
1,方法比较
1） L.P,方法－－只能使用于小,中型问题 （ 若有 100 个起运点和 1000 个目的地时,变量将有 100,000 个 ）
2） 特殊解法－－ 可以 简化计算,对大型问题更有效率
2,特殊解法的思路首先将问题用 表格形式 予以表达? 随意 求一个 初始可行 解
然后进行 迭代 以改善解?直到求出 最优解 为止
3,例子及其表格作业法求解
1） 例子
Foster公司 3 个 origins 和 4 个 destinations之例 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
3,例子及其表格作业法求解
2） 运输表形如下列形式的表格称为 运输表,（ 注,空格对应于 12条路径 ）
第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 5000
7 5 2 3
O2 6000
2 5 4 5
O3 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
3,例子及其表格作业法求解
3） 运输表的意义
（ 1） 方便收集资料 / 数据
（ 2） 保持运算 轨迹
4,（ 最小成本法 ） 求 初始可行 解
1） 思路
1) 对最小成本路径,安排尽可能多的货物
2) 若有相同的最低成本路径,优先选择运量最 大 的方格－－路径 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
4,（ 最小成本法 ） 求初始可行解
2） 表上作业可得运输方案及相关成本如下：
总成本,42000
第一节 运输问题凌晨,凌晨,
从 至 运输单位 单位成本 成本
o1 - - - - - - - - - - d1 1000 3 3000
o1 - - - - - - - - - - d2 4000 2 8000
o2 - - - - - - - - - - - d1 2500 7 17500
o2 - - - - - - - - - - d3 2000 2 4000
o2 - - - - - - - - - - - d4 1500 3 4500
o3 - - - - - - - - - - - d1 2500 2 5000
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
4,（ 最小成本法 ） 求初始可行解
3） 求初始可行解要保证利用 m + n－ 1 条路径
（ 1） 例子第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
6 8 3 10
O1 30
2 9 5 7
O2 15
7 8 6 4
O3 15
μ? μ? Dè?ó á? 10 25 10 15 60
Ling Xueling
4,（ 最小成本法 ） 求初始可行解
3） 求初始可行解要保证利用 m + n－ 1 条路径
（ 2） 为什么求出初始可行解以后向最优解进行 迭代之必须
（ 3） 调整方法上例中,最后一次运输安排时剩余的行供量和列需量 同时减为零,若此情形发生在安排最后路径以前,则所得初始可行解所利用的路径就会不足 m + n－ 1。 可调整如下：
( i ) 将出问题的行和列分别用横,竖直线划去
( ii ) 额外指定一个零单位运输计划到所划横或竖线上的 任意一个空格 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
4,（ 最小成本法 ） 求初始可行解
4） 求初始可行解的其它方法常用如西北角法,差额法等等,除非运气特别好,一般都需要迭代,只是步骤数量的差异
5,从初始可行解到 最优解 的踏石法
1） 方法思路
（ 1） 对所有 未利用 路径做试探性运量安排
（ 1） 若能使总成本下降,可考虑作为新路径安排运输量
( 2） 若使总成本上升,该路径当然作罢不用
（ 2） 迭代停止准则：
所有未用路径一当被安排运量,即使总成本上升,则当前解当然就是最优解了 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
2） 例子,试探及结果
（ 1） Foster 公司之初始可行解
（ 2） 试探：在未用路径 o2 ---- d2,安排一个单位运量,则第一节 运输问题凌晨,凌晨, μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1001 3999 5000
7 5 2 3
O2 2499 1 2000 1500 6000
2 5 4 5
O3 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
5,从初始可行解到最优解的踏石法
2） 例子,试探及结果
（ 3） 微调之对成本影响 ( net effect )
对成本之影响
O2 － D2 加 1 单位 ＋ 5
O1 － D2 减 1 单位 － 2
O1 － D1 加 1 单位 ＋ 3
O2 － D1 减 1 单位 － 7
net effect = － 1.
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
3） 踏石回路－－对新路径进行试探的一般方法实际上是换基的方法,是代数的迭代换基之表上作业法目的：
求出每一条未用路径,入基,－－安排运输－－对成本之影响方法：
(1) 石－－当前解,只有 当前解可以作为基,可以作为石
(2) 踏石－－ 可以在石头之间跳跃,但只能 跳奇数块石头
(3) 定要构成回路－－ 可以是折线构成的回路
(4) 顺或逆时钟方向 踏石都可以例子及结果对所有新路径要计算出：入基后对成本的净变化,如后所示 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
3） 踏石回路－－对新路径进行试探的一般方法第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1000 4000 ( ￡? 9) ( ￡? 7) 5000
7 ( ￡- 1) 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 ( ￡? 4 ) ( ￡? 7) ( ￡? 7) 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
5,从初始可行解到最优解的踏石法
4） 调整运输方案如何调整？ 是不言而喻的,当然是对 o2 ---- d2 作出 尽可能多的运量安排第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 3500 1500 5000
7 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
5,从初始可行解到最优解的踏石法
5） 计算所有 新 （ 未用 ） 路径的净变化及踏石回路,
结果如下：
第一节 运输问题凌晨,凌晨,
d1 d2 d3 d4
o1 3 5 0 0 - - - - - - - - - - - - - - - - - - - 1 5 0 0 ( 8 ) ( 6 )
o2 ( 1 ) 2 5 0 0 - - - - - - - - - - - - - - - - - - 2 0 0 0 1 5 0 0
o3 2 5 0 0 - - - - - - - - - - - - - - - - - - - - - ( 4 ) - - - - - - - - - - - - - - - - - - - - - ( 6 ) ( 6 )
Ling Xueling
5,从初始可行解到最优解的踏石法
6） 最优解当所有新的路径所对应的方格的单位 净变化 皆 ≥ 0 时,
最优解也就求得了此例的最优解是：
x11 = 3500 x12 = 1500 x22 = 2500
x23 = 2000 x24 = 1500 x31 = 2500
其余 xij = 0 o.f,= 39500（ 总成本 ）
与 L.P,模型的计算机 解相同 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
7） 踏石法中也要始终保持 m + n－ 1 条运输路径被得到利用为什么？
路径少,则踏石法中,石头,少,走回路会发生困难解决因为 0 单位物流也可作为一个运输方案,所以若有现有解同时被减少至 0 单位物流时,只需择其一添,0”,仍作为,现有解,－－留在基内例子
1) 初始解第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
7） 踏石法中也要始终保持 m + n－ 1 条运输路径被得到利用例子
1) 初始解第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1000 2500 3500
7 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 2500 2000 1500
Ling Xueling
5,从初始可行解到最优解的踏石法
7） 踏石法中也要保持 m + n－ 1 条运输路径被得到利用例子
2) 调整
o2 ---- d2 安排 2500 单位,这使得表格变为：
第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 3500 3500
7 5 2 3
O2 0 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 2500 2000 1500 12,0 00
Ling Xueling
6,修正分布法－－求净变化的另一种有效方法
1） 从 c i j = u i + v j 对 已占 方格 定出 u i v i ( 待求 )
对上例,对 已占 方格可得：
u 1 + v 1 = 3,u 1 + v 2 = 2,u 2 + v 1 = 7,u 2 + v 3 = 2,
u 2 + v 4 = 3,u 3 + v 1 = 2,再令,u 1 = 0 可 得各 u i v i 值 。
第一节 运输问题凌晨,凌晨, μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1000 4000 5000
7 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
6,修正分布法－－求净变化的另一种有效方法
1） 从 c i j = u i + v j 对 已占 方格 定出 u i v i ( 待求 )
因为 u 1 = 0
则 u 2 = 4,u 3 = － 1,v 1 = 3,
v 2 = 2,v 3 = － 2,v 4 = － 1
2） 从 e i j = c i j － u i － v j 又可 得 空方格 （ 数学可证明 ） 之净变化为：
e 13 = 9,e 14 = 7,e 22 = － 1,e 32 = 4,e 33 = 7,e 34 = 7
与踏石法所得结果一致 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理
1） 总供给 ≠ 总需求统一处理为,1)引入一个虚拟起点或虚拟目标
2) 虚拟 可供量或需求量＝差额
3) 虚拟单位运输成本＝ 0 （ 虚拟成本 ）
2） 最大化问题 ( 如求运输利润等问题 )
（ 1） 入基空方格：净变化最大者＝ max e i j ( 正值 )
e i j > 0
（ 2） 停止迭代准则,所有 e i j ≤ 0 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理
3） 存在不能利用的运输路径
（ 1） 对 min 问题：指定一个极高的单位成本,M > 0
（ 2） 对 max 问题：指定一个 （ － M） ( M > 0,|M| 极大 )
特殊情况例子
a) 起点：三个工厂,生产能力不同工厂 P1 P2 P3
生产能力 50 40 30
b)目的地：三个零售点,需求预测如下零售点 R1 R2 R3
需求预测 45 15 30
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理例子
c) 利润：由于工厂的生产成本,零售点售价,运输成本可能不同,综合后得到如下利润表
R1 R2 R3
P1 2 8 10
P2 6 11 6
P3 12 7 9
d） 运输表 （ 最大化问题 ）
因为 S > D,S － D = 30,所以虚拟需求量为 30 的 R4,得 初始可行方案为：
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理例子注：求出的 e i j 已 在上表中标出,o.f,( 最大利润 ) ＝ 915
迭代停止,因为是求 max,而所有 e i j < 0,所以认为已求得最优解 。 注意,P1 处留 20,P2 处留 10 单位剩余不运出 。
第一节 运输问题凌晨,凌晨,目的地
R1 R2 R3 R4 Supp ly
2 8 10 0 50
O1 ( － 4) ( － 3) 30 20 20
6 11 6 0 40
O2 15 15 ( － 4) 10 10
12 7 9 0 30
O3 30 ( － 10) ( － 7) ( － 6) 0
D e ma nd 4 5 1 5 1 5 0 3 0 0 30
Ling Xueling
指派－－如：对人员指派项目,机器指派加工任务,对不同公司指派业务,不同航线指派不同船只运输,不同仓库调运物资到指派市场,投标中指派条款,....
解法中强调－－ 1 ←→ 1,仅指派于一个项目目标－－最小成本,最少时间,最大利润,.....
第二节 指派问题凌晨,凌晨,
Ling Xueling
A,常规解法 ( L.P,解法 )
一,问题及假定
1,F,营销 调研公司新近接到三家委托公司要作营销调研项目；
2,F,公司初步评估,T,C 和 M 三人可作为三个项目的组长；
3,三个项目的优先等级大致相同,所以可将项目完成天数 作为评估三个人工作指派的优劣标准
4,三个人对三个项目的能力各不相同,如下表 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
A,常规解法 ( L.P,解法 )
一,问题及假定委 托 人
1 2 3
项目 T 10 15 9
领导 C 9 18 5
人 M 6 14 3
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,建模与,MS”解
1,与运输问题进行比较 ( L.P,之比较 )
若视 人 ←→ 起点 各 （ 人 ） 供给量 ＝ 1
项目 ←→ 目标 各 （ 项目 ） 需求量 ＝ 1
则指派问题是运输问题的 特例 －－当然应有更 特殊 的解法第二节 指派问题凌晨,凌晨,
t
t
c
m
1
2
3
1
1
1
1
1
1
供 需
Ling Xueling
二,建模与,MS”解建模原则还是：为每一条弧指定一个变量,为每一个结点确定一个约束
2,决策变量
x i j = 1 －－第 i 人指派于第 j 项目
0 －－否则
3,o.f,( 总天数最少 )
min 10 x11 + 15 x12 + 9 x13
+ 9 x21 + 18 x22 + 5 x23
+ 6 x31 + 14 x32 + 3 x33
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,建模与,MS”解
4,约束
1) 人 ←→ "≤ " 因为每人至多指派一个项目
∑ x1 j ≤ 1 －－ T
∑ x2 j ≤ 1 －－ C
∑ x3 j ≤ 1 －－ M
2) 任务 ←→ "=" 因为每个项目必要有人做
∑ x i 1 = 1 －－项目 1
∑ x i 2 = 1 －－项目 2
∑ x i 3 = 1 －－项目 3
3) x i j = 0,1
5,计算机解
x 12 = x 23 = x 31 = 1,其余 x i j = 0,o.f,= 26 ( = 15 + 5 + 6 )。
第二节 指派问题凌晨,凌晨,
Ling Xueling
三,特殊情形的处理
1,S ≠ D
1) S > D 模型照旧
2) S < D 虚拟,人,,,人,可供量＝ D － S,o.f,系数 c i j
= 0
2,若干指派不可接收 （ 如：回避制度,不懂业务 ）
取消对应变量即可
3,多项指派的 ( 一到多 ) 处理假定 T 能力特别强,所以可以指派到二个委托人,则关于
T 的约束可更改为：
x 11 + x 12 + x 13 ≤ 2 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
B,指派问题：特殊解法一,概述因为是运输问题的 特 例,当然可用运输问题 特殊 解法加以求解,但下面介绍的 Hungarian 法更简单
1,Hungarian 法 (匈牙利法 )―― 矩阵缩减法依据此方法根据匈牙利数学家 D,Konig 一条关于矩阵性质的定理：,如果从系数矩阵 C = (c i j ) 的一行 （ 或列 ） 各元素分别减去该行 （ 或列 ） 的最小元素,得到新矩阵 B = (b i j )
,那么,以 B = (b i j ) 为系数矩阵的指派问题的最优解和原问题的最优解相同,发展而来－－等价化简 。
线性代数里的 等价 －－ 同解 方程第二节 指派问题凌晨,凌晨,
Ling Xueling
B,指派问题：特殊解法一,概述
2,Hungarian 法应用 前提
1)“人,数 ＝,项目,数即：要保证,1 ←→ 1,即：行数＝列数 （ 方阵 ）
2） 是求 min 的 问题
3,例子
F,营销 调研问题：
三个人 ←→ 三项任务 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
1,方法流程图
no
yes
第二节 指派问题凌晨,凌晨,
选最优解问题的矩阵表达缩减法等价化简最优？
Ling Xueling
二,解法
2,问题的矩阵形式第二节 指派问题凌晨,凌晨,
项目领导人
t
c
M
1 2 3
委托人
10 15 9
9 18 5
6 14 3
Ling Xueling
二,解法
3,步骤一 （ 利用缩减法简化成 等价 阵 ）
1） 做法在原矩阵中,从每行元素中减去该行的 最小 元素,然后从每列元素中减去该列的 最小 元素
2） 为什么是 等价 变换？ －－ 等价：机会损失因为：每个人总要指派一个项目,项目总要被指派一个人行变换－－对人而言,变换后的数表示 未 做最优安排时的多耗天数 （ 机会损失 ）
列变换－－对项目而言,变换后的数表示 未 作最优安排时的多耗天数 （ 机会损失 ） 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
3,步骤一 （ 简化成 等价 阵 ）
3） 具体变换
10 15 9 行 1 6 0 列 0 0 0
9 18 5 － → 4 13 0 － → 3 7 0
6 14 3 3 11 0 2 5 0
4,步骤二 ( 判断是否最优？ )
1） 说明 ( 以,0”为优 )
因为人与项目要 1 → 1,又因为要求最少天数,所以注意力要集中在那些数字,0”上,若能按人而言,每人指派一个,0”,当然即为最优解 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
4,步骤二 ( 判断是否最优？ )
2） 做法 ( 判断标准 )－－求 最小直线数求能覆盖所有 0 元素 （ 不要求覆盖的全部是 0 元素 ） 且贯通矩阵行或列的最小直线数若覆盖所用的最小直线数＝行数 （ 或列数 ）,则最优解已经求得,否则转入步骤三
3） 具体求如下第二节 指派问题凌晨,凌晨,
0 0 0
3 7 0
2 5 0
二条直线覆盖了所有的 0
Ling Xueling
二,解法
5,步骤三
1) 求出最小元,以 O 圈住,上面的 2 即是,称为 枢元
2) 未 覆盖元 减 去 O 内元素
3) 单 覆盖元不变
4) 双 覆盖元 加 上 O 内元素
5) 再 回到步骤二,得：
第二节 指派问题凌晨,凌晨,
0 0 2
1 5 0
0 3 0
已得最优解
Ling Xueling
二,解法
6,选最优解
1) 原则：每人都安排有 0 值的项目
2) 做法：先求仅含一个 0 元素的行或列,0 用 □ 画出,删去该行或列持续下去,可得：
即：最优解是,T － → 2,C－ → 3,M － → 1,o.f,= 15 + 5
+ 6 = 26 。
第二节 指派问题凌晨,凌晨,
1 2 3
0 0 2
1 5 0
0 3 0
T
C
M
Ling Xueling
二,解法
7,说明若每一行,每一列都包含不只一个,0” 时,多解 。 见下例例子 按 min 求下列分配 ( 指派 ) 问题最优解 （ 课堂联系 ）
13 5 10 8
0 11 1 7
2 1 3 4
11 0 2 6
解,13 5 10 8 8 0 5 3 8 0 4 0
0 11 1 7 行缩减 0 11 1 7 列缩减 0 11 0 4
2 1 3 4 -------- 1 0 2 3 ----- 1 0 1 0
11 0 2 6 11 0 2 6 11 0 1 3
第二节 指派问题凌晨,凌晨,
Ling Xueling
7,说明覆盖线数＝ 3 < 矩阵行数 4,故不能分配,最优解得不出,需进一步化简如下未覆盖元之 min=1 7 0 3 0
1) 未覆盖元－ 1 0 12 0 5 因为 4＝ 4
2) 双覆盖元＋ 1--- 0 0 0 0 可以分配了
10 0 0 2
最优方案 (一 ) (二 ) (三 ) (四 )
甲 → 2 甲 → 4 甲 → 4 甲 → 4
乙 → 1 乙 → 1 乙 → 3 乙 → 1
丙 → 4 丙 → 3 丙 → 1 丙 → 2
丁 → 3 丁 → 2 丁 → 2 丁 → 3
各方案 统一 的 o.f,= 77。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
8,关于最小直线数的求法选择有 单个 0 元素的行或列,若是 行,则作通过此 0
元素所在 列 的直线,若是 列,作通过此 0 元素所在 行的直线,持续下去,直到所有 0 元素被覆盖三,特殊情况处理
1,人数和任务数不相等添 虚拟 行或虚拟列,元素取数值,0” 即可 。 注意：
行数＝列数是 Hungarian 法之 必要,但不要同时添加虚拟行和虚拟列 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
2,最大化问题－－考虑一个例子
1） 问题
S.D,公司刚刚租借到一家商店,尚有五个柜台,四个位置没有安排：
五个柜台分别是：鞋子,玩具,汽车部件,日杂和唱片柜台四个位置分别标号为,1,2,3,4
目标：不同柜台安排在不同位置时,预期的利润不一样,调研和经验数据表明 （ 单位：千 ）
位 置
1 2 3 4 5虚拟柜台 1 鞋子 10 6 12 8 0
柜台 2 玩具 15 18 5 11 0
柜台 3 汽车部件 17 10 13 16 0
柜台 4 日杂 14 12 13 10 0
柜台 5 唱片 14 16 6 12 0
第二节 指派问题凌晨,凌晨,
Ling Xueling
2,最大化问题－－考虑一个例子
2） (方 ） 矩阵化
3） 化成 min 问题 －－将所有元素转变成 机会损失 ( 利润 )
(1) 方法,每一 列 中每个元素都被该列元素中的最 大 元去减
(2) 新矩阵意义：
元素－－机会损失,可证：最小机会损失的指派与原问题最大化等价,同解
(3) 机会损失阵 1 2 3 4 5 ( dummy )
鞋子 7 12 1 8 0
玩具 2 0 8 5 0
部件 0 8 0 0 0
日杂 3 6 0 6 0
唱片 3 2 7 4 0
第二节 指派问题凌晨,凌晨,
Ling Xueling
2,最大化问题－－考虑一个例子
3） 化成 min 问题 －－将所有元素转变成 机会损失 ( 利润 )
(4)按 Hungarian 法求最小机会损失,可得 （ 课堂练习 ）,
鞋子 → 5,玩具 → 2,汽车部件 → 4,日杂 → 3,唱片 → 1
3,有不可接受的指派
1) max 问题：对不可接收之指派,定义其利润 ( 或其它指标 ) 为 － M
2) min 问题：不可接收之指派定义其元素值为 M
例如：若上述问题中经理认为：玩具柜不能考虑放在 2
号位置,汽车部件柜不能考虑放在 4 号位置,则上述指派矩阵变成,(元素＝利润值 )
第二节 指派问题凌晨,凌晨,
Ling Xueling
3,有不可接受的指派
1 2 3 4 5 ( dummy )
鞋子 10 6 12 8 0
玩具 15 － M 5 11 0
部件 17 10 13 － M 0
日杂 14 12 13 10 0
唱片 14 16 6 12 0
第二节 指派问题凌晨,凌晨,
Ling Xueling
一,概述
1,三种节点：起运点,转运点,目的点
2,特点货运可以从任何三种类型的点之间任意点间进行
3,处理原则
1) 起运点,可供量有限,可以有多余 ←→,≤,
2) 转运点,进出平衡 ←→,=,
3) 目的点,需求量有限,满足即可 ←→,=,。
第三节 转运问题凌晨,凌晨,
Ling Xueling
二,例子
R 电子公司在苏州,广州各有一家工厂,在武汉,郑州各有一家仓库 （ 转运点 ）,在昆明,兰州,北京,青岛各有一家零售店
1,转运网络第三节 转运问题凌晨,凌晨,
苏州广州武汉郑州昆明兰州北京青岛
6 00
4 00
1
2
3
4
5
6
7
8
2 00
150
350
3 00
Ling Xueling
二,例子
2,网络各路径单位运输成本仓库武汉 郑州工厂 苏州 2 3
工厂 广州 3 1
零售点昆明 兰州 北京 青岛武汉仓库 2 6 3 6
郑州仓库 4 4 6 5
如何建立 L.P,模型？
第三节 转运问题凌晨,凌晨,
Ling Xueling
三,L.P,模型为每一条弧指定一个变量,为每一个结点指定一个约束
1,决策变量,x i j －－ i 节点 至 j 节点之运量
2,o.f,∑∑ c i j x i j c i j －－ 运输单位成本
3,约束 ( 按节点逐个求 )
1) 工厂－－,≤,
x13 + x14 ≤ 600
x23 + x24 ≤ 400
第三节 转运问题凌晨,凌晨,
Ling Xueling
三,L.P,模型
3,约束 ( 按节点逐个求 )
2) 仓库－－进出平衡－－,＝,
x35 + x36 + x37 + x38 = x13 + x23
x45 + x46 + x47 + x48 = x14 + x24
3) 零售点－－满足－－,=”
x35 + x45 = 200
x36 + x46 = 150
x37 + x47 = 350
x38 + x48 = 300
4) 非负约束 x i j ≥ 0
第三节 转运问题凌晨,凌晨,
Ling Xueling
三,L.P,模型
4,说明 ( 注意掌握 )
1) 约束式按节点逐个求出即可
2) 起运点－－可供量 ≤
中转点－－进出平衡 =
目的地－－需求满足 =
3) 对 有限制的路径只要增加约束：
x i j ≤ b －－限制量
4) 有多种特殊解法－－不介绍了 。
第三节 转运问题凌晨,凌晨,
Ling Xueling
四,转运模型在物流管理方面的应用
1,例子
C.C,公司在今后四个季度内的产能,市场需求,每季度生产成本及库存成本如下表所示,(单位：平方码 )
季度 产能 需求 生产成本 库存成本
1 600 400 2 0.25
2 300 500 5 0.25
3 500 400 3 0.25
4 400 400 3 0.25
公司要决策：如何安排今后四个季度生产计划及库存策略可以使生产,库存之 总 成本最小 。 如何建模？
第三节 转运问题凌晨,凌晨,
Ling Xueling
2,问题的网络表达第三节 转运问题凌晨,凌晨,
1
第一季度生产第二季度生产第三季度生产第四季度生产第一季度需求第二季度需求第三季度需求第四季度需求
2
5
6
3
4
7
8
6 0 0
3 0 0
5 0 0
4 0 0
4 0 0
4 0 0
5 0 0
4 0 0
生产结点 需求结点生产产能 需求
2
5
3
3
生产成本
0,2 5
0,2 5
0,2 5
库存成本
Ling Xueling
3,网络特点结点 5,6,7,8 既可视作转运问题中的 中转点,
又可视为其中的 目的地,在这样的考虑之下,容易得到以下的 L.P,模型：
4,建模 ( L.P,模型 )－－为每一 结点 建立一个 约束,为每一 弧 指定一 变量
1） 决策变量令 x i j = 结点 i 至结点 j 的产品 流量
2） o.f.－－总成本最小
Min 2x15 + 5x26 + 3x37 + 3x48 + 0.25x56 + 0.25x67 + 0.25x78
第三节 转运问题凌晨,凌晨,
Ling Xueling
4,建模 ( L.P,模型 ）
3） 约束
(1) 生产结点 （ 产能限制 ）
x 15 ≤ 600
x 26 ≤ 300
x 37 ≤ 500
x 48 ≤ 400
(2) 需求结点－－进出平衡,进货量－库存量 ＝ 需求量
x 15 － x 56 = 400
x 26 + x 56 － x 67 = 500
x 37 + x 67 － x 78 = 400
x 48 + x 78 = 400
(3) 非负约束 x i j ≥ 0 任意 i 和 j
第三节 转运问题凌晨,凌晨,
Ling Xueling
5,求解总成本,o.f,= 5150
生产计划,x15 = 600 x26 = 300
x37 = 400 x48 = 400
库存成本,x 56 = 200 x 67 = 0 x 78 = 0。
第三节 转运问题凌晨,凌晨,
Ling Xueling
The End of Chapter 6
运输,指派和转运问题,实际上都可以用
L.P,模型加以描述,所以可以认为它们是
L.P,的特例单列一章的原因在于：应用面极广,实践性很强,而特有的数学结构使得人们设计出了特别有效的方法对此类模型进行求解本章的重点在：掌握表格化方法 求解 运输,
指派,转运问题的模型 。
第六章 运输、指派和转运问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
1,运输问题的概念问题 －－从 m 个起运点 （ origin） 到 n 个目的地 （
destination） 的 货物 和 服务 的 分配 计划起运点特征 －－可供量有限,无法 （ 不能 ） 超过目的地特征 －－需求量有限,满足即可分配 －－因为不同路径往往成本不相同,才有优化的必要优化目标 －－成本最低,运费最小,或利润最大 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
P&T 公司分销问题,地图
C A N N E R Y 1
B e l l i n g h a m
C A N N E R Y 2
E u g e n e
W A R E H O U S E 1
S a c r a m e n t o
W A R E H O U S E 2
S a l t L a k e C i t y
W A R E H O U S E 3
R a p i d C i t y
W A R E H O U S E 4
A l b u q u e r q u e
C A N N E R Y 3
A l b e r t L e a
Ling Xueling
P&T 公司分销问题,运输量与成本数据
300 车合计
85 车Albuquerque300 车合计
70 车Rapid City100 车Albert Lea
65 车Salt Lake City125 车Eugene
80 车Sacramento75 车Bellingham
分配量仓库产量罐头加工厂
685388682995Albert Lea
791690416352Eugene
$867$654$513$464Bellingham
罐头加工厂
AlbuquerqueRapid CitySalt Lake CitySacramento从 \ 到仓库
Ling Xueling
P&T 公司分销问题,无算法的方案
851500Albert Lea
055655Eugene
00075Bellingham
罐头加工厂
AlbuquerqueRapid CitySalt Lake CitySacramento从 \ 到仓 库
决策模型：就近原则（观察运输成本）
– Bellingham加工厂离仓库最远，将其产品运到最近仓库 Sacramento；
若 Bellingham加工厂有剩余，则送到 Salt Lake City。
– Albuquerque仓库离加工厂最远，从距其最近的 Albert Lea加工厂产品送货；
若 Albert Lea加工厂有剩余，则送到 Rapid City。
–Eugene加工厂的产品满足其它仓库的剩余需求。
总运输成本 = 75($464) + 5($352) + 65($416) + 55($690) + 15($388) + 85($685) = $165,595
Ling Xueling
P&T 公司分销问题,还有成本更低的方案吗?
总运输成本 = 20($513) + 55($867) + 80($352) + 45($416) + 70($388) + 35($685)
= $152,535
降低 $13060,约 8%!
P & T 公司配送问题单位成本 目的地（仓库）
萨克拉门托 盐湖城 赖皮特城 奥尔巴古出发地 贝林翰 $464 $513 $654 $867
( 罐头工厂 ) 尤基尼 $352 $416 $690 $791
艾尔贝·李 $995 $682 $388 $685
运输量 目的地（仓库）
卡车装载 萨克拉门托 盐湖城 赖皮特城 奥尔巴古 总运出量出发地 贝林翰 0 20 0 55 75
( 罐头工厂 ) 尤基尼 80 45 0 0 125
艾尔贝·李 0 0 70 30 100
总运入量 80 65 70 85
= = = =
需求量 80 65 70 85
Ling Xueling
一,运输问题及其常规解法
2,例子
1） 有关数据
Foster 公司在全国不同地方有三家工厂 O1,O2,O3,四家地区零售中心 D1,D2,D3,D4,未来 3 个月供需数据如下工厂 三个月 销售中心 三个月生产能力 需求预测
O1 5000 D1 6000
O2 6000 D2 4000
O3 2500 D3 2000
13500 D4 1500
13500
第一节 运输问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
2） 可用运输路径 （ 由 结点,弧 构成的网络图 ）
第一节 运输问题凌晨,凌晨,
1
2
3
1
2
3
4
5 0 0 0
6 0 0 0
2 5 0 0
6 0 0 0
4 0 0 0
2 0 0 0
1 5 0 0
a r c s
n od e s
n e t w or k
源结点目的结点
Ling Xueling
一,运输问题及其 常规 解法
3） 各路径单位运输成本数据 (Cij 数据－－弧之 权 )
目的地起运点 D1 D2 D3 D4
O1 3 2 7 6
O2 7 5 2 3
O3 2 5 4 5
4 ） 假定 ( 以后再逐步放松 )
（ 1） 三家工厂的生产成本一样,仅仅运输成本可变
（ 2） ( 隐含假定 ) 。
第一节 运输问题凌晨,凌晨,
ji DO
Ling Xueling
一,运输问题及其常规解法
3,模型 ( 运输问题的 L.P.)
建模一般原则,为每一 弧 指定一个 变量,为每一 结点 指定一个 约束式
1） 决策变量 xij －－ 从 Oi 到 Dj 的运输量
2） o.f,Min
3） 约束 供方－－,?” 需方－－,＝,。
第一节 运输问题凌晨,凌晨,
jiij xc
Ling Xueling
一,运输问题及其常规解法
3,模型 ( 运输问题的 L.P.)
min ∑∑ c i j x i j
s.t.
x11 + x12 + x13 + x14 ≤ 5000 O1
x21 + x22 + x23 + x24 ≤ 6000 O2
x31 + x32 + x33 + x34 ≤ 2500 O3
x11 + x21 + x31 = 6000 D1
x12 + x22 + x32 = 4000 D2
x13 + x23 + x33 = 2000 D3
x14 + x24 + x34 = 1500 D4
xi j ≥ 0
第一节 运输问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
4,计算机求解及其特点
x11 = 3500 x12 = 1500 x22 = 2500
x23 = 2000 x24 = 1500 x31 = 2500
其余 xij = 0 o.f,= 39500
注意：最优解值都是 整数 ！ 巧合？
5,定理若所有起运点的供货量和目的地的需求量都是 整数的话,运输,指定,转运问题的解也总是 整 数值 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
一,运输问题及其常规解法
6,特殊情况及其处理
1）
（ 1） S > D,不必修改模型,过剩供给会在最优解中以松弛 反应出来
（ 2） S < D,必须修改模型,（ a） 引入一个虚拟起运点其供给量 ＝ D － S （ b） 从虚拟起点到任意一个目的地 Dj 之运输成本指定为 0 （ 不影响 o.f,）
2） 求最大化若 cij 表示的是单位利润和收入,只需相应改变 o.f,即可
3） 有的路径无法使用：取消相关的 xij 即可 。
第一节 运输问题凌晨,凌晨,
ji DO
Ling Xueling
一,运输问题及其常规解法
7,运输问题一般 L.P,模型供 方结点需 方结点第一节 运输问题凌晨,凌晨,
0
).,,,,,2,1(
).,,,,,2,1(
..
m i n
1
1
ij
m
i
jij
n
j
iij
ijij
x
njDx
miOx
ts
xc
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
1,方法比较
1） L.P,方法－－只能使用于小,中型问题 （ 若有 100 个起运点和 1000 个目的地时,变量将有 100,000 个 ）
2） 特殊解法－－ 可以 简化计算,对大型问题更有效率
2,特殊解法的思路首先将问题用 表格形式 予以表达? 随意 求一个 初始可行 解
然后进行 迭代 以改善解?直到求出 最优解 为止
3,例子及其表格作业法求解
1） 例子
Foster公司 3 个 origins 和 4 个 destinations之例 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
3,例子及其表格作业法求解
2） 运输表形如下列形式的表格称为 运输表,（ 注,空格对应于 12条路径 ）
第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 5000
7 5 2 3
O2 6000
2 5 4 5
O3 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
3,例子及其表格作业法求解
3） 运输表的意义
（ 1） 方便收集资料 / 数据
（ 2） 保持运算 轨迹
4,（ 最小成本法 ） 求 初始可行 解
1） 思路
1) 对最小成本路径,安排尽可能多的货物
2) 若有相同的最低成本路径,优先选择运量最 大 的方格－－路径 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
4,（ 最小成本法 ） 求初始可行解
2） 表上作业可得运输方案及相关成本如下：
总成本,42000
第一节 运输问题凌晨,凌晨,
从 至 运输单位 单位成本 成本
o1 - - - - - - - - - - d1 1000 3 3000
o1 - - - - - - - - - - d2 4000 2 8000
o2 - - - - - - - - - - - d1 2500 7 17500
o2 - - - - - - - - - - d3 2000 2 4000
o2 - - - - - - - - - - - d4 1500 3 4500
o3 - - - - - - - - - - - d1 2500 2 5000
Ling Xueling
二,运输问题及其特殊 的 表格作业法 求解
4,（ 最小成本法 ） 求初始可行解
3） 求初始可行解要保证利用 m + n－ 1 条路径
（ 1） 例子第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
6 8 3 10
O1 30
2 9 5 7
O2 15
7 8 6 4
O3 15
μ? μ? Dè?ó á? 10 25 10 15 60
Ling Xueling
4,（ 最小成本法 ） 求初始可行解
3） 求初始可行解要保证利用 m + n－ 1 条路径
（ 2） 为什么求出初始可行解以后向最优解进行 迭代之必须
（ 3） 调整方法上例中,最后一次运输安排时剩余的行供量和列需量 同时减为零,若此情形发生在安排最后路径以前,则所得初始可行解所利用的路径就会不足 m + n－ 1。 可调整如下：
( i ) 将出问题的行和列分别用横,竖直线划去
( ii ) 额外指定一个零单位运输计划到所划横或竖线上的 任意一个空格 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
4,（ 最小成本法 ） 求初始可行解
4） 求初始可行解的其它方法常用如西北角法,差额法等等,除非运气特别好,一般都需要迭代,只是步骤数量的差异
5,从初始可行解到 最优解 的踏石法
1） 方法思路
（ 1） 对所有 未利用 路径做试探性运量安排
（ 1） 若能使总成本下降,可考虑作为新路径安排运输量
( 2） 若使总成本上升,该路径当然作罢不用
（ 2） 迭代停止准则：
所有未用路径一当被安排运量,即使总成本上升,则当前解当然就是最优解了 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
2） 例子,试探及结果
（ 1） Foster 公司之初始可行解
（ 2） 试探：在未用路径 o2 ---- d2,安排一个单位运量,则第一节 运输问题凌晨,凌晨, μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1001 3999 5000
7 5 2 3
O2 2499 1 2000 1500 6000
2 5 4 5
O3 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
5,从初始可行解到最优解的踏石法
2） 例子,试探及结果
（ 3） 微调之对成本影响 ( net effect )
对成本之影响
O2 － D2 加 1 单位 ＋ 5
O1 － D2 减 1 单位 － 2
O1 － D1 加 1 单位 ＋ 3
O2 － D1 减 1 单位 － 7
net effect = － 1.
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
3） 踏石回路－－对新路径进行试探的一般方法实际上是换基的方法,是代数的迭代换基之表上作业法目的：
求出每一条未用路径,入基,－－安排运输－－对成本之影响方法：
(1) 石－－当前解,只有 当前解可以作为基,可以作为石
(2) 踏石－－ 可以在石头之间跳跃,但只能 跳奇数块石头
(3) 定要构成回路－－ 可以是折线构成的回路
(4) 顺或逆时钟方向 踏石都可以例子及结果对所有新路径要计算出：入基后对成本的净变化,如后所示 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
3） 踏石回路－－对新路径进行试探的一般方法第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1000 4000 ( ￡? 9) ( ￡? 7) 5000
7 ( ￡- 1) 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 ( ￡? 4 ) ( ￡? 7) ( ￡? 7) 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
5,从初始可行解到最优解的踏石法
4） 调整运输方案如何调整？ 是不言而喻的,当然是对 o2 ---- d2 作出 尽可能多的运量安排第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 3500 1500 5000
7 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
5,从初始可行解到最优解的踏石法
5） 计算所有 新 （ 未用 ） 路径的净变化及踏石回路,
结果如下：
第一节 运输问题凌晨,凌晨,
d1 d2 d3 d4
o1 3 5 0 0 - - - - - - - - - - - - - - - - - - - 1 5 0 0 ( 8 ) ( 6 )
o2 ( 1 ) 2 5 0 0 - - - - - - - - - - - - - - - - - - 2 0 0 0 1 5 0 0
o3 2 5 0 0 - - - - - - - - - - - - - - - - - - - - - ( 4 ) - - - - - - - - - - - - - - - - - - - - - ( 6 ) ( 6 )
Ling Xueling
5,从初始可行解到最优解的踏石法
6） 最优解当所有新的路径所对应的方格的单位 净变化 皆 ≥ 0 时,
最优解也就求得了此例的最优解是：
x11 = 3500 x12 = 1500 x22 = 2500
x23 = 2000 x24 = 1500 x31 = 2500
其余 xij = 0 o.f,= 39500（ 总成本 ）
与 L.P,模型的计算机 解相同 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
7） 踏石法中也要始终保持 m + n－ 1 条运输路径被得到利用为什么？
路径少,则踏石法中,石头,少,走回路会发生困难解决因为 0 单位物流也可作为一个运输方案,所以若有现有解同时被减少至 0 单位物流时,只需择其一添,0”,仍作为,现有解,－－留在基内例子
1) 初始解第一节 运输问题凌晨,凌晨,
Ling Xueling
5,从初始可行解到最优解的踏石法
7） 踏石法中也要始终保持 m + n－ 1 条运输路径被得到利用例子
1) 初始解第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1000 2500 3500
7 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 2500 2000 1500
Ling Xueling
5,从初始可行解到最优解的踏石法
7） 踏石法中也要保持 m + n－ 1 条运输路径被得到利用例子
2) 调整
o2 ---- d2 安排 2500 单位,这使得表格变为：
第一节 运输问题凌晨,凌晨,
μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 3500 3500
7 5 2 3
O2 0 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 2500 2000 1500 12,0 00
Ling Xueling
6,修正分布法－－求净变化的另一种有效方法
1） 从 c i j = u i + v j 对 已占 方格 定出 u i v i ( 待求 )
对上例,对 已占 方格可得：
u 1 + v 1 = 3,u 1 + v 2 = 2,u 2 + v 1 = 7,u 2 + v 3 = 2,
u 2 + v 4 = 3,u 3 + v 1 = 2,再令,u 1 = 0 可 得各 u i v i 值 。
第一节 运输问题凌晨,凌晨, μ? μe μ?
D1 D2 D3 D4?é 1? á?
3 2 7 6
O1 1000 4000 5000
7 5 2 3
O2 2500 2000 1500 6000
2 5 4 5
O3 2500 2500
μ? μ? Dè?ó á? 6000 4000 2000 1500 13,5 00
Ling Xueling
6,修正分布法－－求净变化的另一种有效方法
1） 从 c i j = u i + v j 对 已占 方格 定出 u i v i ( 待求 )
因为 u 1 = 0
则 u 2 = 4,u 3 = － 1,v 1 = 3,
v 2 = 2,v 3 = － 2,v 4 = － 1
2） 从 e i j = c i j － u i － v j 又可 得 空方格 （ 数学可证明 ） 之净变化为：
e 13 = 9,e 14 = 7,e 22 = － 1,e 32 = 4,e 33 = 7,e 34 = 7
与踏石法所得结果一致 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理
1） 总供给 ≠ 总需求统一处理为,1)引入一个虚拟起点或虚拟目标
2) 虚拟 可供量或需求量＝差额
3) 虚拟单位运输成本＝ 0 （ 虚拟成本 ）
2） 最大化问题 ( 如求运输利润等问题 )
（ 1） 入基空方格：净变化最大者＝ max e i j ( 正值 )
e i j > 0
（ 2） 停止迭代准则,所有 e i j ≤ 0 。
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理
3） 存在不能利用的运输路径
（ 1） 对 min 问题：指定一个极高的单位成本,M > 0
（ 2） 对 max 问题：指定一个 （ － M） ( M > 0,|M| 极大 )
特殊情况例子
a) 起点：三个工厂,生产能力不同工厂 P1 P2 P3
生产能力 50 40 30
b)目的地：三个零售点,需求预测如下零售点 R1 R2 R3
需求预测 45 15 30
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理例子
c) 利润：由于工厂的生产成本,零售点售价,运输成本可能不同,综合后得到如下利润表
R1 R2 R3
P1 2 8 10
P2 6 11 6
P3 12 7 9
d） 运输表 （ 最大化问题 ）
因为 S > D,S － D = 30,所以虚拟需求量为 30 的 R4,得 初始可行方案为：
第一节 运输问题凌晨,凌晨,
Ling Xueling
7,特殊情况的处理例子注：求出的 e i j 已 在上表中标出,o.f,( 最大利润 ) ＝ 915
迭代停止,因为是求 max,而所有 e i j < 0,所以认为已求得最优解 。 注意,P1 处留 20,P2 处留 10 单位剩余不运出 。
第一节 运输问题凌晨,凌晨,目的地
R1 R2 R3 R4 Supp ly
2 8 10 0 50
O1 ( － 4) ( － 3) 30 20 20
6 11 6 0 40
O2 15 15 ( － 4) 10 10
12 7 9 0 30
O3 30 ( － 10) ( － 7) ( － 6) 0
D e ma nd 4 5 1 5 1 5 0 3 0 0 30
Ling Xueling
指派－－如：对人员指派项目,机器指派加工任务,对不同公司指派业务,不同航线指派不同船只运输,不同仓库调运物资到指派市场,投标中指派条款,....
解法中强调－－ 1 ←→ 1,仅指派于一个项目目标－－最小成本,最少时间,最大利润,.....
第二节 指派问题凌晨,凌晨,
Ling Xueling
A,常规解法 ( L.P,解法 )
一,问题及假定
1,F,营销 调研公司新近接到三家委托公司要作营销调研项目；
2,F,公司初步评估,T,C 和 M 三人可作为三个项目的组长；
3,三个项目的优先等级大致相同,所以可将项目完成天数 作为评估三个人工作指派的优劣标准
4,三个人对三个项目的能力各不相同,如下表 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
A,常规解法 ( L.P,解法 )
一,问题及假定委 托 人
1 2 3
项目 T 10 15 9
领导 C 9 18 5
人 M 6 14 3
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,建模与,MS”解
1,与运输问题进行比较 ( L.P,之比较 )
若视 人 ←→ 起点 各 （ 人 ） 供给量 ＝ 1
项目 ←→ 目标 各 （ 项目 ） 需求量 ＝ 1
则指派问题是运输问题的 特例 －－当然应有更 特殊 的解法第二节 指派问题凌晨,凌晨,
t
t
c
m
1
2
3
1
1
1
1
1
1
供 需
Ling Xueling
二,建模与,MS”解建模原则还是：为每一条弧指定一个变量,为每一个结点确定一个约束
2,决策变量
x i j = 1 －－第 i 人指派于第 j 项目
0 －－否则
3,o.f,( 总天数最少 )
min 10 x11 + 15 x12 + 9 x13
+ 9 x21 + 18 x22 + 5 x23
+ 6 x31 + 14 x32 + 3 x33
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,建模与,MS”解
4,约束
1) 人 ←→ "≤ " 因为每人至多指派一个项目
∑ x1 j ≤ 1 －－ T
∑ x2 j ≤ 1 －－ C
∑ x3 j ≤ 1 －－ M
2) 任务 ←→ "=" 因为每个项目必要有人做
∑ x i 1 = 1 －－项目 1
∑ x i 2 = 1 －－项目 2
∑ x i 3 = 1 －－项目 3
3) x i j = 0,1
5,计算机解
x 12 = x 23 = x 31 = 1,其余 x i j = 0,o.f,= 26 ( = 15 + 5 + 6 )。
第二节 指派问题凌晨,凌晨,
Ling Xueling
三,特殊情形的处理
1,S ≠ D
1) S > D 模型照旧
2) S < D 虚拟,人,,,人,可供量＝ D － S,o.f,系数 c i j
= 0
2,若干指派不可接收 （ 如：回避制度,不懂业务 ）
取消对应变量即可
3,多项指派的 ( 一到多 ) 处理假定 T 能力特别强,所以可以指派到二个委托人,则关于
T 的约束可更改为：
x 11 + x 12 + x 13 ≤ 2 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
B,指派问题：特殊解法一,概述因为是运输问题的 特 例,当然可用运输问题 特殊 解法加以求解,但下面介绍的 Hungarian 法更简单
1,Hungarian 法 (匈牙利法 )―― 矩阵缩减法依据此方法根据匈牙利数学家 D,Konig 一条关于矩阵性质的定理：,如果从系数矩阵 C = (c i j ) 的一行 （ 或列 ） 各元素分别减去该行 （ 或列 ） 的最小元素,得到新矩阵 B = (b i j )
,那么,以 B = (b i j ) 为系数矩阵的指派问题的最优解和原问题的最优解相同,发展而来－－等价化简 。
线性代数里的 等价 －－ 同解 方程第二节 指派问题凌晨,凌晨,
Ling Xueling
B,指派问题：特殊解法一,概述
2,Hungarian 法应用 前提
1)“人,数 ＝,项目,数即：要保证,1 ←→ 1,即：行数＝列数 （ 方阵 ）
2） 是求 min 的 问题
3,例子
F,营销 调研问题：
三个人 ←→ 三项任务 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
1,方法流程图
no
yes
第二节 指派问题凌晨,凌晨,
选最优解问题的矩阵表达缩减法等价化简最优？
Ling Xueling
二,解法
2,问题的矩阵形式第二节 指派问题凌晨,凌晨,
项目领导人
t
c
M
1 2 3
委托人
10 15 9
9 18 5
6 14 3
Ling Xueling
二,解法
3,步骤一 （ 利用缩减法简化成 等价 阵 ）
1） 做法在原矩阵中,从每行元素中减去该行的 最小 元素,然后从每列元素中减去该列的 最小 元素
2） 为什么是 等价 变换？ －－ 等价：机会损失因为：每个人总要指派一个项目,项目总要被指派一个人行变换－－对人而言,变换后的数表示 未 做最优安排时的多耗天数 （ 机会损失 ）
列变换－－对项目而言,变换后的数表示 未 作最优安排时的多耗天数 （ 机会损失 ） 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
3,步骤一 （ 简化成 等价 阵 ）
3） 具体变换
10 15 9 行 1 6 0 列 0 0 0
9 18 5 － → 4 13 0 － → 3 7 0
6 14 3 3 11 0 2 5 0
4,步骤二 ( 判断是否最优？ )
1） 说明 ( 以,0”为优 )
因为人与项目要 1 → 1,又因为要求最少天数,所以注意力要集中在那些数字,0”上,若能按人而言,每人指派一个,0”,当然即为最优解 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
4,步骤二 ( 判断是否最优？ )
2） 做法 ( 判断标准 )－－求 最小直线数求能覆盖所有 0 元素 （ 不要求覆盖的全部是 0 元素 ） 且贯通矩阵行或列的最小直线数若覆盖所用的最小直线数＝行数 （ 或列数 ）,则最优解已经求得,否则转入步骤三
3） 具体求如下第二节 指派问题凌晨,凌晨,
0 0 0
3 7 0
2 5 0
二条直线覆盖了所有的 0
Ling Xueling
二,解法
5,步骤三
1) 求出最小元,以 O 圈住,上面的 2 即是,称为 枢元
2) 未 覆盖元 减 去 O 内元素
3) 单 覆盖元不变
4) 双 覆盖元 加 上 O 内元素
5) 再 回到步骤二,得：
第二节 指派问题凌晨,凌晨,
0 0 2
1 5 0
0 3 0
已得最优解
Ling Xueling
二,解法
6,选最优解
1) 原则：每人都安排有 0 值的项目
2) 做法：先求仅含一个 0 元素的行或列,0 用 □ 画出,删去该行或列持续下去,可得：
即：最优解是,T － → 2,C－ → 3,M － → 1,o.f,= 15 + 5
+ 6 = 26 。
第二节 指派问题凌晨,凌晨,
1 2 3
0 0 2
1 5 0
0 3 0
T
C
M
Ling Xueling
二,解法
7,说明若每一行,每一列都包含不只一个,0” 时,多解 。 见下例例子 按 min 求下列分配 ( 指派 ) 问题最优解 （ 课堂联系 ）
13 5 10 8
0 11 1 7
2 1 3 4
11 0 2 6
解,13 5 10 8 8 0 5 3 8 0 4 0
0 11 1 7 行缩减 0 11 1 7 列缩减 0 11 0 4
2 1 3 4 -------- 1 0 2 3 ----- 1 0 1 0
11 0 2 6 11 0 2 6 11 0 1 3
第二节 指派问题凌晨,凌晨,
Ling Xueling
7,说明覆盖线数＝ 3 < 矩阵行数 4,故不能分配,最优解得不出,需进一步化简如下未覆盖元之 min=1 7 0 3 0
1) 未覆盖元－ 1 0 12 0 5 因为 4＝ 4
2) 双覆盖元＋ 1--- 0 0 0 0 可以分配了
10 0 0 2
最优方案 (一 ) (二 ) (三 ) (四 )
甲 → 2 甲 → 4 甲 → 4 甲 → 4
乙 → 1 乙 → 1 乙 → 3 乙 → 1
丙 → 4 丙 → 3 丙 → 1 丙 → 2
丁 → 3 丁 → 2 丁 → 2 丁 → 3
各方案 统一 的 o.f,= 77。
第二节 指派问题凌晨,凌晨,
Ling Xueling
二,解法
8,关于最小直线数的求法选择有 单个 0 元素的行或列,若是 行,则作通过此 0
元素所在 列 的直线,若是 列,作通过此 0 元素所在 行的直线,持续下去,直到所有 0 元素被覆盖三,特殊情况处理
1,人数和任务数不相等添 虚拟 行或虚拟列,元素取数值,0” 即可 。 注意：
行数＝列数是 Hungarian 法之 必要,但不要同时添加虚拟行和虚拟列 。
第二节 指派问题凌晨,凌晨,
Ling Xueling
2,最大化问题－－考虑一个例子
1） 问题
S.D,公司刚刚租借到一家商店,尚有五个柜台,四个位置没有安排：
五个柜台分别是：鞋子,玩具,汽车部件,日杂和唱片柜台四个位置分别标号为,1,2,3,4
目标：不同柜台安排在不同位置时,预期的利润不一样,调研和经验数据表明 （ 单位：千 ）
位 置
1 2 3 4 5虚拟柜台 1 鞋子 10 6 12 8 0
柜台 2 玩具 15 18 5 11 0
柜台 3 汽车部件 17 10 13 16 0
柜台 4 日杂 14 12 13 10 0
柜台 5 唱片 14 16 6 12 0
第二节 指派问题凌晨,凌晨,
Ling Xueling
2,最大化问题－－考虑一个例子
2） (方 ） 矩阵化
3） 化成 min 问题 －－将所有元素转变成 机会损失 ( 利润 )
(1) 方法,每一 列 中每个元素都被该列元素中的最 大 元去减
(2) 新矩阵意义：
元素－－机会损失,可证：最小机会损失的指派与原问题最大化等价,同解
(3) 机会损失阵 1 2 3 4 5 ( dummy )
鞋子 7 12 1 8 0
玩具 2 0 8 5 0
部件 0 8 0 0 0
日杂 3 6 0 6 0
唱片 3 2 7 4 0
第二节 指派问题凌晨,凌晨,
Ling Xueling
2,最大化问题－－考虑一个例子
3） 化成 min 问题 －－将所有元素转变成 机会损失 ( 利润 )
(4)按 Hungarian 法求最小机会损失,可得 （ 课堂练习 ）,
鞋子 → 5,玩具 → 2,汽车部件 → 4,日杂 → 3,唱片 → 1
3,有不可接受的指派
1) max 问题：对不可接收之指派,定义其利润 ( 或其它指标 ) 为 － M
2) min 问题：不可接收之指派定义其元素值为 M
例如：若上述问题中经理认为：玩具柜不能考虑放在 2
号位置,汽车部件柜不能考虑放在 4 号位置,则上述指派矩阵变成,(元素＝利润值 )
第二节 指派问题凌晨,凌晨,
Ling Xueling
3,有不可接受的指派
1 2 3 4 5 ( dummy )
鞋子 10 6 12 8 0
玩具 15 － M 5 11 0
部件 17 10 13 － M 0
日杂 14 12 13 10 0
唱片 14 16 6 12 0
第二节 指派问题凌晨,凌晨,
Ling Xueling
一,概述
1,三种节点：起运点,转运点,目的点
2,特点货运可以从任何三种类型的点之间任意点间进行
3,处理原则
1) 起运点,可供量有限,可以有多余 ←→,≤,
2) 转运点,进出平衡 ←→,=,
3) 目的点,需求量有限,满足即可 ←→,=,。
第三节 转运问题凌晨,凌晨,
Ling Xueling
二,例子
R 电子公司在苏州,广州各有一家工厂,在武汉,郑州各有一家仓库 （ 转运点 ）,在昆明,兰州,北京,青岛各有一家零售店
1,转运网络第三节 转运问题凌晨,凌晨,
苏州广州武汉郑州昆明兰州北京青岛
6 00
4 00
1
2
3
4
5
6
7
8
2 00
150
350
3 00
Ling Xueling
二,例子
2,网络各路径单位运输成本仓库武汉 郑州工厂 苏州 2 3
工厂 广州 3 1
零售点昆明 兰州 北京 青岛武汉仓库 2 6 3 6
郑州仓库 4 4 6 5
如何建立 L.P,模型？
第三节 转运问题凌晨,凌晨,
Ling Xueling
三,L.P,模型为每一条弧指定一个变量,为每一个结点指定一个约束
1,决策变量,x i j －－ i 节点 至 j 节点之运量
2,o.f,∑∑ c i j x i j c i j －－ 运输单位成本
3,约束 ( 按节点逐个求 )
1) 工厂－－,≤,
x13 + x14 ≤ 600
x23 + x24 ≤ 400
第三节 转运问题凌晨,凌晨,
Ling Xueling
三,L.P,模型
3,约束 ( 按节点逐个求 )
2) 仓库－－进出平衡－－,＝,
x35 + x36 + x37 + x38 = x13 + x23
x45 + x46 + x47 + x48 = x14 + x24
3) 零售点－－满足－－,=”
x35 + x45 = 200
x36 + x46 = 150
x37 + x47 = 350
x38 + x48 = 300
4) 非负约束 x i j ≥ 0
第三节 转运问题凌晨,凌晨,
Ling Xueling
三,L.P,模型
4,说明 ( 注意掌握 )
1) 约束式按节点逐个求出即可
2) 起运点－－可供量 ≤
中转点－－进出平衡 =
目的地－－需求满足 =
3) 对 有限制的路径只要增加约束：
x i j ≤ b －－限制量
4) 有多种特殊解法－－不介绍了 。
第三节 转运问题凌晨,凌晨,
Ling Xueling
四,转运模型在物流管理方面的应用
1,例子
C.C,公司在今后四个季度内的产能,市场需求,每季度生产成本及库存成本如下表所示,(单位：平方码 )
季度 产能 需求 生产成本 库存成本
1 600 400 2 0.25
2 300 500 5 0.25
3 500 400 3 0.25
4 400 400 3 0.25
公司要决策：如何安排今后四个季度生产计划及库存策略可以使生产,库存之 总 成本最小 。 如何建模？
第三节 转运问题凌晨,凌晨,
Ling Xueling
2,问题的网络表达第三节 转运问题凌晨,凌晨,
1
第一季度生产第二季度生产第三季度生产第四季度生产第一季度需求第二季度需求第三季度需求第四季度需求
2
5
6
3
4
7
8
6 0 0
3 0 0
5 0 0
4 0 0
4 0 0
4 0 0
5 0 0
4 0 0
生产结点 需求结点生产产能 需求
2
5
3
3
生产成本
0,2 5
0,2 5
0,2 5
库存成本
Ling Xueling
3,网络特点结点 5,6,7,8 既可视作转运问题中的 中转点,
又可视为其中的 目的地,在这样的考虑之下,容易得到以下的 L.P,模型：
4,建模 ( L.P,模型 )－－为每一 结点 建立一个 约束,为每一 弧 指定一 变量
1） 决策变量令 x i j = 结点 i 至结点 j 的产品 流量
2） o.f.－－总成本最小
Min 2x15 + 5x26 + 3x37 + 3x48 + 0.25x56 + 0.25x67 + 0.25x78
第三节 转运问题凌晨,凌晨,
Ling Xueling
4,建模 ( L.P,模型 ）
3） 约束
(1) 生产结点 （ 产能限制 ）
x 15 ≤ 600
x 26 ≤ 300
x 37 ≤ 500
x 48 ≤ 400
(2) 需求结点－－进出平衡,进货量－库存量 ＝ 需求量
x 15 － x 56 = 400
x 26 + x 56 － x 67 = 500
x 37 + x 67 － x 78 = 400
x 48 + x 78 = 400
(3) 非负约束 x i j ≥ 0 任意 i 和 j
第三节 转运问题凌晨,凌晨,
Ling Xueling
5,求解总成本,o.f,= 5150
生产计划,x15 = 600 x26 = 300
x37 = 400 x48 = 400
库存成本,x 56 = 200 x 67 = 0 x 78 = 0。
第三节 转运问题凌晨,凌晨,
Ling Xueling
The End of Chapter 6
