搜索
-253-第二十一章目标规划§1引言1．线性规划的局限性只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题。2．实际决策中，衡量方案优劣考虑多个目标这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，LP则无能为力。3．目标规划（GoalProgramming）美国经济学家查恩斯（A.Charnes）和库柏（W.W.Cooper）在1961年出版的《管理模型及线性规划的工业应用》一书中，首先提出的。4．求解思路（1）加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。（2）优先等级法将各目标按其重要程度不同的优先等级，转化为单目标模型。（3）有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。§2目标规划的数学模型为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。例1某工厂生产I，II两种产品，已知有关数据见下表III拥有量原材料kg2111设备hr1210利润元/件810试求获利最大的生产方案。解这是一个单目标的规划问题，用线性规划模型表述为：21108maxxxz+=⎪⎩⎪⎨⎧≥≤+≤+0,102112212121xxxxxx最优决策方案为：62,3,4**2*1===zxx元。但实际上工厂在作决策方案时，要考虑市场等一系列其它条件。如（i）根据市场信息，产品I的销售量有下降的趋势，故考虑产品I的产量不大于产品II。（ii）超过计划供应的原材料，需要高价采购，这就使成本增加。（iii）应尽可能充分利用设备，但不希望加班。-254-（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优先因子。这问题的数学-255-模型是−+−++++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）-256-*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,,三种设备，关于产品的赢利与使用设备的工时及限制如下表所示。问该企业应如何安排生产，才能达到下列目标：甲乙设备的生产能力（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倍。由此得到相应的目标规划模型。)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:variable/1..2/:x;-257-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。-258-分析计算结果，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(