function y=ff(x1,x2)
%y=10*(x1+x2-5)^2+(x1-x2)^2;
y=x1^2+x2^2-x1*x2-10*x1-4*x2+60;
function alpha=goldmethod2(x01,x02,d,h0)
% 输入分割比gama
gama=0.618;
% 确定搜索区间[a,b]
[a,b]=search2(x01,x02,d,h0);
%计算a1,a2和函数值y1,y2, 确定最优步长alpha
a1=b-gama*(b-a);y1=ff(x01+d(1)*a1,x02+d(2)*a1);
a2=a+gama*(b-a);y2=ff(x01+d(1)*a2,x02+d(2)*a2);
for n=1:100
if y1>=y2
x1(n)=a1;x2(n)=a2;yp1(n)=y1;yp2(n)=y2;
a=a1;a1=a2;y1=y2;
a2=a+gama*(b-a);y2=ff(x01+d(1)*a2,x02+d(2)*a2);
else
x1(n)=a1;x2(n)=a2;yp1(n)=y1;yp2(n)=y2;
b=a2;a2=a1;y2=y1;
a1=b-gama*(b-a);y1=ff(x01+d(1)*a1,x02+d(2)*a1);
end
aa(n)=(a+b)/2; %输出极值点
y(n)=ff(x01+d(1)*aa(n),x02+d(2)*aa(n)); %输出极值点函数值e(n)=abs(b-a);
alpha=(a+b)/2;
if abs(b-a)<1e-5
break;
end
end
clear;
h0=0.1;
x0=[0,0];
e=[1,0;0,1];
xp=[0,0];
for k=1:20
k
for i=1:2
i
x01=x0(1);x02=x0(2);d=e(i,:);
alpha=goldmethod2(x01,x02,d,h0); % 确定最优步长alpha
alpha
x1=x0+alpha*d;
x0=x1;
xp
end
xn=x1;
if abs(xn-xp)<1e-1
break;
end
xp=xn;
end
clear;
% 给定初始值
h0=0.1;
x0=[0,0];
e=[1,0;0,1];
n=2;
for k=1:20
k % k 代表第轮计算
% 111111111111111111 第1 到n 次搜索计算111111111111111111 for i=1:1 % 第1次搜索
i
x01=x0(1);x02=x0(2);d=e(i,:);
F0=ff(x0(1),x0(2));
alpha=goldmethod2(x01,x02,d,h0); % 确定最优步长alpha
alpha
x(i,:)=x0+alpha*d;
F(i)=ff(x(i,1),x(i,2));
Delta(i)=F(i)-F0;
end
for i=2:n % 第2到n次搜索
i
x01=x(i-1,1);x02=x(i-1,2);d=e(i,:);
alpha=goldmethod2(x01,x02,d,h0); % 确定最优步长alpha
alpha
x(i,:)=x(i-1,:)+alpha*d;
F(i)=ff(x(i,1),x(i,2));
Delta(i)=F(i-1)-F(i);
end
% 1111111111111111111111111111111111111111111111111111111111
% 22222222222222222 精度是否满足要求22222222222222222222222 if abs(x(n,:)-x0)<1e-3
break;
end
% 2222222222222222222222222222222222222222222222222222222222
% 3333333333333333333 第n次结束参数计算33333333333333333333 d=x(n,:)-x0;
x(n+1,:)=2*x(n,:)-x0;
[Delta_m,j]=max(Delta);
F2=F(n);F3=ff(x(n+1,1),x(n+1,2));
% 3333333333333333333333333333333333333333333333333333333333
% 44444444444444444 搜索方向是否进行替换44444444444444444444 if F3
alpha=goldmethod2(x01,x02,d,h0); % 确定最优步长alpha
alpha
x(n+1,:)=x(n,:)+alpha*d;
e(j,:)=[];
e(n,:)=d;
x0=x(n+1,:);
else
if F2 x0=x(n,:); else x0=x(n+1,:); end end % 44444444444444444444444444444444444444444444444444444444444 x0 x end function [a,b]=search(x01,x02,d,h0) % search 为外推法确定搜索区间函数 % h0 为初始试探步长 % [a,b] 为搜索区间 %%%%%%%%%% 第一次搜索%%%%%%%%% a1=0; y1=ff(x01+d(1)*a1,x02+d(2)*a1); h=h0; a2=h; y2=ff(x01+d(1)*a2,x02+d(2)*a2); if y2>y1 %反向搜索 h=-h; a3=a1;y3=y1; a1=a2;y1=y2; a2=a3;y2=y3; end a3=a2+h;y3=ff(x01+d(1)*a3,x02+d(2)*a3); %%%%%%%%%% 继续搜索%%%%%%%%%% while y3 h=2*h; a1=a2;y1=y2; a2=a3;y2=y3; a3=a2+h; y3=ff(x01+d(1)*a3,x02+d(2)*a3); end %%%%%%%%%% 确定搜索区间%%%%%%%%%% if h>0 a=a1;b=a3; else a=a3;b=a1; end % a,b 实验一：线性规划单纯形算法 一、实验目的 通过实验熟悉单纯形法的原理，掌握Matlab 循环语句的应用,提高编程的能力和技巧。 二、实验用仪器设备、器材或软件环境 Windows Xp 操作系统 ,Matlab6.5，计算机 三、算法 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始 基本可行解。设初始基为B,然后执行如下步骤： (1).解B Bx b =,求得1 B x B b -=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量 (2).计算单纯形乘子w , B wB C =,得到1 B w C B -=,对于非基变量，计算判别数 1i i i B i i z c c B p c σ-=-=-,令 max{}k i i i R z c σ∈=-,R 为非基变量集合 若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一步 (3).解k k By p =,得到 1 k k y B p -=；若0k y ≤,即k y 的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4). (4).确定下标r,使 { } :0 min ,0 t r rk tk tk b b tk y y t y y >=>且r B x 为离基变量。 k x 为进基变量，用k p 替换r B p ，得到新的基矩阵B ，返回步骤（1）。 对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同。对于极大化问题，应令 min{}k k j j z c z c -=- 四、计算框图 是 否 是 否 开始 初始可行解B 令1,0,B N B B x B b b x f c x -==== 计算单纯形乘子1 B w c B -=，计算判别数,i j j wp c j R σ=-∈（非基变量） 令max{,}k j j R σσ=∈ 0?k σ≤ 得到最优解 解方程k k By p =，得到1k k y B p -=。 0?k y ≤ 不存在有限最优解 确定下标r ，是 { }:0 min ,0 t r rk tk tk b b tk y y t y y >=>且 k x 为进基变量，用 k p 替换r B p ，得到新的基矩阵B 优化设计方法的发展与应用情况 贾瑞芬张翔 （福建农林大学 机电工程学院， 福建 福州 ３５０００２） 摘 要：本文概要地介绍了优化设计方法在国内近年的应用和发展情况，包括传统优化方法、现代优化方法，以及优化软件的应用和发展情况。 关键词：优化 遗传算法 神经网络 ＭＡＴＬＡＢ 优化方法是２０世纪６０年代随着计算机的应用而迅速发展起来的，较早应用于机械工程等领域的设计。８０年代以来，随着国内有关介绍优化设计方法的专著（如《机械优化设计》［１］）的出版和计算机应用的普及，优化设计方法在国内的工程界得到了迅速的推广。本文按传统优化方法、现代优化方法、优化软件应用等三个方面，概要地介绍优化设计方法近年来在国内工程界的应用和发展情况。 １． 传统优化方法的应用与改进情况 １．１传统优化方法的应用 从近10年发表的工程优化设计的论文可以看出，罚函数法、复合形法、约束变尺度法、随机方向法、简约梯度法、可行方向法等，都有较为广泛的应用。对重庆维普信息数据库中的工程技术类刊物做检索，1993年至2003年，这6种约束优化方法应用的文献检出率的比例，依次约为12：10：3：1.5：1.5。 以机械设计为例，传统优化方法主要应用于机构和机械零部件的优化设计，主要对零件或机构的性能、形状和结构进行优化。在结构方面，如对升降天线杆的结构优化设计[2]，采用内点罚函数法优化，在保证天线杆具有足够的刚度和压弯组合强度的前提下所设计出的结构尺寸比按一般的常规设计方法所计算的尺寸要小，自重更轻。在形状方面，赵新海等［３］对一典型的轴对称Ｈ型锻件的毛坯形状进行了优化设计，取得了明显的效果。在性能方面，《凸轮一连杆组合机构的优化设计》［４］一文以最大压力角为最小做为优化目标、并采用坐标轮换法和黄金分割法等优化方法对书本打包机中的推书机构（凸纶—连杆组合机构）进行优化设计，从而使得机构确保运动的平衡性的前提下具有良好的传力性能，使设计结果更加合理。《弹性连杆机构结构和噪声控制一体化设计》［３７］一文，利用改进的约束变尺度法，求解基于噪声控制的弹性连杆机构结构控制同步优化问题，同步优化后机构的声辐射性能指标具有明显改善。由以上的例子可以看出，因此，传统优化方法仍然具有不可忽视的作用。 将优化技术与可靠性理论相结合，形成了可靠性优化设计法。按照可靠性优化设计法设计的产品，既能定量地回答产品在运行中的可靠性，又能使产品的功能参数获得优化解，两种方法相辅相成，是一种非常具有工程实用价值的设计方法。如采用惩罚函数内点法求解齿轮传动的可靠性优化设计的数学模型[5]，以及运用二阶矩法和约束随机方向法对钢板弹簧进行可靠性优化设计[6]。 １．２传统优化方法的一些改进 目前，随着工程问题的日益扩大，优化要面对的问题的规模和复杂程度在逐渐增大，传统的优化方法解决这些问题时，就显露出了其局限性与缺陷。于是就出现了在分析现有算法的基础上，针对方法的不足或应用问题而作出的改进。 1．2．1对传统优化方法应用于离散变量优化的改进 工程设计问题中，经常遇到设计变量必须符合本行业的设计规范和标谁，只能取为限定的离散值或整数值的情况。若应用连续变量优化方法．得到最优解后再作简单的圆整处理，可能造成设计上的不可行解，或得到一个非最优解。为此适用于变量取离散值的优化方法发展起来。朱浩鹏等[7]提出了改进的动态圆整法、拉格朗日松弛法。 惩罚函数优化方法是一种常用的求解约束非线性问题的方法，但它仅限于求解连续变量的优化问题。 #include 数 学 软 件 与 实 验 数学与信息科学学院 信息与计算科学 单纯形法的Matlab程序如下：function [xx,fm]=myprgmh(m,n,A,b,c) B0=A(:,1:m); cb=c(:,1:m); xx=1:n; sgm=c-cb*B0^-1*A; h=-1; sta=ones(m,1); for i=m+1:n if sgm(i)>0 h=1; end end while h>0 [msg,mk]=max(sgm); for i=1:m sta(i)=b(i)/A(i,mk); end [mst,mr]=min(sta); zy=A(mr,mk); for i=1:m if i==mr for j=1:n A(i,j)=A(i,j)/zy; end b(i)=b(i)/zy; end end for i=1:m if i~=mr for j=1:n A(i,j)=A(i,j)-A(i,mk)*A(mr,j); end b(i)=b(i)-A(i,mk)*b(mr); end end B1=A(:,1:m); cb(mr)=c(mk); xx(mr)=mk; sgm=c-cb*B1*A; for i=m+1:n if sgm(i)>0 h=1; end end end fm=c*xx; 例题： 编写下列求解如下线性规划问题的单纯形法函数min f'x s.t ax<=b(其中b>=0) 函数形式function [x,fval,it,op]=singl(f,a,b) 输出中x为最优解 fval为最优值 it为迭代次数 无最优解op=0 有最优解op=1 编写程序如下： function [x,fval,it,op]=singl(f,a,b) [m,n]=size(a); c=[a eye(m) b;f' zeros(1,m+1)]; fval=0; x=zeros(m+n,1); op=1; it=0; e=zeros(1,m); lie=find(f<0); l=length(lie); while(l>0) for j=1:l d=find(c(:,lie(j))); 用MATLAB 实现共轭梯度法求解实例 康福 1 一．无约束优化方法 1.1 无约束优化方法的必要性 一般机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它 们都属于约束优化问题。但是为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优 化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可 微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无 实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典 极值理论是无约束优化方法发展的基础。 1.2共轭梯度法 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向 上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度 法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方 法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中 每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量P 产生向量W=AP ，这不仅 可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由已知向量P 产 生向量W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 共轭梯度法原理的知识较多，请详见《机械优化设计》第四章的第四、五节。 图1为共轭梯度法的程度框图 1(0,1,2,) k k k k s k α+=+=x x %求解标准型线性规划:max c*x;s.t. A*x=b;x>=0 %本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b %N是初始的基变量的下标 %输出变量sol是最优解 %输出变量val是最优值，kk是迭代次数 function [sol,val,kk]=ssimplex(A,N) [mA,nA]=size(A); kk=0; %迭代次数 flag=1; while flag kk=kk+1; if A(mA,:)<=0 %已找到最优解 flag=0; sol=zeros(1,nA-1);%给每个变量赋初值0 for i=1:mA-1 sol(N(i))=A(i,nA);%给基变量赋新值(替换0) end %给出最优解 val=-A(mA,nA); else for i=1:nA-1 if A(mA,i)>0&A(1:mA-1,i)<=0 %问题有无界解 disp('have infinite solution!'); flag=0; break; end end if flag %还不是最优表，进行转轴运算 temp=0; for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i); inb=i; % 进基变量的下标 end end %选择最大检验数纵向对应的变量为进基变量 sita=zeros(1,mA-1); for i=1:mA-1 if A(i,inb)>0 sita(i)=A(i,nA)/A(i,inb); end end temp=inf; for i=1:mA-1 if sita(i)>0&sita(i) 现代设计方法及其应用matlab程序作业（） 源程序： %坐标轮换法 clear e=input('输入精度要求e：'); X=input('输入初始点：'); syms t s a=10*X(1,1)^2+106*X(2,1)^2+10*X(1,1)*X(2,1)+96*X(1,1)+100*X(2,1); k=1; e1=[1;0]; e2=[0;1]; A=X; %A矩阵用于存储每一轮变换所得解 C=X+t*e1; %沿e1方向搜索 x1=C(1,1); x2=C(2,1); df=diff(10*x1^2+106*x2^2+10*x1*x2+96*x1+100*x2); t=solve(df); X=X+t*e1; C=X+s*e2; %沿e2方向搜索 x1=C(1,1); x2=C(2,1); df=diff(10*x1^2+106*x2^2+10*x1*x2+96*x1+100*x2); s=solve(df); X=X+s*e2; A=[A X]; b=10*X(1,1)^2+106*X(2,1)^2+10*X(1,1)*X(2,1)+96*X(1,1)+100*X(2,1); a=[a b]; B=A(:,k+1)-A(:,k); while double(sqrt(B(1,1)^2+B(2,1)^2))>e syms t s C=X+t*e1; %沿e1方向搜索 x1=C(1,1); x2=C(2,1); df=diff(10*x1^2+106*x2^2+10*x1*x2+96*x1+100*x2); t=solve(df); X=X+t*e1; C=X+s*e2; %沿e2方向搜索 x1=C(1,1); x2=C(2,1); df=diff(10*x1^2+106*x2^2+10*x1*x2+96*x1+100*x2); s=solve(df); X=X+s*e2; A=[A X]; b=10*X(1,1)^2+106*X(2,1)^2+10*X(1,1)*X(2,1)+96*X(1,1)+100*X(2,1); a=[a b]; 算法实现与分析 算法1.单纯形法 具体算例: 标准化后: 用单纯形法求解,程序如下: clear clc M=1000000; A=[3,2,-3,1,0;1,-2,1,0,1];%系数矩阵 C=[-3,1,2,M,M,0];%价值矩阵 B=[6;4]; Xt=[4 5]; for i=1:length(C)-1 D=0; for j=1:length(Xt) D=D+A(j,i)*C(Xt(j)); end xi(i)=C(i)-D; end s=[]; for i=1:length(xi) if xi(i)<0 s=[s,i]; end end f=length(s); h=1; while(f) for k=1:length(s) j=1; A x=[]; for i=1:length(Xt) if A(i,s(k))>0 x(j)=i; j=j+1; end end x if(length(x)+1==1) break; end y=1 x for i=1:length(x) if B(x(i))/A(x(i),s(k)) 大学 机械优化设计部分程序 1.外推法 2.黄金分割法 3.二次插值法 4.坐标轮换法 5.随机方向法 6.四杆机构优化设计 1.外推法 源程序： #include #include 单纯形法（Matlab 程序） %%单纯形法( Matlab 程序) a=input('input the major matrix A '); b=input('input the matrix b '); n=input('input the judgement '); %%为计数器(确定循环次数) g=0; while g<40 %%确定非负 alength=max(size(n)); blength=max(size(b)); m=0; for i=1:alength if n(i)>=0 m=m+1; end end; if m==alength x=b; break end; %%找 K s=min(n); for i=1:alength if n(i)==s k=i; break end; end; %%a[i,k] 的非负性 m=0; for i=1:blength if a(i,k)<0 m=m+1; end; end; if m==blength disp('x does not exit'); judge=1; break end; %%找 L 确定主元 cc=100000; for i=1:blength if a(i,k)>0 if (b(i)/a(i,k))< cc cc=b(i)/a(i,k); end end end; for i=1:blength if a(i,k)~=0 if (b(i)/a(i,k))==cc l=i; break end end end; %%计算 ,a 标准化 zu=a(l,k); aa=a; for i=1:l-1 for j=1:alength aa(i,j)=a(i,j)- a(l,j)*a(i,k)/a(l,k); end end; for i=l+1:blength for j=1:alength aa(i,j)=a(i,j)- a(l,j)*a(i,k)/a(l,k); end end; for j=1:alength aa(l,j)=a(l,j)/zu; end; %%b勺判别 bb=b; bb(l)=b(l)/zu; for i=1:l-1 bb(i)=b(i)- b(l)*a(i,k)/a(l,k); end; for i=l+1:blength bb(i)=b(i)- b(l)*a(i,k)/a(l,k); end; b=bb; %%确定判别数 线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。 8.2.1 基本数学原理 线性规划问题的标准形式是： ????? ??????≥=+++=+++=++++++=0,,,min 21221122222121112 121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a x c x c x c z 或 ???? ?????=≥===∑∑==n j x m i b x a x c z j n j i j ij n j j j ,,2,1,0,,2,1,min 1 1 写成矩阵形式为： ?? ???≥==O X b AX CX z min 线性规划的标准形式要求使目标函数最小化，约束条件取等式，变量b 非负。不符合这几个条件的线性模型可以转化成标准形式。 MATLAB 采用投影法求解线性规划问题，该方法是单纯形法的变种。 8.2.2 有关函数介绍 在MATLAB 工具箱中，可用linprog 函数求解线性规划问题。 linprog 函数的调用格式如下： ●x=linprog(f,A,b)：求解问题minf'*x ，约束条件为A*x<=b 。 ●x=linprog(f,A,b,Aeq,beq)：求解上面的问题，但增加等式约束，即Aeq*x=beq 。若没有不等式约束，则令A=[ ],b=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub)：定义设计x 的下界lb 和上界ub ，使得x 始终在该范围内。若没有等式约束，令Aeq=[ ],beq=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0)：设置初值为x0。该选项只适用于中型问题，默认时大型算法将忽略初值。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)：用options 指定的优化参数进行最小化。 ●[x,fval]=linprog(…)：返回解x 处的目标函数值fval 。 ●[x,lambda,exitflag]=linprog(…)：返回exitflag 值，描述函数计算的退出条件。 ●[x,lambda,exitflag,output]=linprog(…)：返回包含优化信息的输出参数output 。 ●[x,fval,exitflag,output,lambda]=linprog(…)：将解x 处的拉格朗日乘子返回到lambda 参数中。 基于MATLAB的鲍威尔法求极值问题 姓名：xxx 学号：xxx （北京理工大学机械与车辆学院车辆工程，北京 100081） 摘要：无约束优化方法主要有七种，按照求导与否把这些方法分为间接法和直接法。牛顿法的成败与初始点选择有极大关系，其可靠性最差；坐标轮换法、单纯形法和最速下降法对于高维优化问题计算效率很低，有效性差；由于编制变尺度法程序复杂，其简便性不足。综合考虑后，鲍威尔法、共轭梯度法具有较好的综合性能。本文首先对鲍威尔法的原理进行阐述，根据其迭代过程给出流程图，并编写MATLAB程序。最后用此MATLAB程序求解实际的极值问题，并对求解结果进行简要分析。 1.鲍威尔法的基本思想 1.1其他优化方法对鲍威尔法形成的影响 通过对鲍威尔法的学习，可以很明显看出来其迭代思想中汲取了其他几种优化方法的核心思想。为了更全面、更深入的学习鲍威尔法，很有必要对其他有影响的优化思想进行学习和梳理。 由最基本的数学基础知识可知，梯度方向是函数增加最快的方向，负梯度方向是函数下降最快的方向，于是，利用这个下降最快方向产生了最速下降法。每次迭代都沿着负梯度方向进行一维搜索，直到满足精度要求为止。其特点是相邻两个搜索方向互相正交，所以很明显的一个现象就是刚开始搜索步长比较大，愈靠近极值点其步长愈小，收敛速度愈慢，特别当二维二次目标函数的等值线是较扁的椭圆时，迭代速度更慢。这时，倘若目标函数是等值线长、短轴都平行于坐标轴的椭圆形，则通过坐标轮换法可以很高效的解决问题。通过两次分别沿坐标轴进行一维搜索，便可达到极值点。但对于目标函数的等值线椭圆的长、短轴倾斜于坐标轴时，坐标轮换法的搜索效率也显得极低。抛开这两种特殊情况，对于一般形态的目标函数，如果在某些明显可以直达最优点的情况下（一般为靠近极 多目标线性规划的若干解法及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 为等式约束 北京联合大学 实验报告 项目名称：运筹学专题实验报告 学院：自动化专业：物流工程 班级： 1201B 学号：2012100358081 姓名：管水城成绩： 2015 年 5 月 6 日 实验二：MATLAB 编程单纯形法求解 一、实验目的： (1)使学生在程序设计方面得到进一步的训练;，掌握Matlab (C 或VB)语言进行程序设计中一些常用方法。 (2)使学生对线性规划的单纯形法有更深的理解. 二、实验用仪器设备、器材或软件环境 计算机, Matlab R2006 三、算法步骤、计算框图、计算程序等 本实验主要编写如下线性规划问题的计算程序: ?? ?≥≥≤0 ,0..min b x b Ax t s cx 其中初始可行基为松弛变量对应的列组成. 对于一般标准线性规划问题: ?? ?≥≥=0 ,0..min b x b Ax t s cx １．求解上述一般标准线性规划的单纯形算法（修正）步骤如下： 对于一般的标准形式线性规划问题(求极小问题),首先给定一个初始基本可行解。设初始基为B,然后执行如下步骤： (1).解B Bx b =,求得 1 B x B b -=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量 (2).计算单纯形乘子w, B wB C =,得到1 B w C B -=,对于非基变量，计算判别 数1i i i B i i z c c B p c σ-=-=-,可直接计算 σ =1 B A c c B --令 max{}k i R σσ∈=,R 为非基变量集合 若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一 步 (3).解k k By p =,得到 1 k k y B p -=；若0k y ≤,即k y 的每个分量均非正数， 则停止计算，问题不存在有限最优解，否则，进行步骤(4).确定下标r,使 { }:0 min ,0 t r rk tk tk b b tk y y t y y >=>且r B x 为离基变量, ,r k B x p k 为进基变量,用p 替换得到新的基矩阵B,还回步骤(1) ; 【最新整理，下载后即可编辑】 用MATLAB 实现共轭梯度法求解实例 康福 201103710031 一．无约束优化方法 1.1 无约束优化方法的必要性 一般机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。但是为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达 到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令一阶导数为零， 但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。 1.2共轭梯度法 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺 度法、共轭梯度法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 1(0,1,2,)k k k k s k α+=+=x x 搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量P产生向量W=AP，这不仅可充分利用Ａ的稀疏性，而且对某些提供 矩阵Ａ较为困难而由已知向量P产生向量W=AP又十分方便 的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像SOR等；（3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 共轭梯度法原理的知识较多，请详见《机械优化设计》第四章的第四、五节。 图1为共轭梯度法的程度框图 大连民族学院 数学实验报告 课程：____________________ 最优化方法______________________ 实验题目： ___________ 单纯形法的matlab实现 ___________________ 系别：______________________ 理学院________________________ 专业：__________________ 信息与计算科学____________________ 姓名：__________________________________________________ 班级：_____________________ 信息102班 ____________________ 指导教师：___________________ 葛仁东_______________________ 完成学期：2013 年__9 ___________ 月_2________ 日 实验目的： 实验方法和步骤(包括数值公式、算法步骤、程序) ： 考察标准形式的线性规划问题： min f(x) C T x s.t Ax b, x 0 设x(k)F为一个基本可行解，单纯形方法首先检验它的最优性。如果它不是最优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这个边移 动多远可以到达另一个更优的相邻点，也就是得出一个新的基本可行解 算法步骤： 步骤1给定一个初始基本可行解，记迭代次数 k 1 ； 步骤2 :计算单纯形乘子y k B k T c B k)和简约价值系数向量C N k) c N k) N T y k ； 步骤3 :最优性检验，计算C?k) min{C (k)|j 2}，如果C?k) 0，则x (k)为最优解， 停止迭代；否则有x p 0，选x p 为入基变量； 步骤4:确定出基变量，计算g k) B k 1a p ，如果对所有j B k ，有器)0,则问题 无有界的最优解，停止迭代；否则确定出基变量指标 步骤5:交换B k 的列a q 与N k 的列a p 得到新的基矩阵 盼和山+1，计算新的基本可 行解 x (k1),置k:k 1后转步骤 2； 在上述算法中，当存在不止一个简约价值系数 C j k) 0时，选取最负的?“的 指标为p ，并以X p 作为入基变量。 Matlab 计算程序： Function] x,f]=zuiyouhua(A,b,c) Size(A)=[m, n]; i=n+1: n+m; N=1: n; B=eye(m,m); xb=b '; xn=zeros(m,1); f1=0; w=zeros(1,m); z=-c; flag=1; while(1) [a,k]=max(z); If a<=0 flag=0; break else y=i nv(B)*A(:,k) b (k) B k }； min{ _(k )殆 0, j 最优化方法及其Matlab程序设计 1.最优化方法概述 在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证，从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。最优化是每个人，每个单位所希望实现的事情。对于产品设计者来说，是考虑如何用最少的材料，最大的性能价格比，设计出满足市场需要的产品。对于企业的管理者来说，则是如何合理、充分使用现有的设备，减少库存，降低能耗，降低成本，以实现企业的最大利润。 由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。 用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型。 即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解。 数学模型建好以后，选择合理的最优化算法进行求解。 最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 2.最优化方法（算法）浅析 最优化方法求解很大程度上依赖于最优化算法的选择。这里，对最优化算法做一个简单的分类，并对一些比较常用的典型算法进行解析，旨在加深对一些最优化算法的理解。 最优化算法的分类方法很多，根据不同的分类依据可以得到不同的结果，这里根据优化算法对计算机技术的依赖程度，可以将最优化算法进行一个系统分类：线性规划与整数规划；非线性规划；智能优化方法；变分法与动态规划。 2.1 线性规划与整数规划 线性规划在工业、农业、商业、交通运输、军事和科研的各个研究领域有广泛应用。例如，在资源有限的情况下，如何合理使用人力、物力和资金等资源，以获取最大效益；如何组织生产、合理安排工艺流程或调制产品成分等，使所消耗的资源（人力、设备台时、资金、原始材料等）为最少等。 线性规划方法有单纯形方法、大M法、两阶段法等。 整数规划有割平面法、分枝定界法等。 2.2 非线性规划 20世纪中期，随着计算机技术的发展，出现了许多有效的算法——如一些非线性规划算法。非线性规划广泛用于机械设计、工程管理、经济生产、科学研究和军事等方面。 function Z=dcxf(c,A,N) %定义函数名称为dcxf。 l=length(N); CB=c(N(1):N(l)) [m,n]=size(A); b=A(:,n); A=A(:,1:n-1); %参数包括目标函数系数(C)，约束条件的系数矩阵(A)， %其中A的最后一列为约束条件的右端值b，初始基向量的位置(N)。 sigma=c-CB*A;%计算检验数sigma。 display('初始单纯形表为:');%输出初始的单纯形表table=[nan,nan,nan,c;CB',N',b,A;nan,nan,nan,si gma] opt=1;step=0; while opt step=step+1;%定义循环，直到第“step”步找到最优解(opt=0)。 if sum(sigma>0)==0 %利用检验数判断是否得到最优解，并给出提示。 display('没有得到最优解,继续迭代．'); opt=0; else inb=find(sigma==max(sigma)); %利用单纯形方法找到入基变量的位置 num=length(inb); Inb=inb(num) flag=0; for i=1:m %利用单纯形方法找出出基变量的位置 if A(i,inb)>0 theta(i)=b(i)/A(i,inb); else theta(i)=inf; end end outb=find(theta==min(theta)); num=length(outb); %判断足否出现退化现象，如出现退化，给il{语言提示，并取最后出现的符合出基条件的变量为出基变量。 if num~=1 display('出现退化情况．'); end outb=outb(num); 《机械优化设计》复习题 一、填空 1、用最速下降法求f(X)=100(x 2- x 12) 2+(1- x 1) 2的最优解时，设X （0）＝[-0.5,0.5]T ，第一步迭代的搜索方向为[-47;-50] 。 2、机械优化设计采用数学规划法,其核心一是建立搜索方向 二是计算最佳步长因子 。 3、当优化问题是__凸规划______的情况下，任何局部最优解就是全域最优解。 4、应用进退法来确定搜索区间时，最后得到的三点，即为搜索区间的始点、中间点和终点，它们的函数值形成 高-低-高 趋势。 5、包含n 个设计变量的优化问题，称为 n 维优化问题。 6、函数 C X B HX X T T ++2 1的梯度为 HX+B 。 7、设G 为n ×n 对称正定矩阵，若n 维空间中有两个非零向量d 0，d 1，满足(d 0)T Gd 1=0，则d 0、d 1之间存在_共轭_____关系。 8、 设计变量 、 约束条件 、 目标函数 是优化设计问题数学模型的基本要素。 9、对于无约束二元函数),(21x x f ，若在),(x 20100x x 点处取得极小值，其必要条件是 梯 度为零 ，充分条件是 海塞矩阵正定 。 10、 库恩-塔克 条件可以叙述为在极值点处目标函数的梯度为起作用的各约束函数梯度的非负线性组合。 11、用黄金分割法求一元函数3610)(2+-=x x x f 的极小点，初始搜索区间 ]10,10[],[-=b a ，经第一次区间消去后得到的新区间为 [-2.36,2.36] 。 12、优化设计问题的数学模型的基本要素有设计变量 、约束条件 目标函数 、 13、牛顿法的搜索方向d k = ，其计算量 大 ，且要求初始点在极小点 逼近 位置。 14、将函数f(X)=x 12+x 22-x 1x 2-10x 1-4x 2+60表示成 C X B HX X T T ++2 1的形式 。最优化实验报告(单纯形法的matlab程序,lingo程序)
优化设计方法的发展与应用情况
约束坐标轮换法
单纯形法matlab
用MATLAB实现共轭梯度法求解实例
matlab单纯形法
坐标轮换法matlab程序
单纯形法matlab程序
机械优化设计黄金分割法 外推法
单纯形法MATLAB程序
运用Matlab进行线性规划求解(实例)
基于MATLAB的鲍威尔法求极值问题
多目标线性规划的若干解法及MATLAB实现
实验二：MATLAB编程单纯形法求解
用MATLAB实现共轭梯度法求解实例(精编文档).doc
单纯形法的matlab实现(20200814192014)
最优化方法及其Matlab程序设计
单纯形法matlab程序
【机械优化设计】试题(卷)答案解析
相关主题
文本预览