最优化问题数学模型精选PPT.ppt

《最优化问题数学模型精选PPT.ppt》由会员分享，可在线阅读，更多相关《最优化问题数学模型精选PPT.ppt（117页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关于最优化问题数学模型第1页，讲稿共117张，创作于星期二 数学家对最优化问题的研究已经有很多年的历史。数学家对最优化问题的研究已经有很多年的历史。以前解决最优化问题的数学方法只限于古典求导方以前解决最优化问题的数学方法只限于古典求导方法和变分法，拉格朗日（法和变分法，拉格朗日（LagrangeLagrange）乘数法解决等式约）乘数法解决等式约束下的条件极值问题。束下的条件极值问题。计算机技术的出现，使得数学家研究出了许多最优计算机技术的出现，使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。化方法和算法用以解决以前难以解决的问题。一、最优化模型的概述一、最优化模型的概述 解

2、决最优生产计划、最优设计、最优策略解决最优生产计划、最优设计、最优策略.第2页，讲稿共117张，创作于星期二 运用最优化方法解决最优化问题的一般方法步骤运用最优化方法解决最优化问题的一般方法步骤如下：如下：前期分析：分析问题，找出要解决的目标，约束条件，前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。并确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目标函数和约束定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。条件。针对建立的模型，选择合适的求解方法或数学软件。针对建立的模型，选择合适的求解方法或数学软件。编写程序，利用计算机求解。编写程序，利用计算机

3、求解。对结果进行分析，讨论诸如：结果的合理性、正确性，算法对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。的收敛性，模型的适用性和通用性，算法效率与误差等。第3页，讲稿共117张，创作于星期二 最最优优化化模模型型分分类类方方法法有有很很多多，可可按按变变量量、约约束束条条件件、目目标标函函数数个个数数、目目标标函函数数和和约约束束条条件件的的是是否否线性是否依赖时间等分类。线性是否依赖时间等分类。根根据据目目标标函函数数，约约束束条条件件的的特特点点将将最最优优化化模模型型包包含含的的主要内容大致如下划分：主要内容大致如下划分：线性规划线

4、性规划 整数规划整数规划 非线性规划非线性规划 多目标规划多目标规划 动态动态规划规划 对策论对策论二、最优化模型的分类二、最优化模型的分类第4页，讲稿共117张，创作于星期二最优化模型的求解方法分类最优化模型的求解方法分类第5页，讲稿共117张，创作于星期二最优化数学模型形式最优化数学模型形式 其中，极大值问题可以转化为极小值问题来进行求其中，极大值问题可以转化为极小值问题来进行求解。如求：解。如求：可以转化为：可以转化为：三、最优化模型的建立三、最优化模型的建立目标：求函数极值或最值，求取得极值时变量的取值。目标：求函数极值或最值，求取得极值时变量的取值。第6页，讲稿共117张，创作于星期

5、二1.1.线性规划线性规划问题问题：某工厂在计划期内要安排生产：某工厂在计划期内要安排生产I、II两种产品，已知生产两种产品，已知生产单位产品所需的设备台时及单位产品所需的设备台时及A、B两种原材料的消耗，如下表两种原材料的消耗，如下表所示所示 12kg40原材料原材料B16kg04原材料原材料A8台时台时21设备设备III该工厂每生产一件产品该工厂每生产一件产品I可获利可获利2元，每生产一件产品元，每生产一件产品II可获可获利利3元。问应如何安排计划使该工厂获利最多？元。问应如何安排计划使该工厂获利最多？第7页，讲稿共117张，创作于星期二解解：该工厂生产产品：该工厂生产产品I x1件，生产

6、产品件，生产产品II x2件，我件，我们可建立如下数学模型：们可建立如下数学模型：s.t.第8页，讲稿共117张，创作于星期二 最优化问题中的所有变量均为整数时，这类问题称最优化问题中的所有变量均为整数时，这类问题称为整数规划问题。为整数规划问题。整数规划可分为线性整数规划和非线性整数规划整数规划可分为线性整数规划和非线性整数规划 ，以及混合整数规划等。，以及混合整数规划等。如果决策变量的取值要么为如果决策变量的取值要么为0 0，要么为，要么为1 1，则这，则这样的规划问题称为样的规划问题称为0 01 1规划。规划。2.2.整数规划整数规划第9页，讲稿共117张，创作于星期二问题：问题：某班级

