2020/8/20
单纯形法小结
Page 20
建 立 个数
模 型 两 三个 xj≥0
个 以上
求 图 单纯 不
解 解 形法 处
法、
理
单
纯
形
法
取值
xj无 约束
令xj = xj′ - xj″
xj ≤ 0
令 xj’ = - xj
xj′ ≥0 xj″ ≥0
右端项
等式或 不等式
极大或极小
bi ≥0 bi < 0 ≤ = ≥ max Z
-1
0
0
-M
x3
x4
x5
x6
1
－1ቤተ መጻሕፍቲ ባይዱ
0
1
2
0
1
0
1
0
0
0
－1+2M↑ －M
0
－1
0
1
0
0
1
0
1
0
0
0
0
－M
0
0
0
－1/5
0
0
3/5
1
1
－2/5
0
0
0
0
0
1
2
0
1
5/3
1
0
2/3
0
-5
-25/3
-M
x7
θi
0
4
0
5
1
1→
3/5 →
8/3 ——
——
31/3 →
——
2、两阶段法 在原来问题引入人工变量后分两个阶段求解线性
x1-2x2+x3+x4
=11
-4x1+x2+2x3 -x5+x6 =3
-2x1 +x3
+x7 =1
xi≥0,i=1,2, …,7
用单纯形法进行第一阶段的计算如下表
2020/8/20
人工变量x6=x7＝ 0，第一阶段目标函数W=0，则 (0，1，1，12，0)T是原线性规划问题的基可行解，转第 二阶段的计算
x6
-M
x5
-1
x3
j
2
x2
-M
x5
-1
x3
j
2
x2
3
x1
-1
x3
2020/8/20 j
3
b
x1
4
-4
10
1
1
2
3－2M
3
－6
8
－3
1
2
5-6M 3/5 －6/5
31/5 3/5 11/5 －2/5
5↑
13
0
31/3
1
19/3
0
0
2 x2 3 －1 －2 2+M 5 3 －2 5M↑ 1 0 0 0 1 0 0 0
验数，即：k max{ j | j 0} ，其对应的xk作为换入变 量。
② 确定换出变量。根据下式计算并选择θ ，选最小的θ对应基
变量作为换出变量。 L
2020/8/20
min
bi aik
aik
0
单纯形法的计算步骤
Page 4
③ 用换入变量Xk替换基变量中的换出变量，得到一个新的 基。对应新的基可以找出一个新的基可行解，并相应地 可以画出一个新的单纯形表。
4）解的判断同单纯形法
2020/8/20
例4.2 用两阶段法求解线性规划问题
minΖ=-3x1+x2+x3
s.t.
x1-2x2+x3 ≤11
-4x1+x2+2x3 ≥3
-2x1 +x3
=1
x1,x2,x3, ≥0
解：先在约束条件中加入人工变量，写出辅助规划问
题。
s.t.
2020/8/20
Min W=x6+x7
1
0
1/3 30
0
0 －4/3
0
3/5 －1/5
1 －1/5 －2/5
0 －1 －1
最优值：
单纯形法的计算步骤
Page 6
例1.11 用单纯形法求解
max Z x1 2 x2 x3
2x1 3x2 2x3 15
s.t
1 3 x1 x2 x1、x2、x3
5x3 0
20
解：将数学模型化为标准形式：
x3
x7
1
x j 0, j 1,2,,7
其中：M是一个很大的抽象的数，不需要给出具体的数值， 可以理解为它能大于给定的任何一个确定数值；再用前面介 绍的单纯形法求解该模型，计算结果见下表。
2020/8/20
单纯形法的进一步讨论－人工变量法 Page 11
cj
CB
XB
0
x6
-M
x5
-M
x7
j
0
不 约束条 加 加 减 不
处 理
件两端 同乘以
松
入
去
处
-1 弛 人 xs 理
变工加
量变入
xs
量 xa
xa
minZ
令 z′=- Z minZ =－ max z′
新加变 量目标
系数 xs xa
0 -M
2020/8/20
A
求: j cj zj
循环
所有 是
j 0
否
找 出( j )max即 k
基变 量中是否 否
4x1 3x2 x3 4
x12x1x2
2x3 2x2
10 x3
1
x1、x2、x3 0
解：首先将数学模型化为标准形式
2020/8/20
max Z 3 x1 2 x2 x3
4x1 3x2 x3 x4 4
x1
x2
2x3
x5
10
2
x1
2x2
x3
1
x j 0, j 1,2,,5
30
x1
,
x2
,
x3
,
x4
0
2020/8/20
单纯形法的计算步骤
Page 2
2）求出线性规划的初始基可行解， 列出初始单纯形表。
cj
3
4
0 0 σj cj ciaij
θi
cB
XB
b
x1
x2
x3
x4
0
x3
40
2
1
1
0
0
x4
30
1
3
0
1
j
3？ 0
0
检验数
1 c1 (c3a11 c4a21) 3 (0 2 01) 3
σj cj ciaij
2020/8/20
单纯形法的计算步骤
Page 3
3）进行最优性检验
如果表中所有检验数 j 0 ，则表中的基可行解就是问题
的最优解，计算停止。否则继续下一步。
4）从一个基可行解转换到另一个目标值更大的基可行解， 列出新的单纯形表
① 确定换入基的变量。选择 j 0 ，对应的变量xj作为换入变 量，当有一个以上检验数大于0时，一般选择最大的一个检
单纯形法的计算步骤
Page 1
例1.10 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x2
2xx1 13
x x
2 2
40 30
x1
,
x2
0
解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:
max Z 3 x1 4 x2
2 x1 x2 x3 40
x1
3x2
x4
要求解问题的目标函数能用数值指标来反映，且 为线性函数
存在着多种方案 要求达到的目标是在一定条件下实现的，这些约 束可用线性等式或不等式描述
Page 22
2020/8/20
规划问题的方法。其中，第一阶段在原来问题中引入 人工变量，设法构造一个单位阵的初始可行基，另外 在目标函数中令非人工变量的系数全部为0，人工变量 的系数为1，构造一个新的辅助目标函数。在此基础上， 建立辅助线性规划问题。然后运用单纯形方法求解， 直到辅助目标函数值为0时为止。第二阶段重新回到原 来的问题，以第一阶段得到的可行基为初始可行基， 运用单纯形方法以求出原来问题的解。
2020/8/20
3)两阶段法的计算步骤 （1）不考虑原问题是否存在基可行解， 引进人工变 量，构造辅助线性规划问题。 （2）用单纯形方法求解辅助问题，若辅助问题的目标 函数值w≠ 0，则原问题无可行解，停止计算。 （3）若辅助问题目标函数的值w =0，则将第一阶段 计算得到的最终表，除去人工变量，将目标函数行的 系数换原问题的目标函数系数，作为第二阶段的初始 表。
max Z x1 2 x2 x3
2x1 3x2 2x3 x4 15
s.t
1
3 x
j
x1
x2 0, j
5x3 x5 1,2,,5
20
不难看出x4、x5可作为初始基变量，列单纯形表计算。
2020/8/20
单纯形法的计算步骤
Page 7
cj
1
cB 基变量 b
x1
0
x4
15 2
1、大M 法
通过引进人工变量，构造一个辅助的线性规划问题，然后 由辅助的线性规划问题找出原问题的第一个初始可行基，在此 基础上，利用单纯形方法求出原问题的最优解。
2020/8/20
单纯形法的进一步讨论－人工变量法 Page 9
例1.10 用大M法解下列线性规划
max Z 3 x1 2 x2 x3
且存在人工变量>0时，则表明原线性规划无可行解。
5）退化解的判别：存在某个基变量为零的基本可行解。 2020/8/20