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

我已经尝试过pulp和linprog库（from scipy.optimize import linprog），但是我没有任何进展。第一点是，这两个库都希望我输入某种“目标函数”来最小化，而我希望最小化我的变量本身（这意味着要验证我没有太多的解决方案）。但是，我试图最小化以下目标函数：

x1 + x2

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

^{pr2}$

以及

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!)

需要的其他信息：

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.

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

去检查设置了什么属性。（我不展示这些，因为我的scipy安装有点定制了一些私人调试打印）

现在给你一些建议：

• 不信任scipy.linprog(method='simplex')
  • 如果你不信任我：查找github问题或搜索
  • （如果没有人修复这个函数，我早就反对了）
• {cd2>尝试^
  • 如果你能接受非单纯形的方法
  • 如果scipy>；=1.0
• 与scipy相比，Coin的pulp带来了一个非常先进的LP解算器（Clp，偏爱单纯形），并且正确使用它，它不会在这里为您的问题输出错误的状态消息！
  • 在我看来，Clp是最先进的开源LP解算器
• 如果没有目标：将目标向量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求解器，应该永远在问题不可行时返回一个成功的解决方案（这不是说问题不可行！）。在

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

只有破碎的解算器linprog(method='simplex')在这里可能很麻烦。在

（以上对于不意味着数值问题的问题是有效的，使用有限内存浮点数学总是有可能的；除了可能是专门的rational类型解算器。这甚至适用于最先进的商业解决方案，对您的问题来说并不重要）

编辑：使用Coin的方法pulp：

^{pr2}$

输出：

^{3}$