資源分配與生產排程

問題描述

你的工廠收到 10 張訂單，但你只有有限的機器和工時。每張訂單的利潤不同、所需工時不同、截止日期不同。如何選擇接哪些訂單才能最大化利潤？

ILP 模型

import pulp

# === 訂單資料 ===
orders = [
    {"id": "A", "profit": 500, "hours": 40, "deadline": 5},
    {"id": "B", "profit": 300, "hours": 25, "deadline": 3},
    {"id": "C", "profit": 800, "hours": 60, "deadline": 7},
    {"id": "D", "profit": 200, "hours": 15, "deadline": 2},
    {"id": "E", "profit": 600, "hours": 45, "deadline": 6},
    {"id": "F", "profit": 400, "hours": 30, "deadline": 4},
    {"id": "G", "profit": 900, "hours": 70, "deadline": 8},
    {"id": "H", "profit": 350, "hours": 20, "deadline": 3},
    {"id": "I", "profit": 700, "hours": 50, "deadline": 6},
    {"id": "J", "profit": 250, "hours": 18, "deadline": 2},
]

# === 建立問題 ===
prob = pulp.LpProblem("生產訂單選擇", pulp.LpMaximize)

# 變數：x[i] = 1 表示接受訂單 i
x = {}
for i, order in enumerate(orders):
    x[i] = pulp.LpVariable(f"x_{order['id']}", cat="Binary")

# 目標：最大化總利潤
prob += pulp.lpSum(orders[i]["profit"] * x[i] for i in range(len(orders)))

# 限制 1：每週可用工時
max_hours_per_week = 100
weeks = 4
for week in range(weeks):
    week_orders = [i for i, o in enumerate(orders) if o["deadline"] >= week + 1]
    prob += pulp.lpSum(orders[i]["hours"] * x[i] for i in week_orders) <= max_hours_per_week

# 求解
prob.solve()

print(f"求解狀態: {pulp.LpStatus[prob.status]}")
print(f"最大利潤: {pulp.value(prob.objective)}")
print(f"\n接受的訂單:")
selected = []
for i, order in enumerate(orders):
    if x[i].value() == 1:
        selected.append(order)
        print(f"  {order['id']}: 利潤 {order['profit']}, 工時 {order['hours']}, 期限 {order['deadline']}天")

print(f"\n總工時: {sum(o['hours'] for o in selected)}")
print(f"總利潤: {sum(o['profit'] for o in selected)}")