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

实用运筹学

－－运用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求解非线性规划问题的操作方法。2．内容和要求利用Excel求解二次规划、可分离规划等，题目自选。3．操作步骤（1）在Excel中建立非线性规划问题的电子表格模型；（2）利用Excel中的“规划求解”功能求解非线性规划问题；（3）结果分析；（4）在Word文档（或PowerPoint演示文稿）中撰写实验报告，包括非线性规划的数学模型、电子表格模型和结果分析等。实用运筹学

－－运用Excel建模和求解（第3版）第8章线性目标规划LinearGoalProgramming本章内容要点目标规划的基本概念和数学模型优先目标规划加权目标规划本章主要内容框架图目标规划的提出线性规划的特征是在满足一组约束的条件下，优化一个单一目标（如总利润最大或总成本最小）。而在现实生活中最优只是相对的，或者说没有绝对意义上的最优，只有相对意义上的满意。1978年诺贝尔经济学奖获得者西蒙（H.A.Simon）教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”的概念和“最大化”的行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的研究。8.1目标规划的基本概念和数学模型对于第1章的例1-1，现在工厂领导要考虑市场等一系列其他因素，提出如下三个目标：（1）根据市场信息，窗的销量有下降的趋势，故希望窗的产量不超过门产量的2倍；(希望≤)（2）车间3另有新的生产任务,因此希望车间3节省4个工时用于新的生产任务;(希望＝)（3）应尽可能达到并超过计划的每周总利润3000元。（希望≥）例8-1

在工厂三个车间的工时不能超计划使用的前提下，考虑上述三个目标，应如何安排生产，才能使这些目标依次实现？8.1目标规划的基本概念和数学模型【解】引入正偏差变量和负偏差变量目标约束1：目标约束2：目标约束3：优先目标规划的目标函数依次为：8.1目标规划的基本概念和数学模型目标规划的基本思想是化多目标为单一目标，下面引入与建立目标规划数学模型有关的概念。1．决策变量和偏差变量2．绝对约束和目标约束3．优先因子（优先级）与权系数4．目标规划的目标函数是由各目标约束的正、负偏差变量和赋予的相应的优先因子及权系数组成的。决策者的愿望是尽可能缩小与目标值的偏差，因此目标函数总是最小化。8.1目标规划的基本概念和数学模型对于例8-1，分别赋予三个目标优先因子P1、P2、P3，则例8-1的目标规划数学模型为：目标约束偏差变量8.1目标规划的基本概念和数学模型目标规划的一般数学模型为：目标约束偏差变量8.2优先目标规划在多目标决策问题中，决策者往往根据自己对目标的重视程度，赋予每个目标一定的优先级，从而将所有目标排序：优先目标规划就是按照目标的先后顺序，逐一满足优先级较高的目标，最终得到一个满意解。假如所有目标都得到满足，满意解就是最优解。

