最新最全最易懂自己整理的算法与实例程序讲解第21章 目标规划.docx

第二十一章 目标规划§1 引言1. 线性规划的局限性 只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题2. 实际决策中，衡量方案优劣考虑多个目标 这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的， 也有定性的；有相互补充的，也有相互对立的，LP则无能为力3. 目标规划（Goal Programming）美国经济学家查恩斯（A. Charnes）和库柏（W. W. Cooper）在1961年出版的《管 理模型及线性规划的工业应用》一书中，首先提出的4. 求解思路（1） 加权系数法 为每一目标赋一个权系数，把多目标模型转化成单一目标的模型但困难是要确 定合理的权系数，以反映不同目标之间的重要程度2） 优先等级法 将各目标按其重要程度不同的优先等级，转化为单目标模型3） 有效解法 寻求能够照顾到各个目标，并使决策者感到满意的解由决策者来确定选取哪一个 解，即得到一个满意解但有效解的数目太多而难以将其一一求出§2 目标规划的数学模型 为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍 目标规划的有关概念及数学模型例1某工厂生产I, II两种产品，已知有关数据见下表原材料kg 设 备hr 利润元/件丄~28IIT2拥有量10试求获利最大的生产方案。

解 这是一个单目标的规划问题，用线性规划模型表述为：max z = 8x + 10xa2x + x < 11 2x ¥ 2 x2 < 10 ^x1, x > £ -1 2 一最优决策方案为： x*= 4, x*= 3, z* = 62 元12 但实际上工厂在作决策方案时，要考虑市场等一系列其它条件如① 根据市场信息，产品I的销售量有下降的趋势，故考虑产品I的产量不大于 产品 IIii） 超过计划供应的原材料，需要高价采购，这就使成本增加iii） 应尽可能充分利用设备，但不希望加班iv） 应尽可能达到并超过计划利润指标56 元 这样在考虑产品决策时，便为多目标决策问题目标规划方法是解决这类决策问题的 方法之一下面引入与建立目标规划数学模型有关的概念1. 正、负偏差变量设d为决策变量的函数，正偏差变量d += max{d - d ,0}表示决策值超过目标值0的部分，负偏差变量-= - min{d — d ,0}表示决策值未达到目标值的部分，这里/表 00 示 d 的目 标值因 决策值 不可能既超过 目 标值同 时又未达到目 标值，即恒有 d + x d -= 0 o2. 绝对（刚性）约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。

目标约束是目标规 划特有的，可把约束右端项看作要追求的目标值在达到此目标值时允许发生正或负偏差, 因此在这些约束中加入正、负偏差变量，它们是软约束线性规划问题的目标函数，在给 定目标值和加入正、负偏差变量后可变换为目标约束也可根据问题的需要将绝对约束变 换为目标约束如：例1的目标函数z = 8xi + 10x2可变换为目标约束8x + 10x + d-— d + = 56 o绝 对约束2x + x < 11可变换为目标约束2X1+ x + d-- d += 11 o 1 21 2 2 23. 优先因子（优先等级）与权系数 一个规划问题常常有若干目标但决策者在要求达到这些目标时，是有主次或轻重缓急的不同凡要求第一位达到的目标赋于优先因子 咒，次位的目标赋于优先因子 P ,L,并规定P >> P , k = 1,2,L, q表示P比P 有更大的优先权以此类推，2 k k +1 k k +1若要区别具有相同优先因子的两个目标的差别，这时可分别赋于它们不同的权系数•， 这些都由决策者按具体情况而定 ‘4. 目标规划的目标函数 目标规划的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋于相应的优先因子而构造的。

当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值因 此目标规划的目标函数只能是min z = f （d +, d -）其基本形式有三种：（1） 要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时min z= f（d++ d-）（2） 要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小， 这时min z = f（d +）（3） 要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时min z = f（d -）对每一个具体目标规划问题，可根据决策者的要求和赋于各目标的优先因子来构造目标函 数，以下用例子说明例2例1的决策者在原材料供应受严格限制的基础上考虑：首先是产品II的产量 不低于产品 I 的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于56 元求决策方案解 按决策者所要求的，分别赋于这三个目标P,P ,P优先因子这问题的数学123模型是min P d + + P (d - + d +) + P d -1 1 2 2 2 3 3a2x + x < 11x -1 x +2d - - d + = Qx1+ 2x2 + d1- - d1+ = 1Q▲8X + 10x + d--d + = 56▲x1, x ,d-,d + > Q, 3i = 1,2,3.▼ 1 2 i i5. 目标规划的一般数学模型设x. ( j = 1,2,L, n )是目标规划的决策变量，共有m个约束是刚性约束， 可能是等式约束，也可能是不等式约束。

