声振论坛

 找回密码
 我要加入

QQ登录

只需一步,快速开始

查看: 15918|回复: 24

[共享资源] MATLAB优化方法应用

 关闭 [复制链接]
发表于 2005-7-6 20:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?我要加入

x
§1 线性规划模型
一、线性规划课题:
实例1:生产计划问题
假设某厂计划生产甲、乙两种产品,现库存主要材料有A类3600公斤,B类2000公斤,C类3000公斤。每件甲产品需用材料A类9公斤,B类4公斤,C类3公斤。每件乙产品,需用材料A类4公斤,B类5公斤,C类10公斤。甲单位产品的利润70元,乙单位产品的利润120元。问如何安排生产,才能使该厂所获的利润最大。
建立数学模型:
设x1、x2分别为生产甲、乙产品的件数。f为该厂所获总润。
max f=70x1+120x2
s.t 9x1+4x2≤3600
4x1+5x2≤2000
3x1+10x2≤3000
x1,x2≥0


实例2:投资问题
某公司有一批资金用于4个工程项目的投资,其投资各项目时所得的净收益(投入资金锪百分比)如下表:
工程项目收益表
01.png
由于某种原因,决定用于项目A的投资不大于其他各项投资之和而用于项目B和C的投资要大于项目D的投资。试确定全文该公司收益最大的投资分配方案。
建立数学模型:
设x1、 x2 、x3 、x4分别代表用于项目A、B、C、D的投资百分数。
max f=0.15x1+0.1x2+0.08 x3+0.12 x4
s.t x1-x2- x3- x4≤0
x2+ x3- x4≥0
x1+x2+x3+ x4=1
xj≥0 j=1,2,3,4


实例3:运输问题
有A、B、C三个食品加工厂,负责供给甲、乙、丙、丁四个市场。三个厂每天生产食品箱数上限如下表:
02.PNG
四个市场每天的需求量如下表:
03.PNG
从各厂运到各市场的运输费(元/每箱)由下表给出:
04.PNG
求在基本满足供需平衡的约束条件下使总运输费用最小。
建立数学模型:
设ai j为由工厂i运到市场j的费用,xi j 是由工厂i运到市场j的箱数。bi是工厂i的产量,dj是市场j的需求量。
b= ( 60 40 50 ) d= ( 20 35 33 34 )
s.t
x i j≥0


当我们用MATLAB软件作优化问题时,所有求maxf 的问题化为求min(-f )来作。约束g i (x)≥0,化为 –g i≤0来作。
上述实例去掉实际背景,归结出规划问题:目标函数和约束条件都是变量x的线性函数。

形如:
(1) 形如: (1) min f T X
s.t A X≤b
Aeq X =beq
lb≤X≤ub

其中X为n维未知向量,f T=[f1,f2,…fn]为目标函数系数向量,小于等于约束系数矩阵A为m×n矩阵,b为其右端m维列向量,Aeq为等式约束系数矩阵,beq为等式约束右端常数列向量。lb,ub为自变量取值上界与下界约束的n维常数向量。

二.线性规划问题求最优解函数:
调用格式:
  1. x=linprog(f,A,b)
  2. x=linprog(f,A,b,Aeq,beq)
  3. x=linprog(f,A,b,Aeq,beq,lb,ub)
  4. x=linprog(f,A,b,Aeq,beq,lb,ub,x0)
  5. x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
  6. [x,fval]=linprog(…)
  7. [x, fval, exitflag]=linprog(…)
  8. [x, fval, exitflag, output]=linprog(…)
  9. [x, fval, exitflag, output, lambda]=linprog(…)
复制代码


说明:x=linprog(f,A,b)返回值x为最优解向量。
x=linprog(f,A,b,Aeq,beq) 作有等式约束的问题。若没有不等式约束,则令A=[ ]、b=[ ] 。
x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 中lb ,ub为变量x的下界和上界,x0为初值点,options为指定优化参数进行最小化。
Options的参数描述:
Display 显示水平。 选择’off’ 不显示输出;选择’iter’显示每一 步迭代过程的输出;选择’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的线性等式。
回复
分享到:

使用道具 举报

 楼主| 发表于 2005-7-6 20:05 | 显示全部楼层
三. 举例

例1:求解线性规划问题:
max f=2x1+5x2
s.t

先将目标函数转化成最小值问题:
min(-f)=- 2x1-5x2

程序:
  1. f=[-2 -5];
  2. A=[1 0;0 1;1 2];
  3. b=[4;3;8];
  4. [x,fval]=linprog(f,A,b)
  5. f=fval*(-1)
复制代码

结果: x = 2
3
fval = -19.0000
maxf = 19

