数学建模优化

12几类典型优化问题及其软件解法3举例4最优化概论MATLAB优化工具箱简介最优化概论当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。一、最优化概念所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。数学建模竞赛中的优化问题2000B钢管订购和运输问题—二次规划2001B公交车优化调度2001C基金使用的最优策略-----线性规划2002B彩票中的数学2003B露天矿生产的车辆安排问题2004A奥运会临时超市网点设计问题2004D公务员招聘工作中录用方案—多目标规划2005BDVD在线租赁2006A出版社的资源配置问题2007A乘公交，看奥运2008B高等教育学费探讨2009B眼科病床的合理安排数学建模竞赛中的优化问题2002B，彩票中的数学—约束非线性规划从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型．无约束最优化问题)(minxfnRx目标函数二、最优化问题的一般形式约束最优化问题IixcEixctsxfii,0)(,0)(..)(min约束函数最优解；最优值三、最优化问题分类分类1：无约束最优化约束最优化非线性规划：目标函数与约束函数中至少有一个是变量x的非线性函数；线性规划：目标函数与约束函数均为线性函数；分类2：线性规划非线性规划三、最优化问题分类(续）分类3（根据决策变量、目标函数和要求不同）整数规划动态规划网络规划随机规划几何规划多目标规划三、最优化问题分类(续）函数最优化组合最优化分类４函数最优化：决策变量是一定区间内的连续变量．组合最优化：决策变量是离散状态，同时可行域是由有限个点组成的集合典型组合优化问题：旅行商问题；加工调度问题；0-1背包问题；图着色问题四、求解最优化问题的方法（1）传统优化方法-----基于导数的优化方法无约束规划：梯度法、共轭梯度法、拟牛顿法约束规划：序列二次规划法，罚函数法线性规划：单纯形方法等（2）现代优化方法-----智能优化方法遗传算法，模拟退火法，蚁群算法，粒子群算法神经网络算法，禁忌搜索算法等为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法通常采用迭代法求最优解，过程是：五、构造数值优化算法的一般过程)(min)(min)()(lim,}{*)()(xfxfxfxfxXxRxnnnn使点列某一迭代规则产生一个给定一个初始点，按照或迭代公式)()()()1(kkkkdxx.)()(次搜索方向为第次步长因子，为第其中kdkkk六、最优化方法的基本结构意义的下降；，使目标函数值有某种确定步长因子搜索方向处的下降可行方向作为点在造，即依照一定规则，构确定搜索方向，给定初始点)()()()0()(;)(kkkbxfdax)()()()1()(kkkkdxxc令.)1()1(，否则，重复以上步骤最优解停止迭代，得到近似满足某种终止条件，则若kkxx七、搜索算法结构框图线性搜索求，使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)k)()()()1(kkkkdxx是否满足停机条件？停k=k+1YesNo八、最优化方法解决问题的步骤（1）确定变量，写出目标函数和有关约束条件，建立数学模型。（2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法；（3）编程求解；尽量利用现有的数学软件或最优化软件，比如Matlab，Mathematica，Lindo，Lingo等，来计算。（4）最优解的验证和实施。九、MATLAB优化工具箱简介1.功能（1）求解无约束条件非线性极小值；（2）求解约束条件下非线性极小值，包括目标逼近问题、极大-极小值问题和半无限极小值问题；（3）求解二次规划和线性规划问题；（4）非线性最小二乘逼近和曲线拟合；（5）非线性系统的方程求解；（6）约束条件下的线性最小二乘优化；（7）求解复杂结构的大规模优化问题。2.常用函数：一元函数极小值X=fminbnd(‘F’,x1,x2,options)无约束极小值X=fminunc(‘F’,X0,options)X=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)3.Options选项说明输入参数中可以用options，用于所有函数，其中包括有一下参数。（1）Display：结果显示方式，off不显示，iter显示每次迭代的信息，final为最终结果，notify只有当求解不收敛的时候才显示结果。（2）MaxFunEvals：允许函数计算的最大次数，取值为正整数。（3）MaxIter：允许迭代的最大次数，正整数。（4）TolFun：函数值（计算结果）精度，正整数。（5）TolX：自变量的精度，正整数。而且可以用函数optimset创建和修改。4.输出变量说明变量描述调用函数x由优化函数求得的值.若exitflag0,则x为解;否则,x不是最终解,它只是迭代制止时优化过程的值所有优化函数fval解x处的目标函数值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin,fminbndexitflag描述退出条件:exitflag0,表目标函数收敛于解x处exitflag=0,表已达到函数评价或迭代的最大次数exitflag0,表目标函数不收敛output包含优化结果信息的输出结构.Iterations:迭代次数Algorithm:所采用的算法FuncCount:函数评价次数所有优化函数2010数模竞赛培训几类典型最优化问题及软件解法线性规划问题及其MATLAB解法1.线性规划的一般形式),,2,1(0),(),(),(..max)min(221122222121112121112211nixbxaxaxabxaxaxabxaxaxatsxcxcxczimnmnmmnnnnnn或或或或或或或),,2,1(0..max)(minnixbeqxAeqbAxtsxcziT或或线性规划问题及其MATLAB解法2.线性规划的matlab解法问题形式1：minz=CTxS.t.Ax≤b指令：（x，z）=linprog(f,A,b)问题形式2：minz=CTxS.t.Ax≤bAeqx=beq指令：（x，z）=linprog(f,A,b,Aeq,beq)线性规划问题及其MATLAB解法问题形式3：minz=CTxS.t.Ax≤bAeqx=beqlb≤x≤ub指令：（x，z）=linprog(f,A,b,Aeq,beq,lb,ub)注：若没有不等式约束,可用[]替代A和b,若没有等式约束,可用[]替代Aeq和beq,若某个xi下无界或上无界,可设定-inf或inf；x1+x25,-6x110,-1x24;例:minZ=4x1+3x2s.t.解：程序如下c=[4,3];a=[1,1];b=[5];vlb=[-6;-1];%lowerboundofvectorx%vub=[10;4];%upperboundofvectorx%[X,z]=linprog(c,a,b,[],[],vlb,vub)1.整数线性规划一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、混合整数规划、0－1整数规划。整数线性规划(ILP)及其lindo解法n)1.2(j0)2.1(.)min(max11jnjijijnjjjxmibxatsxcZZ或部分或者全部为整数2、整数规划的计算机求解方法目前，求解整数规划模型的现成数学软件有：Lindo,Lingo和Matlab,其中Lindo和Lingo是专业的优化软件.LINDO公司软件产品是美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.）。网址：)X143)X234)2x1+3x212END123234.23max212121xxxxtsxxz注：Lindo中已规定所有决策变量均非负，故非负约束不用输入；乘号省略，式中不能有括号，右边不能有数学符号；=，=与，等效；2），3），4）是为了便于从结果中查找信息和进行灵敏性分析；程序以end结束。ILP问题的Lindo输入范例之一MAX3x1+2x2ST2)X143)X234)2x1+3x212ENDGIN2(!表示前两个变量为一般整数)123234.23max212121xxxxtsxxzILP问题的Lindo输入范例之二MAX3x1+2x2ST2)X143)X234)2x1+3x212ENDINT2(!表示前两个变量为0-1整数)123234.23max212121xxxxtsxxzILP问题的Lingo输入范例一MAX=3*x1+2*x2;STX14;X23;2*x1+3*x212;@GIN(X1);@GIN(X2);123234.23max212121xxxxtsxxzILP问题的Lingo输入范例之二max3x1+2x2s.t.X14X232x1+3x212@bin(x1);@bin(x2);(!x1,x2为0-1变量)123234.23max212121xxxxtsxxz使用LINDO的一些注意事项1.“”（或“”）号与“=”（或“=”）功能相同2.变量与系数间可有空格(甚至回车),但无运算符3.变量名以字母开头，不能超过8个字符4.变量名不区分大小写（包括LINDO中的关键字）5.目标函数所在行是第一行，第二行起为约束条件6.行号(行名)自动产生或人为定义。行名以“）”结束7.行中注有“!”符号的后面部分为注释。如:!It’sComment.8.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLEThisModelisonlyanExample9.变量不能出现在一个约束条件的