最优化方法教案.docx

《最优化方法教案.docx》由会员分享，可在线阅读，更多相关《最优化方法教案.docx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第一章 最优化问题及数学预备学问最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。应用最优化方法解决问题时一般有以下几个特点：1. 好用性强2. 采纳定量分析的科学手段3. 计算量大，必需借助于计算机4. 理论涉及面广应用领域：工业，农业，交通运输，能源开发，经济支配，企业管理，军事作战。1.1 最优化问题实例最优化问题：追求最优目的的数学问题。经典最优化理论：（1） 无约束极值问题： （或）其中，是定义在n维空间上的可微函数。解法（求极值点）：求驻点，即满意并验证这些驻点是否极值点。（2） 约束极值问题：s.t. 解法：采纳Lagrange乘子法，即将问题转化为求L

2、agrange函数的无约束极值问题。近代最优化理论的实例：例1 (消费支配问题) 设某工厂有3种资源B1，B2，B3，数量各为b1，b2，b3，要消费10种产品A1，A10 。每消费一个单位的Aj须要消耗Bi的量为aij，依据合同规定，产品Aj的量不少于dj，再设Aj的单价为cj 。问如何支配消费支配，才能既完成合同，又使总收入最多？（线性规划问题）数学模型：设Aj的支配产量为，z为总产值。目的函数：约束条件： 线性规划问题通常采纳单纯形法来求解。例2 (工厂设址问题) 要在m个不同地点支配修建m个规模不完全一样的工厂，他们的消费实力分别是（为简便起见，假设消费同一种产品），第i个工厂的建立费

3、用。又有n个零售商店销售这种产品，对这种产品的需求量分别为，从第i个工厂运送一个单位产品到第j个零售商店的运费为cij。试确定应修建哪个工厂，使得既满意零售商店的需求，又使建立工厂和运输的总费用最小。（混合整数规划问题）数学模型： 设第i个工厂运往第j个零售商店的产品数量为xij（i=1，m；j=1，n），且目的函数：约束条件：整数规划问题通常可用分枝定界法或割平面法来求解。例3 (投资支配问题) 假设某一个消费部门在一段时间内可用于投资的总金额为亿元，可供选择的工程总共有n个，分别记为1，2，n。并且已知对第j个工程的投资总数为亿元，而收益额总数为亿元。问如何运用资金亿元，才能使单位投资获得

4、的收益最大。（非线性规划问题）数学模型：设目的函数：约束条件： 非线性规划问题的求解方法许多，是本课的重点。动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman最优性原理”，例如：资源安排问题，消费及存储问题。例4 (多参数曲线拟合问题)已知热敏电阻依靠于温度的函数关系为 （*）其中，是待定的参数，通过试验测得和的15组数据列表如下，如何确定参数？i12345678505560657075808534.7828.6123.6519.6316.3713.7211.549.744i910111213141590951001051101151208.2617.036.0055

5、.1474.4273.823.307建立数学模型：测量点及曲线对应的点产生“偏向”，即得如下无约束最优化问题：通常采纳最小二乘法。1.2 最优化问题的数学模型一、 最优化问题的数学模型1. 定义1：设向量.若，则记或；若，则记或。2一般模型： ， （1）s.t. 其中，；，是关于变量的实值连续函数，一般可假定它们具有二阶连续偏导数。3向量模型： ， （1）s.t. 其中，称为目的函数；，称为约束函数；满意约束条件（2），（3）的点称为容许解或容许点（或可行解）；可行解的全体称为容许域（或可行域），记为R；满意（1）的容许点称为最优点或最优解（或微小（大）点），记为；称为最优值；不带约束的问题称

6、为无约束问题，带约束的问题称为约束问题；若目的函数，约束函数，都是线性函数，则称为线性规划；若其中存在非线性函数，则称为非线性规划；若变量只取整数，称为整数规划；若变量只取0，1，称为01规划。注：因，则最优化问题一般可写成二、 最优化问题的分类1.3 二维问题的图解法例1. 解：1. 由全部约束条件作图，求出可行域R：凸多边形OABC2. 作出一条目的函数的等值线：设，作该直线即为一条目的函数的等值线，并确定在可行域内，这条等值线向哪个方向平移可使值增大。3. 平移目的函数等值线，做图求解最优点，再算出最优值。顶点是最优点，即最优解，最优值。分析： 线性规划问题解的几种状况（1） 有唯一最优

