L16多目标决策

L16多目标决策詹文杰（教授/博导）Office:华中科技大学管理学院611室Tel:[phone]Email:[e-mail]学习目标了解多目标决策的特征；了解常用的多目标决策求解方法；了解步骤法(STEM法)；掌握目标规划方法(图解法)。16多目标决策16.1多目标决策的特征16.2多目标决策的求解16.3步骤法(STEM法)16.4目标规划方法16.1多目标决策的特征本章讨论决策变量为连续型的多准则决策问题，即多目标决策问题(MODM)。这类问题的备选方案集由一集有因果关系的决策变量隐式地给出。由于在求解这一类问题时，尤其在生成非劣解过程中，决策分析人员的作用十分重要，因此将特别关注分析人员如何与决策人结合去获得决策人最满意的方案。16.1多目标决策的特征一、解的特点二、模型结构f1f212345678在解决单目标问题时，我们的任务是选择一个或一组变量X，使目标函数f(X)取得最大（或最小）。对于任意两方案所对应的解，只要比较它们相应的目标值，就可以判断谁优谁劣。但在多目标情况下，问题却不那么单纯了。例如，有两个目标f1(X)，f2(X),希望它们都越大越好。下图列出在这两个目标下共有8个解的方案。其中方案1，2，3，4称为劣解，因为它们在两个目标值上都比方案5差，是可以淘汰的解。而方案5，6，7，8是非劣解（或称为有效解，满意解），因为这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一个相比，总有一个指标更优越，而另一个指标却更差。一、解的特点二、模型结构多目标决策问题包含有三大要素：目标、方案和决策者。在多目标决策问题中，目标有多层次的含义。从最高层次来看，目标代表了问题要达到的总目标。如确定最满意的投资项目、选择最满意的食品。从较低层次来看，目标可看成是体现总目标得以实现的各个具体的目标，如投资项目的盈利要大、成本要低、风险要小；目标也可看成衡量总目标得以实现的各个准则，如食品的味道要好，质量要好，花费要少。多目标决策问题中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。XxtsXfXfXfXFoptTp..}))(),....,(),(()({21),....,,(21nxxxX为决策变量如对于求极大(max)型，其各种解定义如下：绝对最优解：若对于任意的X，都有F(X*)≥F(X);有效解：若不存在X，使得F(X*)≤F(X);弱有效解：若不存在X，使得F(X*)F(X)。多目标决策的数学模型绝对最优解不存在绝对最优解的情况设方案的效用是目标属性的函数：),...,,()(21pfffUxU并设：)(jiijxfa且各个方案的效用函数分别为：),...,,()(21pjjjjaaaUxU则多目标优选模型的结构可表示如下：XxtsXUXUXUXUoptTp..}))(),....,(),(()({21多目标决策的效用数学模型16.2多目标决策的求解一、主要目标法二、线性加权和法三、平方加权和法四、理想点法一、主要目标法在有些多目标决策问题中，各种目标的重要性程度往往不一样。其中一个重要性程度最高和最为关键的目标，称之为主要目标法。其余的目标则称为非主要目标。XxtsxfxfxfxFoptPp..)]}(,),(),([)({021）（例如，在上述多目标问题中，假定f1(x)为主要目标，其余p-1个为非主要目标。这时，希望主要目标达到极大值，并要求其余的目标满足一定的条件，即：XxtsxfoptP..)}({11）（例1：某工厂在一个计划期内生产甲、乙两种产品，各产品都要消耗A，B，C三种不同的资源。每件产品对资源的单位消耗、各种资源的限量以及各产品的单位价格、单位利润和所造成的单位污染如下表。假定产品能全部销售出去，问每期怎样安排生产，才能使利润和产值都最大，且造成的污染最小？甲乙资源限量资源A单位消耗资源B单位消耗资源C单位消耗9434510240200300单位产品的价格400600单位产品的利润70120单位产品的污染32解：问题的多目标模型如下：0,300103200542404923)(min600400)(max12070)(max21212121213212211xxxxxxxxxxXfxxXfxxXf对于上述模型的三个目标，工厂确定利润最大为主要目标。另两个目标通过预测预先给定的希望达到的目标值转化为约束条件。经研究，工厂认为总产值至少应达到20000个单位，而污染控制在90个单位以下，即：9023)(20000600400)(213212xxXfxxXf由主要目标法化为单目标问题：0,300103200542404990232000060040012070)(max212121212121211xxxxxxxxxxxxxxXf用单纯形法求得其最优解为：90)(,20750)(,4025)(,25.26,5.1232121xfxfxfxx在上述目标规划中，假定f1(X),f2(X),…,fp(X)具有相同的量纲,按照一定的规则分别给fk赋予相同的权系数ωk，作线性加权和评价函数：pkkkXfXU1)()(则多目标问题化为如下的单目标问题：二、线性加权和法XxtsxfxfxfxFoptPp..)]}(,),(),([)({021）（XxtsXfXUoptPpkkk..})()({21）（二、线性加权和法例2：求解X={x∈R2|x1+2x2≤10，x2≤4，x1≥0，x2≥0}X是凸集，f1(x),f2(x),f3(x)都是X上的凸函数。XxtsxfxfxfxF..)](),(),([)(min321222132221222211)2()4()()3()2()()1()1()(xxxfxxxfxxxf这里：解：定义权系数wk≥0(k=1,2,3),其中：w1+w2+w3=1.构造评价函数：求解单目标最优目标问题：显然，对于不同的权系数，最优解x*(w)是不同的，但是它们都是原多目标问题的非劣解，下面给出几组权系数及其对应的最优解（表1）。31)()(kkkxfwxUXxtsxfwxUkkk..)()(min31序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线性加权法的最优解332211*2*1,)()(*xwxwxwxxwx24,32,11321xxx可以证明，这个问题的全部非劣解为：其中：0),,(321222132221222211)2()4()()3()2()()1()1()(xxxfxxxfxxxf二、线性加权和法线性加权和法中权系数确定方法：1)—法2)λ—法1)—法PjjpjkjjkwPkxfwxU111...,,2,1)()(先对P个分量fk(x)分别求极值(k=1,2,…,P)。假设得到P个相应的极值点xk(k=1,2,…,P)，令：),,2,1(;)()}({*PkxfxfoptfkkkXxk然后把这个P个极值点分别代入评价函数U(x)中，得到P个方程：其中：是待定常数，由此可以解出权系数。105105051050321213132.21,0,21,5*3*2*123,25**wx213,25,25F例3：用法求本节例2的权系数。从表1知，3个单目标分量单独求极小化，所得3个极小点是：24,32,11321xxx222132221222211)2()4()()3()2()()1()1()(xxxfxxxfxxxf将3个极小点依次代入目标函数U(x)后，可以构造线性方程组如下：31)()(jkjjkxfwxU不难解出，这个方程组有唯一解：其相应的线性加权和问题（P2）的最优解为：，它也是多目标问题（P0）的非劣解，这时：2)λ—法XxtsxfxfxfoptTP　..)(,),(),(21)()}({1**kkkXxkkkxfxfoptff，化为单目标决策问题：XxtsxfxoptUmkkk　..)()(1适用条件：fk*≠0。多目标决策问题：其中，三、平方加权和法),,2,1(;)()}({*PkxfxfoptfkkkXxkPkkkkfxfwxU12*])([)(XxtsfxfwxUPPkkkk..}])([)(min{312*）（XxtsxfxfxfxFoptPp..)]}(,),(),([)({021）（先求各分量的最优值：再分别赋以权系数wk(k=1,2,..,P)，作平方加权和评价函数：则多目标问题化为如下的单目标问题：意义：目标fk(x)与规定值fk*相差尽量小（k=1,2,…,P）。四、理想点法TpfffF**2*1*,,,则称：XxtsfxfxUPmkkk　..])([)(min)4(2112*为理想点。若所有xk都相同，记为x*，则x*就是所求的多目标决策问题的最优解；若不然，则考虑求解下面的单目标决策问题：XxtsxfxfxfxFoptPp..)]}(,),(),([)({021）（先求各分量的最优值：),,2,1(;)()}({*PkxfxfoptfkkkXxk例4：设有多目标决策问题0,342..)(),(max21212121xxxxxxtsxfxfT　21221123)(4)(xxxfxxxf解：1.先求各分量的最优值，得：21,0021xx7;0*2*1ff2.构造目标函数：2122122121212*])723()4[(]))(([)(xxxxfxfxUkkk3.用理想点法化为单目标决策问题0,342..])723()4[()(min21212121221221xxxxxxtsxxxxxU　16.3步骤法(STEM法)STEM法，它是英文“StepMethod”的缩写。这个方法是一种迭代方法。它和目的规划法不同，在求解过程中的每一步，分析人和决策人之间都有对话。分析人把分析的结果告诉决策人，并征求他的意见。如果决策人认为满意，则迭代终止；如果决策人认为不够满意，则分析人根据他的意见再重复计算，去改进他的结果。由于它是逐步进行的，故称步骤法。设有多目标线性规划问题：矩阵是，　nmAxbxAtsxfxfxfxFTk0..)(,),(),()(max21其中：kixcxcxfnjjijii,,2,1)(1STEM法的求解步骤：分别求解k个单目标线性规划问题：kixbxAtsxfi,,2,10..)(max　得到的最优解记为