运筹学第4讲单纯形法的进一步讨论ppt课件_第1页
运筹学第4讲单纯形法的进一步讨论ppt课件_第2页
运筹学第4讲单纯形法的进一步讨论ppt课件_第3页
运筹学第4讲单纯形法的进一步讨论ppt课件_第4页
运筹学第4讲单纯形法的进一步讨论ppt课件_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

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

文档简介

第 4讲:单纯形法的 进一步讨论 浙江工业大学经贸管理学院 曹柬 一、 LP问题的标准化 LP模型的标准形式 运筹学 第 4讲:单纯形法的进一步讨论 max Z = CX s.t. AX = b X 0 Q 目标函数为 max型 Q X 0 Q b 0 ! 单纯形法仅适于 LP标准模型的求解 非标准型 LP模型的标准化 ( P10) 一、若目标函数为: min Z = CX 令 Z = -Z,则原目标函数转化为 max Z = -CX 二、若存在 bi 0时,说明模型中存在多余的约束,使 多个基可行解对应同一顶点。当模型存在退化解时,处 理方法如下: 最小比值相同时,取下标值最大的变量为换出变量 j最大值相同时,取下标值最小的变量为换入变量 运筹学 第 4讲:单纯形法的进一步讨论 ( 大 M法的问题在于:采用手工计算求解不 会碰到问题,但用计算机求解时,对 M只能在 计算机中输入一个机器最大字长的数字;显 然,如果其他参数值大于或与这个数字相近 ,便会导致计算结果发生错误! 运筹学 第 4讲:单纯形法的进一步讨论 max z = -4x1 x2 s.t. 3x1 + x2 = 3 4x1 + 3x2 - x3 = 6 x1 + 2x2 + x4 = 4 x1-4 0 例 3: P20例 2.6 运筹学 第 4讲:单纯形法的进一步讨论 运筹学 第 4讲:单纯形法的进一步讨论 三、二阶段法 针对大 M法存在的问题,我们可以对添加人工变量后 的 LP模型分为两个阶段来计算,称为二阶段法 (P22)。 第一阶段:先求一个目标函数中只包含人工变量的 LP模型, 也就是说,令目标函数中其他变量的系数为 0,人工变量的系 数为某个正常数 (一般为 1),在原问题约束条件不变的情况下求 解。 第二阶段:当第一阶段求解结果表明模型有可行解时,在原 问题中去除人工变量,从第一阶段的最优解出发,继续求解。 例 4: 采用二阶段法求解 P22中 LP模型 运筹学 第 4讲:单纯形法的进一步讨论 运筹学 第 4讲:单纯形法的进一步讨论 首先应确定当 x5, x6=0时,可行域是否存在! 则第一阶段先求解如下的 LP模型: 显然,若 z=0,即 x5, x6=0,则问题的可行域存在。 运筹学 第 4讲:单纯形法的进一步讨论 x5, x6=0,则 z=0,问题的 可行域存在。 运筹学 第 4讲:单纯形法的进一步讨论 去除 x5和 x6,进一步求解 第二阶段的 LP模型: 得到最优解和最优值。 四、采用单纯形法求解的几种情况 惟一最优解 无可行解 (P23-例 2.7) 所有检验数 j 0,但基变量中仍含有非零人工变量 无界解 (例 5) 当存在最大的 j 0,但 值无解 多重最优解 (例 6:习题 2-1) 当所有检验数 0,但存在非基变量 j = 0,该非基变 量可以作为换入变量,模型存在多重最优解 运筹学 第 4讲:单纯形法的进一步讨论 max z = 3x1 + 2x2 s.t. -2x1 + x2 2 x1 - 3x2 3 x1, x2 0 例 5: 求解如下 LP模型 运筹学 第 4讲:单纯形法的进一步讨论 cj 3 2 0 0 b bi/aik cB XB x1 x2 x3 x5 0 x3 -2 1 1 0 2 / 0 x4 1 -3 0 1 3 3 j (1) 3 2 0 0 max z = 3x1 + 2x2 + 0x3 + 0x4 s.t. -2x1 + x2 + x3 = 2 x1 - 3x2 + x4 = 3 x1, x2 0 解:将模型化为标准型, 运筹学 第 4讲:单纯形法的进一步讨论 cj 3 2 0 0 b bi/aik cB XB x1 x2 x3 x5 0 x3 -2 1 1 0 2 / 0 x4 1 -3 0 1 3 3 j (1) 3 2 0 0 0 x3 0 -5 1 2 8 / 3 x1 1 -3 0 1 3 / j (2) 0 11 0 -3 由于 max j | j 0所对应的 值无解,则该 LP问题解无界。

温馨提示

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

评论

0/150

提交评论