数值计算方法第八章

1第八章最优化问题最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。应用最优化方法解决问题时一般有以下几个特点：1.实用性强2.采用定量分析的科学手段3.计算量大，必须借助于计算机4.理论涉及面广应用领域：工业，农业，交通运输，能源开发，经济计划，企业管理，军事作战……。§8.1最优化问题实例最优化问题：追求最优目标的数学问题。经典最优化理论：（1）无约束极值问题：),,,(opt21nxxxf（),,,(min21nxxxf或),,,(max21nxxxf）其中，),,,(21nxxxf是定义在n维空间上的可微函数。解法（求极值点）：求驻点，即满足0),,(0),,(0),,(11121nxnxnxxxfxxfxxfn并验证这些驻点是否极值点。2（2）约束极值问题：),,,(opt21nxxxfs.t.)(,,2,1,0),,,(21nlljxxxhnj解法：采用Lagrange乘子法，即将问题转化为求Lagrange函数),,(),,,(),,;,,,(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个零售商店销售这种产品，对这种产品的需求量分别为3nbbb,,21，从第i个工厂运送一个单位产品到第j个零售商店的运费为cij。试决定应修建哪个工厂，使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。（混合整数规划问题）数学模型：设第i个工厂运往第j个零售商店的产品数量为xij（i=1，…，m；j=1，…，n），且miiyi,,1,,0,1否则个工厂如果修建第目标函数：min11minjijijiixcyfz约束条件：njmixmiynjbxmiyaxijimijijnjiiij,,1;,,1,0,,1,10,,1,,,1,11或整数规划问题通常可用分枝定界法或割平面法来求解。例3(投资计划问题)假设某一个生产部门在一段时间内可用于投资的总金额为a亿元，可供选择的项目总共有n个，分别记为1，2，…n。并且已知对第j个项目的投资总数为ja亿元，而收益额总数为jc亿元。问如何使用资金a亿元，才能使单位投资获得的收益最大。（非线性规划问题）4数学模型：设njjxj,,1,,0,1否则个项目投资对第目标函数：max11njjjnjjjxaxcz约束条件：njxaxajnjjj,,1,101或非线性规划问题的求解方法很多，是本课的重点。动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman最优性原理”，例如：资源分配问题，生产与存储问题。例4(多参数曲线拟合问题)已知热敏电阻R依赖于温度T的函数关系为321xTxexR（*）其中，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.3075建立数学模型：测量点),(iiRT与曲线)(TR对应的点产生“偏差”，即21511][32ixTxiiexRS得如下无约束最优化问题：21511][)(min32ixTxiiexRxf通常采用最小二乘法。§8.2最优化问题的数学模型一、最优化问题的数学模型1.定义1：设向量T21T21],,,[,],,,[mmbbbaaa.若),,2,1(mibaii，则记或；若),,2,1(mibaii，则记或。2．一般模型：))(max)((min),,,()(opt21xfxfxxxfxfn或，（1）s.t.)3(,,1,0)()2(,,1,0)(ljxhmixSji其中，T21],,,[nxxxx；)(xf，)(xSi，)(xhj是关于变量nxxx,,,21的实值连续函数，一般可假定它们具有二阶连续偏导数。3．向量模型：6))(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，则最优化问题一般可写成0)(..)(optxStsxf二、最优化问题的分类7动态规划非线性规划线性规划约束问题维问题一维问题无约束问题静态规划最优化问题n§8.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80,2-42..212121xxxxxxts结论：（1）线性规划问题的可行域为凸集，特殊情况下为无界域或空集。（2）线性规划问题若有最优解，一定可在其可行域的顶点上得到。例2.1)-()2min(2221xx0,0505..21212221xxxxxxxts解：目标函数等值线：11)-()2(2221xxC为最优点0505212221xxxxx，得Tx]14[定义2：在三维及三维以上的空间中，使目标函数取同一常数的点集是常数rrxfx,)(称为等值面。