数据结构课程设计停车场管理系统设计报告

开始最优化方法（最优化课件研制组）退出主讲：张京1最优化方法为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法是在第二次世界大战前后，在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。最优化方法解决问题一般步骤：（1）提出需要进行最优化的问题，开始收集有关资料和数据；（2）建立求解最优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件；（3）分析模型，选择合适的最优化方法；（4）求解方程。一般通过编制程序在电子计算机上求得最优解；（5）最优解的验证和实施。随着系统科学的发展和各个领域的需求，最优化方法不断地应用于经济、自然、军事和社会研究的各个领域。2第1章预备知识§1.2最优化问题实例上述4个例子都是最优化问题，其中例3与例4是NP问题，例1与例2是LP问题，例3是无约束问题，例4是有约束问题，将在第三章、第四章中讨论它们的基本理论与算法。通过求解方程组（求驻点）问题（2）1212min,,,..,,,0,1,2,,ninfxxxsthxxxilln0,1,,ifinx问题（1）1min(,,)nfxx3通过求111,2121(,,,,,),,,-,,,nnnljjnjLxxfxxxhxxx的无约束极值即可（也求L的驻点）。通过求驻点求极值问题的解的方法称为经典极值。它们的求解都归结为非线性方程组的解。优化模型分类：（1）按函数类型分，有线性和非线性模型；（2）按有无约束分，有无约束和有约束模型；（3）按变量类型分，变量取整数值和取连续值；（4）按目标个数分，有单目标和多目标模型；（5）按涉及的阶段分，有静态和动态模型；（6）按参数类型分，有确定性和非确定性优化。4优化方法的的解题步骤：1、建模；2、求解；3、回代。§1.3最优化问题的基本概念min..0,1,,()0,1,2,,()ijfxstsximhxjlln（1）的实值函数，f为目标函数，其余为约束条件。以上问题还可用向量形式写出：（2）min..00fxstsxhx1(,,),,,Tnijxxxfsh都是向量1(,,)Tnxxx511()((),,()),()((),,()).TTmlsxsxsxhxhxhx,,ijfsh均是的线性函数时，称为线性规划，否则称为非线性x规划。当所考虑问题为max()fx时，可用min(())fx来代替。当约束条件出现0时，可用（-1）乘两边，因而前面问题具有一般性。容许点（解）：称满足所有约束条件的点（或向量）x为容许点（解），所有容许解集合为容许集{()0,()0}Dxsxhx最优解：问题（1）的求解是指在D中找到一点*x，使对任意容许解,有*()(),fxfx这样的*x称为最优解，*()fx称为最优值。x6*x的各个分量及*()fx均为有限值。由于非线性，极值问题又分为局部极值与全局极值。邻域：称00(,){,0}Nxxxx为点0x的邻域(y称为向量y的长度，通常取21)niiyy局部极小点：若有点*,xD且有0,使对任意*(,),xDNx有*()(),fxfx则称*()xfxD为在上的局部极小点。全局极小点：如果有*,xD使对任意,xD*()(),fxfx有则称*()xfxD为在上的全局极小点。当上述两个不等式变为严格不等式时，分别称为严格局部极小点和严格全局极小点。7全局极小点一定是局部极小点。到目前为止，大多数最优化算法求到的都是局部极小点的近似解。为了求得全局极小点，一种解决办法是，先求出所有的局部极小点，然后再从中找出全局极小点。8***maxmin..0..000fxfxsthxsthxsxsxxxffx922min,21fxyxy§1.4二维问题图解法二维极值问题有时可以用图解的方式进行求解，有明显的几何解释。例1求解1022,21fxyxyc0c图解法的步骤：，显然；②取0,1,4,9,c并画出相应的曲线（称之为等值线）.③确定极值点位置，并用以往所学方法求之。易知本题的极小值点*2,1.Tx①令11例2求221212min(2)(1)..5xxstxx解等值线与容许集如图。我们的目标是让同心圆靠近（2,1）点，且与125xx有交点，显然，某同心圆与125xx相切时，切点即为极小点。圆01234560123456x2x1(x*1,x*2)1222*12(2)(1)xxf过**12(,)xx的切线方程为***1122(2)(2)(1)(1)xxxxf，它与125xx相同。所以****1212**1221(,)(3,2)5xxxxxx例3求221221221212min(2)(1)..5050,0xxstxxxxxxx解：2122225(5),xxxxx这是一个抛物线，它向1x轴方向开口，顶点在01234560123456x1CDBAx2虽然三维及以上的问题不便于在平面上画图，图解法失效，但仍有相应的等值面的概念，且等值面具有以下性质：（在①不同函数值的等值面互不相交（因目标函数是单值函数的缘故）；②等值面不会在区域的内部中断，除了极值点所在的等值面以外。这是由于目标函数是连续函数的缘故；nR使目标函数()fx取同一常数值的点集{(),xfxcc为一常数}称为等值面）1321221520,2.5,52.52.56.25.xxxx红线部分为容许集。显然，在D点处，目标值最小。D点满足方程1221225(4,1),(0,5).50xxxxx（4,1）为最优解。⑶等值面稠密的地方，目标函数值变化得比较快；等值面稀疏的地方，目标函数值变化得比较慢；⑷在极值点附近，等值面（等值线）一般近似地呈现为同心椭球面族（椭圆线族）。§1.5梯度和Hesse矩阵本段讨论都基于对函数fx为n元函数可微的假定。14称一、多元函数的梯度0()fxx在处的n个一阶偏导数构成的n维向量为0()fxx在处的梯度：0001()()()(,,)Tnfxfxfxxx多元函数的梯度有两个重要的性质：（1）如果函数在某点的梯度00,(()0),fx则必与过该点的等值面“垂直”。以二元函数为例来说明这个问题。00(,),(,)Zfxyxy在处的梯度0000(,)(,)(,)0fxyfxyZxy15不妨设0,xffx则x轴到梯度的转角的正切为（梯度斜率）00tan,(,)(,)yxfZfxyxyf而在处的等值面方程为00(,)(,)fxyfxyxoy,在平面上它表示一条曲线，曲线上任一点切线斜率为dydx，法线斜率为1dydx，两边微分等值面方程0000(,)(,)0xyfxydxfxydy法线斜率为11xyyfdyxdxfff16与梯度斜率一样，说明法线方向与梯度方向平行，而法线与等值面“垂直”，所以梯度与等值面垂直。（2）梯度方向具有最大变化率方向00(()fxx是处上升最快的方向，00()fxx是处下降最快的方向）方向导数：0()fxx在处具有一阶连续偏导数，p是非0向量，ep是上的单位向量，则称0000()()()limtfxfxtefxpt为0()fxx在处沿方向p的方向导数。17下降方向与上升方向：0(),,,0,0,nfxxpRp若存在使当(0,t）时，有00()(),fxtpfx则称()pfx为0x在处的下降方向；若00()(),fxtpfx则称()pfx为0x在处的上升方向。由定义可以得出：若0()0,fxp则p是下降方向；若0()0,fxp则p是上升方向。18因为0()0,fxp由极限性质，存在0,当(0,)t时，有00()()0fxtefxt即00()(),fxtefx代入pep知p是下降方向；同理，若0()0,fxpp是上升方向。在高数中，对于二元函数，已证明00()(),Tfxfxepep是上单位向量。由此可得到结论：当0()0Tfxp时，p是下降方向；当0()0Tfxp时，p是上升方向。对于多元函数来说，下降方向有19有许多，哪个方向使函数下降得最多呢？显然应由方向导数的值来确定，当取值达最小时，下降得最多。因为000ˆ()()cos((),)Tfxefxefxe且01,()efx是正数，当0ˆcos((),)1fxe时，方向导数负得最大，即当00ˆ(),cos((),)1efxfxe有所以负梯度方向是函数下降得最快的方向，同理正梯度方向是函数上升最快的方向。结合（1）知，梯度方向与等值面的法线方向一致，0()fx指向函数值增加的方向；0()fx指向函数值减少的方向。20例22120()1,(0,3)fxxxx求处最速单位上升，下降方向，令其在该方向上移动一个单位，求出新函数值。1,20(22),()(0,6),TTfxxfx解：最速单位上升方向为000000()(0,1),1(0,3)(0,1)(0,4),()()9110,()16117().TTTTfxexefxfxfxefx则最速单位下降方向为：000(0,1),1()(0,2),()415(),TTexefxefx0()fxx在处的等值面222212012021()10,9,()60Txxfxxxfxpp即而是下降方向，02()60Tfxpp是上升方向。21二、Hesse矩阵与多元函数的Taylor展开式一元函数0()fxx在处如果有n+1阶导数，则0()fxx在附近可展开为x的多项式形式。那么多元函数的展开又是什么呢？令00()(),tfxtpx为某一点，p为一(0)(0)11()(,,),nntfxtpxtp根据多元函数复合求导公式001122001121122200012,11()()(),()()()[]()()()[]nnnnnnnijijnnijfxtpfxtptppxxfxtpfxtptpppxxxfxtpfxtpfxtppppppxxxxx方向，t为一元变量,则其中(0)(0)011(,,),(,,)TTnnxxxppp22由矩阵向量知识，20220021120220021()(),()()()()()Tnnntpfxtppfxtpfxtpxxxfxtpfxtpfxtpxxx其中0()fxxtp称为在处的Hesse矩阵。显然Hesse矩阵是对称阵，由此可得Taylor展开式。定理：如0()fxx在处具有二阶连续偏导数，则210000222100002()()()(),,01,()()()()(),TTTTfxpfxfxppfxpxxpfxpfxfxppfxpop或23证：令0()(),tfxtp于是0(0)(),fx由于2000()(),(0)(),()()TTTtfxtppfxptpfxtpp将()0tt在处展开有212ˆˆ()(0)(0)(),,01,tttt于是22100002()()()(),TTfxtpfxfxptpfxtpPt令t=1,有2100002()()()().TTfxpfxfxppfxpp因为2每个分量连续，所以22000()(),0,limijijpijijfxpfxxxxx