第二章 多目标规划第二章 多目标规划
2.1 多目标规划的数学模型
2.2 多目标规划问题的解
2.3 多目标规划问题的解法
http://www.tju.edu.cn
第二章多目标规划本书大部分章节讨论的基本上都是单目标优化问题，
实际上，许多实际问题的优化牵涉的目标往往不止一个，如设计一个工厂的施工方案，就要考虑工期、成本、质量、污染等目标、再如找工作、购买家用电器追求的目标往往都不止一个。由于这类问题需同时考虑多个目标，而有些目标之间又相互矛盾，从而使决策问题变得复杂,这类决策问题称为多目标决策问题。
http://www.tju.edu.cn
第二章多目标规划多目标决策方法是现代管理科学的重要内容，也是系统分析的基本工具。按照决策变量是连续的还是离散的，
多目标决策可以分为多目标规划决策(Multiple
Objective Decision Making)和多准则决策(Multiple
Attribute Decision Making)两大类，前者是以数学规划的形式呈现的决策问题，后者则是已知各个方案及它产生的结局向量，由此选择最优方案的决策。
http://www.tju.edu.cn
第二章多目标规划多目标决策主要指多目标最优化，即多目标规划。
对于某些问题，可以先用多目标规划选出几个备选方案，然后再用多准则决策方法作进一步处理，因此，这两者既有区别又有联系。
http://www.tju.edu.cn
第二章多目标规划多目标最优化的思想萌芽于1776年经济学中的效用理论。1896年，法国经济学家V·Pareto首先在经济理论的研究中提出了多目标最优化问题。1951年，美国数理经济学家T·C·Koopans从生产和分配的活动分析中考虑了多目标决策问题，并首次提出了多目标最优化问题解的概念，将其命名为“Pareto解”(即有效解)。同年，H·W·Kuhn和 A·W·Tucker从数学规划论角度首次提出向量极值问题及有关概念。
http://www.tju.edu.cn
第二章多目标规划进入20世纪70年代，随着第一次国际多目标决策研讨会的召开及这方面专著的问世，多目标决策问题的研究工作迅速、蓬勃地开展起来，到目前为止，已取得若干有价值的研究成果。
http://www.tju.edu.cn
第二章多目标规划
2.1 多目标规划模型线性规划及非线性规划研究的都是在给定的约束集合
R={X|gi(X) ≥0,i=1,2,……，m)} X ∈ En上，求单目标
f(x)的最大或最小的问题，即方案的好坏是以一个目标去衡量。
http://www.tju.edu.cn
第二章多目标规划然而，在很多实际问题中，衡量一个方案的好坏往往难以用一个指标来判断 。也就是说，需要用一个以上的目标去判断方案的好坏，而这些目标之间又往往不是那么协调，甚至是相互矛盾的。本章将以实例归结出几类常见的描述多目标最优化问题的数学模型。
http://www.tju.edu.cn
第二章多目标规划一、一般多目标规划模型：
例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别为4
元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5
斤。问如何确定最佳的采购方案。
12
12
1
12
42 40
10
5
0,0
xx
xx
x
xx
+ ≤
+≥
≥
≥≥
我们先确定此问题应满足的条件（即约束条件）。不难看出，当甲级糖数量为x
1
，乙级糖数量为x
2
时，有：
http://www.tju.edu.cn
第二章多目标规划在研究以什么为“最佳”的衡量标准时，“筹备小组”的成员们意见可能会发生分歧，其原因是他们会提出各种各样的目标来。
如果要求总花费最小，即要求：
f
1
(x
1
,x
2
)=4x
1
+2x
2
→min
如果要求糖的总数量最大，即要求：
如果要求甲级糖的数量最大，即要求：
易见，这是具有3个目标的规划问题（由于约束及目标均为线性函数，故它为多目标线性规划问题）。
212 1 2
(,) maxfxx x x= +→
312 1
(,) maxfxx x= →
http://www.tju.edu.cn
第二章多目标规划例2：【投资决策问题】某投资开发公司拥有总资金A万元，
今有n(≥2)个项目可供选择。设投资第i(i=1，……，n)
个项目要用资金a
i
万元，预计可得到收益b
i
万元。问应如何使用总资金A万元，才能得到最佳的经济效益？
n
ii
i=1
ii i
1 i
i=1 2 n
0 i
ax A
x (x 1) 0 i=1 2 n x =0 1
i
x
=
≤
=
∑
决定投资第 个项目设,，……，
决定不投资第 个项目问题的约束条件为
，，……,或
http://www.tju.edu.cn
第二章多目标规划所谓“最佳的经济效益”，如果理解为“少花钱多办事”
则变为两个目标的问题，即投资最少，收益最大：
这是具有两个目标的0－1规划问题。
11
1
21
1
()max
()min
n
nii
i
n
nii
i
fx x bx
fx x ax
=
=
=→
=→
∑
∑
，……，
，……，
http://www.tju.edu.cn
第二章多目标规划例3：【木梁设计问题】把横截面为圆形的树干加工成矩形横截面的木梁。为使木梁满足一定的规格和应力及强度条件，要求木梁的高度不超过H，横截面的惯性矩不少于给定值W，且横截面的高度要介于其宽度和4倍宽度之间。
问应如何确定木梁尺寸，可使木梁的重量最轻，并且成本最低。
设所设计的木梁横截面的高为x
1
，宽为x
2
（图1）。
为使具有一定长度的木梁重量最轻，应要求其横截面面积x
1
x
2
为最小，即要求x
1
x
2
→min
x
1
x
2
r
图1
http://www.tju.edu.cn
第二章多目标规划由于矩形横截面的木梁是由横截面为圆形的树干加工而成的，故其成本与树干横截面面积成正比。由此，为使木梁的成本最低还应要求尽可能的小，或即：
根据问题的要求，应满足下述约束条件：
这是具有两个目标的非线性规划问题。
222
12
(/2) (/2)rx xππ
=+
22
12
()/4xxπ +
22
12
()minxx+→
1
12
12
21
12
0
40
0,0
xH
xx W
xx
xx
xx
≤
≥
≥
≥
≥≥
http://www.tju.edu.cn
第二章多目标规划由以上实例可见，多目标最优化模型与单目标最优化模型的区别主要是目标多于一个。在这些目标中，有的是追求极大化，有的是追求极小化，而极大化与极小化是可以相互转化的。因此，我们不难将多目标最优化模型统一成一般形式：
决策变量：x
1
，……，x
n
标函数：minf
1
(x
1
，……，x
n
)
………………
minf
p
(x
1
，……，x
n
)
11
1
()0
()0
n
mn
gx x
gx x
≥
≥
，……，
约束条件,………………
，……，
http://www.tju.edu.cn
第二章多目标规划若记X= (x
1
，……，x
n
)，且用V-min表示对向量
F(X)=[f
1
(X)，……，f
p
(X)]
T
中的各目标函数f
1
(X)，……，
f
p
(X)同等的进行极小化。R={X|g
i
(X)≥0，i=1，……，m}表示约束集。则模型一般式也可简记为：
这里(VMP)为向量数学规划(Vector Mathematical
Programming)的简写。
1
min[() ()]
()
( ) 0 i=1
min ( )
()
p
i
VfX fX
VMP
gX
VFX
VMP
XR
≥
∈
，……，
，……，m
或
http://www.tju.edu.cn
第二章多目标规划二、分层多目标规划模型本节介绍一类不同于(VMP)形式的多目标最优化模型。这类模型的特点是：在约束条件下，各个目标函数不是同等的被优化，而是按不同的优先层次先后的进行优化。
例如，在第一节例1中，若筹备小组希望把所考虑的三个目标按重要性分成以下两个优先层。
第1优先层——总的花费最小。
第2优先层——糖的总数量最大。
甲级糖数量最大。
http://www.tju.edu.cn
第二章多目标规划那么这种先在第1优先层次极小化总花费，然后在此基础上再在第2优先层次同等的极大化糖的总数量和甲级糖的问题，就是所谓分层多目标最优化问题。可将其目标函数表示为：
L-min{P
1
[f
1
(X)]，P
2
[f
2
(X)，f
3
(X)]}
其中P
1
，P
2
是优先层次的记号，L-min表示按优先层次序进行极小化。
下面，我们来看一个建立分层多目标最优化模型的例子
http://www.tju.edu.cn
第二章多目标规划例4：某水稻区一农民承包10亩农田从事农业种植。已知有三类复种方式可供选择，其相应的经济效益如下表：
方案复种方式 粮食产量
(公斤/ 亩)
油料产量
(公斤/ 亩)
利润
(元/ 亩 )
投入氮素
(公斤/ 亩)
用工量
(小时/ 亩)
1
大麦－早稻－晚梗
1056 —— 120.27 50 320
2
大麦－早稻－玉米
1008 —— 111.46 48 350
3
油菜－玉米－蔬菜
336 130 208.27 40 390
http://www.tju.edu.cn
第二章多目标规划设该农户全年至多可以出工3410小时，至少需要油料156公斤。今该农户希望优先考虑总利润最大和粮食总产量最高，然后考虑使投入氮素最少。问如何确定种植方案。
首先设立决策变量如下：
方案1的种植亩数：x
1
，
方案2的种植亩数：x
2
，
方案3的种植亩数：x
3
，
根据农户的要求确定问题的三个目标函数为：
http://www.tju.edu.cn
第二章多目标规划年总利润：f
1
(x
1
，x
2
，x
3
)=120.27x
1
+111.46x
2
+208.27x
3
粮食总产量：f
2
(x
1
，x
2
，x
3
)=1056x
1
+1008x
2
+336x
3
投入氮素量：f
3
(x
1
，x
2
，x
3
)=50x
1
+48x
2
+40x
3
根据农户的全年出工能力，对油料需求量，所承包农田数以及种植亩数应为非负等限制，应有约束条件：
总用工量：320x
1
+350x
2
+390x
3
≤3410
油料需求,130x
3
≥156
农田数,x
1
+x
2
+x
3
＝10
种植亩数非负：x
1
≥0,x
2
≥0,x
3
≥0。
http://www.tju.edu.cn
第二章多目标规划根据农户对目标重要性的排序，将前两个目标作为第一优先层，将第三个目标作为第二优先层，再把其中的求最大化转化为求其负数的最小，便得到下列具有两个优先层次的分层多目标极小化模型：
对它进行求解便可得到农户满意的种植方案。
1123
123
21 2 3
123
3
123
123
min[ ( 120.27 111.46 208.27
1056 1008 336 )
(50 48 40 )]
320 350 390 3410
130 156
.
10
000
L Pxx x
xxx
Px x x
xxx
x
st
xxx
xxx
++
++≤
≥
++=
≥≥≥
，
,
，，
http://www.tju.edu.cn
第二章多目标规划三、多目标规划模型：
本节介绍一类在实际中有着广泛应用的特殊多目标最优化模型。这类模型并不是去考虑对各个目标进行极小化或极大化，而是希望在约束条件的限制下，每一目标都尽可能的接近于事先给定的各目标值。
设p个目标函数的给定目标值分别为：
00
1
0
1
( ) (1)
p
p
ii
i
ff
fX f
∈
=
∑
XR
，……，
则为使各目标函数尽量接近其目标值，可建立以追求总绝对偏差极小化为目标的目标规划模型：
min
http://www.tju.edu.cn
第二章多目标规划
0
00
0
0
0
00
()
( ) ( )
0 ( ) 1
()
0 ( )
( ) ( )
ii
ii i i
i
ii
ii
ii
i
ii i i
fX f
fX f fX f
d
fX f i p
fX f
fX f
d
ffX fXf
+
>
=
≤=
≥
=
<
若记 关于 的正偏差为
-，,
，,……，
关于 的负偏差为
，，
0
0
1
( )
( )
0 1
ii i i
iii i
ii
ip
dd fXf
ddfXf
dd i p
+
+
+
=
+
= =
－
－
－
，,……，
则不难看出
＝-，
＝-，
，，…，
http://www.tju.edu.cn
第二章多目标规划
1
0
min ( )
()
,
0
0 0 1 (2)
(2)
p
ii
i
iiii
ii
ii
dd
XR
fX d d f
st
dd
dd i p
+
=
+
+
+
+
∈
+=
=
≥≥=
∑
－
－
－
－
于是目标规划模型(1－1)也可以表示为
，，…，
虽然去掉了绝对值运算，但却含有偏差变量相乘的约束条件，这仍然使求解很不方便。考察去掉偏差变量相乘的约束条件，得到模型：
(1)
http://www.tju.edu.cn
第二章多目标规划
1
0
min ( )
,( )
0 0 1 ( )
)()
))
()
p
ii
i
iiii
ii
dd
XR
st f X d d f
dd i p
+
=
+
+
+
∈
+=
≥≥=
∑
nullnullnull
nullnull
－
－
－
+-
++ +-- -
1p1p
，，…，3
可以证明，若(X，d,d 是 3 的最优解，其中d ＝(d,……，d,d ＝(d,……，d,则X是
(2)的最优解。因而可将 3 作为目标规划模型的一般形式。在此一般形式基础上，还可以建立加权的或分层的目标规划模型。
http://www.tju.edu.cn
第二章多目标规划例5：某机器制造厂生产两种型号的机器，同时也进行机器的零部件和工业性作业生产。已知有关数据如下表，
并且该工厂全年能承担生产的总工时为58万小时。
生产项目 单位 产值 利润 工时 需要量
1号机 套
5
万元/ 套
1
万元/ 套
1000
小时/ 套
160套
(指令性计划 )
2号机 台
1.6
万元/ 套
0.2
万元/ 台
400
小时/ 台
320～ 500台
(市场预测)
零部件和工业性作业万小时
50
元/ 小时
8.1
元/ 小时
26万小时
(市场预测)
http://www.tju.edu.cn
第二章多目标规划今决策者希望在完成上级下达的指令性计划的前提下，全年总产值达到2750万元左右，总利润不低于440万元，并且要避免开工不足。然后，还希望工人的加班时间不超过总工时的4％，以及依据市场预测的信息进行生产。试问应如何安排工厂的年生产计划。
首先，设立决策变量为：
x
1
：生产1号机套数
x
2
：生产2号机台数
x
3
：生产零部件和工业性作业的工时数(万小时)
http://www.tju.edu.cn
第二章多目标规划
1
2
3
4
5
( ) 160
( ) 2750
( ) 440
400
() 58
10000
() 4
400
10000
fX
fX
fX
fX
fX
→=
→=
→=
++→
++→
0
11
0
1232
0
1233
0
1234
1235
目标函数及其目标值：
：1号机产量x f
：年总产值5x +1.6x +50x f
：总利润x +0.2x +8.1x f
1000
：总工时 x x x f＝
10000
：加班时间不超过总工时的 ％的要求：
1000
xxxf
10000
6
58 (1 4 )
()
2 320 500
26
fX
×+
≤≤
→
0
2
0
36
＝％
：按市场预测信息进行生产的要求：
号机产量,x
工业性作业和零部件的工时：x f＝
http://www.tju.edu.cn
第二章多目标规划
111 22234 356788
11 1
12322
12333
12344
1
min[ ( ) ( ) ( )]
160
5 1.6 50 2750
0.2 8.1 440
0.1 0.04 58
0.1 0.04
..
L Pdd Pdddd Pddddd
xd d
xxxdd
xxxdd
xxxdd
xx
st
+? + +?++?
+?
+?
+?
+?
+ +++ ++++
+=
++?+=
++?+=
++?+=
+
根据决策者对目标重要性的优先次序 可得该问题的分层目标规划模型
，，
235 5
26 6
27 7
38 8
12 3
58 (1 4%)
320
500
26
0
0 i=1 2 8
ii
xd d
xdd
xdd
xd d
xx x
dd
+?
+?
+?
+?
+?
+?+ =×+
+=
+=
+=
≥
≥
,为非负整数，
、，,…
由上例可见，利用偏差变量建立目标 规划模型，常常可不必严格区分问题中的目标与约束，而将一些约束条件考虑作为目标。
http://www.tju.edu.cn
第二章多目标规划
2.2 多目标规划问题的解：
在单目标规划问题中，任意两个可行方案都可通过比较其目标函数值来确定其优劣。在所有可行方案中，使目标达最优的就是最优解。
而在多目标规划问题中，约束集R中的两个方案x
1
，x
2
其优劣往往不能进行比较。这是因为它们的目标值F(X
1
)与
F(X
2
)是向量，而向量是无法直接比较大小的。所以，在R
中也往往不存在一个方案对每个目标都是最优的。
这种多目标规划问题区别于单目标规划问题的本质表明，仅仅将单目标问题最优解的概念平移到多目标问题中是不行的。本章将介绍多目标规划问题各种解的概念及其相互关系。
http://www.tju.edu.cn
第二章多目标规划一,各种解的概念：
11 1
1
22 2
1
12 1
2 12
12 1
2
( )
( )
(1) " "
1
(2)" "
1
pp
pp
ii
Ff fE
Ff fE
FF F
Fipf
FF F
Fi
=∈
<<
=<
<<
=
先 引 进 一 些 记 号,记
，……，
，……，
,意 味 着 向 量 的 每 个 分 量 都 要 严 格 的 小 于 向量 对 应的分量。即对于,……，,均有 。
,意 味 着 向 量 的 每 个 分 量 都 要 小 于 或 等 于 向量 对 应的分量。即对于,
00
12
12 1
21 2
12
12
12 12 12
(3)" "
1
""""""
ii
ii
ii
pff
FF F
F FF
ipff
ff
FF FF FF
≤
≤≤
=≤
≤≤ <
≤<≠
00
……，,均有 。
,意 味 着 向 量 的 每 个 分 量 都 要 小 于 或 等 于 向量 对 应的分量，并且存在 的 某一个分量要严格的小于向量对应的分量。即对于,……，,均有,并且要至少存在某个i (1 i p),有 。
可 见,等 价 于 且 。
http://www.tju.edu.cn
第二章多目标规划图2给出了两个目标，一维变量时绝对最优解的例子
X
f
0
1
()f x
2
()f x
x
2图
*
1 ( ) ( )
() ()
ab
XR XR FX FX
XVMP VMP
R
∈∈≥定义 设,若对于任意 均有,
则称 为问题 的绝对最优解。 的绝对最优解全体记为,称其为绝对最优解集合。
X
12
图中的 即是f(x)的极小点，又是f(x)的极小点，也就是使所有目标都达最优，因而是该问题的绝对最优解。但在大多数多目标规划问题中，这样的绝对最优解往往是不存在的。
http://www.tju.edu.cn
第二章多目标规划
2
(1 )
RR
p
pp
∈∈≤
≤
≤≤
00
0110
10
ii 0
10 0 1
0ii
0
为引出以下的定义,我们先考查什么叫做劣解。设
X,若存在另一个可行解X,有F(X ) F(X )，即对于i=1，……，p，均有f(X ) f(X )，并且至少存在某个i
i 有f (X )<f (X )，显然可行解X 相对于X 来说是劣的。这是因为方案X的 个目标值都不比X 对应的 个目标值坏，
且至少比有一个要好。我们称X 为劣解。于是有如下非劣解的 R∈定义，从字面上可知：X 如果不是劣解就称其为非劣解。
*
2()(
() ()
()
pa
RXRFXF
VMP VMP
RVMP
∈∈≤ 定义 设X,若不存在,有 X,
则称X为问题 的非劣解（也称有效解）。 的有效解全体记为,称其为 的有效解集合。
http://www.tju.edu.cn
第二章多目标规划图3 给出了两个目标，一维变量时有效解集合的例子
f
0
1
()fx
2
()f x
x
3图
*
1
x
*
2
x
*
pa
R
**
12
,()()
" "
""
xx X
XFXFX≤
≤
<
图中 与 之间的点 均为有效解，因为找不到另一个可行解 满足 。
在定义2中我们用 定义了有效解，当我们使用符号 时，则可以定义弱有效解。
http://www.tju.edu.cn
第二章多目标规划图4给出了弱有效解集合的例子。
*
wp
R
f
0
1
()f x
2
()f x
x
4图
*
3 ( ) ( )
() ()
()
wp
X RXRFXFX
XVMP VMP
RV
∈∈<定义 设,若不存在,使,
则称 为问题 的弱有效解。 的弱有效解全体记为,称其为 的弱有效解集合。
*
() ()
wp
Rx
xR Fx Fx∈<
不难看出,中的任一点 都为弱有效解。因为找不到另一个,满足 。
http://www.tju.edu.cn
第二章多目标规划二,各种解之间的关系:
1
*
** * * *
1
**
1
() ()
min ( )
()
1
p
i
i
i
ab pa wp p
p
ab i
i
p
fx fx R
fX
P
XR
Ri p
RR R R R R
RR
=
∈
=……
∩
为了较完整的讨论各种解集之间的关系，将 个 目标
，……,分 别与约束集 组成的单目标问题（即线性或非线性规划）
的最优解集记为,,,。
集合,,,,,……,之间的关系由以下一些定理给出。定理1是显然的。
定理1 ＝ 。
http://www.tju.edu.cn
第二章多目标规划
**
*
**
2
( ) ( )
1
() ( )
(
pa wp
wp pa wp
pa wp
ii
RRR
RR RR
XR XR YR
FY FX
ip
fY fX
Y
FY
∈? ∈
<
=……
<
定理证,是显然的，只需证 。用反证法证之。
设,但 。根据弱有效解定义，必存在,使
，
即对于,,,均有
因此 满足
**
**
)()
pa wp
pa wp
FX
XXR XR
RR
≤
∈
由此推得 为劣解，即,矛盾。从而证明,即
。证毕。
http://www.tju.edu.cn
第二章多目标规划
0
00
0
**
0
***
3 1
() ( ) 1
( ) ( )
( ) ( )
iwp
p
ii
ii
iiwp
RRi p
XR XR YR
FY FX i p
fY fX
ii
fY fX
XR R R
=…
∈?∈
<=…
<
=
<
∈?
定理,,,
证：设,但,于是存在,
有 。即对于,,,均有特别的，对 有这与 矛盾，故,证毕。
http://www.tju.edu.cn
第二章多目标规划
0
**
**
00
4
() ( ) 1
( ) ( )
(1 )
(
ab pa
ab ab
ab pa
ii
i
RR
XR XR YR
FY FX i p
fY fX
iip
fY
=?≠?
∈? ∈
≤=
≤
≤≤
定理证：若,结论显然成立。故不妨设 。
设,但 。由有效解定义，必存在某,
使,即对,……，,均有并且至少存在,有
0
0 0
****
1
**
)()
i
p
iabii
i
ab pa
fX
XR XR RXR
RR
=
<
∈ ∈
∩
说明,但由 知,矛盾。故必有 。证毕。
http://www.tju.edu.cn
第二章多目标规划
{ } { }
**
1122
**
12
[ ]
pa wp
R xRx
R Rxx
==
==
例6 见图5，此时，,
，
2
x
1
x
1
()f x
2
()f x
x
f
0
5图
http://www.tju.edu.cn
第二章多目标规划
*
pa
R
*
wp
R
*
1
R
0
1
()f x
2
()f x
x
6图
*
2
R
f
*** *
12
wp pa
RRR R例7 见图6，,,,如图所示。
http://www.tju.edu.cn
第二章多目标规划
**
ab pa
RR=
*
wp
R
*
1
R
f
0
1
()f x
2
()f x
x
7图
*
2
R
*
***** **
12 12
ab
pa ab wp
R
RRRRR RR
≠?
==∩∪
例8 见图7，
在这个例子中，,并且
＝,
http://www.tju.edu.cn
第二章多目标规划
*
***
1
**
1
5
(1)
(2)
ab
p
pa i ab
i
p
wp i
i
R
R RR
RR
=
=
≠?
==
=
∩
∪
事实上，
可以证明如下定理：
定理 设,
则；
。
http://www.tju.edu.cn
第二章多目标规划
*
p a
R
*
wp
R
R
*
1
R
*
2
R
*
3
R
*
3
ab
pR= =?，
8图本节讨论的解集之间的关系可以由图8，9给出。
http://www.tju.edu.cn
第二章多目标规划
*
1
R
*
2
R
*
3
R
*
3
ab
pR= ≠?，
**
ab pa
R=R
9图
http://www.tju.edu.cn
第二章多目标规划三、多目标决策与单目标决策区别:
点评价与向量评价:
单目标,方案 d
j
←评价值 f(d
j
)
多目标：方案 d
j
←评价向量( f
1
(d
j
),f
2
(d
j
)…,f
p
(d
j
))
全序与半序,方案 d
i
与 d
j
之间单目标问题,d
i
<d
j; d
i
=d
j; d
i
>d
j
多目标问题：除了这三种情况之外,还有一种情况是不可比较大小决策者偏好：多目标决策过程中，反映决策者对目标的偏好。
解概念区别:
http://www.tju.edu.cn
第二章多目标规划四、解的概念:
单目标决策的解只有一种（绝对）最优解多目标决策的解有下面四种情况：
绝对最优解劣解有效解(Pareto解)
弱有效解
http://www.tju.edu.cn
第二章多目标规划
d
1
80 75 88
有效解
d
2
75 81 85
有效解
d
3
76 78 89
有效解劣解
d
5
79 74 86
d
4
85 82 92 绝对最优解数学 外语 专业 解的类型五、多目标决策解的例子:
http://www.tju.edu.cn
第二章多目标规划
2.3 多目标最优化问题的解法:
求解多目标最优化模型，就是要根据问题的特点和决策者的意图，选择适当解法，求得模型的有效解或弱有效解。本章将介绍一些常用的多目标最优化问题解法。
http://www.tju.edu.cn
第二章多目标规划
()( 1 )
()
( )
min ( )
i
i
i
ii
XR
p
f Xi p
fX
fX
f
ffX
∈
=……
=
在实际问题中,个目标的量纲往往都是不同的，
所以事先需把每个目标规范化，然后再进行数学上的处理。比如，可以把带量纲的目标,,
进行如下处理，令其中 ＝
以后我们总假定所讨论的多目标最优化模型已经过了规范化处理。
http://www.tju.edu.cn
第二章多目标规划一、评价函数法:
1
( ) ( )
()
( ) min [ ( )]
() ()
()
p
XR
hF hf f
VMP
PhFX
hF P X
VMP
∈
=
评价函数法就是利用一个复合函数:
，……，
把多目标问题 转化为单目标问题:
然后来求解，而单目标问题的解法我们是熟知的。问题是，用评价函数 得到的 的最优解 是否为原问题的有效解或弱有效解？因为若连弱有效解都不是，
那显然是不足取的。
http://www.tju.edu.cn
第二章多目标规划
**
121 2
12
( )
()
( ) ( )
()
()
pa wp
p
pp
p
hF
XR XR
hF E
FFFEFE
hF hF
hF
hF E
∈∈
≤∈∈
<
下面我们将指出，当评价函数 具有某种“单调性时”，是可以保证 （或 ）的。为此，先给出两个定义：
定义4 设 是定义在 上的函数，若对于任意满足 的,,均有：
则称 为严格单调函数。
定义5 设 是定义在 上的函数，若对于任
121 2
12
( ) ( )
()
pp
FFFEFE
hF hF
hF
<∈∈
<
意满足 的,,均有：
则称 为单调函数。
http://www.tju.edu.cn
第二章多目标规划
*
*
( )
( ) min [ ( )]
() ( )
()
[ ( )] < [ ( )]
()
p
XR
pa
pa
hF E X
phFX
XR
X RYRFYFX
hF
hFY hF X
Xp
∈
∈
∈≤
定理6 若 为定义在 上的严格单调函数，为规划问题的最优解，则 。
证：用反证法。若,则存在,有,
由 的严格单调性，有这与 为问题 的最优
*
*
( )
( ) min [ ( )]
pa
p
XR
wp
XR
hF E X
phFX
XR
∈
∈
∈
解矛盾，故 。
定理7 若 为定义在 上的单调函数，为规划问题的最优解，则 。
证明方法与定理6雷同。
http://www.tju.edu.cn
第二章多目标规划
1
1
1
1
1
()
01 1
ipp
p
p
p
ii
i
hF f f
ip
λλ
λλ
λ λ
λλ
=
=+…+
≥= =
∑
下面 介绍两种常用的评价函数方法。
,线 性加权和法
该方 法就是取评价函数为各目标函数的线性加权和，
即
其中,……,为相应目标的权系数。
线性 加权和法的步骤如下：
(1)依目标的重要程度给出一组权系数,……，,
其中,,……，,。
http://www.tju.edu.cn
第二章多目标规划
1
*
*
*
(2) ( )
() min ()
()
(3) ( )
01
01 ()
0
p
ii
XR
i
wp
i
pa
i
pa i
VMP
PfX
PX
XVMP XR
ip
XR
iphF
XR
λ
λ
λ
λ
λ
λ
∈
=
∈
>=…
∈
>=…
∈≥
∑
将 转化为单目标问题
求解 得最优解 。
可以证明，是 的弱有效解，即 。进一步，若所有权系数均为正，即,,,,则
。
事实上，当,,,时,为严格单调函数，故 ；而当,
*
1()
wp
iphF
XR
=……
∈
，，时，
为单调函数，故 。
http://www.tju.edu.cn
第二章多目标规划
3
12
22
12 1 2
1
1
3
12.5
0.3 0.7
3
min 0.3 0.7( )
2.5 0
,,
WH
xx x x
x
x
st
λλ
==
==
++
≥
用线性加权和法求解例 的木梁设计问题。
设其中的 尺,尺，又设决策者认为成本与重量两个目标的权系数各为 和 。
解,根据例 的木梁设计问题模型，可建立线性加权和模型。
例9
2
12
21
12
10
0
40
0
x
xx
xx
xx
≥
≥
≥
≥
、
http://www.tju.edu.cn
第二章多目标规划
12
1
2
( ) (1.1511 0.7547)
37
( ) 1.1511( )
( ) 0.7547(
TT
Xxx
X
x
x
==
这是一个单目标非线性规划问题，用非线性约束最优化方法可求得其最优解
,,
由于权系数均大于零，故 是原多目标问题有效解。
以上结果表明，在决策者认为重量目标与成本目标的重要性之比为,的意义下，木梁设计的满意尺寸应是
高＝ 尺
宽＝ 尺 )
http://www.tju.edu.cn
第二章多目标规划
**
1
** * * *
1
** *
*
2
()
()
()
p
T
p
ab
ff
pFf f F XR
X RX
FR
hF F F
=∈
∈
、理想点法：
理想点 一般是指由各单目标最优值,……,组成的 维点,……,。若 相应的自变量,
即,那么当然很理想。但我们已经知道，这样的往往是不存在的（见图10）。于是自然想到找一个中离它最近的点，即可取评价函数 为 与 的距离，
具体构造如下：
10图
1
f
***
12
()
T
F ff=,
()F R
2
f
0
http://www.tju.edu.cn
第二章多目标规划
*2
1
(1)
( ) ( )
( ) min [ ( )]
01 1()
() 01
()
(2)
p
ii i
i
XR
ii
i
hF f f
phFX
ip pX
VMP i p
XVMP
λ
λλ
λ
=
∈
=?
≥= =
>=
∑
∑
平方和加权法：
取,再求解单目标问题其中,,……，,。则 的最优解是原问题 的弱有效解。若,,……，,
则 是 的有效解。
最小偏差法取
*
1
()
( ) min [ ( )]
p
ii
i
XR
hF f f
phFX
=
∈
=?
∑
，构成单目标问题
http://www.tju.edu.cn
第二章多目标规划
1
*
*
1
( ') min( ) ( )
() 1
,,
(') ( )
(
p
ii ii
i
iiii
pdddd
f Xdd fi p
st
XR
pXVMP
Ff
+? +?
=
+?
=+
+= =
∈
=
∑
*
为避免绝对值运算，一般将其转化为与之等价的偏差变量模型：
，
，,……，
可以证明,的最优解 是其相应 的有效解。
以,……
*
00
1
)
()(')
p
p
f
p
Ff f p=
0
,作理想点，需要事先求解个单目标规划，实际中有时也可凭经验给出一组目标值,……，,这时 即为目标规划模型。
http://www.tju.edu.cn
第二章多目标规划
1
( 1 )
(1 )
1
jij
k
j
ij
i
kiik
fj p
ki
λ
λλ
=
=
=
=
∑
最后介绍两种确定权系数的方法。
(1)老手法:
邀请一批“老手”（如专家、学者、有实践经验的技工、干部等），请他们对如何取权系数发表意见。
设邀请了 位老手，设第,……,位老手认为目标,……,的权系数为,计算各目标的权系数均值。
1jp=,……，
http://www.tju.edu.cn
第二章多目标规划
λ
kp
……
λ
k2
λ
k1
k
…………………………
λ
2p
……
λ
22
λ
21
2
λ
1p
……
λ
12
λ
11
1
……
f
p
(X)……f
2
(X)f
1
(X)
目标权系数老手
1
ij
j
ij ij
jp
λ
λλΔ=? =
然后计算 与均值的偏差
，……，
请那些有最大偏差的“老手”发表意见，充分讨论后再重复上述步骤。
1
λ
2
λ
p
λ
http://www.tju.edu.cn
第二章多目标规划
1
1
*
(2)
min ( )
1()
1
1
0 1
j
XR
iii
jj
p
i
jj
j
p
j
j
j
ab
p
fX
Xi p f fX
fi p
jp
R
α
λα
λ
λ
∈
=
=
==
==
=
≥=
=?
∑
∑
方法先求 个单目标问题的最优解,,……,。记,构造方程组
，……，
，……，
当时，此
1
1
()
p
p
λλα
λλ
方程组有唯一解,……，,,由此即得权系数,……,。
确定权系数，还可采用层次分析法，见第四章。
http://www.tju.edu.cn
第二章多目标规划二、分层求解法本节将针对第一节中介绍的分层多目标最优化模型，介绍一般的分层评价法和适用于线性分层模型的分层单纯形法。
1、分层评价法:
设将目标分为L个优先层，则可首先在约束集R上对第一优先层进行多目标极小化，然后在第一层优化所得的（弱）有效解集上对第二层进行优化，然后在第二层优化所得的（弱）有效解集上对第三层进行优化……
可以证明，按分层评价法进行求解时，只要每一层选用的评价函数都是严格增的，则最后所得的解必为相应的不分层多目标最小化模型的有效解。
http://www.tju.edu.cn
第二章多目标规划
1123
123
21 2 3
123
min[ ( 120.27 111.46 208.27
1056 1008 336 ),
(50 48 40 )]
320 350 390 3410
,
L Pxx x
xxx
Px x x
xxx
st
++
++≤
用分层评价法求解例4中的农田种植问例10：
题：
，
3
123
123
130 156
10
000
x
R
xxx
xxx
≥
++=
≥≥≥
，，
http://www.tju.edu.cn
第二章多目标规划
1
1123
(120.27 111.46 208.27) /100
4.4 (1056 1008 336) /100 24
11 1
( ) -27 - 25 - 47
33 3
fX x x x
++
++
=
解：问题的第一优先层含有利润和粮食产量两个目标，今选用线性加权法对它求解。首先对两个目标作统一量纲处理。以 ＝
除利润目标函数，以 ＝ 除粮食产量目标函数，则可得
1
2123
11
12
111
12123
( ) -44 - 42 -14
0.6
0.4
[ ()]0.6 ()0.4 ()-34-32 -34
fX x x x
ff
hF X f X f X x x x
=
=+=
设该农户认为两个目标 和 的权系数分别为和,则有线性加权和评价函数
http://www.tju.edu.cn
第二章多目标规划
1
1
33 3
11
1
123
312
min [ ( )]
(10 0 ) 1.2 3
[()] 340
{ | 34 32 34 340}
'
()50 48
XR
T
hF X
Xxx x
hF X
RXR x x x
R
fX x x
∈
=?≤≤
=?
=∈ ≤?
=++
求解线性规划
可得最优解,，,其中,
和最优值 。
由第一优先层的最优值构造第二优先层的可行域
再在 上极小化第二优先层的目标（氮素量）
3
22
40
(7 0 3)
T
x
XX=可得最优解,,。 即为问题的有效解。
http://www.tju.edu.cn
第二章多目标规划上述结果表明：若该农户认为利润和粮食目标在问题中的重要程度分别为0.6和0.4的话，则他应该选择如下的种植方案：
方案1：种植7亩方案2：不种植方案3：种植3亩这时，还可算出:
年总利润＝1466.66元粮食总产量＝8400公斤氮素投入量＝470公斤油料产量＝390公斤总用工量＝3410小时
http://www.tju.edu.cn
第二章多目标规划
2、分层单纯形法：
将普通单纯形法加以适当推广，便可用来求解分层多目标线性规划模型。其一般步骤如下：
(1)将每一优先层中各目标函数通过评价函数法（如线性加权和）转化为单目标；
(2)用单纯形法求解各层目标相应的线性规划问题。
设共有L个优先层，则在每张单纯形表上的检验数位置有L
行检验数(C
j
-C
B
B
-1
p
j
)，将P
1
层对应的检验数写在最下行，
P
L
层对应的检验数写在最上行。
http://www.tju.edu.cn
第二章多目标规划
(3)检验调整时由下往上，先调P
1
行（迭代方法同单纯形法），直至P
1
行检验数满足最优性要求
（检验数≥0），再开始调P
2
行。若某行负检验数相应下行中有正检验数，则根据“高级优先”的原则，放弃调整该列。这样进行直至无法再调时（全部检验数为非负或虽有某为负，但其下方有正的）
为止。
http://www.tju.edu.cn
第二章多目标规划
11 2 21 2
31 2 3
12
2
123
123
min[ ( 3 ) ( 2 )
(2 )]
5
2
,,
4
000
LPxxPxx
Px x x
xx
x
st
xxx
xxx
++
+≤
≤
+ ≤
≥≥≥
用分层单纯形法求解下面的分层线性规划问题
，，
例11
，
:
，
http://www.tju.edu.cn
第二章多目标规划
456
11 2 21 2
31 2 3
124
25
1236
16
min[ ( 3 ) ( 2 )
(2 )]
5
2
,,
4
0
xxx
LPxxPxx
Px x x
xxx
xx
st
xxxx
++
++
+
++
≥
解：引入松弛变量，,,,将问题转化为标准形式
,,
＝
＝
＝
，……，
http://www.tju.edu.cn
第二章多目标规划
0
0
0
0
0
0
0
0
0
1
-2
0
2
0
-3
1
-1
-1
P
3
P
2
P
1
0
0
1
0
1
0
1
0
0
0
0
1
1
[1]
-1
1
0
-1
x
4
5
x
5
2
x
6
4
x
6
x
5
x
4
x
3
x
2
x
1
X
B
B
-1
b
12
5
3
1
Px
x
调整时先看 行，令检验数 对应的 进基，
根据单纯形法原理，确定出基变量为,以其交叉元 为枢轴元进行单纯形迭代。得下一张单纯形表建立初始单纯形表:
http://www.tju.edu.cn
第二章多目标规划
0
0
0
0
0
3
0
0
0
1
-2
0
0
0
0
1
-1
-1
P
3
P
2
P
1
0
0
1
-1
1
1
1
0
0
0
0
1
0
1
0
[1]
0
-1
x
4
3
x
2
2
x
6
6
x
6
x
5
x
4
x
3
x
2
x
1
X
B
B
-1
b
114
1 1
1
P xx行仍有负检验数,再令 对应的 进基，
出基，以其交叉元 为枢轴元进行单纯形迭代。得到下一张单纯形表
http://www.tju.edu.cn
第二章多目标规划
0
0
0
1
-1
2
-1
1
1
1
-2
0
0
0
0
0
0
0
P
3
P
2
P
1
0
0
1
-1
1
0
1
0
1
0
0
[1]
0
1
0
1
0
0
x
1
3
x
2
2
x
6
9
x
6
x
5
x
4
x
3
x
2
x
1
X
B
B
-1
b
12
36
21
PP
xx?
这时 行已满足最优性要求，开始调整 行，令对应的 进基,出基，以其交叉元 为枢轴元进行单纯形迭代。得到下一张单纯形表
http://www.tju.edu.cn
第二章多目标规划
X
B
B
-1
bx
1
x
2
x
3
x
4
x
5
x
6
x
1
3
x
2
2
x
3
9
1
0
0
0
1
0
0
0
1
1
0
1
-1
1
0
0
0
1
P
3
P
2
P
1
0
0
0
0
0
0
0
0
0
-2
3
1
-1
-1
2
-1
2
0
2
3
(3 2 0)
( 9 2116)
T
T
P
P
X
F
=
=
此时虽然 行还有负检验数-1，但其下方已有正检验数2。故停止调整。同理,行也已不必再调了。此表给出最优化即为所求：,，
,,。
http://www.tju.edu.cn
第二章多目标规划三、目标规划法：
第一节提出的目标规划模型(3)已经化为单目标问题。特别，当目标函数f
i
(X)(i=1，……，p)和约束R均为线性时，它就是一个线性规划，其解法不必赘述。
本节主要举例说明在实际中常用的分层加权线性目标规划的解法。
例12,有一纺织厂生产尼龙和棉布，平均生产能力都是1
千米/小时，工厂生产能力为每周80小时。根据市场预测，下周最大销量为：尼龙布70千米，棉布45千米，尼龙布利润为
2.5元/米，棉布利润为1.5元/米。工厂领导的管理目标如下，
P
1
：保证职工正常上班，避免开工不足；P
2
：尽量达到最大销售量；P
3
：尽量减少加班时间，限制加班时间不得超过10小时。
http://www.tju.edu.cn
第二章多目标规划
12
0
1121
0
212
0
323
( ) 80
( ) 80
( ) 45
( 1 2 3)
ii
xx
fX x x f
fX x f
fX x f
ddi
+?
=+→ =
=→ =
=→ =
=
解：决策变量,分别表示尼龙布和棉布的下周计划产量。
目标函数：
工时尼龙布产量棉布产量设相应偏差变量为 和,，，则可建立模型目标函数
11 2 2 3 31
min[ ( ) (5 3 ) ( )]LPdPddPd
+
+
如下：
，，
http://www.tju.edu.cn
第二章多目标规划
2
121 1
12
23
1
12
80
70
,,45
10
0123
ii
P
xxd d
xd
st x d
d
xxd d i
+
+
+?
++?=
+=
+=
≤
≥=
其中 优先层表示使产量尽量大，权系数是根据尼龙布与棉布利润之比2,5:1.5＝5:3得到的,约束条件如下：
，，,,,
采用分层单纯形法求解如下（第4约束增加松弛变量S）：
http://www.tju.edu.cn
第二章多目标规划
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
-3
-1
0
0
0
P
3
P
2
P
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
-3
-1
0
-5
-1
P
3
P
2
P
1
0
0
1
0
0
0
1
0
0
0
0
1
-1
1
0
0
-1
0
0
1
1
0
0
0
[1]
0
1
0
0
1
0
0
10
x
1
70
45
S 10
0
0
0
1
0
1
0
0
-1
0
0
1
1
0
0
0
1
0
1
0
1
[1]
0
0
80
70
45
S 10
Sx
2
x
1
X
B
B
-1
b
1
d
1
d
1
d
+
2
d
2
d
3
d
3
d
1
d
3
d
http://www.tju.edu.cn
第二章多目标规划
-1
3
0
0
0
0
1
0
-1
1
0
0
0
1
S
0
0
0
0
2
0
0
0
0
0
3
1
0
0
0
0
0
0
P
3
P
2
P
1
0
0
0
0
2
0
1
-3
0
0
3
1
0
0
0
0
0
0
P
3
P
2
P
1
0
0
1
0
0
0
1
0
-1
1
1
0
0
0
0
1
1
0
-1
0
1
0
0
0
0
1
0
0
x
2
20
x
1
70
25
10
-1
1
1
0
-1
0
1
[1]
1
0
-1
0
1
0
0
0
0
1
0
0
x
2
10
x
1
70
35
S 10
x
2
x
1
X
B
B
-1
b
1
d
1
d
+
2
d
3
d
3
d
3
d
1
d
+
http://www.tju.edu.cn
第二章多目标规划
12 11
23
70 20 0 10
025 205
25
xxdd
dd
+
====
==
得到结果：,,,,
，,总利润 千元。
说明第一目标已经达到，第二目标中尼龙布已经达到，棉布还差 千米，第三目标只达到最低要求。若厂方还想增加棉布量，只有再放宽加班限制。
2.1 多目标规划的数学模型
2.2 多目标规划问题的解
2.3 多目标规划问题的解法
http://www.tju.edu.cn
第二章多目标规划本书大部分章节讨论的基本上都是单目标优化问题，
实际上，许多实际问题的优化牵涉的目标往往不止一个，如设计一个工厂的施工方案，就要考虑工期、成本、质量、污染等目标、再如找工作、购买家用电器追求的目标往往都不止一个。由于这类问题需同时考虑多个目标，而有些目标之间又相互矛盾，从而使决策问题变得复杂,这类决策问题称为多目标决策问题。
http://www.tju.edu.cn
第二章多目标规划多目标决策方法是现代管理科学的重要内容，也是系统分析的基本工具。按照决策变量是连续的还是离散的，
多目标决策可以分为多目标规划决策(Multiple
Objective Decision Making)和多准则决策(Multiple
Attribute Decision Making)两大类，前者是以数学规划的形式呈现的决策问题，后者则是已知各个方案及它产生的结局向量，由此选择最优方案的决策。
http://www.tju.edu.cn
第二章多目标规划多目标决策主要指多目标最优化，即多目标规划。
对于某些问题，可以先用多目标规划选出几个备选方案，然后再用多准则决策方法作进一步处理，因此，这两者既有区别又有联系。
http://www.tju.edu.cn
第二章多目标规划多目标最优化的思想萌芽于1776年经济学中的效用理论。1896年，法国经济学家V·Pareto首先在经济理论的研究中提出了多目标最优化问题。1951年，美国数理经济学家T·C·Koopans从生产和分配的活动分析中考虑了多目标决策问题，并首次提出了多目标最优化问题解的概念，将其命名为“Pareto解”(即有效解)。同年，H·W·Kuhn和 A·W·Tucker从数学规划论角度首次提出向量极值问题及有关概念。
http://www.tju.edu.cn
第二章多目标规划进入20世纪70年代，随着第一次国际多目标决策研讨会的召开及这方面专著的问世，多目标决策问题的研究工作迅速、蓬勃地开展起来，到目前为止，已取得若干有价值的研究成果。
http://www.tju.edu.cn
第二章多目标规划
2.1 多目标规划模型线性规划及非线性规划研究的都是在给定的约束集合
R={X|gi(X) ≥0,i=1,2,……，m)} X ∈ En上，求单目标
f(x)的最大或最小的问题，即方案的好坏是以一个目标去衡量。
http://www.tju.edu.cn
第二章多目标规划然而，在很多实际问题中，衡量一个方案的好坏往往难以用一个指标来判断 。也就是说，需要用一个以上的目标去判断方案的好坏，而这些目标之间又往往不是那么协调，甚至是相互矛盾的。本章将以实例归结出几类常见的描述多目标最优化问题的数学模型。
http://www.tju.edu.cn
第二章多目标规划一、一般多目标规划模型：
例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别为4
元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5
斤。问如何确定最佳的采购方案。
12
12
1
12
42 40
10
5
0,0
xx
xx
x
xx
+ ≤
+≥
≥
≥≥
我们先确定此问题应满足的条件（即约束条件）。不难看出，当甲级糖数量为x
1
，乙级糖数量为x
2
时，有：
http://www.tju.edu.cn
第二章多目标规划在研究以什么为“最佳”的衡量标准时，“筹备小组”的成员们意见可能会发生分歧，其原因是他们会提出各种各样的目标来。
如果要求总花费最小，即要求：
f
1
(x
1
,x
2
)=4x
1
+2x
2
→min
如果要求糖的总数量最大，即要求：
如果要求甲级糖的数量最大，即要求：
易见，这是具有3个目标的规划问题（由于约束及目标均为线性函数，故它为多目标线性规划问题）。
212 1 2
(,) maxfxx x x= +→
312 1
(,) maxfxx x= →
http://www.tju.edu.cn
第二章多目标规划例2：【投资决策问题】某投资开发公司拥有总资金A万元，
今有n(≥2)个项目可供选择。设投资第i(i=1，……，n)
个项目要用资金a
i
万元，预计可得到收益b
i
万元。问应如何使用总资金A万元，才能得到最佳的经济效益？
n
ii
i=1
ii i
1 i
i=1 2 n
0 i
ax A
x (x 1) 0 i=1 2 n x =0 1
i
x
=
≤
=
∑
决定投资第 个项目设,，……，
决定不投资第 个项目问题的约束条件为
，，……,或
http://www.tju.edu.cn
第二章多目标规划所谓“最佳的经济效益”，如果理解为“少花钱多办事”
则变为两个目标的问题，即投资最少，收益最大：
这是具有两个目标的0－1规划问题。
11
1
21
1
()max
()min
n
nii
i
n
nii
i
fx x bx
fx x ax
=
=
=→
=→
∑
∑
，……，
，……，
http://www.tju.edu.cn
第二章多目标规划例3：【木梁设计问题】把横截面为圆形的树干加工成矩形横截面的木梁。为使木梁满足一定的规格和应力及强度条件，要求木梁的高度不超过H，横截面的惯性矩不少于给定值W，且横截面的高度要介于其宽度和4倍宽度之间。
问应如何确定木梁尺寸，可使木梁的重量最轻，并且成本最低。
设所设计的木梁横截面的高为x
1
，宽为x
2
（图1）。
为使具有一定长度的木梁重量最轻，应要求其横截面面积x
1
x
2
为最小，即要求x
1
x
2
→min
x
1
x
2
r
图1
http://www.tju.edu.cn
第二章多目标规划由于矩形横截面的木梁是由横截面为圆形的树干加工而成的，故其成本与树干横截面面积成正比。由此，为使木梁的成本最低还应要求尽可能的小，或即：
根据问题的要求，应满足下述约束条件：
这是具有两个目标的非线性规划问题。
222
12
(/2) (/2)rx xππ
=+
22
12
()/4xxπ +
22
12
()minxx+→
1
12
12
21
12
0
40
0,0
xH
xx W
xx
xx
xx
≤
≥
≥
≥
≥≥
http://www.tju.edu.cn
第二章多目标规划由以上实例可见，多目标最优化模型与单目标最优化模型的区别主要是目标多于一个。在这些目标中，有的是追求极大化，有的是追求极小化，而极大化与极小化是可以相互转化的。因此，我们不难将多目标最优化模型统一成一般形式：
决策变量：x
1
，……，x
n
标函数：minf
1
(x
1
，……，x
n
)
………………
minf
p
(x
1
，……，x
n
)
11
1
()0
()0
n
mn
gx x
gx x
≥
≥
，……，
约束条件,………………
，……，
http://www.tju.edu.cn
第二章多目标规划若记X= (x
1
，……，x
n
)，且用V-min表示对向量
F(X)=[f
1
(X)，……，f
p
(X)]
T
中的各目标函数f
1
(X)，……，
f
p
(X)同等的进行极小化。R={X|g
i
(X)≥0，i=1，……，m}表示约束集。则模型一般式也可简记为：
这里(VMP)为向量数学规划(Vector Mathematical
Programming)的简写。
1
min[() ()]
()
( ) 0 i=1
min ( )
()
p
i
VfX fX
VMP
gX
VFX
VMP
XR
≥
∈
，……，
，……，m
或
http://www.tju.edu.cn
第二章多目标规划二、分层多目标规划模型本节介绍一类不同于(VMP)形式的多目标最优化模型。这类模型的特点是：在约束条件下，各个目标函数不是同等的被优化，而是按不同的优先层次先后的进行优化。
例如，在第一节例1中，若筹备小组希望把所考虑的三个目标按重要性分成以下两个优先层。
第1优先层——总的花费最小。
第2优先层——糖的总数量最大。
甲级糖数量最大。
http://www.tju.edu.cn
第二章多目标规划那么这种先在第1优先层次极小化总花费，然后在此基础上再在第2优先层次同等的极大化糖的总数量和甲级糖的问题，就是所谓分层多目标最优化问题。可将其目标函数表示为：
L-min{P
1
[f
1
(X)]，P
2
[f
2
(X)，f
3
(X)]}
其中P
1
，P
2
是优先层次的记号，L-min表示按优先层次序进行极小化。
下面，我们来看一个建立分层多目标最优化模型的例子
http://www.tju.edu.cn
第二章多目标规划例4：某水稻区一农民承包10亩农田从事农业种植。已知有三类复种方式可供选择，其相应的经济效益如下表：
方案复种方式 粮食产量
(公斤/ 亩)
油料产量
(公斤/ 亩)
利润
(元/ 亩 )
投入氮素
(公斤/ 亩)
用工量
(小时/ 亩)
1
大麦－早稻－晚梗
1056 —— 120.27 50 320
2
大麦－早稻－玉米
1008 —— 111.46 48 350
3
油菜－玉米－蔬菜
336 130 208.27 40 390
http://www.tju.edu.cn
第二章多目标规划设该农户全年至多可以出工3410小时，至少需要油料156公斤。今该农户希望优先考虑总利润最大和粮食总产量最高，然后考虑使投入氮素最少。问如何确定种植方案。
首先设立决策变量如下：
方案1的种植亩数：x
1
，
方案2的种植亩数：x
2
，
方案3的种植亩数：x
3
，
根据农户的要求确定问题的三个目标函数为：
http://www.tju.edu.cn
第二章多目标规划年总利润：f
1
(x
1
，x
2
，x
3
)=120.27x
1
+111.46x
2
+208.27x
3
粮食总产量：f
2
(x
1
，x
2
，x
3
)=1056x
1
+1008x
2
+336x
3
投入氮素量：f
3
(x
1
，x
2
，x
3
)=50x
1
+48x
2
+40x
3
根据农户的全年出工能力，对油料需求量，所承包农田数以及种植亩数应为非负等限制，应有约束条件：
总用工量：320x
1
+350x
2
+390x
3
≤3410
油料需求,130x
3
≥156
农田数,x
1
+x
2
+x
3
＝10
种植亩数非负：x
1
≥0,x
2
≥0,x
3
≥0。
http://www.tju.edu.cn
第二章多目标规划根据农户对目标重要性的排序，将前两个目标作为第一优先层，将第三个目标作为第二优先层，再把其中的求最大化转化为求其负数的最小，便得到下列具有两个优先层次的分层多目标极小化模型：
对它进行求解便可得到农户满意的种植方案。
1123
123
21 2 3
123
3
123
123
min[ ( 120.27 111.46 208.27
1056 1008 336 )
(50 48 40 )]
320 350 390 3410
130 156
.
10
000
L Pxx x
xxx
Px x x
xxx
x
st
xxx
xxx
++
++≤
≥
++=
≥≥≥
，
,
，，
http://www.tju.edu.cn
第二章多目标规划三、多目标规划模型：
本节介绍一类在实际中有着广泛应用的特殊多目标最优化模型。这类模型并不是去考虑对各个目标进行极小化或极大化，而是希望在约束条件的限制下，每一目标都尽可能的接近于事先给定的各目标值。
设p个目标函数的给定目标值分别为：
00
1
0
1
( ) (1)
p
p
ii
i
ff
fX f
∈
=
∑
XR
，……，
则为使各目标函数尽量接近其目标值，可建立以追求总绝对偏差极小化为目标的目标规划模型：
min
http://www.tju.edu.cn
第二章多目标规划
0
00
0
0
0
00
()
( ) ( )
0 ( ) 1
()
0 ( )
( ) ( )
ii
ii i i
i
ii
ii
ii
i
ii i i
fX f
fX f fX f
d
fX f i p
fX f
fX f
d
ffX fXf
+
>
=
≤=
≥
=
<
若记 关于 的正偏差为
-，,
，,……，
关于 的负偏差为
，，
0
0
1
( )
( )
0 1
ii i i
iii i
ii
ip
dd fXf
ddfXf
dd i p
+
+
+
=
+
= =
－
－
－
，,……，
则不难看出
＝-，
＝-，
，，…，
http://www.tju.edu.cn
第二章多目标规划
1
0
min ( )
()
,
0
0 0 1 (2)
(2)
p
ii
i
iiii
ii
ii
dd
XR
fX d d f
st
dd
dd i p
+
=
+
+
+
+
∈
+=
=
≥≥=
∑
－
－
－
－
于是目标规划模型(1－1)也可以表示为
，，…，
虽然去掉了绝对值运算，但却含有偏差变量相乘的约束条件，这仍然使求解很不方便。考察去掉偏差变量相乘的约束条件，得到模型：
(1)
http://www.tju.edu.cn
第二章多目标规划
1
0
min ( )
,( )
0 0 1 ( )
)()
))
()
p
ii
i
iiii
ii
dd
XR
st f X d d f
dd i p
+
=
+
+
+
∈
+=
≥≥=
∑
nullnullnull
nullnull
－
－
－
+-
++ +-- -
1p1p
，，…，3
可以证明，若(X，d,d 是 3 的最优解，其中d ＝(d,……，d,d ＝(d,……，d,则X是
(2)的最优解。因而可将 3 作为目标规划模型的一般形式。在此一般形式基础上，还可以建立加权的或分层的目标规划模型。
http://www.tju.edu.cn
第二章多目标规划例5：某机器制造厂生产两种型号的机器，同时也进行机器的零部件和工业性作业生产。已知有关数据如下表，
并且该工厂全年能承担生产的总工时为58万小时。
生产项目 单位 产值 利润 工时 需要量
1号机 套
5
万元/ 套
1
万元/ 套
1000
小时/ 套
160套
(指令性计划 )
2号机 台
1.6
万元/ 套
0.2
万元/ 台
400
小时/ 台
320～ 500台
(市场预测)
零部件和工业性作业万小时
50
元/ 小时
8.1
元/ 小时
26万小时
(市场预测)
http://www.tju.edu.cn
第二章多目标规划今决策者希望在完成上级下达的指令性计划的前提下，全年总产值达到2750万元左右，总利润不低于440万元，并且要避免开工不足。然后，还希望工人的加班时间不超过总工时的4％，以及依据市场预测的信息进行生产。试问应如何安排工厂的年生产计划。
首先，设立决策变量为：
x
1
：生产1号机套数
x
2
：生产2号机台数
x
3
：生产零部件和工业性作业的工时数(万小时)
http://www.tju.edu.cn
第二章多目标规划
1
2
3
4
5
( ) 160
( ) 2750
( ) 440
400
() 58
10000
() 4
400
10000
fX
fX
fX
fX
fX
→=
→=
→=
++→
++→
0
11
0
1232
0
1233
0
1234
1235
目标函数及其目标值：
：1号机产量x f
：年总产值5x +1.6x +50x f
：总利润x +0.2x +8.1x f
1000
：总工时 x x x f＝
10000
：加班时间不超过总工时的 ％的要求：
1000
xxxf
10000
6
58 (1 4 )
()
2 320 500
26
fX
×+
≤≤
→
0
2
0
36
＝％
：按市场预测信息进行生产的要求：
号机产量,x
工业性作业和零部件的工时：x f＝
http://www.tju.edu.cn
第二章多目标规划
111 22234 356788
11 1
12322
12333
12344
1
min[ ( ) ( ) ( )]
160
5 1.6 50 2750
0.2 8.1 440
0.1 0.04 58
0.1 0.04
..
L Pdd Pdddd Pddddd
xd d
xxxdd
xxxdd
xxxdd
xx
st
+? + +?++?
+?
+?
+?
+?
+ +++ ++++
+=
++?+=
++?+=
++?+=
+
根据决策者对目标重要性的优先次序 可得该问题的分层目标规划模型
，，
235 5
26 6
27 7
38 8
12 3
58 (1 4%)
320
500
26
0
0 i=1 2 8
ii
xd d
xdd
xdd
xd d
xx x
dd
+?
+?
+?
+?
+?
+?+ =×+
+=
+=
+=
≥
≥
,为非负整数，
、，,…
由上例可见，利用偏差变量建立目标 规划模型，常常可不必严格区分问题中的目标与约束，而将一些约束条件考虑作为目标。
http://www.tju.edu.cn
第二章多目标规划
2.2 多目标规划问题的解：
在单目标规划问题中，任意两个可行方案都可通过比较其目标函数值来确定其优劣。在所有可行方案中，使目标达最优的就是最优解。
而在多目标规划问题中，约束集R中的两个方案x
1
，x
2
其优劣往往不能进行比较。这是因为它们的目标值F(X
1
)与
F(X
2
)是向量，而向量是无法直接比较大小的。所以，在R
中也往往不存在一个方案对每个目标都是最优的。
这种多目标规划问题区别于单目标规划问题的本质表明，仅仅将单目标问题最优解的概念平移到多目标问题中是不行的。本章将介绍多目标规划问题各种解的概念及其相互关系。
http://www.tju.edu.cn
第二章多目标规划一,各种解的概念：
11 1
1
22 2
1
12 1
2 12
12 1
2
( )
( )
(1) " "
1
(2)" "
1
pp
pp
ii
Ff fE
Ff fE
FF F
Fipf
FF F
Fi
=∈
<<
=<
<<
=
先 引 进 一 些 记 号,记
，……，
，……，
,意 味 着 向 量 的 每 个 分 量 都 要 严 格 的 小 于 向量 对 应的分量。即对于,……，,均有 。
,意 味 着 向 量 的 每 个 分 量 都 要 小 于 或 等 于 向量 对 应的分量。即对于,
00
12
12 1
21 2
12
12
12 12 12
(3)" "
1
""""""
ii
ii
ii
pff
FF F
F FF
ipff
ff
FF FF FF
≤
≤≤
=≤
≤≤ <
≤<≠
00
……，,均有 。
,意 味 着 向 量 的 每 个 分 量 都 要 小 于 或 等 于 向量 对 应的分量，并且存在 的 某一个分量要严格的小于向量对应的分量。即对于,……，,均有,并且要至少存在某个i (1 i p),有 。
可 见,等 价 于 且 。
http://www.tju.edu.cn
第二章多目标规划图2给出了两个目标，一维变量时绝对最优解的例子
X
f
0
1
()f x
2
()f x
x
2图
*
1 ( ) ( )
() ()
ab
XR XR FX FX
XVMP VMP
R
∈∈≥定义 设,若对于任意 均有,
则称 为问题 的绝对最优解。 的绝对最优解全体记为,称其为绝对最优解集合。
X
12
图中的 即是f(x)的极小点，又是f(x)的极小点，也就是使所有目标都达最优，因而是该问题的绝对最优解。但在大多数多目标规划问题中，这样的绝对最优解往往是不存在的。
http://www.tju.edu.cn
第二章多目标规划
2
(1 )
RR
p
pp
∈∈≤
≤
≤≤
00
0110
10
ii 0
10 0 1
0ii
0
为引出以下的定义,我们先考查什么叫做劣解。设
X,若存在另一个可行解X,有F(X ) F(X )，即对于i=1，……，p，均有f(X ) f(X )，并且至少存在某个i
i 有f (X )<f (X )，显然可行解X 相对于X 来说是劣的。这是因为方案X的 个目标值都不比X 对应的 个目标值坏，
且至少比有一个要好。我们称X 为劣解。于是有如下非劣解的 R∈定义，从字面上可知：X 如果不是劣解就称其为非劣解。
*
2()(
() ()
()
pa
RXRFXF
VMP VMP
RVMP
∈∈≤ 定义 设X,若不存在,有 X,
则称X为问题 的非劣解（也称有效解）。 的有效解全体记为,称其为 的有效解集合。
http://www.tju.edu.cn
第二章多目标规划图3 给出了两个目标，一维变量时有效解集合的例子
f
0
1
()fx
2
()f x
x
3图
*
1
x
*
2
x
*
pa
R
**
12
,()()
" "
""
xx X
XFXFX≤
≤
<
图中 与 之间的点 均为有效解，因为找不到另一个可行解 满足 。
在定义2中我们用 定义了有效解，当我们使用符号 时，则可以定义弱有效解。
http://www.tju.edu.cn
第二章多目标规划图4给出了弱有效解集合的例子。
*
wp
R
f
0
1
()f x
2
()f x
x
4图
*
3 ( ) ( )
() ()
()
wp
X RXRFXFX
XVMP VMP
RV
∈∈<定义 设,若不存在,使,
则称 为问题 的弱有效解。 的弱有效解全体记为,称其为 的弱有效解集合。
*
() ()
wp
Rx
xR Fx Fx∈<
不难看出,中的任一点 都为弱有效解。因为找不到另一个,满足 。
http://www.tju.edu.cn
第二章多目标规划二,各种解之间的关系:
1
*
** * * *
1
**
1
() ()
min ( )
()
1
p
i
i
i
ab pa wp p
p
ab i
i
p
fx fx R
fX
P
XR
Ri p
RR R R R R
RR
=
∈
=……
∩
为了较完整的讨论各种解集之间的关系，将 个 目标
，……,分 别与约束集 组成的单目标问题（即线性或非线性规划）
的最优解集记为,,,。
集合,,,,,……,之间的关系由以下一些定理给出。定理1是显然的。
定理1 ＝ 。
http://www.tju.edu.cn
第二章多目标规划
**
*
**
2
( ) ( )
1
() ( )
(
pa wp
wp pa wp
pa wp
ii
RRR
RR RR
XR XR YR
FY FX
ip
fY fX
Y
FY
∈? ∈
<
=……
<
定理证,是显然的，只需证 。用反证法证之。
设,但 。根据弱有效解定义，必存在,使
，
即对于,,,均有
因此 满足
**
**
)()
pa wp
pa wp
FX
XXR XR
RR
≤
∈
由此推得 为劣解，即,矛盾。从而证明,即
。证毕。
http://www.tju.edu.cn
第二章多目标规划
0
00
0
**
0
***
3 1
() ( ) 1
( ) ( )
( ) ( )
iwp
p
ii
ii
iiwp
RRi p
XR XR YR
FY FX i p
fY fX
ii
fY fX
XR R R
=…
∈?∈
<=…
<
=
<
∈?
定理,,,
证：设,但,于是存在,
有 。即对于,,,均有特别的，对 有这与 矛盾，故,证毕。
http://www.tju.edu.cn
第二章多目标规划
0
**
**
00
4
() ( ) 1
( ) ( )
(1 )
(
ab pa
ab ab
ab pa
ii
i
RR
XR XR YR
FY FX i p
fY fX
iip
fY
=?≠?
∈? ∈
≤=
≤
≤≤
定理证：若,结论显然成立。故不妨设 。
设,但 。由有效解定义，必存在某,
使,即对,……，,均有并且至少存在,有
0
0 0
****
1
**
)()
i
p
iabii
i
ab pa
fX
XR XR RXR
RR
=
<
∈ ∈
∩
说明,但由 知,矛盾。故必有 。证毕。
http://www.tju.edu.cn
第二章多目标规划
{ } { }
**
1122
**
12
[ ]
pa wp
R xRx
R Rxx
==
==
例6 见图5，此时，,
，
2
x
1
x
1
()f x
2
()f x
x
f
0
5图
http://www.tju.edu.cn
第二章多目标规划
*
pa
R
*
wp
R
*
1
R
0
1
()f x
2
()f x
x
6图
*
2
R
f
*** *
12
wp pa
RRR R例7 见图6，,,,如图所示。
http://www.tju.edu.cn
第二章多目标规划
**
ab pa
RR=
*
wp
R
*
1
R
f
0
1
()f x
2
()f x
x
7图
*
2
R
*
***** **
12 12
ab
pa ab wp
R
RRRRR RR
≠?
==∩∪
例8 见图7，
在这个例子中，,并且
＝,
http://www.tju.edu.cn
第二章多目标规划
*
***
1
**
1
5
(1)
(2)
ab
p
pa i ab
i
p
wp i
i
R
R RR
RR
=
=
≠?
==
=
∩
∪
事实上，
可以证明如下定理：
定理 设,
则；
。
http://www.tju.edu.cn
第二章多目标规划
*
p a
R
*
wp
R
R
*
1
R
*
2
R
*
3
R
*
3
ab
pR= =?，
8图本节讨论的解集之间的关系可以由图8，9给出。
http://www.tju.edu.cn
第二章多目标规划
*
1
R
*
2
R
*
3
R
*
3
ab
pR= ≠?，
**
ab pa
R=R
9图
http://www.tju.edu.cn
第二章多目标规划三、多目标决策与单目标决策区别:
点评价与向量评价:
单目标,方案 d
j
←评价值 f(d
j
)
多目标：方案 d
j
←评价向量( f
1
(d
j
),f
2
(d
j
)…,f
p
(d
j
))
全序与半序,方案 d
i
与 d
j
之间单目标问题,d
i
<d
j; d
i
=d
j; d
i
>d
j
多目标问题：除了这三种情况之外,还有一种情况是不可比较大小决策者偏好：多目标决策过程中，反映决策者对目标的偏好。
解概念区别:
http://www.tju.edu.cn
第二章多目标规划四、解的概念:
单目标决策的解只有一种（绝对）最优解多目标决策的解有下面四种情况：
绝对最优解劣解有效解(Pareto解)
弱有效解
http://www.tju.edu.cn
第二章多目标规划
d
1
80 75 88
有效解
d
2
75 81 85
有效解
d
3
76 78 89
有效解劣解
d
5
79 74 86
d
4
85 82 92 绝对最优解数学 外语 专业 解的类型五、多目标决策解的例子:
http://www.tju.edu.cn
第二章多目标规划
2.3 多目标最优化问题的解法:
求解多目标最优化模型，就是要根据问题的特点和决策者的意图，选择适当解法，求得模型的有效解或弱有效解。本章将介绍一些常用的多目标最优化问题解法。
http://www.tju.edu.cn
第二章多目标规划
()( 1 )
()
( )
min ( )
i
i
i
ii
XR
p
f Xi p
fX
fX
f
ffX
∈
=……
=
在实际问题中,个目标的量纲往往都是不同的，
所以事先需把每个目标规范化，然后再进行数学上的处理。比如，可以把带量纲的目标,,
进行如下处理，令其中 ＝
以后我们总假定所讨论的多目标最优化模型已经过了规范化处理。
http://www.tju.edu.cn
第二章多目标规划一、评价函数法:
1
( ) ( )
()
( ) min [ ( )]
() ()
()
p
XR
hF hf f
VMP
PhFX
hF P X
VMP
∈
=
评价函数法就是利用一个复合函数:
，……，
把多目标问题 转化为单目标问题:
然后来求解，而单目标问题的解法我们是熟知的。问题是，用评价函数 得到的 的最优解 是否为原问题的有效解或弱有效解？因为若连弱有效解都不是，
那显然是不足取的。
http://www.tju.edu.cn
第二章多目标规划
**
121 2
12
( )
()
( ) ( )
()
()
pa wp
p
pp
p
hF
XR XR
hF E
FFFEFE
hF hF
hF
hF E
∈∈
≤∈∈
<
下面我们将指出，当评价函数 具有某种“单调性时”，是可以保证 （或 ）的。为此，先给出两个定义：
定义4 设 是定义在 上的函数，若对于任意满足 的,,均有：
则称 为严格单调函数。
定义5 设 是定义在 上的函数，若对于任
121 2
12
( ) ( )
()
pp
FFFEFE
hF hF
hF
<∈∈
<
意满足 的,,均有：
则称 为单调函数。
http://www.tju.edu.cn
第二章多目标规划
*
*
( )
( ) min [ ( )]
() ( )
()
[ ( )] < [ ( )]
()
p
XR
pa
pa
hF E X
phFX
XR
X RYRFYFX
hF
hFY hF X
Xp
∈
∈
∈≤
定理6 若 为定义在 上的严格单调函数，为规划问题的最优解，则 。
证：用反证法。若,则存在,有,
由 的严格单调性，有这与 为问题 的最优
*
*
( )
( ) min [ ( )]
pa
p
XR
wp
XR
hF E X
phFX
XR
∈
∈
∈
解矛盾，故 。
定理7 若 为定义在 上的单调函数，为规划问题的最优解，则 。
证明方法与定理6雷同。
http://www.tju.edu.cn
第二章多目标规划
1
1
1
1
1
()
01 1
ipp
p
p
p
ii
i
hF f f
ip
λλ
λλ
λ λ
λλ
=
=+…+
≥= =
∑
下面 介绍两种常用的评价函数方法。
,线 性加权和法
该方 法就是取评价函数为各目标函数的线性加权和，
即
其中,……,为相应目标的权系数。
线性 加权和法的步骤如下：
(1)依目标的重要程度给出一组权系数,……，,
其中,,……，,。
http://www.tju.edu.cn
第二章多目标规划
1
*
*
*
(2) ( )
() min ()
()
(3) ( )
01
01 ()
0
p
ii
XR
i
wp
i
pa
i
pa i
VMP
PfX
PX
XVMP XR
ip
XR
iphF
XR
λ
λ
λ
λ
λ
λ
∈
=
∈
>=…
∈
>=…
∈≥
∑
将 转化为单目标问题
求解 得最优解 。
可以证明，是 的弱有效解，即 。进一步，若所有权系数均为正，即,,,,则
。
事实上，当,,,时,为严格单调函数，故 ；而当,
*
1()
wp
iphF
XR
=……
∈
，，时，
为单调函数，故 。
http://www.tju.edu.cn
第二章多目标规划
3
12
22
12 1 2
1
1
3
12.5
0.3 0.7
3
min 0.3 0.7( )
2.5 0
,,
WH
xx x x
x
x
st
λλ
==
==
++
≥
用线性加权和法求解例 的木梁设计问题。
设其中的 尺,尺，又设决策者认为成本与重量两个目标的权系数各为 和 。
解,根据例 的木梁设计问题模型，可建立线性加权和模型。
例9
2
12
21
12
10
0
40
0
x
xx
xx
xx
≥
≥
≥
≥
、
http://www.tju.edu.cn
第二章多目标规划
12
1
2
( ) (1.1511 0.7547)
37
( ) 1.1511( )
( ) 0.7547(
TT
Xxx
X
x
x
==
这是一个单目标非线性规划问题，用非线性约束最优化方法可求得其最优解
,,
由于权系数均大于零，故 是原多目标问题有效解。
以上结果表明，在决策者认为重量目标与成本目标的重要性之比为,的意义下，木梁设计的满意尺寸应是
高＝ 尺
宽＝ 尺 )
http://www.tju.edu.cn
第二章多目标规划
**
1
** * * *
1
** *
*
2
()
()
()
p
T
p
ab
ff
pFf f F XR
X RX
FR
hF F F
=∈
∈
、理想点法：
理想点 一般是指由各单目标最优值,……,组成的 维点,……,。若 相应的自变量,
即,那么当然很理想。但我们已经知道，这样的往往是不存在的（见图10）。于是自然想到找一个中离它最近的点，即可取评价函数 为 与 的距离，
具体构造如下：
10图
1
f
***
12
()
T
F ff=,
()F R
2
f
0
http://www.tju.edu.cn
第二章多目标规划
*2
1
(1)
( ) ( )
( ) min [ ( )]
01 1()
() 01
()
(2)
p
ii i
i
XR
ii
i
hF f f
phFX
ip pX
VMP i p
XVMP
λ
λλ
λ
=
∈
=?
≥= =
>=
∑
∑
平方和加权法：
取,再求解单目标问题其中,,……，,。则 的最优解是原问题 的弱有效解。若,,……，,
则 是 的有效解。
最小偏差法取
*
1
()
( ) min [ ( )]
p
ii
i
XR
hF f f
phFX
=
∈
=?
∑
，构成单目标问题
http://www.tju.edu.cn
第二章多目标规划
1
*
*
1
( ') min( ) ( )
() 1
,,
(') ( )
(
p
ii ii
i
iiii
pdddd
f Xdd fi p
st
XR
pXVMP
Ff
+? +?
=
+?
=+
+= =
∈
=
∑
*
为避免绝对值运算，一般将其转化为与之等价的偏差变量模型：
，
，,……，
可以证明,的最优解 是其相应 的有效解。
以,……
*
00
1
)
()(')
p
p
f
p
Ff f p=
0
,作理想点，需要事先求解个单目标规划，实际中有时也可凭经验给出一组目标值,……，,这时 即为目标规划模型。
http://www.tju.edu.cn
第二章多目标规划
1
( 1 )
(1 )
1
jij
k
j
ij
i
kiik
fj p
ki
λ
λλ
=
=
=
=
∑
最后介绍两种确定权系数的方法。
(1)老手法:
邀请一批“老手”（如专家、学者、有实践经验的技工、干部等），请他们对如何取权系数发表意见。
设邀请了 位老手，设第,……,位老手认为目标,……,的权系数为,计算各目标的权系数均值。
1jp=,……，
http://www.tju.edu.cn
第二章多目标规划
λ
kp
……
λ
k2
λ
k1
k
…………………………
λ
2p
……
λ
22
λ
21
2
λ
1p
……
λ
12
λ
11
1
……
f
p
(X)……f
2
(X)f
1
(X)
目标权系数老手
1
ij
j
ij ij
jp
λ
λλΔ=? =
然后计算 与均值的偏差
，……，
请那些有最大偏差的“老手”发表意见，充分讨论后再重复上述步骤。
1
λ
2
λ
p
λ
http://www.tju.edu.cn
第二章多目标规划
1
1
*
(2)
min ( )
1()
1
1
0 1
j
XR
iii
jj
p
i
jj
j
p
j
j
j
ab
p
fX
Xi p f fX
fi p
jp
R
α
λα
λ
λ
∈
=
=
==
==
=
≥=
=?
∑
∑
方法先求 个单目标问题的最优解,,……,。记,构造方程组
，……，
，……，
当时，此
1
1
()
p
p
λλα
λλ
方程组有唯一解,……，,,由此即得权系数,……,。
确定权系数，还可采用层次分析法，见第四章。
http://www.tju.edu.cn
第二章多目标规划二、分层求解法本节将针对第一节中介绍的分层多目标最优化模型，介绍一般的分层评价法和适用于线性分层模型的分层单纯形法。
1、分层评价法:
设将目标分为L个优先层，则可首先在约束集R上对第一优先层进行多目标极小化，然后在第一层优化所得的（弱）有效解集上对第二层进行优化，然后在第二层优化所得的（弱）有效解集上对第三层进行优化……
可以证明，按分层评价法进行求解时，只要每一层选用的评价函数都是严格增的，则最后所得的解必为相应的不分层多目标最小化模型的有效解。
http://www.tju.edu.cn
第二章多目标规划
1123
123
21 2 3
123
min[ ( 120.27 111.46 208.27
1056 1008 336 ),
(50 48 40 )]
320 350 390 3410
,
L Pxx x
xxx
Px x x
xxx
st
++
++≤
用分层评价法求解例4中的农田种植问例10：
题：
，
3
123
123
130 156
10
000
x
R
xxx
xxx
≥
++=
≥≥≥
，，
http://www.tju.edu.cn
第二章多目标规划
1
1123
(120.27 111.46 208.27) /100
4.4 (1056 1008 336) /100 24
11 1
( ) -27 - 25 - 47
33 3
fX x x x
++
++
=
解：问题的第一优先层含有利润和粮食产量两个目标，今选用线性加权法对它求解。首先对两个目标作统一量纲处理。以 ＝
除利润目标函数，以 ＝ 除粮食产量目标函数，则可得
1
2123
11
12
111
12123
( ) -44 - 42 -14
0.6
0.4
[ ()]0.6 ()0.4 ()-34-32 -34
fX x x x
ff
hF X f X f X x x x
=
=+=
设该农户认为两个目标 和 的权系数分别为和,则有线性加权和评价函数
http://www.tju.edu.cn
第二章多目标规划
1
1
33 3
11
1
123
312
min [ ( )]
(10 0 ) 1.2 3
[()] 340
{ | 34 32 34 340}
'
()50 48
XR
T
hF X
Xxx x
hF X
RXR x x x
R
fX x x
∈
=?≤≤
=?
=∈ ≤?
=++
求解线性规划
可得最优解,，,其中,
和最优值 。
由第一优先层的最优值构造第二优先层的可行域
再在 上极小化第二优先层的目标（氮素量）
3
22
40
(7 0 3)
T
x
XX=可得最优解,,。 即为问题的有效解。
http://www.tju.edu.cn
第二章多目标规划上述结果表明：若该农户认为利润和粮食目标在问题中的重要程度分别为0.6和0.4的话，则他应该选择如下的种植方案：
方案1：种植7亩方案2：不种植方案3：种植3亩这时，还可算出:
年总利润＝1466.66元粮食总产量＝8400公斤氮素投入量＝470公斤油料产量＝390公斤总用工量＝3410小时
http://www.tju.edu.cn
第二章多目标规划
2、分层单纯形法：
将普通单纯形法加以适当推广，便可用来求解分层多目标线性规划模型。其一般步骤如下：
(1)将每一优先层中各目标函数通过评价函数法（如线性加权和）转化为单目标；
(2)用单纯形法求解各层目标相应的线性规划问题。
设共有L个优先层，则在每张单纯形表上的检验数位置有L
行检验数(C
j
-C
B
B
-1
p
j
)，将P
1
层对应的检验数写在最下行，
P
L
层对应的检验数写在最上行。
http://www.tju.edu.cn
第二章多目标规划
(3)检验调整时由下往上，先调P
1
行（迭代方法同单纯形法），直至P
1
行检验数满足最优性要求
（检验数≥0），再开始调P
2
行。若某行负检验数相应下行中有正检验数，则根据“高级优先”的原则，放弃调整该列。这样进行直至无法再调时（全部检验数为非负或虽有某为负，但其下方有正的）
为止。
http://www.tju.edu.cn
第二章多目标规划
11 2 21 2
31 2 3
12
2
123
123
min[ ( 3 ) ( 2 )
(2 )]
5
2
,,
4
000
LPxxPxx
Px x x
xx
x
st
xxx
xxx
++
+≤
≤
+ ≤
≥≥≥
用分层单纯形法求解下面的分层线性规划问题
，，
例11
，
:
，
http://www.tju.edu.cn
第二章多目标规划
456
11 2 21 2
31 2 3
124
25
1236
16
min[ ( 3 ) ( 2 )
(2 )]
5
2
,,
4
0
xxx
LPxxPxx
Px x x
xxx
xx
st
xxxx
++
++
+
++
≥
解：引入松弛变量，,,,将问题转化为标准形式
,,
＝
＝
＝
，……，
http://www.tju.edu.cn
第二章多目标规划
0
0
0
0
0
0
0
0
0
1
-2
0
2
0
-3
1
-1
-1
P
3
P
2
P
1
0
0
1
0
1
0
1
0
0
0
0
1
1
[1]
-1
1
0
-1
x
4
5
x
5
2
x
6
4
x
6
x
5
x
4
x
3
x
2
x
1
X
B
B
-1
b
12
5
3
1
Px
x
调整时先看 行，令检验数 对应的 进基，
根据单纯形法原理，确定出基变量为,以其交叉元 为枢轴元进行单纯形迭代。得下一张单纯形表建立初始单纯形表:
http://www.tju.edu.cn
第二章多目标规划
0
0
0
0
0
3
0
0
0
1
-2
0
0
0
0
1
-1
-1
P
3
P
2
P
1
0
0
1
-1
1
1
1
0
0
0
0
1
0
1
0
[1]
0
-1
x
4
3
x
2
2
x
6
6
x
6
x
5
x
4
x
3
x
2
x
1
X
B
B
-1
b
114
1 1
1
P xx行仍有负检验数,再令 对应的 进基，
出基，以其交叉元 为枢轴元进行单纯形迭代。得到下一张单纯形表
http://www.tju.edu.cn
第二章多目标规划
0
0
0
1
-1
2
-1
1
1
1
-2
0
0
0
0
0
0
0
P
3
P
2
P
1
0
0
1
-1
1
0
1
0
1
0
0
[1]
0
1
0
1
0
0
x
1
3
x
2
2
x
6
9
x
6
x
5
x
4
x
3
x
2
x
1
X
B
B
-1
b
12
36
21
PP
xx?
这时 行已满足最优性要求，开始调整 行，令对应的 进基,出基，以其交叉元 为枢轴元进行单纯形迭代。得到下一张单纯形表
http://www.tju.edu.cn
第二章多目标规划
X
B
B
-1
bx
1
x
2
x
3
x
4
x
5
x
6
x
1
3
x
2
2
x
3
9
1
0
0
0
1
0
0
0
1
1
0
1
-1
1
0
0
0
1
P
3
P
2
P
1
0
0
0
0
0
0
0
0
0
-2
3
1
-1
-1
2
-1
2
0
2
3
(3 2 0)
( 9 2116)
T
T
P
P
X
F
=
=
此时虽然 行还有负检验数-1，但其下方已有正检验数2。故停止调整。同理,行也已不必再调了。此表给出最优化即为所求：,，
,,。
http://www.tju.edu.cn
第二章多目标规划三、目标规划法：
第一节提出的目标规划模型(3)已经化为单目标问题。特别，当目标函数f
i
(X)(i=1，……，p)和约束R均为线性时，它就是一个线性规划，其解法不必赘述。
本节主要举例说明在实际中常用的分层加权线性目标规划的解法。
例12,有一纺织厂生产尼龙和棉布，平均生产能力都是1
千米/小时，工厂生产能力为每周80小时。根据市场预测，下周最大销量为：尼龙布70千米，棉布45千米，尼龙布利润为
2.5元/米，棉布利润为1.5元/米。工厂领导的管理目标如下，
P
1
：保证职工正常上班，避免开工不足；P
2
：尽量达到最大销售量；P
3
：尽量减少加班时间，限制加班时间不得超过10小时。
http://www.tju.edu.cn
第二章多目标规划
12
0
1121
0
212
0
323
( ) 80
( ) 80
( ) 45
( 1 2 3)
ii
xx
fX x x f
fX x f
fX x f
ddi
+?
=+→ =
=→ =
=→ =
=
解：决策变量,分别表示尼龙布和棉布的下周计划产量。
目标函数：
工时尼龙布产量棉布产量设相应偏差变量为 和,，，则可建立模型目标函数
11 2 2 3 31
min[ ( ) (5 3 ) ( )]LPdPddPd
+
+
如下：
，，
http://www.tju.edu.cn
第二章多目标规划
2
121 1
12
23
1
12
80
70
,,45
10
0123
ii
P
xxd d
xd
st x d
d
xxd d i
+
+
+?
++?=
+=
+=
≤
≥=
其中 优先层表示使产量尽量大，权系数是根据尼龙布与棉布利润之比2,5:1.5＝5:3得到的,约束条件如下：
，，,,,
采用分层单纯形法求解如下（第4约束增加松弛变量S）：
http://www.tju.edu.cn
第二章多目标规划
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
-3
-1
0
0
0
P
3
P
2
P
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
-3
-1
0
-5
-1
P
3
P
2
P
1
0
0
1
0
0
0
1
0
0
0
0
1
-1
1
0
0
-1
0
0
1
1
0
0
0
[1]
0
1
0
0
1
0
0
10
x
1
70
45
S 10
0
0
0
1
0
1
0
0
-1
0
0
1
1
0
0
0
1
0
1
0
1
[1]
0
0
80
70
45
S 10
Sx
2
x
1
X
B
B
-1
b
1
d
1
d
1
d
+
2
d
2
d
3
d
3
d
1
d
3
d
http://www.tju.edu.cn
第二章多目标规划
-1
3
0
0
0
0
1
0
-1
1
0
0
0
1
S
0
0
0
0
2
0
0
0
0
0
3
1
0
0
0
0
0
0
P
3
P
2
P
1
0
0
0
0
2
0
1
-3
0
0
3
1
0
0
0
0
0
0
P
3
P
2
P
1
0
0
1
0
0
0
1
0
-1
1
1
0
0
0
0
1
1
0
-1
0
1
0
0
0
0
1
0
0
x
2
20
x
1
70
25
10
-1
1
1
0
-1
0
1
[1]
1
0
-1
0
1
0
0
0
0
1
0
0
x
2
10
x
1
70
35
S 10
x
2
x
1
X
B
B
-1
b
1
d
1
d
+
2
d
3
d
3
d
3
d
1
d
+
http://www.tju.edu.cn
第二章多目标规划
12 11
23
70 20 0 10
025 205
25
xxdd
dd
+
====
==
得到结果：,,,,
，,总利润 千元。
说明第一目标已经达到，第二目标中尼龙布已经达到，棉布还差 千米，第三目标只达到最低要求。若厂方还想增加棉布量，只有再放宽加班限制。
