122
§17.借助于Matlab 用贯序算法求解目标规
划问题
虽然Matlab 没有提供直接求解目标规划的优化工具，但是根据目标规划的求解思路——单纯形方法。我们可以将一个目标规划问题分解成若干线性规划问题，通过序贯式算法借助于Matlab 优化工具进行求解。
例1：教材第6章第3节中的目标规划问题：
-
+
-
+
+++=3
322211)(min d p d d p d p Z
11221≤+x x
01121=-+-+
-
d d x x
10
22221=-+++
-d d x x
56
1083321=-+++
-d d x x
)
3,2,1(0
,,,21=≥+
-i d d x x i i
首先将上述问题化为标准形式：
-
+
-
+
+++=3
322211)(min d p d d p d p Z
112321=++x x x
01121=-+-+
-d d x x
123
10
22221=-+++
-d d x x
56
1083321=-+++
-d d x x
)
3,2,1(0
,,=≥+
-i d d x i i i
然后按照以下步骤分解计算： 第一步：求解如下线性规划问题：
min d1
2x1+x2+x3=11
x1-x2+d1_-d1=0
x1,x2,x3>=0,d1_>=0,d1>=0
对上述线性规划问题，可以借助于Matlab 优化工具中的linprog 函数求解，函数调用命令为：
[x,fval]=linprog(f,[],[],Aeq,beq,lb,[]) 其中，参数如下：
Aeq= 2 1 1 0 0 0 0 0 0 1 -1
1
-1
beq=
11 0
f=
0 0 0 1 0 0 0 0
lb=
0 00000000
运行后，得求解结果如下：
Optimization terminated successfully.
x =
0.1645
6.0628
4.6083
267.4155
261.5173
fval =
即：d1＝0
第二步：求解如下线性规划问题：
min d2_+d2
2x1+x2+x3=11
x1-x2+d1_-d1=0
x1+2x2+d2_-d2=10
d1=0
x1,x2,x3>=0,d1_>=0,d1>=0,d2_>=0,d2>=0
对上述线性规划问题，可以借助于Matlab优化工具中的linprog函数求解，函数调用命令为：
[x,fval]=linprog(f,[],[],Aeq,beq,lb,[],x0)
其中，参数如下：
124
Aeq=
211000000
1-101-10000
120001-100
000010000
beq=
11
10
f=
0 00001100
lb=
0 00000000
x0=
0.1645
6.0628
4.6083
267.4155
261.5173
运行后，得求解结果如下：
x =
0.0577
4.9712
5.9135
4.9135
0.0000
0.0000
125
fval =
5.1844e-010
即：d2_＋d2＝5.1844e-010≈0
第三步：求解如下线性规划问题：
min d3_
2x1+x2+x3=11
x1-x2+d1_-d1=0
x1+2x2+d2_-d2=10
8x1+10x2+d3_-d3=56
d1=0
d2_+d2=0
x1,x2,x3>=0; d1_>=0,d1>=0,d2_>=0,d2>=0,d3_>=0,d3>=0
对上述线性规划问题，可以借助于Matlab优化工具中的linprog函数求解，函数调用命令为：
[x,fval]=linprog(f,[],[],Aeq,beq,lb,[],x0)
其中，参数如下：
Aeq=
211000000
1-101-10000
120001-100
810000001-1
000010000
000001100
beq=
11
10
126
56
f=
0 00000010
lb=
0 00000000
x0=
0.0577
4.9712
5.9135
4.9135
运行后，输出结果如下：
x =
2.2793
3.8603
2.5810
1.5810
0.0000
0.0000
0.0000
0.8380
fval =
3.6940e-013
最后得到如下一组满意解：
2.2793
3.8603
127
128
2.581 1.581 0 0 0 0 0.838
可以看出，以上求解的满意解方案不同于用Lindo 软件求得的结果。这是因为，该问题本身有多重解，而linprog 函数求解算法又不同于Lindo 的缘故。有兴趣的读者可以进一步验证，上述解和借助于Lindo 软件用贯序方法求解的结果都是满意解方案。
例2：教材第6章第4节中的目标规划问题，土地利用问题：
)
()(min 222111+
-
+
-
+++=d d P d d P Z
耕地面积约束：
???
??=++=++=++200
x x x 300x x x 100
x x x 332313
322212312111
最低收获量约束：
???
??≥++≥++≥++35000010000x 12000x 14000x 0000310x 0066800x 8000x 1900009000x 9500x 11000x 333231232221131211
目标约束为：
6100000
(X) 111=-++
d d f -
129
6600000
(X) 222=-++
d d f -
即：
6100000
10000x
12000x
14000x +0x
0066800x
8000x
+ 9000x
9500x
11000x 1133
32
31
23
22
21
13
12
11
=-++++++++
-
d d
00
660000x
0089600x
11200x
9000x
10200x
12000x
10800x 11400x
13200x 2233
32
31
23
22
21131211
=-++++++++++
-
d d
非负约束：
1,2,3)
j 1,2,3;(i 0
x ij ==≥
,00,0,2211≥≥≥≥+
-+-d d d d
对于上述目标规划问题，可以按照如下两个步骤进行分解求解： 第一步：求解线性规划问题：
min d1_+d1 x11+x21+x31=100 x12+x22+x32=300 x13+x23+x33=200
11000x11+9500x12+9000x13>=190000 8000x21+6800x22+6000x23>=130000 14000x31+12000x32+10000x33>=350000
11000x11+9500x12+9000x13+8000x21+6800x22+6000x23+14000x31+12000x32+10000x 33+d1_-d1=6100000
xij>=0 (i,j=1,2,3); d1_>=0, d1>=0
对上述线性规划问题，可以借助于Matlab 优化工具中的linprog 函数求解，
函数调用命令为：
[x,fval]=linprog(f,A,b,Aeq,beq,lb,[])
其中，参数如下：
A=
-11000-9500-900000000000 000-8000-6800-600000000
000000-14000-12000-1000000 b=
-190000
-130000
-350000
Aeq=
10010010000
010********
00100100100
11000 950090008000680060001400012000100001-1 beq=
100
300
200
6100000
f=
00000000011 lb=
00000000000求解运行，输出结果：
x =
33.2724
108.3943
145.3961
16.4696
130
54.3202
0.6296
50.2580
137.2855
53.9743
0.0000
0.0000
fval =
2.6261e-014
即：d1_+d1=2.6261e-014≈0
第二步：求解线性规划问题：
min d2_+d2
x11+x21+x31=100
x12+x22+x32=300
x13+x23+x33=200
11000x11+9500x12+9000x13>=190000
8000x21+6800x22+6000x23>=130000
14000x31+12000x32+10000x33>=350000
11000x11+9500x12+9000x13+8000x21+6800x22+6000x23+14000x31+12000x32+10000x 33+d1_-d1=6100000
d1_+d1=0
13200x11+11400x12+10800x13+12000x21+10200x22+9000x23+11200x31+9600x32+800 0x33+d2_-d2=6600000
xij>=0 (i,j=1,2,3); d1_>=0, d1>=0,d2_>=0,d2>=0
对上述线性规划问题，可以借助于Matlab优化工具中的linprog函数求解，函数调用命令为：
[x,fval]=linprog(f,A,b,Aeq,beq,lb,[])
131
其中，参数如下：
A=
-11000-9500-9000000000000 0 000-8000-6800-6000000000 0
000000-14000-12000-10000000 0
b=
-190000
-130000
-350000
Aeq=
100100100000 0 010********* 0 001001001000 0 11000 950090008000680060001400012000100001-10 0 13200 1140010800120001020090001120096008000001-1
0 000000001100 beq=
100
300
200
6100000
6600000
f=
00000000000 1 1 lb=
000000000000 0
运行输出求解结果：
x =
5.9011
232.5826
198.5503
12.8145
4.2771
132
0.7905
81.2844
63.1403
0.6592
0.0000
0.0000
0.0000
0.0000
fval =
1.0126e-015
即：d2_+d2=1.0126e-015≈0
最后得到一个非劣解方案，如下表：
I等耕地II等耕地III等耕地水稻 5.901 1 232.582 6 198.550 3
大豆12.814 5 4.277 1 0.790 5
玉米81.284 4 63.140 3 0.659 2
同样可以看出，以上求解的满意解方案不同于用LINDO软件求得的结果。这是因为，该问题本身有多重解，而linprog函数求解算法又不同于LINDO的缘故。有兴趣的读者可以进一步验证，上述解和借助于LINDO软件用贯序方法求解的结果都是满意解方案。
133
122 §17.借助于Matlab 用贯序算法求解目标规 划问题 虽然Matlab 没有提供直接求解目标规划的优化工具，但是根据目标规划的求解思路——单纯形方法。我们可以将一个目标规划问题分解成若干线性规划问题，通过序贯式算法借助于Matlab 优化工具进行求解。 例1：教材第6章第3节中的目标规划问题： - + - + +++=3 322211)(min d p d d p d p Z 11221≤+x x 01121=-+-+ - d d x x 10 22221=-+++ -d d x x 56 1083321=-+++ -d d x x ) 3,2,1(0 ,,,21=≥+ -i d d x x i i 首先将上述问题化为标准形式： - + - + +++=3 322211)(min d p d d p d p Z 112321=++x x x 01121=-+-+ -d d x x
123 10 22221=-+++ -d d x x 56 1083321=-+++ -d d x x ) 3,2,1(0 ,,=≥+ -i d d x i i i 然后按照以下步骤分解计算： 第一步：求解如下线性规划问题： min d1 2x1+x2+x3=11 x1-x2+d1_-d1=0 x1,x2,x3>=0,d1_>=0,d1>=0 对上述线性规划问题，可以借助于Matlab 优化工具中的linprog 函数求解，函数调用命令为： [x,fval]=linprog(f,[],[],Aeq,beq,lb,[]) 其中，参数如下： Aeq= 2 1 1 0 0 0 0 0 0 1 -1 1 -1 beq= 11 0 f= 0 0 0 1 0 0 0 0 lb=
多目标线性规划的若干解法及MATLAB 实现 一．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ， 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件：0 Ax b x ≤?? ≥? （3） 二．MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为： ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理：单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ） fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束
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年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。 编辑本段 求解方法 化多为少的方法 即
§15. 利用Matlab求解线性规划问题 线性规划是一种优化方法，Matlab优化工具箱中有现成函数linprog对如下式描述的LP问题求解： % min f'x % s.t .(约束条件)：Ax<=b % (等式约束条件)：Aeqx=beq % lb<=x<=ub linprog函数的调用格式如下： x=linprog(f,A,b) x=linprog(f,A,b,Aeq,beq) x=linprog(f,A,b,Aeq,beq,lb,ub) x=linprog(f,A,b,Aeq,beq,lb,ub,x0) x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) [x,fval]=linprog(…) [x, fval, exitflag]=linprog(…) [x, fval, exitflag, output]=linprog(…) [x, fval, exitflag, output, lambda]=linprog(…) 其中： x=linprog(f,A,b)返回值x为最优解向量。 x=linprog(f,A,b,Aeq,beq) 作有等式约束的问题。若没有不等式约束，则令 111
A=[ ]、b=[ ] 。 x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 中lb ,ub为变量x的下界和上界，x0为初值点，options为指定优化参数进行最小化。 Options的参数描述： Display显示水平。选择’off’ 不显示输出；选择’I ter’显示每一步迭代过程的输出；选择’final’ 显示最终结果。 MaxFunEvals 函数评价的最大允许次数 Maxiter 最大允许迭代次数 TolX x处的终止容限 [x,fval]=linprog(…) 左端fval 返回解x处的目标函数值。 [x,fval,exitflag,output,lambda]=linprog(f,A,b, Aeq,beq,lb,ub,x0) 的输出部分： exitflag描述函数计算的退出条件：若为正值，表示目标函数收敛于解x 处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。 output 返回优化信息：output.iterations表示迭代次数；output.algorithm表示所采用的算法；outprt.funcCount表示函数评价次数。 lambda返回x处的拉格朗日乘子。它有以下属性： lambda.lower-lambda的下界； lambda.upper-lambda的上界； lambda.ineqlin-lambda的线性不等式； lambda.eqlin-lambda的线性等式。 112
优化与决策 ——多目标线性规划的若干解法及MATLAB实现 指导老师: XX教授 学生姓名: XX 多目标线性规划的若干解法及MATLAB实现 丁宏飞 （西南交通大学数学学院四川成都 610031）
摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍了理想点法、线性加权和法、最大最小法、目标规划法[1]，然后给出多目标线性规划的模糊数学解法[2]，最后对每种解法给出例子，并用Matlab 软件加以实现。 关键词：多目标线性规划 Matlab 模糊数学 Some solutions of Multi-objective linear programming and realized by Matlab Ding Hongfei School of Mathematics, Southwest Jiaotong University ,Chengdu, 610031 Abstract: The basic ideas to solve Multi-objective linear programming are transforming the multi-objective problem into single-objective planning, This paper introduces the ideal point method, linear weighted and law, max-min method, the goal programming method, then given multi-objective linear programming Fuzzy mathematics method, finally give examples of each method and used Matlab software to achieve. Key words: Multi-objective Linear Programming Matlab fuzzy mathematics 一．引言 多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有效解(非劣解)。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法，然而这些方法对多目标偏好信息的确定、处理等方面的研究工作较少，本文也给出多目标线性规划的模糊数学解法。 二．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为： 11111221221122221122m ax n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++?? =+++?? ? ?=+++? （1）
一种偏向目标型的RRT算法实现 摘要：本文针对基本快速扩展随机树(RRT)算法存在搜索过于平均、效率低下、用时较长的缺陷，提出了一种偏向目标型的改进型RRT算法。这种算法在生成随机点时以一定概率选择最终目标点作为局部目标点，使树的扩展有一个趋向于最终目标点的趋势，从而加快了算法的收敛速度，优化了规划路径。最后通过Matlab程序仿真，在二维平面上验证了改进型算法相对于基本算法的优越性。关键词：路径规划、RRT算法、偏向目标型 一.引言 机器人学是当今科学技术研究的热点问题，它汇聚了各个尖端学科最先进的研究成果。科学家们从上世纪40年代开始着手研制机器人到如今，机器人的发展主要经历了三次技术变革。从最简单的第一代机器人到现在的第三代智能机器人，机器人从只会机械的执行命令逐渐演变成利用各种先进的传感器自动的学习环境，适应环境，并完成人类下达的任务。 路径规划问题是机器人研究中的重要的组成部分，它的重点就是要使机器人自主并且安全的从起始位姿移动到目标位姿。机器人路径规划主要分为全局路径规划和局部路径规划两大方面。全局路径规划是一种利用环境全局信息的方法，它通常将周边环境信息存储在一张地图中，并且利用这张地图寻找可行路径。全局路径规划的优点是有利于找到全局可行解和最优解，但是它的运算时间长，不适用于快速变化的动态环境。常用的全局路径规划方法有栅格法、可视图法、拓扑法和自由空间法等。局部路径规划只考虑机器人当前能探测到的环境信息，运算速度快、反应迅速，非常适用于动态环境。但其缺点是算法可能无法收敛，不能保证机器人一定能够到达目标点，而且找到的可行路径可能会偏离最短路径。常用的局部路径规划算法有人工势场法、模糊逻辑法、神经网络法和遗传算法等等。 RRT算法是最近几年才发展起来的，并且应用比较普遍的一种路径规划算法。它在处理非完整约束的路径规划问题时具有相当大的优势，因为它可以将各种约束集成到算法本身之中，因此对环境要求较低。而且该算法概率完备，在理论上肯定能找到可行路径。但其缺点是搜索过于平均，算法效率较低，而且规划
Matlab程序设计 课程大作业 题目名称：_________________________________ 班级：_________________________________ 姓名：_________________________________ 学号：_________________________________ 课程教师：温海骏 学期：2015-2016学年第2学期 完成时间： MATLAB优化应用 §1 线性规划模型 一、线性规划问题： 问题1：生产计划问题 假设某厂计划生产甲、乙两种产品，现库存主要材料有A类3600公斤，B类2000公斤，C类3000公斤。每件甲产品需用材料A类9公斤，B类4公斤，C类3公斤。每件乙产品，需用材料A类4公斤，B类5公斤，C类10公斤。甲单位产品的利润70元，乙单位产品的利润120元。问如何安排生产，才能使该厂所获的利润最大。 问题2：投资问题 某公司有一批资金用于4个工程项目的投资，其投资各项目时所得的净收益(投入资金百分比)如下表：工程项目收益表 工程项目 A B C D 收益(%) 15 10
12 由于某种原因，决定用于项目A的投资不大于其他各项投资之和而用于项目B和C的投资要大于项目D的投资。试确定该公司收益最大的投资分配方案。 问题3：运输问题 有A、B、C三个食品加工厂，负责供给甲、乙、丙、丁四个市场。三个厂每天生产食品箱数上限如下表： 工厂 A B C 生产数 60 40 50 四个市场每天的需求量如下表： 市场 甲 乙 丙 丁 需求量 20 35 33 34 从各厂运到各市场的运输费(元/每箱)由下表给出： 收点 发点 市场 甲 乙 丙 丁 工 厂 A 2 1 3 2 B
多目标规划问题
3.5 黑龙江省可持续农业产业结构优化模型的求解 鉴于上面的遗传算法的基本实现技术和理论分析，对标准遗传算法进行适当改进，将其用于求解黑龙江省可持续农业产业结构优化模型中。黑龙江省农业产业结构优化模型具有大系统、多目标、非线性等特点，传统的求解方法受到了模型复杂程度的限制，由引言可知，遗传算法对解决此类问题具有明显的优势。下面介绍具体采用的遗传多目标算法操作设计以及模型求解过程。 3.5.1遗传多目标算法操作设计 3.5.1.1 实数编码方法 在求解复杂优化问题时，二进制向量表示结构有时不太方便，并且浮点数编码的遗传算法对变异操作的种群稳定性比二进制编码好（徐前锋，2000）。以浮点数编码的遗传算法也叫实数遗传算法（Real number Genetic Algorithms ，简称RGA ）。每一个染色体由一个浮点数向量表示，其长度与解向量相同。假如用向量),(21n x x x X 表示最优化问题的解，则相应的染色体就是 ),(21n x x x V ，其中n 是变量个数。 3.5.1.2 种群初始化方法 遗传算法中初始群体的个体是随机产生的，由于本文优化模型所涉及的变量容易给出一个相对较大的问题空间的变量分布范围，并且若给出一定的搜索空间也会加快遗传算法的收敛速度；因此本文采取3.3.2中的第一种策略，对每一个变量设置可能区间，然后在可能区间内随机产生初始种群。为保证不会遗漏最优解，选择区间跨度范围很大。 3.5.1.3 适应度函数设计
用遗传算法求解多目标优化问题中出现的一个特殊情况就是如何根据多个目标来确定个体的适应值。本文采用Gen 和Cheng 提出的适应性权重方法 （Adaptive Weight Approach ），该方法利用当前种群中一些有用的信息来重新调整权重，从而获得朝向正理想点的搜索压力（玄光男等，2004）。将目标函数按3.3.3所述转化成带有q 个目标（本文模型3 q ）的最大化问题： )}(,),(),({max 2211x f z x f z x f z q q （3-14） 对于每代中待检查的解来说，在判据空间中定义两个极限点：最大极限点 z 和最小极限点 z 如下： },,,{} ,,,{m in m in 2m in 1m ax m ax 2m ax 1q q z z z z z z z z （3-15） 其中m in m ax k k z z 和是当前种群中第k 个目标的最大值和最小值。由两个极限点定义的超平行四边形是包含当前所有解的最小超平行四边形。两个极限点每代更新，最大极限点最终将接近正理想点。目标k 的适应性权重用下式计算： ),,2,1(1 min max q k z z k k k 因此，权重和目标（Weighted-sum Objective ）函数由下面的公式确定 q k k k k q k k k z z x f x f x z 1m in m ax 1)()()( （3-16） 3.5.1.4 遗传操作 （1）选择操作。以比例选择法和最优个体保存法配合使用进行选择操作，即选择过程仍以旋转赌轮来为新的种群选择染色体，适应度越高的染色体被选中的概率越大；另一方面，为了保证遗传算法的全局收敛性，在选择作用后保留当前群体中适应度最高的个体，不参与交叉和变异，同时也确保当前最优个体不被随机进行的遗传操作破坏。
多目标蚁群算法及其实现 李首帅（2012101020019） 指导老师：张勇 【摘要】多目标优化问题对于现阶段来说，是十分热门的。本文将对多目标规划当中的旅行商问题，通过基于MATLAB的蚁群算法来解决，对多目标问题进行局部优化。 【关键词】旅行商问题；蚁群算法；MATLAB 一、背景介绍 旅行商问题是物流领域当中的典型问题，它的求解十分重要。蚁群算法是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体的模拟进化算法,属于随机搜索算法。M. Dorigo等人充分利用了蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性,通过人工模拟蚁群搜索食物的行为(即蚂蚁个体之间通过间接通讯与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP问题。为区别于真实蚁群,称算法中的蚂蚁为“人工蚂蚁”。人们经过大量研究发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递,从而能相互协作,完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 二、蚁群算法原理介绍 1.蚁群在路径上释放信息素； 2.碰到还没走过的路口，就随机挑选一条路走。同时释放与路径长度有关的信息素； 3.信息素浓度与路长成反比； 4.最优路径上的信息浓度越来越大； 5.最终蚁群找到最优路径。 其实自然界中，蚁群这种寻找路径的过程表现是一种正反馈的过程，与人工蚁群的优化算法很相近。所以我们简单功能的工作单元视为蚂蚁，则上述的搜寻路径过程可以用来解释人工蚁群搜寻过程。 人工蚁群和自然界蚁群各具特点。人工蚁群具有一定的记忆能力。它能够记忆已经访问过的节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规律有意识地寻找最短路径。而自然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者
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 求解，
%遗传算法解决多目标函数规划 clear clc syms x; %Function f1=f(x) f1=x(:,1).*x(:,1)/4+x(:,2).*x(:,2)/4; %function f2=f(x) f2=x(:,1).*(1-x(:,2))+10; NIND=100; MAXGEN=50; NV AR=2; PRECI=20; GGPA=0.9; trace1=[]; trace2=[]; trace3=[]; FielD=[rep([PRECI],[1,NV AR]);[1,1;4,2];rep([1;0;1;1],[NV AR])]; Chrom=crtbp(NIND,NV AR*PRECI); v=bs2rv(Chrom,FielD); gen=1; while gen §18. 运用目标达到法求解多目标规划 用目标达到法求解多目标规划的计算过程，可以通过调用Matlab软件系统优化工具箱中的fgoalattain函数实现。 在Matlab的优化工具箱中，fgoalattain函数用于解决此类问题。其数学模型形式为： minγ F(x)-weight ·γ≤goal c(x) ≤0 ceq(x)=0 A x≤b Aeq x=beq lb≤x≤ub 其中，x，weight，goal，b，beq，lb和ub为向量；A和Aeq为矩阵；c(x)，ceq(x)和F(x)为函数。 调用格式： x=fgoalattain(F,x0,goal,weight) x=fgoalattain(F,x0,goal,weight,A,b) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq) 134 x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2) [x,fval]=fgoalattain(…) [x,fval,attainfactor]=fgoalattain(…) [x,fval,attainfactor,exitflag,output]=fgoalattain(…) [x,fval,attainfactor,exitflag,output,lambda]=fgoalattain(…) 说明：F为目标函数；x0为初值；goal为F达到的指定目标；weight为参数指定权重；A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。 x返回最优解；fval返回解x处的目标函数值；attainfactor返回解x处的目标达到因子；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。 例1：教材第6章第4节第二小节，即生产计划问题： 某企业拟生产A和B两种产品，其生产投资费用分别为2100元/t和4800元/t。A、B两种产品的利润分别为3600元/t和6500元/t。A、B产品每月的最大生产能力分别为5t和8t；市场对这两种产品总量的需求每月不少于9t。试问该企业应该如何安排生产计划，才能既能满足市场需求，又节约投资，而且使生产利润达到最大最。 135 多目标非线性规划程序 M a t l a b Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】 f u n c t i o n[e r r m s g,Z,X,t,c,f a i l]= BNB18(fun,x0,xstat,xl,xu,A,B,Aeq,Beq,nonlcon,setts,options1,options2,maxSQPit,varargin ); %·Dêy1￡Díóa·§¨μü′ú·¨￡úDê1ó￡DèOptimization toolbox §3 % Minimize F(x) %subject to: xlb <= x <=xub % A*x <= B % Aeq*x=Beq % C(x)<=0 % Ceq(x)=0 % % x(i)éaáD±á￡êy￡ò1ì¨μ % ê1óê %[errmsg,Z,X]=BNB18('fun',x0,xstat,xl,xu,A,B,Aeq,Beq,'nonlcon',setts) %fun￡o Mt￡±íê×Dˉ±êoˉêyf=fun(x) %x0: áDòá￡±íê±á3μ %xstat￡o áDòá￡xstat(i)=0±íêx(i)aáD±á￡1±íêêy￡2±íê1ì¨μ %xl￡o áDòá￡±íê±á %xu: áDòá￡±íê±áé %A: ó, ±íêD2μèêêμêy %B: áDòá, ±íêD2μèêêé %Aeq: ó, ±íêDμèêêμêy %Beg: áDòá, ±íêD2μèêêóòμ %nonlcon: Mt￡±íê·Dêoˉêy[C,Ceq]=nonlin(x),DC(x)a2μèêê, % Ceq(x)aμèêê %setts: ·¨éè %errmsq: ·μ′íóìáê %Z: ·μ±êoˉêy×Dμ %X: ·μ×óa % %àyìa % max x1*x2*x3 % -x1+2*x2+2*x3>=0 % x1+2*x2+2*x3<=72 % 10<=x2<=20 % x1-x2=10 % èD′ Moˉêy % function f=discfun(x) % f=-x(1)*x(2)*x(3); %óa % clear;x0=[25,15,10]';xstat=[1 1 1]'; % xl=[20 10 -10]';xu=[30 20 20]'; % A=[1 -2 -2;1 2 2];B=[0 72]';Aeq=[1 -1 0];Beq=10; % [err,Z,X]=BNB18('discfun',x0,xstat,xl,xu,A,B,Aeq,Beq); % XMAX=X',ZMAX=-Z % 桂林电子科技大学 数学与计算科学学院实验报告 实验室：06406 实验日期： 2014年12月6日 院（系） 数学与计算科学学院 年级、专业、班级 12007301 姓名 成绩 课程 名称 运筹学实验 实验项目 名 称 目标规划算法实现 指导 教师 南江霞 一 、实验目的 1、掌握目标规划的数学模型创建方法； 2、掌握目标规划问题的图解法和单纯形法； 3、掌握目标规划问题的软件求解； 4、掌握目标规划问题的满意解的分析方法。 二、实验原理 利用WinQSB 和Lingo 的软件关于线性方程组求解的方法对问题求解。 三、使用仪器，材料 实验指导书、课本、WinQSB 和Lingo 软件。 四、实验内容与步骤 某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外 购件外，生产一台录音机需要甲车间加工2小时，乙车间装配1小时；生产一台电视机 需要甲车间加工1小时，乙车间装配3小时。两种产品生产出来后均需要经过检验、销 售等环节。已知每台录音机检验销售费用为50元，每电视机检验销售费用为30元。又 甲车间每月可用生产工时为120小时，车间管理费用为80元/小时；乙车间每月可用的 生产工时为150小时，车间管理费用为20元/小时。估计每台录音机利润为100元，每 台电视机利润为75元，又估计下一年度内平均每月可销售录音机50台，电视机80台。 工厂制定月度计划的目标如下： 第一优先级：检验和销售每月不超过4600元； 第二优先级：每月销售录音机不少于50台； 第三优先级：甲乙两车间的生产工时得到充分的利用； 第四优先级：甲车间加班不超过20小时； 第五优先级：每月销售电视机不少于80台； 第六优先级：两个车间加班总时间要有控制； 试确定该厂为达到以上目标的最优月度计划生产数字。 根据题意我们可以得到如下的目标规划： )4()4(min 21655642134231++-+---++++++++=d d P d P d P d d P d P d P z MATLAB 语言应用————最优化 MATLAB 编程线性规划问题 第二章0-1规划 MATLAB 的0-1规划函数bintprog 是针对下述0-1规划： 12min *.**[,,],01,1,2,n i z f x s t A x b aeq x beq x x x x x or i n L L （）解0-1规划（）的0-1规划函数bintprog 表述为 [x, fv, exitflag, output]= bintprog(f,A,b,aeq, beq) （）输入部分： f 为目标函数,实为目标函数的系数。 A 为（）中的不等式约束矩阵 b 为（）中的不等式约束向量 aeq 为（）中的等式约束矩阵 beq （）中的等式约束向量 输出部分： x 为最优解fval 为最优值 exitflag 为输出标志 exitflag=1,有最优解exitflag=0，迭代次数超过设定次数exitflag==-2，约束区域不可行 exitflag=-3，问题无解 output ，表明算法和迭代情况如果我们不需要了解迭代情况和存储情况，可将 0-1规划函数bintprog 写成[x, fv, ex]= linprog(f,A,b,aeq, beq) （） 在函数bintprog 中，输入或输出元素的符号可以变更，如（）中 ex 仍为输出标志，但元素的符号位置不能变更。在输出部分，如有缺者，可用 []号代替。函数bintprog 的使用要点与函数linprog 的使用要点相同。 函数是为求目标函数的最小值而设置的， 如要求函数的最大值，可先求出()f 的最小值fv ，则fv 必为f 的最大值。 例一用函数bintprog 求解下列0-1规划用MA TLAB 语言编程如下： -253- 第二十一章 目标规划 §1 目标规划的数学模型 为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。 例1 某工厂生产I ，II 两种产品，已知有关数据见下表 I II 拥有量 原材料 kg 2 1 11 设 备 hr 1 2 10 利润 元/件 8 10 试求获利最大的生产方案。 解 这是一个单目标的规划问题，用线性规划模型表述为： 21108max x x z += ?????≥≤+≤+0,1021122 12121x x x x x x 最优决策方案为：62,3,4**2*1===z x x 元。 但实际上工厂在作决策方案时，要考虑市场等一系列其它条件。如 （i ）根据市场信息，产品I 的销售量有下降的趋势，故考虑产品I 的产量不大于产品II 。 （ii ）超过计划供应的原材料，需要高价采购，这就使成本增加。 （iii ）应尽可能充分利用设备，但不希望加班。 （iv ）应尽可能达到并超过计划利润指标56元。 这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解决这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。 1. 正、负偏差变量 设d 为决策变量的函数，正偏差变量}0,max{0d d d -=+表示决策值超过目标值的部分，负偏差变量}0,min{0d d d --=-表示决策值未达到目标值的部分， 这里0d 表示d 的目标值。因决策值不可能既超过目标值同时又未达到目标值，即恒有0=?-+d d 。 2. 绝对约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如：例1的目标函数21108x x z +=可变换为目标约束561081121=-+++-d d x x 。绝对约束11221≤+x x 可变换为目标约束 1122221=-+++-d d x x 。 第13卷 第4期运 筹 与 管 理 Vol.13,No.42004年8月OPERAT IO NS RESEARCH AN D M ANA GEM EN T SCI EN CE Aug.2004 收稿日期:2003-10-27 基金项目:陕西省教育厅专项科研基金资助项目(03jk065);西安建筑科技大学基础研究基金资助项目(02BR01) 作者简介:卢志义(1973-),男,内蒙古包头市人,硕士研究生,从事最优化理论研究;徐裕生(1950-),西安建筑科技大学理学院教授,主要从事最优化理论和不动点理论的研究。 完全分层多目标规划的基线算法 卢志义, 徐裕生, 马春晖 (西安建筑科技大学理学院,陕西西安710055) 摘 要:本文采用基线算法求解完全分层多目标规划问题。给出了简单完全分层多目标规划基线算法的求解步骤,并对其进行了修正,从而得到完全分层多目标规划的宽容基线算法。并给出了两个计算实例。关键词:运筹学;宽容算法;基线算法;多目标规划 中图分类号:O22116 文章标识码:A 文章编号:1007-3221(2004)04-0050-05 Th e Basic Line Algorithm for Complete Tratified Mu ltiobjective Programmin g LU Zh-i yi,XU Yu -sheng,MA Chun -hui (College of Science,X i .an University o f A rchitecture and Technology ,Xi .an 710055,China)Abstract:In this paper,we make use of the basic line algorithm to solve the complete tratified multiobjective prog ramming.The procedures of solv ing the simple com plete tratified multiobjective program ming are g iven.M eanw hile,w e rev ise it so as to succeed in obtaining the compromise solution of the complete tratified mult-i objective programm ing.T wo examples also are g iven. Key words:operations research;comprom ise algorithm;the basic line algorithm;multiobjective programming 0 引言 基线算法是一种线性规划的新算法,具有操作方便,迭代次数小,效率高,数值稳定性好等特点,是单纯形法的发展(参见[1])。我们陆续将此算法推广到与线性规划有关的其它规划。本文旨在将此算法推广到多目标规划。较单纯形法而言,用基线算法解决完全分层多目标规划,步骤更简洁,易操作,运算速度更快。 1 简单完全分层多目标规划的基线算法 1.1 算法的形成 讨论完全分层多目标规划问题 L -max [v s =P s c T s x ]m s =1 (1) s.t.Ax [b x \0§18运用目标达到法求解多目标规划
多目标非线性规划程序Matlab完整版
运筹学实验二目标规划算法实现
MATLAB编程0-1规划问题
数学建模算法大全目标规划
完全分层多目标规划的基线算法
相关主题
文本预览