第五章目标规划.doc

《第五章目标规划.doc》由会员分享，可在线阅读，更多相关《第五章目标规划.doc（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、,第 五 章 目 标 规 划教学目的通过本章学习，使学生明确目标规划是LP应用的拓展，与LP不同的是目标规划强调了系统性，其方法在于寻找一个尽可能满足所有目标要求的解。并要求学生掌握目标规划的解法与应用。教学方法课堂教学。教学手段讲授中要注重例题分析，说明约束条件转换与建立目标规划模型的技巧。学时分配1，2，（2学时）3（2学时）4 （2学时）共6学时重点难点重点是目标规划模型中的目标函数、系统约束、偏差变量的概念与特点；难点是对偏差变量和优先因子、加权系数的理解。作业布置第一次 目标规划的转换建模；第二次 第二次.用单纯形法求解目标规划；第三次.建立模型应用题。 辅导安排个别问题利用课间个别

2、辅导，普遍问题与学习委员联系约定时间专门安排时间进行辅导。教学内容1问题的提出与目标规划的数学模型；2目标规划的图解法；3用单纯形法求解目标规划问题与灵敏分析；4应用举例与计算机求解。 第五章 目标规划 （Goal Programming，简称GP）要求： 1、理解有关概念； 2、学会图解法； 3、学会单纯形解法； 4、学会建模； 5、举一反三，学会应用。1目标规划的数学模型 前面我们介绍的线性规划是单目标决策方法，也就是说，只用一个性能指标的大小来衡量方案的好坏。但在实际生活中，确定一个方案的好坏，往往要考虑多个目标。比如，在制定生产计划时，既要求产量高，又要求质量好，还期望成本低。又如，在

3、选择一个新工厂的厂址时，要考虑的问题有生产成本、运输费用、基建投资费用，环境污染等多种因素。而且有些指标之间往往不是那么协调，甚至相互矛盾，使得决策人难以确定最优方案。目标规划是在线性规划的基础上，为适应企业经营管理中多个目标决策的需要而逐步发展起来的。目标规划是一种多目标决策方法，它是在决策者所规定的若干目标值和要求实现这些目标值的先后顺序，以及在给定有限资源条件下，寻求总的偏离目标值最小的方案，这种方案称为满意方案。目标规划的有关概念和数学模型是在1961年由美国学者查恩斯(A.Charnes)和库伯(W.W.Cooper)首次在管理模型及线性规划的工业应用一书中提出，当时是作为解一个没有

