《单纯形法计算步骤》PPT课件.ppt

《《单纯形法计算步骤》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《单纯形法计算步骤》PPT课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线线 性性 规规 划划Linear ProgrammingLinear Programming运运筹筹学学课课件件第2页线线性性规规划划|线性规划问题及其数学模型线性规划问题及其数学模型|图解法图解法|单纯形法原理单纯形法原理|单纯形法计算步骤单纯形法计算步骤|单纯形法的进一步讨论单纯形法的进一步讨论|数据包络数据包络|其他应用例子其他应用例子|案例分析案例分析第3页既然最优解如果存在，必定可以在基本可行解处取到，既然最优解如果存在，必定可以在基本可行解处取到，则只要在基本可行解集合（顶点集合）中寻找即可。则只要在基本可

2、行解集合（顶点集合）中寻找即可。基本可行解基本可行解是是终止终止是否最优？是否最优？否否迭代寻找更好的基本可行解迭代寻找更好的基本可行解判断问题无最优解判断问题无最优解单纯形方法基本思想单纯形方法基本思想第4页单纯形法计算步骤单纯形法计算步骤第5页单单纯纯形形表表cjc1c2cmcm+1ckcnCBXBbx1x2xm xm+1xkxnc1c2cmx1x2xmb1b2bm100 a1m+1a1ka1n010 a2m+1a2ka2n001amm+1amkamnj000第6页单纯形法的基本法则法则法则1 最优性判定法则若对基可行解X1，所有检验数j0，则X1为最优解。法则法则2入基变量确定法则设 ，

3、则xk为入基变量。法则法则3 出基变量确定法则第7页算 例|求解下列LP问题第8页0-2-3/401/20j-280103-10j03-4010 x6002x5-200 x6014-2012x400-1317x10 x4x3x2x1bXBCB03-10Cj0-12/5-4/500-1/5jx1021/405/21100 x3001/41-1/2033x618-3/40-5/2010 x204/51/10012/54-1x302/53/10101/553x6110-1/2001110算 例310/34第9页关于单纯形法的补充说明关于单纯形法的补充说明无穷多最优解与唯一最优解的判别法则无穷多最优解

4、与唯一最优解的判别法则若对某基可行解若对某基可行解X1，（1）所有检验数）所有检验数j0，且有一个非基变量，且有一个非基变量xk的检验数等于的检验数等于0，则问题有无穷多最优解；，则问题有无穷多最优解；（2）所有非基变量的检验数）所有非基变量的检验数j0，但，但aik0，i=1，2，m即即xk的系数列的系数列向量无正分量，则问题无最优解。向量无正分量，则问题无最优解。第12页关于单纯形法的补充说明关于单纯形法的补充说明求求minz的情况的情况直接计算最优性检验条件改为：所有直接计算最优性检验条件改为：所有j0；入基变量确定法则改为：如果入基变量确定法则改为：如果则则xk为入基变量。为入基变量。第13页关于单纯形法的补充说明关于单纯形法的补充说明cj22300CBXBbx1x2x3x4x523x2x31/42/51/21/21001-1/4000-1/20j-1/2001/203/2023x1x31/23/20102-101-1/201/400-1/20j0101/403/20X*=(0.5,0,0.15,0,0)T，z=21/2+33/20=1.45 第14页练练习习第15页练练习习第16页练练习习第17页练练习习