运筹学基础-目标规划(1).ppt

1、第五章、目标规划,目标规划(Goal programming)是在线性规划基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个运筹学分支。目前研究较多的有线性目标规划、非线性目标规划、线性整数目标规划和0-1目标规划等。本章主要讨论线性目标规划，简称目标规划。,5.1目标规划问题的提出与目标规划模型,引例1某生物药厂需在市场上采购某种原料，现市场上有甲、乙两个等级，单价分别为2千元/kg和1千元/kg，要求采购的总费用不得超过20万元，购得原料的总重量不少于100kg，而甲级原料又不得少于50kg，问如何确定最好的采购方案（即用最少的钱、采购最多数量的原料）。,目标函数为：,一、问题的

2、提出,分析：这是一个含有两个目标的数学规划问题 设x1、x2分别为采购甲级、乙级原材料的数量（单位：kg）， y1为花掉的资金， y2为所购原料总量则：,约束条件为：,注：此规划模型是一个多目标规划模型,引例2,某企业生产、两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品需占用各设备为2、1、4、0小时，生产每件产品 需占用各设备为2、2、0、4小时，各设备用于生产这两种产品的能力分别为12、8、16、12小时，又知生产一件产品获得2元，生产一件产品 获得3元，问如何安排生产，使总的利润最大。,则该问题的数学模型表示为,但企业通常的经营目标会更实际、更多样！,这是一

3、个线性规划模型,企业的新目标：,力求使利润指标不低于12元；,考虑到市场需求，, 两种产品的生产量需保持1:1的比例；,C和D为贵重设备，严格禁止超时使用；,设备B必要时可以加班，但加班时间要控制，设备A既要求充分利用，又尽可能不加班。,等等,这些目标通过线性规划无法实现,引例3,某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如下表所示试确定计划期内的生产计划，使利润最大。,分析:设x1、x2分别是计划期内甲、乙产品的产量则该问题的数学模型为,同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标规划问题,分析：,

4、对于这样的多目标问题，线性规划很难为其找到最优方案极有可能出现： 第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的。 实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法目标规划,目标规划与线性规划相比，有以下优点：,1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题,2.线性规划是在满足所有约束条件的可行解中求得最优解。,实际问题中，往往要考虑多个目标的决策问题，这些目标可能互相矛盾，也可能没有统一的度量单位，很

5、难比较。目标规划就能够兼顾地处理多种目标的关系，求得更切合实际的解。,而在实际问题中往往存在一些相互矛盾的约束条件，如何在这些相互矛盾的约束条件下，找到一个满意解就是目标规划所要讨论的问题。,3.线性规划问题中的约束条件是不分主次、同等对待的,线性规划问题是一律要满足的“硬约束”。而在实际问题中，多个目标和多个约束条件不一定是同等重要的，而是有轻重缓急和主次之分的，如何根据实际情况确定模型和求解，使其更合实际是目标规划的任务。,4.线性规划的最优解可以说是绝对意义下的最优,为求得这个最优解，往往要花去大量的人力、物力和才力。而在实际问题中，却并不一定需要去找这种最优解。目标规划所求的满意解是指

6、尽可能地达到或接近一个或几个已给定的指标值，这种满意解更能够满足实际的需要。,目标规划更能够确切描述和解决经济管理中的许多实际问题。目前目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到广泛的应用。,二、目标规划的基本概念,1.目标值和正、负偏差变量,目标规划通过引入目标值和正、负偏差变量，可将目标函数转化为目标约束。 所谓目标值是预先给定的某个目标的一个期望值。实现值（或决策值）是当决策变量x1、x2、xn选定以后目标函数的对应值。显然，实现值和目标值之间会有一定的差异，这种差异称为偏差变量(事先无法确定的未知量)，用d和d表示。,当实际值超出目标值时，有d

