《运筹学（第3版）》 课件 第7章 非线性规划

实用运筹学

－－运用Excel建模和求解（第3版）第7章非线性规划NonlinearProgramming本章内容要点非线性规划的基本概念二次规划可分离规划本章主要内容框架图7.1非线性规划的基本概念前6章所涉及规划问题的目标函数和约束条件都是线性的。但在许多实际问题中，往往会遇到目标函数或约束条件是非线性的情况，这类规划问题就是非线性规划问题。在规划问题中，如果目标函数或约束条件中有一个是决策变量的非线性函数，则这类规划问题称为非线性规划问题。本章将介绍其中一类比较简单的情形，即目标函数是决策变量的非线性函数，而约束条件是线性的。7.1非线性规划的基本概念例7-1

用一根长度为400米的绳子，围成一块矩形的菜地，问长和宽各为多少米时菜地的面积最大？【解】本问题是一个小学数学问题，现在把它当作一个规划问题来求解。（1）决策变量设矩形菜地的长为x1米，宽为x2米。（2）目标函数菜地的面积最大。（3）约束条件 ①绳子长度为400米 ②非负7.1非线性规划的基本概念例7-1的电子表格模型（采用“非线性GRG”求解方法）7.1.2非线性规划的求解方法例7-2求解复杂的非线性规划问题：7.1.2非线性规划的求解方法例7-2的电子表格模型（采用“非线性GRG”求解方法，与初始值有关）7.1.2非线性规划的求解方法正是局部最优解的存在，才使得非线性规划问题的求解要比线性规划问题的求解复杂得多。当求得一个最优解时，常常无法确定该最优解是否为全局最优解。处理复杂的有几个局部极大值的非线性规划问题，一个方法就是重复应用Excel的“规划求解”（采用“非线性GRG”求解方法），用不同的初始值进行测试，然后从这些局部最优解中挑选出最优的一个。虽然这种方法仍然不能保证找到全局最优解，但它毕竟对找到一个相当好的解给予了很大的可能。因此，对一些相对较小的问题而言，这是一种合理的方法。Excel的“规划求解”功能有一个搜索程序（算法），称为“演化”求解方法（EvolutionarySolver）。7.1.2非线性规划的求解方法例7-2的电子表格模型（采用“演化”求解方法，与初始值无关）7.2二次规划若某非线性规划的目标函数为决策变量的二次函数，而且是边际收益递减的，约束条件又都是线性的，那么称这种规划为二次规划。决策变量在有限域内变动的边际收益递减的二次规划存在最优解，且此最优解与初始值无关，即局部最优解就是全局最优解。实际上，二次规划是非线性规划中比较简单的一种，只要问题不是很复杂，Excel的“规划求解”功能就能求解。7.2二次规划在营销过程中，营销成本往往是非线性的，而且随着销量的增加，单位营销成本也在增加。也就是说，单位利润随着销量的增加而减少（边际收益递减）。例7-3

考虑非线性营销成本的例1-1。在例1-1中，增加考虑新产品（门和窗）的营销成本。原来估计每扇门的营销成本是75元、每扇窗的营销成本是200元。因此，当时估计的门和窗的单位利润分别是300元和500元。也就是说，如果不考虑营销成本，每扇门的毛利润是375元，每扇窗的毛利润是700元。已知门和窗的营销成本随着销量的增加而呈现非线性增长，若设x1为门的每周产量，x2为窗的每周产量，则门每周的营销成本为25x12，窗每周的营销成本为60x22。7.2二次规划【解】新的模型考虑了非线性的营销成本，所以在原来模型的基础上，需要修改目标函数。（1）决策变量设x1为门的每周产量，x2为窗的每周产量。（2）目标函数①门的每周销售毛利润为375x1，每周营销成本为25x12

，因此，门的每周净利润为375x1－25x12

；②窗的每周销售毛利润为700x2，每周营销成本为60x22

