L16多目标决策.ppt

L16 多目标决策n詹文杰（教授詹文杰（教授/博导）博导）n Office: 611室室n Tel: n Email: 1学习目标n了解多目标决策的特征；n了解常用的多目标决策求解方法；n了解步骤法(STEM法)；n掌握目标规划方法(图解法)216 多目标决策多目标决策 n16.1 多目标决策的特征n16.2 多目标决策的求解n16.3 步骤法(STEM法)n16.4 目标规划方法316.1 多目标决策的特征n本章讨论决策变量为连续型的多准则决策问题，即多目标决策问题(MODM)n这类问题的备选方案集由一集有因果关系的决策变量隐式地给出n由于在求解这一类问题时，尤其在生成非劣解过程中，决策分析人员的作用十分重要，因此将特别关注分析人员如何与决策人结合去获得决策人最满意的方案416.1 多目标决策的特征n一、解的特点n二、模型结构5f1f212345678n在解决单目标问题时，我们的任务是选择一个或一组变量在解决单目标问题时，我们的任务是选择一个或一组变量X，，使目标函数使目标函数f(X)取得最大（或最小）对于任意两方案所对取得最大（或最小）对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。

应的解，只要比较它们相应的目标值，就可以判断谁优谁劣n但在多目标情况下，问题却不那么单纯了例如，有两个目但在多目标情况下，问题却不那么单纯了例如，有两个目标标f1(X)，，f2(X),希望它们都希望它们都越大越好越大越好下图列出在这两个目标下图列出在这两个目标下共有下共有8个解的方案其中个解的方案其中方案方案1，，2，，3，，4称为劣解称为劣解，因为它，因为它们在两个目标值上都比方案们在两个目标值上都比方案5差，是可以淘汰的解而差，是可以淘汰的解而方案方案5，，6，，7，，8是非劣解（或称为有效解，满意解），是非劣解（或称为有效解，满意解），因为这些解都因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却更差有一个指标更优越，而另一个指标却更差一、解的特点6二、模型结构n多目标决策问题包含有三大要素：目标、方案和决策者n在多目标决策问题中，目标有多层次的含义从最高在多目标决策问题中，目标有多层次的含义从最高层次来看，目标代表了问题要达到的总目标如确定层次来看，目标代表了问题要达到的总目标。

如确定最满意的投资项目、选择最满意的食品从较低层次最满意的投资项目、选择最满意的食品从较低层次来看，目标可看成是体现总目标得以实现的各个具体来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少如食品的味道要好，质量要好，花费要少n多目标决策问题中的方案即为多目标决策问题中的方案即为决策变量决策变量，也称为多目，也称为多目标问题的解备选方案即决策问题的标问题的解备选方案即决策问题的可行解可行解在多目标决策中，有些问题的方案是有限的，有些问题标决策中，有些问题的方案是有限的，有些问题 的的方案是无限的方案有其特征或特性，称之为属性方案是无限的方案有其特征或特性，称之为属性7为决策变量n如对于求极大(max)型，其各种解定义如下：n绝对最优解：若对于任意的X，都有F(X*) ≥ F(X);n有效解：若不存在X，使得 F(X*) ≤ F(X);n弱有效解：若不存在X，使得F(X*) < F(X)。

多目标决策的数学模型8绝对最优解9不存在绝对最优解的情况10n设方案的效用是目标属性的函数：并设：且各个方案的效用函数分别为：n则多目标优选模型的结构可表示如下：多目标决策的效用数学模型1116.2 多目标决策的求解n一、主要目标法n二、线性加权和法n三、平方加权和法n四、理想点法12一、主要目标法n在有些多目标决策问题中，各种目标的重要性程度往往不一样其中一个重要性程度最高和最为关键的目标，称之为主要目标法其余的目标则称为非主要目标n例如，在上述多目标问题中，假定f1(x)为主要目标，其余p-1个为非主要目标这时，希望主要目标达到极大值，并要求其余的目标满足一定的条件，即：13例例1：：某工厂在一个计划期内生产甲、乙两种产品，各产某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗品都要消耗A，，B，，C三种不同的资源每件产品对资源三种不同的资源每件产品对资源的单位消耗、各种资源的限量以及各产品的单位价格、的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表假定产品能全部单位利润和所造成的单位污染如下表假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？最大，且造成的污染最小？14解：问题的多目标模型如下：n对于上述模型的三个目标，工厂对于上述模型的三个目标，工厂确定利润最大为主要目标。

