对偶单纯形法详解ppt课件.ppt
《对偶单纯形法详解ppt课件.ppt》由会员分享,可在线阅读,更多相关《对偶单纯形法详解ppt课件.ppt(22页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、 是应用是应用求解原始求解原始线性规划的一种方法线性规划的一种方法在原始问题的单在原始问题的单纯形表格上进行纯形表格上进行。 不是解对偶问题的单纯形法!不是解对偶问题的单纯形法! 从更高的层次理解单纯形法从更高的层次理解单纯形法 (对应一个初始基本可行解)(对应一个初始基本可行解) (对应另一个基(对应另一个基本可行解),直至本可行解),直至为止为止。 所有检验数所有检验数0意味着意味着 ,10NBCC B NYAC说明说明。换言之,当原始问题的基。换言之,当原始问题的基B既是原始可既是原始可行基又是对偶可行基时,行基又是对偶可行基时,B成为最优基。成为最优基。 . .0MaxZstCXAXb
2、X1YBC B 1BC B等价等价N00N YAC-1BC B AC0-1BCC B A-1BCC B A0()()BN-1BC BCB0CN()()BN-1-1BBCCC BBB CN0()BN-11B-BCCC B BC B N0NB-1-1BBCCC B BB0CN0 0N (b列保持列保持0), (检验数行检验数行0) :保持保持的前提下(的前提下() ,通过逐步迭,通过逐步迭代代(,从非可行解变成,从非可行解变成可行解)。可行解)。 原问题原问题初始基本初始基本可行解可行解保持为基本保持为基本可行解可行解初始对偶可行解初始对偶可行解保持对偶可行性保持对偶可行性始终满足解始终满足解的可
3、行性的可行性始终满始终满足对偶足对偶可行性可行性 每每一次迭代过程中取出一次迭代过程中取出作为作为去去某个某个(作为作为),使原始问题的非可行解向可行解靠近。使原始问题的非可行解向可行解靠近。 : (一般选最小的负元素)(一般选最小的负元素); 即即出基,则选lliiixbBbBbB,)(0)()(min111相应的行相应的行。是:在是:在下,下,。如果如果 0minlkkkljljjjjazcaazc(最小比值原则最小比值原则),则选则选 为换入变量为换入变量 , 相应相应的列为的列为, 主元行和主元列交叉处的元主元行和主元列交叉处的元素素 。kxlka若 ,要计算最小比值吗?为什么?0lj
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对偶 单纯 详解 ppt 课件
限制150内