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。第二点是，纸浆和林普似乎都无法处理“不可行”的案件。这意味着，当这两个库都出现一个不可行的问题时，而不是打印一些相关的东西(即：“问题无法解决”)，而是开始放弃约束，直到得到答案。例如，上面的问题是不可行的，因为没有满足上述所有方程的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中的每个元素，定义该参数的界。当在该方向上没有约束时，使用None作为最小或最大值之一。默认情况下，如果提供了包含单个元组的序列，则的界为(0，None) (非负)，那么min和max将应用于问题中的所有变量。

，所有这些运行都不会输出status=success！(设置了与某些退出状态对应的标志)。

去检查设置了哪些属性。(我没有显示这些，因为我的bit install是用一些私有的调试打印来定制的)

现在有几句忠告：

• 不要相信scipy.linprog(method='simplex')
  • 如果你不信任我:查找github-问题或搜索
  • (我早就不赞成这一职能了，如果没有人来修理的话)

​

• 试试scipy.linprog(method='interior-point')
  • 如果你能接受一种非单纯的方法
  • 如果你有>= 1.0

​

• 与之相比，硬币的纸浆带来了一个非常先进的LP-解决程序(中电，偏袒Simplex)并正确使用它，它不会为您的问题输出错误的状态信息！
  • 在我看来，中电是最先进的开源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