运筹学

——————————————————————————————————————————————

运筹学笔记

——————————————————————————————————————————————

Tsui Dik Sang

2024 年 2 月 8 日——2026 年 2 月 9 日

0 1 2 3 4 5

x1 + x2 = 4

2x1 + x2 = 6

data1

data2

data3

写在笔记之前

还是涉及很多数学的，并且学好矩阵将会对学习运筹学有很大帮助!

Tsui Dik Sang

2026 年 1 月 5 日

第一章非线性规划 6

1.1 极值问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.1 梯度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.2 Hessian 矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.2.1 泰勒展开 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.2.2 正定性判定凸优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 凹凸函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.1 定义与性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.2 判定方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.2.1 直接定义法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.3 一阶条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.3.1 二阶条件 (Hessian 矩阵法) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 凸规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Lagrange 乘数法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.1 基本定义以及扩展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.2 Karush Kuhn Tucker 条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.3 可行下降方向 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.4 多约束条件下的 Karush Kuhn Tucker 条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

第二章线性规划 13

2.1 线性规划的基本概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.1 基本元素 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.2 形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.2.1 代数形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.2.2 矩阵形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.2.3 向量形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1.3 标准形式的转换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1.3.1 独立变量的反转 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1.3.2 自由变量的消除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1.3.3 松弛变量引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.3.4 目标函数的调整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.3.5 等式约束的调整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.3.6 人工变量法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.4 解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.5 基本定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

运筹学笔记目录 Tsui Dik Sang

2.2 单纯形法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1 引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1.1 寻找基变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1.2 移非基变量到右边 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1.3 判断是否最优 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1.4 换基 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.1.5 重复判断是否最优 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.2 代数形式的单纯形法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.2.1 寻找或者构造基变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.2.2 判断最优性并选择换入变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.2.3 计算 θ

确定换出变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.3 表格单纯形法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.4 矩阵表示的求解过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.5 人工变量法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.5.1 大 M 法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.5.2 两阶段法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 对偶问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3.1 定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.2 性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.2.1 基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.2.2 互补松弛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3.3 对偶单纯形法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3.3.1 引入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3.3.2 通式方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3.4 敏感性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3.4.1 资源系数 b

的变化：影子价格 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3.4.2 价值系数 c

的变化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.4.3 技术系数 a

的变化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.4.4 增加变量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.4.5 新增约束条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.5 参数线性规划

∗

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.4 运输问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.4.1

基本建模

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.4.2 表上作业法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4.2.1 确定初始基可行解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4.2.2 解的最优性检验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4.2.3 闭回路调整法——应该是唯一的方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.4.2.4 无穷解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.2.5 退化解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.3 产销不平衡问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.3.1 产大于销 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.3.2 销大于产 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.3.3 运输路线不存在 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.3.4 弹性供货问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.4.4 转运问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

运筹学笔记目录 Tsui Dik Sang

2.4.4.1 参数调整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.5 目标规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.5.1 画图法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5.2 单纯形法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.6 整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.6.1 分支定界法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.6.2 Gomory 割平面法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.6.3 0-1 规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.6.3.1 指派问题：匈牙利方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.6.3.2 不均衡指派 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.6.3.3 一般 0-1 规划：隐式枚举法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

第三章动态规划 39

3.1 动态规划的基本概念与思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1.1 基本思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1.1.1 逆序法与顺序法的思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1.2 基本概念与定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2 具体解题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.1 离散题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.2 连续-非线性题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.2.1 建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.2.2 求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2.2.3 基于 Lagrange 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

第四章笔记结束 42

第一章非线性规划

直接给出标准形式

定义 1.0.1 (非线性规划 NLP 标准形式).

min f(X) (1.1)











(X) = 0, i = 1, 2, · · · , m

(X) ⩾ 0, j = 1, 2, · · · , p

X = (x

, x

, · · · , x

)

∈ R

(1.2)

1.1 极值问题

1.1.1 梯度

在高数中已经广泛地讨论，因此这里从略。

1.1.2 Hessian 矩阵

定义 1.1.1 (Hessian 矩阵). 若 f (X ) 在 X

的某个邻域内二阶可微，则可定义其在 X

处的 Hessian 矩阵为

H(X

) =



∂

∂x



n×n







∂

∂x

∂

∂x

· · ·

∂

∂x

∂

∂x

∂

∂x

· · ·

∂

∂x

∂

∂x

∂

∂x

· · ·

∂

∂x









X=X

(1.3)

定义 1.1.2 (Hessian 矩阵的正定性). -

• 正定：∀Z ∈ R

, Z ̸= 0, Z

HZ > 0

• 半正定：∀Z ∈ R

, Z ̸= 0, Z

HZ ⩾ 0

• 负定：∀Z ∈ R

, Z ̸= 0, Z

HZ < 0

• 半负定：∀Z ∈ R

, Z ̸= 0, Z

HZ ⩽ 0

运筹学笔记第一章非线性规划 Tsui Dik Sang

推论 1.1.1 (Hessian 矩阵的正定性判定法). 设 H 为 n 阶实对称矩阵，则 H 的正定性可由其特征值判定：

• 正定：H 的 n 个特征值均为正；

• 半正定：H 的 n 个特征值均为非负；

• 负定：H 的 n 个特征值均为负；

• 半负定：H 的 n 个特征值均为非正。

1.1.2.1 泰勒展开

这里首先给一个 Hessian 矩阵的应用——泰勒展开

定理 1.1.2 (多元函数的泰勒公式). 若 f (X ) 在 X

的某个邻域内二阶可微，则对于 X 在该邻域内，有

f(X) = f(X

) + ∇f(X

)

(X − X

) +

(X − X

)

H(X

)(X − X

) + o(∥X − X

∥

) (1.4)

1.1.2.2 正定性判定凸优化

下面将会详细讲

1.2 凹凸函数

1.2.1 定义与性质

先定义集合的凹凸性

定义 1.2.1 (凸集). 设 D ⊆ R

为 n 维空间 R

上的某个集合，若对于任意实数 α ∈ [0, 1] 及任意 X

, X

∈ D，其连线上的

点也都在 D 中，即

αX

+ (1 − α)X

∈ D (1.5)

则称 D 为凸集；没有凹集的定义

定义 1.2.2 (凸函数). 设 f(X) 为定义在 n 维空间 R

上的某个凸集 D 上的实值函数，若对于任意实数 α ∈ [0, 1] 及任意

, X

∈ D，都有

f(αX

+ (1 − α)X

) ⩽ αf(X

) + (1 − α)f (X

) (1.6)

则称 f(X) 为 D 上的凸函数；从几何上理解，即连线上的点在函数图像的上方

如果取的是“<”，则称为凸函数。凹函数的定义则如下

定义 1.2.3 (凹函数). 设 f(X) 为定义在 n 维空间 R

上的某个凹集 D 上的实值函数，若对于任意实数 α ∈ [0, 1] 及任意

, X

∈ D，都有

f(αX

+ (1 − α)X

) ⩾ αf(X

) + (1 − α)f (X

) (1.7)

则称 f(X) 为 D 上的严格凹函数；若等号成立，则称 f (X ) 为 D 上的凹函数。

实际上只有一维有可能有严格凹函数，

运筹学笔记第一章非线性规划 Tsui Dik Sang

推论 1.2.1 (凸函数的线性性). 有限个凸函数的非负线性组合仍然是凸函数。

f(X) =

i=1

(X), α

⩾ 0, i = 1, 2, · · · , n (1.8)

推论 1.2.2 (凸函数水平集). 设 f (X ) 为定义在凸集 D 上的凸函数，则对于任意实数 β，集合

= {X |X ∈ D, f(X ) ⩽ β} (1.9)

是凸集，称为水平集。

如果用一元函数来类比的话，在图上要注意是数轴的部分！并非上面的部分，这样的话可以证明凸集的定义还是成立的

引入凹凸函数可以帮助我们确定局部极值是否为全局极值

定理 1.2.3 (凸函数的局部极小即全局极小). 设 f (X ) 为定义在 n 维空间 R

上的某个凸集 D 上的凸函数，则 f(X ) 在 D

上的任一局部极小点 X

∗

都是 f(X) 在 D 上的全局极小点。并且极小点集为凸集。

这个定义可以直接由 theorem 1.2.6得到

推论 1.2.4 (凹函数的局部极大即全局极大). 设 f (X ) 为定义在 n 维空间 R

上的某个凸集 D 上的可微凸函数，若

∃X

∗

∈ D, ∀X ∈ D, ∇f(X

∗

)

(X − X

∗

) ⩾ 0 (1.10)

则 X

∗

为 f(X) 在 D 上的全局极小点。

推论 1.2.5 (当最小值为内点时的充分必要条件). 此时上式子收窄，直接可得

∇f(X

∗

) = 0 (1.11)

抓住邻域特点以及凸函数的定义就可以证

证明. 在局部极小值点 X

∗

的某个邻域 N(X

∗

) ⊂ D 内，任取 X ∈ N (X

∗

)，则由局部极小值的定义，有

