整数规划和混合整数规划

《整数规划和混合整数规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、整数规划与混合整数规划2015/10/22应用优化技术1整数规划与混合整数规划混合整数规划问题分支定界法0-1规划的隐数法割平面法混合整数非线性规划2015/10/22应用优化技术2混合整数规划问题f,h,g线性LPminf(,)xyxy,Y空st..hxy(,)0一大类gxy(,)0优化命题f,h,g非线性NLPnxXRf,h,g线性MILPyY整数Y非空f,h,g非线性MINLP2015/10/22应用优化技术3混合整数线性规划问题TTmincxdyxy,LPst..AxBybnxx0,XR

2、0-1规划y0,1LN1yyz2z4z2z123NULlogyyN1INTlog22015/10/22应用优化技术4实例一0-1背包问题容积v物品j：价值w，体积vjj设1j放入xj0j不放nmaxwxjjj1nst..vxjjvj1x01,或j1,2,nj2015/10/22应用优化技术5实例二工厂选址问题n个城市，需要某种物资数量为d，d，…，d12n现计划建造m座工厂假设在城市j建厂，规模为S，投资为F，从城市i到j的单位运jj价

3、为Cij问m个工厂应设在何处，使满足需要且成本最低1若有一个工厂建在城市iminCxijijFyiiyij,ii0i不建厂nst..xijSyiii1,,nj1x为i运往j的物资总量nijxdj1,,nijji1nymii1y01或2015/10/22应用优化技术i6x0ij,1,2,,nij实例三调和问题：利用一些成分mincxjjdvykkk调和为一个产品jklux——连续用量的j成分的量st..wxjvykkwjjkyk——1或0表示离散用量的Alu

4、axavyAiijjikkki成分用或不用；v表示用量kjkcj，dk——成分的成本0xjjuforalljaij——成分j中i组分分量yk(0,1)forallk如何调和使得产品质量合格uj成分上界j且成本最低？luww,重量上下界luA，Ai分析上下界ii2015/10/22应用优化技术7实例四x(0,1)TSP问题对任意Ai、Aj，引入ij若紧跟着A后的是A，取从A出发，经过A、ij01x1x0A、…、A再回到Aij，否则ij2n0nnA到A的距离：dmindxijijijijij

5、00n总行程最短st..xij1i0,,n前后各一j0个城市AAA,,,,AA,0i1i2in0nxij1j0,,ni0xij1任意非空真子集S0,1,,njSjSnn形成回路xnij1ij00x01或ij，0,,nij2015/10/22应用优化技术8实例五加工问题m台机床，n种零件加工时间aa12,,,an如何分配，使各机床总加工任务相等，或尽可能均衡minx0n1ai在上加工jst..axxi1,,mxjij0ij0ai不在上加工j1j

6、mxij=1j1,,ni1x(0,1)i1,,mj，1,,nij2015/10/22应用优化技术9整数规划解法概述枚举可行方案的数目常常是有限求解实际问题不现实先放弃变量的整数性要求，然后求整数解只有在变量取值很大时才有成功的可能性变量取值较小时，如0-1变量，往往不会成功2015/10/22应用优化技术10例整点凸包OEFGHIJx2maxx3x13x012st..2x9x4012D11xx882I12Jxx,0,xx取整HB1212GFOEAxx58,x2,x41012x58

7、.8,x9.2,x2.4012割平面法先不考虑整数限制求线性规划问题的解然后增加新的约束，这些约束将整数限制松弛后所扩大的可行域逐步割掉，但不割掉任何可行的整数解最后使所得到的线性规划问题的最优解就是原问题的最优整数解2015/10/22应用优化技术11分支定界按树形方式，分解为5个定义域互不相交的整数规划子问题x2Px3x211x6x7P111Px3x2x31222P2P4PPPP2345OAx1放弃整数性要求后，三子问题的最优解Px:(2,4),58810Px:(98/11,2),524

8、011Px:(6,3),57202015/10/22应用优化技术12整数规划与混合整数规划混合整数规划问题分支定界法0-1规划的隐数法割平面法混合整数非线性规划2015/10/22应用优化技术13分支定界法分解松弛探测2015/10/22应用优化技术14分解问题(P)的