三、基本可行解的几何意义 1、讨论课堂练习1-2 令(1)观察图解法求解图,其中点 H、G均在第一象限,它们是基解, 但不是基本可行解,这与基本可行 解非负性有无矛盾? (2)如何求得基本解?
三、基本可行解的几何意义 ❖ 1、 讨论课堂练习1-2 ❖ （1）观察图解法求解图，其中点I、 H、G均在第一象限，它们是基本解， 但不是基本可行解，这与基本可行 解非负性有无矛盾？ ❖ （2）如何求得基本解？
第一步模型标准化; 第二步按照基本解的定义 ①找基(非退化3阶方阵) 多少个?不超过C3,为什麽?怎麽找? ②确定基变量和非基变量; ③令非基变量为0,解出基变量; ④基变量和相应非基变量搭配构成基本解
第一步 模型标准化； 第二步 按照基本解的定义 ① 找基（非退化3阶方阵）—— 多少个？不超过 ，为什麽？怎麽找？ ② 确定基变量和非基变量； ③ 令非基变量为0，解出基变量； ④基变量和相应非基变量搭配构成基本解； 3 C5
求解结果: H(6,46,0,0),C(3,1,0,3,0), B(2,2,0,0,2),D(2,0,2,4,0)1, F(-2,0,6,0,4),I(4,0,0,6,2)1, E(0,-2,6,6,0)1,A(0,13,0,3) G(0,4,0,8,6),O(0,0,4,2,2)
求解结果： 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)基本可行解对应可行域的顶点
（3）求得的基本解和图解法对照，找出 相应的点； 2、结论： (1) 基本解对应所有可行域边界延长线、 坐标轴之间的交点； (2) 基本可行解对应可行域的顶点
四、线性规划解的性质 1、基本概念: 凸集—设K是n维欧氏空间的一个点 集,若任意两点X(1)K,X(2)K的 连线上的一切点: aX(1)+(1-0)X(2)∈K (0x1),则称K为凸集
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个数, ●● k 满足 k 0≤1≤1,=1,2,…k;∑x1=1 则称X=1X(D)+2X(2)+…+1X为X() X(2),…,X(k)的凸组合。 顶点—设K是凸集,X∈K;若X不能用 X()∈K,X(2)∈K的线性组合表示即 Xx(1)+(1-a)x(2)(0<a<1)9 则称X为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是凸集，XK；若X不能用 X（1） K，X（2） K 的线性组合表示，即 X≠αX（1）+（1-α）X（2） （0<α<1） 则称X为K的一个顶点（也称为极点或角点）。 = = k i i 1 1
讨论 1、定义“顶点”的方式有什麼特点? 2、这种定义方式在什麼场合运用最 方便?
1、定义“顶点”的方式有什麽特点？ 2、这种定义方式在什麽场合运用最 方便？ 讨 论
2、线性规划问题解的性质定理 定理1-1线性规划问题的可行解集 (即可行域)D={x∑Px=bx20}是凸集 证明思路:根据凸集定义,采用直接法证明 具体步骤:①从D中任取两个不同的点, 应满足可行解定义中相应的条件; ②证明X=aX((1-0)X2∈D (利用①,证明X满足凸集定义中相应的条件)
2、线性规划问题解的性质定理： 定理1-1 线性规划问题的可行解集 （即可行域） 是凸集。 = = = n j j j j D X P x b x 1 , 0 证明思路：根据凸集定义，采用直接法证明； 具体步骤：①从D中任取两个不同的点， 应满足 可行解定义中相应的条件； ②证明X=αX(1)+(1-α)X(2)∈D (利用①，证明X满足凸集定义中相应的条件)
定理1-2线性规划几何理论基本定理 若 D=XP bx.≥0 则X是D的一个顶点的充分必要条件是X为线 性规划的基本可行解。 证明思路:定理12是X是D的一个顶点<>X为LP的 基本可行解;引理是X为LP的基本可行解<X的正 分量所对应的系数列向量线性无关;从而将问题转化 为 X是D的一个顶点≤ X的正分量所对应的系数列向量线性无关
定理1-2 线性规划几何理论基本定理 若 ， 则X是D的一个顶点的充分必要条件是X为线 性规 划的基本可行解。 证明思路：定理1-2是X是D的一个顶点 X为LP的 基本可行解; 引理是X为LP的基本可行解X的正 分量所对应的系数列向量线性无关; 从而将问题 转化 为 X是D的一个顶点 X的正分量所对应的系数列向量线性无关 = = = n j D X Pj x j b x j 1 , 0
证明要点:(1)引理:X为LP的基本可行解 X的正分量所对应的系数列向量线性无关 必要性→由基本可行解定义直接证得 充分性←正分量K个 k=m→X=(x2x2…,xm0,0)为 基本可行解 k<m→补齐得基→退化的基本可行解 (2)定理12(反证法):4
证明要点：（1）引理: X为LP的基本可行解 X的正分量所对应的系数列向量线性无关 必要性→由基本可行解定义直接证得 充分性←正分量K个 k=m →X=(x1,x2,…,xm,0,…0) T即为 基本可行解 k<m →补齐得基→退化的基本可行解 （2）定理1-2 （反证法）
