第5章 单纯形法

1、123单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划的问题的单纯形表解法几种特殊情况41管理运筹学第五章 单 纯 形 法图解法的局限性？1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。管理运筹学即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。管理运筹学一、单纯形法的基本思想1、顶点的逐步转移顶点转移的依据？根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解， 就一定可以在可行域的顶点上

2、找到。于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解， 那么肯定在可行域的顶点中可以找到至少一个最优解。管理运筹学转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值2需要解决的问题：(1)为了使目标函数逐步变优，怎麽转移？ (2)目标函数何时达到最优判断标准是什麽？管理运筹学单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无

3、最优解为止。通过第二章例1的求解来介绍单纯形法:在加上松弛变量之后我们可得到标准型如下：目标函数： max 50x1+100x2约束条件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj0 （j=1，2）,sj0（j=1，2,3）6管理运筹学1单纯形法的基本思路和原理它的系数矩阵, 101111000100A = ( p1 , p2 , p3 , p4 , p5 ) = 2 01其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。基： 已知A是约束条件的mn系数矩阵，其秩为

4、m。若B是A中mm阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。7管理运筹学1单纯形法的基本思路和原理非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有nm个。由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。在此例中我们不妨找到了0为A的一个基，令这个基的11000B3 = 111

5、非基变量x，s2为零。这时约束方程就变为基变量的约束方程：8管理运筹学1单纯形法的基本思路和原理x2+s1=300，x2=400， x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=100，s2=0，s3=150由于在这个基本解中s1=100，s3=150，不满足该线性规划s10，s30的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解 是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。9管理运筹学1单纯形法的基本思路和原理一般来说判断一个基是否是可行基，

6、只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如， 01001 10 00那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。10管理运筹学1单纯形法的基本思路和原理在本

7、例题中我们就找到了一个基是单位矩阵。100100B2= 0 01在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。11管理运筹学1单纯形法的基本思路和原理二、 最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解。1. 最优性检验的依据检验数j一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非

8、基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为i。显然所有基变量的检验数必为零。在本例题中目标函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知1=50，2=100，3=0，4=0，5=0。12管理运筹学1单纯形法的基本思路和原理2.最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解， 如果所有检验数s j 0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解

9、判别定理。设用非基变量表示的目标函数为如下形式z = z0 + s j xjjJ由于所有的xj的取值范围为大于等于零，当所有的s j都小于等于零时，可知 s j xj 是一个小于等于零的数，要使z的值最大，显然s j xj 只有为零。我们把这些xj取为非基jJ变量(即令这些xj的值为零)，所求得的基本可行解就使目标jJ函数值最大为z0。*对于求目标函数最小值的情况，只需把s j 0改为s j 013管理运筹学1单纯形法的基本思路和原理三、 基变换通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得

10、求解得到的新的基本可行解，其目标函数值更优。为了换基就要确定换入变量与换出变量。1. 入基变量的确定从最优解判别定理知道，当某个j0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的j0，则为了使目标函数增加得更大些，一般选其中的j最大者的非基变量为入基变量，在本例题中2=100是检验数中最大的正数，故选x2为入基变量。14管理运筹学1单纯形法的基本思路和原理2. 出基变量的确定在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？如果

11、把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3=0， 我们也可以从下式：x2 +s1=300， x2+s2=400， x2=250，求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因为此解满足非负条件，是基本可行解，故s3可以确定为出基变量。能否在求出基本解以前来确定出基变量呢？以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？15管理运筹学1单纯形法的基本思路和原理我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项的值

12、，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。在本例题中约束方程为x1 + x2 + s1 = 300, 2x1 + x2 + s2 = 400,x2 + s3 = 250.在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得b1= 300 = 300,b2= 400 = 400,b3= 250 = 250.a121a221a32116管理运筹学1单纯形法的基本思路和原理b3的值最小，所以可以知道在原基变量中系数向量为e= (0, 0,1)T其中3a32的基变量s3为出基变量，这样可知x

13、2，s1，s2为基变量，x1，s3为非基变量。令非基变量为零，得x2+s1=300, x2+s2=400, x2=250.求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.这时目标函数值为50x1+100x2=500+100250=25000。显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好得多。下面我们再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。17管理运筹学1单纯形法的基本思路和原理单纯形法原理（用代数方法求解LP）例1-6max Z = 2x1 + 3x2+ 3x3

14、x1+ x2+ x3 3(劳动力约束)（原材料约束）s.t.x1 + 4x2+ 7x3 9x , x, x 0123管理运筹学第一步：引入非负的松弛变量x4,x5,LP化为标准型将该max Z = 2x1 + 3x2+ 3x3+ 0x4+ 0x5(劳动力约束)（原材料约束）x1+ x2+ x3+ x4= 3s.t x+ 4x+ 7x+ x= 9.1235x , x, x, x, x 012345管理运筹学第二步：寻求初始可行基，确定基变量1010141710B = (P4 ,P ) = 1A = 1501x4，x5；对应的基变量是第三步：写出初始基本可行解和相应的目标函数值管理运筹学两个关键的