7、0， d0； 当实际值未达到目标值时，有d0， d0 ； 当实际值同目标值恰好一致时， d d 0 。 因为在一次决策中，实现值不可能既超过目标值，同时又未达到目标值，所以有 d与d两者中必有一个为零。故恒有d d 0,d超出目标的差值，称正偏差变量；,d未达到目标的差值，称负偏差变量；,2.绝对约束与目标约束,绝对约束又称系统约束，是指必须严格满足的等式和不等式约束，如线性规划问题的所有约束都是绝对约束，不满足这些约束条件的解称为非可行解，所以它们是硬约束。 以例2为例，如设备C和D严格禁止超时，故有：,对那些不严格限定的约束，连同原线性规划建模时的目标函数转化为的约束，均可通过目标约束来表

8、达。,下面是如何形成目标约束,(1) 将目标函数转化为目标约束,在引入了目标值和正、负偏差变量后，可以将原目标函数加上负偏差变量 ，减去正偏差变量 ，并令其等于目标值，这样形成一个新的函数方程，把它作为一个新的约束条件，加入到原问题中去，称这种新的约束条件为目标约束。 目标约束是一种将约束和目标结合在一起的表达式，是目标规划所特有的，它把约束右端项看作要求的目标值。,比如：在实际计划工作中，利润指标往往是上级主管部门或工厂计划部门预先规定并要求实现的数值。以例2为例，力求利润指标不低于12元，这就是目标值。而工厂在安排了甲、乙两种产品的产量（决策）后，可能实现的利润额与规定的利润指标12元之间

9、会有一定差距，这个差距就是偏差变量。,这样就将目标函数则转化为目标约束,(2) 将系统约束转化为目标约束,有时也可以根据需要将绝对约束转化为目标约束，这时只须将该约束的右端项看作目标值，再引入正、负偏差变量即可。 如在例2中，考虑到市场需求，, 两种产品的生产量需保持1:1的比例；,或,此为系统约束,在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束，在给定目标值和加入正、负偏差变量之后，可以将系统约束转化为目标约束。,转化方法：,x1 x2 d 0,当产品 产量多于产品 ，有x1x2，即出现正偏差量d ，若将x1减去这个正偏差量d ，就有,x1x2 d 0,

10、因正负偏差不可能同时出现，故合在有一起设为,x1x2 d d 0,由于允许有偏差，当产品 产量小于产品 ，有x1x2，即出现负偏差量d ，若将x1加上这个负偏差量d ，就有,3目标规划的目标函数达成函数,凡满足目标约束和绝对约束的解，应如何判别它的优劣呢？ 从决策者的要求分析它总希望得到的结果与规定的目标值之间的偏差愈小愈好，由此决策者可根据自己的要求构造一个使总偏差量为最小的目标函数，这种函数就是目标规划的目标函数称为达成函数，记为,即达成函数是正、负偏变量的函数。,一般来说，可能提出的要求只能是以下三种情况之一，对应每种要求，可分别构造的达成函数是：,构造达成函数的方法,如希望产品 产量恰

11、好等于产品的产量 ，即正、负偏变量都要尽可能地小，这时函数是：,如希望产品 产量低于产品的产量 ，即允许达不到目标值,就是正偏差变量要尽可能地小,即不希望上式中的d0，这时达成函数是：,如希望产品 产量不低于产品的产量 ，即要求超过目标值，但不得低于目标值，即必须是负偏差变量尽可能地小，不希望上式中的d0，这时达成函数是：,又如中力求利润指标不低于12元，达成函数为：,设备B限制中必要时可以加班可表为：,设备A限制中既要求充分利用，又尽可能不加班可表为：,4. 目标的优先级与权系数,在一个多目标决策问题中，要找出使所有目标都达到最优的解是很不容易的；在有些情况下，这样的解根本不存在(当这些目标

12、是互相矛盾时)。实际作法是：决策者将这些目标分出主次，或根据这些目标的轻重缓急不同，区别对待。,在一个目标规划的模型中，如果两个不同目标重要程度相差悬殊，为达到某一目标可牺牲其它一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1，P2，表示，并规定Pk Pk1，符号“”表示“远大于”，表示Pk与Pk1，不是同一各级别的量，即Pk与Pk1有更大的优先权。,对属于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。,5. 满意解,目标规划问题的求解是分级进行的，首先要求满足P1级目标的解；然后再保证

