高级运筹学非线性规划优秀课件.ppt

《高级运筹学非线性规划优秀课件.ppt》由会员分享，可在线阅读，更多相关《高级运筹学非线性规划优秀课件.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、高级运筹学非线性规划第1页，本讲稿共49页 第2页，本讲稿共49页 第3页，本讲稿共49页 Prisoners Dilemma 第4页，本讲稿共49页 运筹学F运筹学的研究对象可大致归纳为三类机器、设备、网络、乃至系统的运用问题，即如何提高运作效率；拥挤现象：交通路口的车辆排队、服务热线、飞机着陆、船舶进港、网络；竞争现象：人与自然的对策、人与人的对抗；第5页，本讲稿共49页 运筹学的分支F数学规划线性规划 非线性规划整数规划 动态规划F图与网络流 F网络计划F库存论F排队论F对策论F决策论第6页，本讲稿共49页 决策问题的分类F确定性、静态优化问题数学规划（单目标、多目标）图与网络流决策论（

2、多目标）F确定性、动态优化问题动态规划（离散）最优控制（离散、连续）F随机性优化问题存储论排队论决策论（单目标）F多人竞争性决策问题博弈论（对策论）第7页，本讲稿共49页 本课程的主要内容F非线性规划（一维无约束极值问题）F决策论F博弈论F排队论F库存论第8页，本讲稿共49页 非线性规划问题F一般数学描述目标函数或约束函数中至少有一个是非线性的F应用背景有着最广泛的应用，应该说所有现实问题都是非线性的，线性模型都是经过简化而来的。机械、电子等行业的器件最优设计问题，如飞行器的结构优化设计等；管理科学中的应用问题更是不胜枚举；系统控制问题。第9页，本讲稿共49页 决策论（decision)F著名

3、经济学家西蒙有一句名言：“管理就是决策”。F“决策”一词本身是一个广义的概念，本课程介绍的是针对在不确定或随机环境下的决策分析方法。F应用背景：产品开发决策问题、风险投资决策问题、开设连锁店问题等等第10页，本讲稿共49页 博弈论（博弈论（Game Theory)第11页，本讲稿共49页 博弈论博弈论F博弈论研究的问题是：当一个主体，如一个人或一个企业的选择，受到其他人、其他企业选择的影响，而且反过来又影响到其他人、其他企业选择时的决策问题和均衡问题。博弃论又称为“对策论”.F博弈论可以解释一些经济和社会现象，比如家电的价格战、民航业的价格战、国家之间的军备竞赛、“劣币逐良币”等等现象。第12

4、页，本讲稿共49页 排队论F银行、医院、机场跑道、港口码头、理银行、医院、机场跑道、港口码头、理发店、通信设备、交通路口等等的排队发店、通信设备、交通路口等等的排队现象；现象；F排队论是运筹学的又一个分支，又叫做排队论是运筹学的又一个分支，又叫做随机服务系统理论。它的研究目的是要随机服务系统理论。它的研究目的是要回答如何改进服务机构、或组织被服务回答如何改进服务机构、或组织被服务的对象，使得某种指标达到最优的问题。的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等工厂应该有多少维修人员等。第13页，本讲稿共49页 库

5、存论F存储物品的现象是为了解决供应（生产）与需求（消费）之间的不协调的一种措施；F由此带来一些需要决策的问题：库存量、进货量（如报童问题）、补货的时间等等决策量。F现在也是供应链管理研究中的热点问题。第14页，本讲稿共49页 运筹学会与杂志F中国运筹学学会(ORSC)TheOperationsResearchSocietyofChina网站:杂志:,F美国运筹与管理学会(IFORMS)InstituteforOperationsResearchandtheManagementSciences英文网址：http:/institutions.informs.org中文网站：http:/杂志第15页

6、，本讲稿共49页 Decision AnalysisInformation Systems ResearchINFORMS Journal on ComputingInterfacesManagement ScienceManufacturing&Service Operations ManagementMarketing ScienceMathematics of Operations ResearchOperations ResearchOrganization ScienceTransportation Science第16页，本讲稿共49页 运筹学软件FLINDO是一种专门用于求解数学

7、规划问题的软件包。由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题。因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数，可供使用者建立规划问题时调用。F一般用LINDO（LinearInteractiveandDiscreteOptimizer）解决线性规划（LPLinearProgramming）。整数规划（IPIntegerProgramming）问题。其中LINDO6.1学生版至多可求解多达300个变量和150

8、个约束的规划问题。其正式版（标准版）则可求解的变量和约束在1量级以上。第17页，本讲稿共49页 FLINGO则用于求解非线性规划（NLPNONLINEARPROGRAMMING）和二次规则（QPQUARATICPROGRAMING）其中LINGO6.0学生版最多可版最多达300个变量和150个约束的规则问题，其标准版的求解能力亦再104量级以上。虽然LINDO和LINGO不能直接求解目标规划问题,但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题。第18页，本讲稿共49页非线性规划NonlinearProgramming第19页，本讲稿共49页 1.1相关的数学知识F一、一般数

