运筹学(第5章割平面)_

1、第五章整数规划 51整数规划模型 52纯整数规划的割平面 法 54分支定界法 57最优分配问题 本章基本要求 v掌握整数规划的数学模型的建摸技巧； v掌握0-1规划模型 v了解割平面公式； v掌握分支定界法； v掌握匈牙利法解决最优分配问题。 整数规划 v整数规划：决策变量全体或部分约 束为整数的数学规划问题. v整数规划又分线性整数规划和非线 性整数规划. v线性整数规划也叫整数线性规划 (ILP),简称整数规划,简记(IP). 整数线性规划的分类 v纯整数规划:所有的决策变量均取整 数.简记（） v混合整数规划:只有部分决策变量取 整数值.简记（） v0-1整数规划:整数变量只能取0或1.

2、 简记（） 问题 1、去掉整数约束的规划问题 的最优解与整数规划的最优 解有何关系？ 2、如何建立整数规划模型？ 如何求解整数规划问题？ 例5-1 求解整数规划 (1.5, 3.33) 最优值是最优值是-4.83 v放松整数约束得到的线性规划问题 为该整数规划松弛问题 v任何一个整数规划都可以看成是一 个线性规划松弛问题再加上整数约 束构成 v整数规划的可行域是线性规划松弛 问题可行域的一个子集. 整数规划最优解和线性规划 松弛问题最优解的关系 v对于最大化问题 松弛问题最优解整数规划最优解 v对于最小化问题 松弛问题最优解整数规划最优解 5.1整数规划模型 1、固定费用问题 2、选择性约束条

3、件 固定费用问题 例5-2某工厂生产1#、2#和3#三种产 品，每种产品需经过三道工序，有关 信息如下表所示。若j#产品投产，无论 产量大或小，都需要一笔固定的费用dj， 问每种产品各生产多少，可使这一周 内生产的产品所获利润最大?试建立整 数规划模型 若固定费用dj: 100 ， 200 ， 150 定额 （工时/件） j# 每周可利用 有效工时 1#2#3# 工序A1.21.0 1.1 5400 B0.70.9 0.6 2800 C0.90.8 1.0 3600 利润（元/件） Cj 101512 工厂生产信息表工厂生产信息表 解解 设一周内设一周内j产品的生产件数为产品的生产件数为xj

4、若不考虑固定费用若不考虑固定费用 max f= 10 x1+15x2+12x3 s.t . 1.2x1+1.0 x2 +1.1x3 5400 0.7x1+0.9x2 +1.0 x3 2800 0.9x1 +0.8x2+ 1.0 x33600 xj0, j=1,2,3. 又设又设0-1变量变量 本问题的数学模型（本问题的数学模型（ 考虑固定费用考虑固定费用 ） max f= 10 x1+15x2+12x3-100y1-200y2-150y3 s.t . 1.2x1+1.0 x2 +1.1x3 5400 0.7x1+0.9x2 +1.0 x3 2800 0.9x1 +0.8x2+ 1.0 x336

5、00 xj0, j=1,2,3. 其中其中M为充分大的正数为充分大的正数 1,0 12 3 0 j j x yj 当， ， ， ，否则， 12 3 jj xMyj， ， 选择性约束条件选择性约束条件 例例5-3某工厂生产第某工厂生产第j种产品的数量为种产品的数量为 xj,j=1,2,3.其使用的材料在材料甲及材料乙中其使用的材料在材料甲及材料乙中 选择一种选择一种。材料消耗的约束条件分别为。材料消耗的约束条件分别为 2x1+5x2 +6x3 180或或 4x1+3x2 +7x3 240， （其他资源未列出），试问这类选择性约束条（其他资源未列出），试问这类选择性约束条 件如何体现在模型中？件如

6、何体现在模型中？ 0, 1 y 选择材料甲， ，否则。 约束条件约束条件 2x1+5x2 +6x3 180+My 4x1+3x2 +7x3 240+M(1-y) 其中其中M为充分大的正数为充分大的正数 解解 引进引进0-1变量变量 例例5-10 旅行售货员问题旅行售货员问题 P151 52 纯整数规划的割平面法 521割平面法的几何特征 记（AIP）的可行域为KAIPAIP。若将（AIP）中 要求变量为整数这个约束去掉，则得到相应的 线性规划（LP），记（LP）的可行域为KLPLP。 例5-13求解下列（AIP）： min f= -7x1-9x2 s.t. -x1 +3x2 6 7x1 + x

7、2 35 xj0, 整数， j=1,2。 介绍一些相关概念介绍一些相关概念 522 柯莫利割柯莫利割 设设B为为(LP)的一个基，的一个基，X为为(AIP)的一个可的一个可 行解由行解由KAIP KLP，所以，所以x也是也是(LP)的一个的一个 可行解，因此，可行解，因此，x应满足单纯形表应满足单纯形表T(B)所表示所表示 的方程组：的方程组： (1) 该条件是该条件是(AIP)任何一个可行解任何一个可行解x必须满足的必须满足的 条件，我们称它为条件，我们称它为柯莫利割柯莫利割 (2) (1)-(2)得： 例5-14用割平面法求解例513 min f= -7x1-9x2 s.t. -x1 +3

8、x2 6 7x1 + x2 35 xj0, 整数， j=1,2。 解引进松弛变量x3和x4，将问题化成标准型： min f= -7x1-9x2 s.t. -x1 +3x2 + x3 = 6 7x1 + x2 + x4 = 35 xj0, 整数， j=1,，4。 因为松弛变量 x3=6+ x1-3x2，x4=35-7xl-x2， 所以当x1和x2为整数时，x3和x4也一定是整数 应用单纯形法求解相应的线性规划(LP)，得最优表 （5-23）（5-24） 应用对偶单纯形法应用对偶单纯形法 于是，X*=（x1，x2）T=（4，3）T 最优值f*=-55。 5.2.3柯莫利割平面法 v割平面法的基本思路：先用单纯形法解松弛问题， 得最优解0，如果0是整数，则问题已经解决， 如果不全是整数，给松弛问题一个线性约束条件 割平面方程，它将松弛问题的可行域割去一块， 且这个0恰被割去,原问题的可行解都不会被割去. 把松弛问题的最优表添加割约束,得改进的松弛问 题,用对偶单纯形法求解,直至最优解为整数为止.