非线性规划PPT演示文稿

1、第第7章章 非线性规划非线性规划ruc, information school, ye xiang实用运筹学实用运筹学运用运用excelexcel建模和求解建模和求解第第7 7章章非线性规划非线性规划nonlinear programmingnonlinear programming第第7章章 非线性规划非线性规划ruc, information school, ye xiang本章内容要点本章内容要点非线性规划基本概念非线性规划基本概念二次规划建模与应用二次规划建模与应用可分离规划建模与应用可分离规划建模与应用第第7章章 非线性规划非线性规划ruc, information school,

2、ye xiang本章节内容本章节内容7.1 7.1 非线性规划基本概念非线性规划基本概念7.2 7.2 二次规划二次规划7.3 7.3 可分离规划可分离规划第第7章章 非线性规划非线性规划ruc, information school, ye xiang本章主要内容框架图本章主要内容框架图基本概念：非线性函数非线性营销成本问题非线性规划 二次规划有价证券投资组合问题可分离规划第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.1 7.1 非线性规划基本概念非线性规划基本概念u 在前面几章中，所涉及规划问题的目标函数在前面几章中，所涉及规划问题的

3、目标函数和约束条件都是和约束条件都是线性线性的。但在许多实际问题的。但在许多实际问题中，往往会遇到目标函数或约束条件是中，往往会遇到目标函数或约束条件是非线非线性性的情况，这类规划问题就是非线性规划问的情况，这类规划问题就是非线性规划问题。题。u 在规划问题中，如果目标函数或约束条件中在规划问题中，如果目标函数或约束条件中有一个是决策变量的非线性函数，则这类规有一个是决策变量的非线性函数，则这类规划问题称为非线性规划问题。本章要讨论的划问题称为非线性规划问题。本章要讨论的是其中一类比较简单的情形，即是其中一类比较简单的情形，即目标函数是目标函数是决策变量的非线性函数，而约束条件全是线决策变量的

4、非线性函数，而约束条件全是线性性的的情况。情况。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.1 7.1 非线性规划基本概念非线性规划基本概念u例例7.17.1 给定一根长度为给定一根长度为400400米米的绳子，用来围成一块矩形菜的绳子，用来围成一块矩形菜地，问长和宽各为多少，使菜地，问长和宽各为多少，使菜地的面积最大？地的面积最大？u解：解：这是一个小学数学问题，这是一个小学数学问题，现在把它当作一个规划问题来现在把它当作一个规划问题来求解。求解。第第7章章 非线性规划非线性规划ruc, information school, ye

5、xiang7.1 7.1 非线性规划基本概念非线性规划基本概念(1) (1) 决策变量决策变量 设矩形菜地的长为设矩形菜地的长为x1米，宽为米，宽为x2米。米。(2) (2) 目标函数目标函数 本题的目标是使菜地本题的目标是使菜地的面积最大。的面积最大。(3) (3) 约束条件约束条件绳子长度为绳子长度为400400米米非负约束非负约束1 21212max z2()400s.t. , 0 x xxxxx第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.1 7.1 非线性规划基本概念非线性规划基本概念例例7.17.1的的电电子子表表格格模模型型

6、第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.1 7.1 非线性规划基本概念非线性规划基本概念u非线性规划问题存在着非线性规划问题存在着局部最优解局部最优解和和全局最优解全局最优解。通常，非线性规划的解是局部极大点或极小点（。通常，非线性规划的解是局部极大点或极小点（即局部最优解），它使得目标函数在一部分可行域即局部最优解），它使得目标函数在一部分可行域上达到极大值或极小值（局部极值），具体的解与上达到极大值或极小值（局部极值），具体的解与给定的决策变量初值有关，最后只能从这些局部最给定的决策变量初值有关，最后只能从这些局部最优解中挑选出

7、一个最优解作为最后的答案。优解中挑选出一个最优解作为最后的答案。u正是由于局部最优解的存在，使得非线性规划问正是由于局部最优解的存在，使得非线性规划问题的求解要比线性规划问题的求解复杂得多题的求解要比线性规划问题的求解复杂得多。当求。当求得一个最优解时，常常无法确定该解是否为全局最得一个最优解时，常常无法确定该解是否为全局最优解。但是在某些情况下，可以保证所求得的解就优解。但是在某些情况下，可以保证所求得的解就是全局最优解。下面是全局最优解。下面7.27.2节、节、7.37.3节所介绍的节所介绍的边际收边际收益递减益递减的二次规划和可分离规划的二次规划和可分离规划就属于这种情况。就属于这种情况

