运筹学 单纯形法的进一步讨论

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

1

第五节 单纯形法的进一步讨论◆人工变量法 ◆关于解的判别 ◆单纯形法小结

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

2

一、人工变量法当线性规划的系数矩阵中不含单位矩阵 怎么办？ 时，怎么办？ 可以人为的添加变量，来构造单位矩阵。 可以人为的添加变量，来构造单位矩阵。 通过添加人工变量构造单位矩阵的方法， 通过添加人工变量构造单位矩阵的方法， 称为人工变量法。 1. 当约束条件是 时，添加人工变量。 当约束条件是=时 添加人工变量。 2. 当约束条件是 时，可以先添加一剩余变量 当约束条件是≥时 实质为松弛变量),然后再添加人工变量。 ),然后再添加人工变量 (实质为松弛变量),然后再添加人工变量。

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

3

◆大M法 法人工变量价值系数为“ 人工变量价值系数为“-M”, M为一个 ， 为一个 任意大的正数。 任意大的正数。 原因：人工变量必须为0, 原因：人工变量必须为 ，这样当人工变 量不为0时 目标函数就不能极大化。 量不为 时，目标函数就不能极大化。

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

4

例1.9:解线性规划问题 1.9: 目标函数 ： 约束条件： 约束条件：

min f = 2 x1 + 3 x 2

x1 + x 2 ≥ 350,x1 ≥ 125, 2 x1 + x 2 ≤ 600, x1 ≥ 0, x 2 ≥ 0.

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

5max z = 2 x1 3 x 2 Mx 6 Mx 7 s .t . x1 + x 2 x 3 + x 6 = 350 , x1 x 4 + x 7 = 125 ,2 x1 + x 2 + x 5 = 600 , x1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ≥ 0

用单纯性表格解该线性规划迭代

xB cB次数

x1-2

x2-3 1 0 1

x30 -1 0 0

x40 0 -1 0 -M

x50 0 0 1 0

x6-M 1 0 0 0

x7bi-M 0 1 0 0

θi

x 6 -M

1 1 2

350 350/1 125 125/1 600 600/2 475M管理工程学院5

0

x 7 -M x50

σ

-2+2M -3+M -M

2010年8月

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》迭代

6x1-2

xB cB次数

x2-3 1 0 1

x30 -1 0 0

x40 0 -1 0 -M 1 -1 2 M-22010年8月

x50 0 0 1 0 0 0 1 0

x6-M 1 0 0 0 1 0 0 0

x7 bi-M 0 1 0 0 -1 1 -1 350 125 600 475M 225 125 325

θi350/1 125/1 600/2

x6

-M -M 0j

1 1 2

0

x7 x5

σ

-2+2M -3+M -M 0 1 1 0 1 0 1 -3+M -1 0 0 -M

x 6 -M

225/1 -----350/2

1

x1 x5

-2 0j

σ

2-2M 225M管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》x6-M -2 0j

70 1 1 0 0 1 0

1

x1 x5

σ

注： 由于 为任意大数， 由于M为任意大数 为任意大数， 1 x2 和 x5 的检验数可以认为是 -1 1 0 1 -1 225 225/1 0 一样大，这时最好选决策变 0 -1 0 0 1 125 一样大， -----1 量入基，而不是松弛、剩余 0 2 1 0 350 量入基，而不是松弛、 -1 -3+M 和人工变量入基。 0 -M M-2 0 2-2M 225M 350/2 和人工变量入基。1/2 1/2 1/2 -1 0 0 -M -2 1 1 -4 0 0 1 0 0 0 1 02010年8月

x 6 -M

-1/2 1/2 1/2 ½ M+1 -1 1 1 -1

1 0 0 0 2 -1 -1 -M+4

0 0 -1 -M 0 0 -1 -M

50 300 175

50*2 300*2 175*2

2

x1 x4

-2 0j

σx2

0 ½ M-2 -3 -2 0 0 1 0 0 1 0 0 0

50M+600 100 250 125 800管理工程学院7

3

x1 x4

σ

j

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

8

所有的检验数都小于等于0,而且人工变量都已出基， 所有的检验数都小于等于 ，而且人工变量都已出基，已找到 最优解。 最优解。 最优解为： 最优解为：( x1 , x 2 , s1 , s 2 , s 3 , a 1 , a 2 ) = (250,100,0,125,0,0,0 ) .T T

最优目标函数值为： 最优目标函数值为：min f = max z = 800.

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

9

例1.10:用单纯形法求解线性规划问题 ：(1.28a) (1.28b) (1.28c) (1.28d) (1.28e)

解：在(1.28b)中添加松弛变量，在(1.28c)中添加剩余变 量，再添加人工变量，在(1.28d)中添加人工变量。得线 性规划(1.28)可相应表示为：

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

10

用单纯形法求解过程如下：

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

11 -3 0 1 0 0 -M x1 x2 x3 x4 x5 x6 1 1 1 1 0 0 -2 [ 1 ] -1 0 -1 1 0 3 1 0 0 0 -2M-3 4M 1 0 -M 0 3 0 2 1 1 -1 -2 1 -1 0 -1 1 [6] 0 4 0 3 -36M-3 0 4M+1 02010年8月

cj→ CB 基 0 x4 -M x6 -M x7 cj- zj 0 x4 0 x2 -M x7 cj- zj

b 4 1 9 3 1 6

-M x7 0 0 1 0 0 0 1

3M -4M 0 表1-6管理工程学院11

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

12 -0 x1 0 0 1 0 x2 0 1 0 0 0 0 0 -1/2 1 3/2 0-3/2 0

cj→ CB 基 b 0 x4 0 0 x2 3 -3 x1 1 cj- zj 0 x4 0 0 x2 5/2 1 x3 3/2 cj- zj

1 x3 0 1/3 [2/3] 3 0 0 1

0 x4 1 0 0 0 1 0 0

0 x5 -1/2 0 1/2 3/2 -1/2 -1/4 3/4

-M -M x6 x7 -1/2 -1/2 0 1/3 -1/2 1/6 -M-3/2 -M+1/2 -1/2 -1/2 1/4 1/4 -3/4 1/4

0 0 表1-6续2010年8月

-3/4 -M+3/4 -M-1/4管理工程学院12

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

13

注意：计算时当人工变量出基后不可能再入基， 注意：计算时当人工变量出基后不可能再入基，则此变量对应的列下面的数值不用再计算(划红线部分)。 变量对应的列下面的数值不用再计算(划红线部分)。

区别：大M法中的松弛变量与人工变量 区别： 法中的松弛变量与人工变量

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

14

◆两阶段法用计算机求解时，由于参数值和M取值 用计算机求解时，由于参数值和 取值 上的误差，可能使计算结果发生错误。 上的误差，可能使计算结果发生错误。所以 我们介绍两阶段法。 我们介绍两阶段法。

2010年8月

管理工程学院

运筹学 单纯形法的进一步讨论

《运筹学》 运筹学》

15

阶段1 阶段1:构造目标函数只包含人工变量的线性规划问题。即令目标函数中其他变量系数取零， 划问题。即令目标函数中其他变量系数取零，人 工变量的价值系数取1,目标函数求极小化， 工变量的价值系数取 ，目标函数求极小化，

约

束条件同上。

阶段2 当阶段1中目标函数值为 中目标 …… 此处隐藏：3019字，全部文档内容请下载后查看。喜欢就下载吧 ……