第五章+目标规划.pdf

《第五章+目标规划.pdf》由会员分享，可在线阅读，更多相关《第五章+目标规划.pdf（52页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、5 5 目标规划目标规划5.1 概述5.2 数学模型5.3 Lindo软件实现5.4 Lingo软件实现5.1 5.1 概述概述?问题的提出5.1 5.1 概述概述?问题的提出5.1 5.1 概述概述?问题的提出5.1 5.1 概述概述?问题的提出?问题的提出第四章介绍的线性规划问题，研究的是只有一个目标函数，若干个约束条件的最优决策问题。然而现实生活中，衡量一个方案或决策好坏的标准往往不止一个，而且这些标准之间可能是不协调的，甚至是相互冲突的。目标规划（Goal Programming,GP）是美国学者Charnes等在1952年提出来的。它在线性规划的基础上，为适应复杂的多目标最优决策的需

2、要逐步发展起来的。它的重要特点是对各个目标分级加权与逐级优化，符合人们处理问题时考虑轻重缓急确保重点的思维方式。5.1 5.1 概述概述?问题的提出例5-1某一江段，沿江设有两个工厂，第一个工厂每日向江中排放的污染物为20个单位，第二个工厂每日向江中排放的污染物为14个单位。那些污染物向江中排放之前，曾作部分处理。每处理一个单位的污水处理费在第一个工厂为1000元，第二个工厂为800元。流经第一个工厂的河流在经过工厂以前为未受污染的河流，其江水流量Q1为5m3/s，在第一个工厂到第二个工厂之间又有一小支流汇入，其流量Q2为2m3/s，也未受污染。另外，第一个工厂排入江中的污染物在未到第二个工厂

3、之前由于自净作用而自净掉20%。按照当地环保局规定，这条江对污染物的允许含量不得超过2个单位。在满足环境标准的前提下，试确定污水处理计划，使污水处理费用最少，并尽可能减少工厂一的处理量？5.1 5.1 概述概述工厂1工厂2Q1Q2?问题的提出例5-2某一江段，沿江设有两个工厂，第一个工厂每日向江中排放的污染物为20个单位，第二个工厂每日向江中排放的污染物为14个单位。那些污染物向江中排放之前，曾作部分处理。每处理一个单位的污水处理费在第一个工厂为1000元，第二个工厂为800元。流经第一个工厂的河流在经过工厂以前为未受污染的河流，其江水流量Q1为5m3/s，在第一个工厂到第二个工厂之间又有一小

4、支流汇入，其流量Q2为2m3/s，也未受污染。另外，第一个工厂排入江中的污染物在未到第二个工厂之前由于自净作用而自净掉20%。按照当地环保局规定，这条江对污染物的允许含量不得超过2个单位。在满足环境标准的前提下，试确定污水处理计划，尽可能减少工厂一的处理量，降低处理费用？工厂1工厂2Q1Q25.1 5.1 概述概述?问题的提出例5-3 某国家的土地管理机构要对100km2的公有土地制定规划。根据土地多种用途的总政策，该机构决定把这片土地分成三个区，即野生动物保护区、公共游乐区和商业性林区。政府拥有土地权，并预算每年最多支出90 000 元管理这片土地。野生动物保护区、公共游乐区和商业性林区三种

5、土地用途的年费用分别为1000元/km2、4000元/km2和5000元/km2。商业性林区每年给该机构带来的收入为7000元/km2。假定这片土地对三种用途都是适用的，应该如何对这片土地进行规划。5.1 5.1 概述概述?问题的提出5.1 5.1 概述概述土地用途年费用（元土地用途年费用（元/km2）目标目标X(km2)目标目标F（价值（价值）权重权重012024056088091001001206408601080101001001203405607809100100.20.50.3野生动物保护区野生动物保护区公共游乐区商业性林区公共游乐区商业性林区100040005000?一般形式将实际

6、问题转化为在一组线性不等式或等式约束下求线性目标函数的最大值最小值问题。5.2 5.2 数学模型数学模型目标函数约束条件111 112 211221 122 2221 12 211 112 21121 122 22MaxMax Maxs.tn nn nmmmmn nmn nn nyc xc xc xC Xyc xc xc xC Xyc xc xc xC Xa xa xa xba xa xa x=+=+=+LLMMMLLL21 12 212 ,0kkkn nknba xc xc xbx xx+MMMLLMaxYCX=0AXBX?解 可行解（feasible solution）设,称为多目标线性规

