Ограниченная оптимизация в python, где одна переменная зависит от другой переменной - PullRequest
Новая
       18

Ограниченная оптимизация в python, где одна переменная зависит от другой переменной

1 голос
/ 08 мая 2019

У меня проблема с 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 (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? Или есть?Любой другой способ сделать это?

Это можно решить с помощью нелинейного решателя GRG в Excel, но я не могу найти эквивалент в Python.

1 Ответ

2 голосов
/ 08 мая 2019

Ваша проблема, по сути, является линейной, и поэтому она идеально подходит для подхода линейного программирования. Тем не менее, вы даете его решателю, не имея ни малейшего понятия о линейности проблемы, так что он непременно найдет это хитрым: он в значительной степени должен попробовать каждую возможность, которая займет много времени. Возможно, можно переписать ваши ограничения в различные формы для решателя 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

Вы можете добавить границы для x1 к x4, как вы упомянули в вопросе, но по умолчанию они будут просто неотрицательными. Итак, для 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 - ноль, а не крошечный эпсилон больше нуля.

Наконец, обратите внимание, что проблема сильно ограничена: мы можем выбрать совершенно другое решение, изменив цель. Вот решение, в котором мы просим 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)

1039 * дает * 

[255.1293488  212.60779066 163.54445436 148.67677669]
...