数模引言线性非线性-1_3

1、一、从现实对象到数学模型 原原型型和模型和模型 原型（原型（Prototype）指人们）指人们在在现实世现实世界里界里关关 心心、研究或者从研究或者从事事生产、管理生产、管理的的实际对象。实际对象。 模型模型（Model）指为了某个）指为了某个特特定目的将原型定目的将原型 的的某某一一部分信息部分信息简简缩、提练而缩、提练而构构造的原型替造的原型替 代代物物。 注注意意：为了某种为了某种目目的构造模型的构造模型，模型不是原模型不是原 型型原原封封不动的复不动的复制制品，原型有品，原型有各各个方面和各个方面和各 种种层层次次的的特征，特征，而而模型只要求模型只要求反反映与某种目映与某种目 的的有

2、有关的那些关的那些方方面面和层次。和层次。模型的分类模型的分类 直观模型（直观模型（如如实物实物、玩具、照片）玩具、照片） 物物质质模型（形象模型（形象模模型）型） 物理模型（物理模型（为为了模了模拟拟实验）实验） 模型模型 思维模型（思维模型（经经验形验形式）式） 理理想想模型（抽象模型（抽象模模型）型） 符号模型（符号模型（如如地图地图、电路图、分电路图、分子子式）式） 数数学学模模型型（由数由数字字、字母或其它字母或其它数数学符学符号号组成的，组成的， 描述描述现实对现实对象象数量数量规规律的数学公律的数学公式式，图，图形形或算法）或算法）模型的定义模型的定义 所所谓谓数数学学模模型型是

3、是指指对对现现实实世世界界的的一个一个 特特定定对对象象，为为了了一一个个特特定定目目的的，根根据据 特特有有的的内内在在规规律律，做做出出一一些些必必要要的的简简 化化假假设设，运运用用适适当当的的数数学学工工具具得得到到的的 一一个个数数学学结结构构。建立数学模型的过程建立数学模型的过程 数数学学模型是运用模型是运用数数学的语言和学的语言和工工具，对部分具，对部分 现现实实世界的信息世界的信息（现象、数现象、数据据）加）加以以翻译、翻译、 归归纳纳的的产物，它产物，它源源于现实，又于现实，又高高于现实。数于现实。数 学学模模型经过型经过演绎演绎、推断，给出推断，给出数数学上的分析、学上的分

4、析、 预预报报、决策或、决策或控控制制，再经过解，再经过解释释，回到现实，回到现实 世世界界，最后，这，最后，这些些分析、预报分析、预报、决策或控制决策或控制 必必须须接受实际的接受实际的检检验，验，完成实完成实践践理论理论实践这实践这一一循环循环，如果检验的如果检验的结结果是正确的果是正确的或或基基本正确的，本正确的，就就可以用来指可以用来指导导实际，否实际，否 则则，要要重新考虑重新考虑翻翻译，归纳的译，归纳的过过程，修改数程，修改数 学学模模型。型。1数学建模流程图数学建模流程图现实对象的信现实对象的信息息 数学模型数学模型现实对象的解现实对象的解答答 数学模型的解答数学模型的解答（分析

5、、预报、（分析、预报、 决策或控制）决策或控制）表达（归纳）表达（归纳）解释解释验证验证求解（演绎）求解（演绎）二、国外数学建模情况（国外从70年代初） 1、教学、教学 课课程程、教材、教材 1978 年年 由由 Springer 出出 版 ，版 ， 国国 防 科防 科 大大 翻翻 译译 Modeling in Applied Mathematics共共4卷卷Ellis HarwoodMath and its ApplicationKaporMathematical Modeling 数数学学国际会议，国际会议，1983年起，会年起，会议议录由录由Harwood出版出版 竞赛竞赛国外数学建模情

6、况 2、科研科研 会议会议 1977数学和数学和计计算机建模国算机建模国际际会议会议 期刊期刊Mathematical and computer Modeling年刊年刊Applied Mathematical ModelingSIAM Review、SIAM NewsJ. of Mathematical Modeling for Teacher三、国内数学建模发展的情况 国国内内从从1983起起，先先驱有驱有肖肖树树铁铁、叶叶其其 孝孝、姜姜启启源等源等 我我国国从从1991年年在在上上海等海等地地区区开开展展数数学学 建建模模竞竞赛的赛的工工作作，1992年年起起由由中中国国工工 业与业与

