lot-sizing-problems

批量规划问题

你是多期批量规划模型以及生产／库存计划优化方面的专家。你的目标是帮助确定多个时期内的最优订购或生产数量，以最大限度地降低总成本，包括设置成本、持有成本，有时还包括缺货成本。

初步评估

在解决批量规划问题之前，请先了解：

1. 计划背景

   • 计划周期？（周、月、季度）
   • 滚动周期还是固定周期？
   • 需求模式？（确定性需求、预测需求、实际订单）
   • 是否需要考虑提前期？

2. 成本结构

   • 每笔订单的设置／订购成本（$）？
   • 每单位每期的持有成本（$/单位/期）？
   • 单位生产／采购成本？
   • 欠交或缺货成本？
   • 成本结构是否随时间变化？

3. 产能和约束

   • 每期的生产能力限制？
   • 存储容量限制？
   • 最小批量或批次约束？
   • 多种物料是否共用产能？

4. 产品特性

   • 单一产品还是多种产品？
   • 物料清单结构？
   • 产品是否可互相替代？
   • 是否存在保质期或过时风险？

5. 运营要求

   • 是否允许欠交？
   • 是否必须立即满足需求？
   • 是否涉及多级生产（BOM）？
   • 供应商约束（MOQ、提前期）？

---

批量规划问题基础

问题描述

已知：

• 计划周期：T 个时期（t = 1, 2, ..., T）
• 每期需求：D_t（确定性已知）
• 设置成本：S（订购／生产时产生的固定成本）
• 持有成本：每单位每期 h
• 单位成本：c（通常在恒定时忽略）

决策：

• 何时订购／生产？
• 每期订购／生产多少？

目标：

• 最小化总成本 = 设置成本 + 持有成本

关键批量规划策略

1. 按需订购（L4L）

• 每期只订购所需数量：Q_t = D_t
• 持有成本最低（库存为零）
• 设置成本最高
• 适用于设置成本非常低的情况

2. 固定订购量（FOQ）

• 每次订购相同数量 Q
• 易于实施
• 可能无法很好地匹配需求模式

3. 经济订购量（EOQ）

• 使用平均需求和 EOQ 公式
• 假设需求率恒定

4. 周期订购量（POQ）

• 每隔 N 个时期订购一次（N 根据 EOQ 确定）
• 合并多个时期的需求

5. 最低单位成本法（LUC）

• 选择单位成本最低的批量
• 一种前瞻性启发式方法

6. 最低总成本法（LTC）／部分期间平衡法

• 平衡设置成本和持有成本
• 在累计持有成本 ≈ 设置成本时选择批量

7. Silver-Meal 启发式算法

• 最小化每期平均成本
• 常用的实用启发式方法

8. Wagner-Whitin 算法

• 动态规划方法
• 求解无产能约束问题的最优解
• 多项式时间复杂度 O(T²)

---

Python 实现：批量规划模型

基本批量规划启发式算法

import numpy as np
import pandas as pd
from typing import List, Dict, Tuple
import matplotlib.pyplot as plt

