线性规划的基本性质_第1页
线性规划的基本性质_第2页
线性规划的基本性质_第3页
线性规划的基本性质_第4页
线性规划的基本性质_第5页
已阅读5页，还剩18页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

关于线性规划的基本性质2024/4/42第2页,共23页，2024年2月25日，星期天2024/4/43第3页,共23页，2024年2月25日，星期天2024/4/44第4页,共23页，2024年2月25日，星期天2024/4/45第5页,共23页，2024年2月25日，星期天2024/4/46第6页,共23页，2024年2月25日，星期天第7页,共23页，2024年2月25日，星期天2024/4/48第8页,共23页，2024年2月25日，星期天2024/4/49第9页,共23页，2024年2月25日，星期天2024/4/410第10页,共23页，2024年2月25日，星期天第11页,共23页，2024年2月25日，星期天2024/4/412第12页,共23页，2024年2月25日，星期天2024/4/413是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足四、线性规划解的概念和性质1.线性规划解的概念第13页,共23页，2024年2月25日，星期天2024/4/414第14页,共23页，2024年2月25日，星期天2024/4/415B是可逆的；B的行列式≠0第15页,共23页，2024年2月25日，星期天2024/4/416x≥0第16页,共23页，2024年2月25日，星期天2024/4/417基本解的个数？第17页,共23页，2024年2月25日，星期天2024/4/418非基变量是自由变量.基变量用非基变量表示。第18页,共23页，2024年2月25日，星期天2024/4/4引理1.线性规划的可行解为基可行解的充要条件是其正分量对应的系数列向量线性无关.引理2.可行解x是K的顶点的充要条件是x为线性规划的基可行解。第19页,共23页，2024年2月25日，星期天2024/4/4当这些列向量线性无关时，由引理1，知x为基础可行解.当向量线性相关时，则存在一组不全

为零的数组,使得成立。证明：设x是可行解，且前k个正分量为若它们在矩阵A中对应的列向量为（1）则有由(2)式右端为零，因此总可假定存在非零的,(否则乘以-1于（2）的两端)，总有成立。（2）第20页,共23页，2024年2月25日，星期天2024/4/4在上式中乘以并与（2）相加得：因而，当取时，上式中至少会有一个分量。也就是说，若记上式中对应的点为，则正分量比x至少减少一个.若此时，正分量对应的{}线性无关，则已是基础可行解。否则重复上述过程，正分量的个数不断减少，至多减至只剩一个时为止，例如对应列向量为但，它是只含一个向量的线性无关组，因此，如果约束集有可行解，则必定存在基本可行解。第21页,共23页，2024年2月25日，星期天2024/4/4定理2（线性规划基本定理）设约束集K非空()有解，且最大值可在一个顶点（基础可行解）上达到。对任意的，LP的目标函数值有上界，则线性规划第

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论