7、应用应用数数学学会主学学会主办办全国大全国大学生学生数数 学学建建模模竞赛竞赛，从，从1994年年起起由由政政府府国国家家 教委（现教委（现为为教育部）教育部）下下达文件达文件在全在全国国 高高校校中中开开展展数数学学建建模模竞竞赛。赛。我校数学建模发展的情况 我我校校从从1993年年起起每每年都年都参参加加全全国国大大学学 生生数学建数学建模模竞赛，并竞赛，并取取得了较得了较好的好的成成 绩。绩。四、数学建模发展迅速的主要原因 1、花花费费少、少、设设备备少少、周周期短期短 2、许多问、许多问题题的解决只的解决只有有建模是唯建模是唯一一途途 径径（如太（如太阳阳表面温度表面温度、人体血人体血

8、液总液总量量 等）等）2数学建模发展迅速的主要原因 3、以以前前发展发展慢慢的的原原因因、计计算算工工具具（如（如 计计算算机机速速度度慢慢、编编程程的的复复杂杂、不不能解能解 决符决符号号的的运运算算、图图形形学学的的问问题题），而，而 今高今高速速、小小型型、智智能能、廉廉价价计计算算机的机的 出现出现使使数数模模发发展展迅迅速速，注注意意数数学学建模建模 的美的美国国五五大大工工业业：汽汽车车、计计算算机机、石、石 油、油、飞飞机机工工业业、机机器器制造制造五、建立数学模型的方法和步骤 1、方法上方法上大大体分体分为为两大类两大类 机理分析：是根据对现实对机理分析：是根据对现实对象特性的

9、认识，分象特性的认识，分 析其析其因果关系，找出反映机因果关系，找出反映机理的规律，建立的理的规律，建立的 模型常有模型常有明确的物理或现实意义。明确的物理或现实意义。 测试分析：测试分析：将研究对象视为一个将研究对象视为一个“黑箱黑箱”系统，系统， 内部内部机理机理无无法法直直接寻求，接寻求，可可测测量量系统的输系统的输入入 （出）数（出）数据据，并并以此为基以此为基础础运运用用统计分析统计分析方方 法，按法，按照事先确定的准则在照事先确定的准则在某一类模型中选出某一类模型中选出 一个与数据一个与数据拟合得最好的模拟合得最好的模型。这种方法称为型。这种方法称为 系统辨识（系统辨识（Syste

10、m Identification）。）。建立数学模型的方法和步骤 2、建、建立立模型模型的的大大体体过程过程 模型准备：了解问题模型准备：了解问题的的实际背景，明确实际背景，明确 建模建模的目的，掌握对的目的，掌握对象象的各种信息和统的各种信息和统 计数据等，计数据等，弄清实际弄清实际对对象的特征，由此象的特征，由此 初初步步确定用哪一确定用哪一类类模型。模型。 模型假设：根据对象模型假设：根据对象的的特征和建模的目特征和建模的目 的，的，对问题进行必要对问题进行必要的的合理的简化，并合理的简化，并 用精确的用精确的语言做出假语言做出假设设，这是关键的一，这是关键的一 步。步。建立数学模型的方

11、法和步骤 模型构成：根据所作模型构成：根据所作假假设，利用适当的设，利用适当的 数学数学工具，构造各个工具，构造各个量量之间的关系或其之间的关系或其 它数学结它数学结构，这里除构，这里除需需要上些相关学科要上些相关学科 的专门知识外，的专门知识外，还需还需要要较广阔的应用数较广阔的应用数 学学方方面的知识。面的知识。 模模型型求解求解 模模型型分析分析 模模型型检验检验 模模型型应用应用建立模型过程建立模型过程模型应用模型应用模型求解模型求解六、六、建模示例 例例1：椅椅子能子能在在不不平平的的地地面面上上放放稳稳吗？吗？ 现实生活中，把椅子现实生活中，把椅子往往不平的地面上一不平的地面上一

