二、整数规划问题的数学模型·一般形式：Max(或Min)Z=Zcx;j=1n,≤(或≥;或=) b(i=1,2,,m)s.t.j=1[x,≥0（j=1,2,,n)且部分或全部为整数·结论：（1）全部变量限制为整数的纯整数规划的可行解的个数是可数的，特别若变量有界。则可行解的个数有限；②整数规划的可行域是对应松弛问题的可行域的子域，但一般不能通过对松弛问题的最优解舍入取整而得到整数规划的最优解。金
二、整数规划问题的数学模型 • 一般形式： = = = = = 且部分或全部为整数 或 或＝） 或 0 ( 1,2, , ) ( ; ( 1,2, , ) . . ( ) 1 1 x j n a x b i m s t Max Min Z c x j j i n j i j j n j j • 结论： ①全部变量限制为整数的纯整数规划的可行 解的个数是可数的，特别若变量有界，则可行解的 个数有限；②整数规划的可行域是对应松弛问题的 可行域的子域，但一般不能通过对松弛问题的最优 解舍入取整而得到整数规划的最优解
第二节分枝定界法一、分枝定界法基本思路分枝定界法的核心是“分枝”和“定界”基本思路：设极大化的整数规划问题为IP，相应的不含整数约束的线性规划即松弛问题为LP。若LP的最优解不符合IP的整数条件，那么LP的最优目标函数值必为IP的最优目标函数值Z*的一个上界，记作乙；而IP的任意可行解的目标函数值将是Z*的一个下界，记作Z。对LP的非整数解的相邻整数作附加条件，从而形成两个分枝，即两个子问题，两个子问题的可行域中包含原整数规划问题的所有可行解。不断分枝，逐步减小乙，增大乙，最终求得乙*
第二节 分枝定界法 一、分枝定界法基本思路 分枝定界法的核心是“分枝”和“定界”。 基本思路：设极大化的整数规划问题为IP，相 应的不含整数约束的线性规划即松弛问题为LP。若 LP的最优解不符合IP的整数条件，那么LP的最优目 标函数值必为IP的最优目标函数值Z 的一个上界， 记作 ；而IP的任意可行解的目标函数值将是Z 的 一个下界，记作Z 。对LP的非整数解的相邻整数作 附加条件，从而形成两个分枝，即两个子问题，两 个子问题的可行域中包含原整数规划问题的所有可 行解。不断分枝，逐步减小 ，增大 Z ，最终求 得Z 。 Z Z
二、分枝定界法求解[例2]用分枝定界法求解例1中的整数规划IP：Max Z =8x, +5xX +2 ≤69x +5x2 ≤45s.t.X,X ≥0Xi,x,均为整数解：第1步先不考虑整数约束，求解IP的松弛问题LPX +x,≤6s.t.39x +5x2 ≤45MaxZ =8x, +5x2[ Xi,X, ≥ 0
二、分枝定界法求解 [例2] 用分枝定界法求解例1中的整数规划IP： Max 1 2 Z x x = + 8 5 1 2 1 2 1 2 1 2 6 9 5 45 . . , 0 , x x x x s t x x x x + + 均为整数 解：第1步 先不考虑整数约束，求解IP的松弛问题LP: + + = + , 0 9 5 45 6 8 5 . . 1 2 1 2 1 2 1 2 x x x x x x MaxZ x x s t
这时LP可能会得到下列情况之一：LP没有可行解，此时可下结论，原问题IP没有可行解，计算停止：②LP有最优解，并符合IP的整数条件，则LP的最优解即为IP的最优解，计算停止：③LP有最优解，其最优值为Z(O)，但解不符合IP的整数条件，转入第二步。本例LP的最优解为x=3.75，x2=2.25，最优值为Z(0)=41.25，不符合整数条件，属于情况③。第2步定界。设IP的目标函数最优值为Z*，则Z*<Z(O)，即Z(O)为Z*的一个上界，记为 =Z(O）。用观察法任找IP问题的一个可行解，其对应的目标函数值记为Z，则Z为Z*的一个下界，若IP问题的可行解不易看出，也可直接取Z=-0，于是我们有Z≤Z≤Z
这时LP可能会得到下列情况之一：①LP没有 可行解，此时可下结论，原问题IP没有可行解， 计算停止；②LP有最优解，并符合IP的整数条件， 则LP的最优解即为IP的最优解，计算停止；③LP 有最优解，其最优值为Z (0)，但解不符合IP的整数 条件，转入第二步。 本例LP的最优解为x1＝3.75，x2＝2.25，最优值 为Z (0)＝41.25，不符合整数条件，属于情况③。 第2步 定界。设IP的目标函数最优值为Z ，则 Z Z (0)，即Z (0)为Z 的一个上界，记为 ＝Z Z (0) 。 Z Z Z 用观察法任找IP问题的一个可行解，其对应的目标 函数值记为Z ，则 Z 为Z的一个下界，若IP问题 的可行解不易看出，也可直接取Z ＝ -， 于是我们有
对本例，我们取Z=-80,-8=Z≤Z≤z=41.25第3步分枝。在LP的最优解中任选一个不符合整数条件的变量x;，其值为b;，记[b,]为b,的整数部分，构造两个约束条件：x;≤[b;]和x;≥[b;]+1，把这两个条件分别加入LP，从而将LP分为两枝：LP1和LP2，求线性规划LP1和LP2后进入下一步。本例对x=3.75，构造约束条件xi≤3和xi≥4，得Maxz =8x; +5xMaxZ=8x,+5x,X +X, ≤6Xi+x, ≤6LP1:9x, +5x, ≤ 459x, +5x,≤45LP2:s.t.s.t.Xi,x ≥0Xi,x, ≥0[X)≥4x≤3
对本例，我们取 Z＝ -， Z Z Z ＝41.25 -＝ 第3步 分枝。在LP的最优解中任选一个不符合整数 条件的变量xi，其值为bi，记[bi ]为bi的整数部分，构 造两个约束条件：xi [bi ]和xi [bi ]+1，把这两个条件 分别加入LP，从而将LP分为两枝：LP1和LP2，求线 性规划LP1和LP2后进入下一步。 本例对x1＝3.75，构造约束条件x13和x14，得 LP1： LP2： + + = + 3 , 0 9 5 45 6 . . 8 5 1 1 2 1 2 1 2 1 2 x x x x x x x s t MaxZ x x + + = + 4 , 0 9 5 45 6 . . 8 5 1 1 2 1 2 1 2 1 2 x x x x x x x s t MaxZ x x