7、准备从某班级准备从5名名游泳队员中选择游泳队员中选择4人人组成接力队，参加学校组成接力队，参加学校的的4*100m混合泳接力比赛。混合泳接力比赛。5名队员名队员4种泳姿种泳姿的百米平均成绩如的百米平均成绩如表表2-1，问应如何选拔队员组成接力队？，问应如何选拔队员组成接力队？队员队员甲甲已已丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳66.866.8秒秒57.257.27878707067.467.475.675.66666878758.658.666.466.4535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.8

8、62.462.4表表2-12-1第10页，讲稿共117张，创作于星期二问题分析：问题分析：记甲、乙、丙、丁、戊分别为记甲、乙、丙、丁、戊分别为i i=1,2,3,4,5;=1,2,3,4,5;记泳记泳姿姿j j=1,2,3,4.=1,2,3,4.记队员记队员 i i 的第的第 j j 种泳姿的百米最好成绩为种泳姿的百米最好成绩为c_c_ijij(s),(s),则表则表2-12-1可以表示成表可以表示成表2-2.2-2.c_iji=1i=2i=3i=4i=5j=1j=2j=3j=466.866.857.257.27878707067.467.475.675.66666878758.658.666

9、.466.4535367.867.874.274.2717184.684.659.459.469.669.657.257.283.883.862.462.4表表2-22-2第11页，讲稿共117张，创作于星期二 决策变量：决策变量：引入引入0-1变量变量 ，若选择队员，若选择队员i参加泳姿参加泳姿j的比赛的比赛,记，记，否则记，否则记 。目标函数：目标函数：当队员当队员i入选泳姿入选泳姿j时，时，表示该队员的成绩，表示该队员的成绩，否则否则 。于是接力队的成绩可表示为。于是接力队的成绩可表示为 约束条件：约束条件：根据接力队要求，根据接力队要求，满足约束条件满足约束条件a.每人最多只能入选每人

10、最多只能入选4种泳姿之一，即种泳姿之一，即b.每种泳姿必须有每种泳姿必须有1人而且只能有一人入选，即人而且只能有一人入选，即第12页，讲稿共117张，创作于星期二 综上所述，这个问题的优化模型可写作：综上所述，这个问题的优化模型可写作：第13页，讲稿共117张，创作于星期二非线性规划问题的一般数学模型：非线性规划问题的一般数学模型：其中，其中，为目标函数，为目标函数，为约束函数，这些函数中至少有一个为约束函数，这些函数中至少有一个是非线性函数。是非线性函数。3.3.非线性规划非线性规划第14页，讲稿共117张，创作于星期二应用实例：应用实例：供应与选址供应与选址 某公司有某公司有6个建筑工地要

11、开工，每个工地的位置（用平面坐标系个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：表示，距离单位：km）及水泥日用量）及水泥日用量d(t)由下表给出目前有两个临时由下表给出目前有两个临时料场位于料场位于A(5,1)，B(2,7)，日储量，日储量各有各有20t假设从料场到工地之间均有假设从料场到工地之间均有直线道路相连直线道路相连 （1）试制定每天的供应计划，即从）试制定每天的供应计划，即从A，B两料场两料场分别向各工地运送多少水泥，分别向各工地运送多少水泥，可使总的可使总的吨千米数最小吨千米数最小（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，）为了进一步

12、减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为日储量各为20t，问应建在何处，节省的吨千米数有多大？，问应建在何处，节省的吨千米数有多大？第15页，讲稿共117张，创作于星期二建立模型建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；料场；料场j向工地向工地i的运送量为的运送量为Xij当用临时料场时决策变量为：当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：当不用临时料场时决策变量为：Xij，xj，yj第16页，讲稿共117张，创作于星期二 事实上

