单纯形法计算步骤精选PPT.ppt

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

1、第1页第1页，讲稿共17张，创作于星期日第2页既然最优解如果存在，必定可以在基本可行解处取到，因为只要在基本可行解集合（顶点集合）中寻找即可。基本可行解是终止是否最优？否迭代寻找更好的基本可行解判断问题无最优解单纯形方法基本思想第2页，讲稿共17张，创作于星期日第3页第3页，讲稿共17张，创作于星期日第4页cjc1 c2 cm cm+1 ck cnCBXBbx1 x2 xm xm+1 xk xnc1c2cmx1x2xmb1b2bm1 0 0 a1m+1 a1k a1n0 1 0 a2m+1 a2k a2n 0 0 1 amm+1 amk amnj0 0 0miimimacc111miikika

2、cc1miininacc1第4页，讲稿共17张，创作于星期日第5页法则1 最优性判定法则若对基可行解X1，所有检验数j0，则X1为最优解。法则2 入基变量确定法则设 ，则xk为入基变量。lklikikiiabaab0min0maxjjjk法则2 出基变量确定法则设 ，则xl为入基变量。第5页，讲稿共17张，创作于星期日第6页|求解下列求解下列LP问题问题0,108 34 12 42 7 2 3 23 max65432165324325321532xxxxxxxxxxxxxxxxxxxxz第6页，讲稿共17张，创作于星期日第7页0-2-3/401/20j-280103-10j 03-4010 x

3、6 0 02x5-200 x6014-2012x400-1317x10 x4x3x2x1bXBCB03-10Cj0-12/5-4/500-1/5jx1021/405/21100 x3001/41-1/2033x6 18-3/40-5/201 0 x204/51/10012/54-1x302/53/10101/553x6 110-1/200111 0 310/34第7页，讲稿共17张，创作于星期日第8页 无穷多最优解与唯一最优解的判别法则 若对某基可行解X1，（1）所有检验数j0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解；（2）所有非基变量的检验数j0，但aik0，i=1，2，m

4、即xk的系数列向量无正分量，则问题无最优解。第10页，讲稿共17张，创作于星期日第11页 求min z 的情况直接计算最优性检验条件改为：所有j0；入基变量确定法则改为：如果则xk为入基变量。kjjj 0min0,8 20 1010 4020 322 min54321531421321xxxxxxxxxxxxxxz52201 2141 401 21531421xxxxxx第11页，讲稿共17张，创作于星期日第12页cj22300CBXBbx1x2x3x4x523x2x31/42/51/21/21001-1/4000-1/20j-1/2001/203/2023x1x31/23/20102-101

5、-1/201/400-1/20j0101/403/20X*=(0.5,0,0.15,0,0)T，z=21/2+33/20=1.45 第12页，讲稿共17张，创作于星期日第13页第13页，讲稿共17张，创作于星期日第14页121231425min 835 s.t.2 82.4 16 4 12 0(1,2,3,4,5)jzxxxxxxxxxxj第14页，讲稿共17张，创作于星期日第15页121231425min 835 s.t.2 83.4 16 4 12 0(1,2,3,4,5)jzxxxxxxxxxxj第15页，讲稿共17张，创作于星期日第16页1212312425min 835 s.t.2 84.42 16 4 12 0(1,2,3,4,5)jzxxxxxxxxxxxj第16页，讲稿共17张，创作于星期日第17页感谢大家观看第17页，讲稿共17张，创作于星期日