最优化理论与方法单纯形法课件.pptx
最优化理论与方法单纯形法最优化理论与方法单纯形法2.1 标准形式o 一般线性规划问题总可以写成下列一般线性规划问题总可以写成下列标准形式标准形式： (2.1.1)o 用矩阵表示：用矩阵表示： (2.1.2)11min . . 1,., 0 1,., njjjnijjijjc xsta xbimxjnmin . . 0 stcxAxbx其中，A是mXn矩阵，c是n维行向量，b是m维列向量。为了计算方便，一般假设 ，即b的每个分量都是非负数。 b0表示定理o 设 为非空多面集，则有：n极点集非空，且存在有限个极点 .n极方向集为空集的充要条件是S有界。若S无界，则存在有限个极方向 .nxS的充要条件是：( )( )1111,0, 1,., ,0, 1,., .kljjjjjjkjjjjxxdjkjl(1)( ),.,ldd(1)( ),.,kxx |, 0Sx Axb x定理与结论o 线性规划的可行域是凸集。线性规划的可行域是凸集。 o 设线性规划设线性规划 (2.1.2)的可行域非空，则有下列结论：的可行域非空，则有下列结论：n线性规划线性规划(2.1.2)存在有限最优解的充要条件是所有存在有限最优解的充要条件是所有 为非负数，为非负数， 其中其中 是可行域的极方向。是可行域的极方向。n若线性规划若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某存在有限最优解，则目标函数的最优值可在某个极点上达到。（个极点上达到。（最优极点最优极点）( ) jcd( ) jd极点是个几何概念，直观性强，但不便于演算，因此需要研究极点的代数含义。基本可行解o 称为方程组的一个称为方程组的一个基本解基本解；oB称为称为基矩阵基矩阵，简称基；，简称基；oxB的各分量称为的各分量称为基变量基变量；o基变量的全体基变量的全体 称为一组基；称为一组基；oxN的各分量称为的各分量称为非基变量非基变量；o若若 ，则称基本可行解，则称基本可行解是非退化的是非退化的基本可行解基本可行解；o若若 且至少有一个分量是零，则称且至少有一个分量是零，则称 此时的基本可行解是此时的基本可行解是退化的基本可行解退化的基本可行解；同时，此基本可行解对应的基被称为同时，此基本可行解对应的基被称为退化退化的可行基的可行基。10BNxB bxx12, ,.,mBBBxxxo又若又若 ，则称，则称 为约束条件为约束条件 的的基本可行解基本可行解， 称称B为为可行基矩阵可行基矩阵， 为一组为一组可行基可行基；10B b10BNxB bxx12, ,.,mBBBxxx10B b10B b, 0Axb x基本可行解的个数o 若A是mXn矩阵， A的秩为m时， 基本可行解的个数不会超过：!()!nnmm nm定理与推理o 线性规划的可行域是凸集。线性规划的可行域是凸集。 o 设线性规划设线性规划 (2.1.2)的可行域非空，则有下列结论：的可行域非空，则有下列结论：n线性规划线性规划(2.1.2)存在有限最优解的充要条件是所有存在有限最优解的充要条件是所有 为非负数，为非负数， 其中其中 是可行域的极方向。是可行域的极方向。n若线性规划若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某存在有限最优解，则目标函数的最优值可在某个极点上达到。（个极点上达到。（最优极点最优极点）o 线性规划的线性规划的可行域的极点集可行域的极点集与与基本可行解集基本可行解集等价等价；o 当线性规划当线性规划(2.1.2)有可行解，则一定存在基本可行解。有可行解，则一定存在基本可行解。o 当线性规划当线性规划(2.1.2)存在最优解时，则一定存在一个基本可行解存在最优解时，则一定存在一个基本可行解是目标函数的最优解。（是目标函数的最优解。（最优基本可行解最优基本可行解）( ) jcd( ) jd第3章 单纯形方法o 3.1单纯形方法原理o 3.2两阶段法o 3.3修正单纯形法单纯形方法的基本思想o 就是，从一个基本可行解出发，求一个使目标函数值有所改变的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。o 怎样实现基本可行解的转换？表格形式的单纯形法o显然，在单纯形表中包含了单纯形方法所需的全部数据。f xB xN 右端xB 0 Im B-1N B-1bf 1 0 cBB-1N-cN cBB-1bmin . . 0 fcxst Axbx min . . 0 0, 0BBNNBNBNfstfc xc xBxNxbxx11 11min s.t. 0() 0, 0BNBBNNBBNfxB NxB bfxc B Ncxc B bxx 表格形式的单纯形法o显然，在单纯形表中包含了单纯形方法所需的全部数据。 11111 1 0 0 rmBBBjkBjkxxxxxxyyb 0 1 0 rmBrjrkrBxyybx 0 0 1 0 0 0 mjmkmjjkkByybfzczcc b主元进基变量离基变量maxkkjjzczcmin|0rikikrkikbbxyyy表格形式的单纯形法o 解的几种情况在单纯形表上的体现(min型)：n 唯一最优解：终表非基变量判别数均小于零；n 多重最优解：终表非基变量判别数中有等于零的；n 无界解：任意表有正判别数正判别数相应的系数列系数列均非正非正。o max型单纯形表与min型的区别仅在于： 判别数反号，即，n 令负判别数中最小的对应的变量进基；n 当判别数均大于等于零时为最优。两阶段法o 用单纯形法消去人工变量（如果可能），即把人工变量变为非基变量，求出原问题的一个基本可行解；n首先引入人工变量。令 ， 即 n消去人工变量的一种方法是解如下第一阶段问题：o 用单纯形法求解原问题。0 , 0 aaAxxbxx( ,)0 , 0 maaxA Ibxxx min . .0, 0Taaae xstAxxbxx设得到的最优基本可行解是 ，此时必有下列三种情况之一： （1） （无可行解）（2） 且 的分量都是非基变量 （得基本可行解 ）（3） 且 的某些分量是基变量 （用主元消去法） (,)TTTaxx0ax 0ax 0ax axaxxx大M法o 其基本思想是：其基本思想是：在约束中增加人工变量 xa，同时修改目标函数，增加惩罚值惩罚值MeTxa ，M是很大的正数，这样，在极小化目标函数的过程中，由于M的存在，将迫使人工变量离基。 min =+. .0, 0Taaafcx Me xstAxxbxx min =. .0fcxstAxbx修正单纯形法o 在运用单纯形法解决线性规划问题时，如果知道了可行可行基的逆基的逆，就能利用它和原始数据原始数据来计算基变量的取值及判别数，从而能够确定一个基本可行解，并判断它是否为最优解。因此，只要保存原始数据和现行基的逆即可。o 修正单纯形法的基本思想是：给定初始基本可行解以后，修正单纯形法的基本思想是：给定初始基本可行解以后，通过修改通过修改旧基的逆旧基的逆来获得来获得新基的逆新基的逆，进而完成单纯形法，进而完成单纯形法的其它运算。在整个过程中的其它运算。在整个过程中保存现行基的逆保存现行基的逆。修正单纯形法的计算步骤1.给定初始可行基的逆给定初始可行基的逆 ，计算单纯形乘子，计算单纯形乘子w 和右端向量和右端向量 。构成下表：。构成下表：2.对于每个非基变量，计算判别数，令对于每个非基变量，计算判别数，令 。 如果如果 则停止计算，现行基本可行解是则停止计算，现行基本可行解是最优解最优解；否则，下一步。；否则，下一步。3.计算主列计算主列 。若。若 ,则停止计算则停止计算,无有限最优解无有限最优解; 否则下一步。否则下一步。4.把主列置于把主列置于逆矩阵表逆矩阵表的右边，组成下表：的右边，组成下表： 按最小比值确定主行，令按最小比值确定主行，令 ， r 为主行，以为主行，以 为主元为主元进行主元消去，然后去掉原来的主列，返回第进行主元消去，然后去掉原来的主列，返回第2步。步。111 (=) (=)BBBwc Bc bxBbB b1Bmaxkkjjzczc0kkzc1kkyB p0ky 目标函数值单纯形乘子可行基的逆 kBxwc b1 kkBkzcxBbymin|0riikrkikbbyyyrkyb【例】用修正单纯形法解下列问题123451234513452345 min 23. . 3 25 2 6 23 0 1,.,5 jxxxxxstxxxxxxxxxxxxxxj
