运筹学基本可行解几何意义.pptVIP

课堂练习1-2：用图解法求解下面的线性规划 ;;凸集——设K是n维欧氏空间的一个点集，若任意两点X（1）∈K，X（2）∈K的连线上的一切点： αX（1）+（1-α）X（2） ∈ K （0α1），则称K为凸集。 ; 顶点——设K是凸集，X?K；若X不能用 X（1） ? K，X（2） ? K 的线性组合表示，即 X≠αX（1）+（1-α）X（2） （0α1） 则称X为K的一个顶点（也称为极点或角点）。 ;;;2、线性规划问题解的性质定理： ;;证明要点：（1）引理: X为LP的基本可行解=X的正分量所对应的系数列向量线性无关 必要性→由基本可行解定义直接证得 充分性←正分量K个;必要性→ 第一步：将反证法假设和已知条件具体化； 第二步：寻找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有两个或两个以上最优解，那麽就一定有无穷多个最优解。