非线性规划和多目标规划模型ppt课件.ppt

《非线性规划和多目标规划模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《非线性规划和多目标规划模型ppt课件.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模数学建模数学建模数学建模 从自然走向理性之路从自然走向理性之路从自然走向理性之路从自然走向理性之路 严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第第5 5讲讲 非线性规划和多目标规划模型非线性规划和多目标规划模型2/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。【主要内容】介绍非线性规划模型和多目标规划模型的主要特点和求解。【主要目的】了解非线性规划问题和多目标规划问题的建模与求解，重点在模型的建立与结果的分析第第第第5 5讲讲讲讲 非线性规划和多目

2、标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型3/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。非线性规划模型非线性规划模型(Nonlinear Programming)建立模型建立模型 非线性规划问题：目标函数或约束条件组中有一个或一个以上是变量的非线性函数。非线性规划问题的一般描述为：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型4/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违

3、纪行为或突发事件。非线性规划问题求解非线性规划问题求解 l非线性规划问题的最优值不一定在可行域的边界达到；l一般求的是局部最优解，但局部最优解并不一定是全局最优解l迭代法是主要求解方法:通常从一个初始解出发，在可行域中沿着使得目标函数降低的方向前进到下一个解。l一般求解方法：罚函数法，拉格朗日乘子法，近似规划法等,或者采用智能算法，如：遗传算法，模拟退火算法，蚁群算法等。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型5/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发

4、事件。在建模过程中，应该尽量建立线性规划模型而避免非线性规划模型。如对于问题 作变换作变换 显然显然 第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型6/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。且 相应的原非线性规划问题变换为：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型7/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。

5、例1 飞行管理问题（CUMCM95A)在高空中一个边长为160公里的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据。当一架欲进入该区域的飞机到达区域边缘时，要立即计算并判断其是否会与区域内的飞机碰撞。如果会碰撞，则要计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假定条件如下：l不碰撞的标准为任意两架飞机的距离大于8公里；l每架飞机飞行方向角调整的幅度不应超过30度；l所有飞机飞行速度均为800公里/小时；第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型8/43严格执行突发

6、事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。l欲进入飞机在到达区域边缘时，与区域内飞机的距离应在60公里以上；l最多需考虑6架飞机；l不必考虑飞机离开此区域后的状况。请你建立数学模型，对以下数据进行计算（方向角误差不超过0.01度），要求飞机飞行方向角调整的幅度尽量小。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型9/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第第第第5 5讲讲讲讲 非线性规划和多目标

7、模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型飞行管理视频1.wmv10/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。模型建立与求解 模型一：设第 i 架飞机在调整时的 方向角为i,调整角度为 i（i 1，2，6）。任意两架飞机在区域内的t时刻最短距离为dij(i,j,t)，那么问题的非线性规划模型为 目标函数也可以定义为 第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型11/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度

8、。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。我们来简单看一下其复杂程度（1）区域内飞行时间：假设飞行角度为i=i+i（2）计算任意飞机在t时刻两者的距离：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型12/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。整理后，距离可写成：其中：这样不碰撞约束条件就变为：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型13/43严格执行突发事件上报制度、

9、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。为转化成线性问题，换一个角度看不相撞条件不相撞条件：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型14/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。原非线性规划问题转化为 上述模型相比原非线性规划模型，约束条件进行了极大简化，但仍然难以直接做到线性化。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型15/43严

10、格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。此变量可直接计算得到。由于上述公式中 的取值为-，为了将上述值变换到0 2之间，取进一步考虑到角度的周期性，不碰撞的约束条件可写成：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型16/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。最终，原非线性规划问题转化为引入 即 则原问题可转化为线性规划问题。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划

11、和多目标模型非线性规划和多目标模型非线性规划和多目标模型17/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型飞行管理视频2.wmv18/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例2 钢管订购与运输（2000B）由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A132580101031201242701088107062703020203

12、0450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站（沿管道建有公路）第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型19/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。问：如何制定

13、钢管的订购和运输计划，使总费用最小 假设已知每个钢厂Si的订购范围为500,si单位，单位销售价格为pi，并且已知铁路单位运价为u，公路单位运价为v。并且铺设管道的每一段长度lj也已知。进一步假设已经计算得到每个钢厂Si运送到每个钢管铺设节点Aj的最小费用cij（最短路算法），当然知道了最小费用也就知道了运送路线第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型20/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。模型建立 设钢厂Si运送到钢管铺设节点Aj的钢管运量

14、为xij，对于每个钢管铺设节点Aj，其向左向右分别铺设量为yj和zj，则从Aj向左向右铺设的公路运输距离分别为1+yj=yj(yj+1)/2和1+zj=zj(zj+1)/2二次规划二次规划第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型21/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。引入0-1变量 设wi表示钢厂Si是否进入到钢管采购厂商中，则上述模型可变为第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和

15、多目标模型22/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。注记：（1）非线性规划中非线性部分的处理是体现创新的源头也是问题求解最关键的部分；（2）巧妙的决策变量的设计或充分挖掘问题中隐藏的约束和条件往往能起到四两拨千斤的作用；（3）充分利用模型特点，制定有针对性的求解方法能有效缓解非线性所带来的困扰。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型23/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或

