第4章 整数规划（IP）ppt课件.ppt

《第4章 整数规划（IP）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章整数规划（IP）整数规划问题；整数规划模型；整数规划的割平面算法；整数规划的分支定界算法；例题与习题；引例[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+5X

2、2<=13X1,X2>=0MaxZ=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,采用水运方式；则可建

3、立（IP）模型：一、整数规划（IP）问题的性质（1）可行域：KLP/KIP；（2）最优解：X*LP/X*IP。6230x1x24引例[1]——需要研究整数规划问题的专用算法！问：如何求解上述整数规划问题？（1）四舍五入法——可能不可行；（2）完全枚举法——可能不实际；——对于特殊的整数规划建模，需要引进0-1变量（逻辑变量）和大M参数等！二、整数规划问题的模型建立5X1+4X2<=24+（1-y)M；7X1+5X2<=32+yM；三、整数规划问题的分类（一）决策变量的分类（二）整数规划问题的分类（1）连续变量（R——实数）；（2）离散变量（N——

4、整数）；（3）0-1变量（1/0——逻辑变量）；（1）纯整数规划（AIP）；（2）混合整数规划（MIP）；（3）0-1规划（BIP）；——这里，Cj均为整数，j=1,2,…,n。4.2整数规划建模举例例[1]：固定费用问题某工厂明年准备在甲、乙、丙三种产品中选址两种产品投产，他们都需要经过A，B，C三道工序加工。有关参数如下表，且甲、乙、丙投产时，无论产量多大，都需要固定费用，分别为1500，2000，1800。问：如何安排生产计划，可以使工厂获得最大利润？加工时间甲乙丙生产能力（小时/件）（小时）工序A3211800工序B1122000工序C1

5、311600单位产品成本508060单位产品价格200300250固定费用1500，2000，1800某公司每年可用于投资的资金为100万元,有10个投资项目可供选择，项目j每年的利润为Cj，需要资金aj，问（1）如何选择投资项目，可使年总利润最大？（2）若上述项目相互排斥，至多选择6个项目，如何建立整数规划模型？（3）如果项目k优先于项目g，即只有选择项目k的情况下才能选择项目g，如何建立整数规划模型？例[2]：投资决策问题Cj6108115876912aj15201220111617101720例[3]：最优分配问题P132P133例[4]：

6、工厂选址问题4.3纯整数规划的割平面算法一、算法思想（AIP）松弛问题（LP）X*（LP）X*（LP）满足整数约束？X*（LP）=X*（IP）增加约束条件（割平面）：。至少切割掉X*（LP）；。切割区域不包含整数解。（一）框图关键：如何增加割平面！例[1]：Maxz=x1+x2s.t.-x1+x2<=13x1+x2<=4x1,x2》=0，整数（二）示例10x1x21割平面X1+2x2<=3（3/4，7/4）二、Gomory割平面及其相关概念（三）Gomory割平面示例；（一）相关概念及示例；（二）Gomory割平面原理；例[1]：Maxz=x1+

7、x2s.t.-x1+x2<=13x1+x2<=4x1,x2》=0，整数松弛问题：Maxz=x1+x2s.t.-x1+x2+x3=1-3x1+x2+x4=4x1,x2,x3,x4》=0XBX1X2X3X4b’X110–1/41/43/4X2013/41/47/4r00–1/2–1/2–5/2T*(B)割平面:-3/4X3-1/4x4<=-3/4X2<=1三、纯整数规划的Gomory割平面算法（一）算法基本步骤；（1）利用单纯形法求解（AIP）的松弛问题（LP），得基本最优解X*（LP）；（2）X*（LP）的变量全部为整数吗？是：X*（LP）=X*（

8、IP）否：取=max{bi’

9、1<=i>=m},增加如下Gomory割，得到新的松弛问题LP）;-<=-