12、放通放通常只有三只脚着常只有三只脚着地地，放不稳，然而，放不稳，然而 只需稍挪只需稍挪动几次，就动几次，就可可以使四只脚同时以使四只脚同时 着着地地，放稳了。，放稳了。3模型准备模型准备模型假设模型假设模型建立模型建立模型检验模型检验模型分析模型分析模型构成： 建立模型的关键在于恰建立模型的关键在于恰当当 地寻找表示椅子位置的地寻找表示椅子位置的变变 量量，并并把把要要证证明的明的“着地着地” 这个结论归结为某个简这个结论归结为某个简单单 的的数数学关系。学关系。 注意到椅子四脚连线呈注意到椅子四脚连线呈正正 方形方形ABCD。中心点为。中心点为O， 椅子绕椅子绕O点点转转动时，对动时，对角角

13、线线 AC与与X轴的夹角轴的夹角 来来表示椅表示椅 子子的的位位置置，“着地着地”就是椅就是椅 脚脚与与地面的距离地面的距离等等于于0.yxC CA ABDDBo模型构成： 距距离是离是 的函的函数数，记记A、C两两脚脚与与地面地面 距距离离之之和和为为g( )，B、D两两脚脚与与地地面距面距 离离之之和和为为f( )，不不失失一一般般性性，可设可设 g(0)=0，注注意意到到椅椅子子在在任任何何位位置置总总有有 三三只只脚脚可可以以着着地地，即即对对任任意意 ，f( )和和 g( )中中总总有一有一个个为为零零，则则“稳稳定定的的椅椅子子” 可可归归结结为为下下面面的的数数学学问问题：题：模

14、型构成： 假 设假 设 ： f( ) 、 g( ) 是是 的的 连 续 函连 续 函 数数 ， g(0)=0 ， f(0)0 ， 且 对 任且 对 任 意意 ， f( ).g( )=0 求求证证：存在存在 0，使使f( 0)=g( 0)=0 证证：令：令h( )=f( )-g( ) 则则h(0)0, h( /2)ui交交易费易费 =piuixiui而而题题目所给目所给定定的的定值定值 ui(单单位位:元元)相相对对总总投投资资 M 很小很小, piui 更小更小, 可可以以忽忽略不略不计计,这这样样购购买买 Si 的的净净收益收益为为(ri-pi)xi 3要要使使净收净收益益尽可能尽可能大大，

15、总体总体风风险险尽尽可可能能小小,这是这是一一个个多多目目标规标规划划模型模型:n目标目标函函数数约束约束条条件件4. 模模型型简化：简化：MAX (ri pi ) xii 0MINmax qixin (1 pi )xi =Mi 0 xi0i=0,1,nc投投资资者在权者在权衡衡资资产产风风险和险和预预期收益期收益两两方方面时面时，希希望望选选择一个择一个令令自自己己满满意意的的投投资组合。资组合。因此因此对对风险、风险、收收益赋益赋予予权权重重 s（0s1)，s 称为投称为投资资偏好偏好系系数数.n模型模型 3目目标标函数：函数：min smaxqixi -（1-s） (ri pi ) xi

16、i 0n约束条件约束条件 (1 pi )xi =M， xi0i 0i=0,1,2,nb若投资者希望若投资者希望总总盈利至少盈利至少达达到水平到水平 k 以上，在以上，在风风险最小的情况险最小的情况下下寻找相寻找相应应的投资组的投资组合合。 模型模型 2 固定盈利水平固定盈利水平，极小化风险极小化风险目目标标函数：函数： R= minmax qixin约约束束条件：条件： (ri pi ) xi k，i 0 (1 pi )xi M ， xi 0i=0，1，na 在实际投在实际投资资中中，投投资者资者承承受风险的受风险的程程度不一样度不一样，若若给给定风险一个定风险一个界界限限 a，使最大的一个，

17、使最大的一个风风险险 qixi/Ma，可找到相应，可找到相应的的投资方投资方案案。这样把。这样把多多目标规划变成目标规划变成一一个目标个目标的的线性规划。线性规划。 模模型型 1 1 固固定定风险水平风险水平，优化收益优化收益n目标目标函函数：数： Q=Q=M MAXAX (ri pi ) xii 0约束约束条条件：件：qi xi aaM (1 pi )xi M ， xi 0 i=0，1，n四、模型四、模型1 1的的求解求解模型 1 为:minf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x 4 ) Tx0 + 1.01x1 +

