运筹学第五章-整数规划.ppt
《运筹学第五章-整数规划.ppt》由会员分享,可在线阅读,更多相关《运筹学第五章-整数规划.ppt(64页珍藏版)》请在咨信网上搜索。
1、运筹学运筹学赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院第五章第五章 整数规划整数规划1.整数规划的数学模型整数规划的数学模型2.割平面法割平面法3.分支定界法分支定界法4.0-1整数规划整数规划5.指派问题指派问题6.应用应用2024/5/13 周一23求整数解的线性规划问题,不是用四舍五入法或去尾法对线性求整数解的线性规划问题,不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的,而要用整数规划的方法规划的非整数解加以处理都能解决的,而要用整数规划的方法加以解决。加以解决。在整数规划中在整数规划中:如果所有的变量都为非负整数,则称为如果所有的变量都为非负整数,则称为纯
2、整数规划问题纯整数规划问题;如果只有一部分变量为非负整数,则称之为如果只有一部分变量为非负整数,则称之为混合整数规划问题混合整数规划问题。如果所有的变量都为如果所有的变量都为0-10-1变量,则称之为变量,则称之为0-10-1规划规划。2024/5/13 周一34例例5.15.1 某公司拟用集装箱托运甲、乙两种货物,这两种货物每某公司拟用集装箱托运甲、乙两种货物,这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运甲种货物至多托运4 4件,问两种货物各托运多少件,可使获得利件,问两种货物各托运多少件,可使获得利润最大润
3、最大?货物货物每件体积每件体积(立方英尺)(立方英尺)每件重量每件重量(百千克)(百千克)每件利润每件利润(百元)(百元)甲甲乙乙19527344023托运限制托运限制1365140第一节第一节 整数规划的数学模型整数规划的数学模型2024/5/13 周一45解:解:设x1、x2分分别为甲、乙两种甲、乙两种货物托运的件数,建立模型物托运的件数,建立模型 Max z=2x1+3 x2 s.t.195 x1+273 x2 1365 4 x1+40 x2 140 x1 4 x1,x2 0 为整数。整数。如果去掉最后一个如果去掉最后一个约束,就是一个束,就是一个线性性规划划问题。2024/5/13 周
4、一56得到线性规划的最优解为得到线性规划的最优解为x x1 1=2.44,x=2.44,x2 2=3.26,=3.26,目标函数值为目标函数值为14.6614.66。由图表可看出,整数规划的最优解为由图表可看出,整数规划的最优解为x x1 1=4,x=4,x2 2=2,=2,目标函数值目标函数值为为1414。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=62024/5/13 周一67性质:性质:任何求任何求最大最大目标函数值的纯整数规划或混合整数规目标函数值的纯整数规划或混合整数规划的最大目标函数值划的最大目标函数值小于或等于小于或等于相应的线性规划的相应
5、的线性规划的最大目标函数值;最大目标函数值;任何求任何求最小最小目标函数值的纯整数规划或混合整数规目标函数值的纯整数规划或混合整数规划的最小目标函数值划的最小目标函数值大于或等于大于或等于相应的线性规划的相应的线性规划的最小目标函数值。最小目标函数值。2024/5/13 周一713/4,5/2松弛问题第一次切割4,1第二次切割x1+x25第二节第二节 割平面法割平面法2024/5/13 周一8设纯整数规划设纯整数规划伴随伴随LP的最优解的最优解若若 全为整数,则为全为整数,则为IP的最优解。否则,的最优解。否则,若不全为整数,设第若不全为整数,设第r r行基变量行基变量 非整。对应方程为非整。
6、对应方程为2024/5/13 周一9将将 分离成一个整数与一个非负真分数之和:分离成一个整数与一个非负真分数之和:则有则有等式两边都为整数并且有等式两边都为整数并且有2024/5/13 周一10加入松弛变量加入松弛变量此式称为以此式称为以r行为源行(来源行)的割平面,或分数切割式,行为源行(来源行)的割平面,或分数切割式,或或R.E.Gomory(高莫雷高莫雷)约束方程约束方程。将将Gomory约束加入到松弛问题约束加入到松弛问题(伴随伴随LP)的最优表中,用的最优表中,用对偶单纯形法对偶单纯形法计算,若最优解中还有非整数解,再继续切割,计算,若最优解中还有非整数解,再继续切割,直到全部为整数
7、解。直到全部为整数解。则则2024/5/13 周一11割平面法割平面法,即通过添加约束条件,逐步切割可行区域的边,即通过添加约束条件,逐步切割可行区域的边角余料,让其整数解逐步的露到边界或顶点上来,只要整角余料,让其整数解逐步的露到边界或顶点上来,只要整数解能曝露到顶点上来,则就可以利用单纯形法求出来。数解能曝露到顶点上来,则就可以利用单纯形法求出来。关键关键是通过添加什么样的约束条件,既能让整数解往边界是通过添加什么样的约束条件,既能让整数解往边界露,同时又不要切去整数解,这个条件就是露,同时又不要切去整数解,这个条件就是GomoryGomory约束条约束条件。件。GomoryGomory约
8、束只是割去线性规划可行域的一部分,保留了全约束只是割去线性规划可行域的一部分,保留了全部整数解。部整数解。2024/5/13 周一12 例例5-55-52024/5/13 周一13cj3-1000XBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/700-5/70-3/7选择较大小数的行构造割平面选择较大小数的行构造割平面2024/5/13 周一14运筹学-线性规划-线性规划-线性规划cj3-10000XBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700 x431/70
9、0-3/7122/700 x6-6/700-1/70-2/7100-5/70-3/702024/5/13 周一15运筹学-线性规划-线性规划-线性规划3x11100001-1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4000-1/40-17/4cj3-10000XBbx1x2x3x4x5x62024/5/13 周一16运筹学-线性规划-线性规划-线性规划 分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法,它既是求解整数规划的一种常用的有效的方法,它既能解决纯整数规划的问题,又能解决混合整数规划的问题。能解决纯整数规划的问
10、题,又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。成的。1.1.先先求解整数规划的线性规划求解整数规划的线性规划问题问题(伴随伴随LP)LP)。2.2.如果如果其最优解不符合整数条件,则求出整数规划的其最优解不符合整数条件,则求出整数规划的上上下界。下界。3.3.增加增加约束条件的办法,把相应的线性规划的可行域分成子区约束条件的办法,把相应的线性规划的可行域分成子区域(称为域(称为分枝分枝)4.4.再再求解这些子区域上的线性规划求解这些子区域上的线性规划问题。问题。5.5.不断不断缩小缩小整数规划上整数
11、规划上下界的距离,最后得整数规划的最优解下界的距离,最后得整数规划的最优解。第三节分枝定界法第三节分枝定界法2024/5/13 周一1718 用用分枝定界法分枝定界法求解目标函数值最大的整数规划的求解目标函数值最大的整数规划的步骤步骤,我们将,我们将求解的整数规划求解的整数规划问题称为问题称为A A,将,将与其相对应的线性规划问题称为与其相对应的线性规划问题称为B B:第一步第一步:求解问题:求解问题B B,可得以下情况之一:,可得以下情况之一:1.B1.B没有可行解,则没有可行解,则A A也没有可行解,求解过程停止。也没有可行解,求解过程停止。2.B2.B有最优解,且符合问题有最优解,且符合
12、问题A A的整数条件,则的整数条件,则B B的最优解即为的最优解即为A A的最优解,的最优解,求解过程停止。求解过程停止。3.B3.B有最优解,但不符合有最优解,但不符合A A的整数条件,记其目标函数值为的整数条件,记其目标函数值为z z1 1。第二步第二步:确定:确定A A的最优目标函数值的最优目标函数值z*z*的上下界,其上界即为的上下界,其上界即为 ,再用观察法再用观察法找到找到A A的一个整数可行解,求其目标函数值作为的一个整数可行解,求其目标函数值作为z*z*的下界,记为的下界,记为z z。第三步第三步:判断:判断 是否等于是否等于z z 。若相等,则整数规划最优解即为其目标函。若相
13、等,则整数规划最优解即为其目标函数值等于数值等于z z的的A A的那个整数可行解;否则进行第四步。的那个整数可行解;否则进行第四步。2024/5/13 周一18 第四步第四步:在:在B的最优解中的最优解中任选一个(或最远离整数要求的变量)任选一个(或最远离整数要求的变量),不妨设,不妨设此变量为此变量为xj,以,以bj表示小于表示小于bj的最大整数,构造以下两个约束条件,并加的最大整数,构造以下两个约束条件,并加入问题入问题B,得到,得到B的两个分枝的两个分枝B1和和B2。xj bj和和xj bj+1 第五步第五步:求解:求解B1和和B2。修改。修改A问题的最优目标函数值问题的最优目标函数值z
14、*的上下界,的上下界,和和z。第六步第六步:比较和剪枝。各分枝的:比较和剪枝。各分枝的最优目标函数值中若有小于最优目标函数值中若有小于z者,则剪者,则剪掉这枝(用打掉这枝(用打表示),即以后不再考虑了。表示),即以后不再考虑了。若大于若大于 ,则不符合整数条,则不符合整数条件,则重复第三步至第六步,件,则重复第三步至第六步,直至直至 =z,求出最优解为止。,求出最优解为止。对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。2024/5/13 周一19例例5-65-62024/5/13 周一20运筹学-线性规划-线性规划-线性
15、规划例例5.15.1Max 2Max 2x x1 1+3+3x x2 2s.t.195s.t.195x x1 1+273+273x x2 213651365 4 4x x1 1+40+40 x x2 2140140 x x1 1 4 4 x x1 1,x,x2 2 0 0且且x x1 1,x,x2 2为整数整数2024/5/13 周一21运筹学-线性规划-线性规划-线性规划线性规划线性规划1Z1=14.66X1=2.44X2=3.26z z=13,=13,=14.66 线性规划线性规划2Z2=13.90X1=2X2=3.30线性规划线性规划3Z3=14.58X1=3X2=2.86线性规划线性规
16、划4Z4=14.00X1=4X2=2线性规划线性规划5无可行解无可行解X12X13X22X23z z=13,=13,=14.58 z z=14,=14,=142024/5/13 周一22 0-10-1规划的分支定界法规划的分支定界法 0-10-1规划的规划的适用背景适用背景双态变量的归一化(变量)双态变量的归一化(变量)不相容约束的归一化(约束条件)不相容约束的归一化(约束条件)分段线性函数的归一化(目标函数)分段线性函数的归一化(目标函数)第四节第四节0-10-1规划规划2024/5/13 周一23双态变量的归一化双态变量的归一化24(1 1)多个不全相容约束的归一化)多个不全相容约束的归一
17、化不全相容约束的归一化不全相容约束的归一化252024/5/13 周一26(2 2)约束常数项多个互斥取值的归一化)约束常数项多个互斥取值的归一化27282024/5/13 周一29(3 3)多组约束的归一化)多组约束的归一化3031(1 1)固定费用的问题)固定费用的问题例例5.2 5.2 高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如表所示。属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如表所示。不考虑固定费用,每种容器售出一只所得的利润分别为不考虑固定
18、费用,每种容器售出一只所得的利润分别为 4 4万元、万元、5 5万元、万元、6 6万元,可使用的金属板有万元,可使用的金属板有500500吨,劳动力有吨,劳动力有300300人人/月,机器有月,机器有100100台台/月,此月,此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是l00l00万元,中号为万元,中号为 150 150 万元,大号为万元,大号为200200万元。现在要制定一个生产计划,使万元。现在要制定一个生产计划,使获得的利润为最大。获得的利润为最大。分段线性函数的归一化(目标函数)分段线性函数的归一化(目
19、标函数)2024/5/13 周一3132解:解:这是一个整数是一个整数规划的划的问题。设x1,x2,x3 分分别为小号容器、中号容器和大号容器的生小号容器、中号容器和大号容器的生产数量。各种容器数量。各种容器的固定的固定费用只有在生用只有在生产该种容器种容器时才投入,才投入,为了了说明固定明固定费用的用的这种性种性质,设 yi=1(当生当生产第第 i种容器种容器,即即 xi 0 时)或或0(当不生当不生产第第 i种容器即种容器即 xi=0 时)。)。引入引入约束束 xi M yi ,i=1,2,3,M充分大,充分大,以保以保证yi=0 xi=0 这样我我们可建立如下的数学模型:可建立如下的数学
20、模型:Max z=4Max z=4x x1 1+5+5x x2 2+6+6x x3 3-100y-100y1 1-150y-150y2 2-200y-200y3 3s.t.2s.t.2x x1 1+4+4x x2 2+8+8x x3 3 500 500 2 2x x1 1+3+3x x2 2+4+4x x3 3 300 300 x x1 1+2+2x x2 2+3+3x x3 3 100 100 xi M yi ,i=1,2,3,M充分大充分大 x xj j 0 0 y yj j 为0-10-1变量量,i i=1,2,3=1,2,32024/5/13 周一32(2 2)变动费用的问题)变动费用
21、的问题例例5.3 330-1 0-1 规划的解法规划的解法隐枚举法隐枚举法:2024/5/13 周一34求解思路求解思路:2024/5/13 周一352024/5/13 周一3637 有有 n n 项不同的任不同的任务,恰好,恰好 n n 个人可分个人可分别承担承担这些任些任务,但由于每,但由于每人特人特长不同,完成各不同,完成各项任任务的效率等情况也不同。的效率等情况也不同。现假假设必必须指派每个指派每个人去完成一人去完成一项任任务,怎,怎样把把 n n 项任任务指派指派给 n n 个人,使得完成个人,使得完成 n n 项任任务的的总的效率最高,的效率最高,这就是就是指派指派问题。例例5 5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第五 整数 规划 胡运权
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。