- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
X1
0
10
X1
-10 3 4 3
-1 3/4 13/4 (3/2) 0 0 0 1
12
0
X2
X3
-12 0
(4) 1
1
0
2
0
0
3
1 1/4
0 -1/4
0 -1/2
0
8/3
1 1/2
0
5/6
0 -1/3
0
0
X4
X5
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0 2/3
0 -1/2
1 -13/6
0 2/3
θi
3/2 2/1 3/2
Y
结束
N
沿边界找新
的基本可行解
2.1 单纯形法的基本思想
单纯形法的三种形式：1）方程组形式； 2）表格形式；3）矩阵形式。
2.1.1 方程组形式的单纯形法
maxZ=3X1 +5X2
X1
+X3
=8
2X2 +X4 =12
3X1+4X2
+X5 =36
X1 … X5 0
解：(1)、确定初始可行解
B=(a3 a4 a5)=I Z -3X1-5X2 =0 X3 =8- X1 X4=12-2X2
x1 ，x2 ，… ，xn ≥ 0
2.基本过程:
1）加入人工变量;
2）通过单纯形法的迭带,将虚拟的人 工变量从原来的基变量中替换出去, 变成非基变量,使每一个人工变量都 等于0.反之,如果不能都变为非基变 量,表明原问题无可行解.
(一)、大M法：
2.4 单纯形法补遗
2.4.1 进基变量的相持及其突破
120
0
0
X1
X2
X3
X4
X5
CB
XB
0
-1 -2
0
0
0
0
X3
4
101
0
0
0
X4
3
0 (1) 0
1
00X58来自12001
CB XB
6
-1 0 0 2
0
0
X3
4
101
0
0
2
X2
3
010
1
0
0
X5
2
(1) 0
0
-2 1
(接下表)
CB
XB
8
0
X3
2
2
X2
3
1
X1
2
CB XB
8
0
X4
1
2
X2
2
1
X1
4
1
2
+x5 = 24
x1，x2 ，x3，x4 ， x5 0
突破离基变量必然立即导 致一个退化的基本可行解， 这就有可能造成单纯形法 的迭代步骤 陷入一个周而 复始的循环过程。
避免循环的方法有：
1。摄动法 2。辞典序法 3。Bland法等
摄动法避免循环的规则：
从相持的离基变量中选择下标最大者 离基。
X5 =36 -3X1-4X2
令X1 = X2 =0 X0 =(0, 0, 8, 12, 36)T
Z0 =0——初始可行解，简称初始解
基本概念
• 条典、典式 • 检验数
条典、典式
（1）基本可行解X0对应的可行基是一个m(=3） 阶单位阵。 （2）目标方程中所有基变量X3 ，X4 ，X5 的系 数全都为0。
第2章 单纯形法
美国著名的运筹学家丹茨格 1947年提出的.
X2
(0,6) D
C
(4,6)
X0 =(0, 0, 8, 12, 36)T
X1 =(0, 6, 8, 0, 12)T
B
(8,3)
(0,0)0
A
X1
X2 =(4, 6, 4, 0, 0)T
单纯形法的解题思路
初始基本可行解
是否最优解或 无限最优解?
min
j<0
j
=
k
若出现两个或更多个 j<0同时达到
最小，而相持不下时，任选一个作为进基。
2.4.2 离基变量的相持及其突破----退化情形
2.4.2 离基变量的相持及其突破----退化情形
目标函数 Max z =3x1+5x2
约束条件
s.t.
x1 + x3
=8
2x2 +x4
=12
3x1 +4x2
这两个条件简称为条典，把满足条典的线性 方程组称为典式（方程组）。
检验数
当目标方程中基变量系数全为0时，非基 变量的系数可以作为检验当前的基本可 行解是否最优的标志，称之为检验数。
(2)、判定解是否最优
Z-3X1-5X2 =0 当X1从0↗或X2从0↗ Z从0↗
∴ X0 不是最优解
(3)、由一个基可行解→另一个基可行解。
=8 ①
2X2 + X4
=12 ②
3X1+ 4X2
X5 =36 ③
概念 ：主元，换基运算，迭代P54（从一个
基本可行解转换到另一个基本可行解）
接下来要让进基变量X2的系数列向量变为单位向量 具体做法： （１）主元素所在行的所有元素都除以主元素 （２）主元素所在列要变为单位向量,方法是采用
行变换,即将主元素行的某个倍数加到另一行上去。
2.4.3 多重最优解
判定LP模型是否有多重最优解是必要的。 如何判定LP模型是否有多重最优解？ 如何找到？
(1)、例 maxZ=X1 +2X2
X1 4 X2 3 X1+2X2 8 X1 , X2 0
X1 +X3
=4
X2
+X4
=3
X1+2X2
+X5 = 8
X1 … X5 0
此时可以确定X5为离基变量
Z
+1/2X4 +X5 =42
X3 +2/3X4 -1/3X5 =4
X2 +1/2X4 =6
X1 -2/3X4+1/3X5=4
令X4 =X5 =0
X =(4, 6, 4, 0, 0)T Z =42
。此时4=1/2, 5=1, Z值不
再增大了,X值是最优基本解
即:X*=(4,6)T,Z*=42
X1
X2
- X5
X1 … X5 0
=100 =120 =14
= 22
maxZ=6X1+4X2-MX6 -MX7
2X1 +3X2 +X3 4X1 +2X2 +X4 X1
=100 =120 +X6 =14
X2
- X5 +X7 = 22
X1 … X7 0
6
4
0
0 0 -M -M
X1
X2
X3
X4
X5
2.2.3 单纯形法计算之例
2-3 人工变量法 (Artificial Variable)
一、人工变量法
在单纯形法中,首先要求找到一个m阶 排列阵,但是往往做不到.如何找到单 位阵？
•目标函数：
Max z = c1x1 + c2x2 + … + cnxn
•约束条件：
a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22...x2 + … + a2nxn = b2 am1x1 + am2x2 + … + amnxn = bm
它与图解法结果一致
X2 2.1.2单纯形法的几何意义
(0,6) D
C
(4,6)
X0 =(0, 0, 8, 12, 36)T
X1 =(0, 6, 8, 0, 12)T
B
(8,3)
(0,0)0
A
X1
X2 =(4, 6, 4, 0, 0)T
2.2单纯形法的计算过程 2.2.1 单纯形表
例： Z=30X1+20X2
3/2
1 X2 5/2
3 X5
1
-1 1 -1
X1
X2
X3
0 -4 0
0
11
1
20
0
2
0
0 -2/3 0
0 -1/3 1
1
2
0
0 2/3 0
1/3 0
0
1/6 0
1
1/2 1 0
-2/3 0 0
0
X4
3 -1 -2 1 14/3 -5/3 -2 1/3
4 -2 -1 1
3
0
X5
X6
-5 0
2
0
0
0
3
16 0 -17 0 4 0
0 X3 6 0 -3 1 1 0 4 X1 4 1 -4 0 1 0 0 X5 4 0 (2) 0 -1 1
50 0 0 0 -9/2 17/2
0 X3 12 0 0 4 X1 12 1 0 1 X2 2 0 1
1 -1/2 3/2 0 -1 2 0 -1/2 1/2
j<0
(2)、决定离基变量：
bi -aikXik 0 ( i=1 ,2 ,…, m)
bi
Xik
aik
(aik>0 )
最小比值θ ( P 55)
bi
bl
θ = min
=
aik
alk
