Python中的优化问题 [英] Optimization problem in Python

问题描述

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

I need to solve a problem. I have 5 devices. They all have 4 kind of I/O types. And there is a target input/output combination. At first step, I want to find all combinations among the devices so that the total I/O number of selected devices are all equal or greater than the target values. Let me explain:

# 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个.

There are constraints as well. In combinations, max. number of devices can be 5 at most.

第二步，在找到的组合中，我选择最便宜的组合.

At the second step, among the combinations found, I will pick the cheapest one.

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

Actually, I managed to solve this problem with for loops in Python. I works like a charm. But it takes too much time even though I use cython.

对于这种问题，我还可以从其他哪些选项中受益?

What other options can I benefit from for this kind of problem?

推荐答案

您可以使用线性编程程序包，例如 PulP . (请注意，这还要求您安装LP库，例如 GLPK ).

You can use a linear programming package like PuLP. (note this also requires you to install an LP library like GLPK).

在这里，您将使用它来解决您给出的示例:

Here's how you would use it to solve the example you gave:

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.

Running this is extremely fast, and I get that n1 = 2 and n2 = 1 and the others are 0.

这篇关于Python中的优化问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！