运筹学Ch3整数线性规划.ppt

《运筹学Ch3整数线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学Ch3整数线性规划.ppt（33页珍藏版）》请在优知文库上搜索。

1、OR第三章 整数线性规划CH 3 整数线性规划(ILP)整数线性规划的基本问题整数线性规划的基本问题割平面法割平面法分枝定界法分枝定界法分解算法分解算法OR第三章 整数线性规划学习目的学习目的3.1 整数线性规划整数线性规划 基本问题基本问题OR第三章 整数线性规划要求变量取整数值的要求变量取整数值的LP纯纯(全全)整数规划问题整数规划问题只要求部分变量取整数值的只要求部分变量取整数值的LP混合整数规划问题混合整数规划问题一般形式一般形式Tnijjijjimin(max)s.t.(,),10,1,1,2,c xa xbimxjnxIiJnN Axb0 x 非负整数集或其某一子集非负整数集或其某

2、一子集OR第三章 整数线性规划分类分类:0,1,2,I 若若1,2,1,2,JnNJn0,1I 若若1,2,1,2,JnJn纯纯(全全)整数规划问题整数规划问题混合整数规划问题混合整数规划问题01 规划规划混合混合01 规划规划Note:因为有关纯整数规划问题的理论、因为有关纯整数规划问题的理论、算法均可易于推广算法均可易于推广 到一般的混合整数规划问题到一般的混合整数规划问题,故以下仅讨论纯整数规故以下仅讨论纯整数规 划问题划问题.OR第三章 整数线性规划 许多实际问题中许多实际问题中,所研究或可供选择的量具有不可所研究或可供选择的量具有不可分割分割,或间断变化的性质或间断变化的性质某些问题

3、真与假、取与舍等带有逻辑、组合特性某些问题真与假、取与舍等带有逻辑、组合特性均可描述为某些形式的均可描述为某些形式的 IP、MIP进而进而,离散最优化问题离散最优化问题OR第三章 整数线性规划Exp.1:(投资选择问题投资选择问题)设现有资金总额为设现有资金总额为B,可供选择的投资项目有可供选择的投资项目有n个个,其中其中项目项目j所需投资额和收益分别为所需投资额和收益分别为 和和 .此外此外,由于由于种种原因种种原因,有三个附加条件有三个附加条件:第一第一,若选择项目若选择项目1,就必须同时就必须同时选择项目选择项目2,反之反之,则不一定则不一定;第二第二,项目项目3和和4至少得选择一个至少

4、得选择一个;第三第三,项目项目5,6,7中必须选择两个中必须选择两个.试问应当怎样选择投资项目试问应当怎样选择投资项目,才能使总收益最大才能使总收益最大?jj,1,acjn OR第三章 整数线性规划解解:令令不对项目不对项目j投资投资对项目对项目j投资投资jx 01njjj=1njjj=1maxs.t.Zc xa xB21xx341xx5671xxxj0,1,1xjn 第一个附加条件第一个附加条件:第二个附加条件第二个附加条件:第三个附加条件第三个附加条件:01 规划问题规划问题1,jn OR第三章 整数线性规划Exp.2:旅行商旅行商(货郎担货郎担)问题问题 TSP 有一推销员有一推销员,从

5、城市从城市 出发出发,要通访城市要通访城市 各各一次一次,最后返回到最后返回到 .已知从已知从 到到 的旅费为的旅费为 ,问他应按怎问他应按怎样的次序访问这些城市样的次序访问这些城市,使得总旅费最小使得总旅费最小?0v0v12n,v vvijvvijc否则否则10解解:对每一对城市对每一对城市 ,定义一个变量定义一个变量ij,v vijxijx 若推销员决定从若推销员决定从 直接前往直接前往ijvv令令 相对于相对于 为充分大的正数为充分大的正数,ii,cMMij()cij0,1,in目的目的:迫使迫使ii0,0,1,xinOR第三章 整数线性规划nnijiji=0 j=0mins.t.Zc

