混合整数线性规划

1混合整数线性规划张冰剑[e-mail]第二篇过程优化2优化问题三要素：决策变量；目标函数；约束条件约束条件决策变量优化问题的一般形式njiDxljxgmixhtsxfℜ⊆∈=≤==,...,1,0)(,...,1,0)(..)(min目标函数3决策变量连续变量：温度、压力和流程等，通常称为操作变量离散变量：设备和流程选择等，通常称为结构变量变量类型4整数规划问题整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。学习重点：整数线性规划问题(MIP)5若变量全部取整数，称此为纯整数规划。若其中仅部分变量要求取整数，则称为混合整数规划，其解法较一般线性规划的解法要复杂些。jnjjxcZ∑==1max(min)⎪⎩⎪⎨⎧≥=≥≤∑=0),(1jinjjijxbxaxj中取部分或全部为整数6一个旅行者一个旅行者,,为了准备旅行的必须用品为了准备旅行的必须用品,,要在要在背包内装一些最有用的东西背包内装一些最有用的东西,,但有个限制但有个限制,,最最多只能装多只能装bb公斤的物品公斤的物品,,而每件物品只能整个而每件物品只能整个携带携带,,这样旅行者给每件物品规定了一个这样旅行者给每件物品规定了一个““价价值值””以表示其有用的程度以表示其有用的程度,,如果共有如果共有nn件物品件物品,,第第jj件物品件物品aajj公斤公斤,,其价值为其价值为ccjj..问题变成问题变成::在在携带的物品总重量不超过携带的物品总重量不超过bb公斤条件下公斤条件下,,携带携带哪些物品哪些物品,,可使总价值最大可使总价值最大??背包问题(KnapsackProblem)7解：解：如果令如果令xxjj=1=1表示携带物品表示携带物品jj，，xxjj=0=0表示不携带物品表示不携带物品jj，，则问题表则问题表示成示成00--11规划规划::MaxZ=MaxZ=ΣΣccjjxxjjs.t.s.t.ΣΣaajjxxjj≤≤bbxxjj=0=0或或118解法概述解法概述当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背比较后，总能求出最好方案，例如，背包问题充其量有包问题充其量有22nn--11种方式；实际上这种种方式；实际上这种方法是不可行。方法是不可行。9假设有假设有3535件物品，计算机每秒能件物品，计算机每秒能比较比较1000010000个方式，那么要比较完个方式，那么要比较完223434种方式，大约需要种方式，大约需要2020天！天！10先放弃变量的整数性要求，解一个先放弃变量的整数性要求，解一个线性规划问题，然后用线性规划问题，然后用““四舍五入四舍五入””法取整数解，这种方法，只有在变法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别性，而当变量的取值较小时，特别是是00--11规划时，往往不能成功。规划时，往往不能成功。11O1234567891054321xx11xx22I(2,4)B(9.2,2.4)AD可行域可行域OABDOABD内整数点，放弃整数要求后，最优内整数点，放弃整数要求后，最优解解B(9.2,2.4)ZB(9.2,2.4)Z00=58.8=58.8，，而原整数规划最优而原整数规划最优解解I(2,4)ZI(2,4)Z00=58=58，，实际上实际上BB附近四个整点附近四个整点(9,2)(10,2)(9,3)(10,3)(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。都不是原规划最优解。12且为整数0,45956..85max21212121≥≤+≤++=xxxxxxtsxxz．．．．．．．．．．．．．．．．．．．x1x20Po69Zmax56去掉整数限制后，可行域为点（0,0),(6,0),(0,5),P(2.25,3.75)围成的4边形LP最优解PP的舍入解最靠近P的可行解IP最优解（2.25，3.75）（2，4）（2，3）（0，5）z=41.25不可行z=34z=40从LP最优解经过简单的“移动”不一定得到IP最优解13O1234567891054321xx11xx22I(2,4)B(9.2,2.4)AD假如能求出可行域的假如能求出可行域的““整点凸包整点凸包””（包含所有整（包含所有整点的最小多边形点的最小多边形OEFGHIJOEFGHIJ），），则可在此凸包上则可在此凸包上求线性规划的解，即为原问题的解。但求求线性规划的解，即为原问题的解。但求““整整点凸包点凸包””十分困难。十分困难。EEFFGGHHIIJJ14取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入下界（对Min问题）上界（对Max问题）非最优解原问题松弛15基本思想：隐式地枚举一切可行解（“分而治之”）所谓分支，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分支（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分支进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.混合整数线性规划的分支定界法（BB:BranchandBound）对于极小化问题，在子域上解LP，其最优值是IP限定在该子域时的下界；IP任意可行点的函数值是IP的上界16定界：为求解纯整数规划和混合整数规划问题(A)，先求出其松弛问题（B）的最优解，作为问题A的最优目标函数值的下界，同时选择任意整数可行解作为A的最优目标函数值的上界。分支：将应为整数解，但尚是非整数解之一的决策变量取值分区，并入松弛问题中，形成两个分支松弛问题，分别求解。依结果来调整上下界。171221212min33.13:2234285,zxxxRxxxx=+≥⎧⎪+≥⎨⎪⎩为非负整数解：（１）忽略是整数这一条件，求得最优解为：12xx，12min8.123.1317.5xxz===，，18这不是整数解。于是，可将R中与有关的区域分成两个区域，即把和。因要求取整数，所以这两个局部约束区域也可写成整数形式和。1x12RR、18.12x≥19x≥18x≤18.12x1x19112129:3.132234285xRxxx≥⎧⎪≥⎨⎪+≥⎩122128:3.132234285xRxxx≤⎧⎪≥⎨⎪+≥⎩（２）在内求最优，得：1R12min29,3.13,18.39xxzLB====20(4)由于(2)、(3)所得的解都不是整数解，且,所以在内的值就可能比在内的值小,于是进一步将分成两个区域,注意到由(3)所得的非整数解,且要求是整数,故对追加条件和,对应地将分成和.(3)同样地，在内求最优，得：2R12min38,3.12,17.62xxzLB====32LBLBminz2R1R2R23.21x=2x2R24x≥23x≤21R2R22R21(5)求出内的最优解:21R12min46.77,4,18.77xxzLB====(在中因新的约束和原有的约束矛盾,故中没有可行解.23x≤23.13x≥22R22R22(6)对区域和进行比较,有,所以应转向在中搜索,因中的非负整数解,把分为和,对应地得到两个约束区域:1R21R24LBLB1R1R23.13x=1R24x≥23x≤211121249:3.132234285xxRxxx≥⎧⎪≥⎪⎨≥⎪⎪+≥⎩211221239:3.132234285xxRxxx≤⎧⎪≥⎪⎨≥⎪⎪+≥⎩23(7)显然无可行解,在中的最优解是:这个解满足整数解的条件,但是否是最优解呢?因有,故最优解可能位于中.12R11R21R12min57,4,21xxzLB====45LBLB24(8)对分别追加条件和,又分成两个局部区域和。中的最优解是：的最优解是：12min76,4.5,19.5xxzLB====212R211R12min67,4,19xxzLB====17x≥16x≤21R21R211R212R25可见，中的最优解满足整数条件。同时，目标函数的下限值比其它局部区域的下限值小，即：所以或没有必要进一步搜索，因此，最后得到所求的最优整数解为：12min67,4,19xxzLB====6LB11R675LBLBLB211R212R26举例x1,x2都为整数MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥027问题Bx1=4.81,x2=1.82Z=356Z=356Z=0问题B1x1=4,x2=2.1Z=349问题B2x1=5,x2=1.57Z=341x1≤4x1≥5Z=349Z=0x2≤2x2≥3问题B3x1=4,x2=2Z=340问题B4x1=1.42x2=3Z=327Z=349Z=340x2≤1x2≥2问题B5x1=5.44x2=1Z=308Z*=340问题B6无可行解28作业：现有资金总额为B。可供选择购买的化工产品有n个，产品j的价格和预期利润分别为aj和cj,此外，因供货商对产品的采购约束，有3个附加条件：第一，若选择产品1必须同时选择项目2，反之，不一定；第二，产品3和产品4中至少选择一个；第三，产品5、6、7中恰好选择两个。应当怎样选择购买产品，才能使总预期收益最大？291购买产品j0不购买产品jxj=MaxZ=∑cjxj∑ajxj≤Bx2≥x1x3+x4≥1x5+x6+x7=2xj=0或1（j=1,2,…n）30结束！