确定利润最大为主要目标n另两个目标通过预测预先给定的另两个目标通过预测预先给定的希望达到的目标值转化为约束条件希望达到的目标值转化为约束条件n经研究，工厂认为总产值至少应经研究，工厂认为总产值至少应达到达到20000个单位，而污染控制在个单位，而污染控制在90个单位以下，即：个单位以下，即：由主要目标法化为单目标问题：用单纯形法求得其最优解为：15n在上述目标规划中，假定f1(X), f2(X),…, fp(X)具有相同的量具有相同的量纲纲,按照一定的规则分别给fk 赋予相同的权系数ωk，作线性加权和评价函数：则多目标问题化为如下的单目标问题：二、线性加权和法16二、线性加权和法例2：求解 X={x∈R2|x1+2x2≤10，x2≤4，x1≥0，x2≥0}X是凸集，f1(x), f2(x), f3(x)都是X上的凸函数这里：17解：定义权系数wk≥0 (k=1,2,3), 其中：w1+w2+w3=1. 构造评价函数： 求解单目标最优目标问题： 显然，对于不同的权系数，最优解对于不同的权系数，最优解x*(w)是不是不同的，但是它们都是原多目标问题的非劣解同的，但是它们都是原多目标问题的非劣解，下面给出几组权系数及其对应的最优解（表1）。

18序w=(w1,w2,w3)X(w)=(x1,x2)F=(f1,f2,f3)12345(1, 0, 0)(0, 1, 0)(0, 0, 1)(1/3, 1/3, 1/3)(3/6, 2/6, 1/6)(1, 1)(2, 3)(4, 2)(7/3, 2)(11/6, 11/6)(0, 5, 10)(5, 0, 5 )(10, 5, 0)(25/9, 10/9, 25/9)(25/18, 25/18, 85/18)表表1 1 线性加权法的最优解线性加权法的最优解 可以证明，这个问题的全部非劣解为：可以证明，这个问题的全部非劣解为：其中：19二、线性加权和法n线性加权和法中权系数确定方法：n1)  — 法 n2)λ — 法 201)  — 法 n先对P个分量 fk(x)分别求极值(k=1,2,…,P)假设得到P个相应的极值点xk (k=1,2,…,P)，令：n然后把这个P个极值点分别代入评价函数U(x)中，得到P个方程：其中：是待定常数，由此可以解出权系数21例3： 用法求本节例2的权系数n从表1知，3个单目标分量单独求极小化，所得3个极小点是：n将3个极小点依次代入目标函数U(x)后，可以构造线性方程组如下：不难解出，这个方程组有唯一解：n其相应的线性加权和问题（P2）的最优解为： ， 它也是多目标问题（P0）的非劣解，这时： 222)λ — 法 n化为单目标决策问题：化为单目标决策问题：适用条件：适用条件：fk*≠≠0。

n多目标决策问题：多目标决策问题：其中，其中，23三、平方加权和法n先求各分量的最优值：n再分别赋以权系数wk (k=1,2,..,P)，作平方加权和评价函数：n则多目标问题化为如下的单目标问题：意义：目标意义：目标意义：目标意义：目标f fk k( (x x) )与规定值与规定值与规定值与规定值f fk k* *相差尽量小（相差尽量小（相差尽量小（相差尽量小（k k=1, 2, …, =1, 2, …, P P）24四、理想点法则称：为理想点n若所有xk都相同，记为 x*，则x*就是所求的多目标决策问题的最优解；n若不然，则考虑求解下面的单目标决策问题：n先求各分量的最优值：25n例4：设有多目标决策问题解：1. 先求各分量的最优值，得：2. 构造目标函数：3. 用理想点法化为单目标决策问题2616.3 步骤法(STEM法)nSTEM法，它是英文“Step Method”的缩写这个方法是一种迭代方法n它和目的规划法不同，在求解过程中的每一步，分析人和决策人之间都有对话分析人把分析的结果告诉决策人，并征求他的意见n如果决策人认为满意，则迭代终止；n如果决策人认为不够满意，则分析人根据他的意见再重复计算，去改进他的结果。

