Python - 无法解决LP

Question

我一直在尝试用 Python 解决以下线性问题：

minimize{x1,x2}, such that:
x1+2*x2 = 2
2*x1+3*x2 =2
x1+x2=1
x1>=0
x2>=0

我已经尝试过纸浆和 linprog 库 ( from scipy.optimize import linprog)，但我什么也没有。第一点是，这两个库都希望我输入某种“目标函数”来最小化，而我希望将我的变量最小化（本质上是为了验证我没有无限多的解决方案）。但是，我尝试最小化以下目标函数：

x1 + x2

判断这几乎等于最小化 x1 和 x2，因为它们都大于 0。第二点是纸浆和 linprog 似乎都无法处理“不可行”的情况。这意味着当这两个库遇到不可行的问题时，它们不会打印出相关的内容（即：“问题无法解决”），而是开始放弃约束，直到得到答案。例如，上述问题是不可行的，因为不存在满足上述所有方程的数 x1 和 x2。现在 linprog 在这种情况下打印出以下内容

message: 'Optimization terminated successfully.'

和

x: array([ 0.,  0.])

从中我了解到解决方案是x1 = 0和x2 = 0，这当然是不正确的。

我的下一步是用嵌套的 for 循环和条件语句自己编写所有代码来描述约束，但我还不想去那里。此外，我正在寻找一个可以轻松推广的解决方案，比如 100 多个不同的方程（因为我将在实数的 n 维空间中进行操作）和 60 多个变量（x1，x2，...， x60）。

Answer 1

这是微不足道的，如果您遇到问题，我不明白为什么您没有显示任何代码：

代码：

import numpy as np
from scipy.optimize import linprog

A_eq = np.array([[1, 2],  # x1+2*x2
                 [2, 3],  # 2*x1+3*x2
                 [1, 1]]) # x1+x2
b_eq = np.array([2,2,1])
c = np.array([1,1])       # min x1 + x2

res = linprog(c, A_eq=A_eq, b_eq=b_eq, method='simplex')
print(res)                                         # fails as expected;
                                                   #   crypted message (for non-experts)

# scipy >= 1.0 !!!
res = linprog(c, A_eq=A_eq, b_eq=b_eq, method='interior-point')
print(res)                                         # warns about problem-status in presolve

res = linprog(c, A_eq=A_eq, b_eq=b_eq, method='interior-point', options={'presolve': False})
print(res)                                         # declares infeasible
                                                   #   turning-off presolve sometimes needed
                                                   #   for more accurate status messages
                                                   #   (which is documented!)

需要的其他信息：

边界：序列，可选

(min, max) 对 x 中的每个元素，定义该参数的边界。当该方向没有界限时，对 min 或 max 之一使用 None 。默认边界为 (0, None)（非负）如果提供了包含单个元组的序列，则 min 和 max 将应用于问题中的所有变量。

这些运行都不会输出 status=success！（并设置了与某些退出状态相对应的标志）

去检查设置了哪些属性。（我没有展示这些，因为我的 scipy-install 有点定制了一些私人调试打印）

现在给你一些忠告：

• 不要相信 scipy.linprog(method='simplex')
  • 如果你不相信我：查找 github-issues 或搜索 SO
  • （我早就弃用了该功能；如果没有人修复它）
• 尝试 scipy.linprog(method='interior-point')
  • 如果你能接受非简单的方法
  • 如果你有 scipy >= 1.0
• 与 scipy 相比，Coin 的纸浆带来了一个非常非常先进的 LP 求解器（Clp，支持 Simplex ）并且正确使用它，它不会在这里为您的问题输出错误的状态消息！
  • Clp 在我看来是最先进的开源 LP 求解器
• 如果您没有目标：将目标向量c设置为零！

只是要清楚

这意味着当这两个库遇到不可行的问题时，它们不会打印出相关的内容（即：“问题无法解决”），而是开始放弃约束，直到得到答案。例如，上述问题是不可行的，因为不存在满足上述所有方程的数 x1 和 x2。

不！. 当问题不可行时，没有 LP 求解器应该返回一个成功的解决方案（这不是说问题不可行！）。

此外，大多数 LP 求解器支持不可行检测（所有单纯形求解器；并非所有类似 IPM 的求解器，而是 scipy 的），并在问题不可行时返回可行性证书！

只有损坏的求解器linprog(method='simplex')在这里可能会很麻烦。

（以上适用于不暗示数值问题的问题，使用有限内存浮点数学总是可能的；除了可能专门的有理型求解器。这甚至适用于最先进的商业求解器，这并不重要在这里解决您的问题）

编辑：使用硬币 纸浆的方法：

from pulp import *

prob = LpProblem("problem", LpMinimize)
x1 = LpVariable('x1', lowBound=0., upBound=None, cat='Continuous')
x2 = LpVariable('x2', lowBound=0., upBound=None, cat='Continuous')

# The objective function is added to 'prob' first
prob += 1.*x1 +1.*x2, "min x1 + x2"

# Constraints
prob += 1.*x1 + 2.*x2 == 2, "1*x1 + 2*x2 == 2"
prob += 2.*x1 + 3.*x2 == 2, "2*x1 + 3*x2 == 2"
prob += 1.*x1 + 1.*x2 == 1, "1*x1 + 1*x2 == 1"

# Solve
prob.solve()
print("Status:", LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)
print("Objective: ", value(prob.objective))

输出：

Status: Infeasible
x1 = 0.0
x2 = 1.0
Objective:  1.0