暑期集训专题一 规划模型与综合评价模型PPT学习教案

1、会计学1暑期集训专题一暑期集训专题一 规划模型与综合评价模规划模型与综合评价模型型第1页/共171页一、规划模型回顾一、规划模型回顾 五、规划模型练习五、规划模型练习三、非线性规划模三、非线性规划模型型二、多目标规划模型二、多目标规划模型 四、四、Matlab优化工具箱简介优化工具箱简介第2页/共171页 （一）规划模型的数学描述（一）规划模型的数学描述下的最大值或最小值。下的最大值或最小值。.,.,)(mihi210 x.,.,),)()(piggii2100 xx),.,(nxxxx321x求函数：求函数：)(xfu 在等式约束条件：在等式约束条件：和不等式约束条件：和不等式约束条件：第3

2、页/共171页.,.,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(max)min(or规划模型的数学模型表达式：规划模型的数学模型表达式：第4页/共171页.,.,.,.,.minnixnibxatsxcuinkikikniii2102111（1）线性规划（）线性规划（LP） 目标函数和所有的约束条件都是决策目标函数和所有的约束条件都是决策变量的线性函数。变量的线性函数。（二）规划模型的分类（二）规划模型的分类第5页/共171页（2）非线性规划）非线性规划目标函数和约束条件中，至少有一个非线性函数。目标函数和约束条件中，至少有一个非线性函数。.,.

3、,)(.mihtsi210 x.,.,),)()(piggii2100 xx xxfu )(min第6页/共171页（3）二次规划问题）二次规划问题目标函数为二次函数，约束条件为线性约束目标函数为二次函数，约束条件为线性约束.,.,.,.,.)(min,nixnibxatsxxbxcxfuinjijijnjijiijniii2102121111第7页/共171页（4）整数规划（）整数规划（0-1规划）规划） 决策变量取值为整数，取值只能为决策变量取值为整数，取值只能为0或者或者1。（5）多目标规划）多目标规划 目标函数有两个或两个以上的规划。目标函数有两个或两个以上的规划。第8页/共171页（

4、三）建立规划模型的一般步骤（三）建立规划模型的一般步骤1.确定决策变量和目标变量；确定决策变量和目标变量；2.确定目标函数的表达式；确定目标函数的表达式；3.寻找约束条件。寻找约束条件。第9页/共171页123,x x x第10页/共171页第11页/共171页第12页/共171页第13页/共171页第14页/共171页第15页/共171页第16页/共171页第17页/共171页第18页/共171页第19页/共171页第20页/共171页第21页/共171页大豆大豆案例案例1 1：土地利用问题：土地利用问题例例: 某农场某农场I、II、III等耕地的面积分别为等耕地的面积分别为100 hm2、

5、300 hm2和和200 hm2，计划种植水稻、大豆和玉米，要求三种，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为作物的最低收获量分别为190000 kg、130000 kg和和350000kg。I、II、III等耕地种植三种作物的单产如下表所等耕地种植三种作物的单产如下表所示。若三种作物的售价分别为水稻示。若三种作物的售价分别为水稻1.20元元/kg，大豆，大豆1.50元元/ kg，玉米，玉米0.80元元/kg。那么，（。那么，（1）如何制订种植计划，）如何制订种植计划，才能使总产量最大和总产值最大？才能使总产量最大和总产值最大？ I I等等耕耕地地IIII等等耕耕地地IIIII

6、I等等耕耕地地水稻水稻11000110009500950090009000大豆大豆大豆大豆800080006800680060006000玉米玉米140001400012000120001000010000第22页/共171页 取取 xij 决策变量，它表示在第决策变量，它表示在第 j 等级的耕地上种植第等级的耕地上种植第i种作物的面积。如果追求总产量最大和总产值最大双重种作物的面积。如果追求总产量最大和总产值最大双重目标，那么，目标函数包括：目标，那么，目标函数包括： 33323123222113121111000012000140006000680080009000950011000)(m

7、axxxx+ xxx+ xxx=Xf 追求总产值最大追求总产值最大3332312322211312113332312322211312112800096001120090001020012000108001140013200)100001200014000(800)600068008000(501)9000950011000(201)(maxxxxxxxxxxxxx .+ xxx.+xxx.=Xf 追求总产量最大追求总产量最大第23页/共171页根据题意，约束方程包括：根据题意，约束方程包括： 200300100332313322212312111xxxxxxxxx 3500001000012

8、000140001300006000680080001900009000950011000333231232221131211xxxxxxxxxv 非负约束非负约束),;j,(ixij3213210 对上述多目标规划问题，我们可以采用如下方法，求对上述多目标规划问题，我们可以采用如下方法，求其非劣解。其非劣解。v耕地面积约束耕地面积约束v最低收获量约束最低收获量约束第24页/共171页用线性加权方法用线性加权方法 取取 1 1= = 2 2=0.5=0.5, ,重新构造目标函数：重新构造目标函数： 333231232221131211219000108001260075009000100009

9、9001045012100)(50)(50maxxxxxxxxxxXf.Xf.Z 这样，就将多目标规划转化为单目标线性规划。这样，就将多目标规划转化为单目标线性规划。 用单纯形方法对该问题求解，可以得到一个满意解（非劣解用单纯形方法对该问题求解，可以得到一个满意解（非劣解）方案，结果见表）方案，结果见表第25页/共171页 此方案是：此方案是：III等耕地全部种植水稻，等耕地全部种植水稻，I等耕地全等耕地全部种植玉米，部种植玉米，II等耕地种植大豆等耕地种植大豆19.1176公顷、种公顷、种植玉米植玉米280.8824公顷。在此方案下，线性加权目标公顷。在此方案下，线性加权目标函数的最大取值为

10、函数的最大取值为6445600。 第26页/共171页第27页/共171页第28页/共171页第29页/共171页第30页/共171页第31页/共171页第32页/共171页第33页/共171页DVD名称DVD1DVD2DVD3DVD4 DVD5愿意观看的人数200100502510第34页/共171页DVD编号D001D002D003D004DVD现有数量10401520会员在线订单C00016000C00020000C00030003C00040000表2 现有DVD张数和当前需要处理的会员的在线订单（表格格式示例）第35页/共171页 经营成本和会员的满意度是被考虑的两个相经营成本和会员

11、的满意度是被考虑的两个相互制约的重要因素互制约的重要因素. 在忽略邮寄成本的前提下，在忽略邮寄成本的前提下，经营成本主要体现为经营成本主要体现为DVD的数量的数量. 我们主要考虑我们主要考虑在会员向网站提供需求信息，且满足一定要求的在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量前提下，对给定数量DVD进行分配决策，使得进行分配决策，使得DVD的数量尽量小，会员满意度最大的数量尽量小，会员满意度最大. 第36页/共171页 假设按照公历月份进行的租赁业务，即会员假设按照公历月份进行的租赁业务，即会员无论两次租赁还是一次租赁，必须在当月内完成无论两次租赁还是一次租赁，必须在当月内完成

12、DVD的租与还的租与还. 同时假设网站对其会员进行一次同时假设网站对其会员进行一次租赁业务时，只能向其提供租赁业务时，只能向其提供3张该会员已经预定的张该会员已经预定的DVD，否则不进行租赁，否则不进行租赁. 经观察，可以认为在线订单中每个会员的预经观察，可以认为在线订单中每个会员的预定定DVD的表示偏好程度的数字反映了会员对所预的表示偏好程度的数字反映了会员对所预定不同定不同DVD的满意程度，且当会员租到其预定排的满意程度，且当会员租到其预定排序为序为1，2，3的三张的三张DVD时，满意度达到时，满意度达到100% .会员没有预定的会员没有预定的DVD对其满意度的贡献为对其满意度的贡献为0

13、. 第37页/共171页 利用层次分析法的思想，对此满意指数的合利用层次分析法的思想，对此满意指数的合理性进行简单分析理性进行简单分析. 该问题要求根据现有的该问题要求根据现有的100种种DVD的数量和的数量和当前需要处理的当前需要处理的1000位会员的在线订单，制定位会员的在线订单，制定分配策略，使得会员达到最大的满意度分配策略，使得会员达到最大的满意度. 因而我因而我们认为只需对这些们认为只需对这些DVD进行一次性分配，使得进行一次性分配，使得会员的总体满意度达到最大会员的总体满意度达到最大. 为此考虑建立优化为此考虑建立优化模型，进行求解模型，进行求解. 第38页/共171页 经营成本和

14、会员的满意度是被考虑的两个相经营成本和会员的满意度是被考虑的两个相互制约的重要因素互制约的重要因素. 在忽略邮寄成本的前提下，在忽略邮寄成本的前提下，经营成本主要体现为经营成本主要体现为DVD的数量的数量. 我们主要考虑我们主要考虑在会员向网站提供需求信息，且满足一定要求的在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量前提下，对给定数量DVD进行分配决策，使得进行分配决策，使得DVD的数量尽量小，会员满意度最大的数量尽量小，会员满意度最大. 第39页/共171页第40页/共171页第41页/共171页第42页/共171页由此，可得问题二的由此，可得问题二的0-1整数线性规划模型如

15、下：整数线性规划模型如下： 1000 100111001100011max2700030,1,2,.,1000,1,2,.,. .,1,2,.,1,2,.,10001,1,2,.,1,ijijijijijijjiijijijwc xxzixnjs txcijxij 100100 1000, 1000, 或或1000, 1000, 2,.,10001,1,2,.,izi 或或 1000, 1000,第43页/共171页 根据所得的根据所得的0-1整数线性规划模型，利用整数线性规划模型，利用LINGO软件进行求解，我们得到了一组最优分软件进行求解，我们得到了一组最优分配方案配方案. 该组最优解其目

16、标函数会员总体最大满意该组最优解其目标函数会员总体最大满意度为度为91.56%，只有，只有6人未成功租赁（如：前人未成功租赁（如：前30名会员中名会员中C0008未被分配到未被分配到DVD），其余），其余994个会员全都得到了个会员全都得到了3张预定的张预定的DVD . 第44页/共171页第45页/共171页第46页/共171页第47页/共171页第48页/共171页1001minjjzy由此，可以得到问题三的双目标整数线性规划模型由此，可以得到问题三的双目标整数线性规划模型如下：如下： 第49页/共171页10011000 100111000 10011100011001min1max27

17、000100030.951.61,100301,1000. .1,10001,100011,10001,jjijijijijijijjiijijijijijzywc xxxyjxzis txcijxij 或 100011,10001,100ijziyj或取整 第50页/共171页第51页/共171页10011000 100111000110011000 10011min100030.951.61,100301,1000. .1270001,10001,100011,10001,1jjijijijjiijijijijijijijijzyxxyjxzis tc xxcijxij 或 00011,1

18、0001,100ijziyj或 取整第52页/共171页第53页/共171页(1,2,.,100)jyj DVD编号D01D02D03D04D05D06D07D08D09D10最少购买量14211724121719212214DVD编号D11D12D13D14D15D16D17D18D19D20最少购买量18181717172418161823DVD编号D21D22D23D24D25D26D27D28D29D30最少购买量20182214181715121624DVD编号D31D32D33D34D35D36D37D38D39D40最少购买量19222019222213171717DVD编号D4

19、1D42D43D44D45D46D47D48D49D50最少购买量322016212216201520200.95第54页/共171页DVD编号D51D52D53D54D55D56D57D58D59D60最少购买量24171917191819172021DVD编号D61D62D63D64D65D66D67D68D69D70最少购买量16191920171917212019DVD编号D71D72D73D74D75D76D77D78D79D80最少购买量21221520151412171917DVD编号D81D82D83D84D85D86D87D88D89D90最少购买量1810141221132

20、2151317DVD编号D91D92D93D94D95D96D97D98D99D100最少购买量24171514251522201122第55页/共171页 前面介绍了线性规划问题，即目标函数和前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际约束条件都是线性函数的规划问题，但在实际问题建模过程中，还常常会遇到另一类更一般问题建模过程中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有的规划问题，即目标函数和约束条件中至少有一个是非线性函数的规划问题，即非线性规划一个是非线性函数的规划问题，即非线性规划问题问题. . 第56页/共171页m in ()

21、()0,1, 2,. .()0,1, 2,ijfxgxims thxjr第57页/共171页非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类： 无约束非线性规划模型：无约束非线性规划模型： 等式约束非线性规划模型：等式约束非线性规划模型：min ( )nf xxRmin ( ). . ( )0,1,2,jf xst h xjr第58页/共171页 不等式约束非线性规划模型：不等式约束非线性规划模型：1)1) 无约束的非线性规划问题无约束的非线性规划问题. .针对上述三类非线性规划模型，其常用求解的基针对上述三类非线性规划模型，其常用求解的基本思路可归纳如下：本思路

