工程优化设计中单纯形法的基本原理张云龙（大连海洋大学土木工程学院辽宁大连116023)摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。

在此基础上进一步讨论单纯形法的推广，即大M法和两相法。

关键词：线性规划图解法单纯形法大M法THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGNZHANG Yun-long(Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 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-phase method.Key Words: Linear programming；Graphic method；Simplex Method; Big M Method1引言在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。

如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。

线性规划在工程实例中的应用已相当广泛。

虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。

其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。

尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等错误!未找到引用源。

因此，深刻理解线性规划问题及其标准解法——单纯形法，显得尤为关键。

2线性规划问题2.1数学模型线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。

例如，美佳公司计划制造Ⅰ、Ⅱ两种家电产品。

已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。

问该公司应制造两种家电各多少件，使获取的利润最大？表1-1 工时及利润简表解题过程：设公司制造Ⅰ、Ⅱ两种家电分别为1,x 2x 件。

问题：1?x = 2?x =可使得利润Z 最大？ 设备A 的工时限制： 2515x ≤ 设备B 的工时限制： 126224x x +≤ 调试工序的时间限制：125x x +≤ 利润： 122Z x x =+ 即要求：12max 2Z x x =+ 目标函数即为：12max 2Z x x =+约束条件：s.t. 212121251562245,x x x x x x x ≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩其中，约束条件可记 s. t. (subject to), 意思为“以…为条件”、“假定”、“满足”之意。

从数学的角度来看上述的例子①每一个问题都有一组变量—称为决策变量，一般记为12,,,.n x x x 对决策变量每一组值：(0)(0)(0)12(,,)T n x x x 代表了一种决策方案。

通常要求决策变量取值非负，即0,(1,2,).i x i n ≥=②每个问题中都有决策变量需满足的一组约束条件—线性的等式或不等式。

③都有一个关于决策变量的线性函数—称为目标函数。

要求这个目标函数在满足约束条件下实现最大化或最小化。

将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。

有时也将线性规划问题简记为LP （linear programming)其数学模型为：1122max(min)n n Z c x c x c x =+++11112211211222221122(,)(,)..(,)0,(1,2,,)n n n n m m mn n mj a x a x a x b a x a x a x b s t a x a x a x bx j n +++≤=≥⎧⎪+++≤=≥⎪⎪⎨⎪+++≤=≥⎪≥=⎪⎩上述模型的简写形式为：1max(min)nj jj Z c x==∑1(,)(1,2,,).0(1,2,,)nij j i j j a x b i m s t x j n =⎧≤=≥=⎪⎨⎪≥=⎩∑若令12(,,,);n C c c c =12;n x x X x ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭12;m b b b b ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭11121212221212(,,,)n n n m m mn a a a a a a A P P P a a a ⎛⎫ ⎪ ⎪== ⎪ ⎪⎝⎭则线性规划问题的矩阵形式：max(min)Z CX =(,).0AX bs t X ≤=≥⎧⎨≥⎩2.2 线性规划问题的标准形式LP 问题的数学模型的标准形式为：1122max n n Z c x c x c x =+++1(1,2,,,0).0(1,2,,)nij j i i j j a x b i m b s t x j n =⎧==≥⎪⎨⎪≥=⎩∑且⑴ 若目标函数为 1122min n n Z c x c x c x =+++，则可以引进新的目标函数,Z Z '=-则Z 的最小值即为Z ’的最大值，即：min max Z Z '=。

从而目标函数变换为：1122max n n Z c x c x c x '=----⑵ 当约束条件中含有不等式时， 如：12max 33Z x x =+()()12122101.21420(1,2)ix x s t x x x i +≤→⎧⎪+≤→⎨⎪≥=⎩此时，对⑴ 12210x x +≤，引入变量30,x ≥ 使得⑴式变为：123210x x x ++=，同理对⑵式12214x x +≤引入变量40,x ≥使得⑵式变为：124214x x x ++= 于是原LP 问题化为标准形式：12max 33Z x x =+123124210.2140(1,2,3,4)i x x x s t x x x x i ++=⎧⎪++=⎨⎪≥=⎩引进变量x 3,x 4称为松弛变量。

