三、基本可行解的几何意义
?1,讨论课堂练习 1-2
?（ 1） 观察图解法求解图, 其中点 I、
H,G均在第一象限, 它们是基本解,
但不是基本可行解, 这与基本可行
解非负性有无矛盾？
?（ 2） 如何求得基本解？
第一步 模型标准化 ；
第二步 按照基本解的定义
① 找基 （ 非退化 3阶方阵 ） ——
多少个？ 不超过, 为什麽？ 怎麽找？
② 确定基变量和非基变量；
③ 令非基变量为 0,解出基变量；
④ 基变量和相应非基变量搭配构成基本解；
3
5C
求解结果：
H(6,4,-6,0,0)T,C(3,1,0,3,0)T,
B(2,2,0,0,2)T,D(2,0,2,4,0)T,
F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,
E(0,-2,6,6,0)T,A(0,1,3,0,3)T,
G(0,4,0,-8,6)T,O(0,0,4,2,2)T
（ 3） 求得的基本解和图解法对照, 找出
相应的点；
2,结论：
(1) 基本解对应所有可行域边界延长线,
坐标轴之间的交点；
(2) 基本可行解对应可行域的顶点 。
1,基本概念：
凸集 —— 设 K是 n维欧氏空间的一个点
集, 若任意两点 X（ 1） ∈ K,X（ 2） ∈ K的
连线上的一切点：
αX（ 1） +（ 1-α） X（ 2） ∈ K
（ 0<α<1）, 则称 K为 凸集 。
四, 线性规划解的性质
凸组合 — — 设 X（ 1）, X（ 2）, …, X（ k） 是 n
维欧氏空间中的 K个点, 若存在 k个数 μ1，
μ2,…, μk,满足
0≤μi≤1,i=1,2,…,k；,
则称 X=μ1X（ 1） +μ2X（ 2） +… +μkX(k)为 X（ 1）,，
X（ 2）, …, X（ k） 的 凸组合 。
顶点 —— 设 K是凸集, X?K；若 X不能用
X（ 1） ?K,X（ 2） ?K 的线性组合表示, 即
X≠αX（ 1） +（ 1-α） X（ 2） （ 0<α<1）
则称 X为 K的一个 顶点 （也称为极点或角点） 。
?
?
?
k
i
i
1
1?
1,定义, 顶点, 的方式有什麽特点？
2,这种定义方式在什麽场合运用最
方便？
讨 论
2,线性规划问题解的性质定理,
?定理 1-1线性规划问题的可行解集
（ 即可行域 ） 是凸集 。
??
?
?
?
??
?
?
?
??? ?
?
n
j
jjj xbxPXD
1
0,
证明思路, 根据凸集定义, 采用直接法证明；
具体步骤,① 从 D中任取两个不同的点,
应满足 可行解定义中相应的条件；
② 证明 X=αX(1)+(1-α)X(2)∈ D
(利用 ①, 证明 X满足凸集定义中相应的条件 )
?定理 1-2线性规划几何理论基本定理
若,
则 X是 D的一个顶点的充分必要条件是 X为线
性规 划的基本可行解 。
证明思路, 定理 1-2是 X是 D的一个顶点 <=> X为 LP的
基本可行解 ; 引理 是 X为 LP的基本可行解 <=>X的正
分量所对应的系数列向量线性无关 ; 从而将问题 转化
为 X是 D的一个顶点 <=>
X的正分量所对应的系数列向量线性无关
??
???
??
??? ??? ?
?
n
j
jjj xbxPXD
1
0,
证明要点,（ 1） 引理, X为 LP的基本可行解
<=>X的正分量所对应的系数列向量线性无关
必要性 → 由基本可行解定义直接证得
充分性 ← 正分量 K个
k=m→X=(x 1,x2,…,xm,0,… 0)T即为
基本可行解
k<m→ 补齐得基 → 退化的基本可行解
（ 2）定理 1-2（反证法）
必要性 →
第一步,将反证法假设和已知条件具体化；
第二步,寻找 X附近的属于 D的两个点 X（ 1）
和 X（ 2） （技巧：将第一步得到的两个式子
相加减得到） ；
第三步,选取适当的 λ，可保证
X=1/2X（ 1） +1/2X（ 2）,
从而与,X是顶点, 矛盾 。
充分性 ←
第一步,将反证法假设具体化, 明确正
分量；
第二步,由 大前提 X是可行解,找出不全
为 0的一组数；
第三步,得到 P1,P2,…, Pm线性相关的
结论, 与已知条件矛盾；
定理 1-3 若可行域非空有界, 则线性规
划问题的目标函数一定可以在可行域
的顶点上达到最优值 。
证明思路：
首先可行域非空有界就肯定有最优解
本定理要证明的是 设在非顶点 X处取得最优
值, 则存在顶点 X（ 1） 和 X（ 2） 也取得相同的
最优值 。
定理 1-4 若目标函数在 k个点处达到最
优值 （ k≥2）,则在这些顶点的凸组合
上也达到最优值,
证明思路,根据凸组合的定义直接证
得结论 。
课后小组讨论 2：
（ 1） 读懂证明, 理清思路, 写出从最罗
嗦的证明过渡到最简洁的证明过程
（ 加上边注 —— 段落大意 ）
可以作为小实践选题 ！
（ 2） P70习题 1-4（ ① 检查是否属于可行
域； ② 检查相应的 Pj是否线性相关 ）
上述 4个定理的一些有意义的启示：
?LP的可行域一定是凸集, 但是凸集不
一定成为 LP的可行域, 而非凸集一定
不会是 LP的可行域 。
（ 为什麽？ 能举例说明吗？ ）
?线性规划的基本可行解和可行域的顶
点是一一对应的 （ 类似于坐标与点的对
应关系 ！ ）
? 在可行域中寻找 LP的最优解可以
转化为只在可行域的顶点中找, 从而
把一个无限的问题转化为一个有限的
问题 。
? 若已知一个 LP有两个或两个以上
最优解, 那麽就一定有无穷多个最优
解 。
?1,讨论课堂练习 1-2
?（ 1） 观察图解法求解图, 其中点 I、
H,G均在第一象限, 它们是基本解,
但不是基本可行解, 这与基本可行
解非负性有无矛盾？
?（ 2） 如何求得基本解？
第一步 模型标准化 ；
第二步 按照基本解的定义
① 找基 （ 非退化 3阶方阵 ） ——
多少个？ 不超过, 为什麽？ 怎麽找？
② 确定基变量和非基变量；
③ 令非基变量为 0,解出基变量；
④ 基变量和相应非基变量搭配构成基本解；
3
5C
求解结果：
H(6,4,-6,0,0)T,C(3,1,0,3,0)T,
B(2,2,0,0,2)T,D(2,0,2,4,0)T,
F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,
E(0,-2,6,6,0)T,A(0,1,3,0,3)T,
G(0,4,0,-8,6)T,O(0,0,4,2,2)T
（ 3） 求得的基本解和图解法对照, 找出
相应的点；
2,结论：
(1) 基本解对应所有可行域边界延长线,
坐标轴之间的交点；
(2) 基本可行解对应可行域的顶点 。
1,基本概念：
凸集 —— 设 K是 n维欧氏空间的一个点
集, 若任意两点 X（ 1） ∈ K,X（ 2） ∈ K的
连线上的一切点：
αX（ 1） +（ 1-α） X（ 2） ∈ K
（ 0<α<1）, 则称 K为 凸集 。
四, 线性规划解的性质
凸组合 — — 设 X（ 1）, X（ 2）, …, X（ k） 是 n
维欧氏空间中的 K个点, 若存在 k个数 μ1，
μ2,…, μk,满足
0≤μi≤1,i=1,2,…,k；,
则称 X=μ1X（ 1） +μ2X（ 2） +… +μkX(k)为 X（ 1）,，
X（ 2）, …, X（ k） 的 凸组合 。
顶点 —— 设 K是凸集, X?K；若 X不能用
X（ 1） ?K,X（ 2） ?K 的线性组合表示, 即
X≠αX（ 1） +（ 1-α） X（ 2） （ 0<α<1）
则称 X为 K的一个 顶点 （也称为极点或角点） 。
?
?
?
k
i
i
1
1?
1,定义, 顶点, 的方式有什麽特点？
2,这种定义方式在什麽场合运用最
方便？
讨 论
2,线性规划问题解的性质定理,
?定理 1-1线性规划问题的可行解集
（ 即可行域 ） 是凸集 。
??
?
?
?
??
?
?
?
??? ?
?
n
j
jjj xbxPXD
1
0,
证明思路, 根据凸集定义, 采用直接法证明；
具体步骤,① 从 D中任取两个不同的点,
应满足 可行解定义中相应的条件；
② 证明 X=αX(1)+(1-α)X(2)∈ D
(利用 ①, 证明 X满足凸集定义中相应的条件 )
?定理 1-2线性规划几何理论基本定理
若,
则 X是 D的一个顶点的充分必要条件是 X为线
性规 划的基本可行解 。
证明思路, 定理 1-2是 X是 D的一个顶点 <=> X为 LP的
基本可行解 ; 引理 是 X为 LP的基本可行解 <=>X的正
分量所对应的系数列向量线性无关 ; 从而将问题 转化
为 X是 D的一个顶点 <=>
X的正分量所对应的系数列向量线性无关
??
???
??
??? ??? ?
?
n
j
jjj xbxPXD
1
0,
证明要点,（ 1） 引理, X为 LP的基本可行解
<=>X的正分量所对应的系数列向量线性无关
必要性 → 由基本可行解定义直接证得
充分性 ← 正分量 K个
k=m→X=(x 1,x2,…,xm,0,… 0)T即为
基本可行解
k<m→ 补齐得基 → 退化的基本可行解
（ 2）定理 1-2（反证法）
必要性 →
第一步,将反证法假设和已知条件具体化；
第二步,寻找 X附近的属于 D的两个点 X（ 1）
和 X（ 2） （技巧：将第一步得到的两个式子
相加减得到） ；
第三步,选取适当的 λ，可保证
X=1/2X（ 1） +1/2X（ 2）,
从而与,X是顶点, 矛盾 。
充分性 ←
第一步,将反证法假设具体化, 明确正
分量；
第二步,由 大前提 X是可行解,找出不全
为 0的一组数；
第三步,得到 P1,P2,…, Pm线性相关的
结论, 与已知条件矛盾；
定理 1-3 若可行域非空有界, 则线性规
划问题的目标函数一定可以在可行域
的顶点上达到最优值 。
证明思路：
首先可行域非空有界就肯定有最优解
本定理要证明的是 设在非顶点 X处取得最优
值, 则存在顶点 X（ 1） 和 X（ 2） 也取得相同的
最优值 。
定理 1-4 若目标函数在 k个点处达到最
优值 （ k≥2）,则在这些顶点的凸组合
上也达到最优值,
证明思路,根据凸组合的定义直接证
得结论 。
课后小组讨论 2：
（ 1） 读懂证明, 理清思路, 写出从最罗
嗦的证明过渡到最简洁的证明过程
（ 加上边注 —— 段落大意 ）
可以作为小实践选题 ！
（ 2） P70习题 1-4（ ① 检查是否属于可行
域； ② 检查相应的 Pj是否线性相关 ）
上述 4个定理的一些有意义的启示：
?LP的可行域一定是凸集, 但是凸集不
一定成为 LP的可行域, 而非凸集一定
不会是 LP的可行域 。
（ 为什麽？ 能举例说明吗？ ）
?线性规划的基本可行解和可行域的顶
点是一一对应的 （ 类似于坐标与点的对
应关系 ！ ）
? 在可行域中寻找 LP的最优解可以
转化为只在可行域的顶点中找, 从而
把一个无限的问题转化为一个有限的
问题 。
? 若已知一个 LP有两个或两个以上
最优解, 那麽就一定有无穷多个最优
解 。
