因而 的取值可无限增大不受限制， z(1) 也可无限增大,表明线性
规划问题有无界解。
二、单纯形法的矩阵描述
在线性规划问题的标准型：
Max z CT X
s.t.

AX X
b 0
中，不妨设 B ( p1, p2 , , pm ) 是一个可行基，则系数矩阵Ａ可分块为
（Ｂ，Ｎ）。对应于Ｂ的基变量
基：A中任何一组m个线性无关的列向量构 成的子矩阵,称为该问题的一个基（basis）,
与中的这些列向量对应的变量称为基变量 （basic variable）
基本解：对于基,令非基变量为零,求得满足 （1-13）的解，称为基对应的基本解（basic solution）。
基本可行解：满足（1-14）的基本解 称为基本可行解（basic feasible solution）；基本可行解所对应的基称 为可行基（feasible basis）。
为，X B (x1, x2 , , xm )T 为 X N (xm1, xm2 , , xn )T
，非基变量 ，Ｎ
＝ ( pm1, pm2 , , pn )
。并令C T

(C
T B
,
C
T N
)
，其
中 B 为基变量X B的系数列向量，N 为
非基变量的系数列向量。于是原问题可化
为
Max
0

x
0 l
a lj
由（1-22）式得
（1-22）
xi0
aij

0 0
(i l) (i l)
（1-23）
故 X (1) 是一个可行解
3、最优性检验和解的判别
将基本可行解 X (0) 和 X (1) 分别代入目标函数得
m
z (0) ci xi0 i 1 m
， y2 y1
。
M2x2, y2
Mx, y
即

x y


a
x1 y1


(1

a)
x2 y2

M x1, y1
o
当 a [0,1] 时,上式表示以 M1, M2 为端点的线 段的点集。若 X (1) , X 表示 (2) n 维空间中的 两个点,则 X aX(1) (1 a)X (2) a[0,1] X 表示 X (1) , X (2) 两点的线性组合,几何上 仍表示一个点。
❖ 最优解：若基本可行解又是最优解（也 称基本最优解），这个基就称为最优基 （optimal basis）。
二.解的性质
在右图中设线段长度与之比为，由此得x2 x a y2 y a
x ax 1 (1 a ) x 2
所以

y

ay 1

(1

a)
y2
x2 x1
§1-4.线性规划问题的解
❖ 一.解的基本概念
对于标准型LP问题 max（或 min） z CT X
(1 12)
s.t.
AX b X 0
(1 13) (1 14)
设 A 是mn阶矩阵,mn,且 A 的秩为 m。
可行解：满足约束条件（1-13）和（1-14） 的解称为可行解。
“-M”称为“罚因子”，即只要人工变量取值大于零，目 标函数就不可能实现最优。因而添加人工变量后，例110的数学模型的标准形式就变为
max z 3x1 x3 0x4 0x5 Mx6 Mx7
x1 x2 x3 x4
4
s.t.


2x1

x2

x3

3x2 x3
一个数学符号一起参加运算。检验数中含M符号的项，当
M的系数为正时，该检验数为正，当M的系数为负时，该
项检验数为负。
例1-10添加人工变量后，用单纯形法求解的过程见下页 表1-8。最优解为：
(x1, x2 , x3 )T (0,5 2,3 2)T
凸集：在点集 S 上,对任何两点 X (1) , X (2) ,若
X aX (1) (1 a) X (2) S a [0,1]
称 S 为一凸集（convex set）。即凸集上任 何两点所连线必在凸集上。二维空间中三 角形域、矩形域、圆形域都是凸集,而环形 域就不是凸集；三维空间的椭球体、平行 六面体也是凸集。 极点：在凸集 S 上,若点 X 不能用相异两点 X (1) , X (2) 线性表示为 X aX (1) (1 a) X (2) a (0,1) 称 X 为 S 的极点（Extreme Point）或顶点。 这也就是说极点不是 S 上任何线段的内点。 比如三角形的顶点，圆周上的点均为极点。
z(1) ci xi0 aij c j
i 1

m i1
ci xi0
cj

m i1
ci
aij


z(0)

c j

m i1
ci aij