13、，客观世界中的大多问题都是非线性的，给予线性事实上，客观世界中的大多问题都是非线性的，给予线性化处理是近似的，是在作了科学的假设和简化后得到的化处理是近似的，是在作了科学的假设和简化后得到的.另一另一方面，有一些是不能进行线性化处理的，否则将严重影响模型方面，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型对实际问题近似的可依赖型.由于非线性规划问题在理论分析和计算上通常是很困难的，由于非线性规划问题在理论分析和计算上通常是很困难的，也不能像线性规划那样给出简洁的结果形式和全面透彻的结论也不能像线性规划那样给出简洁的结果形式和全面透彻的结论.所以，在数学建模时，要进行认

14、真的分析，对实际问题进行合所以，在数学建模时，要进行认真的分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，理的假设、简化，首先考虑用线性规划模型，若线性近似误差较若线性近似误差较大时大时，则考虑用非线性规划，则考虑用非线性规划.第17页，讲稿共117张，创作于星期二 在约在约1万米的高空的某边长为万米的高空的某边长为160km的正方形的正方形区域内，经常有若干架飞机作水平飞行，区域内每架区域内，经常有若干架飞机作水平飞行，区域内每架飞机的位置和速度向量均由计算机记录其数据，以便飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域进行飞行管理

15、。当一架欲进入该区域的飞机到达区域边缘时，计算机记录其数据后，要立即计算并判断是边缘时，计算机记录其数据后，要立即计算并判断是否会发生碰撞。若会发生碰撞，则应计算否会发生碰撞。若会发生碰撞，则应计算如何调整如何调整各架飞机（包括新进入的飞机）飞行的方向角，各架飞机（包括新进入的飞机）飞行的方向角，以避免碰撞，且使飞机的调整的幅度尽量小，以避免碰撞，且使飞机的调整的幅度尽量小，例例1 1995年全国数学建模年全国数学建模A题：飞行管理问题题：飞行管理问题例题讲解例题讲解第18页，讲稿共117张，创作于星期二该题比较有意思的一句话是：该题比较有意思的一句话是：“使调整弧度最小使调整弧度最小”开放性

16、的一句话，没有限制得很死，较灵活，开放性的一句话，没有限制得很死，较灵活，给参赛者的创新空间比较大一些，使得构建模型给参赛者的创新空间比较大一些，使得构建模型的目标函数表现形式很多，再加上模型求解方法（算法）的目标函数表现形式很多，再加上模型求解方法（算法）的多样性，从而可以呈现出五花八门的论文。的多样性，从而可以呈现出五花八门的论文。第19页，讲稿共117张，创作于星期二不碰撞的标准为任意两架飞机的距离大于不碰撞的标准为任意两架飞机的距离大于8km;假设条件：假设条件：飞机飞行的方向角调整幅度不应超过飞机飞行的方向角调整幅度不应超过 ；（因飞机飞行的速度变化不大）所有飞机的飞行（因飞机飞行的

17、速度变化不大）所有飞机的飞行 速度速度 v 均为均为800km/h;有时需要通过查阅文献、资料给出合理假设有时需要通过查阅文献、资料给出合理假设注：注：第20页，讲稿共117张，创作于星期二进入该区域的飞机在到达区域边缘时，与区域内进入该区域的飞机在到达区域边缘时，与区域内 飞机的距离应在飞机的距离应在60km以上；以上；最多需考虑六架飞机；最多需考虑六架飞机；不必考虑飞机离开此区域后的状况。不必考虑飞机离开此区域后的状况。根据当年竞赛题目给出的数据，可以验证新进根据当年竞赛题目给出的数据，可以验证新进入的飞机与区域内的飞机的距离超过入的飞机与区域内的飞机的距离超过60公里。公里。根据当年竞赛