22、可归纳如下： min ( ). . ( )0,1,2,if xst g xim第59页/共171页第60页/共171页第61页/共171页 在下降迭代算法中，搜索方向起着关键的作在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好用，而当搜索方向确定后，步长又是决定算法好坏的重要因素坏的重要因素. 非线性规划只含一个变量，即一非线性规划只含一个变量，即一维非线性规划可以用一维搜索方法求得最优解，维非线性规划可以用一维搜索方法求得最优解，一维搜索方法主要有进退法和黄金分割法一维搜索方法主要有进退法和黄金分割法. 二维二维的非线性规划也可以像解线性规划那样用图形求的非线

23、性规划也可以像解线性规划那样用图形求解解. 对于二维非线性规划，使用搜索方法是要用对于二维非线性规划，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降到梯度的概念，最常用的搜索方法就是最速下降法法.第62页/共171页2)2) 只有等式约束的非线性规划问题通常可用消只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化元法、拉格朗日乘子法或反函数法，将其化为无约束问题求解为无约束问题求解. .3)3) 具有不等式约束的非线性规划问题解起来很具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为复杂，求解这一类问题，通常将不等式化为等式约束

24、，再将约束问题化为无约束问题，等式约束，再将约束问题化为无约束问题，用线性逼近的方法将非线性规划问题化为线用线性逼近的方法将非线性规划问题化为线性规划问题性规划问题.第63页/共171页 给定初始点nEX0，允许误差0,令 k=0； 计算kXf； 检验是否满足收敛性的判别准则： kXf， 若满足，则停止迭代，得点kXX*，否则进行； 令kkXfS，从kX出发，沿kS进行一维搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1，k=k+1 返回. 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位最速下降法是一种最基本的算法，它在最优化方法中占有重要地位. .最速下

