1-2线性规划问题几何意义与解的性质定理-zff课件.ppt

上传人(卖家):晟晟文业 文档编号:4403058 上传时间:2022-12-06 格式:PPT 页数:21 大小:202.50KB
下载 相关 举报
1-2线性规划问题几何意义与解的性质定理-zff课件.ppt_第1页
第1页 / 共21页
1-2线性规划问题几何意义与解的性质定理-zff课件.ppt_第2页
第2页 / 共21页
1-2线性规划问题几何意义与解的性质定理-zff课件.ppt_第3页
第3页 / 共21页
1-2线性规划问题几何意义与解的性质定理-zff课件.ppt_第4页
第4页 / 共21页
1-2线性规划问题几何意义与解的性质定理-zff课件.ppt_第5页
第5页 / 共21页
点击查看更多>>
资源描述

1、122.12.1基本概念基本概念凸集凸集:设:设K是是n维欧式空间的一个点集维欧式空间的一个点集,若任意若任意 两点两点 X(1)K,X(2)K 的连线上一切点的连线上一切点 a a X(1)+(1-a a)X(2)K(0a1),则称则称K为凸集为凸集.3顶点顶点:设:设K是凸集是凸集,X K。若若X不能用不同的不能用不同的两点两点x(1)K,x(2)K 的线性组合表示,即的线性组合表示,即 Xa x(1)+(1-a)x(2)(0a1),则称则称X为为K的一个顶点的一个顶点(极极/角点角点).凸组合凸组合:设:设 X(1),X(2),X(k)是是n维欧式空间的维欧式空间的 k个点个点,若存在若

2、存在k个数个数u u1 1,u u2 2,u uk k满足满足0ui1,则称则称 X=u u1 1X(1)+u u2 2X(2)+u uk kX(k)为为 X(1),X(2),X(k)的凸组合。的凸组合。11kiiu42.2.四个重要定理四个重要定理 线性规划问题的可行解集线性规划问题的可行解集(可行域可行域)是凸集。是凸集。njjjjxbxPXD10,:从从D中任取两个不同的点中任取两个不同的点X(1)和和 X(2),二者应满足可行解定义中的二者应满足可行解定义中的等式条件等式条件;设设X是点是点X(1)和和X(2)连线上的任意连线上的任意一点,有一点,有X=X(1)+(1-)X(2),证明

3、证明XD。5:X(1)和和X(2)满足可行解定义中的满足可行解定义中的等式条件等式条件,则有;,则有;设设X是点是点X(1)和和X(2)连线上的任意一点,有连线上的任意一点,有X=X(1)+(1-)X(2),那么有,那么有;1)2(1)1(bxPbxPnjjjnjjj)2()1()1(jjjxaxax6bbaabxaPxaPxaPxaPxaxaPxPnjjjnjjjjjnjjjjnjjjnjjj)1()1()1()1(1)2(1)1()2(1)1()2(1)1(17 若若X是是LP问题的可行解,则问题的可行解,则X是基本可是基本可行解的充分必要条件是行解的充分必要条件是X的正分量所对应的系数的

4、正分量所对应的系数列向量线性独立列向量线性独立.8 9 (线性规划几何理论基本定理)线性规划几何理论基本定理)X是是LP问题的可行解(可行域中的一点),如果问题的可行解(可行域中的一点),如果它是基可行解,则它必然对应于可行域它是基可行解,则它必然对应于可行域D的顶点。的顶点。:10 X是基可行解是基可行解X是是D的一个顶点的一个顶点X不是不是基可行解基可行解X不是不是D的顶点的顶点11X不是不是基可行解基可行解X不是不是D的顶点的顶点0.2211mmPaPaPamjjjbxP112X不是基可行解不是基可行解X不是不是D的顶点的顶点bPuaxPuaxPuaxbPuaxPuaxPuaxmmmmm

5、m)(.)()()(.)()(2221112221110,.,0),(),.,(),(0,.,0),(),.,(),(2211)2(2211)1(mmmmuaxuaxuaxXuaxuaxuaxX13X不是基可行解不是基可行解X不是不是D的顶点的顶点)2()1(2121XXX必要性证毕必要性证毕14X不是不是D的顶点的顶点 X不是基可行解不是基可行解)2()2(2)2(1)2()1()1(2)1(1)1(,.,.,nnxxxXxxxX0)2()1(jjjxxx15X不是不是D的顶点的顶点 X不是基可行解不是基可行解mjjjbxP1)1(mjjjbxP1)2(mjjjjxxP1)2()1(0)(充

6、分性证毕充分性证毕16若若K是有界凸集,则此凸集上的任何是有界凸集,则此凸集上的任何一点一点X可表示为可表示为K的顶点的凸组合。的顶点的凸组合。根据凸组合的定义证明。根据凸组合的定义证明。17 若可行域若可行域有界有界,则线性规划问题的目标,则线性规划问题的目标函数函数一定一定可以在可行域的可以在可行域的顶点顶点上达到最优值。上达到最优值。1)首先首先,可行域有界就能够找到最优解可行域有界就能够找到最优解;在在非顶点非顶点X处取得最优值,则存在处取得最优值,则存在顶点顶点X(m)也取得相同的最优值。也取得相同的最优值。18kiiikiiiaaXaX11)(010且;kiiikiiiCXaXaCCX1)(1)(019kikimmimikiiiCXXaCCXaCXa11)()()(1)()()0(mCXCX20上述定理的一些有意义的启示:上述定理的一些有意义的启示:(为什么?能举例说明吗?为什么?能举例说明吗?)(类似于坐标与点的对(类似于坐标与点的对应关系!)应关系!)21顶点个数顶点个数基本可行解个数基本可行解个数基的个数基的个数mnC

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(1-2线性规划问题几何意义与解的性质定理-zff课件.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|