运筹学(五)解决方案.ppt

第五章 整 数 规 划 主要内容： 第一节 整数规划的数学模型及解的特点 第二节 解纯整数规划的割平面法 第三节 分支定界法 第四节 0-1型整数规划 第五节 指派问题 第一节 整数规划的数学模型及解的特点 一、整数规划问题举例 例1（纯整数规划） ：某个中型百货商场对售货人员（周工资200元）的需求经统计如下表： 为了保证销售人员充分休息，销售人员每周工作5天，休息2天（这两天是连续的）。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？ 例2（0-1整数规划） ：某公司有5个投资项目被列入投资计划，各项目需要的投资额和期望的收益见下表： 已知该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束： （1）项目1、项目2和项目3至少应有一项选择； （2）项目3和项目4最多只能选一项； （3）项目5选中的前提是项目1必须选中。 问如何选择一个最好的投资方案使得总的投资收益最大。 二、整数规划问题的数学模型 三、整数规划问题的解的特点 第二节 求解纯整数规划的割平面法 一、割平面法的思路 1、求出整数规划问题的松弛问题的最优解。 2、若得到最优解满足整数要求，则该最优解就是整数规划问题的最优解； 若最优解不满足整数要求，则增加一个约束条件（建立割平面方程），使得最优解不满足该约束条件，而所有的整数规划的可行解仍满足该约束条件。 3、重新求解增加约束条件后的最优解，回到2。 二、割平面法计算步骤 例：用割平面法求解纯整数规划 三、注意 整数规划模型的约束条件中，若约束条件中变量的系数或右端常数取值不为整数时，首先要把它们变为整数） 第三节 分 支 定 界 法 一、分支定界法的思路 分支：若整数规划的松弛问题的最优解不符合整数要求，假设 不符合整数要求， 是不超过 的最大整数，则构造两个约束条件： 和 ，分别将其并入松弛问题中，从而形成两个后继问题，即两个分支。 二、分支定界法的步骤 解：（1）求解其松弛问题。得到最优解 (3/2,10/3)，不满足整数要求。 （2）分支。 选择x1=3/2进行分支。 上述求解过程可以总结如下图： 第四节 0-1 整 数 规 划 一、0-1规划的举例 1、选址问题（布点问题） 二、0-1整数规划的解法 完全枚举法 隐枚举法 第五节 指 派 问 题 一、标准形式的指派问题及其数学模型 二、匈牙利解法 三、非标准形式的指派问题 1、最大化指派问题 2、人数和事数不相等的指派问题 3、一个人可以做几件事情的问题 4、某事一定不能由某人来做的指派问题  构造两个约束条件：x1≤1和x1≥2进行分支。 x1 x2 （1，7/3） B C（2，23/9） S1 S2 得到两个后继问题：LP1和LP2。 （3）继续分支。 因为LP1和LP2所得到的最优解都不满足整数要求，需要继续分支。考虑到LP2的最优解对应的目标函数值较大些，因此，选择LP2进行分支。 LP2最优解中x2=23/9不满足整数要求，需要进行分支。构造两个约束条件：x2≤2和x2≥3 x1 x2 （1，7/3） B D（33/14，2） S1 S21 得到两个后继问题：LP21和LP22。 （4）继续分支。 LP22无可行解；LP21所得到的最优解（33/14，2）不满足整数要求，需要继续分支。考虑到LP21的最优解对应的目标函数值较大些，因此，选择LP21的x1进行分支。 构造两个约束条件：x1≤2和x1≥3. x1 x2 （1，7/3） B F（2，2） S1 S212 S211 E（3，1） 得到两个后继问题：LP211和LP212。 （5）定界 LP211和LP212所得到的最优解（2，2）和（3，1）都满足整数要求，且对应的目标值相同，都为4，因此可以给目标函数定下界4。 考虑LP1，其最优解对应的目标函数为10/3，小于下界4，因此不用对其进行分支。 所以，该整数规划问题的最优解为（2，2）和（3，1） 。 S S1 S2 S21 S22 S211 S212 要选取投资场所，已知： c7 b7 A7 c6 b6 A6 南区 c5 b5 A5 c4 b4 A4 西区 c3 b3 A3 c2 b2 A2（最多选两个点） B c1 b1 A1 东区 总资金 （元） 年利润（元） 投资（元） Ai可供选择的点 区名 （至少选一个点） （至少选一个点） 问如何布点，使