25、降法的优点是工作量小，存储变量较少最速下降法的优点是工作量小，存储变量较少, ,初始点要求不高；缺点是初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法极值点时，宜选用别种收敛快的算法. . 1 1最速下降法（共轭梯度法）算法步骤：最速下降法（共轭梯度法）算法步骤：第64页/共171页2 2牛顿法算法步骤：牛顿法算法步骤：(1) 选定初始点nEX0，给定允许误差0，令 k=0；(2) 求kXf,12kXf,检验：若kXf,则 停止迭代,kXX*.否则, 转向(3)

26、；(3) 令 kkkXfXfS12（牛顿方向） ； (4) kkkSXX1,1 kk,转回(2). 如果如果f f是对称正定矩阵是对称正定矩阵A A的二次函数，则用牛顿法经过一次迭代的二次函数，则用牛顿法经过一次迭代就可达到最优点就可达到最优点, ,如不是二次函数，则牛顿法不能一步达到极值点，如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似但由于这种函数在极值点附近和二次函数很近似, ,因此牛顿法的收因此牛顿法的收敛速度还是很快的敛速度还是很快的. . 牛顿法的收敛速度虽然较快，但要求牛顿法的收敛速度虽然较快，但要求HessianHessian矩阵要可逆矩

27、阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量. .第65页/共171页3 3拟牛顿法拟牛顿法 为克服牛顿法的缺点，同时保持较快收敛速度的优点，利用第 k 步和第 k+1 步得到的kX，1kX，)(kXf，)(1kXf，构造一个正定矩阵1kG近似代替)(2kXf,或用1kH近似代替12)(kXf，将牛顿方向改为： 1kG1kS=-)(1kXf，1kS=-1kH)(1kXf从而得到下降方向.第66页/共171页 通常采用迭代法计算1kG，1kH，迭代公式迭代公式为:BFGSBFGS（Boryden-Fletcher-Goldf

28、arb-Shanno）公式 kkTkkTkkkkTkTkkkkxGxGxxGxfffGG)()()()(1 kTkTkkkTkkkTkkkxfxxxffHfHH)()()()(11 kTkTkkkkTkkxfxfHHfx)()()(第67页/共171页 D DF FP P（Davidon-Fletcher-Powell）公式： kTkTkkkTkkkTkkkXffffXXGXGG)()()()(11 kTkTkkkkTkkfXfXGGXf)()()( kkTkkTkkkkTkTkkkkfHfHffHXfXXHH)()()()(1 计算时可置IH 1（单位阵） ，对于给出的1X利 用上面的公式进

29、行递推.这种方法称为拟牛顿法拟牛顿法. . 返回第68页/共171页第69页/共171页有约束有约束非线性规划的基本解法非线性规划的基本解法SUTM外点法外点法SUTM内点法（障碍罚函数法）内点法（障碍罚函数法）1. 罚函数法罚函数法2.2. 近似规划法近似规划法第70页/共171页 罚函数法罚函数法 罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法序列无约束最小化方法.简称为SUMTSUMT法法 其一为SUMTSUMT外点法外点法, ,其二为SUMTSUMT内点法内点法第71页/共171页2211,m

30、in 0, (2)mlijijT X Mf XMgXMhX可设：)3( ,min 1MXTnEX）转化为无约束问题：将问题（ 其中T(X,M)称为罚函数罚函数，M称为罚因子罚因子，带M的项称为罚项罚项，这里的罚函数只对不满足约束条件的点实行惩罚:当 时，满足各 ，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚XD 0, 0XhXgiiDX 00XhXgii或SUTMSUTM外点法外点法 ) 1 ( .,.,2 , 1 0 m;1,2,., 0. . min ljXhiXgtsXfji对一般的非线性规划：第72页/共171页 罚函数法的缺点缺点是：每个近似最优解Xk往往不是容许

31、解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误1、任意给定初始点X0，取M11，给定允许误差 ，令k=1；2、求无约束极值问题 的最优解，设为Xk=X(Mk)，即 ；3、若存在 ，使 ，则取MkM( )令k=k+1返回（2），否则，停止迭代得最优解 .计算时也可将收敛性判别准则 改为 . 0MXTnEX,min),(,minkkEXMXTMXTnmii1kiXg10, 1MMk 0, 0min12miiXgMkXX*kiXg SUTMSUTM外点法外点法(罚函数法)的迭代步骤迭代步骤第73页/共171页) 1 (

32、,.,2 , 10. .min i mXgtsXfi考虑问题： 所有严格内点的集合。是可行域中，设集合00, 2 , 1, 0|DmiXgXDi 1111 1,ln (, )()1ln mmiiiimmiiiiI X rI X rfXrgXI X rf XrgXrgXrrgX构造障碍函数：或其中称或为障碍项， 为障碍因子0 1)min, kkkXDIX rXr这样问题( 就转化为求一系列极值问题：得（ ）SUTMSUTM内点法（障碍函数法）内点法（障碍函数法）第74页/共171页 内点法的迭代步骤内点法的迭代步骤(1) 给定允许误差0，取10 , 01r；(2) 求出约束集合 D 的一个内点0

33、0DX ，令1k；(3) 以01DXk为 初 始 点， 求 解kDXrXI,min0， 其 中0DX 的最优解，设为 0DrXXkk；(4) 检验是否满足mikiXgr1ln或miikXgr11，满足，停止迭代，kXX*；否则取kkrr 1，令1 kk，返回(3） 第75页/共171页 近似规划法的基本思想近似规划法的基本思想：将问题中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题,再用单纯形法求解之，把其符合原始条件的最优解作为原问题解的近似Xf), 1( 0 m);1,.,( 0ljXhiXgji近似规划法近似规划法每得到一个近似解后，都从

34、这点出发，重复以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。第76页/共171页 近似规划法的算法步骤如下近似规划法的算法步骤如下(2) 在点kX处，将Xf，XhXgji, 按泰勒级数展开并取一阶近似，得到近似线性规划问题： kTkkXXXfXfXfmin miXXXgXgXgkTkikii, 1 0 lXXXhXhXhkTkjkjj, 1j 0；第77页/共171页5) 判断精度： 若njkj, 1 ， 则点1kX为近似最优解；否则，令 njkjkj, 1 1，k=k+1，返回步骤(2)(3)在上述近似线性规

35、划问题的基础上增加一组限制步长的线性约束条件因为线性近似通常只在展开点附近近似程度较高，故需要对变量的取值范围加以限制， 所增加的约束条件是： njxxkjkjj, 1 求解该线性规划问题，得到最优解1kX；(4) 检验1kX点对原约束是否可行。若1kX对原约束可行，则转步骤(5)；否则，缩小步长限制，令 njkjkj, 1 ，返回步骤(3)，重解当前的线性规划问题；第78页/共171页第79页/共171页MatlabMatlab优化工具箱简优化工具箱简介介1.MATLAB1.MATLAB求解优化问题的主要函数求解优化问题的主要函数类 型模 型基本函数名一元函数极小Min F（x）s.t.x1

36、xx2x=fminbnd(F,x1,x2)无约束极小Min F(X)X=fminunc(F,X0)X=fminsearch(F,X0)线性规划Min XcTs.t.AX=bX=linprog(c,A,b)二次规划Min 21xTHx+cTxs.t. Ax=bX=quadprog(H,c,A,b)约束极小（非线性规划）Min F(X)s.t. G(X)=0X=fmincon(FG,X0)达到目标问题Min rs.t. F(x)-wr=goalX=fgoalattain(F,x,goal,w)极小极大问题Min max Fi(x)X Fi(x)s.t. G(x)0,则x为解;否则,x不是最终解,它

37、只是迭代制止时优化过程的值所有优化函数fval解x处的目标函数值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin, fminbndexitflag描述退出条件: exitflag0,表目标函数收敛于解x处 exitflag=0,表已达到函数评价或迭代的最大次数 exitflag0,表目标函数不收敛output包含优化结果信息的输出结构. Iterations:迭代次数 Algorithm:所采用的算法 FuncCount:函数评价次数所有优化函数第82页/共171页4 4控制参数控制参数optionsopti

38、ons的设置的设置 (3) MaxIterMaxIter: 允许进行迭代的最大次数,取值为正整数.OptionsOptions中常用的几个参数的名称、含义、取值如下中常用的几个参数的名称、含义、取值如下: : (1)DisplayDisplay: 显示水平.取值为off时,不显示输出; 取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果.默认值为final.(2)MaxFunEvalsMaxFunEvals: 允许进行函数评价的最大次数,取值为正整数.第83页/共171页例：opts=optimset(Display,iter,TolFun,1e-8) 该语句创建一个称为o

39、pts的优化选项结构,其中显示参数设为iter, TolFun参数设为1e-8. 控制参数控制参数optionsoptions可以通过函数可以通过函数optimsetoptimset创建或修改。创建或修改。命令的格式如下：命令的格式如下：(1) options=optimset(options=optimset(optimfunoptimfun) ) 创建一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构options.（2）options=optimset(options=optimset(param1param1,value1,value1,param2param2,v

40、alue2,.),value2,.) 创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.(3)options=optimset(oldops,options=optimset(oldops,param1param1,value1,value1,param2param2, , value2,.) value2,.) 创建名称为oldops的参数的拷贝,用指定的参数值修改oldops中相应的参数.返回第84页/共171页用用MatlabMatlab解无约束优化问题解无约束优化问题 1. 一元函数无约束优化问题一元函数无约束优化问题: : min f（x

41、） 21xxx 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：常用格式如下：（1）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2) )（2）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2 ，options)options)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag

