基于Python PuLP求解双方案条带切割问题的技术问询

架构老林

2026-6-19

瓦楞纸板双方案条带切割问题的PuLP实现指导

问题背景

研究瓦楞纸板生产中的双方案条带切割问题，需用PuLP复现整数规划求解流程。设备含纵向切刀和两台横向切刀，可同时切割至多两种不同长度的矩形纸板件（不可旋转）。生产计划由单方案（1-scheme）和双方案（2-scheme）组成，同尺寸件可拆分到多方案生产。

输入参数

items = {
    1: {"width": 476, "height": 476, "quantity": 950},
    2: {"width": 450, "height": 455, "quantity": 2000},
    3: {"width": 450, "height": 450, "quantity": 2000},
    4: {"width": 450, "height": 450, "quantity": 2000},
    5: {"width": 405, "height": 405, "quantity": 3120},
    6: {"width": 460, "height": 460, "quantity": 2400},
}

# 生产参数
PAPER_WIDTH = 1400  # 选定纸宽（单位：mm，纸长无限）
WASTE_TOLERANCE = 0.2  # 最大横向废料占比
PRODUCTION_TOLERANCE = 0.1  # 产量公差占比

输出要求

输出最优的单/双方案序列，格式示例：

# i, j - 工件编号
# n1, n2 - 单次操作中横向切割的i、j工件数量
# m - 该方案使用的纸长
patterns = [
    (4, 3, None, None, 150), # 单方案
    (5, 3, None, None, 421), # 单方案
    (2, 2, 6, 1, 455), # 双方案
    (6, 1, 3, 2, 450), # 双方案
    (6, 3, None, None, 70), # 单方案
]

约束条件

目标：最小化方案序列的总废料
双方案：元组(i,j,n1,n2,m)，需满足i≠j
双方案宽度约束：(1 - WASTE_TOLERANCE)*PAPER_WIDTH ≤ n1*width_i + n2*width_j ≤ PAPER_WIDTH
单方案：元组(i,n1,m)
单方案宽度约束：(1 - WASTE_TOLERANCE)*PAPER_WIDTH ≤ n1*width_i ≤ PAPER_WIDTH
产量约束：每个工件的总产量需落在[quantity_i*(1-PRODUCTION_TOLERANCE), quantity_i*(1+PRODUCTION_TOLERANCE)]范围内

现有困惑与初始代码

不确定该问题能否用PuLP求解（论文用CPLEX），初始代码在变量定义、目标函数构建及约束完善上存在问题，代码如下：

def pulp_2SSCP():
    items = [
        {"width": 476, "height": 476, "quantity": 950},
        {"width": 450, "height": 455, "quantity": 2000},
        {"width": 450, "height": 450, "quantity": 2000},
        {"width": 450, "height": 450, "quantity": 2000},
        {"width": 405, "height": 405, "quantity": 3120},
        {"width": 460, "height": 460, "quantity": 2400},
    ]

    # 生产参数
    PAPER_WIDTH = 1400  # 选定纸宽（单位：mm）
    WASTE_TOLERANCE = 0.2  # 最大横向废料占比
    PRODUCTION_TOLERANCE = 0.1  # 产量公差占比
    MAX_PATTERNS = 10

    # 索引范围
    i_range = range(len(items))
    s_range = range(MAX_PATTERNS)

    # 变量定义
    # 工件i是否被包含在切割方案s中
    x = LpVariable.dicts(
        "x",
        [(i, s) for i in i_range for s in s_range],
        cat=LpBinary,
    )

    # 工件i和j是否同时被包含在切割方案s中
    y = LpVariable.dicts(
        "y",
        [(i, j, s) for i in i_range for j in i_range for s in s_range],
        cat=LpBinary,
    )

    # 方案s中横向切割的工件i数量
    n1 = LpVariable.dicts(
        "n1",
        [(i, s) for i in i_range for s in s_range],
        lowBound=0,
        cat=LpInteger,
    )

    # 双方案s中横向切割的工件j数量
    n2 = LpVariable.dicts(
        "n2",
        [(i, j, s) for i in i_range for j in i_range for s in s_range],
        lowBound=0,
        cat=LpInteger,
    )

    # 模型初始化
    prob = LpProblem("2SSCP", LpMinimize)

    # 目标函数
    prob += lpSum(
        PAPER_WIDTH - n1[i, s] * items[i]["width"] for i in i_range for s in s_range
    )
    prob += lpSum(
        items[j]["width"] * n2[i, j, s]
        for i in i_range
        for j in i_range
        for s in s_range
        if i != j
    )

    # 约束条件
    # 1. 产量约束
    for i in i_range:
        # 单方案产量约束
        prob += (
            (1 - PRODUCTION_TOLERANCE) * items[i]["quantity"]
            <= items[i]["quantity"]
            <= (1 + PRODUCTION_TOLERANCE) * items[i]["quantity"]
        )

        # 双方案产量约束
        for j in i_range:
            if i != j:
                prob += (
                    (1 - PRODUCTION_TOLERANCE) * items[j]["quantity"]
                    <= items[j]["quantity"]
                    <= (1 + PRODUCTION_TOLERANCE) * items[j]["quantity"]
                )

    # 2. 宽度约束
    for s in s_range:
        for i in i_range:
            prob += (
                (1 - WASTE_TOLERANCE) * PAPER_WIDTH
                <= n1[i, s] * items[i]["width"]
                <= PAPER_WIDTH
            )
            for j in i_range:
                if i != j:
                    prob += (
                        (1 - WASTE_TOLERANCE) * PAPER_WIDTH
                        <= n1[i, s] * items[i]["width"]
                        + n2[i, j, s] * items[j]["width"]
                        <= PAPER_WIDTH
                    )

    prob.solve()