8、。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2 7.2 二次规划二次规划u若某非线性规划的若某非线性规划的目标函数目标函数为为决策变量决策变量的的二次二次函数，函数，约束条件约束条件又都是又都是线性线性的，就称这的，就称这种规划为二次规划。二次规划是非线性规划种规划为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解。中比较简单的一类，它较容易求解。u决策变量在有限域内变动的决策变量在有限域内变动的边际收益递减边际收益递减的二次规划问题存在最优解的二次规划问题存在最优解，且此最优解与，且此最优解与初值无关，即局部最优解为全局

9、最优解。初值无关，即局部最优解为全局最优解。u实际上，二次规划是非线性规划中比较简实际上，二次规划是非线性规划中比较简单 的 一 种 ， 只 要 问 题 不 是 太 大 ， 利 用单 的 一 种 ， 只 要 问 题 不 是 太 大 ， 利 用excel“excel“规划求解规划求解”工具就能求解工具就能求解。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.1 7.2.1 非线性营销成本问题非线性营销成本问题u在营销过程中，在营销过程中，营销成本往往是非线性的营销成本往往是非线性的，而且随着，而且随着销量的增加，单位营销成本也增加，也就是

10、说，单位利销量的增加，单位营销成本也增加，也就是说，单位利润随着销量的增加而减少（润随着销量的增加而减少（边际收益递减边际收益递减）。）。u例例7.2 7.2 考虑非线性营销成本的例考虑非线性营销成本的例1.11.1。在例在例1.11.1的问题中，增加考虑新产品（门和窗）的的问题中，增加考虑新产品（门和窗）的营销成营销成本本。原来估计每扇门的营销成本是原来估计每扇门的营销成本是7575元、每扇窗的营销元、每扇窗的营销成本是成本是200200元。因此当时估计的门和窗的单位利润为元。因此当时估计的门和窗的单位利润为300300元和元和500500元。也就是，如果不考虑营销成本，每扇门的毛元。也就是

11、，如果不考虑营销成本，每扇门的毛利润为利润为375375元，每扇窗的毛利润为元，每扇窗的毛利润为700700元。元。由于门和窗的营销成本随着销量的增加而呈现非线性增由于门和窗的营销成本随着销量的增加而呈现非线性增长，设长，设x1为门的每周产量，为门的每周产量， x2为窗的每周产量，而门的为窗的每周产量，而门的每周营销成本为每周营销成本为2525x12，窗的每周营销成本为，窗的每周营销成本为6060 x22。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.1 7.2.1 非线性营销成本问题非线性营销成本问题解：解：新的模型考虑了新的模型考

12、虑了非线性的非线性的营销成本，所以在原来模型营销成本，所以在原来模型的基础上，需要的基础上，需要修改目标函数修改目标函数。(1) (1) 决策变量决策变量 设设x1为门的每周产量，为门的每周产量，x2为窗的每周产量。为窗的每周产量。(2) (2) 目标函数目标函数 每周门的每周门的销售毛利润销售毛利润为为375375x1，门的每周，门的每周营销成本营销成本为为2525x12 ，因此，每周门的净利润为，因此，每周门的净利润为375375x12525x12 ； 每周窗的每周窗的销售毛利润销售毛利润为为700700 x2，窗的每周，窗的每周营销成本营销成本为为6060 x22 ，因此，每周窗的净利润

13、为，因此，每周窗的净利润为700700 x26060 x22 。 本题的目标是总的净利润最大，因此本题的目标是总的净利润最大，因此221122max z 3752570060 xxxx第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.1 7.2.1 非线性营销成本问题非线性营销成本问题(3) (3) 约束条件，还是原有的三个车间每周约束条件，还是原有的三个车间每周可用工时限制和非负约束。可用工时限制和非负约束。 因此，该问题的数学模型为：因此，该问题的数学模型为：221122121212max z 37525700604212s.t. 3

14、218, 0 xxxxxxxxxx第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.1 7.2.1 非线性营销成本问题非线性营销成本问题例例7.27.2的电子表格模型的电子表格模型第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.2 7.2.2 运用非线性规划优化运用非线性规划优化有价证券投资组合有价证券投资组合u管理大量管理大量证券投资组合证券投资组合的职业经理人，现在的职业经理人，现在都习惯于用部分基于都习惯于用部分基于非线性规划非线性规划的计算机模型的计算机模型来指导他们的工作

