数值计算方法第八章

《数值计算方法第八章》由会员分享，可在线阅读，更多相关《数值计算方法第八章（13页珍藏版）》请在装配图网上搜索。

1、第八章最优化问题最优化分支：线性规划，整数规划，几何规划，非线性规划，动 态规划。 又称规划论。应用最优化方法解决问题时一般有以下几个特点 ：1. 实用性强2. 采用定量分析的科学手段3 计算量大，必须借助于计算机4.理论涉及面广应用领域：工业，农业，交通运输，能源开发，经济计划，企业 管理，军 事作战。 8.1 最优化问题实例最优化问题：追求最优目标的数学问题。经典最优化理论：无约束极值问题：opt f(X，X2, ,xn)(min f(Xj,X2, ,Xn)或 max f(X,x2A ,Xn)其中，f(Xi,X2/，Xn)是定义在n维空间上的可微函数。解法(求极值点)：求驻点，即满足fx

2、(Xi， ,Xn) = 0xi in) =HX ,Xn) = 0f；(Xi,，Xn) = 0并验证这些驻点是否极值点（2） 约束极值问题Opt f(Xi,X2, ,Xn)s.t. hj(Xi,X2, ,Xn) = 0, j = 1,2,1(1 n)解法：采用 Lagrange 乘子法，即将问题转化为求 Lagrange 函数L（X X；1,的无约束极值问题l论心必,入）X）j=1近代最优化理论的实例：例1 （生产计划问题）设某工厂有3种资源B1, B2, Bs,数量各为b” b2, bs,要生产10种产品Aj,，Aio。每生产一个单位的Aj需要消耗Bi的量为 根据合同规定，产品Aj的量不少于q

3、,再设Aj的单价 为q。问如何安排生产计划，才能既完成合同，又使总 收入最多？（线性规划问 题）数学模型：设Aj的计划产量为人,z为总收入10目标函数： maxz-y CjXj jm1olz am 玄 bj =1,2,3约束条件：冃XA dj, j = 1,2，,10线性规划问题通常采用单纯形法来求解。例 2 （工厂设址问题）要在 m 个不同地点计划修建 m 个规模不完 全相同 的工厂，他们的生产能力分别是6，a2，am （为简便起见，假设生产同一种 产品），第i个工厂的建设费用fj =1,2，m。乂有n个零售商店销售这种产品，对这种产品的需求量分别为b15bA ,bn,从第i个工厂运送一个单

4、位产品到第j个零售商店的运费为q。试决定应修建哪个工厂，使得既满足零售商店的需求，又使 建设工厂和运输的总费用最小。（混合整数规划问题）数学模型： 设第 i 个工厂运往第 j 个零售商店的产品数量为 xj（i=1，m; j=1，n）,且如果修建第 i 个工厂0,yi=否则,i = 1, ,m目标函数:m min z 八fiVnCij Xijijiji =11 Xjj 岂 ay., i = 1,1 m约束条件:-Xj _ bj，j = I,m,m; j = 1, nA 0 或 1, i = 1,1 - 0, i = 1,整数规划问题通常可用分枝定界法或割平面法来求解。例 3 （投资计划问题） 假

5、设某一个生产部门在一段时间内可用于投资的总金额为a亿元，可供选择的项目总共有n个，分别记为1, 2,n。并 且已知对第 j 个项目的投资总数为 aj 亿元，而收益额总数 为 Cj 亿元。问如何使 用资金 a 亿元，才能使单位投资获得的收益最大。（非线性规划问题）1, 对第 j 个项目投资数学模型：设X.十否则，j，n0、 cx目标函数：j jj max迟 aj xjjjj =1n约束条件：2- ajXj 乞 aXj = 0 或 1, j = 1,，n非线性规划问题的求解方法很多，是本课的重点。动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman最优性原理”，例如：资源分

