单纯形法基本原理

《单纯形法基本原理》由会员分享，可在线阅读，更多相关《单纯形法基本原理（13页珍藏版）》请在装配图网上搜索。

1、工程优化设计中单纯形法的基本原理张云龙（大连海洋大学 土木工程学院 辽宁 大连 116023)摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。关键词：线性规划 图解法 单纯形法 大M法THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGNZHANG Yun-long (Dalian Ocean University, College of Civil Engineering, Liaoning, Dal

2、ian 16023)Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phas

3、e method.Key Words: Linear programming；Graphic method；Simplex Method; Big M Method1 引言在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的

4、讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等Error! Reference source not found.。因此，深刻理解线性规划问题及其标准解法单纯形法，显得尤为关键。2 线性规划问题2.1 数学模型线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。例如，美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的

5、利润最大？表1-1 工时及利润简表项目每天可用工时设备A (h)设备B (h)调试工序(h)06152115245利润（元）21解题过程：设公司制造、两种家电分别为件。 问题： 可使得利润Z 最大？设备A的工时限制： 设备B的工时限制： 调试工序的时间限制：利润： 即要求：目标函数即为：约束条件：s.t. 其中，约束条件可记 s. t. (subject to), 意思为“以为条件”、“假定”、“满足”之意。从数学的角度来看上述的例子每一个问题都有一组变量称为决策变量，一般记为对决策变量每一组值：代表了一种决策方案。通常要求决策变量取值非负，即每个问题中都有决策变量需满足的一组约束条件线性的等

6、式或不等式。都有一个关于决策变量的线性函数称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming)其数学模型为：上述模型的简写形式为：若令则线性规划问题的矩阵形式：2.2 线性规划问题的标准形式LP问题的数学模型的标准形式为： 若目标函数为 ，则可以引进新的目标函数则Z的最小值即为Z的最大值，即：。从而目标函数变换为： 当约束条件中含有不等式时，如：此时，对 ，引入变量 使得式变为：，同理对式引入变量使得式变为：于是原LP问题化为标准形式：引进变量x

7、3,x4称为松弛变量。 若约束条件中线性方程式的常数项为负数，则将该线性方程式两端乘以-1，使得常数项为正数。 若变量无约束，则引进两个非负变量将表示为： 所有的线性规划问题，总可以通过这四步将其化为标准形式，这样便于利用图解法或单纯形法进一步求解。3 线性规划的图解法线性规划的图解法是解决两个变量LP问题的一种简单实用的方法。图解法步骤： 根据约束条件画出可行域。 根据目标函数Z的表达式画出目标直线Z=0，并表明目标函数增加的方向，即目标函数原点处的梯度方向，可通过求偏导数得到。 在可行域中，找符合要求的距离目标直线Z=0的最远或最近点，并求出该点坐标。例如，解LP问题：解：在原点的梯度：所

8、以，。随着直线沿梯度方向去扫可行域，目标函数中的Z在增加。如：经过点时，由此可见，当目标函数沿梯度的方向去扫可行域时，在顶点处取得最大值。目标函数的最优值为：图1 线性规划图解法实际上，如果利用图解法解决很多的类似的题目后，我们可以得到以下事实：若线性规划问题的可行域存在，则可行域一定是凸集。若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个顶点。4 单纯形法4.1 单纯形法中的一些基本概念在一个非齐次线性方程组中，例如：非其次方程组，其增广矩阵为 称为基变量（括号中的数字所对应的变量）。基变量个数=。此方程组的解为。其中为任意实数。称它们为非基变

9、量，或自由变量。称非基变量为0的解 叫基解。如果一个解的每个分量都是非负数，就叫做可行解。如果基解是可行的，就叫基可行解，如即为基可行解。基可行解所对应的基称为可行基，如即为可行基。基可行解很重要，可以证明以下定理：定理1：若线性规划问题存在最优解，则问题的可行域是凸集。定理2：线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。定理3：若线性规划问题最优解存在，则最优解一定在可行域顶点处取得2。由此可看出，最优解要在基可行解（可行域顶点）中找。通过以上分析，我们也可以得到以下几个结论：（1）线性规划问题的可行域是一个凸集，可行域可能有界，也可能无界，但其顶点数是有限个。（2）线性规划

10、问题每个基本可行解对应于可行域的一个顶点。（3）若线性规划问题有最优解，则必可在其可行域的某个（或多个）顶点上达到最优值。4.2 单纯形法基本原理首先说明什么是基变换。例如，对于LP问题： 当前可行基所对应的基可行解。这个解显然不是最优。因为，当时是没有现实意义的。相应地，将代入目标函数得，若让非基变量取值从零增加，相应的目标函数值Z也将随之增加。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。再注意到目标函数中，前的系数2比前的系数1大，即每增加一个单位对Z的贡献比大。故应让从非基变量转为基变量，称为进基。这种判断进基变量的方法称为最大系数原则法。

