、单纯形法的基本原理非基本·基本解与基本可行解可得到基本解为：可行解例：对方程组X=(-2500)T@ x,+x2-X3+2x4=3同样对①、②施行初等变换②L 2x,+x2 -3x4=1还可以得到：1.4x+x2-0.6x3=2.2③施行初等变换，可以得到：-0.2 x, -0.2 x3+ x,=0.4(4X +X3-5x4=-2基本④X2-2x3+7x4=5此时，基本变量为x2可行解非基本变量为x1和式③和④为典型方程组，基基本解为：X（02.200.4）T本变量是x1和x2，非基本变量为x3和x4。、单纯形法的基本原理（五）单纯形法的原理单纯形法的基本思路是：根据问题的标准形式，从可行域中的一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并目使目标函数的值逐步增大：当目标函数达到最大值时，问题就得到了最优解。21
21
、单纯形法的基本原理在用单纯形法求解线性规划问题时，应考虑的问题：1.建立初始基本可行解2．最优性检验3．基本可行解的改进、单纯形法的基本原理建立初始基本可行解：在用单纯形法求解时，首先应将线性规划问题以标准形式表达、约束条件以典型方程组表示，确定初始基本可行解。初始基本可行解获取的步骤：1．将线性规划问题化为标准形式通过初等变换（行变换）将约束条件以典型方程组表示2.3.另非基变量等于零，得到基变量大于等于零的初始基本可行解。22
22
单纯形法的基本原理·最优性检验用非基变量表示基变量x,=b’-Zax(i-l,2,m)j=m+1将上式代入目标函数式，整理后得Zeadx,Z-Ze,b+Z(c,V-1j=m+1Zo,Z.-Ze,b:z,=令(j=m+1,m+2,...,n)H1nEc(2-6)Z=Z+-Z,)x于是j=m+1、单纯形法的基本原理由于当-1,2，…m时，z,=c,=c,i=1即c,-Z,=0所以式2-6也可写作Z=Z。 + Z (c, -Z,)x, =Z + Z(c, -Z,)x,+Z(e, -Z,)x)j=#+1j=m+1i=1Z =Z。+Z(cj -Z,)xji-1再令=c,-Z，（j=1，2，，n）,为变量x的检验数则 Z=Z。+ZCxjj-123
23
、单纯形法的基本原理（1）最优解判别若x(o）=(b'b,...b"0..0)为基本可行解且对一切j=1,2,…，n有0，则X(0）为最优解。（2）无有限最优解判别(bb,·.·b"0....0)为基本可行解若X(0）=有一个C,>0，且对一切i=1,2..,m有β≤0（β为约束条件方程中的系数，k=l，2，..，n）该线性规划问题无有限最优解（或称有无界解或无最优解）。、单纯形法的基本原理基本可行解的改进：若初始基本可行解X(O)不是最优解及不能判别无最优解时，需找一个新的基本可行解1.进基变量的确定max(C, >0) =C则对应的x为进基变量。进基变量所在的列（k）称为枢列。2.出基变量的确定2>0/b,min(0.]=min)BaJβ则基本变量X,为出基变量出基变量所在的行（1）称为枢行枢行与枢列交点处的元素（β）称为枢元24
24
、单纯形法的表格形式单纯形法的计算步骤：一找出初始基本可行解，建立初始单纯形表一检验对应于非基本变量的检验数C，若对所有的C,≤0（i=1，2，…，n），则已得到最优解，计算最优值。否则，转入下一步。一在所有C>0中，若有一个C,对应x，的系数列向量，即对i=，m均有β≤0，则此问题无有限最优解（或称有无1.2.界解或无最优解），停止计算。否则转入下一步。根据Max（C>0）=C，确定x为进基变量，再依据"最小比值规则”（[>0-）确定x为出基变min(0=min量。Lpkβe实施以枢元素为中心的初等变换，使约束方程组变为关于新的基本变量的典型方程组，得到新的单纯形表，重复第步..，一直到没有新的非基本变量可以改善目标函数为止二、单纯形法的表格形式[例6]现以本章第一节的例1来说明单纯形法的表上作业方法。maxZ =30x,+25x2x+4x2≤40s.133x+2x2≤30[,x ≥025
25