运筹学0最优化理论与算法引言.pdf

最优化理论与算法TPSHUAI1提纲使用教材:最优化理论与算法陈宝林参考书:数学规划黄红选,-K--,&Sons,(2ndEdit,1993,3ndEdit,2006)-pany,2ndEdition,1984/2003..,,,,JohnWiley&Sons,Inc.,、plexity清华大学出版社,1988Printice-HallInc.,1982/1998运筹学基础手册徐光辉、刘彦佩、程侃科学出版社,1999TPSHUAI41,绪论----学科概述•最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标的科学.•达到最佳目标的方案是最优方案,寻找最优方案的方法----最优化方法(算法)•这种方法的数学理论即为最优化理论.•,运筹学的“三个代表”其次才是一种方法.•模型•理论TPSHUAI•算法5绪论---运筹学(OperationsResearch-OR)运筹学方法最优化/数学规划方法随机过程方法统计学方法连续优化:线性规划、统计决策理论回归分析非线性规划、非光滑优化、全局优化、变分法、马氏过程群分析二次规划、分式规划等排队论模式识别离散优化:组合优化、更新理论实验设计网络优化、整数规划等仿真方法因子分析等几何规划可靠性理论等动态规划不确定规划:随机规划、模糊规划等多目标规划对策论等TPSHUAI6优化树TPSHUAI7•最优化的发展历程费马:1638;牛顿,1670minf(x)x:数df(x)0dx欧拉,1755Minf(x1x2···xn)f(x)=0TPSHUAI8拉格朗日,1797Minf(x1x2···xn)(x1x2···xn)=0,k=1,2,…,m欧拉,拉格朗日:无穷维问题,变分学柯西:最早应用最速下降法TPSHUAI9电子计算机----------最优化1930年代,康托诺维奇:线性规划1940年代,Dantzig:单纯形方法,冯诺依曼:对策论1950年代,Bellman:动态规划,最优性原理;KKT条件;1960年代:Zoutendijk,Rosen,Carroll,,Duffin,Zener等几何规划,Gomory,整数规划,Dantzig等随机规划6-70年代:Cook等复杂性理论,组合优化迅速发展TPSHUAI10