中国人民大学信息学院：《运筹学》课程教学资源（PPT课件讲稿）第十章 非线性规划

Chapter 10 Nonlinear Programming 非线性规划 Data model and decisions 数据、模型与决策 第10章 Nonlinear Programming 非线性规划 RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 Data, Model and Decisions 数据、模型与决策 第10章 Nonlinear Programming 非线性规划

Chapter 10 Nonlinear Programming 本章内容 非线性规划 10.1非线性规划的挑战 要求掌握: 102边际收益递减的非线性规划|1、边际收益递减 103可分离规划 的二次规划 104复杂非线性规划问题 2、可分离规划 10.5 Evolutionary Solver软件和遗传算法(了解即可) 10.6小结 案例10.3跨国投资 RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 本章内容 10.1 非线性规划的挑战 10.2 边际收益递减的非线性规划 10.3 可分离规划 10.4 复杂非线性规划问题 10.5 Evolutionary Solver 软件和遗传算法（了解即可） 10.6 小结 案例10.3 跨国投资 要求掌握： 1、边际收益递减 的二次规划 2、可分离规划

Nonlinear programming Chapter 10 非线性规划P394 Nonlinear Programming 非线性规划 线性规划的目标函数和约束条件都是其自变量(决策变 量X)的线性函数,如果目标函数或约束条件中包含有 自变量(决策变量X)的非线性函数,则这样的规划问 题就属于非线性规划。 例1:给定一根长度为400米的绳子,用来围成一块矩形 菜地,问长和宽各为多少,使菜地的面积最大? 令假设长为x米,宽为x2米,Max面积S=x1*x2 令绳子长度(周长)约束:2(x+x2)=400且x1x2≥0 例2:对于一般的产品来说,提高价格将会导致需求的 减少,反之,会使需求增加。 ☆假设d=产品的年需求量,p=单价,并且公司认为需求价格的 关系如下:d=800-10,这里20Sp≤70。 ☆则总收益Po年需求量×单价=d×P=(800-10p)P 冷求p=?,总收益P最大,此时的年需求量d是多少?(40, 16000,400) RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 Nonlinear Programming 非线性规划 P394 ➢ 线性规划的目标函数和约束条件都是其自变量（决策变 量X）的线性函数，如果目标函数或约束条件中包含有 自变量（决策变量X）的非线性函数，则这样的规划问 题就属于非线性规划。 ➢ 例1：给定一根长度为400米的绳子，用来围成一块矩形 菜地，问长和宽各为多少，使菜地的面积最大？ ❖ 假设长为x1米，宽为x2米，Max 面积S=x1 *x2 ❖ 绳子长度（周长）约束：2（x1+x2）＝400 且x1 ,x2  0 ➢ 例2：对于一般的产品来说，提高价格将会导致需求的 减少，反之，会使需求增加。 ❖ 假设d＝产品的年需求量，p＝单价，并且公司认为需求价格的 关系如下：d＝800－10p，这里20  p  70。 ❖ 则总收益Profit＝年需求量×单价＝d×p＝（800－10p）p ❖ 求p＝？，总收益P最大，此时的年需求量d是多少？（40， 16000，400）

Nonlinear programming Chapter 10 非线性规划(补充) Nonlinear Programming 非线性规划 非线性规划的解经常是局部极大点或极小点(局部最优解 ),它使得目标函数在一部分可行域上达到极大值或极小 值(局部极值),具体的解与给定的决策变量初值有关( 例子请见P403图107),我们只能从这些局部最优解中挑 选出一个最优解作为最后的答案(我们无法判断一个具体 的非线性规划问题到底有几个局部最优解)。 有一些理论来判别局部最优解就是全局最优解(如判断 Min目标函数f(X)是否是凸函数,如果是,则该非线性规 划就是凸规划(目标Min),其局部最优解就是全局最优 解,容易想到,线性规划也是一种凸规划(目标Min时) 。反之,对于Max目标函数(X)要判断是否是凹函数(利 润函数图形上任意两点的连线都在这个图形的下方),凹 规划,我们这章节讲的是目标函数是Max利润P的凹函数 边际利润递减的情况:分为连续和分段直线P398) RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 Nonlinear Programming 非线性规划（补充） ➢ 非线性规划的解经常是局部极大点或极小点（局部最优解 ），它使得目标函数在一部分可行域上达到极大值或极小 值（局部极值），具体的解与给定的决策变量初值有关（ 例子请见P403图10.7），我们只能从这些局部最优解中挑 选出一个最优解作为最后的答案（我们无法判断一个具体 的非线性规划问题到底有几个局部最优解）。 ➢ 有一些理论来判别局部最优解就是全局最优解（如判断 Min 目标函数f(X)是否是凸函数，如果是，则该非线性规 划就是凸规划（目标Min），其局部最优解就是全局最优 解，容易想到，线性规划也是一种凸规划（目标Min时） 。反之，对于Max 目标函数f(X)要判断是否是凹函数（利 润函数图形上任意两点的连线都在这个图形的下方），凹 规划，我们这章节讲的是目标函数是 Max 利润P的凹函数 －－边际利润递减的情况：分为连续和分段直线P398）