13、 P1级目标不被破坏的前提下，再要求满足P2级目标的解；依次类推。总之，是在不破坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，我们称它为满意解。 之所以叫满意解，是因为对于这种来说，前面的目标是可以保证实现或部分实现的，后面的目标就不一定能保证实现。,满意解这一概念的提出是对最优化概念的一种突破，显然它更切合实际，更便于运用，因而受到广大实际工作者的欢迎而被广泛采用。,三、目标规划的数学模型及建模步骤,以上介绍的几个基本概念，实际上就是建立目标规划模型时必须分析的几个要素，把这些要素分析清楚了，目标规划的模型也就建立起来了。,设有L个目标，K个优先

14、等级(KL)的一般目标规划问题。再同一个优先级别的不同目标，它们的正负偏差变量的重要程度还可以有差别。这时还可以给同一优先级别的正负偏差变量赋予不同的权系数和 。则目标规划问题的一般数学模型可表述为,目标约束,绝对约束,目标规划问题建立模型的步骤为：,1. 根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；,2.可根据决策者的需要将某些或全部绝对约束转化为目标约束，这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可；,3.给各自目标赋予相应的优先因子Pk（k=1,2,K）变量即可；,4. 对同一优先等级中的各偏差变量，若需要，可按其重要程度不同，赋予相应的权系数。,

15、5.根据决策者需求，按下列三种情况：,a.恰好达到目标值，取,c.不允许超过目标值，取,b.允许超过目标值，取,对于由绝对约束转化而成的目标约束，也可以根据需要，按照上面三种方式，将正、负偏差变量列入达成函数中去。,例 2,某企业生产、两种产品。这两种产品都要分别在A、B、C、D四各不同设备上加工。生产每件产品需占用各设备为2、1、4、0小时，生产每件产品 需占用各设备为2、2、0、4小时，各设备用于生产这两种产品的能力分别为12、8、16、12小时，又知生产一件产品获得2元，生产一件产品 获得3元，问如何安排生产，使总的利润最大。,则该问题的数学模型表示为,这是一个线性规划模型,4x1 16

16、 4x2 12,minZ= P1 d1-,目标规划,x1x2 +d2-d2+ =0,2x1 +2x2 +d3- d3+ =12,+ P2(d2- + d2+),x1 +2x2 +d4- d4+ =8,+3 P3(d3- + d3+) + P3d4+,x1, x2 ，di-,di+ 0,第一优先级：利润不得低于12,第二优先级：生产量保持1:1的比例,第三优先级： B必要时可以加班， A既要求充分利用，又尽可能不加班,2x1 +3x2 +d1- d1+ =12,现假定企业最重要的目标是利润，不得低于12，列为第一优先级，其次目标是,产品的生产量尽量保持1:1的比例，列为第二优先级：再次是设备A、

17、B尽量不超负荷工作，设备B必要时可以加班，但加班时间要控制，设备A既要求充分利用，又尽可能不加班。列为第三优先级。在第三级中中设备A的重要性比设备B大三倍，因此目标函数中在设备A的偏差变量前冠以权系数3。对其编号目标规划模型为：,绝对约束：C和D为贵重设备，严格禁止超时使用,例 2,某计算机制造厂生产A,B,C三种型号的计算机，它们在同一生产线上装配。三种产品的工时消耗分别为5小时，8小时，12小时。生产线上每月正常运转时间是170小时。这三种产品的利润分别为每台1000元，1440元，2520元。该厂的经营目标为,P1：充分利用现有工时，必要时加班； P2：A,B,C的最低产量分别为5，5，