设有l个柔性目标约束，其目标规划约束的偏 差为d +,d-( i = 1,2,L,l )设有q个优先级别，分别为P ,P ,L,P在同一个优先 i i 1 2 q级P中，有不同的权重，分别记为w+ ,w- (j = 1,2,L,l)因此目标规划模型的一般kj kj□-J - + +w,d. + w d □kj j kj jminj=1 □j=1k 数学表达式为a x < (=,>)b , i = 1,L, mij j i+ d--d + = g, i = 1,2,L, li i ic x♦ ...ij j▲ j=ij = 1,2,L, n▲ x > Q▲j.d-,d + > Q i = 1,2,L, lii建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它都具有一 定的主观性和模糊性，可以用专家评定法给以量化§3 求解目标规划的序贯式算法 序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序 将目标规划问题分解成一系列的单目标规划问题，然后再依次求解求解目标规划的序贯算法min znS.t.乙 a x :ij j龙+厶c x +=工(w- d - + w+ d+)( 1 )kj j kj jj=1< (=,>)b , i=1,L,mi(2)d--d+=g, i=1,2,L,l(3)ij j i i i对于k = 1,2,L, q，求解单目标规划j=1习(w-d- + w+d+) < z*, s = 1,2,L,k 一 1, (4)sj j sj j s j=1x > 0, j = 1,2,L,n (5)jd-,d+> 0, i=1,2,L,l (6)其最优目标值为z*，当k = 1时，约束(4)为空约束。

当k = q时，z*所对应的解x*为 kq 目标规划的最优解注 此时最优解的概念与线性规划最优解的概念已有所不同，但为方便起见，仍 称为最优解例3某企业生产甲、乙两种产品，需要用到A,B, C三种设备，关于产品的赢利与使用设备的工时及限制如下表所示问该企业应如何安排生产，才能达到下列目标：甲乙设备的生产能力(h)A (h/件)2212B (h/件)4016C (h/件)0515赢利(元/件)200300(1) 力求使利润指标不低于1500元；(2) 考虑到市场需求，甲、乙两种产品的产量比应尽量保持1:2；(3) 设备A为贵重设备，严格禁止超时使用；(4) 设备C可以适当加班，但要控制；设备•既要求充分利用，又尽可能不加班 在重要性上，设备B是设备C的3倍建立相应的目标规划模型并求解解 设备 A 是刚性约束，其余是柔性约束首先，最重要的指标是企业的利润， 因此，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持1:2 的比例，列为 第二级；再次，设备:,B的工作时间要有所控制，列为第三级在第三级中，设备的 重要性是设备C的三倍，因此，它们的权重不一样，设备B前的系数是设备C前系数的 3 倍。

由此得到相应的目标规划模型min z = Pd-+P(d++d-)+P(3d++ 3d- +d+)(7)1 1 2 2 2 3 3 3 4s.t.2x + 2x < 12(8)20 2 i i0x+ 序贯算法中每个单目标问题都是一个线性规划问题，可以使用LINGO软件进行求 解300x+d--d+= 1500(9)2x - 1x + d - -2d + =1 0 1(10)4x1+d2--d2+= 162(11)5x1+d-求第一级目标 LINGO 程序如下：model: sets:variable/1..2/:x;-d+3= 15(12)x ,2x , d-256-- , d +4> 0， i =1,2,3,4(13)S_Con_Num/1..4/:g,dplus,dminus;S_con(S_Con_Num,Variable):c;endsetsdata:g=1500 0 16 15;c=200 300 2 -1 4 0 0 5;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(l)=O,即目标函数的最优值为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=1500 0 16 15;c=200 300 2 -1 4 0 0 5;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 ( var i able:@g i n ( x ) ) ;end 求得目标函数的最优值为0,即第二级的偏差仍为0求第三级目标, LINGO 程序如下：model:sets:variable/1..2/:x;S_C。