二次规划(补充) Chapter 10 Nonlinear Programming 非线性规划 >若某非线性规划的目标函数为自变量X的二次 函数,约束条件全是线性函数,称这种规划为 次规划 二次规划是非线性规划中比较简单的一类,它 比较容易求解。很多方面的问题都可以抽象成 次规划的模型(10.2节书上举的2个例子全是 次凹规划) 二次规划是凸规划(目标为Min时)或凹规划 (目标为Max时),其局部最优解就是全局最 优解。 RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 二次规划（补充） ➢ 若某非线性规划的目标函数为自变量X的二次 函数，约束条件全是线性函数，称这种规划为 二次规划。 ➢ 二次规划是非线性规划中比较简单的一类，它 比较容易求解。很多方面的问题都可以抽象成 二次规划的模型（10.2节书上举的2个例子全是 二次凹规划）。 ➢ 二次规划是凸规划（目标为Min时）或凹规划 （目标为Max时），其局部最优解就是全局最 优解

10 10.1非线性规划的挑战P396N0mmr g 非线性规划 非比例关系的挑战P396 1、线性规划的比例性假设:各种活动对目标函 数值的贡献与活动水平成比例,也就是目标函数 中各和项是系数与决策变量的乘积。 2、违背比例性假设:每增加一个单位的活动与 前面第一个单位创造的收益不同,也就是线性规 划活动的收益与活动的水平不成比例(目标函数 非线性) 3、P398四种活动水平X和其利润P的关系曲线( 边际收益不同,斜率不同),边际收益递减的 利润曲线称为凹函数(函数图形上的任意两点的 连线都在这个图形的下方)。 RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 10.1 非线性规划的挑战P396 ➢ 非比例关系的挑战P396 1、线性规划的比例性假设 :各种活动对目标函 数值的贡献与活动水平成比例，也就是目标函数 中各和项是系数与决策变量的乘积。 2、违背比例性假设：每增加一个单位的活动与 前面第一个单位创造的收益不同，也就是线性规 划活动的收益与活动的水平不成比例（目标函数 非线性） 3、 P398四种活动水平X和其利润P的关系曲线（ 边际收益不同，斜率不同 ），边际收益递减的 利润曲线称为凹函数（函数图形上的任意两点的 连线都在这个图形的下方）