15、。因为投资者不仅关心预期来指导他们的工作。因为投资者不仅关心预期回报，还关注着投资带来的相应风险，所以非回报，还关注着投资带来的相应风险，所以非线性规划经常用来确定投资的组合，该投资组线性规划经常用来确定投资的组合，该投资组合在一定的假设下可以获得收益和风险之间的合在一定的假设下可以获得收益和风险之间的最优平衡。最优平衡。u这种方法主要来自于哈里这种方法主要来自于哈里 马克维茨（马克维茨（harry harry markowitzmarkowitz）和威廉）和威廉 夏普（夏普（william sharpewilliam sharpe）开创性的研究，他们因为该项研究而获得了开创性的研究，他们因为

16、该项研究而获得了19901990年的诺贝尔经济学奖年的诺贝尔经济学奖。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.2 7.2.2 运用非线性规划优化运用非线性规划优化有价证券投资组合有价证券投资组合u这种方法是将这种方法是将3.23.2节的节的成本收益平衡问题非成本收益平衡问题非线性化线性化。在这种情况下，成本是与投资有关。在这种情况下，成本是与投资有关的风险，收益是投资组合的预期回报。的风险，收益是投资组合的预期回报。u因此，该模型的一般表达形式为：因此，该模型的一般表达形式为： 最小化最小化 风险风险 约束条件约束条件 预期回报

17、预期回报最低可接受水平最低可接受水平u这个模型关注这个模型关注投资组合的风险和预期收益投资组合的风险和预期收益之间的平衡之间的平衡。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.2 7.2.2 运用非线性规划优化运用非线性规划优化有价证券投资组合有价证券投资组合u投资组合优化，就是确定投资项目中的一投资组合优化，就是确定投资项目中的一组最优组最优投资比例投资比例。这里所说的。这里所说的“最优最优”，可，可以是在一定风险水平下使得投资回报最大，以是在一定风险水平下使得投资回报最大，也可以是在一定的投资回报水平下使得风险也可以是在一定的投

18、资回报水平下使得风险最小。最小。u首先介绍关于均值、方差等概念，然后首先介绍关于均值、方差等概念，然后举举三个例子说明在三个例子说明在不同数据条件不同数据条件下投资组合优下投资组合优化问题的建模与求解方法化问题的建模与求解方法。1 1、单项投资的期望回报率与风险、单项投资的期望回报率与风险2 2、一组投资（即多项投资）的期望回报与风险、一组投资（即多项投资）的期望回报与风险第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.2 7.2.2 运用非线性规划优化运用非线性规划优化有价证券投资组合有价证券投资组合u例例7.37.3 现有三个可投资

19、的项目：股票现有三个可投资的项目：股票1 1，股，股票票2 2和债券。它们自和债券。它们自19871987年至年至20062006年年2020年的投年的投资回报率资回报率如表如表7-17-1所示。求对三个投资项目的所示。求对三个投资项目的最优投资比例，要求在总投资回报率不低于最优投资比例，要求在总投资回报率不低于1313的前提下，使得投资的总风险最小。的前提下，使得投资的总风险最小。u解：解：数学模型：数学模型：p244p244电子表格模型：电子表格模型：p245p245结果分析：结果分析：p247p247248248第第7章章 非线性规划非线性规划ruc, information schoo

20、l, ye xiang7.2.2 7.2.2 运用非线性规划优化运用非线性规划优化有价证券投资组合有价证券投资组合u例例7.47.4 现要投资三种股票（股票现要投资三种股票（股票1 1、股票、股票2 2和股票和股票3 3）。表）。表7-37-3给出了三种股票所需要的数据（这些数给出了三种股票所需要的数据（这些数据主要是从前些年的股票收益中取几个样本，接着据主要是从前些年的股票收益中取几个样本，接着计算了这些样本的计算了这些样本的平均值平均值、标准差标准差和和协方差协方差，具体，具体计算方法见例计算方法见例7.37.3。当股票的前景与前几年的不一。当股票的前景与前几年的不一致时，至少要对一个股票

21、预期收益的相应估计作出致时，至少要对一个股票预期收益的相应估计作出调整）。如果投资者预期回报的最低可接受水平为调整）。如果投资者预期回报的最低可接受水平为18%18%，请确定三种股票的最优投资比例，使投资组，请确定三种股票的最优投资比例，使投资组合的总风险最小。合的总风险最小。u解：解：（这种情况要求掌握）（这种情况要求掌握）数学模型：数学模型：p249p249电子表格模型：电子表格模型：p250p250结果分析：结果分析：p251p251252252第第7章章 非线性规划非线性规划ruc, information school, ye xiang例例7.4 7.4 分析过程分析过程u三种股票