f(X

∗

) ⩽ f (X ) (1.12)

又由凸函数的定义，因此上面所取的 X 一定在 X 与凸集上另外一点 Y 的连线上，即

X = αX

∗

+ (1 − α)Y , α ∈ [0, 1] (1.13)

因此由凸函数的定义，有

f(X

∗

) ⩽ f (X ) = αf (X

∗

) + (1 − α)f (Y ) (1.14)

由此可得

f(Y ) ⩾ f(X

∗

) (1.15)

运筹学笔记第一章非线性规划 Tsui Dik Sang

1.2.2 判定方法

1.2.2.1 直接定义法

即直接验证要判断的函数是否满足定义式1.6，

1.2.3 一阶条件

这个方法的判定定理如下

定理 1.2.6 (凸函数的一阶条件). 设 R 为 n 维空间 R

上的某个凸集，f(X ) 为定义在 R 上的一阶连续可微函数，则 f(X)

为 R 上的凸函数的充分必要条件为

∀X

, X

∈ R, f (X

) ⩾ f (X

) + ∇f(X

)

− X

) (1.16)

从集合上理解就是每一个点的切线都在函数图像的下方

1.2.3.1 二阶条件 (Hessian 矩阵法)

定理 1.2.7 (凸函数的二阶条件). 设 R 为 n 维空间 R

上的某个凸集，f(X ) 为定义在 R 上的二阶连续可微函数，则 f(X)

为 R 上的凸函数的充分必要条件为

∀X ∈ R, H(X )处处半正定 (1.17)

关于正定性的判定可以参考 theorem 1.1.1，

于是，有关凸集的问题将会变得和线性一样简单 (无需考虑局部极值和全局极值的区别)

1.3 凸规划

1.3.1 定义

定义 1.3.1 (凸规划). 对于如下的非线性规划问题

min f(X) (1.18)











(X) = 0, i = 1, 2, · · · , m

(X) ⩾ 0, j = 1, 2, · · · , p

X = (x

, x

, · · · , x

)

∈ R

(1.19)

若 f (X ) 为凸函数，且 D{X|X ∈ R

, h

(X) = 0, i = 1, 2, · · · , m, g

(X) ⩾ 0, j = 1, 2, · · · , p} 为凸集，则称该非线性规划问

题为凸规划问题。

首先 D 为凸集以及 f(X) 为凸函数是凸规划的充要条件。但是直接判定一个集合是否是凸集比较困难，不过根据 theorem 1.2.2，

可以给一个充分不必要条件

定理 1.3.1 (凸规划的充分不必要条件). 对于 denition 1.3.1中的非线性规划问题是凸规划问题的充分不必要条件为

• f(X ) 为凸函数

• g

(X), j = 1, 2, · · · , p 为凹函数 (或者说 −g

(X) 为凸函数)

运筹学笔记第一章非线性规划 Tsui Dik Sang

• h

(X), i = 1, 2, · · · , m 为线性函数 (即仿射函数，或者说是非凸非凹函数)

从图像上去理解就能知道为什么这不是必要条件。

1.4 Lagrange 乘数法

1.4.1 基本定义以及扩展

高数中学的只能处理等式约束问题，接下来要介绍的广义的 Lagrange 乘数法可以处理不等式约束问题

定义 1.4.1 (起作用的约束). 设 X

∗

为非线性规划问题的一个可行解，若对于某个不等式约束 g

(X) ⩾ 0，有 g

∗

) = 0，

则称该约束在 X

∗

处起作用，否则称该约束在 X

∗

处不起作用。

起作用约束必然会使得最优点在边界上，

尽管在这里梯度的方向无关紧要，但是还是明确一下，梯度方向是最快上升的方向

定理 1.4.1 (起约束条件下的极值点性质). 如果 X

∗

在某一个约束条件 g(X) ⩽ 0 下取得极小值 (min)，则必然有 −∇f (X

∗

)

与 −∇g(X

∗

) 反向，即

−∇f(X

∗

) = λ∇g(X

∗

), λ > 0 (1.20)

上面的这个定理对于等式约束或者不等式约束分析方法都是一样的，不等式约束多出的情况是函数极值点就在约束区域内，则此

时约束条件不起作用，此时的最优解满足







g(X

∗

) ⩽ 0

∇

f(X

∗

) = 0

(1.21)

将起作用的约束条件也写出来







g(X

∗

) = 0

−∇

f(X

∗

) = λ∇

g(X

∗

), λ > 0

(1.22)

可以发现 eq. (1.21) 是 λ = 0 的时候，

于是就可以合并出目标函数在约束条件下取得极值的充要条件











g(X

∗

) ⩽ 0

−∇

f(X

∗

) = λ∇

g(X

∗

)

λ ⩾ 0

λg(X

∗

) = 0

(1.23)

1.4.2 Karush Kuhn Tucker 条件

其实就是对上面的式子给了一个更加确切的封装

下面一步步解释要满足这个条件的奇怪原因

• 首先是关于等式约束 h

(X) = 0，其是线性函数的意思是其图像是一个超平面，如果不是超平面的话，一定会出现两点连线不在该集合内的情况 (可以想

象二维的曲面就知了)

• 接着关于不等式 g

(X) ⩾ 0，其实是 eq. (1.6) 的推论，不做过多解释，由此即可理解，考试亦能明白

运筹学笔记第一章非线性规划 Tsui Dik Sang

定理 1.4.2 (单一约束条件下的 Karush Kuhn Tucker 条件). 对于优化问题







min

X∈R

f(X)

g(X) ⩽ 0

(1.24)

构造 Lagrange 函数

L(X, λ) = f ( X ) + λg(X) (1.25)

对于极小值点 X

∗

，存在 λ

∗











∇

L(X

∗

, λ

∗

) = 0

g(X

∗

) ⩽ 0

∗

⩾ 0

∗

g(X

∗

) = 0

(1.26)

推论 1.4.3 (约束条件下极值点的判定). 在满足 eq. (1.26) 的条件下，且 L 在 (X

∗

, λ

∗

) 处的正定，或者说 Hessian 矩阵在该

点处正定，则 X

∗

为该约束条件下的极小值点。

1.4.3 可行下降方向

先给出两个定义

定义 1.4.2 (可行方向). 方向 P ∈ R

再点 X

∈ D 处为可行方向的条件是

∃λ

, ∀λ ∈ [0, λ

], X

+ λP ∈ D (1.27)

这意味着这一步迭代还不会出界，因此是“可行的”。

定义 1.4.3 (下降方向). 方向 P ∈ R

在点 X

∈ D 处为下降方向的条件是

∃λ

> 0, f(X

+ λP ) < f (X

), ∀λ ∈ (0, λ

] (1.28)

这意味着这一步迭代是可以得到更优的

将上面两个定义结合起来就是可行下降方向了，不过用微分形式进行表达会更具清晰，对于约束条件不等式的大于小于符号

不同定义会相反，下面以一种优化问题为例进行定义

定义 1.4.4 (可行下降方向). 对于

min

X∈R

f(X), g(X ) ⩾ 0 (1.29)

P 是可行下降的充分条件是

∇g(X

)

P ⩾ 0, ∇f ( X

)

P < 0 (1.30)

显然

运筹学笔记第一章非线性规划 Tsui Dik Sang

推论 1.4.4 (在最优点不存在可行下降方向). 若 X

∗

为该优化问题的最优点，且 f (X ), g(X ) 在 X

∗

处可微，则在 X

∗

处不

存在可行下降方向。即满足







∇g(X

∗

)

P > 0

∇f(X

∗

)

P < 0

(1.31)

如果我们从几何上去理解 eq. (1.30)，则

推论 1.4.5 (可行下降方向的几何意义). 如果 P 为可行下降方向，则 P 与 ∇g(X

) 和 −∇f(X

) 的夹角均小于等于 90 度。

1.4.4 多约束条件下的 Karush Kuhn Tucker 条件

思路是一一对应，

定理 1.4.6 (多约束条件下的可行下降方向). 如果约束条件是 g

(X) ⩾ 0, j = 1, 2, · · · , p，也就是都要满足可行下降，即 P

与每一个约束条件的梯度夹角小于 90 度, 且与 −∇f(X

) 夹角小于 90 度，

满足这种情况则 ∇f(X

∗

) 一定要在 ∇g

∗

), j = 1, 2, · · · , p 的锥空间内，不然的话 theorem 1.4.6成立，这个点还不是最优点，

于是我们就可以得到多约束条件下的 Karush Kuhn Tucker 条件，

定理 1.4.7 (多约束条件下的 Karush Kuhn Tucker 条件). 对于规划问题







min

X∈R

f(X)

(X) ⩾ 0, j = 1, 2, · · · , p

(1.32)

∇f(X

∗

) 在 ∇g

∗

), j = 1, 2, · · · , p 的锥空间内则此时 X

∗

为该优化问题的极小值点。数学表示如下











∇

f(X

∗

) −

j=1

∗

∇

∗

) = 0

