-1/2
-1/2
0
用对偶单纯形法求解,得新的最优解。若
此时得到整数解，则解题过程完毕。否则， 重复第3，4步，直至获得原问题最优整数解 为止。此题计算得x1=1,x2=1,停止计算。此时 最优解为：X*=(1,1)T, Z*=2.
4.4 0—1整数规划问题
• 某些特殊问题，只做是非选择，故变量设置简 化为0或1，1代表选择，0代表不选择。
• ④对上面两个子问题按照LP方法求最优解。若某 个子问题的解是整数解，则停止该子问题的分枝， 并且把它的目标值与上一步求出的最优整数解相 比较以决定取舍。
• ⑤重复③④步直至获得原问题最优整数解为 止。
例题
• 例1. maxZ=5x1+7x2 7x1+24x2≤84 3x1+2x2 ≤18 x1，x2 ≥0且为整数
• 选取非整数解X*(0)的一个非整数分量xi*＝bi，其小 数部分为di，以该非整数分量的相邻整数bi－ di和bi － di＋1为边界将原问题分枝为两个子问题，并抛 弃这两个整数之间的非整数区域：
• Ⓐ在原LP模型中添加分枝约束xi≤ bi－ di,构成第一 个子问题；ⓑ在在原LP模型中添加分枝约束xi≥ bi － di＋1，构成第二个子问题。
• 例3. 某城市拟在其东、西、南三个区域设立邮
局，各地区都有几个具体的地点可供选择。要 求不超过总投资100万元的条件下，做出盈利最 大的决策。
地区 地点 投资 盈利 选点数
东区 西区
A1 A2 B1 B2 C1 C2
≥1
A3 A4 A5 B3 B4 B5 C3 C4 C5
≤2
南区
A6 A7 B6 B7 C6 C7
问题举例（整数规划模型）
• 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托
运所受限制如下表：
货物
甲 乙
托运限制
体积 每箱（米3）
5 4
24
重量 每箱（百斤）
2 5
利润 每箱（百元）
20 10
13
请问两种货物各托运多少箱，可使获得利润为最大？
4.2 整数规划图解法
x2
3 3
22
1
运筹学-整数规划
整数规划
本章要求 • 理解整数规划的含义 • 掌握分枝定界法的思想和 方法 • 掌握0-1变量的含义和用法 • 掌握指派问题的算法
4.1 整数规划问题的提出
• 决策问题中经常有整数要求， 如人数、件数、机器台数、货 物箱数……如何解决？四舍五 入不行，枚举法太慢 • 问题分类：纯整数规划、混合 整数规划、0-1整数规划 • 专门方法：分枝定界法、割平 面法、隐枚举法、匈牙利法
≥1
约束
100万元 最大化
求解0—1规划的隐枚举法
• 隐枚举法：不需要列出所有组合，只需关心目标函数值得最 优可行组合。按目标值从优到劣依次列出组合，逐个检验其 可行性；最先满足所有约束条件的组合为最优解，劣于最优 解的组合即使可行，也不列出检验而隐去。
•
④将割平面方程标准规范化，加到原最优 表中，用对偶单纯形法求新的最优解。
• ⑤重复第3，4步，直至获得原问题最优整 数解为止。
例题
• 例2：求解整数规划： • maxZ=x1+x2 • -x1+x2≤1 • 3x1+x2 ≤ 4 • x1,x2≥0,且为整数
解法如下：
• 1、先去掉整数约束条件，当成一般LP问题求解，得 最优解：x1=3/4,x2=7/4,z=5/2.
(4,1)
1
B
பைடு நூலகம்
（4.8,0) A
5x1+4x2=24
x1
2x1+5x2=13
图解法的启示
• A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是 IP的最优解;
• 纯整数规划的可行解就是可行域中的整数点； • 非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，
• ②若求得的最优解X*(0)刚好是整数解，则该整数解就是原IP 的最优解，否则，转下步。
• ③寻求割平面方程： • Ⓐ从最优表中抄下非整数解的约束方程：
•
Ⓑ将该约束方程所有系数和常数分解为整 数和正分数之和；
•
Ⓒ将整系数项归写于方程左边，真分数项 写于右边；
• ⓓ 考虑整数条件约束。以上方程左边为整 数，右边为非正数，即方程右边≤0。这就 是所求的割平面方程。
• 3/4-(3/4x3+1/4x4) ≤0，即-3x3－x4 ≤-3
割平面方程：-3x3－x4 ≤-3
4、将割平面方程标准规范化，加到原最优表中。
1
1
0
0
0
CB XB b
x1
x2
x3
x4
x5
1 x1 ¾
1
0
-1/4--1/4 ¼
0
1 x2 7/4
0
1
¾
¼
0
0 x5 -3
0
0
-3
-1
1
5/2 0
0
x1-1/4x3+1/4x4=3/4; x2+3/4x3+1/4x4=7/4
• ⓑ将该约束方程所有系数和常数分解为整数和正分数之和，并将整系数项 归写于方程左边，真分数项写于右边；
• x1-x3=3/4-(3/4x3+1/4x4)
• x2-1=3/4-(3/4x3+1/4x4)
• Ⓒ考虑整数条件约束。以上方程左边为整数，右边为非正数，即方程右边 ≤0。这就是所求的割平面方程。即
• 最终单纯形表如下：
1
1
CB XB b
x1
x2
1 x1 ¾
1
0
1 x2 7/4
0
1
0
0
x3
x4
-1/4
¼
3/4
1/4
5/2
0
0
-1/2
-1/2
• 2、该解不是整数解，转入下一步； • 3、ⓐ从最优表中抄下非整数解的约束方程： • x1-1/4x3+1/4x4=3/4; • x2+3/4x3+1/4x4=7/4
4.3 割平面法
• 基本思想：新增加一些线性(不等式）约束条件，称为割平面， 去“切割”相应的LP的可行域，并使切掉部分都是非整数解， 所有整数解都被保留下来。当这种割平面足够多时，使相应 LP和原IP具有相同的最优解。那么，相应LP的最优解也就是 原IP的最优解。
割平面法求解步骤
• ①先不考虑整数约束，变成一般的LP问题，求其最优解，记 为X*(0)。
不妨碍整数规划问题的优化； • IP问题的最优解不优于LP问题的最优解。
4.3 分枝定界法 • 思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求 最优解。 • 分枝定界法的步骤： • ①先不考虑整数约束，变成一般的LP问题，求其最优解，记为X*(0). • ②否则若，求得转的入最下优一解步。X*(0)刚好就是整数解，则该整数解就是原IP的最优解， • ③对原问题进行分枝，寻求整数最优解。