Lecture 7 整数规划

华南理工大学模具研究室[e-mail]变量取整数的规划称为整数规划。所有变量都取整数的规划称为纯整数规划，部分变量取整数的规划称为混合整数规划。所有变量都取0、1两个值的规划称为0-1规划，部分变量取0、1两个值的规划称为0-1混合规划。在线性规划问题的讨论中，有些最优解是小数，但某些常要求最优解是整数（即整数解）,如决策变量是：机器的台数、人数、车辆数等等整数规划模型例1背包问题有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为maxz=v1x1+v2x2+…+vkxks.t.w1x1+w2x2+…+wkxk≤Wx1,x2,…xk≥0x1,x2,…xk为整数这个问题如果用线性规划求解，k个变量中将只有一个基变量大于0，其余k-1个非基变量都等于0，而且这个大于0的基变量一般情况下是非整数。这样的解显然是没有意义的。例如以下一个背包问题maxz=17x1+72x2+35x3s.t.10x1+42x2+20x3≤50x1,x2,x3≥0x1,x2,x3为整数线性规划最优解为x1=0，x2=4150，x3=0而整数规划的最优解是x1=1，x2=0，x3=2。例2厂址选择问题在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，…，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。设地建厂表示在地不建厂表示在i1i0xi整数规划模型为1,0xrxLxLIxI.t.sxPzmaxiN1iiN1iiiN1iiiN1iii这是一个0-1规划问题。线性规划和整数规划的关系对IP问题，可能会认为，只要求出不受整数约束的解，然后“舍入化整”，就可得到整数最优解？对吗？设线性规划问题为maxz=x1+4x2s.t.14x1+42x2≤196-x1+2x2≤5x1x2≥0相应的整数规划问题为maxz=x1+4x2s.t.14x1+42x2≤196-x1+2x2≤5x1x2≥0x1、x2为非负整数5x24A3B2101234567x1线性规划的可行域如图中阴影部分所示，由图解法可知，线性规划的最优解位于图中的A点，即（x1，x2）=（13/5，19/5）=（2.6，3.8），线性规划最优解的目标函数值为z=89/5=17.8。而相应的整数规划的可行解是图中线性规划可行域中整数网格的交点，共有29个可行解，整数规划的最优解位于图的B点，即（x1，x2）=（5，3），整数规划最优解的目标函数值为z=17。由以上例子可以看到，简单地将线性规划的非整数的最优解用四舍五入或舍去尾数的办法得到整数解，一般情况下并不能得到整数规划的最优解。整数规划的求解方法要比线性规划复杂得多。上例得到的启示１：（１）化整后未必是可行解（２）即使是可行解，也未必是最优解（３）即使该方法结果可以得到最优解，但如果有n个决策变量，则取舍方案有２n种。当n=60时，260约等于1018，这使计算机也难以实现。所以，有必要讨论整数规划的求解方法。启示２：（１）是否能在LP的约束区域中切去几块不含整数解的可行域，使整数解作为顶点，这样求LP问题的最优解，即为整数解。如前例，增加约束x2≤3，则LP问题的最优解，即为x1=5,x2=3,Zmax=17，就是IP问题的解。（２）在LP的可行域中，整数点不多时（12个），是否可以用穷举法。割平面法1959年，R.E.Gomory首先提出，从此使IP逐渐形成为一个独立的运筹学分支。其实质是用解LP问题的方法来解IP问题。基本思想是：通过对LP问题的求解，如果最优解X*是整数解，则就是IP的解。不是整数解，设法对LP问题增加约束（割平面），把LP的可行域中去掉不含整数解的一部分，再求LP问题。反复进行，直到求得最优解割平面法的关键在于如何寻找适当的切割约束条件（即构造一个割平面），且保证切掉的部分不含有整数解。但由于用割平面法求解IP问题常常会遇到收敛很慢的情况。所以用它来求解IP问题的仍然不多，但在理论上是重要的。设Tnxxxx)ˆ,,ˆ,ˆ(ˆ21是（IP）问题对应的（LP）问题的一个最优解，若),,2,1(ˆnixi全为整数，则xˆ就是（IP）问题的最优解；若),,2,1(ˆnixi不全为整数，则需构造割平面，假设（LP）问题的最优单纯形表的第i行的基变量xBi非整数，则第i行的方程为：nmjijijibxax1''XBx1x2…xr…xmxm+1xm+2…xnbx11'1,1ma'2,1ma…'1na'1bx21'1,2ma'2,2ma…'2na'2b…………xr1'1,mra'2,mra…'rna'rb…………xm1'1,mma'2,mma…'mna'mbZ00…0…0m+1m+2…n-Z(0)将式中的'ija（j=m+1,m+2,…,n）和'ib分解为一个整数N与一个正的真分数f的两数之和：''(01)(01)ijijijijiiiiaNffbNff则可写成：nmjnmjiijijjijifNxfxNx11经整理得：nmjnmjjijiijijixffNxNx11由于xi、xj（j=m+1,…,n）、Nij（j=m+1,…,n）及Ni都为整数，故上式左端必为整数，则右端也须为整数.观察右端，因为(01)ijf，)10(if又因为xj0，则有nmjjijxf10于是得到nmjijijifxff11又要满足右端为整数，则必定有：01nmjjijixff这就是一个割平面，可以证明，将上式加入原（IP）问题所对应的（LP）问题的约束中，可以割去非整数最优解X，却不会切割掉任一整数可行解nmjnmjjijiijijixffNxNx11例用割平面法求解下面的IP.maxz=x1+x2s.t.5221xx2421xx且全为整数0,21xx解：将对应的LP问题化为标准形，用单纯形法求解.minz’=-x1-x2s.t.12325xxx12442xxx1234,,,0xxxx序号bcBxBx1x2x3x4(a)0x3211050x4-4*101-2检验数-1-1000(b)0x111/21/205/21x403218检验数0-1/21/205/2(c)1X1101/6-1/67/61x2012/31/38/3检验数005/61/623/6求解得最最优解为X0=(7/6,8/3)T.由于X0是非整数最优解，则构造割平面''(01)(01)ijijijijiiiiaNffbNff引入一个变量x5，得：323132543xxx并将该约束添加到表中倒数第二行22223232324242482222,33322200,33311100,333bNfaNfaNf01nmjjijixff0)3132(3243xx序号bcBxBx1x2x3x4x5(a)1x2012/31/308/31x1101/6-1/607/60x500-2/3-1/3*1-2/3检验数005/61/6023/6(b)1x20100121x1101/20-1/23/20x40021-32检验数001/201/27/2注意：此处需要用对偶单纯形法求解分枝定界法（BranchandBoundmethod）如果通过对全体可行的整数解，逐个比较优劣，得到最优解的方法，称为完全枚举法（穷举法）。但在解的个数很多时，这往往是不可能的。如果能通过仅对部分可行整数解的讨论，就得到原问题的最优解，称为部分枚举法或隐枚举法。分枝定界法就是一种隐枚举法，这是一种应用很广的求解方法。分枝定界法是求解整数规划的一种常用的有效方法，它不仅能针对纯整数规划问题求解，也能对混合整数规划问题求解.先给出它的一般思想：))(max()(minxfxfsxsx松弛问题的提出考察这样的问题其中S是有限集设A,B是两个有限集，且)2()(min)1()(minxfxfBxAxBAf(x)是定义在B上的函数，优化模型：称问题(2)是问题(1)的松弛问题。显然(2)的最优值小于等于问题(1)的最优值。问题(2)的搜索范围大，所以(2)的求解更难一些？看一个生活中的例子：B—全国100m跑运动员全体A—全国18岁的百米运动员全体米成绩表示具体运动员的100)(Bxxf问题(2))(minxfBx很易解决，只需查一下全国记录就)(minxfAx知道了。但问题(1)确难多了。先假设对某个最优化问题（1）(min)已找到一个容易解决的松弛问题(2),设x0是(2)的最优解，其最优解z0=f(x0).１、如果则问题(1)也解决了２、否则，至少可知问题(1)的最优值z1一定≥z0.即给出了问题(1)的一个下界所以解决问题(2)总是有好处的。0xA分枝定界法由“分枝”和“定界”两部分组成.分枝定界法首先求解整数规划相应的线性规划问题，如果其最优解符合整数条件，则线性规划问题的最优解就是整数规划问题的解.如果其最优解不符合整数条件，则求出整数规划的上下界用增加约束条件的方法，并把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小最优目标函数值上下界的距离，当上下界的值相等时，整数规划的解就被求出，就是其目标函数值取此下界的对应线性规划的整数可行解.首先不考虑变量的整数约束，求解相应的线性规划问题，得到线性规划的最优解。设线性规划问题minz=CTXs.t.AX=bX≥0x2EDCBSub1Sub2x1OIrxrIr+1A构造两个子问题Sub1和Sub2：Sub1Sub2minz=CTXminz=CTXs.t.AX=bs.t.AX=bxr≤Irxr≥IrX≥0X≥0如果某一个子问题的最优解是整数解，就获得了一个整数可行解，这个子问题的目标函数值要记录下来，作为整数规划最优目标函数值的上界。如果某一个子问题的解还不是整数解，但这个非整数解的目标函数值已经超过和这个上界，那么这个子问题就不必再进行分枝。如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则用较小的整数解的目标函数值代替原来的上界。上界的值越小，就可以避免更多不必要的分枝。这个确定整数解目标函数值上界并不断更新上界，并且不断“剪除”目标函数值超过上界的分枝的过程，称为定界（Bound）。当最低一层子问题出现以下三种情况之一时，分枝定界算法终止：1、子问题无可行解；2、子问题已获得整数解；3、子问题的目标函数值超过上界。例用分枝定界法求解以下整数规划minz=-2x1-3x2s.t.5x1+7x2≤354x1+9x2≤36x1x2≥0x1，x2为整数先求得相应的线性规划的最优解，为17814z,1762x,17123x21x24Sub2321Sub1x101234567取1762x2分割可行域，得到以下两个子问题：Sub-1Sub-2minz=-2x1-3x2minz=-2x1-3x2s.t.5x1+7x2≤35s.t.5x1+7x2≤354x1+9x2≤364x1+9x2≤36x2≤2x2≥3x1x2≥0x1x2≥0求解过程0-1规划如果线性规划中的所有变量的取值只能取0、1，则这类线性规划问题是一种特殊的整数规划问题，我们把它称为0-1规划，把只能取0或1值的变量称为0-1变量。主要求解方法：（过滤性隐枚举法）过滤性隐举法基本思想是：首先将全部变量取0或1的所有组合列出，然后再逐个检查这些组合（解）是否可行的过程中，利用增加并不断修改过滤条件的办法，减少计算量，达到求出最优解的目的。例用完全枚举法求解0—1规划问题