线性规划的对偶理论

PROBLEM ANCHOR

今天的课件可以帮你解决什么问题？

选择一个你关心的问题，后续内容会围绕它展开。

我有自己的问题

选择或输入后，本课会围绕你的问题展开。

LEARNING OBJECTIVES

学习目标

能从原问题出发，正确构造对称型和非对称型的对偶线性规划
能陈述并证明弱对偶定理和强对偶定理，理解它们的区别与联系
能运用互补松弛定理判断给定解的最优性
能解释影子价格的经济含义，并将其与对偶最优解建立对应

PRETEST

课前检测

先测试一下你对线性规划基础知识的掌握情况。

问题：考虑原问题 max z = 3x₁ + 5x₂，约束为 x₁ ≤ 4，2x₂ ≤ 12，3x₁ + 2x₂ ≤ 18，x₁, x₂ ≥ 0。它对应对偶问题中，决策变量的个数是多少？

请先点击一个选项，查看你的诊断反馈。

CORE CONCEPT 1

一、对称型对偶规划

已经知道：线性规划可以用单纯形法求解最优值和最优解。

但是问题是：如何从"外部"视角——比如从资源定价的角度——理解这个最优解的价值？

所以这一段要解决：引入"对偶问题"的概念，为每个原始线性规划建立一个镜像问题。

原问题 (P) max z = c 1 x 1 + c 2 x 2 + \dots + c n x n s.t. a 11 x 1 + a 12 x 2 + \dots + a 1n x n \leq b 1 a 21 x 1 + a 22 x 2 + \dots + a 2n x n \leq b 2 ⋮ a m1 x 1 + a m2 x 2 + \dots + a mn x n \leq b m x 1, x 2, \dots, x n \geq 0

对偶问题 (D) min w = b 1 y 1 + b 2 y 2 + \dots + b m y m s.t. a 11 y 1 + a 21 y 2 + \dots + a m1 y m \geq c 1 a 12 y 1 + a 22 y 2 + \dots + a m2 y m \geq c 2 ⋮ a 1n y 1 + a 2n y 2 + \dots + a mn y m \geq c n y 1, y 2, \dots, y m \geq 0

构造要诀：

原问题 (max)	对偶问题 (min)
目标系数 c	约束右端 c
约束右端 b	目标系数 b
约束矩阵 A	转置矩阵 A^T
n 个变量，m 条约束	m 个变量，n 条约束
"≤" 约束	"≥" 约束

例题 1

写出下述线性规划的对偶问题：

max z = 4x 1 + x 2 + 3x 3 s.t. x 1 + x 2 + x 3 \leq 3 3x 1 + x 2 - x 3 \leq 2 x 1, x 2, x 3 \geq 0

点击查看答案

min w = 3y 1 + 2y 2 s.t. y 1 + 3y 2 \geq 4 y 1 + y 2 \geq 1 y 1 - y 2 \geq 3 y 1, y 2 \geq 0

CORE CONCEPT 2

二、非对称型对偶与转换规则

当原问题中含有 $等式约束$ 或 $无符号限制变量$ 时，对偶问题的形式需要特殊处理。

完整对偶转换表

原问题（max 问题）	对偶问题（min 问题）
第 i 个约束 ≤	y_i ≥ 0
第 i 个约束 =	y_i 无符号限制 (free)
第 i 个约束 ≥	y_i ≤ 0
x_j ≥ 0	第 j 个约束 ≥
x_j 无符号限制 (free)	第 j 个约束 =
x_j ≤ 0	第 j 个约束 ≤

记忆技巧：约束方向与对偶变量符号呈"反比"关系——越紧的约束（≤）对应越大的对偶变量（≥ 0）；等式约束则对应自由变量。

CORE CONCEPT 3

三、弱对偶性与强对偶性

定理 1：弱对偶定理 (Weak Duality)

设 x 是原问题 (P) 的任一可行解，y 是对偶问题 (D) 的任一可行解，则恒有：

c T x \leq b T y

重要推论：

原问题目标函数值的上界由对偶可行解给出
若原问题无界，则对偶问题必无可行解
若 c^Tx = b^Ty，则 x 和 y 分别是各自问题的最优解

定理 2：强对偶定理 (Strong Duality)

若原问题 (P) 有有限最优解 x*，则对偶问题 (D) 也有有限最优解 y*，且：

c T x* = b T y*

关键洞察：弱对偶给了我们一个不等式，强对偶说在最优点处这个不等式变为等式——原问题的最优值和对偶问题的最优值完全相等！

