运筹学(第5章割平面)_解决方案.ppt

第五章　整数规划 §5·1整数规划模型 §5·2纯整数规划的割平面法 §5·4分支定界法 §5·7最优分配问题 本章基本要求 掌握整数规划的数学模型的建摸技巧； 掌握0-1规划模型 了解割平面公式； 掌握分支定界法； 掌握匈牙利法解决最优分配问题。 整数规划 整数规划：决策变量全体或部分约束为整数的数学规划问题. 整数规划又分线性整数规划和非线性整数规划. 线性整数规划也叫整数线性规划(ILP),简称整数规划,简记(IP). 整数线性规划的分类 纯整数规划:所有的决策变量均取整数.　简记（ＡＩＰ） 混合整数规划:只有部分决策变量取整数值.　简记（ＭＩＰ） 0-1整数规划:整数变量只能取0或1.　　简记（ＢＩＰ） 问　题 例5-1 求解整数规划 放松整数约束得到的线性规划问题为该整数规划松弛问题 任何一个整数规划都可以看成是一个线性规划松弛问题再加上整数约束构成 整数规划的可行域是线性规划松弛问题可行域的一个子集. 整数规划最优解和线性规划松弛问题最优解的关系 对于最大化问题 松弛问题最优解≥整数规划最优解 对于最小化问题 松弛问题最优解≤整数规划最优解 §5.1整数规划模型 1、固定费用问题 2、选择性约束条件 １．固定费用问题 　例5-2　某工厂生产1#、2#和3#三种产品，每种产品需经过三道工序，有关信息如下表所示。若j#产品投产，无论产量大或小，都需要一笔固定的费用dj，问每种产品各生产多少，可使这一周内生产的产品所获利润最大?试建立整数规划模型． 若固定费用dj: 100 ， 200 ， 150 解 设一周内j产品的生产件数为xj 若不考虑固定费用 max f= 10x1+15x2+12x3 s.t . 1.2x1+1.0x2 +1.1x3 ≤5400 0.7x1+0.9x2 +1.0x3≤ 2800 0.9x1 +0.8x2+ 1.0x3≤3600 xj≥0, j=1,2,3. 　　又设0-1变量 本问题的数学模型（ 考虑固定费用 ） max f= 10x1+15x2+12x3-100y1-200y2-150y3 s.t . 1.2x1+1.0x2 +1.1x3 ≤5400 0.7x1+0.9x2 +1.0x3≤ 2800 0.9x1 +0.8x2+ 1.0x3≤3600 xj≥0, j=1,2,3. 其中M为充分大的正数 ２．选择性约束条件 　例5-3　某工厂生产第j种产品的数量为xj,j=1,2,3.其使用的材料在材料甲及材料乙中选择一种。材料消耗的约束条件分别为 2x1+5x2 +6x3 ≤180或 4x1+3x2 +7x3≤ 240， （其他资源未列出），试问这类选择性约束条件如何体现在模型中？ §5·2 纯整数规划的割平面法 　5．2．1割平面法的几何特征 　　记（AIP）的可行域为KAIP。若将（AIP）中要求变量为整数这个约束去掉，则得到相应的线性规划（LP），记（LP）的可行域为KLP。 　 例5-13　求解下列（AIP）： 　　　　　min f= -7x1-9x2 　　　　s.t. -x1 +3x2 ≤6 　　　　　　7x1 + x2 ≤35 　　　xj≥0, 整数， j=1,2。 5．2．2 柯莫利割 　　　设B为(LP)的一个基，X为(AIP)的一个可行解．由KAIP KLP，所以x也是(LP)的一个可行解，因此，x应满足单纯形表T(B)所表示的方程组： 　例5-14用割平面法求解例5－13 min f= -7x1-9x2 s.t. -x1 +3x2 ≤6 7x1 + x2 ≤35 xj≥0, 整数， j=1,2。 解　引进松弛变量x3和x4，将问题化成标准型： min f= -7x1-9x2 s.t. -x1 +3x2 + x3 = 6 7x1 + x2 + x4 = 35 xj≥0, 整数， j=1,…，4。 因为松弛变量 x3=6+ x1-3x2，x4=35-7xl-x2， 所以当x1和x2为整数时，x3和x4也一定是整数． 应用单纯形法求解相应的线性规划(LP)，得最优表． 5.2.3　柯莫利割平面法 割平面法的基本思路：先用单纯形法解松弛问题，得最优解Ｘ0，如果Ｘ0是整数，则问题已经解决，如果不全是整数，给松弛问题一个线性约束条件－－割平面方程，它将松弛问