python - scipy.optimize linprog 不会返回我期望的最小解决方案

Question

我读到 scipy 中的 linprog 返回最小解，并且可以通过将目标函数乘以 -1 来获得最佳解。

我在这里读到的:https://realpython.com/linear-programming-python/ 我测试了他们提供的示例，看看我是否也能得到最小的解决方案——我可以。


关于我试图解决的问题 我希望解决方案是:

opt_sol1.x = [0.61538462 0.38461538]
opt_sol2.x = [0.0, 1.0]

但是在两种情况下我都得到相同的结果 [0.61538462 0.38461538] 为什么？ -- 我的猜测是它与我的目标函数中的值相互接近有关，但只是一种猜测 有没有办法获得我正在寻找的第二个解决方案？

from scipy.optimize import linprog

obj_fct1 = [0.5, 0.5]
obj_fct2 = [-0.5, -0.5]
lhs_ineq = [[1.5, 0.2]]
rhs_ineq = [1]
lhs_eq = [[1,1]]
rhs_eq = [1]
bnds = [(0, 1),
          (0, 1)]

opt_sol1 = linprog(c=obj_fct1,
                  A_ub=lhs_ineq,
                  b_ub=rhs_ineq,
                  A_eq=lhs_eq,
                  b_eq=rhs_eq,
                  bounds=bnds)
print(opt_sol1.x)
print("------------------------------------------")
opt_sol2 = linprog(c=obj_fct2,
                  A_ub=lhs_ineq,
                  b_ub=rhs_ineq,
                  A_eq=lhs_eq,
                  b_eq=rhs_eq,
                  bounds=bnds)
print(opt_sol2.x)


>>> [0.61538462 0.38461538]
>>> ------------------------------------------
>>> [0.61538462 0.38461538]

Answer 1

这里的“问题”是，这个问题有无限数量的最小值和最大值，所有最优解的目标函数等于相同的值(忽略最大化的符号翻转)。这可以通过检查相对于目标函数的等式约束并注意到它们是彼此的线性组合来看出。对于线性规划，最优解位于边界上，可以是直线，也可以是顶点。如果它位于顶点而不是直线，则有唯一解，但如果它位于直线上，则有无限解。因为你的目标函数和等式约束是彼此的线性组合，所以结果是有无限多个解，并且最小值和最大值是相同的。

就您而言，您的目标是 f(x1, x2) = 0.5*x1 + 0.5*x2 或等效的 f(x1, x2) = 0.5*(x1 + x2) 。您的等式约束表明 x1 + x2 = 1，因此我们看到结果是 f(x1, x2) = 0.5。 (如果我们要最大化，我们将像您一样更改目标函数的符号，并为所有可行的解决方案得出 f(x1,x2) = -0.5。)

考虑到最大化和最小化问题都有无限多个解决方案，为什么求解器总是返回[0.61538462 0.38461538]？默认求解器使用 SIMPLEX 算法的一种形式，该算法始终返回一个顶点值(即使存在一行解，顶点值仍然是一个解，这缩小了需要检查的可能解的数量) 。在本例中，x1 + x2 = 1 和 1.5*x1 + 0.2*x2 = 1 相交时存在一个顶点，该顶点位于 x1 = 8/13 和 x2 = 5/13。