第7章-非线性规划.ppt

实用运筹学运用Excel建模和求解,第7章非线性规划NonlinearProgramming,本章内容要点,非线性规划基本概念二次规划建模与应用可分离规划建模与应用,本章节内容,7.1非线性规划基本概念7.2二次规划7.3可分离规划,本章主要内容框架图,7.1非线性规划基本概念,在前面几章中，所涉及规划问题的目标函数和约束条件都是线性的。但在许多实际问题中，往往会遇到目标函数或约束条件是非线性的情况，这类规划问题就是非线性规划问题。在规划问题中，如果目标函数或约束条件中有一个是决策变量的非线性函数，则这类规划问题称为非线性规划问题。本章要讨论的是其中一类比较简单的情形，即目标函数是决策变量的非线性函数，而约束条件全是线性的情况。,7.1非线性规划基本概念,例7.1给定一根长度为400米的绳子，用来围成一块矩形菜地，问长和宽各为多少，使菜地的面积最大？解：这是一个小学数学问题，现在把它当作一个规划问题来求解。,7.1非线性规划基本概念,(1)决策变量设矩形菜地的长为x1米，宽为x2米。(2)目标函数本题的目标是使菜地的面积最大。(3)约束条件绳子长度为400米非负约束,7.1非线性规划基本概念,例7.1的电子表格模型,7.1非线性规划基本概念,非线性规划问题存在着局部最优解和全局最优解。通常，非线性规划的解是局部极大点或极小点（即局部最优解），它使得目标函数在一部分可行域上达到极大值或极小值（局部极值），具体的解与给定的决策变量初值有关，最后只能从这些局部最优解中挑选出一个最优解作为最后的答案。正是由于局部最优解的存在，使得非线性规划问题的求解要比线性规划问题的求解复杂得多。当求得一个最优解时，常常无法确定该解是否为全局最优解。但是在某些情况下，可以保证所求得的解就是全局最优解。下面7.2节、7.3节所介绍的边际收益递减的二次规划和可分离规划就属于这种情况。,7.2二次规划,若某非线性规划的目标函数为决策变量的二次函数，约束条件又都是线性的，就称这种规划为二次规划。二次规划是非线性规划中比较简单的一类，它较容易求解。决策变量在有限域内变动的边际收益递减的二次规划问题存在最优解，且此最优解与初值无关，即局部最优解为全局最优解。实际上，二次规划是非线性规划中比较简单的一种，只要问题不是太大，利用Excel“规划求解”工具就能求解。,7.2.1非线性营销成本问题,在营销过程中，营销成本往往是非线性的，而且随着销量的增加，单位营销成本也增加，也就是说，单位利润随着销量的增加而减少（边际收益递减）。例7.2考虑非线性营销成本的例1.1。（提示:第1次和第2次印刷书上有错，第3次及以后印刷的就改为如下）在例1.1的问题中，增加考虑新产品（门和窗）的营销成本。原来估计每扇门的营销成本是75元、每扇窗的营销成本是200元。因此当时估计的门和窗的单位利润为300元和500元。也就是，如果不考虑营销成本，每扇门的毛利润为375元，每扇窗的毛利润为700元。由于门和窗的营销成本随着销量的增加而呈现非线性增长，设x1为门的每周产量，x2为窗的每周产量，而门的每周营销成本为25x12，窗的每周营销成本为60 x22。,7.2.1非线性营销成本问题,解：新的模型考虑了非线性的营销成本，所以在原来模型的基础上，需要修改目标函数。(1)决策变量设x1为门的每周产量，x2为窗的每周产量。(2)目标函数每周门的销售毛利润为375x1，门的每周营销成本为25x12，因此，每周门的净利润为375x125x12；每周窗的销售毛利润为700 x2，窗的每周营销成本为60 x22，因此，每周窗的净利润为700 x260 x22。本题的目标是总的净利润最大，因此,7.2.1非线性营销成本问题,(3)约束条件，还是原有的三个车间每周可用工时限制和非负约束。因此，该问题的数学模型为：,7.2.1非线性营销成本问题,例7.2的电子表格模型,7.2.2运用非线性规划优化有价证券投资组合,管理大量证券投资组合的职业经理人，现在都习惯于用部分基于非线性规划的计算机模型来指导他们的工作。因为投资者不仅关心预期回报，还关注着投资带来的相应风险，所以非线性规划经常用来确定投资的组合，该投资组合在一定的假设下可以获得收益和风险之间的最优平衡。这种方法主要来自于哈里马克维茨（HarryMarkowitz）和威廉夏普（WilliamSharpe）开创性的研究，他们因为该项研究而获得了1990年的诺贝尔经济学奖。,7.2.2运用非线性规划优化有价证券投资组合,这种方法是将3.2节的成本收益平衡问题非线性化。在这种情况下，成本是与投资有关的风险，收益是投资组合的预期回报。因此，该模型的一般表达形式为：最小化风险约束条件预期回报最低可接受水平这个模型关注投资组合的风险和预期收益之间的平衡。,7.2.2运用非线性规划优化有价证券投资组合,投资组合优化，就是确定投资项目中的一组最优投资比例。这里所说的“最优”，可以是在一定风险水平下使得投资回报最大，也可以是在一定的投资回报水平下使得风险最小。首先介绍关于均值、方差等概念，然后举三个例子说明在不同数据条件下投资组合优化问题的建模与求解方法。1、单项投资的期望回报率与风险2、一组投资（即多项投资）的期望回报与风险,7.2.2运用非线性规划优化有价证券投资组合,例7.3现有三个可投资的项目：股票1，股票2和债券。它们自1987年至2006年20年的投资回报率如表7-1所示。求对三个投资项目的最优投资比例，要求在总投资回报率不低于13的前提下，使得投资的总风险最小。解：数学模型：P244电子表格模型：P245结果分析：P247248,7.2.2运用非线性规划优化有价证券投资组合,例7.4现要投资三种股票（股票1、股票2和股票3）。表7-3给出了三种股票所需要的数据（这些数据主要是从前些年的股票收益中取几个样本，接着计算了这些样本的平均值、标准差和协方差，具体计算方法见例7.3。当股票的前景与前几年的不一致时，至少要对一个股票预期收益的相应估计作出调整）。如果投资者预期回报的最低可接受水平为18%，请确定三种股票的最优投资比例，使投资组合的总风险最小。解：（这种情况要求掌握）数学模型：P249电子表格模型：P250结果分析：P251252,例7.4分析过程,三种股票的投资比例（决策变量）投资组合x1股票1占总投资的比例x2股票2占总投资的比例x3股票3占总投资的比例约束条件：这些比例相加必须等于100：x1+x2+x3=100根据每种股票的预期回报率，计算整个投资组合的预期回报：总预期回报21x1+30x2+8x3投资者当前选择的最低可接受水平为：最低可接受预期回报18总风险(方差)：每种股票的独立风险(系数为方差=标准差的平方)两种股票交叉风险（系数为交叉风险协方差的2倍），公式为：Min总风险（方差）(0.252)x12+(0.452)x22+(0.052)x32+2(0.04)x1x2+2(-0.005)x1x3+2(-0.01)x2x3注意：P249表7-3给的风险系数为标准差和协方差,例7.4数学模型（二次）,决策变量：三种证券的投资比例（投资组合）x1股票1占总投资的比例x2股票2占总投资的比例x3股票3占总投资的比例目标是总风险（方差）最小：Minz(0.252)x12+(0.452)x22+(0.052)x32+2(0.04)x1x2+2(-0.005)x1x3+2(-0.01)x2x3约束条件：预期回报：21x1+30x2+8x318总比例：x1+x2+x3100且非负：x1，x2，x30,这个模型的目标函数是边际收益递减的，且是二次的，所以是一个二次规划问题。是一个比较简单的非线性规划问题。,例7.4电子表格模型,目标函数：Min总风险（方差）-非线性，公式复杂结果：总风险(方差2)=0.0238，总风险(标准差)=15.4%预期回报()18（说明投资组合最终获得的实际收益不大可能为负）,求总风险（方差）的一种简便方法,由于目标函数“总风险（方差）”的公式是非线性的，也复杂，希望找到一种不容易出错且简便的办法构造协方差矩阵（方差、协方差）总风险（方差）=SUMPRODUCT（MMULT（投资组合,协方差矩阵）,投资组合）注意:在输入此公式时,要在“投资组合”中先输入数据，如0,寻找成本（风险）和收益（预期回报）之间的最佳平衡P251,利用多次运行“规划求解”工具，将结果记录在一个表中，表格中给出了当预期回报最低可接受水平在某个范围（830，每隔2）变动时，分别获得模型最优解时的预期回报与风险（表中还包括三种股票的投资比例）画总风险（标准差）和总预期回报的X-Y平滑散点图（曲线）投资者需要在表格和曲线中决定哪个投资组合在预期回报和风险之间提供了最佳平衡。,7.2.2运用非线性规划优化有价证券投资组合,例7.5某投资公司的最优投资组合管理。某公司正在对资产进行股票的投资组合，要投资的股票包括一只科技股、一只银行股、一只能源股。公司的金融分析师已经收集了数据，并估计了有关这些股票的收益率的期望值，以及有关这些股票的标准差和相关系数信息，具体如表7-5所示。如果公司预期回报的最低可接受水平为11%，请确定三种股票的最优投资比例，使投资组合的总风险最小。解：数学模型：P253电子表格模型：P254,7.3可分离规划,在二次规划中，讨论了边际收益递减的非线性规划问题。这里讨论的仍是边际收益递减的非线性规划问题，区别在于利润或成本曲线是分段直线。对于利润或成本曲线是分段直线并且边际收益递减的非线性规划问题，可利用可分离规划技术将问题转换成相应的线性规划问题。这有助于非常有效地求解模型，并且可以对线性规划问题进行灵敏度分析。可分离规划技术为利润或成本曲线上的每一段直线引入新的决策变量，以代替原来的单一决策变量。也就是为利润曲线（成本曲线）的每个线段给出一个分离的决策变量。,7.3可分离规划,例7.6需要加班时的例1.1。表7-6给出了车间1和车间2每周在正常工作时间和加班工作时间生产门、窗的最大数量及单位利润。车间3不需要加班，约束条件也不需要改变。,7.3可分离规划,解：（1）决策变量例1.1中的决策变量是：x1为每周门的产量；x2为每周窗的产量。由于加班时的产品单位利润减少，所以利用可分离规划技术，将正常时间和加班时间的产量分开，引入新的决策变量：x1R=正常工作每周门的产量；x1O=加班工作每周门的产量；x2R=正常工作每周窗的产量；x2O=加班工作每周窗的产量。并且有：x1=x1R+x1Ox2=x2R+x2O,7.3可分离规划,（2）目标函数本问题的目标是使得总利润最大。由于正常工作和加班工作的产品单位利润不同，所以在目标函数中用的是新引入的决策变量。,（3）约束条件原有的例1.1的三个车间的约束还是有效的，只不过将x1以（x1Rx1O）代替，x2以（x2Rx2O）代替。正常工作和加班工作的每周最大产量约束非负,7.3可分离规划,例7.6的电子表格模型,7.3可分离规划,由于有“每周总产量”