∗

) ⩾ 0, j = 1, 2, · · · , p

∗

⩾ 0, j = 1, 2, · · · , p

∗

) = 0, j = 1, 2, · · · , p

(1.33)

其中等式约束也被归入不等式约束中

这里的约束条件是小于某值！注意与单约束的情况不同，这是受制于 ppt，我的笔记尽量与 ppt 一致，但是就出现了这样的混淆情况，不过理解原理

后其实可以手动确定方向，也强烈建议这样子做进行验算

这个条件不仅是可以列，也可以真正用于求解，参见 ppt 上的题目

然后注意前面的两行都是矩阵方程，需要列的等式可能不止一个

第二章线性规划

2.1 线性规划的基本概念

2.1.1 基本元素

• 决策变量

• 目标函数

• 约束条件

2.1.2 形式

2.1.2.1 代数形式

定义 2.1.1 (线性规划的一般形式).

max z =

j=1

(2.1)

s.t.











j=1

= b

, i = 1, 2, . . . , m, b

> 0

≥ 0, j = 1, 2, . . . , n

(2.2)

其中，x

为决策变量，c

为价值系数，a

为消耗系数，b

为资源限制系数。

下面为了方便先讨论等式约束的情况

2.1.2.2 矩阵形式

推论 2.1.1 (线性规划的矩阵形式).

max Z = CX (2.3)

s.t.







AX = B

X ⩾ 0

(2.4)

其中

X =













, C =

· · · c

, B =













, A =







· · · a







(2.5)

运筹学笔记第二章线性规划 Tsui Dik Sang

2.1.2.3 向量形式

与矩阵形式类似，写出来是为了之后可以少写一些东西

推论 2.1.2 (线性规划的向量形式).

max Z = CX (2.6)

s.t.











j=1

= B

⩾

(2.7)

其中













(2.8)

2.1.3 标准形式的转换

完成这种题的诀窍包括

• 首先不能抄错数

• 然后记得补零

• 反号和大于小于的时候要格外小心

• 被换掉了的变量一定要带入新变量！

• 右边的数值不能为负！

• 无约束的变量可能不会标，这一定要发现后将其代换!

按照下面的步骤来，最快最方便

2.1.3.1 独立变量的反转

先看最后一行的独立变量，如果存在小于零的约束，就取负号，比如，若存在约束

⩽ 0 (2.9)

那么就取

′

= − x

⩾ 0 (2.10)

即可

2.1.3.2 自由变量的消除

如果某个变量 x

是无约束，可以转换成







= x

′

− x

′′

′

, x

′′

⩾ 0

(2.11)

运筹学笔记第二章线性规划 Tsui Dik Sang

2.1.3.3 松弛变量引入

首先引入的松弛变量也是正的，因此对于 ⩽ 型约束，引入 +x

，的约束反之引入 −x

，的约束

2.1.3.4 目标函数的调整

右端还不能是负数，于是直接两边同时反转即可

2.1.3.5 等式约束的调整

如果是 max，不用管，如果是 min，就直接反转即可转成 max

2.1.3.6 人工变量法

这是针对还需要列单纯形表的情况，后面会说，这里先不赘述

2.1.4 解

下面给出一些基本前提

这都是在标准形式之下的！所以如果一开始非标准的话要先转换

• X 为 n 维列向量

• C 为 n 维行向量

• B 为 m 维列向量

• A 为 m × n 矩阵，且 rank(A) = m < n

定义 2.1.2 (可行解). 满足约束条件 eq. (2.2) 的解称为可行解

定义 2.1.3 (最优解). 在所有可行解中，使目标函数取得最大值的可行解称为最优解

定义 2.1.4 (基). 若 B 是 A 的一个 m × m 非奇异子矩阵，则称 B 为 A 的一个基

如果将非基的变量设为 0，那么对于任意的一个基都可以解出一个解

= ( x

, x

, . . . , x

)

(2.12)

结合非基变量 x

m+1

, x

m+2

, . . . , x

= 0，就可以得到一个基本解 (简称基解)

定义 2.1.5 (基本解).

X = (X

, 0, 0, . . . , 0)

(2.13)

称为 A 的一个基本解

下面开始关系非负的约束条件，然后，事实上

至于证明，我猜你首先要对其几何意义有一个清晰的理解，不过现在还没有，那么我们就先放一放，先记住结论

运筹学笔记第二章线性规划 Tsui Dik Sang

推论 2.1.3 (基解与可行解的关系). 基本解不一定是可行解，可行解也不一定是基解

推论 2.1.4 (退化解). 在基本可行解中又存在一个或多个基变量为 0 的解，称为退化基本可行解，简称退化解

推论 2.1.5 (基可行解与最优解的关系). 如果线性规划问题存在最优解，则至少存在一个基可行解是最优解

通过枚举基解，然后检验是否可行来得到基可行解——因此这种方法其实是枚举的，不算是通式!

看下面的图来理清楚关系，至于实际的几何理解目前还没有找到，但是结论可记。

图 2.1: 可行解等的关系

之后做几道求一个规划的基本可行解以及退化解的练习题就熟练了。

2.1.5 基本定理

在 denition 1.2.1已经定义了凸集，下面给出更多定义

定义 2.1.6 (凸组合). 设 X

, X

, . . . , X

为 R

中的 n 个向量，若存在实数 α

⩾ 0, i = 1, 2, . . . , n ，且满足

i=1

= 1 (2.14)

则称向量

Y =

i=1

(2.15)

为向量 X

, X

, . . . , X

的一个凸组合

关于线性规划的顶点，与其说是一个结论，不如说是一个定义

运筹学笔记第二章线性规划 Tsui Dik Sang

定义 2.1.7 (顶点). 设 D ⊆ R

为 n 维空间 R

上的某个凸集，若 X ∈ D，且 X 不能表示成 D 中两个不同点的凸组合，则

称点 X 为凸集 D 的一个顶点

容易根据线性性证明

定理 2.1.6 (可行域的凸性). 若线性规划问题存在可行域，则其可行域

D = {X |AX = B, X ⩾ 0} (2.21)

是一个凸集

接着由基和可行解的定义等可以得出

引理 2.1.7 (正分量对应列向量的无关性). 对于线性规划问题的可行解

X = (x

, x

, . . . , x

)

(2.22)

是基本可行解的充分必要条件是其正分量所对应的列向量线性无关

于是代数上的解就和几何联系在一起了

定理 2.1.8 (基可行解与顶点的关系). 线性规划问题的基本可行解 X 对应于可行域 D 的一个顶点，反之亦然

证明先从略

那顶点和可行域内的点的关系呢？从共线的角度可以阐述清楚这个问题

引理 2.1.9 (可行域与顶点的关系). 若 K 是有界凸集，则任意一点 X ∈ K 可表示为 K 的顶点的凸组合

因此有

定理 2.1.10 (最优解与顶点的关系). 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上取得最优

证明. 只要证明 D 中任意两点连线上的一切点均满足线性约束条件即可。

任取 X

(1)

, X

(2)

∈ D，满足







(1)

= B, X

(1)

⩾ 0

(2)

= B, X

(2)

⩾ 0

(2.16)

则对任意的 α，0 < α < 1，有

X = αX

(1)

+ (1 − α)X

(2)

(2.17)

AX = A[αX

(1)

+ (1 − α)X

(2)

] (2.18)

= αAX

(1)

+ (1 − α)AX

(2)

(2.19)

= αB + (1 − α)B = B (2.20)

又因为 X

(1)

⩾ 0，X

(2)

⩾ 0，且 α > 0，1 − α > 0，所以 X ⩾ 0。

由此可知 X ∈ D，即 D 是凸集。

运筹学笔记第二章线性规划 Tsui Dik Sang

2.2 单纯形法

PPT 上的内容有点零散抽象，笔者一开始怎么也看明白原理，更别提后面的表格法了，后面跟书本 P31 的例题 2-7 推演了

一次，豁然开朗，下面是笔者的理解——先从例题开始说明原理

2.2.1 引入

有如下的标准线性规划问题

max z = 2x

+ 3x

(2.23)











+ 2x

+xx3 = 8

+ x

= 16

= 12

, x

⩾ 0

(2.24)

2.2.1.1 寻找基变量

从构造上不难看出，后面这三个实际上是松弛变量，从形式上来看也是基变量

因此对于系数矩阵

A == (P

, P

) =







1 2 1 0 0

4 0 0 1 0

0 4 0 0 1







(2.25)

可以得到一个单位基矩阵

B = (P

, P

) =







1 0 0

0 1 0

0 0 1







(2.26)

2.2.1.2 移非基变量到右边

得到











= 8 −x

− 2x

= 16 −4x

= 12 − 4x

(2.27)

做到这里其实可以得到一组满足约束条件的解

X = (0, 0, 8, 16, 12)

(2.28)

注意，这只是满足约束条件的，并非最优，是否最优下面将会判断

2.2.1.3 判断是否最优

由上面的解代入 eq. (2.23) 发现结果为零，并且后面 x

, x

