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

最优化理论与方法单纯形法第1页，课件共18页，创作于2023年2月2.1标准形式一般线性规划问题总可以写成下列标准形式：(2.1.1)用矩阵表示：(2.1.2)其中，A是mXn矩阵，c是n维行向量，b是m维列向量。为了计算方便，一般假设，即b的每个分量都是非负数。第2页，课件共18页，创作于2023年2月表示定理设为非空多面集，则有：极点集非空，且存在有限个极点.极方向集为空集的充要条件是S有界。若S无界，则存在有限个极方向.x∈S的充要条件是：第3页，课件共18页，创作于2023年2月定理与结论线性规划的可行域是凸集。

设线性规划(2.1.2)的可行域非空，则有下列结论：线性规划(2.1.2)存在有限最优解的充要条件是所有为非负数，其中是可行域的极方向。若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达到。（最优极点）极点是个几何概念，直观性强，但不便于演算，因此需要研究极点的代数含义。第4页，课件共18页，创作于2023年2月基本可行解称为方程组的一个基本解；B称为基矩阵，简称基；xB的各分量称为基变量；基变量的全体称为一组基；xN的各分量称为非基变量；若，则称基本可行解是非退化的基本可行解；若且至少有一个分量是零，则称此时的基本可行解是退化的基本可行解；同时，此基本可行解对应的基被称为退化的可行基。又若，则称为约束条件

的基本可行解，称B为可行基矩阵，为一组可行基；第5页，课件共18页，创作于2023年2月基本可行解的个数若A是mXn矩阵，A的秩为m时，基本可行解的个数不会超过：第6页，课件共18页，创作于2023年2月定理与推理线性规划的可行域是凸集。

设线性规划(2.1.2)的可行域非空，则有下列结论：线性规划(2.1.2)存在有限最优解的充要条件是所有为非负数，其中是可行域的极方向。若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达到。（最优极点）线性规划的可行域的极点集与基本可行解集等价；当线性规划(2.1.2)有可行解，则一定存在基本可行解。当线性规划(2.1.2)存在最优解时，则一定存在一个基本可行解是目标函数的最优解。（最优基本可行解）第7页，课件共18页，创作于2023年2月第3章单纯形方法3.1单纯形方法原理3.2两阶段法3.3修正单纯形法第8页，课件共18页，创作于2023年2月单纯形方法的基本思想就是，从一个基本可行解出发，求一个使目标函数值有所改变的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。怎样实现基本可行解的转换？第9页，课件共18页，创作于2023年2月表格形式的单纯形法显然，在单纯形表中包含了单纯形方法所需的全部数据。fxBxN

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

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

第14页，课件共18页，创作于2023年2月修正单纯形法在运用单纯形法解决线性规划问题时，如果知道了可行基的逆，就能利用它和原始数据来计算基变量的取值及判别数，从而能够确定一个基本可行解，并判断它是否为最优解。因此，只要保存原始数据和现行基的逆即可。修正单纯形法的基本思想是：给定初始基本可行解以后，通过修改旧基的逆来获得新基的逆，进而完成单纯形法的其它运算。在整个过程中保存现行基的逆。第15页，课件共18页，创作于2023年2月修正单纯形法的计算步骤给定初始可行基的逆，计算单纯形乘子w和右端向量。构成下表：对于每个非基变量，计算判别数，令。如果则停止计算，现行基本可行解是最优解；否则，下一步。计算主列。若,则停止计算,无有限最优解;否则下一步。把主列置于逆矩阵表的右边，组成下表：按最小比值确定主行，令，r为主行，以为主元进行主元消去，然后去掉原来的主列，返回第2步。目标函数值单纯形乘子可行基的逆