《运筹学(第5章目标规划).ppt》由会员分享，可在线阅读，更多相关《运筹学(第5章目标规划).ppt（33页珍藏版）》请在三一办公上搜索。
1、,运筹学基础及应用(Operations Research),主讲：杨启明,第5章 目标规划,目标规划问题及其数学模型,例5.1 某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。,问该企业应如何安排计划，使得计划期内的总利润收入为最大？,解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：,其最优解为x14，x22，z14元,但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：力求使利润指标不低于12元；考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间
2、要控制；设备A即要求充分利用，又尽可能不加班。,要考虑上述多方面的目标，需要借助目标规划的方法。,线性规划模型存在的局限性：1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。,目标规划问题举例,例1企业生产:不同企业的生产目标是不同的。多数企业追求最大的经济效益。但随着环境问题的日益突出，可持续发展已经成为全社会所必须考
3、虑的问题。因此，企业生产就不能再如以往那样只考虑企业利润，必须承担起社会责任，要考虑环境污染、社会效益、公众形象等多个方面。兼顾好这几者关系，企业才可能保持长期的发展。例2商务活动:企业在进行盈亏平衡预算时，不能只集中在一种产品上，因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分。因此，需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题（多产品的盈亏平衡点往往是不一致的）。,例3投资:企业投资时不仅仅要考虑收益率，还要考虑风险。一般地，风险大的投资其收益率更高。因此，企业管理者只有在对收益率和风险承受水平有明确的期望值时，才能得到满意的决策。例4裁员:同样的，企业裁员时要考虑很
4、多可能彼此矛盾的因素。裁员的首要目的是压缩人员开支，但在人人自危的同时员工的忠诚度就很难保证，此外，员工的心理压力、工作压力等都会增加，可能产生负面影响。例5营销:营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果，又希望营销的成本控制在某一个范围内。此外，营销活动的深入程度也决定了营销效果的好坏和持续时间。,目标规划问题及其数学模型,目标规划怎样解决上述线性规划模型建模中的局限性？,1.设置偏差变量，用来表明实际值同目标值之间的差异。,偏差变量用下列符号表示：,d+超出目标的偏差，称正偏差变量d-未达到目标的偏差，称负偏差变量,正负偏差变量两者必有一个为0。当实际值超出目标值时：d
5、+0,d-=0;当实际值未达到目标值时：d+=0,d-0;当实际值同目标值恰好一致时：d+=0,d-=0;故恒有d+d-=0,目标规划问题及其数学模型,2.统一处理目标和约束。,对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。,对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。,1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，当x1x2时，出现正偏差d+，即：x1-d+=x2或x1x2-d+=0,目标规划问题及其数学模型,正负偏差不可能同时出现，故总有：x1x2+d-d+=0,若希望
6、甲的产量不低于乙的产量，即不希望d-0,用目标约束可表为:,若希望甲的产量低于乙的产量，即不希望d0,用目标约束可表为:,若希望甲的产量恰好等于乙的产量，即不希望d0,也不希望d-0用目标约束可表为:,目标规划问题及其数学模型,3）设备B必要时可加班及加班时间要控制，目标约束表示为：,2）力求使利润指标不低于12元，目标约束表示为：,4）设备A既要求充分利用，又尽可能不加班，目标约束表示为：,目标规划问题及其数学模型,3.目标的优先级与权系数,在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,表示。对于同一
7、层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。,现假定：,第1优先级P1企业利润；第2优先级P2甲乙产品的产量保持1:1的比例 第3优先级P3设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。,目标规划问题及其数学模型,上述目标规划模型可以表示为：,目标规划问题及其数学模型,目标规划数学模型的一般形式,达成函数,目标约束,其中：gk为第k个目标约束的预期目标值，和 为pl 优先因子对应各目标的权系数。,目标规划问题及其数学模型,用目标规划求解问题的过程：,明确问题，列出目标的优先级和权系数,构造目标规划模型,求
8、出满意解,满意否？,分析各项目标完成情况,据此制定出决策方案,N,Y,目标规划的图解法,例6一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1：从上表可知，A股票的收益率为（320）10015，股票B的收益率为4501008，A的收益率比B大，但同时A的风险也比B大。这也符合高风险高收益的规律。试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。,目标规划的图解法,显然，此问题属于目标规划问题。它有两个目标变量：一是限制风险，一是确保收益。在求解之前，应首先考虑两个目标
9、的优先权。假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目标。建立模型：设x1、x2分别表示投资商所购买的A股票和B股票的数量。首先考虑资金总额的约束：总投资额不能高于90000元。即 20 x150 x290000。,目标规划的图解法,约束条件 再来考虑风险约束：总风险不能超过700。投资的总风险为0.5x10.2x2。引入两个变量d1+和d1-,建立等式如下：0.5x1+0.2x2=700+d1+-d1-其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的部分，d1+0。目标规划中把d
10、1+、d1-这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。,把等式转换，可得到 0.5x1+0.2x2-d1+d1-=700。再来考虑年收入:年收入=3x1+4x2 引入变量d2+和d2-，分别表示年收入超过与低于10000的数量。于是，第2个目标可以表示为 3x1+4x2-d2+d2-=10000。,有优先权的目标函数 本问题中第一个目标的优先权比第二个目标大。即最重要的目标是满足风险不超过700。分配给第一个目标较高的优先权P1,分配给第二个目标较低的优先权P2。针对每一个优先权，应当建立一个单一目标的线性规划模型。首先建立具有最高优先权的目标的线性规划模型，求解；然后
11、再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原来模型的基础上修改目标函数，并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中，并求解。,图解法针对优先权最高的目标建立线性规划建立线性规划模型如下：Min d1+s.t.20 x150 x290000 0.5x1+0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-0,针对优先权次高的目标建立线性规划优先权次高（P2）的目标是总收益超过10000。建立线性规划如下：Min d2-s.t.20 x150 x290000 0.5x1+0.2x2-d1+d1-=7
12、00 3x1+4x2-d2+d2-=10000 d1+0 x1,x2,d1+,d1-,d2+,d2-0,目标规划的这种求解方法可以表述如下：1确定解的可行区域。2对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。3对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。4.重复第3步，直至所有优先权的目标求解完。,目标规划模型的标准化 例6中对两个不同优先权的目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下：Min P1（d1+）+P2（d2-）s.t.20 x150 x290000 0.5x1+0.2x2-d1+d1-=700 3x1+4x2
13、-d2+d2-=10000 x1,x2,d1+,d1-,d2+,d2-0,复杂情况下的目标规划,例7一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A
14、完成200件的重要性的2倍。试求如何安排生产？,解：本问题中有3个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。对应P1有两个目标：每周总耗费人力资源不能低于600工时,也不能超过680工时；对应P2有一个目标：每周的利润超过70000元；对应P3有两个目标：每周产品A和B的产量分别不低于200和120件。,采用简化模式，最终得到目标线性规划如下：Min P1(d1+)+P1(d2)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.2x1+3x2-d1+d1-=680 对应第1个目标 2x1+3x2-d2+d2-=600 对应第2个目标 250 x1+125x2+d3-
15、d3+70000 对应第3个目标 x1-d4+d4-=200 对应第4个目标 x2-d5+d5-=120 对应第5个目标 x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-0,使用运筹学软件求解可得：x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；d4+=50；d4-=0；d5+=0；d5-=60，目标函数d4-+2d5-=120。可见，目标1、目标3和目标4达到了，但目标2、目标5都有一些偏差。,加权目标规划,加权目标规划是另一种解决多目标决策问题的方法，其基本方法是通过量化的方法分配给每个目标的偏离
16、的严重程度一个罚数权重，然后建立总的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，整个问题都可以描述为一个线性规划的问题。如果在例7中我们对每周总耗费的人力资源超过680工时或低于600工时的每工时罚数权重定为7；每周利润低于70000元时，每元的罚数权重为5；每周产品A产量低于200件时每件罚数权重为2，而每周产品B产量低于120件时每件罚数权重为4。,则其目标函数化为：min7d1+7d2-+5d3-+2d4-+4d5-这就变成了一个普通的单一目标的线性规划问题 min7d1+7d2-+5d3-+2d4-+4d5-s.t.2x1+3x2-d1+d1-=680 2x1+3x2-d2-+d2+=680 250 x1+125x2-d3-+d3+=70000 x1-d4+d4-=200 x2-d5+d5-=120 x1,x2,d1+,d1-,d2-,d2+,d3+,d3-,d4+,d4-,d5+,d5-0。,
