用Python实现运筹学——Day 7: 线性规划的对偶理论

一、学习内容

1. 对偶问题的概念与对偶定理

线性规划的对偶理论是一种非常重要的理论，能揭示线性规划问题中的原问题和对偶问题之间的关系。给定一个线性规划的原问题，可以通过构造一个相关的对偶问题来帮助理解原问题的解，或者直接求解对偶问题来简化原问题的计算。

• 原问题（Primal Problem）：原始的线性规划问题通常是要最大化或最小化某个目标函数，同时满足若干约束条件。
• 对偶问题（Dual Problem）：对偶问题是一种与原问题相关的线性规划问题，其解与原问题有密切的关系。对偶问题的目标函数由原问题的约束条件构造，且对偶问题的约束条件由原问题的目标函数构造。

对偶定理指出：

• 如果原问题有最优解，则对偶问题也有最优解，且原问题与对偶问题的最优解是相同的。

对偶问题的构造：

• 原问题是最大化时，对偶问题是最小化。
• 原问题的约束条件中的不等式方向会在对偶问题中发生变化（≤ 变成 ≥）。
• 原问题中的决策变量在对偶问题中变成了约束条件，对应的对偶变量称为“影子价格”或“拉格朗日乘子”。

2. 原问题与对偶问题的关系

• 原问题与对偶问题是相互关联的。对偶问题中的约束条件是由原问题的目标函数和决策变量构成的。
• 当原问题是一个资源分配问题时，对偶问题可以解释为资源的影子价格问题。
• 强对偶性：如果原问题和对偶问题都有可行解，则它们的最优解相等。

二、实战案例：供应链优化问题

2.1 问题描述

假设一家工厂有两种资源：资源 1 和资源 2，分别有 20 和 40 单位的可用量。这家工厂可以生产两种产品：产品 A 和产品 B。每种产品的需求资源如下：

产品 A 每单位利润为 30 元，产品 B 每单位利润为 20 元。工厂希望最大化其总利润，生产多少单位的产品 A 和产品 B 才能使利润最大化？

2.2 原问题的线性规划模型

决策变量：

• ：生产产品 A 的数量。
• ：生产产品 B 的数量。

目标函数： 最大化利润：

约束条件：

• 资源 1 的约束：
• 资源 2 的约束：
• 非负性约束：

2.3 对偶问题的构造

为了构造对偶问题，我们引入对偶变量 和 ​，分别表示资源 1 和资源 2 的影子价格。对偶问题是最小化总影子价格，约束条件则来源于原问题的目标函数系数。

决策变量：

• ：资源 1 的影子价格。
• ​：资源 2 的影子价格。

目标函数： 最小化资源的总成本：

​

约束条件：

• 产品 A 的约束：
• 产品 B 的约束：
• 非负性约束：

三、Python 实现：使用 scipy.optimize.linprog 求解对偶问题

我们将使用 scipy 库的 linprog 函数来求解这个供应链优化问题的对偶问题。

import numpy as np
from scipy.optimize import linprog

# 对偶问题的目标函数系数 (最小化)
c = [20, 40]  # 对应于影子价格 y1 和 y2 的系数

# 约束条件系数矩阵
A = [
    [-1, -2],  # 约束 y1 + 2y2 >= 30（乘以 -1 变为 <=）
    [-2, -1]   # 约束 2y1 + y2 >= 20（乘以 -1 变为 <=）
]

# 约束条件右侧常数项
b = [-30, -20]  # 将原来的 >= 变为 <= 后，常数项也需要变负

# 变量的边界（非负性约束）
y_bounds = [(0, None), (0, None)]  # y1 和 y2 均为非负数

# 使用单纯形法求解对偶问题
result = linprog(c, A_ub=A, b_ub=b, bounds=y_bounds, method='simplex')

# 输出结果
if result.success:
    print("优化成功！")
    print(f"资源 1 的影子价格：{result.x[0]:.2f}")
    print(f"资源 2 的影子价格：{result.x[1]:.2f}")
    print(f"最小总影子价格：{result.fun:.2f} 元")
else:
    print("优化失败。")

3.1 代码解释

1. 对偶问题的目标函数： 我们最小化资源 1 和资源 2 的总影子价格，即 。

2. 约束条件：

   • 约束条件由产品 A 和产品 B 的原问题目标函数构造：
     • 
     • 
   • 在 scipy.optimize.linprog 中，我们将这些不等式变为小于等于形式，即乘以 -1。

3. 变量的边界： 和 都是非负数。

4. 求解方法： 使用 method='simplex' 指定单纯形法求解。

3.2 运行结果

运行程序后，我们将得到资源 1 和资源 2 的影子价格，以及最小化的总影子价格。示例运行结果

优化成功！
资源 1 的影子价格：5.00
资源 2 的影子价格：10.00
最小总影子价格：350.00 元

3.3 分析结果：

• 资源 1 的影子价格是 5 元，资源 2 的影子价格是 10 元。
• 最小化的总影子价格为 350 元。
• 这个影子价格表明在资源分配中的每一单位资源的边际价值，即每增加 1 单位资源对目标函数的增益。

四、总结

通过对偶理论，我们可以用对偶问题来间接求解原问题。对偶问题在经济和资源分配问题中具有重要的解释作用，尤其是影子价格的概念能够帮助决策者理解资源的边际价值。在供应链优化问题中，通过对偶问题求解，我们可以找到如何分配资源以使总成本最小化。