组合优化问题(一).pptVIP

优 化 问 题 无 约 束 优 化 问 题 简单组合优化问题 组合优化 组合优化又称为离散优化，它的目标是从组合问题的可行解集中求出最优解，通常可描述为：令Ω＝{s1，s2，…，sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，使得对于所有的si∈Ω，有C(s*)＝minC(si)。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。 典型的组合优化问题有旅行商问题、加工调度问题、0-1背包问题、装箱问题、图着色问题等。 组合优化问题的数学模型为： * * 用Matlab解无约束优化问题 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。 常用格式如下： （1）x= fminbnd (fun,x1,x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）[x，fval]= fminbnd（...） （4）[x，fval，exitflag]= fminbnd（...） （5）[x，fval，exitflag，output]= fminbnd（...） 主程序为wliti1.m: f=2*exp(-x).*sin(x); fplot(f,[0,8]); %作图语句 [xmin,ymin]=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); [xmax,ymax]=fminbnd (f1, 0,8) 例2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？ 解 先编写M文件fun0.m如下: function f=fun0(x) f=-(3-2*x).^2*x; 主程序为wliti2.m: [x,fval]=fminbnd(fun0,0,1.5); xmax=x fmax=-fval 运算结果为: xmax = 0.5000,fmax =2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米. 命令格式为: （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，fval，exitflag，output]= fminsearch（...） 2、多元函数无约束优化问题 标准型为：min F(X) [3] fminunc为中型优化算法的步长一维有哪些信誉好的足球投注网站提供了两种算法， 由options中参数LineSearchType控制： LineSearchType=’quadcubic’(缺省值)，混合的二次和三 次多项式插值； LineSearchType=’cubicpoly’，三次多项式插 使用fminunc和 fminsearch可能会得到局部最优解. 说明: fminsearch是用单纯形法寻优. fminunc的算法见以下几点说明： [1] fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制： LargeScale=’on’(默认值),使用大型算法 LargeScale=’off’(默认值),使用中型算法 [2] fminunc为中型优化算法的有哪些信誉好的足球投注网站方向提供了4种算法，由 options中的参数HessUpdate控制： HessUpdate=’bfgs’（默认值），拟牛顿法的BFGS公式； HessUpdate=’dfp’，拟牛顿法的DFP公式； HessUpdate=’steepdesc’，最速下降法 例3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1) 1、编写M-文件 fun1.m: