第十讲目标规划

第十讲目标规划实际工作中，人们经常遇到一类含有多个目标的数学规划问题，称之为多目标规划。在这一讲，我们介绍一种特殊的多目标规划，称为目标规划（GoalProgramming）.目标规划就是要在满足约束的条件下，求出尽可能接近决策者预先给出的每个目标理想值的解---称之为满意解。1、引例某工厂生产甲、乙两种产品，生产单位产品所需的原材料及占用设备台时如表所示。该工厂每天拥有设备台时为10，原材料最大供应量为11。已知生产每单位甲种产品可获利800元，乙种产品为1000元。工厂在安排生产计划时，有如下一系列考虑：（1）由市场信息反馈，产品甲销售量有下降趋势，故决定产品甲的生产量最好不超过产品乙的生产量；（2）不能超计划使用原材料，因为该原材料是国家严格执行配给的；（3）尽可能充分利用设备，但不希望加班；（4）尽可能达到或超过计划利润5600元。甲产品乙产品拥有量原材料2111设备1210利润（百元）810该问题不能用线性规划方法求解，原因是优化目标有多个且约束条件不是绝对的。2、目标规划的基本概念与特点我们结合上例给出目标规划的基本概念与特点。设甲产品和乙产品的产量分别为21,xx.（1）理想值。理想值是决策者事先对每个目标的期望值。（2）绝对约束（硬约束）与目标约束（软约束）。绝对约束是必须严格满足的约束条件，否则就不是可行解，如上例中关于原材料的约束就是硬约束，它可以表述为11221xx.软约束就是最好能够满足的约束，上例中的其他约束都是软约束。相应于每个软约束，可以引入一对偏差变量来描述实际值与理想值的差距。（3）正负偏差变量iidd,.正负偏差变量iidd,是描述每个目标的实际值与理想值差距的一对变量。它们的取值总是非负的。当0id时，表示实际值比理想值大；当0id时，表示实际值比理想值小。如此，每个优化目标就可用一个方程和一个极小值问题来描述，如上例中，第一个目标可描述为11121min0dddxx，第三个目标可描述为)min(102333321ddddxx，第四个目标可描述为44421min56001000800dddxx（4）优先级与权因子。优先级是表示目标重要程度的一种度量，用ip表示，1p表示最高级，2p次之，依此类推。在上例中，如果三个软约束的重要性依次递减，则它们的优先级可依次表示为431,,ppp.也就是说，我们的优化目标首先是1mind，其次是)min(33dd，再其次是4mind.如果我们对优先级作下述理解：021kppp，则整个优化目标可写为4433311)(mindpddpdp.权因子是区别同一优先级中不同偏差变量的重要程度的一种度量。（5）准则函数。准则函数是由各目标约束的正负偏差变量及其相应的优先级、权因子构成的函数。求解目标规划的问题可表述为以相应准则函数为目标函数的极小化问题。准则函数中不含决策变量。构造准则函数的方法：设目标约束为iiiigddxf)(，且其优先级为ip.如果希望iigxf)(，则这个目标在准则函数中贡献的和项为iidp；如果希望iigxf)(，则这个目标在准则函数中贡献的和项为iidp；如果希望iigxf)(，则这个目标在准则函数中贡献的和项为)(iiiddp.3、目标规划的数学模型引例的数学模型4433311)(mindpddpdps.t.01121ddxx11221xx1023321ddxx560010008004421ddxx4,3,1,0,,,21iddxxii4、目标规划的优先级顺序解法目标规划给定以后，先求解关于第一级优先权的目标函数的目标规划，求出最优解后，将当前目标函数的最优值作为约束条件，并入原问题的约束条件中，求解关于下一级优先权的目标函数的目标规划。如此下去，直到解出关于最后一级优先权的目标函数的目标规划。引例的优先级顺序解法求解问题1minds.t.01121ddxx11221xx1023321ddxx560010008004421ddxx4,3,1,0,,,21iddxxii解得0min1dx1x2d1-d1+d3-d3+d4-d4+3.1111113.111111000.666667000再求解规划问题33mindds.t.01121ddxx11221xx1023321ddxx560010008004421ddxx4,3,1,0,,,21iddxxii01d解得0)(min33ddx1x2d1-d1+d3-d3+d4-d4+24200000再求解规划问题4minds.t.01121ddxx11221xx1023321ddxx560010008004421ddxx4,3,1,0,,,21iddxxii01d033dd解得0min4dx1x2d1-d1+d3-d3+d4-d4+24200000所以，最终得到的满意解（最接近事先设定目标的解）为x1x2d1-d1+d3-d3+d4-d4+24200000解释：甲乙产品分别生产2和4件，所有目标都得以实现。21d表示甲产品的数量比乙产品少两件。练习：p461,11-2;p461,11-3;p462,11-7决策变量x1,x2,x3X1+X2+X3=55X3=100.5*X1+0.2*X3+d(1-)-d(1+)=15并且mind(1-)0.3*x2+0.2*x3+d(2-)-d(2+)=10并且mind(2-)Mind(1-)+d(2-)6*X1+4*X2+5*X3+D(1-)-D(1+)=508*X1+7*X2+5*x3+D(2-)-d(2+)=75M=20*X1+15*X2+25*X3-6*(D(1-)+D(1+))-3*D(2-)