(1 24)
m
❖ （1-24）式中因 0, 所以只要[Cj ciaij ] 0 ,就 i1 m
§1-6 .初始可行基的求法
一、 大M法
在上一节例1-9中，化为标准形式后约束 条件的系数矩阵中含有单位矩阵，以此作 初始基，使求初始基可行解和建立初始单 纯形表都十分方便。但时常化为标准形后 的约束条件的系数矩阵中不存在单位矩 例1-10 用单纯形法求解线性规划问题
Max z 3x1 x3
x1 x2 x3 4
s.t.


2x1
x2 3x2

x3 x3
1 9
x1, x2, x3 0
解 先将其化成标准形有
Max z 3x1 x3 0x4 0x5

s.t.



x1 x2 x3 x4 4
2x1 x2 x3 x5 1
j 1


n
pjxj b
j 1
xj 0( j 1, , n)
(1-17)
(1 18) (1 19)
在约束条件（1-18）式的变量的系数矩阵中总 会存在一个单位矩阵，不妨设为
1 0
p1, p2 ,
,
pm
0
1

0 0
0
0 (1-20)
综上所述,我们在理论上得到了线性规划问题的以 下结论：
❖ 线性规划问题的可行域是一凸集（包括有界凸集 和无界凸集）；线性规划问题的每个基本可行解 对应着可行域的一个极点（顶点）；若线性规划 问题有最优解,必在可行域的某一极点上得到。 由此可见,我们只需在基本可行解中寻求最优解。 如何有效地寻求最优解,这就是下节要介绍的单 纯形法。
3x2 x3
9
x15 0
(1 33) (1 34) (1 35)
这种情况下，可以通过添加两列单位向量，使连同 约束条件中的向量构成单位矩阵。
p4 p6 p7
1 0 0 0 1 0 0 0 1
p6 , p7是人为添加上去的，它相当于在上述问题的约
束条件（1-34）中添加变量，约束条件(1-35)中添加变 量，变量相应称为人工变量。由于约束条件（1-34） （1-35）在添加人工变量前已是等式为使这些等式得到 满足，因此在最优解中人工变量取值必须为零。为此， 令目标函数中人工变量的系数为任意大的负值，用“M”代表。
其中 是 X(1) 的第 j 个坐标的值。要使 X (1) 是一个基本可行解，
因规定 >0，故应对所有 i=1,…,m，存在
x
0 i

a ij

0
（1-21）
令这 m 个不等式中至少有一个等号成立。因为当 aij 0 时,
上式显然成立,故可令


min

x
0 i
a ij
a ij
（2）当所有的 j 0 ,又对某个非基变量 x j 有 j 0 ,且可以找到
0,这表明可能找到另一顶点（基可行解）目标函数值也达到最大
由于该两点连线上的点也属可行域内的点,且目标函数值相等,即该 线性规划问题有无穷多最优解。反之,当所有非基变量的 j 0 时,线 性规划问题具有唯一最优解。 （3）如果所有的 j 0 不满足，说明还有比 X(0) 更好的基本解， 此时可用换基迭代得到比 X(0) 更好且与 X(0) 相临的基本可行解 X(1)。 （4） 如果存在某个, j 0 且 p j 0 ,对任意的0,均有 x0i aij 0,
线性规划问题的几个定理
定理1-1 线性规划问题的可行域是凸集。
定理1-2 A为线性规划问题可行域的极 点的充要条件是的A正分量对应的系数 列向量线性无关。（证明从略）。 定理1-3A是可行域的极点的充要条件是它 为基本可行解。（证明从略。） 定理1-4 线性规划问题有可行解,必有基本
可行解；有最优解,必有基本最优解。
，
C
CBT B1A
，
则又有
Z

C
T B
B
1b
+NXN
=
C
T B
B
1b
+
X
三、单纯形法的计算步骤
根据上节中讲述的原理,单纯形法的计算步骤如下： 第一步：求初始基本可行解,列出初始单纯形表。
第二步：最优性检验。 第三步：从一个基本可行解转换到相邻的目标函
数值更大的基本可行解，列出新的单纯形表。 第四步：重复第二、三两步，一直到计算结束为止。
Z

C
T B
B
1b

(C