运筹学第五章目标规划课件.ppt

1、第五章第五章 目标规划目标规划东 北 林 业 大 学5.15.1问题的提出与目标规划模型问题的提出与目标规划模型5.25.2目标规划的图解分析目标规划的图解分析法法5.35.3应用举例应用举例5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学一、目标规划问题的提出一、目标规划问题的提出线性规划的局限性线性规划的局限性P P133133：第一，它要求问题的解必须满足全部约束条件，但实际问题中第一，它要求问题的解必须满足全部约束条件，但实际问题中对某些约束有一定程度的违背是允许的；对某些约束有一定程度的违背是允许的；第二，只能处理单目标的优化问题，因此线性规划模

2、型中人为第二，只能处理单目标的优化问题，因此线性规划模型中人为地将一些次要目标转为约束。而实际问题中，目标和约束可以地将一些次要目标转为约束。而实际问题中，目标和约束可以互相转化，处理时不一定要严格区分。互相转化，处理时不一定要严格区分。第三，线性规划中各个约束条件第三，线性规划中各个约束条件(实际上也可看作目标实际上也可看作目标)都处于都处于同等重要地位，但现实问题中，各目标的重要性既有层次上的同等重要地位，但现实问题中，各目标的重要性既有层次上的差别，同一层次中又可以确权重上的区分；差别，同一层次中又可以确权重上的区分；第四，线性规划寻求最优解，但很多实际问题中只需找出满意第四，线性规划寻

3、求最优解，但很多实际问题中只需找出满意解就可以。解就可以。001202410032.4621212121,xxxxxxtsxxzmax5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学为克服为克服LPLP的缺陷，美国学者的缺陷，美国学者19611961年提出了目标规划的有关概念年提出了目标规划的有关概念和模型。和模型。19761976年伊格尼齐奥发表了年伊格尼齐奥发表了目标规划及其扩展目标规划及其扩展一书，一书，系统归纳总结了目标规划的理论和方法。系统归纳总结了目标规划的理论和方法。定义：定义：目标规划是求一组变量的值，在满足一组目标目标规划是求一组变量的值

4、，在满足一组目标约束（也称柔性约束）和资源约束（也称刚性约束）约束（也称柔性约束）和资源约束（也称刚性约束）条件下，实现管理目标和实际可能完成的目标之间的条件下，实现管理目标和实际可能完成的目标之间的偏差最小。偏差最小。5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学二、目标规划模型二、目标规划模型例例5.1 5.1 问题的提出问题的提出：对例对例1.11.1 某企业生某企业生产两种产品，需要两种原料产两种产品，需要两种原料,有关数据有关数据见表。如何安排生产计划可使总的收见表。如何安排生产计划可使总的收益最大。益最大。企业管理人员又提出如下目企业管理人员

5、又提出如下目标要求标要求:产品产品资源资源甲甲 乙乙资源资源拥有量拥有量 100 100 120 120单件收益单件收益 （千元）（千元）第三目标第三目标P P3 3：A A资源要充分利用，但不能超额。资源要充分利用，但不能超额。B B资源可超额利用，资源可超额利用，但最多不能超额但最多不能超额8 8个单位。个单位。A A、B B资源的权系数分别为资源的权系数分别为7 7和和3 3。由市场预测可知，甲、乙的产量不能超过由市场预测可知，甲、乙的产量不能超过4040和和3030件。如何制定件。如何制定满足上述目标要求的生产计划方案满足上述目标要求的生产计划方案.第一目标第一目标P P1 1：收益不

6、低于：收益不低于180180千元；千元；第二目标第二目标P P2 2：甲乙的产量尽量满足：甲乙的产量尽量满足5:35:3的关系；的关系；试建立该问题的目标规划模型。试建立该问题的目标规划模型。5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学目的目的-制定一个制定一个生产计划方案生产计划方案。（甲乙各生产多少件）（甲乙各生产多少件）目标目标-管理目标和实际可能完成的目标之间的偏差最小。管理目标和实际可能完成的目标之间的偏差最小。（目标规划模型中的目标均如此表示目标规划模型中的目标均如此表示）设置变量：设置变量：决策变量，决策变量，x1,x2分别表示产品甲、乙

7、的产量。分别表示产品甲、乙的产量。偏差变量，偏差变量有正负之分，用正偏差偏差变量，偏差变量有正负之分，用正偏差d d+和负偏差和负偏差d d-表表示。示。d d+表示超过目标值的部分；表示超过目标值的部分；d d-表示不足目标值的部分。表示不足目标值的部分。显然有显然有d d-d d+=0 0。解：解：5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学P P1 1:收益不低于收益不低于180180千元；千元；P P2 2:甲乙的产量尽量满足甲乙的产量尽量满足5:35:3的关系；的关系；P P3 3:A:A资源要充分利用，但不能超额。资源要充分利用，但不能超额

