《数学实验 第4版》 7.第三章 实验3.1 文档：单纯形法求解线性规划.doc

PAGE6

MACROBUTTONMTEditEquationSection2SEQMTEqn\r\hSEQMTSec\r1\hSEQMTChap\r1\h单纯形法求解线性规划

在解决线性规划问题时，通常应用的方法有图像法和单纯形法等,而应用最多、最有效的方法为单纯形法.单纯形法是一种解决线性规划问题的有效方法，它的应用原理方法为：把线性规划问题的解的可实施部分看做一个维向量空间中的凸集，由此可得线性规划问题如果存在最优值,那么此最优值只能在凸集的顶点处.既然最优值在顶点处，我们就把所有顶点看做一个集合，先在这个集合里面挑选出一个顶点的值，对它进行判别，判别是否为最优值；如果判别结果不是最优值，那么就用一些方法把这个顶点的值转换为另外一个更可能为最优值的顶点值，依次进行判别，因为顶点有限，所以都可以转换出最终的结果，从而达到解决问题的要求，如果线性规划问题中没有最优解也可以利用单纯形法进行计算判别.

：

目标函数

约束条件

我们不难看出上式的三个特点：

（1）有决策变量：.

（2）有目标函数，：，一般多用.两者可以互换，即.

（3）有约束条件，通常为等式，对于“”或“”型的约束条件，可以添加变量转换成等式约束条件，添加的变量称为松弛变量，在目标函数中，松弛变量相对应的系数为0.

在利用单纯形法进行计算时，对于线性规划的解的相关概念也需要牢记，在接下来的单纯形法格式中，是以基本概念的求解为基础.线性规划解的概念对于不同元素的换入、换出等都有影响.

1、可行解:，称为线性规划问题的可行解.可行解的集合，称为可行域.

2、最优解:最符合题目要求的解，在可行域中，能够使目标函数取得最大值的可行解称为最优解.最优解一定是可行解.

3、基:设A阶系数矩阵（设），基为A的满秩子矩阵矩阵.

4、基可行解:，最优解一定是基可行解.

5、可行基:对应于基可行解的基称为可行基.

1.初始基可行解的确定

我们说单纯形法是一种迭代算法.所以我们在迭代时需要确定每一次迭代的对象，特别是在进行第一次迭代前，我们必须确定好对象才能使单纯形法的迭代顺利进行.第一次迭代的对象我们称为初始基可行解.为了确定初始基可行解，首先要找出初始可行基.找出初始可行基的方法为：

（1）有的线性规划问题中能直接观察得到一个初始可行基：

（2）如果所有约束条件是“”的不等式，在化为标准形式后，可以重新对变量和变量系数进行编号，得到一个的单位矩阵

此时单位矩阵可作为可行基.再将标准形式下的约束条件移项为在同一边的等式，再令，可得，这样就得到一个初始基可行解.

（3）如果所有约束条件是“”的不等式，及等式约束情况不存在单位矩阵时，就采用人工造基方法.即对不等式约束中减去一个非负的变量后，再加上一个非负的人工变量；对于等式约束一样加上一个非负的人工变量，就可以得到一个单位矩阵.

2.最优性检验与解的判定

线性规划问题解的结果有以下四种情况：唯一最优解、无穷多最优解、无界解和无可行解.在用单纯形对线性规划进行迭代的过程中，对于什么样的情况使得线性规划有解或无解、什么样的情况线性规划达到最优，这就需要进行最优性检验与解的判定.所以对于线性规划的解需要建立判定准则.

（1）最优解的判定

设为一个基可行解，并且对于一切都有检验数，则可以判定在该线性规划问题中为最优解.

（2）无穷多最优解的判定

设为一个基可行解，并且对于一切都有检验数，同时又存在某个非基变量的检验数，则可以判定该线性规划问题有无穷多最优解.

（3）无界解的判定

设为一个基可行解，有检验数，并且对于有则判定该线性规划问题有无界解也称之为无最优解.

3.单纯形法的计算

单纯形表是为了便于展现单纯形法中各种计算关系、使计算过程规范简单不杂乱所设计出的一种计算表格.它的功能、表达方式与增广矩阵类似，接下来，将为大家详细介绍单纯形法中的重要步骤单纯形表.

为了在下面的运算中便于观察进行迭代，我们可以先将上述的线性规划问题的形式改写成增广矩阵的形式

已知，所以它与的系数构成一个基，换将变换为零，即

基

此表为初始单纯形表，在基列填入基变量，例如；在列中填入基变量的价值系数，例如，它们与基变量相对应；列中填入约束方程组右端的常数；行中填入基变量的价值系数；最后一行为检验数行，对应各非基变量的检验数.每迭代一次可构成一个新的单纯形表.

计算步骤

（1）根据目标方程，约束条件建立初