Python组合优化：仓库产品调运最小中心访问数求解

需求与库存信息 #

• 产品需求清单（格式：{产品ID: 所需数量}）：

  center_a_products = {1: 8, 2: 4, 3: 12}
  

• 各仓库产品库存（格式：{仓库ID: {产品ID: 库存数量}}）：

  product_quantities = {1: {1: 10, 2: 3, 3: 15}, 2: {1: 5, 2: 8, 3: 10}, 3: {1: 12, 2: 6}}
  

调运规则 #

• 每次仅能访问一个仓库，但可从该仓库采集多种产品
• 若某产品的总库存小于需求数量，必须访问所有存有该产品的仓库并采集其全部库存
• 核心目标：找到访问仓库数量最少的调运组合

尝试的错误代码 #

from itertools import combinations

# 定义仓库列表
centers = [1, 2, 3]

# 定义Center A的产品需求
center_a_products = {
    1: 8,
    2: 4,
    3: 12
}

# 定义各仓库的产品库存
product_quantities = {
    1: {1: 10, 2: 3, 3: 15},
    2: {1: 5, 2: 8, 3: 10},
    3: {1: 12, 2: 6}
}

# 检查组合是否满足需求的函数
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

# 查找所有符合条件的组合
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)

# 打印所有组合
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. 直接累加仓库全部库存，未考虑可以只取部分库存的情况（除非产品总库存不足需求）
2. 收集所有符合条件的组合，但未优先返回最少仓库数量的最优解
3. 未处理规则中“总库存不足时必须取所有该产品仓库”的约束

修正代码 #

from itertools import combinations

center_a_products = {1: 8, 2: 4, 3: 12}
product_quantities = {1: {1: 10, 2: 3, 3: 15}, 2: {1: 5, 2: 8, 3: 10}, 3: {1: 12, 2: 6}}
centers = list(product_quantities.keys())

# 计算每个产品的总库存，判断是否需要取所有仓库的全部库存
product_total_stock = {}
for product in center_a_products:
    total = 0
    for center in centers:
        total += product_quantities[center].get(product, 0)
    product_total_stock[product] = total

# 标记必须取全部库存的产品
must_take_all = {p for p, total in product_total_stock.items() if total < center_a_products[p]}

def check_combination(center_list):
    collected = {p: 0 for p in center_a_products}
    # 验证必须取全部库存的产品是否覆盖了所有存有该产品的仓库
    for p in must_take_all:
        for center in centers:
            if p in product_quantities[center] and center not in center_list:
                return None
            if center in center_list:
                collected[p] += product_quantities[center].get(p, 0)
    # 计算非必须取全部的产品可采集数量
    for center in center_list:
        for p, stock in product_quantities[center].items():
            if p not in must_take_all:
                needed = center_a_products[p] - collected[p]
                if needed <= 0:
                    continue
                take = min(stock, needed)
                collected[p] += take
    # 检查是否满足所有需求
    if all(collected[p] >= center_a_products[p] for p in center_a_products):
        # 生成调运明细
        details = []
        remaining = center_a_products.copy()
        for center in center_list:
            for p, stock in product_quantities[center].items():
                if p not in remaining:
                    continue
                take = stock if p in must_take_all else min(stock, remaining[p])
                if take > 0:
                    details.append(f"Move {take} units of product {p} from Center {center}")
                    remaining[p] -= take
                    if remaining[p] == 0:
                        del remaining[p]
        return details
    return None

# 按访问仓库数量从少到多遍历，找到第一个符合条件的最优组合
for r in range(1, len(centers)+1):
    for combo in combinations(centers, r):
        result = check_combination(combo)
        if result:
            print("\n".join(result))
            exit()

# 理论上不会触发，仅做兜底
print("No valid combination found")

代码说明 #

1. 先统计每个产品的总库存，标记出必须取所有仓库全部库存的产品
2. 按访问仓库数量从1到3遍历所有组合，优先检查最少仓库的情况
3. 对每个组合，先验证必须取全部库存的产品是否覆盖了所有存有该产品的仓库
4. 计算组合能提供的产品数量，生成具体调运明细（非必须取全部的产品只取所需数量）
5. 找到第一个符合条件的组合后立即输出并退出，确保得到最优解

内容的提问来源于stack exchange，提问作者user22167296