列生成算法应用_第1页
列生成算法应用_第2页
列生成算法应用_第3页
列生成算法应用_第4页
列生成算法应用_第5页
已阅读5页，还剩19页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、1列生成算法最早被用来求解大规模线性规划问题 块角结构的线性规划用D-W分解算法求解相当有效，其主要思想是首先将问题转化为一个可以处理的等价问题，转化的目的在于：将问题转化为具有某种特殊结构的又有现成方法求解的问题将问题化为规模较小的子问题2由D-W分解原理，上述LP问题对应的主问题MP是3列生成算法步骤如下：45列生成算法解线性规划问题234B =100132 1B =1 112 3B =5 16789101112 分配n项任务给m台机器完成，分配不同任务到不同机器所获得的效益是不同的，每项任务必须而且仅能由一台机器完成，每台机器都有能力限制ci;，问题是要得到最大经济效益的分配但不能超出每

2、台机器的负荷能力，类似的问题称为广义分配问题数学上，GAP问题能被表示成如下:131415 (2) (1) (3) (4)注：（2）表示一个任务被分配而且仅被分配到一个机器 （3）代表至多一个可行分配被选择到每个机器结合列生成技术使用分支定价算法解这个多列GAP问题16LP松弛的解松弛的解列生成的主要思想就是：对大规模LP问题，不必列出所有的列，只通过解由这个约束矩阵列的一个子集构成的问题，称为限制的主问题，而获得原问题的解。在每一步解限制的主问题的迭代里，通过主问题的最优性检验获得原问题的最优解或者产生进基列重新进行迭代。（5）（6）（7）（8）17（6）（7）那么主问题的最优性判断由下式获

3、得（PP）的最优值）的最优值18价格问题价格问题1920分支定界过程实现分支定界过程实现实现分支定价算法的挑战之一是确定分支策略。分支的机理是划分解空间以删除分数解。然而解空间的直接划分通过固定一个单个 是不合适的，因为这将导致列生成算法难于实现，而且产生不平衡的分支定界树，使分支定界算法变坏。定理： 若列生成问题的最优解 是不可行的，即是 分数，则必至少存在一个j,使21因此得以下分支策略在一个分支：令在另外一个分支：令这个分支规则通过以下两个步骤实现：1、在每个分支节点求解限制的主问题时，在左分支对由第i个价格问题所产生的列做如下处理：删除第j个分量不为0的列；在右支删除第j个分量为0的列。2、为保持价格问题的相容性，当求解第i个价格问题的子问题产生新的添加列时，在左分支固定第j个分量为0，即不允许分配第j个任务给第i个机器；在右

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论