例2:
minf=5x1-x2+2x3+3x4-8x5
s.t –2x1+x2-x3+x4-3x5≤6
2x1+x2-x3+4x4+x5≤7
0≤xj≤15 j=1,2,3,4,5

程序:
  1. f=[5 -1 2 3 -8];
  2. A=[-2 1 -1 1 -3;2 1 -1 4 1];
  3. b=[6;7];
  4. lb=[0 0 0 0 0];
  5. ub=[15 15 15 15 15];
  6. [x,fval]=linprog(f,A,b,[],[],lb,ub)
复制代码

结果:x =
0.0000
0.0000
8.0000
0.0000
15.0000

minf =
-104

例3:求解线性规划问题:
minf=5x1+x2+2x3+3x4+x5
s.t –2x1+x2-x3+x4-3x5≤1
2x1+3x2-x3+2x4+x5≤-2
0≤xj≤1 j=1,2,3,4,5


程序:
  1. f=[5 1 2 3 1];
  2. A=[-2 1 -1 1 -3;2 3 -1 2 1];
  3. b=[1;-2];
  4. lb=[0 0 0 0 0];
  5. ub=[1 1 1 1 1];
  6. [x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb,ub)
复制代码

运行结果:
Exiting: One or more of the residuals, duality gap, or total relative error
has grown 100000 times greater than its minimum value so far:
the primal appears to be infeasible (and the dual unbounded).
(The dual residual < TolFun=1.00e-008.)
x = 0.0000
0.0000
1.1987
0.0000
0.0000
fval =2.3975
exitflag =-1
output =
iterations: 7
cgiterations: 0
algorithm: 'lipsol'
lambda =
ineqlin: [2x1 double]
eqlin: [0x1 double]
upper: [5x1 double]
lower: [5x1 double]
显示的信息表明该问题无可行解。所给出的是对约束破坏最小的解。

例4:求解实例1的生产计划问题
建立数学模型:
设x1、x2分别为生产甲、乙产品的件数。f为该厂所获总润。
max f=70x1+120x2
s.t 9x1+4x2≤3600
4x1+5x2≤2000
3x1+10x2≤3000
x1,x2≥0

将其转换为标准形式:
min f=-70x1-120x2
s.t 9x1+4x2≤3600
4x1+5x2≤2000
3x1+10x2≤3000
x1,x2≥0

程序:
  1. f=[-70 -120];
  2. A=[9 4 ;4 5;3 10 ];
  3. b=[3600;2000;3000];
  4. lb=[0 0];
  5. ub=[];
  6. [x,fval,exitflag]=linprog(f,A,b,[],[],lb,ub)
  7. maxf=-fval
复制代码

结果:
x =
200.0000
240.0000
fval =-4.2800e+004
exitflag =1
maxf =4.2800e+004

例5:求解实例2
建立数学模型:
max f=0.15x1+0.1x2+0.08 x3+0.12 x4
s.t x1-x2- x3- x4≤0
x2+ x3- x4≥0
x1+x2+x3+ x4=1
xj≥0 j=1,2,3,4

将其转换为标准形式:
min z=-0.15x1-0.1x2-0.08 x3-0.12 x4
s.t x1-x2- x3- x4≤0
-x2- x3+ x4≤0
x1+x2+x3+ x4=1
xj≥0 j=1,2,3,4


程序:
  1. f = [-0.15;-0.1;-0.08;-0.12];
  2. A = [1 -1 -1 -1
  3. 0 -1 -1 1];
  4. b = [0; 0];
  5. Aeq=[1 1 1 1];
  6. beq=[1];
  7. lb = zeros(4,1);
  8. [x,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb)
  9. f=-fval
复制代码


结果:
x =
0.5000
0.2500
0.0000
0.2500
fval =-0.1300
exitflag =1
f =0.1300

即4个项目的投资百分数分别为50%,25%,0, 25%时可使该公司获得最大的收益,其最大收益可到达13%。过程正常收敛。
 楼主| 发表于 2005-7-6 20:05 | 显示全部楼层
例6:求解实例3
建立数学模型:
设ai j为由工厂i运到市场j的费用,xi j 是由工厂i运到市场j的箱数。bi是工厂i的产量,dj是市场j的需求量。
b= ( 60 40 50 )T d= ( 20 35 33 34 )T
s.t
x i j≥0

