线性规划单纯形法运筹学.pptx

上传人:莉*** 文档编号:77256916 上传时间:2023-03-13 格式:PPTX 页数:53 大小:1.24MB
返回 下载 相关 举报
线性规划单纯形法运筹学.pptx_第1页
第1页 / 共53页
线性规划单纯形法运筹学.pptx_第2页
第2页 / 共53页
点击查看更多>>
资源描述

《线性规划单纯形法运筹学.pptx》由会员分享,可在线阅读,更多相关《线性规划单纯形法运筹学.pptx(53页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2.线性规划问题的矩阵表达式:第1页/共53页3、图解法的基本步骤:(一般是一个凸多边形)注意:若是求目标函数的最小值,目标函数直线向下移动第2页/共53页4、线性规划解的结论:1、若(LP)问题有可行解,则可行域是一个凸多边形(或凸多面体)。它可能是有界的;也可能是无界的。2、若(LP)问题有最优解,则最优解可能是唯一的;也可能 是无穷多个。如果是唯一的,这个解一定在该凸多边形的某 个顶点上;如果是无穷多个,则这些最优解一定充满凸多边 形的一条边界(包括此边界的两个顶点)总之,若(LP)问题有最优解,则最优解一定可以在凸多边形的某个顶点达到3、若(LP)问题有可行解,但没有有限最优解,此时凸

2、多边形 是无界的(反之不成立)4、若(LP)问题没有可行解,则该问题没有最优解第3页/共53页定义1.3 在(LP)问题中,A的任意一个mm阶 的非奇异子方阵B(即|B|0)称为 (LP)问题的一个基设r(A)=m0基本可行解退化基本可行解:基本可行解中,存在取0值的基变量非退化基本可行解:基本可行解中,基变量的取值均0对应的基称为退化基对应的基称为非退化基线性规划问题:存在退化基:所有基均非退化m第7页/共53页若有可行解,则可行域是一个凸多边形若(LP)问题有最优解,则最优解一定可以在凸多边形的某个顶点达到基本可行解与可行域的顶点的关系?第8页/共53页0结论:1.可行域为一个凸集2.凸集

3、上有5个顶点3.最优解在顶点产生基的个数=10基的个数=9基本可行解的个数=基的个数最优解第9页/共53页基本可行解0.凸多边形的顶点最优解第10页/共53页基本可行解0.第11页/共53页0.该基本解不是基本可行解不在可行域中第12页/共53页基本可行解0.第13页/共53页基本可行解0.第14页/共53页基本可行解0.第15页/共53页0.基 基本解结论:顶点基本可行解第16页/共53页总结:1.若(LP)问题有可行解,则可行域是一个凸多边形2.若(LP)问题有最优解,则最优解一定可以在凸多边 形的某个顶点达到4.基本可行解的个数是有限的3.顶点与基本可行解是一一对应的若(LP)问题有最优

4、解,则最优解一定可以在某个 基本可行解达到找最优解可从一个基本可行解入手,通过某种方法,调整基变量,转到另一个基本可行解,并使目标函数值不断增大,通过有限次的迭代就能找到最优解单纯形法第17页/共53页第18页/共53页单纯形法的基本思路:1、找出一个可行基,并得到一个基本可行解2、检验该基本可行解是否是最优解,即目标函数值 是否最大,或看看是否存在目标函数值比它大的 基本可行解3、换一个目标函数值比他大的基本可行解4、重复以上步骤,直至找不到更好的基本可行解第19页/共53页第20页/共53页第一步:寻找第一个基本可行解(初始基本可行解)第21页/共53页X0为基本可行解对应目标函数值三、换

5、基迭代第22页/共53页取做非基变量第23页/共53页8第24页/共53页五、循环迭代出基变量的确定:第25页/共53页1.5105.530最优解第26页/共53页第一步:寻找初始基本可行解第三步:换基迭代(2)确定出基变量:第27页/共53页(2)确定出基变量:三、换基迭代在第4个方程五、循环迭代:第28页/共53页第29页/共53页单纯形法的基本思想:(1)入基变量:设ck=maxci|ci 0,取xk为入基变量 得到新的非基变量目标函数表示成新非基变量的函数,4、把约束方程化为每个方程只含一个新的基变量令非基变量取零的一新的基本可行解X(2)出基变量:1、找到一个基本可行解X此时的约束方

6、程每个方程只含一个基变量目标函数必须表示成非基变量的函数2、判断X是否为最优解:若目标函数中有非基变量的系数ci0,则X不是最优解。3、换基迭代第30页/共53页常数项2 3 1 0 0 0 6-3 2 0 1 0 0 30 2 0 0 1 0 52 1 0 0 0 1 4基变量4 3 0 0 0 0 z单纯形表主元素b1 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0 1 0 1.5 90 2 0 0 1 0 50 1 0 0 0 -2 z-8检验行第31页/共53页b1 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0 1 0 1.5 90

7、 2 0 0 1 0 50 1 0 0 0 -2 z-8b0 1 0.5 0 0 -0.5 10 0 -1.75 1 0 3.25 5.5 0 0 -1 0 1 1 31 0-0.25 0 0 0.75 1.50 0 -0.5 0 0 -1.5 z-9为最优解第32页/共53页常数项 4 1 0 0 0 Z-1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 848第33页/共53页1 -4 0 1 0 4 0 -3 1 1 0 60 2 0 -1 1 4 0 17 0 -4 0 Z-16 1 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/

8、2 2 0 0 0 9/2 -17/2 Z-48 无界!常数项 4 1 0 0 0 Z-1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 848第34页/共53页1 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-48 对应的线性规划问题无界所以,该线性规划问题无界第35页/共53页3、将约束方程化为每个方程只含一个基变量 目标函数表示成非基变量的函数 单纯形法步骤:1、化标准型 2、选定一个可行基,并得一基本可行解X?5、判断X是否为最优解:若目标函数行中所有检验数ci0,则X为 最优解。若存在

9、某个cj0,且所有的aij 0,取xk为入基变量 (2)出基变量:7、对单纯形表做初等行变换:把基变量对应的列化为 单位向量,目标函数的基变量系数化为零,得一新的基本可行解X。转第4步第36页/共53页可行典则形式第37页/共53页不是单纯形表初始单纯形表 1 0 0 2 2 z-10 11 0 0 0 8 z+50 第38页/共53页典则形式b 4 2 0 0 0 z2 1 0 1 0 42 5 1 0 0 12-1 1 0 0 1 2 6 2b 0 0 0 -2 0 z-81 0.5 0 0.5 0 20 4 1 -1 0 80 1.5 0 0.5 1 4b 0 0 0 -2 0 z-8

10、1 0 -0.125 0.125 0 1 0 1 0.25 0.25 0 2 0 0 -0.375 0.375 0 1 第39页/共53页本题说明:1、最优解不唯一,但最优值唯一3、在实际应用中,有多种方案可供选择第40页/共53页单纯形法的矩阵形式:第41页/共53页B 可逆第42页/共53页关于可行基B的典则形式第43页/共53页=一个数Z0常数第44页/共53页行向量检验数第45页/共53页第46页/共53页初始单纯形表的矩阵形式:设B为一个可行基B的典则形式为:E0常数项第47页/共53页E0常数项0最优值 最优单纯形表第48页/共53页设B为一个可行基B的典则形式为定理1.7 对非退

11、化线性规划问题,单纯形法必然在有限次迭代内终止于下述两种情况之一:或者找到一个最优基本可行解;或者判断该问题无界。第49页/共53页练习:用单纯形法求下列线性规划问题的解:无界,即无最优解第50页/共53页b 4 3 0 0 0 z5 2.5 0 1 0 25002 2 1 0 0 16001 0 0 0 1 400800500400b1 0 0 0 1 4000 2.5 0 1 -5 500 0 2 1 0 -2 8000 3 0 0 -4 z-1600400200b0 1 0 0.4 2.2001 0 0 0 1 4000 0 1 -0.8 2 4000 0 0 -1.2 2 z-2200b2004000 0 0.5-0.4 1 2000 1 1 -0.4 0 6001 0 -0.5 0.4 0 2000 0 -1 0.4 0 z-2600第51页/共53页b-1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 84 1 0 0 0 z48b1 -4 0 1 0 40 2 0 -1 1 40 -3 1 1 0 6 0 16 0 -4 0 z-162b0 1 0-0.5 0.5 21 0 0 -1 2 80 0 0 4 -8 z-48无界,即无最优解第52页/共53页感谢您的观看!第53页/共53页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 应用文书 > PPT文档

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