4、可行解的线性规划而引入的一种方法。这种方法把规划问题表达为尽可能地接近预期的目标。1965年，尤吉艾吉里(Yuji Ijiri)在处理多目标问题，分析各类目标的重要性时，引入了赋予各目标一个优先因子及加权系数的概念；并进一步完善了目标规划的数学模型。表达和求解目标规划问题的方法是由杰斯基莱恩(Jashekilaineu)和桑李(Sang#Li)给出并加以改进的。下面我们用例子来介绍目标规划的数学模型和有关概念。例1 某厂生产I、II两种产品，有关数据见表。试求获利最大的生产方案。 这是一个单目标线性规划问题，设x1、x2分别为生产产品I、II的数量，可得如下线性规划模型： 由图解法可求得最优生

5、产方案是：x1*= 4，x2*= 3，Z *= 62 千元。但实际上，工厂作决策时，不仅要考虑利润，而且要考虑市场等一系列因素，如：（1）根据市场信息，产品I的销售量有下降的趋势，为此，希望产品I的产量不超过产品II的产量；（2）超计划使用原材料要高价采购，会使成本增加。为此不希望超用；（3）应尽可能充分利用设备台时数，但不希望加班；（4）应尽可能达到或超过计划利润指标56千元。这样在考虑产品决策时，需要考虑四个目标要求，这就是多目标决策问题。目标规划就是解决这种多目标决策问题的方法。下面我们用上例来说明目标规划的有关概念。 1偏差变量：目标规划中引入了正、负偏差变量d+、d-（d+、d-0）

6、。正偏差变量d+表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分。因为正、负偏差不会同时出现，即d+、d-至少有一个为零，因此恒有 d+ * d- = 0 . 2. 系统（绝对）约束和目标约束系统约束是指必须严格满足的等式或不等式，如线性规划问题中的所有约束条件都是系统约束，不满足这种约束条件的解就不是可行解，所以它们是硬性约束。目标约束是目标规划特有的等式约束，相对硬性约束来说，它是一种软性约束。当某些约束条件不是必须严格满足时，可用目标约束来表示。比如，希望利润不低于56千元，这个要求并不是必须严格大于等于56千元（即8x1+10x256），而是可以有一定的正、负偏差

7、，为此，我们可引入正、负偏差变量d+、d-，将其写成8x1+10x2-d+ + d-=56，并用min(d-)表示希望利润尽量不低于56千元。又如，希望尽量不超时使用设备，这个要求并不是必须严格小于等于10（即x1+2x210），而是可以有一定的正、负偏差，为此，我们可引入正、负偏差变量d+、d-，将其写成x1+2x2-d+ + d-=10，并用min(d+)表示希望不超时使用设备。这种等式约束就是目标约束。它把约束条件右端项看作是要追求的目标值，但在实现此目标值的过程中允许发生正偏差或负偏差，为此，在这种约束中引入了正、负偏差变量。线性规划的目标函数，在给定目标函数值时，可转化为目标约束。另

8、外，根据问题的需要，系统约束也可转化为目标约束。3. 目标的优先级与权系数 一个规划问题常常有若干个目标。但决策者在要求实现这些目标时，是有主次或轻重缓急的。凡要求第一位要实现的目标，就赋予优先因子P1 ；第二位要实现的目标赋予优先因子P2 ，并规定 Pk Pk+1 ，k =1，2，K ，表示 Pk 比 Pk+1 有更大的优先权。即首先保证P1级目标的实现，这时可以不考虑其他目标；而 P2 级目标是在实现 P1 级目标的前提下考虑的；以此类推。若要区别具有相同优先级的两个目标的差别，这时可分别赋予它们不同的权系数 wj ，这些都由决策者按照具体情况确定。4. 目标规划的目标函数 目标规划的目标

9、函数（又称准则函数）是由各目标约束中的正、负偏差变量和决策者规定的优先因子而构成的。当每一目标值确定后，决策者总是希望实现值尽可能接近目标值，也就是希望有关偏差尽量小。因此，目标规划的目标函数都是求极小值的。其基本形式有以下三种： （1）若目标要求尽量等于目标值时，这就是希望正、负偏差都尽量小，它可表示为： min Z = f（d+ + d-） （2）若目标要求尽量不超过目标值，而允许达不到目标值时，这就是希望正偏差尽量小。它可表示为： min Z = f（d+） （3）若目标要求尽量不低于目标值，而允许超过目标值时，这就是希望负偏差尽量小。它可表示为: min Z = f (d-) 对每一个

10、具体目标规划问题，可根据决策者的要求和赋予各级目标的优先因子来构造目标函数，下面用例子来说明。 例2 例1的决策者在原材料供应受严格限制的基础上还要考虑；P1：希望产品I 的产量不高于产品II的产量；P2：希望充分利用设备的有效台时数，但不希望加班；P3：希望利润不低于 56千元。求决策方案。解：按决策者的要求，这三个目标的规划问题的数学模型为： 式中：P1是希望，但不是必须严格小于，可以有偏差，于是引入，把改写为，并用 表示希望。P2是希望使用设备的台时数尽可能等于10，但不是必须严格等于10，可以有偏差，于是引入，把改写为，并用 表示希望。P3是希望利润，但不是绝对不能少，可以有偏差，于是

11、引入，把改写为，并用 表示希望利润尽量不低于56千元。胡运权书P117习题5.6例2 某厂生产A、S两种型号电脑，每种型号的电脑均需经过两道相同的工序，每台电脑所需的加工时间、销售利润及工厂每周最大加工能力见下表。如果工厂经营目标的期望值和优先等级如下：P1：每周总利润尽量不得低于10000元；P2：因合同要求,A型电脑每周至少生产10台,S型电脑每周至少生产15台；P3：希望工序的每周生产时间恰好为150小时，工序的生产时间最好用足，甚至可适当加班。根据上述要求建立这个问题的目标规划模型，不必求解。解: 设x1, x2分别是生产A、B型电脑的台数，则此问题的目标规划模型为：目标规划数学模型的

12、一般形式如下： 建立目标规划的数学模型时，决策者需要事先确定各级目标值gk、优先等级次序Pl、权系数Wlk等，它都具有一定的主观性和模糊性，可用专家评定法予以量化。目标规划与线性规划相比有以下优点：1.线性规划立足于求满足所有约束条件的最优解，而在实际问题中，可能存在相互矛盾的约束条件。目标规划可以在相互矛盾的约束条件下找到满意解。2.线性规划只能处理一个目标，而现实问题往往要处理多个目标。目标规划能统筹兼顾地处理多个目标的关系，求得更切合实际要求的解。3.线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际需要给予轻重缓急的考虑。4. 目标规划的最优解指的是尽可能地达到或接近一个或若

13、干个已给定的目标值，实际上是满意解。因此，可以认为目标规划更能确切地描述和解决经营管理中的许多实际问题。目前，目标规划已在经济计划、生产管理、市场管理、财务分析、技术参数的选择等方面得到广泛的应用。2 目标规划的图解法 方法：先画出满足系统约束的可行域和各目标偏差变量的出现方向，然后按照优先级顺序在可行域内寻找最满意的解。满意解可以是一个点、一条线段或者一个区域。对具有两个决策变量的目标规划可以用图解法求解。下面我们对前面例2用图解法求解。画图可知，满足系统约束的可行域是OAB。下面按照优先级顺序考虑目标约束，画出各级目标约束及其偏差出现的方向。P1希望，不限，所以在直线左上方的点满足要求，加

14、上系统约束，可行域缩小到OCB上；P2希望，所以在直线上的点满足要求，综合前面约束，可行域缩小到线段ED上；P3希望，不限，所以在直线右上方的点满足要求，综合前面约束，可行域缩小到线段GD上。从图中可知，该目标规划的最优解是线段GD上的所有点。因为线段GD上的点能够满足目标规划问题的所有约束条件(包括系统约束和目标约束)。但大多数目标规划问题并非如此，还可能出现非可行解，所以将目标规划问题的最优解称之为满意解。 例3 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时，预计市场每周彩色电视机的销售量是24台，每台获利80元；黑白电视机的销售量是3

15、0台，每台获利40元。该厂确定的目标是：第一优先级：充分利用装配线每周计划开动40小时；第二优先级：允许装配线加班，但每周加班时间尽量不超过10小时；第三优先级：装配电视机的数量尽量满足市场的需要。又因彩色电视机的利润高，我们取其权系数为2。 试建立该问题的目标规划模型，并求解黑白和彩色两种电视机的产量。解：设 x1 、 x2 分别表示彩色和黑白电视机的产量。这个问题的目标规划问题的数学模型为：我们用图解法求解该问题如下图所示： 3 目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型没有本质的区别，所以仍可用单纯形法求解。但考虑到目标规划的目标函数中有各级优先因子，每一级因子代表一个

16、目标，和线性规划一样，要求该级目标的最优值，需要有相应的一行检验数。为此，用单纯形法求解目标规划时，检验数要分成若干行，每一级因子各占一行，有几级因子就要分几行。下面我们用例子来说明目标规划的求解过程。例2 用单纯形法求解下面的目标规划问题 解：（1）将模型标准化，引入松弛变量x3把不等式约束变成等式，并选取d1-，x3，d2-，d3-作为基变量。把求最小值的目标函数转化求最大值的目标函数。由于检验数就是不含基变量的等价目标函数中系数，为此用消元法消去目标函数中的基变量得如下等价模型：（2）列表迭代求解基变量x1 x2 x3 d1+ d1- d2+ d2- d3+ d3-bd1-X3d2-d3

17、-2 3 0 -1 1 0 0 0 04 2 1 0 0 0 0 0 01 0 0 0 0 -1 1 0 04 5 0 0 0 0 0 -1 1908015140检验数P11 0 0 0 0 -1 0 0 0不满足P24 5 0 0 0 0 0 -1 0P3 0 0 0 -1 0 0 0 0 0d1-X3x1d3-0 3 0 -1 1 2 -2 0 00 2 1 0 0 4 -4 0 01 0 0 0 0 -1 1 0 00 5 0 0 0 4 -4 -1 160201580检验数P1 0 0 0 0 0 0 -1 0 0满足P2 0 5 0 0 0 4 -4 -1 0不满足P3 0 0 0

18、-1 0 0 0 0 0不满足d1-x2x1d3-0 0 -3/2 -1 1 -4 0 00 1 1/2 0 0 2 0 0 1 0 0 0 0 -1 0 00 0 -5/2 0 0 -6 -1 130101530jP20 0 -5/2 0 0 -6 -1 1满足P3 0 0 0 -1 0 0 0 0满足因为本例中有3个优先级因子，所以检验数要分3行，分别以P1、P2、P3表示。P1级目标是否达到最优取决于P1行中各检验数的符号，P2级目标取决于P2行中各检验数的符号，依次类推。因为初始表内P1行中最大正数为1，所以让x1进基，d2-出基。换基迭代后的表中P1行各检验数全部0，于是P1级目标已

19、达到最优。此时可将P1行中负数所在的列和P1行从表中划去。这样做不仅能保证在后面的计算中P1级目标的最优性不变，而且还能简化计算。接下来由P2行检验P2级目标，P2行中最大正数是5，所以让x2进基，x3出基。换基迭代后的P2和P3两行各检验数全部0，于是P2级和P3级目标同时实现了最优，至此，整个解题工作结束。要注意，这里的P2、P3级目标最优与P1级目标最优是不同的，因为P1级目标最优是在不考虑P2和P3目标要求下取得的，而P2和P3级的目标最优是在保证P1级目标最优的前提下取得的。自然要受到P1级的限制。从最终表中可以看出，P1级目标达到要求（因x1=15，d2-=0）；P2级目标差30百

20、元未达到（因d3-=30）；P3级目标也达到了要求，因d1+=0，d1-=30表示比目标值90还少用30。从上例的求解结果可以看出，目标规划方法是一种折中的办法，因为各级目标之间相互制约，要想同时实现每一个目标最优，是不大可能的，为此只能寻求一种折中的方案。目标规划就是寻找最优折中方案的方法。并不是求得各级目标都独立达到最优的解，而是找出一种尽可能满意的解，所以称为满意解。例3 用单纯形法求解下面的问题 解：（1）将GP模型标准化，选取d1-，d2-，d3-作为基变量。把求最小值的目标函数转化求最大值的目标函数。由于检验数就是不含基变量的等价目标函数中系数，为此用消元法消去目标函数中的基变量得

21、如下等价模型：（2）列表迭代求解 经三次迭代计算得唯一满意解为：X1=10，X2=20，d1-=d1+=d2-=d2+=d3+=0，d3-=30。胡运权书P117习题5.45.4 已知某问题的线性规划模型为：假定重新确定这个问题的目标为：P1：希望Z的值不低于1900；P2：希望资源1全部（充分）利用。请将原LP模型转换为目标规划问题的模型，不必求解。4 目标规划应用举例胡运权书P117习题5.6例4 某厂生产A、S两种型号电脑，每种型号的电脑均需经过两道相同的工序，每台电脑所需的加工时间、销售利润及工厂每周最大加工能力见下表。如果工厂经营目标的期望值和优先等级如下：P1：每周总利润尽量不得低

22、于10000元；P2：因合同要求,A型电脑每周至少生产10台,S型电脑每周至少生产15台；P3：希望工序的每周生产时间恰好为150小时，工序的生产时间最好用足，甚至可适当加班。根据上述要求建立这个问题的目标规划模型，不必求解。解: 设x1, x2分别是生产A、B型电脑的台数，则此问题的目标规划模型为：例5某厂生产A、B 两种产品，该厂有加工和装配两个车间，班生产能力以及两种产品生产工时定额和单位产值如下表所示。如果管理部门提出三级目标： P1：每班产值尽量达到75000元；P2：充分利用两个车间的工时（加工工时费用是装配工时费用的2倍）；P3：尽量减少加班工时。根据上述三级目标要求拟定一个满意

23、的生产规划。解: 依题意，设x1, x2分别是A、B产品的班产量，则此问题的目标规划模型为：利用Excel规划功能求解，取P1=106，P2=103，P3=1，求解结果如下表所示。 计算结果给出的生产方案是：生产A产品37.5件，B产品7.5件，装配车间加班5小时/班。恰好达到产值指标和工时利用指标。胡运权书P113例6 某电子厂生产录音机和电视机两种产品，分别由甲、乙两个车间生产。已知除外购件外，生产一台录音机需甲车间加工2小时、乙车间装配1小时; 生产一台电视机需甲车间加工1小时、乙车间装配3小时。这两种产品生产出来后均需经检验、销售等环节。已知每台录音机检验、销售费用需50元; 每台电视

24、机检验、销售费用需30元。又知甲车间每月可用的生产工时120小时，车间管理费用每小时为80元; 乙车间每月可用的生产工时150小时，车间管理费用每小时为20元。估计每台录音机利润为100元，每台电视机利润为75元，又估计下一年度内每月可销售录音机50台，电视机80台。工厂确定制订月度生产计划的目标为：第一优先级：检验和销售费用每月不超过4600元;第二优先级：每月售出录音机不少于50台;第三优先级：甲、乙两个车间的生产工时要得到充分利用（重要性权系数按两个车间每小时管理费用的比例确定）;第四优先级：甲车间加班不超过20小时;第五优先级：每月售出电视机不少于80台;第六优先级：两个车间加班总时间

25、要有控制（权系数分配与第三优先级相同）。试确定该厂为达到以上目标的最优月度生产计划数字。解：设X1、X2分别为每月生产录音机和电视机的台数。则根据题中给出的条件，有如下目标约束：（1）检验和销售费用的约束为 （2）每月录音机的销售量要求（3）甲、乙两个车间可用工时的约束 （4）对甲车间加班的约束 （5）每月录音机的销售量要求 （6）两个车间加班总时间要有控制，即要求：综上，该厂为达到以上目标的最优月度生产计划的数学模型为：经计算得满意解为： X1=50, X2=40，即该厂应当每月生产录音机50台，电视机40台，总利润可达8000元。例7 已知三个工厂生产的产品供应四个用户需要，各厂生产量和用

26、户的需求量以及从各厂到各用户的单位产品运输费用如表5-7所示：用表上作业法求得的最优调配方案如表5-8所示，总运费为2950元。但上述方案只考虑了运费最少，而没考虑到很多具体情况和条件。故上级部门研究后确定了制订调配方案时要考虑的七项目标，并规定重要性的次序为：P1: 第4用户为重要部门，需求量必须全部满足;P2: 供应用户1的产品中，工厂3的产品不少于100单位;P3: 为兼顾一般，每个用户满足率不低于80%;P4: 新方案总运费不超过原方案总运费的110%;P5: 因道路限制，从工厂2到用户4的路线应尽量避免分配运输任务;P6: 用户1和用户3的满足率应尽量保持平衡;P7: 力求减少总运费

27、。根据上述要求，建立目标规划的模型如下：设Xij为工厂i调配给用户j的产品数量（i=1,2,3;j=1,2,3,4）。工厂生产量的约束（1）用户需求量的约束（2）用户1的需求量中，工厂3的产品不少于100单位 （3）为兼顾一般，每个用户满足率不低于80%（4）新方案总运费不超过原方案的110%（原方案总运费为2950元）（5）道路限制，从工厂2到用户4的路线应尽量避免分配运输任务（6）用户1和用户3的满足率应尽量保持平衡（7）力求减少总的运费综合的目标函数为经计算得满意解为: P117习题5.7某种牌号的酒系由三种等级的酒兑制而成。已知各种等级酒料的每天供应量和单位成本如下：等级 供应量150

28、0单位/天，成本6元/单位;等级 供应量1500单位/天，成本6元/单位;等级 供应量1500单位/天，成本6元/单位。该种牌号的酒有三种商标（红、黄、蓝），各种商标酒的混合比及销售价中表5-10所示。商标兑制配比要求单位售价红少于10%多于50%5.5黄少于70%多于20%5.0蓝少于50%多于10%4.8为保持声誉，确定经营目标为：P1：兑制要求配比必须严格满足;P2：企业获取尽可能多的利润;P3：红色商标酒每天产量不低于2000单位。试根据这三个目标建立目标规划模型。解：用i=1，2，3表示红、黄、蓝三种商标酒，用j=1，2，3表示、三种等级酒料，Xij表示每天兑制第i种商标酒中使用第j

29、种等级酒料的单位数，则有三种酒料的供应量约束P1：兑制配比要求：P2：利润要求（利润=销售收入-成本）P3：红色商标酒每天产量要求综合上述各种约束得该问题的目标规划模型如下：例8 某厂生产两种型号的产品，产品信息如下表所示。如果每周正常工作时数为48小时，要求完成下列目标的生产计划：P1：尽量达到计划产值4000元 / 周；P2：避免加班；P3：争取外汇；P4：产品数量不要低于计划值（产品A为新型号，从发展来看会具有竞争能力，应争取多生产。两种产品产量的重要程度之比为A ：B=2 ：1）；P5：如果提前完成生产任务，早下班的时间也不要多于5小时/周。根据上述要求建立该问题的目标规划模型，不必求

30、解。解: 依题意，设x1, x2分别是A、B产品的产量，则此问题的目标规划模型为： 5 灵敏度分析 学习方法：参考课件，自己看，老师答疑，有共性的问题时，讲解。 1、 一般只对约束右端项的变化以及优先级系数的变化进行。 2、目标规划灵敏度分析的方法、原理同线性规划的灵敏度分析本质上相同。（可以参考前面灵敏度分析有关内容）P110，例4，（2）（a）也可理解为， d1-与d4+的价值系数（即优先因子）交换了一下 ，重新计算检验数，仍然都 0，最优解不改变；（b）将价值系数也即优先因子的变换直接反映到原来的最终单纯形表中，系数矩阵不用变化，重新计算检验数即可。P111，例5， （a） d1- d2- d3- d4- 1 -1 0 1 B-1 = 0 1 0 1 -1 1 1 -1 0 0 0 1只有d1- 列起作用，因此书上只写出了此列；求的情况表明原问题仍然为可行解，同P53表2-7的第一种情况，仍为最优解。 （b）求的情况表明原问题为非可行解，同P53表2-7的第三种情况，一般LP情况下应该用对偶单纯形法，但这里是目标规划的满意解，不用对偶单纯形法，用的是把原问题d3- 一行全部乘以-1 ，同时取d3+为基变量，重新用定义求检验数，继续迭代求得最优解为止。 总之，方案满足P1 P2 P3 P5各优先级目标。