教案四线性规划的单纯形法.doc

教案四 线性规划的单纯形法
教学内容 第三节 单纯形法
1．单纯形法
2．单纯形法的基本原理
3．单纯形解法
4．大法
教学学时 9学时
教学目标 1．理解单纯形法的解题思想
2．掌握单纯形法的基本原理
3．掌握单纯形解法和大法
重点难点 重点单纯形法的基本原理、单纯形解法和大法，难点单纯形法的基本原理
教学方法及手段 教师讲解 使用多媒体课件
教学过程
一、复习巩固
1．线性规划图解法的步骤（见课件）
2．线性规划数学模型解的几种情况（见课件）
二、讲授新课
1．单纯形法基本概念（见课件）
典型方程组
一般线性规划问题标准形式的约束条件如下式（2-1），是一个有n个未知数、m个方程的线性方程组．如果这m个方程是独立的（即其中任一方程均不能由其它方程代替），则通过初等变换，必能使式（2-1）化成式（2-2）形式的同解方程组：
（2-1）
+
+ （2-2）
…………………………………………………………
+
式中是重新排序后的变量．式（2-2）被称为典型方程组．即如果在一个线性方程组中的每一个方程中都有系数为1，并且不再出现在其它方程的一个未知量，则此方程组称为典型方程组．
基本变量
如果变量在某一方程中系数为1，而在其它一切方程中的系数为零，则称为该方程中的基本变量．否则为非基本变量．如式（2-2）中的为基本变量，为非基本变量．基本变量的个数为线性无关的方程的个数．事实上，个变量中任意个都可能作为基本变量，因此由排列组合知识可知，基本变量的组数为个，为未知变量的个数，为线性无关的方程的个数．
基本解
在典型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解．基本解的个数为个．
基本可行解
基本变量为非负的一组基本解称为基本可行解，基本可行解的个数最多不超过个．
例如，对方程组
①
②
施行初等变换[①×（－2）＋②],可以得到：

①
③
[③×(－1)] : ①
④
[④×（－1）＋①]: ⑤
④
式⑤和④为典型方程组，基本变量是和，非基本变量为和．设非基本变量和为零，则和分别等于-2和5，即对应于典型方程组⑤和④，基本解为：=．
因基本变量中为负值，所以此解不是基本可行解．根据方程组①和②有4个未知变量，因此通过初等变换可得到组（即6组）典型方程组和基本解．若令和为基本变量，通过初等变换，方程组①和②可变换为：
[①×（－1）＋②]: ①
③
[③×（－1/5）]: ①
④
[④×（－2）＋①] : ⑤
④
此时，典型方程组的基本变量为和，非基本变量为和．基本解为：，因为基本变量为非负值，所以此基本解也为基本可行解．
2．单纯形法的基本原理（见课件）
理论上已经证明，线性规划的基本可行解与可行域的顶点是一对一的．这就决定了线性规划可行域的顶点个数最多也不超过个．上面讨论线性规划问题解的特点时已指出，如果线性规划有最优解，一定可以在可行域的某个顶点处达到．因此，单纯形法的基本思路是：根据问题的标准形式，从可行域中的一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解．
在用单纯形法求解线性规划问题时，应考虑的问题：
建立初始基本可行解 在用单纯形法求解时，首先应将线性规划问题以标准形式表达、约束条件以右端常数非负的典型方程组表示，确定初始基本可行解．在前面的阐述中，已讨论了如何将一般线性规划问题转化为标准形式的线性规划问题，如何将约束条件通过初等变换以典型方程组形式表示，以及如何得出基本可行解（最初得到的基本可行解也称初始基本可行解），此处不再赘述．经过变换，典型方程组和初始基本可行解可用式（2-3）表示：
+
+ （2-3）
………………………………………………………
+
初始基本可行解：．
最优性检验 得到一个基本可行解后，我们要判断它是不是最优解．一般情况下，经过迭代后式（2-3）变为
（） （2-4）
将式（2-4）代入目标函数式，整理后得
（2-5）
令 , ,
于是 （2-6）

