《管理运筹学》02-2求解线性规划的单纯形法_第1页
《管理运筹学》02-2求解线性规划的单纯形法_第2页
《管理运筹学》02-2求解线性规划的单纯形法_第3页
《管理运筹学》02-2求解线性规划的单纯形法_第4页
《管理运筹学》02-2求解线性规划的单纯形法_第5页
已阅读5页，还剩14页未读， 继续免费阅读

下载本文档

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

文档简介

第二节单纯形法,SimplexMethod,求解线性规划的单纯形法,单纯形法思路,求解线性规划的单纯形法,Q1：初始基本可行解如何找？标准型基本解Q2：怎样判断最优？最优性条件Q3：如何找下一个相邻的基本可行解？确定移动的方向确定在何处停下确定新的基本可行解,关键问题,求解线性规划的单纯形法,例：用单纯形法求解以下线性规划问题,求解线性规划的单纯形法,首先将模型转化成标准形式,求解线性规划的单纯形法,Q1：确定初始的基本可行解,选择原点：令决策变量x1=x2=0得：X0=(0，0，3，4)T选择单元阵作为初始基：令非基变量x1=x2=0得：X0=(0，0，3，4)T,求解线性规划的单纯形法,非最优：增加非基变量的值，可以使得目标函数Z值增加基变量在目标函数中的系数为0非基变量在目标函数中的系数=0,Q2：最优性检验,检验数,求解线性规划的单纯形法,迭代步骤1：确定移动的方向例：z=2x1+3x2选择x1？Z的增长率=2选择x2？Z的增长率=332，选择x2！进基变量的选择：选择非基变量的系数最大的！,Q3：如何找下一个相邻的基本可行解,确定进基变量,检验数的绝对值哦,求解线性规划的单纯形法,迭代步骤2：确定在何处停下增加x2的值，x1=0所有变量非负令x2=2，从而x4=0离基变量的选择：最小比值法,确定离基变量,最小比值法,Q3：如何找下一个相邻的基本可行解,求解线性规划的单纯形法,迭代步骤3：确定新的基本可行解原方程寻找新的基本可行解：初等数学变换,初等数学变换,1,X*=（0,2,1,0）,Z*=6+x1/2-3x4/26,新方程,Q3：如何找下一个相邻的基本可行解,非基变量x1的系数是正数！,非最优解！,求解线性规划的单纯形法,第2次迭代确定进基变量x1确定离基变量,非基变量x4=0,确定x3为离基变量,初等行变换,初等行变换,非基变量系数0，最优！,Z*=7,X*=(2,1,0,0),求解线性规划的单纯形法,目标函数无界的情况,用单纯形法求解以下线性规划模型。,求解线性规划的单纯形法,最优性检验：,一切j0？,然后确定初始基本可行解X0=(0,0,1,2)Tz0=0,当前解X0非优；,须由X0转化为另一个基本可行解X1。,思路：让X0中的一个非基变量进基，去替换原来的一个基变量（离基）。,首先标准化，令z=-z，引入松弛变量x3,x4,x1仍为非基变量，其值为0。,x21/1x22/1,离基（最小比值规则）：x2min1/1，2/1=1x2=min1/1，2/1=1,x3,x3为离基变量,进基（最小检验数规则）：在负检验数中选择最小的进基。minjj=0,x2、x1不受x3限制！
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论