18、1.02x2 +1.045x3 +1.065x4 =1s.t.0.025x1aa0.055x3a0.026x4a0.015x2xi 0 (i = 0,1,.4)由于由于a是是任意给任意给定定的风险度，的风险度，到到底怎底怎样样给定没有一给定没有一个个准则准则，不同的投不同的投 资者有不同资者有不同的的风险风险度度。我们从。我们从a=0开始，开始，以以步长步长a=0.001进行进行循循环搜索，环搜索， 编制程序如编制程序如下下：11xBbx1x2x3ix1211/ 204x3101/ 414 j509/ 40 x24210 x30-1/201 j-4-9/200siri （% %）qi （% %

19、）pi （% %）ui （元）元）S S1 128282 2.5.51 11 10303S S2 221211 1.5.52 21 19898S S3 32 23 35 5.5.54 4. .5 55 52 2S S4 42 25 52 2.6.66 6. .5 54 40 0a=0;while(1.1-a)1A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;b=a;a;a;a; vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub); ax=xQ=-valplot(a,Q

20、,.)，axis(0 0.1 0 0.5)，hold ona=a+0.001;end xlabel(a),ylabel(Q)a = 0.0200 x = 00.8000 0.1882 0a = 0.0400 x = 0.0000 0.9901 0.0000 000Q =0.2518Q =0.2673计算结果：计算结果：五、五、 结结果果分析分析 1. 1.风险大风险大，收益也收益也大大。2.2.当投资当投资越越分散时分散时，投资者承担投资者承担的的风险风险越越小，这与题小，这与题意意一致一致。即即: : 冒险的冒险的投投资资者会者会出出现集中投资现集中投资的的情况情况，保守的投资保守的投资者者

21、则尽则尽量量分散投资。分散投资。3.3.曲线上曲线上的的任一点任一点都都表示该风险表示该风险水水平的平的最最大可能收益大可能收益和和该收该收益益要求的最要求的最 小风小风险。对险。对于于不同不同风风险的承受能险的承受能力力，选，选择择该风险水平该风险水平下下的最的最优优投资组合。投资组合。4.4.在在a a= =0.00.00 06 6附近附近有一有一个转折点，个转折点，在在这一这一点点左边，风险左边，风险增增加很加很少少时，利润增长时，利润增长 很快。很快。在在这一点这一点右右边，风险增边，风险增加加很大很大时时，利润增长，利润增长很很缓慢缓慢，所以对于风所以对于风险险和和 收益没收益没有有

22、特殊偏特殊偏好好的投资者来的投资者来说说，应，应该该选择曲线的选择曲线的拐拐点作点作为为最优投资组最优投资组合合， 大约大约是是a a* *= =0.60.6% %，Q Q* *=20% =20% ，所对，所对应应投资投资方方案为案为: :风险度风险度 收益收益 x0 x1x2x3x40.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212实实验验作业作业某厂生产甲乙两种口味的饮料某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料每百箱甲饮料需用原料6千克千克, 工人工人10名名,可获利可获利10万元万元;每百箱乙饮料需用原料每百箱乙饮料需用原料5千克千克,工人工人

23、20 名名,可获可获利利9万元万元.今今工厂共有原料工厂共有原料60千千克克,工人工人150名名,又又由由于其于其 他条件所限他条件所限甲饮料产量不超过甲饮料产量不超过8百箱百箱.问如何安排生产计划问如何安排生产计划,即即 两种饮料各生产两种饮料各生产多少使获利最大多少使获利最大.进一步讨论进一步讨论:1)若投资若投资0.8万万元可增加原料元可增加原料1千克千克,问应否作这项投资问应否作这项投资.2)若每百箱若每百箱甲甲饮料多获利饮料多获利1万元万元,问应否改变生产计划问应否改变生产计划.第5章无约束优化 3.1预备预备知知识识 一一、问题的提出问题的提出 例例 选址选址问问题：某题：某市市燃

24、气公司计燃气公司计划划要建一个要建一个 煤煤气气供应站，该供应站，该站站要向城市中要向城市中有有固定位置的固定位置的 m个个用用户户供货。对供货。对于于选定的坐标选定的坐标系系而言，煤而言，煤 气气供供应站与煤应站与煤气气厂厂其坐标其坐标为为(0,0)相相距不能超距不能超 过过20km，已知，已知第第i个用户的位置个用户的位置（坐标）为坐标）为（ai,bi），），i=1,m，如，如果果只考只考虑虑直线距直线距离离，问如何确定问如何确定这这个煤气站的个煤气站的位位置，才能使置，才能使 总总的的运输距离最运输距离最短短？问题的提出 解：设煤气站的位置为（x1,x2） 即求：ms.t.x2 x2 2

