列生成算法的应用-.ppt

Add your text here and write down your opninon thank you add your text here
列生成算法的应用-
由D-W分解原理，上述LP问题对应的主问题MP是
列生Add your text here and write down your opninon thank you add your text here
列生成算法的应用-
由D-W分解原理，上述LP问题对应的主问题MP是
列生成算法步骤如下：
列生成算法解线性规划问题
用列生成法求解
(2)
(1)
(3)
(4)
注：（2）表示一个任务被分配而且仅被分配到一个机器
（3）代表至多一个可行分配被选择到每个机器
结合列生成技术使用分支定价算法解这个多列GAP问题
LP松弛的解
列生成的主要思想就是：对大规模LP问题，不必列出所有的列，只通过解由这个约束矩阵列的一个子集构成的问题，称为限制的主问题，而获得原问题的解。在每一步解限制的主问题的迭代里，通过主问题的最优性检验获得原问题的最优解或者产生进基列重新进行迭代。
（5）
（6）
（7）
（8）
（6）
（7）
那么主问题的最优性判断由下式获得
（PP）的最优值
价格问题
分支定界过程实现
实现分支定价算法的挑战之一是确定分支策略。分支的机理是划分解空间以删除分数解。然而解空间的直接划分通过固定一个单个 是不合适的，因为这将导致列生成算法难于实现，而且产生不平衡的分支定界树，使分支定界算法变坏。
定理： 若列生成问题的最优解 是不可行的，即是 分数，则必至少存在一个j,使
因此得以下分支策略
在一个分支：令
在另外一个分支：令
这个分支规则通过以下两个步骤实现：
1、在每个分支节点求解限制的主问题时，在左分支对由第i个价格问题所产生的列做如下处理：删除第j个分量不为0的列；在右支删除第j个分量为0的列。
2、为保持价格问题的相容性，当求解第i个价格问题的子问题产生新的添加列时，在左分支固定第j个分量为0，即不允许分配第j个任务给第i个机器；在右分支固定第j个分量为1，即第j个任务必须分配给第i个机器。
分支定价算法步骤
Thank You