管理运筹学第5章-整数规划.ppt

管理运筹学第5章-整数规划.ppt

ID:48164345

大小:235.50 KB

页数:41页

时间:2020-01-16

管理运筹学第5章-整数规划.ppt_第1页
管理运筹学第5章-整数规划.ppt_第2页
管理运筹学第5章-整数规划.ppt_第3页
管理运筹学第5章-整数规划.ppt_第4页
管理运筹学第5章-整数规划.ppt_第5页
资源描述:

《管理运筹学第5章-整数规划.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第五章整数规划(IP)整数规划问题;整数规划的割平面算法;整数规划的分支定界算法0-1整数规划指派问题;引例[1]:一般最优生产计划问题某工厂拟用集装箱托运甲、乙两种货物,有关资料如下表。问:甲乙两种货物各托运多少箱,可以获得最大利润?4.1整数规划问题货物体积(米3/箱)重量(吨/箱)利润(万元/箱)甲5220乙4510装运限制24米313吨设X1,X2分别表示甲、乙两种货物的托运箱数,S.T.5X1+4X2<=242X1+5X2<=13X1,X2>=0MaxZ=20X1+10X2(LP)模型如下:S.T.5X1+4X2<=242X1+5X2<=13X1,X2>=0MaxZ=

2、20X1+10X2(IP)模型如下:X1,X2NX1,X2R引例[2]:约束条件可选择最优生产计划问题如果引例[1]中的集装箱运输有汽运和水运两种方式可供选择,其体积限制条件分别如下:5X1+4X2<=24;(汽运)7X1+5X2<=32;(水运)问:如何建立整数规划模型,可使工厂获得最大利润?设y=S.T.5X1+4X2<=24+(1-y)M;7X1+5X2<=32+yM;2X1+5X2<=13X1,X2>=0X1,X2N;y=0,1MaxZ=20X1+10X21,采用汽运方式;0,采用水运方式;则可建立(IP)模型:一、整数规划(IP)问题的性质(1)可行域:KLP/

3、KIP;(2)最优解:X*LP/X*IP。6230x1x24引例[1]——需要研究整数规划问题的专用算法!问:如何求解上述整数规划问题?(1)四舍五入法——可能不可行;(2)完全枚举法——可能不实际;二、整数规划问题的分类(1)纯整数规划(AIP);(2)混合整数规划(MIP);(3)0-1规划(BIP);——这里,Cj均为整数,j=1,2,…,n。4.2一般整数规划的分支定界算法一、算法思想设有最大化整数规划问题A,与他对应的线性规划问题B,若其最优解不符合A的整数条件,那么B的最优目标函数必是A的最优目标函数Z*的上界;而A的任意可行解的目标函数值将是Z*的下界。分支定界法

4、就是将B的可行域分成子区域(分支),逐步减小上界,增大下界,逐步寻找到整数最优解。4.2一般整数规划的分支定界算法例1:求解下述(AIP)maxz=40x1+90x2s.t.9x1+7x2〈=567x1+20x2〈=70xj>=0,整数,j=1,2(二)引例20x1x21(4.81,1.82)234561347K0’(K0’):X’0*=(4.81,1.82)TZ0*=35620x1x21(4.81,1.82)234561347(K1’)(K1’):X’1*=(4.00,2.10)TZ1*=349(K2’)(K2’):X’2*=(5.00,1.57)TZ2*=34120x1x2

5、1(4.81,1.82)234561347(K3’)(K3’):X’3*=(4.00,2.00)TZ3*=340(K2’)(K4’):X’4*=(1.42,3.00)TZ4*=327(K4’)20x1x21234561347(K3’)(K5’):X’5*=(5.44,1.00)TZ5*=308(K5’)(K6’):K’6=(K4’)(4.81,1.82)(K6’)=(二)分支定界法步骤----极大化问题将要求解的整数规划问题成为A,将与之对应的线性规划问题称为B(一)解问题B,会出现以下情况(1)B无可行解,则A无可行解----STOP(2)B有最优解,并符合A的整数条件-

6、----最优解(3)B有最优解,但不符合A的整数条件----迭代(二)分支定界法步骤----极大化问题(二)用观察法找A的一个整数可行解,求其目标函数值,记为下界Z一般找x=0,得到z=0,成为下界(二)分支定界法步骤----极大化问题(三)分支与定界1、分支B的最优解中,任选一个不符合整数条件的x,其值为b,设【b】为小于b的最大整数,增加两个约束条件x》【b】+1;x《【b】将两个约束加入到问题中,求后继问题B1,B2的解2、定界以每一个后继问题为一个分支,标明求解结果,与其它问题的解的结果中,找到目标函数值最大者为新的上界Z,从已符合整数条件的各分支中,找最大目标函数值为

7、新的下界z(二)分支定界法步骤----极大化问题(四)比较与剪支各分支中的最优目标函数中若有小于下界者,此支剪掉,不予考虑若大于下界者,且不符合整数条件的,重复第一步直到找到Z*=下界z,找到最优解(二)分支定界法步骤----极大化问题注意:1、下界z:必须是满足整数条件的解,得到的目标函数值2、上界Z:不需要满足整数条件3、当Z*=下界z,得到最优解三、例题与习题例1:求解下述(AIP):maxz=3x1+4x2s.t.2x1+5x2<=152x1-2x2<=5xj>=0,整数,j=1,2

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。