8、。B B资源可资源可超额利用，但最多不能超额超额利用，但最多不能超额8 8个单位。个单位。A A、B B资资源的权系数分别为源的权系数分别为7 7和和3 3。约束条件：约束条件：P P1 1：6 6x1 1+4+4x2 2+=180 =180d d1 1-d d1 1+(d(d1 1-0)0)P P2 2：3 3x1 1-5-5x2 2+=0+=0d d2 2-d d2 2+(d(d-，d d2 2+0)0)P P3 3：2 2x1 1+3+3x2 2+=100+=100d d3 3-d d3 3+(d(d3 3-，d d3 3+0)0)4 4x1 1+2+2x2 2+=128+=128d d

9、4 4-d d4 4+(d(d4 4+0)0)（2 2）系统约束（刚性约束）系统约束（刚性约束）x1 1 40 40 x2 2 30 30（3 3）变量非负限制）变量非负限制（1 1）目标约束（柔性约束）目标约束（柔性约束）1,2,3,4lddxxll,0,215.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学433221)()(minddddddz目标函数：目标函数：管理目标和实际可能完成的目标之间的偏差最小。管理目标和实际可能完成的目标之间的偏差最小。是否能反应出目标的重要性程度，或层次关系是否能反应出目标的重要性程度，或层次关系?请思考请思考:目标函数

10、怎么写目标函数怎么写?如果这么写如果这么写:(d(d1 1-0)0)(d(d-，d d2 2+0)0)(d(d3 3-，d d3 3+0)0)(d(d4 4+0)0)5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学目标函数：目标函数：管理目标和实际可能完成的目标之间的偏差最小。管理目标和实际可能完成的目标之间的偏差最小。(d(d1 1-0)0)(d(d-，d d2 2+0)0)(d(d3 3-，d d3 3+0)0)(d(d4 4+0)0)43333222113)(7)(mindpddpddpdpzkp叫优先因子叫优先因子Kppp21“”远远重要于的意思。

11、远远重要于的意思。整理后得到该问题的目标规划模型为：整理后得到该问题的目标规划模型为：433333)(7dp、ddp这两项中的这两项中的7和和3是对同一目标层次中，是对同一目标层次中，不同重要程度的权重区分。不同重要程度的权重区分。5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学43333222113)(7)(mindpddpddpdpz180461121ddxx0532221ddxx128244421ddxx100323321ddxx304021xx4,3,2,10,21lddxxlls.t.5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模

12、型东 北 林 业 大 学)(min11lkllLlklKkkdwdwpz目标规划模型的一般形式：目标规划模型的一般形式：（见（见P P135-136135-136）)(1,L1,lgddxclllnjjlj)(),(1,m1,ibxainjjlj0jx)(,n1,j0,lldd)(,L1,l(柔性、目标约束柔性、目标约束)(刚性、系统约束刚性、系统约束)s.t.5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学目标规划模型的特点：目标规划模型的特点：1.1.引进正负偏差变量引进正负偏差变量 ，且有，且有 ；0,lldd0lldd2.2.模型中必需有目标约束，

13、而资源约束可以不存在；模型中必需有目标约束，而资源约束可以不存在；3.3.目标函数为偏差变量表达式；目标函数为偏差变量表达式；4.4.以优先因子（优先级系数）描述目标的重要性程度。以优先因子（优先级系数）描述目标的重要性程度。5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学特别强调：特别强调：目标要求准确完成：目标要求准确完成：llddzmin目标要求超额完成：目标要求超额完成：ldzmin目标要求不能突破：目标要求不能突破：ldzmin1.1.那些偏差变量应进入目标函数？那些偏差变量应进入目标函数？2.2.约束条件有两大类。约束条件有两大类。目标约束目标

14、约束-柔性约束。柔性约束。资源约束资源约束-刚性约束、一般约束、系统约束。刚性约束、一般约束、系统约束。5.1 5.1 问题的提出与目标规划模型问题的提出与目标规划模型东 北 林 业 大 学用目标规划模型来处理问题时的难点用目标规划模型来处理问题时的难点：在于构造模型时，需事先拟定在于构造模型时，需事先拟定目标值、优先级和权系数目标值、优先级和权系数。而这。而这些信息来自人的主观判断，往往带有模糊性，很难给出一个些信息来自人的主观判断，往往带有模糊性，很难给出一个“绝对绝对”的数值。的数值。用目标规划模型求解问题的过程用目标规划模型求解问题的过程：明确问题明确问题,给出目标值、给出目标值、优先

15、级和权系数优先级和权系数构造目标规构造目标规划数学模型划数学模型求求 出出 满满 意意 解解 分析各项指标分析各项指标可能完成情况可能完成情况满意否满意否?据此制订出据此制订出决决 策策 方方 案案否否是是图图5-1 5-1（教材（教材136136页）页）5.2 5.2 目标规划的图解分析法目标规划的图解分析法东 北 林 业 大 学对模型中只含两个变量（不包括偏差变量）的目标规划问题，对模型中只含两个变量（不包括偏差变量）的目标规划问题，可以用图解分析的方法找出满意解。可以用图解分析的方法找出满意解。目标规划的图解分析法的步骤为目标规划的图解分析法的步骤为:作平面直角坐标系；作平面直角坐标系；

16、作出系统约束直线；作出系统约束直线；作出目标约束直线，标出偏差方向；作出目标约束直线，标出偏差方向；按优先级次序，确定满意解。按优先级次序，确定满意解。10 20 30 40 50 606050403020101x2x43333222113)(7)(mindpddpddpdpz180461121ddxx0532221ddxx128244421ddxx100323321ddxx304021xx4,3,2,10,21lddxxll 、OABC11:dp1d1dDEDCBE)(:222ddpFG2d2dFG)77(:333 ddpH3dH433:dpI4dH满意解在满意解在H H点，即：点，即：19

17、1615,1962621xx1988,1914141dd0,433221dddddd 目标规划的目标规划的图解分析法图解分析法OABC5.2 5.2 目标规划的图解分析法目标规划的图解分析法东 北 林 业 大 学10 20 30 40 50 606050403020101x2xOABC1d1dDEFG2d2dH3dI4d最优解在最优解在H H点，即：点，即：191615,1962621xx1988,1914141dd0,433221dddddd如何体现出柔性？如何体现出柔性？5.3 5.3 应用举例应用举例东 北 林 业 大 学例例 5.2 问题的提出：问题的提出：某电视机厂装配彩色和黑白两种

18、电视机，每装配一台某电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线电视机需占用装配线1小时，小时，装配线每周计划开动装配线每周计划开动40小时。小时。预计市场每周预计市场每周彩色电视机的销量是彩色电视机的销量是24台，每台可获利台，每台可获利80元；元；黑白电视机的销量是黑白电视机的销量是30台，台，每台可获利每台可获利40元。该厂确定的目标为：元。该厂确定的目标为：p p1 1：充分利用装配线每周计划开动：充分利用装配线每周计划开动4040小时；小时；p p2 2：允许装配线加班，但加班时间每周尽量不超过：允许装配线加班，但加班时间每周尽量不超过1010小时；小时；p p3

19、3：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权系数为系数为2 2。试建立这问题的目标规划模型，并求解彩色和黑白电视机的产量。试建立这问题的目标规划模型，并求解彩色和黑白电视机的产量。5.3 5.3 应用举例应用举例东 北 林 业 大 学解：设解：设x1，x2分别表示彩色和黑白电视机的产量。模型为：分别表示彩色和黑白电视机的产量。模型为：4,3,2,1,0,30245040.)2(min21442331222111214332211iddxxddxddxddxxddxxtsddPdPdPzii5.3 5.3 应用举例

20、应用举例东 北 林 业 大 学4,3,2,1,0,30245040.)2(min21442331222111214332211iddxxddxddxddxxddxxtsddPdPdPzii在考虑具有在考虑具有P P1 1、P P2 2的目标实现的目标实现后，后，x1、x2的取值范围为的取值范围为ABCDABCD。考虑考虑P P3 3的目标要求时，的目标要求时，因因d d3 3的权系数大于的权系数大于d d4 4，故，故先考虑先考虑min dmin d3 3；这时；这时x1、x2的取值范围缩小为的取值范围缩小为ABEFABEF区域。区域。然后考虑然后考虑d d4 4。在。在ABEFABEF中无中

21、无法满足法满足d d4 4=0=0，因此只能在，因此只能在ABEFABEF中取一点，使中取一点，使d d4 4尽可尽可能小，这就是能小，这就是E E点。故点。故E E点为点为满意解。其坐标为满意解。其坐标为(24(24，26)26)，即该厂每周应装配彩色电视即该厂每周应装配彩色电视机机2424台，黑白电视机台，黑白电视机2626台。台。5.3 5.3 应用举例应用举例东 北 林 业 大 学例例 5.3 5.3 问题的提出：问题的提出：某纺织厂生产两种布料，窗帘布和衣料。某纺织厂生产两种布料，窗帘布和衣料。平均生产能力是平均生产能力是10001000米米/小时，正常生产能力是每周小时，正常生产能

22、力是每周8080小时。小时。根据市场顶测，下周的销售量为：窗帘布根据市场顶测，下周的销售量为：窗帘布7000070000米，衣料米，衣料4500045000米；每米窗帘布和衣料的利润分别为米；每米窗帘布和衣料的利润分别为2.502.50元和元和1.501.50元。元。工厂经理考虑实际管理日标如下：工厂经理考虑实际管理日标如下：P1P1：避免开工不足，使职工正常就业；：避免开工不足，使职工正常就业；P2P2：加班时间不超过：加班时间不超过1010小时小时;P3P3：努力达到最大销量：努力达到最大销量,即窗帘布即窗帘布7000070000米，衣料米，衣料4500045000米；目标米；目标相对重要

23、性程度按两种布料利润比值确定。相对重要性程度按两种布料利润比值确定。P4:P4:尽可能减少加班尽可能减少加班.5.3 5.3 应用举例应用举例东 北 林 业 大 学设：设：x1，x2表示用于生产窗帘布和衣料的工时表示用于生产窗帘布和衣料的工时(1)(1)目标约束为目标约束为 P1:P1:x1 1+x2 2+d+d1 1-d-d1 1+=80 (d=80 (d1 1-0)0)P2:P2:x1 1+x2 2+d+d2 2-d-d2 2+=90 (d=90 (d2 2+0)0)P3:P3:x1 1 +d +d3 3-d-d3 3+=70 (d=70 (d3 3-0)0)x2 2+d+d4 4-d-d

24、4 4+=45 (d=45 (d4 4-0)0)P4:(dP4:(d1 1+0)0)(2)(2)变量非负限制变量非负限制 x1,x20,d0,dl-,d,dl+0 (0 (l=1,2,3,4)=1,2,3,4)目标函数：目标函数：min=Pmin=P1 1 d d1 1-+P+P2 2d d2 2+5P+5P3 3d d3 3-+3P+3P3 3d d4 4-+P+P4 4d d1 1+P1:避免开工不足，使职工正常就业；避免开工不足，使职工正常就业；P2:加班时间不超过加班时间不超过10小时小时;P3:努力达到最大销量努力达到最大销量,即窗帘布即窗帘布70000米，衣料米，衣料45000米米

25、;目标相对重要性程度按两种布料利润比值确定目标相对重要性程度按两种布料利润比值确定.P4:尽可能减少加班尽可能减少加班.5.3 5.3 应用举例应用举例东 北 林 业 大 学练习一练习一要求：要求：P1:P1:充分利用工时充分利用工时 P2P2：A A、B B、C C分别达到分别达到5 5、5 5、8 8件，并按工时利润件，并按工时利润确定权重确定权重 P3P3：加班时间不要超过：加班时间不要超过1616小时小时 P4P4：A A、B B、C C月销量限制为月销量限制为1010、1212、1010件件 P5P5：尽量减少加班时间：尽量减少加班时间 A B C A B C工时限制工时限制工时工时

26、/件件 5 8 12 5 8 12 120 120利润利润/件件100 144 252100 144 2525.3 5.3 应用举例应用举例东 北 林 业 大 学 8X1+5X2+12X3+d1-d1+=120 X1+d2-d2+=5 X2+d3-d3+=5 X3+d4-d4+=8 8X1+5X2+12X3+d5-d5+=120+16 X1+d6-d6+=10 Xj,di-,di+0,j=1,2,3 i=1,2,5 minZ=P1d1-+P2(20 d2-+18 d3-+21d4-)+P3 d5+P4(d6+d7+d8+)+P5 d1+5.3 5.3 应用举例应用举例东 北 林 业 大 学练习

27、二练习二 销地销地产地产地 B B1 1 B B2 2 B B3 3产量产量 A A1 1 A A2 2 A A3 3 A A4 4 5 8 35 8 3 7 4 5 7 4 5 2 6 9 2 6 9 4 6 6 4 6 610010040404040120120 销量销量 120 140 140 120 140 140 多目标运输问题如多目标运输问题如 下表。目标要求：下表。目标要求：P1P1：产地不存货，且销量至少满足一半：产地不存货，且销量至少满足一半 P2P2：满足：满足B1B1需求，且需求，且A4B2A4B2尽量少运尽量少运 P3P3：总运费最小：总运费最小 试建立该问题的目标规划

28、模型。试建立该问题的目标规划模型。5.3 5.3 应用举例应用举例东 北 林 业 大 学解：设解：设A Ai i到到B Bj j的运输量为的运输量为x xij ijX11+X12+X13+d1-d1+=100X21+X22+X23+d2-d2+=40X31+X32+X33+d3-d3+=40X41+X42+X43+d4-d4+=120X11+X21+X31+X41+d5-d5+=120/2X12+X22+X32+X42+d6-d6+=140/2X13+X23+X33+X43+d7-d7+=140/2X11+X21+X31+X41+d8-d8+=120X42 +d9-d9+=0 Cij Xij +d10-d10+=0Xij,dl-dl+0 i=1,2,3,4 j=1,2,3 l=1,2,10minZ=P1(d1-+d7-)+P2(d8-+d9+)+P3 d10+