哈工大运筹学课件整数规划

《哈工大运筹学课件整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntegerProgramming整数规划AllIntegerProgramming全整数规划MixedProgramming混合整数规划第4章整数规划2006/081--第4章整数规划--4.1一般整数规划问题的特点及分枝定界法一、引例某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙22331214米39吨托运限制2006/082--第4章整数规划--建模：解：设托运甲货物x1箱，乙货物x2箱Maxz=3x1+2x2st.2x

2、1+3x2142x1+x29x10，x20，且为整数2006/083--第4章整数规划--24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=62006/084--第4章整数规划--24624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)2006/085--第4章整数规划--24624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)2006/086--第4章整数规划--分枝定界法:L0：z0=14.75x1=3.2

3、5，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥42006/087--第4章整数规划--LINDO软件及EXCEL求解：LINDO程序软件：同求解LP模型时的输入及编辑修改过程，在使用‘GO’命令求解之前，对整数变量给予说明。命令格式：GIN<变量名>。EXCEL求解：2006/088--第4章整数规划--4.20-1规划问题及模型一、0-1规划问题的概念在整数规划问题中，若变量取值为0或者1，则为0-

4、1规划问题。0-1变量通常用来表示逻辑性选择的决策。2006/089--第4章整数规划--二、0-1变量的应用例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制1、表示选择性决策2006/0810--第4章整数规划--2.表示选择性约束例2

5、：上述例题中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：∑djxjf采用自备柴油机发电：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正数2006/0811--第4章整数规划--3.表示条件性约束例3：若在开采时还需满足下述条件：（a）若开采8号，则必须同时开采6

6、号；（b）若开采5号，则不许开采3号；（c）2号和4号至少开采一个；（d）8号与7号必须同时开采；（e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。2006/0812--第4章整数规划--（a）当x8=1x6=1，x6≠0当x8=0x6=1，x6=0∴x8x6（b）当x5=1x3=0，x3≠1当x5=0x3=0，x3=1∴　x5+x31（c）x2+x41（d）x8=x7（e）x1+x4+x6+x922006/0813--第4章整数规划--4.两组条件满足其中一组若x14，则x21，否则(x14)，则x23。设yi=1

7、0第i组条件起作用第i组条件不起作用则i=1,2x14＋(1-y1)Mx21－(1-y1)MM——充分大正数x14－(1-y2)Mx23＋(1-y2)My1＋y2=1y1，y2=0或12006/0814--第4章整数规划--5.分段函数线性表示设有f(xj)=Kj+cjxj当xj>00当xj=0，将minf(xj)表示成线性函数。设yj=10当xj>0当xj=0Minf(xj)=kjyj+cjxjst.xjyjMxj0,yj=0或1M—非常大的正常数则f(xj)=kjyj+cjxjxjyjMyjxjMxj0,yj=0或1或为：200

8、6/0815--第4章整数规划--三、隐枚举法步骤：①化标准形(隐枚举法)：1)目标函数极小化2)约束条件化