单纯形法基本原理(4)

x1 2x2 x3

s.t 2x1 x2

xi 0

10 x4 14(i 1,2,3,4)

引进变量x3,x4称为松弛变量。

⑶ 若约束条件中线性方程式的常数项为负数，则将该线性方程式两端乘以-1，使得常

数项为正数。

⑷ 若变量xl无约束，则引进两个非负变量xl 0,xl 0将xl表示为：xl xl xl 所有的线性规划问题，总可以通过这四步将其化为标准形式，这样便于利用图解法或单纯形法进一步求解。

3 线性规划的图解法

线性规划的图解法是解决两个变量LP问题的一种简单实用的方法。 图解法步骤：

⑴ 根据约束条件画出可行域。

⑵ 根据目标函数Z的表达式画出目标直线Z=0，并表明目标函数增加的方向，即目标函数原点处的梯度方向，可通过求偏导数得到。

⑶ 在可行域中，找符合要求的距离目标直线Z=0的最远或最近点，并求出该点坐标。

例如，解LP问题：maxZ 3x1 x2

x1 2x2 8

s.t x1 6 xi 0

1

i 1,2

3,Zx 1 解：Z 3x1 x2在原点的梯度：Zx

2

所以， Z (3,1)。随着直线x2 3x1沿梯度方向去扫可行域，目标函数Z 3x1 x2中的Z在增加。如：经过点(1,1)时，Z 4.

由此可见，当目标函数沿梯度的方向去扫可行域时，在顶点(6,1)处取得最大值。目标函数的最优值为：maxZ 3 6 1 19.