6、xniji=0(1)1,0,1,xjnnijj=0(2)1,0,1,xin011220344553ij110 xxxxxxx其其它它每个城市恰好进入一次每个城市恰好进入一次每个城市恰好离开一次每个城市恰好离开一次不够不够!0v1v2v3v4v5v子环游消去约束子环游消去约束ijijiji(3)10,1,0,1,0,1,uunxnxi jnuRinOR第三章 整数线性规划(3)34344545535315 14154154xuuxuuxuu 54 矛盾矛盾.无论无论 与与 取什么值取什么值345,u uu一个更好的子环游消去约束一个更好的子环游消去约束:(3)i ji S j Si1xS 0,1

7、,0,1,SnSn 10,1,32nSnSOR第三章 整数线性规划整数线性规划的难解性整数线性规划的难解性考虑纯考虑纯 ILP:Tmins.t.0c xAxbxx为为整整值值向向量量忽略该限制忽略该限制:(ILP)(LP)Question 1:可否通过解可否通过解(ILP)对应的对应的(LP),然后将其舍入然后将其舍入 到最接近的整数解到最接近的整数解,而得而得(ILP)的最优解的最优解?l某些情况下某些情况下,如当对应如当对应LP的解的分量是的解的分量是一些很大的数时一些很大的数时,此法是可行的此法是可行的.此时对舍入误差不敏感此时对舍入误差不敏感.OR第三章 整数线性规划Question

8、2:l一般情况下一般情况下,把把LP的解舍入到一可行的整数解往往非常困难的解舍入到一可行的整数解往往非常困难,甚至不可行甚至不可行!从实际问题的背景从实际问题的背景逻辑性原则逻辑性原则建模准则建模准则变量取整值的约束变量取整值的约束是用来描述某种组合限制是用来描述某种组合限制本质上是一种非线性本质上是一种非线性,不连续的约束不连续的约束如如:jjj01(1)0 xorxx非线性约束非线性约束,无法用线性约束代替无法用线性约束代替!目标目标下降方向下降方向LP的可行解集的可行解集ILP的最优解的最优解LP的最优解的最优解OR第三章 整数线性规划依据依据LP的这些本质的这些本质.舍入法自然不可取舍

9、入法自然不可取,因为这样会因为这样会破坏原建破坏原建LP描述问题的目的描述问题的目的.Question 3:可否用枚举法来解可否用枚举法来解ILP呢呢?ILP的可行解集合是由一些离散的整数点的可行解集合是由一些离散的整数点(格点格点)构成构成相应的相应的LP的可行解集和是包含这些格点的多面凸集的可行解集和是包含这些格点的多面凸集!IF有有界界格点的数目是有限的格点的数目是有限的低维低维&数目少数目少可行可行!Otherwise,NO!01 规划规划:49!231030n 3103022298102410Exp.:TSP 50个城市个城市OR第三章 整数线性规划解解IP的算法的算法传统传统(精确

10、精确):现代现代(近似近似):割平面割平面,B&B,分解分解,DP 启发启发,近似近似,GA,NN,并行并行,模拟模拟 OR第三章 整数线性规划整数规划与线性规划之间的关系整数规划与线性规划之间的关系考虑考虑IPnn:,PxRAxbSPZ令令Tn()max:,Z bc x Axb xZTnTmax:max:c x xPZc x xS和其对应的线性规划和其对应的线性规划TnLP()max:,Zbc x Axb xRTmax:c x xP则有以下基本结论则有以下基本结论:OR第三章 整数线性规划Th.:LPTm)(0)(0)(0)0:)(0),(),()aZZbZQuRuAccZQdQSZ beQ

11、SZ b 若若则则或或有有限限若若则则或或Proof:LP0(0)(0)ZZ显然显然若若 ,则相应的对偶问题则相应的对偶问题:可行可行Q min0s.t.uuQ由由LP的对偶理论的对偶理论LP(0)0ZLP(0)(0)0ZZ)aOR第三章 整数线性规划原始问题无界原始问题无界Minkowski Th若若 ,则对偶问题不可行则对偶问题不可行,而原始问题可行而原始问题可行Q 必存在必存在P的一极方向的一极方向 ,使得使得jrTj0c r jr 可取为整值向量可取为整值向量,展开展开nPZSLP(0)(0)ZZ )abc、成成立立若若 ,则由则由LP的对偶理论知的对偶理论知:Q LP,()PQZb要

