最优化方法
Dimitris Bertsimas 教授
1 课程结构 幻灯片 1
线性优化（LO）：1-9 课
网络流程图：10-11 课
离散优化：12-15 课
动态优化：16 课
非线性优化（NLO）：17-25 课
2 要求 幻灯片 2
作业：30%
期中考试：30%
期末考试：40%
使用 Matlab 解决最优化问题
3 课程概述 幻灯片 3
最优化的发展历程
LOPs
方法出现在哪些地方？
列举代表公式
4 最优化的发展历程 幻灯片 4
费马，1638；牛顿，1670
数
)( min xf
:x
0
)(
=
dx
xdf
欧拉，1755
),...,( min
1 n
xxf
0)(
=
∇
xf
拉格朗日，1797
),...,( min
1 n
xxf
..ts 0),...,(
1
=
nk
xxg
mk ,...,1
=
欧拉，拉格朗日：无穷维问题，变分学
5 非线性最优化
5.1 常见形式 幻灯片 5
),...,( min
1 n
xxf
..ts 0),...,(
11
≤
n
xxg
.
.
.
0),...,(
1
≤
nm
xxg
6． 什么是线性优化？
6.1 表达形式 幻灯片 6
minimize
21
3 xx
+
subject
to
22
21
≥
+
xx
32
21
≥+xx
0,0
21
≥≥ xx
(
)
(
)
(
)
[
]
1 2
2 1
,
3
2
,
,
1
3
2
1
==== Ab
x
x
xc
7． 线性优化的发展
7.1 前算法时期 幻灯片 7
傅立叶，1826 解线性不等式组的方法
Poussin Vallee la de
求解带绝对值的目标函数的单纯形法
康托洛维奇，库普曼斯，20 世纪 30 年代 公式和解方法
冯.诺意曼，1928 对策论，对偶性
Farkas，闵可夫斯基，卡拉泰奥多里，1870-1930 基础
7.2 模型时期
丹捷格，1947 单纯形法
20 世纪 50 年代 应用
20 世纪 60 年代 大规模最优化
20 世纪 70 年代 复杂性理论
Khachyan，1979 椭球算法
Karmakar，1984 内点算法
8．
LOPs
方法出现在哪些地方？
8.1 广泛的适用性 幻灯片 9
z 运输
空运控制，员工安排
重载卡车的运转
z 通讯
z 通讯
z 制造业
z 医药
z 工程
z 排版（TEX，LATEX）
9．运输问题
9.1 数据 幻灯片 10
z m 个工厂，n 个仓库
z
表示第 个工厂的供应，
i
s
i m1,...,i
=
z
j
d
表示第 个仓库的需求，j
n1,...,j
=
z
表示从 地到 地的运输费用
,ij
c
i
j
9.2 决策变量
9.2.1 表述形式 幻灯片 11
,ij
x
=从 地运到 地的单位数量
i
j
mi
n
∑
=
∑
=
m
i
n
j
xc
ijij
11
..ts
jij
d
m
i
x =
∑
= 1
nj ,...,1
=
∑
mi
=
=
n
j
sx
iij
1
,...,1
=
10
≤
≤
i
x
ni ,...,1
=
10． 通过线性优化进行分类 幻灯片 12
z 给出
n
z 序列统计
(1) (2)
,,cc
(1) (2) ( )n
cc c
个数字
12
,,,
n
cc cL ；
( )
,
n
cL
：
≤
≤≤L
；
z 通过线性优化得到
()
1
i
i
c
=
∑
。
10 ≤≤
i
i
n
i
ii
x
kxts
xc
11． 幻灯片 13
i ，
ni ,...,1
k
..
min
1
1
=
∑
∑
=
=
i
税下投资
z 以价格
i
q 购买了
i
份股票s
=
z 股票
i
的现价是
i
p
z 你预期一年后股票
i
的价格为 r
i
z 在出售股票时需要支付的税金=资本收益
×
30%
z 易费用
z 例如：将原先以每股 30$的价格买入的 1000 股股票，以每股 50$的价格出售，则净
现金为：
z 扣除税金后，你的现金仍然比购买股票前增多
支付 1%的交
