0 8 5 1 2 0 4 4 1 2 0 5 2 11
38
改进单纯形法示例1
320 8 -1 b=B b , p1 = B p 1 100 2 320 100 320 min{ , } 8 2 8 新的基变量组合XB ( x1 , x5 )T
-1
39
改进单纯形法示例1
40
你们好
矩阵形式算法示例1
42

例2-10
max Z = 3x1 - 2 x2 - x3 s.t. x1 - 2 x2 + x3 + x4 -4 x1 + x2 + 2 x3 - 2 x1 + x3 x1 , x2 , x3 , x4 , x5 ³ 0 max Z = 3x1 - 2 x2 - x3 - Mx6 - Mx7 s.t. Þ x1 - 2 x2 + x3 + x4 -4 x1 + x2 + 2 x3 - 2 x1 + x3 - x5 + x6 =11 =3 + x7 = 1
第2章
线性规划的单纯形解法
1
单纯形法的扩展

1-目标函数为求最小值的问题
2
单纯形法的扩展

1-目标函数为求最小值的问题
3
单纯形法扩展的示例1

例2-8
Z = 3x1 + 5x2 x1 £4 x2 £ 6 3x1 + 2 x2 £ 18 x1 , x2 ³ 0
min W 3x1 5 x2 s.t. x1 4 x2 6 3x1 2 x2 18 x1 , x2 0
10
=11 - x5 =3 =1
x1 , x2 , x3 , x4 , x5 , x6 , x7 ³ 0
大M法示例1
11
单纯形法的扩展

2.2- 人工变量法之两阶段法
12
两阶段法示例1

例2.12
max Z = 3x1 - 2 x2 - x3 s.t. x1 - 2 x2 + x3 + x4 -4 x1 + x2 + 2 x3 - 2 x1 + x3 x1 , x2 , x3 , x4 , x5 ³ 0 min W = x6 + x7 s.t. Þ x1 - 2 x2 + x3 + x4 -4 x1 + x2 + 2 x3 - 2 x1 + x3 - x5 + x6 =11 =3 + x7 = 1
21
改进单纯形法

单纯形表法 示意
22
改进单纯形法

单纯形表法 示意
23
改进单纯形法

单纯形表法 示意
24
改进单纯形法

2- 单纯形法迭代计算的矩阵形式算法描述
定义CN = CN - CB B-1 N为非基变量XN的检验向量 Z CB B-1b + CN XN
25
改进单纯形法

2-单纯形法迭代计算的矩阵形式算法描述
20
改进单纯形法

1- 标准单纯形法的矩阵形式算法描述

一般性基变量组合对应的检验数
XB AX = (B, N) = b BX B + NX N = b XN XB + B -1 NX N = B -1b XB = B -1b - B -1 NX N XB Z = CX = (CB ,CN ) = CB X B + C N X N XN = CB (B -1b - B -1 NX N ) + CN X N = CB B-1b + (CN - CB B -1 N)X N

17
化示例1
19
改进单纯形法

1- 标准单纯形法的矩阵形式算法描述

最优基变量组合对应的解和目标函数
XB AX = (B, N) = b BXB + NX N = b XN XB + B-1 NXN = B -1b 令非基变量XN = 0 XB = B -1b B-1b -1 Z = CX = (CB ,CN ) = C B b B 0
max Z 3x1 2 x2 x3 x1 2 x2 x3 x4 s.t. 4 x1 x2 2 x3 2 x1 x3 x1 , x2 , x3 , x4 , x5 0
7
max Z 3x1 2 x2 x3 x1 2 x2 x3 11 s.t. 4 x1 x2 2 x3 3 2 x1 x3 1 x1 , x2 , x3 0
初始基变量组合XB ( x4 , x5 )
T
s.t.
8 x1 4 x2 5 x3 x4 2 x1 2 x2 x3 x1 , x2 , x3 , x4 , x5 0
320 x5 100
1 0 -1 B (p 3 ,p 4 ) B 0 1 1 -1 c1 c1 CB B p1 5 (0, 0) 0 1 -1 c2 c2 CB B p 2 4 (0, 0) 0 1 -1 c3 c3 CB B p 3 2 (0, 0) 0
max s.t .
4
单纯形法扩展的示例1
min W 3x1 5 x2 x1 x3 s.t. x2 3x1 2 x2 x1 , x2 , x3 , x4 , x5 0 x4 4 6 x5 18
5
单纯形法扩展的示例1
6
单纯形法的扩展

2-人工变量法

对于约束条件包含等式约束或“≥”约束的线性规 划问题，标准形式不存在现成的初始可行基，无法 直接应用单纯形表法。
13
=11 - x5 =3 =1
x1 , x2 , x3 , x4 , x5 , x6 , x7 ³ 0
两阶段法示例1
14
两阶段法示例1
15
两阶段法示例1
16
单纯形法的扩展

3- 退化与循环

应用最小比值准则时可能会出现两个以上相等的最 小比值，这时应选择最小比值所对应的任意一个基 变量作为出基变量，而其他未被选择的基变量在下 一个基本可行解中仍然为基变量。 下一轮基本可行解中会出现有基变量的取值为零的 情况。这种现象称之为退化，而这时得到的基本解 称为退化解。
26
改进单纯形法

2-单纯形法迭代计算的矩阵形式算法描述
27
矩阵形式算法示例1
28
矩阵形式算法示例1
29
矩阵形式算法示例1
30
矩阵形式算法示例1
31
矩阵形式算法示例1
32
矩阵形式算法示例1
33
矩阵形式算法示例1
34
矩阵形式算法示例1
35
改进单纯形法

2- 改进单纯形法计算步骤
36
=11 x5 =3 1
单纯形法的扩展

2.1 -人工变量法之大M法
8
单纯形法的扩展

2.1-人工变量法之大M法
判定定理


1-当人工问题的最优解中不包含非零的人工变量时 ，人工问题的最优解就是原始问题的最优解。 2-当人工问题的最优解中包含有非零的人工变量时 ，原始问题无可行解。

9
大M法示例1
改进单纯形法示例1

例2-14
max Z 5 x1 4 x2 2 x3 s.t. 8 x1 4 x2 5 x3 x4 2 x1 2 x2 x3 x1 , x2 , x3 , x4 , x5 0 320 x5 100
37
改进单纯形法示例1
max Z 5 x1 4 x2 2 x3