单纯形法基本原理

工程优化设计中单纯形法的基本原理

张云龙

（大连海洋大学 土木工程学院 辽宁 大连 116023)

摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。 关键词：线性规划 图解法 单纯形法 大M法

THE BASIC PRINCIPLES OF SIMPLEX METHOD TO

THE ENGINEERING OPTIMIZE DESIGN

ZHANG 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 Method

1 引言

在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。

虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等。

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

错误！未找到引用源。

2 线性规划问题

2.1 数学模型

线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。例如，美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？

表1-1 工时及利润简表

解题过程：设公司制造Ⅰ、Ⅱ两种家电分别为x1,x2件。 问题：x1 ? x2 ?可使得利润Z 最大？ 设备A的工时限制： 5x2 15 设备B的工时限制： 6x1 2x2 24 调试工序的时间限制：x1 x2 5 利润： Z 2x1 x2 即要求：maxZ 2x1 x2 目标函数即为：maxZ 2x1 x2 6x1

约束条件：s.t.

x1 x, 1

5x2 2x2 x2x2 0

15 24 5

其中，约束条件可记 s. t. (subject to), 意思为“以 为条件”、“假定”、“满足”之意。 从数学的角度来看上述的例子

①每一个问题都有一组变量—称为决策变量，一般记为x1,x2, ,xn.对决策变量每一组

(0)(0)(T0)

值：(x1,x2, xn)代表了一种决策方案。通常要求决策变量取值非负，即

xi 0,(i 1,2, n).

②每个问题中都有决策变量需满足的一组约束条件—线性的等式或不等式。

③都有一个关于决策变量的线性函数—称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming)其数学模型为：

max(min)Z c1x1 c2x2 cnxn

s.t.

a11x1 a12x2 a1nxn ( , )b1

ax a22x2 a2nxn ( , )b2 211

ax ax ax ( , )b

m22mnnm

m11

xj 0,(j 1,2, ,n)

n

上述模型的简写形式为：max(min)Z

c

j 1

j

xj

n

aijxj ( , )bis.t j 1

xj 0

(i 1,2, ,m)(j 1,2, ,n)

若

C (c1,c2, ,cn);X

x1 b1 a1

x2b2a ;b ;A 2

xn b m am1

aa am2

an

(P,P, ,P)

12n

amn

n

令

a

则线性规划问题的矩阵形式：max(min)Z CX

AX ( , )bs.t

X 0

2.2 线性规划问题的标准形式

LP问题的数学模型的标准形式为：maxZ c1x1 c2x2 cnxn

n

aijxj bis.t j 1

xj 0

(i 1,2, ,m,且bi 0)

(j 1,2, ,n)

⑴ 若目标函数为 minZ c1x1 c2x2 cnxn，则可以引进新的目标函数Z Z,

Z 。从而目标函数变换为：则Z的最小值即为Z’的最大值，即：minZ max

maxZ c1x1 c2x2 cnxn

⑵ 当约束条件中含有不等式时， 如：maxZ 3x1 3x2

x1 2x2

s.t 2x1 x2

x 0 i

10 1 14 2 (i 1,2)

此时，对⑴ x1 2x2 10，引入变量x3 0, 使得⑴式变为：x1 2x2 x3 10，同理对⑵式2x1 x2 14引入变量x4 0,使得⑵式变为：2x1 x2 x4 14 于是原LP问题化为标准形式：maxZ 3x1 3x2

x1 2x2 x3

s.t 2x1 x2

xi 0

10 x4 14(i 1,2,3,4)

引进变量x3,x4称为松弛变量。

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

数项为正数。

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

3 线性规划的图解法

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

⑴ 根据约束条件画出可行域。

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

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

例如，解LP问题：maxZ 3x1 x2

x1 2x2 8

s.t x1 6 xi 0

1

i 1,2

3,Zx 1 解：Z 3x1 x2在原点的梯度：Zx

2

所以， Z (3,1)。随着直线x2 3x1沿梯度方向去扫可行域，目标函数Z 3x1 x2中的Z在增加。如：经过点(1,1)时，Z 4.

由此可见，当目标函数沿梯度的方向去扫可行域时，在顶点(6,1)处取得最大值。目标函数的最优值为：maxZ 3 6 1 19.

