用分支定界法解下列问题：min 4x1＋7x2＋3x3 s．t． x1＋3x2＋x3≥5 3x1＋

正确答案：先给出最优值上界．任取可行点(x₁x₂x₃)=(112)整数规划最优值一个上界F_u=17．解松弛问题(p)： min 4x₁+7x₂+3x₃ s.t. x₁+3x₂+x₃≥5 (p) 3x₁+x₂+2x₃≥8 x₁x₂x₃≥0． 用单纯形方法求得松弛问题的最优解规划分解成两个子问题： min 4x₁+7x₂+3x₃ s．t． x₁+3x₂+x₃≥5 3x₁+x₂+2x₃≥8 (P₁) x₂ ≤0 x₁x₂x₃≥0且为整数和 min 4x₁+7x₂+3x₃ s．t． x₁+3x₂+x₃≥5 3x₁+x₂+2x₃≥8 (P₂) x₂ ≥1 x₁x₂x₃≥0且为整数． 求解子问题(P₁)的松弛问题： min 4x₁+7x₂+3x₃ s．t． x₁+3x₂+x₃≥5 3x₁+x₂+2x₃≥8 (P₁) x₂ ≤0 x₁x₂x₃≥0．用单纯形方法求得(p₁)的最优解(x₁x₂x₃)=(005)最优值f_min=15．=(005)^T是子问题(P₁)的可行解也是(P₁)的最优解整数规划最优值新的上界F_u=15． 再用单纯形方法解(P₂)的松弛问题： min 4x₁+7x₂+3x₃ s．t． x₁+3x₂+x₃≥5 3x₁+x₂+2x₃≥8 x₂ ≥1 x₁x₂x₃≥0．最优解(x₁x₂x₃)=最优值．由此可知(P₂)没有更好的整数解． 综上整数规划的最优解(x₁x₂x₃)=(005)最优值F*=15．
先给出最优值上界．任取可行点(x1,x2,x3)=(1,1,2),整数规划最优值一个上界Fu=17．解松弛问题(p)：min4x1+7x2+3x3s.t.x1+3x2+x3≥5,(p)3x1+x2+2x3≥8,x1,x2,x3≥0．用单纯形方法求得松弛问题的最优解规划分解成两个子问题：min4x1+7x2+3x3s．t．x1+3x2+x3≥5,3x1+x2+2x3≥8,(P1)x2≤0,x1,x2,x3≥0,且为整数,和min4x1+7x2+3x3s．t．x1+3x2+x3≥5,3x1+x2+2x3≥8,(P2)x2≥1,x1,x2,x3≥0,且为整数．求解子问题(P1)的松弛问题：min4x1+7x2+3x3s．t．x1+3x2+x3≥5,3x1+x2+2x3≥8,(P1)x2≤0,x1,x2,x3≥0．用单纯形方法求得(p1)的最优解(x1,x2,x3)=(0,0,5),最优值fmin=15．=(0,0,5)T是子问题(P1)的可行解,也是(P1)的最优解,整数规划最优值新的上界Fu=15．再用单纯形方法解(P2)的松弛问题：min4x1+7x2+3x3s．t．x1+3x2+x3≥5,3x1+x2+2x3≥8,x2≥1,x1,x2,x3≥0．最优解(x1,x2,x3)=,最优值．由此可知,(P2)没有更好的整数解．综上,整数规划的最优解(x1,x2,x3)=(0,0,5),最优值F*=15．