多目标决策讲义课件(ppt 63页).ppt

1、1,管理决策分析,裴 凤 合肥工业大学管理学院,2,主要内容：,第三章 多目标决策,第一节 多目标决策问题 第二节 化多目标为单目标的方法 第三节 目标分层法 第四节 目的规划法 第五节 逐步法,3,1. 什么是多目标决策？ 干部选拔、大学生择业、购物,2. 多目标决策问题的特点 目标多于一个 目标之间的不可公度性 目标之间的矛盾性,4,3. 多目标决策问题的分类,多属性决策问题（有限方案的多目标决策问题） 多目标决策问题（无限方案的多目标决策问题）,多准则决策问题,前者的决策空间是离散的，后者是连续的； 前者的选择余地是有限的、已知的，后者是无穷的、未知的。,区别：,5,准则(criteri

2、a)是对决策事物或现象有效性的某种度量，是事物或现象评价的基础。它在实际问题中有两种基本表现形式，即目标和属性。,目标(objective)是关于被研究问题的某种决策者所希望达到的状态的陈述，它表示决策者的愿望或决策者所希望达到的、努力的方向。,属性(attribute)是指方案所固有的特征、品质或性能参数，它是对基本目标达到程度的直接度量。对于每一种属性应该能够使用一定的方法来测量其水平的高低，即属性是可测得量，它反映了特定目标（该属性所联系的目标）被达到的程度。,4. 基本术语,6,第一节 多目标决策问题,一、多目标决策问题的一般形式,f1(x), f2(x), , fN(x)为目标函数

3、gi(x)0，i=1, 2, , m为约束条件 x为决策变量,目标函数,约束条件,向量优化问题（Vector optimization problems，简称VOP）,7,二、多目标决策问题解的概念,最优解 设x*X，如果对任意的xX ，均有f(x) f(x*), 即对一切的j=1, 2, , N，均有fj(x) fj(x*)，则称x*为多目标决策问题（Vp）的最优解。,第一节 多目标决策问题,8,非劣解,选好解,二、多目标决策问题解的概念,第一节 多目标决策问题,9,三、多目标决策方法的分类,1.优化之前给出偏好 2.优化之后给出偏好 3.优化之中逐步给出偏好,第一节 多目标决策问题,10,

4、第二节 化多目标为单目标的方法,1数学规划法,设有N个目标f1(x), f2(x), , fN(x) ，从中选择一个最重要的目标fk(x) ，使它满足最大或最小，而其它目标只要满足一定规格要求即可。从而构成了一个以重要目标fk(x)为单目标，以其余目标为约束的一个数学规划问题。,11,例：某厂生产A、B两种产品以供应市场的需要。生产两种产品所需的设备台时、原料消耗定额及其限制量、单位产品利润等如下表所示。在制定生产计划时工厂决策者考虑了如下三个目标：第一，计划期内生产产品所获得的利润为最大；第二，为满足市场对不同产品的需要，产品A的产量必须为产品B的产量的1.5倍；第三，为充分利用设备台时，设

5、备台时的使用时间不得少于11个单位。,第二节 化多目标为单目标的方法,12,解：设x1为产品A的产量，x2为产品B的产量，则以利润最大作为目标，其它两个目标可作为约束条件，其数学模型如下：,第二节 化多目标为单目标的方法,13,2线性加权和法,当目标函数 f1(x), f2(x), , fN(x)都要求最小（或最大）时，可构造新的目标函数,注：在运用线性加权和法时，所有的目标都必须具有相同的量纲。如果量纲不同，则需要统一量纲或做无量纲化处理。在多目标决策问题中，或由于各个目标的量纲不同，或有些目标值要求最大而有些要求最小，则可首先将目标值变换成效用值或无量纲值，然后再用线性加权和法计算新的目标

6、函数值并进行比较，以决定方案取舍。,第二节 化多目标为单目标的方法,14,3平方和加权法,基本思想：为所有目标 fj(x), j=1,2, ,N 确定一个预期达到的目标值fj*，使作出的决策与这些目标值越接近越好。,第二节 化多目标为单目标的方法,15,4理想点法,设有N个目标f1(x), f2(x), , fN(x) ，每个目标单独优化后的最优值为 则F* = (f1*, f2*, , fN*)T是一个理想点。,基本思想：定义一个范数，在这个范数意义下找一个点尽量接近理想点。,第二节 化多目标为单目标的方法,16,5费用效益分析法,f1(x), f2(x), , fs(x), fs+1(x)

