单纯形法理论

单纯形法理论单纯形法单纯形法，求解线性规划问题的通用方法单纯形是美国数学家丹齐克于年首先提出来的它的理论根据是线性规划问题的可行域是维向量空间g.b.中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到顶点所对应的1947n可行解称为基本可行解单纯形法的基本思想是先找出一个基本可行解，对它进rn行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行因基本可行解的个数有限，故经有限次转换必能得出问题的最优解如果问题无最优解也可用此法判别概述根据单纯形法的原理，在线性规划问题中，决策变量（控制变量），，的值称为一个解，满足所有的约束条件的解称为可行解使目标函数达到最大值x1x2…xn（或最小值）的可行解称为最优解这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）求解线性规划问题的目的就是要找出最优解最优解可能出现下列情况之一存在着一个最优解；存在着无穷多个最优解；不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不

①②阻止目标函数的值无限增大（或向负的方向无限增大）

③单纯形法的一般解题步骤可归纳如下把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解若基本可行解不存在，即

①约束条件有矛盾，则问题无解若基本可行解存在，从初始基本可行解作为起

②点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数

③值更优的另一基本可行解按步骤进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解若迭代过程中发现

④3问题的目标函数值无界，则终止迭代

⑤用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有个决策变量和个约束条件的线性规划问题已能在计算机上解得106改进单纯形法104原单纯形法不是很经济的算法年美国数学家丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法其基本步骤和单纯形法大致1953g.b.相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量对偶单纯形法（）年美国数学家莱姆基提出对偶单纯形法单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条dualsimplexmethod1954c.件为止对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失设原始问题为，，则其对偶问题（）为当原始问题的一个基解满足最优性条件时，其检验数min{cx|ax=b x≥0}dualproblem即知＝（称为单纯形算子）为对偶问题的可行解所谓满足对偶可行性，max{yb|ya≤c}cbb-1a-c≤0即指其检验数满足最优性条件因此在保持对偶可行性的前提下，一当基解成为可y cbb-1行解时，便也就是最优解其他信息数学优化中，由发明的单纯形法是线性规划问题的数值求解的流行技术有一个算法与此无关，但名称类似，它是法或称下山单纯形georgedantzig法，由和发现（年），这是用于优化多维无约束问题的一种数nelder-mead值方法，属于更一般的搜索算法的类别nelder mead1965这二者都使用了单纯形的概念，它是维中的个顶点的凸包，是一个多胞体直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等n n+1。