运筹学·整数规划

整数规划 Integer Programming(IP)

整数规划

整数规划 Integer Programming(IP)整数规划数学模型的一般形式(IP)问题 Max(min) z = ∑cjxj ∑aijxj ≤(或=,或≥)bi i=1,2,…,m xj ≥ 0 j=1,2,…,n xj 中部分或全部取整数 Max(min) z = ∑cjxj

s.t.松弛问题 s.t.

∑aijxj ≤(或=,或≥)bi i=1,2,…,mxj ≥ 0 j=1,2,…,n 松弛问题：不考虑整数条件，由余下的目标函数和约束条件 2 构成的规划问题称为该整数规划问题的松弛问题。

整数规划 Integer Programming(IP)整数规划问题的类型1.

2.

3.

纯整数线性规划——pure integer linear programming:全部决策变量都必须取整数值。 混合整数线性规划——mixed integer linear programming:决策变量中一部分必须取整数值， 另一部分可以不取整数值。 0-1型整数线性规划——zero-one integer linear programming:决策变量只能取值 0 或 1 。

整数规划 Integer Programming(IP)线性整数规划问题解的特点1.2.

3.

整数规划问题的可行解是松弛问题的可行解吗？ 松弛问题的最优解就是线性整数规划问题的最优 解吗？ 松弛问题的最优解经过化整处理后就是整数规划 的最优解吗？

整数规划 Integer Programming(IP)例1

Max s.t.

Z = 20X1 +10 X2 5X1 + 4X2 ≤ 24 2X1 + 5X2 ≤ 13 X1 , X2 ≥ 0 X1 , X2 取整数

整数规划 Integer Programming(IP)

最优解不一定在顶点上达到； 最优解不一定是放松问题最优解的邻近整 数解； 整数可行解远多余于顶点，枚举法不可取

整数规划 Integer Programming(IP)整数规划问题的求解方法 分支定界法(branch and bound method)

设有最大化的整数规划问题A,与它相应的线 性规划问题为B,求解问题B,若B的最优解不 符合A的整数条件，则B的最优值一定为A最优 值Z*的上界，而A的任意可行解的目标函数值 将是Z*的下界，分支定界法就是将B的可行域 分成子区域(称为分支方法)的方法，通过减 小最优值的上界和下界最终得到最优值。7

整数规划 Integer Programming(IP)例2

Max s.t.

Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 , X2 ≥ 0 X1 , X2 取整数

整数规划 Integer Programming(IP)松弛问题 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 , X2 ≥ 0该整数规划松弛问题的解为： (X1 ,X2 )= (3/2 ,10/3) Z0 = 29/6

0≦Z* ≦29/6

整数规划 Integer Programming(IP)为原问题增加两个约束条件 X1≥ 2; X1≤ 1

问题2 问题1

0≦Z* ≦29/6

整数规划 Integer Programming(IP)松弛问题 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 , X2 ≥ 0 B2 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≤1 X1 , X2 ≥ 0 Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥2 X1 ,

X2 ≥ 0

(3/2 ,10/3) Z0 = 29/6 B2:解 (1,7/3 ) Z2= 10/3 B1:解 (2,23/9 ) Z1= 41/9

B1

Max

0≦Z* ≦41/911

整数规划 Integer Programming(IP)B1 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥2 X1 , X2 ≥ 0

(3/2 ,10/3) Z0 = 29/6

B2:解 (1,7/3 ) Z2 = 10/3

B1:解 (2,23/9 ) Z1 = 41/9

B11

Max

B12:解 (33/14,2 ) B12 Z12 = 61/14

Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥2 X2 ≥ 3 X1 , X2 ≥ 0 Max Z = X 1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥2

X2 ≤ 2 X1 , X2 ≥ 0

0≦Z* ≦41/9

整数规划 Integer Programming(IP)B12 Max Z = X 1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥2 X2 ≤ 2 X1 , X2 ≥ 0 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥3 X2 ≤ 2 X1 , X2 ≥ 0 Max Z = X 1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≤2 X2 ≤ 2 X1 , X2 ≥ 013

(3/2 ,10/3) Z0 = 29/6

B2:解 (1,7/3 ) Z2 = 10/3

B1:解 (2,23/9 ) Z11 = 41/9 B12:解 (33/14,2 ) Z12 = 61/14 B121:解 (3,1 ) Z112 = 4

B121

B122

B122:解 (2,2 ) Z121 = 4

整数规划 Integer Programming(IP)分枝定界法求解问题的步骤： 将要求解的整数规划问题称为问题A,将其松 弛问题称为问题B,若 (1)B没有可行解，这时A也没有可行解，停 止； (2)B有最优解，并符合问题A的整数条件， B的最优解即为A的最优解； (3)B有最优解，但不符合A的整数条件，记 它目标函数值为最优值上界。14

整数规划 Integer Programming(IP)第一步：分枝，在B中选择一个不符合整数条 件的变量xj,其值为bj,[bj]表示小于bj的最 大整数，构造两个约束条件。 xj ≦[bj]; xj ≧[bj]+1 将此两个约束条件加入B,在不考虑整数条件 的情况下，求解两个后继问题B1和B2。

整数规划 Integer Programming(IP)定界，以每个后继问题为一分枝标明求解结果， 与其他问题解的结果中，找出目标函数最大者 作为新的上界，从已符合整数条件的各分支中， 找出目标函数值最大者作为新的下界，若无作 用，下界仍为零。 第二步：比较与剪枝，各分枝的最优目标函数 中若有小于下界者，则剪掉这枝，此后无需再 考虑。若大于下界，且不符合整数条件，则重 复第一步，直至找到最优解为止。16

整数规划 Integer Programming(IP)0-1整数规划问题 0-1决策变量 0-1规划 固定成本问题 辅助0-1变量 产品互斥问题 两个约束中选一个 约束的问题

整数规划 Integer Programming(IP)0-1整数规划问题 0-1 变量及其应用 0-1变量作为逻辑变量(Logical variable),常常被引 用来表示系统是否处于某个特定的状态，或者决策变量是否取 某个特定的方案。如1 0 当决策取方案 Pj 时 当决策不取方案 Pj 时

xj =

整数规划 Integ

er Programming(IP)0-1型整数规划问题的求解 方法： 枚举法。将全部解列出，验证约束，比较目标。 隐枚举法。找出一个可行解，算其目标。由此 确定一个过滤条件，再枚举。