7、划问题的可行解集合或可行解域。最优解（optimum solution）设多目标规划问题的可行解集合非空，且对任意的都有，则称为多目标规划问题的最优可行解，简称最优解。最优解实际上是使所有目标同时达到最优值。5.2 5.2 数学模型数学模型R0=XBAXXR,RX*RX CXCX*X?解满意解（非劣解，有效解 satisfactory solution）更多的情况是，多目标之间相互矛盾，最优解不存在。退而求其次，根据目标之间的相对重要程度，分等级和权重，求出相对最优解有效解（满意解,非劣解）。需要对目标函数和约束条件作适当处理。5.2 5.2 数学模型数学模型目标值 f11234567目标值f

8、2偏差变量(deviation variable)在多目标规划问题中，由于目标之间存在冲突或约束条件中有矛盾方程，我们可以设想降低目标要求、“放松”严格的约束条件，即从实际出发,给每个目标确定一个希望达到的目标值ei,(i=1，2，m)。一般说来，这些值ei的确定并不要求十分精确或严格，允许决策的实际值大于或小于ei。实际值与目标值的差距为被称为偏差变量用表示。5.2 5.2 数学模型数学模型iidd+，目标规划不是对每个目标求最优解，而是寻找使每个目标与各自的理想值之差尽可能小的解。?偏差变量(deviation variable)第i个目标实际值超出目标值的部分，称为正偏差变量。第i个目标

9、实际值不足目标值的差距，称为负偏差变量。规定5.2 5.2 数学模型数学模型idid+0 (1,2,)iiddim+=?0,?偏差变量(deviation variable)当目标值确定时，所做的决策只可能出现以下三种情况：即第i个目标的实际值大于目标值即第i个目标的实际值未达到目标值即第i个目标的实际值恰好等于目标值无论发生什么情况，均有5.2 5.2 数学模型数学模型0 iidd+=0,0,0=+iidd0=0=+iidd,0=+iidd?目标约束和绝对约束 目标约束(goal restrictions)指在约束条件中允许目标值发生一定的正偏差或负偏差。它通过在约束条件中引入正、负偏差变量

10、 来实现，也称为软约束。绝对约束(absolute restrictions)指必须严格满足的等式或不等式约束，也称为系统约束。它对应于线性规划中的约束条件，不能满足绝对约束的解即为不可行解，因此也称为硬约束。绝对约束可以通过引入偏差变量转化为目标约束。5.2 5.2 数学模型数学模型?目标函数目标规划的目标函数由偏差变量构成，它有三种基本表现形式：要求恰好达到目标值的，即正、负偏差变量都要尽可能小。构造目标函数为：要求不能超过目标值的，即允许达不到目标值，但即使超过，一定要越小越好。构造目标函数为：要求超过目标值的，即允许超过目标值，但即使不足，一定要使缺少量越少越好。构造目标函数为：根据各

11、个目标要求，确定出总的目标函数：5.2 5.2 数学模型数学模型Min iiZdd+=+Min iZd+=Min iZd=,Min()iji jZdd+=+目标函数就是尽可能使偏差变小?优先因子 目标规划中，当决策者要求实现多个目标时，这些目标的偏差可能相互替代或抵消，因为我们求的是所有偏差和最小，而实际问题中的目标之间也有主次、轻重、缓急之区别。决策者往往有一些最重要的，第一位要求达到的目标，我们赋予它优先因子(factor of priority)P1，在它实现的前提下再去解决次要目标依次把第二位达到的目标赋予优先因子P2，并规定Pk Pk+1，即 Pk比Pk+1具有绝对的优先权，低阶的目

12、标只有在高阶的目标完成之后才能被考虑。因此，不同的优先因子代表着不同的优先等级。5.2 5.2 数学模型数学模型1Min()kijjiZP dd+=+?权系数若要进一步区别具有同一优先级的多个目标，则可分别赋予它们不同的权系数，根据目标的重要程度而给它们赋值，重要的目标，赋值较大，反之 就小。5.2 5.2 数学模型数学模型11Min()kmiijjijjijZPdd+=+ij注：不同优先等级的偏差变量是不可比较的。?模型构建?设定约束条件（目标约束，绝对约束）?规定目标约束优先级?建立目标规划模型5.2 5.2 数学模型数学模型?模型构建?根据问题所提出的各目标与条件，确定目标值（期望值），

13、设定决策变量并列出目标约束与绝对约束；?根据决策者的需要将某些或全部绝对约束，通过引入偏差变量转换为目标约束；?给各级目标赋予相应的优先因子，对同一优先级的各目标，按重要程度不同赋予相应的权系数；?根据决策者的要求，各目标按三种情况取值：恰好达到目标值，取允许超过目标值，取不允许超过目标值，取然后构造一个由优先因子、权系数与偏差变量组成的、求最小化的目标函数。5.2 5.2 数学模型数学模型+iiddid+id?标准形式5.2 5.2 数学模型数学模型目标函数由各目标约束的正、负偏差变量及其相应的优先级、权系数构成。1111 min()(,),1,2,.,s.t.1,2,.,0,0(j=1,2

14、,.n,1,2,)kmllkklkkljntjjtjnijjiiijjkkZPdda xb tLc xddgimxddkm+=+=+=+=+=L对于n个决策变量，m个目标约束，L个硬约束，k个优先级的目标规划，其数学模型的标准形式为：实现值与期望值偏差最小11223344121112221233124412min()(1.5).30158121000240,0 iiZP ddP dP dP ddS Txddxddxxddxxddxxdd+=+=+=+=+=（i=1,2,3,4）?标准形式5.2 5.2 数学模型数学模型目标函数约束条件根据约束方程和目标函数，运用序贯法、单纯形等方法获得可行解、

