(本科）第9章 其他常见的数学规划教学ppt课件.ppt

(本科）第9章 其他常见的数学规划教学ppt课件21世纪高等院校公共课精品教材管理运筹学管理运筹学董银红 付丽丽 编著东 北 财 经 大 学 出 版 社Dongbei University of Finance&Economics PressCONTENTS第9章 其他常见的数学规划前面几章主要对常见的数学规划问题进行了分析和总结。本章将简要介绍其他几种常见的数学规划。这些数学规划在经济管理和工程设计方面已经得到了很多应用，并且也进一步拓展了数学规划在实践问题中的发展。本章首先主要简要介绍目标规划，层次规划以及随机规划问题，希望在学习本章后，对这些数学规划模型有一些直观的映象。CONTENTS9.1 目标规划目标规划正是在线性规划的基础上为适应这种复杂的多目标最优决策的需要，而从20世纪60年代初逐步发展起来的它对众多的目标分别确定一个希望实现的目标值，然后按目标的重要程度（级别）依次进行考虑与计算，以求得最接近各目标预定数值的方案如果某些目标由于种种约束不能完全实现，它也能指出目标值不能实现的程度以及原因，以供决策者参考。CONTENTS9.1目标规划9.1.1 目标规划模型及基本概念目标规划模型及基本概念1.目标值和正、负偏差变量目标规划通过引入目标值和正、负偏差变量，可将目标函数转化为目标约束。所谓目标值是预先给定的某个目标的一个期望值，实现值或决策值是当决策变量 选定以后，该目标函数的对应值。对应不同的决策方案，实现值和目标值之间会有不同的差异，这种差异可用偏差变量来表示。正偏差变量表示实现值超过目标值的部分，记为 （ ）；负偏差变量表示实现值未达到目标值的部分，记为 （ ）。因为实现值不可能既超过目标值，同时又未达到目标值，所以恒有 。),2, 1(njxjd0dd0d0ddCONTENTS9.1目标规划2绝对约束和目标约束 绝对约束又称系统约束，是指必须严格满足的等式和不等式约束，如线性规划问题的所有约束都是绝对约束，不满足这些约束条件的解称为非可行解，所以它们是硬约束。如例9-1中，如果原有的两个约束条件不作任何处理而予以保留，则它们是绝对约束。目标约束是目标规划所特有的。对于绝对约束，把约束左端表达式看作一个目标函数，把约束右端项看作要求的目标值。在引入正、负偏差变量后，可以将目标函数加上负偏差变量 ，减去正偏差变量 ，使其等于目标值，这样形成一个新的函数方程。把它作为一个新的约束条件，加入到原问题中去，称这种新的约束条件为目标约束。ddCONTENTS9.1目标规划3优先因子与权系数在一个多目标决策问题中，要找出使所有目标都达到最优的解是很不容易的；在有些情况下，这样的解根本不存在(当这些目标是互相矛盾时)。实际作法是：决策者将这些目标分出主次，或根据这些目标的轻重缓急不同，区别对待，也就是说，将这些目标按其重要程度排序，并用优先因子 来标记，即要求第一位达到的目标赋予优先因子 ,要求第二位达到的目标赋予优先因子 ,要求第 位达到的目标赋予优先因子 。规定), 2 , 1(KkPk1PKPKPPP21CONTENTS9.1目标规划符号“ ”表示“远大于”； 表示 与 不是同一级别的量，即 比 有更大的优先权。这些目标优先等级因子也可以理解为一种特殊的系数，可以量化，但必须满足其中 是一个充分大的数。 1KKPPKP1KPKP1KP) 1, 2 , 1(1KkMPPKk0MCONTENTS9.1目标规划4.目标规划的目标函数目标规划的目标函数是根据各目标约束的正负偏差变量和赋予它们的优先因子及权系数来构造的。决策者的要求是希望得到的结果与规定的目标值之间的偏差愈小愈好，由此可根据要求构造一个使总偏差量为最小的目标函数，这种函数称为达成函数(achievement functions)，记为 ,即达成函数是正、负偏差变量的函数。),(minddfzCONTENTS9.1目标规划5.满意解目标规划问题的求解是分级进行的，首先要求满足 级目标的解；然后再保证 级目标不被破坏的前提下，再要求满足 级目标的解；依次类推。总之，是在不破坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，我们称之为“满意解”。以上介绍的几个基本概念，实际上就是建立目标规划模型时必须分析的几个要素，把这些要素分析清楚了，目标规划的模型也就建立起来了。请看下例。1P1P2PCONTENTS9.1 目标规划【例9-2】 在例9-1中，若提出下列要求：（1）第1级目标：产品B产量不低于产品A的产量；（2）第2级目标：充分利用设备台时，但不加班；（3）第3级目标：利润不小于30。试建立目标规划模型。CONTENTS9.1 目标规划综上所述， 对于L个目标，K个优先等级(KL )的一般目标规划问题。对于同一个优先级别的不同目标，它们的正负偏差变量的重要程度还可以有差别。如对于第 级目标的正负偏差变量分别赋予不同的权系数 和 （ ），则目标规划问题的一般数学模型可表述为 （）),2, 1(KkkklwklwLl, 2 , 1 LlddnjxmibxaLlqddxctsdwdwPzlljnjijijllljnjijKkLllkllklk, 2 , 1, 0, 2 , 1, 0, 2 , 1, 2 , 1,. .)(min1111CONTENTS9.1 目标规划目标规划问题建立模型的步骤为：（1） 根据问题所提出的各个目标与条件，确定目标值，列出目标约束与绝对约束；（2）根据决策者的需要将某些或全部绝对约束转化为目标约束，这时只需要给绝对约束加上负偏差变量和减去正偏差变量；（3）给各个目标赋予相应的优先因子 ；（4）对同一优先等级中的各偏差变量，根据需要可按其重要程度不同，赋予相应的权系数 和 （ ）；), 2 , 1(KkPkklwklwLl, 2 , 1CONTENTS9.1 目标规划（5）根据决策者需求，按下列三种情况：a.恰好达到目标值，取 b.允许超过目标值，取 c.不允许超过目标值，取 构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数。llddldldCONTENTS9.1 目标规划 9.1.2 求解目标规划问题的常用方法求解目标规划问题的常用方法1.求解目标规划问题的图解法图解法解题的步骤为:（1）在平面上画出所有约束条件：绝对约束条件的作图与线性规划相同；对于目标约束，先令正负偏差变量为0，画出目标约束所代表的边界线，然后在该直线上，用箭头标出正、负偏差变量值增大的方向。（2）求出第一优先等级目标的解；（3）转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；（4）重复步骤3，直到所有优先等级的目标都已审查完毕为止。CONTENTS9.1 目标规划【例例9-39-3】 对于一个生产计划的线性规划问题：其中， 、 表示A、B两种产品的周产量， 表示周工时为40的约束，每件产品的利润均为1个单位（如1000元），目标函数表示周总利润。容易看出，该线性规划问题没有可行解。0,7401510. .max2122121xxxxxtsxxz1x2x40151021xxCONTENTS9.1 目标规划现生产决策者考虑以下的目标及优先等级：(1)第1级目标：避免加班时间；(2)第2级目标：每周利润不小于10；(3)第3级目标：产品B的产量不小于7。试建立目标规划模型，并用图解法求解。CONTENTS9.1 目标规划在上述例子中，求得的结果对于线性规划问题而言是非可行解，而这正是目标规划模型与线性规划模型在求解思想上的差别，即：（1）目标规划对各个目标分级加权与逐级优化，立足于求满意解。这种思想更符合人们处理问题要分别轻重缓急保证重点的思考方式。（2）任何目标规划问题都可以找到满意解。（3）目标规划模型的满意解虽然可能是非可行解，但它却有助于了解问题的薄弱环节以便有的放矢改进工作。CONTENTS9.1 目标规划2. 求解目标规划问题的序贯式法 序贯式法是求解目标规划问题的核心思想是序贯地求解一系列单目标规划模型。也就是根据优先级别，把目标规划模型分解成单目标模型，然后依次求解。下面以例9.1建立目标规划问题：为例，说明序贯式法求解目标规划问题的步骤。3 , 2 , 1, 0,710401510. .min2133222211121332211jddxxddxddxxddxxtsdPdPdPzjjCONTENTS9.1 目标规划第一步：令k=1（k表示当前考虑的优先级别，K表示是总的优先级别数，K3）； 第二步：建立对应于第k(=1)优先级的线性规划问题： 其中目标函数 ，取第一优先级的达成函数，约束条件中可以不考虑目标函数 中未出现的偏差变量（如： 、 、 、 ）所对应的目标约束。第三步：选用适当的解法或计算机软件求解对应于优先级别为k线性规划问题，其最优解为 0，最优值 为 0。0,401510. .min1121112111ddxxddxxtsdz11mindz11mindz2d2d3d3d1d*1zCONTENTS9.1目标规划第四步：对应于第k+1(=2)优先等级，将 0作为约束条件，建立线性规划问题：第五步：转第三步。即求解得：最优解 0， ，最优值为6。继续第四步。即对应于第k+1(=3)优先等级，将 0作为约束条件，建立线性规划问题：1d2 , 1, 0,010401510. .min211222111212jddxxdddxxddxxtsdzjj11dd62d11ddCONTENTS9.1目标规划继续第三步。即求解得：最优解 0， ，最优值为7。即已得最终的满意解： ， 。此时 ，这表明最高优先等级的目标已经完全达到，而第二优先等级和第三优先等级目标都没有达到。3 , 2 , 1, 0,6, 0710401510. .min2121332222111213jddxxddddxddxxddxxtsdzjj, 0, 421xx11dd7, 632dd41x02x760321ddd，CONTENTS9.1目标规划3. 求解目标规划问题的单纯形法目标规划的数学模型结构与线性规划模型结构没有本质的区别。从目标规划的图解法可以看出，求解目标规划相当于求解多级线性规划。因此可对单纯形法进行适当修改后求解目标规划。在组织、构造具体算法时，考虑目标规划的数学模型一些特点，作以下规定：(1) 因为目标规划问题的目标函数都是求最小化，所以检验数的最优准则是 ； (2) 因为非基变量的检验数中含有不同等级的优先因子，), 2 , 1(0njzcjj), 2 , 1(1njPzckKkkjjjCONTENTS9.1目标规划解目标规划问题的单纯形法的计算步骤:(1)建立初始单纯形表。在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时， 构成了一组初始基变量，这样很容易得到初始单纯形表。置 。(2)检查当前检验数行中是否存在负数，且对应的前 行的系数为零。若有取其中最小者对应的变量为换入变量，转(3)。若无这样的检验数，则转(5)。(3)按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。1k1kCONTENTS9.1目标规划(4)按单纯形法进行基变换运算，建立新的单纯形表，返回(2)。(5)当 时，计算结束。表中的解就是满意解。否则置 ，返回（2）。 【例例9-49-4】 用单纯形法求解目标规划问题：Kk 1 kk3 , 2 , 1, 0,710401510. .min2133222211121332211jddxxddxddxxddxxtsdPdPdPzjjCONTENTS9.1目标规划9.1.3 目标规划问题的一些例子目标规划问题的一些例子【例【例9-59-5】 波德桑小姐是一个小学教师，她刚刚继承了一笔遗产，交纳税金后净得50 000美元。波德桑小姐感到她的工资已足够她每年的日常开支，但是还不能满足她暑假旅游的计划。因此，她打算把这笔遗产全部用去投资，利用投资的年息资助她的旅游。她的目标当然是在满足某些限制的条件下进行投资，使这些投资的年息最大。波德桑小姐的目标优先等级是：第一，她希望至少投资20 000美元去购买年息为6的政府公债；第二，她打算最少用5 000美元，至多用15 000美元购买利息为5的信用卡；第三，她打算最多用10 000美元购买随时可兑换现款的股票，这些股票的平均利息为8；第四，她希望给她的侄子的新企业至少投资30 000美元，她侄子允诺给她7的利息。CONTENTS9.1目标规划 购买公债的投资额（美元） 购买信用卡的投资额（美元） 购买可兑换股票的投资额（美元） 对她侄子企业的投资额（美元）这个问题的线性规划模型如下：1x2x3x4x0,30000100001500050002000050000. .07. 008. 005. 006. 0max43214322143214321xxxxxxxxxxxxxtsxxxxzCONTENTS9.1 目标规划如果用线性规划的单纯形法求解这个问题，就会发现这个问题无可行解，或者说这个问题“不可行”。只要检查一下第1、第2、第3和第6个约束，问题的不可行性是一目了然的。简而言之，波德桑小姐没有足够的钱来实现她的愿望。然而，对于波德桑小姐来说，用线性规划得出的这样一个答案是不能使她满意的。而能够使她满意的是，她希望知道即使不可能绝对地满足她的全部愿望，那么怎样才能尽可能地接近于满足她的愿望？在这样一个更为实际的许可条件下，我们假定她的目标优先等级是：P1：她的全部投资额不允许超过50 000美元，这是一个绝对约束；P2：尽可能的满足：用20 000美元购买公债，用5 00015 000美元购买信用卡。她认为购买信用卡比购买公债重要2倍；CONTENTS9.1 目标规划P3：尽可能资助她的侄子30 000美元；P4：(1) 尽可能用10 000美元购买兑换股票，(2) 每年利息的总收入尽可能达到4 000美元。那么，可以建立这个问题的目标规划模型：0)6, 2 , 1(,),4 , 3 , 2 , 1(400007. 008. 005. 006. 030000100001500050002000050000. .)()22(max774321664553442332221114321475463432211kddjxddxxxxddxddxddxddxddxddxxxxtsxddPdPdddPdPzkkjCONTENTS9.1 目标规划求解这个目标规划问题，得到的满意解是： 20 000美元 =5 000美元 =0 =25 000美元因此，我们得到了一个有意义的解，这个解能够最好地满足（即使不能绝对地满足）波德桑小姐的全部目标。事实上，在实际的决策中，决策者的某些目标不可能完全地达到，这本来也是很自然的事情。1x2x3x4xCONTENTS9.1 目标规划求解这个目标规划问题，得到的满意解是： 20,000美元 =5,000美元 =0 =25,000美元因此，我们得到了一个有意义的解，这个解能够最好地满足（即使不能绝对地满足）波德桑小姐的全部目标。事实上，在实际的决策中，决策者的某些目标不可能完全地达到，这本来也是很自然的事情。1x2x3x4xCONTENTS9.1目标规划【例例9-69-6】 一个公司需要从两个仓库调拨同一种零部件给下属的三个工厂。每个仓库的供应能力，每个工厂的需求数量以及从每个仓库到每个工厂之间的单位运费如表9-4所示（表中方格内的数字为单位运费）。CONTENTS9.1目标规划公司提出的目标要求是： P1：尽量满足工厂3的全部需求； P2 ：其他两个工厂的需求分别至少满足75； P3：总运费要求最少； P4：仓库2给工厂1 的供应量至少为1 000单位； P5：工厂1和工厂2的需求量满足程度尽可能平衡。试建立这个问题的目标规划模型。CONTENTS9.1目标规划9.1.4 用用LINGO软件求解目标规划问题软件求解目标规划问题LINGO（或LINDO）不能直接求解目标规划问题，但可以通过逐级求解线性规划的方法，求得目标规划问题的满意解。【例9-7】 用LINGO求解目标规划问题：3 , 2 , 1, 0,710401510. .min2133222211121332211jddxxddxddxxddxxtsdPdPdPzjjCONTENTS9.1目标规划 启动LINGO软件，窗口如图9-2所示。 图9-2 启动LINGO软件CONTENTS9.1目标规划 在LINGO工作区中录入以下程序：model:min=d1;10*x1+15*x2+d1_-d1=40;END其中x1、x2分别代表决策变量 、 ；d1_、d1分别代表偏差变量 、 。在菜单LINGO下点选“Solve”，或按复合键“Ctrl+S”进行求解。LINGO弹出求解结果报告，详细信息如下1x2x1d1dCONTENTS9.1目标规划CONTENTS9.1目标规划（2）对应于第二优先等级，将 0作为约束条件，建立线性规划问题：用LINGO求解，得最优解 0， ，最优值为6。具体LINGO程序及输出信息如下：1d2 , 1, 0,010401510. .min211222111212jddxxdddxxddxxtsdzjj62d11ddCONTENTS9.1目标规划LINGO程序为： model:min=d2_;10*x1+15*x2+d1_-d1=40;x1+x2+d2_-d2=10;d1=0;END其中x1、x2分别代表决策变量 、 ；d1_、d1、d2_、d2分别代表偏差变量 、 、 、 。1x2x1d1d2d2dCONTENTS9.1目标规划LINGO运算后输出为： CONTENTS9.1目标规划（3）对应于第三优先等级，将 0， 作为约束条件，建立线性规划问题：用LINGO求解，得最优解是 0， ，最优值为7。具体LINGO程序及输出信息如下： 1d62d3 , 2 , 1, 0,6, 0710401510. .min2121332222111213jddxxddddxddxxddxxtsdzjj, 0, 421xx11dd7, 632ddCONTENTS9.1目标规划LINGO程序为： model:min=d3_;10*x1+15*x2+d1_-d1=40;x1+x2+d2_-d2=10;x2+d3_-d3=7;d1=0;d2_=6;END其中x1、x2分别代表决策变量 ；d1_、d1、d2_、d2、d3_、d3分别代表偏差变 。CONTENTS9.1目标规划LINGO运算后输出为：CONTENTS9.1目标规划因此， 0， 就是目标规划的满意解。, 0, 421xx11dd7, 632ddCONTENTS9.2不确定规划在现实世界中，人们制定决策时经常会碰到不确定性现象。这种现象包括以前所熟悉的 两类：一类是随机现象，一类是模糊现象。描述、刻画随机现象的量称为随机变量，描述、刻画模糊现象的量称为模糊集。为了方便，不妨把二者分别称为随机参数和模糊参数。含有随机(模糊)参数的数学规划称为随机（模糊）规划，二者统称为不确定规划。随机(模糊)规划为解决带有随机(模糊)参数的优化问题提供了有力的工具。CONTENTS9.2不确定规划一个复杂的决策系统通常具有多维性、多样性、多功能性和多准则性，并带有随机参数或模糊参数。对于随机规划问题中所出现的随机变量，出于不同的管理目的和技术要求，采用的方法也不尽相同。首先，似乎最自然的方法是：取这些随机变量所对应的函数的概率平均值(数学期望)，从而把随机规划转化为一个确定的数学规划（只是多了几个多重积分）。这种在期望值约束下，使目标函数的概率期望达到最优的模型通常称为期望值模型。第二种方法是机会约束规划，由Charnes和Cooper提出，主要针对约束条件中含有随机变量，且必须在观测到随机变量的实现之前作出决策的问题。考虑到所作决策在不利的情况发生时可能不满足约束条件，而采用一种原则：即允许所作决策在一定程席下不满足约束条件，但该决策应使约束条件成立的概率不小于某一置信水平。CONTENTS9.2不确定规划对一些特殊情况，机会约束规划问题可以转化为等价的确定性数学规划问题，但是对较复杂的机会约束规划问题，通常很难做到这一点。目前对于该问题的求解主要利用基于随机模拟的遗传算法。有时，一个复杂的决策系统要涉及到多项任务，称之为事件， 决策者往往希望这些事件实现的概率（即机会函数）尽可能的大。为了解决这一问题，一些科技工作者提出了利用相关机会约束多目标规划和相关机会约束目标规划。简单的说，相关机会规划是使事件的机会函数在不确定环境下达到最大值的优化问题。在确定性规划以及期望值模型和机会约束规划中，当对实际问题建模以后，可行集则实际上已经确定，这就导致所给定的最优解在实际执行的时候根本无法实现，相反，相关机会约束规划并不假定可行集是确定的。CONTENTS9.2不确定规划实际上相关机会规划的可行集描述为所谓的不确定环境。虽然相关机会约束规划也给出一个确定的解，但这个解只是要求在实际问题中尽可能的实现。另外，对于处理含有模糊参数的最优化问题，模糊数学规划提供了一套有力的方法。沿用在随机规划中所提出的机会约束规划的思想，在模糊环境中，假定模糊约束成立的可能性不小于置信水平，这样可以得到模糊机会约束规划。与随机规划相类似，还可以得到其他的模糊规划形式。这些规划形式通过一系列的变换，都可以转化为清晰等价类。CONTENTS9.3 双层规划9.3.1 二层规划问题概述二层规划问题概述决策作为一门学科被人们承认只是近几十年的事。但是现在它已经成为系统科学和管理科学的重要分支。决策理论与方法来源于实际问题的需要，促进了决策理论和方法的不断完善和成熟。随着人类社会的发展，实际问题规模越来越大，结构越来越复杂，涉及到对问题作出决策的人越来越多，而且这些决策者各自处于不同的层次上，从而形成了一类具有多人参与的呈递阶结构的决策系统。这类系统具有这样的一些特征：有相对独立的决策人参与决策，他们各自都有自己的可控的决策变量；某个决策者或者某些决策者的决策一般会影响其他决策者的利益等等。CONTENTS9.3 双层规划然而，对于二层规划的研究还是与实际的应用需要很不符合。造成这种状况的因素是多方面的。其中与层次规划问题本身的性质是分不开的。层次规划问题有多个层次，以二层规划为例，它有两层，其中上层决策者独立地优化其目标函数，同时也受下层规划问题反应的影响；下层决策者在上层之后进行决策，虽然下层的决策者不能控制上层的决策，但是下层的最终决策却影响上层和全局的结果。因此该问题是非凸的并且非处处可微，这就给它的数值求解带来了极大困难。Bard证明了二层线性规划是一个NP-Hard问题，甚至寻找二层线性规划的局部最优解也是一个NP-Hard问题。CONTENTS9.3 双层规划9.3.2 二层规划问题的定义二层规划问题的定义二层规划的研究起源于经济问题，如稀有资源在各个部门之间的分配问题研究，价格控制问题研究等等。前已指出，二层规划是二层决策问题的数学模型，它是一种具有二层递阶结构的系统优化问题。上层和下层问题都有自己的目标函数和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量相关，而且还依赖于下层问题的最优解，而下层问题的最优解又受上层决策变量的影响。其一般形式为：CONTENTS9.3 双层规划其中 且F(x,y),f(x,y)分别是二层规划（BLP）问题的上层和下层目标函数，x,y分别是BLP的上层和下层决策变量。集合X，Y分别是上层和下层搜索空间。m in(,). .(,)0(1)m in(,). .(,)0 xXyYFxys t Gxyyfxys t gxy其 中是 下 面 问 题 的 解 ：1,:,:,:.nmnmpnmqF fGg