18、8台，并依单位工时的利润比例确定权系数； P3：生产线的加班时每月不超过20小时； P4：A,B,C的月销售指标分别为10，12，10台，并依单位工时的利润比例确定权系数。 试建立其目标规划模型。,解 设A,B,C三种产品每月的产量分别为x1,x2,x3；单位工时利润分别为1000/5=200，1440/8=180，2520/12=210。故单位工时利润比例为20：18：21。于是得到目标规划模型为,每月运转时间是170小时，充分利用现有工时，必要时加班，列为第一优先级,min Z=P1d1-,x1 +d2- d2+ 5 x2 +d3- d3+ 5 x3 +d4- d4+ 8,5x1 +8x2

19、+12x3 +d1- d1+ 170, P2(20d2- 18d3- 21d4- ),x1 +d6- d6+ 10 x2 +d7- d7+ 12 x3 +d8- d8+ 10,A,B,C的最低产量分别为5，5，8台，列为第二优先级,d1+ +d5- d5+ 20,x1, x2 ，di-,di+ 0, P3d5+,生产线的加班时每月不超过20小时，列为第三优先级,A,B,C的月销售指标分别为10，12，10台，列为第四优先级, P4(20d6- 18d7- 21d8- ),例 3 已知一个生产计划的线性规划模型为,其中目标函数为总利润，则三个约束条件均为甲、乙、丙三种资源限制。x1 ，x2为产品

20、A、B的产量，现有下列目标,第一，要求总利润必须超过2500元； 第二，虑到产品A，B受市场影响，为避免造成产品积压，其生产量不超过60件和100件； 第三，由于原料甲供应比较紧张，因此不要超过现有量140。 试建立目标规划模型。,解 由于产品A与产品B的单件利润之比为2.5:1，分别以它们为权系数，的目标规划问题,30 x1+12x2 +d1- d1+ 2500,第一，要求总利润必须超过2500元；,2x1 +x2 +d2- d2+ =140,x1, x2 ，di-,di+ 0,x1+ d3- d3+ = 60,x2 + d4- d4+ = 100,min Z=P1d1-,第二，考虑到产品A

21、，B受市场影响，为避免造成产品积压，其生产量不超过60件和100件；,+P2( 2.5 d3+d4+ ),+P3d2+,第三，由于原料甲供应比较紧张，因此不要超过现有量140。,练习,某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如下表所示试确定计划期内的生产计划，使利润最大，同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标规划问题,(1) 第1级目标是要完成或超额完成利润指标45000元； (2) 第2级目标是产品甲的生产件数不得超过200件；产品乙的生产件数不得低于250件； (3) 第3级目标是现有钢材

22、3600吨必须用完 试建立目标规划模型。,(1) 第1级目标是要完成或超额完成利润指标45000元；,70 x1+120 x2 +d1- d1+ 45000,x1 +d2- d2+ =200,x1, x2 ，di-,di+ 0,x2+ d3- d3+ 250,9.2x1 +4x2 + d4- d4+ = 3600,min Z=P1d1-,(2) 第2级目标是产品甲的生产件数不得超过200件；产品乙的生产件数不得低于250件；,(3) 第3级目标是现有钢材3600吨必须用完,+P2(7d2+ + 12d3-),+P3(d4-+d4+),4x1 +5x2 + d5- d5+ = 2000,3x1

23、+10 x2 + d6- d6+ = 3000,小结：目标规划模型与线性规划模型的异同,5.3目标规划的图解法,和线性规划问题一样，图解法虽然只适用于两个决策变量的目标规划问题，但其操作简便，原理一目了然，并且有助于理解一般目标规划问题的求解原理和过程。,图解法解题的步骤为：,1.确定各约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来；,2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；,3.求满足最高优先等级目标的解；,4.转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；,5.重复4，直到所有优先等级的目标都已审查完毕为止；,6.确定最优解或满意解。,下面通过例子来说明目标规划图解法的原理和步骤。,例1 用图解法求解目标规划问题：,解 确定各个约束条件的可行域。在x1Ox2坐标平面上，暂不