15、最优解或满意解。?求解方法序贯式算法（Sequential Algorithm）1.建立仅含p1级目标的线性规划单目标模型5.3 Lindo 5.3 Lindo 软件实现软件实现11223344121112221233124412121112221min()(1.5)3015.8121000240,0 min 3015.812iiZP ddPdPdP ddxddxddS Txxddxxddx x ddZddxddxddS Txx+=+=+=+=+=+=+=+（i=1,2,3,4）2331244121000240,0 iiddxxddx x dd+=+=（i=1,2,3,4）可去除Lindo不能

16、直接求解多目标规划，但可以通过序贯法来求解。?求解方法序贯式算法（Sequential Algorithm）2.用单纯形法求解第一个优先级p1的单目标线性规划模型，获得p1级目标所能达到的最优值1120Zdd+=+=P1级目标完全被满足5.3 Lindo 5.3 Lindo 软件实现软件实现112233441211122212331244123111222123min()(1.5)3015.8121000240,0 min 3015812.iiZP ddPdPdP ddxddxddS Txxddxxddx x ddZdxddxddxxdS T+=+=+=+=+=+=+=+（i=1,2,3,4）

17、31244121210002400,0 iidxxddddx x dd+=+=+=（i=1,2,3,4）?求解方法序贯式算法（Sequential Algorithm）3.建立第二个相对优先级p2的单目标线性规划模型。5.3 Lindo 5.3 Lindo 软件实现软件实现?求解方法序贯式算法（Sequential Algorithm）4.用单纯形法求解第二个优先级p2的单目标线性规划模型，获得p2级目标所能达到的最优值23580Zd=P2级目标没有完全被满足5.3 Lindo 5.3 Lindo 软件实现软件实现11223344121112221233124412411122212min()

18、(1.5)3015.8121000240,0 min 3015812.iiZP ddPdPdP ddxddxddS Txxddxxddx x ddZdxddxddxxS T+=+=+=+=+=+=+=+（i=1,2,3,4）3312441231210002400 580,0 iiddxxdddddx x dd+=+=+=（i=1,2,3,4）?求解方法序贯式算法（Sequential Algorithm）5.建立第三个相对优先级p3的单目标线性规划模型。5.3 Lindo 5.3 Lindo 软件实现软件实现?求解方法序贯式算法（Sequential Algorithm）6.用单纯形法求解第三

19、个优先级p3的单目标线性规划模型，获得p3级目标所能达到的最优值3420Zd+=P3级目标没有完全被满足5.3 Lindo 5.3 Lindo 软件实现软件实现11223344121112221233124412121112221min()(1.5)3015.8121000240,0 min 1.530158.iiZP ddPdPdP ddxddxddS Txxddxxddx x ddZddxddxddxS T+=+=+=+=+=+=+=+（i=1,2,3,4）23312441234121210002400 580 20,0 iixddxxddddddx x dd+=+=+=（i=1,2,3,

20、4）?求解方法序贯式算法（Sequential Algorithm）7.建立第三个相对优先级p4的单目标线性规划模型。5.3 Lindo 5.3 Lindo 软件实现软件实现?求解方法序贯式算法（Sequential Algorithm）8.用单纯形法求解第三个优先级p4的单目标线性规划模型，获得p4级目标所能达到的最优值4121.50Zdd=+=P4级目标完全被满足5.3 Lindo 5.3 Lindo 软件实现软件实现?求解方法序贯式算法（Sequential Algorithm）9.结论123015xx=最优解12340580200ZZZZ=目标达成5.3 Lindo 5.3 Lindo

21、 软件实现软件实现?案例分析例5-1某一江段，沿江设有两个工厂，第一个工厂每日向江中排放的污染物为20个单位，第二个工厂每日向江中排放的污染物为14个单位。那些污染物向江中排放之前，曾作部分处理。每处理一个单位的污水处理费在第一个工厂为1000元，第二个工厂为800元。流经第一个工厂的河流在经过工厂以前为未受污染的河流，其江水流量Q1为5m3/s，在第一个工厂到第二个工厂之间又有一小支流汇入，其流量Q2为2m3/s，也未受污染。另外，第一个工厂排入江中的污染物在未到第二个工厂之前由于自净作用而自净掉20%。按照当地环保局规定，这条江对污染物的允许含量不得超过2个单位。在满足环境标准的前提下，试