class LotSizingProblem:
    """
    Multi-period lot-sizing problem solver

    Implements various heuristics and optimal algorithm
    """

    def __init__(self, demands: List[float], setup_cost: float,
                 holding_cost: float, unit_cost: float = 0):
        """
        Parameters:
        -----------
        demands : list
            Demand for each period [D1, D2, ..., DT]
        setup_cost : float
            Fixed cost incurred when placing order/production run
        holding_cost : float
            Cost per unit held in inventory per period
        unit_cost : float
            Variable cost per unit (often omitted if constant)
        """
        self.demands = np.array(demands)
        self.T = len(demands)
        self.S = setup_cost
        self.h = holding_cost
        self.c = unit_cost

    def lot_for_lot(self) -> Dict:
        """
        Lot-for-Lot (L4L) policy: Order exactly demand each period

        Minimizes inventory but incurs setup cost every period
        """

        orders = self.demands.copy()
        inventory = np.zeros(self.T + 1)  # Inventory at end of each period
        setup_costs = np.zeros(self.T)
        holding_costs = np.zeros(self.T)

        for t in range(self.T):
            # Order arrives at start of period
            inventory[t] += orders[t]

            # Satisfy demand
            inventory[t] -= self.demands[t]

            # Costs
            if orders[t] > 0:
                setup_costs[t] = self.S
            holding_costs[t] = inventory[t] * self.h

            # Carry inventory forward
            inventory[t + 1] = inventory[t]

        total_setup = setup_costs.sum()
        total_holding = holding_costs.sum()
        total_cost = total_setup + total_holding

        return {
            'method': 'Lot-for-Lot',
            'orders': orders,
            'inventory': inventory[:-1],
            'setup_cost': total_setup,
            'holding_cost': total_holding,
            'total_cost': total_cost,
            'num_orders': (orders > 0).sum()
        }

    def fixed_order_quantity(self, Q: float) -> Dict:
        """
        Fixed Order Quantity: Order Q units whenever inventory insufficient

        Parameters:
        -----------
        Q : float
            Fixed order quantity
        """

        orders = np.zeros(self.T)
        inventory = np.zeros(self.T + 1)
        setup_costs = np.zeros(self.T)
        holding_costs = np.zeros(self.T)

        for t in range(self.T):
            # Check if order needed
            if inventory[t] < self.demands[t]:
                orders[t] = Q
                inventory[t] += Q

            # Satisfy demand
            inventory[t] -= self.demands[t]

            # Handle backorders if negative
            if inventory[t] < 0:
                # Need more orders
                num_orders = int(np.ceil(-inventory[t] / Q))
                orders[t] += num_orders * Q
                inventory[t] += num_orders * Q

            # Costs
            if orders[t] > 0:
                setup_costs[t] = self.S * (orders[t] / Q)  # Proportional setups
            holding_costs[t] = max(0, inventory[t]) * self.h

            # Carry forward
            inventory[t + 1] = inventory[t]

        total_setup = setup_costs.sum()
        total_holding = holding_costs.sum()
        total_cost = total_setup + total_holding

        return {
            'method': f'FOQ (Q={Q})',
            'orders': orders,
            'inventory': inventory[:-1],
            'setup_cost': total_setup,
            'holding_cost': total_holding,
            'total_cost': total_cost,
            'num_orders': (orders > 0).sum()
        }

    def silver_meal(self) -> Dict:
        """
        Silver-Meal Heuristic

        Iteratively add periods to lot, stop when average cost per period increases
        """

        orders = np.zeros(self.T)
        inventory = np.zeros(self.T + 1)
        t = 0

        while t < self.T:
            # Determine lot size starting at period t
            best_periods = 1
            min_avg_cost = float('inf')

            for k in range(1, self.T - t + 1):
                # Consider covering periods t through t+k-1
                # Cost = Setup cost + holding cost for carrying inventory

                total_demand = sum(self.demands[t:t+k])
                holding_cost = sum((j - t) * self.demands[t+j] * self.h
                                  for j in range(k))

                total_cost = self.S + holding_cost
                avg_cost = total_cost / k

                if avg_cost < min_avg_cost:
                    min_avg_cost = avg_cost
                    best_periods = k
                else:
                    # Average cost increased, stop
                    break

            # Place order for best_periods worth of demand
            order_qty = sum(self.demands[t:t+best_periods])
            orders[t] = order_qty

            # Update inventory levels
            inv = order_qty
            for j in range(best_periods):
                if t + j < self.T:
                    inventory[t + j] = inv
                    inv -= self.demands[t + j]

            t += best_periods

        # Calculate costs
        setup_costs = np.where(orders > 0, self.S, 0)
        holding_costs = inventory[:-1] * self.h

        return {
            'method': 'Silver-Meal',
            'orders': orders,
            'inventory': inventory[:-1],
            'setup_cost': setup_costs.sum(),
            'holding_cost': holding_costs.sum(),
            'total_cost': setup_costs.sum() + holding_costs.sum(),
            'num_orders': (orders > 0).sum()
        }

    def least_unit_cost(self) -> Dict:
        """
        Least Unit Cost (LUC) Heuristic

        For each order, add periods until cost per unit increases
        """

        orders = np.zeros(self.T)
        inventory = np.zeros(self.T + 1)
        t = 0

        while t < self.T:
            min_unit_cost = float('inf')
            best_periods = 1

            for k in range(1, self.T - t + 1):
                # Total demand covered
                total_demand = sum(self.demands[t:t+k])

                # Holding cost
                holding_cost = sum((j - t) * self.demands[t+j] * self.h
                                  for j in range(k))

                # Total cost
                total_cost = self.S + holding_cost

                # Unit cost
                unit_cost = total_cost / total_demand

                if unit_cost < min_unit_cost:
                    min_unit_cost = unit_cost
                    best_periods = k
                else:
                    break

            # Place order
            order_qty = sum(self.demands[t:t+best_periods])
            orders[t] = order_qty

            # Update inventory
            inv = order_qty
            for j in range(best_periods):
                if t + j < self.T:
                    inventory[t + j] = inv
                    inv -= self.demands[t + j]

            t += best_periods

        # Calculate costs
        setup_costs = np.where(orders > 0, self.S, 0)
        holding_costs = inventory[:-1] * self.h

        return {
            'method': 'Least Unit Cost',
            'orders': orders,
            'inventory': inventory[:-1],
            'setup_cost': setup_costs.sum(),
            'holding_cost': holding_costs.sum(),
            'total_cost': setup_costs.sum() + holding_costs.sum(),
            'num_orders': (orders > 0).sum()
        }

    def wagner_whitin(self) -> Dict:
        """
        Wagner-Whitin Algorithm

        Dynamic programming approach - finds optimal solution
        for uncapacitated lot-sizing problem

        Time complexity: O(T²)
        """

        T = self.T
        # F[t] = minimum cost for periods 1..t
        F = np.full(T + 1, np.inf)
        F[0] = 0

        # Predecessor: which period did we last order from?
        pred = np.zeros(T + 1, dtype=int)

        # DP forward pass
        for t in range(1, T + 1):
            for j in range(t):
                # Consider ordering in period j to cover demand through period t
                # Cost = F[j] + setup cost + holding cost

                # Holding cost for covering periods j+1 through t
                holding_cost = 0
                for k in range(j + 1, t + 1):
                    # Hold demand[k-1] for (k - j - 1) periods
                    holding_cost += (k - j - 1) * self.demands[k - 1] * self.h

                cost = F[j] + self.S + holding_cost

                if cost < F[t]:
                    F[t] = cost
                    pred[t] = j

        # Backtrack to find order periods
        orders = np.zeros(T)
        t = T
        while t > 0:
            j = pred[t]
            # Order in period j to cover through period t
            order_qty = sum(self.demands[j:t])
            orders[j] = order_qty
            t = j

        # Reconstruct inventory
        inventory = np.zeros(T + 1)
        for t in range(T):
            inventory[t] += orders[t]
            inventory[t] -= self.demands[t]
            inventory[t + 1] = inventory[t]

        # Calculate costs
        setup_costs = np.where(orders > 0, self.S, 0)
        holding_costs = inventory[:-1] * self.h

        return {
            'method': 'Wagner-Whitin (Optimal)',
            'orders': orders,
            'inventory': inventory[:-1],
            'setup_cost': setup_costs.sum(),
            'holding_cost': holding_costs.sum(),
            'total_cost': setup_costs.sum() + holding_costs.sum(),
            'num_orders': (orders > 0).sum(),
            'optimal': True
        }

    def compare_methods(self) -> pd.DataFrame:
        """Compare all lot-sizing methods"""

        methods = [
            self.lot_for_lot(),
            self.silver_meal(),
            self.least_unit_cost(),
            self.wagner_whitin()
        ]

        # Add FOQ with EOQ-based quantity
        avg_demand = self.demands.mean()
        if avg_demand > 0:
            eoq = np.sqrt(2 * avg_demand * self.T * self.S / self.h)
            methods.append(self.fixed_order_quantity(eoq))

        results = []
        for method in methods:
            results.append({
                'Method': method['method'],
                'Total Cost': method['total_cost'],
                'Setup Cost': method['setup_cost'],
                'Holding Cost': method['holding_cost'],
                'Num Orders': method['num_orders'],
                'Avg Inventory': method['inventory'].mean()
            })

        df = pd.DataFrame(results)
        df = df.sort_values('Total Cost')

        return df

    def plot_solution(self, solution: Dict):
        """Visualize lot-sizing solution"""

        fig, (ax1, ax2, ax3) = plt.subplots(3, 1, figsize=(14, 10))

        periods = np.arange(1, self.T + 1)

        # Plot 1: Demand and Orders
        ax1.bar(periods, self.demands, alpha=0.6, label='Demand', color='blue')
        order_periods = periods[solution['orders'] > 0]
        order_qtys = solution['orders'][solution['orders'] > 0]
        ax1.bar(order_periods, order_qtys, alpha=0.8, label='Orders', color='green')

        ax1.set_xlabel('Period', fontsize=11)
        ax1.set_ylabel('Quantity', fontsize=11)
        ax1.set_title(f"{solution['method']}: Demand and Order Pattern",
                     fontsize=12, fontweight='bold')
        ax1.legend()
        ax1.grid(True, alpha=0.3)

        # Plot 2: Inventory Levels
        ax2.plot(periods, solution['inventory'], marker='o', linewidth=2,
                color='orange', label='Ending Inventory')
        ax2.fill_between(periods, 0, solution['inventory'], alpha=0.3, color='orange')
        ax2.axhline(y=solution['inventory'].mean(), linestyle='--',
                   color='red', label=f"Avg Inv = {solution['inventory'].mean():.1f}")

        ax2.set_xlabel('Period', fontsize=11)
        ax2.set_ylabel('Inventory Level', fontsize=11)
        ax2.set_title('Inventory Over Time', fontsize=12, fontweight='bold')
        ax2.legend()
        ax2.grid(True, alpha=0.3)

        # Plot 3: Costs
        setup_costs = np.where(solution['orders'] > 0, self.S, 0)
        holding_costs = solution['inventory'] * self.h

        width = 0.35
        ax3.bar(periods - width/2, setup_costs, width, label='Setup Cost',
               color='red', alpha=0.7)
        ax3.bar(periods + width/2, holding_costs, width, label='Holding Cost',
               color='blue', alpha=0.7)

        ax3.set_xlabel('Period', fontsize=11)
        ax3.set_ylabel('Cost ($)', fontsize=11)
        ax3.set_title('Period Costs', fontsize=12, fontweight='bold')
        ax3.legend()
        ax3.grid(True, alpha=0.3)

        plt.tight_layout()
        return plt


