欢迎来到天天文库
浏览记录
ID：57308189
大小：83.50 KB
页数：10页
时间：2020-08-11
《分支定界法例题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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本支最优解已经找到，此分支停止计算。z(1)作为新的上界。-19.8<=z*<=-16Bx1x2(1)(2)LP1LP2BCLP2的最优解是C点，x1=2,x2=10/3,z(2)=-56/3=-18.7<-16所以还可以在这个分支继续找更小的整数解。LP21LP22LP22无可行解x1
2、x2(1)(2)LP1LP21BCDLP21在D点取得最优解。x1=2.4,x2=3,z(3)=-87/5=-17.4还可对x1继续分支。LP211LP212x1x2(1)(2)LP212BCDELP211FGLP212的最优解在G点，x1=3,x2=2.5,z(5)=-15.5LP211的最优解在E点，x1=2,x2=3,z(6)=-17此为本题最优解。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
此文档下载收益归作者所有
