第一章 线性规划
显然xn+I也具有非负约束，即xn+i≥0，这时新的约束条件成为
ai1x1?ai2x2???ainxn?xn?i?bi ai1x1?ai2x2???ainxn?bi xn?i?(ai1x1?ai2x2???ainxn)?bi ai1x1?ai2x2???ainxn?xn?i?bi
当约束条件为 时，类似地令
则同样有xn+i≥0，新的约束条件成为
为了使约束由不等式成为等式而引进的变量xn+i称为“松弛变量(Slack Variable)”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。
例1.6 将以下线性规划问题转化为标准形式
max z= 3x1 -2x2 +x3 s.t.
x1 +2x2 4x1 x1,
-x3 ≤5
(1) (2) (3)
+3x3 ≥8 x2,
x3 ≥0
x1 +x2 +x3 =6
将目标函数转换成极小化，并分别对约束（1）、（2）引进松弛变量x4，x5，得到以下标准形式的线性规划问题
min z’= -3x1 +2x2 s.t.
x1 +2x2 4x1 x1,
-x3
-x3 +x4
=5 =6
+3x3 x2,
-x5 =8
x1 +x2 +x3
x3, x4, x5 ≥0
1.3.3 变量无符号限制的问题
在标准形式中，每一个变量都有非负约束。当一个变量xj没有非负约束时，可以令
其中
xj’≥0，xj”≥0
即用两个非负变量之差来表示一个无符号限制的变量，当xj的符号取决于xj’和xj”的大小。
11
xj=xj’-xj”
第一章 线性规划
例1.7 将以下线性规划问题转化为标准形式
max z= 2x1 -3x2 +x3 s.t.
x1 2x1 +3x2
-x2 +2x3 ≤3
-x3 ≥5
x1 +x2 +x3 =4 x1,x3≥0, x2无符号限制
令z’=-z，引进松弛变量x4，x5≥0，并令
x2=x2'-x2''
min z’= -2x1 +3x2' -3x2'' s.t.
x1 x1
2x1 +3x2' -3x2''
+x2' x2',
x1,
x2'',
-x3 -x3
其中x2'≥0，x2''≥0得到以下等价的标准形式
-x2' +x2'' +2x3 +x4
-x2'' +x3
=3 =4
-x5 =5
x3, x4, x5 ≥0
1.3.4 变量小于等于零的问题
在一些实际问题中，变量不允许为正数，这样的问题也不是标准问题。例如：
min z= s.t.
3x1 2x1 -x1
-5x2 +4x2 -3x2
+x3
+x3 ≤15 +2x3 ≥ 6
x1≥0 x2≤0 x3≥0
3x1 2x1 -x1
+5x'2 -4x'2 +3x'2
+x3
令x2=-x'2，x'2≥0，原问题成为：
min z= s.t.
+x3 ≤15 +2x3 ≥ 6
x4
-x5 x5
= 6 ≥0
x1≥0 x'2≥0 x3≥0
+5x'2 -4x'2 x'2
+x3
然后引进松弛变量x4，x5，成为标准问题：
min z= 3x1 s.t.
题。
12
2x1 -x1 x1
+x3 +x4 x3
=15
+3x'2 +2x3
这样，我们就能够将任何非标准形式的线性规划问题转化为等价的标准形式问
第一章 线性规划
§1.4 线性规划问题的几何解释
对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。 例1.8
max z= x1 +3x2
s.t. x1 +x2 ≤6 -x1 +2x2 ≤8 x1, x2 ≥0
?x?其中满足约束(1)的点X??1?位于坐标平面上直线x1+x2=6
?x2? (1) (2) 靠近原点的一
侧。同样，满足约束(2)的点位于坐标平面上直线 -x1+2x2=8的靠近原点的一侧。而变量x1，x2的非负约束表明满足约束条件的点同时应位于第一象限内。这样，以上几个区域的交集就是满足以上所有约束条件的点的全体。
我们称满足线性规划问题所有约束条件（包括变量非负约束）的向量 X=(x1，x2，?，xn)T
为线性规划的可行解（Feasible Solution），称可行解的集合为可行域（Feasible Region）。
x2 z=463 z=12 z=9 z=6 z=3 z=0 6 5 4 3 2 1 x1 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 图 1.2 例1.8的线性规划问题的可行域如图1.2中阴影部分所示。
为了在图上表示目标函数，令z=z0为某一确定的目标函数值，取一组不同的z0
值，在图上得到一组相应的平行线，称为目标函数等值线。在同一条等值线上的点，
13
第一章 线性规划
相应的可行解的目标函数值相等。在图1.2中，给出了z=0，z=3，z=6，?，z=463等一组目标函数等值线，对于目标函数极大化问题，这一组目标函数等值线沿目标函数增大而平行移动的方向（即目标函数梯度方向）就是目标函数的系数向量C=(c1,c2,?,?,cn)T；对于极小化问题，目标函数则沿-C方向平行移动。
在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是B点，这就是线性规划问题的最优解，这个最优解可以由两直线
x1+ x2=6 -x1+2x2=8
的交点求得
x1?4,3x2?14 3最优解的目标函数值为
41446 z?x1?3x2??3??333为了将以上概念推广到一般情况，我们给出以下定义： 定义1.1 在n维空间中，满足条件
的点集
X=(x1，x2，…，xn)T
称为一个超平面。 定义1.2 满足条件
的点集
X=(x1，x2，…，xn)T
称为n维空间中的一个半空间。
定义1.3 有限个半空间的交集，即同时满足以下条件的非空点集
a11x1+a12x2+…+a1nxn≤（或≥）b1 a21x1+a22x2+…+a2nxn≤（或≥）b2
………
am1x1+am2x2+…+amnxn≤（或≥）bm ai1x1+ai2x2+…+ainxn≤（或≥）bi ai1x1+ai2x2+…+ainxn=bi
称为n维空间中的一个多面体。
运用矩阵记号，n维空间中的多面体也可记为
AX≤（或≥）b
14
第一章 线性规划
每一个变量非负约束xi≥0（i=1，2，?，n）也都是半空间，其相应的超平面就是相应的坐标平面xi=0。
在图1.2中，我们看到，线性规划问题的可行域是一个凸多边形。容易想象，在一般的n维空间中，n个变量，m个约束的线性规划问题的可行域也应具备这一性质。为此我们引进如下的定义。
定义1.4 设S是n维空间中的一个点集。若对任意n维向量X1?S，X2?S，且X1?X2，以及任意实数?（0???1），有
X=?X1+(1-?)X2?S
则称S为n维空间中的一个凸集（Convex Set）。点X称为点X1和X2的凸组合。
以上定义有明显的几何意义，它表示凸集S中的任意两个不相同的点连线上的点（包括这两个端点），都位于凸集S之中。
x1 x2 x1 x2 x1 x2
(a)凸集 x1 (b)凸集 x1 (c)凸集
x2
x1 x2 x2 (f)非凸集
(d)非凸集 (e)非凸集 图1.3
从图1.2还可以看出，线性规划如果有最优解，其最优解必定位于可行域边界的某些点上。在平面多边形中，这些点就是多边形的顶点。在n维空间中，我们称这样的点为极点（Extreme Point）。
在凸集中，不能表为不同点的凸组合的点称为凸集的极点。 定义1.5 设S为一凸集，且X?S，X1?S，X2?S。对于0???1，若
X=?X1+(1-?)X2
则必定有X=X1=X2，则称X为S的一个极点。
运用以上的定义，线性规划的可行域以及最优解有以下性质： 1、若线性规划的可行域非空，则可行域必定为一凸集。 2、若线性规划有最优解，则最优解至少位于一个极点上。
15