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

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

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

введите здесь описание изображения Я использую этот пример кода для воспроизведения результатов:

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), в ограничения?


python optimization linear-programming pulp
person Luis Ramon Ramirez Rodriguez    schedule 16.03.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вам нужно внести два очень маленьких изменения в свой код. Во-первых, вам нужно удалить верхнюю границу, которую вы установили для своих 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
person kabdulla    schedule 18.03.2019