第5章--单纯形法ppt课件.ppt

《第5章--单纯形法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第5章--单纯形法ppt课件.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、经济与管理学院经济与管理学院 何宜军何宜军管理运筹学管理运筹学管理运筹学管理运筹学 主讲：何宜军主讲：何宜军第五章第五章 单纯形法单纯形法n1 单纯形法的基本思路和原理n2 单纯形法的表格形式n3 求目标函数值最小的线性规划的问题的 单纯形表解法n4 几种特殊情况管理运筹学管理运筹学 主讲：何宜军主讲：何宜军1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理 单纯形法的基本思路基本思路：从可行域中某一个顶点顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者

2、能判断出线性规划问题无最优解为止。 通过第二章例1的求解来介绍单纯形法: 在加上松弛变量之后我们可得到标准形式如下： 目标函数： max 50 x1+100 x2 约束条件：x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250. xi0 （i=1，2）,sj0 （j=1，2,3）管理运筹学管理运筹学 主讲：何宜军主讲：何宜军它的系数矩阵, 其中pj为系数矩阵A第j列的向量。A的秩为3，A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。 基基： 已知A是约束条件的mn系数矩阵，其秩为m。若B是A中mm阶非奇异子矩阵（即可逆矩

3、阵可逆矩阵），则称B是线性规划问题中的一个基。 基向量：基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理100100101200111),(54321pppppA管理运筹学管理运筹学 主讲：何宜军主讲：何宜军非基变量：非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n nm m个。 由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零令这个基的非

4、基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。 在此例中我们不妨找到了 为A的一个基，令这个基的 非基变量非基变量x x，s s2 2为零为零。这时约束方程就变为基变量的约束方程：1010010113B1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理管理运筹学管理运筹学 主讲：何宜军主讲：何宜军 x2+s1300， x2=400， x2+s3=250. 求解得到此线性规划的一个基本解一个基本解： x1=0，x2=400，s1=100，s2=0，s3=150 由于在这个基本解中s1=100，s3=150，不满足该线性规划s10，s30的约束条件

5、，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。 我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。1 单纯形法的基本思路和原理单纯形法的基本思路和原理管理运筹学管理运筹学 主讲：何宜军主讲：何宜军 如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如， 那么显然所求得的基本解一定一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。0100011001 单纯形法的基本思路和原理单纯形法的基本思路和原理管理运筹学管

6、理运筹学 主讲：何宜军主讲：何宜军 在本例题中我们就找到了一个基是单位矩阵。 在第一次第一次找可行基时，所找到的基或为单位矩阵单位矩阵或为由单位矩阵为由单位矩阵的各列向量所组成的矩阵的各列向量所组成的矩阵，称之为初始可行基初始可行基，其相应的基本可行解叫初始基本可行解初始基本可行解。 如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基构造初始可行基，具体做法在以后详细讲述。1000100012B1 单纯形法的基本思路和原理单纯形法的基本思路和原理管理运筹学管理运筹学 主讲：何宜军主讲：何宜军概念辨析概念辨析1 1、可行解不一定是基本解，基本解也不一定是可行解！

7、、可行解不一定是基本解，基本解也不一定是可行解！2 2、基本解不一定是基本可行解，基本可行解一定是基本解！、基本解不一定是基本可行解，基本可行解一定是基本解！3 3、可行解不一定是基本可行解，基本可行解一定是可行解！、可行解不一定是基本可行解，基本可行解一定是可行解！注意注意可行解和基本解的定义出发点不同，没有必然联系管理运筹学管理运筹学 主讲：何宜军主讲：何宜军二、最优性检验二、最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。1. 最优性检验的依据检验数j 一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处

8、理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中目标函数中所有变量的系数所有变量的系数即为各即为各变量的检验数变量的检验数，把变量把变量x xi i的检验数记为的检验数记为i i。显然所有基变量的检验数所有基变量的检验数必为零必为零。在本例题中目标函数为50 x1+100 x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知1=50，2=100，3=0，4=0，5=0。1 单纯形法的基本思路和原理

9、单纯形法的基本思路和原理管理运筹学管理运筹学 主讲：何宜军主讲：何宜军1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理n 2.最优解判别定理 对于求最大求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理最优解判别定理。设用非基变量表示的目标函数为如下形式 由于所有的xj的取值范围为大于等于零，当所有的 都小 于等于零时，可知 是一个小于等于零的数，要使z的值最大，显然 只有为零。我们把这些xj取为非基变量(即令这些xj的值为零)，所求得的基本可行解就使基本可行解就使目标函数值最大为目标函数值最大为z0。*对

10、于求目标函数最小值求目标函数最小值的情况，只需把 0改为 0j0jjj Jzzxjjjj Jxjjj Jxjj管理运筹学管理运筹学 主讲：何宜军主讲：何宜军1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理三、三、 基变换基变换 下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。为了换基就要确定换入变量换入变量与换出变量换出变量。1. 入基变量的确定 从最优解判别定理知道，当某个j0时，我们选基检验数大于基检验数大于0 0的非的非基变量换到基变量中去（称之为入基变量）基变量换到基变量中去（称之

11、为入基变量）。 若有两个以上的j0，则为了使目标函数增加得更大些，一般选其中的j j最大者的非基变量为入基变量最大者的非基变量为入基变量， 在本例题中2=100是检验数中最大的正数，故选x2为入基变量。管理运筹学管理运筹学 主讲：何宜军主讲：何宜军1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理2. 出基变量的确定 我们把确定出基变量的方法概括如下： 把已确定的入基变量入基变量在各约束方程中的正正的系数除除其所在约束方程中的常数项的值，把其中最小比值最小比值所在的约束方程中的原基变量确定为出基变量出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。 【备注】负的系

12、数和0系数不参与计算比较！管理运筹学管理运筹学 主讲：何宜军主讲：何宜军1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理在本例题中约束方程为: 在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得12112223300,2400,250.xxsxxsxs312122232300400250300,400,250.111bbbaaa管理运筹学管理运筹学 主讲：何宜军主讲：何宜军1 1 单纯形法的基本思路和原理单纯形法的基本思路和原理 其中 的值最小，所以可以知道在原基变量中系数向量为 的基变量s3为出基变量出基变量，这样可知x2，s1，s2为基变量，x1，

13、s3为非基变量。 令非基变量为零，得 x2+s1=300, x2+s2=400, x2=250. 求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150. 这时目标函数值为 50 x1+100 x2=500+100250=25000。 显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好得多。 下面我们再进行检验其最优性再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。332ba30,0,1Te 管理运筹学管理运筹学 主讲：何宜军主讲：何宜军2 2 单纯形法的表格形式单纯形法的表格形式

14、在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）： 以下用 表示基变量基变量，用 表示非基变量非基变量。j112211,111,122,112,2,11,max.,0.1,2,nnmmnnmmnnmm mmm nnmjzc xc xc xxaxaxbxaxaxbxaxaxbxjn1,2,ix im1,2,jxjmmn管理运筹学管理运筹学 主讲：何宜军主讲：何宜军2 2 单纯形法的表格形式单纯形法的表格形式 把第i个约束方程移项，就可以用非基变量来表示基变量用非基变量来表示基变量xi， 把以上的表

15、达式带入目标函数，就有 其中：,11,22,1.1,2,iii mmi mmi nnniijjj mxbaxaxaxba xim1 122110011mnnniijjij mnnjjjjjj mj mzc xc xc xc xc xzczxzx01,;miijjjizcbcz121 12212112,jmjjiijjjmmjmimjmjaazc ac ac ac ac ccac ccp管理运筹学管理运筹学 主讲：何宜军主讲：何宜军2 2 单纯形法的表格形式单纯形法的表格形式 上面假设x1,x2,xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生

16、变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列向量为 则 其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。1,2,jpjn1,jBBmjBjzccpcp管理运筹学管理运筹学 主讲：何宜军主讲：何宜军2 2 单纯形法的表格形式单纯形法的表格形式 单纯形法的表格形式单纯形法的表格形式是把用单纯形法求出基本可行解、是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用表格的形式有些像增

17、广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。矩阵的行的初等变换。 以下用单纯形表格来求解第二章的例1。 max 50 x1+100 x2+0s1+0s2+0s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s30. 把上面的数据填入如下的单纯形表格。管理运筹学管理运筹学 主讲：何宜军主讲：何宜军2 2 单纯形法的表格形式单纯形法的表格形式n 按照线性规划模型在表中填入相对应的值，如上表所示；n 在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；n 在zj行中填入第第j列与列与cB列中对应的元素相乘再相

18、加所得的值列中对应的元素相乘再相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；n 在 行中填入cj-zj所得的值，如 ；n z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列；n 初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;n 由于250/1最小，因此确定s3为出基变量出基变量；n 由于 ，因此确定x2为入基变量入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。jjjcz迭代次数基变量 cB x1 x2 s1 s2 s3 b比值Bi/ai2 50 100 0 0 00

19、s1 s2 s3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1300400250300/1400/1250/1 zj 0 0 0 0 0 50 100 0 0 0z=0jjjcz150050210管理运筹学管理运筹学 主讲：何宜军主讲：何宜军2 2 单纯形法的表格形式单纯形法的表格形式n 以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得具体的做法用行的初等变换使得x2的系数向量的系数向量p2变换成单位向量变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是 也就是主元素变成1。这样我们

20、又得到的第1次迭代的单纯表如下所示。n 在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。n 求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.30,0,1Te jjjcz迭代次数基变量 cB x1 x2 s1 s2 s3 b 比值 bi/aij 50 100 0 0 01 s1 s2 x2 0 0 100 1 0 1 0 -1 2 0 0 1 -1 0 1 0 0 1 50

21、150 250 50/1 150/2 zj 0 100 0 0 100 50 0 0 0 -10025000管理运筹学管理运筹学 主讲：何宜军主讲：何宜军迭代次数基变量 cB x1 x2 s1 s2 s3 b 比值 bi/aij 50 100 0 0 02 x1 s2 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50 250 zj 50 100 50 0 50 0 0 -50 0 -50275002 2 单纯形法的表格形式单纯形法的表格形式n 从上表可以看出，第一次迭代的 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正

22、数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。n 从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27500。n 由于检验数都0，因此所求得的基本可行解为最优解， z=27500为最优目标函数值。n 实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。1500jjjcz管理运筹学管理运筹学 主讲：何宜军主讲：何宜军单纯形法的表格计算步骤：单纯形法的表格计算步骤：第一步第一步：将线性规划方程（max）转化为标准形式标准形式；第二步第二步：画单纯性表格，找系数矩阵的单位矩阵（或单位矩阵的列向量构成的矩阵），确定

23、基变量；第三步第三步：计算zj和j的的值，如果所有j0，则计算终止。第四步第四步：选择j中最大者，确定入基变量。再用常数项除以入基变量对应的正系数，选最小比值作为出基变量；第五步第五步：通过初等行变换，求新的基向量的基本可行解。依次迭代迭代，直到所有的j0，计算终止。如果目标函数是求min，要通过换元转化成求max！管理运筹学管理运筹学 主讲：何宜军主讲：何宜军单纯形法的表格计算步骤：单纯形法的表格计算步骤：矩阵初等行变换的三种运算： 1、某一行，乘以一个非零倍数。 2、某一行乘以一个非零倍数，加到另一行。 3、某两行，互换。注意注意单纯形法中只能用前两种运算，不能用第3种运算！管理运筹学管理

24、运筹学 主讲：何宜军主讲：何宜军0,24261553).(2max21212121xxxxxxtsxxz性规划问题。例、用单纯形法求解线补充练习：补充练习：0,24261553).(002max,2121221121212121ssxxsxxsxxtsssxxzss标准型：得到该线性规划问题的量题中，分别加入松驰变解：在上述线性规划问迭代次数基变量 cB x1 x2 s1 s2 b比值Bi/ai2 2 1 0 00 s1 s2 0 0 3 5 1 0 6 2 0 1 152415/324/6 zj 0 0 0 0 2 1 0 0 z=0jjjzc 1 s1 x1 0 2 0 4 1 -1/2

25、1 1/3 0 1/6 343/44/(1/3) zj 2 2/3 0 1/3 0 1/3 0 -1/3 2 x2 x1 1 2 0 1 1/4 -1/8 1 0 -1/12 5/243/415/4 zj 2 1 1/12 7/24 0 0 -1/12 -7/24jjjzc jjjzc 4334341522max,)41543(),(2121xxzxxXTT故有：，所以，最优解为管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法一、大M法n 以第二章的例2来讲解如何用单纯形表的方法求解目标函数值最小

26、目标函数值最小的线性规划问题。n 目标函数：n 约束条件：n 加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：12min23.fxx1211212350,125,2600,0.xxxxxx x1211212312123350,125,2600,0.xxsxsxxsx x s s s管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法 把所有求目标函数最小值的问题化成求目标函数最大值的问题目标函数最小值的问题化成求目标函数最大值的问题。 具体做法只要把目标函数乘以（1）。 要注意到人工变量是与松

27、弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解了。 为了竭尽全力地要求人工变量为零，我们规定人工变量在目标函数中的规定人工变量在目标函数中的系数为系数为M M，这里M M为任意大的数为任意大的数。这样只要人工变量M0，所求的目标函数最大值就是一个任意小的数。 这样为了使目标函数实现最大就必须把人工变量从基变量中换出。必须把人工变量从基变量中换出。 如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则该问题无

28、可行解无可行解。管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法 此例的数学模型如下所示： 目标函数： max z=2x13x2Ma1Ma2. 约束条件：x1+x2s1+a1=350， x1s2+a2=125， 2x1+x2+s3=600， x1，x2，s1，s2，s3，a1，a20. 像这样，为了构造初始可行基构造初始可行基得到初始可行解，把人工变量人工变量“强行”地加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为求最大值的目标函数里的系

29、数为M M，这个方法叫做大M法，M叫做罚因子。 管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法下面我们就用大M法来求解此题:迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3 a1 a2b比值比值 -2 -3 0 0 0 -M -M0a1a2s3-M-M0 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2M -M M M 0 -M -M-2+2M -3+M -M -M 0 0 0-475M

30、1a1x2s3-M-20 0 1 -1 0 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0 -2225125350225-350/2 zj -2 -M M -M+2 0 -M -M-2 0 -3+M -M M-2 0 0 2-2M-225M-2502a1x1s2-M-20 0 1/2 -1 0 -1/2 1 0 1 1/2 0 0 1/2 0 0 0 1/2 0 1 1/2 0 -15030017550/1/2300/1/2175/1/2 zj -2 -1/2M-1 M 0 1/2M-1 -M 0 0 1/2M-2 -M 0 - 1/2M+1 0 -M-50M-600jjj

31、czjjjczjjjcz管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法n 从上表中可知检验数都小于零。n 已求得最优解为： x1=250,x2=100,s1=0, s2=125,s3=0,a1=0,a2=0，其最优值为 f=-z=-(-800)=800。jjjcz迭代迭代次数次数基变基变量量 cB x1 x2 s1 s2 s3 a1 a2 b 比值比值 -2 -3 0 0 0 -M -M3 x2 x1 s2 -3 -2 0 0 1 -2 0 -1 2 0 1 0 1 0 1 -1 0 0 0 1

32、 1 1 -1 -1 100 250 125 zj -2 -3 4 0 1 -4 0 0 0 -4 0 -1 -M+4 -M -800管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法二、两阶段法 两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。 第一阶段：第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题先求解下列线性规划问题： 目标函数： 约束条件：12max;zaa 1211122

33、1231212312350,125,2600,0.xxsaxsaxxsx x s s s a a管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法 注意：第一阶段，线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。 如果最终目标函数值大于零，则原问题无可行解可行解，停止计算。 如果最终目标函数值等于零，即说明存在一个可行解，使得所有的人工变量都为零。进入第二阶段计算。 管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求

34、目标函数值最小的线性规划的问题的单纯形表解法迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3 a1 a2b比值比值 0 0 0 0 0 -1 -10a1a2s3-1-10 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2 -1 1 1 0 -1 -1-2 1 -1 -1 0 0 0-4751a1x1s3-100 0 1 -1 1 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0 -2225125350 zj 0 -1 1 -1 0 -1 1 0 1 -1 1 0 0

35、2-2252x2x1s3000 0 1 -1 1 0 1 0 1 0 0 -1 0 0 1 0 0 1 1 1 -1 -1225125125jjjczjjjczjjjcz管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯形表解法 第二阶段： 将第一阶段的最终单纯形表中的人工变人工变量取消量取消，将目标函数换成原问题的目标函数，把第一阶段的可行解作为初始可行解进行迭代计算。管理运筹学管理运筹学 主讲：何宜军主讲：何宜军3 3 求目标函数值最小的线性规划的问题的单纯形表解法求目标函数值最小的线性规划的问题的单纯

36、形表解法迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3b比值比值 -2 -3 0 0 0 0 x2x1s3-3-20 0 1 -1 1 0 1 0 0 -1 0 0 1 0 1 1225125125225/1125/2 zj-2 -3 3 -1 0 0 0 -3 1 0-9251x2x1s2-3-20 0 1 -2 0 -1 1 0 1 0 1 0 0 1 1 1100250125 zj -2 -3 4 0 1 0 0 -4 0 -1-800 从表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。

37、jjjczjjjcz管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 . 0,40,30,1501033020max212112121xxxxxxxxxz约束条件目标函数一、无可行解一、无可行解 例例1、用单纯形表求解下列线性规划问题、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到： 121121121231121231max2030310150,30,40,0.zxxMaxxsxsxxsax xs ss a目标函数约束条件 填入单纯形表计算得：填入单纯形

38、表计算得：管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2 s1 s2 s3 a1b比值比值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1zjcj-zj-M -M 0 0 M -M20+M 30+M 0 0 -M 0-40M1x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)zjcj-zj9-7

