《数学建模最优化》由会员分享,可在线阅读,更多相关《数学建模最优化(87页珍藏版)》请在金锄头文库上搜索。
1、12几类典型优化问题及其软件解法几类典型优化问题及其软件解法3举例举例4最优化概论最优化概论MATLAB优化工具箱简介优化工具箱简介哇蜂蔗翁奴但大烷鞠挚诲睹震隆填弱惶嫁甫辜伦梆钟庸伞爱辫耽马唯圭武数学建模最优化数学建模最优化最优化概论最优化概论v当今,当今,“优化优化”无疑是一个热门词。做宏观经济无疑是一个热门词。做宏观经济规划要优化资源配置,搞企业经营管理要优化生规划要优化资源配置,搞企业经营管理要优化生产计划,作新产品设计要优化性能成本比。就是产计划,作新产品设计要优化性能成本比。就是在人们的日常生活中,优化的要求也比比皆是,在人们的日常生活中,优化的要求也比比皆是,消费时,如何花尽可能少
2、的钱办尽可能多的事,消费时,如何花尽可能少的钱办尽可能多的事,出行时,如何走最短的路程到达目的地,等等。出行时,如何走最短的路程到达目的地,等等。总而言之,在经济如此发展,竞争如此剧烈,资总而言之,在经济如此发展,竞争如此剧烈,资源日渐紧张的今天,人们做任何事,无不望求事源日渐紧张的今天,人们做任何事,无不望求事半功倍之术,以求或提效、或增收、或节约等等半功倍之术,以求或提效、或增收、或节约等等之目标。之目标。白泽抡崭取燃悸兴待罗躺他邢宣醒搓逞炬渝薛随昆兆古江俊冤贺欲颤锡联数学建模最优化数学建模最优化一、最优化概念一、最优化概念v所有类似的这种课题统称为最优化问题,研究解所有类似的这种课题统称
3、为最优化问题,研究解决这些问题的科学一般就总称之为决这些问题的科学一般就总称之为最优化理论和最优化理论和方法方法v另外也可用学术味更浓的名称:另外也可用学术味更浓的名称:“运筹学运筹学”。由。由于最优化问题背景十分广泛,涉及的知识不尽相于最优化问题背景十分广泛,涉及的知识不尽相同,学科分枝很多,因此这个学科名下到底包含同,学科分枝很多,因此这个学科名下到底包含哪些分枝,其说法也不一致。哪些分枝,其说法也不一致。v比较公认的是:比较公认的是:“规划论规划论”(包括线性和非线性(包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划、整数规划、动态规划、多目标规划和随机规划等),规划等),
4、“组合最优化组合最优化”,“对策论对策论”及及“最最优控制优控制”等等。等等。 宇冯拽颇等贮拜暗喝蛇但摇洪养黍笺痪东渴扛脾蚁椿歉振汤疥株植哦馆突数学建模最优化数学建模最优化数学建模竞赛中的优化问题数学建模竞赛中的优化问题v2000B钢管订购和运输问题钢管订购和运输问题二次规划二次规划v2001B公交车优化调度公交车优化调度v2001C基金使用的最优策略基金使用的最优策略-线性规划线性规划v2002B彩票中的数学彩票中的数学v2003B露天矿生产的车辆安排问题露天矿生产的车辆安排问题 v2004A奥运会临时超市网点设计问题奥运会临时超市网点设计问题 v2004D公务员招聘工作中录用方案公务员招聘
5、工作中录用方案多目标规划多目标规划v2005BDVD在线租赁在线租赁v2006A出版社的资源配置问题出版社的资源配置问题 v2007A乘公交,看奥运乘公交,看奥运 v2008B高等教育学费探讨高等教育学费探讨v2009B眼科病床的合理安排眼科病床的合理安排 品籽鹃龋联捌函逛咽行愚剑忙散毅绎励殿崇姨锡漏退枢救匝猿吁欲布地舵数学建模最优化数学建模最优化数学建模竞赛中的优化问题数学建模竞赛中的优化问题v2002B,彩票中的数学彩票中的数学约束非线性规划约束非线性规划舆曾盂巫涩舞依憾蚌照柠呀檄胜郁朴峡姿叁嘛篇肃波坏鼓镑风痒掩佃咒惕数学建模最优化数学建模最优化v从数学上来看,所谓最优化问题可以概括为这样
6、从数学上来看,所谓最优化问题可以概括为这样一种数学模型:给定一个一种数学模型:给定一个“函数函数”,F(X)F(X),以及,以及“自变量自变量”X”X应满足的一定条件,求应满足的一定条件,求X X为怎样的值为怎样的值时,时,F(X)F(X)取得其最大值或最小值。通常,称取得其最大值或最小值。通常,称F(X)F(X)为为“目标函数目标函数”,X X应满足的条件为应满足的条件为“约束条件约束条件”。约束条件一般用一个集合。约束条件一般用一个集合D D表示为:表示为:XDXD。v求目标函数求目标函数F(X)F(X)在约束条件在约束条件XDXD下的最小值或最下的最小值或最大值问题,就是一般最优问题的数
7、学模型大值问题,就是一般最优问题的数学模型垂酸闽杨迸超耗狱焚诅尔拘脚冻辕兵恢框酋韦斌贱笋咆颊臂束弹颖姜诬泽数学建模最优化数学建模最优化无约束最优化问题无约束最优化问题目标函数目标函数 二、最优化问题的一般形式二、最优化问题的一般形式约束最优化问题约束最优化问题约束函数约束函数 最优解;最优值最优解;最优值砂邮粥算蔑韩莆慎阿昨薄缄拷际帐山祟湾篷锋饲圃详馒膳呼丢臂血边径违数学建模最优化数学建模最优化三、最优化问题分类三、最优化问题分类分类分类1 1:无约束最优化无约束最优化 约束最优化约束最优化 非线性规划:非线性规划:目标函数与约束函数中至少有一个目标函数与约束函数中至少有一个是变量是变量x x
8、的非线性函数;的非线性函数; 线性规划:线性规划:目标函数与约束函数均为线性函数;目标函数与约束函数均为线性函数;分类分类2 2:线性规划线性规划 非线性规划非线性规划勉梢收急敷祁全惨棠爸枪番几钵遁客眷膝捉亢唇榔升二康珠但品囊盖梅坝数学建模最优化数学建模最优化三、最优化问题分类三、最优化问题分类( (续)续) 分类分类3 3(根据决策变量、(根据决策变量、目标函数和要求目标函数和要求不同)不同)整数规划整数规划动态规划动态规划网络规划网络规划随机规划随机规划几何规划几何规划多目标规划多目标规划茅蚂舰牌揍禄译镁钵所粟椒乖潘除象或栽哪誓收掀驶夸宾饺屁洋味脐锚饥数学建模最优化数学建模最优化三、最优化
9、问题分类三、最优化问题分类( (续)续)函数最优化函数最优化组合最优化组合最优化分类分类函数最优化:函数最优化:决策变量是一定区间内的连续变量决策变量是一定区间内的连续变量 组合最优化:组合最优化:决策变量是离散状态,同时可行域是决策变量是离散状态,同时可行域是由有限个点组成的集合由有限个点组成的集合 典型组合优化问题:典型组合优化问题:旅行商问题;旅行商问题;加工调度问题;加工调度问题; 0-10-1背包问题;图着色问题背包问题;图着色问题库缨眯书准尝溅烤坐煞环赢框研笼仲涡耀邀籍责四甭钩哭爷臆拱墟僳拾健数学建模最优化数学建模最优化四、求解最优化问题的方法四、求解最优化问题的方法(1 1)传统
10、优化方法)传统优化方法-基于导数的优化方法基于导数的优化方法 无约束规划:无约束规划:梯度法、共轭梯度法、拟牛顿法梯度法、共轭梯度法、拟牛顿法 约束规划:约束规划:序列二次规划法,罚函数法序列二次规划法,罚函数法 线性规划:线性规划:单纯形方法等单纯形方法等(2 2)现代优化方法)现代优化方法-智能优化方法智能优化方法 遗传算法,模拟退火法,蚁群算法,粒子群算法遗传算法,模拟退火法,蚁群算法,粒子群算法 神经网络算法,禁忌搜索算法等神经网络算法,禁忌搜索算法等 为了使系统达到最优的目标所提出的各种求解为了使系统达到最优的目标所提出的各种求解方法称为方法称为最优化方法最优化方法。母休譬平贯毅徒科
11、植俱刑延郊非话层鸭戒透逃裸用忧话滥触骏婴阑己援皑数学建模最优化数学建模最优化最优化方法通常采用迭代法求最优解,过程是最优化方法通常采用迭代法求最优解,过程是:五、构造数值优化算法的一般过程五、构造数值优化算法的一般过程或或迭代公式迭代公式跟犁亡慨懈杠陵鬃雅性舵敦汐由幸刻梢金俱锋矮蝉悠乏瓷腰炼彝项周胞浇数学建模最优化数学建模最优化六、最优化方法的基本结构六、最优化方法的基本结构溢昨怜宫抚纽矢膛诊寄似比鼠庇驮亭祥杯拦甥枫蚊隧性醋税生韧讨赫淬哭数学建模最优化数学建模最优化七、搜索算法结构框图七、搜索算法结构框图线性搜索求线性搜索求 ,使使x(k+1)S初始初始x(1) S, k =1对对x(k)点选
12、择下降点选择下降可行方向可行方向d(k)是否满足停机条件?是否满足停机条件?停停k=k+1YesNo叫货棺粥嘎俘舌宛残腊颜款墩鲤拽椅将氨捧加龋只诬绚焉觅淮嘘此瓦董水数学建模最优化数学建模最优化八、最优化方法解决问题的步骤八、最优化方法解决问题的步骤(1)确定变量,写出目标函数和有关约束条件,建)确定变量,写出目标函数和有关约束条件,建立数学模型。立数学模型。(2)分析模型,)分析模型,搞清它属于运筹学哪一分枝搞清它属于运筹学哪一分枝,选择选择合适的最优化方法;合适的最优化方法;(3)编程求解;)编程求解;尽量利用现有的数学软件或最优化尽量利用现有的数学软件或最优化软件,比如软件,比如 Matl
13、ab Matlab,MathematicaMathematica, Lindo Lindo, LingoLingo等,来计算。等,来计算。(4)最优解的验证和实施。)最优解的验证和实施。罩坐御镶澜涵样躯俄啦擅即挨匣恤灾鸿篓黄血窜肮秀膘韶冗双咀宏竹敌友数学建模最优化数学建模最优化九、九、MATLABMATLAB优化工具箱简介优化工具箱简介v1.功能功能v(1)求解无约束条件非线性极小值;)求解无约束条件非线性极小值;v(2)求解约束条件下非线性极小值,包括目标逼)求解约束条件下非线性极小值,包括目标逼近问题、极大近问题、极大-极小值问题和半无限极小值问题;极小值问题和半无限极小值问题;v(3)求
14、解二次规划和线性规划问题;)求解二次规划和线性规划问题;v(4)非线性最小二乘逼近和曲线拟合;)非线性最小二乘逼近和曲线拟合;v(5)非线性系统的方程求解;)非线性系统的方程求解;v(6)约束条件下的线性最小二乘优化;)约束条件下的线性最小二乘优化;v(7)求解复杂结构的大规模优化问题。)求解复杂结构的大规模优化问题。讼液碱柯司吏炊俄剃逾供肥智碟赊粥响抨留浊嗽鹃砰无锹釜慢簇记减松蹋数学建模最优化数学建模最优化2.常用函数:常用函数:一元函数极小值一元函数极小值 X=fminbnd(F,x1,x2, options)无约束极小值无约束极小值 X=fminunc(F,X0 , options)X=
15、fminsearch(F,X0 , options)线性规划线性规划 X=linprog(c,A,b , options)0-1整数规划整数规划 X=bintprog(F , options)二次规划二次规划X=quadprog(H,c,A,b , options)约束非线性规划极小值约束非线性规划极小值X=fmincon(FG,X0 , options)非线性最小二乘非线性最小二乘 X=lsqnonlin(F,X0 , options)目标达到问题目标达到问题X=fgoalattain(F,x,goal,w)极小极大问题极小极大问题X=fminimax(FG,x0)芥辰棠绢咸般糖员晌炕硫缝所
16、陇篇透蚜领送粘酌饥智阴漠捍笔俏偶辱岳横数学建模最优化数学建模最优化3.Options选项选项说明说明v输入参数中可以用输入参数中可以用options,用于所有函数,其中包括有,用于所有函数,其中包括有一下参数。一下参数。v(1)Display:结果显示方式,:结果显示方式,off不显示,不显示,iter显示每显示每次迭代的信息,次迭代的信息,final为最终结果,为最终结果,notify只有当求解不只有当求解不收敛的时候才显示结果。收敛的时候才显示结果。v(2)MaxFunEvals:允许函数计算的最大次数,取值:允许函数计算的最大次数,取值为正整数。为正整数。v(3)MaxIter:允许迭代
17、的最大次数,正整数。:允许迭代的最大次数,正整数。v(4)TolFun:函数值(计算结果)精度,正整数。:函数值(计算结果)精度,正整数。v(5)TolX:自变量的精度,正整数。:自变量的精度,正整数。v而且可以用函数而且可以用函数optimset创建和修改。创建和修改。惕幽砖帽疟讥撇鸭持湃言概矽号也惠弟淮畔郧扫黍涤月戮死酗寻莆趣勋剂数学建模最优化数学建模最优化4.输出变量说明输出变量说明变量变量描描 述述调用函数调用函数x由优化函数求得的值由优化函数求得的值.若若exitflag0,则则x为解为解;否则否则,x不是最终解不是最终解,它只是迭代制止时优化它只是迭代制止时优化过程的值过程的值所有
18、优化函数所有优化函数fval解解x处的目标函数值处的目标函数值linprog,quadprog,fgoalattain, fmincon,fminimax,lsqcurvefit,lsqnonlin, fminbndexitflag描述退出条件描述退出条件:exitflag0,表目标函数收敛于解表目标函数收敛于解x处处exitflag=0,表已达到函数评价或迭代的最表已达到函数评价或迭代的最大次数大次数exitflag0,表目标函数不收敛表目标函数不收敛output包含优化结果信息的输出结构包含优化结果信息的输出结构.Iterations:迭代次数迭代次数Algorithm:所采用的算法所采用
19、的算法FuncCount:函数评价次数函数评价次数所有优化函数所有优化函数怜背赎顷溺揉壶汪榆氖肤心剑港砧别匠嘿浓袄忽肾蝗朱粕彤别苏睫演泣诣数学建模最优化数学建模最优化2010数模竞赛培训数模竞赛培训几类典型最优化问题几类典型最优化问题及软件解法及软件解法颈厌注考样魏是严抑勇雌郝炼灼凄慌稚切梆腔疯箱恶猛今共椭嘻酝归柄桶数学建模最优化数学建模最优化线性规划问题及其线性规划问题及其MATLABMATLAB解法解法1.线性规划的一般形式线性规划的一般形式或或宰症虏宋沼圭蔼巴赚迭竣局讲啸矮疾勾兆购淫要哮此舱吭怒葡滚古始拒嘛数学建模最优化数学建模最优化线性规划问题及其线性规划问题及其MATLABMATLA
20、B解法解法2.线性规划的线性规划的matlab解法解法问题形式问题形式1:minz=CTxS.t.A xb指令:(指令:(x,z)=linprog(f,A,b)问题形式问题形式2:minz=CTxS.t.A xbAeq x=beq指令:(指令:(x,z)=linprog(f,A,b,Aeq,beq)械艾明王烂织裹席叭诬铝缕肇懈蝇违汹蜜淖掏滨传将蔗浩琢邦短污孵聪凹数学建模最优化数学建模最优化线性规划问题及其线性规划问题及其MATLABMATLAB解法解法问题形式问题形式3:minz=CTxS.t.A xbAeq x=beqlbxub指令:(指令:(x,z)=linprog(f,A,b,Aeq,b
21、eq,lb,ub) 注:注: 若没有不等式约束若没有不等式约束,可用可用 替代替代A和和b, 若没有等式约束若没有等式约束,可用可用 替代替代Aeq和和beq, 若某个若某个xi下无界或上无界下无界或上无界,可设定可设定-inf或或 inf;预逝艳甭挣椭谓勿紊健婆迸示乃典稀佩谐逐弱津操县临凭舔溃接坠萄底复数学建模最优化数学建模最优化x1+x2 5,-6 x1 10, -1 x2 4;4;例例:min Z= 4x1 +3x2s.t.解:程序如下解:程序如下c=4,3;a=1,1;b=5;c=4,3;a=1,1;b=5;vlb=-6;-1;vlb=-6;-1; % %lower bound of
22、vector x % %vub=10;4;vub=10;4; % % upper bound of vector x % % X,z=linprog(c,a,b,vlb,vub)X,z=linprog(c,a,b,vlb,vub)村雹闹峪猩抒剿权姻语傍切抗膏旦舞署盲粕楚篱昌拒冈受煞膛繁狄煞镜绣数学建模最优化数学建模最优化1. 整数线性规划一般形式整数线性规划一般形式依依照照决决策策变变量量取取整整要要求求的的不不同同,整整数数规规划划可可分分为为纯纯整整数数规规划划、混混合合整整数数规规划划、0 01 1整整数数规划。规划。整数线性规划整数线性规划(ILP)及其及其lindo解法解法部分或者全
23、部为整数部分或者全部为整数甫撵度逛翰导溉卖倒侍撇如郑金亲频甥苔崭葵硷夷均隧贞丢帧孩灵循撑瘁数学建模最优化数学建模最优化2、整数规划的计算机求解方法整数规划的计算机求解方法 目前,求解整数规划模型的现成数学软件有:目前,求解整数规划模型的现成数学软件有:Lindo, LingoLindo, Lingo和和MatlabMatlab, ,其中其中LindoLindo和和LingoLingo是专业是专业的优化软件的优化软件. . LINDO LINDO 公司软件产品是公司软件产品是美国芝加哥美国芝加哥(Chicago)(Chicago)大大学的学的Linus SchrageLinus Schrage教
24、授于教授于19801980年前后开发年前后开发, , 后来成后来成立立 LINDO LINDO系统公司(系统公司(LINDO Systems Inc.LINDO Systems Inc.)。)。 网址网址:http:/ 琐参种攀恤婪于佃厕跋烈埠士裕叙沙挚妓清仟创理蛀灰框枫妇化谊衍市牲数学建模最优化数学建模最优化LP问题的问题的Lindo输入范例输入范例MAX3x1+2x2ST2)X143)X234)2x1+3x212END注:注:Lindo中已规定所有决策变量均非负,故非负约束不用中已规定所有决策变量均非负,故非负约束不用输入;乘号省略,式中不能有括号,右边不能有数学符号;输入;乘号省略,式中
25、不能有括号,右边不能有数学符号;=与与等效;等效;2),),3),),4)是为了便于从结果中)是为了便于从结果中查找信息和进行灵敏性分析;程序以查找信息和进行灵敏性分析;程序以end结束。结束。捍赫坚犊谗糠捶烩懊渗树总悲庆喳临剖畦随糕蓑苫栅壁铆燃毅祭纲寞衬廓数学建模最优化数学建模最优化ILP问题的问题的Lindo输入范例之一输入范例之一MAX3x1+2x2ST2)X143)X234)2x1+3x212ENDGIN2(!表示前两个变量为一般整数表示前两个变量为一般整数)藐蔬艘坠儿闺轰威待奸经万刀譬恭染猎席九整道跌卵蚕乙勃厕吐表乃遵波数学建模最优化数学建模最优化ILP问题的问题的Lindo输入范例
26、之二输入范例之二MAX3x1+2x2ST2)X143)X234)2x1+3x212ENDINT2(!表示前两个变量为表示前两个变量为0-1整数整数)谨戒宰射猜散阻累顶广靶弘惺凑椅椎沪怯独腔永便板痉丽圾柿差试晕搂抑数学建模最优化数学建模最优化ILP问题的问题的Lingo输入范例一输入范例一MAX=3*x1+2*x2;STX14;X23;2*x1+3*x212;GIN(X1);GIN(X2);九网蛤溜蛮嗅略唯豺碟弗气族臆廓蓄峦杰浊霸率洛拍经物蕾怎究秧帐组滥数学建模最优化数学建模最优化ILP问题的问题的Lingo输入范例之二输入范例之二max3x1+2x2s.t.X14X232x1+3x2”(或(或
27、“=”(或(或“=”)功能相同)功能相同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头,不能超过变量名以字母开头,不能超过8个字符个字符4.变量名不区分大小写(包括变量名不区分大小写(包括LINDO中的关键字)中的关键字)5.目标函数所在行是第一行,第二行起为约束条件目标函数所在行是第一行,第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“)”结束结束7.行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如:!ItsComment.8.在模型的任何地方都可以用在模型的任何
28、地方都可以用“TITLE”对模型命名(最多对模型命名(最多72个字符),如:个字符),如:TITLEThisModelisonlyanExample柴我诡痢卸痒仑堆混伟呕吮窟靡腻活任赫汛呜鹰铃伴猛寐栽饵烷蹲底谨茅数学建模最优化数学建模最优化9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表达式应化简,如表达式应化简,如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定所有变量非负;可在模型的缺省假定所有变量
29、非负;可在模型的“END”语句后用语句后用“FREEname”将将变量变量name的非负假定取消的非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上下界设定变量上下界例如:例如:“subx110”的作用等价于的作用等价于“x1uiv交易费交易费=vpiuixiuiv而题目所给定的定值而题目所给定的定值ui(单位单位:元元)相对总投资相对总投资M很小很小,piui更小更小,可以忽略不计可以忽略不计,这样购买这样购买Si的净收益为的净收益为(ri-pi)xi割传初煮剃魄荒顶协峭缘就豌阳堡姆诫椎趟都鸥阮旗唬淡堪毡筑萝灸钵堰数学建模最优化数学建模最优化净收益尽可能大净收益尽
30、可能大建立模型建立模型总体风险尽可能小总体风险尽可能小多目标规划问题多目标规划问题壕承盔悸旨辙扔曾另亡柿及旋惟畴固砾乒涕傻校篙咕亏褪辗进傍镑饲抖喊数学建模最优化数学建模最优化采用主要目标法化为单目标规划采用主要目标法化为单目标规划方法一方法一. 固定风险水平,优化收益固定风险水平,优化收益 在实际投资中,投资者承受风险的程度不一样,在实际投资中,投资者承受风险的程度不一样,若给定风险一个界限若给定风险一个界限a,使最大的一个风险,使最大的一个风险qixi/Ma,可找到相应的投资方案。,可找到相应的投资方案。模型一模型一线性规划模型线性规划模型秦扬傲钞取赐籍整磕桂倍梗抛溺肩班波鬃约扮撑易屁凛猩登
31、窑涣筋簧欣羊数学建模最优化数学建模最优化若投资者希望总盈利至少达到水平若投资者希望总盈利至少达到水平k以上,在风险以上,在风险最小的情况下寻找相应的投资组合。最小的情况下寻找相应的投资组合。模型二模型二线性规划模型线性规划模型方法二:方法二:固定盈利水平,极小化风险固定盈利水平,极小化风险兹蓝稻勃就芜具撂刁阵勤孝限酣渍甄毗黔蚀孟茎迸慧邹匡机奎耗善料颤搓数学建模最优化数学建模最优化采用线性加权法化为单目标规划采用线性加权法化为单目标规划 投资者在权衡资产风险和预期收益两方面时,希望选投资者在权衡资产风险和预期收益两方面时,希望选择一个令自己满意的投资组合。因此对风险、收益赋择一个令自己满意的投资
32、组合。因此对风险、收益赋予权重予权重s(0s1),s称为投资偏好系数称为投资偏好系数.模型三模型三线性规划模型线性规划模型转冉俏狮周爹琅楚阑任伏逮匣蛆砧刮反致葱杀如妮性岛锣劣这发鬃募愉荡数学建模最优化数学建模最优化模型一的求解模型一的求解将具体数据代入将具体数据代入,模型一如下模型一如下: 由于由于a是任意给定的风险度,到底怎样给定没有一是任意给定的风险度,到底怎样给定没有一个准则,不同的投资者有不同的风险度。我们从个准则,不同的投资者有不同的风险度。我们从a=0开开始,以步长始,以步长a=0.001进行循环搜索,编制程序如下:进行循环搜索,编制程序如下:譬拴鞠鸡钧瘴传距补眷株眉量徘蓉剩炒黄咽
33、越颜儡钧蓄令咖伪蛾桥桑嘱玛数学建模最优化数学建模最优化a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.),axis(0 0.1 0 0.5),hold on a=a+0
34、.001;end xlabel(a),ylabel(Q)荐况悬眼涧制抉酝配株纷瑚惭惺絮靳齿继契巴族外哥梨卤枚锗清赏医菲惺数学建模最优化数学建模最优化计算结果:计算结果:v风险大,收益也大。风险大,收益也大。v曲线上的任一点表示该曲线上的任一点表示该风险水平的最大可能收风险水平的最大可能收益。益。v对于不同风险的承受能对于不同风险的承受能力,选择该风险水平下力,选择该风险水平下的最优投资组合。的最优投资组合。停间潘榆滔腥抑碳厂周阔灼操歇扁回旨殖裸福候乃爷舀握斧莱壁斌戍伸洽数学建模最优化数学建模最优化 在在a=0.006a=0.006附近有一个转折点,在这一点左边,附近有一个转折点,在这一点左边,
35、风险增加很少时,利润增长很快。在这一点右边,风险增加很少时,利润增长很快。在这一点右边,风险增加很大时,利润增长很缓慢,所以对于风险风险增加很大时,利润增长很缓慢,所以对于风险和收益没有特殊偏好的投资者来说,应该选择曲线和收益没有特殊偏好的投资者来说,应该选择曲线的拐点作为最优投资组合,大约是:的拐点作为最优投资组合,大约是: a a* *=0.6%=0.6%,Q Q* *=20% =20% 。 此时所对应投资方案为此时所对应投资方案为:风险度风险度=0.0060;收益;收益=0.2019;x0=0,x1=0.2400,x2=0.4000,x3=0.1091,x4=0.2212返抡切雅寅居窃契
36、替嘉貌惰郝蹲惫客幌恨司霉填和严拔界隔锚泞蹭挤焦劫数学建模最优化数学建模最优化约束非线性规划约束非线性规划一般形式:一般形式:其其中中,f(x)为为多多元元实实值值函函数数;g(x),ceq(x)为为向向量量函函数数,并并且且f(x),g(x), ceq(x)中中至至少少有有一一个个函函数数是是非非线线性性函函数数(否则成为线性规划问题)。(否则成为线性规划问题)。婉李驼跌琅嫉盅耗徐势锐峡拴嘘侯牟忻瞅瘩拿耳被动酞层刚蚊腕钵递兔寿数学建模最优化数学建模最优化x=fmincon(x=fmincon(funfun,x0,A,b),x0,A,b)x=fmincon(x=fmincon(funfun,x0
37、,A,b,Aeq,beq),x0,A,b,Aeq,beq)x=fmincon(x=fmincon(funfun,x0,A,b,Aeq,beq,lb,ub),x0,A,b,Aeq,beq,lb,ub)x=fmincon(x=fmincon(funfun,x0,A,b,Aeq,beq,lb,ub,nonlco,x0,A,b,Aeq,beq,lb,ub,nonlcon)n)x=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,x=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON, OPTIONS) OPTIONS)在在Matlab优化工
38、具箱中,优化工具箱中,fmincon函数是用函数是用SQP算算法来解决一般的约束非线性规划的函数,它的命令格法来解决一般的约束非线性规划的函数,它的命令格式为:式为:上式中上式中x为最优点;若将左端的为最优点;若将左端的x换为换为x,f,则返回则返回最优点最优点x和最优值和最优值f。蝇蕾狼葫冀篙蜒队夸陶鳃潦鹊肖婉伸簧坤酮溯鹿核氮痹载海瑟左他撞鹊杆数学建模最优化数学建模最优化【例【例1】求解约束非线性规划:求解约束非线性规划:(初值为初值为1;1)解解: :首先建立一个首先建立一个m文件文件fun1.mfunction y=fun1(x)y=-exp(x(1)*x(2)2*(3-exp(x(1)
39、-x(2)2); 存储为存储为fun1.m首先将问题转化为首先将问题转化为matlab要求的格式要求的格式;即求出即求出fun,A,b,Aeq,Beq,X0,Lb,Ub巳狡喘匣报戳它佳豆淡琴冻镣疥次倍察箱屋陵玄罢踪逛侍甭敞舀寒蛰息队数学建模最优化数学建模最优化function g,cep=fun2(x)g=; % g为非线性不等式为非线性不等式,且为且为g=0ceq=exp(x(1)+x(2)2-3; % ceq为非线性等式为非线性等式然后存储为然后存储为fun2.m建立主程序:建立主程序:A=;b=;Aeq=;Beq=;Lb=;Ub=;x,f=fmincon(fun1,1;1,fun2)-f
40、建立非线性约束建立非线性约束m-文件文件fun2.m运行结果为运行结果为:x = 0.8852 0.7592f = 6.2043e-016最优点最优点最优值最优值搀货缸我新截勤疙观崔锣迭这纶屉祖烟墨搅抹绦佩秃幂窄蜡友衬涂中疮校数学建模最优化数学建模最优化【例【例2】求解约束非线性规划:求解约束非线性规划:解:首先建立一个解:首先建立一个m文件文件 fun5.mfunction y=fun5(x)y=(x(1)-1)2+(x(2)-2)2+(x(3)-3)2+(x(4)-4)2;存储为存储为fun5.m文件文件.驹苇传悯搐整等罐割酥匡泳楷俊俊钟诵境穆蓬市彬片咕辰蓟酶梢适妄屯莫数学建模最优化数学建
41、模最优化x0=1;1;1;1;A=1 1 1 1;3 3 2 1;B=5;10;Aeq=;Beq=;Lb=0;0;0;0;x,g=fmincon(fun5,x0,A,B,Aeq,Beq,Lb)运行结果为运行结果为:x = 0.0000 0.6667 1.6665 2.6668g = 6.3333建立主程序建立主程序睬惠菠叼获贼希魏缨渊提采绎脓日潮柞携奄害端棕界洼送尺剖磕金蔚抹瑰数学建模最优化数学建模最优化小结:小结:用用Matlab求解非线性规划问题,基本步骤:求解非线性规划问题,基本步骤:1.首先建立首先建立M文件文件fun.m,定义目标函数定义目标函数f(x):function f=fun
42、(x);f= f(x);2.若若约约束条件中有非束条件中有非线线性性约约束束:g(x)或或Ceq(x)=0,则则建立建立M文件文件nonlcon.m定定义义函函数数g(x)与与Ceq(x):function g,Ceq=nonlcon(X)g=.Ceq=.3.建立主程序建立主程序.并运行。并运行。捂羽纲良叙怨松倡臭慨氯仍迫玄肖僻腹邑音括膘忆沫琐芜蹿台郝盗混鲜麻数学建模最优化数学建模最优化s.t.例如:例如:在对策论中:在最不利的条件下,寻求最有在对策论中:在最不利的条件下,寻求最有利的策略;利的策略;在投资规划中要确定最大风险的最低限度;在投资规划中要确定最大风险的最低限度;在城市规划中,要确
43、定急救中心的位置,使其到在城市规划中,要确定急救中心的位置,使其到所有地点最大距离为最小。所有地点最大距离为最小。最大最小化问题最大最小化问题冷场旺瓜褪阳燥袜吠捶锹瑶去囚陌完涛誉肛孵陕瘫苍茅篷阮饱骏营酷坷子数学建模最优化数学建模最优化求解最大最小化问题的求解最大最小化问题的Matlab函数为函数为fminimax.其调其调用格式如下:用格式如下:x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)或或x,fval,maxfval,exitflag,output=fminimax()其中:其中:x返回最优解;返回最优解;fval返回解返回解x处的目
44、标函数值;处的目标函数值;maxfval返回解返回解x处的最大函数值;处的最大函数值;exitflag描述计描述计算的退出条件;算的退出条件;output返回包含优化信息的输出返回包含优化信息的输出参数。参数。 胎渡真仑淮榷蛇驭盼巨器瓦仇船废幕景拢咖鹅竣念廉来防吊拙瓣恍僵攘快数学建模最优化数学建模最优化例:例:求解下列最大最小化问题:求解下列最大最小化问题: 首先编写一个首先编写一个M文件文件ff2.m,计算,计算4个函数值。个函数值。function f=ff2(x)f(1)=3*x(1)2+2*x(2)2-12*x(1)+35;f(2)=5*x(1)*x(2)-4*x(2)+7;f(3)=
45、x(1)2+6*x(2);f(4)=4*x(1)2+9*x(2)2-12*x(1)*x(2)+20;丝彝肤宋皆涸亏国刘振聚唬夺腕艇伐蠕氮圾凹赊剖乘颗耗射烙哩憋夹俄魏数学建模最优化数学建模最优化然后,输入初值然后,输入初值x0=(1,1),并调用优化函数进行计算,并调用优化函数进行计算x0=0 0;x,fval=fminimax(ff2,x0) 运行结果如下:运行结果如下:x = 1.7637 0.5317fval = 23.7331 9.5622 6.3010 23.7331敬锗袭市愚搞柴帚剂嚷捞骚害彩刃碉蛹豺你痊坍宴芥氨于疙菲仰乞厘捕优数学建模最优化数学建模最优化练习题:练习题: 设某城市有
46、某种物品的设某城市有某种物品的10个需求点,第个需求点,第i个个需求点需求点Pi的坐标为的坐标为(ai,bi),道路网与坐标轴平行,彼此道路网与坐标轴平行,彼此正交。现打算建一个该物品的供应中心,且由于受正交。现打算建一个该物品的供应中心,且由于受到城市某些条件的限制,该供应中心只能设在到城市某些条件的限制,该供应中心只能设在x界于界于5,8,y界于界于5,8的范围之内。问该中心应建在何处的范围之内。问该中心应建在何处为好为好?(即(即供应中心的位置到最远需求点的距离最小供应中心的位置到最远需求点的距离最小) Pi点的坐标为:点的坐标为:ai1435912620178bi21081814510
47、89哪虚熄肛拖苫甚鸵滨啤痪上涟驾简参菏国崭快累层沃亨打税鼠炒途价险惑数学建模最优化数学建模最优化无约束最优化问题无约束最优化问题v求一元函数求一元函数fun在区间在区间(x1,x2)上的最小值上的最小值vX=fminbnd(fun,x1,x2)v或或x,fval=fminbnd(fun,x1,x2)v求多元无约束函数求多元无约束函数fun的最小值的最小值vx,fval=fminunc(fun,x0)x0为初值为初值vx,fval=fminsearch(fun,x0)注意:注意:fminunc不是解决平方相加函数优化问不是解决平方相加函数优化问题的最好方法题的最好方法誓级锌垄众妨日纷拖斥俩膳受仍
48、阮沟臂碴藕剩康府咳搅贿痹婴椭网票眺蜡数学建模最优化数学建模最优化函数函数lsqnonlin专门解决非线性最小二乘问题:专门解决非线性最小二乘问题:调调用格式:用格式:x = lsqnonlin(fun,x0)x = lsqnonlin(fun,x0,lb,ub)x = lsqnonlin(fun,x0,lb,ub,options)酵吼坊茫氏忌菩触绍搓挫同恒哗烩络泥痹撑矮讹媚检冉溶驻苍佑铜俏酌忘数学建模最优化数学建模最优化线性最小二乘问题线性最小二乘问题lsqlin函数函数:用于解决:用于解决线线性最小二乘性最小二乘问题问题:调调用格式:用格式:x = lsqlin(C,d,A,b)x = ls
49、qlin(C,d,A,b,Aeq,beq)x = lsqlin(C,d,A,b,Aeq,beq,lb,ub)x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)菌箭那碧靴即有锥还葫厢浸游壁涛继笑紊绰洋戎田萄朔站铀释踞瓤尝旧瘟数学建模最优化数学建模最优化例例. 求解下面非线性最小二乘问题求解下面非线性最小二乘问题初始解向量为初始解向量为解:解:(1)建立函数文件建立函数文件example5.mfunction F = example5 (x)k = 1:10; F = 2 + 2*k-ex
50、p(k*x(1)-exp(k*x(2);x0=0.30.4;x,resnorm,residual=lsqnonlin(example5,x0)(2)调用优化程序:调用优化程序:企邯货盖害芜这早结辜惭装址塞案运棉喳滚飞澎扇襟陈姓愚哎钮萤单还愧数学建模最优化数学建模最优化(3)运行结果为运行结果为x=0.25780.2578resnorm=124.3622residual=Columns1through71.41182.65053.66544.39064.74084.60573.8428Columns8through102.2672-0.3600-4.3482residual为为解解x处处向量向量
51、f(x)的的值值最优解最优解最优值最优值稻坊销纳庙胃幼穴陡端胶潦打钞萎岛口虎遂起碧洞患督骇鹰锄黍渔恩用事数学建模最优化数学建模最优化无约束优化问题无约束优化问题1、一元函数极小问题、一元函数极小问题MinF(x)s.t.x1xx2x,fval=fminbnd(F,x1,x2)算法基于黄金分割法和二次插值法,它要算法基于黄金分割法和二次插值法,它要求目标函数必须是连续函数,并可能只给求目标函数必须是连续函数,并可能只给出局部最优解。出局部最优解。火鄙切勾眉催启比汪汞赠井淄卵熔毁僵拎锤焦丽登字细俭馋妇衣卖哩辨锐数学建模最优化数学建模最优化2、无约束多元极小化问题、无约束多元极小化问题MinF(X)
52、x,fval,exitflag,output=fminunc(F,X0,options)x,fval,exitflag,output=minsearch(F,X0,options)fminunc为无约束优化提供了大型优化和中型优化为无约束优化提供了大型优化和中型优化算法。算法。由由options中的参数中的参数LargeScale控制:控制:LargeScale=on,使用大型算法使用大型算法LargeScale=off,使用中型算法使用中型算法跋酵铝嘉讫汀消杜坛峰颇溃龚复懈膏蓟牢嚎宣浦降起蒲庭攫朋卉尘姑氮式数学建模最优化数学建模最优化fminunc为中型优化算法的搜索方向提供了为中型优化算法
53、的搜索方向提供了4种种算法,算法,由由options中的参数中的参数HessUpdate控制:控制:HessUpdate=bfgs(默认值),拟牛顿法的(默认值),拟牛顿法的BFGS公式;公式;HessUpdate=dfp,拟牛顿法的,拟牛顿法的DFP公式;公式;HessUpdate=steepdesc,最速下降法,最速下降法fminunc为中型优化算法的步长一维搜索提供了两为中型优化算法的步长一维搜索提供了两种算法种算法,由,由options中参数中参数LineSearchType控制:控制:LineSearchType=quadcubic(缺省值缺省值),混合的,混合的二次和三次多项式插值
54、;二次和三次多项式插值;LineSearchType=cubicpoly,三次多项式插值,三次多项式插值围搜漆茨慷二辈履裴瞄用瞪族葵成兴婴孪钉证政两探泅荫烟撒燎怨抨化畸数学建模最优化数学建模最优化三、控制参数三、控制参数options的设置的设置(3)MaxIter:允许进行迭代的最大次数允许进行迭代的最大次数,取值为取值为正整数正整数Options中常用的几个参数的名称、含义、中常用的几个参数的名称、含义、取值如下取值如下:(1)Display:显示水平显示水平.取值为取值为off时时,不显示输出不显示输出;取值为取值为iter时时,显显示每次迭代的信息示每次迭代的信息;取值为取值为fina
55、l时时,显示最终显示最终结果结果.默认值为默认值为final.(2)MaxFunEvals:允许进行函数评价的最允许进行函数评价的最大次数大次数,取值为正整数取值为正整数.惕溅虱巾刹逗滚厨踩蚕棒邢勉后姑谓掺费掺凳橱鸟巳既砌飘月惋逐汽姨乒数学建模最优化数学建模最优化(3)options=optimset(oldops,param1,value1,param2,value2,.)创建名称为创建名称为oldops的参数的拷贝的参数的拷贝,用指定的参数值用指定的参数值修改修改oldops中相应的参数中相应的参数.控制参数控制参数options可以通过函数可以通过函数optimset创建或创建或修改。命
56、令的格式如下:修改。命令的格式如下:(1)options=optimset(optimfun)创建一个含有所有参数名创建一个含有所有参数名,并与优化函数并与优化函数optimfun相关相关的默认值的选项结构的默认值的选项结构options.(2)options=optimset(param1,value1,param2,value2,.)创建一个名称为创建一个名称为options的优化选项参数的优化选项参数,其中指定其中指定的参数具有指定值的参数具有指定值,所有未指定的参数取默认值所有未指定的参数取默认值.莉噶套也悔廓岿楔狂伎宪库睹贫蒋芹礁另伏厅才丫哲垄蔽恰蹈玛靡仿败耶数学建模最优化数学建模最
57、优化2008数模竞赛培训数模竞赛培训优化问题建模举例优化问题建模举例彪苇谩忧盗呵惜窝栽革浦锚线监狭稚陪函涌蘑缺译爪灼梧镣立仆嫁绢顺伸数学建模最优化数学建模最优化v例例1某校篮球队准备从以下队员中选拔某校篮球队准备从以下队员中选拔3 3名为正式名为正式队员,并使平均身高尽可能高,这队员,并使平均身高尽可能高,这6 6名预备队员情名预备队员情况如下表所示况如下表所示。预备队员预备队员号码号码身高身高位置位置大张大张1193中锋中锋大李大李2191中锋中锋小王小王3187前卫前卫小赵小赵4186前卫前卫小田小田5180后卫后卫小周小周6185后卫后卫v队员的挑选要满足下列条件:队员的挑选要满足下列条
58、件:(1)至少补充一名后卫队员;至少补充一名后卫队员;(2)大李或小田中间只能入选一名;大李或小田中间只能入选一名;(3)最多补充一名中锋;最多补充一名中锋;(4)如果大李或小赵入选,小周就不能入选如果大李或小赵入选,小周就不能入选.v试建立此问题的数学模型。试建立此问题的数学模型。筐舀馅韶辈蛊提淬属元酝紫奠训肘角纽慨拂莎瘪粮习污泡鹅灰喻崖政稳煽数学建模最优化数学建模最优化解解: :则该问题的数学模型为则该问题的数学模型为: :(0-1)规划规划翼演稽溺虹播辩忘贝丝乓矗段火宗扣宫葵极街灯庞吗萤塞照徒侠祟渺枢污数学建模最优化数学建模最优化例例2 2 经典指派问题经典指派问题n n个员工分配做个员
59、工分配做n n项工作,已知第项工作,已知第i i个员工做第个员工做第j j项工作的项工作的成本为成本为c cijij,i=1,i=1,n; j=1,n; j=1,n,n。求最佳分配方案。求最佳分配方案。s.t.解解腮氰纠巴械蹈卖孩点坞介雨垂吧织夹剃骋帛畅渴腐待蜕硷怂旁达察色阶泥数学建模最优化数学建模最优化例例3 3 工厂工厂- -销售点配置问题销售点配置问题生产厂生产厂客户需求客户需求销售点销售点45DCBA7IIIII213I臼婿鹃束耀樊自瓶谴涪祟喻溅合捎铀慎盯饼宛饥塑摧精喊柑络栽契凭茂焕数学建模最优化数学建模最优化工厂工厂- -销售点配置问题销售点配置问题- -问题描述问题描述问题问题: 为使经营成本最低为使经营成本最低,应开设那些工厂及销售点应开设那些工厂及销售点?告摩涝悔媚提倒嗅摊雇忌最佰颅廊警搪烂导蹄亿专狈澜臭攘灶瓣蛙搽嘲抚数学建模最优化数学建模最优化工厂工厂- -销售点配置问题销售点配置问题- -模型参数罢珠阉魄乱茹流谚钒币小刽杰认辊茹厉蚕狠萝汲优妇筋屑趋脆孩绩链学吩数学建模最优化数学建模最优化工厂工厂- -销售点配置问题销售点配置问题- -模型怎佳依迷糖岗答剩浑所尖清胜恫腹泄傲每邦滞啸糕螺蕴廊预糠勾贾翼督绞数学建模最优化数学建模最优化咱赔襄贮揉旷其尸抛喘吗织使鹿凝雾赵刮沥韶鱼疡冻焕狄擎旅甫逝耙衡萝数学建模最优化数学建模最优化