，因此，窗的每周净利润为700x2－60x22

。本问题的目标是两种新产品的总利润最大。7.2二次规划（3）约束条件

依旧是原有的三个车间每周可用工时限制和非负约束。

例7-3的二次规划模型：7.2二次规划例7-3的电子表格模型7.3可分离规划当利润（或成本）曲线是分段直线时，可分离规划技术可将非线性规划问题转化为相应的线性规划问题。这有助于非常有效地求解问题，并且可以对转化后的线性规划问题进行灵敏度分析。可分离规划技术为利润（或成本）曲线上的每段直线引入新的决策变量，以代替原来单一的决策变量。也就是为利润（或成本）曲线的每个线段给出一个分离的决策变量。产品每周最大产量单位利润正常生产加班生产总计正常生产加班生产门314300200窗336500100车间3的约束条件：7.3.1边际收益递减的可分离规划例7-4

需要加班的例1-1。

表7-1给出了车间1和车间2每周在正常工作时间和加班时间生产门和窗的最大数量及单位利润。车间3不需要加班，约束条件也不需要改变。7.3.1边际收益递减的可分离规划【解】（1）决策变量例1-1中的决策变量是：门的每周产量x1，窗的每周产量x2。由于加班生产的产品单位利润减少，所以利用可分离规划技术，将正常工作时间和加班时间的产量分开，引入新的决策变量：

x1R为正常工作时间内门的每周产量，

x1O为加班时间内门的每周产量；

x2R为正常工作时间内窗的每周产量，

x2O为加班时间内窗的每周产量。并且有：x1=x1R+x1O

，

x2=x2R+x2O7.3.1边际收益递减的可分离规划（2）目标函数

两种新产品的总利润最大。由于正常工作时间和加班时间生产的产品的单位利润不同，所以在目标函数中用的是新引入的决策变量。（3）约束条件①原有的例1-1的三个车间的约束还是有效的，只不过用（x1R＋x1O）代替x1，用（x2R＋x2O）代替x2。②正常工作时间和加班时间的每周最大产量约束③非负用新引入的4个决策变量7.3.1边际收益递减的可分离规划例7-4的电子表格模型7.3.1边际收益递减的可分离规划由于总产量＝每种产品在正常工作时间内和加班时间内的产量总和，也就是说，有：x1=x1R+x1O，x2=x2R+x2O所以例7-4的数学模型也可以写为：用原来的2个决策变量＋新引入的4个决策变量7.3.2边际收益递增的可分离规划例7-5

原油采购与加工问题。某公司用两种原油（A和B）混合加工成两种汽油（甲和乙），甲和乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有原油A和B的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油A。原油A的市场价为：购买量不超过400吨时的单价为10000元/吨；购买量超过400吨但不超过900吨时，超过400吨的部分单价为8000元/吨；购买量超过900吨时，超过900吨的部分单价为6000元/吨。该公司应如何安排原油的采购和加工？7.3.2边际收益递增的可分离规划例7-5的混合0-1规划模型7.3.2边际收益递增的可分离规例7-5的电子表格模型补充：WPS表格WPS表格，也有“规划求解”，在“数据”->“模拟分析”->“规划求解”。WPS的“规划求解”功能，可以完成：线性规划的求解方法：单纯线性规划，与Excel的“规划求解”相同；非线性规划的求解方法：非线性内点法，与Excel的“规划求解”求解方法（非线性GRG）不同。不同点：在“公式”中应用名称，操作不同(Excel自动引用名称，WPS表格需要手动“粘贴”名称或手动输入名称）；在“规划求解参数”对话框中应用名称，操作相同（Excel自动引用名称，但WPS表格第一次求解时目标和可变单元格没有自动引用名称，第二次求解时才自动引用名称）。Excel的“规划求解”有“演化”求解方法，但WPS表格没有。本章上机实验1．实验目的掌握利用Excel求解非线性规划问题的操作方法。