7、, , fN(x),费用型目标,效益型目标,第二节 化多目标为单目标的方法,17,6功效系数法（几何平均法）,当目标达到最满意值时，取dj =1； 当目标达到最差值时，取dj =0。,功效系数,dj0,1，j = 1, 2, , N,适用情形：有的目标要求越大越好，有的要求越小越好，有的要求适中为好。,用函数来描述目标fj(x)与功效系数dj之间的关系，称之为功效函数，表达式为dj=Fj(x),第二节 化多目标为单目标的方法,18,0,x,Fj(x),(a),0,x,(b),0,x,(c),当 fj 越大越好时选用(a)，越小越好时选用(b)，适中时选用(c)。,不同类型的目标应选用不同类型的

8、功效函数,Fj(x),Fj(x),第二节 化多目标为单目标的方法,19,把fj(x)转化为dj后，用各目标的功效系数值的几何平均值作为评价函数，即 显然D越大越好(0D1)。,D的综合性很强，例如当某项指标dk很不满意时,dk=0,则D=0；如果各项指标都令人满意，di 1，则D=1。 其实，功效系数D是加权平均法中乘法规则的特例：,第二节 化多目标为单目标的方法,20,第三节 目标分层法,1完全分层法（字典序法）,基本思想：把所有目标按照其重要性递减的顺序排列，首先求出第一重要目标的最优解集合X1，然后在集合X1中再求出第二重要目标的最优解集合X2，如此下去，直到把所有目标都求完为止，最后一

9、个目标的最优解就是原多目标决策问题的最优解。,21,2分层评价法,基本思想：把N个目标分为s个优先层次，0sN。记第k层（k =1, 2, , s）所有目标的下标构成的集合为Ik。优先考虑第一层目标，其次考虑第二层目标，如此下去，最后再考虑第s层目标。,第三节 目标分层法,22,3重点目标法,基本思想：先求出单目标fk(x)下的最优解集X1，然后在X1中求解由其余N-1个目标构成的新问题的有效解或弱有效解。,适用情形：多目标决策问题中有一个最重要的目标fk(x)，其余N-1个目标的重要程度难以区分。,第三节 目标分层法,23,第四节 目的规划法,目的规划的数学模型,目的规划的图解法,目的规划的

10、单纯形法,目的规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。,24,例1 某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。,一、目的规划模型,第四节 目的规划法,25,设：甲产品 x1 ，乙产品 x2,Max Z=70 x1+120 x2 9x1+ 4x2 3600 4x1+ 5x2 2000 3x1+10 x23000 x1 , x2 0,Max Z1=70 x1+120 x2 Min Z2= x1

11、Max Z3= x2 9x1+ 4x2 3600 4x1+ 5x2 2000 3x1+10 x23000 x1, x2 0,在上例中，若工厂提出下列要求： 1. 完成或超额完成利润指标50000元； 2. 产品甲不超过200件，产品乙不低于250件； 3. 现有钢材3600吨必须用完。,第四节 目的规划法,26,目标值：预先给定的某个目标的一个期望值。 实现值或决策值：当决策变量xj 被求出以后，目标函数的对应值. 偏差变量（事先无法确定的未知数）：实现值和目标值之间的差异,记为d。 正偏差变量：实现值超过目标值的部分，记为d。 负偏差变量：实现值未达到目标值的部分，记为d。,1.目标值和偏差

12、变量,相关概念,在一次决策中，实现值不可能既超过目标值又未达到目标值，故有 dd 0,并规定d0, d0,第四节 目的规划法,27,例2 对例1中的三个目标进行处理,其结果有两种可能： 70 x1+120 x250000 70 x1+120 x2d1+ = 50000 或70 x1+120 x250000 70 x1+120 x2+d1 = 50000,实际情况只有一种可能，当然优化前并不知道，而建模时却都要考虑到，因此，将上两式合成：,(1) 完成或超额完成利润指标 50000元,第四节 目的规划法,28,(2) 产品甲不超过200件，产品乙不低于250件；,(3) 3600吨钢材必须用完,

13、第四节 目的规划法,29,线性规划问题的目标函数，在给定了目标值并引入正、负偏差变量后，可变换为目标约束。,2.目标约束和绝对约束,绝对约束：必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，有一个不满足就无可行解。所以，绝对约束是硬约束。,第四节 目的规划法,30,3.目标函数, 要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则Min Z = f (d+ d)。, 要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则Min Z = f (d)。, 要求不低于目标值，即超过量不限，也就是负偏差变量尽可能小，则Min Z = f (d)。,对于由绝对约