的系数均为正，也就是说如果这两个非基变量不为零的话，问题

可以得到优化，那是否可以呢？答案是显然的，

不过在这之前先看系数大小，发现 x

的系数更大，因此选择 x

进入基变量

对于无法一眼看出的怎么办呢？后面会介绍人工变量的概念

运筹学笔记第二章线性规划 Tsui Dik Sang

2.2.1.4 换基

实际上就是尝试调大 eq. (2.27) 中的 x

，显而易见的，由于在该式中 x

的系数均为负，因此不能无限调大，需要满足

, x

⩾ 0 (2.29)

的条件不变，因此极限情况下的 x

的值为 3，此时成功使得原来的一个基变量 x

变为 0，成为非基变量，

而这时候还没有结束，还需要经过一些基础的线性行列式变换将 x

完全挪动到左边且系数为 1，











= 2 −x

−

= 16 −4x

= 3 −

(2.30)

同时将目标函数写成非基变量的形式

z = 9 + 2x

−

(2.31)

此时换基完成。

2.2.1.5 重复判断是否最优

此时解为 X = (0, 3, 2, 16, 0)

, 最优值为 9，发现目标函数中 x

的系数为正，因此还可以继续优化，于是再次换基，周而复

始，直到所有的系数都为负为止，这时候再换将不会再对目标函数有优化作用了。

推论 2.2.1 (最优解不唯一的情况). 如果在最终存在非基变量的检验系数是 0，

则此时还可以换入，且最优函数值不会变，因此最优解不唯一，有无穷多的最优解理解了原来后这里对这题之后的解答从略的了

2.2.2 代数形式的单纯形法

在这个一般化的过程中尽量省去了眼花缭乱的代数式，只讲关键思路，详情可看书。

假设一般的线性规划问题如下

max z =

j=1

(2.32)

s.t.











j=1

= b

, i = 1, 2, . . . , m, b

> 0

⩾ 0, j = 1, 2, . . . , n

(2.33)

注意 b

> 0 是为了保证初始基可行解的存在性，这也提示如果题目一开始不是标准形式的话需要进行转换，在之后对偶

单纯形的话就反其道而行之了

2.2.2.1 寻找或者构造基变量

一定可以找到一个初始的单位对角矩阵

然后按照前面题目的方法就可以将基变量用非基变量表示出来

= b

−

j=m+1

, i = 1, 2, . . . , m (2.34)

本来想先从矩阵直观，后面发现绕不过这个表，所以还是先从表进行理解

不能的话就用人工变量法，这个后面会介绍

运筹学笔记第二章线性规划 Tsui Dik Sang

相应的目标函数可以化成只有基变量的形式

z =

i=1

j=m+1

−

i=1

(2.35)

为了不再混淆，定义一个之后会反复用到的量

定义 2.2.1 (检验数).

= c

−

i=1

, j = m + 1, m + 2, . . . , n (2.36)

其实这个并不难理解，将其记成与本行以及 C

相关的量即可

2.2.2.2 判断最优性并选择换入变量

同理的，看最后面的系数是否都为负，若是则最优，否则选取系数最大的非基变量 x

，准备进行换基

2.2.2.3 计算 θ

确定换出变量

对于 eq. (2.34) 中 a

> 0 的行，由非负性知道

⩽ θ

(2.37)

我们想要 x

尽可能大，但是要满足所有的变量都大于零的约束，因此取所有 θ

中的最小值对

应的行的基变量 x

作为换出的

变量因此就可以进行一轮换基

推论 2.2.2 (无最优解的情况). 如果不存在 a

> 0 的行，则线性规划问题无界，即无最优解

引理 2.2.3 (摄动原理). 如果存在两个以及遇上相同的最小比值时，取下表最大的那个作为换出变量对应的行，按此方法一

定能避免循环现象出现

这个条件下意味着此时的 x

将不会受到任何限制可以无限取大，那自然就不存在最优解了

实际上，在上一步的时候就可以确定，只需要检查所有系数大于零的非基变量的 a

是否都小于等于零即可，如果真无最优解的

话可以省去工作量。

注意，对于这种单纯形法只会出现无最优解的情况，无解的情况只会在下面将会介绍到的引入人工变量法时出现

我没想到在 12.26 复习的时候还发现你居然糊里糊涂不知道这是什么——“糊涂的很”！

因此可以理解为这个 min 为无奈之举

运筹学笔记第二章线性规划 Tsui Dik Sang

2.2.3 表格单纯形法

上面的思路可以通过构造表格进行标准化将优化对象也写进来

+ a

1m+1

m+1

+ a

1m+2

m+2

· · · + a

= b

+ a

2m+1

m+1

+ a

2m+2

m+2

· · · + a

= b

+ a

mm+1

m+1

+ a

mm+2

m+2

· · · + a

= b

−z + c

+ c

· · · + c

m+1

+ c

m+2

· · · + c

= 0

(2.38)

写成增广矩阵即可让 z 与其余基变量构成一个基







0 1 0 · · · 0 a

1m+1

1m+2

· · · a

0 0 1 · · · 0 a

2m+1

2m+2

· · · a

0 0 0 · · · 1 a

mm+1

mm+2

· · · a

1 c

· · · c

m+1

m+2

· · · c







(2.39)

通过线性变换变成基







0 1 0 · · · 0 a

1m+1

1m+2

· · · a

0 0 1 · · · 0 a

2m+1

2m+2

· · · a

0 0 0 · · · 1 a

mm+1

mm+2

· · · a

1 0 0 · · · 0 c

m+1

−

i=1

im+1

m+2

−

i=1

im+2

· · · c

−

i=1







(2.40)

通过线性变换可以换基，注意，这里只能对方程组进行行变换才能确保仍然成立。表的代数表示不再赘述，请看下一部分的矩阵

表于是求解步骤可分为

• 列表

• 确定换入变量

• 算出 θ

确定换出变量

• 换基

• 进行行变换使得刚换入的变量位置变成基向量的形式

• 检查检验数是否都为负或零，如果不是，继续循环

具体的不再赘述，做多几道题就非常清楚了。

2.2.4 矩阵表示的求解过程

在考虑了松弛变量的情况下方程标准形式可以表示为

max z = CX (2.41)

s.t.







AX + X

= b

X ⩾ 0

(2.42)

运筹学笔记第二章线性规划 Tsui Dik Sang

列表

最终根据单纯形法的停止条件知道







C − C

−1

A ⩽ 0

−C

−1

⩽ 0

(2.43)

当然，矩阵表示虽然清晰，但是手算需要记一些公式，因此常用的还是代数方法因此最终得到的最优解为

推论 2.2.4 (最优解的矩阵表示). 不论顺序，将最终单纯形表中的基变量先写为 X

，那么最优解看此时的 b 列为

∗

= ( B

−1

b, 0, 0, . . . , 0)

(2.44)

得到的最优目标函数值为

∗

= C

−1

b (2.45)

然而还是有一点需要注意的是，松弛变量的解实际上是没有意义的——我的理解。

2.2.5 人工变量法

处理的是无法直接找出基变量的情况

2.2.5.1 大 M 法

手动添加变量，并且这些变量取值只能为零，如何实现呢，使得其在目标函数中的系数为 −M ，M 为一个非常大的正数，因

此任何其不为零的解都不可能是最优解。

这个方法手工列表格的话可以轻松判断，但是如果是计算机处理庞大数据的话这个 M 的大小就不好确定了。

推论 2.2.5 (无解的情况). 如果最终人工变量不为零 (也就是说没有被出基掉)，则原式无解

注意人工变量是早在标准型后发现无基变量后才加入，因此遇到一个问题首先还是要检查是否是标准型，还是有可能要先

依靠松弛变量转成标准型再加入人工变量

2.2.5.2 两阶段法

我们希望人工变量是零上面的式子成立，那么完全可以再加一个目标函数为

min w =

i=1

(2.46)

其中 x

为人工变量，约束条件为添加了人工变量的约束条件。利用单纯形法求解这个问题，如果最后人工变量不为零，则原式

无解

，如果为零，则将人工变量去掉，继续用单纯形法求解原式即可。(例子见书本 P47)

2.3 对偶问题

课本上的租用设备的例子就很好的例子。这里不废话，直接上定义

这个结论待证明

运筹学笔记第二章线性规划 Tsui Dik Sang

2.3.1 定义

定义

