Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第六章
Transportation and
Assignment Problems
运输问题和指派问题
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
本章内容 Topics
The Transportation Problem 运输问题及其数学模型
Transportation Problem Example 运输问题举例
Characteristics of Transportation Problems 运输问题的特征
An Award-Winning Application 运输问题的一个获奖应用
Variants of Transportation Problems 各种运输问题变体
The Assignment Problem 指派问题
The Model for Assignment Problem 指派问题模型
Variants of Assignment Problem 指派问题的变形
Applications of Assignment Problem 指派问题的应用
案例 6.3 项目选择（指派问题）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
运输问题
物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（ sources）（如工厂、仓库）运输到一系列目的地（ destinations）（如仓库、顾客）
S o u r c e s D e s t i n at i o n s
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Transportation Network
运输问题的网络表示
2
3
2
1
3
4
1
s2=10
s3=15
d1=13
d2=21
d3=9
d4=7
s1=25
供应量供应地 运价需求量需求地
67
53
84
27
59
10
6
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型
设在若干个地点（发点） A1,A2,… Am集中了同一种类的物资，其发出量分别为 a1,a2,…,am
现在要把这些物资调运给其它若干个需要这种物资的地点（收点） B1,B2,…,Bn，设这些地点的需要量分别为 b1,b2,…,bn。
已知从 Ai运送一个单位物资到 Bj的运费为 cij。问怎样制定运输方案，才能使总运费最少？
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型（续）
1、当 ai（ i=1,2,… m） bj（ j=1,2,…,n） 满足条件时，称为平衡运输问题（总产量＝总销量）
2、用 xij表示从 Ai运到 Bj的物资数量，则 xij应满足约束条件：
xij?0（非负） (i=1,2,…,m;j=1,2,…,n)
3、运输问题为：求 xij满足 1,2，并使总运费达到最小
11
mn
ij
ij
ab
1
( 1,2,.,,,)
n
i j i
j
x a i m
1
( 1,2,...,)
m
i j j
i
x b j n
11
cmn ij ij
ij
Cx
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型（续）
于是得平衡运输问题的数学模型为：
其中 ai和 bj满足这就是平衡运输问题的数学模型，它包含了 m× n个决策变量 x11,…,x1n,
x21,… x2n,… xm1,xm2,… xmn,还包含了 m+n个等式（确定需求）约束，
以及平衡运输条件。
11
mnij
ij
ab
平衡运输条件
11
i
1
jj
1
M in c
1,2,,) a
s,t,( 1,2,,B b
0 ( i= 1,2,,m ; j= 1,2,,n )
mn
ij ij
ij
n
ij i
j
m
ij j
i
ij
Cx
x a i m
x b j n
x
i
( 从 A 运 送 出 去 的 量 ＝ 供 应 量
) 收 点 收 到 的 量 ＝ 需 求 量非 负
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型（续）
注意,1、平衡运输问题有最优解
2、运输问题有各种变体：主要是由于不满足条件称为不平衡运输问题。
当产大于销,即 这时,运输问题的数学模型为：
当供不应求（产小于销），处理方法类似
11
mn
ij
ij
ab
11
mn
ijijab
11
1
1
Min C c
1,2,,
s.t,1,2,,)
0 ( 1,2,,; 1,2,,)
mn
ij ij
ij
n
ij i
j
m
ij j
i
ij
x
x a i m
x b j n
x i m j n
（ ）
（
在 Excel,只需根据“产量 >
销量”或“产量 <销量 "将原来的,ai约束 "=ai"改为
"<=ai"”或,bj约束 "=bj"
改为 "<=bj"”
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.1 P&T Company Distribution Problem
案例研究,P&T公司的配送问题 P189
P&T公司是一家由家族经营的小公司 。 它收购生菜并在食品罐头厂中把它们加工成为罐头,然后再把这些罐头食品分销到各地卖出去 。
这个公司的一个主要产品是 豌豆罐头 。 这些豌豆罐头在 三个食品罐头厂 （ 靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝 ·李 ） 加工,然后 用卡车 把它们运送到美国西部的 四个分销仓库 (加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科他州赖皮特城；新墨西哥州澳尔巴古 )。
许多年来,公司一直根据经验,有一套从每个罐头加工工厂运送到各个仓库的运输方案 。
但总觉得可以改进,主要原因是因为近期的运营成本正在迅速增长,而利润却没有得到同样的增长 。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P&T公司运输问题的网络表述 P195
供应中心 [称为出发地（ Source） ]在左边，接收中心 [称为目的地
(destinations)]在右边，旁边的数字表示供应量和需求量。箭头表示运输的可能途径，旁边的数字表示单位运输成本。比较形象、直观。
S
1
S
2
S
3
D
4
D 2
D
1
D
3
7 5
1 2 5
1 0 0
8 0
6 5
7 0
8 5
S u p p l i e s D e m a n d s
S o u r c e s
D e s t i n a t i o n s
( B e l l i n g h a m )
( E u g e n e )
( A l b e r t L e a )
( S a c r a m e n t o )
( S a l t L a k e C i t y )
( R a p i d C i t y )
( A l b u q u e r q u e )
464
513
654
867
352
416
690
791
995
682
685
388
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
数学模型 P195－ 196
运输问题是一种线性规划问题用上面讲的运输问题的数学模型去理解。
决策变量,设 xij 为从罐头厂 i 运送到仓库 j的车数 (i = 1,2,3; j = 1,2,3,4)
目标函数：总成本 最小化 Min C = $464x11 + $513x12 + $654x13 + $867x14 +
$352x21 + $416x22 + $690x23 + $791x24 +
$995x31 + $682x32 + $388x33 + $685x34
约束条件（ 由于 75＋ 125＋ 100＝ 80＋ 65＋ 70＋ 85，即总供应＝总需求，平衡运输问题 ）,
罐头厂 1,x11 + x12 + x13 + x14 = 75
罐头厂 2,x21 + x22 + x23 + x24 = 125
罐头厂 3,x31 + x32 + x33 + x34 = 100
仓库 1,x11 + x21 + x31 = 80
仓库 2,x12 + x22 + x32 = 65
仓库 3,x13 + x23 + x33 = 70
仓库 4,x14 + x24 + x34 = 85
且 非负,xij ≥ 0 (i = 1,2,3; j = 1,2,3,4)
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.1 P&T Company Distribution Problem
案例研究,P&T公司的配送问题（续）
作为一个运输问题的 P&T公司电子表格描述
P 1 9 4 P & T 公司的配送问题 P & T C o,D i s t r i b u t i o n P r o b l e m
单位成本 c
ij
目的地 ( 仓库 )
萨克拉门托 盐湖城 赖皮特城 澳尔巴古出发地 ( 源 ) 贝林翰 $464 $513 $654 $867
( 罐头厂 ) 尤基尼 $352 $416 $690 $791
艾尔贝,李 $995 $682 $388 $685
运输量 x
ij
目的地 ( 仓库 )
萨克拉门托 盐湖城 赖皮特城 澳尔巴古 总运出量 供应量出发地 ( 源 ) 贝林翰 0 20 0 55 75 = 75
( 罐头厂 ) 尤基尼 80 45 0 0 125 = 125
艾尔贝,李 0 0 70 30 100 = 100
总运入量 80 65 70 85
= = = = 总成本需求量 80 65 70 85 $ 1 5 2,5 3 5
平衡运输条件：
总供应 总需求
300 = 300
为平衡运输问题
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Characteristics of Transportation Problems
6.2 运输问题的特征 P192
每一个出发地都有一定的 供应量（ supply） 要配送到目的地，每一个目的地都有一定的 需求量（ demand）,
需要接收从出发地发出的产品需求假设 （ The Requirements Assumption）
可行解特性 （ The Feasible Solutions Property）
成本假设 （ The Cost Assumption）
整数解性质 （ Integer Solutions Property）
求解运输问题 （ Solving Transportation Problems）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Requirements Assumption
需求假设 P192
需求假设（ The Requirements Assumption）：
每一个出发地都有一个 固定的供应量,所有的供应量 都必须配送 到目的地。与之相类似，每一个目的地都有一个 固定的需求量,整个需求量都必须由出发地满足 （ 平衡运输问题 ）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Feasible Solutions Property
可行解特性 P192
可行解特性（ The Feasible Solutions Property）：
当且仅当供应量的 总和 等于需求量的 总和 时，
平衡运输问题 才有可行解
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Cost Assumption
成本假设 P193
成本假设（ The Cost Assumption）：
从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量 成线性比例关系,
因此这个成本就等于 配送的单位成本乘以所配送的数量 （ 目标函数是线性的 ）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Integer Solutions Property
整数解性质 P196
整数解性质（ Integer Solutions Property）：
只要它的供应量和需求量都是整数,任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
求解运输问题 P196
求解运输问题（ Solving Transportation Problems）
单纯形法
表上作业法（运输单纯形法）
网络单纯形法
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
An Award-Winning Application
运输问题的一个获奖应用 P197
宝洁公司（ P&G）重新设计制造和配送体系,90’S
成百上千个供应商
50多个产品类别
超过 60个的工厂
15个配送中心
超过 1000个的顾客群体
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
An Award-Winning Application
运输问题的一个获奖应用 （续）
为每个单独的产品种类设计并求解运输问题。
对于针对还在运行的工厂的每一个选择，为每一个产品种类解决相应的运输问题体现了从这些工厂运送产品到配送中心或顾客区所需要的配送成本是多少。
在找出最好的新生产和配送系统的过程之中解决了许多这样的运输问题
最终得到的结果是北美工厂数减少了 20%，并且公司每年节省了 2亿美元的税前费用
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Variants of Transportation Problems
6.3 各种运输问题变体的建模 P198
供应总量超出了需求总量 （供过于求 >）
供应总量小于需求总量 （供不应求 <）
一个目的地同时存在着最小需求和最大需求
（ >=,<=）
在配送中不能使用特定的出发地－目的地组合（运输途径不通，相应的 xij=0）
目标是与配送量有关的总利润最大而不是总成本最小（ Min Cost－ > Max Profit）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P199 例 1：指定工厂生产产品
1,工厂 2不能生产产品 3（解决办法：相应的 x23=0）
2,总供应 >总需求（解决办法：将供应的 ＝ 改为 <=）
P2 0 0 指定工厂生产产品,B e t t e r Pr o d u c t s C o,Pr o d u c t i o n Pl a n n i n g Pr o b l e m
单位成本 c
ij
产品 1 产品 2 产品 3 产品 4
工厂 1 $41 $27 $28 $24
工厂 2 $40 $29 - $23
工厂 3 $37 $30 $27 $21
日产量 x
ij
产品 1 产品 2 产品 3 产品 4 生产 生产能力工厂 1 0 30 30 0 60 <= 75
工厂 2 0 0 0 15 15 <= 75
工厂 3 20 0 0 25 45 <= 45
产量 20 30 30 40
= = = = 总成本需求量 20 30 30 40 $ 3,2 6 0
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P201 例 2：选择顾客
1,满足不同顾客的需求－－采购量（ 解决办法：实际供给量 >=最小采购量和实际供给量
<=最大采购量 ） （但条件是,总最小采购量 <=总供应量 <=总最大采购量）
2,利润最大 （ Min Cost－ >Max Profit）
P 2 0 2 选择顾客 N i f t y C o,P r o d u c t - D i s t r i b u t i o n P r o b l e m
单位利润 c
ij
顾客 1 顾客 2 顾客 3 顾客 4
工厂 1 $55 $42 $46 $53
工厂 2 $37 $18 $32 $48
工厂 3 $29 $59 $51 $35
运输量 x
ij
顾客 1 顾客 2 顾客 3 顾客 4 实际产量 供应量 ( 产量 )
工厂 1 7,0 0 0 0 1,0 0 0 0 8,0 0 0 = 8,0 0 0
工厂 2 0 0 0 5,0 0 0 5,0 0 0 = 5,0 0 0
工厂 3 0 6,0 0 0 1,0 0 0 0 7,0 0 0 = 7,0 0 0
最小采购量 7,0 0 0 3,0 0 0 2,0 0 0 0
<= <= <= <= 总利润实际供给量 7,0 0 0 6,0 0 0 2,0 0 0 5,0 0 0 $ 1,0 7 6,0 0 0
<= <= <= <=
最大采购量 7,0 0 0 9,0 0 0 6,0 0 0 8,0 0 0
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Variants of Transportation Problems Applications
6.4 运输问题变体的其他一些应用 P203
P203 分配自然资源
P205 生产进度安排
P207 划分学生入学区域
P208 以经济的方式满足能源需求
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P203 分配自然资源
1,卡路里河不能给豪利格拉斯供水（解决办法,相应的 X34=0）
2,总供应 >总需求（解决办法：将供应的 =改为 <=）
P 2 0 4 分配自然资源 M e t r o W a t e r D i s t r i c t D i s t r i b u t i o n P r o b l e m
单位成本 c
ij
布都 劳斯戴维斯 圣哥 豪利格拉斯科伦坡河 160 130 220 170
塞克隆河 140 130 190 150
卡路里河 190 200 230 -
流量 x
ij
布都 劳斯戴维斯 圣哥 豪利格拉斯 河流供应量 可供应量科伦坡河 0 5 0 0 5 <= 5
塞克隆河 2 0 2,5 1,5 6 <= 6
卡路里河 0 0 1,5 0 1,5 <= 5
流入城市量 2 5 4 1,5
= = = = 总成本城市需求量 2 5 4 1,5 1,9 7 5
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P206 生产进度安排请看第 6章相应的 Excel文件，不同点：
1,注意解决此类问题的关键所在：数据转换原来为单位生产成本和每月存储成本分别给出，
如何合并成单位成本（单位生产成本＋每月存储成本 × 存储月数）
2,需求总量（计划安装量） <总最大产量
3,生产了，才能安装（相应的 xij=0，在 i>j时）
其中 xij-第 i个月生产第 j个月安装的发动机数
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
思考题：
问题,是否可以用第 3章的方法 (利用剩余量 ri)来解
P206的生产进度安排？
回答：可以
结果：相同
决策变量,xi(RT),yi(OT)－第 i个月正常时间
(RT)和加班时间 (OT)生产的发动机数
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P207 划分学生入学区域请看第 6章相应的 Excel文件,不同点：
1,单位成本为距离，目标是学生所走的平均路程最短
2,学校有最小和最大招生数（ <=,>=）
（但有解的条件是最小招生总数 <=实际招生总数 <=最大招生总数）
其中 xij-区域 i划入到学校 j的学生人数
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P208 以经济的方式满足能源需求
1,电的需求只能通过购买电来满足（解决办法,x21=0,x31=0）
2,电和天然气两种能源没有限制
P 2 1 1 以经济的方式满足能源需求 E n e r g e t i c C o,E n e r g y - S o u r c i n g P r o b l e m
能源需求单位成本( $ / 天) c
ij
电 热水 取暖能源 电 400 500 600
来源 天然气 - 600 500
太阳能 - 300 400
能源需求每天每种能源的用量 x
ij
电 热水 取暖 实际使用电 20 0 0 20
能源 天然气 0 0 10 10 最大太阳能来源 太阳能 0 10 20 30 <= 30
实际供给 20 10 30
= = = 总成本( $ / 天)
需求量 20 10 30 2 4,0 0 0
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.5 Texago Corp,Site Location
P211 案例研究：特塞格公司的选址问题
特塞格公司是一家设在美国本土的大型一体化石油公司。这家公司大部分的石油在公司自己的油田中生产，所需的其他部分从中东地区进口。公司拥有大型配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。
油田：提供原油 (百万桶 )
德克萨斯 80
加利福尼亚 60
阿拉斯加 100
中东地区 120
炼油厂：生产石油产品新奥尔良 100
查尔斯顿 60
西雅图 80
新的炼油厂 120
配送中心：
匹兹堡 100
亚特兰大 80
堪萨斯城 80
旧金山 100
备选炼油厂地址：
洛杉矶加尔维斯敦圣路易斯
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.5 Texago Corp,Site Location
特塞格公司的选址问题 （续）
特塞格公司正在持续增加其几种主要产品的市场占有率。因此管理层决定建立一个新的炼油厂来增加公司的产量，同时增加从中东地区进口石油的数量。接下来所要作出的决策就是确定在什么地方建设新的炼油厂。
新炼油厂的加入对整个配送系统都将产生巨大的影响，其中包括要确定从每一个出发地运送到炼油厂的原油数量，以及从每一个炼油厂运送石油制品到每一个配送中心的数量。因此，影响管理者选择新炼油厂建设地点的三个关键因素是：
1,从出发地运送原油到所有炼油厂（包括新炼油厂）的成本
2,从所有炼油厂（包括新炼油厂）运送石油制品到每一个配送中心的成本
3,新炼油厂的运作成本，包括劳动力成本、赋税、原料（不包括原油
）成本、能源成本、保险成本等（资金成本并不是一个所要关注的因素，因为任何地点的资金成本几乎都是相同的。）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
特塞格选址问题 －解决方案
收集（估计）数据（ P213－ 214）：
1,三个油田的产量，所有炼油厂（包括新炼油厂）的需求量，不够的原油从中东进口，四个配送中心的需求量
2,从四个油田（出发地,3个自己＋中东地区）到所有炼油厂（包括新炼油厂）的单位运输成本
3,从所有炼油厂（包括新炼油厂）到每一个配送中心的单位运输成本
4,新炼油厂的运营成本
将备选新炼油厂（每次一个）增加到整个配送系统，并计算（平衡运输问题）：
1,每一个新炼油厂建设地点选择带来的总原油运输成本
2,每一个新炼油厂建设地点选择带来的总石油制品运输成本
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
地点 运输原油的总成本（百万美元）
运输石油制品的总成本
（十亿美元）
新炼油厂的运营成本
(百万美元 )
总变动成本
(十亿美元 )
洛杉机 880 1.57 620 3.07
加尔维斯敦 920 1.63 570 3.12
圣路易斯 960 1.43 530 2.92
特塞格选址问题－结论 P218
特塞格炼油厂每一个备选厂址所带来的年变动成本最终选择了在 圣路易斯建造新的炼油厂
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
特塞格选址问题：思考题 P217
如果要求最终选择的圣路易斯新炼油厂的生产能力不是原来计划的每年加工 1.2亿桶，而是以后市场需求的每年加工 1.5亿桶。
此时有三种解决方案（详见 P237的 案例 6.2）,
1,将 3.6亿桶原油从产油地运往炼油厂（包括圣路易斯新建的炼油厂），每家炼油厂收到的原油数在不超过其生产能力的基础上，
使运输成本最小化。以此时每家炼油厂收到的原油数为基础，
寻找将产成品从炼油厂运往配送中心的最优运输计划－－ 案例
6.2 的 a和 b。
2,与 1的顺序相反，先求产成品从炼油厂运往配送中心的最优运输计划，然后以此为基础（炼油厂的实际供应量），再求将 3.6
亿桶原油从产油地运往炼油厂（包括圣路易斯新建的炼油厂）
的最优运输计划－－ 案例 6.2 的 c和 d。
3,合并 运输原油和运输石油制品这两张运输问题表为一张表，同时使两种产品的运输计划达到最优（总运输成本最小化） － 案例 6.2 的 e和 f（ 提示：增加约束－－各炼油厂收到的原油数量与运送出去的石油制品数量相等）。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Assignment Problem
6.6 指派问题 P220
在现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂等。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Sellmore Co,Assignment Problem
例子：赛尔默公司的指派问题 P220
赛尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇用了四个临时工（ Ann安,Ian伊恩,Joan琼、
Sean肖恩）,每个人负责完成下面的一项任务
,文字处理、绘图、材料准备和注册报名 。
由于每个人完成每项任务的时间和工资不同，
问：如何指派，使总成本最小。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
赛尔默公司的电子表格模型 P222
请看第 6章相应的 Excel文件，特点：
1,单位成本为每个人做每项工作的总工资
2,目标是要确定哪个临时工进行哪一个工作 xij,使总成本最小。
3,供应量为 1－代表每个人都只能完成一项任务
4,需求量为 1－代表每项任务也只能由一个人来完成
5,总人数和总任务数相同其中 xij-指派临时工 i去做工作 j（结果为 0或 1）
为什么不需要 0-1条件？可以用 IF函数实现更进一步的解释
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
补充：赛尔默公司的数学模型决策变量：设 xij为指派临时工 i去做工作 j (i = 1,2,3,4; j = 1,2,3,4)
目标函数：总成本最小化
Min C = 35*14x11 + 41*14x12 + 27*14x13 + 40*14x14 +
47*12x21 + 45*12x22 + 32*12x23 + 51*12x24 +
39*13x31 + 56*13x32 + 36*13x33 + 43*13x34 +
32*15x41 + 51*15x42 + 25*15x43 + 46*15x44
约束条件 （ 由于有 4个人,4项任务，即总供应＝总需求，平衡 ）,
安 Ann,x11 + x12 + x13 + x14 = 1
伊恩 Ian,x21 + x22 + x23 + x24 = 1
琼 Joan,x31 + x32 + x33 + x34 = 1
肖恩 Sean,x41 + x42 + x43 + x44 = 1
文字处理,x11 + x21 + x31 + x41 = 1
绘图,x12 + x22 + x32 + x42 = 1
材料准备,x13 + x23 + x33 + x43 = 1
注册报名,x14 + x24 + x34 + x44 = 1
且 非负,xij ≥ 0 ( i = 1,2,3,4; j = 1,2,3,4)
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Model for Assignment Problem
指派问题模型 P223
指派问题的形式表述,
给定了一系列所要完成的任务（ tasks）以及一系列完成任务的被指派者（ assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Model for Assignment Problem
指派问题模型 P223
指派问题的假设,
被指派者的数量和任务的数量是相同的
每一个被指派者只完成一项任务
每一项任务只能由一个被指派者来完成
每个被指派者和每项任务的组合有一个相关成本
问题的目标是要确定怎样进行指派才能使得总成本达到最小
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Network Representation for Assignment Problem
指派问题的网络表示法 P223
指派问题是一种特殊的运输问题 P223
求解指派问题,匈牙利方法（ Hungarian method ） P224
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Variants of Assignment Problem
6.7 对指派问题变形的建模 P225
指派问题的变形,
有一些被指派者并不能进行某一些的任务 (相应的 xij=0)
任务比被指派者多，有些任务可以不完成（ 将任务的 =
改为 <=）
被指派者比要完成的任务多，有些被指派者可以没事做
（ 将被指派者的 =改为 <=）
每个被指派者可以同时被指派给多于一个的任务（ 被指派者的供应量由 1->n）
每一项任务都可以由多个被指派者共同完成（ 任务的需求量由 1->n）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Applications of Assignment Problem
指派问题的应用 P225
例子 1：在各个地点分派设备 P225
例子 2：指派工厂生产产品 P227
例子 3：设计学生入学区域 P229
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Assigning Machines to Locations
各个地点分派设备 P225
1,地点 2不能安装机器 2（ 相应的 x22＝ 0）
2,机器少地点多，有些地点不安装（地点的 ＝ 改为 <=）
P 2 2 6 在各个地点安装设备 J o b S h o p C o,M a c h i n e - L o c a t i o n P r o b l e m
单位成本C i j ( $ / 时) 地点 1 地点 2 地点 3 地点 4 地点 5
机器 1 13 16 12 14 15
机器 2 15 - 13 20 16
机器 3 4 7 10 6 7
指派 X i j 地点 1 地点 2 地点 3 地点 4 地点 5 总指派 供应量机器 1 0 0 0 1 0 1 = 1
机器 2 0 0 1 0 0 1 = 1
机器 3 1 0 0 0 0 1 = 1
总分配 1 0 1 1 0
<= <= <= <= <= 总成本( $ / 时)
需求量 1 1 1 1 1 31
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Assigning Plants to Products
指派工厂生产产品 P227
请看第 6章相应的 Excel文件,不同点：
1,求佳产品公司问题指派问题变形（ 运输问题－ >指派问题 ）
2,注意解决此类问题的关键所在,数据转换
单位指派成本 cij,原来的单位成本转换成整批成本＝单位成本 × 需求量，成本改为每家工厂生产每种产品的成本
供应量和需求量的转换问题：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂 3只能生产一种产品（＝ 1），而工厂 1,2可以生产 2种产品（ <=2）
，而产品的需求量＝ 1
3,总供应 >总需求（工厂 1,2供应的 =改为 <=2）
4,结果有时还需验证（验证是否还满足原来的运输问题要求－工厂生产能力限制）
其中 xij-指派工厂 i生产产品 j（ 0－ 1）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Designing School Attendance Zones
设计学生入学区域 P229
请看第 6章相应的 Excel文件,不同点
1,运输问题－ >指派问题
2,注意解决此类问题的关键所在,数据转换
单位指派成本 cij：原来的每位同学平均距离转换成整个地区所有同学的总距离＝每位同学平均距离 × 学生数量
供应量和需求量的转换问题（供应量＝ 1，而需求量变为一个学校接收 3个地区（ =3）
3,结果有时还需验证（验证是否还满足原来的运输问题要求：学校有最小和最大招生数（ <=,>=）
其中 xij-指派区域 i到学校 j（ 0－ 1）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.8 Summary 小结 P231
运输问题考虑 （ 确实的或是比喻的 ） 从出发地运送货物到目的地 。 每一个出发地都有一个固定的供应量,
每一个目的地都有一个固定的需求量
指派问题就是要处理应当将哪一项任务指派给哪一个被指派者,才能使完成这些任务的总成本达到最小
把可能会面临的问题描述为一个运输问题或者指派问题或者它们的变形并进行分析
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P238 案例 6.3项目选择
－指派问题
有 5个项目 （ Up,Stable,Choice,Hope,Release）
有 5位科学家和他们的投标点 （ 每个人都有 1000点 ） 情况
问将哪一个项目指派给哪一位科学家,并使得这位科学家的满意度最高 （ 指派问题 ） － 其实是总的满意度最高
可能会面临多种情况 （ 用指派问题的变形并进行分析 ）
给出一个指派问题模板和数据,请同学们自己完成 （ 包括变形问题 ） 。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P232 习题 6.6（请将 100改为 1000),
6.7,6.13,6.15,6.21,6,22
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
案例（二选一）
P237案例 6.2
改：年总运输成本为 29.2亿美元（原来为 23.9） 2处注意：对于问题 e,f，也可以采用第 7章的方法
P238案例 6.3
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第六章
Transportation and
Assignment Problems
运输问题和指派问题
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
本章内容 Topics
The Transportation Problem 运输问题及其数学模型
Transportation Problem Example 运输问题举例
Characteristics of Transportation Problems 运输问题的特征
An Award-Winning Application 运输问题的一个获奖应用
Variants of Transportation Problems 各种运输问题变体
The Assignment Problem 指派问题
The Model for Assignment Problem 指派问题模型
Variants of Assignment Problem 指派问题的变形
Applications of Assignment Problem 指派问题的应用
案例 6.3 项目选择（指派问题）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
运输问题
物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（ sources）（如工厂、仓库）运输到一系列目的地（ destinations）（如仓库、顾客）
S o u r c e s D e s t i n at i o n s
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Transportation Network
运输问题的网络表示
2
3
2
1
3
4
1
s2=10
s3=15
d1=13
d2=21
d3=9
d4=7
s1=25
供应量供应地 运价需求量需求地
67
53
84
27
59
10
6
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型
设在若干个地点（发点） A1,A2,… Am集中了同一种类的物资，其发出量分别为 a1,a2,…,am
现在要把这些物资调运给其它若干个需要这种物资的地点（收点） B1,B2,…,Bn，设这些地点的需要量分别为 b1,b2,…,bn。
已知从 Ai运送一个单位物资到 Bj的运费为 cij。问怎样制定运输方案，才能使总运费最少？
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型（续）
1、当 ai（ i=1,2,… m） bj（ j=1,2,…,n） 满足条件时，称为平衡运输问题（总产量＝总销量）
2、用 xij表示从 Ai运到 Bj的物资数量，则 xij应满足约束条件：
xij?0（非负） (i=1,2,…,m;j=1,2,…,n)
3、运输问题为：求 xij满足 1,2，并使总运费达到最小
11
mn
ij
ij
ab
1
( 1,2,.,,,)
n
i j i
j
x a i m
1
( 1,2,...,)
m
i j j
i
x b j n
11
cmn ij ij
ij
Cx
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型（续）
于是得平衡运输问题的数学模型为：
其中 ai和 bj满足这就是平衡运输问题的数学模型，它包含了 m× n个决策变量 x11,…,x1n,
x21,… x2n,… xm1,xm2,… xmn,还包含了 m+n个等式（确定需求）约束，
以及平衡运输条件。
11
mnij
ij
ab
平衡运输条件
11
i
1
jj
1
M in c
1,2,,) a
s,t,( 1,2,,B b
0 ( i= 1,2,,m ; j= 1,2,,n )
mn
ij ij
ij
n
ij i
j
m
ij j
i
ij
Cx
x a i m
x b j n
x
i
( 从 A 运 送 出 去 的 量 ＝ 供 应 量
) 收 点 收 到 的 量 ＝ 需 求 量非 负
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Transportation Problem
Model 运输问题的数学模型（续）
注意,1、平衡运输问题有最优解
2、运输问题有各种变体：主要是由于不满足条件称为不平衡运输问题。
当产大于销,即 这时,运输问题的数学模型为：
当供不应求（产小于销），处理方法类似
11
mn
ij
ij
ab
11
mn
ijijab
11
1
1
Min C c
1,2,,
s.t,1,2,,)
0 ( 1,2,,; 1,2,,)
mn
ij ij
ij
n
ij i
j
m
ij j
i
ij
x
x a i m
x b j n
x i m j n
（ ）
（
在 Excel,只需根据“产量 >
销量”或“产量 <销量 "将原来的,ai约束 "=ai"改为
"<=ai"”或,bj约束 "=bj"
改为 "<=bj"”
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.1 P&T Company Distribution Problem
案例研究,P&T公司的配送问题 P189
P&T公司是一家由家族经营的小公司 。 它收购生菜并在食品罐头厂中把它们加工成为罐头,然后再把这些罐头食品分销到各地卖出去 。
这个公司的一个主要产品是 豌豆罐头 。 这些豌豆罐头在 三个食品罐头厂 （ 靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝 ·李 ） 加工,然后 用卡车 把它们运送到美国西部的 四个分销仓库 (加利福尼亚州的萨克拉门托；犹他州盐湖城；南达科他州赖皮特城；新墨西哥州澳尔巴古 )。
许多年来,公司一直根据经验,有一套从每个罐头加工工厂运送到各个仓库的运输方案 。
但总觉得可以改进,主要原因是因为近期的运营成本正在迅速增长,而利润却没有得到同样的增长 。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P&T公司运输问题的网络表述 P195
供应中心 [称为出发地（ Source） ]在左边，接收中心 [称为目的地
(destinations)]在右边，旁边的数字表示供应量和需求量。箭头表示运输的可能途径，旁边的数字表示单位运输成本。比较形象、直观。
S
1
S
2
S
3
D
4
D 2
D
1
D
3
7 5
1 2 5
1 0 0
8 0
6 5
7 0
8 5
S u p p l i e s D e m a n d s
S o u r c e s
D e s t i n a t i o n s
( B e l l i n g h a m )
( E u g e n e )
( A l b e r t L e a )
( S a c r a m e n t o )
( S a l t L a k e C i t y )
( R a p i d C i t y )
( A l b u q u e r q u e )
464
513
654
867
352
416
690
791
995
682
685
388
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
数学模型 P195－ 196
运输问题是一种线性规划问题用上面讲的运输问题的数学模型去理解。
决策变量,设 xij 为从罐头厂 i 运送到仓库 j的车数 (i = 1,2,3; j = 1,2,3,4)
目标函数：总成本 最小化 Min C = $464x11 + $513x12 + $654x13 + $867x14 +
$352x21 + $416x22 + $690x23 + $791x24 +
$995x31 + $682x32 + $388x33 + $685x34
约束条件（ 由于 75＋ 125＋ 100＝ 80＋ 65＋ 70＋ 85，即总供应＝总需求，平衡运输问题 ）,
罐头厂 1,x11 + x12 + x13 + x14 = 75
罐头厂 2,x21 + x22 + x23 + x24 = 125
罐头厂 3,x31 + x32 + x33 + x34 = 100
仓库 1,x11 + x21 + x31 = 80
仓库 2,x12 + x22 + x32 = 65
仓库 3,x13 + x23 + x33 = 70
仓库 4,x14 + x24 + x34 = 85
且 非负,xij ≥ 0 (i = 1,2,3; j = 1,2,3,4)
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.1 P&T Company Distribution Problem
案例研究,P&T公司的配送问题（续）
作为一个运输问题的 P&T公司电子表格描述
P 1 9 4 P & T 公司的配送问题 P & T C o,D i s t r i b u t i o n P r o b l e m
单位成本 c
ij
目的地 ( 仓库 )
萨克拉门托 盐湖城 赖皮特城 澳尔巴古出发地 ( 源 ) 贝林翰 $464 $513 $654 $867
( 罐头厂 ) 尤基尼 $352 $416 $690 $791
艾尔贝,李 $995 $682 $388 $685
运输量 x
ij
目的地 ( 仓库 )
萨克拉门托 盐湖城 赖皮特城 澳尔巴古 总运出量 供应量出发地 ( 源 ) 贝林翰 0 20 0 55 75 = 75
( 罐头厂 ) 尤基尼 80 45 0 0 125 = 125
艾尔贝,李 0 0 70 30 100 = 100
总运入量 80 65 70 85
= = = = 总成本需求量 80 65 70 85 $ 1 5 2,5 3 5
平衡运输条件：
总供应 总需求
300 = 300
为平衡运输问题
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Characteristics of Transportation Problems
6.2 运输问题的特征 P192
每一个出发地都有一定的 供应量（ supply） 要配送到目的地，每一个目的地都有一定的 需求量（ demand）,
需要接收从出发地发出的产品需求假设 （ The Requirements Assumption）
可行解特性 （ The Feasible Solutions Property）
成本假设 （ The Cost Assumption）
整数解性质 （ Integer Solutions Property）
求解运输问题 （ Solving Transportation Problems）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Requirements Assumption
需求假设 P192
需求假设（ The Requirements Assumption）：
每一个出发地都有一个 固定的供应量,所有的供应量 都必须配送 到目的地。与之相类似，每一个目的地都有一个 固定的需求量,整个需求量都必须由出发地满足 （ 平衡运输问题 ）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Feasible Solutions Property
可行解特性 P192
可行解特性（ The Feasible Solutions Property）：
当且仅当供应量的 总和 等于需求量的 总和 时，
平衡运输问题 才有可行解
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Cost Assumption
成本假设 P193
成本假设（ The Cost Assumption）：
从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量 成线性比例关系,
因此这个成本就等于 配送的单位成本乘以所配送的数量 （ 目标函数是线性的 ）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Integer Solutions Property
整数解性质 P196
整数解性质（ Integer Solutions Property）：
只要它的供应量和需求量都是整数,任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
求解运输问题 P196
求解运输问题（ Solving Transportation Problems）
单纯形法
表上作业法（运输单纯形法）
网络单纯形法
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
An Award-Winning Application
运输问题的一个获奖应用 P197
宝洁公司（ P&G）重新设计制造和配送体系,90’S
成百上千个供应商
50多个产品类别
超过 60个的工厂
15个配送中心
超过 1000个的顾客群体
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
An Award-Winning Application
运输问题的一个获奖应用 （续）
为每个单独的产品种类设计并求解运输问题。
对于针对还在运行的工厂的每一个选择，为每一个产品种类解决相应的运输问题体现了从这些工厂运送产品到配送中心或顾客区所需要的配送成本是多少。
在找出最好的新生产和配送系统的过程之中解决了许多这样的运输问题
最终得到的结果是北美工厂数减少了 20%，并且公司每年节省了 2亿美元的税前费用
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Variants of Transportation Problems
6.3 各种运输问题变体的建模 P198
供应总量超出了需求总量 （供过于求 >）
供应总量小于需求总量 （供不应求 <）
一个目的地同时存在着最小需求和最大需求
（ >=,<=）
在配送中不能使用特定的出发地－目的地组合（运输途径不通，相应的 xij=0）
目标是与配送量有关的总利润最大而不是总成本最小（ Min Cost－ > Max Profit）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P199 例 1：指定工厂生产产品
1,工厂 2不能生产产品 3（解决办法：相应的 x23=0）
2,总供应 >总需求（解决办法：将供应的 ＝ 改为 <=）
P2 0 0 指定工厂生产产品,B e t t e r Pr o d u c t s C o,Pr o d u c t i o n Pl a n n i n g Pr o b l e m
单位成本 c
ij
产品 1 产品 2 产品 3 产品 4
工厂 1 $41 $27 $28 $24
工厂 2 $40 $29 - $23
工厂 3 $37 $30 $27 $21
日产量 x
ij
产品 1 产品 2 产品 3 产品 4 生产 生产能力工厂 1 0 30 30 0 60 <= 75
工厂 2 0 0 0 15 15 <= 75
工厂 3 20 0 0 25 45 <= 45
产量 20 30 30 40
= = = = 总成本需求量 20 30 30 40 $ 3,2 6 0
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P201 例 2：选择顾客
1,满足不同顾客的需求－－采购量（ 解决办法：实际供给量 >=最小采购量和实际供给量
<=最大采购量 ） （但条件是,总最小采购量 <=总供应量 <=总最大采购量）
2,利润最大 （ Min Cost－ >Max Profit）
P 2 0 2 选择顾客 N i f t y C o,P r o d u c t - D i s t r i b u t i o n P r o b l e m
单位利润 c
ij
顾客 1 顾客 2 顾客 3 顾客 4
工厂 1 $55 $42 $46 $53
工厂 2 $37 $18 $32 $48
工厂 3 $29 $59 $51 $35
运输量 x
ij
顾客 1 顾客 2 顾客 3 顾客 4 实际产量 供应量 ( 产量 )
工厂 1 7,0 0 0 0 1,0 0 0 0 8,0 0 0 = 8,0 0 0
工厂 2 0 0 0 5,0 0 0 5,0 0 0 = 5,0 0 0
工厂 3 0 6,0 0 0 1,0 0 0 0 7,0 0 0 = 7,0 0 0
最小采购量 7,0 0 0 3,0 0 0 2,0 0 0 0
<= <= <= <= 总利润实际供给量 7,0 0 0 6,0 0 0 2,0 0 0 5,0 0 0 $ 1,0 7 6,0 0 0
<= <= <= <=
最大采购量 7,0 0 0 9,0 0 0 6,0 0 0 8,0 0 0
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Variants of Transportation Problems Applications
6.4 运输问题变体的其他一些应用 P203
P203 分配自然资源
P205 生产进度安排
P207 划分学生入学区域
P208 以经济的方式满足能源需求
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P203 分配自然资源
1,卡路里河不能给豪利格拉斯供水（解决办法,相应的 X34=0）
2,总供应 >总需求（解决办法：将供应的 =改为 <=）
P 2 0 4 分配自然资源 M e t r o W a t e r D i s t r i c t D i s t r i b u t i o n P r o b l e m
单位成本 c
ij
布都 劳斯戴维斯 圣哥 豪利格拉斯科伦坡河 160 130 220 170
塞克隆河 140 130 190 150
卡路里河 190 200 230 -
流量 x
ij
布都 劳斯戴维斯 圣哥 豪利格拉斯 河流供应量 可供应量科伦坡河 0 5 0 0 5 <= 5
塞克隆河 2 0 2,5 1,5 6 <= 6
卡路里河 0 0 1,5 0 1,5 <= 5
流入城市量 2 5 4 1,5
= = = = 总成本城市需求量 2 5 4 1,5 1,9 7 5
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P206 生产进度安排请看第 6章相应的 Excel文件，不同点：
1,注意解决此类问题的关键所在：数据转换原来为单位生产成本和每月存储成本分别给出，
如何合并成单位成本（单位生产成本＋每月存储成本 × 存储月数）
2,需求总量（计划安装量） <总最大产量
3,生产了，才能安装（相应的 xij=0，在 i>j时）
其中 xij-第 i个月生产第 j个月安装的发动机数
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
思考题：
问题,是否可以用第 3章的方法 (利用剩余量 ri)来解
P206的生产进度安排？
回答：可以
结果：相同
决策变量,xi(RT),yi(OT)－第 i个月正常时间
(RT)和加班时间 (OT)生产的发动机数
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P207 划分学生入学区域请看第 6章相应的 Excel文件,不同点：
1,单位成本为距离，目标是学生所走的平均路程最短
2,学校有最小和最大招生数（ <=,>=）
（但有解的条件是最小招生总数 <=实际招生总数 <=最大招生总数）
其中 xij-区域 i划入到学校 j的学生人数
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P208 以经济的方式满足能源需求
1,电的需求只能通过购买电来满足（解决办法,x21=0,x31=0）
2,电和天然气两种能源没有限制
P 2 1 1 以经济的方式满足能源需求 E n e r g e t i c C o,E n e r g y - S o u r c i n g P r o b l e m
能源需求单位成本( $ / 天) c
ij
电 热水 取暖能源 电 400 500 600
来源 天然气 - 600 500
太阳能 - 300 400
能源需求每天每种能源的用量 x
ij
电 热水 取暖 实际使用电 20 0 0 20
能源 天然气 0 0 10 10 最大太阳能来源 太阳能 0 10 20 30 <= 30
实际供给 20 10 30
= = = 总成本( $ / 天)
需求量 20 10 30 2 4,0 0 0
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.5 Texago Corp,Site Location
P211 案例研究：特塞格公司的选址问题
特塞格公司是一家设在美国本土的大型一体化石油公司。这家公司大部分的石油在公司自己的油田中生产，所需的其他部分从中东地区进口。公司拥有大型配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。
油田：提供原油 (百万桶 )
德克萨斯 80
加利福尼亚 60
阿拉斯加 100
中东地区 120
炼油厂：生产石油产品新奥尔良 100
查尔斯顿 60
西雅图 80
新的炼油厂 120
配送中心：
匹兹堡 100
亚特兰大 80
堪萨斯城 80
旧金山 100
备选炼油厂地址：
洛杉矶加尔维斯敦圣路易斯
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.5 Texago Corp,Site Location
特塞格公司的选址问题 （续）
特塞格公司正在持续增加其几种主要产品的市场占有率。因此管理层决定建立一个新的炼油厂来增加公司的产量，同时增加从中东地区进口石油的数量。接下来所要作出的决策就是确定在什么地方建设新的炼油厂。
新炼油厂的加入对整个配送系统都将产生巨大的影响，其中包括要确定从每一个出发地运送到炼油厂的原油数量，以及从每一个炼油厂运送石油制品到每一个配送中心的数量。因此，影响管理者选择新炼油厂建设地点的三个关键因素是：
1,从出发地运送原油到所有炼油厂（包括新炼油厂）的成本
2,从所有炼油厂（包括新炼油厂）运送石油制品到每一个配送中心的成本
3,新炼油厂的运作成本，包括劳动力成本、赋税、原料（不包括原油
）成本、能源成本、保险成本等（资金成本并不是一个所要关注的因素，因为任何地点的资金成本几乎都是相同的。）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
特塞格选址问题 －解决方案
收集（估计）数据（ P213－ 214）：
1,三个油田的产量，所有炼油厂（包括新炼油厂）的需求量，不够的原油从中东进口，四个配送中心的需求量
2,从四个油田（出发地,3个自己＋中东地区）到所有炼油厂（包括新炼油厂）的单位运输成本
3,从所有炼油厂（包括新炼油厂）到每一个配送中心的单位运输成本
4,新炼油厂的运营成本
将备选新炼油厂（每次一个）增加到整个配送系统，并计算（平衡运输问题）：
1,每一个新炼油厂建设地点选择带来的总原油运输成本
2,每一个新炼油厂建设地点选择带来的总石油制品运输成本
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
地点 运输原油的总成本（百万美元）
运输石油制品的总成本
（十亿美元）
新炼油厂的运营成本
(百万美元 )
总变动成本
(十亿美元 )
洛杉机 880 1.57 620 3.07
加尔维斯敦 920 1.63 570 3.12
圣路易斯 960 1.43 530 2.92
特塞格选址问题－结论 P218
特塞格炼油厂每一个备选厂址所带来的年变动成本最终选择了在 圣路易斯建造新的炼油厂
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
特塞格选址问题：思考题 P217
如果要求最终选择的圣路易斯新炼油厂的生产能力不是原来计划的每年加工 1.2亿桶，而是以后市场需求的每年加工 1.5亿桶。
此时有三种解决方案（详见 P237的 案例 6.2）,
1,将 3.6亿桶原油从产油地运往炼油厂（包括圣路易斯新建的炼油厂），每家炼油厂收到的原油数在不超过其生产能力的基础上，
使运输成本最小化。以此时每家炼油厂收到的原油数为基础，
寻找将产成品从炼油厂运往配送中心的最优运输计划－－ 案例
6.2 的 a和 b。
2,与 1的顺序相反，先求产成品从炼油厂运往配送中心的最优运输计划，然后以此为基础（炼油厂的实际供应量），再求将 3.6
亿桶原油从产油地运往炼油厂（包括圣路易斯新建的炼油厂）
的最优运输计划－－ 案例 6.2 的 c和 d。
3,合并 运输原油和运输石油制品这两张运输问题表为一张表，同时使两种产品的运输计划达到最优（总运输成本最小化） － 案例 6.2 的 e和 f（ 提示：增加约束－－各炼油厂收到的原油数量与运送出去的石油制品数量相等）。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Assignment Problem
6.6 指派问题 P220
在现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂等。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Sellmore Co,Assignment Problem
例子：赛尔默公司的指派问题 P220
赛尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇用了四个临时工（ Ann安,Ian伊恩,Joan琼、
Sean肖恩）,每个人负责完成下面的一项任务
,文字处理、绘图、材料准备和注册报名 。
由于每个人完成每项任务的时间和工资不同，
问：如何指派，使总成本最小。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
赛尔默公司的电子表格模型 P222
请看第 6章相应的 Excel文件，特点：
1,单位成本为每个人做每项工作的总工资
2,目标是要确定哪个临时工进行哪一个工作 xij,使总成本最小。
3,供应量为 1－代表每个人都只能完成一项任务
4,需求量为 1－代表每项任务也只能由一个人来完成
5,总人数和总任务数相同其中 xij-指派临时工 i去做工作 j（结果为 0或 1）
为什么不需要 0-1条件？可以用 IF函数实现更进一步的解释
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
补充：赛尔默公司的数学模型决策变量：设 xij为指派临时工 i去做工作 j (i = 1,2,3,4; j = 1,2,3,4)
目标函数：总成本最小化
Min C = 35*14x11 + 41*14x12 + 27*14x13 + 40*14x14 +
47*12x21 + 45*12x22 + 32*12x23 + 51*12x24 +
39*13x31 + 56*13x32 + 36*13x33 + 43*13x34 +
32*15x41 + 51*15x42 + 25*15x43 + 46*15x44
约束条件 （ 由于有 4个人,4项任务，即总供应＝总需求，平衡 ）,
安 Ann,x11 + x12 + x13 + x14 = 1
伊恩 Ian,x21 + x22 + x23 + x24 = 1
琼 Joan,x31 + x32 + x33 + x34 = 1
肖恩 Sean,x41 + x42 + x43 + x44 = 1
文字处理,x11 + x21 + x31 + x41 = 1
绘图,x12 + x22 + x32 + x42 = 1
材料准备,x13 + x23 + x33 + x43 = 1
注册报名,x14 + x24 + x34 + x44 = 1
且 非负,xij ≥ 0 ( i = 1,2,3,4; j = 1,2,3,4)
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Model for Assignment Problem
指派问题模型 P223
指派问题的形式表述,
给定了一系列所要完成的任务（ tasks）以及一系列完成任务的被指派者（ assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Model for Assignment Problem
指派问题模型 P223
指派问题的假设,
被指派者的数量和任务的数量是相同的
每一个被指派者只完成一项任务
每一项任务只能由一个被指派者来完成
每个被指派者和每项任务的组合有一个相关成本
问题的目标是要确定怎样进行指派才能使得总成本达到最小
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
The Network Representation for Assignment Problem
指派问题的网络表示法 P223
指派问题是一种特殊的运输问题 P223
求解指派问题,匈牙利方法（ Hungarian method ） P224
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Variants of Assignment Problem
6.7 对指派问题变形的建模 P225
指派问题的变形,
有一些被指派者并不能进行某一些的任务 (相应的 xij=0)
任务比被指派者多，有些任务可以不完成（ 将任务的 =
改为 <=）
被指派者比要完成的任务多，有些被指派者可以没事做
（ 将被指派者的 =改为 <=）
每个被指派者可以同时被指派给多于一个的任务（ 被指派者的供应量由 1->n）
每一项任务都可以由多个被指派者共同完成（ 任务的需求量由 1->n）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Applications of Assignment Problem
指派问题的应用 P225
例子 1：在各个地点分派设备 P225
例子 2：指派工厂生产产品 P227
例子 3：设计学生入学区域 P229
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Assigning Machines to Locations
各个地点分派设备 P225
1,地点 2不能安装机器 2（ 相应的 x22＝ 0）
2,机器少地点多，有些地点不安装（地点的 ＝ 改为 <=）
P 2 2 6 在各个地点安装设备 J o b S h o p C o,M a c h i n e - L o c a t i o n P r o b l e m
单位成本C i j ( $ / 时) 地点 1 地点 2 地点 3 地点 4 地点 5
机器 1 13 16 12 14 15
机器 2 15 - 13 20 16
机器 3 4 7 10 6 7
指派 X i j 地点 1 地点 2 地点 3 地点 4 地点 5 总指派 供应量机器 1 0 0 0 1 0 1 = 1
机器 2 0 0 1 0 0 1 = 1
机器 3 1 0 0 0 0 1 = 1
总分配 1 0 1 1 0
<= <= <= <= <= 总成本( $ / 时)
需求量 1 1 1 1 1 31
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Assigning Plants to Products
指派工厂生产产品 P227
请看第 6章相应的 Excel文件,不同点：
1,求佳产品公司问题指派问题变形（ 运输问题－ >指派问题 ）
2,注意解决此类问题的关键所在,数据转换
单位指派成本 cij,原来的单位成本转换成整批成本＝单位成本 × 需求量，成本改为每家工厂生产每种产品的成本
供应量和需求量的转换问题：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂 3只能生产一种产品（＝ 1），而工厂 1,2可以生产 2种产品（ <=2）
，而产品的需求量＝ 1
3,总供应 >总需求（工厂 1,2供应的 =改为 <=2）
4,结果有时还需验证（验证是否还满足原来的运输问题要求－工厂生产能力限制）
其中 xij-指派工厂 i生产产品 j（ 0－ 1）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Designing School Attendance Zones
设计学生入学区域 P229
请看第 6章相应的 Excel文件,不同点
1,运输问题－ >指派问题
2,注意解决此类问题的关键所在,数据转换
单位指派成本 cij：原来的每位同学平均距离转换成整个地区所有同学的总距离＝每位同学平均距离 × 学生数量
供应量和需求量的转换问题（供应量＝ 1，而需求量变为一个学校接收 3个地区（ =3）
3,结果有时还需验证（验证是否还满足原来的运输问题要求：学校有最小和最大招生数（ <=,>=）
其中 xij-指派区域 i到学校 j（ 0－ 1）
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
6.8 Summary 小结 P231
运输问题考虑 （ 确实的或是比喻的 ） 从出发地运送货物到目的地 。 每一个出发地都有一个固定的供应量,
每一个目的地都有一个固定的需求量
指派问题就是要处理应当将哪一项任务指派给哪一个被指派者,才能使完成这些任务的总成本达到最小
把可能会面临的问题描述为一个运输问题或者指派问题或者它们的变形并进行分析
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
P238 案例 6.3项目选择
－指派问题
有 5个项目 （ Up,Stable,Choice,Hope,Release）
有 5位科学家和他们的投标点 （ 每个人都有 1000点 ） 情况
问将哪一个项目指派给哪一位科学家,并使得这位科学家的满意度最高 （ 指派问题 ） － 其实是总的满意度最高
可能会面临多种情况 （ 用指派问题的变形并进行分析 ）
给出一个指派问题模板和数据,请同学们自己完成 （ 包括变形问题 ） 。
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P232 习题 6.6（请将 100改为 1000),
6.7,6.13,6.15,6.21,6,22
Chapter 6
Transportation and Assignment Problems
运输问题和指派问题
RUC Information School,Ye Xiang,2007
案例（二选一）
P237案例 6.2
改：年总运输成本为 29.2亿美元（原来为 23.9） 2处注意：对于问题 e,f，也可以采用第 7章的方法
P238案例 6.3
