欢迎来到天天文库
浏览记录
ID:56775217
大小:17.50 KB
页数:1页
时间:2020-07-08
《线性规划最优解的几种可能情况.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、线性规划最优解的几种可能情况:1.有唯一的最优解(可行域为封闭的有界区域、可行域为非封闭的无界区域)2.有一个以上的最优解(可行域为封闭的有界区域、可行域为非封闭的无界区域)3.无界解(目标函数无界,即虽有可行解,但在可行域中,目标函数可以无限增大或无限减小)4.无可行解(可行域为空集)Min型与Max型单纯形表的唯一区别: 检验数反号 Min型单纯形表中 -当检验数均大于等于零时为最优; -令负检验数中最小的对应变量为换入变量。 Max型单纯形表中 -当检验数均小于等于零时为最优; -令正的检验数中最大的对应变量为换入变量。 ①②
2、②③④⑤⑤⑥⑴⑵⑵⑶解的几种情况在单纯形表上的体现(Max型): 1)唯一最优解判别:最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。 2)多重最优解判别:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解(或无穷多最优解)。 3)无界解判别:某个检验数大于零且换入变量对应的列中所有的分量皆非正,则线性规划具有无界解。 4)无可行解的判断:当用大M单纯形法计算得到最优解并基变量中还存在非零人工变量时,则表明原问题无可行解。 5)退化解的判别:存在某个基变量为零的基本可行解。 4.2对偶问题的基本性质1.对称性对偶
3、问题的对偶是原问题。2.弱对偶性若是原问题的可行解,是对偶问题的可行解,则存在求目标函数最大化时,在单纯形表中: ①如果检验数均非正,而b列中有负值,这时使用 对偶单纯形法; ②如果所有bi≥0,检验数有正值,使用 单纯形法: ③如果b列中有负值,且检验数中有正值,这时必须引入 人工变量,建立新的单纯形表,重新计算
此文档下载收益归作者所有