运筹学通论
胡晓东
应用数学研究所 中国科学院数学与系统科学研究院 北京2734信箱,北京100190 Email: xdhu@amss.ac.cn, Tel: 62639192, Rm: 904
Institute of Applied Mathematics
提纲
20世纪数学的五大指导理论 Five Golden Rules 叶其孝,刘宝光 Great Theories of 20th Century Math 上海教育出版社,2000 -and Why They Matter 1. 线性规划 对偶定理 2. 博弈论 极大极小定理 3. 非线性规划 K-K-T 定理 4. 计算/算法理论 停机定理,库克定理 拓扑学 不动点定理 奇点理论 莫尔斯定理 5. 组合最优化 算法设计技巧
运筹学 模型 理论 算法
参考书目
Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley & Sons, Inc. 1979 (2nd Edition, 1993) Linear and Nonlinear Programming David G. Luenberger Addison-Wesley Publishing Company, 2nd Edition, 1984/2003.. Convex Analysis ** R. T. Rockafellar Princeton Landmarks in Mathematics and Physics, 1996. Optimization and Nonsmooth Analysis ** Frank H. Clarke SIAM, 1990. xdhu
3
3. 微分复习-单变量函数
考虑(单变量)函数 y = f(x).当自变量 x 在点 x 有一改变量x 时,函数 y 相应地有一改变量 y = f(x+x)-f(x),那么当 x 趋于零时,若比值 y /x 的极限存在,则称这个极限为函数 f(x) 在点 x 的导数,记 y dy f(x+x)-f(x) y'=f'(x) = dx = lim = lim x x→0 x x→0 从几何直观的角度看,函数 f(x) 的导数 f'(x) 是函数 y = f(x) 表示的曲线在点 x 的切线的斜 率,即 f'(x) = tgα,这里α 是曲 线在点 x 处的切线与X-轴的夹 角.
xdhu
Y f(x)
f(x+x)
y x
α
O
x
x+x X
4
3. 微分复习-多变量函数
考虑多变量函数 z = f(x, y).当变量x 在点x 有一改变量x, 而变量 y 保持不变时,函数z 相应地有一改变量z = f(x+x, y)f(x, y),那么当 x 趋于零时,若比值 z /x 的极限存在,则称 这个极限为函数 f(x, y) 在点(x, y) 关于变量 x 的偏导数,记
f(x, y) z z = lim f(x+x, y)-f(x, y) = = lim f '(x, y) = x x x x→0 x x→0 x
类似地,记多变量函数 f(x, y) 在点(x, y)关于变量 y 的偏导数为
f(x, y) z z = lim f(x, y+y)-f(x, y) fy'(x, y) = = = lim y y y→0 y y→0 y
多变量函数的偏导数可以按照单变量函数的微分法则求出, 只需要对所讨论变量求导数,其余的变量都看作常数即可.
xdhu 5
3. 微分复习-多变量函数(续一)
Z f(x, y)
β
O
α
(x, y) Y
X
在几何上,二元函数 f(x, y) 表示一个曲 线,通过曲面上一点(x, y, z)作一平行于OXZ 平面的平面,与曲面有一条交线, z/ x 就 是这条曲线在该点的切线与X-轴正向夹角α 的正切,即 z/ x =tgα.
xdhu 6
3. 微分复习-多变量函数(续二)
多元函数 y = f(x) 在 x*∈int(S) 处是可微的,如果存在梯度 f(x*) 和一个函数α(x) 满足:对任意x∈S f (x) = f(x*) + f(x*)T(x-x*) + ||x-x*||α(x*; x*-x), 这里limx→x* α(x*; x*-x)=0.事实上f(x) 的每一个分量就是 相应的偏导数,即f(x)=(f /x1, f /x2, … , f /xn) 多元函数 y =f(x) 在 x*∈int(S) 处是二阶可微的,如果存在梯 度f(x*)及一个海森矩阵H(x*),和一个函数α(x)满足: x∈S f(x) = f(x*)+

下一页