Python实现Simplex LP求解目标为固定值的线性规划问题

核心问题说明 #

你遇到的是典型的子集和类0-1整数规划问题，PuLP完全可以实现和Excel Solver一致的求解效果，不需要额外依赖其他库。

多数人卡在PuLP强制要求设置目标函数的规则上，实际上只需要设置一个常数虚拟目标，就能实现「不做最值优化、仅寻找满足约束的可行解」的需求，和Excel Solver的可行解求解逻辑完全对齐。

实现逻辑 #

• 变量定义：为每笔债务定义取值只能是0或1的二进制决策变量，1代表全额偿还该笔债务，0代表不偿还。
• 约束设置：添加硬约束，要求所有选中债务的金额求和结果严格等于给定的付款总金额，从规则上禁止部分还款。
• 目标设置：设置固定值为0的虚拟目标，仅用于满足PuLP的模型格式要求，不做实际的最值优化。
• 求解器选择：调用PuLP内置的CBC开源求解器，求解速度远高于Excel自带的Simplex LP方法，适合千级批量任务。

可直接运行的代码 #

首先安装依赖：

pip install pulp pandas

核心求解代码，适配给出的测试样例：

import pandas as pd
import pulp

def solve_single_debt_group(debt_group: pd.DataFrame) -> pd.DataFrame:
    """
    求解单组债务匹配问题：选中若干笔债务全额偿还，总金额恰好等于给定付款额
    输入的debt_group要求包含Debt(债务名称)、Amount(债务金额)、Payment(该组总付款额)列
    返回带Boolean列的结果，True代表该笔债务被选中偿还
    """
    # 提取该组固定付款总额（同组付款额一致）
    total_pay = debt_group['Payment'].iloc[0]
    # 初始化模型
    model = pulp.LpProblem("Debt_Repayment_Match", pulp.LpMinimize)
    # 定义0-1决策变量
    select_vars = pulp.LpVariable.dicts(
        "select_debt",
        debt_group['Debt'].to_list(),
        lowBound=0,
        upBound=1,
        cat="Binary"
    )
    # 设置虚拟目标，无实际优化意义
    model += 0, "virtual_objective"
    # 添加核心约束：选中债务总金额恰好等于付款总额
    model += (
        pulp.lpSum(
            select_vars[row['Debt']] * row['Amount']
            for _, row in debt_group.iterrows()
        ) == total_pay,
        "total_amount_match_constraint"
    )
    # 静默求解，关闭日志输出
    model.solve(pulp.PULP_CBC_CMD(msg=False))
    # 将求解结果写回DataFrame
    debt_group['Boolean'] = [
        bool(select_vars[debt_name].varValue)
        for debt_name in debt_group['Debt']
    ]
    return debt_group

# 测试提供的样例
if __name__ == "__main__":
    test_data = [
        ['Debt1', 100, 400, True],
        ['Debt2', 200, 400, True],
        ['Debt3', 300, 400, True]
    ]
    test_df = pd.DataFrame(test_data, columns=['Debt', 'Amount', 'Payment', 'Boolean'])
    result_df = solve_single_debt_group(test_df)
    print(result_df)

结果与批量处理说明 #

• 上述测试样例运行后输出结果和参考示例完全一致：Debt1、Debt3被选中（Boolean为True），总金额100+300=400，恰好等于付款总额，Debt2未被选中。
• 批量处理1000组以上任务时，只需要将全量数据按付款批次分组，循环调用solve_single_debt_group函数即可，单组千笔以内债务的求解耗时在毫秒级，效率远高于Excel手动操作。
• 如果存在多组可行解（多组债务组合总金额等于付款额），可以将虚拟目标替换为自定义优先级规则，比如优先偿还高息债务、优先偿还小额债务等，只需将对应优先级的线性表达式作为目标函数即可。

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