2.3.1 (

对偶问题

对于原问题

max z = CX (2.47)

s.t.







AX ⩽ b

X ⩾ 0

(2.48)

其对偶问题为

min w = Y b (2.49)

s.t.







Y A ⩾ C

Y ⩾ 0

(2.50)

对于混合约束的情形，可参考下表给出的原问题与对偶问题之间的一一对应关系：

这个表最好直接记住！否则需要记住对偶问题的来历，详见 ppt 中给的例子，但是应该只能辅助理解几个符号的变化，并

不能给出一个更加抽象的理解

原问题对偶问题

max z min w

n 个变量 n 个约束条件

约束











⩽

⩾

变量











⩾ 0

无约束

⩽ 0

m 个约束条件 m 个变量

变量











⩾ 0

无约束

⩽ 0

约束











⩾

⩽

表 2.1: table

原问题与对偶问题的对应关系（max → min）

原问题对偶问题

min z max w

n 个变量 n 个约束条件

约束











⩽

⩾

变量











⩽ 0

无约束

⩾ 0

m 个约束条件 m 个变量

变量











⩽ 0

无约束

⩾ 0

约束











⩾

⩽

表 2.2: table

原问题与对偶问题的对应关系（min → max）

从影子价格的角度来理解一下第一个表

影子价格就像资源的“市场价”。在 max 原问题中，原约束（资源有限）对应影子价格 0（价格不能负）。原变量 0（决

策非负）对应影子价格的约束（确保定价覆盖利润）。这样，对偶问题最小化总影子成本，与原问题最大化利润互补。

实际上如果只背一个表，可以在遇到另外一个转换的时候先将 min 转 max，然后再使用左表，但是变换后会发现变量符号

变了，但是这时候实际上问题不变的，仔细看是因为系数矩阵目标也发生了变化，这也意味着下面很多的结论都用不来哦，所以

极度不建立议只背一个表，还是直接对应吧

2.3.2 性质

2.3.2.1 基本性质

首先应该有

当然，这其实给我们的检验提供了一种思路。

运筹学笔记第二章线性规划 Tsui Dik Sang

定理 2.3.1 (对称性). 对偶问题的对偶问题即为原问题

定理 2.3.2 (弱对偶定理). 若

X 是原问题的任意可行解，

Y 是对偶问题的任意可行解，则有

X ⩽

Y b (2.51)

因此可以得到一个在解的存在性上的结论

推论 2.3.3 (解的存在性). 如果原问题有无界解，则对偶问题无可行解，反之亦然

通过一些简单的矩阵运算上面的是易证的

推论 2.3.4 (最优性). 如果

X 和

Y 分别是原问题和对偶问题的可行解，且满足

X =

Y b (2.52)

则

X 和

Y 分别是原问题和对偶问题的最优解

推论 2.3.5 (最优对偶解). 若 B 为原问题的最优基，则 Y

∗

= C

−1

为对偶问题的最优解

证明需要用到表，不过也不难，看书 P75。

2.3.2.2 互补松弛性

接下来将介绍一个对于快速找到最优解非常有用的性质

定理 2.3.6 (互补松弛性定理). 如果

X 和

Y 分别是如下问题的两个解

max z = CX

s.t.







AX + X

= b

X, X

⩾ 0

(2.53)

min w = Y b

s.t.







Y A − Y

= C

Y , Y

⩾ 0

(2.54)

那么其为对应两个问题最优解的充要条件为







Y X

= 0

X = 0

(2.55)

或者写成







Y (b − A

X) = 0

(C −

Y A)

X = 0

(2.56)

注意，着意味着

运筹学笔记第二章线性规划 Tsui Dik Sang

推论 2.3.7 (互补松弛性的应用). 如果其对偶问题的松弛变量不为零，那么其原问题的对应变量必为零，反之亦然。

根据这个定理，可以利用已知对偶问题解的性质将原问题中的不等式约束轻松变成等式约束，从而大大简化问题的求解难度。

不过这种题的技巧性相当的强大，下面根据我做到的题的一些技巧进行总结

• (习题解答 P62)

– 首先根据对偶问题的解明确对偶问题的符号，进而得到对偶问题的松弛变量是否为零性

– 然后已经由此可以判断出原问题中一些变量是否为零，同时松弛变量是否为零也已经确定了，

– 然后就是直接对着等式解方程的事情了

可以参考一些例题

2.3.3 对偶单纯形法

2.3.3.1 引入

之前普通的单纯形法是从一个可行解开始，迭代出最优解，而对偶的单纯形法则是从一个最优基开始，迭代出一个可行解，

就是最优解。

即先取一个最优基

C − C

−1

A ⩽ 0 (2.57)

定义 2.3.2 (正则解). 满足 eq. (2.57) 的解称为正则解

推论 2.3.8 (正则解的非可行性质). 正则解不一定是可行解，但是可行的正则解一定是最优解

在迭代过程中保持上式成立，迭代至 B

−1

b ⩾ 0

, 就是最优解

2.3.3.2 通式方法

考虑一个标准的问题

max z = CX (2.58)







AX = b

X ⩾ 0

(2.59)

设 B 为基，对应的基向量为 X

, 当非基变量都是零时，可以得到 X

= B

−1

b，

如果 B

−

b 中有负分量，那就说明还不是可行解，还需要换基，不过着依据的就是 B

−

b 这一行进行换了。将最小的 (B

−

的 x

作为换出变量，

然后开始确定换入变量，找各个非基变量的第 i 行系数，如果都是正的

则原问题无解，否则找到

θ = min



− z



ij<0



(2.60)

刚做了一道习题解答书 P63 的题目

这是标准问题解的非负性决定的，具体不清楚可以再去看表

同样的为何选最小是被证明的，证明从略，注意，最小的是负数，所以也可以说是取负数中绝对值最大的

这意味着在换出后不能保证 eq. (2.57) 成立

运筹学笔记第二章线性规划 Tsui Dik Sang

将 j 作为换入再来

14 15

图 2.2: 对比单纯形法与对偶单纯形法

我仍然打算用课本上的一道题来演练 (P82-3.6)

2.3.4 敏感性分析

这一定是考试的重点，我不希望你是考死记硬背记住的，这完全可以根据表格来很轻松的得到，这才是重点，去看看题目

吧

也就是说系数的改变对最优解的影响——注意，对于目标值的影响的研究并没有意义 (肯定会变)，然而如果解没有变的话重

新算一次即可，因此我们这里将要探究是解是否会发生变化的问题。

表 2.3: 单纯形表（灵敏度分析）

C C

b X

−1

b I B

−1

N B

−1

−Z −C

−1

b 0 C

− C

−1

N −C

−1

2.3.4.1 资源系数 b

的变化：影子价格

这也是没有给出证明的，姑且记住吧，

实际上方法大同小异，我觉得更难的是一种直觉上的理解，这也是我第二轮复习的目的，就是要尝试建立一个故事线很好的理解这些算法

运筹学笔记第二章线性规划 Tsui Dik Sang

定义 2.3.3 (影子价格). 在保持其他参数不变的前提下，某个约束的右边项在一个微小的范围内变动一个单位导致的最优目

标函数值的变动

影子价格实际上就是对偶解

定理 2.3.9 (单纯形表中的影子价格). 由单纯表直接可以得影子价格

∗

= C

−1

(2.61)

即对偶变量 y

就是第 i 个约束条件的影子价格

证明必须要给出来才能加深印象

证明. 由表格

∗

= C

−1

b = y

∗

+ y

∗

+ · · · + y

∗

(2.62)

然后根据影子价格的偏导定义，

∂Z

∗

∂b

= y

∗

(2.63)

观察表格，发现只有 B

−1

b 会受到影响——这意味着变化后可能就不是可行解了。因此分两种情况

• 变化后仍然满足 B

−1

b ⩾ 0，则最优解不变

• 变化后不满足 B

−1

b ⩾ 0，则需要用对偶单纯形法继续变换直到这个正则解变成可行解

2.3.4.2 价值系数 c

的变化

由表，会影响检验系数，需要分两种情况来讨论

• 变化的是非基变量的系数：也就是 C

，

′

= c

+ ∆c

(2.64)

⇒ σ

′

= c

+ ∆c

− C

−1

= σ

+ ∆c

(2.65)

由此可见，没有变到矩阵乘法内，所以结论比较简单

推论 2.3.10 (非基变量系数变化的影响). 因此只需要保证

′

= σ

+ ∆c

⩽ 0 (2.66)

即可保证最优解不变

• 变化的是基变量的系数：也就是 C

，进行推导的仍然是非基变量的检验数，不过这时候的 ∆ 就在外面了

′

= c

− (C

+ ∆C

−1

−

∆

−1

= σ

−

i=1

∆c

¯a

(2.67)

为了方便假设每次只变一个，比如只变 c

，那么下面的结论才成立

还是需要手写推导一下加深印象

运筹学笔记第二章线性规划 Tsui Dik Sang

推论 2.3.11 (基变量系数变化的影响). 因此只需要保证

⩽ ∆c

⩽ δ

(2.68)

其中











= max

¯a



¯a



= min

¯a



¯a



(2.69)

即可保证最优解不变

2.3.4.3 技术系数 a

的变化

这是最麻烦的，牵一发而动全身。也是分两种情况来讨论

然而如果只是涉及小变动的话直接肉眼利用变换后的表格进行计算比下面的矩阵公式要方便 (习题解答 P67 题) 就算式

变一列的情况也不用全部重算，也只是针对变的这一类的变量

• 变化的是非基变量的系数：

′

= σ

− C

−1

∆a

(2.70)

⇒ Y ∆a

⩾ σ

(2.71)

如果变化的只有第 i 个分量则进一步可以推出

∆a

⩾

(2.72)

• 基变量发生变化，似乎并没有很好的通式，不过仍能通过计算 b 列以及检验数来判断是否还是可行解或者最优解，进而采

取下一步的行动

2.3.4.4 增加变量

假设新增了 x

n+1

, 那么也会多一个价值系数 c

n+1

和一个技术系数列 a

n+1

，那么问题变为

max Z = C

X + c

n+1

(2.73)

s.t.







AX + a

n+1

= b

X, x

n+1

⩾ 0

(2.74)

求解的步骤是先假设可行解不变——这也意味着 x

n+1

= 0，解为

′

∗

(2.75)

在此基础上列单纯形表，容易推得

n+1

= c

n+1

− C

−1

n+1

(2.76)

如果 σ

n+1

⩽ 0，则最优解不变，否则使用 x

n+1

作为换入变量进行换基，直到最优解为止。

根据单纯形法矩阵表示中矩阵的单行推导得

由此可知，实际上两种单纯形法是交织进行的，哪一种方便用哪一种，并不矛盾，看初始条件决定

运筹学笔记第二章线性规划 Tsui Dik Sang

2.3.4.5 新增约束条件

假设新增的不等式是

m+1,1

+ a

m+1,2

+ · · · + a

m+1,n

⩽ b

m+1

(2.77)

先检查原问题最优解是否满足这个约束条件，如果满足则最优解不变，否则

• 引入松弛变量

m+1,1

+ a

m+1,2

+ · · · + a

m+1,n

+ x

n+1

= b

m+1

(2.78)

• 然后将其作为基变量新加一行在单纯形表中，系数为 a

m+1,j

(j = 1, 2, . . . , n)，右边项为 b

m+1

• 如果此时其他基向量不是单位向量，则要通过初等行变换先变过去

• 之后的步骤仍然是单纯形法

如果增加的是等式

m+1,1

+ a

m+1,2

+ · · · + a

m+1,n

= b

m+1

(2.79)

那么还是先检验最优解是否满足，不满足就要引入人工变量，再用大 M 法或者两阶段法求解。

表 table 2.3是重点，其实对矩阵熟悉的话也很好推，敏感性本身也是据此进行，不过记住一些矩阵运算可以规范运算不容

易出错罢了。

之后，请及时做题！多多练习，并且，留意一下多个约束变量同时变化的情况 (参照某一道作业题)——出生题来的

2.3.5 参数线性规划

∗

定义 2.3.4 (参数线性规划 (价值系数)).

max z = (C + λC

∗

)X (2.80)

s.t.







AX = b

X ⩾ 0

(2.81)

定义 2.3.5 (参数线性规划 (资源系数)).

max z = CX (2.82)

s.t.







AX = b + λb

∗

X ⩾ 0

(2.83)

ppt 参数规划最后一页有一个表，吃透了就没有人任何问题了。

指的是原来的向量在加入了这一行后在这一行可能不为零，要先变换为零

不是考试重点，但是理解一下对于更加透彻理解单纯形表等都有帮助

运筹学笔记第二章线性规划 Tsui Dik Sang

2.4 运输问题

定义 2.4.1 (运输问题). 某种物资有 m 个产地 A

, A

, . . . , A

，每个产地的供应量分别为 a

, a

, . . . , a

；有 n 个销地

, B

, . . . , B

，每个销地的需求量分别为 b

, b

, . . . , b

；假定从产地 A

向销地 B

运输每单位物资的运输费用为 c

，需要

求解运货量 x

，使得总运输费用最小，并且满足各产地的供应量和各销地的需求量。

写成数学形式

定义 2.4.2 (运输问题的数学形式).

min z =

i=1

j=1

(2.84)

s.t.











j=1

= a

, i = 1, 2, . . . , m

i=1

= b

, j = 1, 2, . . . , n

⩾ 0, i = 1, 2, . . . , m; j = 1, 2, . . . , n

(2.85)

如果产销平衡，则

i=1

j=1

(2.86)

2.4.1 基本建模

引理 2.4.1 (平衡运输问题解的存在性问题). 平衡运输问题必有可行解与最优解

上面的证明不难，给一个例子 x

就是

接下来看求解，实际上，运输问题的矩阵相当的稀疏 (这个自己看书)

• 是一个 (m + n) ∗ (mn) 的矩阵

• 系数矩阵上只有 0 和 1

• 前 m 行表征的是产量平衡，后 n 行表征的是需求平衡

如果用系数列向量表示

推论 2.4.2 (运输问题的列向量).

= (0 , · · · , 1, · · · , 0, 1, · · · , 0)

= e

+ e

m+j

(2.87)

其中 e

为第 i 个单位向量

接下来还可以证明

推论 2.4.3 (运输矩阵的秩). 运输问题的系数矩阵 A 的秩为 m + n − 1

运筹学笔记第二章线性规划 Tsui Dik Sang

先证上界，显然吗，前 m 行行向量的和等于后 n 行行向量的和，因此显然秩小于 m+n；进一步的，去掉第一行，选取 1, n, 2n, . . . , (m−

1)n 列，可以构造出一个如下子式

|D| =



0 0 · · · 0 1 0 0 · · · 0

1 0 · · · 0 0 1 0 · · · 0

1 0 · · · 0 1 1 1 · · · 1

0 1 · · · 0 0 0 0 · · · 0

0 0 · · · 1 0 0 0 · · · 0



= ± 1 ̸= 0 (2.88)

所以其秩至少为 m + n − 1，综上可知其秩为 m + n − 1。

2.4.2 表上作业法

这是一个数独游戏

2.4.2.1 确定初始基可行解

• 最小元素法：按照最小的元素逐行画

• 西北角法：从左上角开始逐行画

• Vogel 近似法：计算每行每列的罚值，选择罚值最大的行或列进行分配 (综合了最小元素法的短视以及西北角法的稳妥)

推论 2.4.4 (三种方法的优劣). 最小元素法容易陷入局部最优，西北角法比较稳妥，而 Vogel 近似法综合了两者的优点，一

般效果较好

推论 2.4.5 (数字格的个数). 数字格的个数是 m + n − 1

上面的证明和秩关系不大，实际上是通过划线的次数来得到的

遇到过一道对于初始解的存在性问题

易错辨析：在运输问题中，只要任意给出一组含有 m + n − 1 个非零的 {x

}，且满足

j=1

= a

和

i=1

= b

，则一

定存在一个可行解使得这些 x

为其基本变量吗？

答案：错误。

原因：仅仅满足数量和供需平衡是不够的，这 m + n − 1 个非零变量还必须不包含闭回路（即线性无关）。如果包含闭回

路，则对应的列向量线性相关，无法构成基。

反例：3 × 3 运输问题，基变量应为 3 + 3 − 1 = 5 个。若非零格分布如下：







• •

•







虽然有 5 个非零格，但左上角 4 个构成闭回路，且右下角孤立（不连通），故不能构成基变量。

注意，每次都要计算罚数，划掉的行都罚数可能会发生变化

可能会出判断题或者一些小题？我不确定

运筹学笔记第二章线性规划 Tsui Dik Sang

2.4.2.2 解的最优性检验

闭回路法有点影子价格的意味，具体步骤如下

• 对于一个空格，将其增加变为 1，

• 其横向或者竖向遇到的第一个数字格-1.

• 最后兜兜转转回来，

• 从新计算这个变化带来的价格差 σ

增加的位置的c

−

减少的位置的c

从而对于每一个空格都得到了一个类似于检验数的东西，如果这个值都大于等于零，则最优，否则意味着这轮改变可以降低价格，

那肯定不是最优，可以继续寻找最优解

推论 2.4.6 (闭回路的存在性与唯一性). 对于任意一个空格，都存在唯一的闭回路

注意，虽然对于其相邻可能有多个数字格，但是接着走下去不一定能找到闭合的回路，最终闭合的只有一条，因此上式是成立的。

对偶变量法 (位势法) 首先可以写出原问题的对偶问题

max Z

′

i=1

j=1

(2.89)

s.t.







+ v

⩽ c

, i = 1, 2, . . . , m; j = 1, 2, . . . , n

, v

无约束

(2.90)

然后根据单纯形表

= c

− C

−1

(2.91)

其中

−1

= ( u

, u

, . . . , u

, v

, . . . , v

) (2.92)

之前又知道 P

= e

+ e

m+j

，因此

推论 2.4.7 (基变量检验数).

= c

− (u

+ v

) (2.93)

令其为零即可得到 u

和 v

的值，这也被称为行位势和列位势，这时候就可以算出非基变量的检验数 (也就是空格的检验数)，检

验所有的非基变量，如果都大于等于零，则最优，否则继续迭代——迭代方法下面会讲。

2.4.2.3 闭回路调整法——应该是唯一的方法

上面的闭回路只是用 1 作为增量进行调整，这真只能起到检验的作用，如果想要优化，就需要将检验数小于零的格直接变成

数字格，然后将最小的偶数格数字格子归零，即变成了空格，从而保持数字格的个数不变，实现了调整。

如果最小的偶数格数字格子有多个，则只需要变一个数字格为空格即可，其他要填 0，保持数字格个数不变

如果与上面的对偶变量法结合起来，

• 先由对偶变量法计算出位势，

注意，下面这个式子实际上是恒成立的

运筹学笔记第二章线性规划 Tsui Dik Sang

• 进而确定空格的检验数，

• 如果有小于零的检验数，则选择其中最小的那个空格，

• 进行闭回路调整

• 之后重新计算位势，直到所有检验数都大于等于零

2.4.2.4 无穷解

当检验数为零时会出现

2.4.2.5 退化解

当填入某个数字格时后同时满足产地和销地的供需平衡，这时候需要同时划掉一行和一列，然后为了保持数字格始终有 m +

n − 1 个，需要在划掉的行或者列中任意位置填入一个 0，这样就不会影响供需平衡，同时也不会影响检验数的计算。

2.4.3 产销不平衡问题

2.4.3.1 产大于销

则需要增加一个运费为零的虚拟销地 B

n+1

，需求量为

n+1

i=1

−

j=1

(2.94)

但是注意，这里的零运费不能按照最小元素来处理

在 vogel 法中似乎又可以处理这个零运费的问题

最终假想销地的意义其实是储存，不过总之就是要满足销售量后所用运费最小，剩下的储存。

2.4.3.2 销大于产

则需要增加一个运费为零的虚拟产地 A

m+1

，供应量为

m+1

j=1

−

i=1

(2.95)

同样地，这里的零运费不能按照最小元素来处理

基本一致，从略

2.4.3.3 运输路线不存在

使用一种类似于大 M 法，将不存在的路线的费用设置为一个很大的数 M 实现禁运，具体参见 ppt 上的四季度供货题

2.4.3.4

弹性供货问题

• 最低需求表征的是销地的最低需求量，是必须满足的

• 最高需求表征的是销地的最高需求量，是不能超过的，超过则无法接受

运筹学笔记第二章线性规划 Tsui Dik Sang

2.4.4 转运问题

产地和销地都可充当转运, 但是，对于从产地 A

, 其入与出差为 a

，同样的，对于销地 B

，其入与出差为 b

，因此可以将

转运问题列为一个维数更多的运输问题

其通式表达式需要用四段表示，

min z =

m+n

i=1

m+n

j=1

m+n

i=1

(2.96)

s.t.











m+n

j=1,j̸=i

= a

+ t

, i = 1, 2, . . . , m

m+n

j=1,j̸=i

= t

, i = m + 1, m + 2, . . . , m + n

m+n

i=1,i̸=j

= t

, j = 1, 2, . . . , m

m+n

i=1,i̸=j

= b

+ t

, j = m + 1, m + 2, . . . , m + n

, t

⩾ 0

(2.97)

其中一些需要注意的定义量

• t

: 第 i 个站点的转运量

• c

: 从站点 i 到站点 j 的单位运输费用

• c

: 站点 i 的单位转运费用

不过最后依然可以用表上作业法完成

之后还有更加复杂的包含中转站的问题，这里先从略，先做作业去！

不过表上作业法始终是很好用的，对于多转运的问题都可以用上，具体参见书本 p117

习题书 p110 一直到后面几页有一道非常细致的题目，是关于过去未来转运的，非常经典，现在看懂了，我感觉我变强大

了！

2.4.4.1 参数调整

这应该也是小题可能会考

来源于习题书 P99 题，使用的是位势法，进而列出不等式确定参数取值使得最优解不变

2.5 目标规划

这部分掌握建模方法比求解方法更重要！

目前来说理解无大碍，无非是引入了 d

, d

−

来表示偏差变量，然后将目标函数引入优先级概念，根据优先级依次决定可行

域。

注意一个点，虽然又优先级，但是对于绝对约束仍然是要强制满足的，相当于第 0 级优先级

也是请看 ppt 上的表

运筹学笔记第二章线性规划 Tsui Dik Sang

2.5.1 画图法

从略，但是基本只适用于二维

2.5.2 单纯形法

优先级系数同样也是系数，根据优先级来确定基出基，从最高优先级开始，在最高优先级符号已定的情况下才往下延申。

• 注意这里其实系数 σ

对于多个优先级是有多层的，因此在入基出基的时候都要进行线性变换一次，具体见 ppt 上面的例题

• 这里需要对检验数小于零的变量进行入基，与 LP 问题恰好相反，这其实是因为两者要优化的内容刚好相反而已，LP 问题

的标准形式是 max，而这里是 min

2.6 整数规划

学习这部分之前单纯形法是一定要吃透的！

这部分分支定界等知道思路即可，不是考试重点，因为属实过于繁琐了

虽然仍然是线性规划，但是复杂度有所增加。

分为两种，纯整数和混合，以及 0-1 规划

2.6.1 分支定界法

这个方法适用于混合整数规划

方法如下

• 首先看其松弛问题，找到最优解

• 如果最优解已经是整数解，则结束

• 否则，选择一个非整数变量 x

，其最优解为 x

∗

• 以 x

⩽ ⌊ x

∗

⌋ 和 x

⩾ ⌈ x

∗

⌉ 为约束条件构造两个子问题——仍然是松弛的不一定是整数的问题

• 解这些问题，如果解是非整数，那么其一定是比全局最优解更差的解，更新作为上界

• 如果解出的是整数解，则更新作为下界

• 继续对这些子问题——或者说是在上面分出来中最优的那一个问题，进行分支，直到上下界相等，结束

•

2.6.2 Gomory 割平面法

注意，这个只适用于纯整数规划！

关键是切一个平面，切掉的可行域包含最优解，但是不包含任何的整数解，首先找到一个基变量，写出诱导方程

j∈N

¯a

(2.98)

其地位相当于运输问题在线性规划中的地位

所以算是一个通式了

这个不再赘述，看前面普通线性规划问题

运筹学笔记第二章线性规划 Tsui Dik Sang

然后按照整数和分数进行分割

j∈N

([¯a

] + {¯a

})x

= [

] + {

} (2.99)

然后按照整数和分数分开，

j∈N

[¯a

− [

] = {

} −

j∈N

{¯a

⩽ 0 (2.100)

于是产生的就是一个割平面！将其放入表中继续使用单纯形法即可。更详细的请看 b 站网课

如果有多个的，其实只需要考虑

一个即可

{

} −

j∈N

{¯a

⩽ 0 (2.101)

加上松弛变量即可构成新加入的平面约束，

{

} −

j∈N

{¯a

+ x

n+1

= 0 (2.102)

放入单纯形表中继续计算即可

2.6.3 0-1 规划

有系数矩阵 C, 以及决策变量 X ，其只能取 0 或者 1。至于求解用到的是匈牙利数学家提到的两个定理，

2.6.3.1 指派问题：匈牙利方法

定义 2.6.1 (独立零元素). 在系数矩阵中处于不同行不同列的一组零元素

引理 2.6.1 (减去最小元素最优解性质). 设原分配问题的费用矩阵为 (c

)

m×n

。对每一行取其最小元素 r

，对每一列取其最

小元素 s

，令

˜c

= c

− r

− s

则对于任意可行分配（对应一个一一对应映射 π）有

˜c

i,π (i )

−

因此原问题与经上述行列约减得到的新问题有相同的最优分配，且最优值只相差常数

。

引理 2.6.2 (独立零元素与覆盖线数等价性). 系数矩阵 C 中独立零元素的最大个数等于能覆盖所有零元素的最少直线（行或

列）数。

于是就可以通过不断的变换系数矩阵来得到最优解

• 首先对矩阵应用 theorem 2.6.1，对于不含 0 的行和列，先减去行最小元素，处理结果为每行每列中都含有 0

• 对上面得到的初始矩阵查看是否存在 n 个独立零元素，如果有，那么直接结束，如果没有，去按照下面步骤进行

• – 对含零元素最少的行/列开始，用记号 O 将该零元素圈起，然后将被圈起的零元素所在列/行的其他未标记的零元素用

记号/划去。

由于这是不等式，如果放入化成标准式必然还会加入一个松弛变量 x

n+1

, 可以证明加入的这个也是整数变量

然后 ppt 上说根据经验，考虑式子右端最大真分数的式子

这部分在第二节课上才讲

运筹学笔记第二章线性规划 Tsui Dik Sang

– 重复上述过程，直到不能再圈出新的零元素为止。

– 如果每一行均有圈 0 出现，并且个数恰好为 n, 那么结束

– 做最小直线覆盖当前所有的零元素，

– ∗ 对于不含圈 0 的行打勾

∗ 在打勾的行中，对所有零元素所在的列打勾

∗ 在所有打勾的列中。对圈 0 所在的行打勾

∗ 重复上述过程，直到不能再打勾为止

∗ 对未打勾的每一行画一条横线，对打勾的每一列画一条竖线

∗ 找到未被直线覆盖的最小数字 k，

∗ · 对矩阵中无直线覆盖的行，每个元素 a

− k

· 对矩阵中有直线覆盖的列，每个元素 a

+ k

· 其他元素不变

– 重复上述过程，直到找到 n 个独立零元素为止

2.6.3.2 不均衡指派

这也才是课内会重点考察的！并且，有一道课后思考题！一定要做做

其实可以类比运输问题中的非平衡运输

例 2.6.1 (最小费用分派问题). 要解决这个最小费用分派问题，我们需要结合“每个工程队最多承接 2 栋楼、共 5 栋楼”的

条件，将问题转化为匈牙利法可解的方阵模型。

步骤 1：问题转化（构建虚拟方阵）

由于 3 个工程队（A

, A

）最多各接 2 栋楼（共 6 个“虚拟任务位”），但实际只有 5 栋楼，因此添加 1 个“虚拟项

目”（B

），虚拟项目的费用为 0（无实际成本）。

将每个工程队拆分为 2 个“虚拟工程队”（代表其 2 个任务位），构建 6 × 6 的费用矩阵（行：虚拟工程队；列：项目

− B

）：

虚拟工程队 B

（虚拟）

（A

的位 1） 3 8 7 15 11 0

（A

的位 2） 3 8 7 15 11 0

（A

的位 1） 7 9 10 14 12 0

（

的位

） 7 9 10 14 12 0

（A

的位 1） 6 9 13 12 17 0

（A

的位 2） 6 9 13 12 17 0

步骤 2：匈牙利法求解（行/列约减 + 零元素匹配）

匈牙利法的核心是通过行/列约减简化矩阵，再找到覆盖所有零元素的最少直线，最终匹配最小费用的组合。

（1）行约减：每行减去该行最小值

每行最小值均为 0（虚拟项目 B

的费用），因此矩阵不变。

（2）列约减：每列减去该列最小值

• 列 B

：min(3, 3, 7, 7, 6, 6) = 3 → 列 B

减 3

• 列 B

：min(8, 8, 9, 9, 9, 9) = 8 → 列 B

减 8

运筹学笔记第二章线性规划 Tsui Dik Sang

• 列 B

：min(7, 7, 10, 10, 13, 13) = 7 → 列 B

减 7

• 列 B

：min(15, 15, 14, 14, 12, 12) = 12 → 列 B

减 12

• 列 B

：min(11, 11, 12, 12, 17, 17) = 11 → 列 B

减 11

• 列 B

：min(0, 0, 0, 0, 0, 0) = 0 → 列 B

不变

约减后的矩阵：

虚拟工程队 B

0 0 0 3 0 0

4 1 3 2 1 0

3 1 6 0 6 0

（3）零元素匹配（最小费用组合）

我们需要选择 5 个实际项目（B

− B

）+1 个虚拟项目（B

），每个虚拟工程队对应 1 个项目，且每个项目仅被选 1 次。

通过匹配零元素（对应最小费用），最优组合为：

• A

的 2 个任务位：A

→ B

（费用 3）、A

→ B

（费用 7）

• A

的 2 个任务位：A

→ B

（费用 9）、A

→ B

（费用 12）

• A

的 1 个任务位：A

→ B

（费用 12），A

→ B

（虚拟项目，费用 0）

步骤 3：确定最终分派方案与总费用

• 分派方案：A

承担 B

、B

；A

承担 B

、B

；A

承担 B

。

• 总费用：3 + 7 + 9 + 12 + 12 = 43

2.6.3.3 一般 0-1 规划：隐式枚举法

简单来说就是先试一个根，其可行解得到的目标函数未 z

init

如果是求最小值的将

j=1

⩽ z

init

(2.103)

其作为约束条件放进去，接着枚举即可

第三章动态规划

3.1 动态规划的基本概念与思想

3.1.1 基本思想

其实这个已经在摸强化学习的边了，不过其实也可以说有点像是复杂网络，方法不难理解。

3.1.1.1 逆序法与顺序法的思路

目前刚学完还记得非常清楚，通俗的讲就是从最后一个点开始，往前先回一层，然后找到这一层的最优路径，接着考虑前一

层的连接成本等，结合这一层的最优路径进行计算，然后得到前一层的最优路径，如此递推到开始，这就是逆序法。

如果是顺序法的话反过来。

关于两种方法使用哪一种：

• 逆序法（Backward Induction）：从终点向起点推导。计算的是“从当前状态到终点的最优代价”（Cost-to-Go）。

• 顺序法（Forward Induction）：从起点向终点推导。计算的是“从起点到当前状态的最优代价”（Cost-to-Come）。

修正建议：如果起点较多（或者需要求出从任意点到固定的终点的路径），通常选择逆序法（一次计算即可得到所有点到

终点的最优解）。如果终点较多（或者需要求出从固定的起点到任意点的路径），通常选择顺序法。

3.1.2 基本概念与定义

为了给上面的方法套上一层严谨的外衣，我们需要定义以下概念：

定义 3.1.1 (阶段 (Stage)). 把一个复杂决策问题按时间或空间特征分解为若干个相互联系的阶段，以便按顺序求解。阶段变

量描述当前所处的阶段位置，一般用下标 k 表示 (k = 1, 2, . . . , n)。

定义 3.1.2 (状态 (State)). 表示每个阶段开始时所处的自然状况或客观条件。它描述了影响决策的因素随决策进程的变化情

况。

• 状态变量：s

，第 k 阶段的状态。

• 状态集合：S

，状态变量 s

取值的集合。

无后效性（Markov Property）：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。即“未来与过

去无关”，当前的状态是此前历史的一个总结。

运筹学笔记第三章动态规划 Tsui Dik Sang

定义 3.1.3 (决策 (Decision)). 当某阶段的状态确定以后，确定下一阶段状态的选择。

• 决策变量：x

)，第 k 阶段当状态为 s

时的决策。

• 允许决策集合：D

)，决策变量的取值范围。

定义 3.1.4 (策略 (Strategy)). 由各阶段的决策构成的序列。

• 全过程策略：P

1,n

= {x

, x

, . . . , x

}

• 子策略：P

k,n

= {x

, x

k+1

, . . . , x

}

定义 3.1.5 (状态转移方程 (State Transfer Equation)). 确定过程由一个状态转移到另一个状态的演变过程。

k+1

= T

, x

) (3.1)

定义 3.1.6 (指标函数与最优值函数). -

• 阶段指标函数：v

, x

)，第 k 阶段的收益或代价。

• 过程指标函数：V

k,n

，从第 k 阶段到终点的总指标。通常为和的形式：V

k,n

j=k

, x

)。

• 最优值函数：f

)，从第 k 阶段状态 s

到终点采取最优策略所得到的指标函数值。

定理 3.1.1 (动态规划基本方程 (Bellman Equation)). 对于逆序解法，基本方程为：











) = opt