程序:
  1. A=[2 1 3 2;1 3 2 1;3 4 1 1];
  2. f=A(:);
  3. B=[ 1 0 0 1 0 0 1 0 0 1 0 0
  4. 0 1 0 0 1 0 0 1 0 0 1 0
  5. 0 0 1 0 0 1 0 0 1 0 0 1];
  6. D=[1 1 1 0 0 0 0 0 0 0 0 0
  7. 0 0 0 1 1 1 0 0 0 0 0 0
  8. 0 0 0 0 0 0 1 1 1 0 0 0
  9. 0 0 0 0 0 0 0 0 0 1 1 1];
  10. b=[60;40;50];
  11. d=[20;35;33;34];
  12. lb=zeros(12,1);
  13. [x,fval,exitflag]=linprog(f,B,b,D,d,lb)
复制代码


结果: x =
0.0000
20.0000
0.0000
35.0000
0.0000
0.0000
0.0000
0.0000
33.0000
0.0000
18.4682
15.5318

fval =122.0000
exitflag =1

即运输方案为:甲市场的货由B厂送20箱;乙市场的货由A厂送35箱;丙商场的货由C厂送33箱;丁市场的货由B厂送18箱,再由C厂送16箱。

最低总运费为:122元。
 楼主| 发表于 2005-7-6 20:06 | 显示全部楼层
§2 非线性规划模型
一.非线性规划课题
实例1 表面积为36平方米的最大长方体体积。

建立数学模型:
设x、y、z分别为长方体的三个棱长,f为长方体体积。
max f = x y (36-2 x y)/2 (x+y)

实例2 投资决策问题
某公司准备用5000万元用于A、B两个项目的投资,设x1、x2分别表示配给项目A、B的投资。预计项目A、B的年收益分别为20%和16%。同时,投资后总的风险损失将随着总投资和单位投资的增加而增加,已知总的风险损失为2x12+x22+(x1+x2)2.问应如何分配资金,才能使期望的收益最大,同时使风险损失为最小。

建立数学模型:
max f=20x1+16x2-λ[2x12+x22+(x1+x2)2]
s.t x1+x2≤5000
x 1≥0,x2≥0


目标函数中的λ≥0是权重系数。
由以上实例去掉实际背景,其目标函数与约束条件至少有一处是非线性的,称其为非线性问题。
非线性规划问题可分为无约束问题和有约束问题。实例1为无约束问题,实例2为有约束问题。

二.无约束非线性规划问题:
求解无约束最优化问题的方法主要有两类:直接搜索法(Search method)和梯度法(Gradient method).
1.fminunc函数
调用格式:
  1. x=fminunc(fun,x0)
  2. x=fminunc(fun,x0,options)
  3. x=fminunc(fun,x0,options,P1,P2)
  4. [x,fval]=fminunc(…)
  5. [x,fval, exitflag]=fminunc(…)
  6. [x,fval, exitflag,output]=fminunc(…)
  7. [x,fval, exitflag,output,grad]=fminunc(…)
  8. [x,fval, exitflag,output,grad,hessian]=fminunc(…)
复制代码

说明:fun为需最小化的目标函数,x0为给定的搜索的初始点。options指定优化参数。
返回的x为最优解向量;fval为x处的目标函数值;exitflag描述函数的输出条件;output返回优化信息;grad返回目标函数在x处的梯度。Hessian返回在x处目标函数的Hessian矩阵信息。

例1 :
程序:编辑ff1.m文件
  1. function f=ff1(x)
  2. f=8*x(1)-4*x(2) +x(1)^2+3*x(2)^2;
复制代码

通过绘图确定一个初始点:
  1. [x,y]=meshgrid(-10:.5:10);
  2. z= 8*x-4*y +x.^2+3*y.^2;
  3. surf(x,y,z)
复制代码

选初始点:
  1. x0=(0,0)
  2. x0=[0,0];
  3. [x,fval,exitflag]=fminunc(@ff1,x0)
复制代码


结果:
x =-4.0000 0.6667
fval =-17.3333
exitflag =1

例2:
程序:编辑ff2.m文件:
  1. function f=ff2(x)
  2. f=4*x(1)^2+5*x(1)*x(2)+2*x(2)^2;
复制代码

取初始点:
  1. x0=(1,1)
  2. x0=[1,1];
  3. [x,fval,exitflag]=fminunc(@ff2,x0)
复制代码

结果:
x =1.0e-007 *
-0.1721 0.1896
fval =2.7239e-016
exitflag =1

例3:将上例用提供的梯度g最小化函数进行优化计算。
修改M文件为:
  1. function [f,g]=ff3(x)
  2. f=4*x(1)^2+5*x(1)*x(2)+2*x(2)^2;
  3. if nargut >1
  4. g(1)=8*x(1)+5*x(2);
  5. g(2)=5*x(1)+4*x(2);
  6. end
复制代码

通过下面将优化选项结构options.GradObj设置为’on’来得到梯度值。
  1. options=optimset(‘Gradobj’,’on’);
  2. x0=[1,1];
  3. [x,fval,exitflag]=fminunc(@ff3,x0,options)