39、/10M 30 3+M/10 0 M -M11+7/10M 0 -3-M/10 0 -M 0 450-25M2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304zjcj-zj20 30 3+M/10 11+7M/10 M -M0 0 -3-M/10 -11-7M/10 -M 0780-4M管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 从第二次迭代的检验数都小于零来看，可知第从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可次迭代所得的基本可行解已经是最优解了，其最大的目

40、标函数值为行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得代入第三个约束方程得x1+x2-0+4=40,即有：即有：x1+x2=3640. 并不满足原来的约束条件并不满足原来的约束条件3，可知原线性规划问题，可知原线性规划问题无可行解无可行解，或者说，或者说其可行解域为空集，当然更不可能有最优解了。其可行解域为空集，当然更不可能有最优解了。 像这样只要求线性规划的最优解里有像这样只要求线性规划的最优解里有人工变量大于零人工变量大于零，则此线性规，则此线性规划划无可行解无可行解。管理

41、运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 二、无界解二、无界解 在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取任意的大。数值可以取任意的大。 下面我们用单纯形表来求下例。下面我们用单纯形表来求下例。例例2 2、用单纯形表求解下面线、用单纯形表求解下面线性规划问题。性规划问题。 12121212max1,326,0.zxxxxxxx x目标函数约束条件管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 迭代迭代次数次数基基变变量量CBx1 x2 s1