直观理解： 弱对偶 = "蛋糕总价不超过材料成本" 强对偶 = "最优生产方案下，蛋糕卖价恰好等于材料的最佳定价"

CORE CONCEPT 4

四、互补松弛定理

定理 3：互补松弛定理 (Complementary Slackness)

设 x* 和 y* 分别是原问题和对偶问题的可行解。它们是各自问题最优解的充要条件是：

(1) 原始互补松弛： y i * (b i - Σ j a ij x j *) = 0，\forall i (2) 对偶互补松弛： (Σ i a ij y i * - c j) x j * = 0，\forall j

条件 (1) 的含义

若 y_i* > 0（资源有正价值），则 Σa_ijx_j* = b_i（资源完全用尽）；

若资源有剩余（严格 <），则该资源的影子价格必为 0。

条件 (2) 的含义

若 x_j* > 0（生产该产品），则对偶约束必紧（成本 = 收益）；

若对偶约束不紧（成本 > 收益），则该产品不应生产（x_j* = 0）。

INTERACTIVE

五、交互式探索：原问题与对偶问题的关系

拖动滑块修改原问题参数，观察对偶问题如何随之变化。注意观察弱对偶性和强对偶性。

💡 拖动滑块改变参数，观察原问题可行域（蓝色）和对偶最优值的变化。最优解时原问题目标值 = 对偶目标值。

APPLICATION

六、影子价格：对偶变量的经济解释

y_i*

对偶最优解的第 i 个分量 = 第 i 种资源的影子价格

反映了增加一单位该资源对目标函数最优值的边际贡献

数学解释

若最优基不变，有：

\partialz*/\partialb i = y i *

影子价格是对最优目标值关于资源量的偏导数——即资源的边际价值。

经济含义

y_i* > 0：该资源是稀缺的，增加供应会提升目标值
y_i* = 0：该资源有剩余，增加供应无边际价值
定价决策：市场价 < 影子价格 → 买入资源有利；市场价 > 影子价格 → 卖出资源有利

实例：某工厂生产两种产品，约束为机器工时（≤4h）和原料（≤12kg）。若最优对偶解 y₁*=0, y₂*=1.5，说明：机器工时非瓶颈（影子价格=0），但每增加 1kg 原料可多赚 1.5 元——这就是原料的"影子价格"。

CONCEPTEST

概念测试

关于对偶理论，以下哪个说法是错误的？

先独立判断，再查看诊断反馈。

PRACTICE

练习：从示范到独立

全支架示范

问题：写出 min z = 2x₁ + 3x₂
s.t. x₁ + x₂ ≥ 4
x₁ − x₂ ≤ 2
x₁, x₂ ≥ 0 的对偶问题。

查看解答

标准化：min \to 保持 min 形式 对偶为 max w = 4y 1 + 2y 2 s.t. y 1 + y 2 \leq 2 y 1 - y 2 \leq 3 y 1 \geq 0, y 2 \leq 0

半支架练习

原问题 max z = x₁ + 2x₂ + 3x₃
s.t. x₁ + x₂ + x₃ = 5
2x₁ − x₂ ≤ 3
x₁ ≥ 0, x₂ ≤ 0, x₃ free

提示：

等式约束 → 对偶变量 _____
x₃ 无限制 → 对偶约束 _____
确认 max → min 的方向

独立完成

用互补松弛定理判断 x*=(2,0,3)^T 是否为下述问题的最优解，并求对偶最优解：

max z = x 1 + x 2 + x 3 s.t. 3x 1 + x 2 + x 3 \leq 9 x 1 - x 2 + 2x 3 \leq 5 x 1, x 2, x 3 \geq 0

SUMMARY

本课小结

1

对偶构造

max-≤-≥0 → min-≥-≥0
A → A^T，b ↔ c

2

弱对偶

c^Tx ≤ b^Ty
任何可行解对

3

强对偶

最优时值相等
c^Tx* = b^Ty*

4

互补松弛

紧约束 ↔ 正对偶变量
最优性充要条件

5

影子价格

y_i* = 资源边际价值
指导买卖决策

KNOWLEDGE GRAPH

知识图谱

本节点在大学运筹学知识体系中的定位（free_mode）：

前置知识

线性代数（矩阵运算、向量空间）
线性规划的标准形式
单纯形法

后续知识

对偶单纯形法
灵敏度分析
非线性规划的对偶理论
拉格朗日对偶