复制代码

结果:
x =1.0e-015 *
-0.2220 -0.2220
fval =5.4234e-031
exitflag =1

2. minsearch函数
调用格式:
  1. x=fminsearch(fun,x0)
  2. x=fminsearch(fun,x0,options)
  3. x=fminsearch(fun,x0,options,P1,P2)
  4. [x,fval]=fminsearch(…)
  5. [x,fval, exitflag]=fminsearch(…)
  6. [x,fval, exitflag,output]=fminsearch(…)
  7. [x,fval, exitflag,output,grad]=fminsearch(…)
  8. [x,fval, exitflag,output,grad,hessian]=fminsearch(…)
复制代码

说明:参数及返回变量同上一函数。对求解二次以上的问题,fminsearch函数比fminunc函数有效。

3. 多元非线性最小二乘问题:
非线线性最小二乘问题的数学模型为:
其中L为常数。
调用格式:
  1. x=lsqnonlin(fun,x0)
  2. x=lsqnonlin(fun,x0,lb,ub)
  3. x=lsqnonlin(fun,x0,options)
  4. x=lsqnonlin(fun,x0,options,P1,P2)
  5. [x,resnorm]=lsqnonlin(…)
  6. [x,resnorm, residual,exitflag]=lsqnonlin(…)
  7. [x,resnorm, residual , exitflag,output]=lsqnonlin(…)
  8. [x,resnorm, residual,exitflag, output,lambda]=lsqnonlin(…)
  9. [x,resnorm, r esidual,exitflag, output,lambda,jacobian]=lsqnonlin(…)
复制代码

说明:x返回解向量;resnorm返回x处残差的平方范数值:sum(fun(x).^2);residual返回x处的残差值fun(x);lambda返回包含x处拉格朗日乘子的结构参数;jacobian返回解x处的fun函数的雅可比矩阵。
lsqnonlin默认时选择大型优化算法。Lsqnonlin通过将options.LargeScale设置为’off’来作中型优化算法。其采用一维搜索法。

例4.求 minf=4(x2-x1)2+(x2-4)2 ,选择初始点x0(1,1)

程序:
  1. f ='4*(x(2)-x(1))^2+(x(2)-4)^2'
  2. [x,reshorm]=lsqnonlin(f,[1,1])
复制代码

结果:
x =3.9896 3.9912
reshorm =5.0037e-009

例5:求 ,选择初始点x0(0.2,0.3)
求解:先编辑ff5.m文件:
  1. function f=ff5(x)
  2. k=1:10;
  3. f=2+2*k-exp(k*x(1))-exp(k*x(2));
复制代码

然后作程序:
  1. x0=[0.2,0.3];
  2. [x,resnorm]=lsqnonlin(@ff5,x0)
复制代码

结果 :
x =0.2578 0.2578
resnorm =124.3622
 楼主| 发表于 2005-7-6 20:08 | 显示全部楼层
二. 有约束非线性规划问题:

数学模型:
min F(x)
s.t Gi (x) ≤0 i=1,…,m
Gj (x) =0 j=m+1,…,n
xl≤x≤xu
其中:F(x)为多元实值函数,G(x)为向量值函数

在有约束非线性规划问题中,通常要将该问题转换为更简单的子问题,这些子问题可以求并作为迭代过程的基础。其基于K-T方程解的方法。它的K-T方程可表达为:

方程第一行描述了目标函数和约束条件在解处梯度的取消。由于梯度取消,需要用拉格朗日乘子λi来平衡目标函数与约束梯度间大小的差异。

调用格式:
  1. x=fmincon(f,x0,A,b)
  2. x=fmincon(f,x0,A,b,Aeq,beq)
  3. x=fmincon(f,x0,A,b,Aeq,beq,lb,ub)
  4. x=fmincon(f,x0,A,b,Aeq,beq,lb,ub,nonlcon)
  5. x=fmincon(f,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)
  6. [x,fval]=fmincon(…)
  7. [x, fval, exitflag]=fmincon(…)
  8. [x, fval, exitflag, output]=fmincon(…)
  9. [x, fval, exitflag, output, lambda]=fmincon(…)
复制代码

说明:
x=fmincon(f,x0,A,b)返回值x为最优解向量。其中:x0为初始点。A,b为不等式约束的系数矩阵和右端列向量。
x=fmincon(f,x0,A,b,Aeq,beq) 作有等式约束的问题。若没有不等式约束,则令A=[ ]、b=[ ] 。
x=fmincon(f, x0,A,b,Aeq,beq,lb,ub, nonlcon ,options) 中lb ,ub为变量x的下界和上界;nonlcon=@fun,由M文件fun.m给定非线性不等式约束c (x) ≤0和等式约束g(x)=0;options为指定优化参数进行最小化。

