《多目标规划模型演示文稿》由会员分享，可在线阅读，更多相关《多目标规划模型演示文稿（60页珍藏版）》请在金锄头文库上搜索。
1、多目标规划(guhu)模型演示文稿1页，共60页，星期一。2（优选）第五讲多目标(mbio)规划模型2页，共60页，星期一。f1f21234567810.1多目标多目标(mbio)决策问题的特征决策问题的特征 在解决单目标问题时，我们的任务是选择一个或一组变量在解决单目标问题时，我们的任务是选择一个或一组变量(binling)X，使目标函数，使目标函数f(X)取得最大（或最小）。对于任意两方案取得最大（或最小）。对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。但在多目标情况下，问题却不那么单纯了。例如，有两个目标
2、但在多目标情况下，问题却不那么单纯了。例如，有两个目标f1(X)，f2(X),希望它们都越大越好。下图列出在这两个目标下共有希望它们都越大越好。下图列出在这两个目标下共有8个解的方案。个解的方案。其中方案其中方案1，2，3，4称为劣解，因为它们在两个目标值上都比方案称为劣解，因为它们在两个目标值上都比方案5差，差，是可以淘汰的解。而方案是可以淘汰的解。而方案5，6，7，8是非劣解（或称为有效解，满意解）是非劣解（或称为有效解，满意解），因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相，因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却
3、更差。比，总有一个指标更优越，而另一个指标却更差。一、解的特点一、解的特点3页，共60页，星期一。二、模型结构二、模型结构 多目标决策问题包含有三大要素：目标、方案和决策者。多目标决策问题包含有三大要素：目标、方案和决策者。在多目标决策问题中，目标有多层次的含义。从最高层次来看，目在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目
4、的盈利要大、成本要低、风险要小；的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道目标也可看成衡量总目标得以实现的各个准则，如食品的味道(wi dao)要好，质量要好，花费要少。要好，质量要好，花费要少。 多目标决策问题中的方案即为决策变量，也称为多目标问多目标决策问题中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题些问题的方案是有限的，有些问题 的方案是无限的。方案有的方案是无限的。方案有其特征或特性，称
5、之为属性。其特征或特性，称之为属性。4页，共60页，星期一。1、多目标规划问题的模型(mxng)结构为决策(juc)变量如对于求极大(max)型，其各种解定义如下：绝对最优解：若对于任意的X，都有F（X*）F(X)有效解：若不存在X，使得F（X*）F(X)弱有效解：若不存在X，使得F（X*)F(X)5页，共60页，星期一。6页，共60页，星期一。7页，共60页，星期一。2、多目标优选问题的模型(mxng)结构可用效用函数来表示。设方案的效用是目标属性的函数：并设且各个方案(fngn)的效用函数分别为则多目标优选模型的结构可表示如下：8页，共60页，星期一。10.2 多目标规划多目标规划(guh
6、u)问题的求解问题的求解1、主要目标法、主要目标法在有些多目标决策问题中，各种目标的重要性程度(chngd)往往不一样。其中一个重要性程度(chngd)最高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。例如，在上述多目标问题中，假定f1(X)为主要目标，其余p-1个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足一定的条件，即9页，共60页，星期一。例题例题1 某工厂在一个计划期内生产甲、乙两种产品，各产品都某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗要消耗A，B，C三种不同的资源三种不同的资源(zyun)。每件产品对资源。每件产品对资源(zyun)
7、的的单位消耗、各种资源单位消耗、各种资源(zyun)的限量以及各产品的单位价格、单位利的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？怎样安排生产，才能使利润和产值都最大，且造成的污染最小？甲乙资源限量资源A单位消耗资源B单位消耗资源C单位消耗9434510240200300单位产品的价格400600单位产品的利润70120单位产品的污染3210页，共60页，星期一。解：问题(wnt)的多目标模型如下对于上述模型的三个目标，工厂确定利润最
8、大为主要目标。另两个目标则通过预测预先给定的希望达到的目标值转化为约束条件。经研究，工厂认为总产值至少应达到20000个单位，而污染控制(kngzh)在90个单位以下，即由主要目标法化为单目标问题用单纯形法求得其最优解为11页，共60页，星期一。2、线性加权和目标、线性加权和目标(mbio)规划规划在上述目标规划中，假定f1(X),f2(X),fp(X)具有相同的量纲,按照一定的规则(guz)分别给fi赋予相同的权系数i，作线性加权和评价函数则多目标问题化为如下的单目标问题12页，共60页，星期一。例如，某公司计划购进一批新卡车，可供选择的卡车有如下例如，某公司计划购进一批新卡车，可供选择的卡
9、车有如下4种种类型：类型：A1，A2，A3，A4。现考虑。现考虑6个方案属性：维修期限个方案属性：维修期限(qxin)f1，每，每100升汽油所跑的里数升汽油所跑的里数f2，最大载重吨数，最大载重吨数f3，价格（万，价格（万元）元）f4，可靠性，可靠性f5，灵敏性，灵敏性f6。这。这4种型号的卡车分别关于目标属性种型号的卡车分别关于目标属性的指标值的指标值fij如下表所示。如下表所示。fijf1f2f3f4f5f6A12.01500455一般高A22.527003.665低一般A32.020004.245高很高A42.21800450很高一般首先对不同首先对不同(b tn)度量单位和不同度量单
10、位和不同(b tn)数量级的指标值进行标准化处数量级的指标值进行标准化处理。先将定性指标定量化：理。先将定性指标定量化：13页，共60页，星期一。效益型指标很低低一般高 很高13579很高高一般低 很低 成本型指标可靠性和灵敏性都属于效益型指标，其打分(dfn)如下可靠性一般低高很高5379灵敏性高一般很高一般7595按以下公式作无量(wling)纲的标准化处理其中：14页，共60页，星期一。变换(binhun)后的指标值矩阵为：aijf1f2f3f4f5f6A1116750.53450.5A2100100110011A3142.25100167100A440.625.756725.75100
11、1设权系数(xsh)向量为W=（0.2,0.1,0.1,0.1,0.2,0.3),则故最优方案为选购A3型卡车15页，共60页，星期一。3、分层序列法：、分层序列法：1.基本步骤：把(VP)中的p个目标按其重要程度排序。依次求单目标规划(guhu)的最优解。2.过程：无妨设其次序为先求解得最优值，记再解得最优值，依次进行，直到得最优值则是在分层序列意义下的最优解集合。16页，共60页，星期一。3.性质：，即在分层序列意义下的最优解是有效解。证明：反证。设，但，则必存在使即至少(zhsho)有一个j0，使,由于，即，矛盾。得证。4.进一步讨论：上述方法过程中，当某个问题(Pj)的解唯一时，则问题
12、的求解无意义，因为解都是唯一的。实际求解时，有较宽容意义下的分层序列法：取为预先给定的宽容值，整个解法同原方法类似，只是取各约束集合时，分别取为：17页，共60页，星期一。4、步骤法（、步骤法（STEM法）法）这是一种交互方法(fngf)，其求解过程通过分析者与决策者之间的对话逐步进行，故称步骤法。步骤法的基本思想是，首先需要求出原多目标问题的一组理想解(f1*,f2*,fp*)。实际上，这些解fi*(i=1,2,p)无法同时达到，但可以当作一组理想的最优值。以理想解作为一个标准，可以估计有效解，然后通过对话，不断修改目标值，并把降低要求的目标作为新的约束条件加入原来的约束条件中去重新计算，直
13、到决策者得到满意的解。步骤法算法如下：第一步：分别求解以下p个单目标问题的最优解18页，共60页，星期一。得到最优解，其相应的目标值即为理想(lxing)值，此最优解处别的目标所取的值用表示，即，把上述计算结果列入下表19页，共60页，星期一。在表中，确定(qudng)每一列的最小值并记第i列的最小值为fip(i=1,2,p)第二步：求解(qiji)其中：这里（1）20页，共60页，星期一。第三步：将上述模型（1）的解X0与相应的目标值f1(X0),f2(X0),fp(X0)交给决策者去判断。决策者把这些目标值与理想值进行比较后，如果认为其中某些目标值太坏，另一些目标值可以不要那么太好，可以把
14、比较好的目标值中的某一个(y)修改得差一些，以使水平太坏的目标得到改善。当决策者减少了第j个目标的值之后，约束条件S应该改为S*在进行下一次迭代时，对应于降低了要求的那些目标(mbio)fj(j=1,2,k)的权系数i应该设为0。这种迭代继续下去，直到决策者满意为止。21页，共60页，星期一。例题：例题：某公司考虑生产两种光电太阳能电池：产品(chnpn)甲和产品(chnpn)乙。这种生产过程会在空气中引起放射性污染。因此，公司经理有两个目标：极大化利润与极小化总的放射性污染。已知在一个生产周期内，每单位甲产品(chnpn)的收益是1元，每单位乙产品(chnpn)的收益是3元。而放射性污染的数
15、量，每单位甲产品(chnpn)是1.5个单位,每单位乙产品(chnpn)是1个单位.由于机器能力(小时)、装配能力（人时）和可用的原材料（单位）的限制，约束条件是目标有两个(lin):一是利润最大,二是污染最小.该问题的多目标规划模型如下:22页，共60页，星期一。解:首先,分别求解两个单目标问题(wnt)的最优解,由它们得到的目标函数值组成理想解.23页，共60页，星期一。由此,构造(guzo)支付表Xf1*f2*(7,13)(0,0)460-23.50由此计算(jsun)两个目标与理想值偏离的权重解下列线性规划问题:24页，共60页，星期一。由此求得,分析者把计算结果交给决策者,决策者将目
16、标值与理想值(21.192,-7.064)与理想值(46,0)比较,如果认为f2是满意的,但利润太低,并认为污染可接受到10个单位(dnwi).于是,约束集修改成进行下一轮迭代.首先设2=0,并计算(jsun)得1=1.将模型修改为25页，共60页，星期一。由此求得:决策者把这一结果(jigu)与前一轮的解及理想值作比较,认为两个目标值都比较满意,则迭代结束.26页，共60页，星期一。 目标目标(mbio)(mbio)规划模型规划模型线性规划问题都是处理单个目标的情况，但是在现实世界中有许多问题具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，有的目标相互依赖，例如决策者既希望实现利润最大，又希望实现产值最大；有的相互抵触，如决策者既希望充分利用资源(zyun)，又不希望超越资源(zyun)限量。而决策者希望在某些限制条件下，依次实现这些目标。这就是目标规划所要解决的问题。当所有的目标函数和约束条件都是线性时，我们称其为线性目标规划问题。在这里我们主要讨论线性目标规划问题。一、目标规划模型的建立一、目标规划模型的建立27页，共60页，星期一。引例引例1： 对于生产计划问题： 甲