42、= fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.）第85页/共171页运行结果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448 例例 1 1 求 f = 2xexsin在 0 x8 中的最小值与最大值 主程序为主程序为: f=2*exp(-x).*sin(x); fplot(f,0,8); %作图语句作图语句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,yma

43、x=fminbnd (f1, 0,8)第86页/共171页例例2 2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解解先编写先编写M M文件文件fminbndtest.mfminbndtest.m如下如下: : function f=myfun(x) f=-(3-2*x).2*x;主程序调用主程序调用fminbnd:fminbnd: x,fval=fminbnd(fminbndtest,0,1.5); xmax=x fmax=-fval运算结果为运算结果为: : xmax = 0.5000,fmax =2.0000.即剪掉的正方形的边长为0

44、.5米时水槽的容积最大,最大容积为2立方米.第87页/共171页 命令格式为命令格式为: :（1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ）（2）x= fminunc（fun,X0 ，options）； 或x=fminsearch（fun,X0 ，options）（3）x，fval= fminunc（.）； 或x，fval= fminsearch（.）（4）x，fval，exitflag= fminunc（.）； 或x，fval，exitflag= fminsearch（5）x，fval，exitflag，output= fminunc（.）； 或x，

45、fval，exitflag，output= fminsearch（.） 2、多元函数无约束优化问题、多元函数无约束优化问题标准型为标准型为：min F(X)第88页/共171页3 fminunc为中型优化算法的步长一维搜索提供了两种算法， 由options中参数LineSearchType控制：LineSearchType=quadcubic(缺省值)，混合的二次和三 次多项式插值；LineSearchType=cubicpoly，三次多项式插使用使用fminuncfminunc和和 fminsearchfminsearch可能会得到局部最优解可能会得到局部最优解. .说明说明: :fmins

