运筹学 第5章整数规划

三、第5章整数规划(IntegerProgramming)整数规划的模型分枝定界法割平面法0－1整数规划指派问题（一）、整数规划问题实例例1、合理下料问题设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得既满足需要，又使所用的原材料最少？零件方个数式零件零件毛坯数一、整数规划的模型1mAA1nBB1mbb1111nmmnaaaa例2、某公司计划在m个地点建厂，可供选择的地点有A1,A2,…,Am，他们的生产能力分别是a1,a2,…,am（假设生产同一产品）。第i个工厂的建设费用为fi(i=1.2…m),又有n个地点B1,B2,…,Bn需要销售这种产品，其销量分别为b1,b2,…,bn。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？jjxB解设为按种方式下料的原材料件数,12min...nZxxx1(1,2,...,)..0(1,2,...,)nijjijjaxbimstxjn且为整数单销地厂址价生产能力建设费用销量12nBBB12mAAA12maaa12mfff12nbbb111212122212nnmmmnccccccccc11ijijxABi,...,m,j,...,n设表示从工厂运往销地的运量1120iiiAyi,,...,mA在建厂又设不在建厂111mnmijijiiijiminzcxfy111212001212nijiijmijjiijixayi,,...,ms.t.xbj,,...,nx,yi,,...,m,j,,...,n或1例3、机床分配问题设有m台同类机床，要加工n种零件。已知各种零件的加工时间分别为a1,a2,…an，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。设：1分配第i台机床加工第j种零件；xij＝（i=1.2…m,j=1.2…n）0相反。于是，第i台机床加工各种零件的总时间为：njijjmixa1)2.1(又由于一个零件只能在一台机床上加工，所以有miijmix1)2.1(1因此，求xij，使得121111minmax(,,,)1(j1,2,,n)01(i1,2,,m,j1,2,,n)nnnjjjjjmjjjjmijiijZaxaxaxxx或（二）、整数规划的数学模型一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。1112012njjjnijjijjjmaxzminzcxaxbi,,...,ms.t.xj,,...,nx或且部分或全部为整数纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。（三）、整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。举例说明。例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。12121212149516310maxzxxxxs.t.xxx,x12121212149516310maxzxxxxs.t.xxx,x,且为整数x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。用图解法求出最优解1231029236x,x,z且有因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分枝定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。（一）、基本思路考虑纯整数问题：整数问题的松弛问题：二、分枝定界法1112012njjjnijjijjmaxzcxaxbi,,...,ms.t.xj,,...,n且为整数1112012njjjnijjijjmaxzcxaxbi,,...,ms.t.xj,,...,n1.,IPLP,先不考虑整数约束解的松弛问题可能得到以下情况之一:1LP,IP,;若没有可行解则也没有可行解停止计算2LP,IP,LP若有最优解并符合的整数条件则的,.最优解即为IP的最优解停止计算3LP,IP,若有最优解但不符合的整数条件转入.,LP:下一步为讨论方便设的最优解为01200rmXb,b,...,b,...,b,,...,12i,bi,,...,m0目标函数最优值为Z其中不全为整数2.定界0**IPZ,ZZ,记的目标函数最优值为以作为的上界记为0ZZ.X,再用观察法找一个整数可行解并以其相应的*ZZ,ZZ,目标函数值作为的下界记为也可以令Z=-,*ZZZ.则有3.分枝0LPX,,在的最优解中任选一个不符合整数条件的变量rrrrxb,bb.例如不为整数以表示不超过的最大整数构造两个约束条件1rrrrxbxb和**,ZZZ,X.如此反复进行直到得到为止即得最优解5.比较与剪枝,Z,,各分枝的目标函数值中若有小于者则剪掉此枝表明,;.此子问题已经探清不必再分枝了否则继续分枝IP,将这两个约束条件分别加入问题形成两个子问题1212IPIP,LPLP.和再解这两个问题的松弛问题和4.修改上下界1,;在各分枝问题中找出目标函数值最大者作为新的上界2,从已符合整数条件的分枝中找出目标函数值最大者.作为新的下界选一分支写出并求解放松问题，同时从分支集中删除该分支判定是否为整数解初始分支为可行解集，初始界为无穷大判定是否分支集空是停止当前最好解为最优解是否判定最优值是否小于当前界判定最优值是否小于当前界是否按非整数变量分支并加入分支集否是以最优解替代当前最好解最优值替代当前界例1：用分枝定界法求解整数规划问题（用图解法计算）解：首先去掉整数约束，变成一般线性规划问题（二）、例题12121211252563040minzxxxxxxs.t.IPxx,x记为且为整数12121211252563040minzxxxxxxs.t.LPxx,x记为用图解法求（LP）的最优解，如图所示。x1x2⑴⑵33(18/11,40/11)⑶对于x1＝18/11≈1.64，取值x1≤1，x1≥2对于x2=40/11≈3.64，取值x2≤3，x2≥4先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z(0)也是（IP）最小值的下限。z19.8有下式：且为整数0,1430652)1(5min2111212121xxxxxxxxIPxxZ且为整数0,2430652)2(5min2111212121xxxxxxxxIPxxZ现在只要求出（LP1）和（LP2）的最优解即可。x1x2⑴⑵33(18/11,40/11)⑶先求（LP1）,如图所示。此时B在点取得最优解。x1＝1,x2=3,Z(1)＝－1611同理求（LP2）,如图所示。在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7BAC∵Z2Z1＝－16∴原问题有比（－16）更小的最优解，但x2不是整数，故利用3≥10/3≥4加入条件。找到整数解，问题已探明，此枝停止计算。加入条件：x2≤3,x2≥4有下式：且为整数0,32430652)3(5min21211212121xxxxxxxxxIPxxZ且为整数0,42430652)4(5min21211212121xxxxxxxxxIPxxZ只要求出（LP3）和（LP4）的最优解即可。x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如图所示。此时D在点取得最优解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4Z=-16D求（LP4），如图所示。无可行解，不再分枝。但x1＝12/5不是整数，可继续分枝。即3≤x1,x1≤2。在（LP3）的基础上继续分枝。加入条件3≤x1,x1≤2有下式：且为整数0,232430652)5(5min211211212121xxxxxxxxxxIPxxZ且为整数0,332430652)6(5min211211212121xxxxxxxxxxIPxxZ只要求出（LP5）和（LP6）的最优解即可。x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如图所示。此时E在点取得最优解。即x1＝2,x2=3,Z(5)＝－17找到整数解，问题已探明，此枝停止计算。E求（LP6），如图所示。此时F在点取得最优解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5Z(5)F如对Z(6)继续分解，其最小值也不会低于－15.5，问题探明,剪枝。至此，原问题（IP）的最优解为：x1=2，x2=3,Z*=Z(5)＝－17以上的求解过程可以用一个树形图表示如右：LP1x1=1,x2=3Z(1)＝－16LPx1=18/11,x2=40/11Z(0)＝－19.8LP2x1=2,x2=10/3Z(2)＝－18.5LP3x1=12/5,x2=3Z(3)＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)＝－17LP6x1=3,x2=5/2Z(6)＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃且全为整数0,13651914max21212121xxxxxxxxZ练习：用分枝定界法求解整数规划问题（图解法）LP1x1=1,x2=7/3Z(1)＝10/3LPx1=3/2,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)＝3LP6无可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)＝61/14LP4无可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤2x1≥3＃＃LP1x1=1,x2=7/3Z(1)＝10/3LPx1=2/3,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9LP3x1=33/14,x2=2Z(3)＝61/14LP4无可行解LP7x1=2,x2=2Z(7)＝4LP8x1=3