18、题目给出的数据，可以验证区域内根据当年竞赛题目给出的数据，可以验证区域内的飞机不超过架的飞机不超过架(包括新进入的包括新进入的)。第21页，讲稿共117张，创作于星期二个人的想法不同，队友之间争执不下的情况下，若时间允个人的想法不同，队友之间争执不下的情况下，若时间允许，都可一一写到论文中去，建立的模型一、模型二许，都可一一写到论文中去，建立的模型一、模型二；或者经讨论后，选择一个认为更合理的。或者经讨论后，选择一个认为更合理的。现在看来，无论是构建模型，还是计算，都不太难。现在看来，无论是构建模型，还是计算，都不太难。本例题未给出数据，将重点放在如何构建模型上本例题未给出数据，将重点放在如何

19、构建模型上第22页，讲稿共117张，创作于星期二解：解：(1)不考虑飞机的尺寸，用点代表飞机；不考虑飞机的尺寸，用点代表飞机；(2)已在区域内的已在区域内的5架飞机按给定的方向角作架飞机按给定的方向角作 直线飞行，则必不会碰撞，也不会发生直线飞行，则必不会碰撞，也不会发生 意外；意外；(应该根据题目中所给出的数据简应该根据题目中所给出的数据简 单的单的 验证一下验证一下)(3)飞机调整方向角的过程可在瞬间完成飞机调整方向角的过程可在瞬间完成,(不不 计调整方向所花费的时间计调整方向所花费的时间)。为解决该问题，补充假设：为解决该问题，补充假设：第23页，讲稿共117张，创作于星期二变量、参数的

20、符号假设变量、参数的符号假设（为了建模）（为了建模）在区域内飞行在区域内飞行飞飞时间（可以根据数据算出来）时间（可以根据数据算出来）第24页，讲稿共117张，创作于星期二四种情况：四种情况：四个象限，易用四个象限，易用4个表达式表示个表达式表示说明：说明：用初等数学的知识即可完成，用初等数学的知识即可完成，思考：思考：在哪个时间段某两架飞机可能相撞？在哪个时间段某两架飞机可能相撞？In fact,我们只需考虑两架飞机我们只需考虑两架飞机同时同时在区域内在区域内飞行时的情况，也就是说，飞行时的情况，也就是说，才是同在区域内的状况。才是同在区域内的状况。记为记为第25页，讲稿共117张，创作于星期

21、二根据题目条件，需计算第根据题目条件，需计算第 架飞机之间架飞机之间的的最短距离最短距离第26页，讲稿共117张，创作于星期二为此，我们可以给出原问题的模型如下：为此，我们可以给出原问题的模型如下：思考：思考：是否还有其他的表达形式？是否还有其他的表达形式？非线性规非线性规划模型划模型分别从目标函数和约束条件角度思考分别从目标函数和约束条件角度思考第27页，讲稿共117张，创作于星期二首先思考一下目标函数是否有其它的表达？首先思考一下目标函数是否有其它的表达？同学们首先想到的可能是同学们首先想到的可能是Oh,Sorry!有正有负有正有负抵消抵消第28页，讲稿共117张，创作于星期二最小一乘最小

22、一乘 法法最小二乘最小二乘 法法 因最小一乘法带绝对值，不好计算，以上两式，因最小一乘法带绝对值，不好计算，以上两式，比较而言，后者较好。比较而言，后者较好。为为了了避避免免抵抵消消or第29页，讲稿共117张，创作于星期二有的队员这样考虑：有的队员这样考虑：令为令为 ,转化为二次规划转化为二次规划用到经验模型中确定参数的近似准则用到经验模型中确定参数的近似准则:就所有飞机而言，就所有飞机而言，让调整弧度最大的让调整弧度最大的即即尽可能小，尽可能小，Chebshavf 准则准则第30页，讲稿共117张，创作于星期二其次讨论一下约束条件是否有其它表达？其次讨论一下约束条件是否有其它表达？若考虑区

23、域内不发生碰撞（若时间允许，也若考虑区域内不发生碰撞（若时间允许，也可以考虑出了区域的情况，另外建模）、错层可以考虑出了区域的情况，另外建模）、错层飞行（飞高或者飞低避免碰撞），进行模型的飞行（飞高或者飞低避免碰撞），进行模型的进一步改进，重点应放在解决问题的方法上。进一步改进，重点应放在解决问题的方法上。如如第31页，讲稿共117张，创作于星期二 无论选择哪一种表达，怎样考虑约束条件，目无论选择哪一种表达，怎样考虑约束条件，目标函数都不可能是线性的。标函数都不可能是线性的。现在看来，那年的题目建模只是在条件的考虑上现在看来，那年的题目建模只是在条件的考虑上和建模中目标函数的表达方面较难一点。

