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。