9、学描述可行域特别当R=En,称为无约束优化问题第20页，本讲稿共49页 1.1相关的数学知识二、解的定义F全局最优解、严格全局最优解；F局部最优解（极值点、极小点）三、多元函数的偏导F偏导数：指函数沿某个坐标轴方向的变化率；F梯度：由各个坐标轴方向组成的向量；F方向导数：指函数沿某个给定方向的变化率；F常用的求梯度公式第21页，本讲稿共49页 1.1相关的数学知识四、Hessian矩阵（二阶导数矩阵）F几个常用的公式五、正定矩阵F定义F正定二次函数六、多元函数的Taylor展开第22页，本讲稿共49页 1.1相关的数学知识七、凸函数、凸规划F凸集(convexset)：F凸函数(convex)

10、、凹函数(concave)：定义几何意义性质判别条件特别：线性函数既是凸函数也是凹函数。F凸规划(convexprogramming)第23页，本讲稿共49页 1.2解的最优性条件F一阶必要条件在极值点的梯度=0F二阶充分条件二阶导数矩阵为正定矩阵第24页，本讲稿共49页 1.3下降搜索算法F目标函数的等值线（二维，等高线）v对二次函数，等值线是一族同心的椭圆；对于非二次函数，在极小点附近，等值线近似一族同心椭圆；v具有不同值的等值线不相交；v等值线稠密处目标函数变化快，稀疏处变化慢；v等值线上一点的梯度与该点的的等值线切线方向相互垂直。第25页，本讲稿共49页 1.3下降搜索算法F算法：给定

11、一个初始点X0，然后按照一定的规则产生一个点列Xk，这种产生点列的规则称为算法；F下降算法的规则：给定一个初始点X0，在点Xk选择一个方向(向量)Pk,并沿此方向选择一点Xk+1=Xk+tkPk使得f(Xk+1)f(Xk)。第26页，本讲稿共49页 1.3下降搜索算法F算法步骤中的关键要素：给定初始点；确定寻优方向；确定一个步长；判别是否满足终止条件第27页，本讲稿共49页1.4 一维寻优方法一维寻优方法The One-Dimensional Search Procedure第28页，本讲稿共49页 一、“成功-失败”法F基本思想“成功”则大步向前，“失败”则小步后退。F框图F特点u简单易行，

12、对初始点选择无严格限制；u适用于不可微的函数；u在极小点附近收敛慢；u可用此方法来确定一个搜索区间。第29页，本讲稿共49页 二、牛顿法（切线法）F基本思想：适合二阶连续可微的函数，求导数为0的方程根。F迭代公式F算法步骤F特点u适用于二阶可微函数；u最快的收敛速度，二阶收敛速度；u初始点要求接近极小点；u可与“成功-失败”法联合使用。第30页，本讲稿共49页 序贯实验法F单峰函数（UnimodalFunction,下单峰、单谷)定义（在极小点左边单调下降，右边单调上升）性质(Unimodality，单峰性)F基本思想：通过选择实验点，计算其函数值，比较实验点的函数值大小，缩小包含极值点的区间

13、第31页，本讲稿共49页 二分搜索法TheDichotomyMethodwithoutDerivativesF基本思想对称取点，等比例缩小区间F特点：u简单u对称取点，不论取哪个区间，其长度相等；u每次要计算两次函数值第32页，本讲稿共49页 黄金分割法（0.618法)TheGoldenSectionSearchMethodF基本思想：对称取点，等比例的缩小区间，除第一次外，每次只需计算一次函数值，可使区间缩小。b0a0t11t12b1a1f(t11)f(t12)t22t21第33页，本讲稿共49页 黄金分割法（0.618法)TheGoldenSectionSearchMethodF实验点的计

14、算公式F算法步骤F特点：具有相同的区间缩短率0.618；精度不如Fobonacci分数法；适用于不可微、不连续函数，可以先用“成功-失败”法搜索到一个包含极小点的区间。第34页，本讲稿共49页 Fibonacci分数法TheFibonacciSearchMethodF基本思想对称取点，利用上次已有的实验点的函数值；F如何选择实验点，计算n次函数值能得到多大的区间缩短率？换句话说，计算n次函数值能将多大的区间缩短到1。第35页，本讲稿共49页 Fibonacci分数法FFibonacci数列(FibonacciSequence)F0=1,F1=1,F2=2,F3=5,F4=8,Fk=Fk-1+F

