Python 价值优化 - LP，遗传算法？

Question

希望大家平安回家！

我遇到以下问题：

多个"N"台机器，每台机器可以有多个"M"个状态。每个州都有不同的功率级别。我的目标是计算每台机器需要设置在什么状态下才能达到负载阈值。

例如，假设我有 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 上运行，则总功率为 4700W。

但是假设我要降700W，那么新的运行需要<=4000W。当然有很多可能的解决方案，我可以在状态 2 上操作机器 3 和 4，或者只在状态 2 上操作机器 2，我真的不在乎我得到什么解决方案（目前）但我需要计算这个快速地！

**obs：真实数据大概有1到2k台机器。

我可以用 LP 解决这个问题吗？我怎样才能解决这个问题？

我已经尝试过的事情：

1) 我实现了一个遗传算法来解决这个问题，但是性能真的很差，解决这个问题需要几分钟，也许我实现不好，也许是变量的数量。

2) 我尝试暴力破解并生成所有可能的排列并生成大量查找 table，但是机器和状态可能会经常更改，因此这不是一个有效的解决方案。

3) 当前实现在状态 1 上启动所有机器，并减少一台机器，逐个状态对所有状态从低到高排序。运行相当快，但有时结果不是最佳的。

更新 (03/30)

我的目标（如果不清楚的话）是为每台机器计算一组状态，以最小化它们的功率与 SET TARGET 之间的差异。

对于上面的示例，如果我绘制可能的状态和总功率，我会得到如下结果：

所以如果我想以 3000 的最大功率运行两台机器（1 和 2），我需要在状态 1 下运行它们，因为该状态的最大功率是 2500。

如果我想以 2300 的最大功率操作两台机器（1 和 2），我需要在状态 2 下操作机器 1，在状态 1 下操作机器 1。

换句话说，我需要在设定的负载下，并且在最大可能的功率下。

Answer 1

这是一种使用简单 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

Python 价值优化 - LP，遗传算法？

Python Value Optimization - LP, Genetic algorithm?

python

algorithm

numpy

optimization

linear-programming

我已经尝试过的事情：

更新 (03/30)