北邮最优化课件0最优化理论与算法引言

《北邮最优化课件0最优化理论与算法引言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、TPSHUAI1最优化理论与算法帅天平北京邮电大学数学系2021/7/14TPSHUAI2提纲1.线性规划对偶定理2.非线性规划K-K-T定理3.组合最优化算法设计技巧使用教材：最优化理论与算法陈宝林参考书：数学规划黄红选，韩继业清华大学出版社2021/7/14TPSHUAI3其他参考书目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramm

2、ingDavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysisR.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysisFrankH.ClarkeSIAM,1990.2021/7/14TPSHUAI4LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&S

3、ons,Inc.,1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性CombinatorialOptimization蔡茂诚、刘振宏AlgorithmsandComplexity清华大学出版社，1988Printice-HallInc.,1982/1998其他参考书目2021/7/14TPSHUAI51,绪论----学科概述最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标的科学.达到最佳目标的方案是最优方案,寻找最优方案的方法----最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部

4、分.运筹学的“三个代表”模型理论算法最优化首先是一种理念,其次才是一种方法.2021/7/14TPSHUAI6绪论---运筹学（OperationsResearch-OR）运筹学方法随机过程方法统计学方法最优化/数学规划方法连续优化：线性规划、非线性规划、非光滑优化、全局优化、变分法、二次规划、分式规划等离散优化：组合优化、网络优化、整数规划等几何规划动态规划不确定规划：随机规划、模糊规划等多目标规划对策论等统计决策理论马氏过程排队论更新理论仿真方法可靠性理论等回归分析群分析模式识别实验设计因子分析等2021/7/14TPSHUAI7优化树2021/7/14TPSHUA

5、I8最优化的发展历程费马:1638;牛顿,1670欧拉,1755Minf(x1x2···xn)f(x)=02021/7/14TPSHUAI9欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m2021/7/14TPSHUAI101930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性

6、规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划6-70年代：Cook等复杂性理论，组合优化迅速发展电子计算机----------最优化2021/7/14TPSHUAI11最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，adhoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSIetc.排版（TEX,Latex,etc.）2021/7/14TPSHUAI121.食谱问题我每天要求一定量的两种维生素，Vc和Vb。

7、假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。2021/7/14TPSHUAI131.食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.