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上，总功率将是4700 W。

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

**obs:真正的数据可以有1到2k左右的机器。

我能用LP解决这个问题吗？我怎样才能把这个问题设想成能够解决它呢？

我已经尝试过的事情：

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

2)我试图强行生成所有可能的排列，并生成一个大的查找表，但是机器和状态的变化太频繁，所以这不是一个有效的解决方案。

3)当前实现启动状态1上的所有机器，并减少一台机器，按状态从低到高对所有状态进行排序。它运行得相当快，但有时结果并不理想。

最新情况(03/30)

如果不清楚的话，我的目标是为每台机器计算一组状态，以便将它们的功率与设定的目标之间的差异降到最小。

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

​

​

因此，如果我想在最大功率为3000的情况下操作这两台机器(1和2)，我需要在状态1下操作，因为状态的最大功率是2500。

如果我想以2300的最大功率操作这两台机器(1和2)，我需要在状态2处操作机器1，在状态1处操作机器1。

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

Answer 1

下面是一种使用简单的MIP模型并用纸浆求解的方法：

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