# Example Usage
def example_lot_sizing():
    """Example: Multi-period lot-sizing problem"""

    print("\n" + "=" * 70)
    print("MULTI-PERIOD LOT-SIZING PROBLEM")
    print("=" * 70)

    # 12-period planning horizon with varying demand
    demands = [50, 60, 40, 80, 100, 90, 70, 60, 50, 80, 90, 100]

    problem = LotSizingProblem(
        demands=demands,
        setup_cost=200,      # $200 per order
        holding_cost=2,      # $2 per unit per period
        unit_cost=10         # $10 per unit (often ignored)
    )

    print("\nProblem Data:")
    print(f"  Planning Horizon: {problem.T} periods")
    print(f"  Setup Cost: ${problem.S}")
    print(f"  Holding Cost: ${problem.h}/unit/period")
    print(f"  Total Demand: {problem.demands.sum():.0f} units")
    print(f"  Average Demand: {problem.demands.mean():.1f} units/period")

    print("\n  Period-by-period demand:")
    for t, d in enumerate(demands, 1):
        print(f"    Period {t:2d}: {d:3.0f} units")

    # Compare all methods
    print("\n" + "=" * 70)
    print("COMPARISON OF LOT-SIZING METHODS")
    print("=" * 70)

    comparison = problem.compare_methods()
    print("\n" + comparison.to_string(index=False))

    # Analyze optimal solution
    optimal = problem.wagner_whitin()

    print("\n" + "=" * 70)
    print(f"OPTIMAL SOLUTION: {optimal['method']}")
    print("=" * 70)

    print(f"\n{'Total Cost:':<25} ${optimal['total_cost']:,.2f}")
    print(f"{'Setup Cost:':<25} ${optimal['setup_cost']:,.2f}")
    print(f"{'Holding Cost:':<25} ${optimal['holding_cost']:,.2f}")
    print(f"{'Number of Orders:':<25} {optimal['num_orders']}")
    print(f"{'Average Inventory:':<25} {optimal['inventory'].mean():.1f} units")

    print("\n  Order Schedule:")
    for t in range(problem.T):
        if optimal['orders'][t] > 0:
            print(f"    Period {t+1}: Order {optimal['orders'][t]:.0f} units")

    # Visualize
    problem.plot_solution(optimal)
    plt.savefig('/tmp/lot_sizing_optimal.png', dpi=300, bbox_inches='tight')
    print(f"\nOptimal solution plot saved to /tmp/lot_sizing_optimal.png")

    return problem, optimal


