单纯形法基本原理(8)

x1

2x1 x, 1

x2 x23x2x2,x3

x3 x3 x3 0

4 1 9

首先将其化为标准形式，maxZ 3x1 0x2 x3 0x4 0x5

x1

2x1s.t. x 1~5

x2 x23x2 0

x3 x3 x3

x4

x5

4 1 9

再强行加上人工变量，使其出现单位矩阵：

x1

2x1 x 1~5

x2 x3 x2 x33x2 x3

0

x4

x5 x6

x7

4 1 9

但这样处理后产生两个问题：①不易接受。因为是强行引进，x6,x7称为人工变量。它们与x4,x5不一样。x4,x5称为松弛变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。②人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。

为此，可以把目标函数作如下处理：

maxZ 3x1 0x2 x3 0x4 0x5 Mx6 Mx7

x1

2x1 x 1~5

x2 x3 x2 x33x2 x3

0

x4

x5 x6

x7

4 1 9

其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有：

1 2T

0 3

1130

1 111

1

000

0 100

010 M

001 M

4 1 9 0