15、基本表达式： 用非基变量表示基变量的表达式管理运筹学x4= 3 - x1 - x2- x3x= 9 - x- 4x- 7x5123初始基本可行解X (0)= (0,0,0,3,9)T用非基变量表示目标函数的11111表达式请解释结果的经济含义 不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为0！管理运筹学Z = 2x1+ 3x2+ 3x3当前的目标函数值Z (0)= 0第四步：分析两个基本表达式，看看目标函数是否可以改善？ 分析用非基变量表示目标函数的表达式非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加通常把非基变量前面的系数叫“检验数”；管理运筹学Z

16、 = 2x1+ 3x2+ 3x3 选哪一个非基变量进基？选x1为进基变量（换入变量）问题：能否选其他的非基变量进基？a 任意一个a 任意一个正检验数对应的非基变量a 最大正检验数对应的非基变量a 排在最前面的正检验数对应的非基变量管理运筹学由用非基变量表示基变量的表达式当x1增加时，x4，x5会减小，但有限度必须大于等于0，以保持解的可行性！于是x 31x= 3 - x 0 39D1= 3=q41x min,11 911x= 9 - x 0x511管理运筹学x4= 3 - x1x= 9 - x51- x2- x3- 4x2- 7x3当x1的值从0增加到3时，x4首先变为0，此时x5=60因此选

17、x4为出基变量（换出变量）。这种用来确定出基变量的规则称为“最小比值原则”（或原则）。管理运筹学如果P10，会出现什麽问题？最小比值原则会失效！m 基变换新的基变量x1,x5；新的非基变量x2,x3,x4；写出用非基变量表示基变量的表达式：由可得新的基本可行解X（1）=（3，0，0，0，6）T管理运筹学x1 = 3 - x2 - x3 - x4x= 6 - 3x- 6x+ x5234x4 = 3 - x1 - x2 - x3x= 9 - x- 4x- 7x 5123 写出用非基变量表示目标函数的表达式:检验数仍有正的返回进行讨论。管理运筹学可得相应的目标函数值为Z（1）=6Z = 2x1 +

18、3x2 + 3x3= 2(3 - x2 - x3 - x4 ) + 3x2 + 3x3= 6 + x2 + x3 - x4第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解!为什麽？分析用非基变量表示目标函数的表达式， 如果让负检验数所对应的变量进基，目标函数值将下降！管理运筹学在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 s的表达式。j可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：max z = c1x1 + c2 x2 + cn xn .+ a1,n xn+ a2,n x

