最优化问题数学模型

最优化模型一、最优化模型的概述二、最优化模型的分类三、最优化模型的建立及求解四、最优化模型的评价分析数学家对最优化问题的研究已经有很多年的历史。以前解决最优化问题的数学方法只限于古典求导方法和变分法，拉格朗日（Lagrange）乘数法解决等式约束下的条件极值问题。计算机技术的出现，使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。一、最优化模型的概述解决最优生产计划、最优设计、最优策略….运用最优化方法解决最优化问题的一般方法步骤如下：①前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。②定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。③针对建立的模型，选择合适的求解方法或数学软件。④编写程序，利用计算机求解。⑤对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。最优化模型分类方法有很多，可按变量、约束条件、目标函数个数、目标函数和约束条件的是否线性是否依赖时间等分类。根据目标函数，约束条件的特点将最优化模型包含的主要内容大致如下划分：线性规划整数规划非线性规划多目标规划动态规划对策论二、最优化模型的分类最优化模型的求解方法分类图克定理库恩极值原理有约束变分法微分法无约束解析法-.1....5.4网络优化方法多目标优化法随机搜索法单纯形法方向加速法步长加速法坐标轮换法多维搜索法插值法黄金分割法裴波那契法一维搜索法数值算法.2复形法法法化有为无梯度法梯度投影法可行方向法有约束梯度法变尺度法共轭梯度法拟牛顿法最速下降法无约束梯度法梯度算法SWIFTSUMT.3最优化数学模型形式min()xfx..()0,1,2,...,()0,1,2,...,iistgximhxin其中，极大值问题可以转化为极小值问题来进行求解。如求：max()xfx可以转化为：min()xfx三、最优化模型的建立目标：求函数极值或最值，求取得极值时变量的取值。1.线性规划问题：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示12kg40原材料B16kg04原材料A8台时21设备III该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？解：该工厂生产产品Ix1件，生产产品IIx2件，我们可建立如下数学模型：2132maxxxz0,12416482212121xxxxxxs.t..2,41421xxz最优化问题中的所有变量均为整数时，这类问题称为整数规划问题。整数规划可分为线性整数规划和非线性整数规划，以及混合整数规划等。如果决策变量的取值要么为0，要么为1，则这样的规划问题称为0－1规划。2.整数规划问题：某班级准备从5名游泳队员中选择4人组成接力队，参加学校的4*100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如表2-1，问应如何选拔队员组成接力队？队员甲已丙丁戊蝶泳仰泳蛙泳自由泳66.8秒57.2787067.475.6668758.666.45367.874.27184.659.469.657.283.862.4表2-1问题分析：记甲、乙、丙、丁、戊分别为i=1,2,3,4,5;记泳姿j=1,2,3,4.记队员i的第j种泳姿的百米最好成绩为c_ij(s),则表2-1可以表示成表2-2.c_iji=1i=2i=3i=4i=5j=1j=2j=3j=466.857.2787067.475.6668758.666.45367.874.27184.659.469.657.283.862.4表2-2决策变量：引入0-1变量，若选择队员i参加泳姿j的比赛,记，，否则记。目标函数：当队员i入选泳姿j时，表示该队员的成绩，否则。于是接力队的成绩可表示为约束条件：根据接力队要求，满足约束条件a.每人最多只能入选4种泳姿之一，即b.每种泳姿必须有1人而且只能有一人入选，即ijx0ijx1ijx.151iijx.141jijxijx.4151jiijijxcf0ijijxcijijxc综上所述，这个问题的优化模型可写作：}.1,0{ijx.4,3,2,1,151jxiij.5,4,3,2,1,1..41ixtsjij4151minjiijijxcf非线性规划问题的一般数学模型：其中，，为目标函数，为约束函数，这些函数中至少有一个是非线性函数。min()..()0,1,2,,,()0,1,2,,.ijfxstgximhxjlnEx)(xf)(),(xhxgji3.非线性规划应用实例：供应与选址某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出．目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t．假设从料场到工地之间均有直线道路相连．（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小．（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？工地位置（a，b）及水泥日用量d123456a1.258.750.55.7537.25b1.250.754.7556.57.25d3547611建立模型记工地的位置为(ai，bi)，水泥日用量为di，i=1,…,6;料场位置为(xj，yj)，日储量为ej，j=1,2；料场j向工地i的运送量为Xij．目标函数为：216122)()(minjiijijijbyaxXf约束条件为：2,1,6,,2,1,6121jeXidXjiijijij当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj．事实上，客观世界中的大多问题都是非线性的，给予线性化处理是近似的，是在作了科学的假设和简化后得到的.另一方面，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型.由于非线性规划问题在理论分析和计算上通常是很困难的，也不能像线性规划那样给出简洁的结果形式和全面透彻的结论.所以，在数学建模时，要进行认真的分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，若线性近似误差较大时，则考虑用非线性规划.在约1万米的高空的某边长为160km的正方形区域内，经常有若干架飞机作水平飞行，区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，计算机记录其数据后，要立即计算并判断是否会发生碰撞。若会发生碰撞，则应计算如何调整各架飞机（包括新进入的飞机）飞行的方向角，以避免碰撞，且使飞机的调整的幅度尽量小，例11995年全国数学建模A题：飞行管理问题例题讲解该题比较有意思的一句话是：“使调整弧度最小”开放性的一句话，没有限制得很死，较灵活，给参赛者的创新空间比较大一些，使得构建模型的目标函数表现形式很多，再加上模型求解方法（算法）的多样性，从而可以呈现出五花八门的论文。•不碰撞的标准为任意两架飞机的距离大于8km;假设条件：30•飞机飞行的方向角调整幅度不应超过；•（因飞机飞行的速度变化不大）所有飞机的飞行速度v均为800km/h;有时需要通过查阅文献、资料给出合理假设注：•进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在60km以上；•最多需考虑六架飞机；•不必考虑飞机离开此区域后的状况。根据当年竞赛题目给出的数据，可以验证新进入的飞机与区域内的飞机的距离超过60公里。根据当年竞赛题目给出的数据，可以验证区域内的飞机不超过架(包括新进入的)。•个人的想法不同，队友之间争执不下的情况下，若时间允许，都可一一写到论文中去，建立的模型一、模型二……；或者经讨论后，选择一个认为更合理的。•现在看来，无论是构建模型，还是计算，都不太难。•本例题未给出数据，将重点放在如何构建模型上解：(1)不考虑飞机的尺寸，用点代表飞机；(2)已在区域内的5架飞机按给定的方向角作直线飞行，则必不会碰撞，也不会发生意外；(应该根据题目中所给出的数据简单的验证一下)(3)飞机调整方向角的过程可在瞬间完成,(不计调整方向所花费的时间)。为解决该问题，补充假设：变量、参数的符号假设（为了建模）00,126)iixyii——第架机的初始位置,(，，0126)iii——第架机的整前的方向角,(，，126)iii——第架机的整后的方向角,(，，在区域内飞行iiTi——第架机按方向角飞时间（可以根据数据算出来）00002202,mincoscossinsinijijijijijtTijijdxxvtyyvt根据题目条件，需计算第架飞机之间的最短距离,ij为此，我们可以给出原问题的模型如下：00612min,60,,1,2,,6,,..,1,2,,6.6iiiijijiidijijsti思考：是否还有其他的表达形式？非线性规划模型分别从目标函数和约束条件角度思考首先思考一下目标函数是否有其它的表达？061miniii同学们首先想到的可能是Oh,Sorry!有正有负抵消061miniii0621miniii最小一乘法最小二乘法因最小一乘法带绝对值，不好计算，以上两式，比较而言，后者较好。为了避免抵消or其次讨论一下约束条件是否有其它表达？若考虑区域内不发生碰撞（若时间允许，也可以考虑出了区域的情况，另外建模）、错层飞行（飞高或者飞低避免碰撞），进行模型的进一步改进，重点应放在解决问题的方法上。如02,1,2,,6,6,60,,1,2,,6,iiijijidijij无论选择哪一种表达，怎样考虑约束条件，目标函数都不可能是线性的。现在看来，那年的题目建模只是在条件的考虑上和建模中目标函数的表达方面较难一点。是一个带不等式约束的非线性规划问题。而且不可能转化成线性的形式。非线性规划模型按约束条件可分为以下三类：⑴无约束非线性规划模型：⑵等式约束非线性规划模型：min()nfxxRmin()..()0,1,2,jfxsthxjr⑶不等式约束非线性规划模型：min()..()0,1,2,ifxstgxim如数据拟合的最小二乘问题就是一个无约束极值问题。其思想是：观察点（实验数据点）到曲线的距离的平方之和最小⑴无约束非线性规划模型：理论上无约束极值问题可化成求解0gradfx即解一个n元方程组，且往往是非线性方程组。而一般说来，非线性方程组的求解并不比求无约束极值容易。求解无约束极值问题的基本方法：迭代法从一个给定的初始可行点出发，依次0x产生一个可行点列12,,,,,kxxx的一个极小值点,恰好是使得某个kxfx基本思路：或kx收敛于x,称具有这种性质的算法是收敛的.由kx迭代到1kx时,1,kkkkxxp记即1,kkkkxxpkp其中向量为搜索方向,实数k称为步长,确定以后,,kkpkx由可唯一地确定1,kx从0x出发就可确定点列.kx迭代的方法很多,各种迭代法的区别在于选取,kkp的方式不同,而kp尤为关键.一般要求kfx递减,具有这种性质的算法叫做下降算法.若已得,kx下降得最多,并确定了kx的可行下降方向,kp上选取步长则在射线0kkxp,k使,kkkkfxpfx且使kfx00minmin,kkkkkfxpfxp即求求k的过程称为一维搜索.1.下降算法于是