用分支定界法解下列问题：min 2x1+x2—3x3 s．t． x1+x2+2x3≤5 2x1+2

正确答案：先给出一个最优值的上界．任取一个可行点例如(002)目标函数最优值的一个上界F_u=一6解下列松弛问题： min 2x₁+x₂—3x₃ s．t． x₁+x₂+2x₃≤5 2x₁+2x₂一x₃≤1 (P) x₁x₂x₃≥0．min 2x₁+x₂—3x₃s．t． x₁+x₂+2x₃≤5 2x₁+2x₂一x₃≤1 (P₁) x₃≤2x₁x₂x₃≥0且为整数和 min 2x₁+x₂—3x₃ s．t． x₁+x₂+2x₃≤5 2x₁+2x₂—x₃≤1(P₂) x₃≥3 x₁x₂x₃≥0且为整数． 用单纯形方法求解(P₁)的松弛问题： min 2x₁+x₂—3x₃ s．t． x₁+x₂+2x₃≤5 2x₁+2x₂一x₃≤1 (P₁) x₃≤2 x₁x₂x₃≥0得到松弛问题(p₁)的最优解(x₁x₂x₃)=(002)也是子问题(P₁)的最优解最优值f_min=一6=F_u子问题(P₁)不需要再分解． 再用单纯形方法解(P₂)的松弛问题(p₂)： min 2x₁+x₂—3x₃ s．t． x₁+x₂+2x₃≤5 2x₁+2x₂一x₃≤1(Pz) x₃≥3 x₁x₂x₃≥0． 用两阶段法求解(p₂)易知无可行解因此子问题(P₂)无可行解． 综上整数规划的最优解(x₁x₂x₃)=(002)最优值F*=一6．
先给出一个最优值的上界．任取一个可行点,例如(0,0,2),目标函数最优值的一个上界Fu=一6,解下列松弛问题：min2x1+x2—3x3s．t．x1+x2+2x3≤5,2x1+2x2一x3≤1,(P)x1,x2,x3≥0．min2x1+x2—3x3s．t．x1+x2+2x3≤5,2x1+2x2一x3≤1,(P1)x3≤2,x1,x2,x3≥0,且为整数,和min2x1+x2—3x3s．t．x1+x2+2x3≤5,2x1+2x2—x3≤1,(P2)x3≥3,x1,x2,x3≥0,且为整数．用单纯形方法求解(P1)的松弛问题：min2x1+x2—3x3s．t．x1+x2+2x3≤5,2x1+2x2一x3≤1,(P1)x3≤2,x1,x2,x3≥0,得到松弛问题(p1)的最优解(x1,x2,x3)=(0,0,2),也是子问题(P1)的最优解,最优值fmin=一6=Fu,子问题(P1)不需要再分解．再用单纯形方法解(P2)的松弛问题(p2)：min2x1+x2—3x3s．t．x1+x2+2x3≤5,2x1+2x2一x3≤1,(Pz)x3≥3,x1,x2,x3≥0．用两阶段法求解(p2),易知无可行解,因此子问题(P2)无可行解．综上,整数规划的最优解(x1,x2,x3)=(0,0,2),最优值F*=一6．