例6:求解:
min 100(x2-x12 )2+(1-x1)2
s.t x1≤2;
x2≤2


程序:首先建立ff6.m文件:
  1. function f=ff6(x)
  2. f=100*(x(2)-x(2)^2)^2+(1-x(1))^2;
复制代码

然后在工作空间键入程序:
  1. x0=[1.1,1.1];
  2. A=[1 0;0 1];
  3. b=[2;2];
  4. [x,fval]=fmincon(@ff6,x0,A,b)
复制代码

结果:
x =1.0000 1.0000
fval =3.1936e-011

例7:求解:
首先建立目标函数文件ff7.m文件:
  1. function f=ff7(x)
  2. f=-x(1)*x(2)*x(3)
复制代码

然后将约束条件改写成如下不等式:
  1. -x1-2x2-2x3≤0
  2. x1+2x2+2x3≤72
复制代码

在工作空间键入程序:
  1. A=[-1 –2 –2;1 2 2];
  2. b=[0;72];
  3. x0=[10;10;10];
  4. [x,fval]=fmincon(@ff71,x0,A,b)
复制代码


结果:
x =
24.0000
12.0000
12.0000

fval =-3456

例8求解:
minf=ex1(6x12+3x22+2x1x2+4x2+1)
s.t x1x2-x1-x2+1≤0
-2x1x2-5≤0

程序:首先建立目标函数文件ff8.m文件:
  1. function f=ff8(x)
  2. f=exp(x(1))*(6*x(1)^2+3*x(2)^2+2*x(1)*x(2)+4*x(2)+1);
复制代码

再建立非线性的约束条件文件:ff8g.m
  1. function [c,g]=ff8g(x)
  2. c(1)=x(1)*x(2)-x(1)-x(2)+1;
  3. c(2)=-2*x(1)*x(2)-5;
  4. g=[];
复制代码

然后在工作空间键入程序:
  1. x0=[1,1];
  2. nonlcon=@ff8g
  3. [x, fval] =fmincon(@ff8,x0,[],[],[],[],[],[], nonlcon)
复制代码

结果:
x =-2.5000 1.0000
fval =3.3244
exitflag =1

当有等式约束时,要放在矩阵g的位置,如上例中加等式约束:
x(1)+2*x(1)=0

程序:首先建立 fun1.m文件:
  1. function[c,g]=ff8g1(x)
  2. c(1)=x(1)*x(2)-x(1)-x(2)+1;
  3. c(2)=-2*x(1)*x(2)-5;
  4. g(1)=x(1)+2*x(2);
复制代码

然后在工作空间键入程序:
  1. x0=[-1,1];
  2. nonlcon=@ff8g1;
  3. [x, fval,exitflag] =fmincon(@ff8,x0,[],[],[],[],[],[], nonlcon)
复制代码

结果:
x =-2.2361 1.1180
fval =3.6576
exitflag =1
 楼主| 发表于 2005-7-6 20:08 | 显示全部楼层
§3 二次规划模型

数学模型:
其中H为二次型矩阵,A、Aeq分别为不等式约束与等式约束系数矩阵,f,b,beq,lb,ub,x为向量。
求解二次规划问题函数为quadprog( )

调用格式:
  1. X= quadprog(H,f,A,b)
  2. X= quadprog(H,f,A,b,Aeq,beq)
  3. X= quadprog(H,f,A,b,Aeq,beq,lb,ub)
  4. X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
  5. X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
  6. [x,fval]= quadprog(…)
  7. [x,fval,exitflag]= quadprog(…)
  8. [x,fval,exitflag,output]= quadprog(…)
  9. [x,fval,exitflag,output,lambda]= quadprog(…)
复制代码

说明:输入参数中,x0为初始点;若无等式约束或无不等式约束,就将相应的矩阵和向量设置为空;options为指定优化参数。输出参数中,x是返回最优解;fval是返回解所对应的目标函数值;exitflag是描述搜索是否收敛;output是返回包含优化信息的结构。Lambda是返回解x入包含拉格朗日乘子的参数。

例1:求解:二次规划问题
  1. min f(x)= x1-3x2+3x12+4x22-2x1x2
  2. s.t 2x1+x2≤2
  3. -x1+4x2≤3
复制代码

程序:
  1. f=[1;-3]
  2. H=[6 -2;-2 8]
  3. A=[2 1;-1 4]
  4. b=[2;3]
  5. [X,fval,exitflag]=quadprog(H,f,A,b)
复制代码

结果:
X =
-0.0455
0.3636
fval =-0.5682
exitflag =1

