- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
整数规划（IP）的可行解是解除整数约束的 松弛线性规划（relaxation）的可行解。
推论：LP的最优目标函数值优于IP。
蓝颖杰 5
2014/1/3
整数规划IP与其松弛LP
可行域
LP空集 LP有界 LP无界
＝> ＝> ＝>
IP
空集
IP 空集或有界非空 IP 空集或有界非空或无界 IP 无解
求解整数规划的方法
从一个实例说起
车间扩张：如何扩张使每日利润最大化？
设备类型 压榨机 车床
预算
车间面积
采购价格
每日利润
15 30 200
8,000 4,000 40,000
100 150
设 x1 为压榨机的台数，x2 为车床的台数 maximize subject to Z = 100x1 + 150x2 8,000x1 + 4,000x2 40,000 15x1 + 30 x2 200 x1,x2 0且为整数
Z = 100x1 + 150x2 8,000x1 + 4,000x2 40,000
15x1 + 30 x2 200
x2 6 x1 1 x2 7 x1,x2 0
2014/1/3
无可行解
蓝颖杰 20
分支定界法：达到最优
更新定界后发现：上界=下界 DONE！（定界的功用之1） 注意：即使 现在还没有 达到最优， 我们也不必 对这个子问 题分支了。 它的线性规 划的可行区 域最大，这 省了我们不 少的麻烦！
19
分支定界法：求解新分支
node 6: maximize subject to Z = 100x1 + 150x2 8,000x1 + 4,000x2 40,000 15x1 + 30 x2 200 x2 6 x1 1 x2 6 x1,x2 0 node 7: maximize subject to 最优解: x1 = 1, x2 = 6 Z = 1,000
2014/1/3 蓝颖杰
x2 = 5.56 Z = 1,055.56
11
和Simplex的对话
小伙伴： Simplex先生，辛苦了！只可惜X2 = 5.56，能帮我们找到让X2为整数的最优解吗？ Simplex：只考虑整数？我可能帮不了，抱歉！ 小伙伴：等等，这样行吗？或者X2≤5，或者 X2≥6，就是不能在5和6之间。（放松要求） Simplex：我看看：这时可行域中间出现了一条 鸿沟，不再是凸集了。恐怕也不行。。。 小伙伴：再等等！可行域是被分成了两块，那么 分成两个规划分别求解如何？（分而治之） Simplex：分开求解两个线性规划是可以的…
2014/1/3 蓝颖杰
整数规划 的下界如 何定呢？ 提示：该 整数规划 的任何一 个可行解 都提供一 个下界。 下界未知 时等于负 无穷大。
21
整数规划的分支定界法
1.
不考虑整数约束求解模型。解若满足整数约束， 停止。否则令待分支问题集B ={原问题}。
2.
从B中找出上界最大的进行分支。选择一个分支 变量（通常选值离整数最远的）进行分支，并 分别求解分支问题的线性规划模型，然后判断：
• 所谓定界，就是确定子问题及原问题的上下界。若最大化： • 所有子问题的上/下界中最大的是原问题的上/下界。 • 任何子问题的最优解目标函数值是原问题的一个下界。 • 当某子问题的上界≤原问题的下界时，就不再细分它
• 分支定界法是通用的方法，不仅仅可应用到整数规划。
2014/1/3 蓝颖杰 23
对混合整数规划的运用
1hr
单位利润：300/unit
单位利润：500/unit
固定成本问题
伟恩德公司生产固定成本 如果每个生产周期内需要生产门(哪怕只产1 扇),都需要调整设备设置,成本是$700.这 样的成本是固定成本（不随产量变化）。 类似的, 生产窗的固定成本为$1300。 如何建立模型?
2014/1/3 蓝颖杰 31
前面的分支定界法的计算过程显然也适用于 混合整数规划。 我们在分支的时候，只考虑要求为整数的变 量——如此而已。
2014/1/3
蓝颖杰
24
整数规划的建模与应用
指派问题（IP例3_1,2,3)已讲 Knapsack（最基本的一类整数规划） 固定成本问题 其它类型的问题(可参阅教材)
2014/1/3
蓝颖杰 15
分支定界法：分支的解
2014/1/3
蓝颖杰
16
分支定界法：再次分支
有分支处的上界UB=该处两分支上界中较大的。 无分支处的上界UB=松弛线性规划的最优目标。 下一步：所有未分支处取上界UB最大的来分支。理由？
2014/1/3
蓝颖杰
17
分支定界法：再次求解
在新分支上求解对应的线性规划：
蓝颖杰
25
Knapsack （1）
物品不可重复的背包问题
（binary knapsack problem）
打包远行。背包的总重量不能超过W。可带 的有N件物品，每一件都独一无二。 物品i的重量为w[i]，使用价值为v[i]。应该 带哪些物品，使总价值最大？
2014/1/3
蓝颖杰
26
Knapsack （2）
x2 5
x1,x2 0
最优解: x1= 2.5, x2= 5, Z = 1,000
maximize
Z = 100x1 + 150x2
subject to
8,000x1 + 4,000x2 $40,000
15x1 + 30 x2 200
x2 6
x1,x2 0
2014/1/3
最优解: x1 = 1.33, x2 = 6, Z = 1,033.33
Knapsack （3）
物品可重复携带的情况
物品i共有G[i]个可带 这时0 <= x[i] <= G[i] 是一个纯整数规划问题。
2014/1/3
蓝颖杰
28
Knapsack （4）
现在我们继续扩展Binary Knapsack，分别 考虑下面的要求，如何建立约束：
① ② ③ ④ ⑤ ⑥
LP最优解: (1, A)。而IP的最优解分两种情况：
若A为正整数，(1, A) 若A为正分数，如 100.4，最优解（0，0）
舍入法可能得到非可行解，且可能相去甚远
若约束不要求严格成立（有一定弹性），舍入是好法子！ 对整数规划不好定义“影子价格”：不是右端项的线性函数。
蓝颖杰 8
2014/1பைடு நூலகம்3
Z = 100x1 + 150x2 8,000x1 + 4,000x2 40,000 15x1 + 30 x2 200 x2 6 x1 2 x1,x2 0 无可行解 18
2014/1/3
蓝颖杰
分支定界法：更新定界
全局上界再次变小：1033 1025.5
2014/1/3
蓝颖杰
整数规划的计算机求解（1）
在EXCEL中，设定可变单元格要满足 整数约束，INT表示整数，BIN表示0 －1变量（二进制）。
2014/1/3
蓝颖杰
12
分支定界法：区域的分割
2014/1/3
蓝颖杰
13
分支定界法：第一次分支
这俩“分支”问题各 自仍是整数规划： 一个麻烦变成了两 个麻烦！分成两个
能减少麻烦？要 考虑的可行解的 总数目可没有变！
小伙伴：根据整数规 划的基本性质。。。 碰运气！何况已经 挖去了一条鸿沟
2014/1/3
整数规划的求解复杂度
其可行域非凸集，求解的计算复杂度大增！
计算复杂度:基本运算量(加减乘除的次数） 问题规模：变量和约束的个数：系数矩阵大小 LP求解的计算复杂度与问题规模的平方成正比 IP则复杂得多,计算复杂度随规模呈指数增长！ 割平面法：这里我们不作详细介绍。 分支定界法：下面我们来详细介绍。
2014/1/3 蓝颖杰 10
先解松弛LP（试运气）
maximize Z = 100x1 + 150x2
subject to
8,000x1 + 4,000x2 40,000
15x1 + 30 x2 200 x1,x2 0
解得： x1 = 2.22
最优解不满足整数要求！ 我们必须向Simplex先生 反映这个问题。。。
如果带物品4的话，物品5也必须带 物品4,5必须同时带或不带 物品1,2,3不可以同时带 当且仅当同时带物品6，7时，必须带8 若带了物品6,7,8中任何一项，就必须带9 若恰带了物品9,10,11中的2项，则必带12
2014/1/3
蓝颖杰
29
伟恩德的例子
生产能力、产品所需资源、利润
4hr/wk 工厂1 12hr/wk 工厂2 3hr 2hr 固定成本: 700 门 窗 2hr 固定成本: 1300 18hr/wk 工厂3
node 4: maximize
subject to
Z = 100x1 + 150x2
8,000x1 + 4,000x2 40,000 15x1 + 30 x2 200 x2 6
x1 1
x1,x2 0 解得: x1 = 1, x2 = 6.17 Z = 1,025
node 5: maximize subject to
蓝颖杰 7
IP可行解的个数（可行域一般非凸）：
