http://www.ma-xy.com
目录
第一章 线性规划 1
1.1 问题的引入与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 模型规范化及基本理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 线性规划的最优化条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 对偶理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 最优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5.1
内点算法
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5.2 路径跟踪法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 MATLAB 应用实例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1
http://www.ma-xy.com
第一章 线性规划
1.1 问题的引入与分析
前面，我们讨论的都是非线性规划，无约束非线性规划和约束非线性规划，下面，我们讨论
两种特殊情况：1. 线性规划 2. 二次规划。线性规划要求目标函数和约束条件皆为线性函数。二
次规划则要求目标函数为二次函数。我们先来讨论线性规划。
示例：设某工厂用 4 种资源生产 3 种产品，单位 j 产品需要 i 资源的数量为 a
ij
，可获利 c
j
。
并要求第 i 种资源总消耗不超过 b
i
，第 j 种产品产量不超过 d
j
，问如何安排生产使总利润最大？
解：设 3 种产品的产量分别为 x
1
, x
2
, x
3
，则
max
3
j=1
c
j
x
j
s.t.
3
j=1
a
ij
x
j
⩽ b
i
i = 1, 2, 3, 4
x
j
⩽ d
j
x
j
⩾ 0
j = 1, 2, 3
线性规划的目标函数 f 是线性的，约束函数是线性的，约束有等式和不等式两种。Optimiza-
tion Toolbox 采用下列 3 种方法求解线性规划：
¬单纯形算法，也是最常用的算法；
内点算法：基于原始预估校正算法，尤其适用于稀疏结构或其它特殊结构的大规模问题；
®动态序列算法。
1.2 模型规范化及基本理论
线性规划的一般形式为
min
x∈R
n
f(x) = c
T
x
s.t.
Ax ⩽ b
x ⩾ 0
1
http://www.ma-xy.com
1.2 模型规范化及基本理论 第一章 线性规划
其中：x = (x
1
, x
2
, . . . , x
n
)
T
∈ R
n
，f = c
T
x : R
n
→ R 为线性函数。A ∈ R
m×n
，b ∈ R
m
，c ∈ R
n
。
设解的可行域为 D = {x|Ax ⩽ b & x ⩾ 0}，最优解记为 x
∗
，上面的线性规划问题也可以写
成分量形式
min
n
j=1
c
j
x
j
s.t.
n
j=1
a
ij
x
j
⩽ b
i
i = 1, 2, . . . , m
x
j
⩾ 0 j = 1, 2, . . . , n
设 E = {1, 2, . . . , m} 为指标集，J = {1, 2, . . . , n}。
我们可以将上面的线性规划 (LP) 一般形式化为标准形，标准形的定义如下
min c
T
x
s.t.
Ax = b
x ⩾ 0
其中：A ∈ R
m×n
, b ∈ R
m
，c, x ∈ R
n
。记可行域为 S
S = {x|x ∈ R
n
|Ax = b, x ⩾ 0}
下面，我们将线性规划一般形式转化为标准形式：
1) 不等式转化为等式：
对于
n
j=1
a
ij
x
j
⩽ b
i
，增加一个松弛变量
b
i
−
n
j=1
a
ij
x
j
+ r
i
⩾ 0
对于
n
j=1
a
ij
x
j
⩾ b
i
，增加一个剩余变量
n
j=1
a
ij
x
j
− b
i
+ s
i
⩾ 0
2) 受限与非受限变量转化为非负变量：
对于 x
j
⩾ l
j
，进行平移变换：¯x
j
= x
j
− l
j
⩾ 0；
对于 x
j
⩽ u
j
，进行反射变换与平移变换：x
j
= u
j
− ¯x
j
⩾ 0；
对于自变量 x
j
∈ R，将它分解成非负变量之差：x
j
= ¯x
j
− ˆx
j
，其中，¯x
j
⩾ 0, ˆx
j
⩾ 0。
3) 极大化转化为极小化目标。
由可行域 S 的定义可知，S 是一个凸集，事实上，S 是一个多面体区域。设可行域 S 的极
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 线性规划 1.2 模型规范化及基本理论
点为 x
i
(i ∈ E)，极方向为 d
j
(j ∈ J)，那么对于任意的点 x ∈ S，有
x =
i∈E
λ
i
x
i
+
j∈J
µ
j
d
j
i∈E
λ
i
= 1
λ
i
⩾ 0
µ
j
⩾ 0
把 x 代入原问题，得到以 λ
i
, µ
j
为变量的等价的线性规划
min
i∈E
(c
T
x
i
)λ
i
+
j∈J
(c
T
d
j
)µ
j
s.t.
i∈E
λ
i
= 1
λ
i
⩾ 0
µ
j
⩾ 0
i ∈ E
j ∈ J
由于 µ
j
⩾ 0 可以任意大。因此，若对于某个 j 有 c
T
d
j
< 0，则 (c
T
d
j
)µ
j
随着 µ
j
的增大而无限
减小，从而目标函数值趋向 −∞，称该问题无界或不存在有限最优值。如果对于所有的 j ∈ J，
有 c
T
d
j
⩾ 0，则相对于最小化目标来说，令 µ
j
= 0(j ∈ J)，于是，线性规划的标准形式转化为
min
i∈E
(c
T
x
i
)λ
i
(1.1)
s.t.
i∈E
λ
i
= 1
λ
i
⩾ 0
i ∈ E
在上述问题中，令
c
T
x
p
= min
i
c
T
x
i
显然，当 λ
p
= 1 并且 λ
i
= 0(i = p) 时，目标函数值最小，所以 (1.1) 式必然有最优解。
线性规划的基本定理 假设线性规划标准形式的可行域 S = ϕ，则有
(1) 标准形存在有限最优解，当且仅当，对于 S 的任意极方向 d
j
(j ∈ J)，有
e
T
d
j
⩾ 0
(2) 若标准形存在有限最优解，则其最优值可以在 S 的某个极点上取到。
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.3 线性规划的最优化条件 第一章 线性规划
1.3 线性规划的最优化条件
最优化条件 - KKT 条件。对于一般形式的线性规划而言，x
∗
∈ R
n
是其最优解，当且仅当
存在向量 w ∈ R
m
, r ∈ R
n
使得
Ax
∗
⩾ b, x
∗
⩾ 0
c − A
T
w − r = 0, w ⩾ 0, r ⩾ 0 (1.2)
和
w
T
(Ax
∗
− b) = 0, r
T
x
∗
= 0 (1.3)
对于标准形式的线性规划而言，x
∗
∈ R
n
是其最优解，当且仅当存在向量 w ∈ R
m
, r ∈ R
n
，
使得
Ax
∗
= b x
∗
⩾ 0
A
T
w + r = c r ⩾ 0
r
T
x
∗
= 0
最优性条件将求解线性规划的问题转化为求解代数方程组 (不等式组) 的问题，后者有 n + m + 1
个变量和 n + m + 1 个方程。
1.4 对偶理论
在线性规划的 KKT 条件中，条件方程 (1.2)(1.3) 分别等价于下面的不等式组和方程组
A
T
w ⩽ c w ⩾ 0
b
T
w − (w
T
A)x
∗
= 0 c
T
x
∗
− w
T
(Ax
∗
) = 0
于是，我们可以写出如下形式的对偶规划
max b
T
w
s.t.
A
T
w ⩽ c
w ⩾ 0
我们称上述规划为原线性规划的对偶形式 (DLP)。
弱对偶定理 (1) 设原线性规划的可行域为 S，对偶规划的可行域为 T ，若 S = ϕ, T = ϕ，则
∀x ∈ S, w ∈ T ，有 c
T
x ⩾ b
T
w。(2) 若 ∃x
∗
∈ S, w
∗
∈ T ，使得 c
T
x
∗
= b
T
w
∗
，则 x
∗
, w
∗
分别为
PLP 和 DLP 的最优解。(3) 若 PLP 无下界，则其对偶 DLP 是不相容的 (即 T = ϕ)，反之，若
DLP 无上界，则 PLP 是不相容的 (即 S = ϕ)。
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 线性规划 1.5 最优化算法
强对偶定理 (1) 若 PLP 和 DLP 中任何一个问题存在有限的最优解，则另一个问题也存在有限
的最优解，并且它们的目标函数最优值相等。(2) 对于 PLP 或 DLP 问题，若目标函数值无界，
则另一个问题是不相容的 (无可行解)。
1.5 最优化算法
1.5.1 内点算法
考虑标准形式的线性规划问题
min b
T
y (1.4)
s.t.
A
T
y = c
y ⩾ 0
其中：A ∈ R
m×n
, b, y ∈ R
m
, c ∈ R
n
。上述问题的对偶问题为
max c
T
x (1.5)
s.t. Ax ⩽ b
其中：c, x ∈ R
n
, A ∈ R
m×n
, m ⩾ n。
先假设存在内点 x
0
，并假设问题是有界的。内点法的基本思想是：从内点 x
0
出发，沿可行
方向求出使目标函数值上升的后继点，再从得到的内点出发，沿另一个可行方向求使目标函数值
上升的内点，重复以上步骤，产生一个内点组成的序列 {x
k
}，使得
c
T
x
k+1
> c
T
x
k
= 0
当满足终止准则时，则停止迭代。这种方法的关键是选择使得目标函数值上升的可行方向。
首先，引进松弛变量
v
，将模型
(
1.5) 写为标准型
max c
T
x
s.t.
Ax + v = b
v ⩾ 0
在第 k 次迭代，定义 v
k
为非负松弛变量构成的 m 维向量，使得
v
k
= b − Ax
k
再定义对角矩阵
D
k
= diag
1
v
k
1
, · · · ,
1
v
k
m
作仿射变换，令
w = D
k
v
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.5 最优化算法 第一章 线性规划
把线性规划 (1.5) 改写为
max c
T
x
s.t.
Ax + D
−1
k
w = b
w ⩾ 0
在变换空间中，选择搜索方向
d =
d
x
d
w
显然，d 作为可行方向，它必是下列齐次方程的一个解
D
k
Ad
x
+ d
w
= 0 (1.6)
对于上式的任一解，有
A
T
D
k
(D
k
Ad
x
+ d
w
) = 0
由此得到
d
x
= −(A
T
D
2
k
A)
−1
A
T
D
k
d
w
每次迭代中，目标函数在 d
x
方向的方向导数是
c
T
d
x
将 d
x
代入上式，则有
c
T
d
x
= c
T
[−(A
T
D
2
k
A)
−1
A
T
D
k
d
w
] = −[D
k
A(A
T
D
2
k
A)
−1
c]
T
d
w
选择 d
w
，使 c
T
d
x
最大，则
d
w
= −D
k
A(A
T
D
2
k
A)
−1
c
由上式确定 d
w
后，可以得到式 (1.6) 中的一个解，其中
d
x
= (A
T
D
2
k
A)
−1
c
同时，对 d
w
作逆仿射变换，可得到
d
v
= D
−1
k
d
w
= −A(A
T
D
2
k
A)
−1
c = −Ad
x
搜索方向确定后，还需确定沿此方向移动的步长。设后继点
x
k+1
= x
k
+ αd
x
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 线性规划 1.5 最优化算法
步长 α 在保证 x
k+1
为可行域的内点情况下取值，即满足
A(x
k
+ αd
x
) < b
αAd
x
< b − Ax
k
− αd
v
< v
k
令
β = min
v
(k)
i
−(d
v
)
i
(d
v
)
i
< 0, i ∈ {1, 2, . . . , m}
取 α = γβ，其中 γ ∈ (0, 1)，这样即可得到 x
k+1
。下面给出内点法的计算步骤：
step1. 初始化。x
0
∈ R
n
，γ ∈ (0, 1)，容许误差 ε > 0，置 k := 0
step2. 计算 v
k
v
k
= b − Ax
k
step3. 置对角矩阵
D
k
= diag
1
v
k
1
, · · · ,
1
v
k
m
step4. 计算 d
x
= (A
T
D
2
k
A)
−1
c
step5. 令 d
v
= −Ad
x
step6. 令
α = γ min
v
(k)
i
−(d
v
)
i
(d
v
)
i
< 0, i ∈ {1, 2, . . . , m}
step7. 置 x
k+1
= x
k
+ αd
x
step8. 若
|
c
T
x
k+1
−
c
T
x
k
|
c
T
x
k
< ε 则停止，输出 x
k+1
；否则，置 k := k + 1，返回 step2。
前面，我们假设存在内点 x
0
。这里，我们可以如此求初始内点：首先，从原点出发，沿目标
函数的梯度方向 c 取一点，令
x
0
=
∥b∥
∥A
c
∥
c
如果 v
0
= b − Ax
0
> 0，则 x
0
为初始内点，否则，解下列一阶线性规划问题
max c
T
x − Mx
a
s.t. Ax − x
a
e ⩽ b
其中：M 是大的正数，e 为 1 × m 的单位列向量，x
a
为人工变量，根据 v 的定义，如果令
x
(0)
a
>
min
v
(0)
i
i = 1, 2, . . . , m
则有
Ax
0
− x
(0)
a
e < b
因此，(x
0
, x
0
a
) 必为内点。
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.5 最优化算法 第一章 线性规划
1.5.2 路径跟踪法
考虑线性规划原问题 (PLP)
min c
T
x
s.t.
Ax = b
x ⩾ 0
其对偶形式 (DLP) 为
max b
T
y
s.t.
A
T
y + w = c
w ⩾ 0
其中：c, x ∈ R
n
，b, y ∈ R
m
，A ∈ R
m×n
，Rank(A) = m。记可行域分别为 S, T
S = {x|Ax = b, x ⩾ 0}
T =

