4

我需要解决一个问题。我有 5 台设备。它们都有 4 种 I/O 类型。并且有一个目标输入/输出组合。第一步，我想找到设备之间的所有组合，以便所选设备的总 I/O 数量都等于或大于目标值。让我解释：

# Devices=[numberof_AI,numberof_AO,numberof_BI,numberof_BO,price]

Device1=[8,8,4,4,200]
Device1=[16,0,16,0,250]
Device1=[8,0,4,4,300]
Device1=[16,8,4,4,300]
Device1=[8,8,2,2,150]

Target=[24,12,16,8]

也有限制。在组合中，最大。设备数量最多为 5 个。

第二步，在找到的组合中，我会选择最便宜的一个。

实际上，我设法用 Python 中的 for 循环解决了这个问题。我的工作就像一个魅力。但是即使我使用cython也需要太多时间。

对于此类问题，我还可以从哪些其他选择中受益？

4

3 回答 3

5

您可以使用像PuLP这样的线性编程包。（请注意，这还需要您安装 LP 库，如GLPK）。

以下是您将如何使用它来解决您给出的示例：

import pulp

prob = pulp.LpProblem("example", pulp.LpMinimize)

# Variable represent number of times device i is used
n1 = pulp.LpVariable("n1", 0, 5, cat="Integer")
n2 = pulp.LpVariable("n2", 0, 5, cat="Integer")
n3 = pulp.LpVariable("n3", 0, 5, cat="Integer")
n4 = pulp.LpVariable("n4", 0, 5, cat="Integer")
n5 = pulp.LpVariable("n5", 0, 5, cat="Integer")

# Device params
Device1=[8,8,4,4,200]
Device2=[16,0,16,0,250]
Device3=[8,0,4,4,300]
Device4=[16,8,4,4,300]
Device5=[8,8,2,2,150]

# The objective function that we want to minimize: the total cost
prob += n1 * Device1[-1] + n2 * Device2[-1] + n3 * Device3[-1] + n4 * Device4[-1] + n5 * Device5[-1]

# Constraint that we use no more than 5 devices
prob += n1 + n2 + n3 + n4 + n5 <= 5

Target = [24, 12, 16, 8]

# Constraint that the total I/O for all devices exceeds the target
for i in range(4):
    prob += n1 * Device1[i] + n2 * Device2[i] + n3 * Device3[i] + n4 * Device4[i] + n5 * Device5[i] >= Target[i]

# Actually solve the problem, this calls GLPK so you need it installed
pulp.GLPK().solve(prob)

# Print out the results
for v in prob.variables():
    print v.name, "=", v.varValue

运行它非常快，我得到 n1 = 2 和 n2 = 1，其他为 0。

于 2011-03-03T11:53:41.057 回答
3

只需检查所有组合。由于您只有 5 台设备，因此（最多）6^5=7776有可能（因为这五个位置中的每一个都可能未使用，您必须使用6）。然后对于每种可能性，您检查它是否符合您的标准。我不明白为什么这需要这么多时间。

下面的脚本在我的机器上不需要一秒钟就可以计算出这些东西。

d1=[8,8,4,4,200]
d2=[16,0,16,0,250]
d3=[8,0,4,4,300]
d4=[16,8,4,4,300]
d5=[8,8,2,2,150]
dummy=[0,0,0,0,0]

t=[24,12,16,8]

import itertools
def computeit(devicelist, target):
    def check(d, t):
        for i in range(len(t)):
            if sum([dd[i] for dd in d]) < t[i]:
                return False
        return True
    results=[]
    for p in itertools.combinations_with_replacement(devicelist, 5):
        if check(p, t):
            results.append(p)
    return results

print(computeit([d1,d2,d3,d4,d5,dummy],t))

需要 Python 2.7。

于 2011-03-03T11:12:32.607 回答
1

也可以使用Gustavo Niemeyer的Python 约束模块来解决这个问题。

import constraint

Device1=[8,8,4,4,200]
Device2=[16,0,16,0,250]
Device3=[8,0,4,4,300]
Device4=[16,8,4,4,300]
Device5=[8,8,2,2,150]

Target=[24,12,16,8]

devices = [Device1, Device2, Device3, Device4, Device5]
vars_number_of_devices = range(len(devices))
max_number_of_devices = 5

problem = constraint.Problem()
problem.addVariables(vars_number_of_devices, range(max_number_of_devices + 1))
problem.addConstraint(constraint.MaxSumConstraint(max_number_of_devices), vars_number_of_devices)
for io_index, minimum_sum in enumerate(Target):
    problem.addConstraint(constraint.MinSumConstraint(minimum_sum, [device[io_index] for device in devices]), vars_number_of_devices)

print min(problem.getSolutions(), key=lambda distribution: sum([how_many * devices[device][-1] for device, how_many in distribution.iteritems()]))

这会产生以下输出：

{0: 2, 1: 1, 2: 0, 3: 0, 4: 0}

因此，最优解是 2 x Device1、1 x Device2、0 x Device3、0 x Device4、0 x Device5。

（请注意，变量使用从零开始的索引命名。Device1 对应于 0，Device2 对应于 1，依此类推。）

于 2011-03-03T14:43:51.343 回答