11、又因为基变量只能有三个，因此必须从原有的基变量中选一个离开基转为非基变量，称为出基。谁出基呢？因为是仍留作非基变量的，故仍有。则必有，进而可以解出的一个取值范围，即且。让从零增加，其能取得的最大值为由可知，此时，已经从24降到了0，达到了非基的取值，变成非基变量。所以出基的变量是。从而得到新的可行基。这种判断出基变量的方法称为最小比值原则法。对于式子：，将可行基留在左边，非基变量移到右边，并用代入法消元，则上式变为：。由此得到一个新的基本可行解：。此时目标函数值从目标函数值明显看出，比明显地得到了改善。代入目标函数得：。这一过程可以用增广矩阵的行初等变换表示，并在增广矩阵末尾行增加一行，称为检

12、验行或者目标函数行，其系数即为对应未知数的系数，常数列对应的数值即为目标函数值。即为，其中这一行为检验行，是目标函数Z的系数，行末的0为Z的取值。这个矩阵也称为单纯形矩阵或单纯形数表。对单纯形矩阵进行行变换可以实现进基和出基两个过程，如上文所述，进基过程依据最大系数原则，出基过程依据最小比值原则。从开始至结束，每一步都需要运用这两个原则，并最终找到Z的最大值。结束的标志即为检验行全部系数没有正数3。对于，检验行最大系数为2（尖括号中数字），进基变量为。利用最小比值原则，确定主元行为第二行，主元素为6，对应出基变量为。中括号里面的数字即为主元素，其所在行为主元行，主元行系数为1的基变量即为出基变

13、量。具体过程如下：至此，检验行已没有正数，当前解即为最优解。令非基变量为0，得到最优解，最优值为。5 单纯形法的进一步讨论5.1 人工变量法（大M法）通常对一个线性规划问题进行标准化以后，约束矩阵会有单位化的可行基出现，可以作为单纯形法的初始可行基。但有些情况则没有现成的初始可行基。人工变量法就是针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。例如LP问题：首先将其化为标准形式，再强行加上人工变量，使其出现单位矩阵：但这样处理后产生两个问题：不易接受。因为是强行引进，称为人工变量。它们与不一样。称为松弛变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。人工变量的引入一般

14、来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，可以把目标函数作如下处理：其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有： 至此，检验行已没有正数，当前解即为最优解。去掉人工变量，即得原LP问题的最优解：。最优值为：5.2 两阶段法（两相法）用大M法处理人工变量时，若用计算机处理，必须对M给出一个较大的具体数据，并视具体情况对M值作适当的调整。为了克服这一麻烦，下面的两阶段法将问题拆成两个L

15、P问题分两个阶段来计算：阶段1： 用人工变量的和表示原目标函数，对新的目标函数求最小指，使其满足原问题的约束条件。若此问题有可行域，新目标函数的最小值实际上应该是零，转到第二阶段。否则，若最小值比零大，则不存在可行解。即：阶段：采用第1阶段的最优基本解作为原问题的初始解，在此情况下，原目标函数通过高斯消元法以非基本变量表示，然后用基本单纯形法求解即可。因此两阶段法的第1阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第2阶段的计算。例如用两阶段法解：阶段1的线性规划问题可写为：先对目标函数标准化：令，有。对单纯形矩阵作初等行变换，有 得到最小值

16、为零，转入第二阶段。阶段的目标函数写为：对单纯形矩阵进行初等行变换，有：至此，检验行已没有正数，当前解即为最优解。最优解为：，最优值为：由此可见，用人工变量法和两阶段法得到了同样的结果。6 结论线性规划是数学规划中理论成熟，实践广泛的一个分支。目前，解线性规划的方法很多，最常用最有效的还是单纯形法。此外还有初等矩阵法，迭代法等有关专著4中的方法。这些方法各有特点，例如，初等矩阵法用来求解大规模稀疏线性规划问题较为方便；迭代法可利用在计算机外存较大的机型上，可将迭代法用于高维线性规划问题的求解，但收敛很慢。单纯形法的实质是比较可行集的顶点，逐步调优。应用单纯形法时，必须把线性规划问题化为它的标准形式。通过人工变量技术，单纯形法可以处理任意约束（包括不等式约束，等式约束）问题。有些专家把结构优化问题看成是结构分析的有限元法加线性规划问题。足见线性规划及单纯形法在优化设计中的地位。参考文献1 钱令希.工程结构优化设计.北京:水利电力出版社,19832 陈耿东,工程结构优化设计基础.北京;水利电力出版社,1983.3 张炳华.土建结构优化设计.上海:同济大学出版社,19974 赵凤治.线性规划计算方法.科学出版社,1982. 13