7、解（上例）；（2） 有无穷多组最优解：目的函数改为（3） 无可行解：增加约束，则。（4） 无有限最优解（无界解）：例 结论：（1）线性规划问题的可行域为凸集，特殊状况下为无界域或空集。（2）线性规划问题若有最优解，肯定可在其可行域的顶点上得到。例2. 解：目的函数等值线：C为最优点，得定义2：在三维及三维以上的空间中，使目的函数取同一常数的点集称为等值面。1.4 预备学问（一） 线性代数一、 n维向量空间1. 向量的内积：设，则内积为2. 向量的范数（或长度或模）：设，若实数具有以下性质：（1）当且仅当时；（2）；（3）.则称为上的向量的范数，简记为。规定了向量范数的线性空间称为线性赋范空间,

8、记为.3. 常见的向量范数向量的范数：，三个重要的向量范数：，注：若无特殊说明，本书中的指的是。4. 间的间隔 ：5. 及正交：若非零向量组，的向量两两正交，称它们是正交向量组。6. 标准正交基：，是n个正交的单位向量，即二、 特征值和特征向量定义：设为n阶方阵，存在数和非零向量，使，则称为矩阵的特征值，非零向量为矩阵属于特征值的特征向量。三、 正定矩阵定义：设为n阶实对称方阵，若对随意非零向量，均有，则称为正定二次型，为正定矩阵，记0。；若，半正定二次型，为半正定矩阵。类似有负定（半负定）二次型，负定（半负定）矩阵的概念。性质：实对称方阵为正定矩阵（负）的特征值均为正（负）的各阶依次主子式均

9、为正（奇数阶为负，偶数阶为正）实对称方阵为半正定矩阵的特征值均非负的各阶依次主子式均为非负（二） 数学分析一、 梯度和海色（Hesse）矩阵1. 多元函数的可微性可微定义：设，若存在维向量，对，总有 （1）则称函数在点处可微。式（1）等价于 （2）其中，是的高阶无穷小。 定理1：（可微的必要条件）若函数在点处可微，则在该点关于各个变量的偏导数存在，且2. 梯度（1）概念梯度：令则称为n元函数在处的梯度（或记为）。又称为关于的一阶导数。注：式（2）等价于 （3）等值面：在三维和三维以上的空间中，使目的函数取同一数值的点集称为等值面（曲面）。方向导数：设在点处可微，向量，是方向上的单位向量，则极限

10、称为函数在点处沿方向的方向导数，记作。方向导数的几何说明：方向导数表示函数在点处沿方向的的变更率。函数的下降（上升）方向：设是连续函数，点，为一方向，若存在，对于，都有（）则称方向是函数在点处的下降（上升）方向；结论1：若方向导数，则方向是在点处的下降方向；若方向导数，则方向是在点处的上升方向；（2）性质【性质1】：梯度为等值面在点处的切平面的法矢（向）量。【性质2】：梯度方向是函数具有最大变更率的方向。定理2：设在点处可微，则方向导数其中，是方向上的单位向量，为梯度及的夹角。结论2：1）及梯度方向成锐角的方向是上升方向；及梯度方向成钝角的方向是下降方向；2）梯度方向是函数值上升最快的方向，称

11、为最速上升方向；负梯度方向是函数值下降最快的方向，称为最速下降方向。（3）几种特殊函数的梯度公式（1），为常数；（2），其中；（3）；（4）若是对称方阵，则.例3. 泰勒（Taylor）公式及Hesse矩阵性质1：设具有一阶连续偏导数，则 （*）其中，即介于及之间。性质2：设具有二阶连续偏导数，则 （*）其中为函数关于的二阶导数，称为的海色（Hesse）矩阵。结论1：当时，（即海色矩阵对称）。注1：1) 设向量函数时，称为向量函数在点处的导数（梯度）。2) 向量函数在点处可微是指全部重量都在点处可微。关于向量函数常见的梯度：（1），；（2），；（3）（4）设，其中，则，例：（三） 微小点的断定

12、条件（求）一、 根本概念1. 点的邻域：2. 部分微小点：设. 若存在点和数，对 都有，则称为在上的（非严格）部分微小点；若（），则称为在上的严格部分微小点。3. 全局微小点：设. 若存在点，对于 都有，则称为在上的（非严格）全局微小点；若（），则称为在上的严格全局微小点。 性质：全局微小点必是部分微小点；但部分微小点不肯定是全局微小点。类似有极大点的概念。因，本书主要给出微小问题。4. 驻点：设可微，若，则称点为的驻点或临界点。 二、 极值的条件定理1（一阶必要条件）设具有一阶连续偏导数，是的内点，若是的部分微小点，则定理2（二阶必要条件）设具有二阶连续偏导数，若是的内点且为的部分微小点，则