∈D

)

, x

) + f

k+1

)}, k = n, n − 1, . . . , 1

n+1

) = 0 (边界条件)

(3.2)

其中 s

k+1

= T

, x

)。

3.2 具体解题

3.2.1 离散题

就是网络图题，前面已经练过讲得很清楚了，无论是顺序法还是逆序法变数较少，这里从略。

3.2.2 连续-非线性题

这时候我们就要重新审视这个问题了，接下来从一般的过程来抽象这个问题，具体的例子自己去看 ppt——或者我之后有时

间补充

3.2.2.1 建模

变量包络以下，应该都可以在题目中给出

运筹学笔记第三章动态规划 Tsui Dik Sang

• s

：第 k 阶段的状态变量

• x

：第 k 阶段的决策变量

• s

k+1

= T

, x

)：状态转移方程

• v

, x

)：阶段指标函数

• f

)：最优值函数

方程与离散的其实一致，如果是逆序法的话

定理 3.2.1 (动态规划基本方程).











) = opt

∈D

)

, x

) + f

k+1

)}, k = n, n − 1, . . . , 1

n+1

) = 0 (边界条件)

(3.3)

3.2.2.2 求解

接下来将会逐步的进行求解并求出相应的 x

∗

, 这部分，这有点考验数学功底，需要自己去看具体例题或者看 ppt 例题，这里

先不赘述

3.2.2.3 基于 Lagrange 方法

如果能用上面问题求解的问题一定也能列出 Lagrange 方程来求解

推论 3.2.2 (基于 Lagrange 方法的动态规划基本方程).

max Z =

k=1

, x

) (3.4)

s.t.











k+1

= T

, x

), k = 1 , 2, . . . , n − 1

given

∈ D

), k = 1 , 2, . . . , n

(3.5)

然后用 Lagrange 乘子法求解即可

在有些情况下最优值函数不是相加而是相乘！这也要注意

真的非常依赖题目，我觉得瞪眼做笔记不能解决问题！还是要做题了才有做笔记的资本，那么我可以宣布这个笔记也基本梳理完毕了

第四章笔记结束

基本就结束了这本笔记!

Tsui Dik Sang

2025.1.1

参考文献

[1]《运筹学》教材编写组. 运筹学 [M]. 第 5 版. 北京：清华大学出版社，2021.

No results found