最优化理论与方法单纯形法课件

最优化理论与方法单纯形法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修正单纯形法单纯形方法的基本思想就是，从一个基本可行解出发，求一个使目标函数值有所改变的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。怎样实现基本可行解的转换？表格形式的单纯形法显然，在单纯形表中包含了单纯形方法所需的全部数据。fxBxN

右端xB0ImB-1NB-1bf10cBB-1N-cNcBB-1b表格形式的单纯形法显然，在单纯形表中包含了单纯形方法所需的全部数据。主元进基变量离基变量表格形式的单纯形法解的几种情况在单纯形表上的体现(min型)：唯一最优解：终表非基变量判别数均小于零；多重最优解：终表非基变量判别数中有等于零的；无界解：任意表有正判别数相应的系数列均非正。max型单纯形表与min型的区别仅在于：判别数反号，即，令负判别数中最小的对应的变量进基；当判别数均大于等于零时为最优。两阶段法用单纯形法消去人工变量（如果可能），即把人工变量变为非基变量，求出原问题的一个基本可行解；首先引入人工变量。令，即消去人工变量的一种方法是解如下第一阶段问题：用单纯形法求解原问题。设得到的最优基本可行解是，此时必有下列三种情况之一：（1）（无可行解）（2）且的分量都是非基变量（得基本可行解）（3）且的某些分量是基变量（用主元消去法）大M法其基本思想是：在约束中增加人工变量

xa，同时修改目标函数，增加惩罚值MeTxa

，M是很大的正数，这样，在极小化目标函数的过程中，由于M的存在，将迫使人工变量离基。

修正单纯形法在运用单纯形法解决线性规划问题时，如果知道了可行基的逆，就能利用它和原始数据来计算基变量的取值及判别数，从而能够确定一个基本可行解，并判断它是否为最优解。因此，只要保存原始数据和现行基的逆即可。修正单纯形法的基本思想是：给定初始基本可行解以后，通过修改旧基的逆来获得新基的逆，进而完成单纯形法的其它运算。在整个过程中保存现行基的逆。修正单纯形法的计算步骤给定初始可行基的逆，计算单纯形乘子w和右端向量。构成下表：对于每个非基变量，计算判别数，令。如果则停止计算，现行基本可行解是最优解；否则，下一步。计算主列。若,则停止计算,无有限最优解;否则下一步。把主列