运筹学大学课件1-3线性规划解的性质文档_第1页
运筹学大学课件1-3线性规划解的性质文档_第2页
运筹学大学课件1-3线性规划解的性质文档_第3页
运筹学大学课件1-3线性规划解的性质文档_第4页
运筹学大学课件1-3线性规划解的性质文档_第5页
已阅读5页，还剩15页未读， 继续免费阅读

下载本文档

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

文档简介

第三节线性规划解的性质线性规划解的概念凸集及其顶点几个基本定理的证明继续返回线性规划问题解的概念标准型可行解:满足AX=b,X>=0的解X称为线性规划问题的可行解。全部可行解的集合称为可行域。最优解：使目标函数Z=CX达到最大值的可行解称为最优解。

基：若B是矩阵A中m×m阶非奇异子矩阵（|B|≠0），则B是线性规划问题的一个基。不妨设：

,j=1，2，…,m——

基向量。，j=1，2，…,m

——

基变量。,j=m+1,…,n

——

非基变量。线性规划问题解的概念

求解

线性规划问题解的概念基解：称上面求出的X解为基解,基解个数不超过Cnm个基可行解：非负的基解X称为基可行解,每一个基可行解的非零分量个数不会超过m个.可行基：对应基可行解的基称为可行基线性规划问题解的概念T基变量令可求出：0...21====++nmmxxx

线性规划解的关系图

非可行解可行解

基可行解

基解线性规划问题解的概念

最优解？

例：求基解、基可行解、最优解。线性规划问题解的概念10051045Y20452017Y35005410Y

40550-120N5100-50415N652.5001.517.5Y7540-3022N

2430019Y00

00是否基可行解最优解线性规划问题解的概念解：

：求基解、基可行解、最优解。练习：线性规划问题解的概念凸集及其顶点凸集：凸集及其顶点

顶点:若K是凸集，X∈K；若X不能用不同的两点的线性组合表示为：则X为顶点.

凸集凸集及其顶点定理1:若线性规划问题存在可行域,则其可行域:是凸集.

几个基本定理的证明证明:几个基本定理的证明{})0,³==XbAXXD

只要验证X在D中即可

引理：可行解X为基可行解

X的正分量对应的系数列向量线性无关定理3：若线性规划问题有最优解，则一定存在一个基可行解是最优解。定理2：线性规划问题的基可行解X

对应于可行域D的顶点。证明：反证法。分两步。几点结论：线性规划问题的可行域是凸集。基可行解与可行域的顶点一一对应，可行域有有限多个顶点。最优解必在顶点上得到。图解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生

目标函数等值线的斜率最优解图解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生

目标函数等值线的斜率最优解图解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

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

最新文档

评论

0/150

提交评论