其次证明充分性。设X的正分量为x1，x2,…,xk，其对 应的列向量P1,P2,…,Pk线性无关。显然k≤m。
若k=m，则P1,P2,…,Pk可用来构成一个基，所以X是基 本解。而已知X是可行解，故X又是基可行解。
若k<m，由于A的秩为m，比可从A中再挑出m-k个列向 量，与P1,P2,…,Pk ，一起构成一个线性无关极大组，即 为一个基，由此可知X是基可行解。
定义1.7：设集合S是n维欧式空间En中的闭凸 集，d是En中的非零向量。如果对于S的每 个点X，以及一切非负的数λ，都有
X+λd∈S，λ≥0
则称向量d是凸集S的一个方向。如果d1， d2是S的方向，且d1≠αd2， ∀ α>0，则d1， d2是两个不同的方向。
进一步，如果d是凸集S的一个方向，且 不能表示为S的另外两个不同的方向的正组 合，则称d是S的一个极方向。
约定A是行满秩的m行n列矩阵。
2、基、基向量、基变量、基本解、基本可 行解、可行基、最优解、最优基
基：矩阵A中一个m阶非奇异子矩阵 基向量：基的列向量 基变量：基向量对应的变量 基本解：非基变量全为零的解
基本可行解：非基变量为零，基变量都大 于等于零的解
可行基：基可行解对应的基 最优解：基本解中使目标函数最大的解 最优基：最优解对应的基
X=λX（1）+（1-λ）X（2）
上式的分量表达形式为 显然，当j>m时，有
x
j
xj
xj1 xj1x j2
1 0

xj2
,
j

1,
2,
,n
m
再由于X（1），X（2）均是可行点，故可推知 xjiPj b,i 1, 2
两式相减，得
m
x1j
① 最优解存在的充要条件是 Cdj≤0 j=1,2,···,L
② 若存在最优解，则有某个极点是最优解
谢谢欣赏！
d1
(,1 )
d3 S
d4
d2
( x1, x2 )
定理1.1：设集合D={X|AX=b，X≥0}，其中A是行满秩的m行n 列矩阵。那么，集合D是闭凸集。
证明：首先证明D是凸集。任取D中的两个点X1，X2， 以及λ∈[0,1]，则有AXi=b，Xi≥0，i=1,2
A[λ X1 +(1- λ) X2]= λ AX1 +(1- λ)A X2 = λ b+(1- λ) b=b
（1-5） 因 故 在（1-5）式中，令
，则有
表明， ∈D，所以D是闭集。
四、线性规划解的基本定理
定理1.2：设X是标准线性规划问题的可行解。那 么，X是基可行解的充要条件是X的正分量对应的 列向量线性无关。
证明：首先证明必要性。设X是基可行解，那么，由基可 行解的定义，可知其正分量为基变量，对应的列向量都是 基向量，显然线性无关。
j 1
j
j 1
所以
X（1） ∈D
同理
X（2）∈D
注意到λj不全为零，α>0，所以有 X（1）≠ X（2）
但
X=0.5 X（1） +0.5 X（2）
表明X不是D的极点，与已知条件矛盾，故k≤m。
线性规划解的基本定理
定理1.4：对标准形式的线性规划，基可行解与可行 域的极点一一对应。
证明：首先证明极点必是基可行解。设X是极点， 由定理1.3,可设X=(x1,…xk,0,…,0)T xj>0,k≤m
故
j 1
j 1
现构造两个点X（1），X（2），使满足
X（1）=（x1+αλ1,…, xk+αλk ,0,…,0）T X（2）=（x1-αλ1,…, xk-αλk ,0,…,0）T
其中,α是充分小的正数。显然有X（1）≥0，X（2）≥0
且
K
k
k
AX 1 xj j Pj xjPj j Pj b
若X不是基可行解，由定理1.2，向P1,P2,…,Pk应 线性相关。仿照定理1.3的证明过程，可推导出X 不是极点，与已知条件矛盾。故可知X是基可行解。
其次证明基可行解必是极点。设X是基可行解， 由定义，可设其对应的基向量为P1,P2,…,Pm ,于 是，可设X为
X=(x1,…xk，0,…,0)T
若X不是极点，则存在异于X的两个X（1）,X（2）,X（1）≠ X（2） ， 以及数λ∈（0,1），使得
组合 2.当D无界时，必有且只有有限个极方向。设若D有K
个极点X1,X2,…,XK，有L个极方向d1,d2,…,dL，则 D中任一点X可表现为
其中， 反之，满足上述条件的点必是可行点。
线性规划解的基本定理
定理1.5：如果标准线性规划的可行域D有界，则必 有某个极点是最优解。
定理1.6：设线性规划的可行域D无界,X1 X2,…,XK是 全部极点， d1,d2,…,dL是全部极方向，那么有
则称点X是点X1,…,Xm的一个凸组合。 任取一个集合S，那么S中的点的所有凸 组合的集合是一个凸集。
三、极点与极方向
定义1.6：设集合S是凸集，点X是S中的点。 如果对S中的任意两个相异的点X1，X2，以 及开区间(0,1)上的任意数λ，都不可能有：
X= λ X1 +(1- λ ) X2 则称X是凸集S的一个极点。 设若点X， X1，X2均属于凸集S，0≤λ ≤ 1。那么点X成为S的极点的充要条件是： 如果有等式X= λ X1 +(1- λ ) X2成立 则必有X= X1=X2
且
λ X1 +(1- λ) X2 ≥0
所以
λ X1 +(1- λ) X2 ∈D
由凸集的定义知，D是凸集。
其次，可以证明D是闭集。任取D中的收敛序列{Xk}， 设其极限点为 ，则只需要证明 属于D即可。
注意D是线性规划可行域，可等价地表述为
（1-4） 所以Xk的每个分量Xk j，j=1,2，···，n都满足：
线性规划解的基本定理
定理1.3：设X是可行域D的极点，那么，X最多有m 个正分量。
证明：设X=(x1,…,xk，0,…,0)T，若k>m，由于A的秩为
m，则P1,P2,…Pk线性相关，于是存在k个不全为零的数λj，
使得
k
j Pj 0
j 1
因
n xj PjX∈b D k xj Pj b
二、凸集
定义1.4：设集合S∈En，S≠∅。如果任取S中 的两个点X1，X2，以及区间[0，1]中任一个 数λ，都有 λ X1 + (1- λ ) X2 ∈S 则称集合S是凸集。 规定：单点集 {x} 为凸集，空集∅为凸集。
凸集
非凸集
凸组合
定义1.5：设X1,…,Xm为En中的m个点，若存 在m个数λj满足：

x
2 j
Pj
0
j 1
j 1
已知P1,P2,…,Pm线性无关，所以有 xj1 xj2, j 1,2,,m
综合得：
xj1 xj2
与已知条件矛盾，所以X必是极点。
线性规划解的基本定理
推论：线性规划可行域D必有且只有有限个极点。 表现定理：设D是线性规划的可行域，则 1.当D有界时，D中任意一点均可表现为其极点的凸
线性规划的基本定理
本节主要内容
➢ 上节内容回顾 ➢ 凸集 ➢ 极点与极方向 ➢ 线性规划解的基本定理
一、知识点回顾
1、标准形式的线性规划
设集合
max Z CX

L

s.t.

AX b X 0
D={XⅠAX=b,X≥0}
பைடு நூலகம் 则，D是该线性规划的可行域，可行域中 的点为可行解。