当前位置:文档之家› 最优化理论与算法完整版课件 PPT

最优化理论与算法完整版课件 PPT


Bazaraa, J. J. Jarvis, John Wiley & Sons, Inc.,
1977.
组合最优化算法和复杂性
Combinatorial
Optimization 蔡茂诚、刘振宏
Algorithms and Complexity
清华大学出版社,1988 I运nc筹.,学19基82础/1手99册8
最优化首先是一种理念, 运筹学的“三个代表”
其次才是一种方法.
• 模型
• 理论
2021/4/9
• 算法
5
绪论---运筹学(Operations Research -
运筹学O方R)法
最优化/数学规划方法
连续优化:线性规划、 非线性规划、非光滑优 化、全局优化、变分法、 二次规划、分式规划等
离散优化:组合优化、 网络优化、整数规划等
2021/4/9
11
1. 食谱问题
我每天要求一定量的两种维生素,Vc和Vb。 假设这些维生素可以分别从牛奶和鸡蛋中得到。
维生素
Vc(mg) Vb(mg) 单价(US$)
奶中含量
2 3 3
蛋中含量
4 2 2.5
每日需求 40 50
需要确定每天喝奶和吃蛋的量, 目标以便以最低可能的花费购买这些食物, 而满足最低限度的维生素需求量。
最优化理论与算法
2021/4/9
1
提纲
使用教材:
最优化理论与算法 陈宝林
参考书 :
数学规划 黄红选, 韩继业 清华大学出版社
1. 线性规划 对偶定理
2. 非线性规划 K-K-T 定理
3. 组合最优化 算法设计技巧
2021/4/9
2
其他参考书目
Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley & Sons, Inc. 1979 (2nd Edit, 1993,3nd Edit,2006) Linear and Nonlinear Programming David G. Luenberger Addison-Wesley Publishing Company, 2nd Edition, 1984/2003.. Convex Analysis
min f (x) x:数
欧拉,1755
df(x) 0 dx
Min f(x1 x2 ··· xn )
f(x)=0
2021/4/9
8
拉格朗日,1797
Min f(x1 x2 ··· xn) s.t. gk (x1 x2 ··· xn )=0, k=1,2,…,
欧拉,拉格朗日:无穷维问题,变分学 柯西:最早应用最速下降法
j1
m
s.t xij bj
i1
xij 0
i 1, 2, , m
如果运输问题的总产量等于总销量,即有
m
n
ai bj
i 1
j 1
则称该运输问题为产销平衡问题;反之,称产销不平 衡问题。
2021/4/9
14
2 运输问题(续)
令xij表示由产地Ai运往销地Bj的物品数量,则产销平 衡问题的数学模型为:
nm
min z
cij xij
i1 j 1
n
xij ai
2021/4/9
9
电子计算机----------最优化
1930年代,康托诺维奇:线性规划 1940年代,Dantzig:单纯形方法,
冯 诺依曼:对策论 1950年代,Bellman:动态规划,最优性原理;
KKT条件; 1960年代:Zoutendijk,Rosen,Carroll,etc.非线性
规划算法,Duffin,Zener等几何规划,Gomory, 整数规划,Dantzig等随机规划 6-70年代:Cook等复杂性理论,组合优化迅速发展
2021/4/9
10
最优化应用举例
• 具有广泛的实用性 • 运输问题,车辆调度,员工安排,空运控制等 • 工程设计,结构设计等 • 资源分配,生产计划等 • 通信:光网络、无线网络,ad hoc 等. • 制造业:钢铁生产,车间调度等 • 医药生产,化工处理等 • 电子工程,集成电路VLSI etc. • 排版(TEX,Latex,etc.)
Printice-Hall
徐光辉、刘彦佩、程侃
科学出版社,1999
2021/4/9
4
1,绪论----学科概述
• 最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学.
• 达到最佳目标的方案是最优方案,寻找最优 方案的方法----最优化方法(算法)
• 这种方法的数学理论即为最优化理论. • 是运筹学的方法论之一.是其重要组成部分.
几何规划 动态规划 不确定规划:随机规 划、模糊规划等
多目标规划 20对21/策4/论9 等
随机过程方法
统计决策理论 马氏过程 排队论 更新理论 仿真方法 可靠性理论等
统计学方法
回归分析 群分析 模式识别 实验设计 因子分析等
6
优化树
2021/4/9
7
•最优化的发展历程
费马:1638;牛顿,1670
2021/4/9
13
2 运输问题
设某种物资有m个产地A1,A2,…Am,各产地的产量是 a1,a2,…,am;有 n个销地B1,B2,…,Bn.各销地的销量 是b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)到销地
Bj(j=1,2,…,n)运输单位物品的运价是cij问怎样调 运这些物品才能使总运费最小?
2021/4/9
12
1. 食谱问题(续)
令x表示要买的奶的量,y为要买的蛋的量。食谱问题可以写
成如下的数学形式:
Min 3x +2.5y
极小化目标函数
s.t. 40
50
2x + 4y 3x + 2y
可行区域(单纯形) 可行解
运筹学工作x,者y参与0建.立关于何时出现最小费用 (或者最大利润)的排序,或者计划,早期被标示为programs。 求最优安排或计划的问题,称作programming问题。
R. T. Rockafellar
Princeton Physics, 1996.
Optimization and Nonsmooth Analysis
Frank H. Clarke
SIAM, 1990.
2021/4/9
3
其他参考书目
Linear Programming and Network Flows M. S.
相关主题