Python Значение оптимизации - LP, Geneti c алгоритм? - PullRequest
Новая
       7

Python Значение оптимизации - LP, Geneti c алгоритм?

0 голосов
/ 27 марта 2020

Надеюсь, что все в порядке и в безопасности дома!

У меня есть следующая проблема:

Количество "N" машин, и каждая машина может иметь число "М" состояний. Каждый штат имеет разный уровень мощности. Моя цель - подсчитать, в каком состоянии должна быть установлена ​​каждая машина, чтобы она находилась ниже порога загрузки.

Например, предположим, что у меня 5 разных машин и следующие состояния: 

+---------+---------+---------+---------+---------+
| Machine | State 1 | State 2 | State 3 | State 4 |
+---------+---------+---------+---------+---------+
|       1 |    1000 |     600 |     400 | 50      |
|       2 |    1500 |     800 |     500 | 60      |
|       3 |    1000 |     500 |     400 | 50      |
|       4 |     500 |     300 |     100 | ----    |
|       5 |     700 |     600 |     100 | ----    |
+---------+---------+---------+---------+---------+

** обратите внимание, что машины 4 и 5 не имеют состояния 4

Если предположить, что все работает в состоянии 1, общая мощность будет 4700 Вт.

Но, допустим, я хочу падение 700 Вт, поэтому новая рабочая мощность должна быть <= 4000 Вт. Конечно, есть много возможных решений, я могу управлять машиной 3 и 4 в состоянии 2 или работать только машиной 2 в состоянии 2, мне действительно все равно, какое решение я получу (пока), но мне нужно рассчитать это БЫСТРЫЙ! </p>

** obs: реальные данные могут содержать от 1 до 2 тыс. Машин.

Можно ли решить эту проблему с помощью LP? Как я могу сформулировать эту проблему, чтобы иметь возможность ее решить?

То, что я уже пробовал:

1) Я реализовал алгоритм geneti c, чтобы решить эту проблему, но производительность была действительно низкой, потребовались минуты, чтобы решить проблему, возможно, у меня была плохая реализация, может быть, это было количество переменных.

2) Я пытался использовать грубую силу и генерировать все возможные перестановки и генерировать большую таблицу поиска, но машины и состояние может меняться слишком часто, так что это недопустимое решение.

3) Текущая реализация запускает все машины в состоянии 1 и уменьшает состояние машины, изменяя состояние по всем состояниям. Он работает довольно быстро, но иногда результат не оптимален.

Обновление (03/30)

Моя цель, если неясно, состоит в том, чтобы вычислить набор состояний для каждой машины. чтобы минимизировать разницу между их мощностью и ЦЕЛЕМ НАСТРОЙКИ.

Для примера выше, если я нанесу на график возможные состояния и общую мощность, я получу что-то вроде этого:

enter image description here

Итак, если я хочу использовать обе машины (1 и 2) с максимальной мощностью 3000, мне нужно работать с обеими в состоянии 1, поскольку максимальная мощность этого состояния составляет 2500 .

Если я хочу, чтобы обе машины (1 и 2) работали на максимальной мощности 2300, мне нужно задействовать машину 1 в состоянии 2 и машину 1 в состоянии 1.

Другими словами Мне нужно быть под установленной нагрузкой и максимально возможной мощностью.

1 Ответ

0 голосов
/ 30 марта 2020

Вот один подход, использующий простую модель MIP и решающий с помощью PULP: 

from pulp import *

# DATA
power = [
    [1000, 600, 400, 50], 
    [1500, 800, 500, 60], 
    [1000, 500, 400, 50], 
    [500, 300, 100, 0], 
    [700, 600, 100, 0]]
target_power = 2500
max_machines = 3

# VARIABLES
N = range(len(power))
S = range(len(power[0]))
x = [[pulp.LpVariable("x_" + str(i) + "_" + str(j), 0, 1, 'Binary') for j in S] for i in N]

# OBJECTIVE
prob = LpProblem("Power problem", LpMinimize)
prob += target_power - lpSum([power[i][j]*x[i][j] for j in S for i in N])

# CONSTRAINTS
# Limit total power
prob += lpSum([power[i][j]*x[i][j] for j in S for i in N]) <= target_power      

# At most one state active for each machine
for i in N:
    prob += lpSum([x[i][j] for j in S]) <= 1

# Max. total active machines
prob += lpSum(x) <= max_machines

# SOLVE & SHOW RESULTS
prob.solve()
print(LpStatus[prob.status])
print('obj = ' + str(value(prob.objective)))
print('power = ' + str(target_power - value(prob.objective)))

for i in N:
    state = sum((j+1)*x[i][j].varValue for j in S)
    if state > 0: 
        print('Machine %s = %d' %(i+1, state))

Результат будет показан как: 

Optimal
obj = 0.0
power = 2500.0
Machine 1 = 3
Machine 2 = 1
Machine 5 = 2
...