混合整数线性规划

1、混合整数线性规划张冰hbingjmaiLsysii 优化问题的一般形式优化问题三要素：决策变量；目标函数；约束条件_r:一目标函数 min /(x)约束条件s.t. hf(x) = 0,z = 1，mg jM 0, j = 1,，/一决策变量g D cz 9? 7变量类型C连续变量：温度、压力和流程等，通常称为操作变量决策变量Y离散变量：设备和流程选择 等，通常称为结构变量5整数规划问题整数规划问题(IP):是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的 目标函数和约束条件构成的规划问题。学习重点：整数线性规划问题(MIP)ma

2、x(min)Z =c jxj= inE a ij x j 5( = )b i7=1n 巧中取部分或全部为整数若变量全部取整数，称此为纯整数规划。若其中 仅部分变量要求取整数，则称为混合整数规划，其解 法较一般线性规划的解法要复杂些。9背包问题(Knapsack Problem)一个旅行者，为了准备旅行的必须用品，要在背包内装一些最有用的东西，但有个限制，最 多只能装b公斤的物品,而每件物品只能整个 携带，这样旅行者给每件物品规定了一个“价值”以表示其有用的程度，如果共有n件物品,第j件物品aj公斤，其价值为q.问题变成:在 携带的物品总重量不超过b公斤条件下，携带 哪些物品，可使总价值最大？/

3、11解：如果令Xj=l表示携带物品j, Xj=O表示不携带物品j,则问题表 示成Q-1规划：Max Z = E CjXjs. t. EajXj bXj=O 或 1解法概述 当人们开始接触整数规划问题时，常会 有如下两种初始想法： 因为可行方案数目有限，因此经过一一 比较后，总能求出最好方案，例如，背 包问题充其量有21种方式；实际上这种 方法是不可行。13假设有35件物品,计算机每秒能比较10000个方式,那么要比较完234种方式，大约需要20天!先放弃变量的整数性要求，解一个 线性规划问题，然后用“四舍五入” 法取整数解，这种方法，只有在变 量的取值很大时，才有成功的可能 性，而当变量的取值

4、较小时，特别 是0-1规划时，往往不能成功。可行域OABD内整数点，放弃整数要求后，最优 解B(92, 2. 4)Z0=58. 8,而原整数规划最优解1(2, 4)Z0=58 ,实际上B附近四个整点(9, 2) (10, 2) (9, 3) (10, 3)都不是原规划最优解。max z = 5% +8x2s.t. X + x9 65x +9x2 0且为整数去掉整数限制后，可行域为点(0,0)，(6,0)，(0,5)，P (2.25,3-75)围成的4边形IP最优解pP的舍入解最靠近P的可行解IP最优解(2.25, 3.75)(2, 4)(2, 3)(0, 5)z=41.25不可行z=34z=4

5、O假如能求出可行域的“整点凸包，(包含所有整点的最小多边形OEFGHIJ),则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包，十分困难。X221整数规划问题对应的松弛问题取消整数规划中决策变量为整数的限制（松弛），对 应的连续优化问题称为原问题的松弛问题整数规划问题松弛1 f松弛问题原问题松弛丿最优解.优整数非整数下界（对Min问题）上界（对Max问题）混合整数线性规划的分支定界法（BB: Branch and Bound ）基本思想：隐式地枚举一切可行解（“分而治之”）所谓分支，就是逐次对解空间（可行域）进行划分；而 所谓定界，是指对于每个分支（或称子域）,要计算原 问题的最优解

6、的下界（对极小化问题）.这些下界用来 在求解过程中判定是否需要对目前的分支进一步划分, 也就是尽可能去掉一些明显的非最优点，避免完全枚举.对于极小化问题，在子域上解LP,其最优值是IP限定 在该子域时的下界；IP任意可行点的函数值是IP的上界23定界：为求解纯整数规划和混合整数规划问 题(A),先求出其松弛问题(B)的最优解， 作为问题A的最优目标函数值的下界，同时 选择任意整数可行解作为A的最优目标函数 值的上界。分支：将应为整数解，但尚是非整数解之一 的决策变量取值分区，并入松弛问题中，形 成两个分支松弛问题，分别求解。依结果考 调整上下界。JImin z =坷 + 3x2 x2 3.13

7、R: 8.12 和兀1 9和X1 9R、: 3.1322兀 +34%n 285Xj 8R2: 3.1322jT +34x2 285（2 ）在尺内求最优，得:= 9,x2 = 3.13, zmin = LB2 = 18.39#(3) 同样地，在 鸟内求最优，得：坷二& 兀2 = 3.12, zmin = LB3 = 17.62(4) 由于(2)、(3)所得的解都不是整数解，且S VLB?,所以乙価在&内的值就可能比在尺 内的值小，于是进一步将尽分成两个区域,注意到 由(3)所得的非整数解西=3.21 ,且要求勺是整数，曹 对尺追加条件2 4和勺3,对应地将 尺分成坨1 和 22(5) 求出R2X

8、内的最优解：円=6.77 心=4，贏=LB4 =18.77(在R22中因新的约束x2 3.13 解.矛盾，故R22(6) 对区域K和/?21进行比LB24和兀23,对应地得到两个约束区域:xx9x2 3.1322 + 34兀2 285Rj%! 9 x9 3.1322xj + 34x2 285(7) 尽2显然无可行解，在中的最优解是：西=7,花=4,牯=LB5 =21这个解满足整数解的条件，但是否是最优解 呢？因有lb4lb5 ,故最优解可能位于心 中.对心分别追加条件旺7和x6 ,心又 分成两不局部区域7?211和尺212。人211中的最优解是：= 7, x2 = 4,4山=LB& = 19尺

9、212的最优解是：兀=6,吃=4.5, Zmjn = LB-j 19.5可见，凡11中的最优解满足整数条件。同时,目标函数的下限值LB.比其它局部区域的下限值小，即:LB6 LB LB5所以人212或没有必要进一步搜索, 因此，最后得到所求的最优整数解为：兀7，；2 =4,务=感=19MaxZ=4 Oxt+90x 29x7x2 W56 7x1+20x2 70 xpx20xpx2 都为整数35问题BZ=356x2=4.81 9x2=L82 Z=356问题Bx1=4x2=2.1 Z=349问题B 2Xj=5 2=1.57 Z-341Z=349Z=0问题B3兀1=4, x2=2 Z=340问题B4 x i=1.42 工2=3 Z=327问题B5 x 1=544 兀2=1 Z=308Z=349Z=340问题 6 无可行 解ZJ34037作业:现有资金总额为。可供选择购买的化工产品有兀#个，产品j的价格和预期利润分别为幻和q,此外, 因供货商对产品的采购约束，有3个附加条件： 第一，若选择产品1必须同时选择项目2,反之,