运筹学 多目标规划

运筹学 多目标规划

多目标规划马建华博士副教授管理科学与工程学院 majh@http://www.77cn.com.cn

运筹学 多目标规划

动态规划

马建华

多目标规划多目标决策问题多目标规划目的规划层次分析法

2010-4-24

运筹学 多目标规划

动态规划

马建华

多目标决策问题应用实例问题模型问题特征

返回2010-4-24 3

运筹学 多目标规划

动态规划

马建华

多目标规划问题某市计划发展委员会安排下一个年度的重大项目规划，计划一年安排总投资不超过8亿元，经过初期筛选选中12项可供考虑，每个项目需要投资的数量(单位千万元)、建成后的年利润(单位千万元)、每年废物排放量 (单位万吨)和租用的劳动力(单位千人)如下表所示，为了保护环境该市签订了环保责任书，承诺新增废物量不超过20万吨，从经济的角度要求利润尽可能的高，从社会发展的角度讲要求新增就业岗位尽量多，问应如何选择投资项目？

2010-4-24

运筹学 多目标规划

动态规划

马建华

项目投资利润废物劳动力

1 2.4 0.4 0.3 0.6

2 5.2 1 2 1.1

3 11 3 3 2

4 6.2 2 3 2.8

5 17 4 3 1.5

6 21 5 5 2.6

7 3.5 0.7 1 0.7

8 6.1 1.5 0.5 1.5

9 4.8 1.2 1.4 1

10 15 4 2 2

11 8.5 2.3 2 1

12 30 6 4 1.2

2010-4-24

运筹学 多目标规划

动态规划

马建华

问题分析是否投资总投资额总利润废物排放总量劳动力使用总量

xi12

投资 x i= 1 i= 1,2,...,12

∑ ai xii=1

∑ bi xi i=1∑ ci xii=1 12

12

∑ d i xi i=12010-4-24 6

12

运筹学 多目标规划

动态规划

马建华

模型max∑ bi xii=1 12 12

max∑ d i xii=1

12 ∑ a i xi≤ 80 i=1 12 s.t. ∑ ci xi≤ 20 i=1 x i= 0,1, i= 1,2,...,12 2010-4-24 7

运筹学 多目标规划

动态规划

马建华

特征 约束是线性整数约束； 目标有两个，均为线性函数； 都为求最大

2010-4-24

运筹学 多目标规划

动态规划

马建华

有效解多目标的难点有效解弱有效解

2010-4-24

运筹学 多目标规划

动态规划

马建华

多目标的难点绝对最优解—使每个目标都达到最优的可行解

2010-4-24

运筹学 多目标规划

动态规划

马建华

绝对最优解不一定存在不同的目标在不同的可行解上达到最优

2010-4-24

运筹学 多目标规划

动态规划

马建华

有效解若对于某个可行解x不存在可行解y使得

F ( y )≤ F ( x)

则称可行解x为有效解

2010-4-24

运筹学 多目标规划

动态规划

马建华

弱有效解若对于某个可行解x不存在可行解y使得 F ( y )< F ( x)则称可行解x为弱有效解弱有效解包含有效解

2010-4-24

运筹学 多目标规划

动态规划

马建华

求解有效解的方法理想点法平方和加权法虚拟目标法线性加权和法最小最大法乘除法优先级法

2010-4-24

运筹学 多目标规划

动态规划

马建华

理想点法以单目标最优值为理想值使函数与理想值的差的平方和最小

求理想值写出评价函数求评价函数最优

f j*= min f j ( x), j= 1,2,..., px∈S

h( F )=

∑ ( f j f j* ) 2j=1

p

min h( F )= min∑ ( f j f j* ) 2x

∈S x∈S j=1

p

2010-4-24

运筹学 多目标规划

动态规划

马建华

平方和加权法使函数与某一下界的差的平方和最小确定下界写出评价函数求评价函数最优f j*≤ min f j ( x), j= 1,2,..., px∈S

h( F )=∑ ( f j f j* ) 2j=1

p

min h( F )= min∑ ( f j f j* ) 2x∈S x∈S j=1

p

2010-4-24