运筹学第四章 目标规划.ppt

第四章目标规划（GoalProgramming）,1961年美经济学家查恩斯(A.charnes)和库柏(W.W.Cooper),目标规划的概念和数学模型,1965年日YnjiIjiri管理目标与控制计算,完善模型并分析了目标的优先级和权系数概念,1969年VeikkoJkenen将目标规划用于生产管理,管理模型及线性规划的工业应用,1972年韩国SangM.Lee决策分析的目标规划,进一步完善了目标规划的作用,1.目标规划的数学模型,例某电子公司录音机和收音机两种产品，它们均需经过两个工厂的加工，每一台录音机在第一个工厂加工2小时，然后送到第二个工厂装配试验2.5小时才变成成品；每一台收音机需在第一个工厂加工4小时，在第二个工厂装配试验1.5小时才变为成品。,录音机与收音机每台厂内的每月储存成本分别为8元和15元。第一个工厂有12台制造机器，每台每天工作8小时，每月正常工作天数为25天；第二个工厂有7台装配试验设备，,每台每天工作时间16小时，每月正常工作天数仍为25天。每台机器每小时运转成本，第一个工厂为18元，第二个工厂为15元。每台录音机的销售利润20元，收音机为23元，依市场预测次月的录音机与收音机的销售量估计分别为1,500台和1,000台。,该公司依下列次序为目标的优先次序，以实现次月的生产与销售目标。,P1厂内的储存成本不超过23,000元；,P2录音机销售量必须完成1,500台；,P3第一，二两工厂的设备应全力运转，,避免有空闲时间，两厂的单位运转成本当作它们间的权系数。,P4第一个工厂的超时作业时间全月份不宜超出30小时；,P5收音机销售量必须完成1,000台；,P6两个工厂的超时工作时间总和应予限制，其限制的比率依各厂每小时运转成本核算为准。,试建立这个问题的数学模型。,目标规划数学模型的有关概念：,1.决策变量与正负偏差变量di+,di(i=1,m),我们对每个目标函数引入正负偏差变量di+,di,di+,di0(i=1,2,m)，其中di+表示第i个目标超出期望值的数值，di表示第i个目标未达到期望值的数值,di+di=0,2.绝对约束和目标约束,绝对约束是指必须严格满足的等式和不等式约束；目标约束是把约束右端看作要追求的目标，有正负偏差的约束。,3.优先因子(优先等级)与权系数,优先因子：,目标的重要程度,首先达到的目标赋予优先因子P1，次位的目标赋于优先因子P2,并规定PkPk+1k=1,K，,权系数：,相同的优先级，各目标的重要程度,4.目标函数(达成函数),构造一个新的目标函数，以求得有关偏差变量的最小值。,在达成函数中，根据对各个目标的不同要求，一般采用三种形式:,(1).若要求尽可能地实现某个目标(第i个目标)的期望值，则希望相应的正、负偏差变量di+,di-尽可能地小。,min(di+di),(2).若某个目标允许超过期望值，但希望尽可能不低于期望值。,mindi,(3).若某个目标允许低于期望值，但不得超过期望值。,mindi+,例.列出前述问题的目标规划模型。,解设x1,x2分别表示下月份录音机与收音机的生产量。,di+,di为相应目标与约束的正、负偏差变量。,1.第一、二两工厂设备运转时间约束,第一个工厂设备的总工作时间为,81225=2400小时,第二个工厂装配试验设备总工作时间为,16725=2800小时,2x1+4x2+d1-d1+=2400,2.5x1+1.5x2+d2-d2+=2800,2.厂内储存成本约束,8x1+15x2+d3-d3+=23000,3.销售目标约束,x1+d4-d4+=1500,x2+d5-d5+=1000,4.第一个工厂的超过作业时间约束,d1+d11-d11+=30,5.达成函数,min=P1d3+P2d4-+P3(6d1+5d2)+P4d11+P5d5-+P6(6d1+5d2+),达成函数中P3与P6级目标的权系数是取第一、第二两工厂设备每小时运转成本的比率18:15=6:5。,这个问题的目标规划模型为：,min=P1d3+P2d4+P3(6d1+5d2)+P4d11+P5d5+P6(6d1+5d2+)s.t2x1+4x2+d1-d1+=24002.5x1+1.5x2+d2-d2+=28008x1+15x2+d3-d3+=23000 x1+d4-d4+=1500 x2+d5-d5+=1000d1+d11-d11+=30 x1,x20,di,di+0(i=1,2,3,4,5,11),目标规划的一般数学模型为min=Pl(lk+dk+lkdk)ckjxj+dk-dk+=gkk=1,2,kaijxj(=,)bii=1,2,mxj0j=1,2,ndk,dk+0k=1,2,K,k=1,K,l=1,L,j=1,n,j=1,n,2.目标规划的图解法,目标规划解法是在可行域内，首先是寻找一个使P1级别的各目标均满足的区域R1，然后再在R1中寻找一个使P2级别的各目标均满足的区域R2(R1R2)，再在R2中寻找一个满足P3级别各目标的区域R3(R1R2R3)，如此下去直到寻找到一个区域Rk，满足Pk级别各目标，这个Pk即为我们的解。我们称Ri为第i级的解空间。,如果某一个Ri已退化为一点，则计算亦应终止，这一点亦即为最优解，它只能满足,P1,P2,Pi级目标，而无法进一步改进；以满足Pi+1,Pi+2,Pk各级目标。,例用图解法解下列目标规划模型,min=P1(d1+d2+)+P2d3+P3d4+P4d5+,s.t.4x1+5x2+d1-d1+=80G14x1+2x2+d2-d2+=48G280 x1+100 x2+d3-d3+=800G3x1+d4-d4+=6G4x1+x2+d5-d5+=7G5x1,x20,di,di+0(i=1,5),解作目标约束时，先令di-,di+=0，作相应的直线，然后用垂直于各目标直线的箭头反映偏差变量的增加。,在满足了优先级别P3后，得R3，最后一个优先级别P4，是通过极小化d5+而实现。由于不可能在R3内使d5+=0，因此为了保证较高级别目标不被破坏，我们只能在R3中选择一点，使其对应的d5+的尽可能地小。这一点为X*=(0,8)，在此点d5+=1。说明P4级目标不能完全实现，尚多于目标期望值1个单位。,x1,x2,O,8,6,8,10,12,24,16,20,6,d1+,d2+,d3+,d4+,d5+,R1,R2,R3,解X*=（0，8）,3.解目标规划的单纯形法,(1).因目标规划的目标函数为最小化，所以以j0为最优判别准则；,(2).因非基变量的检验数含有不同等级的优先因子，即j=kjPkj=1,n,因P1P2P3Pk，从每个检验数整体来看：检验数的正、负首先决定于P1的系数1j的正、负，若1j=0，这J时此检验数的正、负就决定于P2的系数2j的正、负，,解目标规划的计算步骤：,(1).建立初始单纯形表，在表中将检验数行按优先因子分别列成k行，设k=1；,(2).检查该行中是否存在负数，且对应的前k-1行的系数是零，若取其中最小者对应的变量为换入变量，转(3)，若无负数，则转(5)。,(3).按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量；,(4).按单纯形法进行基变换运算，建立新的计算表，返回(2)；,(5).当k=K时，计算结束，表中的解即为满意解，否则置k=k+1，返回(2)。,例某公司生产A,B两种塑料布，这两种产品每小时的产量均为1000米(宽度为2米)，该公司每天采用两班制生产，每周最大工作时间为80小时。按预测，A,B两种塑料布每周市场的最大销售量分别为70,000米和45,000米，A种塑料布每米的利润为2.5元，B种塑料布每米的利润是1.5元。试确定公司每周A,B两种塑料布的生产量x1和x2(单位:千米)，公司的目标是：,P1:避免每周80小时生产能力的过少利用；,P2:加班时间限制在10小时以内；,P3:A,B两种塑料布的每周产量分别达到70,000米和45,000米，但不得超出。其权系数依它们每米的利润为准；,P4:尽量减少加班。,解这个问题的目标规划模型。,1.每周可利用的工作时间约束,x1+x2+d1-d1+=80,2.每周可利用的加班时间约束,d1+d11-d11+=10,3.每周塑料布产量约束,x1+d2=70,x2+d3=45,权系数为2.5:1.5=5:3,目标规划模型如下：,min=P1d1+P2d11+P3(5d2+3d3)+P4d1+,s.t.x1+x2+d1-d1+=80,x1+d2=70,x2+d3=45,d1+d11d11+=10,x1,x2,di,di+0(i=1,2,3,11),XBbx1x2d1d1+d2d3d11d11+27010001000d34501000100d111000010011P1000100000P2000000001P3000005300P4000010000,27010001000d34501000100d111000010011P1-80-1-1010000P2000000001P3-485-5-3000000P4000010000,XBbx1x2d2-d2+d3-d3+d11-d11+d1100111-1000d27010001000d34501000100d111000010011P1-100-1011000P2000000001P3-1350-3005000P4000010000,XBbx1x2d2-d2+d3-d3+d11-d11+x2100111-1000 33500-111100d111000010011P1000100000P2000000001P3-105003-32000P4000010000,XBbx1x2d2-d2+d3-d3+d11-d11+x2200110-101-132500-101111d1+1000010011P1000100000P2000000001P3-750030203-3P4-100001001+1,这个问题的满意解：x1=70,x2=20,d1=0,d1+=10,d2=0,d3=25,d11=0,d11+=0,4.灵敏度分析,目标规划有三种基本作用：,(1).在规定条件下，来判断目前投入的资源能否实现指定的目标：,(2).在规定条件下，来判断各个既定目标能实现的程度；,(3).在各种投入情况、约束条件、既定目标、目标的优先等级及权系数等组合、变换，进行模拟分析，以选择最佳的决策方案。,灵敏度分析所研究的变化通常有以下几种：,(1).约束条件右边常数(包括资源约束和各目标的期望值的变化)；,(2).达成函数中偏差变量优先等级及权系数的变化；,(3).约束条件中各变量系数的变化；,(4).加入新的变量(决策变量或偏差变量)；,(5).加入新的约束。,例同上例，将原目标函数变为,min=P1d1+P3d2+P4d3+3P4d1+P2d11+,解将新目标函数写入最终表，经一步变化，得(见红笔),XBbx1x2d2d2+d3d3+d11d11+x2200110-101-132500-101111d1+10000