22、的投资比例（决策变量）投资组合三种股票的投资比例（决策变量）投资组合x1股票股票1占总投资的比例占总投资的比例x2股票股票2占总投资的比例占总投资的比例x3股票股票3占总投资的比例占总投资的比例u约束条件：这些比例相加必须等于约束条件：这些比例相加必须等于100： x1+x2+x3=100u根据每种股票的预期回报率，计算整个投资组合的预期回报：根据每种股票的预期回报率，计算整个投资组合的预期回报： 总预期回报总预期回报21x1+30 x2+8x3u投资者当前选择的最低可接受水平为：投资者当前选择的最低可接受水平为：最低可接受预期回报最低可接受预期回报18u总风险总风险(方差方差)：每种股票的独

23、立风险：每种股票的独立风险(系数为系数为方差方差=标准差的平方标准差的平方)两种两种股票交叉风险（股票交叉风险（系数为系数为交叉风险交叉风险协方差的协方差的2倍倍），公式为：），公式为：min 总风险（方差）总风险（方差） (0.25 2 ) x12+ (0.45 2 ) x22+ (0.052) x32 +2(0.04)x1x2 +2(-0.005)x1x3+2(-0.01)x2x3u注意：注意：p249表表7-3给的风险系数为给的风险系数为标准差和协方差标准差和协方差第第7章章 非线性规划非线性规划ruc, information school, ye xiang例例7.4 7.4 数学模

24、型（二次）数学模型（二次）v决策变量：决策变量：三种证券的投资比例（投资组合）三种证券的投资比例（投资组合）x1股票股票1占总投资的比例占总投资的比例x2股票股票2占总投资的比例占总投资的比例x3股票股票3占总投资的比例占总投资的比例v目标是总风险（方差）最小：目标是总风险（方差）最小：min z (0.25 2 ) x12+ (0.45 2 ) x22+ (0.052) x32 +2(0.04)x1x2+2(-0.005)x1x3+2(-0.01)x2x3v约束条件：约束条件：预期回报：预期回报：21x1+30 x2+8x3 18总比例：总比例： x1 + x2+ x3100且且非负：非负：

25、 x1，x2，x3 0 0这个模型的目标函数是边这个模型的目标函数是边际收益递减的，且是二次际收益递减的，且是二次的，所以是一个二次规划的，所以是一个二次规划问题。是一个比较简单的问题。是一个比较简单的非线性规划问题。非线性规划问题。第第7章章 非线性规划非线性规划ruc, information school, ye xiang例例7.4 7.4 电子表格模型电子表格模型u目标函数：目标函数：min 总风险（方差）总风险（方差）-非线性，公式复杂非线性，公式复杂u结果：结果：总风险总风险( (方差方差 2 )=0.0238)=0.0238，总风险，总风险( (标准差标准差 )=15.4%)=

