多目标最优化问题全面介绍

§8.1多目标最优化问题的基本原理

一、多目标最优化问题的实例 例1 梁的设计问题

设用直径为1的圆木加工成截面积为矩形的梁，为使强度最大而成本最低， 问应如何设计梁的尺寸？

解： 设梁的截面积宽和高分别为1x 和2x 强度最大=惯性矩最大

2

216

1x x = 成本最低=截面积最小=21x x 故数学模型为： min 1

x 2

x

max

2216

1x x

.s t 221

2

1x x +=

10x ≥，20x ≥ 例2 买糖问题 已知食品店有1A , 2

A ,

3

A 三种糖果单价分别为4元∕公斤，2.8元∕公斤，

2.4元∕公斤，今要筹办一次茶话会，要求用于买买糖的钱不超于20元，糖

的总量不少于6公斤，1A ，

2

A 两种糖的总和不少于3公斤，问应如何确定买糖的最佳方案？ 解：设购买1A , 2

A ,

3

A 三种糖公斤数为1x ，2x ，3x

1

A 2

A 3

A

重量 1x 2x

3x

单价 4元∕公斤 2.8元∕公斤 2.4元∕公斤

min 14x +22.8x +3

2.4x （用钱最省）

max 1x +2x +3x （糖的总量最多）

.st 14x +22.8x +3

2.4x 20≤ (用钱总数的限制)

1x +2x +3x 6≥（用糖总量的要求）

1x +2x

3≥（糖品种的要求）

1x ，2x ，3x 0≥

是一个线性多目标规划。

二、 多目标最优化的模型

12min ()((),(),.....())T m V F x f x f x f x -=

.st ()0g x ≥

()0h x ≥

多目标规划最优化问题实际上是一个向量函数的优化问题，当m=1,多目标优化就是前面讲的单目标优化问题 三、解的概念

1.序的概念

12,.....()T

m a a a a = 12,.....()T

m

b b b b =

（1）b a =?a i

i

b = 1,2....i m = （2）a b ≤?a i i

b ≤ 1,2....i m = 称a 小于等于b

（3）a b <

=?a i i

b ≤ 且?1≤j ≤m ，使a j j b ≠，则a 小于向量b

（4）a

b < 1,2....i m = 称a 严格小于b

绝对最优解：设多目标最优化问题的可行域为D ，

*

x ∈D ,如果对

x ?D ∈,都有*()()F F x x <,则称*

x 为多目标最优化的绝对最优解，称绝对最优解的全体为绝对最优解集，记ab R ，absolute —绝对 有效解：可行域为D ，

*

x ∈D ,如果不存在x D ∈,使*

()()F F x x <

=，则称

*

x 为有效解，也称pareto 最优解，称有效解的全体为有效解集，记pa R 是由

1951年T.C.Koopmans 提出的。 弱有效解：可行域为D ， *

x ∈D ,如果不存在x D ∈,使*

()()F F x x <，则

称

*

x 为弱有效解，记wp R

，若有效解是

1959年kanlin 提出的。

四、解的性质：

定理8.1 对于多目标最优化问题，总有ab R ?pa R ，即绝对最优解必是有效解，并且当ab R φ≠，ab R =pa R 。 证明：先证ab R ?pa R 用反证法 设

*

x ∈ab

R

，但*

x ?pa R .由有效解的定义

可知,存在'x ∈D ，使*()()'F F x x <

=，即存在一个1i m ≤≤，使(')(*)i i f x f x <，

这与*x ∈ab R 矛盾，所以*x ∈pa R ，即ab R ?pa R .

当ab R φ≠，只需证明pa R ?ab R ，也用反证法，设"x ∈pa R ，使"x ?ab R ，由于ab R φ≠，"x ?ab R ，则存在一个x ∈ab R ，使()('')F x F x ≤，则至少存在一个i ，使1i m ≤≤，使得()('')i i f x f x <（否则()('')i i f x f x =，则()(")Fx Fx =，

"x ∈ab R ）

，这与"x ∈pa R 矛盾（"x 是有效解表示找不到比"x 更好的点） 所以pa R ?ab R 综合ab R =pa R 。

定理8.2 对于多目标最有优化问题，总有pa R ?wp R ，即有效解必是弱有效解.

证明：用反证法，设*x ∈pa R ，但*x ?wp R ，由弱有效解的定义知，?'x ∈p ,使(')(*)F x F x <，这与*x ∈pa R 矛盾，所以*x ∈wp R ，即pa R ?wp R . 定理8.3 如果记各分量目标函数()i f x 的最优解集为i R ，则有ab R =1m

i i R =

证明：设*x ∈ab R φ≠，则对x ?D ∈，都有(*)F x ≤()F x ，所以对

?1,2....i m =，有(*)()i i f x f x ≤，即*x ∈i R ，这就证明*x ∈1

m

i i R = ，上述推

到过程是可逆的，因此1

m i i R = ?ab R ，从而ab R =1

