运筹学第五章 目标规划

第五章目标规划东北林业大学§5.1问题的提出与目标规划模型§5.2目标规划的图解分析法§5.3应用举例§5.1问题的提出与目标规划模型东北林业大学一、目标规划问题的提出线性规划的局限性P133：第一，它要求问题的解必须满足全部约束条件，但实际问题中对某些约束有一定程度的违背是允许的；第二，只能处理单目标的优化问题，因此线性规划模型中人为地将一些次要目标转为约束。而实际问题中，目标和约束可以互相转化，处理时不一定要严格区分。第三，线性规划中各个约束条件(实际上也可看作目标)都处于同等重要地位，但现实问题中，各目标的重要性既有层次上的差别，同一层次中又可以确权重上的区分；第四，线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。001202410032..4621212121,xxxxxxtsxxzmax§5.1问题的提出与目标规划模型东北林业大学为克服LP的缺陷，美国学者1961年提出了目标规划的有关概念和模型。1976年伊格尼齐奥发表了《目标规划及其扩展》一书，系统归纳总结了目标规划的理论和方法。定义：目标规划是求一组变量的值，在满足一组目标约束（也称柔性约束）和资源约束（也称刚性约束）条件下，实现管理目标和实际可能完成的目标之间的偏差最小。§5.1问题的提出与目标规划模型东北林业大学二、目标规划模型例5.1问题的提出：对例1.1[某企业生产两种产品，需要两种原料,有关数据见表。如何安排生产计划可使总的收益最大。]企业管理人员又提出如下目标要求:产品资源甲乙资源拥有量Ａ２３100Ｂ４２120单件收益６４（千元）第三目标P3：A资源要充分利用，但不能超额。B资源可超额利用，但最多不能超额8个单位。A、B资源的权系数分别为7和3。由市场预测可知，甲、乙的产量不能超过40和30件。如何制定满足上述目标要求的生产计划方案.第一目标P1：收益不低于180千元；第二目标P2：甲乙的产量尽量满足5:3的关系；试建立该问题的目标规划模型。§5.1问题的提出与目标规划模型东北林业大学目的--制定一个生产计划方案。（甲乙各生产多少件）目标--管理目标和实际可能完成的目标之间的偏差最小。（目标规划模型中的目标均如此表示）设置变量：①决策变量，x1,x2分别表示产品甲、乙的产量。②偏差变量，偏差变量有正负之分，用正偏差d+和负偏差d-表示。d+表示超过目标值的部分；d-表示不足目标值的部分。显然有d-×d+=0。解：§5.1问题的提出与目标规划模型东北林业大学P1:收益不低于180千元；P2:甲乙的产量尽量满足5:3的关系；P3:A资源要充分利用，但不能超额。B资源可超额利用，但最多不能超额8个单位。A、B资源的权系数分别为7和3。约束条件：P1：6x1+4x2+=180d1-–d1+(d1-→0)P2：3x1-5x2+=0d2-–d2+(d２-，d2+→0)P3：2x1+3x2+=100d3-–d3+(d3-，d3+→0)4x1+2x2+=128d4-–d4+(d4+→0)（2）系统约束（刚性约束）x1≤40x2≤30（3）变量非负限制（1）目标约束（柔性约束）1,2,3,4lddxxll,0,,,21§5.1问题的提出与目标规划模型东北林业大学433221)()(minddddddz目标函数：管理目标和实际可能完成的目标之间的偏差最小。是否能反应出目标的重要性程度，或层次关系?请思考:目标函数怎么写?如果这么写:(d1-→0)(d２-，d2+→0)(d3-，d3+→0)(d4+→0)§5.1问题的提出与目标规划模型东北林业大学目标函数：管理目标和实际可能完成的目标之间的偏差最小。(d1-→0)(d２-，d2+→0)(d3-，d3+→0)(d4+→0)43333222113)(7)(mindpddpddpdpzkp叫优先因子Kppp21“”远远重要于的意思。整理后得到该问题的目标规划模型为：433333)(7dp、ddp这两项中的7和3是对同一目标层次中，不同重要程度的权重区分。§5.1问题的提出与目标规划模型东北林业大学43333222113)(7)(mindpddpddpdpz180461121ddxx0532221ddxx128244421ddxx100323321ddxx304021xx4,3,2,10,,,21lddxxlls.t.§5.1问题的提出与目标规划模型东北林业大学)(min11lkllLlklKkkdwdwpz目标规划模型的一般形式：（见P135-136）)(1,L1,lgddxclllnjjlj)(),(1,m1,ibxainjjlj0jx)(,n1,j0,lldd)(,L1,l(柔性、目标约束)(刚性、系统约束)s.t.§5.1问题的提出与目标规划模型东北林业大学目标规划模型的特点：1.引进正负偏差变量，且有；0,lldd0lldd2.模型中必需有目标约束，而资源约束可以不存在；3.目标函数为偏差变量表达式；4.以优先因子（优先级系数）描述目标的重要性程度。§5.1问题的提出与目标规划模型东北林业大学特别强调：①目标要求准确完成：llddzmin②目标要求超额完成：ldzmin③目标要求不能突破：ldzmin1.那些偏差变量应进入目标函数？2.约束条件有两大类。①目标约束----柔性约束。②资源约束----刚性约束、一般约束、系统约束。§5.1问题的提出与目标规划模型东北林业大学用目标规划模型来处理问题时的难点：在于构造模型时，需事先拟定目标值、优先级和权系数。而这些信息来自人的主观判断，往往带有模糊性，很难给出一个“绝对”的数值。用目标规划模型求解问题的过程：明确问题,给出目标值、优先级和权系数构造目标规划数学模型求出满意解分析各项指标可能完成情况满意否?据此制订出决策方案否是图5-1（教材136页）§5.2目标规划的图解分析法东北林业大学对模型中只含两个变量（不包括偏差变量）的目标规划问题，可以用图解分析的方法找出满意解。目标规划的图解分析法的步骤为:①作平面直角坐标系；②作出系统约束直线；③作出目标约束直线，标出偏差方向；④按优先级次序，确定满意解。1020304050606050403020101x2x43333222113)(7)(mindpddpddpdpz180461121ddxx0532221ddxx128244421ddxx100323321ddxx304021xx4,3,2,10,,,21lddxxll…①…②…③…⑥…④…⑤⑤、⑥⑤⑥OABC11:dp①1d1dDEDCBE)(:222ddp②FG2d2dFG)77(:333ddp③H3dH433:dp④I4dH满意解在H点，即：191615,1962621xx1988,1914141dd0,,,,,433221dddddd目标规划的图解分析法→OABC§5.2目标规划的图解分析法东北林业大学1020304050606050403020101x2x⑤⑥OABC①1d1dDE②FG2d2d③H3d④I4d最优解在H点，即：191615,1962621xx1988,1914141dd0,,,,,433221dddddd如何体现出柔性？§5.3应用举例东北林业大学例5.2问题的提出：某电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：p1：充分利用装配线每周计划开动40小时；p2：允许装配线加班，但加班时间每周尽量不超过10小时；p3：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权系数为2。试建立这问题的目标规划模型，并求解彩色和黑白电视机的产量。§5.3应用举例东北林业大学解：设x1，x2分别表示彩色和黑白电视机的产量。模型为：4,3,2,1,0,,,30245040..)2(min21442331222111214332211iddxxddxddxddxxddxxtsddPdPdPzii§5.3应用举例东北林业大学4,3,2,1,0,,,30245040..)2(min21442331222111214332211iddxxddxddxddxxddxxtsddPdPdPzii在考虑具有P1、P2的目标实现后，x1、x2的取值范围为ABCD。考虑P3的目标要求时，因d3—的权系数大于d4—，故先考虑mind3—；这时x1、x2的取值范围缩小为ABEF区域。然后考虑d4—。在ABEF中无法满足d4—=0，因此只能在ABEF中取一点，使d4—尽可能小，这就是E点。故E点为满意解。其坐标为(24，26)，即该厂每周应装配彩色电视机24台，黑白电视机26台。§5.3应用举例东北林业大学例5.3问题的提出：某纺织厂生产两种布料，窗帘布和衣料。平均生产能力是1000米/小时，正常生产能力是每周80小时。根据市场顶测，下周的销售量为：窗帘布70000米，衣料45000米；每米窗帘布和衣料的利润分别为2.50元和1.50元。工厂经理考虑实际管理日标如下：P1：避免开工不足，使职工正常就业；P2：加班时间不超过10小时;P3：努力达到最大销量,即窗帘布70000米，衣料45000米；目标相对重要性程度按两种布料利润比值确定。P4:尽可能减少加班.§5.3应用举例东北林业大学设：x1，x2表示用于生产窗帘布和衣料的工时(1)目标约束为P1:x1+x2+d1--d1+=80(d1-→0)P2:x1+x2+d2--d2+=90(d2+→0)P3:x1+d3--d3+=70(d3-→0)x2+d4--d4+=45(d4-→0)P4:(d1+→0)(2)变量非负限制x1,x2＞0,dl-,dl+≥0(l=1,2,3,4)目标函数：min=P1d1-+P2d2++5P3d3-+3P3d4-+P4d1+P1:避免开工不足，使职工正常就业；P2:加班时间不超过10小时;P3:努力达到最大销量,即窗帘布70000米，衣料45000米;目标相对重要性程度按两种布料利润比值确定.P4:尽可能减少加班.§5.3应用举例东北林业大学练习一要求：P1:充分利用工时P2：A、B、C分别达到5、5、8件，并按工时利润确定权重P3：加班时间不要超过16小时P4：A、B、C月销量限制为10、12、10件P5：尽量减少加班时间ABC工时限制工时/件5812120利润/件100144252§5.3应用举例东北林业大学•8X1+5X2+12X3+d1--d1+=120X1+d2--d2+=5X2+d3--d3+=5X3+d4--d4+=88X1+5X2+12X3+d5--d5+=120+16X1+d6--d6+=10……Xj,di-,di+≥0,j=1,2,3i=1,2,…,5•minZ=P1d1-+P2(20d2-+18d3-+21d4-)+P3d5++P4(d6++d7++d8+)+P5d1+§5.3应用举例东北林业大学练习二销地产地B1B2B3产量A1A2A3A45837452694661004040120销量120140140多目标运输问题如下表。目标要求：P1：产地不存货，且销量至少满足一半P2：满足B1需求，且A4—B2尽量少运P3：总运费最小试建立该问题的目标规划模型