建立非线性公式的挑战P399 Chapter 10 Nonlinear Programming 非线性规划 利润曲线(或成本曲线)的二次形式使用很广泛 利润曲线(公式):运用 Excel曲线拟合方法,步骤如下( P400-402): 1.作XY散点图(取消图例,省略标题) 2.用鼠标激活散点图:把鼠标放在任一数据点上,单击鼠标右键 ,打开菜单,在菜单栏里选择“添加趋势线”选项,打开“添 加趋势线”对话框; 3.在“类型Type”页面,选择相应的回归分析类型,如多项式(阶 数:2),Bxce将显示一条拟合数据点的二次曲线 4.在“选项0 ptions”页面的下部,选择“显示公式”和“显示R平 方值”选项,单击“确定0K”按钮,便得到趋势回归图、公式以 及R平方值(R平方值:用来说明用自变量解释因变量变差的程 度,以测量同因变量y的拟合效果,R越接近1越好。本例中: R2=0.9862,表明用自变量X可解释因变量变差的98.62% 5.最后的拟合曲线为 y=-0.3002x2+5.661x+6.1477 RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 建立非线性公式的挑战P399 ➢ 利润曲线（或成本曲线）的二次形式使用很广泛。 ➢ 利润曲线(公式):运用Excel曲线拟合方法，步骤如下（ P400－402）： 1. 作XY散点图（取消图例，省略标题）； 2. 用鼠标激活散点图：把鼠标放在任一数据点上，单击鼠标右键 ，打开菜单，在菜单栏里选择“添加趋势线”选项，打开“添 加趋势线”对话框； 3. 在“类型Type”页面，选择相应的回归分析类型，如多项式（阶 数：2），Excel将显示一条拟合数据点的二次曲线 4. 在“选项Options”页面的下部，选择“显示公式”和“显示R平 方值”选项，单击“确定OK”按钮，便得到趋势回归图、公式以 及R平方值（R平方值：用来说明用自变量解释因变量变差的程 度，以测量同因变量y的拟合效果， R 2越接近1越好。本例中： R 2 = 0.9862，表明用自变量X可解释因变量变差的98.62%）。 5. 最后的拟合曲线为 y = -0.3002x2 + 5.661x + 6.1477

Chapter 10 Nonlinear Programming 非线性规划 非线性规划模型求解的挑战P402 >非线性规划的解经常是局部极大点或极小点( 局部最优解),它使得目标函数在一部分可行 域上达到极大值或极小值(局部极值),具体 的解与给定的决策变量初值有关(例子请见 P403图10.7),我们只能从这些局部最优解中 挑选出一个最优解作为最后的答案(我们无法 判断一个具体的非线性规划问题到底有几个局 部最优解) RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 非线性规划模型求解的挑战P402 ➢ 非线性规划的解经常是局部极大点或极小点（ 局部最优解），它使得目标函数在一部分可行 域上达到极大值或极小值（局部极值），具体 的解与给定的决策变量初值有关（例子请见 P403图10.7），我们只能从这些局部最优解中 挑选出一个最优解作为最后的答案（我们无法 判断一个具体的非线性规划问题到底有几个局 部最优解）

Chapter 10 Nonlinear Programming 非线性规划 102边际收益递减的非线性规划P405 本节中,集中讨论有以下特征的非线性规划问题 1.与线性规划模型的约束条件相同(线性) 2.目标函数为非线性函数(二次) 3.违背线性规划比例性假设的每一活动表现为 边际收益递减(要求的最大化的目标函数是 凹的,而要求的最小化的目标函数是凸的) 这是非线性规划问题中比较简单的类型,使用 Exce1的规划求解 Solver就可以求解,因为它获得 的解能保证是该类问题的最优解。 RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 10.2 边际收益递减的非线性规划 P405 ➢ 本节中，集中讨论有以下特征的非线性规划问题 1. 与线性规划模型的约束条件相同(线性) 2. 目标函数为非线性函数（二次） 3. 违背线性规划比例性假设的每一活动表现为 边际收益递减（要求的最大化的目标函数是 凹的，而要求的最小化的目标函数是凸的） ➢ 这是非线性规划问题中比较简单的类型，使用 Excel的规划求解Solver就可以求解，因为它获得 的解能保证是该类问题的最优解

伟恩德玻璃公司案例研究的续篇: Chapter 10 非线性营销成本的伟恩德问题P405 Nonlinear Programming 非线性规划 门的营销成本=$25D2,每扇门的毛利润为$375(原来每扇门的净利润为$300) ,因此,每周门的净利润大致为 门的净利润=375D-25D2 同样,窗的营销成本=$6667W2,窗的毛利润为$700W(原来窗的净利润为 $500W),因此: 窗的净利润=700W-66.7W P407图10.10显示了两种产品的利润曲线,两者都是具有递减的边际利润 Wyndor Problem With Nonlinear Marketing Costs 目标函数(非线性):Max利润=375D-25D2+700W-66.67W2 用Exce的“规划求解”,只需在选项中,不选中“采用线性模型”即可 P409 非线性营销成本的伟恩德问题 DOors wiNdows 单位毛利 375 每个产品所需生产时数使用时数每周可得时数 0 3214 8.357< 工厂3 18000<= 18 Doors 窗 Windows 每周生产量 214 4.179 销售毛利润」$4,130 营销成本 258 s1,164 总营销成本$1,422 总利润 RuC Information School, Ye Xiang 2007

Chapter 10 Nonlinear Programming 非线性规划 RUC Information School ,Ye Xiang ,2007 伟恩德玻璃公司案例研究的续篇： 非线性营销成本的伟恩德问题 P405 ➢ 门的营销成本＝$25D2，每扇门的毛利润为$375（原来每扇门的净利润为$300 ） ，因此，每周门的净利润大致为： 门的净利润＝ 375D－25D2 ➢ 同样，窗的营销成本＝$66.67W2，窗的毛利润为$700W（原来窗的净利润为 $500W ），因此： 窗的净利润＝ 700W － 66.67W2 ➢ P407 图10.10显示了两种产品的利润曲线，两者都是具有递减的边际利润。 目标函数（非线性）：Max 利润＝375D－25D2 ＋700W－66.67W2 ➢ 用Excel的“规划求解”，只需在选项中，不选中“采用线性模型”即可。 Wyndor Problem With Nonlinear Marketing Costs P409 非线性营销成本的伟恩德问题 门Doors 窗Windows 单位毛利 $375 $700 使用时数 每周可得时数 工厂 1 1 0 3.214 < = 4 工厂 2 0 2 8.357 < = 12 工厂 3 3 2 18.000 < = 18 门Doors 窗Windows 每周生产量 3.214 4.179 销售毛利润 $4,130 营销成本 $258 $1,164 总营销成本 $1,422 总利润 $2,708 每个产品所需生产时数