企业官网建设流程全解析

运筹学对偶理论实战：用Python+PuLP求解线性规划对偶问题

在资源分配、生产计划和投资组合等实际场景中，线性规划是优化决策的利器。但你是否思考过，每个最大化问题背后都隐藏着一个最小化问题？这就是运筹学中迷人的对偶理论。本文将带你从零开始，通过Python的PuLP库，亲手实现线性规划问题的对偶求解，验证强对偶定理，并分析互补松弛条件的经济意义。

1. 对偶理论的核心概念与Python建模基础

对偶理论揭示了每个线性规划问题（称为原始问题）都有对应的"镜像"问题。这对问题如同硬币的两面，蕴含着深刻的经济和管理学解释。

原始问题与对偶问题的基本对应关系：

在Python中，我们可以用PuLP库快速建立线性规划模型。先安装必要的库：

pip install pulp numpy

来看一个生产计划问题的原始模型建立：

import pulp # 初始化原始问题 primal = pulp.LpProblem("Production_Planning", pulp.LpMaximize) # 定义决策变量 x1 = pulp.LpVariable('x1', lowBound=0) # 产品1产量 x2 = pulp.LpVariable('x2', lowBound=0) # 产品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_Limit"

2. 自动推导对偶问题与强对偶验证

PuLP虽然不直接提供对偶问题生成功能，但我们可以根据理论手动构建。对偶变量的数量等于原始问题的约束条件数。

对偶问题构建规则：

1. 每个原始约束对应一个对偶变量
2. 原始目标系数变为对偶约束的右侧常数
3. 原始约束右侧常数变为对偶目标系数
4. 约束矩阵进行转置

基于上述原始问题，手动构建对偶问题：

# 初始化对偶问题 dual = pulp.LpProblem("Dual_Production", pulp.LpMinimize) # 定义对偶变量（与原始约束一一对应） y1 = pulp.LpVariable('y1', lowBound=0) # 机器时间影子价格 y2 = pulp.LpVariable('y2', lowBound=0) # 人工时间影子价格 y3 = pulp.LpVariable('y3', lowBound=0) # 材料限制影子价格 # 定义对偶目标函数 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，有：

1. yᵢ(Ax- b)ᵢ = 0 对所有i
2. (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(f"y1*×slack1 = {y1_val * slack1}") # 应为0 print(f"y2*×slack2 = {y2_val * slack2}") # 应为0 print(f"y3*×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(f"x1*×surplus1 = {x1_val * surplus1}") # 应为0 print(f"x2*×surplus2 = {x2_val * surplus2}") # 应为0

经济解释： 对偶变量y*可以解释为资源的影子价格。当原始约束严格（无松弛）时，对应的影子价格通常为正，表示该资源是稀缺的；当约束有松弛时，影子价格为0，表示该资源有剩余。

在本例中，你可能会发现y3=0，这意味着材料限制在最优解下不是约束生产的瓶颈资源。

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', lowBound=0) # 资产A投资额(百万) xB = pulp.LpVariable('xB', lowBound=0) # 资产B投资额(百万) xC = pulp.LpVariable('xC', lowBound=0) # 资产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', lowBound=0) # 风险约束的影子价格 y3 = pulp.LpVariable('y3', lowBound=0) # 资产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的限制，以获得更高的回报。

通过这个完整的案例，我们不仅实现了对偶问题的编程求解，还获得了有价值的商业洞察，这正是运筹学对偶理论在实际决策中的强大之处。