y
w
A
T
y + w = c, w ⩾ 0
可行域内部记为 S
T
, T
T
S
T
= {x|Ax = b, x > 0}
T
T
=

y
w
A
T
y + w = c, w > 0
x, y, w 为最优解的充分必要条件是
Ax = b x ⩾ 0
A
T
y + w = c w ⩾ 0
XW e = 0
其中：X = diag(x
1
, x
2
, . . . , x
n
)，W = diag(w
1
, w
2
, . . . , w
n
)，上述条件为 KKT 条件。
现在，将 XW e = 0 换作 XW e = µe，e 为 n × 1 的全 1 列向量，实参数 µ > 0，得到松弛
KKT 条件
Ax = b x ⩾ 0
A
T
y + w = c w ⩾ 0
XW e = µe
如果 S 有界且 S
T
= ϕ，则对每一个 µ，松弛 KKT 条件存在唯一内点解。
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 线性规划 1.5 最优化算法
定义 (原始 - 对偶中心路径) 原始 - 对偶可行解 D = {(x, y, w)|Ax = b, A
T
y+w = c, (w, x) ⩾
0} 和可行集内部 D
+
，若 D
+
= ϕ，则对每一个 µ > 0，上述系统存在唯一解 (x(µ), y(µ), w(µ))，
把 {x(µ), y(µ), w(µ)|µ > 0} 称为原始 - 对偶中心路径，记为 C
µ
。
在中心路径 C
µ
上，当 µ 很小时，原问题的目标值单调减小且趋于最优值。对偶问题目标值
单调增加且趋于最优值。对于每一个中心路径参数 µ，对偶间隙 c
T
x(µ) − b
T
y(µ) = nµ。
关于参数 µ 的确定：如果点 (x, y, w) 在中心路径 C
µ
上，显然有
µ
=
x
T
w
n
如果点 (x, y, w) 不在中心路径 C
µ
上，我们仍用上述方法确定。下面介绍如何确定转移方向 d
k
。
当 µ → 0 时，原始问题和对偶问题均趋于最优值。我们通过迭代，大致沿着 C
µ
去逼近最优
解。任取一点 (x, y, w)，其中，x > 0, w > 0。此时，目标是求一个方向 (∇x, ∇y, ∇w) 使迭代点
(x + ∇x, y + ∇y, w + ∇w) 位于 C
µ
上，即
A(x + ∆x) = b
A
T
(y + ∆y) + (w + ∆w) = c
(X + ∆x)(W + ∆w)e = µe
整理后，有
A∆x = b − Ax
A
T
∆y + ∆w = c − A
T
y − A
T
w
W ∆x + X∆w + ∆x∆we = µe − XW e
记作 b − Ax = ρ，c − A
T
y − w = σ，忽略二次项 ∆x∆w，用矩阵形式表示，则有
A 0 0
0 A
T
I
W 0 X
∆x
∆y
∆w
=
ρ
σ
µe − XW e
解上述方程，可求出移动方向 [∆x, ∆y, ∆w]
T
。在求出转移方向之后，需要确定此方向移动
的步长 α，α 取值应满足
x + α∆x > 0 (1.7)
w + α∆w > 0
由于 x
j
> 0, w
j
> 0, α > 0，因此
1
α
= max
i,j
−
∆x
j
x
j
, −
∆w
i
w
i
为保证 (1.7) 式为严格不等式，引进小于且接近 T 的正数 ρ，令
α = min
ρ
max
i,j
−
∆x
j
x
j
, −
∆w
i
w
i