m i i R = ，当ab R φ≠，必有1

m

i i R = =φ，

否则由已证1

m

i i R = ?ab R ，可知ab R φ≠。

定理8.4 如果记各分量目标函数()i f x 的最优解集为i R ，则有i R ?wp R ，并且当ab R φ≠，wp R =1m

i i R = .

证明：先证i R ?wp R 设'x ∈i R ，但'x ?wp R ，由有效解的定义知，?"x ∈D ，使('')(')F x F x <，即?1,2....i m =，都有('')(')i i f x f x <，这与'x ∈i R 矛盾，所以'x ∈wp R ，即i R ?wp R

当ab R φ≠时，由i R ?wp R 可得1

m

i i R = ?wp R ，因此只需证明wp R ?1

m

i i R = ，用

反证法，设'''x ∈wp R ，但'''x ?1

m

i i R = ，即对1,2....i m =都有'''x ?i R ，另一方面

由ab R φ≠，可设*x ∈ab R ，则有*x ∈i R ，即(*)(''')i i f x f x <，所以(*)(''')F x F x <，这与'''x ∈wp R 矛盾，所以'''x ∈1

m

i i R = ，即wp R =1

m

i i R = .

§8.2评价函数法

评价函数法有：（1）理想点法（2）平方和加权法（3）极小极大法基本原理（4）乘除法基本原理（5）线性加权和法 一、理想点法

12min (,.....)T m F f f f =

.s t ()0g x ≥

()0h x =

设12****(,.....)m F f f f =为理想点，一般情况下，绝对最优解往往不存在。 1d = 1

1((()*))m

p p

i i i f x f =-∑ p 为范数

一般p =2时

1d =

1221

((()*))m

i i i f x f =-

∑

例1 max 112

()32f x x x =-+ max 212

()43f x x x =+ .st 1212121802320

x x x x x x +≤≤+≥，

解：先求 max 112()32f x x x =-+

.st 12121218

102320

x x x x x x +≤≤+≥，

*x =（0, 6） max 1

f =12

max 212()43f x x x =+

.st 12121218

02320

x x x x x x +≤≤+≥，

*x =（3,4） max 2f =24

故理想点为 F =（12，24）

min

22

1212

()()12243243x x x x -+--++

.st 12121218

102320

x x x x x x +≤≤+≥，

解之得

*x =(0.53,0.65)T 1

f =9.72，2f =19.06

可以证明理想点法求出的点是有效解。 例2 用理想点法求解 min 1124f x x -= min 2f =123x x +

.st 12121212

10230

x x x x x x +≤≤+≥，

解：min 1124f x x -=

12121212

10230

x x x x x x +≤≤+≥，

1(5,0)20f =

1(12,0)48

f = 1(0,12)12

f =- 110

1033

(0,)f =- 所以min 112f =- 10x = 212x =

2(5,0)5f = 2(12,0)12f = 2(0,12)36

f = 2103

(0,)10f =

所以min 2f =5 15x = 20x = 故理想点F =（-10

3

，0）

min 221212(4)()123x x x x --++

.st 12121212

10230

x x x x x x +≤≤+≥，

求出

1

2??x x ???

??

== 2.平方和加权法

平方和加权法也称虚拟目标法，共思想是构造一个很好的虚拟目标，然后它的目标函数值去逼近虚拟目标.

先对每个目标函数()i x f 确定一个想象的最好值0i f ，并使各目标函数与它的差的平方和最小，常取()i x f 极小值得下届作为0i f 021(())(())m

i i i i h F x w f x f ==-∑

1i w =∑

min

221121f x x =++

min 22212)2(f x x -=+

.s t 120x x ≥，

解： 1f =1， 2f =0

()h x =221122(()1)(()0)w f x w f x -+- 取1w =0.5，2w =0.5

min ()h x =2222221212)20.5()0.5()(x x x x -+++

.s t 120x x ≥，

利用MATLAB

求解：1201x x ???

??

== ()h x =1

可以证明这种方法求出的解是有效解.

3.极小—极大法

1()(())max i

i m f x h F x ≤≤= min (())h F x = 1())min (max i i m

x D

f x ≤≤∈ 例 min 1f =

110

2

(4)x + min 2f =1

2

2(2)x -

.s t 05x ≤≤

解： ()()()()222

1

2,0121

4,14

10

12,452x x h x x x x x ?-≤≤???=+≤≤???-≤≤??

()min h x

05x ≤≤

1

1,2

x h ?==

当

1x =时，10.5f =，2

12

f =

4.乘除法 买糖问题 1123min 4 2.8 2.4f x x x =++

2123max f x x x =++

.S T

123123121234 2.8 2.4206

3,,0

x x x x x x x x x x x ++≤++≥+≥≥

()123

121234 2.8 2.4min x x x f h x f x x x ++==

++

.

st 123123121234 2.8 2.42063,,0

x x x x x x x x x x x ++≤++≥+≥≥

解之得：1

240,3,3x x x ===

5.线性加权和法

线性加权和法是最容易理解的评价函数法，根据各目标函数的重要程度构造评价函数

()()()1

m

i i i h F x w f x ==∑

其中i w 为权函数，满足0,1,2,3......i w i m ≥=，且1

1m

i i w ==∑

然后求解 ()()()1

m i n m i n m

i i x D

x D

i h F x w f x ∈∈==∑

例1. ()()()2211min min 4,44102f x x x x ??

=+-+????

.s t

05x ≤≤ 利用线性加权和法求解

解： ()()()2

21

2

44410

2

h x x x x λλ=

++

-+

（1） 若120.5,0.5λλ==时

()()()22min 0.0540.2544h x x x x =++-+

()

0.610df x x dx

=-= 5

1.66673

x =≈

0.3667h =

（2） 若120.8,0.2λλ==，同理可得

1.1111x =， 0.4977

h = []0,2pa R =，两种做法的结果都属于有效解。

例2. 利用线性加权和法求解问题，买糖问题

1123min 4 2.8 2.4y x x x =++

2123max y x x x =++

.S T 123123121234 2.8 2.4206

3

,,0

x x x x x x x x x x x ++≤++≥+≥≥

取1

20.5w w ==，()()()1231230.54 2.8 2.40.5h x x x x x x x =++-++

.st 123123121234 2.8 2.4206

3

,,0

x x x x x x x x x x x ++≤++≥+≥≥

可得1230,3,3x x x ===， 4.8h =

161P 第3题112min 4f x x =-，212min 3f x x =+

.

st

12121212

2310,0

x x x x x x +≤+≤≥

可行域为D ，若120.5,0.5w w ==

()()121212111

435222

h x x x x x x =-++=?+

()()2510100,00,5,0,0,233

h h h ??=== ???

12120,0,0,0x x f f ====

()0,0x *=，而pa R OD =,可得pa x R *∈

定义：设1:,m m

h R R F R →∈

（1） 若12

F F ≤时，总有()()12

h F h F ≤，则称h 为严格单增函数；

（2） 若12

F F <时，总有()

()12h F h F <,则称h 为单增函数。 定理8.5 （1）如果h 是严格单增函数，则由评价函数法得到的解是原多目标最优化问题的有效解；

（2）如果h 是单增函数，则由评价函数得到的解是弱有效解。

证明：（1）若x *

是()min h x 的最优解，用反证法，假设x *

不是多目标规划

()min F x 的有效解，即pa x R *

?

由定义可知，有.st

x D ∈，有()()1F x F x *

≤

()h x 是严格单增函数，所以()()()()

1h F x h F x *<

这与x *

是评价函数的最优解相矛盾，故pa x R *∈

（2）若x *

是评价函数法的最优解，用反证法，假设wp x R *?，由定义可知，

存在一点1x D ∈，使()()1F x F x *<

()h x 是单增函数，则()()()()1h F x h F x *<

这与x *

是评价函数的最优解矛盾，故wp x R *?

§8.3 分层求解法

可以把目标函数分成优化级，分第一层、分第二层、分第三层再逐步求解； 例1.用分层求解法求

112

212

m i n m i n 2f x x f x x =-=-+

.st 121

2

1

,0x x x x

+≤≥

1f 比2f 更重要，取0.1δ=

解：（1）先求 112min f x x =-

.st 1212

1

,0

x x x x +≤≥

()10,00f =，()11,01f =，()10,11f =- B 点最优解，11f =- （2）取0.1δ=

1210.10.9x x -≤-+=-

()2212min 2f B f x x ==-+

.st 1212120.9

1

,0

x x x x x x -≤-+≤≥

()()()2222, 1.8, 1.85f B f C f D ===

C 点为最优点：12210,0.9, 1.8,0.9x x f f ====-

综合可得：12120,0.9,0.9, 1.8x x f f ===-=

例2.

161.4P 用分层求解法求

112

212min 2min 2f x x f x x =-+=+

.st

122122

1,0

x x x x x +≤≤≥

假设目标1f 比2f 重要，1δ= 解：（1）112min 2f x x =-+

.st 122122

1

,0

x x x x x +≤≤≥

()()()()11110,00,2,04,1,11,0,11f f f f ==-=-=

112min 4,2,0f x x =-==（A 是最优）

（2）取1δ=

212min 2f x x =+

.st 1212212232

1

,0

x x x x x x x -+≤-+≤≤≥

()22233517,0,2,02,,22333

f f f ????=== ? ????? 所以121233,0,3,22

x x f f ===-=

而理想点为（-4,0），实际求得为（-3，

3

2

）其中123

,0,2

x x δ==的取值不同

从而导致结果不同。

可以证明分层求解法求出的解是有效解或弱有效解。

浅析多目标优化问题

浅析多目标优化问题 【摘要】本文介绍了多目标优化问题的问题定义。通过对多目标优化算法、评估方法和测试用例的研究，分析了多目标优化问题所面临的挑战和困难。 【关键词】多目标优化问题；多目标优化算法；评估方法；测试用例 多目标优化问题MOPs （Multiobjective Optimization Problems）是工程实践和科学研究中的主要问题形式之一，广泛存在于优化控制、机械设计、数据挖掘、移动网络规划和逻辑电路设计等问题中。MOPs有多个目标，且各目标相互冲突。对于MOPs，通常存在一个折衷的解集（即Pareto最优解集），解集中的各个解在多目标之间进行权衡。获取具有良好收敛性及分布性的解集是求解MOPs的关键。 1 问题定义 最小化MOPs的一般描述如下： 2 多目标优化算法 目前，大量算法用于求解MOPs。通常，可以将求解MOPs的算法分为两类。 第一类算法，将MOPs转化为单目标优化问题。算法为每个目标设置权值，通过加权的方式将多目标转化为单目标。经过改变权值大小，多次求解MOPs 可以得到多个最优解，构成非支配解集[1]。 第二类算法，直接求解MOPs。这类算法主要依靠进化算法。进化算法这种面向种群的全局搜索法，对于直接得到非支配解集是非常有效的。基于进化算法的多目标优化算法被称为多目标进化算法。根据其特性，多目标进化算法可以划分为两代[2]。 （1）第一代算法：以适应度共享机制为分布性策略，并利用Pareto支配关系设计适应度函数。代表算法如下。VEGA将种群划分为若干子种群，每个子种群相对于一个目标进行优化，最终将子种群合并。MOGA根据解的支配关系，为每个解分配等级，算法按照等级为解设置适应度函数。NSGA采用非支配排序的思想为每个解分配虚拟适应度值，在进化过程中，算法根据虚拟适应度值采用比例选择法选择下一代。NPGA根据支配关系采用锦标赛选择法，当解的支配关系相同时，算法使用小生境技术选择最优的解进入下一代。 （2）第二代算法：以精英解保留机制为特征，并提出了多种较好的分布性策略。代表算法如下。NSGA-II降低了非支配排序的复杂度，并提出了基于拥挤距离的分布性策略。SPEA2提出了新的适应度分配策略和基于环境选择的分布性策略。PESA-II根据网络超格选择个体并使用了基于拥挤系数的分布性策略。

多目标规划

ricanxinghuji实习小编一级|消息 | 我的百科 | 我的知道 | 百度首页 | 退出我的贡献草稿箱我的任务为我推荐 新闻网页贴吧知道MP3图片视频百科文库 帮助设置 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 多目标规划 科技名词定义 中文名称：多目标规划 英文名称：multiple objective program 定义：生态系统管理中，为了同时达到两个或两个以上的目标，需要在许多可行性方案中进行选择的整个过程。 所属学科：

生态学（一级学科）；生态系统生态学（二级学科） 本内容由全国科学技术名词审定委员会审定公布 多目标规划是数学规划的一个分支。研究多于一个的目标函数在给定区域上的最优化。又称多目标最优化。通常记为 MOP(multi-objective programming)。 目录 编辑本段 多目标规划 multiple objectives programming 数学规划的一个分支。研究多于一个目标函数在给定区域上的最优化。又称多目标最优化。通常记为 VMP。在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量 多目标规划

一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年法国经济学家 V. 帕雷托最早研究不可比较目标的优化问题，之后，J.冯·诺伊曼、H.W.库恩、A.W.塔克尔、A.M.日夫里翁等数学家做了深入的探讨，但是尚未有一个完全令人满意的定义。求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法等；另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解；还有一种称为层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。 编辑本段 规划简史 多目标最优化思想，最早是在1896年由法国经济学家V.帕雷托提出来的。他从政治 数学规划 经济学的角度考虑把本质上是不可比较的许多目标化成单个目标的最优 化问题，从而涉及了多目标规划问题和多目标的概念。1947年，J.冯·诺伊曼和O.莫根施特恩从对策论的角度提出了有多个决策者在彼此有矛盾的情 况下的多目标问题。1951年，T.C.库普曼斯从生产和分配的活动中提出多目标最优化问题，引入有效解的概念，并得到一些基本结果。同年，H.W.库恩和 A.W.塔克尔从研究数学规划的角度提出向量极值问题,引入库恩-塔克尔有效解概念，并研究了它的必要和充分条件。1963年，L.A.扎德从控制论方面提出多指标最优化问题，也给出了一些基本结果。1968年，A.M.日夫里翁为了排除变态的有效解，引进了真有效解概念，并得到了有关的结果。自70年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。 编辑本段 求解方法 化多为少的方法 即

多目标优化问题

多目标优化方法 基本概述 几个概念 优化方法 一、多目标优化基本概述 现今,多目标优化问题应用越来越广,涉及诸多领域。在日常生活与工程中,经常要求不只一项指标达到最优,往往要求多项指标同时达到最优,大量的问题都可以归结为一类在某种约束条件下使多个目标同时达到最优的多目标优化问题。例如:在机械加工时,在进给切削中,为选择合适的切削速度与进给量,提出目标:1)机械加工成本最低2)生产率低3)刀具寿命最长;同时还要满足进给量小于加工余量、刀具强度等约束条件。 多目标优化的数学模型可以表示为: X=[x1,x2,…,x n ]T----------n维向量 min F(X)=[f1(X),f2(X),…,f n(X)]T----------向量形式的目标函数s、t、g i(X)≤0,(i=1,2,…,m) h j(X)=0,(j=1,2,…,k)--------设计变量应满足的约束条件多目标优化问题就是一个比较复杂的问题,相比于单目标优化问题,在多目标优化问题中,约束要求就是各自独立的,所以无法直接比较任意两个解的优劣。 二、多目标优化中几个概念:最优解,劣解,非劣解。 最优解X*:就就是在X*所在的区间D中其函数值比其她任何点的函数

值要小即f(X*)≤f(X),则X*为优化问题的最优解。 劣解X*:在D中存在X使其函数值小于解的函数值,即f(x)≤f(X*), 即存在比解更优的点。 非劣解X*:在区间D中不存在X使f(X)全部小于解的函数值f(X*)、 如图:在[0,1]中 X*=1为最优解 在[0,2]中 X*=a为劣解 在[1,2]中 X*=b为非劣解 多目标优化 问题中绝对最优 解存在可能性一般很小,而劣解没有意义,所以通常去求其非劣解来解决问题。 三、多目标优化方法 多目标优化方法主要有两大类: 1)直接法:直接求出非劣解,然后再选择较好的解 将多目标优化问题转化为单目标优化问题。 2)间接法如:主要目标法、统一目标法、功效系数法等。 将多目标优化问题转化为一系列单目标优化问题。 如:分层系列法等。

多目标最优化问题全面介绍

§8.1多目标最优化问题的基本原理 一、多目标最优化问题的实例 例1 梁的设计问题 设用直径为1的圆木加工成截面积为矩形的梁，为使强度最大而成本最低， 问应如何设计梁的尺寸？ 解： 设梁的截面积宽和高分别为1x 和2x 强度最大=惯性矩最大 2 216 1x x = 成本最低=截面积最小=21x x 故数学模型为： min 1 x 2 x max 2216 1x x .s t 221 2 1x x += 10x ≥，20x ≥ 例2 买糖问题 已知食品店有1A , 2 A , 3 A 三种糖果单价分别为4元∕公斤，2.8元∕公斤， 2.4元∕公斤，今要筹办一次茶话会，要求用于买买糖的钱不超于20元，糖 的总量不少于6公斤，1A ， 2 A 两种糖的总和不少于3公斤，问应如何确定买糖的最佳方案？ 解：设购买1A , 2 A , 3 A 三种糖公斤数为1x ，2x ，3x 1 A 2 A 3 A 重量 1x 2x 3x 单价 4元∕公斤 2.8元∕公斤 2.4元∕公斤 min 14x +22.8x +3 2.4x （用钱最省）

max 1x +2x +3x （糖的总量最多） .st 14x +22.8x +3 2.4x 20≤ (用钱总数的限制) 1x +2x +3x 6≥（用糖总量的要求） 1x +2x 3≥（糖品种的要求） 1x ，2x ，3x 0≥ 是一个线性多目标规划。 二、 多目标最优化的模型 12min ()((),(),.....())T m V F x f x f x f x -= .st ()0g x ≥ ()0h x ≥ 多目标规划最优化问题实际上是一个向量函数的优化问题，当m=1,多目标优化就是前面讲的单目标优化问题 三、解的概念 1.序的概念 12,.....()T m a a a a = 12,.....()T m b b b b = （1）b a =?a i i b = 1,2....i m = （2）a b ≤?a i i b ≤ 1,2....i m = 称a 小于等于b （3）a b < =?a i i b ≤ 且?1≤j ≤m ，使a j j b ≠，则a 小于向量b （4）a

Excel规划求解工具在多目标规划中的应用

Excel规划求解工具在多目标规划中的应用 摘要：多目标决策方法是从20世纪70年代中期发展起来的一种决策分析方法。该方法已广泛应用于人口、环境、教育、能源、交通、经济管理等多个领域。文章采用多目标决策方法中分层序列法的思想，应用excel的规划求解工具，对多目标规划问题进行应用研究，并以实例加以说明。 abstract： multi-objective decision method is a kind of decision analysis method from the mid 1970s. the method has been widely used in population， environment， education，energy， traffic， economic management， and other fields. this paper uses the lexicographic method of multi-objective decision method and makes some researches on the multi-objective problem using the excel solver tool and an example to illustrate. 关键词： excel规划求解；多目标规划；分层序列法 key words： excel solver；multi-objective programming；the lexicographic method 中图分类号：tp31 文献标识码：a 文章编号：1006-4311（2013）21-0204-02 0 引言 excel中的规划求解工具只能对单目标的问题进行求解。当遇到多目标问题时，可以把多目标问题先转化为单目标问题，然后求解。

LINGO在多目标规划和最大最小化模型中的应用

LINGO 在多目标规划和最大最小化模型中的应用 在许多实际问题中，决策者所期望的目标往往不止一个，如电力网络管理部门在制定发电计划时即希望安全系数要大，也希望发电成本要小，这一类问题称为多目标最优化问题或多目标规划问题。 一、多目标规划的常用解法 多目标规划的解法通常是根据问题的实际背景和特征，设法将多目标规划转化为单目标规划，从而获得满意解，常用的解法有： 1．主要目标法 确定一个主要目标，把次要目标作为约束条件并设定适当的界限值。 2．线性加权求和法 对每个目标按其重要程度赋适当权重0≥i ω，且1=∑i i ω，然后把) (x f i i i ∑ω作为新的目标函数（其中p i x f i ,,2,1),( =是原来的p 个目标）。 3．指数加权乘积法 设p i x f i ,,2,1),( =是原来的p 个目标，令 … ∏==p i a i i x f Z 1 )]([ 其中i a 为指数权重，把Z 作为新的目标函数。 4．理想点法 先分别求出p 个单目标规划的最优解*i f ，令 ∑-= 2*))(()(i i f x f x h 然后把它作为新的目标函数。 5．分层序列法 将所有p 个目标按其重要程度排序，先求出第一个最重要的目标的最优解，然后在保证前一个目标最优解的前提条件下依次求下一个目标的最优解，一直求到最后一个目标为止。

这些方法各有其优点和适用的场合，但并非总是有效，有些方法存在一些不足之处。例如，线性加权求和法确定权重系数时有一定主观性，权重系数取值不同，结果也就不一样。线性加权求和法、指数加权乘积法和理想点法通常只能用于两个目标的单位（量纲）相同的情况，如果两个目标是不同的物理量，它们的量纲不相同，数量级相差很大，则将它们相加或比较是不合适的。 二、最大最小化模型 在一些实际问题中，决策者所期望的目标是使若干目标函数中最大的一个达到最小（或多个目标函数中最小的一个达到最大）。例如，城市规划中需确定急救中心的位置，希望该中心到服务区域内所有居民点的距离中的最大值达到最小，称为最大最小化模型，这种确定目标函数的准则称为最大最小化原则，在控制论，逼近论和决策论中也有使用。 》 最大最小化模型的目标函数可写成 )}(,),(),(max{min 21X f X f X f p X 或 )}(,),(),(min{max 21X f X f X f p X 式中T n x x x X ),,,(21 是决策变量。模型的约束条件可以包含线性、非线性的等式和不等式约束。这一模型的求解可视具体情况采用适当的方法。 三、用LINGO 求解多目标规划和最大最小化模型 1．解多目标规划 用LINGO 求解多目标规划的基本方法是先确定一个目标函数，求出它的最优解，然后把此最优值作为约束条件，求其他目标函数的最优解。如果将所有目标函数都改成约束条件，则此时的优化问题退化为一个含等式和不等式的方程组。LINGO 能够求解像这样没有目标函数只有约束条件的混合组的可行解。有些组合优化问题和网络优化问题，因为变量多，需要很长运算时间才能算出结果，如果设定一个期望的目标值，把目标函数改成约束条件，则几分钟就能得到一个可行解，多试几个目标值，很快就能找到最优解。对于多目标规划，同样可以把多个目标中的一部分乃至全部改成约束条件，取适当的限制值，然后用LINGO 求解，

多目标优化的求解方法

多目标优化的求解方法 多目标优化(MOP)就是数学规划的一个重要分支,就是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下: 多目标优化方法本质就是将多目标优化中的各分目标函数,经处理或数学变换,转变成一个单目标函数,然后采用单目标优化技术求解。目前主要有以下方法: （1）评价函数法。常用的方法有:线性加权与法、极大极小法、理想点法。评价函数法的实质就是通过构造评价函数式把多目标转化为单目标。 (2)交互规划法。不直接使用评价函数的表达式,而就是使决策者参与到求解过程,控制优化的进行过程,使分析与决策交替进行,这种方法称为交互规划法。常用的方法有:逐步宽容法、权衡比替代法,逐次线性加权与法等。 (3)分层求解法。按目标函数的重要程度进行排序,然后按这个排序依次进行单目标的优化求解,以最终得到的解作为多目标优化的最优解。 而这些主要就是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法与蚁群算法、模拟退火算法及人工免疫系统等。 在工程应用、生产管理以及国防建设等实际问题中很多优化问题都就是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其她若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少与总的运输费用最低, 这就是含有两个目标的优化问题。利用首次适配递减算法与标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合

多目标最优化模型

第六章 最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值 2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法 4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法 5．5 投资收益风险问题 第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X 表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设

多目标最优化模型

第六章最优化数学模型 §1最优化问题 1．1最优化问题概念 1．2最优化问题分类 1．3最优化问题数学模型 §2经典最优化方法 2．1无约束条件极值 2．2等式约束条件极值 2．3不等式约束条件极值 §3线性规划 3．1线性规划 3．2整数规划 §4最优化问题数值算法 4．1直接搜索法 4．2梯度法 4．3罚函数法 §5多目标优化问题 5．1多目标优化问题 5．2单目标化解法 5．3多重优化解法 5．4目标关联函数解法 5．5投资收益风险问题 第六章最优化问题数学模 §1最优化问题 1．1最优化问题概念 （1）最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值； ②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。 一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为x1,x2, , x n ；我们常常也用X （x1,x2, ,x n）表示。 3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设

多目标最优化数学模型

第六章最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法5．5 投资收益风险问题

第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X =表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。 用数学语言描述约束条件一般来说有两种： 等式约束条件 m i X g i ,,2,1,0)( == 不等式约束条件 r i X h i ,,2,1, 0)( =≥ 或 r i X h i ,,2,1, 0)( =≤ 注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件0)(>X h 或0)(

多目标优化问题

多目标优化方法 基本概述几个概念优化方法 一、多目标优化基本概述 现今，多目标优化问题应用越来越广，涉及诸多领域。在日常生活和工程中，经常要求不只一项指标达到最优，往往要求多项指标同时达到最优，大量的问题都可以归结为一类在某种约束条件下使多个目标同时达到最优的多目标优化问题。例如：在机械加工时，在进给切削中，为选择合适的切削速度和进给量，提出目标：1)机械加工 成本最低2)生产率低3)刀具寿命最长；同时还要满足进给量小于加工余量、刀具强度等约束条件。 多目标优化的数学模型可以表示为： X=[x i,x 2,…,x n ] T ---------------------------------- n 维向量 min F(X)=[f i(X),f 2(X),…,f n(X)] T- --------- 向量形式的目标 函数 s.t. g i(X) < 0,(i=1,2,…,m) h j (X)=0,(j=1,2,…,k) ------ 设计变量应满足的约 束条件 多目标优化问题是一个比较复杂的问题，相比于单目标优化问题，在 多目标优化问题中，约束要求是各自独立的，所以无法直接比较任意两个解的优劣。 二、多目标优化中几个概念：最优解，劣解，非劣解。 最优解X*:就是在乂所在的区间D中其函数值比其他任何点的函数值要小即f(X *)

如图：在［0,1］ 中 X*=1为最优解 在［0,2］ 中X*=a为劣解 在［1,2］ 中X*=b为非劣解 多目标优化问 题中绝对最优解存 在可能性一般很 小，而劣解没有 意义，所以通常去 求其非劣解来解决 问题。 三、多目标优化方法 多目标优化方法主要有两大类： 1)直接法：直接求出非劣解，然后再选择较好的解 将多目标优化问题转化为单目标优化问题。 2)间接法女口：主要目标法、统一目标法、功效系数法等。 将多目标优化问题转化为一系列单目标优化问题。女口：分层系列法等。 1、主要目标法 求解时从多目标中选择一个目标作为主要目标，而其他目标只需满足一定要求即可，因此可将这些目标转化成约束条件，也就是用约束条件的形式保证其他目标不致太差，这样就变成单目标处理方法。 例如：多目标函数f 1(X),f 2(X),.?…,f n(X)中选择f k(X)作为主 要目标，这时问题变为求min f k(x) D={x|f min < f i(X)< f ma》,D为解所对应的其他目标函数应满足上下限。 2、统一目标法 通过某种方法将原来多目标函数构造成一个新的目标函数，从而将多目标函数转变为单目标函数求解。 ①线性加权和法 根据各目标函数的重要程度给予相应的权数，然后各目标函数与

多目标优化的求解方法

多目标优化的求解方法 多目标优化（MOP）是数学规划的一个重要分支，是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下： 多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。目前主要有以下方法： （1）评价函数法。常用的方法有:线性加权和法、极大极小法、理想点法。评价函数法的实质是通过构造评价函数式把多目标转化为单目标。 （2）交互规划法。不直接使用评价函数的表达式，而是使决策者参与到求解过程，控制优化的进行过程，使分析和决策交替进行，这种方法称为交互规划法。常用的方法有：逐步宽容法、权衡比替代法，逐次线性加权和法等。 （3）分层求解法。按目标函数的重要程度进行排序，然后按这个排序依次进行单目标的优化求解，以最终得到的解作为多目标优化的最优解。 而这些主要是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法及人工免疫系统等。

在工程应用、生产管理以及国防建设等实际问题中很多优化问题都是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其他若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少和总的运输费用最低, 这是含有两个目标的优化问题。利用首次适配递减算法和标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合应用于汽车零件多工序冷挤压工艺的优化。Chung等人也成功应用遗传算法对锻件工艺进行了优化。 3)投资 假设某决策部门有一笔资金要分配给若干个建设项目, 在确定投资方案时, 决策者总希望做到投资少收益大。Branke等人采用基于信封的多目标进化算法成功地解决了计划投资地选择问题。 4)模拟移动床过程优化与控制 一个工业化模拟移动床正常运行时, 一般有七股物料进、出吸附塔, 其中起关键作用的物料口将作为决策量引起目标值的变化。根据实际生产要求通常包括生产率、产品纯度、吸附剂消耗量等多个目标。模拟移动床分离过程由于其过程操作变量的强耦合性、工艺机理的复杂性及分离性能的影响因素繁多性, 需要众多学者对其操作优化和过程控制进行深入的研究。Huang等人利用TPS 算法解决了模拟移动床多个冲突目标的最大最小的问题, 并与NSGA2 算法的结果进行了比较。吴献东等人运用粒子群算法开发出一种非线性模拟移动床( SMB )色谱分离过程的优化策略。 5)生产调度 在离散制造生产系统中, 一个工件一般经过一系列的工序加工完成, 每道工序需要特定机器和其他资源共同完成, 各工件在各机器上的加工顺序(称技术约束条件)通常是事先给定的。车间调度的作用

多目标优化问题教学提纲

多目标优化问题

多目标优化方法 基本概述 几个概念 优化方法 一、多目标优化基本概述 现今，多目标优化问题应用越来越广，涉及诸多领域。在日常生活和工程中，经常要求不只一项指标达到最优，往往要求多项指标同时达到最优，大量的问题都可以归结为一类在某种约束条件下使多个目标同时达到最优的多目标优化问题。例如：在机械加工时，在进给切削中，为选择合适的切削速度和进给量，提出目标：1）机械加工成本最低2）生产率低3）刀具寿命最长；同时还要满足进给量小于加工余量、刀具强度等约束条件。 多目标优化的数学模型可以表示为： X=[x1,x2,…,x n ]T ----------n维向量 min F(X)=[f1(X),f2(X),…,f n(X)]T----------向量形式的目标函数 s.t. g i(X)≤0,(i=1,2,…,m) h j(X)=0,(j=1,2,…,k)--------设计变量应满足的约束条件 多目标优化问题是一个比较复杂的问题，相比于单目标优化问题，在多目标优化问题中，约束要求是各自独立的，所以无法直接比较任意两个解的优劣。

二、多目标优化中几个概念：最优解，劣解，非劣解。 最优解X*：就是在X*所在的区间D中其函数值比其他任何点的函数值要小即f(X*)≤f(X)，则X*为优化问题的最优解。 劣解X*：在D中存在X使其函数值小于解的函数值，即f(x)≤f(X*), 即存在比解更优的点。 非劣解X*：在区间D中不存在X使f(X)全部小于解的函数值f(X*). 如图：在[0,1]中X*=1为最优解 在[0,2]中X*=a为劣解 在[1,2]中X*=b为非劣解 多目标优化问题中绝对最优解存在可能性一般很小，而劣解没有意义，所以通常去求其非劣解来解决问题。

多目标优化问题(over)

第七章多目标优化问题的求解 优化问题按照目标函数的数量，可以分为单目标优化问题和多目标优化问题，前面我们讲过的线性优化就是一个单目标优化问题，对单目标优化问题进一步突破，将目标函数扩展为向量函数后，问题就转化为多目标优化问题。本节将简要介绍多目标最优化问题的建模与求解方法。 1、多目标优化模型 多目标优化问题一般表示为 ..()min () s t J ≤= x G x 0 x F 其中121()[(),(),,()]T f f f =F x x x x ，下面将通过例子演示多目标优化问题的建模。 例1 设某商店有123,,A A A 三种糖果，单价分别为4,2.8和2.4元/kg ，现在 要举办一次茶话会，要求买糖果的钱不超过20元，但糖果的总重量不少于6kg ， 1A 和2A 两种糖果的总重量不低于3kg ，应该如何确定最好的买糖方案。 分析：首先应该确定目标函数如何选择的问题，本例中，好的方案意味着少花钱多办事，这应该是对应两个目标函数，一个是花钱最少，一个是买的糖果最重，其他的可以认为是约束条件。当然，这两个目标函数有些矛盾，下面考虑如何将这个问题用数学描述。 设123,,A A A 三种糖果的购买重量分别为123,,x x x kg ，这时两个目标函数分别为花钱：1123min ()4 2.8 2.4f x x x =++x ，糖果总重量：2123max ()f x x x =++x ，如果统一用最小值问题表示，则有约束的多目标优化问题可以表示为 123123123123121234 2.8 2.4min -4 2.8 2.4206.. +3,,0 x x x x x x x x x x x x s t x x x x x ++?? ??++??++≤??++≥?? ≥??≥?（）模型建立以后，可以考虑用后面的方法进行求解。