Python - 无法解决LP
Python - Can not solve LP
我已经尝试了一段时间来解决 Python 中的以下线性问题：
minimize{x1,x2}, such that:
x1+2*x2 = 2
2*x1+3*x2 =2
x1+x2=1
x1>=0
x2>=0
我已经尝试了 pulp 和 linprog 库 (from scipy.optimize import linprog)，但我没有任何进展。第一点是，这两个库都希望我输入某种 "objective function" 来最小化，而我正在寻求最小化我的变量（本质上是为了验证我没有无限多的解决方案）。但是，我尝试最小化以下 objective 函数：
x1 + x2
判断这几乎等于最小化 x1 和 x2，因为它们都大于 0。第二点是 pulp 和 linprog 似乎都无法处理 "Infeasible" 情况。这意味着当这两个库都遇到一个不可行的问题时，他们不会打印出相关的东西（即："problem can not be solved"），而是开始放弃约束直到他们得到答案。例如，上述问题是不可行的，因为不存在满足上述所有方程的数 x1 和 x2。现在 linprog 在这种情况下打印出以下内容
message: 'Optimization terminated successfully.'
和
x: array([ 0., 0.])
据我了解解是x1=0和x2=0，当然是不正确的
我的下一步是用嵌套的 for 循环和条件语句自己编写所有代码来描述约束，但我还不想去那里。此外，我正在寻找一个可以轻松推广的解决方案，比如 100 多个不同的方程（因为我将在实数的 n 维空间中做一些事情）和 60 多个变量（x1，x2，...， x60）。
这是微不足道的，我不明白为什么你在遇到问题时没有显示任何代码：
代码：
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!)
需要更多信息：
bounds : sequence, optional
(min, max) pairs for each element in x, defining the bounds on that parameter.
Use None for one of min or max when there is no bound in that direction. By default bounds are (0, None) (non-negative) If a sequence containing a single tuple is provided, then min and max will be applied to all variables in the problem.
None 这些运行将输出 status=success！ （并且设置了对应于某些退出状态的标志）
去检查设置了哪些属性。 （我没有显示这些，因为我的 scipy-install 是用一些私人调试打印定制的）
现在提点建议：
- 不信任
scipy.linprog(method='simplex')
- 如果你不相信我：查找 github-issues 或搜索 SO
- （我早就弃用了该功能；如果没有人修复它）
- 尝试
scipy.linprog(method='interior-point')
- 如果您可以接受非单纯形方法
- 如果你有 scipy >= 1.0
- Coin的pulp brings, compared to scipy, a very very advanced LP-solver (Clp，偏向Simplex)，正确使用，不会为你的问题在这里输出错误的状态信息！
- Clp 在我看来是最先进的开源 LP 求解器
- 如果您没有 objective：将 objective 向量
c 设置为零！
而且要清楚
This means that when both these libraries come in front to an infeasible problem, instead of printing out something relevant (i.e.: "problem can not be solved"), they instead start dropping constraints till they get an answer. For example, the above problem is infeasible, since there are no such numbers x1 and x2 that satisfy all the above equations.
没有！。当问题不可行时，没有 LP 求解器应该 return 成功解决（这与说问题不可行不同！）。
此外，大多数 LP 求解器都支持不可行性检测（所有单纯形求解器；不是所有类似 IPM 的求解器，但 scipy 的求解器）并且会 return 可行性证明问题不可行！
只有损坏的求解器 linprog(method='simplex') 在这里可能会很麻烦。
（以上适用于不暗示数值问题的问题，使用有限内存浮点数学总是可能的；除了可能是专门的有理型求解器。这甚至适用于最先进的商业求解器，这对你的问题并不重要）
编辑：使用 Coin 的方法 pulp:
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
我已经尝试了一段时间来解决 Python 中的以下线性问题：
minimize{x1,x2}, such that:
x1+2*x2 = 2
2*x1+3*x2 =2
x1+x2=1
x1>=0
x2>=0
我已经尝试了 pulp 和 linprog 库 (from scipy.optimize import linprog)，但我没有任何进展。第一点是，这两个库都希望我输入某种 "objective function" 来最小化，而我正在寻求最小化我的变量（本质上是为了验证我没有无限多的解决方案）。但是，我尝试最小化以下 objective 函数：
x1 + x2
判断这几乎等于最小化 x1 和 x2，因为它们都大于 0。第二点是 pulp 和 linprog 似乎都无法处理 "Infeasible" 情况。这意味着当这两个库都遇到一个不可行的问题时，他们不会打印出相关的东西（即："problem can not be solved"），而是开始放弃约束直到他们得到答案。例如，上述问题是不可行的，因为不存在满足上述所有方程的数 x1 和 x2。现在 linprog 在这种情况下打印出以下内容
message: 'Optimization terminated successfully.'
和
x: array([ 0., 0.])
据我了解解是x1=0和x2=0，当然是不正确的
我的下一步是用嵌套的 for 循环和条件语句自己编写所有代码来描述约束，但我还不想去那里。此外，我正在寻找一个可以轻松推广的解决方案，比如 100 多个不同的方程（因为我将在实数的 n 维空间中做一些事情）和 60 多个变量（x1，x2，...， x60）。
这是微不足道的，我不明白为什么你在遇到问题时没有显示任何代码：
代码：
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!)
需要更多信息：
bounds : sequence, optional
(min, max) pairs for each element in x, defining the bounds on that parameter. Use None for one of min or max when there is no bound in that direction. By default bounds are (0, None) (non-negative) If a sequence containing a single tuple is provided, then min and max will be applied to all variables in the problem.
None 这些运行将输出 status=success！ （并且设置了对应于某些退出状态的标志）
去检查设置了哪些属性。 （我没有显示这些，因为我的 scipy-install 是用一些私人调试打印定制的）
现在提点建议：
- 不信任
scipy.linprog(method='simplex')- 如果你不相信我：查找 github-issues 或搜索 SO
- （我早就弃用了该功能；如果没有人修复它）
- 尝试
scipy.linprog(method='interior-point')- 如果您可以接受非单纯形方法
- 如果你有 scipy >= 1.0
- Coin的pulp brings, compared to scipy, a very very advanced LP-solver (Clp，偏向Simplex)，正确使用，不会为你的问题在这里输出错误的状态信息！
- Clp 在我看来是最先进的开源 LP 求解器
- 如果您没有 objective：将 objective 向量
c设置为零！
而且要清楚
This means that when both these libraries come in front to an infeasible problem, instead of printing out something relevant (i.e.: "problem can not be solved"), they instead start dropping constraints till they get an answer. For example, the above problem is infeasible, since there are no such numbers x1 and x2 that satisfy all the above equations.
没有！。当问题不可行时，没有 LP 求解器应该 return 成功解决（这与说问题不可行不同！）。
此外，大多数 LP 求解器都支持不可行性检测（所有单纯形求解器；不是所有类似 IPM 的求解器，但 scipy 的求解器）并且会 return 可行性证明问题不可行！
只有损坏的求解器 linprog(method='simplex') 在这里可能会很麻烦。
（以上适用于不暗示数值问题的问题，使用有限内存浮点数学总是可能的；除了可能是专门的有理型求解器。这甚至适用于最先进的商业求解器，这对你的问题并不重要）
编辑：使用 Coin 的方法 pulp:
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