24、和建模中目标函数的表达方面较难一点。是一个带不等式约束的非线性规划问题。是一个带不等式约束的非线性规划问题。而且不可能转化成线性的形式。而且不可能转化成线性的形式。第32页，讲稿共117张，创作于星期二非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类：无约束非线性规划模型：无约束非线性规划模型：等式约束非线性规划模型：等式约束非线性规划模型：不等式约束非线性规划模型：不等式约束非线性规划模型：第33页，讲稿共117张，创作于星期二如如数据拟合的最小二乘问题就是一个无约束极值问题。数据拟合的最小二乘问题就是一个无约束极值问题。其思想是：观察点（实验数据点）到曲线的距

25、离的其思想是：观察点（实验数据点）到曲线的距离的平方之和最小平方之和最小 无约束非线性规划模型：无约束非线性规划模型：第34页，讲稿共117张，创作于星期二理论上无约束极值问题可化成求解理论上无约束极值问题可化成求解 即解一个即解一个 n 元方程组，且往往是非线性方程组。元方程组，且往往是非线性方程组。而一般说来，非线性方程组的求解并不比求无约束极值而一般说来，非线性方程组的求解并不比求无约束极值容易。容易。第35页，讲稿共117张，创作于星期二求解无约束极值问题的基本方法：求解无约束极值问题的基本方法：迭代法迭代法 从一个给定的初始可行点从一个给定的初始可行点 出发，依次出发，依次产生一个可

26、行点列产生一个可行点列的一个极小值点的一个极小值点,恰好是恰好是使得某个使得某个基本思路：基本思路：或或收敛于收敛于,称具有这种性质的算法称具有这种性质的算法是是收敛的收敛的.第36页，讲稿共117张，创作于星期二由由迭代到迭代到时时,记记即即其中向量其中向量为为搜索方向搜索方向,实数实数称为称为步长步长,确定以后确定以后,由由可唯一地确定可唯一地确定从从出发就可确定点列出发就可确定点列第37页，讲稿共117张，创作于星期二迭代的方法很多迭代的方法很多,各种迭代法的区别在于选取各种迭代法的区别在于选取的方式不同的方式不同,而而尤为关键尤为关键.一般要求一般要求递减递减,具有这种性质的算法叫做具

27、有这种性质的算法叫做下降下降算法算法.第38页，讲稿共117张，创作于星期二若已得若已得下降得最多下降得最多,并确定了并确定了的可行下降方向的可行下降方向上选取步长上选取步长则在射线则在射线使使且使且使即求即求求求的过程称为的过程称为一维搜索一维搜索.1.下降算法下降算法第39页，讲稿共117张，创作于星期二于是一维搜索归结为求解一维无约束极值问题于是一维搜索归结为求解一维无约束极值问题:其算法有其算法有Newton法、平分法、黄金分割法法、平分法、黄金分割法（0.618法）、分数法（法）、分数法（Fibonacci法）、抛物线法）、抛物线法（二次插值法）等，法（二次插值法）等，前两种算法需计

28、算前两种算法需计算的导数，的导数，后三种算法只需计算后三种算法只需计算的函数值。的函数值。下面仅介绍下面仅介绍Newton法，对其他方法的了解可参考法，对其他方法的了解可参考有关书籍。有关书籍。第40页，讲稿共117张，创作于星期二按按 给定初始可行点给定初始可行点 和控制误差和控制误差 ，迭代格式迭代格式迭代，迭代，当当时，时，即求得即求得的最优解的近似解的最优解的近似解停止计算。停止计算。Newton 法介绍法介绍第41页，讲稿共117张，创作于星期二 一个好的算法必须以较快的速度收敛到一个好的算法必须以较快的速度收敛到最优解。最优解。设算法产生的点列设算法产生的点列收敛于最优解收敛于最优

