Комбинированная оптимизация в Python
Мне нужно собрать продукты со складских центров для комплектации продуктов
вот так {продукт:количество}
center_a_products = {1: 8, 2: 4, 3: 12}
Каждый центр имеет различные виды и количество продуктов
вот так {center:{product:quantity}} product_quantities = {1: {1: 10, 2: 3, 3: 15}, 2: {1: 5, 2: 8, 3: 10}, 3: {1: 12, 2: 6}}
Я могу посещать только один центр за раз, но я могу получить несколько товаров из одного центра.
Если общее количество какого-либо продукта меньше center_a_products, я должен посетить каждый центр, содержащий этот продукт, и собрать общее количество этого продукта.
Есть много комбинаций, соответствующих этим условиям, но мне нужно знать наиболее эффективную комбинацию, которая посещает наименьшее количество центров.
Я пробовал это, но это не удалось...
from itertools import combinations
# Define the centers
centers = [1, 2, 3]
# Define the products and quantities needed in Center A
center_a_products = {
1: 8,
2: 4,
3: 12
}
# Define the products and quantities for each center
product_quantities = {
1: {1: 10, 2: 3, 3: 15},
2: {1: 5, 2: 8, 3: 10},
3: {1: 12, 2: 6}
}
# Function to check if a product combination meets the requirements
def meets_requirements(combination):
product_counts = {product: 0 for product in center_a_products.keys()}
for center, products in combination:
for product, quantity in products.items():
product_counts[product] += quantity
for product, required_quantity in center_a_products.items():
if product_counts[product] < required_quantity:
return False
return True
# Find all combinations of products
combinations_to_move = []
for r in range(1, len(centers) + 1):
for combination in combinations(zip(centers, [product_quantities[c] for c in centers]), r):
if meets_requirements(combination):
combinations_to_move.append(combination)
# Print the combinations
for idx, combination in enumerate(combinations_to_move, start=1):
print(f"Combination {idx}:")
for center, products in combination:
for product, quantity in products.items():
print(f"Move {quantity} units of product {product} from Center {center}")
Я ожидал чего-то подобного
Move 8 units of product 1 from Center 1
Move 3 units of product 2 from Center 1
Move 12 units of product 3 from Center 1
Move 1 units of product 3 from Center 2
Спасибо, что дали мне знать! буду переделывать!
Я не понимаю, в чем сложность для примера, который вы привели. центр А - это то, что вам нужно, и количество на разных складах? Для примера, который вы предоставили, просто перейдите в центр 1, у него есть все как 10> 8, 5> 4 и 15> 12. пожалуйста, предоставьте более сложный пример и ожидаемый результат
похоже, вы решаете вариант задачи коммивояжера
Это просто, потому что это образец данных, мой фактический центр, продукт, количество намного сложнее
Ответы 1
Описание проблемы поддается решению с помощью Смешанной целочисленно-линейной программы (MIP).
Удобная библиотека для решения смешанных целочисленных задач — PuLP , которая поставляется со встроенным набором Coin-OR и, в частности, целочисленным решателем CBC.
Сформулируем модель, описывающую вашу проблему:
import pulp
center_a_products = {
1: 8,
2: 4,
3: 12
}
product_quantities = {
1: {1: 10, 2: 5, 3: 15},
2: {1: 5, 2: 8, 3: 10},
3: {1: 12, 2: 6, 3: 20}
}
problem = pulp.LpProblem("CenterSatisfactionProblem", pulp.LpMinimize)
# Center vars are binary variables that we minimize in the objective. They indicate whether a center was visited or not
center_vars = {center: pulp.LpVariable(f"Center_{center}", cat = "Binary") for center in product_quantities}
product_vars = {(center, product): pulp.LpVariable(f"Center_{center}_Product_{product}", lowBound=0, cat = "Integer")
for center in product_quantities
for product in product_quantities[center]}
# Satisfy all demand
for product in center_a_products:
problem += pulp.lpSum(product_vars[center, product] for center in product_quantities) == center_a_products[product]
# We can only take stuff from a center if we visit it
# Also: can't take more stuff from a center than is in stock
for center in product_quantities:
for product in product_quantities[center]:
problem += product_vars[center, product] <= center_vars[center] * product_quantities[center][product]
# Minimize amount of centers visited
problem += pulp.lpSum(center_vars.values())
problem.solve()
Решение для печати:
for center in product_quantities:
if center_vars[center].varValue == 1:
for product in product_quantities[center]:
quantity = product_vars[center, product].varValue
if quantity > 0:
print(f"Move {quantity} units of product {product} from center {center}")
Выход:
Move 8.0 units of product 1 from center 3
Move 4.0 units of product 2 from center 3
Move 12.0 units of product 3 from center 3
В настоящее время приведенный вами пример довольно тривиален. Легко можно добавить дополнительные ограничения, но вам необходимо предоставить более точное описание проблемы и ожидаемого результата.
Преобразование описания проблемы в линейную программу может потребовать некоторой практики. Самая сложная строка в этой программе
problem += product_vars[center, product] <= center_vars[center] * product_quantities[center][product]
Цель минимизирует center_vars, но ограничение удовлетворения заставляет некоторые из них быть равными 1.
Чтобы научиться описывать проблемы, а не думать о решениях, я рекомендую отличный доклад Рэймонда Хеттингера на PyCon 2019 — Современные решатели: четко определенные проблемы — это решенные проблемы
установить PuLP
pip install pulp
Я действительно не могу выразить свою благодарность достаточно. Ваш код значительно облегчил мою работу, и за это я безмерно благодарен. Ваша поддержка и руководство очень ценятся. Желаем вам фантастического дня впереди!
Если код был сгенерирован ChatGPT, имейте в виду, что публикация такого контента (не только ответов) в настоящее время не разрешена