第六章-整数线性规划

运筹学(OperationsResearch)Chapter6整数线性规划§6.1整数线性规划问题的提出§6.2分支定界解法§6.3割平面解法§6.40-1型整数线性规划§6.5指派问题本章主要内容：Page3§6.1整数线性规划问题的提出Page41.整数规划（intergerprogramming,简称IP）要求部分或全部决策变量取整数值的规划问题称为整数规划。变量限制为整数的线性规划则称为整数线性规划（intergerlinearprogramming，简称ILP）。§6.1整数线性规划问题的提出2.整数线性规划问题的种类：（1）纯整数线性规划（pureintergerlinearprogramming）：全部决策变量都必须取整数值的整数线性规划。（2）混合整数线性规划(mixedintergerlinearprogramming)：决策变量中仅有部分取整数值的整数线性规划。（3）0-1型整数线性规划(0-1intergerlinearprogramming)：决策变量只能取值0或1的整数线性规划。Page5一般地，整数线性规划问题的数学模型为（）3.1.11112max(min)(,),1,2,,..0,1,2,,,,,njjjnijjijjnzcxaxorbimstxjnxxx部分或全部为整数整数规划与线性规划在形式上相差不多,但是由于整数规划的解是离散的正整数,实质上它属于非线性规划.若去掉整数规划的整数约束———为整数,则该规划就变成了一个线性规划,一般称这个线性规划为该整数规划的松弛问题.jxPage6例6.1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表所示。问两种货物各托运多少箱，可使获得利润为最大?§6.1整数线性规划问题的提出货物体积（m3/箱）重量（100kg/箱）利润（百元/箱）甲5220乙4510托运限制24m31300kgPage7解：该问题和LP问题的区别仅在于最后一个约束条件(5)。现在先解由(1)～(4)构成的线性规划问题(称这样的问题为与原问题相应的线性规划问题)。1212121212max2010(1)5424(2)2513(3),0(4),(5)zxxxxxxxxxx为整数.§6.1整数线性规划问题的提出x1——甲货物的托运箱数；x2——乙货物的托运箱数；这就是一个(纯)整数线性规划问题，数学模型为：Page8易求得相应的线性规划问题的最优解为§6.1整数线性规划问题的提出***124.8,0,96.xxz目前得到的最优解不是整数，所以不合条件⑤的要求。是不是可以把所得的非整数最优解经过“化整”就可得到合于条件⑤的整数最优解呢?xx125,0凑整为不满足条件②，因而它不是可行解Page9§6.1整数线性规划问题的提出124,1,90.xxz因为124,0,80.xxz凑整为这当然满足各约束条件，因而是可行解，但不是最优解。Page10图中画(+)号的点表示可行的整数解。凑整得到的(5，0)点不在可行域内，而C点又不合于条件⑤。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样z的等值线就由z=96变到z=90，差值为Δz=96-90=6，表示利润的降低，这是由于变量的不可分性(装箱)所引起的。§6.1整数线性规划问题的提出Page11例6.2设整数规划问题：解：首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。§6.1整数线性规划问题的提出12121212max14951631,0zxxxxxxxx且为整数.12121212max14951631,0.zxxxxxxxx•用图解法求出最优解为：***12310,,29/6.23xxzPage12现求整数解(最优解):如用舍入取整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然都不可能是整数规划的最优解。x1x2⑴⑵33(3/2,10/3)按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图。其中(2,2),(3,1)点的目标函数值最大，即为z=4。§6.1整数线性规划问题的提出Page13整数规划IP与线性规划LP解的性质:⑴如果LP的最优值在其可行域T的某个顶点上达到,则相应的IP最优值,在T中去掉不含整数点的区域后的T*中的整数点上达到.⑵对于求最大化(最小化)问题,LP最优解对应的目标函数值,是相应的IP最优解对应的目标函数值的上界(下界).Page14•1.穷举法：可以设想,整数规划的可行解集一定是具有确定数目的点阵,然后搜索这些点,比较目标函数值的大小,从而求得最优解.如例6.2•2.隐枚举法（ImplicitEnumeration）：只检查变量取值的组合的一部分的方法。Page15§6.2分支定界解法Page16整数线性规划问题的求解方法：1.分支定界法（branchandboundmethod）——可用于解纯整数或混合整数规划问题。2.割平面法—可用于解纯整数或混合整数规划问题。3.隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。4.匈牙利法—解决指派问题（“0-1”规划特殊情形）。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。§6.2分支定界解法Page17§6.2分支定界解法6.2.1分支定界法的思想：考虑最大化整数规划问题A，与它相应的线性规划记为问题B。从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数值z*的上界，记作；而A的任意可行解的目标函数值将是z*的一个下界。zzzz分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小和增大，最终求到z*。zzzPage18例求解为整数2121212121,0,702075679.9040maxxxxxxxxxtsxxz（A）0,702075679.9040max21212121xxxxxxtsxxz（B）6.2103.58567921xx7020721xx0·Bx2x1Z=0≤Z*≤Z0=356B的最优解：X1=4.81X2=1.82Z0=356Page20（1）求整数规划IP的相应的LP的最优解；①若LP无可行解，则IP也没有可行解；②若LP有最优解且满足整数要求，则即为IP的最优解;③若LP有最优解但不满足整数要求，则转下一步；（2）进行迭代：①分支与定界：在LP的最优解中任选一个非整数解的变量xi=b,在LP问题中加上约束：6.2.2分支定界法的解题步骤：§6.2分支定界解法组成两个新的LP问题，称为分枝。[][]+1iixbxb和Page21求各分支解和目标值，定界：原问题是求最大值时，各分支最优目标值中最大的为新上界；符合整数条件的分支中目标值最大的为新下界，若无整数分支，若z≥0，可令z=0（求min问题，与之相反）。②比较与剪枝：检查所有分枝的解及目标函数值，若上界等于下界，则停止；否则剪去小于下界的分支，对于大于下界的分支继续重复（2），直到找到最优解（目标值优的先分支）。§6.2分支定界解法Page22序号分支问题1分支问题2说明1无可行解无可行解原问题无可行解2无可行解整数解此整数解为最优解3无可行解非整数解对问题2继续分支4整数解整数解较优的为最优解5整数解，优于问题2非整数解问题1为最优解6整数解非整数解，优于问题1问题1停止分支，继续对问题2分支7非整数解非整数解继续分支,较优的先分一些原则Page23例6.3求解整数规划问题§6.2分支定界解法解：解相应的线性规划B，得最优解而x1=0，x2=0是问题A的一个整数可行解，这时z=0是z*的一个下界，记作1212121240909756720700maxzxxxxs.t.xxx,x,且全部是整数.**1204.81,1.82,356.xxz可见它不符合整数条件。这时z0是问题A的最优目标函数值z*的上界，记作0.z*0356.z即0.zzPage24§6.2分支定界解法Page25分支：问题B的解中有一个非整数变量x1=4.81。则在原问题中增加分别两个约束条件：x1≤4和x1≥5，将B分解为B1和B2。x1≤4§6.2分支定界解法(1)分支与定界x1≥5Page26仍然不考虑整数条件约束，解问题B1和B2，得到最优解为：定界：显然没得到全部整数解。问题B1问题B2x1=4x1=5x2=2.1x2=1.57z1=349z2=341§6.2分支定界解法那么必存在最优整数解，且*0349.z12=349zz,z,Page27分支：因z1＞z2，故先分解B1为两支。B1增加条件x2≤2称为问题B3；B1增加条件x2≥3称为问题B4。§6.2分支定界解法（2）分支与定界Page28求解问题B3和B4，得到定界：显然问题B3已得到整数解。z3=340，故将问题B3问题B4x1=4x1=1.42x2=2x2=3z3=340z4=327而它大于z4=327，所以问题B4没有必要分解。340z那么必存在最优整数解，且§6.2分支定界解法*340349.zPage29分支：继续对问题B2进行分支，B2增加条件x2≤1称为问题B5；B2增加条件x2≥2称为问题B6。问题B5问题B6x1=5.44无可行解x2=1z5=308§6.2分支定界解法（3）分支与定界*340349.z故最优解为x1=4和x2=2，最优值为z*=340.Page30解题过程§6.2分支定界解法Page31•例6.4用分枝定界法求解:解:先求对应的LP问题用图解法得到最优解：§6.2分支定界解法1212121243120810225250B:maxzxx.x.xstx.xx,x1212121243120810225250A:maxzxx.x.xs.t.x.xx,x,且全部是整数.**1203.57,7.14,35.7,xxzPage321010108.02.121xx255.2221xxB的最优解X=(3.57,7.14),Z0=35.7x1x2oABC§6.2分支定界解法Page3310x2oABCB1B234B1:X=(3,7.6),z1=34.8①②B2:X=(4,6.5),z2=35.5§6.2分支定界解法1212121121:max431.20.81022.525..3,0Bzxxxxxxstxxx1212121122:max431.20.81022.525..4,0Bzxxxxxxstxxx1134xxLP增加约束及得到两个Page3410x1x2oABCB1B2134B21:X=(4.33,6),z3=35.33627x不可行§6.2分支定界解法121212121222:max431.20.81022.525..47,0Bzxxxxxxstxxxx，121212121221:max431.20.81022.525..46,0Bzxxxxxxstxxxx，22267LPxx选择目标值最大的分枝，加约束及得Page3510x1x2oACB1346B211:X=(4,6),z5=34B212:X=(5,5),z6=355B6§6.2分支定界解法121212121121211431208102252546404B:maxzxx.x.xx.xs.t.xxxx,xx,，，即可行域是一条线段121212121221243