2015/10/22
应用优化技术
min
Cij xij Fi yi
i, j
i
n
s.t.
xij Si yi
j 1
i 1, , n
n
xij d j
i 1
j 1, , n
n
yi m
i 1
yi 0或1
xij 0
6
i, j 1, 2, , n
实例三
调和问题：利用一些成分 调和为一个产品
N
1 INT
log
yU log 2
yL
2015/10/22
应用优化技术
LP 0-1规划
4
实例一
0-1背包问题
容积v
物品j：价值wj，体积vj
设
1 xj 0
j放入 j不放
max
n
wj xj
j 1
n
s.t.
vjxj v
j 1
x j 0或1, j 1, 2 , n
2015/10/22
min x0
xij
1 0
a j 在i上加工 a j 不在i上加工
n
s.t.
a j xij x0 i 1, , m
j 1
m
xij =1
j 1, , n
i 1
xij (0,1) i 1, , m，j 1, , n
2015/10/22
应用优化技术
9
整数规划解法概述
枚举
可行方案的数目常常是有限 求解实际问题不现实
2015/10/22
应用优化技术
28
隐数法
n
min z cj xj j 1
n
s.t. aij x j bi i 1, 2, , m j 1
xj 0或1 j 1, 2, , n
cj 0 0 c1 c2 cn
化为标准形式
对目标函数求极大值时，将目标函数中的系数加上负号，改为 求极小值
尽量让变量取0，除 非不得已，再使某些 变量取1
min z 8x1 2x2 4x3 7x4 5x5 s.t. 3x1 3x2 x3 2x4 3x5 2
5x1 3x2 2x3 x4 x5 4 x1, x2 , x3 , x4 , x5 0或1
x1 1
② 可行z＝8
④ 不可行可分
14
分解
问题(P)的可行解集合——FS(P) 子问题(P1)、 (P2)、… 、 (Pn)定义为问题(P) 的一个分解nFS(Pi ) FS(P)
i 1
FS(Pi ) FS(Pj )
1i j n
(P)——父（结点）问题
(P1)、 (P2)、… 、 (Pn)——子（结点）问题
2015/10/22
应用优化技术
5
实例二
工厂选址问题
n个城市，需要某种物资数量为d1， d2，…， dn 现计划建造m座工厂
假设在城市j建厂，规模为Sj，投资为Fj，从城市i到j的单位运 价为Cij
问m个工厂应设在何处，使满足需要且成本最低
1 若有一个工厂建在城市i
yi 0
i不建厂
xij 为i运往j的物资总量
i0
xij 1 任意非空真子集S 0,1, , n
jS jS
nn
xij n 1
i0 j0
xij 0或1 i，j 0, , n
2015/10/22
应用优化技术
8
实例五
加工问题
m台机床， n种零件
加工时间 a1, a2, , an
如何分配，使各机床总加工任务相等，或尽可能均
衡
通常矛盾，需要折中
2015/10/22
应用优化技术
18
探测
令(CS)为一个候选的子问题，要确定(CS)的可 行域F(CS)中是否包含(P)的最优解，如有，找 到它
已探明，如果
F(CS)中没有比已知的一个最好解更好的解 找到(CS)的最优解
2015/10/22
应用优化技术
19
探测
探测准则
P4
: (98 /11, 2), x0
52 8 11
2015/10/22
应用优化技术
12
整数规划与混合整数规划
混合整数规划问题 分支定界法 0-1规划的隐数法 割平面法 混合整数非线性规划
2015/10/22
应用优化技术
13
分支定界法
分解 松弛 探测
2015/10/22
应用优化技术
一大类 优化命题
f,h,g线性 LP Y空
f,h,g非线性 NLP
f,h,g线性 Y非空
MILP
f,h,g非线性 MINLP
2015/10/22
应用优化技术
3
混合整数线性规划问题
min cT x d T y x, y
s.t. Ax By b x 0, x X Rn
y 0,1
y yL z1 2z2 4z3 2N 1 zN
A0 , Ai1, Ai2 , , Ain , A0
形成回路
对任意Ai、Aj，引入 xij (0,1) 若紧跟着Ai后的是Aj，取 xij 1，否则 xij 0
nn
min
dij xij
i0 j0
n
s.t.
xij 1 i 0, , n
j0
前后各一 个城市
n
xij 1 j 0, , n
应用优化技术
15
分解
常用的划分子问题方法 两分法
xj 是(P)的0-1变量， (P)可按 xj 1 和 xj 0 分解 x j 是整数，可按 xj xj 和 xj xj 1 分解
2015/10/22
应用优化技术
16
松弛
松弛问题(RP)
放弃(P)的某些约束条件，所得到的问题 FS(P) FS(RP) 性质
最优性 探测
(RCS)——(CS)的松弛问题
zRCS——(RCS)的最优值 zCS——(CS)的最优值 z*——目前为止的最优值，如果还无(P)的可行解，z*=+
可行性 探测
如果(RCS)无可行解，则(CS)无可行解，已探明，可 从(P)的分解表中删去
如果zRCS ≥z*，无更好的可行解，探明，可删去 如果(RCS)的最优解是(CS)的可行解，则已求得(CS)
2015/10/22
应用优化技术
21
分支定界法
(1) 初始化：MILP问题作为(CS)， z*=+
(2) 终止：如果CS列表为空，终止，当前z*为最优解，如果 不存在，则原问题无可行解
(3) (CS)问题的选取：从子问题列表中选一个
(4) 松弛： (CS)(RCS)zRCS (5) 探测：
I. 如果(RCS)无可行解 (CS)无可行解(2)
y变量的一个子集置为0或1，其 它看作[0，1]之间的连续变量。 (RCS)11和(RCS)12两个子问题的解 为(RCS)01解的上界
2015/10/22
应用优化技术
24
线性规划松弛的分支定界
例：
min 2x1 3y1 2 y2 3y3
s.t. x1 y1 y2 y3 2 10x1 5 y1 3y2 4 y3 10 x1 0 y1, y2 , y3 0,1
II. 如果zRCS ≥z* (RCS)中无更好的解(2) III. 如果(RCS)的最优解是(CS)的可行解，则是(CS)的最优解，如
果zRCS <z*，更新z* (2)
(6) 分解：分解(CS)，将子问题加入(CS)问题列表中
2015/10/22
应用优化技术
22
分支定界法
利用先验知识，赋予问题最优值尽可能好的上下界，给 出(CS) 列表
I J
整点凸包 OEFGHIJ
H
B
G
F
x0 58, x1 2, x2 4
O
EA
x1
割平面法
x0 58.8, x1 9.2, x2 2.4
先不考虑整数限制求线性规划问题的解
然后增加新的约束，这些约束将整数限制松弛后所扩大的可行域逐步 割掉，但不割掉任何可行的整数解
最后使所得到的线性规划问题的最优解就是原问题的最优整数解
约束不等式为≥时，两边乘以-1改为≤
约束为等式时，改为≥和≤两个不等式，再在≥式两边乘以-1使
之变为≤
若
cj
0，取
x
j
1
xj
x3 1
①
x1 0
③不可行可分
x2 1
x2 0
⑤
不可行不可分
x3 0
2015/10/22
⑥ 可行z=6
应用优化技术
x4 1
⑦不可行可分
x4 0
⑧
⑨
27
不可行不可分 不可行不可分
隐数法
主要思想
给出一组值（ 由某个子结点的固定变量和自由变量构成）， 计算目标值，决定有无必要再去验证这组值的可行性。如果这 个目标值比已有的目标值还大，就无必要再去验证其可行性， 更无必要对该结点再作分解
xj——连续用量的j成分的量 yk——1或0表示离散用量的
成分用或不用； vk表示用量 cj ，dk——成分的成本 aij——成分j中i组分分量 如何调和使得产品质量合格
且成本最低？
min c j x j dk vk yk
j
k
s.t. wl x j vk yk wu
j
k
Ail aij x j aik vk yk Aiu
最优
z* 6 x 0 ( y1, y2 , y3 ) (1, 0,1)
2015/10/22
应用优化技术
25
整数规划与混合整数规划
混合整数规划问题 分支定界法 0-1规划的隐数法 割平面法 混合整数非线性规划