由于当时，，即（），所以式（2-6）也可写作

再令
为变量的检验数．则 （2-7）
（1）最优解判别 若＝为基本可行解，且对一切,有，则为最优解．
（2）无有限最优解判别 若＝为一基本可行解，有一个>0，且对一切有（为约束条件方程中的系数，），那么该线性规划问题无有限最优解（或称有无界解或无最优解）．
事实上，应用向量的乘法，可以将检验数的求法表示得简明一些．令表示目标函数中变量的系数，表示基本变量在目标函数中的系数行向量，表示变量在典型方程中的系数列向量，则
（2-8）
基本变量的检验数总等于0．目标函数值.
基本可行解的改进 若初始基本可行解不是最优解及不能判别无最优解时，需找一个新的基本可行解．具体方法是：首先确定进基变量，再确定出基变量．
进基变量的确定：由式（2-7）可知，检验数对线性规划问题的实际意义是：表示当变量增加1个单位时，目标函数的增加量；其经济意义表示相对利润．当时，说明非基本变量增加1个单位，目标函数可以增加，即现在的函数值不是最优，还能增加．这时要将某个非基本变量换到基本变量中去（称为进基变量）．为了使目标函数值增长最快，所以应选择值最大的一项所对应的非基本变量进基,. 则对应的为进基变量．进基变量所在的列（）称为枢列．
出基变量的确定：当进基变量确定后（假设是进基变量），出基变量的选定是应用“最小比值规则”．即用此时的各约束方程右端的常数项（非负数）与相应方程中的正系数相比，并选取最小商值的基本变量为出基变量（将由基本变量变为非基本变量）．

出基变量所在的行（）称为枢行．枢行与枢列交点处的元素（）称为枢元．然后通过初等变换，将约束条件转为关于新的基本变量的典型方程组，并求得新的基本可行解．对于新的基本可行解可再进行上述的最优性检验．
3． 单纯形解法（见课件）
上面介绍的单纯形法原理看似复杂，但如用表格形式计算，则比较容易操作．单纯形法的计算步骤：
第1步：找出初始基本可行解，建立初始单纯形表．
第2步：检验对应于非基本变量的检验数，若对所有的，则已得到最优解，计算最优值，即可结束．否则，转入下一步．
第3步：在所有中，若有一个对应的系数列向量，即对均有，则此问题无有限最优解（或称有无界解或无最优解），停止计算．否则转入下一步．
第4步：根据＝，确定为进基变量，再依据“最小比值规则”（）确定为出基变量．
第5步：实施以枢元素为中心的初等变换，使约束方程组变为关于新的基本变量的典型方程组，得到新的单纯形表，重复第二步…，一直到没有新的非基本变量可以改善目标函数为止．
若线性规划模型为：

上述计算步骤仍有效，只是其中的第二步改为：若对所有的（），则已得到最优解；第三步改为在所有中，若有一个对应的系数列向量，即对均有，则此问题无有限最优解（或称有无界解或无最优解）；第四步改为＝，确定为进基变量．
例2-8 现以例2-1来说明单纯形法的表上解法．

解 首先将线性规划问题标准化，引入松弛变量、、、，则：

此时约束方程组已为典型方程组，根据上述线性规划模型可以列出初始单纯形表（表2-4）：
表2-4 单纯形法求解例2-1（1）

200
300
0
0
0
0

0

2
2
1
0
0
0
12
6
0

1
2
0
1
0
0
8
4
0

4
0
0
0
1
0
16

0

0
[4]
0
0
0
1
12
3

200
300
0
0
0
0
=0
表2-4中：　　 为典型方程组中变量的系数，为规划中出现的变量，为变量在目标函数中的系数，为基本变量，为基本变量在目标函数中的系数，为典型方程组右端常数项（非负值），为确定出基变量的商值， （），为变量的检验数，， 为此时目标函数值，．
根据初始单纯形表可以看出：
初始基本可行解是，，，，，
此时目标函数值＝0
检验数＝200－＝200
　＝300－＝300
==＝＝0（基本变量的检验数总等于零）
由于，，所以初始基本可行解非最优解．又由于，所以确定为进基变量．
进一步求最小值：