12、要么么要要么么有有限限)d类似地类似地,若若 ,则则Q LP,()PQZb 要要么么要要么么若若 ,则类似上述则类似上述c)的证明的证明S ()Z b )eOR第三章 整数线性规划推论推论:LPLP),)(),()(0),()aPSbZbSZ bcZSZ b 若若则则若若有有限限 则则或或有有限限若若则则或或理论上理论上,整数规划的求解可转化为线性规划的求解整数规划的求解可转化为线性规划的求解!通过求解通过求解LP问题问题 ,则可知则可知(a),(b),(c)三种三种情况中哪一个将会发生情况中哪一个将会发生.该推论还表明该推论还表明:除非当除非当P非空时非空时 S可能可能为空为空,则则IP与其

13、对应的与其对应的LP问题有着相同的状态问题有着相同的状态.Tmax:c x xP 以下假设以下假设 为一为一 整值矩阵整值矩阵,将证明将证明conv(S)为一有理多面体为一有理多面体.,A b(1)mnOR第三章 整数线性规划Weyl Th.:则则Q为一有理多面体为一有理多面体.若若A为一为一 的有理系数阵的有理系数阵,B为一为一 的有理系数阵的有理系数阵,且且1mn2mn112mmmnkk=1:,1,QxRxyAzByyRzR 当当P有界时有界时,S要么为空要么为空,要么只包含有限多个点要么只包含有限多个点,则由则由Weyl Th知知conv(S)为一有理多面体为一有理多面体.当当S含有无穷

14、多个点的时候含有无穷多个点的时候,我们将证明我们将证明conv(S)可由可由S中的有限多个点和有限多个整值极方向来生成中的有限多个点和有限多个整值极方向来生成!关键在于表明关键在于表明一多面体中整值点的集合可以有限产生一多面体中整值点的集合可以有限产生:找一有限集合找一有限集合 ,并证明并证明S可以通过可以通过在在Q中选取一点中选取一点,再加再加上上P的极方向的非负整系数线性组合来生成的极方向的非负整系数线性组合来生成.QSOR第三章 整数线性规划nn:,PxRAxbSPZ 为一为一 整值矩阵整值矩阵,则有则有,(1)A bmn)存在存在S的一个有限点集的一个有限点集 和和P极方向的一个有限极

15、方向的一个有限 集集 ,使得使得 ll LqQ jj JrLJnjjj J:,1,llll Ll LSxRxqrZZ)若若P为一个锥为一个锥(b=0),则存在则存在P 的极方向的一个有限集的极方向的一个有限集 ,使使 hh HHnhhh H:,SxRxZ Th.:假若假若OR第三章 整数线性规划Proof:所有这些极向量均有有理分量所有这些极向量均有有理分量且由且由Minkowski Th 知知)令令 表示表示P的极点所构成的有限集合的极点所构成的有限集合,为为P的极方向的有限集合的极方向的有限集合kn,xRkKjn,rRjJP为有理多面体为有理多面体knkjkjkkjk Kj Jk K:,1

16、,0,PxRxxrkK jJ 不失一般性不失一般性,设对设对 均为整系数向量均为整系数向量,令令j,jJ rnkjkjkkjk Kj Jk K:,1,0,01,QxZxxrkKjJ且有且有n:lqZlLQSOR第三章 整数线性规划任一点任一点 且且iinxSxZiikiijijkjjjk Kj Jj J()xxrriiikkjk K1,0,kK jJ 为为Q中的一点中的一点,l iL such that ijiijjjj J,l iqrjJ()成立成立)若若P为一个锥为一个锥,则则lqS对对 ,1,lZqS 有有因此因此,只需取只需取:hj:lhHqlLrjJ则由则由)知知)成立成立.OR第三章 整数线性规划Th.:若若 ,其中其中 为一为一 整值整值 矩阵矩阵,且且 ,则则conv(S)为一有理多面体为一有理多面体.n:PxRAxb,(1)A bmnnSPZProof:因任一点因任一点 均可写成均可写成()的形式的形式,点集点集 的任一凸组合则可写为的任一凸组合则可写为:ixSi,xS iI iijiiji Ii Ij Jl ixxqr ijiijj Ji Ii I:ll Ll il