多目标规划模型PPT课件.ppt

《多目标规划模型PPT课件.ppt》由会员分享，可在线阅读，更多相关《多目标规划模型PPT课件.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于多目标规划模型第一张，PPT共三十一页，创作于2022年6月 多目标决策由于考虑的目标多多目标决策由于考虑的目标多,有些目标之间又彼此有矛有些目标之间又彼此有矛盾盾,这就使多目标问题成为一个复杂而困难的问题这就使多目标问题成为一个复杂而困难的问题.但由于客观但由于客观实际的需要实际的需要,多目标决策问题越来越受到重视多目标决策问题越来越受到重视,因而出现了许多因而出现了许多解决此决策问题的方法解决此决策问题的方法.一般来说一般来说,其基本途径是其基本途径是,把求解多目把求解多目标问题转化为求解单目标问题标问题转化为求解单目标问题.其主要步骤是其主要步骤是,先转化为单目标先转化为单目标问题问

2、题,然后利用单目标模型的方法然后利用单目标模型的方法,求出单目标模型的最优解求出单目标模型的最优解,以此作为多目标问题的解以此作为多目标问题的解.化多目标问题为单目标问题的方法大致可分为两类化多目标问题为单目标问题的方法大致可分为两类,一类是一类是转化为一个单目标问题转化为一个单目标问题,另一类是转化为多个单目标问题另一类是转化为多个单目标问题,关键关键是如何转化是如何转化.下面下面,我们介绍几种主要的转化方法我们介绍几种主要的转化方法:主要目标法、线性加主要目标法、线性加权和法、字典序法、步骤法。权和法、字典序法、步骤法。第二张，PPT共三十一页，创作于2022年6月f1f212345678

3、10.1多目标决策问题的特征多目标决策问题的特征 在解决单目标问题时，我们的任务是选择一个或一组变量在解决单目标问题时，我们的任务是选择一个或一组变量X，使目，使目标函数标函数f(X)取得最大（或最小）。对于任意两方案所对应的解，只要比较取得最大（或最小）。对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。但在多目标情况下，问题却不它们相应的目标值，就可以判断谁优谁劣。但在多目标情况下，问题却不那么单纯了。例如，有两个目标那么单纯了。例如，有两个目标f1(X)，f2(X),希望它们都越大越好。下希望它们都越大越好。下图列出在这两个目标下共有图列出在这两个目标下共有8个解的

4、方案。其中方案个解的方案。其中方案1，2，3，4称称为劣解，因为它们在两个目标值上都比方案为劣解，因为它们在两个目标值上都比方案5差，是可以淘汰的解。差，是可以淘汰的解。而方案而方案5，6，7，8是非劣解（或称为有效解，满意解），因为这些是非劣解（或称为有效解，满意解），因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却更差。有一个指标更优越，而另一个指标却更差。一、解的特点一、解的特点第三张，PPT共三十一页，创作于2022年6月二、模型结构二、模型结构 多目标决策问题包含有三大要素：目

5、标、方案和决策者。多目标决策问题包含有三大要素：目标、方案和决策者。在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好

6、，质量要可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。好，花费要少。多目标决策问题中的方案即为决策变量，也称为多目标问题的解。多目标决策问题中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题限的，有些问题 的方案是无限的。方案有其特征或特性，称之为属性。的方案是无限的。方案有其特征或特性，称之为属性。第四张，PPT共三十一页，创作于2022年6月1、多目标规划问题的模型结构为决策变量如对于求极大(max)型，其各种解定义如下：绝对最优解

7、：若对于任意的X，都有F（X*）F(X)有效解：若不存在X，使得F（X*）F(X)弱有效解：若不存在X，使得F（X*)F(X)第五张，PPT共三十一页，创作于2022年6月第六张，PPT共三十一页，创作于2022年6月第七张，PPT共三十一页，创作于2022年6月10.2 多目标规划问题的求解多目标规划问题的求解1、主要目标法、主要目标法在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。例如，在上述多目标问题中，假定f1(X)为主要目标，其余p-1个为非主要目标。这时，希望主要目标达到极大值，并要求其余

