最优化方法及其应用

第一章最优化问题总论无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题．最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科．例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标．这是最简单的最优化问题，实际优化问题一般都比较复杂．概括地说，凡是追求最优目标的数学问题都属于最优化问题．作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件．而且目标应是方案的“函数”．如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题．§1.1最优化问题数学模型最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题．例1.1对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为xxaxf2)2()(．令0)6)(2()2()2)(2(2)('2xaxaxaxxaxf，得两个驻点：axax6121，．第一个驻点不合实际，这是因为剪去4个边长为2a的正方形相当于将铁板全部剪去．现在来判断第二个驻点是否为极大点．∵axf824)(''，04)6(''aaf，∴6ax是极大点．因此，每个角剪去边长为6a的正方形可使所制成的水槽容积最大．例1.2求侧面积为常数)0(62aa，体积最大的长方体体积．解设长方体的长、宽、高分别为zyx，，体积为v，则依题意知体积为xyzzyxfv)(，，，条件为06)(2)(2axyxzyzzyx，，．由拉格朗日乘数法，考虑函数)6222()(2axyxzyzxyzzyxF，，，2()02()02()0xyzFyzyzFxzzxFxyxy，，，由题意可知zyx，，应是正数，由此0，将上面三个等式分别乘以zyx，，并利用条件23axyzxyz，得到2222(3)02(3)02(3)0xyzayzxyzazxxyzaxy，，．比较以上三式可得xyazxayza222333，从而azyx．又侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方体中以正方体体积最大，其最大值为3a．例1.3某单位拟建一排四间的停车房，平面位置如图1.1所示．由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？解设四间停车房长为1x，宽为2x．由题意可知面积为2121)(xxxxf，，且变量1x，2x应满足405221xx，1200xx，．即求2121),(maxxxxxf，1212254000xxxx，，．以上三个例子，虽然简单，但是它代表了三种类型的最优化问题．第一个例子代表无约束极值问题：一般可表示为),,,(min21nxxxf或),,,(max21nxxxf．这里，),,,(21nxxxf是定义在nR上的可微函数．求极值的方法是从如下含有n个未知数nxxx,,,21的非线性方程组x2x1图1.10)('0)('0)('21212121nxnxnxxxxfxxxfxxxfn，，，，，中解出驻点，然后判定或验证这些驻点是不是极值点．第二个例子代表具有等式约束的极值问题：一般可表示为121212min()max()()0123()nnjnfxxxfxxxhxxxjmmn，，，或，，，，，，，，，，，，．该问题的求解通常采用拉格朗日乘数法，即把这个问题转化为求121212121()()()mnmnjjnjLxxxfxxxhxxx，，，；，，，，，，，，，的无约束极值问题．第三个例子代表具有不等式约束的极值问题．下面具体分析上述三种类型的最优化问题中按经典极值问题解法可能出现不能解决的情况：（1）当变量个数增加且方程组又是非线性，求解此方程组只有在相当特殊情况下才能人工解出．正因为如此，通常高等数学中的求极值问题的变量个数一般不超过三个．（2）当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决．直到本世纪50年代，最优化理论的建立以及电子计算机的迅速发展，才为求解各种最优化问题提供了雄厚的基础和有效手段．不过最优化方法作为一门崭新的应用学科，有关理论和方法还没有完善，有许多问题还有待解决，目前正处于迅速发展之中．最优化问题的数学模型包含三个要素：变量（又称设计变量）、目标函数、约束条件．一、变量一个优化设计方案是用一组设计参数的最优组合来表示的．这些设计参数可概括地划分为两类：一类是可以根据客观规律、具体条件、已有数据等预先给定的参数，统称为常量；另一类是在优化过程中经过逐步调整，最后达到最优值的独立参数，称为变量．优化问题的目的就是使各变量达到最优组合．变量的个数称为优化问题的维数．例如有n个变量nxxx，，，21的优化问题就是在n维空间nR中寻优．n维空间nR中的点TnxxxX][21，，，就代表优化问题中的一个方案．当变量为连续量时，称为连续变量；若变量只能在离散量中取值，称为离散变量．二、目标函数反映变量间相互关系的数学表达式称为目标函数．其值的大小可以用来评价优化方案的好坏．按照规范化的形式，一般把优化问题归结为求目标函数的极小化问题，换句话说，目标函数值越小，优化方案越好．对于某些追求目标函数极大的问题，可以转化成求其负值最小的问题，即12max()max()min[()]nfXfxxxfX，，，．因此在本书的叙述中，一律把优化问题描述为目标函数的极小化问题，其一般形式为12min()min()nfXfxxx，，，．如果优化问题只有一个目标函数，称为单目标函数，如果优化问题同时追求多个目标，则该问题的目标函数称为多目标函数．多目标优化问题的目标函数通常表示为12min()[()()()]TmVFXfXfXfX，，，，其中TnxxxX][21，，，．这时的目标函数在目标空间中是一个m维矢量，所以又称之为矢量优化问题（一般用min加一个前缀“V”来表示矢量极小化）．三、约束条件变量间本身应该遵循的限制条件的数学表达式称为约束条件或约束函数．约束条件按其表达式可分为不等式约束和等式约束两种，即()012..()012ijgXilsthXjm，，，，，，，，，．上式中“s.t.”为Subjectto的缩写，意即“满足于”或“受限于”．按约束条件的作用还可将约束条件划分为起作用的约束（紧约束、有效约束）和不起作用的约束（松约束、消极约束）．等式约束相当于空间里一条曲线（曲面或超曲面），点X必须为该曲线（曲面或超曲面）上的一点，因而总是紧约束．有一个独立的等式约束，就可用代入法消去一个变量，使优化问题降低一维．因此，数学模型中独立的等式约束个数应小于变量个数；如果相等，就不是一个待定优化系统，而是一个没有优化余地的既定系统．不等式约束通常是以其边界)0)((0)(XgXg或表现出约束作用的，它只限制点X必须落在允许的区域内（包括边界上），因而不等式约束的个数与变量个数无关．不带约束条件的优化问题称为无约束最优化问题；带约束条件的优化问题称为约束最优化问题．四、带约束条件的优化问题数学模型表示形式综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种：第一种最优化问题表示形式为1212[]1212min()()012..()012()Tnnxxxinjnfxxxgxxxilsthxxxjmmn，，，，，，，，，，，，，，，，，，，，，，．第二种最优化问题表示形式为min()()012..()012()XijfXgXilsthXjmmn，，，，，，，，，，．第三种最优化问题表示形式为min()()0..()0XfGXstHX，，，X（1.1）其中11()[()()]()[()()]TTlmGXgXgXHXhXhX，，，，，．上述三种表示形式中，X称为集约束．在所讨论的最优化问题中，集约束是无关紧要的．这是因为一般nR，不然的话，通常也可用不等式约束表达出来．因此今后一般不再考虑集约束．满足所有约束的点X称为容许点或可行点．容许点的集合称为容许集或可行域．可用{|()012()012()}ijDXgXilhXjmmn，，，，；，，，，表示．一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点*X，使得目标函数)(Xf在该点取得极小值，即***()min()()0..()0fXfXGXstHX，，．这样的*X称为问题（1.1）的最优点，也称极小点，而相应的目标函数值)(*Xf称为最优值；合起来，))((**XfX，称为最优解，但习惯上常把*X本身称为最优解．最优点的各分量和最优值必须是有限数．§1.2最优化问题的算法一、二维最优化问题的图解法二维最优化问题具有鲜明的几何解释，这对于理解有关理论和掌握所述的方法是很有益处的．下面讨论的二维最优化问题为.0)(210)(..)(min212121xxhlixxgtsxxfi，，，，，，，（一）约束集合当约束函数为线性时，等式约束在21xx，的坐标平面上为一条直线；不等式约束在21xx，的坐标平面上为一半平面．当约束函数（例如)(21xxh，）为非线性时，则等式约束条件0)(21xxh，在21xx，的坐标平面上为一条曲线（如图1.2所示）．当约束函数（例如)(211xxg，）为非线性时，则不等式约束0)(211xxg，在21xx，的坐标平面上为曲线0)(211xxg，把坐标平面分成两部分当中的一部分（如图1.3所示）．图1.2图1.3综上所述，当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部分在21xx，坐标平面上画出之后，它们相交的公共部分即为约束集合D．例1.4在21xx，坐标平面上画出约束集合}001|],{[21222121xxxxxxDT，，．解满足12221xx的区域为以原点为圆心，半径为1的圆盘；满足0021xx，的区域为第一象限中的扇形（如图1.4所示）．（二）等高线我们知道)(21xxft，在三维空间中表示一张曲面．ct（其中c为常数）在三维空间中表示平行于21xx，平面的一个平面，这个平面上任何一点的高度都等于常数c（如图1.5所示）．图1.4图1.5现在，在三维空间中曲面)(21xxft，与平面ct有一条交线L．交线L在21xx，平面上的投影曲线是L，可见曲线L上的点Txx][21，到平面ct的高度都等于常数c，也即曲线L上的Txx][21，的函数值)(21xxf，都具有相同的值c．当常数c取不同的值时，重复上面的讨论，在21xx，平面上得到一簇曲线——等高线．不难看出，等高线的形状完全由曲面)(21xxft，的形状所决定；反之，由等高线的形状也可以推测出曲面)(21xxft，的形状．在以后的讨论中，不必具体画出曲面)(21xxft，的图形，只须在21xx，平面上变动常数c画出曲线簇cxxf)(21，．例1.5在21xx，坐标平面上画出目标函数222121)(xxxxf，的等高线．解因为当取0c时，曲线cxx2221表示是以原点为圆心，半径为c的圆．因此等高线是一簇以原点为圆心的同心圆（如图1.6所示）．（三）几何意义及图解法当在21xx，坐标平面上分别画出约束集合D以及目标函数)(21xxf，的等高线后，不难求出二维最优化问题的最优解．下面举例说明．例1.6用图解法求解二维最优化问题2212221212min[(2)(2)]1..00xxxxstxx