13、是半正定的，即对恒有例定理3（二阶充分条件）设具有二阶连续偏导数，为的内点，且，若正定，则为的严格部分微小点。（四）凸函数及凸规划一、凸集1. 凸集的定义：一个n维向量空间的点集中随意两点的连线仍属于这个集合，即对，有则称该点集为凸集。2. 凸集的性质：（1）凸集的交集仍是凸集；（2）数乘凸集仍是凸集；（3）凸集的和集仍是凸集特殊规定，空集是凸集。3. 超平面：设且，则集合称为中的超平面，称为该超平面的法向量，即；（是凸集）半空间：集合称为中的一个半空间。超球：。4. 凸组合：设为中的个点，若存在且，使得则称为的凸组合。若均为正，则称为严格凸组合。5. 顶点（或极点）：设是凸集，若不能用内不同

14、两点和的凸组合表示，即，则称为的顶点。二、凸函数1. 凸函数：设，是凸集，若对及，都有则称为凸集上的凸函数；若则称为凸集上的严格凸函数。类似有凹函数的定义。2.几何意义：函数图形上连接随意两点的线段到处都在函数图形的上方。3. 性质性质1：为凸集上的凸函数，则也为上的凸函数。性质2：两个凸函数的和仍是凸函数。推论1：凸集上有限个凸函数的非负线性组合仍为上的凸函数。性质3：若为凸集上的凸函数，则对，的程度集是凸集。性质4：为凸集上的凹函数为凸集上的凸函数。4. 凸函数的充分必要条件定理1（一阶条件）设可微，是凸集，则（1）为凸函数对，恒有（2）为严格凸函数对，恒有定理2（二阶条件）设具有二阶连续

15、偏导数，为开凸集，则 （1）在内为凸函数对，是半正定的；（2）若正定，则在内为严格凸函数。特殊地，元二次函数为（为对称矩阵）；若正定，则称为正定二次函数。性质：正定二次函数是严格凸函数。（因为）5. 凸函数的极值定理3 设为凸集上的凸函数，则（1）的任一部分微小点为全局微小点；（2）若具有二阶连续偏导数，且存在，使，则为在上的全局微小点；（3）若为严格凸函数，且全局微小点存在，则必唯一。特殊：对于正定二次函数，有，得唯一驻点为唯一的全局微小点。6. 凸规划问题：非空凸集上的凸函数的微小化问题。考虑凸规划问题：， (1)s.t. 其中，为上的凹函数，为上的线性函数，为凸集，为上的凸函数。注：线性

16、函数既可视为凸函数，又可视为凹函数。二次规划： s.t. 其中，半正定或正定。 （五）下降迭代算法1. 下降迭代算法的步骤（1）选择一个初始点，令k：=0（2）检验是否最优？若是，则停顿迭代；若不是，则（3）确定一个下降方向：存在，对，使得（4）从点动身，沿方向进展直线搜寻（一维搜寻），即求步长使（5）计算，令k：=k+1，转（2）2. 直线搜寻及其性质（1）简记： 表示从点动身，沿方向进展直线搜寻，得到微小点。（2）定理：设目的函数具有一阶连续偏导数，若，则证明：（反正法）设，则1），此时是点的下降方向；2），此时是点的下降方向；及冲突。3. 收敛速度定义1：设序列是线性赋范空间中的点列，若

17、则称序列收敛于，记为。定义2：设向量函数，若当时，总有，则称在点连续；若在内每一点都连续，则称在内连续。特殊地，m=1时，为数量函数，则定义3：设序列收敛于，若存在及无关的数和，使得当从某个开场，都有则称序列收敛的阶为，或为阶收敛。当，且时，称线性收敛或一阶收敛；当时，称二阶收敛；当时，称超线性收敛。4. 计算终止准则计算终止准则依据相继两次迭代的结果a. 依据相继两次迭代的肯定误差（不常用），b. 依据相继两次迭代的相对误差，c. 依据目的函数梯度的模足够小为给定的足够小的正数。以上准则统称为Himmelblau计算终止准则，简称H终止准则。第二章 线性规划2.1 数学模型一、线性规划的标准

18、型1. 繁写形式：s.t. 其中，（否则，等式两端同乘以“-1”）。2. 缩写形式：s.t. 3. 向量形式：s.t. 其中，。4. 矩阵形式：s.t. 其中，：约束条件的系数矩阵，一般地，；：限定向量，一般地，；：价值向量；：决策向量，；通常，为已知，未知。二、任一模型化为标准型1. 极大化目的函数：令，则问题转化为2. 约束条件为不等式若约束为“”型，则“左端+松弛变量=右端”（松弛变量0）如：，引入松弛变量，化为若约束为“”型，则“左端-剩余变量=右端”（剩余变量0）如：，引入剩余弛变量，化为3. 若存在无非负要求的变量（称为自由变量）令，其中，代入目的函数及约束条件即可。4. 某变量有

