运筹学对偶理论：用Python+PuLP库手把手教你求解线性规划对偶问题（附完整代码）

运筹学对偶理论实战用PythonPuLP求解线性规划对偶问题在资源分配、生产计划和投资组合等实际场景中线性规划是优化决策的利器。但你是否思考过每个最大化问题背后都隐藏着一个最小化问题这就是运筹学中迷人的对偶理论。本文将带你从零开始通过Python的PuLP库亲手实现线性规划问题的对偶求解验证强对偶定理并分析互补松弛条件的经济意义。1. 对偶理论的核心概念与Python建模基础对偶理论揭示了每个线性规划问题称为原始问题都有对应的镜像问题。这对问题如同硬币的两面蕴含着深刻的经济和管理学解释。原始问题与对偶问题的基本对应关系原始问题 (Primal)对偶问题 (Dual)目标函数max Z cᵀx目标函数min W bᵀy约束条件Ax ≤ b约束条件Aᵀy ≥ c决策变量x ≥ 0对偶变量y ≥ 0在Python中我们可以用PuLP库快速建立线性规划模型。先安装必要的库pip install pulp numpy来看一个生产计划问题的原始模型建立import pulp # 初始化原始问题 primal pulp.LpProblem(Production_Planning, pulp.LpMaximize) # 定义决策变量 x1 pulp.LpVariable(x1, lowBound0) # 产品1产量 x2 pulp.LpVariable(x2, lowBound0) # 产品2产量 # 定义目标函数 primal 3*x1 4*x2, Total_Profit # 添加约束条件 primal 2*x1 x2 10, Machine_Time primal x1 2*x2 8, Labor_Time primal x1 - x2 2, Material_Limit2. 自动推导对偶问题与强对偶验证PuLP虽然不直接提供对偶问题生成功能但我们可以根据理论手动构建。对偶变量的数量等于原始问题的约束条件数。对偶问题构建规则每个原始约束对应一个对偶变量原始目标系数变为对偶约束的右侧常数原始约束右侧常数变为对偶目标系数约束矩阵进行转置基于上述原始问题手动构建对偶问题# 初始化对偶问题 dual pulp.LpProblem(Dual_Production, pulp.LpMinimize) # 定义对偶变量与原始约束一一对应 y1 pulp.LpVariable(y1, lowBound0) # 机器时间影子价格 y2 pulp.LpVariable(y2, lowBound0) # 人工时间影子价格 y3 pulp.LpVariable(y3, lowBound0) # 材料限制影子价格 # 定义对偶目标函数 dual 10*y1 8*y2 2*y3, Total_Shadow_Cost # 添加对偶约束与原始变量一一对应 dual 2*y1 y2 y3 3, Product1_Constraint dual y1 2*y2 - y3 4, Product2_Constraint强对偶定理验证 强对偶定理指出如果原始问题和对偶问题都有可行解则它们的最优目标函数值相等。我们可以通过求解来验证# 求解原始问题 primal.solve() print(f原始问题最优值: {pulp.value(primal.objective)}) # 求解对偶问题 dual.solve() print(f对偶问题最优值: {pulp.value(dual.objective)})运行结果将显示两个最优值相等本例中应为26.0直观验证了强对偶定理。3. 互补松弛条件的编程实现与经济解释互补松弛条件是对偶理论中的关键性质它揭示了原始问题和对偶问题最优解之间的关系互补松弛定理 对于最优解x和y有yᵢ(Ax- b)ᵢ 0 对所有i(Aᵀy* - c)ⱼx*ⱼ 0 对所有j这意味着如果原始约束在最优解处不严格有松弛则对应的对偶变量必须为0如果对偶约束在最优解处不严格则对应的原始变量必须为0用Python验证互补松弛条件# 获取原始问题最优解 x1_val pulp.value(x1) x2_val pulp.value(x2) # 获取对偶问题最优解 y1_val pulp.value(y1) y2_val pulp.value(y2) y3_val pulp.value(y3) # 计算原始约束的松弛量 slack1 10 - (2*x1_val x2_val) # 机器时间松弛量 slack2 8 - (x1_val 2*x2_val) # 人工时间松弛量 slack3 2 - (x1_val - x2_val) # 材料限制松弛量 # 验证互补松弛条件1 print(fy1*×slack1 {y1_val * slack1}) # 应为0 print(fy2*×slack2 {y2_val * slack2}) # 应为0 print(fy3*×slack3 {y3_val * slack3}) # 应为0 # 计算对偶约束的剩余量 surplus1 (2*y1_val y2_val y3_val) - 3 # 产品1约束剩余量 surplus2 (y1_val 2*y2_val - y3_val) - 4 # 产品2约束剩余量 # 验证互补松弛条件2 print(fx1*×surplus1 {x1_val * surplus1}) # 应为0 print(fx2*×surplus2 {x2_val * surplus2}) # 应为0经济解释 对偶变量y*可以解释为资源的影子价格。当原始约束严格无松弛时对应的影子价格通常为正表示该资源是稀缺的当约束有松弛时影子价格为0表示该资源有剩余。在本例中你可能会发现y30这意味着材料限制在最优解下不是约束生产的瓶颈资源。4. 实际应用案例投资组合优化考虑一个投资组合优化问题投资者有100万资金可在三种资产间分配资产A预期回报8%风险系数0.5资产B预期回报12%风险系数1.2资产C预期回报6%风险系数0.3要求整体风险系数不超过0.8且对资产B的投资不超过总投资的40%。原始问题建模# 初始化投资组合原始问题 invest_primal pulp.LpProblem(Portfolio_Optimization, pulp.LpMaximize) # 定义决策变量 xA pulp.LpVariable(xA, lowBound0) # 资产A投资额(百万) xB pulp.LpVariable(xB, lowBound0) # 资产B投资额(百万) xC pulp.LpVariable(xC, lowBound0) # 资产C投资额(百万) # 目标函数最大化预期回报 invest_primal 0.08*xA 0.12*xB 0.06*xC, Total_Return # 约束条件 invest_primal xA xB xC 1, Total_Investment invest_primal 0.5*xA 1.2*xB 0.3*xC 0.8, Risk_Constraint invest_primal xB 0.4, AssetB_Limit对偶问题构建 这个原始问题有3个约束条件因此对偶问题有3个变量# 初始化对偶问题 invest_dual pulp.LpProblem(Dual_Portfolio, pulp.LpMinimize) # 定义对偶变量 y1 pulp.LpVariable(y1) # 总投资约束的影子价格(无符号限制因为是等式约束) y2 pulp.LpVariable(y2, lowBound0) # 风险约束的影子价格 y3 pulp.LpVariable(y3, lowBound0) # 资产B限制的影子价格 # 对偶目标函数 invest_dual y1 0.8*y2 0.4*y3, Total_Shadow_Value # 对偶约束 invest_dual y1 0.5*y2 0.08, AssetA_Constraint invest_dual y1 1.2*y2 y3 0.12, AssetB_Constraint invest_dual y1 0.3*y2 0.06, AssetC_Constraint结果分析与商业洞察 求解这两个问题后我们可以获得各资产的优化配置和对偶变量值。对偶变量y2风险约束的影子价格特别值得关注它表示风险约束每放宽0.1个单位投资组合的预期回报能增加多少。# 求解原始问题 invest_primal.solve() print(最优投资组合) print(f资产A: {pulp.value(xA)*100:.1f}%) print(f资产B: {pulp.value(xB)*100:.1f}%) print(f资产C: {pulp.value(xC)*100:.1f}%) print(f预期回报: {pulp.value(invest_primal.objective)*100:.2f}%) # 求解对偶问题 invest_dual.solve() print(\n对偶变量值) print(f总投资约束影子价格(y1): {pulp.value(y1):.4f}) print(f风险约束影子价格(y2): {pulp.value(y2):.4f}) print(f资产B限制影子价格(y3): {pulp.value(y3):.4f}) # 验证强对偶 print(f\n原始问题最优值: {pulp.value(invest_primal.objective)}) print(f对偶问题最优值: {pulp.value(invest_dual.objective)})运行结果可能显示风险约束的影子价格y2为正而资产B限制的影子价格y3为0这表明在当前最优解下资产B的限制并未起到约束作用。投资者可以考虑是否放宽对资产B的限制以获得更高的回报。通过这个完整的案例我们不仅实现了对偶问题的编程求解还获得了有价值的商业洞察这正是运筹学对偶理论在实际决策中的强大之处。