Выберите один и тот же предмет несколько раз в задаче о ранце [мякоть] - PullRequest
Новая
       51

Выберите один и тот же предмет несколько раз в задаче о ранце [мякоть]

0 голосов
/ 16 марта 2019

Я делаю курс курс дискретной оптимизации , который в рамках курса называется инструментом Minizinc для решения проблем.

Я хочу перевести примеры классов в python, начиная с этого:

enter image description here Я использую этот пример кода для воспроизведения результатов: 

v = {'hammer':6, 'wrench':10, 'screwdriver':8, 'towel':40}
w = {'hammer':13, 'wrench':21, 'screwdriver':17, 'towel':100}
q = {'hammer':1000, 'wrench':400, 'screwdriver':500, 'towel':150}
limit = 1000
items = list(sorted(v.keys()))

# Create model
m = LpProblem("Knapsack", LpMaximize)

# Variables
x = LpVariable.dicts('x', items, lowBound=0, upBound=1, cat=LpInteger)

# Objective
m += sum(v[i]*x[i] for i in items)

# Constraint
m += sum(w[i]*x[i] for i in items) <= limit


# Optimize
m.solve()

# Print the status of the solved LP
print("Status = %s" % LpStatus[m.status])

# Print the value of the variables at the optimum
for i in items:
    print("%s = %f" % (x[i].name, x[i].varValue))

# Print the value of the objective
print("Objective = %f" % value(m.objective))

Но это дает неправильный ответ, поскольку берется только один из них.Как я могу добавить сумму, доступную для каждого элемента (dict q) в ограничения?

1 Ответ

2 голосов
/ 19 марта 2019

Вам нужно сделать два очень небольших изменения в вашем коде. Во-первых, вам нужно удалить верхнюю границу, которую вы установили для переменных x. На данный момент у вас есть двоичные переменные x[i], которые могут быть только одна или ноль.

Во-вторых, вам нужно добавить ограничения, которые эффективно устанавливают пользовательскую верхнюю границу для каждого из элементов. Рабочий код и полученное решение приведены ниже - как вы видите, выбраны несколько ключей (самое высокое соотношение v/w) с помощью одного молотка для заполнения небольшого оставшегося пространства. 

from pulp import *
v = {'hammer':6, 'wrench':10, 'screwdriver':8, 'towel':40}
w = {'hammer':13, 'wrench':21, 'screwdriver':17, 'towel':100}
q = {'hammer':1000, 'wrench':400, 'screwdriver':500, 'towel':150}
limit = 1000
items = list(sorted(v.keys()))

# Create model
m = LpProblem("Knapsack", LpMaximize)

# Variables
x = LpVariable.dicts('x', items, lowBound=0, cat=LpInteger)

# Objective
m += sum(v[i]*x[i] for i in items)

# Constraint
m += sum(w[i]*x[i] for i in items) <= limit

# Quantity of each constraint:
for i in items:
    m += x[i] <= q[i]


# Optimize
m.solve()

# Print the status of the solved LP
print("Status = %s" % LpStatus[m.status])

# Print the value of the variables at the optimum
for i in items:
    print("%s = %f" % (x[i].name, x[i].varValue))

# Print the value of the objective
print("Objective = %f" % value(m.objective))
print("Total weight = %f" % sum([x[i].varValue*w[i] for i in items]))

Что возвращает:

Статус = Оптимальный 

x_hammer = 1.000000
x_screwdriver = 0.000000
x_towel = 0.000000
x_wrench = 47.000000
Objective = 476.000000
Total weight = 1000.000000
...