25、0212i 121i2 i2min f ( x1 , x2 ) ( x a ) ( x b )12a = 0.0030 x = 0.49490.12000.20000.05450.1154Q = 0.1266c=-0.05 -0.27 -0.19 -0.185 -0.185;a = 0.0060 x = 00.24000.40000.10910.2212Q = 0.2019Aeq=1 1.01 1.02 1.045 1.065; beq=1;a = 0.0080 x = 0.00000.32000.53330.12710.0000Q = 0.2112a = 0.0100 x = 00.4000

26、0.584300Q =0.2190一般形式：X R 其其中中R=gj(X)0, j=1,2,m 分分类类：线性规划：线性规划，二次规划，二次规划，非非线性规划线性规划等等 非非线线性规划又可性规划又可分分为为 无无约约束非线性规束非线性规划划，有约束非，有约束非线线性规划。性规划。min f ( X )min f X X En其中f : E n E1标标准准形式：形式：求求解解无约束最优无约束最优化化问题的基本问题的基本思思想想求解的基本思求解的基本思想想 ( 以二元函数为例 )x1x2f (x1 x2 )0 x12x03510XX1X 2f ( X 0 ) f ( X1 ) f ( X 2

27、)连 续 可 微max f X = min f X X EnX En多局部极小f 0 . 298f 0f 0 . 298)1 211 221222f (x x ) 2x 2x x x 3x x二、非线性规划的图示 例1min f ( X ) ( x 2)2 ( x 2)212h( X ) x1 x2 6 0三、极值问题 局部极小点，全局极小点13四、极值点存在的条件 定理1（必要条件）f ( X *) 0 定理2（充分条件）Z 0, ZT H ( X *)Z 0,则x*为f(x)的严格局部极小点。五、凸规划 X R 其中R=gj(X)0, j=1,2,m，这里 f(X)为凸函数，gj(X)为凹

28、函数。 可以证明：上述R为凸集，其局部最优 解X*即为全局最优解，而且其最优解 的集合形成一个凸集，当凸规划的目 标函数f(X)为严格凸函数时，其最优 解必定唯一。min f ( X )3.2无约束非线性规划 一、下降算法 先给定一个初始估计X( 0 )，找X( 1 )，使 f(X(1)0，取，取 =0.618，k=0 (2)若若则停止，则停止，x* a ,b ；否则转；否则转(3)k k (3)计算计算sk=ak+(1-)(bk-ak)tk=ak+(bk-ak)及及f(sk),f(tk) (4)若若f(sk)f(tk)，取取ak+1=sk, bk+1=bk, sk+1=tk, f(sk+1)

29、=f(tk),求求tk+1=ak+1+(bk+1-ak+1)及及f(tk+1) 若若f(sk) f(tk)，取，取ak+1=ak, bk+1=tk, tk+1=sk, f(tk+1)=f(sk),求求sk+1=ak+1+(1-)(bk+1-ak+1)及及f(sk+1) (5)令令k=k+1转转(2)| b0 a0b akk0.618法 P69例3用0.618法求 fplot(x2+2*x, -3,5)grid-3 -2 -1 0 1 2 3 4 5-5030252015105350.618法sktkkakbkf(sk)f(tk) x*=(-1.112 -0.936)/2= -1.024三、无约

30、束非线性规划 1.梯梯度度法法（最最速速下下降降法法）（Steepest Descent Method） 1) 梯梯度法的度法的基基本本原原理理 设设无无约约束束极极值值问问题题中中的的函函数数f(X)有一有一 阶连阶连续续偏偏导导数数，具具有有极极小小点点X* 寻寻找找X(k)X* 在在点点X(k)沿沿方方向向S(k)作射线作射线X=X(k)+S(k)梯度法f(X)在在X(k)处展处展成成Taylor级数级数f ( X ) f ( X ( k ) S ( k ) ) f ( X ( k ) ) f ( X ( k ) )T S ( k ) o( )其其中中lim o( ) 0 对对于于充分小

