设x,x,...,x?K,ti??0,1?,?ti?1,则称
(1)(2)(r)i?1rx?t1x(1)?t2x(2)?...?trx(r)
是x(1),x(2),...,x(r)的凸线性组合。
设K?Rn是凸集，x?K，若x不能表示为K中不同两点的凸线性组合，则称K是凸集的顶点。
§1.2 线性规划的基本定理
定理1. 线性规划的可行域是凸集。
定理2. 设x是线性规划的可行解，则x是基可行解的充要条件是x的正分量所对应的系数列向量线性无关。 证明： 必要性
由基可行解的定义可知。 充分性 若向量p1,p2,...,pk线性无关，则有k?m。当k?m时，它恰好构成线性规划的一个基，从而x?(x1,x2,...,xk,0,...,0)T为相应的基可行解；当k?m时，则一定可以从其余的列向量中取定m?k个与p1,p2,...,pk构成其最大线性无关组，其对应的解恰为x，且x是基可行解。
定理3. 线性规划的基可行解对应于可行域的顶点。
证明：必要性。设x是基可行解，要证明x是可行域的顶点。若x不是可行域的顶点，则必存在可行域中不同的两点x(1)与x(2)及???0,1?，使
x??x(1)?(1??)x(2)
因x是基可行解，不妨设x的前k个分量是正，而其余的为零，这里k?m，因此有
?xpjj?1kj?b
且xk?1?...?xn?0，由x??x(1)?(1??)x(2)，与x(1)，x(2)?0，???0,1?，必可推出
xk?1(i)?...?xn(i)?0,于是有
i?1,2.
4
?xj?1k(1)jpj?b,?xj?1(1)jkj(2)jp?b
上面两式相减，有
?(xj?1k2) ?xj()pj?0而x(1)?x(2)，因此有p1,p2,...,pk线性相关，这与p1,p2,...,pk线性无关矛盾。
充分性。设x是可行域的顶点，要证明x是基可行解。因x是可行域的顶点，不妨设x?(x1,...,xk,0,...,0)T，而x1,...,xk?0，k?n。若x不是基可行解，则由定理1知：p1,p2,...,pk线性相关。因此存在不全为0的数?1,...,?k，使：
??j?1kjpj?0
而
?xpjj?1kj?b
因此有
?(xj?1kj???j)pj?b
因xj?0，取?充分小，必可使xj???j?0。令
x(1)?(x1???1,...,xk???k,0,...,0), x(2)?(x1???1,...,xk???k,0,...,0).
故有
1(1)1(2)x?x。 22这与x是可行域的顶点矛盾。 证毕。 定理4. 若线性规划有可行解，则必有基可行解。
证明：证明是构造性的。设x是可行解，不妨设x的前k个分量大于零，而其余的为零，于是有：
x?x1p1?x2p2?...?xkpk?b
若p1,p2,...,pk线性无关，则x是基可行解。
若p1,p2,...,pk线性相关，则存在不全为零的?1,?2,...,?k使
5
?1p1??2p2?...??kpk?0
不妨设?1,?2,...,?k中至少有一个为正。而x是可行解，于是有?xjpj?b。因此
j?1k有
?(xj?1kj???j)pj?b
令
???xj???min?|?j?0,j?1,...,k?
????j?于是x???是可行解，且x???中至多只有k?1个分量不为0，这里
T。必要时重复这一过程，最后得到的可行解其正分量所对??(?1,...?k,?,0,...,0)n?k应的A中的列线性无关。
证毕。
定理5. 若线性规划有最优解，则必有最优基可行解。
证明：设x为最优解，在定理4证明的基础上补证目标函数值不变即可。 即证
c(x???)?cx或c??0
由xi?0,i?1,...,k,故对充分小??0，必有x????0，从而可知x???是可行解。而x为最优解，故必有
c(x???)?cx
c(x???)?cx
从而有c??0。
证毕。
结论：线性规划的可行域是凸集（有界或无界），它们有有限个顶点。线性规划的每个基可行解对应于可行域的一个顶点。若线性规划有最优解，必在可行域的某个顶点达到最优解。
6
§1.3 线性规划的图解法（变量?2个）
例1．
maxz?2x1?3x2?x1?2x2?8?4x?16?1?4x2?12???x1,x2?0
有唯一解x*?(4,2)T。
例2．
maxz?x1?2x2?x1?2x2?8?4x?16?1?4x2?12??x1,x2?0?
7
有无穷多个解，其解为线段Q2Q3上所有点。 例3．
maxz?x1?x2??x1?x2?1??x1?x2?1 ?x,x?012?
可行域无界，没有最优解。
8