云南师范大学：《数学建模与数学实验》课程PPT教学讲义_第5讲 整数规划（费培之）

(数学模型 第三节 整数规划模型的解

第三节 整数规划模型的解

数学模型 例整数规划模型 2 s.t9x1+7x,≤56 7x1+20x,≤70 1,x2≥0 且为整数 345 由①④解得: ,x2=1.817,maxz=355.890 (1)若取整:x1=4,x2=1,=250, 是可行解,但非最优解,因有可行解: x1=4,x2=2,3Z=340>250 (2)按四舍五入得:x1=5,x2=2,不是可行解 因②左边为:5956 用穷举法也是不可取的

例 整数规划模型 max 40x1 90x2 z = + s.t 9x1 + 7x2  56 7x1 + 20x2  70 x1 , x2  0 且为整数 1 2 3 4 5 由 1 — 4 解得: x1 = 4.809, x2 = 1.817, max z = 355.890                     （1）若取整： 4, 1, 250, x1 = x2 = z = 是可行解，但非最优解， x1 = 4, x2 = 2, z = 340  250 （2）按四舍五入得： 5, 2, x1 = x2 = 不是可行解 因 2 左边为：59 56  用穷举法也是不可取的。 因有可行解：

分枝定界法 (数学模型 设整数规划模型: inz=∑ (P) st ∑ i5 x1≥0且为整数,j=1,2,…,n 记最优解为X”,最优目标值为z 松弛问题: mnz三 ∑ st ≥0,j=1, 记可行域为S0,最优解为X0,最优目标值为z

一、分枝定界法 设整数规划模型： （P） = = n j j xj z c 1 mins t a x bi i m n j ij j . , 1,2, , 1  = =  = xj  0 且为整数， j = 1,2,  ,n = = n j j xj z c 1 mins t a x bi i m n j ij j . , 1,2, , 1  = =  =  0, xj j = 1,2,  ,n 记最优解为 ，最优目标值为 。  X  z 松弛问题： （P0） 记可行域为S0 , 最优解为X0 ,最优目标值为z0 。 1 2 3

(数学模型 3 ≤[b2 →X 1,1 若X1整,则剪枝当前上界 0 3 并换上界:z≤x,则剪枝 自然上界 若z2 19 则分枝

0 0  X ,z : P0 1 — 3 • 若 X0 整，则 X = X0  • 若 非整， 则分枝 0 0 xi = bi   +  z z 且 0 自然上界 S0 0 bi S1 S2 1 1  X ,z P1 : 1 — 3 [ ] 0 0 xi  bi 2 2  X ,z P2 : 1 — 3 [ ] 1 0 0 xi  bi + 若 X1 整，则剪枝 并换上界：   +  z 1 z 若 X2 非整，则 • 若 z2  z1 ，则剪枝 • 若 z2  z1 ，则分枝 当前上界

(数学模型 3x≥|bn+1, X 393 若X3整,则剪枝 2 若3当前上界,则剪枝 若x4≤当前上界,则分枝 剪完所有枝得:x≤k<…<孔<+ 最小上界对 应的最优解 则 2=z X=X 为所求。 kg k

3 3  X ,z 1 — 3 : P3 xi0  [bi0 ]+ 1,  4 4  X ,z P4 : 1 — 3 xi0  [bi0 ]+ 1,  若 X3 整，则剪枝 • 若 z3  z1 ，则换界    +  1 z z3 z • 若 z3  z1 ，则不换界 若 X4 非整，则 • 若 z4  当前上界，则剪枝 • 若 z4  当前上界，则分枝 剪完所有枝得：     +  1 z z z k  则 k X Xk z = z =   , 最小上界对 应的最优解 为所求。 P2

(数学模型 对每个子问题P,不外乎有以下三种可能情况: (1)不可行,则剪枝; (2)其最优解X为整数解,则剪枝,且 当目标值当前上界时,则剪枝; 当目标值z≤当前上界时,则分枝。 注:对于极大化问题,则是定下界,最大下界对应 的整数解为所求 0<1<…<z≤z≤ 0 则 k g X"=Ⅹ

对每个子问题 ，不外乎有以下三种可能情况: Pi （1） 不可行，则剪枝； （2）其最优解 Xi 为整数解，则剪枝，且 • 当目标值 zi  当前上界时，则换界； • 当目标值 zi  当前上界时，则不换界。 （3）其最优解 Xi 为非整数解，则 • 当目标值 zi  当前上界时，则剪枝； • 当目标值 zi  当前上界时，则分枝。 注：对于极大化问题，则是定下界，最大下界对应 的整数解为所求。 1 0 z z z z −     k     则 k X Xk z = z =   , 归纳起来:

(数学模型 例求解minz=-3x-4x2 st2x1+5x,≤15(2 2x1-2x2≤53 > 且为整数 5 解松弛问题P可用 3 图解法 X0(39,14) 01234567 3x1-4x2 目标函数等值线

例 求解 min 3x1 4x2 z = − − s.t 2x1 + 5x2  15 2x1 − 2x2  5 x1 , x2  0 且为整数 1 2 3 4 5 1 2 3    1 2 3 4 5 6 7         1 x 2 x 0      解松弛问题P0 可用 图解法 S0 − x − x = z 3 1 4 2 目标函数等值线 (3.9, 1.4) X0 • S1 S2

(数学模型 →X0=(3.9,1.4) =-17.5 x,<1 175≤z<+0 2≥2 P:①(4x2≤ 2 4)x,≥2 →X1=(3.5,1) →X2=(2.5,2) 14.5 15.5 x,<3 ≥4 2 x,≥3 P P→X3=(31)P不可行X3=12,2)y26不可行 13 14.8<-13 换界:z≤-13<+0 2 x,≥3

: P0 1 4 T X (3.9, 1.4)  0 = z0 = −17.5 −   +  17.5 z T X (3.5,1)  1 = z1 = −14.5 1 : 4 P1 x2  1 x2  1 T X (2.5,2)  2 = z2 = −15.5 : 1 4 P2 x2  2 x2  2 x1  3 T P X (3,1) 3  3 = z3 = −13 x1  4 P4 不可行 x1  2 x1  3 P5  T X (2,2.2) 5 = z5 = −14.8 P6 不可行  −13  −  + x2  2 x2  3  换界: z 13

(数学模型 X 14.8-14 换界:z≤-14<-13<+00 ∴不换界 最优目标值:x*=-14 最优解: X"=(2,2)

P5  T X (2,2.2) 5 = z5 = −14.8 −13 x2  2 x2  3 T P X (2, 2) 7  7 = z7 = −14 T P X (0, 3) 8  8 = z8 = −12 分枝  −13 换界：  −  −  +  z 14 13 不换界 = −12  −14, 8 z 最优目标值： = −14  z 最优解： T X = (2, 2)  ＃

(数学模型 若对每一个变量取0、1进行分枝,计算量很 大。如n=3的情形: 19293 9 9293 (0,0)(0 (1,0,x)(1,1,x3) (0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1) 共有20+21+22+23=24-1个子问题 n个变量的情形共有子问题个数: 1-2 20+21+22+…+2n= 2n+1-1 1-2 下面的方法可减少计算量

二、0－1规划的解 若对每一个变量取0、1进行分枝，计算量很 大。如 n = 3 的情形： ( , , ) x1 x2 x3 (0, , ) x2 x3 (1, , ) x2 x3 (0,0, ) x3 (0,1, ) x3 (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0, ) x3 (1,1, ) x3 (1,0,0) (1,0,1) (1,1,0) (1,1,1) 2 2 2 2 2 1 0 1 2 3 4 共有 + + + = − 个子问题 n个变量的情形共有子问题个数： 2 1 1 2 1 2 2 2 2 2 1 1 0 1 2 = − − − + + + + = + + n n  n 下面的方法可减少计算量