if __name__ == "__main__":
    example_lot_sizing()

---

有产能约束的批量规划

单品有产能约束批量规划问题（CLSP）

from pulp import *

class CapacitatedLotSizing:
    """
    Capacitated Lot-Sizing Problem (CLSP)

    Production capacity constraints in each period
    """

    def __init__(self, demands: List[float], setup_cost: float,
                 holding_cost: float, production_cost: float,
                 capacity: List[float]):
        """
        Parameters:
        -----------
        demands : list
            Demand for each period
        setup_cost : float
            Fixed setup cost per period
        holding_cost : float
            Holding cost per unit per period
        production_cost : float
            Variable production cost per unit
        capacity : list
            Production capacity each period
        """
        self.demands = np.array(demands)
        self.T = len(demands)
        self.S = setup_cost
        self.h = holding_cost
        self.c = production_cost
        self.capacity = np.array(capacity)

    def solve_mip(self) -> Dict:
        """
        Solve using Mixed-Integer Programming

        Decision variables:
        - x_t: production quantity in period t
        - y_t: binary, 1 if production occurs in period t
        - I_t: inventory at end of period t
        """

        # Create problem
        prob = LpProblem("Capacitated_Lot_Sizing", LpMinimize)

        # Decision variables
        x = [LpVariable(f"x_{t}", lowBound=0) for t in range(self.T)]
        y = [LpVariable(f"y_{t}", cat='Binary') for t in range(self.T)]
        I = [LpVariable(f"I_{t}", lowBound=0) for t in range(self.T + 1)]

        # Objective: minimize total cost
        prob += (lpSum([self.S * y[t] + self.c * x[t] + self.h * I[t]
                       for t in range(self.T)]))

        # Constraints

        # Initial inventory
        prob += I[0] == 0

        # Inventory balance
        for t in range(self.T):
            prob += I[t + 1] == I[t] + x[t] - self.demands[t]

        # Production capacity
        for t in range(self.T):
            prob += x[t] <= self.capacity[t] * y[t]

        # Solve
        prob.solve(PULP_CBC_CMD(msg=0))

        # Extract solution
        production = np.array([x[t].varValue for t in range(self.T)])
        setup_decisions = np.array([y[t].varValue for t in range(self.T)])
        inventory = np.array([I[t].varValue for t in range(self.T + 1)])

        # Calculate costs
        setup_cost = self.S * setup_decisions.sum()
        prod_cost = self.c * production.sum()
        holding_cost = self.h * inventory[:-1].sum()
        total_cost = value(prob.objective)

        return {
            'status': LpStatus[prob.status],
            'production': production,
            'inventory': inventory[:-1],
            'setups': setup_decisions,
            'total_cost': total_cost,
            'setup_cost': setup_cost,
            'production_cost': prod_cost,
            'holding_cost': holding_cost,
            'num_setups': int(setup_decisions.sum())
        }


