Ling Xueling
虽然用途广泛,但经常地,客观上要求
L.P.最优解中不能含有非整数值 （ 如股票的购买之解答 ）,整数规划就是专门用来求解这类问题的有效工具重点掌握,0-1 规划灵活应用,分枝定界法 。
第七章 整数规划（ I.P.）
凌晨,凌晨,
Ling Xueling
一,I.P,概念
1,什么是 I.P.
要求部分或全部决策变量是整数的 L.P,问题
2,I.P,的用处
1） 现实需要,不得已
2） 使用 整 变量常常使得建模更 灵活,应用面扩大
3,I.P,的不利求解通常不易所谓 分枝定界法 是最有效的求解方法几乎所有的计算机程序都用此法 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
二,I.P,模型分类
1,全整数规划
L.P,中若要求所有决策变量皆? 0,且为整数 。 如股票决策
2,混合 I.P.
如：奖金人数及其奖金数额之决策
3,0－ 1 规划决策变量只取 0 或 1
4,I.P,的 L.P,松弛简单放弃 I.P,中对决策变量是整数的要求而得到的 L.P.模型 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用－－只介绍 0－ 1规划
1,资金预算问题 （ capital budgeting）
运筹学在财务管理中的应用不少都集中在资金预算问题假定 I.C,公司要对今后四年的一些投资 项目进行 资金管理目标：选择能得到最大利润的项目并对资金作出预算有关数据如下：
资金需求项目 预期收入 第一年 第二年 第三年 第四年
x1 厂房扩建 90,000 15,000 20,000 20,000 15,000
x2 仓库扩建 40,000 10,000 15,000 20,000 5,000
x3 购新机器 10,000 10,000 0 0 4,000
x4 新品开发 37,000 15,000 10,000 10,000 10,000
各年可用资金额 40,000 50,000 40,000 35,000
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
1） 建模 （ 引进 0－ 1 变量,但仍然是 L.P,模型 ）
设 决策变量,（ 单位,1000 ）
max 90x1 + 40x2 + 10x3 + 37x4
s.t.
15x1 + 10x2 + 10x3 + 15x4 ≤ 40
...................................,（ 每年可用资金限制 ）
15x1 + 5x2 + 4x3 + 10x4 ≤ 35
x i ≥ 0
第一节 I.P,概念和应用凌晨,凌晨,
否则项目投资对
0
1 ix
i
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
2） 模型的解及其 问题以上模型实际上是一个 L.P,模型,其 解为：
x1 = 1,x2 = 0.5,x3 = 0.5,x4 = 1,o.f,= 152,000
显然是 不 可行解－－第二,三项目如何只完成 50％？
采用简单化整,x1 = 1,x2 = x3 = 0,x4 = 1,o.f,= 127,000
问题：仍然是最优解吗？
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
3） 采用 I.P,重新建模 （ 0－ 1 模型 ）
max 90x1 + 40x2 + 10x3 + 37x4
s.t.
15x1 + 10x2 + 10x3 + 15x4 ≤ 40
...................................,(每年可用资金限制 )
15x1 + 5x2 + 4x3 + 10x4 ≤ 35
x i ＝ 0,1
最优解,x1 = x2 = x3 = 1,x4 = 0,o.f,= 140,000－－ 可行 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
4） 0－ 1模型用于资金预算的优势
（ 1） 避免小数
（ 2） 灵活性,讨论如下：
（ i） 多重选择假设实际上有三个仓库 可以考虑 扩建,要求：三个中有且仅能有一个得到扩建,则 令,x2 = 1－－第一个考虑仓库,
x5 = 1 －－ 第二个考虑扩建,x6 = 1 －－第三个仓库考虑扩建,则只需添加下列约束即可：
x2 + x5 + x6 = 1 －－－ L.P,模型没 有这么方便 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
4） 0－ 1模型用于资金预算的优势
（ ii） 互斥选择若要求：至多一个扩建,可添加 x2 + x5 + x6 ≤ 1
（ iii） 在若干 个项目中选择 k 个的约束以 x2,x5,x6,x7,x8 表示五个潜在的仓库扩建项目＝ 1 或 0
a) 五中选二,x2 + x5 + x6 + x7 + x8 = 2
b) 五中不超过二,x2 + x5 + x6 + x7 + x8 ≤ 2 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
（ iv） 有条件约束 －某项目的采纳有赖于另一项目的采纳要求：除非扩建厂房，否则不考虑扩建仓库：
x2 ≤ x1 or x2 － x1 ≤ 0
（ v） 共需约束要求：只要扩建厂房,就应扩建仓库,x2 = x1 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2,配送系统设计问题 （ distribution system design）
1） 运输问题的 L.P,模型 ( 一般模型 ) （ 设 ∑ s = ∑ d）
min ∑ ∑ c i j x i j －－成本最低
s.t.
∑ x i j ≤ s i ( i = 1,2,....m) －－供给
∑ x i j = d j ( j = 1,2,..,n ) －－需求
x i j ≥ 0 ( i = 1....m,j = 1,..,n )
此处,
i = 起运点指标,j = 目的地指标
x i j = 从起点 i 至终点 j 的运量单位
c i j = 从起点 i 至终点 j 的单位运输成本
s i = 起点 i 处的可供单位
d j = 终点 j 处的需求单位 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2,配送系统设计问题 （ distribution system design）
2） 配送系统设,供 ∑ s > ∑ d 求 配送,需 先定 s i,再 定 x i j
（ 1） 问题的提出运输问题－－起,终点不变,只要决定运量,使总成本最小即可配送问题－－ 先要定起运点 （ 配送中心 ）,即对起运点先进行选择,然后再定各起运点到各终点的运量,使 总成本最小如：大型连锁店的配货中心之选址和建立,配送方案的决定 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2） 配送系统
（ 2） 配送系统的概述设在某区域内已有 n 个零售点,调研或现有资料表明,
它们的需求量分别是,d j ( j = 1,.,n )
又设：此区域内有 m 个可供建立配货中心的潜在位置,
库存能力分别是 s i ( i = 1....m )
则所 谓的配送系统问题就是：在上述区域内选定并设立若干个配送中心,使得建设配送中心的 （ 固定 ） 成本与这些中心的发货成本 （ 可变 ） 之 和 最小,即：在使建设成本最小的同时也使运输成本最小这需要同时考虑：
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2） 配送系统
（ 2） 配送系统的概述
(a) 二个成本
(i) 固定成本－－设立配货中心的固定成本
(ii) 可变成本－－被选中心至各个零售点不同运输成本
(b) 二类决策变量
(i) m 个位置决定是否建中心
(ii) 各中心至各零售点的运输量
(c) 目标,（ 二类 ） 总成本最小 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2,配送系统设计问题 （ distribution system design）
3） 建模 （ 采用 0－ 1 模型 ）
（ 1） 决策变量：令 y i = 1,若 i 处建中心,否则为 0
f i = i 处建立库存能力为 s i 的配送中心的固定成本
x i j ＝ 如同以前表示运量
（ 2） 模型
min ∑ ∑ c i j x i j + ∑ f i y i －－二类成本之和 min
s.t.
∑ x i j ≤ s i y i ( i = 1....,m )
∑ x i j = d j ( j = 1.....n )
x i j ≥ 0 ( i = 1.....m,j = 1......n )
y i = 0 or 1 ( i = 1....m )
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
2,配送系统设计问题
4） 系统的调节 ( 只举一例 )
若公司规定：因为 1 和 2 处相距太近,不可同时建中心,则只需增加约束：
y1 + y2 ≤ 1
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
四,I.P,模型的敏感性分析最优解对系数很敏感,稍有变化,解的变化往往就很大,尚无完整的理论,只能靠多试几套不同的参数进行观察 。 如：
资金预算问题中四个项目若只考虑一个单期,则模型是
max 40x1 + 60x2 + 70x3 + 160x4
s.t.
16x1 + 35x2 + 45x3 + 85x4 ≤ 100 ------ 可用资金
x1,x2,x3,x4 = 0 or 1
最优解,x1 = x2 = x3 = 1,x4 = 0,o.f,= 170
但若可用资金调整为,100→ 101,则最优解变成,x1 = x4 = 1,
x2 = x3 = 0,o.f,= 200,即：可用资金 100 元每增加 1 元,利润竟然可增加 30 元 ！ 皆因可行域是孤立点所致 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
一,图解法及其启示
1,问题和模型某不动产投资公司拟投资 1,365,000 元用于购买 x1 幢别墅和
x2 幢公寓,考虑到售价,物业管理能力,租赁利润等因素,
得到以下模型,（ 单位,1000）
max 2x1 + 3x2 －－利润
s.t.
195x1 + 273x2 ≤ 1365 －－资金
4x1 + 40x2 ≤ 140 －－物业能力
x1 ≤ 4 －－可购量
x1,x2 ≥ 0,整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
一,图解法及其启示
2,化成 L.P,松驰进行求解一个 自然的 想法：先放弃,整数,的要求求解,然后再,取整,
L.P,松驰之解是：
x1 = 2.44 x2 = 3.26 o.f,= 14.66
显然,是不可行解化整之 （ 变成可行解 ）,
x1 = 2 x2 = 3 o.f,= 13
问题：保证最优？ （ 注意：此时 o.f.减少 10％ 以上 ） 为了回答此问题,试用图解法说明－－ 课堂练习 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
一,图解法及其启示
3,图解法
L.P,最优 （ 2.44,3.26）
I.P,最优最优解,x1 = 4,x2 = 2,o.f,= 14
第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
2
4
4
4 x 1 + 4 0 x 2 1 4 0
1 9 5 x 1 + 2 7 3 x 2 1 3 6 5
x 1 4
Ling Xueling
一,图解法及其启示
4,图解法的启示
1） 三种解的关系下界 上界
L.P.松驰再取整 I.P,x1=4,x2=2 L.P,松驰 x1=2.44,x2=3.26
o.f,= 13 ≤ o.f,= 14 ≤ o.f,= 14.66
( 可行 ) ( 可行且最优 ) ( 不可行 )
一般地,有,
2） 定理一任意 max 全整或混合整 I.P,之最优解 值 ≤ 对应的 L.P,松驰最优解 值,对 min 问题,只需将,≤,改成,≥,即可 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
一,图解法及其启示
4,图解法的启示
3） 定理一的意义既然不等式中间是最优 整数 解,而左边是可行 整数 解,
定理一又肯定上述不等式总是成立的,这启发：为了求得最优整数解,可以从求对应 L.P,松驰及其取整运算而分别获得 I.P,问题 的 上界值 和 下界值,即可完成分枝定界法中的 定界,然后不断设法减少上界并增加下界,直到最终求出 I.P,问题本身的最优整数解 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法
1,从哪个节点处 分 枝？
如果只有一个节点,则从此唯一的节点处分枝若不只一个节点,则可应用下列定理二 max （ min） 问题中,每一个结点处的 L.P,松驰值都是随后所有结点 L.P,松驰的一个上 （ 下 ） 界即,应该选择具有较大 o.f,值的节点处进行分枝
2,对哪个变量 分 枝？
选择距分枝整数 较远 的整数变量 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法
3,定界任何时候,只要求出 L.P,松驰解,就能给出一个上界,UB
分枝过程中,两个新结点处 L.P,松驰之解值中选 大 的一个为,树,的 UB,则,越往下分,UB 会 越小松驰解化整后因为可得到一个整数解,下界也就求得了,LB
在不断的分枝过程中,,树,的下界总是取：到目前的分枝为止,所有求得的整数解值中的最 大 值,则,越分,LB 越大
4,分枝停止准则当 UB = LB 时,说明最优解即已求得,即是取值等于 LB 的整数可行解 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法问题：
max 2x1 + 3x2
s.t.
195x1 + 273x2 ≤ 1365
4x1 + 40x2 ≤ 140
x1 ≤ 4
x1,x2 ≥ 0,整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法问题的求解：
第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
L P = 1 4,6 6
x 1 = 2,4 4
x 2 = 3,2 6
2
l p = 1 3,9
x 1 = 2
x 2 = 3,3
3
l p = 1 4,5 8
x 1 = 3
x 2 = 2,8 6
4
l p = 1 4
x 1 = 4
x 2 = 2
5
不可行
x 2 <2
x 2 >3
x 1 <2
x 1 >3
u b = 1 4,0 0
l b = 1 4,0 0
比较故
u b = 1 4
Ling Xueling
三,课堂练习
1,问题 （ 1）
max 5x1 + 8x2
s.t.
6x1 + 5x2 ≤ 30
9x1 + 4x2 ≤ 36
x1 + 2x2 ≤ 10
x1,x2 ≥ 0,整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
三,课堂练习
2,问题 （ 1） 求解第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
l p = 4 1,4 3
x 1 = 1,4 3
x 2 = 4,2 9
2
l p = 4 1
x 1 = 1
x 2 = 4,,5
3
l p = 3 8,8
x 1 = 2
x 2 = 3,6
4
l p = 3 7
x 1 = 1
x 2 = 4
5
l p = 4 0
x 1 = 0
x 2 = 5
x 1 <1
x 1 >2
x 2 <4
x 2 >5
u b = 4 1,4 3
l b = 3 7
41 40
4 0
最优解：
x 1 = 0
x 2 = 5
o,f,= 4 0
Ling Xueling
三,课堂练习
3,问题 （ 2） －－混合整问题
max 2x1 + 3x2
195x1 + 273x2 ≤ 1365
4x1 + 40x2 ≤ 140
x1 ≤ 4
x1,x2 ≥ 0,x1 整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
三,课堂练习
4,问题 （ 2） 求解第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
l p = 1 4,6 6
x 1 = 2,4 4
x 2 = 3,2 6
2
l p = 1 3,9
x 1 = 2
x 2 = 3,3
3
l p = 1 4,5 8
x 1 = 3
x 2 = 2,8 6
x 1 <2 x 1 >3
比较故 u b = 1 4,5 8
u b = 1 4,6 6 1 4,5 8
l b = 1 3,7 8 1 4,5 8
( x 1 = 2 x 2 = 3,2 6 )
Ling Xueling
一,派出机构的设定如,消防站,卫生站等派出机构问题
1,问题
Ohio 银行拟在某地区 20 个县中开展信贷业务 ( 原先无任何机构 )
州银行法规定：任何一银团在任一县中除非有分行,则可在此县中及相邻县中开展信贷业务银行管理层决定,既要少设分行,又要尽量多 ( 20 个县 ) 开展信贷业务,问题是：如何选定分行所在县？
位于 Ohio 某地区 20 个县的地理分布大致如后,( 县名略 )。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
一,派出机构的设定
1,问题第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
1
13
16
15
14
5
4
3
2
12
6
7
17
9
8
18
10
11
19
20
Ling Xueling
一,派出机构的设定
2,建模
1） 将每一个县及其邻县用数字标出,如：
考虑中县,1 2 3,..................
相邻县,2,12,16 1,3,12 2,4,9,10,12,13,...................
2） 定义决策变量 ( 0－ 1 变量 )
x i = 1 若在第 i 县设分行,否则为 0
3） o.f,（ 最小成本 ）
min ∑ x i
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
一,派出机构的设定
2,建模
4） 约束为了在一个县开展信贷业务,该县要么设分行,要么与有分行的县紧邻,则对第一个县来说
x1 + x2 + x12 x + x16 ≥ 1
对第二个县：
x1 + x2 + x3 + x12 ≥ 1
......................
3,求解
x7 = x11 = x12 = 1 其余 x i = 0。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型为了利用 0－ 1模型的灵活性,可以考虑利用 二进制展开 巧妙地将一些 I.P,模型 转化成 0－ 1 规划模型
1,例子
1） 模型
max 2x1 + 3x2
s.t.
x1 + 2x2 ≤ 10.5
x1 ≤ 6 －－ x1 上界为 6
x1,x2 ≥ 0,x1 整数 。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型利用二进制展开可以巧妙地将一些 I.P,模型 转化成 0
－ 1 规划模型
1,例子
2） 模型的 特点,x1 上界 6
3） 处理,因为 x1 = 0,1,2,3,4,5,6
所以可 令,x1 = 1y1 + 2y2 + 4y3
其中 y i = 0 或 1
4） 新模型见下页 。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型利用二进制展开可以巧妙地将一些 I.P,模型 转化成 0
－ 1 规划模型
1,例子
4） 新模型
max 2( 1y1 + 2y2 + 4y3 ) + 3x2
s.t.
( 1y1 + 2y2 + 4y3 ) + 2x2 ≤ 10.5
( 1y1 + 2y2 + 4y3 ) ≤ 6
y1,2y2,y3,x2 ≥ 0,y1,y2,y3 = 0,1。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型利用二进制展开可以巧妙地将一些 I.P,模型 转化成 0
－ 1 规划模型
1,例子
5） 最优解
y1 = 0,y2 = 1,y3 = 1,x2 = 2.25
即,x1 = 6,x2 = 2.25 o.f,= 18.75
2,一般的二进制展开令：
若 x k 上界是 u,则 p 是 满足 ≥ u 的最小整数 。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
i
p
i
i
k yx?
1
12
Ling Xueling
The End of Chapter 7
虽然用途广泛,但经常地,客观上要求
L.P.最优解中不能含有非整数值 （ 如股票的购买之解答 ）,整数规划就是专门用来求解这类问题的有效工具重点掌握,0-1 规划灵活应用,分枝定界法 。
第七章 整数规划（ I.P.）
凌晨,凌晨,
Ling Xueling
一,I.P,概念
1,什么是 I.P.
要求部分或全部决策变量是整数的 L.P,问题
2,I.P,的用处
1） 现实需要,不得已
2） 使用 整 变量常常使得建模更 灵活,应用面扩大
3,I.P,的不利求解通常不易所谓 分枝定界法 是最有效的求解方法几乎所有的计算机程序都用此法 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
二,I.P,模型分类
1,全整数规划
L.P,中若要求所有决策变量皆? 0,且为整数 。 如股票决策
2,混合 I.P.
如：奖金人数及其奖金数额之决策
3,0－ 1 规划决策变量只取 0 或 1
4,I.P,的 L.P,松弛简单放弃 I.P,中对决策变量是整数的要求而得到的 L.P.模型 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用－－只介绍 0－ 1规划
1,资金预算问题 （ capital budgeting）
运筹学在财务管理中的应用不少都集中在资金预算问题假定 I.C,公司要对今后四年的一些投资 项目进行 资金管理目标：选择能得到最大利润的项目并对资金作出预算有关数据如下：
资金需求项目 预期收入 第一年 第二年 第三年 第四年
x1 厂房扩建 90,000 15,000 20,000 20,000 15,000
x2 仓库扩建 40,000 10,000 15,000 20,000 5,000
x3 购新机器 10,000 10,000 0 0 4,000
x4 新品开发 37,000 15,000 10,000 10,000 10,000
各年可用资金额 40,000 50,000 40,000 35,000
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
1） 建模 （ 引进 0－ 1 变量,但仍然是 L.P,模型 ）
设 决策变量,（ 单位,1000 ）
max 90x1 + 40x2 + 10x3 + 37x4
s.t.
15x1 + 10x2 + 10x3 + 15x4 ≤ 40
...................................,（ 每年可用资金限制 ）
15x1 + 5x2 + 4x3 + 10x4 ≤ 35
x i ≥ 0
第一节 I.P,概念和应用凌晨,凌晨,
否则项目投资对
0
1 ix
i
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
2） 模型的解及其 问题以上模型实际上是一个 L.P,模型,其 解为：
x1 = 1,x2 = 0.5,x3 = 0.5,x4 = 1,o.f,= 152,000
显然是 不 可行解－－第二,三项目如何只完成 50％？
采用简单化整,x1 = 1,x2 = x3 = 0,x4 = 1,o.f,= 127,000
问题：仍然是最优解吗？
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
3） 采用 I.P,重新建模 （ 0－ 1 模型 ）
max 90x1 + 40x2 + 10x3 + 37x4
s.t.
15x1 + 10x2 + 10x3 + 15x4 ≤ 40
...................................,(每年可用资金限制 )
15x1 + 5x2 + 4x3 + 10x4 ≤ 35
x i ＝ 0,1
最优解,x1 = x2 = x3 = 1,x4 = 0,o.f,= 140,000－－ 可行 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
4） 0－ 1模型用于资金预算的优势
（ 1） 避免小数
（ 2） 灵活性,讨论如下：
（ i） 多重选择假设实际上有三个仓库 可以考虑 扩建,要求：三个中有且仅能有一个得到扩建,则 令,x2 = 1－－第一个考虑仓库,
x5 = 1 －－ 第二个考虑扩建,x6 = 1 －－第三个仓库考虑扩建,则只需添加下列约束即可：
x2 + x5 + x6 = 1 －－－ L.P,模型没 有这么方便 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
4） 0－ 1模型用于资金预算的优势
（ ii） 互斥选择若要求：至多一个扩建,可添加 x2 + x5 + x6 ≤ 1
（ iii） 在若干 个项目中选择 k 个的约束以 x2,x5,x6,x7,x8 表示五个潜在的仓库扩建项目＝ 1 或 0
a) 五中选二,x2 + x5 + x6 + x7 + x8 = 2
b) 五中不超过二,x2 + x5 + x6 + x7 + x8 ≤ 2 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
1,资金预算问题 （ capital budgeting）
（ iv） 有条件约束 －某项目的采纳有赖于另一项目的采纳要求：除非扩建厂房，否则不考虑扩建仓库：
x2 ≤ x1 or x2 － x1 ≤ 0
（ v） 共需约束要求：只要扩建厂房,就应扩建仓库,x2 = x1 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2,配送系统设计问题 （ distribution system design）
1） 运输问题的 L.P,模型 ( 一般模型 ) （ 设 ∑ s = ∑ d）
min ∑ ∑ c i j x i j －－成本最低
s.t.
∑ x i j ≤ s i ( i = 1,2,....m) －－供给
∑ x i j = d j ( j = 1,2,..,n ) －－需求
x i j ≥ 0 ( i = 1....m,j = 1,..,n )
此处,
i = 起运点指标,j = 目的地指标
x i j = 从起点 i 至终点 j 的运量单位
c i j = 从起点 i 至终点 j 的单位运输成本
s i = 起点 i 处的可供单位
d j = 终点 j 处的需求单位 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2,配送系统设计问题 （ distribution system design）
2） 配送系统设,供 ∑ s > ∑ d 求 配送,需 先定 s i,再 定 x i j
（ 1） 问题的提出运输问题－－起,终点不变,只要决定运量,使总成本最小即可配送问题－－ 先要定起运点 （ 配送中心 ）,即对起运点先进行选择,然后再定各起运点到各终点的运量,使 总成本最小如：大型连锁店的配货中心之选址和建立,配送方案的决定 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2） 配送系统
（ 2） 配送系统的概述设在某区域内已有 n 个零售点,调研或现有资料表明,
它们的需求量分别是,d j ( j = 1,.,n )
又设：此区域内有 m 个可供建立配货中心的潜在位置,
库存能力分别是 s i ( i = 1....m )
则所 谓的配送系统问题就是：在上述区域内选定并设立若干个配送中心,使得建设配送中心的 （ 固定 ） 成本与这些中心的发货成本 （ 可变 ） 之 和 最小,即：在使建设成本最小的同时也使运输成本最小这需要同时考虑：
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2） 配送系统
（ 2） 配送系统的概述
(a) 二个成本
(i) 固定成本－－设立配货中心的固定成本
(ii) 可变成本－－被选中心至各个零售点不同运输成本
(b) 二类决策变量
(i) m 个位置决定是否建中心
(ii) 各中心至各零售点的运输量
(c) 目标,（ 二类 ） 总成本最小 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
2,配送系统设计问题 （ distribution system design）
3） 建模 （ 采用 0－ 1 模型 ）
（ 1） 决策变量：令 y i = 1,若 i 处建中心,否则为 0
f i = i 处建立库存能力为 s i 的配送中心的固定成本
x i j ＝ 如同以前表示运量
（ 2） 模型
min ∑ ∑ c i j x i j + ∑ f i y i －－二类成本之和 min
s.t.
∑ x i j ≤ s i y i ( i = 1....,m )
∑ x i j = d j ( j = 1.....n )
x i j ≥ 0 ( i = 1.....m,j = 1......n )
y i = 0 or 1 ( i = 1....m )
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
三,I.P,模型的应用
2,配送系统设计问题
4） 系统的调节 ( 只举一例 )
若公司规定：因为 1 和 2 处相距太近,不可同时建中心,则只需增加约束：
y1 + y2 ≤ 1
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
四,I.P,模型的敏感性分析最优解对系数很敏感,稍有变化,解的变化往往就很大,尚无完整的理论,只能靠多试几套不同的参数进行观察 。 如：
资金预算问题中四个项目若只考虑一个单期,则模型是
max 40x1 + 60x2 + 70x3 + 160x4
s.t.
16x1 + 35x2 + 45x3 + 85x4 ≤ 100 ------ 可用资金
x1,x2,x3,x4 = 0 or 1
最优解,x1 = x2 = x3 = 1,x4 = 0,o.f,= 170
但若可用资金调整为,100→ 101,则最优解变成,x1 = x4 = 1,
x2 = x3 = 0,o.f,= 200,即：可用资金 100 元每增加 1 元,利润竟然可增加 30 元 ！ 皆因可行域是孤立点所致 。
第一节 I.P,概念和应用凌晨,凌晨,
Ling Xueling
一,图解法及其启示
1,问题和模型某不动产投资公司拟投资 1,365,000 元用于购买 x1 幢别墅和
x2 幢公寓,考虑到售价,物业管理能力,租赁利润等因素,
得到以下模型,（ 单位,1000）
max 2x1 + 3x2 －－利润
s.t.
195x1 + 273x2 ≤ 1365 －－资金
4x1 + 40x2 ≤ 140 －－物业能力
x1 ≤ 4 －－可购量
x1,x2 ≥ 0,整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
一,图解法及其启示
2,化成 L.P,松驰进行求解一个 自然的 想法：先放弃,整数,的要求求解,然后再,取整,
L.P,松驰之解是：
x1 = 2.44 x2 = 3.26 o.f,= 14.66
显然,是不可行解化整之 （ 变成可行解 ）,
x1 = 2 x2 = 3 o.f,= 13
问题：保证最优？ （ 注意：此时 o.f.减少 10％ 以上 ） 为了回答此问题,试用图解法说明－－ 课堂练习 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
一,图解法及其启示
3,图解法
L.P,最优 （ 2.44,3.26）
I.P,最优最优解,x1 = 4,x2 = 2,o.f,= 14
第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
2
4
4
4 x 1 + 4 0 x 2 1 4 0
1 9 5 x 1 + 2 7 3 x 2 1 3 6 5
x 1 4
Ling Xueling
一,图解法及其启示
4,图解法的启示
1） 三种解的关系下界 上界
L.P.松驰再取整 I.P,x1=4,x2=2 L.P,松驰 x1=2.44,x2=3.26
o.f,= 13 ≤ o.f,= 14 ≤ o.f,= 14.66
( 可行 ) ( 可行且最优 ) ( 不可行 )
一般地,有,
2） 定理一任意 max 全整或混合整 I.P,之最优解 值 ≤ 对应的 L.P,松驰最优解 值,对 min 问题,只需将,≤,改成,≥,即可 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
一,图解法及其启示
4,图解法的启示
3） 定理一的意义既然不等式中间是最优 整数 解,而左边是可行 整数 解,
定理一又肯定上述不等式总是成立的,这启发：为了求得最优整数解,可以从求对应 L.P,松驰及其取整运算而分别获得 I.P,问题 的 上界值 和 下界值,即可完成分枝定界法中的 定界,然后不断设法减少上界并增加下界,直到最终求出 I.P,问题本身的最优整数解 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法
1,从哪个节点处 分 枝？
如果只有一个节点,则从此唯一的节点处分枝若不只一个节点,则可应用下列定理二 max （ min） 问题中,每一个结点处的 L.P,松驰值都是随后所有结点 L.P,松驰的一个上 （ 下 ） 界即,应该选择具有较大 o.f,值的节点处进行分枝
2,对哪个变量 分 枝？
选择距分枝整数 较远 的整数变量 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法
3,定界任何时候,只要求出 L.P,松驰解,就能给出一个上界,UB
分枝过程中,两个新结点处 L.P,松驰之解值中选 大 的一个为,树,的 UB,则,越往下分,UB 会 越小松驰解化整后因为可得到一个整数解,下界也就求得了,LB
在不断的分枝过程中,,树,的下界总是取：到目前的分枝为止,所有求得的整数解值中的最 大 值,则,越分,LB 越大
4,分枝停止准则当 UB = LB 时,说明最优解即已求得,即是取值等于 LB 的整数可行解 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法问题：
max 2x1 + 3x2
s.t.
195x1 + 273x2 ≤ 1365
4x1 + 40x2 ≤ 140
x1 ≤ 4
x1,x2 ≥ 0,整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
二,分枝定界法问题的求解：
第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
L P = 1 4,6 6
x 1 = 2,4 4
x 2 = 3,2 6
2
l p = 1 3,9
x 1 = 2
x 2 = 3,3
3
l p = 1 4,5 8
x 1 = 3
x 2 = 2,8 6
4
l p = 1 4
x 1 = 4
x 2 = 2
5
不可行
x 2 <2
x 2 >3
x 1 <2
x 1 >3
u b = 1 4,0 0
l b = 1 4,0 0
比较故
u b = 1 4
Ling Xueling
三,课堂练习
1,问题 （ 1）
max 5x1 + 8x2
s.t.
6x1 + 5x2 ≤ 30
9x1 + 4x2 ≤ 36
x1 + 2x2 ≤ 10
x1,x2 ≥ 0,整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
三,课堂练习
2,问题 （ 1） 求解第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
l p = 4 1,4 3
x 1 = 1,4 3
x 2 = 4,2 9
2
l p = 4 1
x 1 = 1
x 2 = 4,,5
3
l p = 3 8,8
x 1 = 2
x 2 = 3,6
4
l p = 3 7
x 1 = 1
x 2 = 4
5
l p = 4 0
x 1 = 0
x 2 = 5
x 1 <1
x 1 >2
x 2 <4
x 2 >5
u b = 4 1,4 3
l b = 3 7
41 40
4 0
最优解：
x 1 = 0
x 2 = 5
o,f,= 4 0
Ling Xueling
三,课堂练习
3,问题 （ 2） －－混合整问题
max 2x1 + 3x2
195x1 + 273x2 ≤ 1365
4x1 + 40x2 ≤ 140
x1 ≤ 4
x1,x2 ≥ 0,x1 整数 。
第二节 I.P,的分枝定界求解法凌晨,凌晨,
Ling Xueling
三,课堂练习
4,问题 （ 2） 求解第二节 I.P,的分枝定界求解法凌晨,凌晨,
1
l p = 1 4,6 6
x 1 = 2,4 4
x 2 = 3,2 6
2
l p = 1 3,9
x 1 = 2
x 2 = 3,3
3
l p = 1 4,5 8
x 1 = 3
x 2 = 2,8 6
x 1 <2 x 1 >3
比较故 u b = 1 4,5 8
u b = 1 4,6 6 1 4,5 8
l b = 1 3,7 8 1 4,5 8
( x 1 = 2 x 2 = 3,2 6 )
Ling Xueling
一,派出机构的设定如,消防站,卫生站等派出机构问题
1,问题
Ohio 银行拟在某地区 20 个县中开展信贷业务 ( 原先无任何机构 )
州银行法规定：任何一银团在任一县中除非有分行,则可在此县中及相邻县中开展信贷业务银行管理层决定,既要少设分行,又要尽量多 ( 20 个县 ) 开展信贷业务,问题是：如何选定分行所在县？
位于 Ohio 某地区 20 个县的地理分布大致如后,( 县名略 )。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
一,派出机构的设定
1,问题第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
1
13
16
15
14
5
4
3
2
12
6
7
17
9
8
18
10
11
19
20
Ling Xueling
一,派出机构的设定
2,建模
1） 将每一个县及其邻县用数字标出,如：
考虑中县,1 2 3,..................
相邻县,2,12,16 1,3,12 2,4,9,10,12,13,...................
2） 定义决策变量 ( 0－ 1 变量 )
x i = 1 若在第 i 县设分行,否则为 0
3） o.f,（ 最小成本 ）
min ∑ x i
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
一,派出机构的设定
2,建模
4） 约束为了在一个县开展信贷业务,该县要么设分行,要么与有分行的县紧邻,则对第一个县来说
x1 + x2 + x12 x + x16 ≥ 1
对第二个县：
x1 + x2 + x3 + x12 ≥ 1
......................
3,求解
x7 = x11 = x12 = 1 其余 x i = 0。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型为了利用 0－ 1模型的灵活性,可以考虑利用 二进制展开 巧妙地将一些 I.P,模型 转化成 0－ 1 规划模型
1,例子
1） 模型
max 2x1 + 3x2
s.t.
x1 + 2x2 ≤ 10.5
x1 ≤ 6 －－ x1 上界为 6
x1,x2 ≥ 0,x1 整数 。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型利用二进制展开可以巧妙地将一些 I.P,模型 转化成 0
－ 1 规划模型
1,例子
2） 模型的 特点,x1 上界 6
3） 处理,因为 x1 = 0,1,2,3,4,5,6
所以可 令,x1 = 1y1 + 2y2 + 4y3
其中 y i = 0 或 1
4） 新模型见下页 。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型利用二进制展开可以巧妙地将一些 I.P,模型 转化成 0
－ 1 规划模型
1,例子
4） 新模型
max 2( 1y1 + 2y2 + 4y3 ) + 3x2
s.t.
( 1y1 + 2y2 + 4y3 ) + 2x2 ≤ 10.5
( 1y1 + 2y2 + 4y3 ) ≤ 6
y1,2y2,y3,x2 ≥ 0,y1,y2,y3 = 0,1。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
Ling Xueling
二,将 I.P,模型 转化成 0－ 1 规划模型利用二进制展开可以巧妙地将一些 I.P,模型 转化成 0
－ 1 规划模型
1,例子
5） 最优解
y1 = 0,y2 = 1,y3 = 1,x2 = 2.25
即,x1 = 6,x2 = 2.25 o.f,= 18.75
2,一般的二进制展开令：
若 x k 上界是 u,则 p 是 满足 ≥ u 的最小整数 。
第三节 利用计算机求解 I.P,的例子凌晨,凌晨,
i
p
i
i
k yx?
1
12
Ling Xueling
The End of Chapter 7
