第八章、目标规划(GP)

第八章、目标规划（GP）一、多目标规划问题的提出及数学模型例题1产品资源AB资源限制煤38420水泥43500工日74300利润650900请给出利润最大、使用煤尽可能少的生产方案。设yx,分别为A、B两种产品的生产量。0,300475003442083)83min()900650max(yxyxyxyxyxyx例题2假设在某一段时期内有一笔数量为a亿元的资金，有n个项目可供选择投资，如果对第j个项目投资将用掉ja亿元，收益为jb亿元。请制定最优投资方案。分析：所谓最优就是投资少，收益大。设个项目不投资对第个项目投资对第jj01jx则;1,0maxmin111或jnjjjnjjjnjjjxaxaxbxa通过上面的例题可给出多目标规划的数学模型一般形式：),,2,1(,0)())(,),(),(min(21mixgxfxfxfip其中2p，nTnRxxxx),,,(21二、目标规划的基本概念和目标规划的数学模型(Goalprogramming)目标规划是解决多目标规划问题的一种较为完善和成熟的有效方法，这种方法是由美国著名运筹学家查恩斯（A.charnes）和库柏(w.w.Cooper)于1961年最先提出来的，他强调了系统性，目标规划方法在于寻找一个“尽可能”满足所有目标的解，而不是绝对满足这些目标的值。用目标规划方法处理多目标规划问题时，决策者首先给出各目标的期望值（理想值、目标值）。决策者然后给出各目标的主次轻重顺序（优先因子）评价一个决策方案时，决策方案所得的各个目标函数值（实现值），是否与期望值接近，即用“偏差”来衡量决策方案的优劣、好坏。设ib是)(xfi的期望值。那么niiiibxfp1|)(|min就使决策者追求的目标。ip是第I个目标函数的优先因子。为了具体说明这一方法通过例题先介绍基本的概念和数学模型某厂生产甲、乙两种产品，以致有关数据如下表：产品资源甲乙拥有量原材料2111（千克）设备1210（台时）利润（千元）810如果不考虑其他的因素就可给出获利最大的生产方案。（是一单目标线性规划问题）。实际上工厂决策者在安排生产时有一系列的考虑，如①根据市场信息，产品甲的销售量有下降的趋势，故决定产品甲的生产量不超过产品乙的生产量。②尽可能不超过使用计划供应的原材料，如果超过，需高价采购，使成本增加。③尽可能的使用设备，但不加班。④尽可能的达到并超过计划利润指标56千元。这样在进行生产计划安排时，就要考虑这四个目标，这就是一多目标规划问题。若设21,xx分别是该厂生产甲乙两种产品的产量，则该厂决策者的考虑用数学表达式表示为(4)56108(3)102(2)112(1)021212121xxxxxxxx在使用目标规划描述该问题前，首先介绍目标规划的有关概念1、目标值（理想值）目标值是指预先给定的某个目标函数的期望值，。例如（1）（2）（3）（4）中的右端值：0，11，10，56都是决策者分别对目标所赋予的期望值。实现值或决策值是指决策变量给定后对应的目标函数值。2、正、负偏差量决策值和目标值之间有一定的差异，这种差异称为偏差量。正偏差量：决策值超过目标值的部分，记为d负偏差量：决策值未达到目标值的部分，记为d在一次决策中，决策值不可能既超过目标值有未达到目标值，即恒有0dd并规定0,0dd。在上例中决策者关于利润的考虑用表达式（4），引入偏差量以后变为：5610821ddxx在实现原始目标时，可能出现下面三种情况之一⑴超额完成规定的原始目标（目标值），则表示为：0,0dd⑵未完成规定的原始目标（目标值），则表示为：0,0dd⑶恰好完成规定的原始目标（目标值），则表示为：0,0dd3、目标约束和绝对约束对于每一个目标函数引入了目标值以后形成的目标函数不等式，可把右端项看成要追求的目标值，在实现此目标值时允许发生偏差，因此，引入正负偏差量，即目标函数加上负偏差量减去正偏差量，令其等于目标值，这样形成了新的函数方程，把它作为一个新的约束条件，加入到原问题中去，称这种新的约束条件为目标约束。如本例中（1）（3）（4）化成目标约束为(7)56108(6)102(5)0332122211121ddxxddxxddxx绝对约束是指必须严格满足的等式或不等式约束。如本例中的（2）。绝对约束和目标约束是可以相互转化的。经过以上三步以后，一般的目标函数)(xfi就可表示成iiiibddxf)(4、优先等级与权系数不同目标的主次、轻重有两种差别。一种差别是绝对的，可用优先因子kp来表示，只有在高级优先因子对应的目标已满足的基础上，才能考虑较低级优先因子对应的目标。规定1kkpp，表示kp比1kp有更大的优先权。另一种差别是相对的，具有相同优先因子的目标中，它们的重要程度用权系数j来表示。5、目标规划的目标函数目标规划的目标函数是由各目标约束的偏差量、相应的优先因子和权系数构成。由于目标规划追求的是尽可能接近个既定目标值。也就是各有关偏差量尽可能的小，所以其目标函数只能是极小化。应用时有三种对iiiibddxf)(，要求选取一组x使①如果希望iibxf)(，即)(xfi超过ib可以接受，则对应目标函数为idmin②如果希望iibxf)(，即)(xfi不超过ib可以接受，则对应目标函数为idmin③如果希望iibxf)(，即)(xfi不能超过ib也不能低于ib，则对应目标函数为)min(iidd6、目标规划的数学模型对于本例来说，决策者在原材料供应受严格限制（绝对约束）的基础上考虑：首先是甲的产量不能超过乙的产量，目标约束为（5），因此赋优先级为1p，对应的目标函数为：11mindp。其次是充分利用设备有效台时数，不加班。目标约束为（6），因此赋优先级为2p，对应的目标函数为：)(min222ddp。最后是利润不小于56千元，目标约束为（7），因此赋优先级为3p，对应的目标函数为：33mindp。从而，该例题的目标规划的数学模型为：0,0,561081020112s.t)(min21332122211121213322211iiddxxddxxddxxddxxxxdpddpdpZ三、目标规划的图解法对于两个变量的目标规划的数学模型，可以用图解发来分析求解。以上例来说明。Step1、确定各约束条件的可行域：绝对约束作图与线性规划相同，目标约束作图事先令正、负偏差量为零，作相应的直线，然后在直线旁标上，表明目标约束可沿着两个方向平移。四、目标规划的单纯形法对于已建立好的目标规划数学模型：0)4,3,2,1(,,,,45709080)35(min2121423122211121144332211idddxxdxdxddxxddxxdpddpdpdpSi第一步；建立初始单纯形表基本和单纯形法相同，区别有：检验数的行不再是一行，而是有多少个目标就有多少个检验数行。在写单纯形表中的各模块时注意变量的排列次序。),,,,,,,(21432121ddddddxx),,3,5,0,,0,0(24331pppppCTb)45,70,90,80(00100010000100011000101101000111A选)4,3,2,1(idi为基变量，从而，即4EB,)3,5,0,(331pppCB),,0,0,0,0,3,5()48580(24131311311pppppppCABCppbCbBCBBB检验数行),(11CABCbBCBB按优先等级)4,3,2,1(jpj可列成下面的矩阵。0100000000000003548510000000001000011804321pppp又因为AABbbB11,从而可得单纯形表为：21432121ddddddxx4321pppp0485080010000000000003510000000010000114321dddd4570908000100010000100011000101101000111Step2、判断是否为最优解①如各优先级kppp,,,21行的全体检验数均非证，则相应的单纯形表的最优解是最优解。②前rppp,,,21行的全体检验数均非证，而第1rp行的检验数中有正数，并且在这个正检验数所在列上的前几行中有负检验数，则相应的单纯形表的解为最优解。Step3换基迭代。①按优先等级选取主列，从第一级优先行开始。在单纯形表的上半部中依行取缔一个正的检验数，一次检验数所在的列定为主列。②在主列上，进行换基迭代（同LP）③重复以上两步直到找到最优解。用QM求解多目标规划问题休息