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

三、基本可行解的几何意义
1、  讨论课堂练习1-2
(1)观察图解法求解图,其中点I、H、G均在第一象限,它们是基本解,但不是基本可行解,这与基本可行解非负性有无矛盾?
(2)如何求得基本解?
第一步模型标准化;
第二步按照基本解的定义
① 找基(非退化3阶方阵)——
多少个?不超过,为什麽?怎麽找?
② 确定基变量和非基变量;
③ 令非基变量为0,解出基变量;
④基变量和相应非基变量搭配构成基本解;
求解结果:
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的一个顶点(也称为极点或角点)。
1、定义“顶点”的方式有什麽特点?
2、这种定义方式在什麽场合运用最方便?
讨论
2、线性规划问题解的性质定理:
定理1-1 线性规划问题的可行解集
(即可行域) 是凸集。
证明思路:根据凸集定义,采用直接法证明;
具体步骤:①从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的正分量所对应的系数列向量线性无关
证明要点:(1)引理: X为LP的基本可行解<=>X的正分量所对应的系数列向量线性无关
必要性→由基本可行解定义直接证得
充分性←正分量K个
k=m →X=(x1,x2,…,xm,0,…0)T即为
基本可行解
k<m →补齐得基→退化的基本可行解
(2)定理1-2 (反证法)