四运筹学整数规划.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 山东工商学院 * 习题讨论课 已知某运输问题的产销平衡表和单位运价表，数据如下： 销地 产地 B1 B2 B3 B4 产量 A1 10 1 20 11 15 A2 12 7 9 20 25 A3 2 14 16 18 5 销量 5 15 15 10 （1）求此运输问题的最优调运方案。 （2）从A2-B2的单位运价c22在什么范围变化 时，上述最优调运方案不变？ 山东工商学院 * 例 甲、乙、丙三个城市每年需要煤炭320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量为A—400；B—450万吨。由煤矿至各城市的单位运价如表；由于需大于供，甲城市供应可以减少0~30万吨；乙城市供应全部满足，丙城市供应不少于270万吨。试求最优调运方案。 销地 产地 甲 乙 丙 产量 A 15 18 22 400 B 21 25 16 450 销量 320 250 350 山东工商学院 * 已知某运输问题的产销平衡表和单位运价表，数据如下 山东工商学院 * 有4个工人，分配4项工作，每人做每项工作消耗的时间如表；如何分配使得消耗时间最少 任务 人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 山东工商学院 * 任务 人 A B C D E 甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 分配甲、乙、丙、丁四个人去完成5项任务。每人完成各项任务的时间如表所示。由于任务数多于人数，故规定有一个人可以兼完成两项任务，其余三人每人一项，试确定最优指派方案。 山东工商学院 * 求下列具有最大利润的指派问题： 利润 B1 B2 B3 B4 B5 A1 3 2 1 3 4 A2 4 3 2 3 5 A3 5 4 3 6 4 A4 6 6 3 7 6 A5 7 6 6 4 3 * * * * * * * * * * * * * * * * * * * * * * * * * * 山东工商学院 * B点仍然不是整数解，再增加一个约束 x1+x2≤4，则对应LP 问题的可行域进一步 缩小，如图 5.11 所示，可见在C点达到最大： x1=3,x2=1,Z=22 。 C点是整数点，它正是所要求的整数最优解。 山东工商学院 * A x2 x1 1 4 3 2 1 3 2 4 0 B 3x1+4x2 ≤ 15 5 6 C 图5.11 山东工商学院 * 由于整数规划的可行解集是由对应(LP)问题的可行域内的全部整数点所组成的。若 (LP)问题得最优解是可行域内的整数点，则此解亦为(IP)问题的最优解，若不是整数点，则增加一个约束条件得到缩小的可行域，在图上犹如切割掉了可行域的某一部分边缘区域（要求整数点不会被切割掉）这样做下去，直到使目标函数达到最优的整数点，出现在新可行域的顶点上。 对于二维问题，新增加的约束条件是一条直线。对于三维问题而言，新增加的约束就是一个平面。而三维以上就称之为超平面。由于每增加一个约束就相当于对原有各个约束条件所构成的凸集进行一次切割，因此，称这种解法为割平面法 山东工商学院 * 割平面法的关键在于如何选取割平面，才能使切割的部分只包含非整数解，而不切割掉任何整数可行解。下面介绍怎样产生割平面 一、基本原理 山东工商学院 * 如果某决策变量的最优解不为整数，不妨设： 则松弛问题最优单纯形表中，该决策变量所对应的方程可表示为： 该方程中系数分解为整数部分和非负小数部分之和的形式，即： [br]等表示小于等于该系数的最大整数。 显然： 将分解式代入决策变量所对应的方程。 山东工商学院 * 根据整数的要求，由于等式左边为整数，等式右边也应为整数。又由于 整数解的必要条件 割平面方程！ 可以证明，构造的割平面对可行域进行切割，可以割去非整数最优解，但又不会割去整数规划的整数可行解。 逐步增加类似的割平面方程，解松弛规划，直至整数解。 山东工商学院 * 割平面法应用案例 Maxz=X1+X2 ﹣ X1 +X2≤1 ﹣ 3X1+X2≤4 X1, X2 =0且为整数 松弛问题: Maxz=X1+X2 ﹣ X1 +X2≤1 ﹣3X1+X2≤4 X1, X2 ≥0 步骤： 1、求松弛问题最优解：最终表见下页 2、增加约束条件切割松弛问题可行域， 山东工商学院 * Xb b X1