Pulp Python LP - 错误的解决方案

Question

当我运行下面的代码：

from pulp import * 

x = pulp.LpVariable("x", 0, None , LpContinuous) 
y = pulp.LpVariable("y", 0, None , LpContinuous)
problem = pulp.LpProblem("A simple max problem", pulp.LpMinimize) 
problem += x + y, "The objective function" 
problem += x + 2*y == 2, "1st constraint"
problem += 2*x + 3*y == 2, "2nd constraint"
problem += x >= 0, "3rd constraint"
problem += y >= 0, "4th constraint"
problem += x + y == 1, "5th constraint"

problem.writeLP("WhiskasModel.lp")
problem.solve()

for variable in problem.variables():
    print variable.name, "=", variable.varValue

print value(problem.objective)

我得到输出：

x = 0.0
y = 1.0
1.0

这显然是错误的，因为不满足第二个约束条件。现在的情况是上面的问题没有解决办法。所以我希望 pulp 能通知我一些相关的 ("Infeasible problem") 或类似的东西。相反，我怀疑它会任意删除一些约束并与其余约束一起使用。在以下情况下类似：

x = pulp.LpVariable("x", 0, None , LpContinuous) 
y = pulp.LpVariable("y", 0, None , LpContinuous)
problem = pulp.LpProblem("A simple max problem", pulp.LpMinimize) 
problem += x + y, "The objective function" 
problem += x + 2*y == 2, "1st constraint"
problem += 2*x + 3*y == 20, "2nd constraint"
problem += x >= 0, "3rd constraint"
problem += y >= 0, "4th constraint"
problem += x + y == 1, "5th constraint"

problem.writeLP("WhiskasModel.lp")
problem.solve()

for variable in problem.variables():
    print variable.name, "=", variable.varValue

print value(problem.objective)

输出是

x = 34.0
y = -16.0
18.0

即第 4 个约束现在是 "dropped".

有人知道如何解决这个问题吗？

Answer 1

您的程序将尝试自行求解，从第一个约束向下。

从线性代数的角度来看，增广矩阵为：

[ 1 2 | 2
  2 3 | 20
  1 1 | 1 ]

进一步限制两个变量都应 >=0。直接从第二行中减去第一行的两倍，您将得到：

[ 1 2  | 2
  0 -1 | 16
  .........]

换句话说，为了满足你的第一个约束，你强制你的 y 变量变成 -16，唯一可能的解决方案。结果 x 变量变为 34 以求解第一行。所有进一步的约束和 objective 函数都不再重要。这是唯一可能的解决方案。

你想要的是如果问题没有满足所有约束的解决方案，系统会警告你。目前这还没有在包中实现，看到 Git，他们不打算改变这种行为，所以如果你想收到关于不可行问题的警告，请更改包。

如果您不想更改包，您可以从违反约束的解决方案中看出您的问题是不可行的。可以自己写一段代码抛出一个warning/exception。

Answer 2

正如您所说：重要的是检查数学优化问题是否可行。 Pulp 包含此功能。

包括：

if (problem.status == -1):
     print("Your problem is infeasible!")

在你的代码中，你会看到。

Pulp Python LP - 错误的解决方案

Pulp Python LP - Wrong Solution

python

linear-programming