46、earchfminsearch是用单纯形法寻优是用单纯形法寻优. fminunc. fminunc的算法见以下几点说明的算法见以下几点说明：1 fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制：LargeScale=on(默认值),使用大型算法LargeScale=off(默认值),使用中型算法2 fminunc为中型优化算法的搜索方向提供了4种算法，由 options中的参数HessUpdate控制：HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式；HessUpdate=dfp，拟牛顿法的DFP公式；HessUpdate

47、=steepdesc，最速下降法第89页/共171页例例3 3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1) （1 1）编写）编写M-M-文件文件 fun1.m:fun1.m: function f = fun1 (x) f = exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1); （2 2）输入）输入M M文件文件myprg3.mmyprg3.m如下如下: : x0 = -1, 1; x=fminunc(fun1,x0); y=fun1(x) （3 3）运行结果）运行结果: : x= 0.5000 -1.0000

48、 y = 1.3029e-10第90页/共171页 例4 Rosenbrock 函数 f（x1，x2）=100（x2-x12）2+(1-x1)2 的最优解（极小）为 x*=（1，1） ，极小值为 f*=0.试用 不同算法（搜索方向和步长搜索）求数值最优解. 初值选为 x0=（-1.2 , 2）. （2） 画出画出Rosenbrock 函数的等高线图函数的等高线图,输入命令：输入命令： contour(x,y,z,20) hold on plot(-1.2,2, o ); text(-1.2,2,start point) plot(1,1,o) text(1,1,solution)第91页/共1