15、k-2F实验点的计算公式F计算步骤F算例第36页，本讲稿共49页 Fibonacci分数法F特点：需要预先确定迭代次数n;在计算n次函数值情况下，该方法获得最大的区间缩短率，精度最高；适用于不可微、不连续函数。第37页，本讲稿共49页 作业FP196,6.13,6.14第38页，本讲稿共49页1.5 多维无约束寻优方法多维无约束寻优方法The Multi-Dimensional Search Procedure第39页，本讲稿共49页 下降搜索算法F下降算法的规则：给定一个初始点X0，在点Xk选择一个方向(向量)Pk,并沿此方向选择一点Xk+1=Xk+tkPk使得f(Xk+1)f(Xk)。F不

16、同的寻优方向选择方法构成不同的算法；F有两类方法：解析法利用函数的梯度来构造寻优方向；直接法利用函数值来构造寻优方向；第40页，本讲稿共49页 最速下降法（梯度法）TheSteepestdescentmethodTheGradientMethodF基本思想：以负梯度方向作为寻优方向F算法步骤：F特点：迭代过程简单，存储量少，计算量小；即使是正定二次函数也不能有限步收敛；相邻两次寻优方向是垂直的;寻优路线呈锯齿状（Zig-Zag)，在极小点附近收敛缓慢;第41页，本讲稿共49页 X0P0P1X1X2P2P3X3X*X4第42页，本讲稿共49页 其他解析算法F共轭梯度法共轭梯度法(Conjugat

17、e gradient method)F牛顿法（牛顿法（Newtons method)F变尺度法变尺度法 （Variable Metric Method)（拟牛顿法（拟牛顿法Quasi-Newton method）第43页，本讲稿共49页 有约束优化问题的算法F解的最优性条件解的最优性条件Kuhn-Tucker 条件条件F求解算法求解算法直接法：可行方向法，梯度投影法等直接法：可行方向法，梯度投影法等间接法：将有约束问题转换成一系列的无约间接法：将有约束问题转换成一系列的无约束问题来求解，如惩罚函数法，乘子法等束问题来求解，如惩罚函数法，乘子法等第44页，本讲稿共49页 新算法F模拟退火算法（模

18、拟退火算法（Simulating anneal algorithm)模拟退火算法来源于固体退火原理，将固体加模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能用固体退火模拟组合优化问题，将内能E模拟模拟为目标函数值为目标函数值f，温度，温度T演化成控制

19、参数演化成控制参数t，即得，即得到解组合优化问题的模拟退火算法。到解组合优化问题的模拟退火算法。第45页，本讲稿共49页 新算法F遗传算法遗传算法(Genetic algorithm)遗传算法是模拟达尔文的自然选择学说和自然遗传算法是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它采用简界的生物进化过程的一种计算模型。它采用简单的编码技术来表示各种复杂的结构，并通过单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。汰的自然选择来指导学习和确定搜索的方向。一种新型的、随机

20、性的全局优化方法一种新型的、随机性的全局优化方法第46页，本讲稿共49页 新算法F粒子群算法粒子群算法(particle group algorithm)90年代中期年代中期,Eberhan博士和博士和Kennedy博士共同博士共同发明了一种新的群体智能计算技术发明了一种新的群体智能计算技术粒子群粒子群优化算法优化算法(Padicle.行为的研究行为的研究.粒子群优化算粒子群优化算法的基本思想是通过群体中个体之间的协作和法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解信息共享来寻找最优解;粒子群优化算法是基于一群粒子的智能运动而粒子群优化算法是基于一群粒子的智能运动而产生的随机进化

21、计算方法产生的随机进化计算方法,其优点是算法非常其优点是算法非常利于理解和应用利于理解和应用.第47页，本讲稿共49页 新算法F蚁群优化算法蚁群优化算法(Ant Colony Optimization，ACO)受到蚂蚁觅食时的通信机制的启发，受到蚂蚁觅食时的通信机制的启发，90年代年代Dorigo提出了蚁群优化算法提出了蚁群优化算法(Ant Colony Optimization，ACO)来解决计算机算法学中来解决计算机算法学中经典的经典的货郎担问题货郎担问题-如果有如果有n个城市，需个城市，需要对所有要对所有n个城市进行访问且只访问一次的个城市进行访问且只访问一次的最短距离。最短距离。第48页，本讲稿共49页 本章学习要点F掌握基本概念掌握基本概念凸集、凸函数、凸规划、正定二次函数的性质、凸集、凸函数、凸规划、正定二次函数的性质、特点特点F掌握一维无约束优化算法的基本思想、算掌握一维无约束优化算法的基本思想、算法步骤法步骤(0.618算法，算法，Fibonacci算法）算法）F了解多维无约束问题的下降搜索算法的基了解多维无约束问题的下降搜索算法的基本思想本思想.第49页，本讲稿共49页