n由于它是逐步进行的，故称步骤法27n设有多目标线性规划问题：设有多目标线性规划问题：其中：其中：STEM法的求解步骤：28n分别求解分别求解k个个 单目标线性规划问题：单目标线性规划问题：n得到的最优解记为得到的最优解记为x(i)，其相应的目标函数，其相应的目标函数值记为值记为fi*（（i=1, 2, …, k），并），并x(i)代入其它目代入其它目标函数标函数：：结果可列表给出（称为结果可列表给出（称为支付表支付表）步骤步骤1：：29支付表（ STEM法）x(i)f1f2…fj…fkx(1)z11z21…zj1…zk1…………………x(i)z1iz2i…zji…zki…………………x(k)z1kz2k…zjk…zkk30n求权系数：从支付表中得到求权系数：从支付表中得到n 为找出目标值的偏差以及消除不同目标值的为找出目标值的偏差以及消除不同目标值的量纲不同的问题，进行如下处理量纲不同的问题，进行如下处理：：n归一化后得权系归一化后得权系数：数：步骤步骤2：：31n求解：求解：（（使目标与理想值的最大加权偏差使目标与理想值的最大加权偏差λ最小最小））该线性规划问题的最优解记为该线性规划问题的最优解记为x0 。

步骤步骤3：：32n将将x0 和相应的目标值和相应的目标值交给决策者判断交给决策者判断n 决策者把这些目标值与理想值进行比较后，决策者把这些目标值与理想值进行比较后，若认为满意了，则可停止计算；若认为满意了，则可停止计算；n 若认为相差太远，则考虑适当修正若认为相差太远，则考虑适当修正 如：考虑对第虑对第r个目标让一点步，降低一点目标值个目标让一点步，降低一点目标值△△fr 步骤步骤4：：33n求解：求解：n 求得解后，再与决策者对话，如此重复，求得解后，再与决策者对话，如此重复，直至决策者认为满意了为止直至决策者认为满意了为止步骤步骤5：：34例例5：：某公司考虑生产甲、乙两种太阳能电某公司考虑生产甲、乙两种太阳能电池，生产过程会在空气中引起放射性污染，池，生产过程会在空气中引起放射性污染，因此决策者有两个目标：极大化利润与极因此决策者有两个目标：极大化利润与极小化总的放射性污染已知在一个生产周小化总的放射性污染已知在一个生产周期内，每单位甲产品的收益是期内，每单位甲产品的收益是1元，每单位元，每单位乙产品的收益是乙产品的收益是3元；每单位甲产品的放射元；每单位甲产品的放射性污染是性污染是1.5单位，每单位乙产品的放射性单位，每单位乙产品的放射性污染是污染是1单位，由于机器能力（小时）、装单位，由于机器能力（小时）、装配能力（人时）和可用的原材料（单位）配能力（人时）和可用的原材料（单位）的限制，约束条件是（的限制，约束条件是（ x1、、x2分别为甲、乙分别为甲、乙产品的产量）：产品的产量）：35例例5：： 　该问题的目标函数为：该问题的目标函数为：该问题的约束条件为：该问题的约束条件为：36例例5：： 　步骤步骤1：：先分别求解先分别求解得：得： x(1)=(7.25, 12.75)T，， x(2)=(0, 0)T f1*=45.5，， f2*=037例例5：： 　步骤步骤1：：得到如下支付表得到如下支付表38例例5：： 　步骤步骤2：：求权系数。

