1-2 第3部分 基本可行解的几何意义

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

j=1

证明思路：根据凸集定义，采用直接法证明； 证明思路：根据凸集定义，采用直接法证明；
具体步骤： 中任取两个不同的点， 具体步骤：①从D中任取两个不同的点， 中任取两个不同的点 可行解定义中相应的条件； 应满足 可行解定义中相应的条件； ②证明X=αX(1)+(1-α)X(2)∈D 证明 (利用①，证明X满足凸集定义中相应的条件 利用① 证明 满足凸集定义中相应的条件 满足凸集定义中相应的条件) 利用
） ） X=1/2X（1）+1/2X（2），
从而与“ 是顶点”矛盾。 从而与“X是顶点”矛盾。
充分性← 充分性← 第一步： 将反证法假设具体化， 第一步 ： 将反证法假设具体化 ， 明确正 分量； 分量； 第二步：由 大前提 是可行解 找出不全 是可行解,找出不全 第二步 ： 大前提X是可行解 为0的一组数； 的一组数； 的一组数 第三步： 得到 1,P2,…， Pm 线性相关的 第三步 ： 得到P ， 结论，与已知条件矛盾； 结论，与已知条件矛盾；
第一步 模型标准化； 模型标准化； 第二步 按照基本解的定义 ① 找基（非退化 阶方阵）—— 找基（非退化3阶方阵 阶方阵） 多少个？不超过 C ，为什麽？怎麽找？ 为什麽？怎麽找？ 多少个？ ② 确定基变量和非基变量； 确定基变量和非基变量； ③ 令非基变量为 ，解出基变量； 令非基变量为0，解出基变量； ④ 基变量和相应非基变量搭配构成基本解 ； 基变量和相应非基变量搭配构成基本解；
֠
定理1 定理1-2 线性规划几何理论基本定理
D = X
若
∑
n
j =1
Pj x
j
= b, x j
≥， 0
的一个顶点的充分必要条件是X为线 则 X是 D的一个顶点的充分必要条件是 为线 是 的一个顶点的充分必要条件是 划的基本可行解。 性规 划的基本可行解。
证明思路：定理1 证明思路：定理1-2是X是D的一个顶点<=> X为LP的 的一个顶点<=> LP的 基本可行解; 引理是 基本可行解 ; 引理 是 X 为 LP的基本可行解 <=>X的正 LP 的基本可行解 的基本可行解<=>X 的正 分量所对应的系数列向量线性无关; 分量所对应的系数列向量线性无关 从而将问题 转化 为 X是D的一个顶点 <=> 是 的一个顶点 X的正分量所对应的系数列向量线性无关 的正分量所对应的系数列向量线性无关
i =1
顶点——设K是凸集，X∈K；若X不能用 顶点 设 是凸集 是凸集， ∈ ； 不能用
） ） X（1） ∈ K，X（2） ∈ K 的线性组合表示，即 的线性组合表示， ，
X≠αX（1）+（1-α）X（2） （0<α<1） <α<1 则称X为K的一个顶点（也称为极点或角点）。 则称 为 的一个顶点（也称为极点或角点） 的一个顶点
1、基本概念： 基本概念： 凸集——设K是n维欧氏空间的一个点 凸集 设 是 维欧氏空间的一个点 ） 若任意两点X ） 集 ， 若任意两点 （ 1） ∈ K， X （ 2） ∈ K的 ， 的 连线上的一切点： 连线上的一切点： αX（1）+（1-α）X（2） ∈ K （0<α<1），则称 为凸集。 ） 则称K为凸集。
可以作为小实践选题！ 可以作为小实践选题！ （ （2）P70习题 1-4（①检查是否属于可行 域；②检查相应的Pj是否线性相关） 检查相应的 是否线性相关）
上述4个定理的一些有意义的启示： 上述4个定理的一些有意义的启示：
☺ LP的可行域一定是凸集，但是凸集不 LP的可行域一定是凸集 的可行域一定是凸集，