用单纯形法求解

单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止单纯形法的基本想法是从线性规划可行集的某一个顶点出发，沿着使目标函数值下降的方向寻求下一个顶点，面顶点个数是有限的，所以，只要这个线性规划有最优解，那么通过有限步选代后，必可求出最优解 。为了用选代法求出线性规划的最优解，需要解决以下三个问题 [2] ：(1)最优解判别准则，即迭代终止的判别标准 ；(2)换基运算，即从一个基可行解迭代出另一个基可行解的方法 ；(3)进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降

单纯形法的原理如下：首先设法找到一个（初始）基可行解，然后再根据最优性理论判断这个基可行解是否最优解。若是最优解，则输出结果，计算停止。若不是最优解，则设法由当前的基可行解产生一个目标值更优的新的基可行解，再利用最优性理论对所得的新基可行解进行判断，看其是否最优解，这样就构成一个迭代算法。由于基可行解只有有限个，而每次目标值都有所改进，因而必可在有限步内终止。如果原问题确有最优解，必可在有限步内达到，且计算量大大少于穷举法；若原问题无最优解，也可根据最优性理论及时发现，停止计算，避免错误及无效运算。"单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止 。

单纯性法的标准形式有下面三个特征：（1）目标函数统一为求极大值，也可以用求极小值；（2）所有约束条件（非负条件除外）都是等式，右端常数项为非负；（3）所有变量为非负。在将目标函数转化为标准形式的过程中，主要有三个部分的转换：1 变量的变换 2 目标函数的转换 3 约束方程的转换。1 变量的变换： 若存在取值无约束的变量 ,可令 ,其中： 。2 目标函数的转换： 统一求极大值，若是求极小值，则可将目标函数乘以（-1）。3 约束方程的转换：由不等式转换为等式，这一点可以通过引入松弛变量与剩余变量来解决。例：将下列线性规划问题化为标准形式。 结果如下：

线性规划问题的基本解法,利用图解法、单纯形法、数值模拟三种方法对同一道题进行分析解答,并列出详细步骤。将单纯形法的每一步所得结果与线性规划问题的图解法做出比较,通过几何意义,提高学生的解题能力和实际应用能力

第一步：基于约束条件方程组的系数矩阵，通过寻找或构造单位矩阵的方法，确定基变量，从而求出初始基本可行解，再利用初始基本可行解及线性规划模型提供的信息，编制初始单纯形表。第二步：将检验数cj-zj作为判断基本可行解是否为最优解的标准，（1）若所有非基变量的检验数cj-zj<0，已经达到最优解，计算停止。（2）若存在cj-zj>0，但所有cj-zj>0所在列对应的所有aij≤0，无最优解，计算停止。（3）若至少存在一个cj-zj>0，并且所对应的所有j列中至少有一个aij>0，没有达到最优解，转到第三步。第三步：继续迭代，求解下一个使目标函数更优的基本可行解。

  单纯形法计算分为下面几个步骤：①初始基可行解的确定，②求出基可行解，③最优性检验，④换基变量⑤迭代运算。   这样直接看步骤写出来一定很难以理解，它的内在思路是这样的，首先我们可以确定一组基，然后通过这一组基求出基可行解。这是①②步的工作，当我们求出了基可行解之后，我们还需要判断它是不是最优解，这就是第③步的工作最优性检验。假设我们检验后知道，所求的解是最优解，那运气确实很好，倘若不是也没有关系，我们就进入第四步换基变量。这样就可以求出新的一组基可行解，再进行最优性检测，直到找到最优解为止，这叫做迭代运算。

最小比值规则是保证变换后的解仍旧是可行解的方法,依据此规则,决定入基变量能够取得的正的最小值,否则,入基变量取得其他正值（大于最小正值）都会导致出现负的变量值.

