运筹学-4整数规划_1.ppt

* * * * * * * * * * * * * * * * * * * * * 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 * * * * * * * 指派问题是0-1 规划的特例，也是运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。 * * * 在20世纪60年代初由Land Doig和Dakin等人提出。 分支定界法（Branch and bound method）是一种 隐枚举法或部分枚举法，它是枚举法基础上的改进。 分支定界法的关键是分支和定界。 * * * * * 即两个后继问题。这两个后继问题的可行域总包含原整数规划问题的所有可行解，而在原松驰问题可行域总，满足[bi}xi[bi]+1的一部分区域在以后的求解过程中被抛弃了，因为它不包含整数规划的任何可行解。根据需要，各后继问题可以类似地产生自己的分支，如此不断继续，直到获得整数规划的最优解，这就是所谓的“分支”。 * “分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高有哪些信誉好的足球投注网站的效率。经验表明，在可能的情况下，根据对实际问题的了解，实现选择一个合理的界限，可以提高分支定界发的有哪些信誉好的足球投注网站效率。 * * * * * * * * * * * * 选择有最大目标函数值的节点继续向下分枝 * * * * * * * * * * * * 求解指派问题的新方法 匈牙利算法： 1.变换系数矩阵 2.在新系数矩阵中确定独立零元素 3.在未被直线覆盖的元素中找出一个最小元素，通过行、列变换把该最小元素化为0，得新系数矩阵。返回2. 问题 该步骤每执行一次，系数矩阵中至少增加一个新的0，但不能保证变换后的新系数矩阵中独立零元素的个数也会增加，从而导致迭代次数较多。 闭回路矩阵： 指派问题的系数矩阵中形如 的2×2子矩阵。其中a ,b ,c均为正数。 最小顶点： 在某个闭回路矩阵 中，若a + d ≤ b + c，定义a与d中最小的正数为最小顶点。 纯伪零点： 既存在形如 或 的闭回路矩 阵，又存在形如 或 的闭回路 矩阵，且a为所有上述矩阵的最小顶点（即 a≦c, a≦b），称a为指派问题系数矩阵的 纯伪零点。 纯伪零点具有如下性质： 性质1 任一纯伪零点均可经行、列变换化为零，且变换后新系数矩阵中0的个数至少增加1，同时所有元素均非负。 性质2 将纯伪零点化为零后的新系数矩阵中独立零元素的个数一定增加1。 新算法的原理： 在匈牙利算法的步骤3中，用未被直线覆盖的元素中的纯伪零点代替最小元素，作行、列变换把纯伪零点化为0，并在变换过程中保持系数矩阵中原来的零元素不变。 举例： 求系数矩阵为 的指派问题的最优解 1.变换系数矩阵 2.在新系数矩阵中确定独立零元素 匈牙利算法： 独立零元素仍为3，继续迭代 新算法： 练习： 求系数矩阵为 的指派问题的最优解。 注1 在标注独立零元素过程中，若矩阵 中出现 或 ，指派问题必有 两组最优解。 注2 当纯伪零点恰为未被直线覆盖元素中的最小元素，则同于匈牙利算法。 张红历 Thank You! * * * * * * * * 整数规划这里是指线性规划中的一类特殊的问题，其特点是决策变量只取整数。 ??? 建立整数规划模型如同建立一般线性规划模型一样，要确定决策变量、目标函数和约束条件。所不同的是，这里的可行解中各变量只取整数。如果只有两个决策变 量，可行解只可能是平面上坐标是整数的点。因而在各决策变量有界的条件下，可行解只可能是有限多个。这个特点使我们有可能用一些特殊方法求解整数规划模型。 * * * * * * * 基本思想： 1. 松弛模型的最优解要优于其相应的整数规划的解 ????? 由于松弛模型可行解的区域（多边形）包含了对应的整数规划的可行解的集合（多边形内的整数