8、的目标满足一定的条件，即第八张，PPT共三十一页，创作于2022年6月例题例题1 某工厂在一个计划期内生产甲、乙两种产品，各产品都要消某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗耗A，B，C三种不同的资源。每件产品对资源的单位消耗、各种资源的限三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。假定产量以及各产品的单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？造成的污染最小？甲乙

9、资源限量资源A单位消耗资源B单位消耗资源C单位消耗9434510240200300单位产品的价格400600单位产品的利润70120单位产品的污染32第九张，PPT共三十一页，创作于2022年6月解：问题的多目标模型如下对于上述模型的三个目标，工厂确定利润最大为主要目标。另两个目标则通过预测预先给定的希望达到的目标值转化为约束条件。经研究，工厂认为总产值至少应达到20000个单位，而污染控制在90个单位以下，即由主要目标法化为单目标问题用单纯形法求得其最优解为第十张，PPT共三十一页，创作于2022年6月2、线性加权和目标规划、线性加权和目标规划在上述目标规划中，假定f1(X),f2(X),f

10、p(X)具有相同的量纲,按照一定的规则分别给fi赋予相同的权系数i，作线性加权和评价函数则多目标问题化为如下的单目标问题第十一张，PPT共三十一页，创作于2022年6月例如，某公司计划购进一批新卡车，可供选择的卡车有如下例如，某公司计划购进一批新卡车，可供选择的卡车有如下4种类型：种类型：A1，A2，A3，A4。现考虑。现考虑6个方案属性：维修期限个方案属性：维修期限f1，每，每100升汽升汽油所跑的里数油所跑的里数f2，最大载重吨数，最大载重吨数f3，价格（万元），价格（万元）f4，可靠性，可靠性f5，灵，灵敏性敏性f6。这。这4种型号的卡车分别关于目标属性的指标值种型号的卡车分别关于目标属

11、性的指标值fij如下表如下表所示。所示。fijf1f2f3f4f5f6A12.01500455一般高A22.527003.665低一般A32.020004.245高很高A42.21800450很高一般首先对不同度量单位和不同数量级的指标值进行标准化处理。先首先对不同度量单位和不同数量级的指标值进行标准化处理。先将定性指标定量化：将定性指标定量化：第十二张，PPT共三十一页，创作于2022年6月效益型指标很低低一般高 很高13579很高高一般低 很低成本型指标可靠性和灵敏性都属于效益型指标，其打分如下可靠性一般低高很高5379灵敏性高一般很高一般7595按以下公式作无量纲的标准化处理其中：第十三

12、张，PPT共三十一页，创作于2022年6月变换后的指标值矩阵为：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.751001设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则故最优方案为选购A3型卡车第十四张，PPT共三十一页，创作于2022年6月3、分层序列法：、分层序列法：1.基本步骤：把(VP)中的p个目标 按其重要程度排序。依次求单目标规划的最优解。2.过程：无妨设其次序为 先求解 得最优值 ，记再解 得最优值 ，依次进行，直到 得最优值则 是在分层序列意义

13、下的最优解集合。第十五张，PPT共三十一页，创作于2022年6月3.性质：，即在分层序列意义下的最优解是有效解。证明：反证。设 ，但 ，则必存在 使 即至少有一个j0，使 ,由于 ，即 ，矛盾。得证。4.进一步讨论：上述方法过程中，当某个问题(Pj)的解唯一时，则问题 的求解无意义，因为解都是唯一的。实际求解时，有较宽容意义下的分层序列法：取 为预先给定的宽容值，整个解法同原方法类似，只是取各约束集合时，分别取为：第十六张，PPT共三十一页，创作于2022年6月 目标规划模型目标规划模型线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有

14、不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源，又不希望超越资源限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。一、目标规划模型的建立一、目标规划模型的建立第十七张，PPT共三十一页，创作于2022年6月引例引例1：对于生产计划问题：甲乙资源限额材料2324工时3226单位利润43现在工厂领导要考虑市场等一系列其他因素，提出如下目标：（1）根据市场信息，甲产品的销量有下降的趋势，而乙产