x2图1 线性规划图解法

实际上，如果利用图解法解决很多的类似的题目后，我们可以得到以下事实： ①若线性规划问题的可行域存在，则可行域一定是凸集。

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

4 单纯形法

4.1 单纯形法中的一些基本概念

在一个非齐次线性方程组中，例如：

非其次方程组 6x1

x 1

x1

x2

x3

5x2 2x2 x2

x3

x4

x5

15

24，其增广矩阵为 5

x4x5b

0 A 6

1

521

1

00

000

1

1

15 24 5

称x3,x4,x5为基变量（括号中的数字所对应的变量）。基

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

x3

此方程组的解为 x4

x 5

15245

6x1 x1

5x2 2x2。 x2

其中x1,x2为任意实数。称它们为非基变量，或自由变量。称非基变量x1,x2为0的解

(0,0,15,24,5) 叫基解。如果一个解的每个分量都是非负数，就叫做可行解。如果基解是

T

可行的，就叫基可行解，如X0 (0,0,15,24,5)即为基可行解。基可行解所对应的基称为

可行基，如{x3,x4,x5}即为可行基。

基可行解很重要，可以证明以下定理：

定理1：若线性规划问题存在最优解，则问题的可行域是凸集。

定理2：线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。 定理3：若线性规划问题最优解存在，则最优解一定在可行域顶点处取得。 由此可看出，最优解要在基可行解（可行域顶点）中找。

通过以上分析，我们也可以得到以下几个结论：

（1）线性规划问题的可行域是一个凸集，可行域可能有界，也可能无界，但其顶点数是有限个。

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

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

[2]

4.2 单纯形法基本原理

首先说明什么是基变换。

例如，对于LP问题：maxZ 2x1 x2 0x3 0x4 0x5

6x1

x1 x 0 i

5x2 2x2 x2

x3

x4

x5

i 1, ,5

15 24 5

T

当前可行基{x3,x4,x5}所对应的基可行解X0 (0,0,15,24,5)。

这个解显然不是最优。因为，当x1 0,x2 0时是没有现实意义的。相应地，将X0代入目标函数得Z(X0) 0，若让非基变量x1,x2取值从零增加，相应的目标函数值Z也将随之增加。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。

x1前的系数2比x2前的系数1大，再注意到目标函数Z 2x1 x2 0x3 0x4 0x5中，

即x1每增加一个单位对Z的贡献比x2大。故应让x1从非基变量转为基变量，称为进基。这种判断进基变量的方法称为最大系数原则法。

又因为基变量只能有三个，因此必须从原有的基变量x3,x4,x5中选一个离开基转为非基变量，称为出基。谁出基呢？

因为x2是仍留作非基变量的，故仍有x2 0。

x3

则必有 x4

x 5

15245

0

进而可以解出x1的一个取值范围，即x1 6x1 0， x1 0

246

,5} 4.

246

且x1 5。

