Question

线性规划问题的原问题和对偶问题有可行解,一定有最优解吗

运筹学 对偶定理
有这样一句话：“如果线性规划的原问题和对偶问题都具有可行解,则该线性规划问题一定具有有限最优解.”
答案说这句话是错的,因为“如果线性规划的原问题和对偶问题都具有可行解,则线性规划问题可能有有限最优解也可能为无界解”.
如果能说得很清楚甚至能证明我肯定多给分

Answer 1

错的。

在有限最优解的方面：原问题有有限最优解只能保证对偶问题有有有限最优解。

根据若对偶理论，对偶问题都具有可行解，则优化目标相等的可行解就是最优解，关键是可行解可能有无限个，因此该说法错误。

原问题与其对偶问题目标函数，一个的最大值和另一个的最小值相等。最优解是指变量的，而不是指目标函数的取值的。

扩展资料：

对偶线性规划的经济背景是：若原问题是利用有限资源安排最优生产方案，以获得最大总产值的线性规划问题，则它的对偶问题就是在相同资源的条件下，正确估计资源的使用价值，以达到支付最少费用的线性规划问题。简言之，若原问题为求解资源的最优配置问题，则对偶问题就是求解估价资源的使用价值问题。

参考资料来源：百度百科-对偶线性规划

Answer 2

"如果线性规划的原问题和对偶问题都具有可行解,则该线性规划问题一定具有有限最优解.”
这是一个定理,所以是正确的.
原因: 这句话说的是原问题有可行解, 而且对偶问题也有可行解, 此时线性规划一定有有限最优解,而且对偶问题也有有限最优解.
至于你提到的线性规划原问题是无界解的情形, 这种情形下, 原问题有可行解(无界解),但是其对偶问题无可行解, 所以并不是上述这句话中"原问题和对偶问题都具有可行解"的情形.

Answer 3

我认为答案是错的.
理由是根据对偶定理3 无界性：若原问题（对偶问题）为无界解,则对偶问题（原问题）无可行解.
按照答案如果出现无界解,则条件“原问题和对偶问题都具有可行解”不成立.

Answer 4

答案想表达的是有可能有无限多最优解