例2:求解:二次规划问题
min +x12+2x22-2x1x2-4x1-12x2
s.t x1+x2≤2
-x1+2x2≤2
2x1+x2≤3
0≤x1, 0≤x2

程序:
  1. H=[2 -2;-2 4];
  2. f=[-4;-12];
  3. A=[1 1;-1 2;2 1];
  4. b=[2;2;3];
  5. lb=zeros(2,1);
  6. [x,fval,exitflag]=quadprog(H,f,A,b,[],[],lb)
复制代码

结果:
x =
0.6667
1.3333
fval =-16.4444
exitflag =1
 楼主| 发表于 2005-7-6 20:09 | 显示全部楼层
§4 多目标规划模型
多目标规划定义为在一组约束下,多个不同的目标函数进行优化设计。
数学模型:
s.t gj (x) ≤0 j=1, 2, … ,k
其中x=(x1 ,x2 , … ,xn)为一个n维向量;fi(x)为目标函数,i=1, 2, … ,m; gj (x)为系统约束, j=1, 2, … ,k。
当目标函数处于冲突状态时,不存在最优解使所有目标函数同时达到最优。于是我们寻求有效解(又称非劣解或非支配解或帕累托解)

定义:若 ( ∈Ω)的邻域内不存在Δx,使得( +Δx∈Ω),且
则称 为有效解。


多目标规划问题的几种常用解法:

(1) 主要目标法
其基本思想是:在多目标问题中,根据问题的实际情况,确定一个目标为主要目标,而把其余目标作为次要目标,并且根据经验,选取一定的界限值。这样就可以把次要目标作为约束来处理,于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。

(2) 线性加权和法
其基本思想是:按照多目标fi(x) (i=1, 2, … ,m)的重要程度,分别乘以一组权系数λj(j=1, 2, … ,m)然后相加作为目标函数而构成单目标规划问题。即 ,其中

例1:某钢铁厂准备用5000万用于A、B两个项目的技术改造投资。设x1、x2分别表示分配给项目A、B的投资。据专家预估计,投资项目A、B的年收益分别为70%和66%。同时,投资后总的风险损失将随着总投资和单项投资的增加而增加,已知总的风险损失为0.02x12+0.01x22+0.04(x1+x2)2,问应如何分配资金才能使期望的收益最大,同时使风险损失为最小。

建立数学模型
max f1(x)=70x1+66x2
min f2(x)= 0.02x12+0.01x22+0.04(x1+x2)2
s.t x1+x2≤5000
0≤x1, 0≤x2
线性加权构造目标函数: max f=0.5f1(x) –0.5f2(x)
化最小值问题: min (-f)=- 0.5f1(x) +0.5f2(x)


首先编辑目标函数M文件ff11.m
  1. function f=ff11(x)
  2. f=-0.5*(70*x(1)+66*x(2))+0.5*(0.02*x(1)^2+0.01*x(2)^2+0.04*(x(1)+x(2))^2);
复制代码

调用单目标规划求最小值问题的函数
  1. x0=[1000,1000]
  2. A=[1 1];
  3. b=5000;
  4. lb=zeros(2,1);
  5. [x,fval, exitflag]=fmincon(@ff11,x0, A,b,[],[],lb,[])
  6. f1=70*x(1)+66*x(2)
  7. f2=0.02*x(1)^2+0.01*x(2)^2+0.04*(x(1)+x(2))^2
复制代码

结果:
x =307.1428 414.2857
fval =-1.2211e+004
exitflag =1
f1 = 4.8843e+004
f2 = 2.4421e+004

(3) 极大极小法
其基本思想是:对于极小化的多目标规划,让其中最大的目标函数值尽可能地小为此,对每个 x∈R,我们先求诸目标函数值fi(x)的最大值,然后再求这些最大值中的最小值。即构造单目标规划:

(4) 目标达到法
对于多目标规划:
s.t gj (x) ≤0 j=1, 2, … ,n
先设计与目标函数相应的一组目标值理想化向量 ,
再设γ为一松弛因子标量。设 为权值系数向量。
于是多目标规划问题化为:

在Matlab的优化工具箱中,fgoalattain函数用于解决此类问题。

其数学模型形式为:
  1. min γ
  2. F(x)-weight ·γ≤goal
  3. c(x) ≤0
  4. ceq(x)=0
  5. A x≤b
  6. Aeq x=beq
  7. lb≤x≤ub
  8. 其中,x,weight,goal,b,beq,lb和ub为向量,A和Aeq为矩阵,c(x),ceq(x)和F(x)为函数,
复制代码


