- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
上述分枝过程可7
x1≤3 x1≥4
LP1:X=(3,7.6) Z1=34.8
x2≤6
LP2:X=(4,6.5) Z2=35.5
x2≥7 无可行解 x1≥5 LP5:X=(5,5) Z5=35
OR:SM OR:SM
LP3:X=(4.33,6) Z3=35.33
8 OR:SM OR:SM
第二节 整数规划求解
二、穷举整数法
x2
5 4 3 2 1 2x1 + x2 =9
•
• • •
1
• • •
2
• (3,3) • •
3
(3 1 7 ,2 ) 9 9
•
4
5x1 +7 x2 =35
x1
对于决策变量少，可行的整数解又较少时，这种穷举法有时是 可行的，并且也是有效的。 但对于大型的整数规划问题，可行的整数解数量很多，用穷举 法求解是不可能的。例如，指派问题 。
6 OR:SM OR:SM
第一节 整数规划问题
F 三、混合整数规划
i
例：某产品有n个区域市场，各区域市场的需求量为 bj吨/月；现拟 在m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选 i 地建厂，生产能力为 ai吨/月，其运营固定费用为F元/月；已知址i至j 区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？ 解：选址建厂与否是个0-1型决策变量，
管理运筹学--管理科学方法
李军
桂林电子科技大学商学院
第4 章 整数规划
内容提要 Sub title
第一节 整数规划问题
纯整数规划 0-1规划 混合整数规划
第二节 整数规划求解
分枝定界法
第三节 整数规划应用
2
OR:SM OR:SM
本章框架
本章要点： 1.整数规划的特点； 2.整数线性规划求解原理； 3.0-1规划和指派问题的处理思路
19 OR:SM OR:SM
第三节 整数规划应用
二、人员安排规划
某服务部门各时段(每2小时为一时段)需要的服务人数如表： 1 2 3 4 5 6 7 8 时段 9 11 13 8 5 3 服务员最少数目 10 8 按规定，服务员连续工作8小时 (4个时段)为一班。请安排服务员 的工作时间，使服务员总数最少. 解：设第j 时段开始时上班的服务员 人数为xj 第 j 时段来上班的服务员将在第j+3 时段结束时下班，故决策变量有 x1,x2,x3,x4,x5 。
x1 *=28/9， x2 * =25/9，Z * =293/9
舍入化整 x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 ≤35，非可行解； x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解； x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。
整数 规划
一般 的ILP
问题背景与数学描述 求解
分枝定界法
割平面法
0-1规划 特殊的ILP 指派问题
3 2011-3-25
原理 步骤 进一步讨论
建模 求解 特点分析
OR:SM 3 OR:SM
第一节 整数规划问题
• 线性规划的决策变量取值可以是任意非负实数，但许多 实际问题中，只有当决策变量的取值为整数时才有意义
A 占地（万平米） 费用（万元） 2 5 B 5 4 资源限制 13 24
生产能力（百件/年）
20
10
解：设A、B两类基地各建设 x1,x2 个，则其模型为： max Z 20 x1 10 x 2
2 x1 5 x 2 13 5x1 4 x 2 24
x1 , x 2 0且为整数
例如，产品的件数、机器的台数、装货的车数、完成工作的人 数等，分数或小数解显然是不合理的。
• 要求全部或部分决策变量的取值为整数的线性规划问 题，称为整数规划(Integer Programming)。
全部决策变量的取值都为整数，则称为全整数规划(All IP)
仅要求部分决策变量的取值为整数，则称为混合整数规划 (Mixed IP)
要求决策变量只取0或1值，则称0-1规划(0-1 Programming)
4
OR:SM OR:SM
第一节 整数规划问题
一、纯整数规划
例4.1：某企业利用材料和设备生产甲乙产品，其工艺消耗 系数和单台产品的获利能力如下表所示：
资源 产品 甲 2 乙 1 现有量 9
A
B
5
6
7
5
35
单台利润
问如何安排甲、乙两产品的产量，使利润为最大。 解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整数
LP1
6
LP5:X=(5,5),Z5=35 1.2x1 0.8x2 10
LP3
LP5
C 10
2x1 2.5x2 25 LP5 : x1 5，x2 6 x1 , x2 0
o
15
3
4 5
x1
OR:SM OR:SM
尽管LP1的解中x1不为整数，但Z5>Z因此LP5的最优解 就是原整数规划的最优解。
LP4： x1 2 4 , x 2 3, Z 3 1 5 4 5
上界： 31 下界： 29 4 5
x1≤2
LP5： x 1 2, x 2 3 4 7 , Z 29 6 7
x1 ≥3
LP6： 无 可 行 解
上界： 下界： 29 29 6 7
x2≤3
LP7： x 1 2, x 2 3, Z 2 7 x1
10
OR:SM OR:SM
第二节 整数规划求解
【例3.5 】用分枝定界法求解例3.1
max Z 4 x 1 3 x 2 1 . 2 x 1 0 . 8 x 2 10 2 x 1 2 . 5 x 2 25 x 1 , x 2 0 , 且均取整数
【解】先求对应的松弛问题（记为LP0）：
max Z 4 x1 3x2
1.2 x1 0.8x2 10 LP0 : 2 x1 2.5x2 25 x1 , x2 0 用图解法得到最优解X＝（3.57,7.14）,Z0=35.7,如下图所示。
11 OR:SM OR:SM
第二节 整数规划求解
x2
1.2x1 0.8x2 10
x1≤4
LP4:X=(4,6) Z4=34
16
第二节 整数规划求解
LP 0 ：
三、分支定界法
MaxZ 6 x1 5x2 2 x1 x2 9 5x 7 x2 35 s.t. 1 x1 , x2 0 x1 , x2取整数
上界： 32
x1 3
1 9
,x2 2
x2 ≥4
LP8： 2 1 , x 2 4, Z 28 5 2 5
上界： 29 下界： 29
17
OR:SM OR:SM
分枝定界法小结
非整数解A 增加约束 增加约束
整数解B1 增加约束
非整数解B2, 比B1好 增加约束 整数B3 ，
非整数解B4, 比B1,B3好 增加约束
1 若分枝后得到整数解，则这枝不必再分枝。 2 若分枝后得到非整数解, 如果比整数解更好，则这枝继续分枝
7
OR:SM OR:SM
第二节 整数规划求解
一、舍入化整法
为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到 与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能超出 了可行域，成为非可行解；或者虽是可行解，却不是最优解。
不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题 对于例1的数学模型，不考虑整数约束的最优解：
松弛问题LP0的最优解 X=(3.57,7.14),Z0=35.7
10
A
B
2x1 2.5x2 25
o
12
C 8.33
10
x1
OR:SM OR:SM
x2 ① ② A 10
增加约束x1 3及x1 4得到两个线性规划
max Z 4x1 3x2
LP1:X=(3,7.6),Z1=34.8
5 OR:SM OR:SM
第一节 整数规划问题
二、0-1规划
序号
物品 重量 重要性系数 1 食品 2 氧气 3 冰镐 4 绳索 5 帐篷 6 相机 7 设备
5
20
5
15
2
18
6
14
12
8
2
4
4
10
登山队员可携带最大重量为25公斤。问都带哪些物品的重要性最大。 解：对于每一种物品无非有两种状态，带或者不带，不妨设 0 不带此种物品 xj 1 带此种物品 0-1规划的模型： max Z 20 x1 15 x 2 18 x3 14 x 4 8x5 4 x6 10 x7 5 x1 5x 2 2 x3 6 x 4 12 x5 2 x6 4 x7 25 x j 0或1 ( j 1,2, 7)
7 5 ,Z 32 9 9
5 9
下界： 0
x1≤3
LP1 ： x1 3,x2 2 6 7 ,Z 32 2 7
x1 ≥4
LP 2 ： x 1 4 , x 2 1, Z 2 9
上界： 32
下界： 29 2 7
x2≤2
L P 3： x1 3,x2 2,Z 28
x2 ≥3