29、解若存在若存在及及使使则称则称为为 p 阶收敛的。阶收敛的。该算法也是该算法也是 p 阶收敛的。阶收敛的。第42页，讲稿共117张，创作于星期二 称为称为线性收敛；线性收敛；当当且且时，时，称为称为超线性收敛；超线性收敛；当当时，时，称为称为平方收敛；平方收敛；当当时，时，第43页，讲稿共117张，创作于星期二一个算法是否收敛，一个算法是否收敛，往往与往往与的选取有关的选取有关 若当若当充分接近充分接近时，时，由算法产生的点列由算法产生的点列才收敛于才收敛于则称该算法为具有局部收敛则称该算法为具有局部收敛性的算法；性的算法；若对若对则称该算法为具有全局收敛性的算法。则称该算法为具有全局收敛性的

30、算法。由算法产生由算法产生 的点列的点列均收敛均收敛于于第44页，讲稿共117张，创作于星期二 Newton法是平方收敛的，具有局部收敛性；抛法是平方收敛的，具有局部收敛性；抛物线法是超线性收敛的，具有全局收敛性；平分法、物线法是超线性收敛的，具有全局收敛性；平分法、黄金分割法、分数法是线性收敛的，具有全局收敛黄金分割法、分数法是线性收敛的，具有全局收敛性。性。常见一维搜索算法的收敛性常见一维搜索算法的收敛性第45页，讲稿共117张，创作于星期二当当具有多个极小值点时，具有多个极小值点时，则算法求得则算法求得的往往是的往往是的一个局部极小值点。的一个局部极小值点。此时可此时可改变改变的取值，重

31、新迭代求解。的取值，重新迭代求解。若求得多个极小值点，则从中选择一个若求得多个极小值点，则从中选择一个较满意的结果。较满意的结果。说明：说明：第46页，讲稿共117张，创作于星期二 1847年年Cauchy提出了第一个无约束极值问题提出了第一个无约束极值问题的算法的算法梯度法或最速下降法：梯度法或最速下降法：2.梯度法梯度法第47页，讲稿共117张，创作于星期二例题：应用梯度法求解例题：应用梯度法求解解：解：第48页，讲稿共117张，创作于星期二 该算法具有全局收敛性，是线性收敛的，但有该算法具有全局收敛性，是线性收敛的，但有时是很慢的线性收敛，这似乎与时是很慢的线性收敛，这似乎与“最速下降最

32、速下降”矛盾。矛盾。其实不然，最速下降方向函数在某点处的局部性质，其实不然，最速下降方向函数在某点处的局部性质，对局部来说是最速下降方向，对全局来说却不一定对局部来说是最速下降方向，对全局来说却不一定是最速下降方向，故梯度法不是有效的实用算法。是最速下降方向，故梯度法不是有效的实用算法。通过对它改进或利用它与其他收敛快的算法通过对它改进或利用它与其他收敛快的算法相结合可得相结合可得Newton法、法、Fletcher-Reeves共轭梯共轭梯度法、变尺度法和度法、变尺度法和Powell法法等有效算法。等有效算法。第49页，讲稿共117张，创作于星期二 下面仅介绍前两者，对后两者的了解可参阅下面

33、仅介绍前两者，对后两者的了解可参阅有关书籍。有关书籍。当当时，时，则则 。其中其中称为称为在在 处的处的Hesse矩阵。矩阵。Newton法法第50页，讲稿共117张，创作于星期二 该算法是平方收敛的，具有局部收敛性。该算法是平方收敛的，具有局部收敛性。对对Newton法进行改进，可得具有超线性收法进行改进，可得具有超线性收敛的且具有全局收敛性的敛的且具有全局收敛性的阻尼阻尼Newton法法或或修正修正Newton法法：当当时，时，有有 。第51页，讲稿共117张，创作于星期二 Fletcher-Reeves共轭梯度法共轭梯度法当当时，时，有有 。该算法的收敛速度介于梯度法和该算法的收敛速度介

