单纯形法-人工变量法

一个x12方x程12把中x第去2x二2个x方5x程3直接x加4

4 6
x1 , x一2个, 变x3量,(人x4工, 变x量5 ) 0
规范化
考虑一般问题：
bi > 0 ， i = 1 , … , m
Max Z = c1 x1 + c2 x2 + … + cn xn a11 x1 + a12 x2 + …+ a1n xn = b1 a21 x1 + a22 x2 + …+ a2n xn = b2 … am1 x1+ am2 x2+…+ amn xn = bm
jm 1 j j
i1 i
i
j m 1 ij j
m
n
m
c b (c c a )x
i1 n i i
jm 1
j
i 1 i ij
j
n
Z (c z )x
0
j 1
j
j
j
n
Z C jx
0
j 1
j
其 Z m c 中 b ,C j c z ,z m c a
一、单纯形法的基本原理
（一）基本变量： 如果变量xj在某一方程中系数为1，而在其它一切方
程中的系数为零，则称xj为该方程中的基本变量。否则 为非基本变量。 （二）基本解：
在典型方程中，设非基本变量为零，求解基本变量 得到的解，称为基本解 。 （三）基本可行解：
基本变量为非负的一组基本解称为基本可行解 。
（２）最优解判别 如果任何一个非基变量的值增加都不能
使目标函数值增加，即所有检验数非正，则 当前的基本可行解就是最优解，计算结束。

cj 基 解
3 5 000 x1 x2 x3 x4 x5
0 x3 8 1 0
5 x2 6 0 1
第 0 x5 12 3 0
二
次
30 -3 0
迭 代
0
x3
4
5 x2 6
00 01
3 x1 4
10
1 00 0 1/2 0 0 -2 1
0 5/2 0 1 2/3 -1/3 0 1/2 0 0 -2/3 1/3
Simplex Method 第二章 单纯形法
SM
第2章 单纯形法
2.1 单纯形法的基本思想 2.2 单纯形法的计算过程 2.3 人工变量法 2.4 单纯形法补遗
2
第2章 单纯形法
2.1 单纯形法的基本思想
单纯形法有三种形式： ① 方程组形式 ② 表格形式 ③ 矩阵形式
2.1.1 方程组形式的单纯形法
2x2 0 +1x4 0 = 12 ②
3x1 + 4x2 0 0 +1x5 = 36 ③
条典
⑴ 当前基：m阶排列阵 ⑵ 目标方程中：一切基变量
的系数 σj = 0
满足条典的方程组称为典式(方程组)。 初始基本可行解
排列阵：
每行每列有且仅有一个元素 为1，其余元素全为0 的方阵。
X0 = (0, 0, 8, 12, 36)T z0 = 0
2.3 人工变量法
考虑标准型 (M)： 分别给每个约束方程硬性加入一个非负变量
a11x1 +a12x2+…+a1nxn +xn+1
a12x1 +a22x2+…+a2nxn
+xn+2
… … ………

max z=3x1+4x2 x1 +x2 40
2x1+x260 x1-x2 =0 x1 ,x2 0
cj →
CB XB b 0 x3 40 0 x4 60 -M x5 0
cj- zj
0 x3 40 0 x4 60 3 x1 0
cj- zj 4 x2 20 0 x4 0 3 x1 20
3 40
x1 x2 x3 1 11 2 10 [1] -1 0
例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0
CB XB b
0 x3 15 0 x4 5
0 x5 11
cj-zj
5 x2 3 0 x4 2 0 x5 5
cj-zj
3 50 00 x1 x2 x3 x4 x5 3 [5 ] 1 0 0 2 1010 2 2001 3 5000 3/5 1 1/5 0 0 7/5 0 -1/5 1 0 4/5 0 -2/5 0 1
4 2
x1 x1

x2

2
x3 x3
x5 x6 3 x7 1
x1 , , x7 0
这时，初始基和初始基可行解很明显。X(0)=(0，0，0， 11，0，3，1)T不满足原来的约束条件。如何使得可从 X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解， 从而求得问题的最优解，有两种方法：
• 两种方法
– 大M法 – 二阶段法
约束方程为“>=”或“=”的情形（加人工变量）
标准型：
min z =-3x1+x2+x3
x1 2 x2 x3 11

大M法
在一个线性规划问题的约束条件中加入人 工变量后， 工变量后 ， 要求人工变量对目标函数的取 值无影响， 为此可取人工变量在目标函数 值无影响 ， 中的系数为-M(M为非常大的正数 ，这样目 为非常大的正数)， 中的系数为 为非常大的正数 标函数要实现最大化， 人工变量只能取零， 标函数要实现最大化 ， 人工变量只能取零 ， 因此必须把人工变量从基变量中换出， 因此必须把人工变量从基变量中换出 ， 否 则目标函数就不可能实现最大化。 则目标函数就不可能实现最大化。
两阶段法的算法流程图
MaxZ=-3x1+x3 x1+ x2+ x3≤4 -2x1+ x2- x3≥1 3x2+x3=9 xi ≥0,j=1,2,3
求解辅助问题，得到辅助 问题的最优解 引进人工变量x6，x7，构造辅助 问题，辅助问题的目标函数为 所有人工变量之和的极小化
MaxW=-x6-x7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi ≥0,j=1,…,7
X B X = 同理将 写成分块矩阵 同理将C写成分块矩阵 （CB，CN）， 写成分块矩阵C=（ X N
CB=(C1,C2,…,Cm), CN=(Cm+1Cm+2，…，cn) 则AX=b可写成 ， 可写成
X B (B， ) = BX B + NXN = b N X N
CB 0 0 -3 0 0 1
bi 0 3 1 0 5/2 3/2
θ 9 3/2
3/2 x3入，x1出 -1/2 -1/4 3/4 -3/4
所以：X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2 所以：