《列生成算法的应用.ppt》由会员分享，可在线阅读，更多相关《列生成算法的应用.ppt（24页珍藏版）》请在三一文库上搜索。
1、列生成算法最早被用来求解大规模线性规划问题 列生成算法列生成算法 块角结构的线性规划用D-W分解算法求解相当有效，其主要 思想是首先将问题转化为一个可以处理的等价问题，转化的目 的在于： 将问题转化为具有某种特殊结构的又有现成方法求解的问题 将问题化为规模较小的子问题 由D-W分解原理，上述LP问题对应的主问题MP是 列生成算法步骤如下： 列生成算法解线性规划问题 用列生成法求解用列生成法求解 列生成算法解广义分配问题列生成算法解广义分配问题 分配n项任务给m台机器完成，分配不同任务到不同机器所 获得的效益是不同的，每项任务必须而且仅能由一台机器完成 ，每台机器都有能力限制ci;，问题是要得到
2、最大经济效益的分 配但不能超出每台机器的负荷能力，类似的问题称为广义分配 问题 数学上，GAP问题能被表示成如下: (2) (1) (3) (4) 注：（2）表示一个任务被分配而且仅被分配到一个机器 （3）代表至多一个可行分配被选择到每个机器 结合列生成技术使用分支定价算法解这个多列GAP问题 列生成的主要思想就是：对大规模LP问题，不必列出所 有的列，只通过解由这个约束矩阵列的一个子集构成的 问题，称为限制的主问题，而获得原问题的解。在每一 步解限制的主问题的迭代里，通过主问题的最优性检验 获得原问题的最优解或者产生进基列重新进行迭代。 （5 ） （6 ） （7 ） （8 ） （6） （7）
3、 那么主问题的最优性判断由下式获得 （PP）的最优值 实现分支定价算法的挑战之一是确定分支策略。分支的 机理是划分解空间以删除分数解。然而解空间的直接划 分通过固定一个单个 是不合适的，因为这将 导致列生成算法难于实现，而且产生不平衡的分支定界 树，使分支定界算法变坏。 定理： 若列生成问题的最优解 是不可行的，即是 分数，则必至少存在一个j,使 因此得以下分支策略 在一个分支：令 在另外一个分支：令 这个分支规则通过以下两个 步骤实现： 1、在每个分支节点求解限制 的主问题时，在左分支对由 第i个价格问题所产生的列做 如下处理：删除第j个分量不 为0的列；在右支删除第j个 分量为0的列。 2、为保持价格问题的相容性 ，当求解第i个价格问题的子 问题产生新的添加列时，在 左分支固定第j个分量为0， 即不允许分配第j个任务给第i 个机器；在右分支固定第j个 分量为1，即第j个任务必须 分配给第i个机器。