使用 scipy.optimize.linprog returns 次优解的线性规划

Question

我正在尝试解决 Python 2.7 中的以下线性规划问题，但出于某种原因，linprog 没有返回正确的结果。

Minimize: -x2 -x3

这样：

x0 + 0.33*x2 + 0.67*x3 = 0.5
x1 + 0.67*x2 + 0.33*x3 = 0.5
x0 + x1 + x2 + x3 = 1.0

这是我的代码：

from scipy.optimize import linprog

a_eq = [[1.0, 0.0, 0.33, 0.67],
        [0.0, 1.0, 0.67, 0.33], 
        [1, 1, 1, 1]]

b_eq = [0.5, 0.5, 1.0]

c = [0, 0, -1.0, -1.0]

x = linprog(c=c, A_eq=a_eq, b_eq=b_eq)
print x

这是上面的输出：

fun: -0.0
message: 'Optimization terminated successfully.'
nit: 4
slack: array([], dtype=float64)
status: 0
success: True
x: array([ 0.5,  0.5,  0. ,  0. ])

显然，以下解决方案更优：

x: array([0.0, 0.0, 0.5, 0.5])

这使得 objective 函数值：

fun: -1.0

我确实发现了 github 中报告的一些问题。这可能是我面临的问题还是我做错了什么？任何帮助将不胜感激！谢谢。

Answer 1

I did find some issues reported in github. Could this be what I'm facing...?

完全正确：

It turns out that A_eq in the problem is rank-deficient. After finding and removing rows that are a linear combination of others, linprog's solution agrees with the other.

矩阵 a_eq 秩亏。最后一行是前两行的线性组合。这使得该行对于约束来说是多余的，所以我们可以简单地删除它和 b_eq:

中的相应条目

a_eq = [[1.0, 0.0, 0.33, 0.67],
        [0.0, 1.0, 0.67, 0.33]]

b_eq = [0.5, 0.5]

这导致最优解 x: array([ 0. , 0. , 0.5, 0.5])。

使用 scipy.optimize.linprog returns 次优解的线性规划

Linear programming using scipy.optimize.linprog returns suboptimal solution

python

scipy

linear-programming