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

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