最优化方法介绍通用课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最优化方法,计划学时数：64学时,教材：,最优化方法,，,解可新，韩健，林友联，天津大学出版社。,主要参考书目：,1最优化理论与算法，,陈宝林，清华大学出版社。,2最优化计算方法，,席少霖，赵凤治，上海科学技术出版社。,3非线性规划,，胡毓 达，高等教育出版社,上课时间：01-16周，周二 3,4节，周四3,4节上课地点：3-249,任课教师：李学文（中814）email:,最优化问题至少有,两要素,：一是,可能的方案,；二是要追求的,目标,。后者是前者的函数。,最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到,最优目标,。将达到最优目标的方案称为,最优方案,或最优决策，搜寻最优方案的方法称为,最优化方法,，关于最优化方法的数学理论称为,最优化论,。,最优化技术是一门,较新,的学科分支。,它是在本世纪五十年代初在电子,计算机,广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。,最优化方法,也称为,数学规划,，是,运筹学,的一个分支,.,最优化技术应用范围,十分广泛,。,在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。,最优化技术工作被分成,两个方面,，一是由实际生产或科技问题形成最优化的,数学模型,，二是对所形成的数学问题,进行求解,。,发展历史,微积分时代,极值问题，Langrange乘子法,1847年，Cauchy（柯西），最速下降法,函数值沿什么方向下降最快？,1939年，,康托洛维奇，线性规划,生产组织与计划中的数学方法,二次世界大战后，形成一个新的学科,生产和科学研究的发展，计算机的推广应用,内容,线性规划,单纯形法，Karmarkar方法，,无约束最优化方法,最速下降法，Newton法，共轭梯度法，拟Newton法，,约束最优化方法,罚函数法，乘子法，投影梯度法，简约梯度法，约束变尺度法，,整数规划,分枝定界法，割平面法，,动态规划,几何规划,随机规划,.,运筹学的正式产生：第二次世界大战,鲍德西（Bawdsey）雷达站的研究,1939年，以,Blackett,为首的一个研究小组（代号“Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。,Blackett备忘录,1941年12月，Blackett应盟国政府的要求，写了五份题为“Scientists at the Operational Level”的简短备忘录，建议在各大指挥部建立,运筹学小组,，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。,大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁,运筹学 的产生和发展,英国,OR,小组，美国,OR,小组,50,年 第一种运筹学杂志,48,年 英国运筹协会,52,年 美国运筹协会,59,年 国际运筹学会联盟,线性规划在苏联和美国的出现和发展,康托洛维奇,Dantzig,Koopmans,Von Neumann,线性规划的效用,58,年，美国,Mobil,公司,1975,年，康托洛维奇，,Koopmans,，,“最优资源配置理论的贡献”，诺贝尔经济学奖,由此可见运筹学一门应用性很强的学科。特别是随着计算机技术的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越显示出其广泛的使用价值。,运筹学在工业，农业，商业，物流，经济计划，人力资源，军事等行业都有着非常广泛的应用。有人曾对世界上500家著名的企业集团或跨国公司进行过调查，发现其中95%曾使用过线性规划，75%使用过运输模型，90%使用过网络计划技术，90%使用过存储模型，43%使用过动态规划。,现代运筹学在中国的兴起,钱学森,先生在MIT取得硕士学位，在加州理工大学（California Institute of Technology）取得博士学位后成为该校的第一位Goddard讲座教授。,许国志,先生在堪萨斯大学取得博士学位后，在马里兰大学流体力学和应用数学研究所当研究员。他们两人是第一个运筹学小组的领导者。,现代运筹学被引入中国是在五十年代后期。中国第一个运筹学小组在,钱学森,、,许国志,先生的推动下在1956年于中国科学院力学研究所成立。,中国运筹学会(ORSC),中国运筹学会于文化大革命后的1980年成立，当时作为中国数学会的一个分会。,第一届,全国大会在山东省济南召开，华罗庚教授当然地被选为第一届理事长，副理事长有许国志先生。,历史回顾,中国运筹学会在1982年成为国际运筹学联合会（IFORS）的成员。第二届全国代表大会和学术会议于1984年在上海召开，,越民义,先生被选为该届理事长。第三次全国会议于1988年在安徽省九华山召开，,徐光煇,先生任理事长。第五次全国代表大会和第六次全国代表大会分别于1996年和2000年在西安市和湖南长沙举行，,章祥荪,教授出任理事长。第七届全国代表大会在青岛于2004年10月19日举行,袁亚湘,为新一届理事长.,组织结构,中国运筹学会现有注册会员1200多名。中国运筹学会下属有多个专业分会：如决策科学分会；,数学规划分会,；排序分会；图论组合分会；排队论分会；青年分会；可靠性分会；金融工程及金融风险管理分会；智能计算分会；企业管理运筹分会；经济数学分会等，各分会定期或不定期进行学术交流。北京、陕西、山东、大庆等一些省市还有地区性运筹学会，部队系统有军事运筹学学会,仅大庆油田运筹学会就有会员二百多名，他们在许多领域应用运筹学理论与方法，取得了很好的经济效益与社会效益。,运筹学在中国的一些近期应用,（1）中国运筹学近期应用的亮点是由,华罗庚,教授点燃的。在文化大革命期间，身为中国数学会理事长和中科院院士的他，亲自率领一个小组，大家称为“华罗庚小分队”，到农村、工厂讲解基本的优化技术和统筹方法（PERT），使用于日常的生产和生活中。自1965年起的十年中，他到了约二十个省和无数个城市，受到各界人士的欢迎，他的工作得到了毛泽东主席的肯定和表扬。华罗庚先生这一时期的推广工作播下了运筹学哲学思想的种子，大大推动了运筹学在中国的普及和发展。直到今天，许多中国公民还记得“,优选法,”这个词汇，但不一定知道“运筹学”。,粮食产量预测,（2）中科院陈锡康教授提出了系统综合因素方法预测粮食产量。关键技术包括投入占用产出分析、考虑边际收益率递减的非线性预测方程，以及最小绝对和方法。自1980年始，在每年的四月底成功地预测中国全年的粮食产量，五月初报送给中国政府主要领导以及相关的政府职能部门。三个突出的特点：,预测提前期在半年以上（一般预测方法提前期一般是2个月）；,平均预测误差为1.6%（一般预测方法的平均预测误差为5-10%）；,预报粮食产量丰、平、欠方向正确。1999年陈锡康研究员等在北京召开的第十五届IFORS大会上获得一等奖。,陈锡康提供,（xkchen）,金融管理与经济发展方面的运筹学应用,（3）将优化及决策分析方法，应用于金融风险控制与管理、资产评估与定价分析模型等；例如陕西省运筹学会近年的一些运筹学应用:,证券投资：,沪深股市股指波动的交互影响效应分析,深圳股市内幕交易（例资产重组）的实证分析,经济发展（预测、评价、优化）：,陕北果业发展决策的优化分析,系统结构模型在陕北果业开发中的应用,陕北水果生产基地战略方针多层次分析决策模型,陕西省经济、资源、环境协调发展的相对有效性评价,陕西工业可持续发展的评价及对策,徐渝提供,（,）,工程管理,基于多层次灰色决策模型的施工方案评价,应用灰色理论、方法结合工程实例建立了多层次灰色决策模型对工程施工方案进行综合评价，得到了满意的结果。,建设项目投资风险的仿真分析,结合赢利性民用建筑项目的特点，建立了经济模型及其投资回收期仿真模型，并对仿真模型进行了精度估计,徐渝提供,（）,社会保障与服务业,1、运用排队理论方法对超市收费系统进行分析，建立了在一定的顾客满意度条件下超市的运营费用模型，按运营成本最小的目标进行了优化；,2、住院排队系统病床配置调整方法的分析研究,3、还应用排队理论建立了门诊排队模型与住院排队模型，进行了某医院的住院排队系统计算机仿真，针对扩建、新建医院建立了线性规划决策模型。,徐渝提供,（）,现代物流与供应链管理,供应链上库存协调的利益分享机制研究,应用库存理论及其整合模型建立并分析了竞争型与协商型库存协调的利益 分享模型，对其效率和特征进行了比较,企业供应链模型和采购满意度评价研究,与陕西省物资储运总公司合作的陕西省区域现代物流配送示范工程项目可行性分析与初步设计,徐渝提供,（）,最近的一些理论研究方向,(1)数学规划研究,开展对非线性规划,信赖域方法,的深入和细致的研究(袁亚湘);,开展对非线性,共轭梯度法,进行深入研究工作者(戴域虹、,袁亚湘,、韩继业、邓乃扬、王长钰等);,邓乃扬教授提出一类使用PCG技术的,不精确牛顿法,，大型问题显示出其巨大潜在作用;,研究求解,变分不等式问题,的一类,投影和收缩算法,(何炳生、孙德峰、修乃华、王长钰、王宜举等);,开展对求解变分不等式问题的,非光滑算法,研究，以及开展对求解变分不等式问题的非内点光滑化算法研究。,修乃华提供,（）,最近的一些理论研究方向,(2),不确定性决策研究,供应链管理。主要研究基于信息更新下，供应链模型的优化和决策。,随机存储模型。主要用博弈理论和随机比较理论来研究供应商和销售商之间的协调问题。,在不确定性环境下实时供应链控制和应急管理,具有多类顾客到达的随机排队网络优化与设计。主要研究优化与设计中最基本的两个问题，即具有多类顾客到达随机排队网络的稳定性与扩散逼近。,张汉勤提供（）,最近的一些理论研究方向,(3)离散与组合优化研究,基于判定树计算模型的计算复杂性理论：Rivest-Vuillemin猜想(堵丁柱,高随祥),近似算法：NP-难解问题的近似算法设计和分析,Steiner树问题：Steiner树问题的几何,网络和各种推广模型,计算机和通讯,网络,：交换网络，光纤网络，无线网络和移动网络(堵丁柱,胡晓东 ),排序,问题：排序问题的在线，半在线和离线模型,(何勇),装箱,问题：装箱问题的在线，离线和高维模型,(张国川),胡晓东提供（）,最近的一些理论研究方向,(4)信息科学、生命科学中的运筹学研究,将全局最优化、图论、神经网络等运筹学理论及方法应用于分子生物信息学中的DNA与蛋白质序列比较、芯片测试、生物进化,分析、蛋白质结构预测等问,题的研究；最近中科院数学,与系统科学研究院成立了“生,物信息研究中心”，主要成员,是运筹学者和统计学家，由,章祥荪,担任主任。,最近的一些理论研究方向,(5)与管理科学有关的运筹研究（,管理有效性的概念及测算方法）,管理本身存在着是否有效的问题。对管理好坏的程度进行科学的定量描述。,管理有效性的测算方法二次相对效益。,测算管理有效性的数学模型,冯英俊提供,（）,