单纯形法综述

单纯形法综述zy1415104-曹文亮单纯形法是1947年由GeorgeBernardDantzing(1914-2005)创建的，单纯形法的创建标志着线性规划问题的诞生。线性规划问题是研究在线性约束条件下，求线性函数的极值问题。然而，对这类极值问题，经典的极值理论是无能为力的，只有单纯形法才能有效解决这类极值问题的求解。线性规划是数学规划的一个重要分支，也是最早形成的一个分支，线性规划的理论与算法均非常成熟，在实际问题和生产生活中的应用非常广泛；线性规划问题的诞生标志着一个新的应用数学分支——数学规划时代的到来。过去的60年中，数学规划已经成为一门成熟的学科。其理论与方法被应用到经济、金融、军事等各个领域。数学规划领域内，其他重要分支的很多问题是在线性规划理论与算法的基础上建立起来的，同时也是利用线性规划的理论来解决和处理的。由此可见，线性规划问题在整个数学规划和应用数学领域中占有重要地位。因此，研究单纯形法的产生与发展对于认识整个数学规划的发展有重大意义。单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。概述：根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…xn的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。无最优解与无可行解是两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为无限最优解，或无界解。无最优解判别定理：在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解。无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。退化与循环：如果在一个基本可行解的基变量中至少有一个分量为零，则称此基本可行解是退化的基本可行解。产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。退化可能出现以下情况：①进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。②在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。事实上，已经有人给出了循环的例子。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。求解步骤：（1）确定初始基可行解①从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量；②对约束条件全为“=”连接的LP，化为标准形，左端添加松弛变量后即形成一个单位子矩阵；③约束条件中含有“=”或“=”连接的方程，在插入剩余变量后找不到单位矩阵，则必须采用“人造基”法，也称“人工变量”法。（2）最优性检验及解的判别准则①最优性判定准则②多重最优解判定准则③无界最优解判定准则（3）换基迭代①确定换入变量②确定换出变量③枢运算（旋转运算）单纯形法-正文：根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…xn的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。要缩小对最优解的搜索范围，就必须认识最优解的一般性质，最优解如果存在的话，则它必然处于可行区域的边界上。任何一项约束条件的边界方程是用“＝”号来替换该约束条件中的“≤”或“≥”号而得到的。每一个边界方程确定一个超平面。因此，可行区域的边界是由那些满足一个或同时满足几个边界方程（即处在作为边界的一个或几个超平面上）的可行解所组成，而且最优解必在其中。最优解不仅是在可行区域的边界上，而且也在这个区域的一个隅角上。一个可行解，如果不处在由另两个可行解连接起来的任何线段上，它就是一个角点可行解。如果连接两个角点可行解的线段处在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。角点可行解具有下列三个重要性质：①如果存在着一个最优解，那么它必定是角点可行解。如果存在有多个最优解，那么至少有两个最优解必定是相邻的角点可行解。②只存在有限个数的角点可行解。③如果一个角点可行解按目标函数值来衡量时比其所有的相邻角点可行解更好一些，那它就比所有其他角点可行解都更好，也就是最优解。上述这些性质构成单纯形法的原理基础。最后一个性质的重要性在于它为一个角点可行解是否是最优解提供了一种简便的检验标准，因而毋需列举所有的可行解。单纯形法正是利用了这个性质，只要检查少数的角点可行解，并且一旦这个最优性检验获得通过就可立即停止运算。单纯形法的运算步骤可归结为：①起始步骤──在一个角点可行解上开始。②迭代步骤──移动至一个更好一些的相邻角点可行解（根据需要反复进行这一步骤）。③停止法则──在当前角点可行解比所有相邻角点可行解都更好些时停止。当前角点可行解就是一个最优解。单纯形法的优点及其成功之处在于它只需要较少的有限次数的迭代，即可找到最优解。改进单纯形法：原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。对偶单纯形法：（DualSimplexMethod）1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题（DualProblem）为max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y=cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。