运筹学第四章多目标规划ppt课件.ppt
,第四章 多目标规划,4.1 多目标规划模型及其解的概念 4.2 多目标规划的解法目标规划法,4.1 多目标规划模型及其解的概念,线性目标规划与线性规划比较，具有下面的特点：,1.线性规划只讨论单目标线性函数在一组线性约束条件下的极值问题，而目标规划能统筹兼顾处理实际问题中经常出现的多种目标关系，求得更切合实际的最优解。,2.线性规划要求在满足所有约束条件的可行解中求最优解，而实际问题中存在着互相矛盾的约束条件，从而制约了线性规划解决问题的范围。目标规划将克服这些互相矛盾的约束条件，找到满意的合理解。,3.线性规划将约束条件看成同样重要、不分主次的条件，而目标规划将依据实际情况去确定模型，并主次有别地进行求解。,4.线性规划求得最优解，可能求得此解将花昂贵的代价，而目标规划寻求的是满意解，即在指定的指标值下求得近似解，实际问题可能更需要这样的满意解。,4.2 多目标规划的解法目标规划法,一.目标规划的数学模型,1.问题的提出,例1（P99例4.7）,设生产产品A和B各x1,x2,若要求：1） 生产这两种产品的利润最少达到12万元,2） A产品的产量尽可能是B产品产量的1.5倍,3） 为充分利用设备工时，必须使设备的空闲时间尽可能的地小。,问工厂又应如何决定产品A、B的产量？,仍设生产产品A、B各x1，x2,资源约束：3x1+3x212,硬约束,令d1-表示安排生产时，低于计划利润12的量,负偏差变量,令d1+表示安排生产时，高于计划利润12的量,正偏差变量,故4x1+3.2x2-d1+d1-=12,MinZ1=d1-,令d2-表示安排生产时，A产品比1.5倍B产品产量的不足量,负偏差变量,正偏差变量,令d2+表示安排生产时，A产品比1.5倍B产品产量的超过量,故x1-1.5x2-d2+d2-=0,MinZ2=d2+d2-,令d3-表示剩余的设备工时,d3+表示超过的设备工时,故2x1+4x2-d3+d3-=12,MinZ3=d3-,所以，模型为：,minZ1=d1-,minZ2=d2-+d2+,minZ3=d3-,目标规划模型,转化为单目标：,minW=P1d1-+P2(d2-+d2+)+P3d3-,P1第一优先级,P2第二优先级,P3第三优先级,P1P2P3,2.数学模型,（1）目标规划模型的要素,1决策变量和偏差变量,决策变量：,又称控制变量，用xi表示,偏差变量：,正偏差变量（di+）：,实际决策值超过第i个目标值的数量,di+=,fi(X)-fi(0),fi(X)fi(0),0,fi(X)fi(0),负偏差变量（di-）：,di-=,fi(X)fi(0),fi(0) -fi(X),fi(X)fi(0),实际决策值低于第i个目标值的数量,0,di+0,说明实际值超过目标值,则di-=0,di-0,说明实际值低于目标值,则di+=0,di+di-=0,2.绝对约束和目标约束,绝对约束：指必须严格满足的等式或不等式,硬约束,目标约束：在达到目标值时允发生正或负的 偏差量,软约束,如：对于约束：fi(X)+di-di+=fi(0),当di-=0时，fi(x)fi(0),当di+=0时，fi(x) fi(0),当di+=di-=0时，fi(x) = fi(0),3.优先因子与权系数,第一位达到的目标优先因子P1,第二位达到的目标优先因子P2,并规定：PlPl+1表示Pl比Pl+1有 更大的优先权,不同优先权的因子,权系数,相同优先级权的因子,4.目标函数,构成,各目标约束的正负偏差变量,相应的优先因子,极小化：尽可能缩小偏离目标值,对于约束fi(x)+di-di+=fi(0),(1)若要求恰好达到预定目标值,则min(di+di-),(2)若要求不超过预定目标值,则min(di+),(3)若要求超过预定目标值,则min(di-),一般目标规划模型：,软约束,fi(x)-di+di-=fi(0),XR,硬约束,di+0,di-0(i=1p),二.目标规划的解法,1.图解法（2个决策变量）,步骤：,1.做绝对约束，作法同线性规划图解法；,2.做目标约束：令偏差di=0，标上di的 箭头方向；,3.按优先级逐步缩小可行解的范围，最后 得到有效解。,例2.用图解法求解目标规划,解：,（1）先在平面直角坐标系中做出各约束条 件所确定的区域；,（2）标出目标约束在相应直线上di+,di-增 大的方向；,（3）根据目标函数的优先因子分析求解。,绝对约束如线性规划图解法,目标约束：令di+,di- 均为0，作直线,(1)4x1+3.2x2=12,(2)x1-1.5x2=0,(3)2x1+4x2=12,(4)3x1+3x2=12,(1)(2)(4)约束有公共区域：线段AB,(3)约束与(1)(2)(4)约束无公共区域，故应得满意解,该解尽可能满足(3)约束，故B点为满意解,求解直线x1-1.5x2=0与3x1+3x2=12的交点,得到满意解为x1=12/5,x2=8/5,2.单纯形法,算法：,（1）建立初始单纯形表，在表中将检验数按优先因子个数分成若干行；,（2）换基迭代时先考虑第一优先级的检验数，若均0，再考虑第二优先级，以此类推；,（3）若检验数第k行的某检验数非正，但它所在列的前k-1个检验数均非负，则表中相应解为满意解，停止计算。,例3.用单纯形法求解目标规划：,该目标规划的满意解为：x1=2.4,x2=1.6,3.目标规划的灵敏度分析,在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，目标规划的灵敏度分析主要针对优先级及权系数的变化对最终解的影响。,方法：变化后的优先级及权系数代入初表中重新计算。,4.目标规划应用举例,例1 某单位领导在考虑本单位职工的升级调资方案时，依次遵守如下规定：,（2）每级的人数不超过定编规定的人数；,（1）不超过年工资总额60000元；,（3）二、三级的升级面尽可能达到现有人 数的20%；,（4）三级不足编制的人数可录用新职工， 又一级的职工中有10%要退休。,有关资料汇总于下表，问领导应如何拟定一个满意的方案。,解：设x1,x2,x3分别表示提升到一、二级和 录用到三级的新职工的人数。,对各目标确定的优先因子为：,P1不超过年工资总额60000元,P2每级的人数不超过定编规定的人数,P3二、三级的升级面尽可能达到现有 人数的20%,先分别建立各目标约束：,（1）年工资总额不超过60000元；,2000(10-10*0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1-d1+=60000,mind1+,（2）每级的人数不超过定编规定的人数：,对一级有10(1-0.1)+x1+d2-d2+=12,mind2+,对二级有12-x1+x2+d3-d3+=15,mind3+,对三级有15-x2+x3+d4-d4+=15,mind4+,（3）二、三级的升级面不大于现有人数的 20%，但尽可能多提：,对二级有x1+d5-d5+=12*0.2,mind5-,对三级有x2+d6-d6+=15*0.2,mind6-,目标函数：,minZ=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-),模型为：,以上目标规划模型可用单纯形法求解，得到多重解。现将这些解汇总于下表。该单位领导再按具体情况，从下表中选一个执行方案：,例2 已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表1，并规定其相应的优先级：,P1B4是重点保证单位，必须全部满足其 需要；,P2A3向B1提供的产量不少于100；,P3每个销地供应量不小于其需要量的80%,P4所订调运方案的总运费不超过最小运费 调运方案的10%；,P5因路段的问题，尽量避免安排将A2的产品调往B4；,P6给B1和B3的供应率要相同；,P7力求总运费最省。,试求满意的调运方案。,表1,解：用表上作业法求得最小运费的调运方案，见下表。,这时最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。,（1）供应约束：,x11+x12+x13+x14300,x21+x22+x23+x24200,x31+x32+x33+x34400,（2）需求约束：,x11+x21+x31+d1-d1+=200,x12+x22+x32+d2-d2+=100,x13+x23+x33+d3-d3+=450,x14+x24+x34+d4-d4+=250,（3）A3向B1提供的产品产量不少于100,x31+d5-d5+=100,(5)调运方案的总运费不超过最小运费调运方案的10%,(4)每个销地的供应量不小于其需要量的80%,x11+x21+x31+d6-d6+=2000.8,x12+x22+x32+d7-d7+=1000.8,x13+x23+x33+d8-d8+=4500.8,x14+x24+x34+d9-d9+=2500.8,(6)因路段的问题，尽量避免安排将A2的产品调往B4,x24+d11-d11+=0,(7)给B1和B3的供应率要相同,(8)力求总运费最省,目标函数为：,计算结果，得到满意调运方案，见下表。总运费为3360元。,