19、n+ a1,m+1xm+1+ a2,m+1 xm+1+= b1,= b2 ,x1x2+ am,m+1xm+1+ am,n xn= bm ,xmxj 0.( j = 1, 2, m) 表示基变量，用 xj, n)( j = m +1, m + 2,xi (i = 1, 2, n)以下用表示非基变量。30管理运筹学2单纯形法的表格形式把第i个约束方程移项，就可以用非基变量来表示基变量xi，xi = bi- ai,m+1xm+1 - ai,m+2 xm+2- ai,n xn, m)n(i = 1, 2,= bi -aij xj .j =m+1把以上的表达式带入目标函数，就有mn+ cn xn = c

20、i xij =m+1z = c1 x1 + c2 x2+c j x ji=1nn(- z j )x j = z0 + sj =m+1= z0 +cj x jjj =m+1mz0 = cibi ,i=1s j= cj- z j ; a1 j其中：) a2 jm= i=1= (c , c ,= c a+ c a+ cazc a, cjiij1 1 j22 jmmj12m amj= (c1, c2 , cm ) p j31管理运筹学2单纯形法的表格形式上面假设x1,x2,xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的第i行约束方

21、程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列( j = 1, 2, n) 则z j = (cB1,pj向量为, cBm ) pj = (cB ) pj ,其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵， 而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。max 50x1+100x2+0s 1+0s 2+0s 3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3

22、=250，x1, x2, s1, s2, s30. 把上面的数据填入如下的单纯形表格32管理运筹学2单纯形法的表格形式按照线性规划模型在表中填入相对应的值，如上表所示；在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3； 在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；在 s j = cj- z j 行中填入cj-zj所得的值，如s1 = 50 - 0 = 50；z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列； 初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0

23、;由于250/1最小，因此确定s3为出基变量；由于s2 s1 0，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。33管理运筹学迭代次数基变量cBx1x2s1s2s3b比值Bi/ai2501000000s1 s2 s3000111002101001001300400250300/1400/1250/1zjs j = cj - z j0000050100000z=02单纯形法的表格形式以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，

24、由于主元在p2的第3 分量上，所以这个单位向量是e= (0, 0,1)T 也就是主元素变成1。这样我们又得到的第1次迭代的单纯表3如下所示。在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变 为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使 第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.34管理运筹学迭代次数基变量cBx1x2s1s2s3b比值bi/aij501000001s1 s2 x2001001010-12001-

25、1010015015025050/1150/2zjs j = cj - z j01000010050000-100250002单纯形法的表格形式从上表可以看出，第一次迭代的 s1= 50 0，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27500。由于检验数都观察法观察系数矩阵中是否含有现成的单位阵？ LP限制条件中全部是“”类型的约束将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；管理运筹

26、学线性规划限制条件都是“”或“=”类型的约束先将约束条件标准化，再引入非负的人工变量， 以人工变量作为初始基变量，其对应的系数列向量构成单位阵， 称为“人造基”；然后用大M法或两阶段法求解；管理运筹学使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样， 出现在单纯形表格中的B(i)列（即约 束方程的右边常数）值正好就是基变量的取值。（注意：用非基变量表示基变量的表达式）管理运筹学等式约束左端引入人工变量的目的讨论如果限制条件中既有“”类型的约束，又有“”或“=”类型的约束，怎麽办？为什麽初始可行基一定要选单位阵？b列正好就是基变量的取值，因此称b列为

27、解答列管理运筹学构造“不完全的人造基”！（2）写出初始基本可行解根据“用非基变量表示基变量的表达式”， 非基变量取0，算出基变量，搭配在一起构成初始基本可行解。2、建立判别准则：（1）两个基本表达式的一般形式就LP限制条件中全部是“”类型约束，新增的松弛变量作为初始基变量的情况来描述：管理运筹学此时LP的标准型为管理运筹学nn+mMaxZ= c j x j+0x jj =1j =n+1a11 x1 + a12 x2+L + a1n xn+ xn+1= b1ax+ ax+ L + ax+ x= b2112222nnn+22s.t.MMMax+ ax+L + ax+ x= bm11m 22mnnn

28、+mmx1 , x2 ,L, xn+m 0初始可行基 ：初始基本可行解：管理运筹学X (0)= (0,0,L,0,b ,b ,L,b)T12m 10L0B (0)= (P, P,L, P) = 01L0n+1n+2n+m MMMM 00L1一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式 为：用非基变量表示目标函数的表达式：管理运筹学nx= b- ax,i = 1,2L, mn+iiijjj =1n+mnmnc j x jn+in+ijjjjj=1j=1i=1j=1imn- ci=1 j=1+a xn+iijjnmc + b ,jj0n iijj=1i=1ii=管理运筹学mn+i

29、=1nZ0 + s j x j j=1令s j =c j - z jnZ0 + (c j - z j )x j j=1mn+iij=1mn+iij=1mn+iii=1m= cbn+iii=1nc j x j j=1niijjj=1是（2）最优性判别定理对应于基B的基本可若行解，是非基变量s的检验数，若对于(0)jxj一切非基变量的角指标j，均有为最优解。0，则X(0)（3）无“有限最优解”的判别定理= (0,0,L,0,b ,b ,L,b )为一基本可行解，有若 X (0)12ms k 0一非基变量xk,其检验数,而对于i=1,2,，m，均有 0 ，则该线性规划问题aik没有“有限最优解”。管

30、理运筹学s jX (0) = (0,0,L,0,b ,b ,L,b )12m证明思路构造性证明：依据用非基变量表示基变量的表达式构造一族可行解，其对应的目标函数值趋于无穷大。几何意义：沿着边界前进的一族可行解管理运筹学举例：用非基变量表示基变量的表达式代表两个约束条件：x2对应的系数列向量P2=（1，3）T，当前的换入变量是 X2，按最小比值原则确定换出变量：管理运筹学x1 + x2 + x3 + x4= 33x2 + 6x3 - x4 + x5= 6x1= 3 - x2- x3- x4x= 6 - 3x- 6x+ x5234= 3= 6- x3 - x4 0x1要求：x- 6x+ x 052

31、34于是：如果x2的系数列变成P2=（-1，0）T,则用非基变量表示基变量的表达式就变成；x1= 3 + x2 - x3 - x4 0x= 6 + 0x- 6x+ x 05234可行性自然满足,最小比值原则失效,意即x2的值可以任意增大原线性规划无“有限最优解”。管理运筹学x2 3 /1 x min3 /1,6 / 2= qx 6 / 322- x2- 3x3、进行基变换（1） 选择进基变量原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）； 进基变量对应的系数列称为主元列。 （2） 出基变量的确定按最小比值原则确定出基变量，为的是保持解的可行性； 出基变量

32、所在的行称为主元行。 主元行和主元列的交叉元素称为主元素。管理运筹学4、主元变换（旋转运算或枢运算）按照主元素进行矩阵的初等行变换把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量）写出新的基本可行解，返回最优性检验。管理运筹学求解思想顶点的逐步转移， 条件是使目标函数值不断得到改善。管理运筹学单纯形法小结第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数 阵中有一个单位阵。确定初始可行基，写出初始基本可行解管理运筹学表格单纯形法求解步骤第二步：最优性检验计算检验数，检查：j所有检验数是否 0？是结束，写出最优解和目

33、标函数最优值；k还有正检验数检查相应系数列 0？ 是结束，该LP无“有限最优解”！l不属于上述两种情况，转入下一步基变换。 确定是停止迭代还是转入基变换？管理运筹学第三步：基变换选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。确定进基变量和出基变量。管理运筹学第四步 换基迭代（旋转运算、枢运算)利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。完成一次迭代，得到新的基本可行解和相应的目标函数值管理运筹学停止迭代的标志（停机准则）该迭代过程直至