即从第4个方程中算出的商值最小，而第4个方程中的基本变量是，于是为出基变量．表中给第4个约束方程中的系数4加上方括号以突出其为枢元．
接下去是将取代，表2-4中的约束方程化为以、、和为基本变量，和为非基本变量的典型方程．从表2-4中可以看到，只需对方程组实行初等变换，使枢元位置变成1，而枢列中的其它元素变为零就可以了．
此处可先将第4个方程除以4，使枢元位置变成1；然后用新得到的第4个方程乘以（-2）后分别加到第1个和第2个方程上，使枢列中的第1个和第二个方程所在位变为零．这样我们可以得到新的单纯形表（表2-5）．
表2-5给出的新的基本可行解是＝0，＝3，＝6，＝2，＝16，＝0
此时目标函数值＝900
检验数＝200-＝200
＝0-＝
＝==＝0（基本变量的检验数总等于零）
表2-5 单纯形法求解例2-1（2）

200
300
0
0
0
0

0

2
0
1
0
0

6
3
0

[1]
0
0
1
0

2
2
0

4
0
0
0
1
0
16
4
300

0
1
0
0
0

3

200
0
0
0
0
-75
=900
由于，所以此时基本可行解非最优解，确定为进基变量．
进一步计算最小值：

即从第2个方程中算出的商值最小，而第2个方程中的基本变量是，于是为出基变量．
接着进行第二次迭代，将取代，表2-5中的约束方程化为以、、和为基本变量，和为非基本变量的典型方程，以便求出新的单纯形表．重复单纯形法计算第2 步～第5步，一直到没有新的非基本变量可以改善目标函数为止（见表2-6和表2-7）．
表2-6 单纯形法求解例2-1（3）

200
300
0
0
0
0

0

0
0
1
-2
0

2
4
200

1
0
0
1
0

2

0

0
0
0
-4
1
[2]
8
4
300

0
1
0
0
0

3
12

0
0
0
-200
0
25
=1300

表2-7 单纯形法求解例2-1（4）

200
300
0
0
0
0

0

0
0
1
-1

0
0

200

1
0
0
0

0
4

0

0
0
0
-2

1
4

300

0
1
0

0
2

0
0
0
-150

0
=1400
表2-7中：目标函数值=1400
检验数=0-=-150
=0-=
====0（基本变量的检验数总等于零）
由于，，所以此基本可行解，，，，，，即为最优解，最优值为Z*＝1400．与前面图解法求解结果一致．为了加深对单纯形法基本思想的理解，不妨将表2-4、表2-5、表2-6、表2-7和图2-1进行对照，可以发现表2-4给出的基本可行解对应于图中可行域顶点0，表2-5给出的基本可行解对应于顶点，表2-6给出的基本可行解对应于顶点，表2-7给出的最优解对应于顶点．线性规划问题有无穷多个可行解，应用单纯形法可以高效率地求解此类问题．
例2-9 用单纯形法求解下列规划问题

（解略，见课件）
4． 大法
（1）人工变量 （见课件）
单纯形法求解的一个重要前提是：线性规划问题必须是标准形式，并且约束条件必须化为典型方程组．这样才能得到初始基本可行解，并制作出初始的单纯形表．但许多线性规划问题不是以标准形式出现，约束条件也未以典型方程组形式表示，因此我们往往先要把线性规划问题化为标准形式，然后再使约束方程变为典型方程组．
如果给定的线性规划问题中，约束条件都是“”型的，那么将每一个约束条件的左边添加一个松弛变量后，不仅约束条件化为了标准形式，而且也得到了典型方程组，如下列所示．