15、品的销量有上升的趋势，故考虑乙产品的产量应大于甲产品的产量。（2）尽可能充分利用工时，不希望加班。（3）应尽可能达到并超过计划利润30元。现在的问题是：在原材料不能超计划使用的前提下，如何安排生产才能使上述目标依次实现？第十八张，PPT共三十一页，创作于2022年6月解：（1）决策变量：仍设每天生产甲、乙两种产品各为x1和x2偏差变量：对于每一目标，我们引进正、负偏差变量。如对于目标1，设d1-表示乙产品的产量低于甲产品产量的数，d1+表示乙产品的产量高于甲产品产量的数。称它们分别为产量比较的负偏差变量和正偏差变量。则对于目标1，可将它表示为等式约束的形式-x1+x2+d1-d1+=0(目标约

16、束)同样设d2-和d2+分别表示安排生产时，低于可利用工时和高于可利用工时，即加班工时的偏差变量，则对目标2，有3x1+2x2+d2-d2+=26对于目标3，设d3-和d3+分别表示安排生产时，低于计划利润30元和高于计划利润30元的偏差变量，有：第十九张，PPT共三十一页，创作于2022年6月4x1+3x2+d3-d3+=30（2）约束条件：有资源约束和目标约束资源约束：2x1+3x224目标约束：为上述各目标中得出的约束（3）目标函数：三个目标依次为：minZ1=d1-，minZ2=d2+d2-，minZ3=d3-因而该问题的数学模型可表述如下：minZ1=d1-，minZ2=d2+d2-

17、，minZ3=d3-2x1+3x224st-x1+x2+d1-d1+=03x1+2x2+d2-d2+=264x1+3x2+d3-d3+=30第二十张，PPT共三十一页，创作于2022年6月案例案例2（提级加新问题）（提级加新问题）某公司的员工工资有四级，根据公司的业务发展情况，准备招收部分新员工，并将部分员工的工资提升一级。该公司的员工工资及提级前后的编制表如下，其中提级后编制是计划编制，允许有变化，其中1级员工中有8%要退休。公司领导的目标如下：（1）提级后在职员工的工资总额不超过550千元；（2）各级员工不要超过定编人数；（3）为调动积极性，各级员工的升级面不少于现有人数的18%；（4）总

18、提级面不大于20%，但尽可能多提；（5）4级不足编制人数可录用新工人。第二十一张，PPT共三十一页，创作于2022年6月问：应如何拟定一具满意的方案，才能接近上述目标？级别1234工资（千元）8643现有员工数10204030编制员工数10225230解：（1）决策变量：设x1,x2,x3,x4分别表示提升到1，2，3级和新录用的员工数。偏差变量：为各目标的正、负偏差变量。（2）约束条件：1）提级后在职员工的工资总额不超过550千元；8(10-108%+x1)+6(20-x1+x2)+4(40-x2+x3)+3(30-x3+x4)+d1-d1+=550第二十二张，PPT共三十一页，创作于202

19、2年6月2）各级员工不要超过定编人数1级有：10-108%+x1+d2-d2+=102级有：20-x1+x2+d3-d3+=223级有：40-x2+x3+d4-d4+=524级有：30-x3+x4+d5-d5+=303）各级员工的升级面不少于现有人数的18%对2级有：x1+d6-d6+=2218%对3级有：x2+d7-d7+=4018%对4级有：x3+d8-d8+=3018%4）总提级面人数不大于20%，但尽可能多提x1+x2+x3+d9-d9+=10020%第二十三张，PPT共三十一页，创作于2022年6月（3）目标函数：minZ1=d1+minZ2=d2+d3+d4+d5+minZ3=d6