42、s2b比比值值1 1 0 00s1s2001 -1 1 0-3 2 0 1161zjcj-zj0 0 0 0 1 1 0 001x1s2101 -1 1 0 0 -1 3 119zjcj-zj1 -1 1 00 2 -1 0 1填入单纯形表计算得：填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：解：在上述问题的约束条件中加入松驰变量，得标准型如下：121211221212max1,326,0.zxxxxsxxsx xs s目标函数约束条件管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 12a 从单纯形表中，从第一次迭代的检验数等于从单纯

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

44、数值可以取得无限大。从标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：次迭代的单纯形表中，得到约束方程：22a22a 移项可得：移项可得：1212121,39.xxsxss121221211212121,39.,0,1,0,9.121.xxssxsxM sxMxMssMzxxMMM 不妨设可得一组解：显然这是线性规划的可行解，此时目标函数管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 ij 由于由于M可以是任意大的正数，可知此目标函数值可以是任意大的正数，可知此目标函数值无界无界。 上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：上述

45、的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果在某次迭代的单纯形表中，如果存在着一个大于零的检验数存在着一个大于零的检验数 ，并且该列，并且该列的系数向量的的系数向量的每个元素每个元素aij(i=1,2,m)都小于或等于零都小于或等于零，则此线性，则此线性规划问题是规划问题是无界无界的，一般地说此类问题的出现是由于建模的错误所引起的，一般地说此类问题的出现是由于建模的错误所引起的。的。管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 三、无穷多最优解三、无穷多最优解例例3、用单纯形法表求解下面的线性规划问题。、用单纯形法表求

