最优化方法教案

1第一章最优化问题与数学预备知识最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。应用最优化方法解决问题时一般有以下几个特点：1.实用性强2.采用定量分析的科学手段3.计算量大，必须借助于计算机4.理论涉及面广应用领域：工业，农业，交通运输，能源开发，经济计划，企业管理，军事作战……。§1.1最优化问题实例最优化问题：追求最优目标的数学问题。经典最优化理论：（1）无约束极值问题：),,,(opt21nxxxf（),,,(min21nxxxf或),,,(max21nxxxf）其中，),,,(21nxxxf是定义在n维空间上的可微函数。解法（求极值点）：求驻点，即满足0),,(0),,(0),,(11121nxnxnxxxfxxfxxfn并验证这些驻点是否极值点。（2）约束极值问题：),,,(opt21nxxxfs.t.)(,,2,1,0),,,(21nlljxxxhnj解法：采用Lagrange乘子法，即将问题转化为求Lagrange函数2),,(),,,(),,;,,,(1121121njjljnlnxxhxxxfxxxL的无约束极值问题。近代最优化理论的实例：例1(生产计划问题)设某工厂有3种资源B1，B2，B3，数量各为b1，b2，b3，要生产10种产品A1，…，A10。每生产一个单位的Aj需要消耗Bi的量为aij，根据合同规定，产品Aj的量不少于dj，再设Aj的单价为cj。问如何安排生产计划，才能既完成合同，又使总收入最多？（线性规划问题）数学模型：设Aj的计划产量为jx，z为总收入。目标函数：max101jjjxcz约束条件：10,,2,1,3,2,1,101jdxibxajjjijij线性规划问题通常采用单纯形法来求解。例2(工厂设址问题)要在m个不同地点计划修建m个规模不完全相同的工厂，他们的生产能力分别是maaa,,21（为简便起见，假设生产同一种产品），第i个工厂的建设费用mifi,,2,1,。又有n个零售商店销售这种产品，对这种产品的需求量分别为nbbb,,21，从第i个工厂运送一个单位产品到第j个零售商店的运费为cij。试决定应修建哪个工厂，使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。（混合整数规划问题）数学模型：设第i个工厂运往第j个零售商店的产品数量为xij（i=1，…，m；j=1，…，n），且miiyi,,1,,0,1否则个工厂如果修建第3目标函数：min11minjijijiixcyfz约束条件：njmixmiynjbxmiyaxijimijijnjiiij,,1;,,1,0,,1,10,,1,,,1,11或整数规划问题通常可用分枝定界法或割平面法来求解。例3(投资计划问题)假设某一个生产部门在一段时间内可用于投资的总金额为a亿元，可供选择的项目总共有n个，分别记为1，2，…n。并且已知对第j个项目的投资总数为ja亿元，而收益额总数为jc亿元。问如何使用资金a亿元，才能使单位投资获得的收益最大。（非线性规划问题）数学模型：设njjxj,,1,,0,1否则个项目投资对第目标函数：max11njjjnjjjxaxcz约束条件：njxaxajnjjj,,1,101或非线性规划问题的求解方法很多，是本课的重点。动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman最优性原理”，例如：资源分配问题，生产与存储问题。例4(多参数曲线拟合问题)已知热敏电阻R依赖于温度T的函数关系为4321xTxexR（*）其中，321,,xxx是待定的参数，通过实验测得T和R的15组数据列表如下，如何确定参数321,,xxx？i12345678℃/iT5055606570758085kRi/34.7828.6123.6519.6316.3713.7211.549.744i9101112131415℃/iT9095100105110115120kRi/8.2617.036.0055.1474.4273.823.307建立数学模型：测量点),(iiRT与曲线)(TR对应的点产生“偏差”，即21511][32ixTxiiexRS得如下无约束最优化问题：21511][)(min32ixTxiiexRxf通常采用最小二乘法。§1.2最优化问题的数学模型一、最优化问题的数学模型1.定义1：设向量T21T21],,,[,],,,[mmbbbaaa.若),,2,1(mibaii，则记或；若),,2,1(mibaii，则记或。52．一般模型：))(max)((min),,,()(opt21xfxfxxxfxfn或，（1）s.t.)3(,,1,0)()2(,,1,0)(ljxhmixSji其中，T21],,,[nxxxx；)(xf，)(xSi，)(xhj是关于变量nxxx,,,21的实值连续函数，一般可假定它们具有二阶连续偏导数。3．向量模型：))(max)((min)(optxfxfxf或，（1）s.t.)3(,,1,0)()2(,,1,0)(ljxhmixS其中，T21],,,[nxxxx，)(xf称为目标函数；T1)(,),()(xSxSxSm，T1)(,),()(xhxhxhl。)(xSi，)(xhj称为约束函数；满足约束条件（2），（3）的点称为容许解或容许点（或可行解）；容许解的全体称为容许域（或可行域），记为R；满足（1）的容许点称为最优点或最优解（或极小（大）点），记为*x；)(xf称为最优值；不带约束的问题称为无约束问题，带约束的问题称为约束问题；若目标函数)(xf，约束函数)(xSi，)(xhj都是线性函数，则称为线性规划；若其中存在非线性函数，则称为非线性规划；若变量只取整数，称为整数规划；若变量只取0，1，称为0—1规划。注：因0)(xh0)(xh，0)(-xh，则最优化问题一般可写成60)(..)(optxStsxf二、最优化问题的分类动态规划非线性规划线性规划约束问题维问题一维问题无约束问题静态规划最优化问题n§1.3二维问题的图解法例1.32max21xxz0,16482..21121xxxxxts解：1.由全部约束条件作图，求出可行域R：凸多边形OABC2.作出一条目标函数的等值线：设63221xx，作该直线即为一条目标函数的等值线，并确定在可行域内，这条等值线向哪个方向平移可使z值增大。3.平移目标函数等值线，做图求解最优点，再算出最优值。顶点)2,4(B是最优点，即最优解Tx]24[，最优值14z。分析：线性规划问题解的几种情况（1）有唯一最优解（上例）；（2）有无穷多组最优解：目标函数改为42max21xxz（3）无可行解：增加约束52x，则R。（4）无有限最优解（无界解）：例max21xxz70,2-42..212121xxxxxxts结论：（1）线性规划问题的可行域为凸集，特殊情况下为无界域或空集。（2）线性规划问题若有最优解，一定可在其可行域的顶点上得到。例2.1)-()2min(2221xx0,0505..21212221xxxxxxxts解：目标函数等值线：11)-()2(2221xxC为最优点0505212221xxxxx，得Tx]14[定义2：在三维及三维以上的空间中，使目标函数取同一常数的点集是常数rrxfx,)(称为等值面。§1.4预备知识（一）线性代数一、n维向量空间nR1.向量的内积：设T21T21],,,[,],,,[nnyyyyxxxx，则内积为niiinnTyxyxyxyxyx122112.向量的范数（或长度或模）：设nxR，若实数x具有以下性质：（1）,0x当且仅当0x时0x；8（2）R,xx；（3）nyxyxyxR,,.则称x为nR上的向量的范数，简记为。规定了向量范数的线性空间nR称为线性赋范空间,记为},{Rn.3.常见的向量范数向量的pL范数：pnipipxx11，p1三个重要的向量范数：1x，2x，x注：若无特殊说明，本书中的指的是2x。4.yx,间的距离：yx5.x与y正交：0yxT若非零向量组)1(x，…，)(kx的向量两两正交，称它们是正交向量组。6.标准正交基：)1(e，…，)(ne是n个正交的单位向量，即jijieejiT,0,1)()(二、特征值和特征向量定义：设A为n阶方阵，存在数和非零向量x，使xAx，则称为矩阵A的特征值，非零向量x为矩阵A属于特征值的特征向量。三、正定矩阵定义：设A为n阶实对称方阵，若对任意非零向量x，均有0AxxT，则称AxxT为正定二次型，A为正定矩阵，记0A。；若0AxxT，半正定二次型，A为半正定矩阵，记0A。9类似有负定（半负定）二次型，负定（半负定）矩阵的概念。性质：实对称方阵A为正定矩阵（负）A的特征值均为正（负）A的各阶顺序主子式均为正（奇数阶为负，偶数阶为正）实对称方阵A为半正定矩阵A的特征值均非负A的各阶顺序主子式均为非负（二）数学分析一、梯度和海色（Hesse）矩阵1.多元函数的可微性可微定义：设1RR:nDf，Dx0，若存在n维向量l，对npR0，总有0)()(limT000pplxfpxfp（1）则称函数)(xf在点0x处可微。式（1）等价于pplxfpxf0)()(T00（2）其中，p0是p的高阶无穷小。定理1：（可微的必要条件）若函数)(xf在点0x处可微，则)(xf在该点关于各个变量的偏导数存在，且T02010)(,,)(,)(nxxfxxfxxfl2.梯度（1）概念梯度：令10T21)(,,)(,)()(nxxfxxfxxfxf则称)(xf为n元函数)(xf在x处的梯度（或记为)(gradxf）。又称为)(xf关于x的一阶导数。注：式（2）等价于ppxfxfpxf0)()()(T000（3）等值面：在三维和三维以上的空间中，使目标函数取同一数值的点集},)({Rrrxfx称为等值面（曲面）。方向导数：设1RR:nf在点0x处可微，向量npR0，e是p方向上的单位向量，则极限txftexft)()(lim000称为函数)(xf在点0x处沿p方向的方向导数，记作pxf)(0。方向导数的几何解释：方向导数pxf)(0表示函数)(xf在点0x处沿方向的p的变化率。函数的下降（上升）方向：设1RR:nf是连续函数，点nxR0，npR0为一方向，若存在0，对于),0(t，都有)()(00xftpxf（)()(00xftpxf）则称p方向是函数)(xf在点0x处的下降（上升）方向；结论1：若方向导数0)(0pxf，则方向p是)(xf在点0x处的下降方向；若方向导数0)(0pxf，则方向p是)(xf在点0x处的上升方向；11（2）性质【性质1】：梯度)(0xf为等值面)()(0xfxf在点0x处的切平面的法矢（向）量。【性质2】：梯度方向是函数具有最大变化率的方向。定理2：设1RR:nf在点0x处可微，则方向导数cos)()()(0T00xfexfpxf其中，e是p方向上的单位向量，为梯度与p的夹角。结论2：1）与梯度)(0xf方向成锐角