线性规划问的有效集法_第1页
线性规划问的有效集法_第2页
线性规划问的有效集法_第3页
线性规划问的有效集法_第4页
线性规划问的有效集法_第5页
全文预览已结束

下载本文档

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

文档简介

线性规划问的有效集法

该算法是在20世纪80年代形成的，具有单纯形理论的一些突出优势。有效集法可补充单纯形法，在实践中重要应用。从本质上讲，有效集法和单纯形法是一致的。在本文中，我们展示了有效集法的实际算法，并证明了上述两种方法的一致性。1有效收集方法的实用算法单纯形法是针对线性规划问題的标准形式求解的.使用矩阵和向量的符号可以写为其中设该基本可行解对应的Ax=b典范型为其中1.1线性规划初始可行解的确定(1)计算检验数.对(2)令(3)若αiq≤0(i=1,…,m),则(1.1)式有无限解:否则令其中p是使上式成立的最小下标,主元行标号.(4)对j=1,…,n计算对i=1,…,m,i≠p,j=1,…,n计算转(1).为确定初始基本可行解,考虑辅助线性规划这里有效集法是针对线性规划问題的一般形式求解的.(1.5)式可以写为设1.2算法2下标,当m(1)确定x线性无关.记计算(3)若(4)计算其中s是使上式成立的最小下标.(5)若(6)若对所有i∈G-F(x其中r是使上式成立的最小下标.(8)对i=1,…,n计算,转(2).为求初始可行点,对任意点x令k=1,使用算法2求解(1.7)式,得x2使用有效集法求解线性规划的标准则有2.1设从而当在顶点转移时,选取使式成立的最小下标s,把相应的下标从迭代步长为其中α其中p=r-m.新顶点这与单纯形法也是一致的.因此,顶点的转移就是基本可行解的转移,幷且容易看出,在无限解的情形发生时,结论也是一样的.2.2使用有效集法中求可行点的方法,求(2.1)式的初始可行点,首先取x从而求解引入松驰变量x同样可以得到,使用有效集法求解系列线性规划(1.7)式,对应了使用单纯形法求解辅助线性规划(1.4)式:(1.7)式中的等式约束条件3使用条件约束下的乘子下面将证明,使用有效集法求解线性规划的标准形式和一般形式,结果是相同的.不失一般性,考虑如下形式的线性规划将x其中幷且y设x是(3.1)式的可行域的非退化顶点,记并不妨设是对于相应的矩阵其中-T是矩阵对(3.1)式,这里在求最小乘子时,注意到不等式约束(3.3)式已成为等式约束,但是这些约束中的松驰变量所对应的非负约束y关于迭代方向,对(3.1)式,3.1如果q对应x≥0中的某个有效约束的下标,则在求解(3.2)式时,最小乘子是3.2如果q对应了不等式约束(3.3)式中的某个约束的下标,则在求解(3.2)式时,最小乘子的下标对应了约束y由(3.5)式和(3.6)式可知,关于迭代步长,对(3.2))式,步长为式中:其中从而记容易得到即对(3.1)式和(3.2)式,步长也是一样的.综上所述,单纯形法和有效集方法在本质上是一致的.则由上述基本可行解开始求解(1.1)式的单纯形法的具体步驟

人人文库> 全部分类> 专业文献 > 学术论文

温馨提示

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

最新文档

评论

0/150

提交评论