单纯形法

目录

第一章 单纯形法的提出??????????????????????? 1.1 单纯形法提出背景??????????????????????? 第二章 单纯形法的一般原理????????????????????? 2.1 单纯形法的基本思路?????????????????????? 2.2 确定初始基本可行解?????????????????????? 2.3 最优性检验?????????????????????????? 2.4 基变换???????????????????????????? 2.5 解的判别定理????????????????????????? 2.6 单纯形法求解线性规划问题的程序框图?????????????? 第三章 表格单纯形法????????????????????????

3.1单纯型表求解????????????????????????? 3.2 用单纯形法求解线性规划问题的举例??????????????? 第四章 人工变量及其处理方法????????????????????

4.1大M法 ???????????????????????????? 4.2两阶段法 ??????????????????????????? 4.3无最优解和无穷多最优解 ???????????????????? 4.4退化与循环 ?????????????????????????? 第五章 单纯形法的矩阵表示????????????????????? 总结 ???????????????????????????????? 参考文献 ??????????????????????????????

1

第一章 单纯形法的提出

1.1 单纯形法的提出背景

单纯形法是1947年由George Bernard Dantzing(1914-2005)创建的，单纯形

法的创建标志着线性规划问题的诞生。线性规划问题是研究在线性约束条件下，求线性函数的极值问题。然而，对这类极值问题，经典的极值理论是无能为力的，只有单纯形法才能有效解决这类极值问题的求解。

线性规划是数学规划的一个重要分支，也是最早形成的一个分支，线性规划的理论与算法均非常成熟，在实际问题和生产生活中的应用非常广泛；线性规划问题的诞生标志着一个新的应用数学分支——数学规划时代的到来。过去的60年中，数学规划已经成为一门成熟的学科。其理论与方法被应用到经济、金融、军事等各个领域。数学规划领域内，其他重要分支的很多问题是在线性规划理论与算法的基础上建立起来的，同时也是利用线性规划的理论来解决和处理的。由此可见，线性规划问题在整个数学规划和应用数学领域中占有重要地位。因此，研究单纯形法的产生与发展对于认识整个数学规划的发展有重大意义。

线性规划问题是在一定约束条件下求目标函数的最优(最大或最小)值。求解线性规划问题有图解法，单纯形法，椭球法及投影尺度法。其中以单纯性法最常用，应用范围也更广泛。

通过对线性规划问题的基本学习，我们已经知道，若LP问题有最优解，必可

在某个极点上达到，即某个基本可行解上取得最优解。因此很容易想到枚举法，即把LP问题所有的最优解都找出来，然后逐个进行比较，找出最优解。这种方法看

mm似可行，但事实上往往行不通，因为可行解的个数≤Cn个，而Cn随着ｍ，ｎ的增

大迅速增大，使枚举法变得不可行。 换一种思路：

先设法找到一个初始基可行解，判断它是否是最优解，如果是则停止计算；否则，则找一个比上一个“更好”的基可行解，而不比上一个“更好”的基可行解不去计算。这种逐步改善的求解方法需要解决以下三个问题： （1）：如何判别当前的基可行解是否达到最优；

（2）：若当前基可行解不是最优解，如何去寻找下一个改进的基可行解； （3）：如何得到一个初始的基可行解。

单纯形法（Simplex Method）解决了上述的三个问题。单纯形法是1947年由 G.B.Dantzig提出，是解 LP 问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。

单纯形法是求解优化设计线性规划问题行之有效的方法，在线性规划问题的求解上得到了广泛的应用。单纯形法是利用单纯形表通过转轴运算最终获得最优解和目标函数的极值，但一般要列数个单纯形表和进行数次转轴运算，且要计算单纯形表中的所有元素，其计算量较大和较繁琐。因此，人们在对单纯形法进行了较深入的研究基础上，推出了修正单纯形法或称改进单纯形法。

2

第二章 单纯形法的一般原理

2.1 单纯形法的基本思路

第一步：构造一个初始基本可行解；

对已经标准化的线性规划模型，设法在约束矩阵Am?n中构造出一个m阶单位阵初始可行基，相应的就有一个初始可行解。 以一个例子来说明单纯形法的基本思路， 例 数学模型为：

maxz?5x1?2x2

?30x1?20x2?160,?5x?x?15,?12? x?4, 1???x1,x2?0.化为标准形式：