14、束转化而来的目标函数，也照上述处理即可。,目标函数要求总偏差量最小，记为Min Z = f(d, d)。 一般说来，有以下三种情况，但只能出现其中之一：,第四节 目的规划法,31,优先因子Pk 是将决策目标按其重要程度排序并表示出来。P1P2PkPk+1PK，k=1,2,K。 权系数k 区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。,对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。,4.优先因子（优先等级）与权系数,5.满意解（具有层次意义的解）,第四节 目的规划法,32,对于例1中的目标： 1.完成或超额完成利润

15、指标50000元； 2.产品甲不超过200件，产品乙不低于250件； 3.现有钢材3600吨必须用完。 若实现值没有达到目标，则存在偏差，希望按目标先后尽可能使偏差最小。,目标2有两个要求，且具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即 70:120，化简为7:12。,第四节 目的规划法,33,目的规划模型为：,第四节 目的规划法,34,例3 某厂生产、两种产品，有关数据如表所示。试求获利最大的生产方案。,要求考虑： 1.产品的产量不低于产品的产量； 2.充分利用设备有效台时，不加班； 3.利润不小于56 元。,设：、产品产量分别为x1, x2,第四节 目的规划法,3

16、5,目的规划模型：,第四节 目的规划法,36,目的规划模型的一般形式：,第四节 目的规划法,37,目的规划的建模步骤,1.根据问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；,4.对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数kl+和kl。,3.给各目标赋予相应的优先因子Pk（k=1,2,K）。,2.根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。,其中，kl 和kl +分别为第k 个目标中第l 个子目标的优先权。,第四节 目的规划法,38,5.根据决策者的要求，按下列情况之一构造一个由优先

17、因子和权系数相对应的偏差变量组成的、要求实现极小化的目标函数，即达成函数。, 恰好达到目标值，取dl+ + dl。, 不希望低于目标值，取dl。, 不希望超过目标值，取dl+ 。,第四节 目的规划法,39,图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。,步骤： 1. 确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来； 2. 在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；,二、目的规划的图解法,第四节 目的规划法,40,3.求满足最高优先等级目标的解

18、； 4.转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解； 5.重复4，直到所有优先等级的目标都已审查完毕为止； 6.确定最优解或满意解。,例4 用图解法求解目标规划问题,第四节 目的规划法,41,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,A,x2,x1,B,C,B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上的所有点均是该问题的解（无穷多最优解）。,第四节 目的规划法,42,练习：用图解法求解下列目标规划问题,第四节 目的规划法,43,C,D,结论：有无穷多最优解。C(2,4), D(10/3,1

19、0/3),第四节 目的规划法,44,三、目的规划的单纯形法,单纯形法的基本思想：,确定初始基可行解,检验,结束,Y,旋转运算 寻找新的基可行解,N,第四节 目的规划法,45,第四节 目的规划法,46,P1,P3,P2,第四节 目的规划法,47,= min2500/30, 140/2, 60/1, -=60 ,故d3-为换出变量。, = 2.5P2(0P1+0010+00)= 2.5P2 , 将2.5填P2行。,第四节 目的规划法,48,= min700/30, 20/2, , =10 ,故d2-为换出变量。, = 2.5P2(30P1+2010+00)= 2.5P230P1,第四节 目的规划法

20、,49,= min400/15, =10 ,故d1-为换出变量。, = 0(15P1+2.5P2/2+1/20+00)=15P1-2.5/2,50,= min,350/6,1250/6,100/1=75 ,故d3+为换出变量。,第四节 目的规划法,51,表中 P3 行有负检验数，说明P3 级目标没有实现，但已无法改进，得到满意解 x1 =60，x2 =175/3，d2+ =115/3，d4- =125/3。,第四节 目的规划法,52,结果分析：计算结果表明，工厂应生产A产品60件，B产品175/3件，2500元的利润目标刚好达到。,d4- =125/3，表明产品B比最高限额少125/3件，满足

21、要求。,d2 =115/3 表明甲资源超过库存115/3公斤，该目标没有达到。 即甲资源多消耗115/3公斤，刚好实现2500元的利润目标。而按现有消耗水平和资源库存量，无法实现利润目标。,可考虑如下措施：降低A、B产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变P3级目标值，增加甲资源115/3公斤。 若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意解果。,第四节 目的规划法,53,1.建立初始单纯形表。 一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部 。,2.检验是否为满意解

22、。判别准则如下： 按优先级别从高到低依次检查各检验数行。,单纯形法的计算步骤,检查Pk这一行的检验数kj (j=1,2,n+2m).若Pk这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第3步；若Pk这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第6步。,第四节 目的规划法,54,3.确定进基变量。 在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。,4.确定出基变量 其方法同线性规划，即依据最小比值原则。 故确定xr为出基变量。若有几个相同的行可供选择时，选最上面那一行