最优化方法引言剖析

最优化方法OptimizingMethods数学与计算科学学院杨柳引言在各种活动，尤其经济活动中，如果要作一决策而备选方案不止一个，则自然希望所选方案是最优（最佳）的（某种意义下如：最短、最省、最大etc.）最优化方法就是从众多可能方案中选择以达到最优目标的科学。它是一门新兴的应用数学分支。引言---数学之重要数学是一种技术，是高技术的本质数学技术----数学方法与计算技术的结合形成的一种关键性的、可实现的技术对策论(博弈论)——研究冲突对抗条件下最优决策问题的理论坦白抵赖坦白5，50.5，20抵赖20，0.51，1囚犯的两难处境一位富翁在家中被杀，财物被盗。警方抓到两个犯罪嫌疑人，并从他们的住处搜出被害人家中丢失的财物。但是，他们矢口否认曾杀过人，辩称是先发现富翁被杀，然后只是顺手牵羊偷了点儿东西。于是警方将两人隔离，分别关在不同的房间进行审讯。由地方检察官分别和每个人单独谈话。检察官给出了上表的政策，囚犯该怎么办呢？他们面临着两难的选择——坦白或抵赖。引言---数学之重要结果：两人都选择了坦白，各被判刑5年。这个结局被称为“纳什均衡”也称非合作均衡。坦白抵赖坦白5，50.5，20抵赖20，0.51，1“纳什均衡”对亚当·斯密的“看不见的手”的原理提出挑战.按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果.从“纳什均衡”我们引出了“看不见的手”的原理的一个悖论：从利己目的出发，结果损人不利己，既不利己也不利他。“纳什均衡”提出的悖论实际上动摇了西方经济学的基石.引言---数学之重要关于案例，显然最好的策略是双方都抵赖，结果是大家都只被判1年。但是由于两人处于隔离的情况，首先应该是从心理学的角度来看，当事双方都会怀疑对方会出卖自己以求自保、其次才是亚当·斯密的理论，假设每个人都是“理性的经济人”，都会从利己的目的出发进行选择。这两个人都会有这样一个盘算过程：假如他坦白，如果我抵赖，得坐20年监狱，如果我坦白最多才5年；假如他要是抵赖，如果我也抵赖，我就会被判1年，如果我坦白就会被判0.5年，而他会坐20年牢。综合以上几种情况考虑，不管他坦白与否，对我而言都是坦白了划算。两个人都会动这样的脑筋，最终，两个人都选择了坦白，结果都被判5年刑期。基于经济学中Rationalagent（理性行为者）的前提假设，两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均只判1年就不会出现。这样两人都选择坦白的策略以及因此被判5年的结局，纳什均衡”首先对亚当·斯密的“看不见的手”的原理提出挑战：按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论：从利己目的出发，结果损人不利己，既不利己也不利他。二十世纪最伟大的数学家----二十世纪最伟大的物理学家----D.HilbertA.EinsteinNobelPrizeFieldsMedalGoback引言---数学之重要引言---课程之简介Example1婚姻问题(matchingproblem)DEF女儿ABC追求者EDF327151042628得到分配矩阵：如何嫁娶，使获得的礼品最多？7引言---课程之简介DEF1.贪婪（Greedy)解一般不会产生最差解；2.在某些模型中,贪婪算法能得到最优解；3.可以使用穷举法，但是以时间为代价贪婪解的结果：28+5+1=34最优解的结果：27+4+26=57Note：最差解的结果：3+10+7=20引言---课程之简介Example2旅行商问题（TravelingSalesmanProblem）TSP:有一位旅行售货员，欲到城市v1，v2,…，vn进行商品销售，已知：的距离为wij.(,).他从其中某个城市出发，需访问每一个城市一次且仅一次（在欧氏距离下）而回到出发的城市.问应如何计划他的旅行路线，使他所走路线的总长度最短？ijvvij,1~ijn共有（n-1)!种可能最优Hamilton回路引言---课程之简介设有n个城市（有向图）则有（n-1）！种可能方案。以计算机1秒可以完成24个城市所有路径枚举为单位，则城市数2425262728293031计算时间1s24s10min4.3h4.9d136.5d10.8y325y引言---课程之简介最优化方法是一门集理论与实验，既严密又富启发性的学科。既可把它当作应用数学的一个分支来研究，又几乎在所有科技领域中有广泛应用。现代优化计算方法：人工神经网络、模拟退火算法、遗传算法、蚁群算法etc.14引言---课程之简介主要的优化模型：线性规划（LinearProgramming）非线性规划（NonlinearProgramming）目标规划（GoalProgramming）整数规划（IntegerProgramming）动态规划（DynamicProgramming）网络规划（NetworkProgramming）(备用)引言---课程之简介对每个模型研究的主要内容：1、最优化模型的建立；2、各种模型的最优性条件的研究；3、数值求解方法（算法）的确定；4、这些方法结构的研究以及方法在试验性条件下对现实问题的计算机试验。引言---课程之简介教材及参考书目：1、《运筹学及其应用》胡觉亮等浙江人民出版社2004.082、《运筹学（第三版）》《运筹学》教材编写组清华大学出版社2005.063、《最优化方法》施光燕董加礼高等教育出版社2000.054、《IntroductiontoOperationsResearch》S.HillierJ.Lieberman1999.01Goback引言---课程之要求会做人会做事怎样做为什么这样做不这样做可以吗How?Why?Otherways?4、提高数学素养1、增强优化意识2、掌握常用的优化模型3、掌握求解这些模型的思想和方法(算法)比方法更重要未来的文盲不再是目不识丁的人，而是那些没有学会怎样学习的人AlvinToffler引言---课程之要求英国商船配置高射炮的评价重力加速度问题Ramsey数引言---课程之要求重力加速度问题AristotleHeavyLight快慢GalileoHeavyLight快？慢？Goback引言---课程之要求Ramsey(拉姆齐)数鸽洞（抽屉）原理：把100只鸽子关进99个洞里面，则其中必有一个洞内至少关有2只鸽子。●●●●●●认识：不认识：在世界任何地方找六个人，则其中必有三个人相互认识或相互不认识。数学规划模型实际问题中的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(..),(),()(1或x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析企业生产计划1奶制品的生产与销售空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。本节课题例1加工奶制品的生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划？每天：1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472xxzMax每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天模型分析与假设比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解图解法x1x20ABCDl1l2l3l4l55021xx48081221xx10031x0,21xx约束条件50:211xxl480812:212xxl1003:13xl0:,0:2514xlxl216472xxzMax目标函数Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解软件实现LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格•35元可买到1桶牛奶，要买吗？3548,应该买！•聘用临时工人付出的工资最多每小时几元？2元！RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.00000