线性规划及单纯形法课件

第二章

线性规划及单纯形法§1线性规划问题及模型§2图解法§3单纯形方法及大M法§4线性规划应用举例分析1第二章线性规划及单纯形法§1线性规划问题及模型1§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥02§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两线性规划的组成要素：目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素建模步骤1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件3线性规划的组成要素：3一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥04一般形式4对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法。例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)§2图解法5对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作（1）画出线性规划问题的可行域，如图所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图16（1）画出线性规划问题的可行域，如图所示。x1x2x2=0x（2）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。得到最优解：x1=50，x2=250，最优目标值z=27500x1x2z=20000=50x1+100x2图2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE7（2）目标函数z=50x1+100x2，当z取某一固定值时得例2某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？8例2某公司由于生产需要，共需要A，B两种原料至少3解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q9解：目标函数：Minf=2x1+3x21重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。10重要结论：10线性规划的标准化——引入松驰变量（含义是资源的剩余量）例1中引入s1，s2，s3模型化为目标函数：Maxz=50x1+100x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0

对于最优解

x1=50x2=250，s1=0s2=50s3=0说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。11线性规划的标准化——引入松驰变量（含义是资源的剩余量）11线性规划的标准化线性规划标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥012线性规划的标准化12

可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:13可以看出，线性规划的标准形式有如下四个特131.极小化目标函数的问题：设目标函数为Minf=c1x1

+c2x2

+…+cnxn

(可以)令z＝-f，则该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即Minf＝-Maxz141.极小化目标函数的问题：142、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi可以引进一个新的变量s，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)显然，s也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=bi152、约束条件不是等式的问题：15当约束条件为

ai1x1+ai2x2+…+ainxn

≥bi时，类似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-s=bi16当约束条件为16为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

3.右端项有负值的问题：

在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。17为了使约束由不等式成为等式而引进的变量s,当3.右端例：将以下线性规划问题转化为标准形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,将目标函数转换成极大化：令z=-f=-2x1+3x2-4x3

其次考虑约束，有2个不等式约束，引进松弛变量x4，x5

≥0。第三个约束条件的右端值为负，在等式两边同时乘-1。18例：将以下线性规划问题转化为标准形式

18通过以上变换，可以得到以下标准形式的线性规划问题：Maxz=-2x1

+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0

在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。19通过以上变换，可以得到以下标准形式的线性规划问题：19§3单纯形方法及大M法单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划的问题的单纯形表解法几种特殊情况20§3单纯形方法及大M法单纯形法的基本思路和原理201单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。通过第二章例1的求解来介绍单纯形法:在加上松弛变量之后我们可得到标准型如下：目标函数：max50x1+100x2

约束条件：x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250.xj≥0（j=1，2）,sj≥0（j=1，2,3）211单纯形法的基本思路和原理单纯形法的基本思路：从可它的系数矩阵,

其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。

基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。22它的系数矩阵,22非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。在此例中我们不妨找到了

为A的一个基，令这个基的

非基变量x１，s2为零。这时约束方程就变为基变量的约束方程：

23非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有x2+s1＝300，x2=400，x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=－100，s2=0，s3=－150由于在这个基本解中s1=－100，s3=－150，不满足该线性规划s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。24x2+s1＝300，24一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。

25一般来说判断一个基是否是可行基，只有在求出其基本解以在本例题中我们就找到了一个基是单位矩阵。在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。26在本例题中我们就找到了一个基是单位矩阵。26二、最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解。1.最优性检验的依据——检验数σj一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。27二、最优性检验272.最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数≤0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式

由于所有的xj的取值范围为大于等于零，当所有的都小于等于零时，可知是一个小于等于零的数，要使z的值最大，显然只有为零。我们把这些xj取为非基变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。**对于求目标函数最小值的情况，只需把≤0改为≥0282.最优解判别定理28三、基变换通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。为了换基就要确定换入变量与换出变量。1.入基变量的确定从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题中σ2=100是检验数中最大的正数，故选x2为入基变量。29三、基变换292.出基变量的确定在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？

如果把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可以确定为出基变量。能否在求出基本解以前来确定出基变量呢？以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？

302.出基变量的确定30我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。在本例题中约束方程为

在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得

31我们把确定出基变量的方法概括如下：把已确定的入基变量其中的值最小，所以可以知道在原基变量中系数向量为

的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。令非基变量为零，得x2+s1=300,x2+s2=400,x2=250.求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.这时目标函数值为50x1+100x2=50×0+100×250=25000。显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好得多。下面我们再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。3232在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数的表达式。可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：以下用表示基变量，用表示非基变量。33在讲解单纯形法的表格形式之前，先从一般数学模把第i个约束方程移项，就可以用非基变量来表示基变量xi，把以上的表达式带入目标函数，就有其中：34把第i个约束方程移项，就可以用非基变量来表示基变量上面假设x1,x2,…xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列向量为则其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。max50x1+100x2+0·s1+0·s2+0·s3.x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250，x1,x2,s1,s2,s3≥0.把上面的数据填入如下的单纯形表格35上面假设x1,x2,…xm是基变量，即第i行约按照线性规划模型在表中填入相对应的值，如上表所示；在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；在行中填入cj-zj所得的值，如；z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列；初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此确定s3为出基变量；由于，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。迭代次数基变量cBx1x2s3s4s5b比值Bi/ai2501000000s1s2s3000111002101001001300400250300/1400/1250/150100000z=036迭代次数基变量cBx1x2以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3分量上，所以这个单位向量是也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。在上表中第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.迭代次数基变量cBx1x2s3s4s5b比值bi/aij501000001s1s2x2001001010-12001-1010015015025050/1150/2—50000-1002500037以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初从上表可以看出，第一次迭代的，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50,s3=0,这时z=27500。由于检验数都<0，因此所求得的基本可行解为最优解，z=27500为最优目标函数值。实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。迭代次数基变量cBx1x2s3s4s5b比值bi/aij501000002x1s2x25001001010-100-211010015050250

