資源描述：
《分支定界法例題.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、用分支定界法求解。先去掉整數約束，記為LPX1=18/11,x2=40/11Z(0)=-218/11LP1LP2x1x2(1)(2)先求松弛問題的解。X1=18/11,x2=40/11Z(0)=-218/11=-19.8x1x2(1)(2)LP1LP2LP1的解為B點，x1=1,x2=3,z(1)=-16本支最優(yōu)解已經找到，此分支停止計算。z(1)作為新的上界。-19.8<=z*<=-16Bx1x2(1)(2)LP1LP2BCLP2的最優(yōu)解是C點，x1=2,x2=10/3,z(2)=-56/3=-18.7<-16所以還可以在這個分支繼續(xù)找更小的整數解。LP21LP22LP22無可行解x1
2、x2(1)(2)LP1LP21BCDLP21在D點取得最優(yōu)解。x1=2.4,x2=3,z(3)=-87/5=-17.4還可對x1繼續(xù)分支。LP211LP212x1x2(1)(2)LP212BCDELP211FGLP212的最優(yōu)解在G點，x1=3,x2=2.5,z(5)=-15.5LP211的最優(yōu)解在E點，x1=2,x2=3,z(6)=-17此為本題最優(yōu)解。LP，x1=18/11,x2=40/11,z(0)=-19.8LP1,x1=1,x2=3,z(1)=-16LP2,x1=2,x2=10/3,z(2)=-18.5LP21,x1=2.4,x2=3,z(3)=-17.4LP22,無可行解LP
3、211,x1=2,x2=3,z(6)=-17LP212,x1=3,x2=2.5,z(5)=-15.5X1<=1X1>=2X2<=3X2>=4X1<=2X1>=3