但是，大多数的线性规划中的约束条件为（或＝）的形式，化为典型方程组就不那么容易．在这种情况下，比较简单的方法是先将约束不等式化为等式，然后对每一个约束方程再添加一个非负变量（如果约束方程没有明显的基本变量），使方程组成为典型方程组形式．这种外加的变量不同于松弛变量（或剩余变量），没有实际意义，只是一种形式的存在，本质上应当等于零，所以被称为人工变量．
（2）大法求解（见课件）
在一个线性规划问题的约束条件中加入人工变量，成为典型方程组后，即可用单纯形表求解．由于一开始人工变量是作为基本变量的，而它们本质上应当为零，所以必须设法尽快将它们从基本变量中剔除，成为非基本变量（基本可行解中，非基本变量的值为零）．为此，将人工变量记入目标函数中，并赋予一个极大的负系数．习惯上，这种系数记作，其中是极大的正数．由于标准形式的线性规划是极大化问题，目标函数中添加1个或1个以上以为系数的人工变量后，人工变量取任何非负值均不可能为最优解．从而，在应用单纯形法过程中，人工变量一定会尽快地变成非基本变量，而对原问题的最优解不产生丝毫影响．对于目标函数为极小化时，规定人工变量在目标函数中的系数为极大的正系数（）．这种方法称为大法．
例2-10 用大法求解下列问题．

解 先通过加入松弛变量和使此线性规划问题化为标准形式

然后通过加入人工变量使约束方程组变为典型方程组
-

用单纯形法解之，结果如下表2-11：
表2-11 大法求解例2-10

3
5
0
0
-

0

[1]
0
1
0
0
4
4
0

0
2
0
1
0
12

-

3
2
0
0
1
18
6

3+3
5+2
0
0
0
=-18
3

1
0
1
0
0
4

0

0
2
0
1
0
12
6
-

0
[2]
-3
0
1
6
3

0
5+2
-3-3
0
0
=12-6
3

1
0
1
0
0
4
4
0

0
0
[3]
1
-1
6
2
5

0
1

0

3

0
0

0

=27
3

1
0
0

2

0

0
0
1

2

5

0
1
0

0
6

0
0
0

-1-
*=36
最后计算得出最优解，，，，，最优值*=36．
例2-11 有一线性规划问题

试用大法求解．
解 在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到

这里是一个很大的正数．
大法计算见表2-12．
最优解：＝4，＝1，＝9，＝＝＝＝0；最优值：＝-2．
在用大法求解时，如果得到人工变量不为零的最优解，则说明原问题不可行，即原问题无解．另外，若极小比值相等，则人工变量先出基．
在线性规划问题中，如果线性规划已化为标准形式而约束方程仍没有明显的基本变量，则除可用大法求解外，还可用二阶段法求解（可参阅其他运筹学书籍）．
单纯形法是线性规划问题的通用解法．尽管求解效率较高，但由于在许多实际问题的应用过程中，往往有很多的决策变量和约束条件，人工计算费时且易出现计算错误．计算机技术的发展，使线性规划问题的求解可以通过有关计算机程序完成，极大地增强了线性规划方法解决实际问题的能力．本书第十三章就介绍了用Excel以电子表格的形式建立与求解线性规划模型的方法．
表2-12 大法计算例2-11

-3
1
1
0
0

0

1
-2
1
1
0
0
0
11
11

-4
1
2
0
-1
1
0
3

-2
0
[1]
0
0
0
1
1
1

-3+6
1-
1-3
0

0
0
=4
0

3
-2
0
1
0
0

10

0
[1]
0
0
-1
1

1
1
1

-2
0
1
0
0
0

1

-1
1-
0
0

0

=1+
0

[3]
0
0
1
-2

12
4
1

0
1
0
0
-1

1

1

-2
0
1
0
0

1

-1
0
0
0
1

=2
-3

1
0
0

4

1

0
1
0
0
-1

1

1

0
0
1

9

0
0
0

=-2

三、课堂练习（见课件）
四、本次课小结 （见课件）
五、作 业 （见课件）