最优化理论与方法2单纯形法.pptVIP

第2章 线性规划的基本性质 2.1标准形式及图解法 2.2基本性质 2.1 标准形式 一般线性规划问题总可以写成下列标准形式： (2.1.1) 用矩阵表示： (2.1.2) 其中，A是mXn矩阵，c是n维行向量，b是m维列向量。 为了计算方便，一般假设 ，即b的每个分量都是非负数。 表示定理 设 为非空多面集，则有： 极点集非空，且存在有限个极点 . 极方向集为空集的充要条件是S有界。若S无界，则存在有限个极方向 . x∈S的充要条件是： 定理与结论 线性规划的可行域是凸集。 设线性规划 (2.1.2)的可行域非空，则有下列结论： 线性规划(2.1.2)存在有限最优解的充要条件是所有 为非负数， 其中 是可行域的极方向。 若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达到。（最优极点） 极点是个几何概念，直观性强，但不便于演算， 因此需要研究极点的代数含义。 基本可行解 称为方程组的一个基本解； B称为基矩阵，简称基； xB的各分量称为基变量； 基变量的全体 称为一组基； xN的各分量称为非基变量； 若 ，则称基本可行解是非退化的基本可行解； 若 且至少有一个分量是零，则称 此时的基本可行解是退化的基本可行解；同时，此基本可行解对应的基被称为退化的可行基。 又若 ，则称 为约束条件 的基本可行解， 称B为可行基矩阵， 为一组可行基； 基本可行解的个数 若A是mXn矩阵， A的秩为m时， 基本可行解的个数不会超过： 定理与推理 线性规划的可行域是凸集。 设线性规划 (2.1.2)的可行域非空，则有下列结论： 线性规划(2.1.2)存在有限最优解的充要条件是所有 为非负数， 其中 是可行域的极方向。 若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达到。（最优极点） 线性规划的可行域的极点集与基本可行解集等价； 当线性规划(2.1.2)有可行解，则一定存在基本可行解。 当线性规划(2.1.2)存在最优解时，则一定存在一个基本可行解是目标函数的最优解。（最优基本可行解） 第3章 单纯形方法 3.1单纯形方法原理 3.2两阶段法 3.3修正单纯形法 单纯形方法的基本思想 就是，从一个基本可行解出发，求一个使目标函数值有所改变的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。 怎样实现基本可行解的转换？ 表格形式的单纯形法 显然，在单纯形表中包含了单纯形方法所需的全部数据。 f xB xN 右端 xB 0 Im B-1N B-1b f 1 0 cBB-1N-cN cBB-1b 表格形式的单纯形法 显然，在单纯形表中包含了单纯形方法所需的全部数据。 主元 进基变量 离基变量 表格形式的单纯形法 解的几种情况在单纯形表上的体现(min型)： 唯一最优解：终表非基变量判别数均小于零； 多重最优解：终表非基变量判别数中有等于零的； 无界解：任意表有正判别数相应的系数列均非正。 max型单纯形表与min型的区别仅在于： 判别数反号，即， 令负判别数中最小的对应的变量进基； 当判别数均大于等于零时为最优。 两阶段法 用单纯形法消去人工变量（如果可能），即把人工变量变为非基变量，求出原问题的一个基本可行解； 首先引入人工变量。令 ， 即 消去人工变量的一种方法是解如下第一阶段问题： 用单纯形法求解原