⑶ 若约束条件中线性方程式的常数项为负数，则将该线性方程式两端乘以-1，使得常数项为正数。

⑷ 若变量l x 无约束，则引进两个非负变量0,l x '≥0l x ''≥将l x 表示为：l l l x x x '''=- 所有的线性规划问题，总可以通过这四步将其化为标准形式，这样便于利用图解法或单纯形法进一步求解。

3 线性规划的图解法线性规划的图解法是解决两个变量LP 问题的一种简单实用的方法。

图解法步骤：⑴ 根据约束条件画出可行域。

⑵ 根据目标函数Z 的表达式画出目标直线Z=0，并表明目标函数增加的方向，即目标函数原点处的梯度方向，可通过求偏导数得到。

⑶ 在可行域中，找符合要求的距离目标直线Z=0的最远或最近点，并求出该点坐标。

例如，解LP 问题：12max 3Z x x =+12128.601,2i x x s t x x i +≤⎧⎪≤⎨⎪≥=⎩解：123Z x x =+在原点的梯度：13,xZ '=21x Z '= 所以，(3,1)Z ∇=。

随着直线213x x =-沿梯度方向去扫可行域，目标函数123Z x x =+中的Z 在增加。

如：经过点(1,1)时， 4.Z =由此可见，当目标函数沿梯度的方向去扫可行域时，在顶点(6,1)处取得最大值。

目标函数的最优值为：max 36119.Z =⨯+=图1 线性规划图解法实际上，如果利用图解法解决很多的类似的题目后，我们可以得到以下事实： ①若线性规划问题的可行域存在，则可行域一定是凸集。

②若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个顶点。

4 单纯形法4.1 单纯形法中的一些基本概念在一个非齐次线性方程组中，例如：非其次方程组2312412551562245x x x x x x x x +=⎧⎪++=⎨⎪++=⎩，其增广矩阵为 称3,x 4,x 5x 为基变量（括号中的数字所对应的变量）。

基变量个数=()()3r A r A ==。

此方程组的解为3241251215524625x x x x x x xx =-⎧⎪=--⎨⎪=--⎩。

其中1,x 2x 为任意实数。

称它们为非基变量，或自由变量。

称非基变量1,x 2x 为0的解(0,0,15,24,5) 叫基解。

如果一个解的每个分量都是非负数，就叫做可行解。

如果基解是可行的，就叫基可行解，如0(0,0,15,24,5)TX =即为基可行解。

基可行解所对应的基称为2x ()()()0510********2411015A ⎛⎫ ⎪= ⎪ ⎪⎝⎭1x 2x 3x 4x 5x b可行基，如345{,,}x x x 即为可行基。

基可行解很重要，可以证明以下定理：定理1：若线性规划问题存在最优解，则问题的可行域是凸集。

定理2：线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。

定理3：若线性规划问题最优解存在，则最优解一定在可行域顶点处取得[2]。

由此可看出，最优解要在基可行解（可行域顶点）中找。

通过以上分析，我们也可以得到以下几个结论：（1）线性规划问题的可行域是一个凸集，可行域可能有界，也可能无界，但其顶点数是有限个。

（2）线性规划问题每个基本可行解对应于可行域的一个顶点。

（3）若线性规划问题有最优解，则必可在其可行域的某个（或多个）顶点上达到最优值。

4.2 单纯形法基本原理首先说明什么是基变换。

例如，对于LP 问题：12345max 2000Z x x x x x =++++23124125515622451,,5i x x xx x x x x x i +=⎧⎪++=⎪⎨++=⎪⎪≥=⎩当前可行基345{,,}x x x 所对应的基可行解0(0,0,15,24,5)TX =。

这个解显然不是最优。

因为，当10,x =20x =时是没有现实意义的。