运筹学整数规划教学课件PPT.ppt_第1页
运筹学整数规划教学课件PPT.ppt_第2页
运筹学整数规划教学课件PPT.ppt_第3页
运筹学整数规划教学课件PPT.ppt_第4页
运筹学整数规划教学课件PPT.ppt_第5页
已阅读5页,还剩51页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1,运筹学 第三章 整数规划 integer programming,2,本章内容重点,整数规划数学模型 整数规划的求解 01规划的求解,3,很多实际规划问题都属于整数规划问题,变量是人数、机器设备台数或产品件数等都要求是整数 对某一个项目要不要投资、某项任务要不要选择等等的决策问题,可选用一个逻辑变量 x,当x=1表示投资/选择,x=0表示不投资/不选择;逻辑变量也是只允许取整数值的一类变量。,4,某厂拟用集装箱托运甲乙两种货物,每箱的体积重量可获得的利润及托运所受的限制如表1所示。问每次两种货物各托运多少箱,可使得获得的利润最大?,5,西游记里面沙僧所背的行李里面到底有些什么东西呢?,假如我们已经知道这些物品对唐僧的价值。沙僧可携带最大重量为50公斤,请问应该选择放入哪些物品,使得沙僧所背的价值最大?,6,例一登山队员做登山准备,他需要携带的物品有:食品,氧气,冰镐,绳索,帐篷,照相机和通讯设备,每种物品的重要性系数和重量如下:假定登山队员可携带最大重量为25公斤。,7,整数规划(ip)是一类要求部分或全部变量取整数值的数学规划,根据变量的取值性质,可以分为: 纯整数规划 pure integer programming 混合整数规划 mixed integer programming 0-1 整数规划 0-1 integer programming,8,纯整数规划模型,9,混合整数规划模型,10,0-1整数规划模型,整数规划最优解是否能通过对最优解取整而获得?,11,12,整数规划最优解不能按照实数最优解简单取整而获得。,maximize z = 3x + 4y subject to 5x + 8y 24 x, y 0, 整数 如何求最优解呢?,13,可行域,0 1 2 3 4 5,0 1 2 3 4 5,不考虑整数约束情况下, 求解线性规划问题,得到 x=24/5, y=0, z =14 2/5. 四舍五入, 得到 x=5, y=0, 不可行! 去掉尾数, 得到 x=4, y=0, z =12. 而最优解为 x=3, y=1, z =13,14,整数规划与松弛线性规划的关系,整数规划,松弛的线性规划,可行解是松弛问题的可行解。也即整数规划的可行域包含在它的线性规划松弛的可行域中,最优值小于等于松弛问题的最优值。也即松弛线性规划问题的最优解是原问题的上界,15,+,+,+,+,+,(4.8,0),例1,16,注释,最优解不一定在顶点上达到 最优解不一定是松弛问题最优解的邻近整数解 整数可行解远多余于顶点,枚举法不可取 松弛线性规划不可行,则原问题也不可行,17,整数规划求解方法 1 割平面法主要求解纯整数线性规划 2 分枝定界法可求纯或混合整数线性规划 3 隐枚举法求解“01”整数规划: 4匈牙利法解决指派问题(“01”规划特殊情形)。,18,例 求下列问题: max z=3x1+13x2 s.t.2x1+9x2 40 11x1-8x2 82 x1,x2 0,且取整数值,19,o 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,i(2,4),b(9.2,2.4),a,d,可行域oabd内整数点,放弃整数要求后,最优解b(9.2,2.4) z0=58.8,而原整数规划最优解i(2,4) z0=58,实际上b附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,20,o 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,i(2,4),b(9.2,2.4),a,d,假如能求出可行域的“整点凸包”(包含所有整点的最小多边形oefghij),则可在此凸包上求线性规划的解,即为原问题的解。但求“整点凸包”十分困难。,e,f,g,h,i,j,21,o 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,i(2,4),b(9.2,2.4),a,d,假如把可行域分解成五个互不相交的子问题p1 p2 p3 p4 p5之和, p3 p5的定义域都是空集,而放弃整数要求后p1最优解i(2,4),z1=58 p2最优解(6,3),z2=57 p4最优解(98/11,2),z4=52(8/11),p1,p2,p4,22,x1 2,x1 6,x2 3,x2 2,x1 3,x1 7,x2 4,x2 3,p1,p5,p4,p2,p3,p,z1=58,z2=57,z4=52 (8/11),23,以上描述了目前解整数规划问题的两种基本途径:割平面法和分支定界法,24,纯整数规划的求解: 割平面法 割平面法是通过生成一系列的平面割掉非整数部分来得到最优整数解的方法。,25,用例子说明割平面法基本思想。 例 求下列问题: max z=2x1+ 3x2 s.t.2x1+4x2 25 x1 8 2x2 10 x1,x2 0,且取整数值,26,化成标准问题 max z=2x1+ 3x2 s.t.2x1+4x2 + x3 =25 x1 + x4 =8 2x2 + x5 =10 xj 0,且取整数值,27,松驰问题(p) max z=2x1+ 3x2 s.t.2x1+4x2 + x3 =25 x1 + x4 =8 2x2 + x5 =10 xj 0,28,松驰问题(p) 用单纯形法求解得到最优解: b(8,9/4) z=22(3/4) 但不是原问题(ip)的解,(ip)可行域是oabde内的全部方格点组成。,29,o 1 2 3 4 5 6 7 a8 9 10 11 12,10 9 8 7 6 5 4 3 2 1,x1,x2,30,引进割平面法 l1: x1+ x2 =10 割去非整数部分fbg l2: x1+2x2 =12 割去非整数部分hdgf,31,o 1 2 3 4 5 6 7 a8 9 10 11 12,10 9 8 7 6 5 4 3 2 1,x1,x2,l1: x1+ x2 =10 割去非整数部分fbg,32,o 1 2 3 4 5 6 7 a8 9 10 11 12,10 9 8 7 6 5 4 3 2 1,x1,x2,l2: x1+2x2 =12 割去非整数部分hdgf,33,o 1 2 3 4 5 6 7 a8 9 10 11 12,10 9 8 7 6 5 4 3 2 1,x1,x2,形成新的凸可行域oaghe(整点凸包),它的极点g(方格点)是原规划(ip)的最优解(8,2) z=22。,34,约束条件: l1: x1+ x2 10 l2: x1+2x2 12 称为割平面。 问题是如何寻找割平面?,35,整数规划的求解:分枝定界法 分枝定界法是求整数规划的一种常用的有效的方法,既能解决纯整数规划的问题,也能解决混合整数规划的问题。,36,1 初始:求解松弛问题 求线性规划松弛的最优解 x* = ( x1*, x2*, , xn* ), 如果它是整数,则它就是整数规划的最优解。如果不可行,则整数规划无可行解。 2 分支: 否则,从不满足整数条件的基变量中取一个xj*,分别增加约束 xj xj* 和 xj xj* +1, 生成两个子问题,取代原整数规划,分支定界法的基本思想,37,x,y,0,1,2,3,4,0,1,2,3,3 定界: 把各分枝松弛问题的最优目标函数值作为原整数规划的上(下)界,用它来判断分枝是保留还是剪枝。 分支xj xj*中若相应的松弛问题最优解为zr,那么原整数规划的解不会优于zr,所以zr可以作为该分支的上界,分支定界法的基本思想,38,x,y,0,1,2,3,4,0,1,2,3,4 剪枝: 把那些子问题的最优值与界值比较,凡不优或不能更优的分枝全剪掉,直到每个分枝都查清为止。 分支xj xj*中已经得到符合整数要求的解,最优值为zr,那么另外一个分支中松弛问题的最优值不超过z0,那么就可以剪掉那一支,分支定界法的基本思想,39,例 用分枝定界法求解: max z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1, x2 0 整数 用单纯形法可解得相应的松驰问题的最优解 (6/5,21/10),z=111/10为各分枝的上界。,40,0 1 2 3 4,4 3 2 1,x1,x2,分枝:x1 1,x1 2,p1,p2,41,两个子问题: (p1)max z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , x1 1 ,整数 用单纯形法可解得相应的(p1)的最优解(1,9/4) z=10(3/4),42,(p2)max z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , x1 2 ,整数 用单纯形法可解得相应的(p2)的最优解(2,1/2) z=9(1/2),43,0 1 2 3 4,4 3 2 1,x1,x2,再对(p1)分枝:x1 1 (p3) x2 2 (p4) x2 3,p1,p2,p3,p4,44,(p1)两个子问题: (p3)max z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 2整数 用单纯形法可解得相应的(p3)的最优解(1,2) z=10,45,(p1)两个子问题: (p4)max z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 3整数 用单纯形法可解得相应的(p4)的最优解(0,3) z=9,46,x1 2,x2 2,x1 1,x2 3,p1:(1,9/4) z=10(3/4),p4: (0,3) z=9,p2:(2,1/2) z=9(1/2),p3: (1,2) z=10,p:(6/5,21/10) z=111/10,原问题的最优解(1,2) z=10,47,例 用分枝定界法求解: min z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解(10/3,4/3)z=26/3为各分枝的下界。,48,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,49,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,选 x1进行分枝: (p1) x1 3 (p2) x1 4 为空集,p1,50,(p1) min z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 3 整数 用单纯形法可解得(p1)的最优解(3,3/2)z=9,51,(p2) min z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 4 整数 无可行解。,52,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,对(p1) x1 3 选 x2进行分枝: (p3) x2 1无可行解 (p4) x2 2,p4,53,(p3) min z= x1+4x2 s.t. 2x1+ x2 8 x1

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论