从支付表中得到：求权系数从支付表中得到：归一化后得权系数：归一化后得权系数：39步骤步骤3：：求解求解最优解为最优解为x0=(0, 9.57)T, f1(x0)=28.71, f2(x0)=-9.57 例例5：： 　40步骤步骤5：修改约束集：修改约束集求解得求解得x1=(0, 10)T, f1(x1)=30, f2(x0)=- -10若决策者认为满意，停止迭代若决策者认为满意，停止迭代例例5：： 　步骤步骤4：将：将x0=(0, 9.57)T, f1(x0)=28.71, f2(x0)=-9.57 交给决策者判断交给决策者判断决策者将其与理想值（决策者将其与理想值（45.5, 0）进行比较后，认为）进行比较后，认为f2 是满意的，但利润太低且认为可以接受污染值是满意的，但利润太低且认为可以接受污染值为为10个单位4116.4 目标规划方法n目标规划是求解多目标线性规划的方法之一n目标规划的基本方法：n对每一个目标函数引进一个期望值期望值；n引入正、负偏差变量引入正、负偏差变量，表示实际值与期望值的偏差，并将目标函数转化为约束条件并将目标函数转化为约束条件，与原有约束条件构成新的约束条件组；n引入目标的优先等级和权系数，构造新的单一的目标函数，将多目标问题转化为单目标问题求解。

42例例6：：某厂生产甲、乙两种产品，每件产品的某厂生产甲、乙两种产品，每件产品的单位利润、所消耗的原材料及设备工时、单位利润、所消耗的原材料及设备工时、材料和设备工时的限额如下表所示材料和设备工时的限额如下表所示产品产品消耗消耗原料原料43n决策者根据市场需求等一系列决策者根据市场需求等一系列因素，提出下列因素，提出下列目标目标（依重要（依重要程度排列）：程度排列）：①①首要目标是保证甲、乙产品的产首要目标是保证甲、乙产品的产量尽可能接近量尽可能接近②②尽可能充分利用工时，但又不希尽可能充分利用工时，但又不希望加班望加班；；③③确保达到计划利润确保达到计划利润30元元 试对厂家生产作出决策分析设甲、乙产品试对厂家生产作出决策分析设甲、乙产品的产量分别为的产量分别为x1、、x2件44ª该问题的目标函数为：该问题的目标函数为：•该问题的约束条件为：该问题的约束条件为：45n1)目标函数的目标函数的期望值期望值ek 对于多目标线性规划的每一个目标函数对于多目标线性规划的每一个目标函数值值Zk( (k=1, 2, …, K) )，根据实际情况和决策，根据实际情况和决策者的希望，者的希望，确定一个期望值确定一个期望值ek 。

n在在例例6中中:n乙产品与甲产品产量之差的乙产品与甲产品产量之差的目标值可定为目标值可定为0；；n生产工时的生产工时的目标值为目标值为26（工时）；（工时）；n利润的利润的目标值为目标值为30（元）16.4 目标规划方法46n2、正负偏差变量、正负偏差变量 对每一个目标函数值，分别引入正、负对每一个目标函数值，分别引入正、负偏差变量偏差变量：：n正正负负偏偏差差变变量量分分别别表表示示实实际际目目标标值值超超过过和和低低于期望值的数值于期望值的数值n引引入入偏偏差差变变量量之之后后，，目目标标就就变变成成了了约约束束条条件件，，成为约束条件组的一部分成为约束条件组的一部分16.4 目标规划方法47n在在例例6中，令：中，令：nd1+, d1- -分分别别表表示示乙乙产产品品与与甲甲产产品品产产量量之之差差超超过过和和达达不到目标值的偏差变量；不到目标值的偏差变量；nd2+, d2- -分分别别表表示示生生产产工工时时超超过过和和达达不不到到目目标标值值的的偏偏差变量；差变量；nd3+, d3- -分别利润超过和达不到目标值的偏差变量；分别利润超过和达不到目标值的偏差变量；n则三个则三个目标可化为含有偏差变量的约束条件目标可化为含有偏差变量的约束条件：：16.4 目标规划方法48n3、优先因子（优先等级）和权系数、优先因子（优先等级）和权系数如何区别不同目标的主次轻重？如何区别不同目标的主次轻重？n凡要求第一位达到的目标赋于优先因子凡要求第一位达到的目标赋于优先因子P1，次位，次位的目标赋于优先因子的目标赋于优先因子P2，，…，并规定，并规定Pk＞＞＞＞Pk+1（表示（表示Pk比比Pk+1有更大的优先权，有更大的优先权，Pk+1级目标是在级目标是在保证保证Pk 级目标实现的基础上才能考虑的）（级目标实现的基础上才能考虑的）（k＝＝1,2，，…，，K））n为区别具有相同优先因子的两个目标的差别，可为区别具有相同优先因子的两个目标的差别，可分别赋于它们不同的权系数分别赋于它们不同的权系数ωjn优先等级及权数的赋值由决策者确定优先等级及权数的赋值由决策者确定。