34、下列情况之一发生时停止 检验数行全部变为非正值；（得到最优解）或主元列 0（最优解）依据：最优性检验的两个定理管理运筹学最优性判别定理；无“有限最优解”判断定理五、各种类型线性规划的处理 1、分类及处理原则：（1）类型一：目标要求是“Max”，约束条件是“”类型左边加上非负松弛变量变成等式约束（ 约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。管理运筹学（2）类型二：目标要求是“Max”，约束条件是“=”类型左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵， 然后用大M法或两阶段法求解。（3）类型三：目标要求是“

35、Max”，约束条件是“”类型约束条件标准化，左边减去非负的剩余变量，变成等式约束，化为类型二。管理运筹学（4）类型四：目标要求是“Min”方法1化为极大化问题方法2按照极小化问题直接在单纯形表格上计算处理，但管理运筹学相应的原则要作改动。 2、处理人工变量的方法：（1）大M法在约束条件中人为地加入非负 的人工变量，以便使它们对应的系数列向量构成单位阵。问题：加入的人工变量是否合理？如何处理？在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中， 只要基变量中还存在人工变量，目标函数就不可能实现极大化惩罚！管理运筹学结果最优表中，基变量不包含人工变量，则最优解就是原线性

36、规划的最优解，不影响目标函数的取值；最优表中，基变量中仍含有人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！管理运筹学（2） 两阶段法第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函 数极小化，约束条件与原线性规划相同。管理运筹学3、用表格单纯形法直接计算极小化线性规划时要修改哪些原则？（初始表？最优解判别？换入变量？换出变量？旋转运算？引入人工变量？） 最优性判别：所有检验数非负换入变量的选择原则：（最小）负检验数所对应的变量进基，以保证目标函数值（较快）减小；用大M法求解

37、时，在目标函数中人工变量的前面添上一个很大的正系数M；管理运筹学六、迭代过程中可能出现的问题及处理方法1、为确定出基变量要计算比值，该比值= 解答列元素/主元列元素。对于主元列的0 元素或负元素是否也要计算比值？（此时解的可行性自然满足，不必计算；如果主元列元素全部为0元素或负元素， 则最小比值失效，线性规划无“有限最优解”）管理运筹学2、现若干个相同的最小比值怎麽办？的基本可行解，即非0分量（说明出现了的个数小于约束方程的个数。按照“摄动原理”所得的规则，从相同比值对应的基变量中选下标最小的基变量作为换出变量可以避免出现“死循环”现象）3、选择进基变量时，同时有若干个正检验数，怎麽选？管理运

38、筹学（最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基）课堂练习：直接按极小化问题求解下面的LP：管理运筹学MinZ=x1+ 2x2- x1+ 2x2 2s.t x 3.1x 0, x 012管理运筹学CBXBcj xjb1200MqjX1X2X3X4X5MX52-120-1012/20X431010_-Z-2M1+M2-2MM0020X2X413-1/21-1/201/210010-Z-22010M-1由最优表得：最优解为X*=（0，1，0，3，0）T, 相应的目标函数最优值为Zmin=2管理运筹学一、大M法以第二章的例2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。min f = 2x1 + 3x2.x1 + x2 350,x1 125,2x1 + x2 600,x1 , x2 0.目标函数：约束条件：加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：x1 + x2 - s1 = 350,x1 - s2 = 125,2x1 + x2 + s3 = 600,x1 , x2 , s1 , s2 , s3 0.76管理运筹学3求目标函数值最小的线性规划的问题的单纯形表解法至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个统