00-500-502750038从上表可以看出，第一次迭代的以例2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。目标函数：约束条件：加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：

大M法

39以例2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划

至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个统一的解法，我们把所有求目标函数最小值的问题化成求目标函数最大值的问题。具体做法只要把目标函数乘以（－1）。

要注意到人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解了。为了竭尽全力地要求人工变量为零，我们规定人工变量在目标函数中的系数为－M，这里M为任意大的数。这样只要人工变量M＞0，所求的目标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则该问题无可行解。40至于目标函数，在标准型中并不一定要求求最大值或最小此例的数学模型如下所示：目标函数：maxz=－2x1－3x2－Ma1－Ma2.

约束条件：x1+x2－s1+a1=350，x1－s2+a2=125，2x1+x2+s3=600，x1，x2，s1，s2，s3，a1，a2≥0.像这样，为了构造初始可行基得到初始可行解，把人工变量“强行”地加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为－M，这个方法叫做大M法，M叫做罚因子。

41此例的数学模型如下所示：41下面我们就用大M法来求解此题:迭代次数基变量cBx1x2s1s2s3a1a2b比值-2-3000-M-M0a1a2a3-M-10012100100350125600350/1125/1600/2zj-2M-MMM0-M-M-2+2M-3+M-M-M000-475M1a1x2s3-M-2001-1001-1100-1001010210-2225125350225-----350/2zj

-2-MM-M+20-M-M-20-3+M-MM-2002-2M-225M-2502a1x1s2-M-2001/2-10-1/21011/2001/20001/20111/2300/1/2175/1/2zj

-2-1/2M-1M01/2M-1-M001/2M-2-M0-1/2M+10-M-50M-60042下面我们就用大M法来求解此题:迭代次数基变量cBx1从上表中可知检验数都小于零。已求得最优解为：x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最优值为f=-z=-(-800)=800。迭代次数基变量cBx1x2s1s2s3a1a2b比值

-2-3000-M-M3x2x1s2-3-2001-20-12010101-1000111-1-1100250125

zj

-2-3401-4000-40-1-M+4-M

-80043迭代次数基变量cBx1x2二、两阶段法两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题：目标函数：约束条件：44二、两阶段法44

注意：此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。45注意：此线性规划的约束条件与原线性规迭代次数基变量cBx1x2s1s2s3a1a2b比值-2-3000-1-10a1a2s3-1-1011-10010100-10012100100350125600350/1125/1600/2zj-2-1110-1-1-21-1-1000-4701a1x1s3-10001-1101-1100-1001010210-2225125350zj

0-11-10-1101-110022252x2x1s300001-11010100-100100111-1-1225125125zj

000000000000-1-1046迭代次数基变量cBx1x2迭代次数基变量cBx1x2s1s2s3b比值-2-30000x2x1s3-3-2001-110100-1001021225125125225/1125/2zj-2-33-1000-310-9251x2x1s2-3-2001-20-11010100111100250125zj

-2-340100-40-1-800从表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。47迭代次数基变量cBx1x2

一、无可行解例1、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：填入单纯形表计算得：48一、无可行解解：在上述问题的约束条件中加入松驰变量、剩余变迭代次数基变量CBx1x2s1s2s3a1b比值2030000-M0s1s2a100-M31010001001001100-111503040150/10—40/1zjcj-zj-M-M00M-M20+M30+M00-M0-40M1x2s2a1300-M3/1011/100001001007/100-1/100-1115302515/(3/10)30/125/(7/10)zjcj-zj9-7/10M303+M/100M-M11+7/10M0-3-M/100-M0450-25M2x2x1a13020-M011/10-3/100010010000-1/10-7/10-116304zjcj-zj20303+M/1011+7M/10M-M00-3-M/10-11-7M/10-M0780-4M49迭代次数基变量CBx1x2

从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得x1+x2-0+4=40,即有：x1+x2=36≤40.并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。二、无界解在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二章中的例子。例2、用单纯形表求解下面线性规划问题。

50从第二次迭代的检验数都小于零来看，可知第2

迭代次数基变量CBx1x2s1s2b比值11000s1s2001-110-3201161—zjcj-zj0000110001x1s2101-1100-13119zjcj-zj1-11002-101填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：51迭代次数基变量CBx1x2

从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题：=-1,=-1,找不到大于零的来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：移项可得：52从单纯形表中，从第一次迭代的检验数等于2，

由于M可以是任意大的正数，可知此目标函数值无界。上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数，并且该列的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。三、无穷多最优解例3、用单纯形法表求解下面的线性规划问题。53由于M可以是任意大的正数，可知此目标函数值

解：此题我们用图解法已求了解，现在用单纯形表来求解。填入单纯形表计算得：54解：此题我们用图解法已求了解，现在用单纯形表来求解迭代次数基变量CBx1x2s1s2s3b比值50500000s1s2s3000111002101001001300400250300/1400/1250/1zjcj-zj00000505000001s1s2x200501010-12001-1010015015025050/1150/2—zjcj-zj0500050500000125002x1s2x2500501010-100-211010015050250—50/1250/1zjcj-zj5050500000-50001500055迭代次数基变量CBx1x2

这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数等于零外，非基变量s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：迭代次数基变量CBx1x2s1s2s3b50500003x1s3x25005010-11000-21101