运筹学线性规划.pptx
《运筹学线性规划.pptx》由会员分享,可在线阅读,更多相关《运筹学线性规划.pptx(57页珍藏版)》请在咨信网上搜索。
1、定义定义2:称所有可行解(点)构成的集合为可行集可行集或可行域。也称为可行解集可行解集。例如:上面 SLP 的可行域为R=x|Ax=b,x0定义定义3:若一个线性规划问题的可行集为空集时,则称这一线性规划无可行解无可行解。这时线性规划的约束条件不约束条件不相容相容。由上一章的分析可以看到:一个线性规划的可行解集可以是空集,有界非空集和无界非空集。二 最优解,无界解最优解,无界解定义定义4:称使目标函数值达到最优值的可行解为线性规划问题的最优解最优解。解解:问题的可行域是上图所示的 无界 凸多边形区域,在此无界可行域上,目标函数值无上界,所以这个线性规划问题有无界解。定义定义5:对于极大化目标函
2、数的标准线性规划问题,定义其无界解如下:对于任何给定的正数M,存在可行解 x 满足 Ax=b,x 0,使 cx M。那么称该线性规划问题有无界解无界解。由定义可知,无界解的 意思 是:若是极大化目标函数,则在可行域上目标函数值无上界;若是极小化目标函数,则在可行域上目标函数值无下界。那么,有无界解的线性规划问题一定没有最优解。maxs.t 例例1 1.考虑线性规划问题:例例2.max f=s.t 解:此问题的可行域如上图,是一个无界的 多边形。但极大化目标函数却以1为上界。因此这个线性规划问题没有无界解,而且事实上,此问题目标函数最优值max f=1在可行域射线 上均可达到。三三.基、基本可行
3、解基、基本可行解定义定义6:对于约束条件Ax=b,设A是秩m的mn矩阵,用(Pj,j=1 n)表示A的第j列向量。即A=()。由A的m个列向量构成的m阶方阵 B=()若B是非奇异的,即detB0,则称B为一个基基或称为一个基矩阵基矩阵。因为SLP问题中含有约束条件Ax=b,因此也通常称B为线性规划SLP的一个基。解:A=使min f=满足例3.求x1-x5由上面定义可知,B中m个列向量是线性无关的,并且它是A的列向量组的一个最大无关组。按定义,A中m个列向量,只要是线性无关的就可以构成一个基。定义定义7 7:若变量 对应A中列向量 包含在基B中,则称 为B 的基变量基变量;若变量 对应A中的列
4、向量 不包含在基B中,则称 为B中的非基变量非基变量。定义定义8 8:设Ax=b,x 0一个基 ,其对应的基变量构成的m维列向量记为 这时若取非基 是线性无关,因此 是一组基。而 不在这个基中,所以x1,x2为非基变量。的列是线性无关的,即则于是得到方程组Ax=b的一个解:非基变量 称之为对应于基B的基本解基本解。这个定义也告诉我们怎样找一个基本解)变量等于0,则 Ax=b BxB=b,得唯一解xB=B-1b.记为 如:上面例2中,非基变量 x1=x2=0.则可得x3=5,x4=-2,x5=21.所以x0=(0,0,5,-2,21)是对应于基B的一个基本解,但由于x4=-2=0,则称它为满足约
5、束 Ax=b,x=o的基本可行解基本可行解。对应地称B为可行基,因SLP中具有此约束条件。也通常 称为SLP的基本可行解。上面我们讲到基本解中有n-m个分量必须取零值,而只有m个基变量取非零值。而基本可行解,它一方面是基本解,另一方面又是可行解,因为它是基本解,所以n-m个非基变量取0值;它是可行解,则m个基变量取非负值,从而基本可行解正分量是个数不超过m.定义定义1010:使目标函数达到最优值的基本可行解,称为基基本最优值本最优值。例4:(SLP)如例3,试找一个基本可行解。解:是其一个基矩阵.p1,p3,p5是一个基。则 x1,x3,x5为基变量。X2,x4为非基变量。令 x2=x4=0.
6、得x1=2,x3=3,x5=9.故 x1=(2,0,3,0,9)是原问题的一个基本可行解,B1为基可行基。那么满足Ax=b,x 0的正分量个数不超过m的可行解(Rank(Am n)=m)是否一定是基本可行解呢?我们举例说明这个问题。它有正分量个数等于m(m=2)的可行解:x1=3,x2=1,x3=0,x4=0但它不是基本可行解。证:(反证法)假设可行解x=(3,1,0,0)T是上面约束的基本可行解。因为基本可行解中非基变量取0值,基变量取非负值。在这个可行解中x1,x2非零正值,因此x1,x2不可能是非基变量,只能是基变量。按定义,基变量对应的系数矩阵中的列向量p1,p2应构成一个基矩阵B.但
7、这里p1,p2 是线性相关的(p1=p2),这与B是基矩阵矛盾。故知x=(2,1,0,0)T不是基可行解。例5.已知约束条件为:其可行域如上图,可行解(3,1,0,0)T。用x1,x2表示则为图上点(3,1)。由图可见这不是可行域的顶点。而我们将证明基本可行解是可行域的顶点基本可行解是可行域的顶点。而在例4中p1,p3线性无关,所以B=(p1,p3)是一个基矩阵,对应的基本解为(4,0,0,0)T。用坐标x1,x2表示则为平面上的点(4,0),是上图可行域的顶点。由此例可见,虽然可行解(3,1,0,0)T 正分量个数不超过m,但它的正分量对应的列向量不是线性无关的,不能与一基矩阵相联系,所以它
8、不是一个基本可行解。现在我们把例4中松弛变量x3,x4去掉,约束变为 对于这个基B=(p1,p3)的基本可行解(4,0,0,0)T。除了非基变量 x2=x4=0外,还有基变量 x3=0,这样的基本可行解称为退化的基本可行解退化的基本可行解。定义定义11:有基变量取 0 值的基本可行解,称为退化的基本可行解,它对应的基B称为退化的可行基退化的可行基。m个基变量均取正值的基本可行解,称为非退化的基本可行解非退化的基本可行解对应基B称为非退化的可行基非退化的可行基。如果一个线性规划问题的所有基本可行解都是非退化的,则称这个线性规划问题是非退化的。线性规划问题是非退化的。由以上定义可知,如果约束问题有
9、m 个基变量,则在退化的基本可行解中,正分量个数一定小于m。在基本可行解中取正值的变量一定是基变量。这样基本可行解中正分量个数也不会超过m。但是上面的例4已经说明,正分量个数不超过 m 的可行解不一定是基本可行解,还要看可行解中正分量对应的列向量是否线性无关而定。然而基本可行解中正分量对基本可行解中正分量对应的系数矩阵的列向量一定线性无关应的系数矩阵的列向量一定线性无关。证明证明:(1)必要性.假定x0是基本可行解,由基本可行解定义可知,x0中的正分量一定是基变量,基变量对应系数矩阵A中的列向量一定在基B中,则 线性无关。充分性.假定x0正分量对应A中的列向量线性无关,只要证明x0是基本可行解
10、。因为矩阵A的秩m,则k m(k是x0的正分量个数)定理定理1 1:设设 A A是是m nm n 矩阵,秩为矩阵,秩为 m m ,对于对于Ax=b,Ax=b,x 0 x 0有:有:(1 1)可行解)可行解 x x0 0=是基本可行解的充要条件是是基本可行解的充要条件是 x x0 0 的的正分量正分量 对应对应A A中的列向量中的列向量 线性无关。线性无关。(2 2)如果)如果 x=(0,0.0)x=(0,0.0)T T 即即 x=0 x=0 是可行解,则它一定是基本可行是可行解,则它一定是基本可行解。解。当k=0,则可写成:因此,(SLP)问题的可行集是一个多面凸集。多面凸集可以有界,亦可无界
11、。例例8 8:将下面的约束条件:写成Ax=b的形式一般地,我们可以把任何线性规划问题的条件都写成 Ax=b的形式。例如:解:上面的约束条件可以转化为:其图如下(1),是一个二维有界的多面凸集。(1)(2)所确定的是一个无界的多面凸集。如上图(2)2.2 线形规划的基本定理线形规划的基本定理一一 基本可行解与极点解的等价性本可行解与极点解的等价性例如多边形,多面体的顶点,圆周上,球面上的顶点等都是顶点。若x0是可行域的极点,设x的正分量 要证明x 是基本可行解,由上节的定理1知,只需证明这些数分量对应A中的列向量 线性无关。上面我们已经说(SLP)的可行域是由直线,平面或超平面为边界构成的凸多边
12、形或凸多面体(亦即多面凸集)因此线形规划问题可行域的顶点就是极点。定理定理3 x是线形规划(是线形规划(SLP)可行域可行域R的极点的充要条件的极点的充要条件是:是:x是基本可行解。是基本可行解。证明:必要性。设x是可行域的极点,要证明x是基本可行解。若x=0是可行域的极点。则x=0是可行解,由上节定理1中(2)即知x是基本可行解。现在构造一个n维列向量y,它的第 分量分别为 ,其余分量为0,则有y0。且 Ay=0由于 0。(1=i=0因而 是两个可行解。分别记为:有:因 故 取 则 这表明:x可以表示成R中其它点的凸组合。这与 x是R的极点相矛盾。故必要性得证。充分性:设x是(SLP)的基本
13、可行解。要证x是可行域的极点。若x=0 是基本可行解,而存在可行域中的点,使x=0 能表成:的形式。即 =0 因此 这表明x=0不能表成可行域中两点的凸组合,因此是极点。若x0是基本可行解。由定理1知,x的正分量 对应A中列向量 线形无关。反证法:若基本可行解x不是可行域的极点。则可行域中存在异于x的不同两点设为y和z。或 且 时 =0 所以上式变为:而 故 因而y与z是可行解,应满足 两式相减得 因为y与z是不相同的两点。他们的分量至少有一个不相等。即 不全为0。因此 线性相关。这与x是基本可行解相矛盾。故x是基本可行解。则必为可行域的顶点。证明:(1)设有可行解 若 =0,则由定理1(2)
14、知 就是基本可行解。若 0,不妨设 的正分量为前k个。二二 基本定理基本定理 定理定理4 4 假定线性规划(SLP)的A是mn的矩阵。秩为m,且A的列向量 均不是零向量。(1)若有可行解,则必有基本可行解(即非空可行集若有可行解,则必有基本可行解(即非空可行集R必有极点)必有极点)(2)若有最优解,则目标函数必定在基本可行解上(极若有最优解,则目标函数必定在基本可行解上(极点)达到极值。(即若有最优解,则必有基本最优解)点)达到极值。(即若有最优解,则必有基本最优解)(3)若目标函数在多于一个极点上达到最优,则必在这若目标函数在多于一个极点上达到最优,则必在这些极点的凸组合上达到最优些极点的凸
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 线性规划
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。