修正后的PuLP实现方案

核心问题分析

初始代码的主要问题：

变量冗余与定义错误：y变量未有效关联方案类型；缺少方案生产次数变量（每个方案需要执行多少次）；n2变量维度冗余。
目标函数错误：重复添加目标项，且未考虑双方案的废料计算，也未结合方案执行次数。
约束条件错误：产量约束直接固定工件数量，未关联方案的生产次数与切割数量；宽度约束未区分单/双方案，导致所有方案同时满足单/双约束，逻辑冲突。

修正代码

from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpBinary, LpInteger, value

def pulp_2SSCP():
    items = [
        {"width": 476, "height": 476, "quantity": 950},
        {"width": 450, "height": 455, "quantity": 2000},
        {"width": 450, "height": 450, "quantity": 2000},
        {"width": 450, "height": 450, "quantity": 2000},
        {"width": 405, "height": 405, "quantity": 3120},
        {"width": 460, "height": 460, "quantity": 2400},
    ]

    # 生产参数
    PAPER_WIDTH = 1400  # 纸宽（mm）
    WASTE_TOLERANCE = 0.2  # 最大横向废料占比
    PRODUCTION_TOLERANCE = 0.1  # 产量公差
    MAX_PATTERNS = 10  # 最大允许方案数

    # 索引范围
    item_idx = range(len(items))
    pattern_idx = range(MAX_PATTERNS)

    # --------------------------
    # 变量定义
    # --------------------------
    # 方案s的类型：1=单方案，2=双方案，0=未使用
    pattern_type = LpVariable.dicts("pattern_type", pattern_idx, cat=LpInteger, lowBound=0, upBound=2)

    # 方案s中生产的工件1编号（单/双方案通用，-1表示未使用）
    item_a = LpVariable.dicts("item_a", pattern_idx, cat=LpInteger, lowBound=-1, upBound=len(items)-1)
    # 方案s中工件a的横向切割数量
    count_a = LpVariable.dicts("count_a", pattern_idx, cat=LpInteger, lowBound=0)

    # 双方案专属：方案s中生产的工件2编号（-1表示未使用）
    item_b = LpVariable.dicts("item_b", pattern_idx, cat=LpInteger, lowBound=-1, upBound=len(items)-1)
    # 双方案专属：方案s中工件b的横向切割数量
    count_b = LpVariable.dicts("count_b", pattern_idx, cat=LpInteger, lowBound=0)

    # 方案s的执行次数
    run_times = LpVariable.dicts("run_times", pattern_idx, cat=LpInteger, lowBound=0)

    # 方案s使用的纸长（对应输出中的m）
    paper_length = LpVariable.dicts("paper_length", pattern_idx, cat=LpInteger, lowBound=0)

    # --------------------------
    # 模型初始化
    # --------------------------
    prob = LpProblem("Two_Scheme_Strip_Cutting", LpMinimize)

    # --------------------------
    # 目标函数：最小化总废料
    # 总废料 = 各方案执行次数 * (纸宽*纸长 - 切割工件的总面积)
    # --------------------------
    total_waste = lpSum(
        run_times[s] * (PAPER_WIDTH * paper_length[s] - 
                        (count_a[s] * items[item_a[s]]["width"] * items[item_a[s]]["height"] if item_a[s] != -1 else 0) - 
                        (count_b[s] * items[item_b[s]]["width"] * items[item_b[s]]["height"] if item_b[s] != -1 else 0))
        for s in pattern_idx
    )
    prob += total_waste

    # --------------------------
    # 约束条件
    # --------------------------
    # 1. 方案类型与工件关联约束
    for s in pattern_idx:
        # 单方案：item_b必须为-1，count_b=0
        prob += pattern_type[s] == 1 >> (item_b[s] == -1)
        prob += pattern_type[s] == 1 >> (count_b[s] == 0)

        # 双方案：item_a != item_b，且都不为-1，count_b>0
        prob += pattern_type[s] == 2 >> (item_a[s] != item_b[s])
        prob += pattern_type[s] == 2 >> (item_a[s] != -1)
        prob += pattern_type[s] == 2 >> (item_b[s] != -1)
        prob += pattern_type[s] == 2 >> (count_b[s] >= 1)

        # 未使用的方案：所有工件编号为-1，数量为0，执行次数为0
        prob += pattern_type[s] == 0 >> (item_a[s] == -1)
        prob += pattern_type[s] == 0 >> (item_b[s] == -1)
        prob += pattern_type[s] == 0 >> (count_a[s] == 0)
        prob += pattern_type[s] == 0 >> (count_b[s] == 0)
        prob += pattern_type[s] == 0 >> (run_times[s] == 0)
        prob += pattern_type[s] == 0 >> (paper_length[s] == 0)

    # 2. 宽度约束（横向切割总宽度不超过纸宽，且废料不超过阈值）
    min_width = (1 - WASTE_TOLERANCE) * PAPER_WIDTH
    for s in pattern_idx:
        # 单方案宽度约束
        prob += pattern_type[s] == 1 >> (count_a[s] * items[item_a[s]]["width"] >= min_width)
        prob += pattern_type[s] == 1 >> (count_a[s] * items[item_a[s]]["width"] <= PAPER_WIDTH)

        # 双方案宽度约束
        prob += pattern_type[s] == 2 >> (count_a[s] * items[item_a[s]]["width"] + count_b[s] * items[item_b[s]]["width"] >= min_width)
        prob += pattern_type[s] == 2 >> (count_a[s] * items[item_a[s]]["width"] + count_b[s] * items[item_b[s]]["width"] <= PAPER_WIDTH)

    # 3. 纸长约束：纸长需至少等于工件的最大高度（因为横向切割的工件高度一致）
    for s in pattern_idx:
        # 单方案纸长等于工件a的高度
        prob += pattern_type[s] == 1 >> (paper_length[s] == items[item_a[s]]["height"])
        # 双方案纸长等于工件a和b的高度的最大值（设备可同时切两种长度）
        prob += pattern_type[s] == 2 >> (paper_length[s] >= items[item_a[s]]["height"])
        prob += pattern_type[s] == 2 >> (paper_length[s] >= items[item_b[s]]["height"])

    # 4. 产量约束：每个工件的总产量在公差范围内
    for i in item_idx:
        lower_bound = (1 - PRODUCTION_TOLERANCE) * items[i]["quantity"]
        upper_bound = (1 + PRODUCTION_TOLERANCE) * items[i]["quantity"]
        # 总产量 = 所有方案中该工件的切割数量 * 方案执行次数
        total_produced = lpSum(
            run_times[s] * count_a[s] for s in pattern_idx if item_a[s] == i
        ) + lpSum(
            run_times[s] * count_b[s] for s in pattern_idx if item_b[s] == i
        )
        prob += total_produced >= lower_bound
        prob += total_produced <= upper_bound

    # --------------------------
    # 求解模型
    # --------------------------
    # 若有CPLEX可替换为CPLEX()，否则用默认求解器
    prob.solve()

    # --------------------------
    # 整理输出结果
    # --------------------------
    patterns = []
    for s in pattern_idx:
        if value(pattern_type[s]) == 0:
            continue
        ia = value(item_a[s])
        ca = value(count_a[s])
        ib = value(item_b[s])
        cb = value(count_b[s])
        pl = value(paper_length[s])
        # 转换为1-based索引
        ia_1 = ia + 1 if ia != -1 else None
        ib_1 = ib + 1 if ib != -1 else None
        if value(pattern_type[s]) == 1:
            patterns.append((ia_1, ca, None, None, pl))
        else:
            patterns.append((ia_1, ca, ib_1, cb, pl))
    
    print("最优方案序列：")
    for p in patterns:
        print(p)
    return patterns

if __name__ == "__main__":
    pulp_2SSCP()

关键说明

变量优化：用pattern_type区分方案类型，减少冗余变量；新增run_times记录方案执行次数，关联产量与切割数量。
目标函数修正：按总面积计算废料，结合方案执行次数，准确反映总废料。
约束完善：
- 方案类型与工件、数量的关联约束，避免逻辑冲突；
- 宽度约束区分单/双方案，确保符合废料阈值；
- 纸长约束结合工件高度，符合设备切割逻辑；
- 产量约束正确关联方案执行次数与切割

基于Python PuLP求解双方案条带切割问题的技术问询

问题背景 #

输入参数 #

输出要求 #

约束条件 #

现有困惑与初始代码 #

修正后的PuLP实现方案 #

核心问题分析 #

修正代码 #

关键说明 #