调用格式:
  1. x=fgoalattain(F,x0,goal,weight)
  2. x=fgoalattain(F,x0,goal,weight,A,b)
  3. x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq)
  4. x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub)
  5. x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
  6. x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)
  7. x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2)
  8. [x,fval]=fgoalattain(…)
  9. [x,fval,attainfactor]=fgoalattain(…)
  10. [x,fval,attainfactor,exitflag,output]=fgoalattain(…)
  11. [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返回包含拉格朗日乘子的参数。

例2:某化工厂拟生产两种新产品A和B,其生产设备费用分别为2万元/吨和5万元/吨。这两种产品均将造成环境污染,设由公害所造成的损失可折算为A为4万元/吨,B为1万元/吨。由于条件限制,工厂生产产品A和B的最大生产能力各为每月5吨和6吨,而市场需要这两种产品的总量每月不少于7吨。试问工厂如何安排生产计划,在满足市场需要的前提下,使设备投资和公害损失均达最小。该工厂决策认为,这两个目标中环境污染应优先考虑,设备投资的目标值为20万元,公害损失的目标为12万元。

建立数学模型:

设工厂每月生产产品A为x1吨,B为x2吨,设备投资费为f(x1),公害损失费为f(x2),则问题表达为多目标优化问题:
min f1(x)=2x1+5x2
min f2(x)=4x1+x2
s.t x1≤5
x2≤6
x1+x2≥7
x1 ,x2≥0

程序:首先编辑目标函数M文件ff12.m
  1. function f=ff12(x)
  2. f(1)=2*x(1)+5*x(2);
  3. f(2)= 4*x(1) +x(2);
复制代码

按给定目标取:
  1. goal=[20,12];
  2. weight=[20,12];
  3. x0=[2,2]
  4. A=[1 0; 0 1;-1 -1];
  5. b=[5 6 -7];
  6. lb=zeros(2,1);
  7. [x,fval,attainfactor,exitflag]=fgoalattain(@ff12,x0,goal,weight,A,b,[],[],lb,[])
复制代码

结果:
x =2.9167 4.0833
fval =26.2500 15.7500
attainfactor =0.3125
exitflag =1

例3:某工厂生产两种产品甲和乙,已知生产甲产品100公斤需6个工时,生产乙产品100公斤需8个工时。假定每日可用的工时数为48工时。这两种产品每100公斤均可获利500元。乙产品较受欢迎,且若有个老顾客要求每日供应他乙种产品500公斤,问应如何安排生产计划?

建立数学模型:
设生产甲、乙两种产品的数量分别为x和x(以公斤计),要使生产计划比较合理,应考虑用工时尽量少,获利尽量大,
其用多目标规划描述这:
min f1=6x1+8x2
max f2=100(x1+x2)
max f3=x2
s.t 6x1+8x2≤48
x2≥5
x1 ,x2≥0

将其标准化为:
min f1=6x1+8x2
min - f2=-100(x1+x2)
min - f3=-x2
s.t 6x1+8x2≤48
-x2≤-5
x1 ,x2≥0


程序:首先编辑目标函数M文件ff13.m
  1. function f=ff13(x)
  2. f(1)=6*x(1)+8*x(2);
  3. f(2)= -100*(x(1) +x(2));
  4. f(3)=-x(2);
复制代码

按给定目标取:
  1. goal=[48 -1000 -5];
  2. weight=[48 -1000 -5];
  3. x0=[2 2];
  4. A=[6 8; 0 -1];
  5. b=[48 -5];
  6. lb=zeros(2,1);
  7. [x,fval,attainfactor,exitflag]=fgoalattain(@ff13,x0,goal,weight,A,b,[],[],lb,[])
复制代码

结果:
x =1.3333 5.0000
fval =48.0000 -633.3333 -5.0000
attainfactor =1.6338e-008
exitflag =1

即生产计划为每日生产甲产品133.33公斤,生产乙产品500公斤
 楼主| 发表于 2005-7-6 20:11 | 显示全部楼层
§5 最大最小化模型

基本思想:在对策论中,我们常遇到这样的问题:在最不利的条件下,寻求最有利的策略。在实际问题中也有许多求最大值的最小化问题。例如急救中心选址问题就是要规划其到所有地点最大距离的最小值。在投资规划中要确定最大风险的最低限度等等。为此,对每个x∈R,我们先求诸目标值fi(x)的最大值,然后再求这些最大值中的最小值。

最大最小化问题的数学模型:

求解最大最小化问题的函数为 fmininax

调用格式:
  1. x=fminimax(F,x0,)
  2. x=fminimax(F,x0,,A,b)
  3. x=fminimax(F,x0,,A,b,Aeq,beq)
  4. x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub)
  5. x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub,nonlcon)
  6. x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub,nonlcon,options)
  7. x=fminimax(F,x0,,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2)
  8. [x,fval]=fminimax(…)
  9. [x,fval,maxfval]=fminimax(…)
  10. [x,fval,maxfval,exitflag,output]=fminimax(…)
  11. [x,fval,maxfval,exitflag,output,lambda]=fminimax(…)