31、的充分小的，只要只要 f(X(k)TS(k)0， k=0 (2)计计算算 f(X(k)，若，若| f(X(k)|， 则停则停止止，X*X(k)，否，否则则转转下下一步一步 (3)令令S(k)=- f(X(k)，从从X(k)出出发发，沿，沿 S(k)进进行一行一维维搜搜索索，求求最最佳佳步步长长k k (4)令令X(k+1)= =X(k)+k kS(k)，k=k+1, 转转(2)注：求最佳步长的三种方法 (1)一一维搜索维搜索法法（如如0.618法）法） (2)解解析法（析法（驻驻点点法法） (3)公公式法式法公式法 若若f(X)具具有有二二阶阶连连续续偏偏导导数数，在在X(k)处处 作作f(X

32、(k)- f(X(k)的的Taylor展式展式f ( X ( k ) f ( X ( k ) ) f ( X ( k ) ) f ( X ( k ) )T f ( X ( k ) )2 对对求求导导，并并令令其其等于等于0，得得近近似似最佳最佳 步长步长 1 2 f ( X ( k ) )T H ( X ( k ) ) f ( X ( k ) ) k f ( X ( k ) )T H ( X ( k ) ) f ( X ( k ) ) f ( X ( k ) )T f ( X ( k ) )梯度法 例例4 试试用用梯梯度度法法求求f(X)=(x1 1-1)2+(x2 2-1)2 的的极极小小点

33、点，=0=0.1.12. 牛顿法 设设X(k)是是f(X)的的近近似似点点，将将f(X)在在X(k)点点 作作二二阶阶Taylor展展开开，得，得f ( X ) f ( X ( k ) ) f ( X ( k ) )T ( X X ( k ) )2 记记右右端端=(X) 令令(X)=0得得 f ( X ( k ) ) H ( X ( k ) )( X X ( k ) ) 0 X ( k 1) X ( k ) H ( X ( k ) ) 1 f ( X ( k ) ) 此此即即为为Newton迭代迭代公公式。式。 1 ( X X ( k ) )T H ( X ( k ) )( X X ( k )

34、 )16牛顿法算法步骤：牛顿法算法步骤：(1) 选定初始点 X 0 En ，给定允许误差 0 ，令 k=0； (2) 求 f X k , 2 f X k 1 ,检验：若 f X k ,则停止迭代, X * X k .否则, 转向(3)；(3) 令 S k 2 f X k 1 f X k （牛顿方向） ； (4) X k 1 X k S k , k k 1 ,转回(2).如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代一次迭代 就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点， 但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收 敛速度还是很快的.牛顿法的收敛速度虽然较

35、快，但要求Hessian矩阵要可 逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储 量.3. 拟牛顿法（DFP）（Davidon-Fletcher-Powell） 方方法法：用：用Hk+1近近似似代代替替H(X(k)-1，不，不 需需要要求求逆逆矩阵矩阵 公公式式见见P73。第6章 约束非线性规划 一一、基基本本概念概念 非非线线性性规规划划的的数数学学模型模型 min f ( X ) 可可行行下下降降方方向向的的概念概念i 1,2,., mhj ( X ) 0,j 1,2,., ls.t.gi ( X ) 0,二、最优性条件定定理理 (Kuhn-Tucker条件条件) 设设X*是是NL

36、P的的可可行解，行解，f, gi（iI I起作起作用用约束下约束下 标集标集）在在X*可可微微，gi（i不属不属于于I）在在X*连续，连续，hj（j=1,2,l）在）在X*连续可连续可微微，再再假设假设 gi(X*)（iII）和和 hj(X*)（j=1,2,l）线）线性性无关无关。如。如果果X*是是NLNLP P的的局局部最部最优优解，解，则存则存在在i（iI I）和）和 j（j=1,2,l）使使得得 0, i I i f ( X *) i gi ( X *) j hj ( X *) 0 i Ij 1l定理 (Kuhn-Tucker条件条件) 如果设如果设gi（i不属不属于于I）在）在X*也可

37、也可微，微，则则上述条上述条 件可件可改改为：为： 称称X*为为K-T点。点。 i i i 0, f ( X *) i gi ( X *) j hj ( X *) 0 g ( X *) 0,i 1,., m i 1,., mi 1j 1ml三、约束非线性规划问题的求解方法 1. 1. 非线非线性性规划的规划的线线性逼近性逼近 2 2制约函数方法（制约函数方法（SUMTSUMT）（Sequential Unconstrained Minimization Technique） (1)SUMT外点法外点法（罚函数法）罚函数法）对对minf(X) s.t. hj(X)=0, j=1,2,l 可可转化

38、为求：转化为求： 其中其中M是一个较是一个较大大的正数。的正数。min T ( X , M ) f ( X ) M hj ( X )j 1l217SUMT外点法 对不等式约束，由于对不等式约束，由于gi(X)0 0等价于等价于m minin( (0,0, gi(X)=0, )=0, 故一般非线性规划问题故一般非线性规划问题min f ( X ) gi ( X ) 0, hj ( X ) 0, 可转化为求：可转化为求： jj 1i1min T ( X , M ) f ( X ) M min(0, g ( X ) M h ( X )li 1,2,., mj 1,2,., lmi22s.t . SU

39、MT外点法 例例1 用外用外点点法求法求 T ( X , M ) ( x 1)2 Mmin(0,( x 2)2 min(x-1)2 s.t. x-200 解解：构造罚函数构造罚函数1 M M 0时时, x(M ) 1M 1时时, x(M ) 32M 10时时, x( M ) 2111M , x( M ) 2, x* 2当当x 2 0时时, 令令 dT 2( x 1) 2M ( x 2) 0dx1 2M x( M ) SUMT外点法 例例2 用用外外点点法求法求minf(X)=x1+x2 g1(X)=-x12+x200 g2(X)=x100SUMT外点法 解解：构构造造罚罚函数函数2(1 M )

40、 4(1 M )2 2M当当M 时时, X * (0,0)T得得X ( M ) ( 1 , ( 1 1 )T T 1 2M ( x 2 x ) 0 x T 1 2M( x 2 x )( 2 x ) x 0 x12当当g1 0, g2 0时时, 令令T ( X , M ) x x Mmin(0,( x 2 x )2 min(0, x )2 12212111121(2)SUMT内点法(障碍函数法)对minf(X) s.t. gi(X)0, i=1,2,m 构造m 或I ( X , r) f ( X ) r 1 i1 gi ( X )mI ( X , r) f ( X ) rln gi ( X )i

41、1SUMT内点法 例例3 用用内内点点法求法求 minf(X)=(1/12)(x1+1)3 + x2 g1(X)=x1-100 g2(X)=x20018SUMT内点法 解解：构造障碍函数构造障碍函数I ( X , r ) 1 ( x 1)3 x r( 1 1 )当当r 0时时, x 1, x 0, X * (1,0)T令令 I 0, I 0, 得得 x1 x2x1 1 2 r , x2 rx 2 I 1 r x( x 1)2 I 1 ( x 1)2 r x412求求 min I ( X , r )x1 1 x2122211112四、建模案例：飞行管理问题（95A） 1. 问问题题的的提出提出

42、2. 问问题题分析分析 3. 模模型型假设假设 4. 模模型型建立建立模型建立 从从形式上看，本形式上看，本题题属于最优控属于最优控制制问题（实问题（实 际际是是一一个一般优个一般优化化问题），而问题），而且且有有6个个可可控控 制制对对象，相象，相当复当复杂杂，因为可以，因为可以在在第第6架架飞飞机机 进进入入该正方形区该正方形区域域起至碰撞发起至碰撞发生生前任一时刻前任一时刻 调调整整6架飞架飞机机中任中任一一架、任二架架、任二架、甚至六架甚至六架 飞飞机机的飞行方向的飞行方向，可以一可以一次、次、二二次、多次甚次、多次甚 至至不不断地调整飞断地调整飞机机的飞行方向的飞行方向角角，因而调整

43、，因而调整 方方案案太多了，要太多了，要进进行优化，无行优化，无疑疑似似大海捞大海捞 针针，所以首先要所以首先要简简化方案。化方案。1）两条结论 结结论论1：如：如果果会发会发生生碰撞，尽早碰撞，尽早调调整一定优整一定优 于于晚晚调整。（这调整。（这一一结论大大缩结论大大缩小小了优化范了优化范 围围，原来可原来可在一在一段段时间的任一时间的任一时时刻进行调刻进行调 整整，而根据这一而根据这一结结论，仅需考论，仅需考虑虑开始采取行开始采取行 动动就就可以了。）可以了。） 结结论论2：如：如果果会发会发生生碰撞，则多碰撞，则多次次调整不如调整不如 在在第第一次调整时一次调整时调调整到位好（整到位好（在在不超过