单纯形法原理_第1页
单纯形法原理_第2页
单纯形法原理_第3页
单纯形法原理_第4页
单纯形法原理_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

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

文档简介

第3节单纯形法原理可行域的性质直观：线性规划的可行域是凸集线性规划的最优解在顶点（极点）上凸集凸集不是凸集顶点一、凸集与顶点②顶点：若凸集C中的点X0不能成为C中任何线段的内点，则称X0为C的顶点或极点。①凸集：若连接n维点集C中的任意两点X1和X2之间的线段仍在C中，则C为凸集。即二、LP基本定理定理1

若LP问题存在可行域,则可行域是凸集。定理2

LP问题的基可行解对应于可行域的顶点。定理3

如果LP问题有最优解，则一定有基可行解是最优解。单纯形法的基本思路是：

先找到一个初始基可行解，如果不是最优解，设法转换到另一个基可行解，并使目标函数值不断增大，一直到找到最优解为止。引理

LP问题的可行解X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。三、单纯形法的基本思路三个问题:如何找到初始基可行解?如何判别当前基可行解是否达最优?3若当前基可行解非最优,如何寻找一个改善的基可行解?s.t.初始基变量非基变量将基变量用非基变量线性表示基可行解目标函数值将目标函数用非基变量线性表示检验数！进基变量(x1仍为非基变量)(哪个变量出基？)出基变量主元素两原则：最大检验数进基；最小比值法出基。基变量非基变量要将基变量用非基变量线性表示，需基可行解目标函数值将目标函数用非基变量线性表示检验数！进基变量(x5仍为非基变量)(哪个变量出基？)出基变量主元素即基变量非基变量要将基变量用非基变量线性表示，需基可行解目标函数值将目标函数用非基变量线性表示即由检验数可知，最优解为最优值最优基解的判断顶点基可行解z0012161503616033040420050915140364xy

当线性规划的约束条件全部为“≤”时，可按下述方法比较方便地寻找出初始基可行解。设给定线性规划问题1.确定初始基可行解s.t.四LP问题中三问题的一般解决方法s.t.其约束方程的系数矩阵为：为基变量.就是一个基可行解。

当线性规划中约束条件为“＝”和“≥”时，化为标准形式后，一般约束条件的系数矩阵中不含有单位矩阵。为能方便地找出一个初始的基可行解，可添加人工变量来人为构造一个单位矩阵作为基，称为人工基。这种方法将在本章第五节中讨论。为单位矩阵,可做为初始可行基，2从初始基可行解转换为另一基可行解

设初始基可行解为，其中非零坐标有m个不失一般性，假定前m个坐标为非零，即

方程组(1)的系数矩阵的增广矩阵为最小比值原则3最优解检验和解的判别，又对某个非基变量（2）当所有的且按最小比值原则,可以找到

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

温馨提示

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

最新文档

评论

0/150

提交评论