复制代码


说明:F为目标函数;x0为初值; A、b为线性不等式约束的矩阵与向量;Aeq、beq为等式约束的矩阵与向量;lb、ub为变量x的上、下界向量;nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x);options中设置优化参数。

x返回最优解;fval返回解x处的目标函数值;maxfval返回解x处的最大函数值;exitflag描述计算的退出条件;output返回包含优化信息的输出参数;lambda返回包含拉格朗日乘子的参数。

例1 求解下列最大最小值问题:

首先编辑M文件ff14.m
  1. function f=ff14(x)
  2. f(1)=3*x(1)^2+2*x(2)^2-12*x(1)+35;
  3. f(2)=5*x(1)*x(2)-4*x(2)+7;
  4. f(3)=x(1)^2+6*x(2);
  5. f(4)=4*x(1)^2+9*x(2)^2-12*x(1)*x(2)+20;
复制代码

取初值x0=(1,1)调用优化函数
  1. x0=[1 1];
  2. [x,fval]=fminimax(@ff14,x0)
复制代码

结果:x =  1.7637 0.5317

fval =  23.7331 9.5621 6.3010 23.7331

例2:选址问题

设某城市有某种物品的10个需求点,第i个需求点Pi的坐标为(ai,bi),道路网与坐标轴平行,彼此正交。现打算建一个该物品的供应中心,且由于受到城市某些条件的限制,该供应中心只能设在x界于[5,8],y界于[5.8]的范围之内。问该中心应建在何处为好?

P点的坐标为:

01.png

建立数学模型:

设供应中心的位置为(x,y),要求它到最远需求点的距离尽可能小,此处采用沿道路行走计算距离,可知每个用户点Pi到该中心的距离为 |x-ai|+|y-bi|,于是有:

编程:首先编辑M文件:ff15.m
  1. function f = ff15(x)
  2. a=[1 4 3 5 9 12 6 20 17 8];
  3. b=[2 10 8 18 1 4 5 10 8 9];
  4. f(1) = abs(x(1)-a(1))+abs(x(2)-b(1));
  5. f(2) = abs(x(1)-a(2))+abs(x(2)-b(2));
  6. f(3) = abs(x(1)-a(3))+abs(x(2)-b(3));
  7. f(4) = abs(x(1)-a(4))+abs(x(2)-b(4));
  8. f(5) = abs(x(1)-a(5))+abs(x(2)-b(5));
  9. f(6) = abs(x(1)-a(6))+abs(x(2)-b(6));
  10. f(7) = abs(x(1)-a(7))+abs(x(2)-b(7));
  11. f(8) = abs(x(1)-a(8))+abs(x(2)-b(8));
  12. f(9) = abs(x(1)-a(9))+abs(x(2)-b(9));
  13. f(10) = abs(x(1)-a(10))+abs(x(2)-b(10));
复制代码

然后 用以下程序计算 :
  1. x0 = [6; 6];
  2. AA=[-1 0
  3. 1 0
  4. 0 -1
  5. 0 1];
  6. bb=[-5;8;-5;8];
  7. [x,fval] = fminimax(@ff15,x0,AA,bb)
复制代码

结果: x =
8
8

fval =13 6 5 13 8 8 5 14 9 1

即:在坐标为(8,8)处设置供应中心可以使该点到各需求点的最大距离最小,最小的最大距离为14单位。

评分

1

查看全部评分

发表于 2006-3-14 14:42 | 显示全部楼层
后面的看不大懂了,感觉好像例子和解不是对应的,前面的还可以
发表于 2006-3-22 07:58 | 显示全部楼层
论坛很多相关问题,自己找吧
发表于 2006-3-22 12:33 | 显示全部楼层
最好能把文件传上来,这种粘贴复制以后,丢失了一些东西:(
发表于 2006-3-27 19:18 | 显示全部楼层
写的太好了
先顶一下
自我感觉最优化是挺复杂的,现在我也就是用单纯形法解决些最简单的问题
发表于 2006-4-14 09:12 | 显示全部楼层
不好意思
没说明白
在最小二乘法里面的那个初始点是怎么选择的呢?
发表于 2006-4-14 10:36 | 显示全部楼层
楼主,DFP优化的有没有??
发表于 2006-4-18 22:58 | 显示全部楼层
太好了,谢谢阿
您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-11-28 16:50 , Processed in 0.103477 second(s), 26 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表