最优化理论与方法2单纯形法.ppt
《最优化理论与方法2单纯形法.ppt》由会员分享,可在线阅读,更多相关《最优化理论与方法2单纯形法.ppt(18页珍藏版)》请在三一文库上搜索。
1、第2章 线性规划的基本性质,2.1标准形式及图解法 2.2基本性质,2.1 标准形式,一般线性规划问题总可以写成下列标准形式: (2.1.1) 用矩阵表示: (2.1.2),其中,A是mXn矩阵,c是n维行向量,b是m维列向量。 为了计算方便,一般假设 ,即b的每个分量都是非负数。,表示定理,设 为非空多面集,则有: 极点集非空,且存在有限个极点 . 极方向集为空集的充要条件是S有界。若S无界,则存在有限个极方向 . xS的充要条件是:,定理与结论,线性规划的可行域是凸集。 设线性规划 (2.1.2)的可行域非空,则有下列结论: 线性规划(2.1.2)存在有限最优解的充要条件是所有 为非负数,
2、 其中 是可行域的极方向。 若线性规划(2.1.2)存在有限最优解,则目标函数的最优值可在某个极点上达到。(最优极点),极点是个几何概念,直观性强,但不便于演算, 因此需要研究极点的代数含义。,基本可行解,称为方程组的一个基本解; B称为基矩阵,简称基; xB的各分量称为基变量; 基变量的全体 称为一组基; xN的各分量称为非基变量;,若 ,则称基本可行解是非退化的基本可行解; 若 且至少有一个分量是零,则称 此时的基本可行解是退化的基本可行解;同时,此基本可行解对应的基被称为退化的可行基。,又若 ,则称 为约束条件 的基本可行解, 称B为可行基矩阵, 为一组可行基;,基本可行解的个数,若A是
3、mXn矩阵, A的秩为m时, 基本可行解的个数不会超过:,定理与推理,线性规划的可行域是凸集。 设线性规划 (2.1.2)的可行域非空,则有下列结论: 线性规划(2.1.2)存在有限最优解的充要条件是所有 为非负数, 其中 是可行域的极方向。 若线性规划(2.1.2)存在有限最优解,则目标函数的最优值可在某个极点上达到。(最优极点) 线性规划的可行域的极点集与基本可行解集等价; 当线性规划(2.1.2)有可行解,则一定存在基本可行解。 当线性规划(2.1.2)存在最优解时,则一定存在一个基本可行解是目标函数的最优解。(最优基本可行解),第3章 单纯形方法,3.1单纯形方法原理 3.2两阶段法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 理论 方法 单纯
链接地址:https://www.31doc.com/p-2090142.html