运筹第四章整数规划与分配问题.ppt

第四章 整数规划与分配问题 第一节 整数线性规划问题 1. 问题的提出 2. 整数规划问题的特征与性质 3. 整数规划的分类 第二节 分配问题（Assignment Problem） 1. 问题的提出及数学模型 2. 分配问题的匈牙利解法 匈牙利方法的基本思想 匈牙利解法的基本步骤 例2：用匈牙利解法解本节例1 课堂练习：求解下列分配问题 两点说明 分配问题的求解软件（WINQSB） 作业： 第二节 分枝定界法（Branch and Bound Method） 例6：求解下列整数线性规划问题 分枝的方法 定界的方法 第四节：割平面解法 0 5 3 8 0 4 0 0 0 3 1 4 0 4 0 8 11 0 0 3 4 2 2 0 7 它有5个独立0元，得到最优解相应的解矩阵为 最优目标值：7+6+9+6+4=32 效率矩阵 5 4 3 2 5 6 4 5 7 7 8 5 8 7 9 10 8 7 9 10 甲 5 4 3 2 丁 5 6 4 5 丙 7 7 8 5 乙 D C B A 工作 人员 5 4 3 2 5 6 4 5 7 7 8 5 8 7 9 10 2 4 5 7 3 2 1 0 1 2 0 1 2 2 3 0 1 0 2 3 1 0 0 0 2 2 1 0 0 2 0 1 1 2 3 0 0 0 2 3 ? ? ? -1 -1 +1 1 1 0 0 0 2 0 2 0 1 2 0 0 0 2 4 1 1 0 0 0 2 0 2 0 1 2 0 0 0 2 4 第一组最优解 第二组最优解 1.效率矩阵不是方阵的情况。（即人员与工作数不相等） 处理方法：增加虚拟人或工作，使两者相等。虚拟人或工作对应的效率矩阵中元素为0。 2.最大化分配问题的处理。 如果给出的效率矩阵中的数字表示每个人完成各项任务的收益，则问题变成了如何分配任务才能使总收益最大. 处理方法：用效率矩阵中的最大元减去矩阵中的各个元素得到一个新的矩阵，对这个新的矩阵用匈牙利方法求解。 例4：有四项工作分配给六个人去完成，每个人分别完成各项工作的时间如下表所示，仍然规定每个人只能完成一项工作，每项工作只交给一个人去完成，问挑选哪四个人去完成工作，花费的总时间最少？ 2 6 7 5 A6 3 4 2 5 A5 7 3 4 6 A4 8 5 6 3 A3 4 4 1 7 A2 6 2 6 3 A1 B4 B3 B2 B1 工作 人员 0 0 0 0 0 0 B6 0 0 0 0 0 0 B5 2 3 7 8 4 6 B4 6 7 5 A6 4 2 5 A5 3 4 6 A4 5 6 3 A3 4 1 7 A2 2 6 3 A1 B3 B2 B1 工作 人员 例5 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如下表，由于任务数多于人数，故考虑： 45 32 33 37 E 23 40 20 42 D 36 42 24 丁 28 27 34 丙 26 38 39 乙 31 29 25 甲 C B A 任务 人员 （1）任务E必须完成，其他4项中任选3项完成； （2）其中有一人完成两项，其他每人完成一项； （3）任务A由甲或丙完成，任务C由丙或丁完成，任务E 由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项； 试分别确定最优分配方案，使完成任务的总时间最少。 M 0 0 0 0 戊 45 23 36 42 24 丁 32 33 37 E 40 20 42 D 28 27 34 丙 26 38 39 乙 31 29 25 甲 C B A 任务 人员 （1）任务E必须完成，其他4项中任选3项完成； （2）其中有一人完成两项，其他每人完成一项； 32 20 26 27 24 戊 45 23 36 42 24 丁 32 33 37 E 40 20 42 D 28 27 34 丙 26 38 39 乙 31 29 25 甲 C B A 任务 人员 由于虚拟人完成的工作需要转给甲乙丙丁，因此，虚拟人完成各项工作的时间等于四个人完成该工作的最短时间。 （3）任务A由甲或丙完成，任务C由丙或丁完成，任务E 由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项； 45 23 28 27 34 戊 45 23 36 42 M 丁 M 33 37 E 40 20 42 D 28 27 34 丙 M 38 M 乙 M 29 25 甲 C B A 任务 人员 虚拟人完成某项工作的时间等于丙、丁完成该工作的时间中较小者。 例6：假设有3项工作A,B,C