34、于梯度法和Newton法法其中其中之间，既克服了前者的慢收敛性，又避免了之间，既克服了前者的慢收敛性，又避免了后者计算量大和仅具有局部收敛性的缺陷。后者计算量大和仅具有局部收敛性的缺陷。第52页，讲稿共117张，创作于星期二（2 2）只有等式约束的非线性规划问题通常可用消元法、只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法，将其化为无约束问题求解拉格朗日乘子法，将其化为无约束问题求解.（3 3）具有不等式约束的非线性规划问题解起来很复杂，具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等式约束，再将求解这一类问题，通常将不等式化为等式约束，再将约束问题化

35、为无约束问题，用线性逼近的方法将非线约束问题化为无约束问题，用线性逼近的方法将非线性规划问题化为线性规划问题性规划问题化为线性规划问题.下面先介绍一个简单的非线性规划问题的下面先介绍一个简单的非线性规划问题的例子，其中的一些约束条件是等式，这类非线例子，其中的一些约束条件是等式，这类非线性规划问题可用拉格朗日方法求解性规划问题可用拉格朗日方法求解.第53页，讲稿共117张，创作于星期二第54页，讲稿共117张，创作于星期二第55页，讲稿共117张，创作于星期二第56页，讲稿共117张，创作于星期二第57页，讲稿共117张，创作于星期二Kuhn-Tucker定理：对于不等式约束非线性最优化 极值

36、问题若 ，均可微，则其极值点存在的必要条件是：注：更详细的结论参阅有关书籍注：更详细的结论参阅有关书籍.不等式约束非线性规划模型不等式约束非线性规划模型第58页，讲稿共117张，创作于星期二注：1、库-图条件是判别有约束极值点的必要条件，并非充分条件。但是对于凸函数、凸集问题也是判别其极值点的充分条件。固此时的局部最优解也必为全局的最优解。2、库-图乘子与拉格朗日乘子类似。但拉格朗日乘子的符号不是确定的，可正可负；而库-恩乘子的符号是确定的，其规律为：a、求 ，时，则 b、求 ，时，则 c、求 ，时，则 d、求 ，时，则第59页，讲稿共117张，创作于星期二罚函数法罚函数法:约束最优化问题化为

37、无约束最优化问题的一种求解方法约束最优化问题化为无约束最优化问题的一种求解方法第60页，讲稿共117张，创作于星期二第61页，讲稿共117张，创作于星期二罚函数法的步骤：（等式约束最优化问题罚函数法）罚函数法的步骤：（等式约束最优化问题罚函数法）第62页，讲稿共117张，创作于星期二第63页，讲稿共117张，创作于星期二第64页，讲稿共117张，创作于星期二第65页，讲稿共117张，创作于星期二罚函数法步骤：（不等式约束最优化问题罚函数法）罚函数法步骤：（不等式约束最优化问题罚函数法）第66页，讲稿共117张，创作于星期二第67页，讲稿共117张，创作于星期二第68页，讲稿共117张，创作于星

38、期二注：罚函数法更多的详细改进工作，需参阅相关书籍注：罚函数法更多的详细改进工作，需参阅相关书籍第69页，讲稿共117张，创作于星期二 在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.我们先来看一个投资计划的例子.4.4.多目标规划多目标规划第70页，讲稿共117张，创作于星期二例：例：投资问题投资问题 某公司在一段时间内有某公司在一段时间内有a(亿元亿元)的资金可用于建厂投资。若可的资金可用于建厂投资。若可供选择的项目记为供选择的项目记为1,2,m。而且一旦对第。而且一旦对第i

39、个项目投资就用去个项目投资就用去ai亿亿元；而这段时间内可得收益元；而这段时间内可得收益ci亿元。问如何确定最佳的投资方案？亿元。问如何确定最佳的投资方案？最佳投资方案：投资最少，收益最大！最佳投资方案：投资最少，收益最大！第71页，讲稿共117张，创作于星期二投资最少：投资最少：约束条件为：约束条件为：收益最大：收益最大：第72页，讲稿共117张，创作于星期二第73页，讲稿共117张，创作于星期二第74页，讲稿共117张，创作于星期二第75页，讲稿共117张，创作于星期二第76页，讲稿共117张，创作于星期二第77页，讲稿共117张，创作于星期二第78页，讲稿共117张，创作于星期二第80页

