资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,上页,下页,返回,课堂练习,1-2,：,用图解法求解下面的线性规划,按小组分工完成：,画约束条件,1,；,画约束条件,2,；,画约束条件,3,；,标明可行域；,目标函数等值线；,说明如何得到最优解，算出相应的目标函数最优值。,其他,6,个小组对应讲评。,第一步,模型标准化,；,第二步,按照基本解的定义,找基（非退化,3,阶方阵）,多少个？不超过 ，为什麽？怎麽找？,确定基变量和非基变量；,令非基变量为,0,，解出基变量；,基变量和相应非基变量搭配构成基本解；,凸集,设,K,是,n,维欧氏空间的一个点集，若任意两点,X,（,1,）,K,，,X,（,2,）,K,的连线上的一切点：,X,（,1,）,+,（,1-,）,X,（,2,）,K,（,01,），则称,K,为,凸集,。,顶点,设,K,是凸集，,X,K,；若,X,不能用,X,（,1,）,K,，,X,（,2,）,K,的线性组合表示，即,XX,（,1,）,+,（,1-,）,X,（,2,）,（,01,）,则称,X,为,K,的一个,顶点,（也称为极点或角点）,。,图解法（练习）,18,16,14,12,10,8,6,4,2,0,|,24681012141618,x,1,x,2,4,x,1,+6,x,2,48,2,x,1,+2,x,2,18,2,x,1,+,x,2,16,可行域,A,B,C,D,E,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=(x,1,x,2,x,m,0,0),T,即为,基本可行解,km,补齐得基退化的基本可行解,（,2,）定理,1-2,（反证法）,必要性,第一步：,将反证法假设和已知条件具体化；,第二步：,寻找,X,附近的属于,D,的两个点,X,（,1,）,和,X,（,2,）,（技巧：将第一步得到的两个式子相加减得到）,；,第三步：,选取适当的,，可保证,X=1/2X,（,1,）,+1/2X,（,2,）,，,从而与“,X,是顶点,”,矛盾,。,充分性,第一步：,将反证法假设具体化，明确正分量；,第二步：,由,大前提,X,是可行解,找出不全为,0,的一组数；,第三步：,得到,P,1,P,2,，,P,m,线性相关的结论，与已知条件矛盾；,定理,1-3,若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值。,证明思路：,首先可行域非空有界就肯定有最优解,本定理要证明的是,设在非顶点,X,处取得最优值，则存在顶点,X,（,1,）,和,X,（,2,）,也取得相同的最优值。,定理,1-4,若目标函数在,k,个点处达到最优值（,k2,）,则在这些顶点的凸组合上也达到最优值,.,证明思路：,根据凸组合的定义直接证得结论。,课后小组讨论,2,：,（,1,）读懂证明，理清思路，写出从最罗嗦的证明过渡到最简洁的证明过程,（加上边注,段落大意）,可以作为小实践选题！,（,2,）,P70,习题,1-4,（,检查是否属于可行域；检查相应的,P,j,是否线性相关,）,上述,4,个定理的一些有意义的启示：,LP,的可行域一定是凸集，但是凸集不一定成为,LP,的可行域，而非凸集一定不会是,LP,的可行域。,（为什麽？能举例说明吗？）,线性规划的基本可行解和可行域的顶点是一一对应的,（类似于坐标与点的对应关系！）,在可行域中寻找,LP,的最优解可以转化为只在可行域的顶点中找，从而,把一个无限的问题转化为一个有限的问题,。,若已知一个,LP,有两个或两个以上最优解，那麽就一定有无穷多个最优解。,
展开阅读全文