16、突发事件。多目标规划模型 多目标规划问题：存在多个目标函数的带约束规划问题。往往需要对多个目标进行权衡处理。多目标规划问题的一般描述为：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型24/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。多目标规划问题求解 l多目标规划问题中多个目标可能存在以下特点：（1）存在优先级；（2）存在冲突和矛盾（3）量纲不一样（4）数量级不一样l求解多目标规划问题的主要思路是转化为单目标规划问题。第第第第5 5讲讲讲讲 非线性规划和多目

17、标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型25/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。多目标转化为单目标方法多目标转化为单目标方法（1）评价函数法；（2）功效系数法；（3）约束法；（4）分层序列法；（5）极小极大法。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型26/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。评价函数法评价函数法基本思想：构造一个关于

18、所有目标F(X)的评价函数，以此作为目标函数构造单目标规划模型。（1）线性权和法（2）均方加权法 其中 为 的下界。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型27/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。乘除法：目标函数中存在最大、最小值情况下：设 为求最小值，而为求最大值，且 设：定义单目标函数注意问题：数量级、量纲 第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型28/43严格执行突

19、发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。功效系数法功效系数法 基本思想：对每个目标构造一个功效函数反映逼近其最优目标的程度以此构造单目标。设构造功效函数 定义单目标：第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型29/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。约束法约束法 基本思想：对多个目标选定一个主要目标，而对其它目标设定期望值，在要求结果不比期望值小的情况下，求主要目标的最优值。第第第第5

20、 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型30/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。分层序列法分层序列法 基本思想：将多个目标按重要度排序，逐级构造每个目标在上级目标达到最优条件下的单目标规划问题序列，以此直到获得最后一个目标的最优值。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型31/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或

21、突发事件。极小极大法极小极大法 基本思想：采用悲观主义决策，在最不利的情况下找出最有利的策略。定义目标函数：此方法也存在数量级的问题。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型32/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例3 投资的收益与风险（CUMCM98A)市场上有n种资产（如股票、债券、）Si(i=1,2,n)供投资者选择。某公司有数额为M的一笔相当大的资金可用作一个时期内的投资。公司财务分析人员对这n种资产进行了评估，估算出在这一时期内购买

22、Si的平均收益率为ri，并预测出购买Si的风险损失率为qi。考虑到投资越分散，总的风险越小，公司确定：当用这笔资金购买若干种资产时，总体风险可用所投资的Si中最大的风险来度量。设购买Si所付交易费费率为pi，并且当购买额不超过给定值ui时，交易费按购买ui计算。另外假定同期银行存款利率为r0=5%，且既无交易费又无风险。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型33/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。请设计一种投资组合方案（用给定的资金购买若干

23、种资产或存银行生息），使得净收益尽可能大，而总体风险尽可能小。当n=4时Sir(%)q(%)p(%)u(元)S1282.51103S2211.52198S3235.54.552S4252.66.540第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型34/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。模型建立与求解 设购买Si的投资比例为xi，所需的交易费为c(xi)当然，若存银行的资金比例为x0，则c0(x0)=0，投资净收益目标为第第第第5 5讲讲讲讲 非线性

24、规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型35/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由题意，投资风险目标为：相应的约束为投资所需总资金:问题为双目标优化设投资额大于ui，则约束条件可变为:第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型36/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。目标函数则变为：模型求解（1）线性权和法：min:Q(x)

25、+R(x)S1S2S3S4Bank0000010.10.23760.39590.10790.228400.20.36890.6149000=0.30.990000第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型37/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。（2）约束法:固定风险水平，优化收益kS1S2S3S4Bank0.0050.19990.3330.090.19230.15810.010.40.5840000.020.80.1882000=0.30.99

26、0000第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型38/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。（2）约束法:固定收益水平，最小化风险kS1S2S3S4Bank0.05000010.10.07830.13060.03560.07530.67020.20.23500.39170.10680.22590.01070.3-第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型39/43严格执行突发事

27、件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。（3）分层序列法:目标优先原则l风险-利润:不考虑利润，最小风险为0l风险-利润：不考虑利润，最小风险控制在0-0.05l利润-风险：不考虑风险，最大利润0.2673267l利润-风险：不考虑风险，最大利润控制在0.2-0.27优先S1S2S3S4Bank风险优先00001风险优先210000利润优先10000利润优先20.230.390.110.220.01第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型40/43严格执行突发事件上

28、报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。（4）功效系数法l风险最小风险为0,最大为0.053l利润最小为0.05，最大为0.267构造目标函数:S1S2S3S4Bank0.370.62000第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型41/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。作业题5.1：某计算机公司生产三种型号的笔记本电脑A,B,C。三种笔记本电脑需要在复杂的装配线上生产，生产1台A,B,C型

29、号的笔记本电脑分别需要5,8,12小时。公司装配线正常的生产时间是每月1700小时。公司营业部门估计A,B,C三种笔记本电脑的利润分别是每台1000,1440,2520元，而公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标与约束：第一：充分利用正常的生产能力，避免开工不足；第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型42/43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第二：优先满足老客户的需求，A,B,C三种型号的电脑50,50,80台，同时

30、根据三种电脑的纯利润分配不同的权因子；第三：限制装配线加班时间，不允许超过200小时；第四：满足各种型号电脑的销售目标,A,B,C型号分别为100,120,100台,再根据三种电脑的纯利润分配不同的权因子；第五：装配线的加班时间尽可能少。请列出相应的目标规划模型并求解。第第第第5 5讲讲讲讲 非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型非线性规划和多目标模型数学建模数学建模数学建模数学建模 从自然走向理性之路从自然走向理性之路从自然走向理性之路从自然走向理性之路 严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。