16.4 目标规划方法49n4、达成函数、达成函数(准则函数准则函数)：目标规划模型的目：目标规划模型的目标函数n准则函数由各目标约束的正、负偏差变量及相应准则函数由各目标约束的正、负偏差变量及相应的优先因子和权系数构造而成的优先因子和权系数构造而成n注：目标规划模型的目标函数是对各目标的偏差注：目标规划模型的目标函数是对各目标的偏差的综合（将多目标化为单目标），在目标函数中的综合（将多目标化为单目标），在目标函数中不包含原决策变量，且一定是极小型的（偏差最不包含原决策变量，且一定是极小型的（偏差最小）16.4 目标规划方法504、达成函数(准则函数)n当每一目标值确定后，决策者的要求是偏差当每一目标值确定后，决策者的要求是偏差变量尽可能小，因此其目标函数只能是极小变量尽可能小，因此其目标函数只能是极小形式，形式，具体有以下三种基本形式具体有以下三种基本形式：：n2 2）要求）要求不超过不超过目标值目标值( (正偏差应尽可能小正偏差应尽可能小) )n3 3）要求）要求不低于不低于目标值目标值( (负偏差应尽可能小负偏差应尽可能小) )n1）要求）要求恰好达到恰好达到目标值目标值(正、负偏差都要尽可能正、负偏差都要尽可能小小)51n在在例例6中：中：n首首要要目目标标是是保保证证乙乙产产品品的的产产量量大大于于甲甲产产品品产产量量，，赋于优先因子赋于优先因子P1，目标为，目标为d1- -和和d2＋＋都尽可能小；都尽可能小；n次次级级目目标标是是生生产产工工时时恰恰好好达达到到目目标标值值，，赋赋于于优优先先因子因子P2，目标为，目标为d2- -和和d2＋＋都要小；都要小；n最最后后的的目目标标是是利利润润不不低低于于30元元，，赋赋于于优优先先因因子子P3，目标为，目标为d3- -尽可能小。

尽可能小n因此，可构造准则函数如下：因此，可构造准则函数如下：16.4 目标规划方法52例例6：：目标规划模型目标规划模型53线性规划线性规划 vs. 目标规划目标规划54目标规划的一般模型55n（（1）假设决策变量；）假设决策变量；n（（2）建立约束条件；）建立约束条件；n（（3）建立各个目标函数；）建立各个目标函数；n（（4）确定各目标期望值，引入偏差变量，）确定各目标期望值，引入偏差变量，将目标函数化为约束方程；将目标函数化为约束方程；n（（5）确定各目标优先级别和权系数，构造）确定各目标优先级别和权系数，构造准则函数准则函数 目标规划的建模步骤56例例7(10.2): 图解法图解法-目标规划目标规划n某车间生产甲、乙两种产品，产量分别为某车间生产甲、乙两种产品，产量分别为x1和和x2，产品甲每单位需，产品甲每单位需2个单位的劳动力和个单位的劳动力和3个单位原个单位原料，利润为料，利润为2；生产每单位产品乙需；生产每单位产品乙需3个单位劳动个单位劳动力和力和1.5个单位原料，利润为个单位原料，利润为3在下一计划期间在下一计划期间车间有车间有12单劳动力单劳动力12单位原料。