6、配问题，生产与存储问题。例 4 （多参数曲线拟合问题）已知热敏电阻 R 依赖于温度 T 的函数关系为R = x1eT X3)其中，Xi5x2,X3是待定的参数，通过实验测得T和R的15组数据列 表如下，如何确定参数 X1,X2,X3？i12345678T/C5055606570758085R/炉34.7828.6123.6519.6316.3713.7211.549.744i9101112131415T./C9095100105110115120R/炉8.2617.036.0055.1474.4273.823.307建立数学模型：测量点(Tj,RJ与曲线R(T)对应的点产生“偏差”S =E R

7、 乂点址2得如下无约束最优化问题:minf(x) =Z5R NeTi4JX32i=1通常采用最小二乘法。 8.2 最优化问题的数学模型一、最优化问题的数学模型1.定义1：设向量，二可包厂，amT叮db，bmT.若 a-A bi(i =1,2/ ,m)，则记或一；若a中卫=1,2,m)，则记或：2. 一般模型：opt f (x) = f (xX2, , Xn) (minf(x)或 maxf(x),(1)Si(x)- 0, i =1, ,m(2)s t彳s.t.hj(x) =0, j =1, ,1其中，x =各入2，xJt ; f(x),Si(x),hj(x)是关于变量X.X/，Xn的实值连续函数

8、，一般可假定它们具有二阶连续偏导数。3.向量模型:(1)opt f (x) (minf (x)或 maxf (x),S(x)色 0, i = 1,.，m(2)s tjh(x) = 0j1,. ，1其中，x二XjX?厂，XnT , f(x)称为目标函数；S(x)二 S(x),Sj x)T,h(x)二 h/x), h(x)斤Si(x), hj(x)称为约束函数；满足约束条件(2), ( 3)的点称为容许解或容许点(或可行解)； 容许解的全体称为容许域(或可行域)，记为R；满足(1 )的容许点称为最优点或最优解(或极小(大)点)，记为x ； f (x )称 为最优值；不带约束的问题称为无约束问题，带

9、约束的问题称为约束问题；若目标函数f(x)，约束函数S(x), hj(x)都是线性函数，则称为线性规 划；若其中存在非线性函数，则称为非线性规划；若变量只取整数，称为整数规划；若变量只取0 ，1，称为0 1规划。注：因h(x)=0= h(x)_0，-h(x) 0,则最优化问题一般可写成opt f (x)-S.t. S(x) z 0最优化问题的分类最优化问题静态规划动态规划|无约束问题I，一维问题n 维问题约束问题线性规划非线性规划 8.3 二维问题的图解法例 1. maxz 二 2x1 3x2片 + 2x 兰 82s.t. 4x6 X，xA 0i解：1由全部约束条件作图，求出可行域R：凸多边形

10、OABC 2作出一条目 标函数的等值线：设2xj3xA 6,作该直线即为一条目标函数的等值线，并确定 在可行域内，这条等值线向哪个方 向平移可使 z 值增大。3.平移目标函数等值线，做图求解最优点，再算出最优值。顶点B（4,2） 是最优点，即最优解X二4 2 T,最优值z = 14。分析：线性规划问题解的几种情况（1 ） 有唯一最优解（上例）；（2）有无穷多组最优解：目标函数改为 maxz=2x4x2（3）无可行解：增加约束 X2- 5，则 R 八。（4）无有限最优解（无界解）：例 maxz 二 xX2& - 2x2 乞 4I2s.t. - x1 x2 - 2X, xA 0结论：（1）线性规划问题的可行域为凸集，特殊情况下为无界域 或空集2）线性规划问题若有最优解，一定可在其可行域的顶点上 得到。x1 x； - 5x2 = 0C 为最优点x1 x2 - 5 = 0例 2.min(X - 2)2 (x2 -1)2卜+心=0，得 x 叮 4 1TSt J 捲 + x25兰0为，x2兰0解：目标函数等值线：（石-2）2+ （x2 -1）2 = 1定义2：在三维及三维以上的空间中，使目标函数取同一常数的点集x f（x） = r, r是常数称为等值面。