python中的约束优化，其中一个变量依赖于另一个变量
我有一个问题，我有4个变量x1, x2, x3 and x4。我需要在满足以下条件的情况下找到x1, x2, x3, x4的值：
1. 1995 < 2*x1 + 4*x2 + 3*x3 + x4 < 2000
2. x1 >= 1.2*x2
3. x2 >= 1.3*x3
4. x3 >= 1.1*x4
5. x4 > 0.0我可以使用python-constraint (https://labix.org/python-constraint)来解决这个问题，但是在我的系统上需要大约30分钟才能解决这个问题，这太长了。
from constraint import *
problem = Problem()
problem.addVariable("x1", range(100,500))
problem.addVariable("x2", range(100,500))
problem.addVariable("x3", range(100,500))
problem.addVariable("x4", range(100,500))
problem.addConstraint(lambda a, b, c, d: 2*a + 3*b + 4*c + 5*d > 1995, ["x1", "x2", "x3", "x4"])
problem.addConstraint(lambda a, b, c, d: 2*a + 3*b + 4*c + 5*d < 2005, ["x1", "x2", "x3", "x4"])
problem.addConstraint(lambda a, b: a >= 1.2 * b, ["x1", "x2"])
problem.addConstraint(lambda b, c: b >= 1.3 * c, ["x2", "x3"])
problem.addConstraint(lambda c, d: c >= 1.1 * d, ["x3", "x4"])
problem.addConstraint(lambda d: d > 0, ["x4"])
problem.getSolutions()我还查看了scipy.optimize.linprog，但我找不到传递条件2、3和4的方法，因为它依赖于同一问题中另一个变量的值。我可以使用bounds参数传递每个单独变量的边界，如下所示：
x1_bounds = (100, 200)
x2_bounds = (200, 300)但是如何在界限中传递其他变量的值，比如x1_bounds >= 1.2*x2？或者有没有其他方法可以做到这一点？
这个问题可以用excel中的GRG非线性求解器来解决，但是我在python中找不到等价物。
回答 1
Stack Overflow用户
发布于 2019-05-08 15:49:40
你的问题实际上是线性的，所以它非常适合线性规划方法。然而，你把它交给求解器，却没有关于问题线性的线索，所以它一定会发现这很棘手:它几乎必须尝试每一种可能性，这将需要很长时间。可以将约束重写为python-constraint求解器的不同形式(例如，它具有MaxSumConstraint约束形式)，这可能会更好地工作，但理想情况下，我认为您应该使用专门用于线性问题的求解器。
有一个名为kiwisolver的求解器，它会做你想做的事情。下面是为该库转换的示例：
import kiwisolver
x1 = kiwisolver.Variable('x1')
x2 = kiwisolver.Variable('x2')
x3 = kiwisolver.Variable('x3')
x4 = kiwisolver.Variable('x4')
constraints = [1995 <= 2*x1 + 4*x2 + 3*x3 + x4,
2*x1 + 4*x2 + 3*x3 + x4 <= 2000,
x1 >= 1.2*x2,
x2 >= 1.3*x3,
x3 >= 1.1*x4,
x4 >= 0]
solver = kiwisolver.Solver()
for cn in constraints:
solver.addConstraint(cn)
for x in [x1, x2, x3, x4]:
print(x.value())这给了我们
254.49152542372883
212.07627118644066
163.13559322033896
148.30508474576254但您也可以使用标准的线性规划求解器，如scipy。你只需要将你的不平等重新组织成正确的形式。
您需要：
1. 1995 < 2*x1 + 4*x2 + 3*x3 + x4 < 2000
2. x1 >= 1.2*x2
3. x2 >= 1.3*x3
4. x3 >= 1.1*x4
5. x4 > 0.0因此，我们将其重写为：
2*x1 + 4*x2 + 3*x3 + 1*x4 < 2000
-2*x1 + -4*x2 + -3*x3 + -1*x4 < -1995
-1*x1 + 1.2*x2 + 0*x3 + 0*x4 < 0
0*x1 + -1*x2 + 1.3*x3 + 0*x4 < 0
0*x1 + 0*x2 + -1*x3 + 1.1*x4 < 0您可以像您在问题中提到的那样，向x4添加x1的界限，但默认情况下，它们将是非负的。因此，对于LP，我们还需要选择在可能的解的多面体中的什么位置进行优化:在这种情况下，我将选择具有最小和的解。这就给了我们这个：
from scipy.optimize import linprog
output = linprog([1, 1, 1, 1],
[[ 2, 4, 3, 1],
[-2, -4, -3, -1],
[-1, 1.2, 0, 0],
[0, -1, 1.3, 0],
[0, 0, -1, 1.1]],
[2000, -1995, 0, 0, 0])
print(output.x)这给了我们
[274.92932862 229.10777385 176.23674912 0. ]这是最优的LP解决方案。注意，它使得x4 = 0：LP通常不区分>和>=，因此我们有一个解决方案，其中x4是零，而不是一个大于零的小epsilon。
最后，注意这个问题是强欠约束的:我们可以通过改变目标来选择一个完全不同的解决方案。这是一个让linprog最大化2*x1 + 4*x2 + 3*x3 + x4的解决方案
from scipy.optimize import linprog
output = linprog([-2, -4, -3, -1],
[[ 2, 4, 3, 1],
[-2, -4, -3, -1],
[-1, 1.2, 0, 0],
[0, -1, 1.3, 0],
[0, 0, -1, 1.1]],
[2000, -1995, 0, 0, 0])
print(output.x)给予
[255.1293488 212.60779066 163.54445436 148.67677669]https://stackoverflow.com/questions/56042803
复制
腾讯云开发者
