第一节 多目标规划及其求解技术简介

一、多目标规划及其非劣解

（一)多目标规划数学模型

传统的单目标规划问题，一般可用如下数学模型描述： max(min)Z=f(X) (1)

Φ（X)≤G (2)

在上式中，X=[x1，x2 ，⋯，xn]T 为规划决策变量向量；Z=f（X)是多元标量函数；Φ（X)是 m 维函数向量；G 是 m 维的常数向量，m 是约束条件个数。对于多目标规划问题，其数学模型也可以类似地描写为如下形式： max（min)Z=F（X) (3)

Φ(X)≤G (4)

在上式中，X=[x1，x2，⋯，xn]T 为规划决策变量向量；Z=F（X)是 K 维函数向量，K 是目标函数的个数；Φ（X)是 m 维函数向量；G 是 m 维常数向量，m 是约束方程的个数。

对于线性多目标规划问题，（3)—（4)式可以进一步写作： max(min)Z=AX (5)

BX≤b (6)

在（5)和（6)式，A 为 K×m 阶矩阵；B 为 m×n 阶矩阵，b 为 m 维的向量；X 为 n 维决策变量向量。

（二)多目标规划的非劣解

对于上述多目标规划问题，求解就意味着需要作出如下的复合选择：

（1)每一个目标函数取什么值，原问题可以得到最满意的解决？

（2)每一个决策变量取什么值，原问题可以得到最满意的解决？

在单目标规划问题中，各种方案的目标值之间是可以比较的，因此各种方案总是可以分出优劣的。但在多目标规划中，问题就变得比较复杂。例如， 当规划问题是要求所有的目标都取最大值时，一个目标值的增大就有可能导致另一个目标值的减小。因此，多目标规划问题的求解就不可能象在单目标规划中那样，只追求一个目标的最优（最大或最小)化，而置其它目标于不顾。

在多目标规划问题的求解中，非劣解是一个十分重要的概念，对于这一概念，我们可用图 4-1 说明。在图 4-1 中，就方案①和②来说，①的目标值f2 比②大，但其目标值 f1 比②小，因此无法确定这两个方案的优与劣。在各个方案之间，显然：③比②好，④比①好，⑦比③好，⑤比④好。而对于方案⑤、⑥、⑦，它们之间无法确定优劣，而且又没有比它们更好的其它方案， 它们就被称之为多目标规划问题的非劣解或有效解，其余方案都称为劣解。所有非劣解构成的集合称为非劣解集。

二、多目标规划求解技术简介

多目标规划问题的求解，就是要在非劣解集中寻求一个最为满意的规划方案。然而，非劣解集中往往包含有许多非劣解，究竟哪一个最为满意呢？ 为了解决这一问题，常常需要将多目标规划问题转化为单目标规划问题去处理。实现这种转化，有以下几种建模方法可供借鉴。

（一)效用最优化模型

效用最优化模型建立的依据是基于这样一种假设：规划问题的各个目标函数可以通过一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系，各目标之间通过效用函数协调，从而使多目标规划问题转化为传统的单目标规划问题：

maxZ=ψ（X) （7)

Φ（X)≤G （8)

（7)式中，ψ是与各目标函数相关的效用函数的和函数。

在用效用函数作为规划目标时，需要确定一组权值λi 来反映原问题中各目标函数在总体目标中的权重，即：

k

max ψ = ∑λ i ψ i

i =1

(9)

Фi（x1，x2，⋯，xn)≤gi（i=1，2，⋯，m) （10) 在（9)式中，诸λi 应满足：

k

∑ λi = 1

i=1

(11)

若采用向量与矩阵记号，则上述模型可以进一步改写为： maxψ=λTψ （12)

Φ（X)≤G （13)

（二)罚款模型

如果对每一个目标函数，规划决策者都能提出一个所期望的值（或称满

意值）f *，那么，就可以通过比较实际值f 与期望值f *之间的偏差来选择问

i i i

题来选择问题的解。罚款模型的数学表达式如下：

k

minZ = ∑a (f

− f * ) 2

（14）

i=1

i i i

Ф(X)≤G (17)

或写成矩阵形式：

minZ=（F-F*)TA（F-F*) （16)

Φ（X)≤G （17)

在上式中，αi 是与第 i 个目标函数相关的权重；A 是由诸αi（i=1，2，⋯， K)组成的 m×m 阶对角矩阵。

（三)目标规划模型

目标规划模型与罚款模型类似，它也需要预先确定各个目标的期望值

f *。目标规划模型为数学形式为：

k

+ −

i i

i =1

Фi(x1,x2,⋯,xn)≤gi(i=1,2,⋯,m) (19)

f + f − − f + = f * (i = 1,2, , m) (20)

i i i i

在上式中，f + 和f − 分别表示与f 相应的、与f *相比的目标超过值和不足值.

i i i i

采用矩阵形式表示，则（18)-（20)式可以进一步简记为：

minZ = vT （F+ + F-） （21）

Φ（X）≤G （22）

F + F- - F+

= F*

（23）

在(21)式中，v 表示各元素均为 1 的 K 维列向量。

（四)约束模型

约束模型的立论依据是：如果规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中。

假如，除了第一个目标外，其余目标都可以提出一个可供选的范围，则按上述思路，该多目标规划问题就可以转化为单目标规划问题：

max(minZ)=f1(x1,x2,⋯,xn) (24)

ϕ ( x , x , ,

1 2

xn ) ≤gi (i = 1,2, , m) (25)

f min≤f ≤f max （j = 2，3， ，K）

(26)

采用矩阵记号，上述模型可以进一步改写为如下形式： max（min)Z=f1（X) （27)

Ф(X)≤G (28)

Fmin≤F ≤Fmax (29)