• / 73
  • 下载费用:10 金币  

4.整数规划.ppt

关 键 词:
4.整数规划.ppt
资源描述:
1,第五章 整数规划,整数规划模型及其与线性规划的区别 整数规划的求解——分支定界法、割平面法 0-1整数规划模型与求解 指派问题模型与求解 整数规划的应用——建模,2,一、整数规划的一般形式,例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表:,问两种货物各托运多少箱,可使获得的利润为最大?,第一节 整数规划问题的提出,3,1.整数规划的一般形式,解:设托运甲、乙两种货物x1,x2箱,用数学式可表示为:,xj部分或全部为整数,4,(1)求解方法方面,2.IP问题与LP问题的区别,在例1中, IP问题,实际上,此IP问题的最优解为:,不考虑整数约束的最优解为:,(1),X(1)=(5, 0)T不是(1)的可行解,X(2)=(4, 0)T虽是可行解,但不是最优解,5,例2 做图分析例1的最优解(直观),IP 问题的可行域不是凸集,(2)理论方面,,,x1,x2,4,8,4,,0,,,,,,,,,1,2,3,5,6,7,,,,,3,1,2,,,5x1+4x2=24,2x1+5x2=13,,(4.8, 0)T Z=96,(4, 1)T Z=90,,,,6,二、整数规划的分类,1.纯整数规划问题(Pure Integer Programming),2.全整数规划问题(All Integer Programming),在IP问题(1)中,还要求 aij , bi 全为整数。,4.0-1规划问题,在IP问题(1)中, 要求 xj =0或1.,3.混合整数规划问题(Mixed Integer Programming),在IP问题(1)中,只要求部分 xj 为整数.,7,适用范围:全整数规划问题、纯整数规划问题、混合整数规划问题,第二节 分支定界法 (Branch and Bound Method),指派问题:n!,仅检查可行的整数组合的一部分,隐枚举法,穷举变量的所有可行的整数组合,×,IP:A,LP:B,≤,≤,8,一、几何解释,例1 求解整数规划问题,第二节 分支定界法 (Branch and Bound Method),(0,0) Z*≥0,9,解:图解法。,,,x1,x2,0,,,,,,,,,,,1,2,3,4,5,6,7,8,9,10,,,,,,,,,1,2,3,4,5,6,7,8,,9x1+7x2=56,,7x1+20x2=70,B,C,,,,,问题B1 Z1=349 x1=4.00 x2=2.10,问题B2 Z2=341 x1=5.00 x2=1.57,x1=[x1(0)]=4,x1=[x1(0)]+1=5,,,,,0≤ Z*≤356,0≤ Z*≤349,10,解:图解法。,问题B1 Z1=349 x1=4.00 x2=2.10,问题B2 Z2=341 x1=5.00 x2=1.57,x2=[x2(0)]=2,,,x1,x2,0,,,,,,,,,,,1,2,3,4,5,6,7,8,9,10,,,,,,,,,1,2,3,4,5,6,7,8,,9x1+7x2=56,,7x1+20x2=70,B,C,,,,,,,0≤ Z*≤349,,,,x2=[x2(0)]+1=3,,,问题B3 (4.00, 2.00) 340,问题B4 (1.42, 3.00) 327,340≤ Z*≤341,B3,B4,11,解:图解法。,问题B2 Z2=341 x1=5.00 x2=1.57,x2=[x2(0)]=1,,,x1,x2,0,,,,,,,,,,,1,2,3,4,5,6,7,8,9,10,,,,,,,,,1,2,3,4,5,6,7,8,,9x1+7x2=56,,7x1+20x2=70,C,,,,,,,,x2=[x2(0)]+1=2,340≤ Z*≤341,问题B6 无可行解,问题B5 (5.44, 1.00) 308,,,12,二、分支规则,,在B的最优解中任选一个不符合整数条件的变量 xj ,其值为 bj ,以[bj ]表示小于bj的最大整数,构造两个约束条件:xj ≤ [bj ], xj ≥ [bj ]+1,解问题B,有三种可能: (1)无可行解; (2)有最优解,且符合整数条件; (3)有最优解,但不符合整数条件。,设与整数规划问题A相应的线性规划问题称作问题B。,将这两个约束条件分别加入问题B,求两个后继问题B1和B2(仍不考虑整数条件)。,从可行域中移除的部分包含整数解吗?,[bj ]xj[bj ]+1,13,二、分支规则,,,,,情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分支定界法 情况 7 情况 6 问题B1的整数解作为新的上界被保留,用于以后与问题B2的后续分支所得到的解进行比较,,,,,,,14,,满足要求?,,结 束,分 支,,,,,Y,N,三、运算步骤,解松弛问题,根
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:4.整数规划.ppt
链接地址:https://www.weizhuannet.com/p-9797114.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开