第五讲_多目标规划模型

1
多目标规划模型
在现实生活中,决策的目标往往有多个,例如,对企业产品的生产管 理,既希望达到高利润,又希望优质和低消耗,还希望减少对环境的污 染等.这就是一个多目标决策的问题.又如选购一个好的计算机系统, 似乎只有一个目标,但由于要从多方面去反映,要用多个不同的准则 来衡量,比如,性能要好,维护要容易,费用要省.这些准则自然构成了多 个目标,故也是一个多目标决策问题.一般来说,多目标决策问题有两 类.一类是多目标规划问题,其对象是在管理决策过程中求解使多个 目标都达到满意结果的最优方案.另一类是多目标优选问题,其对象 是在管理决策过程中根据多个目标或多个准则衡量和得出各种备选 方案的优先等级与排序.
400x1 600x 2 20000 3 x 2 x 90 2 1 9 x1 4 x 2 240 4 x1 5 x 2 200 3 x1 10x 2 300 x1 , x 2 0
由主要目标法化为单目标问题max f1 ( X ) 70x1 120x 2 用单纯形法求得其最优解为
1 p
1 1
s.t. x S p 1
p 1
则 S p x f p ( x)
f p*
S
是在分层序列意义下的最优解集合。
3. 性质： S p S pa ，即在分层序列意义下的最优解是有 效解。 ~ ~ ~ * 证明：反证。设 x S p ，但 x S pa ，则必存在 y S ~ ~ 使 F ( y ) F ( x) ~ ~ ~ ~ 即至少有一个j0 ，使 f j ( y) f j ( x), j 1,, j0 1 f j ( y) f j ( x) , ~ ~ 由于 x S j ，即 f j ( x) f j* min f j ( x) xS ， 矛盾。得证。 4. 进一步讨论： 上述方法过程中，当某个问题(Pj)的解唯一时，则 问题 Pj 1 ,, Pp 的求解无意义，因为解都是唯一的。 实际求解时，有较宽容意义下的分层序列法： 取 1 0,, p1 0 为预先给定的宽容值，整个解法同原 方法类似，只是取各约束集合时，分别取为：
在上述目标规划中，假定f1(X),f2(X),…,fp(X)具有相同的量纲, 按照一定的规则分别给fi赋予相同的权系数ωi，作线性加权和 评价函数 p
U ( X ) i f i ( X )
i 1
则多目标问题化为如下的单目标问题
maxU ( X ) i f i ( X )
i 1 p
单位产品的价格 单位产品的利润 单位产品的污染
400 70 3
600 120 2
解：问题的多目标模型如下
max f 1 ( X ) 70x1 120x 2 max f 2 ( X ) 400x1 600x 2 max( f 3 ( X )) 3 x1 2 x 2 9 x1 4 x 2 240 4 x 5 x 200 1 2 3 x1 10x 2 300 x1 , x 2 0
低 3 高
一般 5 一般
高 很高 7 9 低 很低 成本型指标
可靠性和灵敏性都属于效益型指标，其打分如下
可靠性 灵敏性 一般 5 高 7 低 3 一般 5 高 7 很高 9 很高 9 一般 5
按以下公式作无量纲的标准化处理
aij
其中：
99 ( f ij f j * *) f j * f j **
g i ( X ) 0 s.t. h j ( X ) 0
例如，某公司计划购进一批新卡车，可供选择的卡车有如 下4种类型：A1，A2，A3，A4。现考虑6个方案属性：维 修期限f1，每100升汽油所跑的里数f2，最大载重吨数f3，价 格（万元）f4，可靠性f5，灵敏性f6。这4种型号的卡车分别 关于目标属性的指标值fij如下表所示。
fij A1 A2 A3 A4
f1
2.0 2.5 2.0 2.2
f2
1500 2700 2000 1800
f3
4 3.6 4.2 4
f4
55 65 45 50
f5
一般 低 高 很高
f6
高 一般 很高 一般
首先对不同度量单位和不同数量级的指标值进行标准化处理。 先将定性指标定量化：
效益型指标
很低 1 很高
j 1 6
U ( X 4 ) j a 4 j 40.27
j 1
U * maxU U ( X 3 ) 57.925
3、分层序列法：
f ( x),, f ( x) 1.基本步骤：把(VP)中的p个目标 按其重 要程度排序。依次求单目标规划的最优解。 2. 过程：无妨设其次序为 f1, f 2 ,, f p 先求解 min f ( x) ( P ) * S1 x f1 ( x) f1* S s.t. x S 得最优值 f1 ，记 再解 min f 2 ( x) ( P2 ) * * s.t. x S1 得最优值 f 2 ，S 2 x f 2 ( x) f 2 S1 依次进行，直到 min f p ( x) f p* 得最优值 ( Pp )
如对于求极大(max)型，其各种解定义如下： 绝对最优解：若对于任意的X，都有F（X*）≥F(X) 有效解：若不存在X，使得F（X*） ≤ F(X) 弱有效解：若不存在X，使得F（X*)<F(X)
2、多目标优选问题的模型结构 可用效用函数来表示。设方案的效用是目标属性 的函数： U ( x) U ( f , f ,..., f )
s.t. g i ( X ) 0 hj (X ) 0
例如，在上述多目标问题中，假定f1(X)为主要目标，其余p-1 个为非主要目标。这时，希望主要目标达到极大值，并要求 其余的目标满足一定的条件，即 max f1 ( X )
g i ( X ) 0, i 1,2,...,n s.t.h j ( X ) 0, j 1,2,...,m f k ( X ) k , k 1,2,..., p 1
多目标决策由于考虑的目标多,有些目标之间又 彼此有矛盾,这就使多目标问题成为一个复杂而困难 的问题.但由于客观实际的需要,多目标决策问题越来 越受到重视,因而出现了许多解决此决策问题的方法. 一般来说,其基本途径是,把求解多目标问题转化为求 解单目标问题.其主要步骤是,先转化为单目标问题, 然后利用单目标模型的方法,求出单目标模型的最优 解,以此作为多目标问题的解.
x1 12.5, x2 26.25, f1 ( x) 4025 , f 2 ( x) 20750 f 3 ( x) 90 ,
2、线性加权和目标规划
optF( X ) ( f1 ( X ), f 2 ( X ),...., f p ( X ))T s.t. g i ( X ) 0 hj (X ) 0
化多目标问题为单目标问题的方法大致可分为两 类,一类是转化为一个单目标问题,另一类是转化为多 个单目标问题,关键是如何转化. 下面,我们介绍几种主要的转化方法:主要目标法、 线性加权和法、字典序法、步骤法。
§10.1多目标决策问题的特征
一、解的特点
在解决单目标问题时，我们的任务是选择一个或一组变 量X，使目标函数f(X)取得最大（或最小）。对于任意两方案 所对应的解，只要比较它们相应的目标值，就可以判断谁优 谁劣。但在多目标情况下，问题却不那么单纯了。例如，有 两个目标f1(X)，f2(X),希望它们都越大越好。下图列出在这两 个目标下共有8个解的方案。其中方案1，2，3，4称为劣解， 因为它们在两个目标值上都比方案5差，是可以淘汰的解。而 方案5，6，7，8是非劣解（或称为有效解，满意解），因为 这些解都不能轻易被淘汰掉，它们中间的一个与其余任何一 个相比，总有一个指标更优越，而另一个指标却更差。
50.5 1
100 1
设权系数向量为W=（0.2,0.1,0.1,0.1,0.2,0.3), 则
U ( X 1 ) j a1 j 34 U ( X 2 ) j a 2 j 40.6
j 1 6
故最优方案为选购A3型卡车
U ( X 3 ) j a3 j 57.925
§10.2 多目标规划问题的求解
1、主要目标法 在有些多目标决策问题中，各种目标的重要性程度 往往不一样。其中一个重要性程度最高和最为关键的 目标，称之为主要目标法。其余的目标则称为非主要 目标。 optF( X ) ( f1 ( X ), f 2 ( X ),...., f p ( X ))T
i
1
f j * max f ij
f j * * min f ij
i
变换后的指标值矩阵为： aij f1 f2 f3 f4 f5 f6
A1 A2
A3 A4
1 100
1 40.6
1 100
42.25 25.75
67 1
100 67
50.5 100
1 25.75
34 1
67 100
6 j 1 6
对于上述模型的三个目标，工厂 确定利润最大为主要目标。另两 个目标则通过预测预先给定的希 望达到的目标值转化为约束条件。 经研究，工厂认为总产值至少应 达到20000个单位，而污染控制 在90个单位以下，即
f 2 ( X ) 400x1 600x2 20000 f 3 ( X ) 3x1 2 x2 90
f2
1 2
5 3
4
6
7 8 f
二、模型结构
在多目标决策问题中，目标有多层次的含义。从最高层次 来看，目标代表了问题要达到的总目标。如确定最满意的 投资项目、选择最满意的食品。从较低层次来看，目标可 看成是体现总目标得以实现的各个具体的目标，如投资项 目的盈利要大、成本要低、风险要小；目标也可看成衡量 总目标得以实现的各个准则，如食品的味道要好，质量要 好，花费要少。 多目标决策问题中的方案即为决策变量，也称为多目 标问题的解。备选方案即决策问题的可行解。在多目标决 策中，有些问题的方案是有限的，有些问题 的方案是无限 的。方案有其特征或特性，称之为属性。