作为一名数学系的学生，都没有写过关于数学的总结，正上运筹课，学到单纯形法，所以就把他的求解过程写一下。 我们都知道，一个线性规划问题，求解的办法有很多种，我们应用类似枚举法可以求解基本可行解的个数≤Cm,n个时的题目，但是如果可行解个数增大，我们就面临必须快速解决下面三个问题： 解决方法：   1.表格第一行，分别为目标函数变量的所有系数   2.表格第二行，left部分，有三项Cb,Xb,b 。right部分，是所有变量（包括基本变量，剩余变量，松弛变量，人工变量）。 3.表格最后一行，为目标函数-Z。Z的计算：变量的目标函数系数－Cb*约束函数变量的系数，然后求和。 4.中间几行，right部分分别为各约束函数的系数。left部分的Xb的确定，是根据right部分的出现单位矩阵的系数开始记录其变量。Cb是Xb的目标函数中的系数。b为当所有变量（除Xb 变量）为0，算出的结果。人工变量： 要使我们的目标函数实现最大化，所以人工变量必须从基变量中迅速换出去，否则目标函数不能实现最大化。 求解有两种方法：最小化求解和最大化求解 它们有一定的区别，上述方法用于最大化求解。 最小化问题求解： 进基选择判别数为负最小的那一个，在所有判别数大于等于0时达到最优解 最大化问题求解： 进基变量选取判别数为正的最大的那一个数，在所有判别数小于等于0达到最优解 共同点：离基变量均取比值最小的

单纯形法是求解线性规划问题的主要方法，而对偶单纯形方法是将单纯形方法应用于对偶问题的计算，对偶单纯性方法则提高了对求解线性规划问题的效率。初始基解可以是非可行解，当检验数都为负值时，就可以进行基的变换，不需加入人工变量，从而简化计算。对于变量多于约束条件的线性规划问题，用对偶单纯形法可以减少计算量，在灵敏度分析及求解整数规划的割平面法中，有时适宜用对偶规划单纯形法。

如果主列中的数都是负数，那么就不存在这最优解了请你仔细看下书，应该是这样写的

定理1：设 ，X是S的顶点的充要条件是X的非0元对应的A的列向量线性无关。这一定理可由反证法证明。证明:先证必要性．设X是S的顶点，不妨设 ， 是X的非0元， 是与这些非0元对应的A的列向量． 并设 线性相关．于是存在一组不全为0的常数α1 , α2 , ··· , αk，使得α1A1+ α2A2+ … + αkAk=0．令Z=( α1 α2 ··· αk 0 ··· 0 ),(m+n-k个0)．存在常数ε>0， 只要ε足够小，就有X±εZ≥0，并且 A(X± εZ )=b．但是X=(( X + εZ ) + ( X－ εZ ))/2，　　与X是S的顶点相矛盾．因而， 线性无关． 再证充分性．　　设X= ( x1 x2 ··· xk 0 ··· 0 )T∈S，(m+n-k个0), ，是这些非0元对应的 A的列向量，线性无关， 但X不是S的顶点，于是存在X1，X2∈S， X1≠X2，t∈( 0 , 1 )，X=tX1+ ( 1－t )X2．因为X的后n+ m －k个元都为0，所以X1，X2 的后n+ m－k个元也都为0．因而可设：　　X1=( x1(1) x2(1) ··· xk(1) 0 ··· 0 )T　　X2=( x1(2) x2(2) ··· xk(2) 0 ··· 0 )T　　令Y= X1－X2 = ( y1 y2 ··· yk 0 ··· 0 )T．　　因为X1≠X2，所以Y非全0向量．因AY=AX1-AX2=b-b=0，所以有y1A1 + y2A2 +···+ ykAk=0　　这与A1，A2， ··· ，Ak线性无关相矛盾．因而X是S的顶点． 　　证毕!推论：设 的秩为m,在非退化情况下，则X是S的顶点的充要条件是X的非0元为m个．定理2：设线性规划问题 有解，那么必可在S={X|AX=b,X≥0}的某个顶点上取得最大值。

包含关系。单纯形法中通常有两种方法大M法和两阶段法。因此单纯形法和大m法属于包含关系。单纯形法，可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式的单纯形法和表格形式的单纯形法。

