关闭

关闭

关闭

封号提示

内容

首页 第21章 目标规划.pdf

第21章 目标规划.pdf

第21章 目标规划.pdf

上传者: Gingerjin 2012-07-26 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《第21章 目标规划pdf》,可适用于工程科技领域,主题内容包含第二十一章目标规划引言.线性规划的局限性只能解决一组线性约束条件下某一目标只能是一个目标的最大或最小值的问题。.实际决策中衡量方案优劣考虑多个目标这符等。

第二十一章目标规划引言.线性规划的局限性只能解决一组线性约束条件下某一目标只能是一个目标的最大或最小值的问题。.实际决策中衡量方案优劣考虑多个目标这些目标中有主要的也有次要的有最大值的也有最小值的有定量的也有定性的有相互补充的也有相互对立的LP则无能为力。.目标规划(GoalProgramming)美国经济学家查恩斯(ACharnes)和库柏(WWCooper)在年出版的《管理模型及线性规划的工业应用》一书中首先提出的。.求解思路()加权系数法为每一目标赋一个权系数把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数以反映不同目标之间的重要程度。()优先等级法将各目标按其重要程度不同的优先等级转化为单目标模型。()有效解法寻求能够照顾到各个目标并使决策者感到满意的解。由决策者来确定选取哪一个解即得到一个满意解。但有效解的数目太多而难以将其一一求出。目标规划的数学模型为了具体说明目标规划与线性规划在处理问题的方法上的区别先通过例子来介绍目标规划的有关概念及数学模型。例某工厂生产III两种产品已知有关数据见下表III拥有量原材料kg设备hr利润元件试求获利最大的生产方案。解这是一个单目标的规划问题用线性规划模型表述为:maxxxz=,xxxxxx最优决策方案为:,,***===zxx元。但实际上工厂在作决策方案时要考虑市场等一系列其它条件。如(i)根据市场信息产品I的销售量有下降的趋势故考虑产品I的产量不大于产品II。(ii)超过计划供应的原材料需要高价采购这就使成本增加。(iii)应尽可能充分利用设备但不希望加班。(iv)应尽可能达到并超过计划利润指标元。这样在考虑产品决策时便为多目标决策问题。目标规划方法是解决这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。正、负偏差变量设d为决策变量的函数正偏差变量},max{ddd=表示决策值超过目标值的部分负偏差变量},min{ddd=表示决策值未达到目标值的部分这里d表示d的目标值。因决策值不可能既超过目标值同时又未达到目标值即恒有=dd。绝对(刚性)约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束如线性规划问题的所有约束条件不能满足这些约束条件的解称为非可行解所以它们是硬约束。目标约束是目标规划特有的可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差因此在这些约束中加入正、负偏差变量它们是软约束。线性规划问题的目标函数在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如:例的目标函数xxz=可变换为目标约束=ddxx。绝对约束xx可变换为目标约束=ddxx。优先因子(优先等级)与权系数一个规划问题常常有若干目标。但决策者在要求达到这些目标时是有主次或轻重缓急的不同。凡要求第一位达到的目标赋于优先因子P次位的目标赋于优先因子L,P并规定qkPPkk,,,,L=>>。表示kP比kP有更大的优先权。以此类推若要区别具有相同优先因子的两个目标的差别这时可分别赋于它们不同的权系数jw这些都由决策者按具体情况而定。目标规划的目标函数目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋于相应的优先因子而构造的。当每一目标值确定后决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是),(min=ddfz。其基本形式有三种:()要求恰好达到目标值即正、负偏差变量都要尽可能地小这时)(min=ddfz()要求不超过目标值即允许达不到目标值就是正偏差变量要尽可能地小这时)(min=dfz()要求超过目标值即超过量不限但必须是负偏差变量要尽可能地小这时)(min=dfz对每一个具体目标规划问题可根据决策者的要求和赋于各目标的优先因子来构造目标函数以下用例子说明。例例的决策者在原材料供应受严格限制的基础上考虑:首先是产品II的产量不低于产品I的产量其次是充分利用设备有效台时不加班再次是利润额不小于元。求决策方案。解按决策者所要求的分别赋于这三个目标,,PPP优先因子。这问题的数学模型是)(mindPddPdP====,,,,,,iddxxddxxddxxddxxxxii.目标规划的一般数学模型设jx(nj,,,L=)是目标规划的决策变量共有m个约束是刚性约束可能是等式约束也可能是不等式约束。设有l个柔性目标约束其目标规划约束的偏差为iidd,(li,,,L=)。设有q个优先级别分别为qPPP,,,L。在同一个优先级kP中有不同的权重分别记为),,,(,ljwwkjkjL=。因此目标规划模型的一般数学表达式为===ljjkjjkjqkkdwdwPzmin========liddnjxligddxcmibxaiijnjiiijijnjijij,,,,,,,,,,,,,,,,),(LLLL建立目标规划的数学模型时需要确定目标值、优先等级、权系数等它都具有一定的主观性和模糊性可以用专家评定法给以量化。求解目标规划的序贯式算法序贯式算法是求解目标规划的一种早期算法其核心是根据优先级的先后次序将目标规划问题分解成一系列的单目标规划问题然后再依次求解。求解目标规划的序贯算法对于qk,,,L=求解单目标规划==ljjkjjkjdwdwz)(min()st===njijijmibxa,,,),(L()===njiiijijligddxc,,,,L()*)(sljjsjjsjzdwdw=,,,=ksL()njxj,,,,L=()liddii,,,,,L=()其最优目标值为*kz当=k时约束()为空约束。当qk=时*qz所对应的解*x为目标规划的最优解。注此时最优解的概念与线性规划最优解的概念已有所不同但为方便起见仍称为最优解。例某企业生产甲、乙两种产品需要用到CBA,,三种设备关于产品的赢利与使用设备的工时及限制如下表所示。问该企业应如何安排生产才能达到下列目标:甲乙设备的生产能力(h)A(h件)B(h件)C(h件)赢利(元件)()力求使利润指标不低于元()考虑到市场需求甲、乙两种产品的产量比应尽量保持:()设备A为贵重设备严格禁止超时使用()设备C可以适当加班但要控制设备B既要求充分利用又尽可能不加班。在重要性上设备B是设备C的倍。建立相应的目标规划模型并求解。解设备A是刚性约束其余是柔性约束。首先最重要的指标是企业的利润因此将它的优先级列为第一级其次甲、乙两种产品的产量保持:的比例列为第二级再次设备BC,的工作时间要有所控制列为第三级。在第三级中设备B的重要性是设备C的三倍因此它们的权重不一样设备B前的系数是设备C前系数的倍。由此得到相应的目标规划模型。)()(min=dddPddPdPz()stxx()=ddxx()=ddxx()=ddx()=ddx(),,,iiddxx,,,=i()序贯算法中每个单目标问题都是一个线性规划问题可以使用LINGO软件进行求解。求第一级目标。LINGO程序如下:model:sets:variable:xSConNum:g,dplus,dminusScon(SConNum,Variable):cendsetsdata:g=c=enddatamin=dminus()*x()*x()<for(SConNum(i):sum(Variable(j):c(i,j)*x(j))dminus(i)dplus(i)=g(i))end求得dminus()=即目标函数的最优值为第一级偏差为。求第二级目标LINGO程序如下:model:sets:variable:xSConNum:g,dplus,dminusScon(SConNum,Variable):cendsetsdata:g=c=enddatamin=dplus()dminus()!二级目标函数*x()*x()<for(SConNum(i):sum(Variable(j):c(i,j)*x(j))dminus(i)dplus(i)=g(i))dminus()=!一级目标约束for(variable:gin(x))end求得目标函数的最优值为即第二级的偏差仍为。求第三级目标LINGO程序如下:model:sets:variable:xSConNum:g,dplus,dminusScon(SConNum,Variable):cendsetsdata:g=c=enddatamin=*dplus()*dminus()dplus()!三级目标函数*x()*x()<for(SConNum(i):sum(Variable(j):c(i,j)*x(j))dminus(i)dplus(i)=g(i))dminus()=!一级目标约束dplus()dminus()=!二级目标约束end目标函数的最优值为即第三级偏差为。分析计算结果=x=x=d因此目标规划的最优解为),(*=x最优利润为。上述过程虽然给出了目标规划问题的最优解但需要连续编几个程序这样在使用时不方便下面用LINGO软件编写一个通用的程序在程序中用到数据段未知数据的编程方法。例(续例)按照序贯式算法编写求解例的通用LINGO程序。model:sets:level:p,z,goalvariable:xhconnum:bsconnum:g,dplus,dminushcon(hconnum,variable):ascon(sconnum,variable):cobj(level,sconnum),,,:wplus,wminusendsetsdata:ctr=goal=b=g=a=c=wplus=wminus=enddatamin=sum(level:p*z)p(ctr)=for(level(i)|i#ne#ctr:p(i)=)for(level(i):z(i)=sum(obj(i,j):wplus(i,j)*dplus(j)wminus(i,j)*dminus(j)))for(hconnum(i):sum(variable(j):a(i,j)*x(j))<b(i))for(sconnum(i):sum(variable(j):c(i,j)*x(j))dminus(i)dplus(i)=g(i))for(level(i)|i#lt#size(level):bnd(,z(i),goal(i)))end当程序运行时会出现一个对话框。在做第一级目标计算时ctr输入goal()和goal()输入两个较大的值表明这两项约束不起作用。求得第一级的最优偏差为进行第二轮计算。在第二级目标的运算中ctr输入。由于第一级的偏差为因此goal()的输入值为goal()输入一个较大的值。求得第二级的最优偏差仍为进行第三级计算。在第三级的计算中ctr输入。由于第一级、第二级的偏差均是因此goal()和goal()的输入值也均是。最终结果是:=x=x最优利润是元第三级的最优偏差为。多标规划的Matlab解法多目标规划可以归结为γγ,minx使得goalweightxFγ)(beqxAeqbxA=,)(,)(=xceqxcubxlb其中lbbeqbgoalweightx,,,,,和ub是向量A和Aeq是矩阵)(),(xceqxc和)(xF是向量函数他们可以是非线性函数。)(xF是所考虑的目标函数goal是欲达到的目标多目标规划的Matlab函数fgoalattain的用法为[x,fval]=fgoalattain('fun',x,goal,weight)[x,fval]=fgoalattain('fun',x,goal,weight,A,b)[x,fval]=fgoalattain('fun',x,goal,weight,A,b,Aeq,beq)[x,fval]=fgoalattain('fun',x,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)其中fun是用M文件定义的目标向量函数x是初值weight是权重。A,b定义不等式约束A*xbAeq,beq定义等式约束Aeq*x=Beqnonlcon是用M文件定义的非线性约束c(x)ceq(x)=。返回值fval是目标向量函数的值。要完整掌握其用法请用helpfgoalattain或typefgoalattain查询相关的帮助。例求解多目标线性规划问题minmaxxxZxxxxZ===,,,Lixxxxxxxxxi解(i)编写M函数Funm:functionF=Fun(x)F()=*x()*x()*x()*x()F()=*x()*x()(ii)编写M文件a=b='c=c=x,g=linprog(c,a,b,,,zeros(,))求第一个目标函数的目标值x,g=linprog(c,a,b,,,zeros(,))求第二个目标函数的目标值g=gg目标goal的值x,fval=fgoalattain('Fun',rand(,),g,abs(g),a,b,,,zeros(,))这里权重weight=目标goal的绝对值就可求得问题的解。目标规划模型的实例前面介绍了目标规划的求解方法这里再介绍几个目标规划模型的模型帮助我们进一步了解目标规划模型的建立和求解过程。例某计算机公司生产三种型号的笔记本电脑CBA,,。这三种笔记本电脑需要在复杂的装配线上生产生产台CBA,,型号的笔记本电脑分别需要(h)。公司装配线正常的生产时间是每月h。公司营业部门估计CBA,,三种笔记本电脑的利润分别是每台(元)而公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标:第一目标:充分利用正常的生产能力避免开工不足第二目标:优先满足老客户的需求CBA,,三种型号的电脑(台)同时根据三种电脑的纯利润分配不同的权因子第三目标:限制装配线加班时间最好不要超过h第四目标:满足各种型号电脑的销售目标CBA,,型号分别为(台)再根据三种电脑的纯利润分配不同的权因子第五目标:装配线的加班时间尽可能少。请列出相应的目标规划模型并用LINGO软件求解。解建立目标约束。()装配线正常生产设生产CBA,,型号的电脑为,,xxx(台)d为装配线正常生产时间未利用数d为装配线加班时间希望装配线正常生产避免开工不足因此装配线目标约束为=}{minddxxxd()()销售目标优先满足老客户的需求并根据三种电脑的纯利润分配不同的权因子CBA,,三种型号的电脑每小时的利润是,,因此老客户的销售目标约束为===}{minddxddxddxddd()再考虑一般销售。类似上面的讨论得到===}{minddxddxddxddd()()加班限制首先是限制装配线加班时间不允许超过h因此得到=}{minddxxxd()其次装配线的加班时间尽可能少即=}{minddxxxd()写出目标规划的数学模型=)()(mindPdddPdPdddPdPzst=ddxxx===ddxddxddx===ddxddxddx=ddxxx,,,iiddxx,,,L=i写出相应的LINGO程序如下:model:sets:level:p,z,goalvariable:xsconnum:g,dplus,dminusscon(sconnum,variable):cobj(level,sconnum),,,,,,,,:wplus,wminusendsetsdata:ctr=goal=g=c=wplus=wminus=enddatamin=sum(level:p*z)p(ctr)=for(level(i)|i#ne#ctr:p(i)=)for(level(i):z(i)=sum(obj(i,j):wplus(i,j)*dplus(j)wminus(i,j)*dminus(j)))for(sconnum(i):sum(variable(j):c(i,j)*x(j))dminus(i)dplus(i)=g(i))for(level(i)|i#lt#size(level):bnd(,z(i),goal))End经次计算得到=x=x=x。装配线生产时间为h满足装配线加班不超过h的要求。能够满足老客户的需求但未能达到销售目标。销售总利润为=(元)例已知三个工厂生产的产品供应给四个客户各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费用如下表所示其中总生产量小于总需求量。用户生产量工厂工厂工厂需求量()求总运费最小的运输问题的调度方案。()上级部门经研究后制定了调配方案的项指标并规定了重要性的次序。第一目标:用户为重要部门需求量必须全部满足第二目标:供应用户的产品中工厂的产品不少于个单位第三目标:每个用户的满足率不低于%第四目标:应尽量满足各用户的需求第五目标:新方案的总运费不超过原运输问题的调度方案的%第六目标:因道路限制工厂到用户的路线应尽量避免运输任务第七目标:用户和用户的满足率应尽量保持平衡第八目标:力求减少总运费。请列出相应的目标规划模型并用LINGO程序求解。解()求解原运输问题由于总生产量小于总需求量虚设工厂生产量为个单位到各个用户间的运费单价为。用LINGO软件求解得到总运费是元运输方案如下表所示。用户生产量工厂工厂工厂工厂需求量()下面按照目标的重要性的等级列出目标规划的约束和目标函数。设ijx为工厂),,(=ii调配给用户),,,(=jj的运量ijc表示从工厂i到用户j的单位产品的运输费用),,,(=jaj表示第j个用户的需求量),,(=ibi表示第i个工厂的生产量。i)供应约束应严格满足即ijijbx=ii)供应用户的产品中工厂的产品不少于个单位即=ddxiii)需求约束。各用户的满足率不低于%即=ddxxx=ddxxx=ddxxx=ddxxx应尽量满足各用户的需求即=ddxxx=ddxxx=ddxxx=ddxxxiv)新方案的总运费不超过原方案的%(原运输方案的运费为元)即===ddxciijjijv)工厂到用户的路线应尽量避免运输任务即=ddxvi)用户和用户的满足率应尽量保持平衡即)()(=ddxxxxxxvii)力求总运费最少即===ddxciijjij目标函数为=)()()(mindPddPdPdPddddPddddPdPdPz编写LINGO程序如下:model:sets:level:p,z,goalsconnum:g,dplus,dminusplant:acustomer:broutes(plant,customer):c,xobj(level,sconnum),,,,,,,,,,,,,:wplus,wminusendsetsdata:ctr=goal=a=b=c=wplus=wminus=enddatamin=sum(level:p*z)p(ctr)=for(level(i)|i#ne#ctr:p(i)=)for(level(i):z(i)=sum(obj(i,j):wplus(i,j)*dplus(j)wminus(i,j)*dminus(j)))for(plant(i):sum(customer(j):x(i,j))<a(i))x(,)dminus()dplus()=for(customer(j):sum(plant(i):x(i,j))dminus(j)dplus(j)=*b(j)sum(plant(i):x(i,j))dminus(j)dplus(j)=b(j))sum(routes:c*x)dminus()dplus()=x(,)dminus()dplus()=sum(plant(i):x(i,))*sum(plant(i):x(i,))dminus()dplus()=sum(routes:c*x)dminus()dplus()=for(level(i)|i#lt#size(level):bnd(,z(i),goal))End经次运算得到最终的计算结果见下表。总运费为元高于原运费元超过原方案%的上限元。用户生产量工厂工厂工厂实际运量需求量例某公司从三个仓库向四个用户提供某种产品。仓库与用户所在地的供需量及单位运价见下表。单位:元件BBBB供应量(件)AAA需求量(件)公司有关部门根据供求关系和经营条件确定了下列目标:P:完全满足用户B的需要P:A向B提供的产品数量不少于件P:每个用户的供应量不少于其需求的P:从仓库A到用户B之间的公路正在大修运货量应尽量少P:平衡用户B和B的供货满意水平P:力求总运费最省试求满意的调运方案。解这是具有个优先级目标的运输问题。设ijx为从仓库iA到用户jB的运输量(,,=i,,,=j)kkdd,为第k个目标约束中未达到规定目标的负偏差和超过目标的正偏差。ia(,,=i)是第i个仓库的供应量。约束条件有以下几种:i)供应约束(硬约束)。ijijax=,,=iii)需求约束。由于产品供不应求向各用户的实际供应量不可能超过需求量所以需求正偏差没有意义。记jd为各用户需求量的负偏差jb是各用户的需求量(,,,=j)约束为jjiijbdx==,,,=jiii)A向B的供货约束:=ddxiv)至少满足用户需求%的约束:jjjiijbddx==,,,=jv)A到B的运货量尽量少也就是运货量尽可能为零。显然负偏差没有意义故有=dxvi)平衡用户B和B的满意水平也就是供应率要相同。约束条件为===ddxxiiiivii)运费尽量少即尽量等于零负偏差没有意义。所以===ijijijdxc目标函数为=)()(mindPddPdPddddPdPdPz计算程序如下。model:sets:plantAA:acustomerBB:broutes(plant,customer):c,xdeviation:d,d,p,pendsetsdata:a=b=c=p=,,,,,,,,,,,p=,,,,,,,,,,,enddatafor(plant(i):consum(customer(j):x(i,j))<a(i))for(customer(j):consum(plant(i):x(i,j))d(j)=b(j))conx(,)d()d()=for(customer(j):consum(plant(i):x(i,j))d(j)d(j)=*b(j))conx(,)d()=consum(plant(i):x(i,))*sum(plant(i):x(i,))d()d()=consum(routes:c*x)d()=objmin=sum(deviation:p*dp*d)End程序中集合Deviation的属性dd分别为各个负、正偏差变量pp分别为目标函数中负、正偏差变量的系数。各优先级取值为:=P=P=P=P=P=P上述程序目标函数的值为观察dd的值可以看出最小运费为元。数据包络分析年ACharnes,WWCooper和ERhodes给出了评价多个决策单元(DecisionMakingUnits简称DMU)相对有效性的数据包络分析方法(dataenvelopmentanalysis,DEA)。目前数据包络分析是评价具有多指标输入和多指标输出系统的较为有效的方法。数据包络分析的基本概念()相对有效评价问题例(多指标评价问题)某市教委需要对六所重点中学进行评价其相应的指标如下表所示。表中的生均投入和非低收入家庭百分比是输入指标生均写作得分和生均科技得分是输出指标。请根据这些指标评价哪些学校是相对有效的。学校ABCDEF生均投入(百元年)非低收入家庭百分比()生均写作得分(分)生均科技得分(分)为求解例先对上表作简单的分析。学校C的两项输出指标都是最高的达到和应该说学校C是最有效的。但从另一方面说对它的投入也是最高的达到和因此它的效率也可能是最低的。究竟如何评价这六所学校呢?这还需要仔细地分析。这是一个多指标输入和多指标输出的问题对于这类评价问题ACharnes,WWCooper和ERhodes建立了评价决策单元相对有效性的CR模型。()数据包络分析的CR模型数据包络分析有多种模型其中CR(由CharnesCooper和Rhodes三位作者的第一个英文字母命名)的建模思路清晰、模型形式简单、理论完善。设有n个DMU每个DMU都有m种投入和s种产出设ijx(mi,,L=nj,,L=)表示第j个DMU的第i种投入量rjy(sr,,L=nj,,L=)表示第j个DMU的第r种产出量iv),,(miL=表示第i种投入的权值ru(sr,,L=)表示第r种产出的权值。向量),,(,njYXjjL=分别表示决策单元j的输入和输出向量v和u分别表示输入、输出权值向量则TmjjjjxxxX),,,(L=TsjjjjyyyY),,,(L=Tmuuuu),,,(L=Tsvvvv),,,(L=。定义决策单元j的效率评价指数为)()(jTjTjXvYuh=(nj,,,L=)评价决策单元j效率的数学模型为maxjTjTXvYust=,,,,,,,vuvunjXvYujTjTL()通过CharnesCooper变换:tv=ωtu=μjTXvt=可以将模型()变化为等价的线性规划问题maxjTjYVμ=st==,,,,,μωωμωjTjTjTXnjYXL()可以证明模型()与模型()是等价的。由于线性规划问题的对偶线性规划模型具有明确的经济意义。下面写出模型()的对偶形式θminst===njYYXXjjjnjjjnjjj,,,,Lλλθλ()对于CR模型()有如下定义。定义若线性规划问题()的最优目标值=jV则称决策单元j是弱DEA有效的。定

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/17
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部