让x1从零增加，其能取得的最大值为x1 min{

由x4 24 6x1 0可知，此时，x4已经从24降到了0，达到了非基的取值，变成非基变量。所以出基的变量是x4。从而得到新的可行基{x1,x3,x5}。这种判断出基变量的方法称为最小比值原则法。

x3

x4

对于式子：

x5 x 0 i

15245

6x1 x1i 1, ,5

1541

5x2 1323x2x2

1616x4x4

5x2 2x2 x2

，将可行基{x1,x3,x5}留在左边，非基变

x3

x1

量x2,x4移到右边，并用代入法消元，则上式变为：

x

5

x 0 i

。由此

i 1, ,5

T

得到一个新的基本可行解：X1 (4,0,15,0,1)。此时目标函数值

Z(X1) 2 4 8 Z(X0) 0.从目标函数值明显看出，X1比X0明显地得到了改善。代

入目标函数得：Z 8

13

x2

13

x4。

这一过程可以用增广矩阵的行初等变换表示，并在增广矩阵末尾行增加一行，称为检验行或者目标函数行，其系数即为对应未知数的系数，常数列对应的数值即为目标函数值。即 0 6

为A

1 2

5211

1000

0100

0010

15 24

，其中(2,1,0,0,0,0)这一行为检验行，是目标函数Z的系5 0

数，行末的0为Z的取值。这个矩阵也称为单纯形矩阵或单纯形数表。

对单纯形矩阵进行行变换可以实现进基和出基两个过程，如上文所述，进基过程依据最大系数原则，出基过程依据最小比值原则。从开始至结束，每一步都需要运用这两个原则，并最终找到Z的最大值。结束的标志即为检验行全部系数没有正数。

[3]

0 6

对于A

1 2

5211

1

000

000

1

00

1

15 24

，检验行最大系数为2（尖括号中数字），进基 5 0

变量为x1。利用最小比值原则 min

15245 ,, 4，确定主元行为第二行，主元素为061

6，对应出基变量为x4。中括号里面的数字即为主元素，其所在行为主元行，主元行系数为1的基变量即为出基变量。

具体过程如下：

0

6 A

1 2

5211

1

000

000

1

00

1

051/3

15 0 24 1 1

k2

15 6

0 2

51/31115

4 1 8

1

000

01/600

00

1

15

4 5 0

0 1 k3 k2,k4 2k2 0 0

1

000

01/6 1/6 1/3

00

2/3

/3

1

0

3 1 k3

02

0

51/3

1

000

01/6 1/4 1/3

0032000

1

1/3

15

4 32

8

0

11 1

k1 5k3,k2 k3,k4 k3

033

0

1

000

541/4 1/4 1/4

152 1232 2

1

152

72

32

172

至此，检验行已没有正数，当前解即为最优解。令非基变量x4,x5为0，得到最优解

X2 (

731517T,,,0,0)，最优值为maxZ 。 2222

5 单纯形法的进一步讨论

5.1 人工变量法（大M法）

通常对一个线性规划问题进行标准化以后，约束矩阵会有单位化的可行基出现，可以作为单纯形法的初始可行基。但有些情况则没有现成的初始可行基。人工变量法就是针对标准

形约束条件的系数矩阵中不含单位矩阵的处理方法。

例如LP问题：maxZ 3x1 x3

x1

2x1 x, 1

x2 x23x2x2,x3

x3 x3 x3 0

4 1 9

首先将其化为标准形式，maxZ 3x1 0x2 x3 0x4 0x5

x1

2x1s.t. x 1~5

x2 x23x2 0

x3 x3 x3

x4

x5

4 1 9

再强行加上人工变量，使其出现单位矩阵：

x1

2x1 x 1~5

x2 x3 x2 x33x2 x3

0

x4

x5 x6

x7

4 1 9

但这样处理后产生两个问题：①不易接受。因为是强行引进，x6,x7称为人工变量。它们与x4,x5不一样。x4,x5称为松弛变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。②人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。

为此，可以把目标函数作如下处理：

maxZ 3x1 0x2 x3 0x4 0x5 Mx6 Mx7

x1

2x1 x 1~5

x2 x3 x2 x33x2 x3

0

x4

x5 x6

x7

4 1 9

其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有：

1 2T

0 3

1130

1 111

1

000

0 100

010 M

001 M

4 1 9 0

11

14

1

000 k Mk

2

1

10 1 1

1 42,k4 Mk3

031000 1

9

2M 34M

10 M

010M 3

2 1

1 103

kk4Mk

2

1

10 110

1 1 k2,3 3k2,k4 2

6 04

03 3 1

6

6M 30

4M 1

3M

4M

6M

30203

1

1 1 1

1

10 1101 6

k 23

1 02/301/2 1/21/61 6M 3

4M 1

3M

4M

6M

0

0 1

1/2 1/21/2 k2k0

1

1/3

0001/31 3k3,k2 3,k4 6M 3 k

3 1 0 2/3

01/2 1/21/6

00

3

3/2

M 3/2

M 3/4

000 1

1/2 1/21/20 3

0 1

1/3

0001/33 2

k3

3/20 1

03/4 3/41/41 0

3

3/2

M 3/2

M 3/4

3

00

0 1

1/21/2 1/20

k1

1/2 1

0 1/41/41/45/2 2 3

k3,k4 3k3

3/20 1

03/4 3/41/43/2

9/2

3/4

M 3/4

M 1/4

3/2

至此，检验行已没有正数，当前解即为最优解。

去掉人工变量x56,x7，即得原LP问题的最优解：X0 (0,

2,32

,0,0)T

。最优值为：maxZ

32.

5.2 两阶段法（两相法）

用大M法处理人工变量时，若用计算机处理，必须对M给出一个较大的具体数据，并视具体情况对M值作适当的调整。为了克服这一麻烦，下面的两阶段法将问题拆成两个LP问题分两个阶段来计算：

阶段1： 用人工变量的和表示原目标函数，对新的目标函数求最小指，使其满足原问题的约束条件。若此问题有可行域，新目标函数的最小值实际上应该是零，转到第二阶段。

0 3 1 3

否则，若最小值比零大，则不存在可行解。

m

即：min

x

i 1

n i

xn 1

xn 2

xn m

b1 b2 bm

a11x1 a12x2 a1nxn

ax a22x2 a2nxn 211

ax ax ax

m22mnn

m11 x1~n 0,xm 1, ,xn m 0

阶段Ⅱ：采用第1阶段的最优基本解作为原问题的初始解，在此情况下，原目标函数通过高斯消元法以非基本变量表示，然后用基本单纯形法求解即可。

因此两阶段法的第1阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第2阶段的计算。

例如用两阶段法解：maxZ 3x1 x3

x1

2x1 x, 1

x2 x23x2x2,x3

x3 x3 x3 0

4 1 9

阶段1的线性规划问题可写为：

min x6 x7

x1

2x1 x 1~5

x2 x3 x2 x33x2 x3

0

x4

x5 x6

x7

4 1 9

先对目标函数标准化：令 ，有max x6 x7。 对单纯形矩阵作初等行变换，有 1 2T1

0 0

1130

1 110

1

000

0 100

1

010 1

001 1

1 110

4 1 9 0

1 2

k4 k2,k4 k3

0 2

1

000

0 10 1

000

1

34

1

00

1

4 1 9 10

3 2

k1 k2,k3 3k2,k4 4k2

6 6

2 144

1

000

1 133

00

1

00

1

3 1 6 6

3

21 k3

1 6

6

02 12/34

1

000

1 11/23

1

00

3 1 1 6

01/32/30

0 0

k1 3k3,k2 2k3,k4 6k3

1 0

1

000

1/201/20

1

00

0 3 1 0

得到最小值为零，转入第二阶段。

阶段Ⅱ的目标函数写为：maxZ 3x1 0x2 x3 0x4 0x5 对单纯形矩阵进行初等行变换，有：

0 0

T2

1 3

01/3

1

000

1/201/20

1

00

2/3

1

0 3 1 0

0

03 k3

3/22

3

001/3

1

0000

1/203/4000

1

00

1

1

0 3 3/2

0

0

1/21

k2 k3,k4 k3

3/23

9/2

1

000

1/2 1/43/4 3/4

1

00

1

5/2

3/2

3/2

53T

,,0,0)，最22

