Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第九章
Integer Programming
整数规划
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
本章内容 P342
9.1 一般整数规划
9.2 案例分析：加利福尼亚制造公司的例子
9.3 其他一些应用
9.4 0-1变量的一些其他描述方法
9.5 一些建模的例子
9.6 小结案例 9.1 能力问题
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
本章提示
如果中文版的“规划求解”经常找不到解或有其他问题，请安装英文版 Premium Solver
。
在光盘 Premium Solver文件夹下，运行
PremSolv文件安装即可。安装完毕后，
Premium Solver 将代替 Excel原来的规划求解
，界面也变成英文的，具体 P429。有三种算法可供选择
1、标准 GRG非线性－－等同于使用没有选择“
假设线性模型”的选项的标准 Solver
2、标准 Simplex LP－－相当于使用选择了“假设线性模型”的选项的标准 Solver
3、标准 Evolutionary－－新的
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Integer Solutions
整数解
什么时候需要整数解？
得到小数解时如何处理呢？
你有什么绝招吗？
The Challenges of Rounding 舍入解的挑战
舍入解可能不是可行解
舍入解与最优解离很远
可能有多个舍入解出现
Some Solution Technique 一些求解技术
Branch-and-Bound Technique 分枝定界技术
Branch-and-Cut Technique 割平面技术
How Integer Programs are Solved 如何求解整数规划
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Branch-and-Cut Technique
割平面技术首先放弃变量的整数要求，求线性规划最优解如果最优解恰是一整数解，则最优解就是整数规划的最优解如果最优解不是整数解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已得到的规划的最优解，
但保留原可行域中所有的整数解，求解新的线性规划问题，
如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Branch-and-Cut Technique
割平面技术
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
1 2 3 4 5
1
2
3
4
5
x
1
x
2
1 2 3 4 5
1
2
3
4
5
x
1
x
2
Branch-and-Bound Technique
分枝定界技术
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
整数规划分为两大类 P342
1,integer programming
一般整数规划
2,Binary integer programming（ BIP）
0-1整数规划（是非决策问题）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.1 一般整数规划
P343例子,TBA航空公司问题
为了获得最大的年利润，公司应该购买多少飞机（小型飞机和大型飞机），各种型号又该如何组合？
先去掉整数约束,
线性规划模型 P344和图解法 P344，得到的解为 S=2,L=1.8，利润
P=11百万美元
舍入解,S=2,L=1，利润 P=7百万美元，但不是最优整数解
TBA航空公司问题违背了线性规划可分性假设（决策变量值可以是分数形式 ）。
添加整数约束：
整数规划模型,P345（多整数约束）
图解法（整数解） P346
Excel解法 (在线性规划求解中，增加整数约束 INT即可,P347）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
TBA航空公司问题的整数规划模型 P345
假设：购买小型飞机 S架，大型飞机 L架总利润最大化 Max P＝ S＋ 5L
约束条件资金,5S + 50L? 100
小 型 飞机,S? 2
且非负,S,L? 0
S,L均为整数
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
TBA航空公司整数规划电子表格模型
Excel解法：
在线性规划求解中，增加整数决策变量约束 INT即可
P 3 4 3 T B A 航空公司的问题 T B A A i r l i n e s A i r p l a n e P u r c h a s i n g P r o b l e m
小型飞机 大型飞机 单位：百万美元年利润 1 5
所花资金 可获得的资金总额单价 5 50 100 <= 100
小型飞机 大型飞机 总利润购买数量 0 2 10
<=
最多购买数量 2
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Types of Integer Programming
整数规划问题的类型 P347
Pure integer programming
纯整数规划问题
Mixed integer programming
混合整数规划问题
Binary integer programming
0-1整数规划（ BIP）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Binary integer programming
0-1整数规划问题 P347
整数变量皆为 0-1变量的问题即为 0-1整数规划问题（ Binary integer programming）
0-1变量只能在 0和 1间取值，因此很适用于 是非决策（ yes-or-no decisions）。 在这类决策中，决策者只有两种选择，接受或拒绝。
可以用 1表示接受,0表示拒绝。
这种问题在实际工作中有哪些？
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.2 案例分析：加利福尼亚制造公司的例子 P349
选址问题：要建新厂和仓库，应该将新厂建在洛杉矶（ LA）
还是旧金山（ SF），还是同时在两地建厂。管理层同时考虑建一个新仓库，但该仓库必须建在与新厂同一个城市。
P350 表 9.2 加利福尼亚制造公司问题的数据表
决策变量（ x1,x2,x3,x4）
净现值
所需资金
为是非决策问题引入 0-1决策变量（含义 P350 表 9.3）
决策间的相互关系（内在联系）
互斥方案：在洛杉矶建仓库 x3,在旧金山建仓库 x4（ x3+x4?1）
相依决策：建工厂与仓库决策的联系 （ LA,x3? x1,SF,x4? x2）
相依决策的另外一种提法：选 x3后必须也选 x1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
加利福尼亚制造公司 BIP
模型 (数学模型 P350-352)
0-1决策变量 x1,x2,x3,x4:
x1-在洛杉矶建工厂？ x2-在旧金山建工厂？
x3-在洛杉矶建仓库？ x4-在旧金山建仓库？
目标,总净现值最大化 Max NPV＝ 8x1+5x2+6x3+4x4
约束条件：
投资资金 6x1+3x2+5x3+2x4? 10
互斥（仓库）,x3+x4? 1
相依（工厂与仓库）,x3? x1,x4? x2
且 x1,x2,x3,x4=0,1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
加利福尼亚制造公司 BIP
模型的电子表格 P353
注意,0-1决策变量（ x3,x1,x4,x2），决策间的相互关系
互斥方案：在洛杉矶建仓库 x3,在旧金山建仓库 x4（ x3+x4?1）
相依决策：建工厂与仓库间的关系 （ LA,x3? x1,SF,x4? x2）
投资资金限制 （ 约束 ）
目标,NPV总净现值最大化
C a l i fo r n i a M a n u fa c tu r i n g C o,F a c i l i ty L o c a ti o n Pr o b l e m
P3 5 3 加利福尼亚制造公司问题单位：百万美元净现值 LA SF
仓库 6 4
工厂 8 5
所需资金 LA SF
仓库 5 2
花费资金 可用资金工厂 6 3 9 <= 10
建? LA SF 所建仓库数 最多仓库数仓库 0 0 0 <= 1
<= <=
工厂 1 1
总的净现值 13
Excel解法：在线性规划求解中，
增加 0-1决策变量约束 BIN即可
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
展开敏感性分析 P352
可用资金：在 5-15百万美元之间变化，对决策的影响。
可使用的方法：
方法 1：试算法,直接改,可用资金,,然后重新运行规划求解
方法 2,Solver Table
结论,投资
1100万，在洛杉矶 (LA)和旧金山 (SF)两地建厂，并在旧金山 (SF) 建仓库，从而获得期望总净现值
1700万美元可用资金 实用资金 LA SF LA SF 总的净现值
9 0 0 1 1 13
5 5 0 1 0 1 9
6 5 0 1 0 1 9
7 5 0 1 0 1 9
8 5 0 1 0 1 9
9 9 0 0 1 1 13
10 9 0 0 1 1 13
11 11 0 1 1 1 17
12 11 0 1 1 1 17
13 11 0 1 1 1 17
14 14 1 0 1 1 19
15 14 1 0 1 1 19
建仓库? 建工厂?
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.3 Applications of BIP
0-1整数规划应用 P356
投资分析
Interfaces 1990年 7－ 8月号土耳其炼油公司运用 BIP将数千百万的投资用于扩建炼油设施和能源储备上。
选址
Interfaces 1990年 1－ 2月号,AT&T公司运用 BIP模型帮助其客户选择电话营销中心,1988年 AT&T公司为其 46个客户快速而准确的作出了选址决策。
设计生产与配送网络
Interfaces 1995年 1－ 2月号数字设备公司 DEC对公司整个全球供应链进行重整，年制造成本节省 $5亿，物流成本节省 $3亿，所需资金总额减少了 $4亿。
货物配送
Interfaces1991年 1－ 2月号 Reynolds Metals Co.以 BIP为基础建立了自动的配送系统,为其 200多家工厂,仓库和供应商解决运货问题,每年节省超过 $7百万 。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.3 Applications of BIP
0-1整数规划应用 P358
相关活动的排程
Interfaces1995年 1－ 2月号，中国国家计划委员会为了最小化折现成本，和世界银行合作开发了一个 BIP模型，用于指导决策 15年内在能源领域投入至少 $2,400亿的规划，在 15年内，会为中国节省近 $64
亿。
安排资产出售
Interfaces1987年 1－ 2月号荷马特发展公司面临的一个主要问题是如何出售其购物中心和办公楼 。 有 100多处资产需要在 10年内售出 。
通过运用 BIP指导决策,使公司收入增加了 $4千万 。
航空业中的应用
Interfaces1994年 1－ 2月号 Delta 航空公司运用一个大型的 BIP模型
（包括 40,000个函数约束,20,000个 0-1决策变量,40,000个一般整数变量。）来求解飞机的分配问题。每年可为公司节省近 $1亿。
Interfaces1989年 7－ 8月号以及 1991年 1－ 2月号美洲航空公司 运用
BIP模型解决其每月的人员规划问题，每年节省了 $2千多万。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.4 0-1变量的一些其他描述方法 P360
0-1决策变量 （ Binary Decision Variable）是表示是非决策的 0-1变量，为了辅助建立纯的或混合的 BIP
模型，通常会引入一些 辅助 0-1变量 （ Auxiliary
Binary Variable），这些变量并不表示相应的是否决策。辅助 0-1变量通常以 y1,y2等形式表示。
变形 1：在伟恩德的例子中加入生产的启动成本 P361
变形 2：包含互斥产品的伟恩德例子 P364
变形 3：加入二选一约束的伟恩德例子 P368
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 1：在伟恩德的例子中加入生产的启动成本 P361
第一个变化,门和窗都有启动成本（分别为 $700和 $1300），门和窗的单位利润分别保持原来的 $300和 $500
第二个变化,一个生产批次在一个星期后即终止，因此门和窗的数量为整数
用辅助 0-1变量建模,
引入辅助 0-1变量 y1和 y2：是否生产 D,W？
目标函数变为,Max P=300D+500W-700y1-1300y2
引入的辅助 0-1变量 y1,y2与决策变量 D,W的关系：
D与 y1的关系（从工厂 1可知,D? 4y1 ）,D? My1 (M取一个相对极大值，如 99）
W与 y2的关系（从工厂 2可知,W? 6y2 ）,W? My2
W y n d o r G l a s s C o,P r o d u c t - M i x w i t h S e t u p C o s t s
P 3 6 5 变形 1,加入启动成本门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
启动成本 $700 $ 1,3 0 0
使用时数 每周可得时数工厂 1 1 0 0 <= 4
工厂 2 0 2 12 <= 12
工厂 3 3 2 12 <= 18
门 D o o r s 窗 W i n d o w s
每周生产数量 0 6
<= <= 产品总利润 $ 3,0 0 0
M y i 0 99 相对极大值 M 总启动成本 $ 1,3 0 0
是否生产 yi 0 1 99 总利润 $ 1,7 0 0
每个产品所需生产时数图解法 P363
图 9.7
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 1：在伟恩德的例子中加入生产的启动成本的数学模型 P362-364
决策变量：
整数决策变量,D,W为门和窗的生产数量辅助 0-1变量,y1,y2是否生产 D,W？
目标,净利润最大化 Max P=300D+500W-700y1-1300y2
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
y1,y2与 D,W的关系,D? My1,W? My2 （其中 M取 99）
且非负,D,W? 0
D,W均为整数
y1,y2为 0或 1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 2：包含互斥产品的伟恩德例子 P364
不考虑变形 1，假设仅对最初的伟恩德作如下的变形
变形 2：两种新产品门和窗具有相同的用户，是互相竞争的，因此，管理层决定不同时生产两种产品，而是只能选择其中的一种，这样,D=0
或 W=0（或两者均为 0）
同变形 1一样，用辅助 0-1变量建模：
引入辅助 0-1变量 y1和 y2：是否生产 D,W？－－ 同变形 1
D与 y1的关系和 W与 y2的关系,D? My1,W? My2 －－ 同变形 1
表示两种产品是互斥的,y1+y2? 1－－ 新的
D,W不需要限制在整数范围内，所以是一个 混合 BIP模型
目标函数,P=300D+500W －－ 同最初的伟恩德
W y n d o r G l a s s C o,w i t h M u t u a l l y E x c l u s i v e P r o d u c t s
P 3 6 7 变形 2,包含互斥产品的伟恩德例子门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
使用时数 每周可得时数工厂 1 1 0 0 <= 4
工厂 2 0 2 12 <= 12
工厂 3 3 2 12 <= 18
D o o r s W i n d o w s
每周生产数量 0 6
<= <= 生产 最多生产
M y i 0 99 产品种数 产品种数是否生产 yi 0 1 1 <= 1
相对极大值 M 99 总利润 $ 3,0 0 0
每个产品所需生产时数图解法 P366
图 9.9
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 2：包含互斥产品的伟恩德例子的数学模型 P364-366
决策变量：
决策变量,D,W为门和窗的生产数量辅助 0-1变量,y1,y2是否生产 D,W？
目标,净利润最大化 Max P=300D+500W
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
y1,y2与 D,W的关系,D? My1,W? My2 （其中 M取 99）
产品互斥,y1+y2? 1
且非负,D,W? 0
y1,y2为 0或 1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 3：加入二选一约束的伟恩德例子 P368
假设仅对最初的伟恩德作如下的变形
变形 3：公司最近建了一个与工厂 3类似的新厂（工厂 4），因此，新厂也可以生产这两种新产品。但是，为了管理上的原因
，管理层决定只在一个厂内生产新的产品，同时要选取能获得产品组合最大利润的那一家工厂
方法 1：可以分别考虑，然后取使得利润最大的那一家工厂
方法 2：用辅助 0-1变量建模：
引入辅助 0-1变量 y（ 0－选择工厂 3,1－选择工厂 4）,
y与工厂 3、工厂 4的关系 (通过资源约束来实现）：
3D+2W? 18+My －－ 工厂 3约束
2D+4W? 28+M(1-y) －－ 工厂 4约束其中,M可以取一个较大值，如 99。这时，如果选择一家工厂，则另一家工厂的资源就很多，表示不受这家工厂资源的限制
目标函数,P=300D+500W －－ 同最初的伟恩德
D,W不需要限制在整数范围内，所以是一个混合 BIP模型图解法 P369
图 9.11
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 3：加入二选一约束的伟恩德例子 P371
加入二选一约束的伟恩德例子的电子表格模型
W y n d o r G l a s s C o,P r o b l e m w i t h E i t h e r - O r C o n s t r a i n t s
P 3 7 1 变形 3,加入二选一约束的伟恩德例子门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
使用时数修正的每周可得时数每周可得时数工厂 1 1 0 4 <= 4 4
工厂 2 0 2 10 <= 12 12
工厂 3 3 2 22 <= 117 18
工厂 4 2 4 28 <= 28 28
门 D o o r s 窗 W i n d o w s 相对极大值 M 99
每周生产数量 4 5
用哪家工厂? ( 0 = 工厂 3,1 = 工厂 4) 1 总利润 $ 3,7 0 0
每个产品所需生产时数在 Excel中，相对极大值 M需要数值化，从车间 1和车间 2的约束中可以看出,D的最大取值为 4,W的最大取值为 6，分别代入车间 3和车间
4约束的左边，得到最多所需的工时分别为 24和 32
，而车间 3和车间
4的可用工时分别为 18和 28，因此
,M的取值只需不小于 Max（ 24-
18,32-28）即可
，这里取 99
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 3：加入二选一约束的伟恩德例子的数学模型 P368-370（ 右边是另外一种解法 ）
决策变量：
决策变量,D,W为门和窗的生产数量辅助 0-1变量,y在工厂 3或工厂 4生产
（ 0－选择工厂 3,1－选择工厂 4）
？
目标,净利润最大化 Max P=300D+500W
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18＋ My
工厂 4,2D+4W? 28+M(1-y)
且非负,D,W? 0
y=0或 1
决策变量：
决策变量,D,W为门和窗的生产数量辅助 0-1变量,y1,y2是否在工厂 3或工厂 4生产？（ 1表示是）
目标,净利润最大化 Max P=300D+500W
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18＋ M(1-y1)
工厂 4,2D+4W? 28+M(1-y2)
工厂 3,4互斥,y1+y2=1
且非负,D,W? 0
y1,y2=0或 1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.5 一些建模例子 P370
例子 1：增加管理限制
例子 2：不符合比例性要求
例子 3：航班的人员排程问题
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 1：增加管理限制 P371
固特产品公司的研发部最近开发出了三种新产品，但是，为了防止生产线的过度多元化，公司的管理层增加了如下的约束：
约束 1：在三种新产品中，最多只能选择 2种进行生产（引入辅助 0-1变量 y1,y2,y3，注意与三种新产品产量 x1,x2,x3的关系）
y1+y2+y3? 2
x1? My1,x2? My2,x3? My3 (M取 99)
约束 2：两个工厂中必须选出一个专门生产新产品（引入辅助 0-1变量 y4,0--选工厂 1,1--选工厂 2，注意与 2家工厂资源约束关系）
3x1+4x2+2x3? 30+My4 （工厂 1）
4x1+6x2+2x3? 40+M(1-y4) （工厂 2）
还有三种产品每周的生产量受到销售量的限制（?）
是一个混合 BIP模型
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 1：增加管理限制（续）
增加管理限制 的电子表格模型
G o o d P r o d u c t s C o,w i t h M a n a g e r i a l R e s t r i c t i o n s
P 3 7 3 例子 1,增加管理限制单位：千美元产品 1 产品 2 产品 3
单位利润 5 7 3
使用时数修正的每周可得时数每周可得时数工厂 1 3 4 2 3 4,5 <= 129 30
工厂 2 4 6 2 40 <= 40 40
产品 1 产品 2 产品 3
每周生产数量 5,5 0 9
<= <= <= 相对极大值 M 99
M y i 99 0 99
最大销售量 7 5 9 生产 最多生产产品种数 产品种数是否生产 yi 1 0 1 2 <= 2
用哪家工厂? ( 0 = 工厂 1,1 = 工厂 2) 1 总利润 5 4,5
每个产品所需生产时数
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 1：增加管理限制
（数学模型 P372－ 374）
决策变量：
决策变量,x1,x2,x3为三种新产品的每周生产数量辅助 0-1变量,y1,y2,y3三种新产品是否生产？
辅助 0-1变量,y4在工厂 1或工厂 2生产（ 0－选工厂 1,1－选工厂 2）？
目标,总利润最大化 Max P=5x1+7x2+3x3
约束条件：
最多选 2种产品,y1+y2+y3? 2
y1,y2,y3与 x1,x2,x3的关系,x1? My1,x2? My2,x3? My3 (其中 M取 99)
工厂 1,3x1+4x2+2x3? 30+My4
工厂 2,4x1+6x2+2x3? 40+M(1-y4)
最大销售量限制,x1? 7,x2? 5,x3? 9
（说明：可以合并,y1,y2,y3与 x1,x2,x3的关系”和“最大销售量限制”：
x1? 7y1,x2? 5y2,x3? 9y3）
且 非负,x1,x2,x3? 0
y1,y2,y3,y4=0,1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
补充思考题（有启动成本）
有 1,2,3,4四种零件均可在设备 A或设备 B
上加工，已知在这两种设备上分别加工一个零件的费用如表所示。
又知设备 A或 B只要有零件加工均需要设备的启动费用，分别为 100元和 150元。
现要求加工 1,2,3,4零件各 3件。问应如何安排生产使总的费用最小。
试建立线性规划模型并求解零件 1 零件 2 零件 3 零件 4
设备 A 50 80 90 40
设备 B 30 100 50 70
结果：在设备 A上加工零件 2和 4各 3件
，在设备 B上加工零件 1和 3各 3件，总费用为 850元。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 2：不符合比例性要求 P374
超级苏滋公司（ Supersuds Corp.）正在为其下一年的新产品制定营销计划，并准备在全国电视网上购买 5个广告片，以促销三种产品。每个广告只针对一种产品，因此，这一问题就是如何将 5个广告分配给三种产品，
每种产品最多可以有三个广告，最少可以不作广告。
数据 P375，注意,电视广告片数与产品利润不是线性关系
S u p e r s u d s C o r p,M a r k e t i n g P l a n
P 3 7 8 例子 2,不符合比例性要求单位：百万美元利润 产品 1 产品 2 产品 3
电视 1 1 0 -1
广告 2 3 2 2
片数 3 3 3 4
决策变量 X i j,是否将电视广告片数 i 给产品 j
产品 1 产品 2 产品 3
电视 1 0 0 0
广告 2 1 0 0 总利润片数 3 0 0 1 7
T o t a l 1 0 1
<= <= <=
M a x O f O n e 1 1 1
实际总片数 所需总片数广告片数 2 0 3 5 = 5
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 2：不符合比例性要求
（数学模型 P375－ 377）
决策变量：
决策变量,x1,x2,x3分配给产品 1,2,3的广告数量辅助 0-1变量,yij是否给产品 i分配电视广告片数 j
目标,总利润最大化 Max P=y11+3y12+3y13 + 0 y21+2y22+3y23 - y31+2y32+4y33
约束条件：
每种产品广告数量和是否分配关系：
产品 1,x1＝ y11+2y12+3y13
产品 2,x2＝ y21+2y22+3y23
产品 3,x3＝ y31+2y32+3y33
每种产品最多分配一次：
产品 1,y11 + y12 + y13? 1
产品 2,y21 + y22 + y23? 1
产品 3,y31 + y32 + y33? 1
广告片数,x1 + x2 + x3 = 5
每种产品最多广告数量,x1,x2,x3? 3
且 非负 x1,x2,x3? 0,yij=0,1（ i=1,2,3; j=1,2,3）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 2：不符合比例性要求
（数学模型,补充另外一种写法 ）
决策变量：
0-1决策变量 xij：是否将电视广告片数 i 分配给产品 j
目标,总利润最大化 Max P=x11+3x21+3x31 +0x12+2x22+3x32 - x13+2x23+4x33
约束条件：
每种产品最多分配一次：
产品 1,x11 + x21 + x31? 1
产品 2,x12 + x22 + x32? 1
产品 3,x13 + x23 + x33? 1
广告片数,(x11+2x21+3x31 )+(x12+2x22+3x32 )+(x13+2x23+3x33 ) = 5
且 xij=0,1（ i=1,2,3; j=1,2,3）
注意：我这里直接用“类似指派问题”的想法，书上对此进行了解释。
可以用此方法求解
P261使总时间最短（奎克公司）
，即第 7章 PPT中的“思考题 2”
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
补充思考题 （不符合比例性要求）
某建设公司有 4个正在建设的项目，按目前所配给的人力
、设备和材料，这 4个项目分别可以在 15,20,18和 25周内完成，管理部门希望提前完成，并决定追加 35,000元资金分配给这 4个项目。这样，新的完工时间以分配给各个项目的追加资金的函数形式给出，如表所示。试问这
35,000元如何分配给这 4个项目，以使得总完工时间提前为最多（假定追加的资金只能以 5,000元一组进行分配）
试建立线性规划模型并求解结果：项目 1为 5千元，项目 2,3,4均为 10千元，总完工时间为 55周（提前了 23周）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 3：航班的人员排程问题 P377
西南航空公司 需要将 3组机组人员分配给 11个航班，数据如 P377的表 9.8。
用 0-1变量建模,xi－是否将 i次序的航班分配给某一机组人员 (i=1,…… 12)
约束：保证每个航班有机组人员，且只有 3组机组人员。
目标：总成本最小
纯 BIP模型（ 本题可以用 P386习题 9.20的意思来理解）
S o u t h w e s t A i r w a y s C r e w S c h e d u l i n g P r o b l e m
P 3 8 0 航班的人员排程问题 单位：千美元航班次序
1 2 3 4 5 6 7 8 9 10 11 12
成本 2 3 4 6 7 5 7 8 9 9 8 9
是否含有此航班 I n c l u d e s S e g m e n t? 总数 至少有一个旧金山S F O - 洛杉矶L A X 1 0 0 1 0 0 1 0 0 1 0 0 1 >= 1
旧金山S F O - 丹佛D E N 0 1 0 0 1 0 0 1 0 0 1 0 1 >= 1
旧金山S F O - 西雅图S E A 0 0 1 0 0 1 0 0 1 0 0 1 1 >= 1
洛杉矶L A X - 芝加哥O R D 0 0 0 1 0 0 1 0 1 1 0 1 1 >= 1
洛杉矶 L A X - 旧金山 S F O 1 0 0 0 0 1 0 0 0 1 1 0 1 >= 1
芝加哥 O R D - 丹佛 D E N 0 0 0 1 1 0 0 0 1 0 0 0 1 >= 1
芝加哥 O R D - 西雅图 SEA 0 0 0 0 0 0 1 1 0 1 1 1 1 >= 1
丹佛 D E N - 旧金山 S F O 0 1 0 1 1 0 0 0 1 0 0 0 1 >= 1
丹佛D E N - 芝加哥O R D 0 0 0 0 1 0 0 1 0 0 1 0 1 >= 1
西雅图 SEA- 旧金山 S F O 0 0 1 0 0 0 1 1 0 0 0 1 1 >= 1
西雅图 SEA- 洛杉矶 L A X 0 0 0 0 0 1 0 0 1 1 1 1 1 >= 1
1 2 3 4 5 6 7 8 9 10 11 12 总次序 机组数此次序是否飞? 0 0 1 1 0 0 0 0 0 0 1 0 3 <= 3
总成本 18
从 12个航班次序中选择 3个，
使得 11个航班都有机组人员
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 3：航班的人员排程问题
（数学模型 P379）
决策变量：
0-1决策变量,xi是否将 i次序的航班分配给某一机组人员 (i=1,2,…,12)
目标,总成本最小化 Min C=2x1+3x2+4x3 +6x4+7x5+5x6 +7x7+8x8+9x9+9x10+8x11+9x12
约束条件（保证每个航班有机组人员，且只有 3组机组人员,0-1变量）：
SFO-LAX航班,x1 +x4+x7+x10? 1
SFO-DEN航班,x2 +x5+x8+x11? 1
……
SEA-LAX航班,x6 +x9+x10+x11 +x12? 1
只有 3组机组人员,x1+x2+x3 +x4+x5+x6 +x7+x8+x9+x10+x11+x12 = 3
且
xi = 0,1（ i=1,2,…,12 ）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.6 Summary 小结 P381
线性规划可分性假设允许决策变量取包括分数在内的任何实数,当一些决策变量只能取整数时,就必须采用整数规划 。
每个 0-1整数规划 （ BIP） 模型都可以同时考虑多个选项,一个 0-1决策变量对应于一个选项,而混合的 BIP
模型还可以包含一些连续的决策变量 。
在处理一些无法直接建立 BIP模型的问题时,运用辅助
0-1变量是很有用的,辅助变量可以将问题标准化,从而可以用标准的算法求解 。 辅助变量可用来处理很多问题 。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题具体请见 Excel文件企业内部网 IN 安装时间期限第 1 个月 第 2 个月 第 3 个月 第 4 个月 第 5 个月
IN 培训在销售部门安装 IN
在生产部门安装 IN
在仓库安装 IN
在营销部门安装 IN
各部门使用 IN 的员工数 各种型号服务器的成本以及可支持的员工数部门 员工数 服务器类型 支持的员工数 服务器成本销售 60 标准 PC 30 $ 2,5 0 0
生产 200 加强型P C 80 $ 5,0 0 0
仓库 30 S G I 工作站 200 $ 1 0,0 0 0
营销 75 S u n 工作站 2000 $ 2 5,0 0 0
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题
a,以每月采购的方式评估服务器的数量和类型。对于每一个月，建立一个整数规划模型（在上个月的结果情况下，使本月的成本最小），然后将各月的费用相加，得到总费用（ 贪婪算法 ）。
1,第一个月，由于没有安装要求，从成本最小化考虑，本月不买任何类型的服务器
2,第二个月，销售部门有安装要求（?60)，决策变量 xi:本月购进第 i种型号服务器的台数（整数,INT），由于第一个月没有购买，资金没有用，则 2月份可以使用的资金是 $9500，注意：有折扣（ SGI－ 10％
,SUN－ 25％ )，结果,2月购买一台加强型 PC服务器，可支持的员工数为 80(其实也可以购买 2台标准 PC服务器,但可支持的员工数为
2*30=60)，本月费用为 $5000
3,第三个月，生产部门有安装要求（?200)，而第二个月多了 80-60=20
台，所以只需 200-20=180台即可，决策变量 xi:本月购进第 i种型号服务器的台数（整数,INT），此时没有资金限制，也没有折扣，结果
,3月购买一台 SGI工作站，加上 2月份购买的 1台加强型 PC服务器，
可支持的员工数为 80+200=280，本月费用为 $10000。也满足生产部门至少需要三种性能比较好的服务器中的一种。
4,第四、五月，同第三个月。
结果：最后总的费用 =5000+10000+2500+5000=22,500
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题 (续 )
b、综合考虑，整个问题建立一个整数规划模型
1,决策变量 xij：第 i个月应该购进第 j种型号服务器的台数（整数,INT
），用的是满足累计员工数,所以约束的左右两边，从第 2个月开始就为累计到本月,1-2月的资金限制也是采用累计数，所以 2月份实际所花的累计成本 =1月＋ 2月。
2,注意：前面 1,2月受到资金限制（ $9500），且有折扣（ SGI－ 10％
,SUN－ 25％ )。
3,还需注意：生产部门至少需要三种性能比较好的服务器中的一种（
即在 1－ 3月购买）
结果：在 1,3月份各购买一台 SGI工作站（共 2台），成本为 19,000。
c,第一种方法是贪婪算法，没有全盘考虑 。
讨论题：
由于 1,2月有折扣，所以如果能在 1,2月份购买会合算些，此时就不能受到资金的限制（ $9500）：在 b中去掉 1,2月累计资金的限制
（直接在规划求解中实现）即可，结果：在 1或 2月份购买 2台 SGI工作站，成本为 18,000。支持员工数＝ 2× 200＝ 400人
还有：是否可以在 1,2月买一台 SUN，成本＝ 25,000× （ 1－ 25％）
＝ 18,750，但支持员工数＝ 2000人
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题（续）
b还有一种更为简单的方法：因为前面 1,2月有资金限制（ $9500），
且有折扣（ SGI－ 10％,SUN－ 25％ )，而后面 3个月没有，所以决策变量 x1j（ j=1,2,3,4）,1,2月应该购进第 j种型号服务器的台数 (整数 )
决策变量 x2j（ j=1,2,3,4）,3－ 5月应该购进第 j种型号服务器的台数 (整数 )
P 3 8 7 案例 9,1 能力问题
b,还有一种更为简单的方法：因为前面1,2 月有资金限制（9,5 0 0 $ ），且有折扣（S G I －1 0 ％，S U N －2 5 ％),而后面3 个月没有，所以决策变量X 1 j （j = 1,2,3,4 ）：1,2 月应该购进第j 种型号服务器的台数( 整数)
决策变量X 2 j （j = 1,2,3,4 ）：3 －5 月应该购进第j 种型号服务器的台数( 整数)
标准 PC 加强型P C S G I 工作站 S u n 工作站 使用资金支持的员工数 30 80 200 2000
服务器成本 ( 3 - 5 月 ) $ 2,5 0 0 $ 5,0 0 0 $ 1 0,0 0 0 $ 2 5,0 0 0 $ 1 0,0 0 0
1 - 2 月折扣 0% 0% 10% 25% 前 2 个月累计资金限制
1,2 月成本 $ 2,5 0 0 $ 5,0 0 0 $ 9,0 0 0 $ 1 8,7 5 0 $ 9,0 0 0 <= $ 9,5 0 0
服务器购买数 标准 PC 加强型P C S G I 工作站 S u n 工作站 累计实际支持 累计需要支持
1 - 2 月 0 0 1 0 200 >= 60
3 - 5 月 0 0 1 0 400 >= 365
购买各种服务器的台数 S U M
0 0 2 0 2 >= 1
生产部门要求总成本 $ 1 9,0 0 0
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P382 习题：
9.5 9.11 9.13（注意 M的取值）
9.15 9.16（请参考 P370例子 2）
9.20 （类似 P377航班的人员排程问题 ）
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策第九章
Integer Programming
整数规划
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
本章内容 P342
9.1 一般整数规划
9.2 案例分析：加利福尼亚制造公司的例子
9.3 其他一些应用
9.4 0-1变量的一些其他描述方法
9.5 一些建模的例子
9.6 小结案例 9.1 能力问题
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
本章提示
如果中文版的“规划求解”经常找不到解或有其他问题，请安装英文版 Premium Solver
。
在光盘 Premium Solver文件夹下，运行
PremSolv文件安装即可。安装完毕后，
Premium Solver 将代替 Excel原来的规划求解
，界面也变成英文的，具体 P429。有三种算法可供选择
1、标准 GRG非线性－－等同于使用没有选择“
假设线性模型”的选项的标准 Solver
2、标准 Simplex LP－－相当于使用选择了“假设线性模型”的选项的标准 Solver
3、标准 Evolutionary－－新的
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Integer Solutions
整数解
什么时候需要整数解？
得到小数解时如何处理呢？
你有什么绝招吗？
The Challenges of Rounding 舍入解的挑战
舍入解可能不是可行解
舍入解与最优解离很远
可能有多个舍入解出现
Some Solution Technique 一些求解技术
Branch-and-Bound Technique 分枝定界技术
Branch-and-Cut Technique 割平面技术
How Integer Programs are Solved 如何求解整数规划
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Branch-and-Cut Technique
割平面技术首先放弃变量的整数要求，求线性规划最优解如果最优解恰是一整数解，则最优解就是整数规划的最优解如果最优解不是整数解，则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已得到的规划的最优解，
但保留原可行域中所有的整数解，求解新的线性规划问题，
如果最优解仍不是整数解，再增加附加的约束将其切除，但仍保持最初可行域中所有的整数解，如此一直进行，直至得到一个整数的最优解为止。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Branch-and-Cut Technique
割平面技术
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
1 2 3 4 5
1
2
3
4
5
x
1
x
2
1 2 3 4 5
1
2
3
4
5
x
1
x
2
Branch-and-Bound Technique
分枝定界技术
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
整数规划分为两大类 P342
1,integer programming
一般整数规划
2,Binary integer programming（ BIP）
0-1整数规划（是非决策问题）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.1 一般整数规划
P343例子,TBA航空公司问题
为了获得最大的年利润，公司应该购买多少飞机（小型飞机和大型飞机），各种型号又该如何组合？
先去掉整数约束,
线性规划模型 P344和图解法 P344，得到的解为 S=2,L=1.8，利润
P=11百万美元
舍入解,S=2,L=1，利润 P=7百万美元，但不是最优整数解
TBA航空公司问题违背了线性规划可分性假设（决策变量值可以是分数形式 ）。
添加整数约束：
整数规划模型,P345（多整数约束）
图解法（整数解） P346
Excel解法 (在线性规划求解中，增加整数约束 INT即可,P347）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
TBA航空公司问题的整数规划模型 P345
假设：购买小型飞机 S架，大型飞机 L架总利润最大化 Max P＝ S＋ 5L
约束条件资金,5S + 50L? 100
小 型 飞机,S? 2
且非负,S,L? 0
S,L均为整数
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
TBA航空公司整数规划电子表格模型
Excel解法：
在线性规划求解中，增加整数决策变量约束 INT即可
P 3 4 3 T B A 航空公司的问题 T B A A i r l i n e s A i r p l a n e P u r c h a s i n g P r o b l e m
小型飞机 大型飞机 单位：百万美元年利润 1 5
所花资金 可获得的资金总额单价 5 50 100 <= 100
小型飞机 大型飞机 总利润购买数量 0 2 10
<=
最多购买数量 2
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Types of Integer Programming
整数规划问题的类型 P347
Pure integer programming
纯整数规划问题
Mixed integer programming
混合整数规划问题
Binary integer programming
0-1整数规划（ BIP）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Binary integer programming
0-1整数规划问题 P347
整数变量皆为 0-1变量的问题即为 0-1整数规划问题（ Binary integer programming）
0-1变量只能在 0和 1间取值，因此很适用于 是非决策（ yes-or-no decisions）。 在这类决策中，决策者只有两种选择，接受或拒绝。
可以用 1表示接受,0表示拒绝。
这种问题在实际工作中有哪些？
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.2 案例分析：加利福尼亚制造公司的例子 P349
选址问题：要建新厂和仓库，应该将新厂建在洛杉矶（ LA）
还是旧金山（ SF），还是同时在两地建厂。管理层同时考虑建一个新仓库，但该仓库必须建在与新厂同一个城市。
P350 表 9.2 加利福尼亚制造公司问题的数据表
决策变量（ x1,x2,x3,x4）
净现值
所需资金
为是非决策问题引入 0-1决策变量（含义 P350 表 9.3）
决策间的相互关系（内在联系）
互斥方案：在洛杉矶建仓库 x3,在旧金山建仓库 x4（ x3+x4?1）
相依决策：建工厂与仓库决策的联系 （ LA,x3? x1,SF,x4? x2）
相依决策的另外一种提法：选 x3后必须也选 x1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
加利福尼亚制造公司 BIP
模型 (数学模型 P350-352)
0-1决策变量 x1,x2,x3,x4:
x1-在洛杉矶建工厂？ x2-在旧金山建工厂？
x3-在洛杉矶建仓库？ x4-在旧金山建仓库？
目标,总净现值最大化 Max NPV＝ 8x1+5x2+6x3+4x4
约束条件：
投资资金 6x1+3x2+5x3+2x4? 10
互斥（仓库）,x3+x4? 1
相依（工厂与仓库）,x3? x1,x4? x2
且 x1,x2,x3,x4=0,1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
加利福尼亚制造公司 BIP
模型的电子表格 P353
注意,0-1决策变量（ x3,x1,x4,x2），决策间的相互关系
互斥方案：在洛杉矶建仓库 x3,在旧金山建仓库 x4（ x3+x4?1）
相依决策：建工厂与仓库间的关系 （ LA,x3? x1,SF,x4? x2）
投资资金限制 （ 约束 ）
目标,NPV总净现值最大化
C a l i fo r n i a M a n u fa c tu r i n g C o,F a c i l i ty L o c a ti o n Pr o b l e m
P3 5 3 加利福尼亚制造公司问题单位：百万美元净现值 LA SF
仓库 6 4
工厂 8 5
所需资金 LA SF
仓库 5 2
花费资金 可用资金工厂 6 3 9 <= 10
建? LA SF 所建仓库数 最多仓库数仓库 0 0 0 <= 1
<= <=
工厂 1 1
总的净现值 13
Excel解法：在线性规划求解中，
增加 0-1决策变量约束 BIN即可
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
展开敏感性分析 P352
可用资金：在 5-15百万美元之间变化，对决策的影响。
可使用的方法：
方法 1：试算法,直接改,可用资金,,然后重新运行规划求解
方法 2,Solver Table
结论,投资
1100万，在洛杉矶 (LA)和旧金山 (SF)两地建厂，并在旧金山 (SF) 建仓库，从而获得期望总净现值
1700万美元可用资金 实用资金 LA SF LA SF 总的净现值
9 0 0 1 1 13
5 5 0 1 0 1 9
6 5 0 1 0 1 9
7 5 0 1 0 1 9
8 5 0 1 0 1 9
9 9 0 0 1 1 13
10 9 0 0 1 1 13
11 11 0 1 1 1 17
12 11 0 1 1 1 17
13 11 0 1 1 1 17
14 14 1 0 1 1 19
15 14 1 0 1 1 19
建仓库? 建工厂?
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.3 Applications of BIP
0-1整数规划应用 P356
投资分析
Interfaces 1990年 7－ 8月号土耳其炼油公司运用 BIP将数千百万的投资用于扩建炼油设施和能源储备上。
选址
Interfaces 1990年 1－ 2月号,AT&T公司运用 BIP模型帮助其客户选择电话营销中心,1988年 AT&T公司为其 46个客户快速而准确的作出了选址决策。
设计生产与配送网络
Interfaces 1995年 1－ 2月号数字设备公司 DEC对公司整个全球供应链进行重整，年制造成本节省 $5亿，物流成本节省 $3亿，所需资金总额减少了 $4亿。
货物配送
Interfaces1991年 1－ 2月号 Reynolds Metals Co.以 BIP为基础建立了自动的配送系统,为其 200多家工厂,仓库和供应商解决运货问题,每年节省超过 $7百万 。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.3 Applications of BIP
0-1整数规划应用 P358
相关活动的排程
Interfaces1995年 1－ 2月号，中国国家计划委员会为了最小化折现成本，和世界银行合作开发了一个 BIP模型，用于指导决策 15年内在能源领域投入至少 $2,400亿的规划，在 15年内，会为中国节省近 $64
亿。
安排资产出售
Interfaces1987年 1－ 2月号荷马特发展公司面临的一个主要问题是如何出售其购物中心和办公楼 。 有 100多处资产需要在 10年内售出 。
通过运用 BIP指导决策,使公司收入增加了 $4千万 。
航空业中的应用
Interfaces1994年 1－ 2月号 Delta 航空公司运用一个大型的 BIP模型
（包括 40,000个函数约束,20,000个 0-1决策变量,40,000个一般整数变量。）来求解飞机的分配问题。每年可为公司节省近 $1亿。
Interfaces1989年 7－ 8月号以及 1991年 1－ 2月号美洲航空公司 运用
BIP模型解决其每月的人员规划问题，每年节省了 $2千多万。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.4 0-1变量的一些其他描述方法 P360
0-1决策变量 （ Binary Decision Variable）是表示是非决策的 0-1变量，为了辅助建立纯的或混合的 BIP
模型，通常会引入一些 辅助 0-1变量 （ Auxiliary
Binary Variable），这些变量并不表示相应的是否决策。辅助 0-1变量通常以 y1,y2等形式表示。
变形 1：在伟恩德的例子中加入生产的启动成本 P361
变形 2：包含互斥产品的伟恩德例子 P364
变形 3：加入二选一约束的伟恩德例子 P368
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 1：在伟恩德的例子中加入生产的启动成本 P361
第一个变化,门和窗都有启动成本（分别为 $700和 $1300），门和窗的单位利润分别保持原来的 $300和 $500
第二个变化,一个生产批次在一个星期后即终止，因此门和窗的数量为整数
用辅助 0-1变量建模,
引入辅助 0-1变量 y1和 y2：是否生产 D,W？
目标函数变为,Max P=300D+500W-700y1-1300y2
引入的辅助 0-1变量 y1,y2与决策变量 D,W的关系：
D与 y1的关系（从工厂 1可知,D? 4y1 ）,D? My1 (M取一个相对极大值，如 99）
W与 y2的关系（从工厂 2可知,W? 6y2 ）,W? My2
W y n d o r G l a s s C o,P r o d u c t - M i x w i t h S e t u p C o s t s
P 3 6 5 变形 1,加入启动成本门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
启动成本 $700 $ 1,3 0 0
使用时数 每周可得时数工厂 1 1 0 0 <= 4
工厂 2 0 2 12 <= 12
工厂 3 3 2 12 <= 18
门 D o o r s 窗 W i n d o w s
每周生产数量 0 6
<= <= 产品总利润 $ 3,0 0 0
M y i 0 99 相对极大值 M 总启动成本 $ 1,3 0 0
是否生产 yi 0 1 99 总利润 $ 1,7 0 0
每个产品所需生产时数图解法 P363
图 9.7
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 1：在伟恩德的例子中加入生产的启动成本的数学模型 P362-364
决策变量：
整数决策变量,D,W为门和窗的生产数量辅助 0-1变量,y1,y2是否生产 D,W？
目标,净利润最大化 Max P=300D+500W-700y1-1300y2
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
y1,y2与 D,W的关系,D? My1,W? My2 （其中 M取 99）
且非负,D,W? 0
D,W均为整数
y1,y2为 0或 1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 2：包含互斥产品的伟恩德例子 P364
不考虑变形 1，假设仅对最初的伟恩德作如下的变形
变形 2：两种新产品门和窗具有相同的用户，是互相竞争的，因此，管理层决定不同时生产两种产品，而是只能选择其中的一种，这样,D=0
或 W=0（或两者均为 0）
同变形 1一样，用辅助 0-1变量建模：
引入辅助 0-1变量 y1和 y2：是否生产 D,W？－－ 同变形 1
D与 y1的关系和 W与 y2的关系,D? My1,W? My2 －－ 同变形 1
表示两种产品是互斥的,y1+y2? 1－－ 新的
D,W不需要限制在整数范围内，所以是一个 混合 BIP模型
目标函数,P=300D+500W －－ 同最初的伟恩德
W y n d o r G l a s s C o,w i t h M u t u a l l y E x c l u s i v e P r o d u c t s
P 3 6 7 变形 2,包含互斥产品的伟恩德例子门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
使用时数 每周可得时数工厂 1 1 0 0 <= 4
工厂 2 0 2 12 <= 12
工厂 3 3 2 12 <= 18
D o o r s W i n d o w s
每周生产数量 0 6
<= <= 生产 最多生产
M y i 0 99 产品种数 产品种数是否生产 yi 0 1 1 <= 1
相对极大值 M 99 总利润 $ 3,0 0 0
每个产品所需生产时数图解法 P366
图 9.9
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 2：包含互斥产品的伟恩德例子的数学模型 P364-366
决策变量：
决策变量,D,W为门和窗的生产数量辅助 0-1变量,y1,y2是否生产 D,W？
目标,净利润最大化 Max P=300D+500W
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18
y1,y2与 D,W的关系,D? My1,W? My2 （其中 M取 99）
产品互斥,y1+y2? 1
且非负,D,W? 0
y1,y2为 0或 1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 3：加入二选一约束的伟恩德例子 P368
假设仅对最初的伟恩德作如下的变形
变形 3：公司最近建了一个与工厂 3类似的新厂（工厂 4），因此，新厂也可以生产这两种新产品。但是，为了管理上的原因
，管理层决定只在一个厂内生产新的产品，同时要选取能获得产品组合最大利润的那一家工厂
方法 1：可以分别考虑，然后取使得利润最大的那一家工厂
方法 2：用辅助 0-1变量建模：
引入辅助 0-1变量 y（ 0－选择工厂 3,1－选择工厂 4）,
y与工厂 3、工厂 4的关系 (通过资源约束来实现）：
3D+2W? 18+My －－ 工厂 3约束
2D+4W? 28+M(1-y) －－ 工厂 4约束其中,M可以取一个较大值，如 99。这时，如果选择一家工厂，则另一家工厂的资源就很多，表示不受这家工厂资源的限制
目标函数,P=300D+500W －－ 同最初的伟恩德
D,W不需要限制在整数范围内，所以是一个混合 BIP模型图解法 P369
图 9.11
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 3：加入二选一约束的伟恩德例子 P371
加入二选一约束的伟恩德例子的电子表格模型
W y n d o r G l a s s C o,P r o b l e m w i t h E i t h e r - O r C o n s t r a i n t s
P 3 7 1 变形 3,加入二选一约束的伟恩德例子门 D o o r s 窗 W i n d o w s
单位利润 $300 $500
使用时数修正的每周可得时数每周可得时数工厂 1 1 0 4 <= 4 4
工厂 2 0 2 10 <= 12 12
工厂 3 3 2 22 <= 117 18
工厂 4 2 4 28 <= 28 28
门 D o o r s 窗 W i n d o w s 相对极大值 M 99
每周生产数量 4 5
用哪家工厂? ( 0 = 工厂 3,1 = 工厂 4) 1 总利润 $ 3,7 0 0
每个产品所需生产时数在 Excel中，相对极大值 M需要数值化，从车间 1和车间 2的约束中可以看出,D的最大取值为 4,W的最大取值为 6，分别代入车间 3和车间
4约束的左边，得到最多所需的工时分别为 24和 32
，而车间 3和车间
4的可用工时分别为 18和 28，因此
,M的取值只需不小于 Max（ 24-
18,32-28）即可
，这里取 99
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
变形 3：加入二选一约束的伟恩德例子的数学模型 P368-370（ 右边是另外一种解法 ）
决策变量：
决策变量,D,W为门和窗的生产数量辅助 0-1变量,y在工厂 3或工厂 4生产
（ 0－选择工厂 3,1－选择工厂 4）
？
目标,净利润最大化 Max P=300D+500W
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18＋ My
工厂 4,2D+4W? 28+M(1-y)
且非负,D,W? 0
y=0或 1
决策变量：
决策变量,D,W为门和窗的生产数量辅助 0-1变量,y1,y2是否在工厂 3或工厂 4生产？（ 1表示是）
目标,净利润最大化 Max P=300D+500W
约束条件：
工厂 1,D? 4
工厂 2,2W? 12
工厂 3,3D+2W? 18＋ M(1-y1)
工厂 4,2D+4W? 28+M(1-y2)
工厂 3,4互斥,y1+y2=1
且非负,D,W? 0
y1,y2=0或 1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.5 一些建模例子 P370
例子 1：增加管理限制
例子 2：不符合比例性要求
例子 3：航班的人员排程问题
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 1：增加管理限制 P371
固特产品公司的研发部最近开发出了三种新产品，但是，为了防止生产线的过度多元化，公司的管理层增加了如下的约束：
约束 1：在三种新产品中，最多只能选择 2种进行生产（引入辅助 0-1变量 y1,y2,y3，注意与三种新产品产量 x1,x2,x3的关系）
y1+y2+y3? 2
x1? My1,x2? My2,x3? My3 (M取 99)
约束 2：两个工厂中必须选出一个专门生产新产品（引入辅助 0-1变量 y4,0--选工厂 1,1--选工厂 2，注意与 2家工厂资源约束关系）
3x1+4x2+2x3? 30+My4 （工厂 1）
4x1+6x2+2x3? 40+M(1-y4) （工厂 2）
还有三种产品每周的生产量受到销售量的限制（?）
是一个混合 BIP模型
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 1：增加管理限制（续）
增加管理限制 的电子表格模型
G o o d P r o d u c t s C o,w i t h M a n a g e r i a l R e s t r i c t i o n s
P 3 7 3 例子 1,增加管理限制单位：千美元产品 1 产品 2 产品 3
单位利润 5 7 3
使用时数修正的每周可得时数每周可得时数工厂 1 3 4 2 3 4,5 <= 129 30
工厂 2 4 6 2 40 <= 40 40
产品 1 产品 2 产品 3
每周生产数量 5,5 0 9
<= <= <= 相对极大值 M 99
M y i 99 0 99
最大销售量 7 5 9 生产 最多生产产品种数 产品种数是否生产 yi 1 0 1 2 <= 2
用哪家工厂? ( 0 = 工厂 1,1 = 工厂 2) 1 总利润 5 4,5
每个产品所需生产时数
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 1：增加管理限制
（数学模型 P372－ 374）
决策变量：
决策变量,x1,x2,x3为三种新产品的每周生产数量辅助 0-1变量,y1,y2,y3三种新产品是否生产？
辅助 0-1变量,y4在工厂 1或工厂 2生产（ 0－选工厂 1,1－选工厂 2）？
目标,总利润最大化 Max P=5x1+7x2+3x3
约束条件：
最多选 2种产品,y1+y2+y3? 2
y1,y2,y3与 x1,x2,x3的关系,x1? My1,x2? My2,x3? My3 (其中 M取 99)
工厂 1,3x1+4x2+2x3? 30+My4
工厂 2,4x1+6x2+2x3? 40+M(1-y4)
最大销售量限制,x1? 7,x2? 5,x3? 9
（说明：可以合并,y1,y2,y3与 x1,x2,x3的关系”和“最大销售量限制”：
x1? 7y1,x2? 5y2,x3? 9y3）
且 非负,x1,x2,x3? 0
y1,y2,y3,y4=0,1
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
补充思考题（有启动成本）
有 1,2,3,4四种零件均可在设备 A或设备 B
上加工，已知在这两种设备上分别加工一个零件的费用如表所示。
又知设备 A或 B只要有零件加工均需要设备的启动费用，分别为 100元和 150元。
现要求加工 1,2,3,4零件各 3件。问应如何安排生产使总的费用最小。
试建立线性规划模型并求解零件 1 零件 2 零件 3 零件 4
设备 A 50 80 90 40
设备 B 30 100 50 70
结果：在设备 A上加工零件 2和 4各 3件
，在设备 B上加工零件 1和 3各 3件，总费用为 850元。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 2：不符合比例性要求 P374
超级苏滋公司（ Supersuds Corp.）正在为其下一年的新产品制定营销计划，并准备在全国电视网上购买 5个广告片，以促销三种产品。每个广告只针对一种产品，因此，这一问题就是如何将 5个广告分配给三种产品，
每种产品最多可以有三个广告，最少可以不作广告。
数据 P375，注意,电视广告片数与产品利润不是线性关系
S u p e r s u d s C o r p,M a r k e t i n g P l a n
P 3 7 8 例子 2,不符合比例性要求单位：百万美元利润 产品 1 产品 2 产品 3
电视 1 1 0 -1
广告 2 3 2 2
片数 3 3 3 4
决策变量 X i j,是否将电视广告片数 i 给产品 j
产品 1 产品 2 产品 3
电视 1 0 0 0
广告 2 1 0 0 总利润片数 3 0 0 1 7
T o t a l 1 0 1
<= <= <=
M a x O f O n e 1 1 1
实际总片数 所需总片数广告片数 2 0 3 5 = 5
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 2：不符合比例性要求
（数学模型 P375－ 377）
决策变量：
决策变量,x1,x2,x3分配给产品 1,2,3的广告数量辅助 0-1变量,yij是否给产品 i分配电视广告片数 j
目标,总利润最大化 Max P=y11+3y12+3y13 + 0 y21+2y22+3y23 - y31+2y32+4y33
约束条件：
每种产品广告数量和是否分配关系：
产品 1,x1＝ y11+2y12+3y13
产品 2,x2＝ y21+2y22+3y23
产品 3,x3＝ y31+2y32+3y33
每种产品最多分配一次：
产品 1,y11 + y12 + y13? 1
产品 2,y21 + y22 + y23? 1
产品 3,y31 + y32 + y33? 1
广告片数,x1 + x2 + x3 = 5
每种产品最多广告数量,x1,x2,x3? 3
且 非负 x1,x2,x3? 0,yij=0,1（ i=1,2,3; j=1,2,3）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 2：不符合比例性要求
（数学模型,补充另外一种写法 ）
决策变量：
0-1决策变量 xij：是否将电视广告片数 i 分配给产品 j
目标,总利润最大化 Max P=x11+3x21+3x31 +0x12+2x22+3x32 - x13+2x23+4x33
约束条件：
每种产品最多分配一次：
产品 1,x11 + x21 + x31? 1
产品 2,x12 + x22 + x32? 1
产品 3,x13 + x23 + x33? 1
广告片数,(x11+2x21+3x31 )+(x12+2x22+3x32 )+(x13+2x23+3x33 ) = 5
且 xij=0,1（ i=1,2,3; j=1,2,3）
注意：我这里直接用“类似指派问题”的想法，书上对此进行了解释。
可以用此方法求解
P261使总时间最短（奎克公司）
，即第 7章 PPT中的“思考题 2”
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
补充思考题 （不符合比例性要求）
某建设公司有 4个正在建设的项目，按目前所配给的人力
、设备和材料，这 4个项目分别可以在 15,20,18和 25周内完成，管理部门希望提前完成，并决定追加 35,000元资金分配给这 4个项目。这样，新的完工时间以分配给各个项目的追加资金的函数形式给出，如表所示。试问这
35,000元如何分配给这 4个项目，以使得总完工时间提前为最多（假定追加的资金只能以 5,000元一组进行分配）
试建立线性规划模型并求解结果：项目 1为 5千元，项目 2,3,4均为 10千元，总完工时间为 55周（提前了 23周）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 3：航班的人员排程问题 P377
西南航空公司 需要将 3组机组人员分配给 11个航班，数据如 P377的表 9.8。
用 0-1变量建模,xi－是否将 i次序的航班分配给某一机组人员 (i=1,…… 12)
约束：保证每个航班有机组人员，且只有 3组机组人员。
目标：总成本最小
纯 BIP模型（ 本题可以用 P386习题 9.20的意思来理解）
S o u t h w e s t A i r w a y s C r e w S c h e d u l i n g P r o b l e m
P 3 8 0 航班的人员排程问题 单位：千美元航班次序
1 2 3 4 5 6 7 8 9 10 11 12
成本 2 3 4 6 7 5 7 8 9 9 8 9
是否含有此航班 I n c l u d e s S e g m e n t? 总数 至少有一个旧金山S F O - 洛杉矶L A X 1 0 0 1 0 0 1 0 0 1 0 0 1 >= 1
旧金山S F O - 丹佛D E N 0 1 0 0 1 0 0 1 0 0 1 0 1 >= 1
旧金山S F O - 西雅图S E A 0 0 1 0 0 1 0 0 1 0 0 1 1 >= 1
洛杉矶L A X - 芝加哥O R D 0 0 0 1 0 0 1 0 1 1 0 1 1 >= 1
洛杉矶 L A X - 旧金山 S F O 1 0 0 0 0 1 0 0 0 1 1 0 1 >= 1
芝加哥 O R D - 丹佛 D E N 0 0 0 1 1 0 0 0 1 0 0 0 1 >= 1
芝加哥 O R D - 西雅图 SEA 0 0 0 0 0 0 1 1 0 1 1 1 1 >= 1
丹佛 D E N - 旧金山 S F O 0 1 0 1 1 0 0 0 1 0 0 0 1 >= 1
丹佛D E N - 芝加哥O R D 0 0 0 0 1 0 0 1 0 0 1 0 1 >= 1
西雅图 SEA- 旧金山 S F O 0 0 1 0 0 0 1 1 0 0 0 1 1 >= 1
西雅图 SEA- 洛杉矶 L A X 0 0 0 0 0 1 0 0 1 1 1 1 1 >= 1
1 2 3 4 5 6 7 8 9 10 11 12 总次序 机组数此次序是否飞? 0 0 1 1 0 0 0 0 0 0 1 0 3 <= 3
总成本 18
从 12个航班次序中选择 3个，
使得 11个航班都有机组人员
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
例子 3：航班的人员排程问题
（数学模型 P379）
决策变量：
0-1决策变量,xi是否将 i次序的航班分配给某一机组人员 (i=1,2,…,12)
目标,总成本最小化 Min C=2x1+3x2+4x3 +6x4+7x5+5x6 +7x7+8x8+9x9+9x10+8x11+9x12
约束条件（保证每个航班有机组人员，且只有 3组机组人员,0-1变量）：
SFO-LAX航班,x1 +x4+x7+x10? 1
SFO-DEN航班,x2 +x5+x8+x11? 1
……
SEA-LAX航班,x6 +x9+x10+x11 +x12? 1
只有 3组机组人员,x1+x2+x3 +x4+x5+x6 +x7+x8+x9+x10+x11+x12 = 3
且
xi = 0,1（ i=1,2,…,12 ）
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
9.6 Summary 小结 P381
线性规划可分性假设允许决策变量取包括分数在内的任何实数,当一些决策变量只能取整数时,就必须采用整数规划 。
每个 0-1整数规划 （ BIP） 模型都可以同时考虑多个选项,一个 0-1决策变量对应于一个选项,而混合的 BIP
模型还可以包含一些连续的决策变量 。
在处理一些无法直接建立 BIP模型的问题时,运用辅助
0-1变量是很有用的,辅助变量可以将问题标准化,从而可以用标准的算法求解 。 辅助变量可用来处理很多问题 。
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题具体请见 Excel文件企业内部网 IN 安装时间期限第 1 个月 第 2 个月 第 3 个月 第 4 个月 第 5 个月
IN 培训在销售部门安装 IN
在生产部门安装 IN
在仓库安装 IN
在营销部门安装 IN
各部门使用 IN 的员工数 各种型号服务器的成本以及可支持的员工数部门 员工数 服务器类型 支持的员工数 服务器成本销售 60 标准 PC 30 $ 2,5 0 0
生产 200 加强型P C 80 $ 5,0 0 0
仓库 30 S G I 工作站 200 $ 1 0,0 0 0
营销 75 S u n 工作站 2000 $ 2 5,0 0 0
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题
a,以每月采购的方式评估服务器的数量和类型。对于每一个月，建立一个整数规划模型（在上个月的结果情况下，使本月的成本最小），然后将各月的费用相加，得到总费用（ 贪婪算法 ）。
1,第一个月，由于没有安装要求，从成本最小化考虑，本月不买任何类型的服务器
2,第二个月，销售部门有安装要求（?60)，决策变量 xi:本月购进第 i种型号服务器的台数（整数,INT），由于第一个月没有购买，资金没有用，则 2月份可以使用的资金是 $9500，注意：有折扣（ SGI－ 10％
,SUN－ 25％ )，结果,2月购买一台加强型 PC服务器，可支持的员工数为 80(其实也可以购买 2台标准 PC服务器,但可支持的员工数为
2*30=60)，本月费用为 $5000
3,第三个月，生产部门有安装要求（?200)，而第二个月多了 80-60=20
台，所以只需 200-20=180台即可，决策变量 xi:本月购进第 i种型号服务器的台数（整数,INT），此时没有资金限制，也没有折扣，结果
,3月购买一台 SGI工作站，加上 2月份购买的 1台加强型 PC服务器，
可支持的员工数为 80+200=280，本月费用为 $10000。也满足生产部门至少需要三种性能比较好的服务器中的一种。
4,第四、五月，同第三个月。
结果：最后总的费用 =5000+10000+2500+5000=22,500
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题 (续 )
b、综合考虑，整个问题建立一个整数规划模型
1,决策变量 xij：第 i个月应该购进第 j种型号服务器的台数（整数,INT
），用的是满足累计员工数,所以约束的左右两边，从第 2个月开始就为累计到本月,1-2月的资金限制也是采用累计数，所以 2月份实际所花的累计成本 =1月＋ 2月。
2,注意：前面 1,2月受到资金限制（ $9500），且有折扣（ SGI－ 10％
,SUN－ 25％ )。
3,还需注意：生产部门至少需要三种性能比较好的服务器中的一种（
即在 1－ 3月购买）
结果：在 1,3月份各购买一台 SGI工作站（共 2台），成本为 19,000。
c,第一种方法是贪婪算法，没有全盘考虑 。
讨论题：
由于 1,2月有折扣，所以如果能在 1,2月份购买会合算些，此时就不能受到资金的限制（ $9500）：在 b中去掉 1,2月累计资金的限制
（直接在规划求解中实现）即可，结果：在 1或 2月份购买 2台 SGI工作站，成本为 18,000。支持员工数＝ 2× 200＝ 400人
还有：是否可以在 1,2月买一台 SUN，成本＝ 25,000× （ 1－ 25％）
＝ 18,750，但支持员工数＝ 2000人
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
P387 案例 9.1 能力问题（续）
b还有一种更为简单的方法：因为前面 1,2月有资金限制（ $9500），
且有折扣（ SGI－ 10％,SUN－ 25％ )，而后面 3个月没有，所以决策变量 x1j（ j=1,2,3,4）,1,2月应该购进第 j种型号服务器的台数 (整数 )
决策变量 x2j（ j=1,2,3,4）,3－ 5月应该购进第 j种型号服务器的台数 (整数 )
P 3 8 7 案例 9,1 能力问题
b,还有一种更为简单的方法：因为前面1,2 月有资金限制（9,5 0 0 $ ），且有折扣（S G I －1 0 ％，S U N －2 5 ％),而后面3 个月没有，所以决策变量X 1 j （j = 1,2,3,4 ）：1,2 月应该购进第j 种型号服务器的台数( 整数)
决策变量X 2 j （j = 1,2,3,4 ）：3 －5 月应该购进第j 种型号服务器的台数( 整数)
标准 PC 加强型P C S G I 工作站 S u n 工作站 使用资金支持的员工数 30 80 200 2000
服务器成本 ( 3 - 5 月 ) $ 2,5 0 0 $ 5,0 0 0 $ 1 0,0 0 0 $ 2 5,0 0 0 $ 1 0,0 0 0
1 - 2 月折扣 0% 0% 10% 25% 前 2 个月累计资金限制
1,2 月成本 $ 2,5 0 0 $ 5,0 0 0 $ 9,0 0 0 $ 1 8,7 5 0 $ 9,0 0 0 <= $ 9,5 0 0
服务器购买数 标准 PC 加强型P C S G I 工作站 S u n 工作站 累计实际支持 累计需要支持
1 - 2 月 0 0 1 0 200 >= 60
3 - 5 月 0 0 1 0 400 >= 365
购买各种服务器的台数 S U M
0 0 2 0 2 >= 1
生产部门要求总成本 $ 1 9,0 0 0
Chapter 9
Integer Programming
整数规划
RUC Information School,Ye Xiang,2007
Exercise
作业（上机）
P382 习题：
9.5 9.11 9.13（注意 M的取值）
9.15 9.16（请参考 P370例子 2）
9.20 （类似 P377航班的人员排程问题 ）
