(数学模型 第三节 整数规划模型的解
第三节 整数规划模型的解
数学模型 例整数规划模型 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 下面的方法可减少计算量
