混合整数线性规划

整数规划(IntegerProgramming)整数规划的模型分支定界法0－1整数规划指派问题（一）、整数规划问题实例例一、合理下料问题设某型号圆钢可生产零件毛坯为A1,A2,…,Am。在一根圆钢上下料的方式有B1,B2,…,Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？零件方个数式零件零件毛坯数nBB11mAAmbb1mnmnaaaa1111一、整数规划的模型设：xj表示用Bj(j=1.2…n)种方式下料根数模型：且为整数n)1.2(j0)2.1(min11jnjijijnjjxmibxaxZ例二、某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi(i=1.2…m),又有n个地点B1,B2,…Bn需要销售这种产品，其销量分别为b1.b2…bn。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？单销地厂址价生产能力建设费用销量nmmmnmmmnnbbbfacccAfacccAfacccABnBB2121222222121111211121设：xij表示从工厂运往销地的运量(i=1.2…m、j=1.2…n),1在Ai建厂又设Yi＝（i=1.2…m）0不在Ai建厂模型：n)1.2jm1.2(i10,0n)1.2(j)2.1(min111、或iijmijijnjiiijmiiiijijyxbxmiyaxyfxcZ（二）、整数规划的数学模型一般形式且部分或全部为整数或n)1.2(j0)2.1()min(max11jnjijijnjjjxmibxaxcZZ依照决策变量取整要求的不同，整数规划可分为纯整数线性规划、混合整数线性规划、0－1整数线性规划。纯整数线性规划：所有决策变量要求取非负整数。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。（三）、整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。举例说明。例：设整数规划问题如下且为整数0,13651914max21212121xxxxxxxxZ首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。0,13651914max21212121xxxxxxxxZ用解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：割平面法和分支定界法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。（一）、基本思路且为整数)2.1(,0)2.1()(max11mjxmibxaIPxcZjnjijijnjjj考虑纯整数问题：)2.1(,0)2.1()(max11mjxmibxaLPxcZjnjijijnjjj整数问题的松弛问题：二、分支定界法1、先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：不全为整数其中目标函数最优值为),,2,1(.Z)0,,0,,,,,,((0)21)0(mibbbbbXiTmr2、定界：记(IP)的目标函数最优值为Z*,以Z(0)作为Z*的上界，记为＝Z(0)。再用观察法找的一个整数可行解X′，并以其相应的目标函数值Z′作为Z*的下界，记为Z＝Z′，也可以令Z＝－∞，则有：Z≤Z*≤ZZ3、分枝：在(LP)的最优解X(0)中，任选一个不符合整数条件的变量，例如xr=（不为整数），以表示不超过的最大整数。构造两个约束条件xr≤和xr≥＋1rbrbrbrbrb如此反复进行，直到得到Z＝Z*＝为止，即得最优解X*。将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。4、修改上、下界：按照以下两点规则进行。⑴.在各分枝问题中，找出目标函数值最大者作为新的上界；⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝：各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。Z例一：用分枝定界法求解整数规划问题（用图解法计算）且全为整数0,4306525min211212121xxxxxxxxxZ记为（IP）解：首先去掉整数约束，变成一般线性规划问题0,4306525min211212121xxxxxxxxxZ记为（LP）（二）、例题用图解法求（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也是（IP）最小值的下限。有下式：且为整数0,1430652)1(5min2111212121xxxxxxxxIPxxZ且为整数0,2430652)2(5min2111212121xxxxxxxxIPxxZ现在只要求出（LP1）和（LP2）的最优解即可。x1x2⑴⑵33(18/11,40/11)⑶先求（LP1）,如图所示。此时B在点取得最优解。x1＝1,x2=3,Z(1)＝－16找到整数解，问题已探明，此枝停止计算。11同理求（LP2）,如图所示。在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z2Z1＝－16∴原问题有比（－16）更小的最优解，但x2不是整数，故利用x2≤3,x2≥4加入条件。BAC加入条件：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≈-19.8但x1＝12/5不是整数，可继续分枝。即3≤x1或x1≤2。D求（LP4），如图所示。无可行解，不再分枝。在（LP3）的基础上继续分枝。加入条件3≤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－1整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1，一般的解法为隐枚举法。例一、求解下列0－1规划问题10,,(4)64(3)3(2)44(1)22523max3213221321321321或xxxxxxxxxxxxxxxxZ三、0－1整数规划解：对于0－1规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。x1.x2.x3约束条件满足条件Z值(1)(2)(3)(4)是∨否×(0.0.0)0000∨0(0.0.1)－1101∨5(0.1.0)2414∨－2(1.0.0)1110∨3(0.1.1)15×(1.0.1)0211∨8(1.1.0)3×(1.1.1)26×由上表可知，问题的最优解为X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一个可行解，为尽快找到最优解，可将3x1－2x2＋5x3≥5作为一个约束，凡是目标函数值小于5的组合不必讨论，如下表。x1.x2.x3约束条件满足条件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)00000∨0(0.0.1)5－1101∨5(0.1.0)-2×(0.1.1)3×(1.0.0)3×(1.0.1)80211∨8(1.1.0)1×(1.1.1)4×例二、求解下列0－1规划问题4.3.2.11,05356461273max421432143214321jxxxxxxxxxxxxxxxxZj解：由于目标函数中变量x1,x2,x4的系数均为负数，可作如下变换：令x1＝1－x1′,x2=1-x2′,x3=x3′,x4=1-x4′带入原题中，但需重新调整变量编号。令x3′=x1′,x4′=x2′得到下式。10,,,435246121173max4321432432143214321或xxxxxxxxxxxxxxxxxxxZ可以从(1.1.1.1)开始试算，x′(3)＝(1.1.0.1)最优解。∴x(3)＝(1.0.1.0)是原问题的最优解，Z*=－2例三、求解下列0－1规划问题