资源描述：
《运筹学 Ch3 整数线性规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章整数线性规划CH3整数线性规划(ILP)整数线性规划的基本问题割平面法分枝定界法分解算法学习目的§3.1整数线性规划基本问题要求变量取整数值的LP纯(全)整数规划问题只要求部分变量取整数值的LP混合整数规划问题一般形式非负整数集或其某一子集分类:纯(全)整数规划问题混合整数规划问题0—1规划混合0—1规划Note:因为有关纯整数规划问题的理论、算法均可易于推广到一般的混合整数规划问题,故以下仅讨论纯整数规划问题.许多实际问题中,所研究或可供选择的量具有不可分割,或间断变化的性质某些问题真与假、取
2、与舍等带有逻辑、组合特性均可描述为某些形式的IP、MIP进而,离散最优化问题Exp.1:(投资选择问题)设现有资金总额为B,可供选择的投资项目有n个,其中项目j所需投资额和收益分别为和.此外,由于种种原因,有三个附加条件:第一,若选择项目1,就必须同时选择项目2,反之,则不一定;第二,项目3和4至少得选择一个;第三,项目5,6,7中必须选择两个.试问应当怎样选择投资项目,才能使总收益最大?解:令不对项目j投资对项目j投资第一个附加条件:第二个附加条件:第三个附加条件:0—1规划问题Exp.2:旅行商(
3、货郎担)问题TSP有一推销员,从城市出发,要通访城市各一次,最后返回到.已知从到的旅费为,问他应按怎样的次序访问这些城市,使得总旅费最小?否则解:对每一对城市,定义一个变量若推销员决定从直接前往令相对于为充分大的正数,目的:迫使每个城市恰好进入一次每个城市恰好离开一次不够!子环游消去约束(3)矛盾.无论与取什么值一个更好的子环游消去约束:(3)整数线性规划的难解性考虑纯ILP:忽略该限制:(ILP)→(LP)Question1:可否通过解(ILP)对应的(LP),然后将其舍入到最接近的整数解,而得(I
4、LP)的最优解?某些情况下,如当对应LP的解的分量是一些很大的数时,此法是可行的.此时对舍入误差不敏感.Question2:一般情况下,把LP的解舍入到一可行的整数解往往非常困难,甚至不可行!从实际问题的背景逻辑性原则建模准则变量取整值的约束是用来描述某种组合限制本质上是一种非线性,不连续的约束如:非线性约束,无法用线性约束代替!目标下降方向LP的可行解集ILP的最优解LP的最优解依据LP的这些本质.舍入法自然不可取,因为这样会破坏原建LP描述问题的目的.Question3:可否用枚举法来解ILP呢?
5、ILP的可行解集合是由一些离散的整数点(格点)构成相应的LP的可行解集和是包含这些格点的多面凸集!IF有界格点的数目是有限的低维&数目少—可行!Otherwise,NO!0—1规划:Exp.:TSP50个城市解IP的算法传统(精确):现代(近似):割平面,B&B,分解,DP启发,近似,GA,NN,并行,模拟整数规划与线性规划之间的关系考虑IP和其对应的线性规划则有以下基本结论:Th.:Proof:显然若,则相应的对偶问题:可行由LP的对偶理论原始问题无界MinkowskiTh若,则对偶问题不可行,而原
6、始问题可行必存在P的一极方向,使得∵可取为整值向量,展开若,则由LP的对偶理论知:类似地,若,则若,则类似上述c)的证明﹟推论:理论上,整数规划的求解可转化为线性规划的求解!通过求解LP问题,则可知(a),(b),(c)三种情况中哪一个将会发生.该推论还表明:除非当P非空时S可能为空,则IP与其对应的LP问题有着相同的状态.以下假设为一整值矩阵,将证明conv(S)为一有理多面体.WeylTh.:则Q为一有理多面体.若A为一的有理系数阵,B为一的有理系数阵,且当P有界时,S要么为空,要么只包含有限多个
7、点,则由WeylTh知conv(S)为一有理多面体.当S含有无穷多个点的时候,我们将证明conv(S)可由S中的有限多个点和有限多个整值极方向来生成!关键在于表明一多面体中整值点的集合可以有限产生:找一有限集合,并证明S可以通过在Q中选取一点,再加上P的极方向的非负整系数线性组合来生成.为一整值矩阵,则有ⅰ)存在S的一个有限点集和P极方向的一个有限集,使得ⅱ)若P为一个锥(b=0),则存在P的极方向的一个有限集,使Th.:假若Proof:所有这些极向量均有有理分量且由MinkowskiTh知ⅰ)令表示
8、P的极点所构成的有限集合,为P的极方向的有限集合P为有理多面体不失一般性,设对均为整系数向量,令且有任一点且为Q中的一点(△)ⅰ)成立ⅱ)若P为一个锥,则对,因此,只需取:则由ⅰ)知ⅱ)成立.﹟Th.:若,其中为一整值矩阵,且,则conv(S)为一有理多面体.Proof:因任一点均可写成(△)的形式,点集的任一凸组合则可写为:这里对而对故由Weyl定理知conv(S)为一有理多面体.其中对﹟Note:上述证明可直接推广到具有有理数据的混合整数集合,因此以