单纯形法和图解法都可以求解线性规划问题,图解法适用于两个变量的线性规划问题,而单纯形法适用于任意个变量的问题.图解法还可用于揭示线性规划问题可行解集和最优解的特点,图形化表示单纯形法的搜索轨迹. 分支定界法和割平面法都是求解整数规划的算法,都是利用求解整数规划问题的线性松弛问题来间接求解原整数规划问题.分支定界法是通过迭代分割求解松弛问题的可行域,同时定出原问题的上下界的方法,属于隐式枚举法.割平面法则是通过迭代添加割平面来缩小线性松弛问题的可行域,而不改变原整数规划问题的可行域,直到一个整数可行解落到可行域的一个顶点上.二者计算量随着问题规模的增大而增大.

先将原题转化为标准模式，令z=-f，添加松弛变量x3,x4max z = 2x1+3x2+0x3+0x4st. x1 + x2 + x3 = 2 4x1 +6x2 + x4 = 9建立初始单纯形表 cj 2 3 0 0 cB xB b x1 x2 x3 x4 θ 0 x3 2 1 1 1 0 0 x4 9 4 6 0 1 σj 2 3 0 0将x2作为入基变量，求得θ为2, 3/2写入上表 cj 2 3 0 0 cB xB b x1 x2 x3 x4 θ 0 x3 2 1 1 1 0 2 0 x4 9 4 6 0 1 3/2 σj 2 3 0 0将x4作为离基变量，重新计算单纯形表 cj 2 3 0 0 cB xB b x1 x2 x3 x4 θ 0 x3 1/2 1/3 0 0 -1/6 3 x4 3/2 2/3 1 0 1/6 σj 0 0 0 -1/2存在非基变量x1的检验数σj=0，因此该题有无穷多最优解其中一个最优解是x1=0,x2=3/2得到max z = 9/2得到min f = -9/2

计算：最小比值为Ø=min{bi/aik，aik>0}，即为基变量值与所在行的换入变量所在列的对应的大于0的元素相除，得到的最小比值对应的哪一行，则行对应的基变量为换出变量。根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。对于线性规划问题使用单纯形法进行表上作业所得到的表格。直接用公式进行单纯形法的迭代计算是很不方便的，其中最复杂的是进行基变换，但施行基变换所用的实际上是消元法。由线性代数知道，用消元法解线性方程组可在增广矩阵上利用行初等变换进行计算。因此，我们可以将单纯形法的全部计算过程在一个类似增广矩阵的数表上进行，这种表格称为单纯形表。以上内容参考：百度百科-单纯形表

单纯形法计算线性规划的步骤：（1）把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。（2）若基本可行解不存在，即约束条件有矛盾，则问题无解

不用变。单纯形法的最小比值规则是为了保证变换后的解仍旧是可行解的方法。依据此规则，决定入基变量能够取得的正的最小值，否则，入基变量取得其他正值（大于最小正值）都会导致出现负的变量值。

