目标规划

-395-第二十一章目标规划§1引言1．线性规划的局限性只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题。2．实际决策中，衡量 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 优劣考虑多个目标这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，线性规划则无能为力。3．目标规划（GoalProgramming）美国经济学家查恩斯（A.Charnes）和库柏（W.W.Cooper）在1961年出版的《管理模型及线性规划的工业应用》一 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 中，首先提出的。4．求解思路（1）加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。（2）优先等级法将各目标按其重要程度不同的优先等级，转化为单目标模型。（3）有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。§2目标规划的数学模型为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。例1某工厂生产I，II两种产品，已知有关数据见表1，试求获利最大的生产方案。表1III拥有量原 材料 关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料 kg2111设备hr1210利润元/件810解这是一个单目标的规划问题。设生产产品I，II的量分别为21,xx时获利最大，建立如下线性规划模型：21108maxxxz+=⎪⎩⎪⎨⎧≥≤+≤+0,102112212121xxxxxx最优决策方案为：62,3,4**2*1===zxx元。但实际上工厂在作决策方案时，要考虑市场等一系列其它条件。如（i）根据市场信息，产品I的销售量有下降的趋势，故考虑产品I的产量不大于产品II。（ii）超过计划供应的原材料，需要高价采购，这就使成本增加。（iii）应尽可能充分利用设备，但不希望加班。-396-（iv）应尽可能达到并超过计划利润指标56元。这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解决这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。1.正、负偏差变量设d为决策变量的函数，正偏差变量}0,max{0ddd−=+表示决策值超过目标值的部分，负偏差变量}0,min{0ddd−−=−表示决策值未达到目标值的部分，这里0d表示d的目标值。因决策值不可能既超过目标值同时又未达到目标值，即恒有0=×−+dd。2.绝对（刚性）约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如：例1的目标函数21108xxz+=可变换为目标约束561081121=−+++−ddxx。绝对约束11221≤+xx可变换为目标约束1122221=−+++−ddxx。3.优先因子（优先等级）与权系数一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同。凡要求第一位达到的目标赋于优先因子1P，次位的目标赋于优先因子L,2P，并规定qkPPkk,,2,1,1L=>>+。表示kP比1+kP有更大的优先权。以此类推，若要区别具有相同优先因子的两个目标的差别，这时可分别赋于它们不同的权系数jw，这些都由决策者按具体情况而定。4.目标规划的目标函数目标规划的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋于相应的优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是),(min−+=ddfz。其基本形式有三种：（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时)(min−++=ddfz（2）要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小，这时)(min+=dfz（3）要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时)(min−=dfz对每一个具体目标规划问题，可根据决策者的要求和赋于各目标的优先因子来构造目标函数，以下用例子说明。例2例1的决策者在原材料供应受严格限制的基础上考虑：首先是产品II的产量不低于产品I的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于56元。求决策方案。解按决策者所要求的，分别赋于这三个目标321,,PPP优先因子。这问题的数学-397-模型是−+−++++3322211)(mindPddPdP⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=−++=−++=−+−≤++−+−+−+−.3,2,1,0,,,5610810201122133212221112121iddxxddxxddxxddxxxxii5．目标规划的一般数学模型设jx（nj,,2,1L=）是目标规划的决策变量，共有m个约束是刚性约束，可能是等式约束，也可能是不等式约束。设有l个柔性目标约束，其目标规划约束的偏差为−+iidd,（li,,2,1L=）。设有q个优先级别，分别为qPPP,,,21L。在同一个优先级kP中，有不同的权重，分别记为),,2,1(,ljwwkjkjL=−+。因此目标规划模型的一般数学表达式为⎟⎟⎠⎞⎜⎜⎝⎛+=∑∑=++−−=ljjkjjkjqkkdwdwPz11min⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥=≥==−+=≥=≤+−=+−=∑∑liddnjxligddxcmibxaiijnjiiijijnjijij,,2,1,0,,,2,1,0,,2,1,,,1,),(11LLLL建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它们都具有一定的主观性和模糊性，可以用专家评定法给以量化。§3求解目标规划的序贯式算法序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。求解目标规划的序贯算法对于qk,,2,1L=，求解单目标规划∑=++−−+=ljjkjjkjdwdwz1)(min（1）s.t.∑==≥=≤njijijmibxa1,,1,),(L（2）∑=+−==−+njiiijijligddxc1,,2,1,L（3）-398-*1)(sljjsjjsjzdwdw≤+∑=++−−，1,,2,1−=ksL，（4）njxj,,2,1,0L=≥（5）liddii,,2,1,0,L=≥+−（6）其最优目标值为*kz，当1=k时，约束（4）为空约束。当qk=时，*qz所对应的解*x为目标规划的最优解。注此时最优解的概念与线性规划最优解的概念已有所不同，但为方便起见，仍称为最优解。例3某企业生产甲、乙两种产品，需要用到CBA,,三种设备，关于产品的赢利与使用设备的工时及限制如表2所示。问该企业应如何安排生产，才能达到下列目标：表2甲乙设备的生产能力（h）A(h/件)2212B(h/件)4016C(h/件)0515赢利（元/件）200300（1）力求使利润指标不低于1500元；（2）考虑到市场需求，甲、乙两种产品的产量比应尽量保持1:2；（3）设备A为贵重设备，严格禁止超时使用；（4）设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班。在重要性上，设备B是设备C的3倍。建立相应的目标规划模型并求解。解设备A是刚性约束，其余是柔性约束。首先，最重要的指标是企业的利润，因此，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2的比例，列为第二级；再次，设备BC,的工作时间要有所控制，列为第三级。在第三级中，设备B的重要性是设备C的三倍，因此，它们的权重不一样，设备B前的系数是设备C前系数的3倍。设生产甲乙两种产品的件数分别为21,xx，相应的目标规划模型为)33()(min433322211+−+−+−+++++=dddPddPdPz（7）s.t.122221≤+xx（8）15003002001121=−+++−ddxx（9）022221=−+−+−ddxx（10）164331=−++−ddx（11）155442=−++−ddx（12）0,,,21≥+−iiddxx，4,3,2,1=i（13）序贯算法中每个单目标问题都是一个线性规划问题，可以使用LINGO软件进行求解。求第一级目标。LINGO程序如下：model:sets:-399-variable/1..2/:x;S_Con_Num/1..4/:g,dplus,dminus;S_con(S_Con_Num,Variable):c;endsetsdata:g=150001615;c=2003002-14005;enddatamin=dminus(1);2*x(1)+2*x(2)<12;@for(S_Con_Num(i):@sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i));end求得dminus(1)=0，即目标函数的最优值为0，第一级偏差为0。求第二级目标，LINGO程序如下：model:sets:variable/1..2/:x;S_Con_Num/1..4/:g,dplus,dminus;S_con(S_Con_Num,Variable):c;endsetsdata:g=150001615;c=2003002-14005;enddatamin=dplus(2)+dminus(2);!二级目标函数;2*x(1)+2*x(2)<12;@for(S_Con_Num(i):@sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i));dminus(1)=0;!一级目标约束;@for(variable:@gin(x));end求得目标函数的最优值为0，即第二级的偏差仍为0。求第三级目标，LINGO程序如下：model:sets:variable/1..2/:x;S_Con_Num/1..4/:g,dplus,dminus;S_con(S_Con_Num,Variable):c;endsetsdata:g=150001615;c=2003002-14005;enddatamin=3*dplus(3)+3*dminus(3)+dplus(4);!三级目标函数;2*x(1)+2*x(2)<12;@for(S_Con_Num(i):@sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i));dminus(1)=0;!一级目标约束;dplus(2)+dminus(2)=0;!二级目标约束;end目标函数的最优值为29，即第三级偏差为29。-400- 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 计算结果，21=x，42=x，1001=+d，因此，目标规划的最优解为)4,2(*=x，最优利润为1600。上述过程虽然给出了目标规划问题的最优解，但需要连续编几个程序，这样在使用时不方便，下面用LINGO软件，编写一个通用的程序，在程序中用到数据段未知数据的编程方法。例4（续例3）按照序贯式算法，编写求解例3的通用LINGO程序。model:sets:level/1..3/:p,z,goal;variable/1..2/:x;h_con_num/1..1/:b;s_con_num/1..4/:g,dplus,dminus;h_con(h_con_num,variable):a;s_con(s_con_num,variable):c;obj(level,s_con_num)/11,22,33,34/:wplus,wminus;endsetsdata:ctr=?;goal=??0;b=12;g=150001615;a=22;c=2003002-14005;wplus=0131;wminus=1130;enddatamin=@sum(level:p*z);p(ctr)=1;@for(level(i)|i#ne#ctr:p(i)=0);@for(level(i):z(i)=@sum(obj(i,j):wplus(i,j)*dplus(j)+wminus(i,j)*dminus(j)));@for(h_con_num(i):@sum(variable(j):a(i,j)*x(j))<b(i));@for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i));@for(level(i)|i#lt#@size(level):@bnd(0,z(i),goal(i)));end当程序运行时，会出现一个对话框。在做第一级目标计算时，ctr输入1，goal(1)和goal(2)输入两个较大的值，表明这两项约束不起作用。求得第一级的最优偏差为0，进行第二轮计算。在第二级目标的运算中，ctr输入2。由于第一级的偏差为0，因此goal(1)的输入值为0，goal(2)输入一个较大的值。求得第二级的最优偏差仍为0，进行第三级计算。在第三级的计算中，ctr输入3。由于第一级、第二级的偏差均是0，因此，goal(1)和goal(2)的输入值也均是0。最终结果是：21=x，42=x，最优利润是1600元，第三级的最优偏差为29。§4多标规划的Matlab解法多目标规划可以归结为-401-γγ,minx使得goalweightxF≤⋅−γ)(beqxAeqbxA=⋅≤⋅,0)(,0)(=≤xceqxcubxlb≤≤其中lbbeqbgoalweightx,,,,,和ub是向量，A和Aeq是矩阵；)(),(xceqxc和)(xF是向量函数，他们可以是非线性函数。)(xF是所考虑的目标函数，goal是欲达到的目标，多目标规划的Matlab函数fgoalattain的用法为［x,fval］=fgoalattain('fun',x0,goal,weight)［x,fval］=fgoalattain('fun',x0,goal,weight,A,b)［x,fval］=fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq)［x,fval］=fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)其中fun是用M文件定义的目标向量函数，x0是初值，weight是权重。A,b定义不等式约束A*x≤b，Aeq,beq定义等式约束Aeq*x=Beq，nonlcon是用M文件定义的非线性约束c(x)≤0，ceq(x)=0。返回值fval是目标向量函数的值。要完整掌握其用法，请用helpfgoalattain或typefgoalattain查询相关的帮助。例5求解多目标线性规划问题4224321123min708090100maxxxZxxxxZ+=+++=⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+≤+≥+≥+4,,1,0482312023303042314321Lixxxxxxxxxi解（i）编写M函数Fun.m:functionF=Fun(x);F=[-100*x(1)-90*x(2)-80*x(2)-70*x(4)3*x(2)+2*x(4)];（ii）编写M文件a=[-1-10000-1-130200302];b=[-30-3012048]';c1=[-100-90-80-70];c2=[0302];[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1))%求第一个目标函数的目标值[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1))%求第二个目标函数的目标值g3=[g1;g2];%目标goal的值[x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4,1))-402-%这里权重weight=目标goal的绝对值就可求得问题的解。如果使用匿名函数，只要一个程序文件，就可以得到计算结果。程序如下：clc,cleara=[-1-10000-1-130200302];b=[-30-3012048]';c1=[-100-90-80-70];c2=[0302];fun=@(x)[c1;c2]*x;%用匿名函数定义目标向量[x1,g1]=linprog(c1,a,b,[],[],zeros(4,1))%求第一个目标函数的目标值[x2,g2]=linprog(c2,a,b,[],[],zeros(4,1))%求第二个目标函数的目标值g3=[g1;g2];%目标goal的值[x,fval]=fgoalattain(fun,rand(4,1),g3,abs(g3),a,b,[],[],zeros(4,1))§5目标规划模型的实例前面介绍了目标规划的求解方法，这里再介绍几个目标规划模型的例子，帮助我们进一步了解目标规划模型的建立和求解过程。例6某计算机公司生产三种 型号 pcr仪的中文说明书矿用离心泵型号大全阀门型号表示含义汽车蓄电池车型适配表汉川数控铣床 的笔记本电脑CBA,,。这三种笔记本电脑需要在复杂的装配线上生产，生产1台CBA,,型号的笔记本电脑分别需要5，8，12（h）。公司装配线正常的生产时间是每月1700h。公司营业部门估计CBA,,三种笔记本电脑的利润分别是每台1000，1440，2520（元），而公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标：第一目标：充分利用正常的生产能力，避免开工不足；第二目标：优先满足老客户的需求，CBA,,三种型号的电脑分别为50，50，80（台），同时根据三种电脑的纯利润分配不同的权因子；第三目标：限制装配线加班时间，最好不要超过200h；第四目标：满足各种型号电脑的销售目标，CBA,,型号分别为100，120，100（台），再根据三种电脑的纯利润分配不同的权因子；第五目标：装配线的加班时间尽可能少。请列出相应的目标规划模型，并用LINGO软件求解。解建立目标约束。（1）装配线正常生产设生产CBA,,型号的电脑为321,,xxx（台），−1d为装配线正常生产时间未利用数，+1d为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为⎪⎩⎪⎨⎧=−++++−−17001285}{min113211ddxxxd（14）（2）销售目标优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子，CBA,,三-403-种型号的电脑每小时的利润是122520,81440,51000，因此，老客户的销售目标约束为⎪⎪⎩⎪⎪⎨⎧=−+=−+=−++++−+−+−−−−805050}211820{min443332221432ddxddxddxddd（15）再考虑一般销售。类似上面的讨论，得到⎪⎪⎩⎪⎪⎨⎧=−+=−+=−++++−+−+−−−−100120100}211820{min773662551765ddxddxddxddd（16）（3）加班限制首先是限制装配线加班时间，不允许超过200h，因此得到⎪⎩⎪⎨⎧=−++++−+19001285}{min883218ddxxxd（17）其次装配线的加班时间尽可能少，即⎪⎩⎪⎨⎧=−++++−+17001285}{min113211ddxxxd（18）写出目标规划的数学模型+−−−+−−−−++++++++=15765483432211)211820()211820(mindPdddPdPdddPdPzs.t.1700128511321=−++++−ddxxx805050443332221=−+=−+=−++−+−+−ddxddxddx100120100773662551=−+=−+=−++−+−+−ddxddxddx1900128588321=−++++−ddxxx0,,,21≥+−iiddxx，8,,2,1L=i写出相应的LINGO程序如下：model:sets:level/1..5/:p,z,goal;variable/1..3/:x;-404-s_con_num/1..8/:g,dplus,dminus;s_con(s_con_num,variable):c;obj(level,s_con_num)/11,22,23,24,38,45,46,47,51/:wplus,wminus;endsetsdata:ctr=?;goal=????0;g=17005050801001201001900;c=58121000100011000100015812;wplus=000010001;wminus=120182102018210;enddatamin=@sum(level:p*z);p(ctr)=1;@for(level(i)|i#ne#ctr:p(i)=0);@for(level(i):z(i)=@sum(obj(i,j):wplus(i,j)*dplus(j)+wminus(i,j)*dminus(j)));@for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i));@for(level(i)|i#lt#@size(level):@bnd(0,z(i),goal));end经5次计算得到1001=x，552=x，803=x。装配线生产时间为1900h，满足装配线加班不超过200h的要求。能够满足老客户的需求，但未能达到销售目标。销售总利润为3808002520801440551000100=×+×+×（元）例7已知三个工厂生产的产品供应给四个客户，各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费用如表3所示，其中总生产量小于总需求量。表3运输费用表用户1234生产量工厂15267300工厂23546200工厂34523400需求量200100450250（1）求总运费最小的运输问题的调度方案。（2）上级部门经研究后，制定了新调配方案的8项指标，并规定了重要性的次序。第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于80％；第四目标：应尽量满足各用户的需求；第五目标：新方案的总运费不超过原运输问题的调度方案的10％；第六目标：因道路限制，工厂2到用户4的路线应尽量避免运输任务；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少总运费。请列出相应的目标规划模型，并用LINGO程序求解。解（1）求解原运输问题由于总生产量小于总需求量，虚设工厂4，生产量为100个单位，到各个用户间的运费单价为0。用LINGO软件求解，得到总运费是2950元，运输方案如表4所示。-405-表4运输方案表用户1234生产量工厂1100200300工厂2200200工厂3250150400工厂4100100需求量200100450250（2）下面按照目标的重要性的等级列出目标规划的约束和目标函数。设ijx为工厂)3,2,1(=ii调配给用户)4,3,2,1(=jj的运量，ijc表示从工厂i到用户j的单位产品的运输费用，)4,3,2,1(=jaj表示第j个用户的需求量，)3,2,1(=ibi表示第i个工厂的生产量。i）供应约束应严格满足，即ijijbx≤∑=41，3,2,1=iii）供应用户1的产品中，工厂3的产品不少于100个单位，即1001131=−++−ddxiii）需求约束。各用户的满足率不低于80％，即16022312111=−++++−ddxxx8033322212=−++++−ddxxx36044332313=−++++−ddxxx20055342414=−++++−ddxxx应尽量满足各用户的需求，即20066312111=−++++−ddxxx10077322212=−++++−ddxxx45088332313=−++++−ddxxx25099342414=−++++−ddxxxiv）新方案的总运费不超过原方案的10％（原运输方案的运费为2950元），即324510103141=−++−==∑∑ddxciijjijv）工厂2到用户4的路线应尽量避免运输任务，即0111124=−++−ddxvi）用户1和用户3的满足率应尽量保持平衡，即0)(450200)(1212332313312111=−+++−+++−ddxxxxxxvii）力求总运费最少，即295013133141=−++−==∑∑ddxciijjij目标函数为-406-++−++−−−−−−−−−−++++++++++++++=1381212711610598764543231291)()()(mindPddPdPdPddddPddddPdPdPz编写LINGO程序如下：model:sets:level/1..8/:p,z,goal;s_con_num/1..13/:g,dplus,dminus;plant/1..3/:a;customer/1..4/:b;routes(plant,customer):c,x;obj(level,s_con_num)/19,21,32,33,34,35,46,47,48,49,510,611,712,813/:wplus,wminus;endsetsdata:ctr=?;goal=???????0;a=300200400;b=200100450250;c=526735464523;wplus=00000000001111;wminus=11111111110010;enddatamin=@sum(level:p*z);p(ctr)=1;@for(level(i)|i#ne#ctr:p(i)=0);@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(3,1)+dminus(1)-dplus(1)=100;@for(customer(j):@sum(plant(i):x(i,j))+dminus(1+j)-dplus(1+j)=0.8*b(j);@sum(plant(i):x(i,j))+dminus(5+j)-dplus(5+j)=b(j));@sum(routes:c*x)+dminus(10)-dplus(10)=3245;x(2,4)+dminus(11)-dplus(11)=0;@sum(plant(i):x(i,1))-20/45*@sum(plant(i):x(i,3))+dminus(12)-dplus(12)=0;@sum(routes:c*x)+dminus(13)-dplus(13)=2950;@for(level(i)|i#lt#@size(level):@bnd(0,z(i),goal));end经8次运算，得到最终的计算结果，见表5。总运费为3360元，高于原运费410元，超过原方案10％的上限115元。表5用户1234生产量工厂1100200300工厂290110200工厂310025050400实际运量190100360250需求量200100450250下面我们给出目标规划的另外一种解法，把所有的目标偏差加权求和。例8某公司从三个仓库向四个用户提供某种产品。仓库与用户所在地的供需量及-407-单位运价见表6。表6单位：元/件1B2B3B4B供应量（件）1A52673002A35462003A4523400需求量（件）200100450250公司有关部门根据供求关系和经营条件，确定了下列目标：1P：完全满足用户4B的需要；2P：3A向1B提供的产品数量不少于100件；3P：每个用户的供应量不少于其需求的80%；4P：从仓库1A到用户2B之间的公路正在大修，运货量应尽量少；5P：平衡用户1B和2B的供货满意水平；6P：力求总运费最省；试求满意的调运方案。解这是具有6个优先级目标的运输问题。设ijx为从仓库iA到用户jB的运输量（3,2,1=i；4,3,2,1=j），+−kkdd,为第k个目标约束中，未达到规定目标的负偏差和超过目标的正偏差。ia（3,2,1=i）是第i个仓库的供应量。约束条件有以下几种：i）供应约束（硬约束）。ijijax≤∑=41，3,2,1=iii）需求约束。由于产品供不应求，向各用户的实际供应量不可能超过需求量，所以需求正偏差没有意义。记−jd为各用户需求量的负偏差，jb是各用户的需求量（4,3,2,1=j），约束为jjiijbdx=+−=∑31，4,3,2,1=jiii）3A向1B的供货约束：1005531=−++−ddxiv）至少满足用户需求80％的约束：jjjiijbddx8.05531=−+++−+=∑，4,3,2,1=jv）1A到2B的运货量尽量少，也就是运货量尽可能为零。显然，负偏差没有意义，故有01012=−+dxvi）平衡用户1B和4B的满意水平，也就是供应率要相同。约束条件为-408-04502001111313311=−+−+−==∑∑ddxxiiiivii）运费尽量少，即尽量等于零，负偏差没有意义。所以0311241=−∑∑=+=ijijijdxc目标函数为++−+−−−−−−+++++++++=12611115104987635241)()(mindPddPdPddddPdPdPz计算程序如下。model:sets:plant/A1..A3/:a;customer/B1..B4/:b;routes(plant,customer):c,x;deviation/1..12/:d1,d2,p1,p2;endsetsdata:a=300200400;b=200100450250;c=526735464523;p1=0,0,0,100000,10000,1000,1000,1000,1000,0,10,0;p2=0,0,0,0,0,0,0,0,0,100,10,1;enddata@for(plant(i):[con1]@sum(customer(j):x(i,j))<a(i));@for(customer(j):[con2]@sum(plant(i):x(i,j))+d1(j)=b(j));[con3]x(3,1)+d1(5)-d2(5)=100;@for(customer(j):[con4]@sum(plant(i):x(i,j))+d1(5+j)-d2(5+j)=0.8*b(j));[con5]x(1,2)-d2(10)=0;[con6]@sum(plant(i):x(i,1))-4/9*@sum(plant(i):x(i,3))+d1(11)-d2(11)=0;[con7]@sum(routes:c*x)-d2(12)=0;[obj]min=@sum(deviation:p1*d1+p2*d2);end程序中集合Deviation的属性d1，d2分别为各个负、正偏差变量，p1，p2分别为目标函数中负、正偏差变量的系数。各优先级取值为：5110=P，4210=P，3310=P，2410=P，105=P，16=P上述程序目标函数的值为3570，观察d1，d2的值可以看出最小运费为3570元。§6数据包络分析1978年A.Charnes,W.W.Cooper和E.Rhodes给出了评价多个决策单元（DecisionMakingUnits，简称DMU）相对有效性的数据包络分析方法（dataenvelopmentanalysis,DEA）。目前，数据包络分析是评价具有多指标输入和多指标输出系统的较为有效的方法。6.1数据包络分析的基本概念（1）相对有效评价问题例9（多指标评价问题）某市教委需要对六所重点中学进行评价，其相应的指标如表7所示。表7中的生均投入和非低收入家庭百分比是输入指标，生均写作得分和生均-409-科技得分是输出指标。请根据这些指标，评价哪些学校是相对有效的。表7评价指标表学校ABCDEF生均投入(百元/年)89.3986.25108.13106.3862.4047.19非低收入家庭百分比(%)64.39999.69696.279.9生均写作得分(分)25.228.229.426.427.225.2生均科技得分(分)223287317291295222为求解例9，先对上表作简单的分析。学校C的两项输出指标都是最高的，达到29.4和317，应该说，学校C是最有效的。但从另一方面说，对它的投入也是最高的，达到108.13和99.6，因此，它的效率也可能是最低的。究竟如何评价这六所学校呢？这还需要仔细地分析。这是一个多指标输入和多指标输出的问题，对于这类评价问题，A.Charnes,W.W.Cooper和E.Rhodes建立了评价决策单元相对有效性的C2R模型。（2）数据包络分析的C2R模型数据包络分析有多种模型，其中C2R（由Charnes，Cooper和Rhodes三位作者的第一个英文字母命名）的建模思路清晰、模型形式简单、理论完善。设有n个DMU，每个DMU都有m种投入和s种产出，设ijx（mi,,1L=，nj,,1L=）表示第j个DMU的第i种投入量，rjy（sr,,1L=，nj,,1L=）表示第j个DMU的第r种产出量，iv),,1(miL=表示第i种投入的权值，ru（sr,,1L=）表示第r种产出的权值。向量),,1(,njYXjjL=分别表示决策单元j的输入和输出向量，v和u分别表示输入、输出权值向量，则TmjjjjxxxX),,,(21L=，TsjjjjyyyY),,,(21L=，Tmuuuu),,,(21L=，Tsvvvv),,,(21L=。定义决策单元j的效率评价指数为)/()(jTjTjXvYuh=，（nj,,2,1L=）评价决策单元0j效率的数学模型为00maxjTjTXvYus.t.⎪⎩⎪⎨⎧≠≠≥≥=≤0,0,0,0,,2,1,1vuvunjXvYujTjTL（19）通过Charnes-Cooper变换：tv=ω，tu=μ，01jTXvt=，可以将模型（19）变化为等价的线性规划问题00maxjTjYVμ=-410-s.t.⎪⎪⎩⎪⎪⎨⎧≥≥==≥−0,01,,2,1,00μωωμωjTjTjTXnjYXL（20）可以证明，模型（19）与模型（20）是等价的。由于线性规划问题的对偶线性规划模型具有明确的经济意义。下面写出模型（20）的对偶形式θmins.t.⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥≥≤∑∑==njYYXXjjjnjjjnjjj,,2,1,00011Lλλθλ（21）对于C2R模型（20），有如下定义。定义1若线性规划问题（20）的最优目标值10=jV，则称决策单元0j是弱DEA有效的。定义2若线性规划问题（20）存在最优解00>jω，00>jμ，并且其最优目标值10=jV，则称决策单元0j是DEA有效的。从上述定义可以看出，所谓DEA有效，就是指那些决策单元，它们的投入产出比达到最大。因此，我们可以用DEA来对决策单元进行评价。（3）C2R模型的求解从上面的模型可以看到，求解C2R模型，需要求解若干个线性规划，这一点可以用LINGO软件完成。例10（续例9）运用C2R模型（20）求解例9。解按照C2R模型写出相应的LINGO程序如下：model:sets:dmu/1..6/:s,t,p;!决策单元;inw/1..2/:w;!输入权重;outw/1..2/:u;!输出权重;inv(inw,dmu):x;!输入变量;outv(outw,dmu):y;endsetsdata:ctr=?;x=89.3986.25108.13106.3862.4047.1964.39999.69696.279.9;y=25.228.229.426.427.225.2223287317291295222;enddatamax=@sum(dmu:p*t);p(ctr)=1;@for(dmu(i)|i#ne#ctr:p(i)=0);-411-@for(dmu(j):s(j)=@sum(inw(i):w(i)*x(i,j));t(j)=@sum(outw(i):u(i)*y(i,j));s(j)>t(j));@sum(dmu:p*s)=1;end在上述程序中，ctr的值分别输入6,,2,1L，经过6次计算，得到6个最优目标值1，0.9096132，0.9635345，0.9143053，1，1并且对于学校A（决策单元1）有0,012>>μω，对于学校E（决策单元5）有01>ω，02>μ和对于学校F（决策单元6）有0,011>>μω。因此，学校FEA,,是DEA有效的。习题二十一1.试求解多目标线性规划问题⎩⎨⎧+=+=21221123maxxxzxxzs.t.⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+0,557212121xxxxxx2．一个小型的无线电广播台考虑如何最好地安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每分钟可收入250美元，新闻节目每分钟需支出40美元，音乐节目每播一分钟费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20%，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下：1p：满足法律规定的要求；2p：每天的纯收入最大。试建立该问题的目标规划模型。3.某工厂生产两种产品,每件产品I可获利10元，每件产品II可获利8元。每生产一件产品I，需要3小时；每生产一件产品II，需要2.5小时。每周总的有效时间为120小时。若加班生产，则每件产品I的利润降低1.5元；每件产品II的利润降低1元。决策者希望在允许的工作及加班时间内取得最大利润，试建立该问题的目标规划模型并求解。