49、71页（3 3）用）用fminsearchfminsearch函数求解函数求解输入命令: f=100*(x(2)-x(1)2)2+(1-x(1)2; x,fval,exitflag,output=fminsearch(f, -1.2 2)运行结果: x =1.0000 1.0000fval =1.9151e-010exitflag = 1output = iterations: 108 funcCount: 202 algorithm: Nelder-Mead simplex direct search第92页/共171页（4 4） 用用fminunc fminunc 函数函数(1)建立M-文

50、件fun1.m function f=fun1(x) f=100*(x(2)-x(1)2)2+(1-x(1)2(2)求解主程序 oldoptions=optimset(fminunc) options=optimset(oldoptions,LargeScale,off) options11=optimset(options,HessUpdate,dfp)x11,fval11,exitflag11,output11=fminunc(fun1, -1.2 2,options11)第93页/共171页用MATLAB软件求解,其输入格式输入格式如下: 1.x=quadprog(H,C,A,b); 2

51、.x=quadprog(H,C,A,b,Aeq,beq); 3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6.x,fval=quaprog(.); 7.x,fval,exitflag=quaprog(.); 8.x,fval,exitflag,output=quaprog(.);第94页/共171页例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+

52、2x22 s.t. x1+x22 -x1+2x22 x10, x20 1、写成标准形式写成标准形式： 2、 输入命令输入命令： H=1 -1; -1 2; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、运算结果运算结果为： x =0.6667 1.3333 z = -8.2222212121622 11- 1 ),(minxxxxxxzT212100222 11 1 xxxxs.t.第95页/共171页 1. 首先建立M文件fun.m,定义目标函数F（X）:

53、function f=fun(X);f=F(X); 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，基本步骤分三步：2. 若约束条件中有非线性约束:G(X)0或Ceq(X)=0,则建立M文件nonlcon.m定义函数G(X)与Ceq(X): function G,Ceq=nonlcon(X) G=. Ceq=. 第96页/共171页3. 建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A

54、,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,output= fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限第97页/共171页注意：注意：1 fmincon

55、函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。第98页/共171页1、写成标准形式写成标准形式： s.t. 00546322121xxxx2100 xx22212121212minxxxxf222121212

56、12minxxxxf 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例2第99页/共171页2、先建立先建立M-文件文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4、运算结果为：运算结果为： x = 0.7647 1.0588 fval = -2.0294第100页

57、/共171页1先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数: function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);) 12424()(22122211xxxxxexfx x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定义非线性约束：定义非线性约束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;第101

58、页/共171页3主程序主程序youh3.m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)4. 运算结果为运算结果为： x = -1.2250 1.2250 fval = 1.8951第102页/共171页 例4 100 , 50 07 025 . .2min 21222122221121xxxxXgxxXgtsxxXf1先建立先建立M-文件文件fun.m定义目标函数定义目标函数: function f=fun(x); f=-2*x(1)-x(2);2再建立再建立

59、M文件文件mycon2.m定义非线性约束：定义非线性约束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;第103页/共171页3. 主程序主程序fxx.m为为: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,mycon2)第104页/共171页4. 运算结果为运算结果为: x = 4.0000 3.0000fval =-11.0000exitflag = 1output = iterations: 4 funcCount:

60、17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: 第105页/共171页第106页/共171页A城和城和B城之间准备建一条高速公路，城之间准备建一条高速公路，B城位于城位于A城正南城正南20公里和正东公里和正东30公里交汇处，它们之间有东西走向连绵起伏公里交汇处，它们之间有东西走向连绵起伏的山脉。公路造价与地形特点有关，下图给出了整个地区的山脉。公路造价与地形特点有关，下图给出了整个地区的大致地貌情况，显示可分为三条沿东西方向的地形带。的大致地貌情况，显示可分为三条沿东西方向的地形带。你的任务是建立一个数学模型，在