22、确定污水处理计划（1）使污水处理费用最少；（2）尽可能减少工厂一的处理量、增加第二工厂的处理量？工厂1工厂2Q1Q25.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析解析：设x1和x2分别为第一个工厂和第二个工厂的污水处理单位，两个厂所要花费的污水处理费用为1000 x1800 x2，目标函数则为minS11000 x1800 x2 P1 minS2x1 P2maxS3x2 P2约束条件分析表对第一个工厂来说，20 x1 10；对第二个工厂来说，0.8(20-x1)+(14-x2)14对污水处理量来说，0 x120 0 x214 工厂未处理 处理剩余量一20 x120-x110

23、00Q1=525210二14x214-x2800Q1+Q2=727214最大允许纳污量排污量单位污水处理费河流来水量江中允许排污标准5.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析 例5-1目标函数偏差变量1122132Min S1000800Min SMax Sxxxx=+=设污水处理费的期望值为20000元设工厂一的期望值为10个单位设工厂二的期望值为10个单位11223112223(2)2MinSPdPddPdPdPd+=+=+-+-+112233dddddd，分别为处理费不足和超出20000元分别为工厂一的处理量不足和超出10个单位分别为工厂二的处理量不足和超出10个

24、单位12ij2ijPP w2P w1=，5.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-1标准形式11222312111222331121212112233Min +2+subject to1000800200001010100.8162014,0PdPdPdxxddxddxddxxxxxx x dddddd+=+=+=+5.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-15.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-15.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-2某一江段，沿江设有两个工厂，第

25、一个工厂每日向江中排放的污染物为20个单位，第二个工厂每日向江中排放的污染物为14个单位。那些污染物向江中排放之前，曾作部分处理。每处理一个单位的污水处理费在第一个工厂为1000元，第二个工厂为800元。流经第一个工厂的河流在经过工厂以前为未受污染的河流，其江水流量Q1为5m3/s，在第一个工厂到第二个工厂之间又有一小支流汇入，其流量Q2为2m3/s，也未受污染。另外，第一个工厂排入江中的污染物在未到第二个工厂之前由于自净作用而自净掉20%。按照当地环保局规定，这条江对污染物的允许含量不得超过2个单位。在满足环境标准的前提下，试确定污水处理计划，尽可能减少工厂一的处理量，降低处理费用？工厂1工

26、厂2Q1Q25.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-2解析：设x1和x2分别为第一个工厂和第二个工厂的污水处理单位，两个厂所要花费的污水处理费用为1000 x1800 x2，目标函数则为minS1x1minS21000 x1800 x2 约束条件分析表对第一个工厂来说，20 x1 10；对第二个工厂来说，0.8(20-x1)+(14-x2)14对污水处理量来说，0 x120 0 x214工厂未处理 处理剩余量一20 x120-x11000Q1=525210二14x214-x2800Q1+Q2=727214最大允许纳污量排污量单位污水处理费河流来水量江中允许排污标

27、准5.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-2目标函数偏差变量11212Min SMin S1000800 xxx=+设工厂一的期望值为11个单位设污水处理费的期望值为15000元1122 MinSPdPd+=+1122dddd，分别为工厂一的处理量不足和超出11个单位分别为处理费不足和超出15000元12PP5.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-2 标准形式1122111122211212121122Min subject to11100080015000100.8162014,0PdPdxddxxddxxxxxx x dddd

28、+=+=+5.3 5.3 LindoLindo 软件实现软件实现?案例分析例5-25.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-25.3 Lindo 5.3 Lindo 软件实现软件实现?案例分析例5-1 5.4 Lingo 5.4 Lingo 软件实现软件实现?案例分析例5-1 5.4 Lingo 5.4 Lingo 软件实现软件实现?目标规划与线性规划的比较5.5 5.5 小结小结?目标规划与线性规划的比较5.5 5.5 小结小结?目标规划与线性规划的比较5.5 5.5 小结小结?目标规划总结：主要特征?在每个约束条件中引入正、负偏差变量，使硬约束变成软约束；?将距各个目标值的偏差总和最小作为目标函数，便于处理多目标问题;?用划分优先级的方法来处理多个目标的相对重要性，能更好地适应决策者的判断.5.5 5.5 小结小结?目标规划总结：局限性?线性要求。目标函数，约束和目标关系必须是线性的，即要求对目标达到程度的度量和资源利用的度量都必须与决策变量的各自水平成比例。?可加性要求。为了保证目标规划的线性要求，目标函数和约束中的每个因素都必须是可加的，即目标和资源是互相独立的。?确定性要求。模型中的所有系数都必须是常数。5.5 5.5 小结小结