-第部分基本可行解的几何意义.pptVIP

定理1-1证明: 证明： * * 用图解法求解下面的线性规划 按小组分工完成：①画约束条件1,2；?画约束条件3并标明可行域；?画目标函数等值线；?说明如何得到最优解,算出相应的目标函数最优值。其他小组进行讲评。 课堂练习1-3 1 2 3 4 5 x1 X2 5 4 3 2 1 0 (2,2) ? ? ? C=2 C=10 I(4,0) E(0,-2) H(6,4) G(0,4) F(-2,0) ?三、基本可行解的几何意义 1、讨论课堂练习1-3 （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; 1 2 3 4 5 x1 X2 5 4 3 2 1 0 C=2 (2,2) ? ? ? C=10 I(4,0) E(0,-2) H(6,4) G(0,4) F(-2,0) （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满足凸集定义中相应的条件) 在可行域D中任取两点: ， 则有： 设X是X(1)和X(2)连线上的点 则： 根据凸集的定义可知，D是凸集。（证毕） 定理1-2 线性规划几何理论基本定理 若 ， 则X是D的一个顶点的充分必要条件是X为线性规划的基本可行解。 证明思路：定理1-2是X是D的一个顶点= X为LP的基本可行解; 引理是X为LP的基本可行解=X的正分量所对应的系数列向量线性无关; 从而将问题 转化为 X是D的一个顶点 = X的正分量所对应的系数列向量线性无关 证明要点：（1）引理: X为LP