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 です。

2 番目のステップでは、見つかった組み合わせの中から最も安いものを選びます。

実際、この問題は Python の for ループで解決できました。私は魔法のように働きます。しかし、cython を使っているのに時間がかかりすぎます。

この種の問題に対して、他にどのようなオプションを利用できますか?

4

3 に答える 3

5

PuLPのような線形計画法パッケージを使用できます。（これには、 GLPKなどのLPライブラリもインストールする必要があることに注意してください）。

与えた例を解決するためにそれをどのように使用するかを次に示します。

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可能性があります (5 つの位置のそれぞれが使用されていない可能性があるため、使用する必要があります6)。次に、それぞれの可能性について、それが基準を満たすかどうかを確認します。なぜこれにそんなに時間がかかるのかわかりません。

次のスクリプトは、私のマシンで計算するのに 1 秒もかかりません。

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 Constraintモジュールを使用して、この問題を解決することもできます。

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 です。

(変数は、0 から始まるインデックスを使用して名前が付けられていることに注意してください。Device1 は 0 に対応し、Device2 は 1 に対応します。)

于 2011-03-03T14:43:51.343 に答える