如果依靠软件，比如MATLAB，MATHEMATICA什么的（甚至EXCEL），都有现成的线性规划的解决方案，照你图里面的条件输入就可以了（不知道具体的软件无法回答）。以下说明不用软件的手动计算单纯形法的标准方法。首先添加松弛变量，因为有3个方程，故添加3个松弛变量S1,S2,S3。约束方程组变为：2X1+X2+X3+S1=2(注意小于等于号变成了等于号，这就是添加松弛变量的作用）。X1+2X2+3X3+S2=52X1+2X2+X3+S3=6X1,X2,X3,S1,S2,S3>=0这是一个6个未知数（n），3个方程的方程组（m）。则选择n-m=3个变量作为“基变量”，让其余变量为0（非基变量）。使得方程组退化为：3个未知数，3个方程的方程组。然后根据对目标函数的影响迭代求解。注意：单纯形法是一个迭代（或者说尝试的过程）。先列出单纯形表(一个矩阵，里面的数据是目标函数和方程组的系数)。当我们选择从原点开始（令X1,X2,X3为0，则得到一个基本解：S1=2,S2=3,S3=6 , 目标函数X0=0；），则单纯形矩阵如下：( { {1, -3, -1, -3, 0, 0, 0, 0}, {0, 2, 1, 1, 1, 0, 0, 2}, {0, 1, 2, 3, 0, 1, 0, 5}, {0, 2, 2, 1, 0, 0, 1, 6} } )呃，不知道怎么在百度里面输入矩阵这种东西。。。反正第一行就是目标函数的方程的系数：X0-3X1-X2-X3+S1+S2+S3=0其他行就是下面的方程组。矩阵的最右边一列是方程的右边项。此时的矩阵是令X1,X2,X3为非基，S1,S2,S3为基的，代表“原点”（起始点）的矩阵，此时的目标：X0=0然后选择目标函数中系数最大的变量为“进基”（就是选他进入基变量组，设为0），选择解和“进基”变量之比为最小非负数的变量为“离基”（就是让他离开基变量组，不设为0）。在这里，选择X1作为进基（因为其在目标方程中的系数最小（负得最多，此题选X3也可），S1为离基（因S1行的解与X1系数之比为1，为最小非负数），然后进行矩阵运算（线性代数里面学的那些东西），使得矩阵的第一行中，代表X1,S2,S3的系数为0，S1不为0。继续矩阵变换，选择进基和离基，直到目标函数的所有系数非负（停止条件），如果是最小化问题则是非正。懒得算了，告诉你个结果吧。x0=27/5x1=1/5x2=0x3=8/5

在目标函数中用非基变量代替基变量，所得系数即是检验数。在目标规划中，p1p2p3不是具体算出来的值，而是按照原先的方法在草纸上写出计算校验数的式子，系数有p1p2p3就带着，整理会得到一个关于p1p2p3的式子，那一列填的就是这个式子中p1p2p3的系数，就这样一列一列就可以填好。单纯形法具体步骤为从线性方程组找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小了，决定下一步选择的单纯形。通过优化迭代，直到目标函数实现最大或最小值。扩展资料：目标规划中其他的单纯形法：1、对偶单纯形法。1954年美国数学家C.莱姆基提出对偶单纯形法(Dual Simplex Method)。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。2、下山单纯形法。数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现，这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。3、改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。参考资料来源：百度百科-单纯形法

两个常数项，所以两个最优解。对偶单纯形法对偶单纯形法是指从对偶可行性逐步搜索出原始问题最优解的方法。由线性规划问题的对偶理论，原始问题的检验数对应于对偶问题的一组基本可行解或最优解；原始问题的一组基本可行解或最优解对应于对偶问题的检验数；原始问题约束方程的系数矩阵的转置是对偶问题约束条件方程的系数矩阵。所以，在求解常数项小于零的线性规划问题时，可以把原始问题的常数项视为对偶问题的检验数，原始问题的检验数视为对偶问题的常数项。[1]

目标规划是将多目标问题，利用优先因子化成单目标问题，这样在用线性规划单纯形法求解时，将不同优先级对应的目标按优先级分开对待，即检验数按优先级高低来决定换入变量，这样就能保证优先级高的先满足。例子中P1.P2.P3三行检验数，即按优先级高低来寻找负检验数最大。也可以理解为将检验数按照优先因子分解，保证优先因子高的变量先换入。《共同纲领》教育条款是1949年9月通过的《中国人民政治协商会议共同纲领》《第五章文化教育政策》第41条：“中华人民共和国的文化教育为新民主主义的，即民族的、科学的、大众的文化教育。人民政府的文化教育工作，应以提高人民文化水平，培养国家建设人才，肃清封建的、买办的、法西斯主义的思想，发展为人民服务的思想为主要任务。”第 42 条：“提倡爱祖国、爱人民、爱劳动、爱科学、爱护公共财物为中华人民共和国全体国民的公德。”第 46 条：“中华人民共和国的教育方法为理论与实际一致。人民政府应有计划有步骤地改革旧的教育制度、教育内容和教学法。”第 47 条：“有计划有步骤地实行普及教育，加强中等教育和高等教育。注意技术教育，加强劳动者的业余教育和在职干部教育，给青年知识分子和旧知识分子以革命的政治教育，以应革命工作和国家建设工作的广泛需要。”第 56 条：“人民政府应帮助各少数民族的人民大众发展其政治、经济、文化、教育的建设事业。

具体想知道什么去百度文库看看单纯形法的PPT吧http://wenku.baidu.com/view/6961bf1f650e52ea55189827.html

化成标准形式后，可以用手机下载单纯形法计算器，很方便、好用

先将原题转化为标准模式，令z=-f，添加松弛变量x3,x4maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=24x1+6x2+x4=9建立初始单纯形表cj2300cbxbbx1x2x3x4θ0x3211100x494601σj2300将x2作为入基变量，求得θ为2,3/2写入上表cj2300cbxbbx1x2x3x4θ0x32111020x4946013/2σj2300将x4作为离基变量，重新计算单纯形表cj2300cbxbbx1x2x3x4θ0x31/21/300-1/63x43/22/3101/6σj000-1/2存在非基变量x1的检验数σj=0，因此该题有无穷多最优解其中一个最优解是x1=0,x2=3/2得到maxz=9/2得到minf=-9/2

单纯形法是一种求解线性规划问题的有效算法，可以解决任何线性规划问题。所有的线性规划问题都可以转化成标准型。

算法原理相同,前者是直接求解原问题,后者是通过求解其对偶问题,利用对偶理论得到原问题的最优解.

为方便查阅，再link一下 教材 。 假设我们讨论的LP问题有 个变量与 个限制条件。 基本概念部分大概就是这些。第一次看不用要求自己完全理解，不妨先继续往下学习再慢慢理解这些概念。 单纯形方法的示意图如下： 我们先从一下四点直观的认识入手。 由于书上根本就没有优化操作的概念，所以在此我自己给出其定义： 我们称增加的这个非基本变量为 输入变量 ，变为0的这个基本变量为 输出变量 。因为输入变量取代了输出变量成为新的基。（基的定义可以在前面找到。） 通俗一点地说就是选择一个非基本变量，让其不断增加，要求： 回到主题。之前提到单纯形法即对一个基本解实施若干次优化操作后得到最优解的过程。我们先不考虑最优解的存在性，且断言： 任意非基本变量增加不使得目标函数增加等价于目标函数取得最大值。 这是因为由于符号的限制，非基本变量只能增加，而所有的变量都可以被非基本变量表示。因此非基本变量的增加包含了所有变量的各种变化。 当无法再进行优化操作时有两种可能。一种是任意非基本变量的增加不使得目标函数增加。此时目标函数取最大值。另外一种情况是任意非基本变量的增加不使得某一基本变量变为0。注意， LP问题的标准形式中对于变量的所有限制最终都会归结于符号限制 ，因此若基本变量不会变为0，则非基本变量可以无限地增加。 此时LP问题无界。 还有一点需要注意的是优化操作一定会在有限步后结束，之后会讲到这一点。 经过上述讨论我们对单纯形算法的核心步骤应该有一个大致的了解了。 下面是一个小小的总结 单纯形算法到此结束

对偶单纯形法是指从对偶可行性逐步搜索出原始问题最优解的方法。对偶单纯形方法纯形方法的一种对称变形．对于原单纯形方法而言，在迭代过程中始终保持相应的解对原问题是可行的，并不断改善对偶问题解（即判别系数）的可行性，直至可行。而对偶单纯形方法则是始终保持对偶问题的解的可行性，并不断改善原问题解的可行性，直至满足原问题。在求解常数项小于零的线性规划问题时，可以把原始问题的常数项视为对偶问题的检验数，原始问题的检验数视为对偶问题的常数项。优缺点1、对偶单纯形法的优点： 不需要人工变量；当变量多于约束时，用对偶单纯形法可减少迭代次数。2、对偶单纯形法缺点： 在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。

单纯形法没有单位矩阵课采用人造基。在线性规划问题的单纯形法中，若标准化后找不到单位矩阵，可以采用人造基，给方程加入人工变量后，用大M法和两阶段法处理求解。

从最终表中，按照决策对应松弛原则，检验数的相反数就是对偶问题最优解你是指从当前2113单纯形表得到原问题和对偶问题的解吗？原问题的解看5261表的左侧，其中基变量对应的值就是4102b对应的列，非基变量等于零；对偶问题的解看表的下侧检验数行，原问题变量对1653应的检验数为对偶问题松弛变量的值乘回以-1，原问题松弛变量的检验数为对偶问题变量的值乘以－1。

添加2个人工变量后，变量数目变为5个约束条件还是2个，也就是基变量数目不会变还是两个（但是是谁可能会变的，这取决于检验数，换基迭代）计算检验数时，非基变量检验数大于零就行了，最后取值时基变量的值就是b变化后所得的值，非基变量全部取零

用单纯形法求解线性规划问题时，需要有一个单位矩阵作为初始基，当约束条件都是“≤”时，约束条件标准化后，其松弛变量均为正数，在约束方程组的系数矩阵中，就形成了一个初始基。但是，实际问题中常常出现“≥”或“=”的约束条件，经标准化后，约束方程组系数不存在单位矩阵，因而没有一个现成的初始基本可行解。为了解决此问题，采用人造基的办法，在约束方程中引入非负的人工变量。这种人工变量与前述松弛变量不同，它没有物理意义，仅是为了求解方程方便而引入，所以解的结果必须使这些变量为零，才能保持改变后的问题与原题等价，否则，说明原题无解。处理人工变量的方法有-M法和两阶段法。1.-M法当线性规划数学模型中含有“≥”或“=”的约束方程时，需在其左端加一非负的人工变量yi，构成单位矩阵。但加入yi后的方程，就与原约束方程不等价，所以必须保证在最后的解中，yi=0才能与原约束方程等价。为此，在目标函数式中，给加入的人工变量yi一个很大的系数，对极大问题，系数用-M表示；对极小问题，系数用M表示（M本身为正值）。只有当yi=0时，才能使-Myi=0，目标函数才达到最优化。yi由于具有很大的系数而得到严格的控制，故这个-M称为“惩罚因子”。当具有“≥”或“=”的约束方程加入人工变量yi后，即可以yi作为初始基本解，按上述单纯形法计算。2.两阶段法两阶段单纯形法就是将线性规划问题分两个阶段求解。第一阶段是判断原线性规划问题是否有解，并寻求一个初始基本可行解。为此，用人工变量的和代替原来的目标函数，构造一个辅助规划，这个辅助规划具有一个单位矩阵，应用单纯形法，使辅助规划的目标函数最小化。若此辅助规划的最优解使其目标函数等于零，则说明没有一个人工变量在基本变量内取值，从而可得到原问题的一个基本可行解，转向第二阶段。否则，如果最小值为正，那么问题就以不存在可行解而结束。第二阶段是求原问题的最优解。在第一阶段最后单纯形表的基础上，去掉人工变量，然后以第一阶段求得的最优解作为第一个基本可行解，以原问题的目标函数，继续用单纯形法进行迭代，直到求得最优解为止。

单纯形法是针对求解线性规划问题的一个算法，这个名称里的"单纯形"是代数拓扑里的一个概念，可以简单将"单纯形"理解为一个凸集，标准的线性规划问题可以表示为: min（or max） f(x)=cx s.t. Ax=b x>=0,b>=0 以上形式称为线性规划标准型，使用单纯型法时，如果约束条件含有不等式时需新增变量（松弛变量、人工变量）转化为标准型，min. f(x)=cx指求函数最小值（也可以是求最大值），x是一个Rn维向量代表有n个变量，线性规划问题主要是面向实际问题，x变量可以代表距离、成本、价格、数量等，线性规划问题中要求x大于等于0，c同样是一个Rn维向量，这样cx实际上就是一个线性函数f(x);s.t.代表subject to代表服从于意思，这里是指变量x需要满足的约束条件，A是一个Rm*n维矩阵，代表有m个等式约束。下面是一个约束是不等式的情形: min -4x1-x2 s.t. -x1+2x2<=4 2x1+3x2<=12 x1-x2<=3 x1,x2>=0 求解上面这个问题只要初中数学知识即可，具体可以使用代数法或几何的方法轻松得到，考虑到实际问题当中变量x是多维的，约束条件也会比示例多的多，这就需要一个一劳永逸的算法能通过计算机来获得正解，单纯形法就是这样的一个算法。单纯形法最早由 George Dantzig于1947年提出，单纯形法对于求解线性规划问题是具有跨时代意义的，其实不仅仅是针对线性规划，非线性规划问题在求解的过程中也大量依赖单纯形法，

在求解常数项小于零的线性规划问题时，使用对偶单纯形法，可以把原始问题的常数项视为对偶问题的检验数，原始问题的检验数视为对偶问题的常数项。

单纯形法的迭代点术语称为下山点。单纯形法的分类：单纯形法，可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式的单纯形法和表格形式的单纯形法。前者提供基本算法所依据的逻辑规则，适用于在电子计算机上进行求解运算；后者将变量和数据列成表格，适用于笔算。两者在数学上是等价的。单纯形法是由美国数学家G.B.丹齐克（1914～）于1947年提出来的，它与苏联数学家Л.Β.坎托罗维奇（1912～）于1938年提出的解乘数法相类似。与角点有关的单纯形法原理：1、如果存在着一个最优解，那么它必定是角点可行解。如果存在有多个最优解，那么至少有两个最优解必定是相邻的角点可行解。2、只存在有限个数的角点可行解。3、如果一个角点可行解按目标函数值来衡量时比其所有的相邻角点可行解更好一些，那它就比所有其他角点可行解都更好，也就是最优解。上述这些性质构成单纯形法的原理基础。最后一个性质的重要性在于它为一个角点可行解是否是最优解提供了一种简便的检验标准，因而毋需列举所有的可行解。单纯形法正是利用了这个性质，只要检查少数的角点可行解，并且一旦这个最优性检验获得通过就可立即停止运算。

主要步骤：1，建初始表2，求检验数（cj-zj），是否都小于等于0，不是度就要进行出基入基操作3，检验数大的入基4，确认哪个出基，确认方法：比较几个问基的(最后一个数除以入基列的数)的值答，小的出基5，将要入基变量替换出基那一列，替换方法回：1），把之前的确认的入基和出基交点处的那个答数变为+12），把另一行对应此列的数这为0 6，重复2~5步

　　单纯形法检验数计算方法是：用基变量在目标函数中的系数，乘以要算得那个变量对应的系数列的各个值，并求和，再减去要算得那个变量在目标函数中对应的系数，就是检验数。 　　单纯形法就是秉承“保证每一次迭代比前一次更优”的基本思想：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进后更优的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。

单纯形法 simplex method 求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。 最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。

单纯形法simplex method求解线性规划问题的通用方法.单纯形是美国数学家G.B.丹齐克于1947年首先提出来的.它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到.顶点所对应的可行解称为基本可行解.单纯形法的基本思想是：先找出一个基本可行解,对它进行鉴别,看是否是最优解；若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是,则再转换,按此重复进行.因基本可行解的个数有限,故经有限次转换必能得出问题的最优解.如果问题无最优解也可用此法判别.根据单纯形法的原理,在线性规划问题中,决策变量（控制变量）x1,x2,…x n的值称为一个解,满足所有的约束条件的解称为可行解.使目标函数达到最大值（或最小值）的可行解称为最优解.这样,一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）.求解线性规划问题的目的就是要找出最优解.最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解,这只在两种情况下发生,即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）.单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解.②若基本可行解不存在,即约束条件有矛盾,则问题无解.③若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解.④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善）,即得到问题的最优解.⑤若迭代过程中发现问题的目标函数值无界,则终止迭代.用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数.现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解,对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得.改进单纯形法原单纯形法不是很经济的算法.1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差,提出改进单纯形法.其基本步骤和单纯形法大致相同,主要区别是在逐次迭代中不再以高斯消去法为基础,而是由旧基阵的逆去直接计算新基阵的逆,再由此确定检验数.这样做可以减少迭代中的累积误差,提高计算精度,同时也减少了在计算机上的存储量.对偶单纯形法1954年美国数学家C.莱姆基提出对偶单纯形法.单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解,直到检验数满足最优性条件为止.对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解.在迭代过程中始终保持基解的对偶可行性,而使不可行性逐步消失.设原始问题为min{cx|Ax=b,x≥0},则其对偶问题为 max{yb|yA≤c}.当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0.即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解.所谓满足对偶可行性,即指其检验数满足最优性条件.因此在保持对偶可行性的前提下,一当基解成为可行解时,便也就是最优解.数学优化中,由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术.有一个算法与此无关,但名称类似,它是Nelder-Mead法或称下山单纯形法,由Nelder和Mead发现（1965年）,这是用于优化多维无约束问题的一种数值方法,属于更一般的搜索算法的类别.这二者都使用了单纯形的概念,它是N维中的N + 1个顶点的凸包,是一个多胞体：直线上的一个线段,平面上的一个三角形,三维空间中的一个四面体,等等.

单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在三种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。单纯形法引例 http://course.cug.edu.cn/cugFirst/operational_research/main/charpter1/p3.htm例1求解第一节例1所示的线性规划问题。 解：将其标准化后得到首先，我们找出一个初始基本可行解。由于变量 分别只出现在（1.8）式的一个方程中，它们的系数列向量构成单位矩阵，成为线性规划的一个基。于是 就是基变量， 是非基变量。若令 ， ，可得 。显然， 可作为本问题的一个初始基本可行解。（我们将在本章第四节中讨论求解初始基本可行解的一般方法。）

单纯形法 　　simplex method 　　求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。　　根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。 　　最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。　　单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 　　用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。 　　改进单纯形法 　　原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。 　　对偶单纯形法 　　1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 　　数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。 　　这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

可能是因为它比较帅吧

单纯形法 　　simplex method 　　求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。　　根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。 　　最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。　　单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 　　用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。 　　改进单纯形法 　　原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。 　　对偶单纯形法 　　1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 　　数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。 　　这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

1、先划LP标准型2、看是否有现成的可行基(之后看检验数，换基迭代)3、没有现成的可行基就用两阶段法先求解辅助问题，判断原问题是否有可行基

单纯形法是求解线性规划问题最常用、最有效的算法之一。它的计算步骤如下：1、把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解 。2、若基本可行解不存在，即约束条件有矛盾，则问题无解。3、若基本可行解存在，以初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。4、按步骤3进行迭代，直到对应检验数满足最优性条件(这时目标函数值不能再改善)，即得到问题的最优解。5、若迭代过程中发现问题的目标函数值无界，则终止迭代 。单纯形法的概念：单纯形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止。

单纯形法是一种迭代算法，其基本原理及主要步骤是：首先设法找到一个（初始）基可行解，然后再根据最优性理论判断这个基可行解是否最优解。若是最优解，则输出结果，计算停止；若不是最优解，则设法由当前的基可行解产生一个目标值更优的新的基可行解，再利用最优性理论对所得的新基可行解进行判断，看其是否最优解，这样就构成一个迭代算法。由于基可行解只有有限个，而每次目标值都有所改进，因而必可在有限步内终止。如果原问题确有最优解，必可在有限步内达到，且计算量大大少于穷举法；若原问题无最优解，也可根据最优性理论及时发现，停止计算，避免错误及无效运算。

1要保持基变量的取值非负2计算中应进行矩阵的初等行变换

可以。因为最小比值规则是保证变换2113后5261的解仍旧是可行解的方法，依据此规4102则，决定入基变量能够取得的正的最小1653值，否则，入基变量取得其它正值（大于最小正值）都会导致出现负的变量值。确定换入基和换出基的变量之后，把所对应的那个数不是用括号圈上了，比方说换入基变量为x2，换出基变量为x5，假设所对应的那个被圈上的数是5，为了进一步形成新的单纯形表，一开始的单纯形表里，5所在的那行要全乘5分之1(包括那行的b)。性质1等式两边同时加上(或减去)同一个整式，等式仍然成立。若a=b那么a+c=b+c性质2等式两边同时乘或除以同一个不为0的整式，等式仍然成立。若a=b那么有a·c=b·c或a÷c=b÷c （c≠0）

1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

单纯形法是一种迭代算法，其基本原理及主要步骤是：首先设法找到一个（初始）基可行解，然后再根据最优性理论判断这个基可行解是否最优解。若是最优解，则输出结果，计算停止；若不是最优解，则设法由当前的基可行解产生一个目标值更优的新的基可行解，再利用最优性理论对所得的新基可行解进行判断，看其是否最优解，这样就构成一个迭代算法。由于基可行解只有有限个，而每次目标值都有所改进，因而必可在有限步内终止。如果原问题确有最优解，必可在有限步内达到，且计算量大大少于穷举法；若原问题无最优解，也可根据最优性理论及时发现，停止计算，避免错误及无效运算。