运筹学-整数规划方案(-Integer--Programming-).ppt

运 筹 学( Operations Research ) Chapter4 整数规划( Integer Programming ) 整数规划的特点及应用 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。 整数规划的特点及应用 整数线性规划问题的种类： 整数规划的特点及应用 整数规划的典型例子 整数规划的特点及应用 整数规划的典型例子 整数规划的特点及应用 解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量： 整数规划的特点及应用 整数规划的特点及应用 例4.3 指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 整数规划的特点及应用 整数规划的特点及应用 每项工作只能安排一人，约束条件为： 整数规划的特点及应用 整数规划问题解的特征： 整数规划的特点及应用 例4.3 设整数规划问题如下 整数规划的特点及应用 x2 图解法的启示： ① A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解 ②纯整数规划的可行解就是可行域中的整数点 ③非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化 IP问题的最优解不优于LP问题的最优解 整数规划的特点及应用 整数规划问题的求解方法： 分支定界法 1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步； 2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束： xi≤[xi] 和 xi≥[xi]+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。 分支定界法 例4.4 用分枝定界法求解 分支定界法 分支定界法 分支定界法 分支定界法 分支定界法 上述分枝过程可用下图表示： 小结 0-1型整数规划 0-1变量的引入 例1：某公司拟在市东、西、南三区建立门市部。拟议中有7个位置Ai（i=1，2，3，4，5，6，7）可供选择。规定：（1）在东区，A1，A2，A3三个点中最多选两个。（2）在西区，A4，A5两个点中至少选一个。（3）在南区，A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不超过B元。问应选择哪几个点可使年利润为最大？ 0-1型整数规划 解：引入变量xi（i=1，2，3，4，5，6，7）令 建立模型： 0-1型整数规划 例2：某油田开发公司打算在10个有油气构造处选若干个钻井采油。应满足的条件如下，试写出下列约束条件： （1）若开采8号，必须开采6号，但开采6号，不一定 开采8号 （2）若开采5号，不许开采3号，反过来也一样 （3）8号和7号必须同时开采 （4）2号和4号至少开采一个 （5）1号，4号，6号，9号开采时最多不能超过两个 0-1型整数规划 例3：表示选择性约束 (1) m个约束条件只有k个起作用（k≤m） 0-1型整数规划 (2)约束条件右端项可能是m个值中的某一个 0-1型整数规划 例4：设目标函数 ，试表示目标函数。 0-1型整数规划 Exercise:试用0-1变量对下列各题分别表示成一般线性约束条件 解法：隐枚举法 若0-1规划问题有n个0-1变量，则会产生2n个变量取值组合。 例: 试探法找一可行解（0 0 1 ），Z=5。则最大值≥5。我们可以增加约束条件 3X1-2X2+5X3 ≥5, 不满足这个过滤条件的变量取值组合立刻被淘汰，不必再判断是否满足原约束条件。 0-1型整数规划 分配问题