maxz?5x1?2x2?0x3?0x4?0x5 (1-1)

?30x1?20x2?x3?160,?5x?x?x?15,?124? x1?x5?4, （1-2）

???x1,x2,x3,x4,x5?0.约束条件(1-2)式的系数矩阵为：

?30 A?(p,p,p,p,p)?512345???1从(1-2)式可看到x3,x4,x5的系数构成的列向量

20100?1010?

?0001??p3?(1,0,0)T,p4?(0,1,0)T,p5?(0,0,1)T

p3,p4,p5是线性无关的，这些向量构成一个基B,对应于B的变量x3,x4,x5为基变量，x1,x2为非基变量。将基变量用非基变量表示，则（1-2）可表示为：

3

?x3?160?30x1?20x2? ? x4?15?5x1?x2 (1-3)

? x?4?x ?5将（1-3）式带入目标函数式（1-1），得到目标函数的非基变量表示式：

若令非基变量x1z?0?5x1?2x2 (1-4)

?x2?0，代入（1-3）式中，即可得到一个基本可行解x(0) ：

(0) x?(0,0,160,15,4)

第二步：判断当前基本可行解是不是最优解；

在目标函数的规范式中，若至少有一个非基变量前的系数为正数，则当前解就

不是最优解；若所有的非基变量前的系数均为非负数，则当前解就是最优解（特指最大化问题）。将目标函数的规范式中非基变量前的系数称为检验数，故对最大化问题，当所有的检验数≤0时，当前解即为最优解。 在例题中得到一个基本可行解x x(0)(0):

?(0,0,160,15,4)

这个基本可行解显然不是最优解，故进行第三步。

第三步：若当前解不是最优解，则要进行行基变换迭代到下一个基本可行解。 首先从当前解的基变量中选一个作为进基变量。选择的原则一般是：目标函数的规范式中，最大检验数所属的非基变量作为进基变量。

再从当前解的基变量中选择一个作为出基变量。选择的方法是：在用非基变量表示的规范式中，处理进基变量外，让其余变量取值为0，在按最小比值准则确定出基变量。这样就得到一组新的基变量与非基变量，即已从上一个基本可行解迭代到下一个基本可行解。然后求出关于新基矩阵的线性规划问题的规范式，在新的规范式中可求出新基本可行解的取值及目标函数的取值。

再回到第二步判断当前新基本可行解是否达到最优。若已到达最优，停止迭代，当前基本可行解即为最优解；若没有达到最优，在进行第三步做新的基变换，再次迭代，如此往复，直到求出最优解或者判断无（有界）最优解停止。

在本例中，第一次迭代，x1作为进基变量，x4为出基变量，得到新的基本可行解为x(1)?(3,0,70,0,1)，其对应的规范式：

?x3?70?14x2?6x4 ?x?3?1/5x?1/5x (1-5)

?124?x?1?1/5x? 1/5x4 ?52 4

z?15?x2?x4 (1-6)

(1)由（1-6）可知，基本可行解x对应的目标函数值为z?15；

而目标函数的非基变量前的系数仍有正的，故此可行解不是最优的，在进行下一次迭代，x2为进基变量，x3为出基变量，得到新的基金本可行解：

x其对应的规范式：

(2)?(2,5,0,0,2)

?x2?5?1/14x3?3/7x4 ??x1?2?1/70x3?2/7x4 (1-7) ?x?2?1/70x? 1/5x4 ?53 z?20?1/14x3?4/7x4 (1-8)

(2)由（1-8）可知，基本可行解x 即得本题最优解为x(2)对应的目标函数值为20;并且目标函数中非基变

量前的系数（检验数）均为负数，故此可行解为最优解。

?(2,5,0,0,2)， 最大值z?20,

2.2 确定初始基本可行解

为了确定初始基可行解，要首先找出初始可行基，其方法如下： (1)直接观察 (2)加松弛变量 (3)加非负的人工变量 一、直接观察 从线性规划问题

nmax z??cixi (1-9) i?1?Px i?1ii的系数构成的列向量

n?b (1-10)

xi?0 i?1,2,3,?,npi(i?1,2,...,n)中，通过观察，可找出一个初始可行基

?1??0B?(P1,P2,?,Pn)?????0? 5

0?0??1?0??????0?1??

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库单纯形法在线全文阅读。