x2图1 线性规划图解法

实际上，如果利用图解法解决很多的类似的题目后，我们可以得到以下事实： ①若线性规划问题的可行域存在，则可行域一定是凸集。

②若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个顶点。

4 单纯形法

4.1 单纯形法中的一些基本概念

在一个非齐次线性方程组中，例如：

非其次方程组 6x1

x 1

x1

x2

x3

5x2 2x2 x2

x3

x4

x5

15

24，其增广矩阵为 5

x4x5b

0 A 6

1

521

1

00

000

1

1

15 24 5

称x3,x4,x5为基变量（括号中的数字所对应的变量）。基

变量个数=r(A) r(A) 3。

x3

此方程组的解为 x4

x 5

15245

6x1 x1

5x2 2x2。 x2

其中x1,x2为任意实数。称它们为非基变量，或自由变量。称非基变量x1,x2为0的解

(0,0,15,24,5) 叫基解。如果一个解的每个分量都是非负数，就叫做可行解。如果基解是

T

可行的，就叫基可行解，如X0 (0,0,15,24,5)即为基可行解。基可行解所对应的基称为

可行基，如{x3,x4,x5}即为可行基。

基可行解很重要，可以证明以下定理：

定理1：若线性规划问题存在最优解，则问题的可行域是凸集。

定理2：线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。 定理3：若线性规划问题最优解存在，则最优解一定在可行域顶点处取得。 由此可看出，最优解要在基可行解（可行域顶点）中找。

通过以上分析，我们也可以得到以下几个结论：

（1）线性规划问题的可行域是一个凸集，可行域可能有界，也可能无界，但其顶点数是有限个。

（2）线性规划问题每个基本可行解对应于可行域的一个顶点。

（3）若线性规划问题有最优解，则必可在其可行域的某个（或多个）顶点上达到最优值。

[2]

4.2 单纯形法基本原理

首先说明什么是基变换。

例如，对于LP问题：maxZ 2x1 x2 0x3 0x4 0x5

6x1

x1 x 0 i

5x2 2x2 x2

x3

x4

x5

i 1, ,5

15 24 5

T

当前可行基{x3,x4,x5}所对应的基可行解X0 (0,0,15,24,5)。

这个解显然不是最优。因为，当x1 0,x2 0时是没有现实意义的。相应地，将X0代入目标函数得Z(X0) 0，若让非基变量x1,x2取值从零增加，相应的目标函数值Z也将随之增加。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。

x1前的系数2比x2前的系数1大，再注意到目标函数Z 2x1 x2 0x3 0x4 0x5中，

即x1每增加一个单位对Z的贡献比x2大。故应让x1从非基变量转为基变量，称为进基。这种判断进基变量的方法称为最大系数原则法。

又因为基变量只能有三个，因此必须从原有的基变量x3,x4,x5中选一个离开基转为非基变量，称为出基。谁出基呢？

因为x2是仍留作非基变量的，故仍有x2 0。