# Example: Capacitated Lot-Sizing
def example_capacitated():
    """Example: Lot-sizing with capacity constraints"""

    print("\n" + "=" * 70)
    print("CAPACITATED LOT-SIZING PROBLEM")
    print("=" * 70)

    demands = [40, 60, 80, 50, 70, 90]
    capacity = [100, 100, 100, 100, 100, 100]  # Max production per period

    problem = CapacitatedLotSizing(
        demands=demands,
        setup_cost=300,
        holding_cost=2,
        production_cost=10,
        capacity=capacity
    )

    print("\nProblem Data:")
    print(f"  Periods: {problem.T}")
    print(f"  Setup Cost: ${problem.S}")
    print(f"  Holding Cost: ${problem.h}/unit/period")
    print(f"  Production Cost: ${problem.c}/unit")
    print(f"  Capacity per Period: {capacity[0]} units")

    print("\n  Period Demands:")
    for t, d in enumerate(demands, 1):
        print(f"    Period {t}: {d} units")

    # Solve
    solution = problem.solve_mip()

    print(f"\n{'=' * 70}")
    print(f"OPTIMAL SOLUTION")
    print("=" * 70)

    print(f"\n{'Status:':<25} {solution['status']}")
    print(f"{'Total Cost:':<25} ${solution['total_cost']:,.2f}")
    print(f"{'Setup Cost:':<25} ${solution['setup_cost']:,.2f}")
    print(f"{'Production Cost:':<25} ${solution['production_cost']:,.2f}")
    print(f"{'Holding Cost:':<25} ${solution['holding_cost']:,.2f}")
    print(f"{'Number of Setups:':<25} {solution['num_setups']}")

    print("\n  Production Schedule:")
    for t in range(problem.T):
        if solution['production'][t] > 0.01:
            print(f"    Period {t+1}: Produce {solution['production'][t]:.0f} units, "
                  f"Ending Inv: {solution['inventory'][t]:.0f}")

    return problem, solution