19、上、下界若，即，令，有。用代替即可。若，即，令，有。用代替即可。例：2.2 线性规划解的性质一、根本概念标准型（LP）： s.t. 可行解（容许解）：满意约束（2）、（3）的解。最优解：满意（1）的容许解。基：设的秩为，若是中的阶可逆矩阵，称是线性规划问题（LP）的一个基。基向量：基中的一列（）即为一个基向量。（共个）非基向量：基之外的一列（）即为一个非基向量。（共个）基变量：及基向量相应的变量。（共个）非基变量：及非基向量相应的变量。（共个）根本解：令全部非基变量为0，求出的满意约束（2）的解。根本容许解：满意约束（3）的根本解。最优根本容许解：满意约束（1）的根本容许解。退化的根本解：若根

20、本解中有基变量为0的根本解。退化的根本容许解：退化的最优根本容许解：二、线性规划问题的根本定理定理1 若线性规划问题存在容许域，则其容许域是凸集。定理2 线性规划问题的根本容许解对应于容许域的顶点。定理3 若线性规划问题存在有限最优解，则其目的函数最优值肯定可以在容许域的顶点到达。2.3 单纯形法一、单纯形法原理单纯形法的根本思路：依据问题的标准型，沉着许域的一个根本容许解（一个顶点）开场，转移到另一个根本容许解（顶点），并且使目的函数值逐步下降；当目的函数到达最小值时，问题就得到了最优解。二、单纯形法的步骤（以“大M法”为例）数学描绘例（大M法）：s.t. 1. 构造初始容许基初始容许基是一

21、个单位矩阵，它相应的根本解是容许的。1引入附加变量，把数学模型化为标准型。2若约束条件中附加变量系数为“-1”，或原约束即为等式，则一般须引入人工变量。3目的函数中，附加变量系数为0，而人工变量系数为M（很大的正数）。人工变量系数为大M：只要人工变量0，使前后约束条件不等价，但由于目的函数的修改，同时也使所求的目的函数最小值是一个很大的数，也是对“篡改”约束条件的一种惩处，因此，M叫做罚因子，大M法也叫做罚函数法。若对极大化问题，目的函数中人工变量系数为（-M）。得到如下标准型：s.t. 其中，表示基变量；表示非基变量。2. 求出一个根本容许解1用非基变量表示基变量和目的函数。用非基变量表示基

22、变量，即有用非基变量表示目的函数，即其中，而称为非基变量的检验数。上式中，规定各基变量的检验数为0。其中，是基变量的价值系数，随基的变更而变更。2求出一个根本容许解及相应的目的函数值。令非基变量=0即得初始根本容许解：，初始目的函数值：3. 最优性检验1检验数：目的函数式中，各非基变量的系数，即称为各非基变量的检验数。2最优解判别定理：若在微小化问题中，对于某个根本容许解，全部检验数，且人工变量为0，则该根本容许解是最优解。3无穷多最优解判别定理：若在微小化问题中，对于某个根本容许解，全部检验数，又存在某个非基变量的检验数为0，且人工变量为0，则该线性规划问题有无穷多最优解。4无容许解判别定理

23、：若在微小化问题中，对于某个根本容许解，全部检验数，但人工变量不为0，则该线性规划问题无容许解。4. 基变换1根本容许解的改良定理：已知一个非退化的根本容许解具有目的函数值，设某一个非基变量，其，则存在一个可行解具有目的函数值；假如用代替原基中的某一列向量而产生一个新的根本容许解，则该新的解将有。2换入变量确实定为换入变量，使。3换出变量确实定最小非负比值规则为换出变量，使4无有限最优解判别定理：若在微小化问题中，对于某个根本容许解，有一个非基变量的检验数，但列中没有正元素，且人工变量为0，则该线性规划问题无有限最优解。三、单纯形法的表格形式1构造初始可行基，并计算检验数2从表中找出根本可行解

24、和相应的目的函数值3最优性检验4基变换1换入变量确实定2换出变量确实定3主元素确实定单纯形表中，换入变量所在的列和换出变量所在的行穿插处的元素为主元素（即），标“*”号。4取主变换（基变换）即单纯形法的一次迭代。在表中以主元素进展旋转变换（高斯消去法），把所对应的列向量于是得到新一轮的单纯形表。四、单纯形法解极大化和微小化问题的区分原模型目的函数标准型最优性检验换入变量确实定目的函数中人工变量系数为大M全部，且人工变量为0目的函数中人工变量系数为“-M”全部，且人工变量为0五、两阶段法1. 第一阶段：推断原线性规划问题是否有容许解。先求解以下线性规划（人工变量之和）s.t. 用单纯形法对上述问题求解。若，则原问题有容许解；若，则原问题无容许解，停顿计算。2. 第二阶段：求原线性规划问题的最优解。以第一阶段的最终单纯形表为根底，去掉其中的人工变量列，把目的函数换成原问题的目的函数，于是得到第二阶段的初始单纯形表，接着迭代下去，得最优解。