单纯形法基本原理(7)

0 6

对于A

1 2

5211

1

000

000

1

00

1

15 24

，检验行最大系数为2（尖括号中数字），进基 5 0

变量为x1。利用最小比值原则 min

15245 ,, 4，确定主元行为第二行，主元素为061

6，对应出基变量为x4。中括号里面的数字即为主元素，其所在行为主元行，主元行系数为1的基变量即为出基变量。

具体过程如下：

0

6 A

1 2

5211

1

000

000

1

00

1

051/3

15 0 24 1 1

k2

15 6

0 2

51/31115

4 1 8

1

000

01/600

00

1

15

4 5 0

0 1 k3 k2,k4 2k2 0 0

1

000

01/6 1/6 1/3

00

2/3

/3

1

0

3 1 k3

02

0

51/3

1

000

01/6 1/4 1/3

0032000

1

1/3

15

4 32

8

0

11 1

k1 5k3,k2 k3,k4 k3

033

0

1

000

541/4 1/4 1/4

152 1232 2

1

152

72

32

172

至此，检验行已没有正数，当前解即为最优解。令非基变量x4,x5为0，得到最优解

X2 (

731517T,,,0,0)，最优值为maxZ 。 2222

5 单纯形法的进一步讨论

5.1 人工变量法（大M法）

通常对一个线性规划问题进行标准化以后，约束矩阵会有单位化的可行基出现，可以作为单纯形法的初始可行基。但有些情况则没有现成的初始可行基。人工变量法就是针对标准

形约束条件的系数矩阵中不含单位矩阵的处理方法。

例如LP问题：maxZ 3x1 x3