运筹学第四章-多目标规划ppt课件.ppt
认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目第四章 多目标规划 4.1 多目标规划模型及其解的概念 4.2 多目标规划的解法目标规划法认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.1 多目标规划模型及其解的概念单目标问题：方案dj 评价值f(dj)多目标问题：方案dj 评价值向量 f1(dj)，fp(dj)线性目标规划与线性规划比较，具有下面的特点：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1.线性规划只讨论单目标线性函数在一组线性约束条件下的极值问题，而目标规划能统筹兼顾处理实际问题中经常出现的多种目标关系，求得更切合实际的最优解。2.线性规划要求在满足所有约束条件的可行解中求最优解，而实际问题中存在着互相矛盾的约束条件，从而制约了线性规划解决问题的范围。目标规划将克服这些互相矛盾的约束条件，找到满意的合理解。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3.线性规划将约束条件看成同样重要、不分主次的条件，而目标规划将依据实际情况去确定模型，并主次有别地进行求解。4.线性规划求得最优解，可能求得此解将花昂贵的代价，而目标规划寻求的是满意解，即在指定的指标值下求得近似解，实际问题可能更需要这样的满意解。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目x10 x2M1M2M3M4劣解有效解最优解认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目4.2 多目标规划的解法目标规划法一.目标规划的数学模型1.问题的提出例1（P99例4.7）产品 A B 限量设备工时（月/单位）2 4 12材料（百吨/单位）3 3 12利润（万元/单位）4 3.2如何安排生产计划使获利最大？认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目设生产产品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-=12MinZ1=d1-认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目令d2-表示安排生产时，A产品比1.5倍B产品产量的不足量负偏差变量正偏差变量令d2+表示安排生产时，A产品比1.5倍B产品产量的超过量故x1-1.5x2-d2+d2-=0MinZ2=d2+d2-令d3-表示剩余的设备工时 d3+表示超过的设备工时 故2x1+4x2-d3+d3-=12MinZ3=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)0fi(X)fi(0)认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目负偏差变量（di-）：di-=fi(X)fi(0)fi(0)-fi(X)fi(X)Pl+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，作直线认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目x1x20(1)4x1+3.2x2=12(2)x1-1.5x2=0(3)2x1+4x2=12(4)3x1+3x2=12d1+d1-d2+d2-d3+d3-AB(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.用单纯形法求解目标规划：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目Cj000P1P2P2P30CBXBB-1 bx1x2d1+d1-d2+d2-d3-x3P1d1-1243.2-110000P2d2-01-1.500-1100P3d3-12240000100 x3033000001jP1-43.2100000P2-11.5002000P3-2-4000000认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目Cj000P1P2P2P30CBXBB-1 bx1x2d1+d1-d2+d2-d3-x3P1d1-1209.2-114-4000 x101-1.500-1100P3d3-1207002-2100 x31207.5003-301jP10-9.210-4400P200001100P30700-2200认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目Cj000P1P2P2P30CBXBB-1 bx1x2d1+d1-d2+d2-d3-x30 x21.301-0.110.110.43-0.43000 x11.9510-0.1650.165-0.3550.35500P3d3-2.9000.77-0.77-11100 x32.25000.825-0.825-0.2250.22501jP100010000P200001100P300-0.770.771-100认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目Cj000P1P2P2P30CBXBB-1 b x1x2d1+d1-d2+d2-d3-x30 x21.601000.4-0.400.130 x12.41000-0.40.400.2P3d3-0.80000-0.790.791-0.930d1+2.72001-1-0.2730.27301.21jP100010000P200001100P300000.79-0.7900.93该目标规划的满意解为：x1=2.4,x2=1.6认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3.目标规划的灵敏度分析在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，目标规划的灵敏度分析主要针对优先级及权系数的变化对最终解的影响。方法：变化后的优先级及权系数代入初表中重新计算。4.目标规划应用举例例1 某单位领导在考虑本单位职工的升级调资方案时，依次遵守如下规定：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（2）每级的人数不超过定编规定的人数；（1）不超过年工资总额60000元；（3）二、三级的升级面尽可能达到现有人 数的20%；（4）三级不足编制的人数可录用新职工，又一级的职工中有10%要退休。有关资料汇总于下表，问领导应如何拟定一个满意的方案。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目等级 工资额（元/年）现有人数 编制人数一20001012二15001215三10001515合计3742解：设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+=60000mind1+认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（2）每级的人数不超过定编规定的人数：对一级有10(1-0.1)+x1+d2-d2+=12mind2+对二级有12-x1+x2+d3-d3+=15mind3+对三级有15-x2+x3+d4-d4+=15mind4+认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（3）二、三级的升级面不大于现有人数的 20%，但尽可能多提：对二级有x1+d5-d5+=12*0.2mind5-对三级有x2+d6-d6+=15*0.2mind6-目标函数：minZ=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-)认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目模型为：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 以上目标规划模型可用单纯形法求解，得到多重解。现将这些解汇总于下表。该单位领导再按具体情况，从下表中选一个执行方案：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目变量含义解1解2解3解4X1晋升到一级的人数2.42.433X2晋升到二级的人数3335X3新招收三级的人数0335d1-工资总额的结余额 6300 3300 30000d2-一级缺编人数0.60.600d3-二级缺编人数2.42.431d4-三级缺编人数300.60d5+二级超编人数0000.6d6+三级超编人数0002认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例2 已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表1，并规定其相应的优先级：P1B4是重点保证单位，必须全部满足其 需要；P2A3向B1提供的产量不少于100；P3每个销地供应量不小于其需要量的80%P4所订调运方案的总运费不超过最小运费 调运方案的10%；认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目P5因路段的问题，尽量避免安排将A2的产品调往B4；P6给B1和B3的供应率要相同；P7力求总运费最省。试求满意的调运方案。表1 1000900250450100200销量4003254A32006453A23007625A1产量B4B3B2B1 销产认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目解：用表上作业法求得最小运费的调运方案，见下表。1001000100250450100200 A4销量400150250A32002000A2300100200A1产量B4B3B2B1 销产 这时最小运费为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.8x12+x22+x32+d7-d7+=1000.8x13+x23+x33+d8-d8+=4500.8x14+x24+x34+d9-d9+=2500.8(6)因路段的问题，尽量避免安排将A2的产品调往B4x24+d11-d11+=0认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目(7)给B1和B3的供应率要相同(8)力求总运费最省目标函数为：认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目计算结果，得到满意调运方案，见下表。总运费为3360元。10010009025045010010200A4（虚）销量40050250100A320011090A230020010A1产量B4B3B2B1 销产
