scipy - 目标函数值的零乘数不能给出最可行的解决方案

Question

我正在使用 Pulp来解决线性程序（也使用 scipy 得到相同的结果）。所以我的线性程序公式有问题，或者我不知道单纯形算法如何工作的一些棘手细节。

这是minimization的目标函数，注意乘数x2是0，所以我不期望x1或x2有任何值0，因为x3没有最大约束并且-1 * x3能够为最小化提供更多价值：

线性方程组：

作为一个解决方案，x2 = 20即使它在目标函数中的乘数是0.

如果在我设置的目标函数中-2 * x3，那么它工作得很好。

Answer 1

您发布的解决方案给出了目标 = -380。检查x=[20,0,0,20,0,20,20,0]，目标函数也是 -380，这意味着它也是最优的，因此，您有无限多的解决方案（很容易证明这两个点的任何凸组合都是最优的，请参阅任何线性规划书）。问题是您的纸浆求解器在遇到一个最佳极值点时停止了。如果您有兴趣获得所有最佳极端点，我建议您使用 Cplex（它不是免费的，但您可能有资格参加 IBM 学术计划）。此外，您可以在 PuLP 求解器中为 Dual Simlex 设置求解方法，使其朝着不同的方向前进，并且有机会获得另一个极值点。