假定车间主任有单位原料假定车间主任有如下目标：如下目标：n①①利润至少为利润至少为6个单位；个单位；n②②两种产品产量经尽可能保持两种产品产量经尽可能保持x1 : x2 = 3 : 2；；n③③劳动力充分利用（不允许加班）劳动力充分利用（不允许加班）57解答1: 线性规划58解答2：目标规划①①利润是目标函数中的第一优先级，因此用利润是目标函数中的第一优先级，因此用d1表示利润偏差；因表示利润偏差；因为利润可以超过目的值，正偏差为利润可以超过目的值，正偏差d1+可以大于可以大于0，取，取w1+ =0，，使不在目标函数中出现；负偏差使不在目标函数中出现；负偏差d1-则是越小越好，把它作为第则是越小越好，把它作为第一优先级放到目标函数中一优先级放到目标函数中②②产量比例属于第二优先级，用产量比例属于第二优先级，用d2表示产量比例偏差，由于正、表示产量比例偏差，由于正、负偏差都不好，要将负偏差都不好，要将d2+和和d2-同时加入目标函数中同时加入目标函数中③③第三个目的是充分利用劳动力，因此用第三个目的是充分利用劳动力，因此用d3表示劳动力偏差，因表示劳动力偏差，因为不允许加班，劳动力不能出现正偏差，即为不允许加班，劳动力不能出现正偏差，即d3+ ≡0，所以约束，所以约束条件和目标函数中均无条件和目标函数中均无d3+出现；出现； d3-则作为第三个优先级放入则作为第三个优先级放入约束条件和目标函数中。

约束条件和目标函数中④④决策人未对原材料提任何要求，但是按常理，决策人未对原材料提任何要求，但是按常理， d4作为原材料偏作为原材料偏差，与劳动力一样，只会出现负偏差差，与劳动力一样，只会出现负偏差d4- ，正偏差，正偏差d4+ ≡0 59解答2:目标规划（续1）60解答2:目标规划（续2）61例例8（（10.3）：图解法）：图解法例例8（（10.3））：：(续上例) 由于上面的例子中数据选择比较特殊，决策人的所有目的均可满足；为了更好地说明问题，把已知条件中产品甲利润改为4，其余均不变；车间主任的目的改为：①最低利润12单位；②产量比例为1，即x1＝x2；③充分利用原料62解:目的规划①利润是目标函数中的第一优先级，因此用d1表示利润偏差；因为利润可以超过目的值，正偏差d1+可以大于0，使不在目标函数中出现；负偏差d1-则是越小越好，把它作为第一优先级放到目标函数中②产量比例属于第二优先级，用表示产量比例偏差，由于正、负偏差都不好，要将d2+和d2-同时加入目标函数中③决策人的第三个目的是充分利用原材料，因此用表示原材料偏差，因为原材料不可能出现正偏差，即d3+ ≡0，所以约束条件和目标函数中均无d3+出现； d3-则作为第三个优先级放入约束条件和目标函数中。

63例例9（（10.4）：图解法）：图解法例例9（（10.4）：）：(续上例) 由于上面的例子中数据选择比较特殊，决策人的所有目的均可满足；为了更好地说明问题，把已知条件中产品甲利润改为4，其余均不变；车间主任的目的改为：①最低利润12单位；②产量比例为1，即x1=x2；③充分利用劳动力； ④充分利用原料64解:目的规划①利润是目标函数中的第一优先级，因此用d1表示利润偏差；因为利润可以超过目的值，正偏差d1+可以大于0，使不在目标函数中出现；负偏差d1-则是越小越好，把它作为第一优先级放到目标函数中②产量比例属于第二优先级，用表示产量比例偏差，由于正、负偏差都不好，要将d2+和d2-同时加入目标函数中③决策人第三个目是充分利用劳动力，d3作为劳动力偏差，与原材料一样，只会出现负偏差d3- ，正偏差d3+ ≡0④决策人的第四个目的是充分利用原材料，因此用表示原材料偏差，因为原材料不可能出现正偏差，即d4+ ≡0，所以约束条件和目标函数中均无d4+出现； d4-则作为第四个优先级放入约束条件和目标函数中65距离测度中范数距离测度中范数p的选择的选择66偏差的度量偏差的度量67。