至此，检验行已没有正数，当前解即为最优解。最优解为：X0 (0,优值为：maxZ

32.

由此可见，用人工变量法和两阶段法得到了同样的结果。

6 结论

线性规划是数学规划中理论成熟，实践广泛的一个分支。目前，解线性规划的方法很多，最常用最有效的还是单纯形法。此外还有初等矩阵法，迭代法等有关专著[4]中的方法。这些方法各有特点，例如，初等矩阵法用来求解大规模稀疏线性规划问题较为方便；迭代法可利

用在计算机外存较大的机型上，可将迭代法用于高维线性规划问题的求解，但收敛很慢。 单纯形法的实质是比较可行集的顶点，逐步调优。应用单纯形法时，必须把线性规划问题化为它的标准形式。通过人工变量技术，单纯形法可以处理任意约束（包括不等式约束，等式约束）问题。有些专家把结构优化问题看成是结构分析的有限元法加线性规划问题。足见线性规划及单纯形法在优化设计中的地位。

参考文献

[1] [2] [3] [4]

钱令希.工程结构优化设计.北京:水利电力出版社,1983

陈耿东,工程结构优化设计基础.北京;水利电力出版社,1983. 张炳华.土建结构优化设计.上海:同济大学出版社,1997 赵凤治.线性规划计算方法.科学出版社,1982.

本文来源：https://www.bwwdw.com/article/5qwj.html