工程优化设计中单纯形法的基本原理
张云龙
（大连海洋大学土木工程学院辽宁大连116023)
摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。
关键词：线性规划图解法单纯形法大M法
THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGN
ZHANG Y un-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 W ords: Linear programming；Graphic method；Simplex Method; Big M Method
1引言
在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。
虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等错误！未找到引用源。。
因此，深刻理解线性规划问题及其标准解法——单纯形法，显得尤为关键。
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 =+ 即要求：12m ax 2Z x x =+ 目标函数即为：12m ax 2Z x x =+ 约束条件：s.t. 21
2121
251562245
,0
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 =+++
11112211
2112222211
22(,)(,)..
(,)0,(1,2,,)n n n n m m m n n m
j a x a x a x b a x a x a x b s t a x a x a x b
x j n +++≤=≥??
+++≤=≥??
?
?+++≤=≥?≥=??
上述模型的简写形式为：1
m ax(m in)n
j
j j Z c
x ==
∑
1
(,)(1,2,,).0(1,2,,)
n
ij 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 ?? ? ?= ? ?
?? 1
2
121
2
(,,,)n
n
n
m m m n a a a
a a a A P P P a a a ??
? ?== ?
???
则线性规划问题的矩阵形式：max(min)Z CX =
(,).0A X b s t X ≤=≥??≥?
2.2 线性规划问题的标准形式
LP 问题的数学模型的标准形式为：1122m ax n n Z c x c x c x =+++
1
(1,2,,,0)
.0(1,2,,)
n
ij 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 ’的最大值，即：m i n m a x
Z Z '=。从而目标函数变换为：1122m a x n n Z c x c x c x '=----
⑵ 当约束条件中含有不等式时， 如：12m ax 33Z x x =+
()()12
12
2101.21420(1,2)
i
x x s t x x x i +≤→??
+≤→??≥=? 此时，对⑴ 12210x x +≤，引入变量30,x ≥ 使得⑴式变为：123210x x x ++=，同理对⑵式12214x x +≤引入变量40,x ≥使得⑵式变为：124214x x x ++= 于是原LP 问题化为标准形式：12m ax 33Z x x =+
12312
4210.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,2
i x x s t x x i +≤??≤??≥=?
解：123Z x x =+在原点的梯度：1
3,x
Z '=2
1x Z '= 所以，(3,1)Z ?=。随着直线213x x =-沿梯度方向去扫可行域，目标函数123Z x x =+中的Z 在增加。如：经过点(1,1)时， 4.Z =
由此可见，当目标函数沿梯度的方向去扫可行域时，在顶点(6,1)处取得最大值。目标函数的最优值为：m ax 36119.Z =?+=
图1 线性规划图解法
实际上，如果利用图解法解决很多的类似的题目后，我们可以得到以下事实： ①若线性规划问题的可行域存在，则可行域一定是凸集。
②若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个顶点。
4 单纯形法
4.1 单纯形法中的一些基本概念
在一个非齐次线性方程组中，例如： 非其次方程组23
1
24
1
2
5
515
62245
x x x x x x x x +=??
++=??++=?，其增广矩阵为 称3,x 4,x 5x 为基变量（括号中的数字所对应的变量）。基
变量个数=()()3r A r A ==。
此方程组的解为324125
1
2
15524625
x x x x x x x x =
-??
=
--??=--?。 其中1,x 2x 为任意实数。称它们为非基变量，或自由变量。称非基变量1,x 2x 为0的解
(0,0,15,24,5) 叫基解。如果一个解的每个分量都是非负数，就叫做可行解。如果基解是
可行的，就叫基可行解，如0(0,0,15,24,5)T
X =即为基可行解。基可行解所对应的基称为
2x ()
()
()
05100156
2010
2411
15A ?? ?= ? ??
?
1
x 2
x 3
x 4x 5x b
可行基，如345{,,}x x x 即为可行基。
基可行解很重要，可以证明以下定理：
定理1：若线性规划问题存在最优解，则问题的可行域是凸集。
定理2：线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。 定理3：若线性规划问题最优解存在，则最优解一定在可行域顶点处取得[2]
。 由此可看出，最优解要在基可行解（可行域顶点）中找。
通过以上分析，我们也可以得到以下几个结论：
（1）线性规划问题的可行域是一个凸集，可行域可能有界，也可能无界，但其顶点数是有限个。
（2）线性规划问题每个基本可行解对应于可行域的一个顶点。
（3）若线性规划问题有最优解，则必可在其可行域的某个（或多个）顶点上达到最优值。
4.2 单纯形法基本原理
首先说明什么是基变换。
例如，对于LP 问题：12345m ax 2000Z x x x x x =++++
23
1
24
12
5
51562245
01,,5
i
x x x x x x x x x i +=??
++=??
++=??≥=?
当前可行基345{,,}x x x 所对应的基可行解0(0,0,15,24,5)T
X =。
这个解显然不是最优。因为，当10,x =20x =时是没有现实意义的。相应地，将0X 代入目标函数得0()0Z X =，若让非基变量12,x x 取值从零增加，相应的目标函数值Z 也将随之增加。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。
再注意到目标函数123452000Z x x x x x =++++中，
1x 前的系数2比2x 前的系数1大，即1x 每增加一个单位对Z 的贡献比2x 大。故应让1x 从非基变量转为基变量，称为进基。这种判断进基变量的方法称为最大系数原则法。
又因为基变量只能有三个，因此必须从原有的基变量3,x 4,x 5x 中选一个离开基转为非基变量，称为出基。谁出基呢？
因为2x 是仍留作非基变量的，故仍有20x =。
则必有3415
1150
24605
x x x x x =≥??
=
-≥??=-≥?，进而可以解出1x 的一个取值范围，即1246
x ≤且15x ≤。
让1x 从零增加，其能取得的最大值为124m in{
,5} 4.6
x ==
由412460x x =-≥可知，此时，4x 已经从24降到了0，达到了非基的取值，变成非基变量。所以出基的变量是4x 。从而得到新的可行基135{,,}x x x 。这种判断出基变量的方法称为最小比值原则法。
对于式子：32412512
15524625
01,,5
i
x x x x x x x x x i =
-??
=
--??
=--??≥=? ，将可行基135{,,}x x x 留在左边，非基变
量2,x 4x 移到右边，并用代入法消元，则上式变为：3212452
4
155********
3601,,5
i
x x x x x x x x x i =-??
?=
--??
?=
-+?
?≥=? 。由此
得到一个新的基本可行解：1(4,0,15,0,1)T
X =。此时目标函数值
10()248()0.Z X Z X =?== 从目标函数值明显看出，1X 比0X 明显地得到了改善。代
入目标函数得：241183
3
Z x x =+
-
。
这一过程可以用增广矩阵的行初等变换表示，并在增广矩阵末尾行增加一行，称为检验行或者目标函数行，其系数即为对应未知数的系数，常数列对应的数值即为目标函数值。即为05100156
201024
1100152
1
0A ?? ?
?= ? ???
，其中(2,1,0,0,0,0)这一行为检验行，是目标函数Z 的系数，行末的0为Z 的取值。这个矩阵也称为单纯形矩阵或单纯形数表。
对单纯形矩阵进行行变换可以实现进基和出基两个过程，如上文所述，进基过程依据最大系数原则，出基过程依据最小比值原则。从开始至结束，每一步都需要运用这两个原则，并最终找到Z 的最大值。结束的标志即为检验行全部系数没有正数[3]
。
对于()
[]
()
()
0510********
2411001521
0A ?? ?
?
= ? ? ??
?
，检验行最大系数为2（尖括号中数字），进基变量为1x 。利用最小比值原则15245m in ,,4061θ??==?
??
?，确定主元行为第二行，主元素为6，对应出基变量为4x 。中括号里面的数字即为主元素，其所在行为主元行，主元行系数为1的基变量即为出基变量。
具体过程如下：
()
[]()
()
()
[]
()
20
510015051001562010
2411/301/60
411100156
11001521
00210
0A k ????
? ?
?
?=→→ ? ? ? ? ???
?
?
()
()[]
()
3242051001511/3
01/60
4,202/301/61101/3
1/3
8k k k k ??
? ?→--→ ?- ? ?--?
?
()
()[]
3051001511/3
01/60432
0101/432320
1/3
1/3
08k ??
?
?→→ ?
- ?--??
()
()
()
1323430015415215210
01/41272115,,33
0101/432320
1/4
12
172k k k k k k ?-?
?-
?
→---→ ?- ?
---??
至此，检验行已没有正数，当前解即为最优解。令非基变量4,x 5x 为0，得到最优解
27315(
,,,0,0)222T X =，最优值为17m ax 2
Z =。
5 单纯形法的进一步讨论
5.1 人工变量法（大M 法）
通常对一个线性规划问题进行标准化以后，约束矩阵会有单位化的可行基出现，可以作为单纯形法的初始可行基。但有些情况则没有现成的初始可行基。人工变量法就是针对标准
形约束条件的系数矩阵中不含单位矩阵的处理方法。
例如LP 问题：13m ax 3Z x x =-+
123123231
23
42139
,,0
x x x x x x x x x x x ++≤??
-+-≥??+=??≥?
首先将其化为标准形式，12345max 3000Z x x x x x =-++++
1234
1235
23
1~5
421..39
x x x x x x x x s t x x x +++=??
-+--=??+=??≥?
再强行加上人工变量，使其出现单位矩阵：
1234
12356
23
7
1~5
42139
x x x x x x x x x x x x x +++=??
-+--+=??++=??≥?
但这样处理后产生两个问题：①不易接受。因为是强行引进，67,x x 称为人工变量。它们与45,x x 不一样。45,x x 称为松弛变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。②人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。
为此，可以把目标函数作如下处理：
1234567max 3000Z x x x x x M x M x =-++++--
1234
12356
23
7
1~5
42139
x x x x x x x x x x x x x +++=??
-+--+=??++=??≥?
其中M 为任意大的实数，“-M ”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有：
()
1111000421101101031000193
1
0T M
M
?? ?---
?= ? ?---??
()
[]
()
()
424311
110004
2
110110
1,03100019234100
010k M k k M k M M
M
M ??
?---
?→++→ ?
? ?---?
?()
()
[]()
1232423
2111032
110110
1,3,4604
03316630
41
340
6k k k k k M k M M M
M
M ?-?
?---
?→---→ ?-
? ?++-?
?
()
()
[]330211103211011011
6
102/301/21/21/6163
41
340
6k M M M
M
M ?-?
?---
?→→ ?-
?++-??
()()
()
()[]
1323430
011/21/21/200
11/3
0001/333,2,63102/301/21/21/6100
3
3/2
3/2
3/4
3k k k k k M k M M ?--? ?
?→-+-+→ ?- ? ?---+-?
?
()
()
[]
300011/21/21/20011/3
0001/333
2
3/20103/43/41/410
3
3/2
3/2
3/4
3k M M ?--? ?
?→→ ?- ?---+-??
()
()
()
234300
011/21/21/20
1/210
01/41/41/45/21
,33
3/20103/43/41/43/29/2
3/4
3/4
1/4
3/2k k k k M M ?--?
?--
?→--→ ?
-
?---+---??
至此，检验行已没有正数，当前解即为最优解。
去掉人工变量67,x x ，即得原LP 问题的最优解：053(0,
,,0,0)22
T
X =。最优值为：3m ax .2Z =
5.2 两阶段法（两相法）
用大M 法处理人工变量时，若用计算机处理，必须对M 给出一个较大的具体数据，并视具体情况对M 值作适当的调整。为了克服这一麻烦，下面的两阶段法将问题拆成两个LP 问题分两个阶段来计算：
阶段1： 用人工变量的和表示原目标函数，对新的目标函数求最小指，使其满足原问题的约束条件。若此问题有可行域，新目标函数的最小值实际上应该是零，转到第二阶段。
否则，若最小值比零大，则不存在可行解。
即：1
m in m
n i
i x
?+==
∑
11112211
121122222
211221~10,,,0
n n n n n n m m m n n
n m
m
n m n m a x a x a x x b a x a x a x x b a x a x a x
x b x x x +++++++++=??
++++=??
?
?++++=?≥≥??
阶段Ⅱ：采用第1阶段的最优基本解作为原问题的初始解，在此情况下，原目标函数通过高斯消元法以非基本变量表示，然后用基本单纯形法求解即可。
因此两阶段法的第1阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第2阶段的计算。
例如用两阶段法解：13m ax 3Z x x =-+
123123231
23
42139
,,0
x x x x x x x x x x x ++≤??
-+-≥??+=??≥?
阶段1的线性规划问题可写为：
67m in x x ω=+
1234
12356
23
7
1~5
42139
x x x x x x x x x x x x x +++=??
-+--+=??++=??≥?
先对目标函数标准化：令ωω'=-，有67m ax x x ω'=--。 对单纯形矩阵作初等行变换，有 ()
11111000421101101031000190
1
1
0T ?? ?---
?= ? ?--??
()
[]
()
()
424311
1100042
110110
1,0310001924
1
10k k k k ?? ?---
?→++→ ? ? ?--?
?
()
()
[]()
12324230
211032
11010
1,3,4604031660
4
3
6k k k k k k ?? ?---
?→---→ ? ? ??
?
()
()
[]33
0211321101116
102/301/216
4
3
6k ?? ?--- ?→→
? ???
()
()
()13234300
011/200
11/30033,2,6102/301/210
0k k k k k k ?-? ?
?→-+-→ ? ???
得到最小值为零，转入第二阶段。
阶段Ⅱ的目标函数写为：12345max 3000Z x x x x x =-++++ 对单纯形矩阵进行初等行变换，有：
()
()
[]
200
011/200
11/3
003102/301/2130
1
0T ?-? ?
?= ? ? ?-?
?
()
()
[]
30
0011/20011/3
00332
3/20103/43/23
1
000k ?-? ? ?→→
?
?-??
()
()
()
234300
011/20
1/210
01/45/21
,3
3/20103/43/29/2
3/4
3/2k k k k ?-?
?--
?
→--→ ?
?---??
至此，检验行已没有正数，当前解即为最优解。最优解为：053(0,,,0,0)22
T
X =，最优值为：3m ax .2Z =
由此可见，用人工变量法和两阶段法得到了同样的结果。
6 结论
线性规划是数学规划中理论成熟，实践广泛的一个分支。目前，解线性规划的方法很多，最常用最有效的还是单纯形法。此外还有初等矩阵法，迭代法等有关专著[4]中的方法。这些方法各有特点，例如，初等矩阵法用来求解大规模稀疏线性规划问题较为方便；迭代法可利
用在计算机外存较大的机型上，可将迭代法用于高维线性规划问题的求解，但收敛很慢。
单纯形法的实质是比较可行集的顶点，逐步调优。应用单纯形法时，必须把线性规划问题化为它的标准形式。通过人工变量技术，单纯形法可以处理任意约束（包括不等式约束，等式约束）问题。有些专家把结构优化问题看成是结构分析的有限元法加线性规划问题。足见线性规划及单纯形法在优化设计中的地位。
参考文献
[1]钱令希.工程结构优化设计.北京:水利电力出版社,1983
[2]陈耿东,工程结构优化设计基础.北京;水利电力出版社,1983.
[3]张炳华.土建结构优化设计.上海:同济大学出版社,1997
[4]赵凤治.线性规划计算方法.科学出版社,1982.
工程优化设计中单纯形法的基本原理 张云龙 （大连海洋大学土木工程学院辽宁大连116023) 摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。 关键词：线性规划图解法单纯形法大M法 THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGN ZHANG Y un-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 W ords: Linear programming；Graphic method；Simplex Method; Big M Method 1引言 在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。 虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等错误！未找到引用源。。 因此，深刻理解线性规划问题及其标准解法——单纯形法，显得尤为关键。 2线性规划问题 2.1数学模型 线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。例如，美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？ 表1-1 工时及利润简表
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
第4章 单纯形法的计算方法单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z = 从Pj ( j = 1 , 2 , ? , n)中一般能直接观察到存在一个初始可行基 （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 及 ( i = 1 , 2 , ? , m; j = 1 , 2 , ? , n)进行编号, 则可得下列方程组 显然得到一个m×m单位矩阵 以B 作为可行基。将上面方程组的每个等式移项得 令由上式得 又因 ≥0, 所以得到一个初始基可行解 （3）第三种情况：对所有约束条件是“ ≥”形式的不等式及等式约
束情况, 若不存在单位矩阵时, 就采用人造基方法。即对不等式约束减去一个非负的剩余变量后, 再加上一个非负的人工变量; 对于等式约束再加上一个非负的人工变量, 总能得到一个单位矩阵。 4.2 最优性检验和解的判别 对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况, 为此需要建立对解的判别准则。一般情况下, 经过迭代后可以得到： 将上代入目标函数，整理后得 令 于是 再令 则 (1) 最优解的判别定理 若为对应于基B的一个基可行解，且对于一切 且有则 为最优解。称为检验数。 (2) 无穷多最优解的判别定理 若为一个基可行解， 且对于一切 且有 又存在某个非基变量的检验数，则线性规划问题有无穷多最优解。 (3) 无界解判别定理 若为一个基可行解，有一个> 0 ,并且对i = 1 , 2 , ?, m,有≤0 , 那么该线性规划问题具有无界解(或称无最优解)。 4.3 基变换
单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都就是非负的(否则无解),接下来的m 列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都就是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题就是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量与主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格与新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0)、把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行与列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化与处理(本程序所用的实例用的就是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组、用于很难预先估计矩阵的行与列,所以在程序中才了动态的内存分配、需要重载析构函数bool Is_objectLine_All_Positive(); //判断目标行就是否全部为非负数,最后一列不作考虑 这个函数用来判断就是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列就是否全部为负数或零 这个函数用来判断线性规划就是否就是无解的 bool Is_column_all_Positive(int col); //判断col列中就是否全部为正(不包括目标行)
单纯形法表的解题步骤 单纯形法表结构如下： j c → 对应变量的价值系数 i θ B C b X b 1x 2x 3x " j x 基变量的价值系数 基变量 资源列 θ规则 求的值 j σ 检验数 ①一般形式 若线性规划问题标准形式如下： 123451231425max 23000284164120,1,2,5 j z x x x x x x x x x x x x x j =++++++=??+=?? +=??≥=?" 取松弛变量345,,x x x 为基变量，它对应的单位矩阵为基。这样就得到初始可 行基解：()()0 0,0,8,16,12T X =。将有关数字填入表中，得到初始单纯形表，如表 1-1所示： 表 1-1 ()()00,0,8,16,12T X = j c → 2 3 0 0 0 i θ B C b X b 1x 2x 3x 4x 5x 0 3x 8 1 2 1 0 0 4 0 4x 16 4 0 0 1 0 -
5x 12 0 [4] 0 0 1 3 j σ 2 3 0 0 0 若检验数均未达到小于等于0，则对上表进行调整。选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的 θ值，选出其中最小的一行，该行对应的基变量为出基变量。修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。修改后的单纯形表如表 1-2所示： 表 1-2 ()()10,3,2,16,0T X = 检验数12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示： 表 1-3 ()()22,3,0,8,0T X =
单纯形法求解线性规划的步骤
单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive(); //判断目标行是否全部为非负数,最后一列不作考虑 这个函数用来判断是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列是否全部为负数或零 这个函数用来判断线性规划是否是无解的 bool Is_column_all_Positive(int col); //判断col列中是否全部为正(不包括目标行)
单纯形法 需要解决的问题： 如何确定初始基本可行解； 如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降； 如何判断一个基本可行解是否为最优解。 min f(X)=-60x1-120x2 s.t. 9x1+4x2+x3=360 3x1+10x2+x4=300 4x1+5x2+x5=200 x i≥0 (i=1,2,3,4,5) (1) 初始基本可行解的求法。当用添加松弛变量的方法把不等式约 束换成等式约束时，我们往往会发现这些松弛变量就可以作为 初始基本可行解中的一部分基本变量。 例如：x1-x2+x3≤5 x1+2x2+x3≤10 x i≥0 引入松弛变量x4，x5后，可将前两个不等式约束换成标准形式 x1-x2+x3+x4=5 x1+2x2+x3+x5=10 x i≥0 (i=1,2,3,4,5) 令x1=x2=x3=0，则可立即得到一组基本可行解 x1=x2=x3=0，x4=5，x5=10 同理在该实例中，从约束方程式的系数矩阵 中可以看出其中有个标准基，即 与B对应的变量x3，x4，x5为基本变量，所以可将约束方程写成 X3=360-9x1-4x2 x4=300-3x1-10x2 x5=200-4x1-5x2 若令非基变量x1=x2=0，则可得到一个初始基本可行解X0 X0=[0,0,360,300,200] T 判别初始基本可行解是否是最优解。此时可将上式代入到目标函数中，得：
F(X)=-60x1-120x2 对应的函数值为f(X0)=0。 由于上式中x1,x2系数为负，因而f(X0)=0不是最小值。因此所得的解不是最优解。 (2) 从初始基本可行解X0迭代出另一个基本可行解X1，并判断X1是否 为最优解。从一个基本可行解迭代出另一个基本可行解可分为 两步进行： 第一步，从原来的非基变量中选一个（称为进基变量）使其成为基本变量； 第二步，从原来的基本变量中选一个（称为离基变量）使其成为新的非基变量。 选择进基和离基变量的原则是使目标函数值得到最快的下降和使所有的基本变量值必须是非负。 在目标函数表达式中，非基变量x1,x2的系数是负值可知，若x1,x2不取零而取正值时，则目标函数还可以下降。因此，只要目标函数式中还存在负系数的非基变量，就表明目标函数还有下降的可能。也就还需要将非基本变量和基本变量进行对换。一般选择目标函数式中系数最小的（即绝对值最大的负系数）非基变量x2换入基本变量，然后从x3，x4，x5中换出一个基本变量，并保证经变换后得到的基本变量均为非负。 当x1=0，约束表达式为： X3=360-4x2≥0 x4=300-10x2≥0 x5=200-5x2≥0 从上式中可以看出，只有选择 x2=min{}=30 才能使上式成立。由于当x2=30时，原基本变量x4=0，其余x3和x5都满足非负要求。因此，可以将x2，x4互换。于是原约束方程式可得到：4x2+x3=360-9x1 10x2 =300-3x1-x4 5x2+x5=200-4x1 用消元法将上式中x2的系数列向量变[4,10,5]T换成标准基向量[0,1,0]T。其具体运算过程如下： -*4/10 : x3=240-78x1/10+4 x4/10 /10 : x2 =30-3x1/10-x4/10
图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
第4章单纯形法的计算方法 单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。 4.1初始基可行解的确定 为了确定初始基可行解，要首先找出初始可行基，其方法如下。 (1) 第一种情况：若线性规划问题 max z = 'n ' am 二bj = 1,2,...,m X j XO, j =1,2,...n 从Pj ( j = 1 , 2 , ? , n)中一般能直接观察到存在一个初始可行基 (2)第二种情况：对所有约束条件是“W”形式的不等式,可以利用化为标准型的方法，在每个约束条件的左端加上- 一个松弛变量。经过整理，重新对 X j 及a j ( i = 1 , 2 , ?,m j = 1 , 2 ,? , n)进行编号，则可得下列方 程组 为+ a1卬十X m十+???*a1n x n j x 2 + a z’m^h X m 十 + .. .+ a2n X n = b2 X m +a m,m_h X m十+.??*a nn x n - b n X(,X2,...,X^O 显然得到一个m x m单位矩阵 n ' C j X j j=l B=(R,巳，…，P n)= 1 i- 0 1…
以B 作为可行基。将上面方程组的每个等式移项得 X =d —印小书冷出―…―a 1n X n X 2 = b 2 — a 2,^4X m+ _..^ a 2n X n 令Xm 1 ~ Xm ?2 =…=Xi =0,由上式得 X 二 b j (i =1,2,..., m) 又因b i >0,所以得到一个初始基可行解 X =(X 1,X 2，…，X m ,0,...,0) T (n -m) 个 -(b 1, 6 ,...,b m ,0, 0 (n _m) 个 (3)第三种情况：对所有约束条件是“形式的不等式及等式约束情况，若 不存在单位矩阵时，就采用人造基方法。即对不等式约束减去一个非负的剩余变 量后，再加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量， 总能得到一个单位矩阵。 4.2 最优性检验和解的判别 对线性规划问题的求解结果可能出现唯一最优解、 无穷多最优解、无界解和 无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后可 以得到： , n , X i -送 a j X j (i =1,2,...,m) j zm 1 将上代入目标函数，整理后得 m - n m - Z=W C i b i +送(C j ca j )X j i =1 j h 1 if B = (P 1 ,P 2 , ...,P n ) = ‘1 0… 0 1… (T o
第4章 单纯形法的计算方法 单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代, 直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z =n j j j=1c x ∑ 1,1,2,...,0,1,2,...n ij j i j j a x b i m x j n =?==???≥=?∑ 从Pj ( j = 1 , 2 , ? , n )中一般能直接观察到存在一个初始可行基 121(,,...,)n B P P P 0 0?? ?0 1 0 ?== ? ?0 0 1?? （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 j x 及ij a ( i = 1 , 2 , ? , m ; j = 1 , 2 , ? , n )进行编号, 则可得下列方 程组 11,1111 22,1122,1112.........,,...,0 m m n n m m n n m m m m nn n n n x a x a x b x a x a x b x a x a x b x x x +++++++++=?? +++=?? ??+++=??≥? 显然得到一个m ×m 单位矩阵
单纯形法的解题步骤
三、单纯形法的解题步骤 第一步：作单纯形表. （1）（1）把原线性规划问题化为标准形式； （2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； （3）（3）目标函数非基化； （4）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即 ，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而 所对应的列向量无正分量，则线性规划问题无最 优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1）找到最大正检验数，设为，并确定
（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. 表 6.8 x1 x2x3x4x5常数 x 3 x 4 x 51 0 1 0 0 1 2 0 1 0 0 （1）0 0 1 5 10 4 S′ 1 3 0 0 0 0 x 3 x 4 x2 1 0 1 0 0 （1）0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -12 x 3 x 1 x 20 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′0 0 0 -1 -1 -14
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出
单纯形法原理及步骤 单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。 概述： 根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止
目标函数的值无限增大（或向负的方向无限增大）。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。 求解步骤： （1）确定初始基可行解 ①从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量； ②对约束条件全为“<=”连接的LP，化为标准形，左端添加松弛变量后即形成一个单位子矩阵； ③约束条件中含有“<=”或“=”连接的方程，在插入剩余变量后找不到单位矩阵，则必须采用
单纯形算法的一般原理 单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。 考虑到如下线性规划问题： 其中Ａ一个m ×n 矩阵，且秩为m ，ｂ总可以被调整为一个m 维非负列向量，Ｃ为n 维行向量，Ｘ为n 维列向量。 根据线性规划基本定理： 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。 这个重要的定理启发了Dantzig 的单纯形法， 即将寻优的目标集中在D 的各个顶点上。 Dantzig 的单纯形法把寻优的目标集中在所有基本可行解 （即可行域顶点）中。 其基本思路是从一个初始的基本可行解出发，寻找一条达到 最优基本可行解的最佳途径。 单纯形法的一般步骤如下： （1）寻找一个初始的基本可行解。 （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 （3）移至目标函数值有所改善的另一个基本可行解， 然后转会到步骤（2）。 求解思想如下图所示： maxZ=CX AX=b X 0??≥?
确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m 个系数列向量恰好构成一个可行基，即 Ａ=（ＢＮ），其中 Ｂ=（Ｐ1，Ｐ2，…Ｐm ）为基变量x1，x2，…xm 的系数列向量 构成的可行基， Ｎ=(Ｐm+1，Pm+2， …Pn)为非基变量xm+1，xm+2， …xn 的 系数列向量构成的矩阵。 那么约束方程AX=b 就可表示为： 用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得： 若令所有非基变量 ，则基变量 由此可得初始的基本可行解 B B N N X AX=(BN)=BX +NX =b X ?? ???-1-1B N X =B b-B NX N X =0-1B X =B b 1B b X=0-?? ???-1-1-1B N B N N B AX=b BX +NX =b X =B b-B NX X =0,X =B b →→→