20、-+d7-+d8-minZ4=d9+d9-案例案例3 有三个产地向四个销地供应物资。产地有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应的供应量量ai、销地、销地Bj(j=1,2,3,4)的需要量的需要量bj、各产销地之间的单位物资运费、各产销地之间的单位物资运费Cij如表如表2所示。表中，所示。表中，ai和和bj的单位为吨，的单位为吨，Cij的单位为元的单位为元/吨。编制吨。编制调运方案时要求按照相应的优先级依次考虑下列七个目标：调运方案时要求按照相应的优先级依次考虑下列七个目标：P1：B4是重点保证单位，其需要量应尽可能全部满足；是重点保证单位，其需要量应尽可能全部满足；P2

21、：A3向向B1提供的物资不少于提供的物资不少于100吨；吨；P3：每个销地得到的物资数量不少于其需要量的：每个销地得到的物资数量不少于其需要量的80%；第二十四张，PPT共三十一页，创作于2022年6月P4：实实际际的的总总运运费费不不超超过过最最小小总总运运费费a的的110%，这这里里的的最最小小总总费费用利用第三大题中第用利用第三大题中第2小题求出的结果；小题求出的结果；P5：因路况原因，尽量避免安排：因路况原因，尽量避免安排A2的物资运往的物资运往B4；P6：对：对B1和和B3的供应率要尽可能相同；的供应率要尽可能相同；P7：力求使总运费最省。：力求使总运费最省。试建立该问题的运筹学模型

22、。试建立该问题的运筹学模型。Cij BjAiB1B2B3B4aiA15267300A23546200A34523400bj200100450250解：用表上作业法可求得不考虑解：用表上作业法可求得不考虑P1至至P6各目标时的最小运费调运方案，各目标时的最小运费调运方案，相应的最小运费为相应的最小运费为2950元元第二十五张，PPT共三十一页，创作于2022年6月（1）决策变量：设）决策变量：设Ai运往运往Bj的物资为的物资为xij吨吨（2）约束条件：）约束条件：产量约束产量约束B4销量要满足销量要满足销量销量80%的限制的限制供应率尽可能相同供应率尽可能相同第二十六张，PPT共三十一页，创作于

23、2022年6月二、目标规划的解法二、目标规划的解法由于目标规划有多个目标，各个目标又有相对不同的重要性，求解时是首先满足重要性权数大的目标，再满足重要性权数次大的目标，所以并不能保证所有的目标都能达到，所求的解也不一定是最优解，而只能求出满意解。（3）目标函数）目标函数第二十七张，PPT共三十一页，创作于2022年6月求求解解目目标标规规划划的的仍仍用用单单纯纯形形法法，但但是是与与线线性性规规划划的的单单纯纯形形法法不不同同的的是是，此此时时检检验验数数行行不不再再是是一一行行，而而是是变变化化为一个检验数矩阵。为一个检验数矩阵。例例4用单纯形法求解如下线性目标规划模型minZ1=d1-，m

24、inZ2=d2+d2-，minZ3=d3-2x1+3x224 加入松驰变量化为标准形 2x1+3x2+x3=24st-x1+x2+d1-d1+=03x1+2x2+d2-d2+=264x1+3x2+d3-d3+=30解（1）取x3，d1-，d2-，d3-为基变量，建立初始单纯形表第二十八张，PPT共三十一页，创作于2022年6月-1-2-1123-13402630Z1Z2Z3000-100-100-100000100100100100031232-1342402630 x3d1-d2-d3-d3+d2+d1+d3-d2-d1-x3x2x1bXB迭代的步骤完全与线性规划的单纯形法一样。（2）满意解

25、的判定：检验数矩阵的每一列从上至下第一个非零元为负数，则解为满意解。迭代的最优表如下：第二十九张，PPT共三十一页，创作于2022年6月-2-1-1-11-1020Z1Z2Z3100000-106/5-2/5-13/5-10000010-6/52/51-3/57/51/5-11/50100000118/524/5224/5d3+x2d2-x1d3+d2+d1+d3-d2-d1-x3x2x1bXB因而满意解为：x1=24/5，x2=24/5，d2-=2，d3+=18/5其中第一、三目标已达到最优，第二个目标未达最优。目标利润Z=4x1+3x2=168/5第三十张，PPT共三十一页，创作于2022年6月感谢大家观看第三十一张，PPT共三十一页，创作于2022年6月