26、15.4%预期回报预期回报( ( ) 1818（说明投资组合最终获得的实际收益不大可能为负）（说明投资组合最终获得的实际收益不大可能为负）第第7章章 非线性规划非线性规划ruc, information school, ye xiang求总风险（方差）的一种简便方法求总风险（方差）的一种简便方法u由于目标函数由于目标函数“总风险（方差）总风险（方差）”的公式是非线性的，也的公式是非线性的，也复杂，希望找到一种不容易出错且简便的办法复杂，希望找到一种不容易出错且简便的办法u构造协方差矩阵（方差、协方差）构造协方差矩阵（方差、协方差）u总风险（方差）总风险（方差）= sumproduct（mmul

27、t（投资组合（投资组合, ,协方差矩阵）协方差矩阵）, ,投资组合）投资组合）u注意注意: :在输入此公式时在输入此公式时, ,要在要在“投资组合投资组合”中先输入数据，如中先输入数据，如0 0第第7章章 非线性规划非线性规划ruc, information school, ye xiang寻找成本（风险）和收益（预期寻找成本（风险）和收益（预期回报）之间的最佳平衡回报）之间的最佳平衡 p251p251u利用多次运行利用多次运行“规划求解规划求解”工具，将结果记录在一个表中，表格中给出了工具，将结果记录在一个表中，表格中给出了当预期回报最低可接受水平在某个范围（当预期回报最低可接受水平在某个范

28、围（8 83030，每隔，每隔2 2）变动时，分）变动时，分别获得模型最优解时的预期回报与风险（表中还包括三种股票的投资比例）别获得模型最优解时的预期回报与风险（表中还包括三种股票的投资比例）u画总风险（标准差）和总预期回报的画总风险（标准差）和总预期回报的x-yx-y平滑散点图平滑散点图（曲线）（曲线）u投资者需要在表格和曲线中决定哪个投资组合在预期回报和风险之间提供投资者需要在表格和曲线中决定哪个投资组合在预期回报和风险之间提供了最佳平衡。了最佳平衡。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.2.2 7.2.2 运用非线性规划优化

29、运用非线性规划优化有价证券投资组合有价证券投资组合u例例7.57.5 某投资公司的最优投资组合管理。某公司某投资公司的最优投资组合管理。某公司正在对资产进行股票的投资组合，要投资的股票包正在对资产进行股票的投资组合，要投资的股票包括一只科技股、一只银行股、一只能源股。公司的括一只科技股、一只银行股、一只能源股。公司的金融分析师已经收集了数据，并估计了有关这些股金融分析师已经收集了数据，并估计了有关这些股票的票的收益率收益率的期望值，以及有关这些股票的的期望值，以及有关这些股票的标准差标准差和和相关系数相关系数信息，具体如表信息，具体如表7-57-5所示。如果公司预期所示。如果公司预期回报的最低

30、可接受水平为回报的最低可接受水平为11%11%，请确定三种股票的最，请确定三种股票的最优投资比例，使投资组合的总风险最小。优投资比例，使投资组合的总风险最小。u解：解：数学模型：数学模型：p253p253电子表格模型：电子表格模型：p254p254第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.3 7.3 可分离规划可分离规划u在二次规划中，讨论了边际收益递减的非线性规划在二次规划中，讨论了边际收益递减的非线性规划问题。这里讨论的仍是边际收益递减的非线性规划问问题。这里讨论的仍是边际收益递减的非线性规划问题，区别在于利润或成本曲线是题，区别

31、在于利润或成本曲线是分段直线分段直线。对于利润。对于利润或成本曲线是分段直线并且边际收益递减的非线性规或成本曲线是分段直线并且边际收益递减的非线性规划问题，可利用划问题，可利用可分离规划技术将问题转换成相应的可分离规划技术将问题转换成相应的线性规划问题线性规划问题。这有助于非常有效地求解模型，并且。这有助于非常有效地求解模型，并且可以对线性规划问题进行灵敏度分析。可以对线性规划问题进行灵敏度分析。u可分离规划技术可分离规划技术为为利润或成本曲线上的利润或成本曲线上的每一段直线每一段直线引入引入新的决策变量新的决策变量，以代替原来的，以代替原来的单一决策变量单一决策变量。也。也就是为利润曲线（成

32、本曲线）的每个线段给出一个分就是为利润曲线（成本曲线）的每个线段给出一个分离的决策变量。离的决策变量。第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.3 7.3 可分离规划可分离规划u例例7.67.6 需要加班时的例需要加班时的例1.11.1。 表表7-67-6给出了车间给出了车间1 1和车间和车间2 2每周在正常工作每周在正常工作时间和加班工作时间生产门、窗的最大数量时间和加班工作时间生产门、窗的最大数量及单位利润。车间及单位利润。车间3 3不需要加班，约束条件也不需要加班，约束条件也不需要改变。不需要改变。12321 8xx产品产品每周

33、最大产量每周最大产量产品的单位利润产品的单位利润正常工作时间正常工作时间 加班时间加班时间 总计总计 正常工作时间正常工作时间加班时间加班时间门门3 31 14 4300300200200窗窗3 33 36 6500500100100第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.3 7.3 可分离规划可分离规划解：（解：（1 1）决策变量）决策变量 例例1.11.1中的决策变量是：中的决策变量是：x1为每周门的产量；为每周门的产量；x2为每周窗的产量。由于加班时的产品单位利润为每周窗的产量。由于加班时的产品单位利润减少，所以减少，所以利用

34、可分离规划技术利用可分离规划技术，将正常时间和，将正常时间和加班时间的产量分开，引入新的决策变量：加班时间的产量分开，引入新的决策变量： x1r= =正常工作每周门的产量；正常工作每周门的产量； x1o= =加班工作每周门的产量；加班工作每周门的产量； x2r= =正常工作每周窗的产量；正常工作每周窗的产量； x2o= =加班工作每周窗的产量。加班工作每周窗的产量。并且有：并且有： x1 = = x1r + + x1o x2 = = x2r + + x2o第第7章章 非线性规划非线性规划ruc, information school, ye xiang7.3 7.3 可分离规划可分离规划（2 2）目标函数）目标函数 本问题