运筹学第四章多目标规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 多目标规划,4.1 多目标规划模型及其解的概念,4.2 多目标规划的解法目标规划法,4.1 多目标规划模型及其解的概念,单目标问题：方案,d,j,评价值,f(d,j,),多目标问题：方案,d,j,评价值向量 ,f,1,(d,j,)，,f,p,(d,j,),线性目标规划与线性规划比较，具有下面的特点：,1.线性规划只讨论单目标线性函数在一组线性约束条件下的极值问题，而目标规划能统筹兼顾处理实际问题中经常出现的多种目标关系，求得更切合实际的最优解。,2.线性规划要求在满足所有约束条件的可行解中求最优解，而实际问题中存在着互相矛盾的约束条件，从而制约了线性规划解决问题的范围。目标规划将克服这些互相矛盾的约束条件，找到满意的合理解。,3.线性规划将约束条件看成同样重要、不分主次的条件，而目标规划将依据实际情况去确定模型，并主次有别地进行求解。,4.线性规划求得最优解，可能求得此解将花昂贵的代价，而目标规划寻求的是满意解，即在指定的指标值下求得近似解，实际问题可能更需要这样的满意解。,x,1,0,x,2,M,1,M,2,M,3,M,4,劣解,有效解,最优解,4.2 多目标规划的解法目标规划法,一.目标规划的数学模型,1.问题的提出,例1（,P99,例4.7）,产品,A B,限量,设备工时（月/单位）2 4 12,材料（百吨/单位）3 3 12,利润（万元/单位）4 3.2,如何安排生产计划使获利最大？,设生产产品,A,和,B,各,x,1,x,2,若要求：,1）生产这两种产品的利润最少达到12万元,2）,A,产品的产量尽可能是,B,产品产量的1.5倍,3）为充分利用设备工时，必须使设备的空闲时间尽可能的地小。,问工厂又应如何决定产品,A、B,的产量？,仍设生产产品,A、B,各,x,1,，x,2,资源约束：3,x,1,+3x,2,12,硬约束,令,d,1,-,表示安排生产时，低于计划利润12的量,负偏差变量,令,d,1,+,表示安排生产时，高于计划利润12的量,正偏差变量,故4,x,1,+3.2x,2,-d,1,+,+d,1,-,=12,MinZ,1,=d,1,-,令,d,2,-,表示安排生产时，,A,产品比1.5倍,B,产品产量的不足量,负偏差变量,正偏差变量,令,d,2,+,表示安排生产时，,A,产品比1.5倍,B,产品产量的超过量,故,x,1,-1.5x,2,-d,2,+,+d,2,-,=0,MinZ,2,=d,2,+,+d,2,-,令,d,3,-,表示剩余的设备工时,d,3,+,表示超过的设备工时,故2,x,1,+4x,2,-d,3,+,+d,3,-,=12,MinZ,3,=d,3,-,所以，模型为：,minZ,1,=d,1,-,minZ,2,=d,2,-,+d,2,+,minZ,3,=d,3,-,目标规划模型,转化为单目标：,minW,=P,1,d,1,-,+P,2,(d,2,-,+d,2,+,)+P,3,d,3,-,P,1,第一优先级,P,2,第二优先级,P,3,第三优先级,P,1,P,2,P,3,2.数学模型,（1）目标规划模型的要素,1,决策变量和偏差变量,决策变量：,又称控制变量，用,x,i,表示,偏差变量：,正偏差变量（,d,i,+,）：,实际决策值超过第,i,个目标值的数量,d,i,+,=,f,i,(X)-f,i,(0),f,i,(X,)f,i,(0),0,f,i,(X),f,i,(0),负偏差变量（,d,i,-,）：,d,i,-,=,f,i,(X),f,i,(0),f,i,(0),-,f,i,(X,),f,i,(X,),P,l+1,表示,P,l,比,P,l+1,有,更大的优先权,不同优先权的因子,权系数,相同优先级权的因子,4,.,目标函数,构成,各目标约束的正负偏差变量,相应的优先因子,极小化：尽可能缩小偏离目标值,对于约束,f,i,(x)+d,i,-,-d,i,+,=f,i,(0),(1)若要求恰好达到预定目标值,则,min(d,i,+,+d,i,-,),(2)若要求不超过预定目标值,则,min(d,i,+,),(3)若要求超过预定目标值,则,min(d,i,-,),一般目标规划模型：,软约束,f,i,(x)-d,i,+,+d,i,-,=f,i,(0),X,R,硬约束,d,i,+,0,d,i,-,0(i=1p),二.目标规划的解法,1.图解法,（2个决策变量）,步骤：,1,.,做绝对约束，作法同线性规划图解法；,2,.,做目标约束：令偏差,d,i,=0，,标上,d,i,的,箭头方向；,3,.,按优先级逐步缩小可行解的范围，最后,得到有效解。,例2.用图解法求解目标规划,解,：,（1）先在平面直角坐标系中做出各约束条,件所确定的区域；,（2）标出目标约束在相应直线上,d,i,+,d,i,-,增,大的方向；,（3）根据目标函数的优先因子分析求解。,绝对约束如线性规划图解法,目标约束：令,d,i,+,d,i,-,均为0，作直线,x,1,x,2,0,(1)4,x,1,+3.2x,2,=12,(2)x,1,-1.5x,2,=0,(3)2,x,1,+4x,2,=12,(4)3,x,1,+3x,2,=12,d,1,+,d,1,-,d,2,+,d,2,-,d,3,+,d,3,-,A,B,(1)(2)(4)约束有公共区域：线段,AB,(3)约束与(1)(2)(4)约束无公共区域，故应得满意解,该解尽可能满足(3)约束，故,B,点为满意解,求解直线,x,1,-1.5x,2,=0,与3,x,1,+3x,2,=12,的交点,得到满意解为,x,1,=12/5,x,2,=8/5,2.单纯形法,算法：,（1）建立初始单纯形表，在表中将检验数按优先因子个数分成若干行；,（2）换基迭代时先考虑第一优先级的检验数，若均,0，再考虑第二优先级，以此类推；,（3）若检验数第,k,行的某检验数非正，但它所在列的前,k-1,个检验数均非负，则表中相应解为满意解，停止计算。,例3.用单纯形法求解目标规划：,C,j,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,B,-1,b,x,1,x,2,d,1,+,d,1,-,d,2,+,d,2,-,d,3,-,x,3,P,1,d,1,-,12,4,3.2,-1,1,0,0,0,0,P,2,d,2,-,0,1,-1.5,0,0,-1,1,0,0,P,3,d,3,-,12,2,4,0,0,0,0,1,0,0,x,3,0,3,3,0,0,0,0,0,1,j,P,1,-4,3.2,1,0,0,0,0,0,P,2,-1,1.5,0,0,2,0,0,0,P,3,-2,-4,0,0,0,0,0,0,C,j,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,B,-1,b,x,1,x,2,d,1,+,d,1,-,d,2,+,d,2,-,d,3,-,x,3,P,1,d,1,-,12,0,9.2,-1,1,4,-4,0,0,0,x,1,0,1,-1.5,0,0,-1,1,0,0,P,3,d,3,-,12,0,7,0,0,2,-2,1,0,0,x,3,12,0,7.5,0,0,3,-3,0,1,j,P,1,0,-9.2,1,0,-4,4,0,0,P,2,0,0,0,0,1,1,0,0,P,3,0,7,0,0,-2,2,0,0,C,j,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,B,-1,b,x,1,x,2,d,1,+,d,1,-,d,2,+,d,2,-,d,3,-,x,3,0,x,2,1.3,0,1,-0.11,0.11,0.43,-0.43,0,0,0,x,1,1.95,1,0,-0.165,0.165,-0.355,0.355,0,0,P,3,d,3,-,2.9,0,0,0.77,-0.77,-1,1,1,0,0,x,3,2.25,0,0,0.825,-0.825,-0.225,0.225,0,1,j,P,1,0,0,0,1,0,0,0,0,P,2,0,0,0,0,1,1,0,0,P,3,0,0,-0.77,0.77,1,-1,0,0,C,j,0,0,0,P,1,P,2,P,2,P,3,0,C,B,X,B,B,-1,b,x,1,x,2,d,1,+,d,1,-,d,2,+,d,2,-,d,3,-,x,3,0,x,2,1.6,0,1,0,0,0.4,-0.4,0,0.13,0,x,1,2.4,1,0,0,0,-0.4,0.4,0,0.2,P,3,d,3,-,0.8,0,0,0,0,-0.79,0.79,1,-0.93,0,d,1,+,2.72,0,0,1,-1,-0.273,0.273,0,1.21,j,P,1,0,0,0,1,0,0,0,0,P,2,0,0,0,0,1,1,0,0,P,3,0,0,0,0,0.79,-0.79,0,0.93,该目标规划的满意解为：,x,1,=2.4,x,2,=1.6,3.目标规划的灵敏度分析,在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，目标规划的灵敏度分析主要针对优先级及权系数的变化对最终解的影响。,方法：变化后的优先级及权系数代入初表中重新计算。,4.目标规划应用举例,例1 某单位领导在考虑本单位职工的升级调资方案时，依次遵守如下规定：,（2）每级的人数不超过定编规定的人数；,（1）不超过年工资总额60000元；,（3）二、三级的升级面尽可能达到现有人,数的20%；,（4）三级不足编制的人数可录用新职工，,又一级的职工中有10%要退休。,有关资料汇总于下表，问领导应如何拟定一个满意的方案。,等级,工资额（元/年）,现有人数,编制人数,一,2000,10,12,二,1500,12,15,三,1000,15,15,合计,37,42,解：设,x,1,x,2,x,3,分别表示提升到一、二级和,录用到三级的新职工的人数。,对各目标确定的优先因子为：,P,1,不超过年工资总额60000元,P,2,每级的人数不超过定编规定的人数,P,3,二、三级的升级面尽可能达到现有,人数的20%,先分别建立各目标约束：,（1）年工资总额不超过60000元；,2000(10-10*0.1+,x,1,)+1500(12-x,1,+x,2,)+,1000(15-x,2,+x,3,)+d,1,-,-d,1,+,=60000,mind,1,+,（2）每级的人数不超过定编规定的人数：,对一级有10(1-0.1)+,x,1,+d,2,-,-d,2,+,=12,mind,2,+,对二级有12-,x,1,+x,2,+d,3,-,-d,3,+,=15,mind,3,+,对三级有15-,x,2,+x,3,+d,4,-,-d,4,+,=15,mind,4,+,（3）二、三级的升级面不大于现有人数的,20%，但尽可能多提：,对二级有,x,1,+d,5,-,-d,5,+,=12*0.2,mind,5,-,对三级有,x,2,+d,6,-,-d,6,+,=15*0.2,mind,6,-,目标函数：,minZ,=P,1,d,1,+,+P,2,(d,2,+,+d,3,+,+d,4,+,)+P,3,(d,5,-,+d,6,-,),模型为：,以上目标规划模型可用单纯形法求解，得到多重解。现将这些解汇总于下表。该单位领导再按具体情况，从下表中选一个执行方案：,变量,含义,解1,解2,解3,解4,X,1,晋升到一级的人数,2.4,2.4,3,3,X,2,晋升到二级的人数,3,3,3,5,X,3,新招收三级的人数,0,3,3,5,d,1,-,工资总额的结余额,6300,3300,3000,0,d,2,-,一级缺编人数,0.6,0.6,0,0,d,3,-,二级缺编人数,2.4,2.4,3,1,d,4,-,三级缺编人数,3,0,0.6,0,d,5,+,二级超编人数,0,0,0,0.6,d,6,+,三级超编人数,0,0,0,2,例2 已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价