单纯形法求解.ppt_第1页
单纯形法求解.ppt_第2页
单纯形法求解.ppt_第3页
单纯形法求解.ppt_第4页
单纯形法求解.ppt_第5页
已阅读5页，还剩23页未读， 继续免费阅读

下载本文档

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

文档简介

1、线性规划的基本概念,可行解 feasible solution 最优解 optimal solution 基 basic matrix (the basis) 基解 basic solution 基可行解 basic feasible (BF) solution 可行基 feasible basic matrix 可行域 feasible region,LP的基本定理,定义 凸集（convex set），顶点（极点corner point ） 定理1：线性规划问题的可行域是凸集 定理2：线性规划问题的最优解在极点上 定理3：若LP问题有最优解，一定存在一个基可行解是最优解。,凸集,凸集,不是凸

2、集,极点,单纯形表 基变量,引例用单纯形法求解生产计划问题。解： （1）化标准型,(3)本问题的最优解 X =(X1, X2, X3, X4, X5)T = (15, 15/2, 0, 0, 9)T 且Z=975. X3 , X4 =0表示资源1 ，2用完, X5 =9表示资源3剩余9. 图解分析见下。,0,(0,0),X2,X1,从一个基可行解到另一个基可行解,单纯形法基本步骤,(1)、定初始基，初始基本可行解,(3)、若有 k 0，Pk全 0，停， 没有有限最优解； 否则转(4),(2)、对应于非基变量检验数 j全 0。 若是，停，得到最优解； 若否，转(3)。,定Xr为换出变量，arm+

3、k为主元。,由最小比值法求：,转(2),(5)、以arm+k为中心，换基迭代,单纯形法的进一步讨论（简介）,(一)、大M法 the Big M Method 初始基本可行解的求法 - 加入人工变量 大M使人工变量 - 0,例：用大 M 法求解下列问题。,解： （1）化标准型 maxZ=6X1+4X2,（2）加人工变量X6，X7，问题化为 maxZ=6X1+4X2-MX6 -MX7,(二)、两阶段法 The Two-phase Method,解题过程：,第1阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解 第2阶段： 以第一阶段得到的基础可行解为初始解，采用原单纯型法求解,两阶段法原理：,(1)、辅助问题的基本可行解X(0) 为最优解，对应 最小值=0 则X(0) 的前n个分量是原问题的基本可行解。,小结与应用举例,小结 应用举例,(2)、LP问题解的性质：图解法分析,小结,(3)、单纯形法：,1)、标准型中有单位基。,4)、解的几种情况： 唯一解 无穷多解 （多重解 ） 无有限最优解 （无界解） 无可行解,多重解,多个解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行 最优单纯型表中有非基变量的检验数为0 最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=1,无界解 可行区域不闭合(缺约束条件) 单纯型表中

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论