−1
, 1
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.6 MATLAB 应用实例 第一章 线性规划
算法流程：
step1. 初始化。初始点 (x, y, w)，x
1
> 0, w
1
> 0，ρ → 1，容许误差 ε > 0，正数 M < ∞，置
k := 1，δ =
1
10
step2. 计算 ρ = b − Ax
k
, σ = c − A
T
y
k
− w
k
, r = x
T
k
w
k
, µ = δ
γ
n
。
step3. 若 ∥ρ∥
1
< ε & ∥σ∥
1
< ε & r < ε 则停止迭代，输出解；若 ∥x
k
∥ > M 或者 ∥y
k
∥ > M 则
停止迭代，原问题或对偶问题无界，否则，转到 step4。
step4. 解方程
A 0 0
0 A
T
I
W 0 X
∆x
∆y
∆w
=
ρ
σ
µe − XW e
得到 (∆x
k
, ∆y
k
, ∆w
k
)，置 α。
step5. 计算 x
k+1
x
k+1
= x
k
+ α∆x
k
y
k+1
= y
k
+ α∆y
k
w
k+1
= w
k
+ α∆w
k
置 k := k + 1，转到 step2。
1.6 MATLAB 应用实例
MATLAB 中用 linprog 求解线性规划，其调用格式为
[x,fval,exitag,output]=linprog(fun,A,b,Aeq,beq,lb,ub,x0,options)
其中：fun 为目标函数；x0 为初始点；A,b 为 Ax ⩽ b；Aeq,beq 为线性等式约束 Aeqx < beq；
lb,ub 为 lb ⩽ x ⩽ ub；nonlcon 为非线性约束条件；options 为结构体参数。
用 linprog 求解如下线性规划问题
min f = −4x
1
− x
2
s.t.
− x
1
+ 2x
2
⩽ 4
2x
1
+ 3x
2
⩽ 12
x
1
− x
2
⩽ 3
x
1
x
2
⩾ 0
1 f =[−4;−1];
2 x0 = [0 ,0 ] ;
3 A=[ −1 ,2;2 ,3;1 , −1];
4 b= [ 4 ; 1 2 ; 3] ;
5 Aeq= [ ] ;
6 beq = [ ];
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 线性规划 1.6 MATLAB 应用实例
7 lb = [ ] ;
8 ub = [ ] ;
9 [ x , fv al , e x i tf l a g , output , lambda]= l in pr og ( f ,A, b , Aeq, beq , lb , ub , x0 )
10
http://www.ma-xy.com 11 http://www.ma-xy.com