线性规划最优解的几种可能情况.doc

《线性规划最优解的几种可能情况.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列中有负值，且检验数中有正值，这时必须引入 人工变量，建立新的单纯形表，重新计算