if __name__ == "__main__":
    example_capacitated()

---

工具和库

Python 库

优化：

• pulp：线性／混合整数规划
• pyomo：优化建模
• scipy.optimize：通用优化
• ortools：Google OR-Tools

数值计算：

• numpy、pandas：数据处理

商业软件

生产计划：

• SAP APO：提供批量规划功能的高级计划与优化
• Oracle Demantra：需求与供应计划
• Blue Yonder：供应链计划
• Kinaxis RapidResponse：集成计划

MRP 系统：

• 大多数 ERP 系统都提供批量规划规则（SAP、Oracle、Microsoft Dynamics）

---

常见挑战和解决方案

挑战：产能约束

问题：

• 某些时期的产能不足
• 无法在需要时生产

解决方案：

• 使用有产能约束的批量规划 MIP 模型
• 考虑加班生产（成本更高）
• 在需求较低的时期提前建立库存
• 在需求高峰期外包生产

挑战：准备时间与准备成本

问题：

• 准备工作既占用时间（产能），也产生成本
• 简单模型只考虑成本

解决方案：

• 在产能约束中纳入准备时间
• 使用带准备时间的 CLSP
• 与顺序相关的准备时间 → 需要更复杂的模型

挑战：多品种批量规划

问题：

• 多种产品共享同一产能
• 存在联合准备成本或准备时间

解决方案：

• 多品种 CLSP 表述
• 比例批量规划（PROPLS）启发式算法
• 基于优先级进行分配
• 查看代码中的多品种示例

挑战：需求不确定性

问题：

• 批量规划假设需求是确定的
• 实际需求存在不确定性

解决方案：

• 使用滚动时域规划（每期重新规划）
• 为需求添加安全库存
• 使用需求情景进行鲁棒优化
• 查看 stochastic-inventory-models 和 dynamic-lot-sizing

---

相关技能

• economic-order-quantity：单期批量规划
• dynamic-lot-sizing：时变参数和随机需求
• stochastic-inventory-models：概率库存模型
• master-production-scheduling：综合生产计划
• capacity-planning：长期产能决策
• production-scheduling：短期排程