8.2优先目标规划对于例8-1，假设三个目标的优先级依次为目标1（P1）、目标2（P2）、目标3（P3）。由于有三个目标要依次考虑，所以求解要分三步进行：第一步：首先尽可能实现P1级目标，这时不考虑次级目标。在Excel中建立以优先级1的目标（目标1）的正偏差最小化为目标函数的电子表格模型：8.2优先目标规划例8-1优先级1的线性规划数学模型为：8.2优先目标规划第二步：在保证已求得的P1级目标正偏差不变的前提下考虑P2级目标。以优先级2的目标（目标2）的偏差最小化为目标函数的电子表格模型（增加一个约束条件，修改了目标函数）：8.2优先目标规划例8-1优先级2的线性规划数学模型为（修改了目标函数，增加了一个约束条件）：8.2优先目标规划第三步：在保证已求得的P1级和P2级目标偏差不变的前提下考虑P3级目标。以优先级3的目标（目标3）的负偏差最小化为目标函数的电子表格模型（再增加一个约束条件，修改了目标函数）：8.2优先目标规划例8-1优先级3的线性规划数学模型为（修改了目标函数，再增加一个约束条件）：8.2.2优先目标规划的应用举例例8-2提级加薪问题。某公司的员工工资有四级，根据公司的业务发展需要，准备招收部分新员工，并将部分在职员工的工资提升一级。该公司的员工工资（年薪）及提级前后的编制如表8-2所示。其中提级后的编制是计划编制，允许有变化。公司领导在考虑员工的升级调资方案时，依次遵守以下规定：（1）提级后在职员工的年工资总额不超过900万元；（2）提级后各级的人数不超过编制规定的人数；（3）级别2、3、4的升级人数尽可能达到现有人数的20％，且无越级提升；（4）级别4不足编制的人数可录用新员工，另外，级别1的员工中有1人要退休。该公司领导应如何拟定一个满意的员工升级调资方案。级别1级别2级别3级别4每人工资（万元/年）121086现有人数（人）10204030编制人数（人）102252308.2.2优先目标规划的应用举例【解】设x1，x2，x3，x4分别表示提升到级别1，2，3和录用到级别4的新员工人数（整数），则提级后各级的员工人数分别为：三个目标约束分别为：（1）提级后在职员工的年工资总额不超过900万元（2）提级后各级的人数不超过编制规定的人数（3）级别2、3、4的升级人数尽可能达到现有人数的20％目标函数为：8.2.2优先目标规划的应用举例对于例8-2，由于有三个目标要依次考虑，所以求解要分多步进行：第一步：首先尽可能实现P1级目标，这时不考虑次级目标。在Excel中建立以优先级1的目标（目标1）的正偏差最小化为目标函数的电子表格模型。第一次规划求解，满足了优先级1的目标的要求，即目标1（第一目标）可以实现。同时，目标2（第二目标）也实现了。第二步：在保证已求得的P1级和P2级目标偏差不变的前提下考虑P3级目标。以优先级3的目标（目标3）的负偏差最小化为目标函数的电子表格模型（增加了两个约束条件，修改了目标函数）。8.2.2优先目标规划的应用举例例8-2，第一步：首先尽可能实现P1级目标，这时不考虑次级目标。在Excel中建立以优先级1的目标（目标1）的正偏差最小化为目标函数的电子表格模型。第一次规划求解，满足了优先级1的目标的要求，即目标1（第一目标）可以实现。同时，目标2（第二目标）也实现了。8.2.2优先目标规划的应用举例例8-2，第二步：在保证已求得的P1级和P2级目标偏差不变的前提下考虑P3级目标。以优先级3的目标（目标3）的负偏差最小化为目标函数的电子表格模型（增加了两个约束条件，修改了目标函数）：8.3加权目标规划在加权目标规划中，各目标没有明确的优先级；所有偏差（含正、负偏差）都有相应的偏离系数（偏离各目标严重程度的罚数权重）；以偏差加权和（所有偏差与其罚数权重乘积的总和）为目标函数，求其最小值。因此，相对于优先目标规划，加权目标规划得到的满意解是全局的。这个满意解其实可以算作最优解，但为了避免与一般线性规划的最优解发生概念上的混淆，仍称之为满意解。8.3加权目标规划加权目标规划的数学模型8.3加权目标规划例8-3

某公司准备投产三种新产品，现在的重点是确定三种新产品的生产计划，但最好能实现管理层的三个目标：目标1：获得较高利润，希望总利润不低于125万元（希望

）。据估算，产品1、产品2、产品3的单位利润分别为12元、9元、15元。目标2：保持现有的40名工人（希望＝）。据推算，每生产1万件产品1、产品2和产品3分别需要5名、3名和4名工人。目标3：投资资金限制，希望总投资额不超过55万元（希望

）。据测算，生产1件产品1、产品2和产品3分别需要投入5元、7元和8元。8.3加权目标规划例8-3（续）但是，公司管理层意识到要同时实现三个目标是不太现实的，因此，他们对三个目标的相对重要性做出了评价。三个目标都很重要，但在重要程度上还是有些细小的差别，其重要性顺序为：目标1、目标2的前半部分（避免工人下岗）、目标3、目标2的后半部分（避免增加工人）。另外，他们为每个目标分配了表示偏离目标严重程度的罚数权重，如表8-3所示。试制订满意的投产计划。目标因素偏离目标的罚数权重（偏离系数）1总利润5（低于目标的每万元）2工人4（低于目标的每个人）2（超过目标的每个人）3投资资金3（超过目标的每万元）8.3加权目标规划例8-3的加权目标规划数学模型8.3加权目标规划例8-3加权目标规划的电子表格模型8.3加权目标规划可以利用优先目标规划对例8-3重新规划求解，假设目标优先级顺序为目标1、目标2、目标3。例8-3优先目标规划最后一步的电子表格模型：8.3.2加