40、，讲稿共117张，创作于星期二第81页，讲稿共117张，创作于星期二第82页，讲稿共117张，创作于星期二5.动态规划动态规划 动态规划模型问题一般要归结为求最优控制函数使某动态规划模型问题一般要归结为求最优控制函数使某动态规划模型问题一般要归结为求最优控制函数使某动态规划模型问题一般要归结为求最优控制函数使某个泛函达到极值个泛函达到极值个泛函达到极值个泛函达到极值.求解泛函极值问题的方法主要有求解泛函极值问题的方法主要有变分变分法法和和最优控制理论方法最优控制理论方法最优控制理论方法最优控制理论方法.第83页，讲稿共117张，创作于星期二第84页，讲稿共117张，创作于星期二第85页，讲稿共

41、117张，创作于星期二第86页，讲稿共117张，创作于星期二第91页，讲稿共117张，创作于星期二第92页，讲稿共117张，创作于星期二第93页，讲稿共117张，创作于星期二第94页，讲稿共117张，创作于星期二第95页，讲稿共117张，创作于星期二第96页，讲稿共117张，创作于星期二第97页，讲稿共117张，创作于星期二例题：例题：(最速降线问题最速降线问题)最速降线问题是历史上变分法最速降线问题是历史上变分法开始发展的第一个问题开始发展的第一个问题.它是贝努里（它是贝努里（J.BernoulliJ.Bernoulli）于于16961696年提出的。问题的提法是这样的：年提出的。问题的提法

42、是这样的：设设A A和和B B是铅直平面上不在同一铅直线上的两点，在所有是铅直平面上不在同一铅直线上的两点，在所有连结连结A A和和B B的平面曲线中，的平面曲线中，求一曲线求一曲线，当质点仅受重力作用，当质点仅受重力作用，且初速为零，沿此曲线从且初速为零，沿此曲线从A A滑行至滑行至B B时，使所需时间最短时，使所需时间最短.第98页，讲稿共117张，创作于星期二第99页，讲稿共117张，创作于星期二第100页，讲稿共117张，创作于星期二第101页，讲稿共117张，创作于星期二第102页，讲稿共117张，创作于星期二第103页，讲稿共117张，创作于星期二第104页，讲稿共117张，创作于

43、星期二第105页，讲稿共117张，创作于星期二第106页，讲稿共117张，创作于星期二第107页，讲稿共117张，创作于星期二例题：生产设备的最大经济效益例题：生产设备的最大经济效益 某工厂购买了一台新设备投入到生产中。一方面该设备某工厂购买了一台新设备投入到生产中。一方面该设备随着运行时间的推移其磨损程度愈来愈大，因此其转卖价随着运行时间的推移其磨损程度愈来愈大，因此其转卖价将随着使用设备的时间增加而减小；另一方面生产设备总将随着使用设备的时间增加而减小；另一方面生产设备总是要进行日常保养，花费一定的保养费，保养可以减缓设是要进行日常保养，花费一定的保养费，保养可以减缓设备的磨损程度，提高设备的转卖价。那么，怎样确定备的磨损程度，提高设备的转卖价。那么，怎样确定最最优保养费优保养费和和设备转卖时间设备转卖时间，才能使这台设备的经济，才能使这台设备的经济效益最大。效益最大。第108页，讲稿共117张，创作于星期二第109页，讲稿共117张，创作于星期二第110页，讲稿共117张，创作于星期二第111页，讲稿共117张，创作于星期二第112页，讲稿共117张，创作于星期二第113页，讲稿共117张，创作于星期二第114页，讲稿共117张，创作于星期二第115页，讲稿共117张，创作于星期二第116页，讲稿共117张，创作于星期二感谢大家观看第117页，讲稿共117张，创作于星期二