46、解下面的线性规划问题。121212212max5050300,2400,250,0.zxxxxxxxx x目标函数约束条件管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 解：此题我们用图解法已求了解，现在用单纯形表来求解。解：此题我们用图解法已求了解，现在用单纯形表来求解。123121211222312123,max5050300,2400,250,0.ssszxxxxsxxsxsxxsss加入松弛变量，我们得到标准形：目标函数约束条件填入单纯形表计算得：填入单纯形表计算得：管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况迭迭代代次

47、次数数基变基变量量CBx1 x2 s1 s2 s3b比值比值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1zjcj-zj0 0 0 0 050 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 0 15015025050/1150/2zjcj-zj0 50 0 0 5050 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1zjcj-zj50 50 50 0 00 0

48、-50 0 015000管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 124, 这样我们求得了最优解为这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的此线性规划的最优值为最优值为15000。这个最优解是否是惟一的呢？由于在第。这个最优解是否是惟一的呢？由于在第2次迭代的检验数次迭代的检验数中除了基变量的检验数中除了基变量的检验数 等于零外，等于零外，非基变量非基变量s3的检验数也等的检验数也等于零于零，这样我们可以断定此线性规划问题有，这样我们可以断定此线性规划问题有无穷多最优解无穷多最优解。 不妨我们把检验数也为零

49、的非基变量选为入基变量进行第不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。次迭代。可求得另一个基本可行解，如下表所示：可求得另一个基本可行解，如下表所示：迭代迭代次数次数基基变变量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200zjcj-zj50 50 50 0 00 0 -50 0 015000管理运筹学管理运筹学 主讲：何宜军主讲：何宜军4 4 几种特殊情况几种特殊情况 从检验数可知此基本可行解从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s

50、3=50,也是最优解，也是最优解，从图解法可知连接这两点的从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解线段上的任一点都是此线性规划的最优解，不，不妨用向量妨用向量Z1，Z2表示上述两个最优解即表示上述两个最优解即Z1 =（50，250，0，50，0），）， Z2 =（100，200，0，0，50），则此线段上的任一点，即可表示为），则此线段上的任一点，即可表示为Z1+（1- ）Z2，其中，其中01。如图。如图5-1所示：所示：100100200200300300100100200200300300250250Z Z1Z Z2图图5-1管理运筹学管理运筹学 主讲：何宜军主讲：何宜