三节单纯形方法.ppt
《三节单纯形方法.ppt》由会员分享,可在线阅读,更多相关《三节单纯形方法.ppt(47页珍藏版)》请在三一文库上搜索。
1、第三节第三节 单纯形方法单纯形方法 3.1 单纯形方法 3.2 单纯形表 3.1 单纯形方法 考虑标准形式的LP问题 如果它有最优解,则必 可在某一基本可行解处 达到,因而只需在基本 可行解集合中寻求即可 4.非退化 基本假定 : 先找一个基本可行解,判断它是否为最优解,如 果不是,就找一个更好的基本可行解,再进行判 断,如此迭代进行,直到找到最优解,或者判定 该问题无界. 需要解决的两个问题 1. 如何得到第一个基本可行解; 2. 如何判别和进行迭代. 基本思想 典式 引入记号 即 检验数向量 定理1.3.1 最优性准则 定理1.3.2 (无界准则) 定理1.3.3 (可迭代准则) 令 换基
2、过程 基矩阵 基变量 出基列 出基变量 进基列 进基变量 新基矩阵 新基矩阵 定理1.3.4 对于任何非退化的线性规划问题,从任何基本可 行解开始,经过有限多次迭代,或得到一个基本 可行的最优解,或做出该线性规划问题无界的判 断. 单纯形方法步骤 第1步 第2步 第3步 第4步 第5步 第6步 单纯形方法步骤 第7步 3.2 单纯形表 对于给定LP 问题的一个 线性方程组 基变量的值 思考:是否都可 经过简单初等行 变换化成典式? 若将k=4引入基,需计算 利用初等行变换化为对应的典式: RHS 进基离基 转轴元 旋转列 旋转行 旋转 例1.3.1 求解问题 解 迭代后 迭代后 例1.3.2 求解问题 解 这个问题的约束方程组是与例1.3.1最优解对应 的约束方程组,只是目标函数不同. 用表格表示为 所以原 问题解 无界 化为典式后
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 三节 单纯 方法
链接地址:https://www.31doc.com/p-2629679.html