最优化实验报告

最优化方法

课程设计报告班级：________________

姓名： ______

学号： __________

成绩：

2017年 5月 21 日

目录

一、摘要 (1)

二、单纯形算法 (2)

1.1 单纯形算法的基本思路 (2)

1.2 算法流程图 (3)

1.3 用matlab编写源程序 (4)

二、黄金分割法 (7)

2.1 黄金分割法的基本思路 (7)

2.2 算法流程图 (8)

2.3 用matlab编写源程序 (9)

2.4 黄金分割法应用举例 (11)

三、最速下降法 (11)

3.1 最速下降法的基本思路 (11)

3.2 算法流程图 (13)

3.3 用matlab编写源程序 (13)

3.4 最速下降法应用举例 (13)

四、惩罚函数法 (17)

4.1 惩罚函数法的基本思路 (17)

4.2 算法流程图 (18)

4.3 用matlab编写源程序 (18)

4.4 惩罚函数法应用举例 (19)

五、自我总结 (20)

六、参考文献 (20)

一、摘要

运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。通过对数据的调查、收集和统计分析，以及具体模型的建立。收集和统计上述拟定之模型所需要的各种基础数据，并最终将数据整理形成分析和解决问题的具体模型。

最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB 这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。

关键词：优化、线性规划、黄金分割法、最速下降法、惩罚函数法

二、单纯形算法

1.1 单纯形算法的基本思路

线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。

单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。

概述：根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。

求解线性规划问题的目的就是要找出最优解。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。

求解时可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

要缩小对最优解的搜索范围，就必须认识最优解的一般性质，最优解如果存在的话，则它必然处于可行区域的边界上。

任何一项约束条件的边界方程是用“＝”号来替换该约束条件中的“≤”

或“≥”号而得到的。每一个边界方程确定一个超平面。因此，可行区域的边界是由那些满足一个或同时满足几个边界方程（即处在作为边界的一个或几个超平面上）的可行解所组成，而且最优解必在其中。最优解不仅是在可行区域的边界上，而且也在这个区域的一个隅角上。一个可行解，如果不处在由另两个可行解连接起来的任何线段上，它就是一个角点可行解。如果连接两个角点可行解的线段处在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。

角点可行解具有下列三个重要性质：

①如果存在着一个最优解，那么它必定是角点可行解。如果存在有多个最优解，那么至少有两个最优解必定是相邻的角点可行解。

②只存在有限个数的角点可行解。

③如果一个角点可行解按目标函数值来衡量时比其所有的相邻角点可行解

更好一些，那它就比所有其他角点可行解都更好，也就是最优解。

上述这些性质构成单纯形法的原理基础。

最后一个性质的重要性在于它为一个角点可行解是否是最优解提供了一种简便的检验标准，因而毋需列举所有的可行解。单纯形法正是利用了这个性质，只要检查少数的角点可行解，并且一旦这个最优性检验获得通过就可立即停止运算。

1.2 算法流程图

（1）、确定初始基可行解

①从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量；

②对约束条件全为“<=”连接的LP，化为标准形，左端添加松弛变量后即形成一个单位子矩阵；

③约束条件中含有“<=”或“=”连接的方程，在插入剩余变量后找不到单位矩阵，则必须采用“人造基”法，

（2）、单纯形法的运算步骤可归结为：

①起始步骤──在一个角点可行解上开始。

②迭代步骤──移动至一个更好一些的相邻角点可行解（根据需要反复进行这一步骤）。

③停止法则──在当前角点可行解比所有相邻角点可行解都更好些时停止。当前角点可行解就是一个最优解。单纯形法的优点及其成功之处在于它只需要较少的有限次数的迭代，即可找到最优解。

（3）、单纯形法的算法流程如下：

①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。

②若基本可行解不存在，即约束条件有矛盾，则问题无解。

③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

1.3 用matlab编写源程序

Matlab程序源代码：

----------- simplexTab.m子函数-------------------------------------------------------- function simplexTab(mat,numFreeVar)

maxRow=length(mat(:,1));

maxCol=length(mat(1,:));

objEntryExcludingMaxPayOff=mat(maxRow,1:maxCol-2);

[objEnt bestColToPivot]=min(objEntryExcludingMaxPayOff);

while(objEnt<0)

lastColExcludingObjEnty=mat(1:(maxRow-1),maxCol);

ithColExcludingObjEnty=mat(1:(maxRow-1),bestColToPivot);

a=lastColExcludingObjEnty./ithColExcludingObjEnty;

[val bestRowToPivot]=min(a);

sprintf('the best Pivot is %d row and %d col ',bestRowToPivot,bestColToPivot) disp('单纯形表化为：');

[mat,[a;0]]

disp('按任意键继续');

pause;

if(val<0)

[s indices]=sort(a);

if(max(a)>0)

count=1;

while(s(count)<0)

count=count+1;

end

bestRowToPivot=indices(count);

end

end

if(length(a)==0)

length(a)

return

end

mat=pivot(mat,bestRowToPivot,bestColToPivot);

objEntryExcludingMaxPayOff=mat(maxRow,1:maxCol-2);

[objEnt bestColToPivot]=min(objEntryExcludingMaxPayOff);

end

sprintf('the best Picot is %d 行and %d 列',bestRowToPivot,bestColToPivot) disp('单纯形表化为：');

[mat,[a;0]]

disp('运行结束!');

--------------------------------------------------------------- ----------- interChange .m子函数-------------------------------------------------------

function newMat=interChange(mat,row1,row2) temp=mat(row1,:);

mat(row1,:)=mat(row2,:); mat(row2,:)=temp; newMat=mat;

--------------------------------------------------------------- -----------multiFromRowToRow.m 子函数-------------------------------------------- function newMat=multiFromRowToRow(mat,fromRow,toRow,multiplier) rG=mat(fromRow,:)*multiplier; mat(toRow,:)=rG+mat(toRow,:); newMat=mat;

--------------------------------------------------------------- -----------multMat.m 子函数------------------------------------------------------------- fuction newMat=multMat(mat,row,mult)

%multiply a row of a matrix by a nonzero constant mat(row,:)=mat(row,:)*mult; newMat=mat;

--------------------------------------------------------------- -----------pivot.m 子函数------------------------------------------------------------------- function newMat=pivot(mat,row,col) %normalize this row

mat(row,:)=mat(row,:)./mat(row,col);%make the leadinga number a 1 for r=1:length(mat(:,1)) if(r~=row)

mat=multiFromRowToRow(mat,row,r,-mat(r,col)); end end

newMat=mat;

-----------------------------------------------------------------------------------------------

1.4 单纯形算法应用举例

题目： 使用单纯形法解下面线性规划问题：

目标函数为：321max x x x f ---=； 约束条件是： 1937321≤++x x x

..t s

1458321≤++x x x

1596321≤++x x x

0,,321≥x x x

解：化为标准形式：

654321000max x x x x x x g +++++=

100937654321=+++++x x x x x x

..t s

100458654321=+++++x x x x x x 100596654321=+++++x x x x x x

0,,,,,654321≥x x x x x x

利用Matlab 程序计算：

命令窗口输入：

mat=[7 3 9 1 0 0 1; 8 5 4 0 1 0 1; 6 9 5 0 0 1 1; -1 -1 -1 0 0 0 0];

numFreeVar=3;%自由变量个数 simplexTab(mat,numFreeVar) 结果输出： 初始结果：

ans = the best Pivot is 2 row and 1 col 单纯形表化为：

7.0000 3.0000 9.0000 1.0000 0 0 1.0000 0.1429

8.0000 5.0000 4.0000 0 1.0000 0 1.0000 0.1250 6.0000 9.0000 5.0000 0 0 1.0000 1.0000 0.1667 -1.0000 -1.0000 -1.0000 0 0 0 0 0

第一次转换结果:

ans = the best Pivot is 1 row and 3 col 单纯形表化为：

0 -1.3750 5.5000 1.0000 -0.8750 0 0.1250 0.0227

1.0000 0.6250 0.5000 0 0.1250 0 0.1250 0.2500 0 5.2500

2.0000 0 -0.7500 1.0000 0.2500 0.1250 0 -0.3750 -0.5000 0 0.1250 0 0.1250 0

第二次转换结果:

ans = the best Pivot is 1 row and 2 col 单纯形表化为：

0 -0.2500 1.0000 0.1818 -0.1591 0 0.0227 -0.0909

1.0000 0.7500 0 -0.0909 0.2045 0 0.1136 0.1515 0 5.7500 0 -0.3636 -0.4318 1.0000 0.2045 0.0356 0 -0.5000 0 0.0909 0.0455 0 0.1364 0

第三次转换结果:

ans = the best Picot is 3 row and 1 col

)0356.0,0870.0,0316.0(=x ，1542.0=g ，

1542.0321-=---=x x x f

所以该线性规划的最优解是1542.0=g 。

二、 黄金分割法

2.1 黄金分割法的基本思路

一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。

黄金分割法是用于一元函数)(x f 在给定初始区间[a,b]内搜索极小点min x 的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数，即只在单峰区间内才能进行一维寻优，其收敛效率较低。

其基本原理是：

依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间。 具体步骤是：

在区间[a,b]内取点：1a ,2a 把[a,b]分为三段。

① 如果)(1a f >)(2a f ，令a=1a , a1=2a , 2a =a+0.618*(b-a)；

② 如果)(1a f <)(2a f ，令b=2a ，2a =1a , 1a =b-0.618*(b-a)； 如果b a b /)(-和221/)(y y y -都大于收敛精度ε重新开始循环。 因为[a,b]为单峰区间，这样每次可将搜索区间缩小0.618倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区[a,b]逐步缩小，直到满足预先给定的精度时，即获得一维优化问题的近似最优解。

插入点原理图如下：

21λλ=- → 012=-+λλ → 618.0=λ

所谓的黄金分割法，是指将一线段分成两段的方法，使整段的长与较长段的长的长度比值等于较长段与较短段的比值，即：

)1(::1λλλ-=

2.2 算法流程图

黄金分割法的算法步骤： 给定a, b （a>b ），控制误差0>ε。

一般取[a, b]为[0,1]，当然也可以根据自己需要调整。如果目标函数对变量非常灵敏，可以将补偿的可行范围进行范围缩小，以提高搜索精度；反之，可以将步长的可行范围放大，以提高算法的计算速度。

2.3 用matlab编写源程序

Matlab程序源代码：

---------golden.m子函数--------------------------------------- function Pa=golden(x,p,LowBound,UpBound)

%golden is function for golden linear search

%x (k+1) =x (k) +Pa*p;

%input:

% x:搜索初始点

% p:搜索方向

% LowBound,UpBound:搜索区间

%output:

% Pa:搜索步长

%disp ('it is the golden linereasch');

% 搜索步长范围[0,1]可以根据需要修改

gold_a=LowBound;

gold_b=UpBound;

z2=gold_a+0.618*(gold_b-gold_a); %%step1

f2=objfun(x+z2*p);

z1=gold_a+0.382*(gold_b-gold_a); %%step2

f1=objfun(x+z1*p);

in_itera=0;

while abs(gold_b-gold_a)>0.0000000001

% abs a=0,b=1 golden linesearch

in_itera=in_itera+1;

%f1, f2

if f1

gold_b=z2;

z2=z1;

f2=f1;

z1=gold_a+0.382*(gold_b-gold_a);

f1=objfun(x+z1*p);

continue

elseif f1==f2

gold_a=z1;

gold_b=z2;

z2=gold_a+0.618*(gold_b-gold_a); %%step2

f2=objfun(x+z2*p);

z1=gold_a+0.382*(gold_b-gold_a); %%step2

f1=objfun(x+z1*p);

continue

else

gold_a=z1;

z1=z2;

f1=f2;

z2=gold_a+0.618*(gold_b-gold_a);

f2=objfun(x+z2*p);

end

end

Pa= (gold_a+gold_b)/2; %Pa x(k+1)=x(k)+Pa*p;

disp('最优解是：')

%Pa,in_itera

%obj(x+Pa*p)

---------------------------------------------------------------- -----------objfun.m子函数--------------------------------------- function f=objfun(x)

f=x(1)^3+x(2)^2-10*x(1)*x(2)+1;

----------------------------------------------------------------

2.4 黄金分割法应用举例

题目： 利用黄金分割法求解下面函数的最优解：

110212

231+-+=x x x x f

解：

利用Matlab 程序计算：

命令窗口输入： X=[0,0];P=[1,1]; Pa=golden(X,P,0,1) 结果输出：

最优解是： Pa = 1.0000

三、 最速下降法

3.1 最速下降法的基本思路

最速下降法的搜索法向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。

已知目标函数在()

k X

点的梯度为：

()()

()()()()()()12

...

T

k k k k n f X f X f X f X x x x ??

????

??=??????

?

当求目标函数的最小点时，由于函数沿负梯度方向下降最快，故在()

k X 点的

探索方向应取该点的负梯度方向，即

()()

()()()

k k k f X S f X

?=-

?

显然，()

k S

为单位向量。这样第1k +次迭代计算所得的新点为

()

()

()()(1)()()()()()

k k k k k k k k f X X X S X f X

αα+?=+=-

?

负梯度仅给出了最优化方向，而没有给出步长的大小，所以可能有各种各样的最速下降的过程，它们依赖于

()

()

()

k k f X

α?的大小。

步长()k α有两种取法：

一种方法是任意给定一个初始步长，使满足条件：

()()()()()()k k k k f X S f X α+<

另外一种方法是沿负梯度方向做一维探索，以求解一维最优化问题的最优步长α，即对目标函数极小，以得到最优步长：

()()()()()0

min ()()k k k k k f X S f X S ααα>+=+

以此最优步长作为由()k X 点出发沿该点的负梯度方向探索的步长()k α。 这种方法的迭代计算的收敛性，可用以下三式中的任一式或二式作为准则来进行判断：

()()()()()1()(1)

2()()

(1)

3k k k k k k f X f X f X f X X X

εεε--??≤?

?-?≤??

?-≤??

用最速下降法求无约束多维极值问题min (),n f x x R ∈的算法步骤如下：

（1）、取初始点(0)

x ，精度0ε>，令0k =

（2）、计算搜索方向()()()k k v f x =-?，其中()()k f x ?表示函数()f x 在点()k x 处的梯度；

（3）、若()k v ε≤，则停止计算；否则，从()k x 出发，沿()k v 进行一维搜索，即求k λ，使得()()()()0

()min ()k k k k k f x v f x v λλλ≥+=+。此处的一维搜索可以用

MATLAB 的unc f min 函数；令(1)()(),1k k k k x x v k k λ+=+=+，转步骤（2）。

3.2 算法流程图

3.3 用matlab 编写源程序

-----------BanaFunWithGrad.m 子函数------------------------------------------------

function [f,g]=BanaFunWithGrad(x) %(不含导数解析式) f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;

g=[100*(4*x(1)^3-4*x(1)*x(2))+2*x(1)-2;100*(2*x(2)-2*x(1)^2)];

---------------------------------------------------------------- -----------BanaFun.m 子函数-------------------------------------------------------------

function f=BanaFun(x) %(含导数解析式) f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;

----------------------------------------------------------------

3.4 最速下降法应用举例

题目： 求解函数212

212)1()(100

x x x f -+-=

解：

利用Matlab程序计算：

命令窗口输入：

OPTIONS=optimset('LargeScale','off','HessUpdate','steepdesc','gradobj','on','MaxFu nEvals',250,'display','iter');

x=[-1.9,2];

[x,fval,exitflag,output]=fminunc(@BanaFunWithGrad,x,OPTIONS)

结果输出：

迭代次数函数计算次数函数值步长一阶导数最优性

Gradient's Iteration Func-count f(x) Step-size infinity-norm

0 1 267.62 1.23e+003

1 2 214.416 0.000813405 519

2 9 5.83639 0.0009849

3 13.4

3 15 5.78292 0.000567305 1.58

4 18 5.73127 0.0387979 12.9

5 24 5.68023 0.00058373

6 1.59

6 2

7 5.63081 0.0367599 12.5

7 33 5.5819 0.000600291 1.6

8 36 5.53444 0.0349482 12.1

9 42 5.48743 0.000617009 1.61

10 45 5.44173 0.0333245 11.7

11 51 5.39641 0.000633925 1.62

12 54 5.35228 0.0318587 11.3

13 60 5.30849 0.000651074 1.63

14 63 5.26579 0.0305271 11

15 69 5.22338 0.000668487 1.64

16 72 5.18197 0.0293106 10.7

17 78 5.14082 0.000686194 1.64

18 81 5.10059 0.0281937 10.4

19 87 5.06058 0.000704225 1.65

20 90 5.02144 0.0271635 10.1

21 96 4.98249 0.000722609 1.66

22 99 4.94433 0.0262095 9.89

23 105 4.90635 0.000741376 1.67

24 108 4.86912 0.0253228 9.65

25 114 4.83204 0.000760554 1.68

26 117 4.79566 0.0244958 9.42

27 123 4.7594 0.000780174 1.69

28 126 4.72381 0.023722 9.2

29 132 4.68833 0.000800267 1.7

30 135 4.65347 0.022996 8.99

31 141 4.61871 0.000820866 1.7

32 144 4.58453 0.022313 8.79

33 150 4.55043 0.000842002 1.71

34 153 4.5169 0.0216689 8.6

35 159 4.48343 0.000863711 1.72

36 162 4.45049 0.0210601 8.42

37 168 4.4176 0.000886029 1.73

38 171 4.38522 0.0204834 8.24

39 177 4.35289 0.000908995 1.74

40 180 4.32103 0.019936 8.07

41 186 4.2892 0.000932649 1.75

42 189 4.25784 0.0194154 7.91

43 195 4.2265 0.000957033 1.76

44 198 4.19559 0.0189194 7.75

45 204 4.1647 0.000982194 1.77

46 207 4.13423 0.0184462 7.6

47 213 4.10377 0.00100818 1.78

48 216 4.07371 0.0179939 7.45

49 222 4.04364 0.00103505 1.79

50 225 4.01396 0.0175609 7.3

51 231 3.98427 0.00106284 1.8

52 234 3.95495 0.0171458 7.16

53 240 3.92561 0.00108886 1.8

54 243 3.89441 0.0181085 7.29

55 249 3.86321 0.00111764 1.82

Maximum number of function evaluations exceeded;（达到最大的函数值计算次数）

increase options.MaxFunEvals（建议增加最大的函数值计算次数）

x = -0.9634 0.9372（最后迭代点）

fval = 3.8632（最优点对应的函数值）

exitflag = 0

output = (函数基本信息)

iterations: 56 （迭代次数）

funcCount: 250（目标函数最大计算次数）

stepsize: 0.0011（步长）

firstorderopt: 1.8155

algorithm: 'medium-scale: Quasi-Newton line search'

message: [1x78 char]

从结果可见：在250次最大的目标函数计算次数内，算法没有到最优点[1,1]。将最大目标函数计算次数调高到2500次，则：

命令窗口输入：

OPTIONS=optimset('LargeScale','off','HessUpdate','steepdesc','gradobj','on','MaxFu nEvals',2500,'display','iter');

x=[-1.9,2];

[x,fval,exitflag,output]=fminunc(@BanaFunWithGrad,x,OPTIONS)

结果输出：

迭代次数函数计算次数函数值步长一阶导数最优性

Gradient's Iteration Func-count f(x) Step-size infinity-norm

0 1 267.62 1.23e+003

1 2 214.416 0.000813405 519

2 9 5.83639 0.0009849

3 13.4

3 15 5.78292 0.000567305 1.58

4 18 5.73127 0.0387979 12.9

5 24 5.68023 0.00058373

6 1.59

6 2

7 5.63081 0.0367599 12.5

7 33 5.5819 0.000600291 1.6

8 36 5.53444 0.0349482 12.1

9 42 5.48743 0.000617009 1.61

10 45 5.44173 0.0333245 11.7

11 51 5.39641 0.000633925 1.62

12 54 5.35228 0.0318587 11.3

13 60 5.30849 0.000651074 1.63

14 63 5.26579 0.0305271 11

15 69 5.22338 0.000668487 1.64

16 72 5.18197 0.0293106 10.7

17 78 5.14082 0.000686194 1.64

18 81 5.10059 0.0281937 10.4

19 87 5.06058 0.000704225 1.65

…………………………

400 1459 0.000541511 0.00111768 0.0162

401 1462 0.000538084 0.0141525 0.0574

Maximum number of iterations exceeded;

increase options.MaxIter.

x = 0.9770 0.9542

fval = 5.3808e-004

exitflag = 0

output =

iterations: 401

funcCount: 1462

stepsize: 0.0142

firstorderopt: 0.0574

algorithm: 'medium-scale: Quasi-Newton line search'

message: [1x67 char]

从以上两个算法的结果可以看出，最速下降法对bana函数不是十分有效。

当目标函数不可微或者导数求解复杂时，可以无需提供目标函数的导函数的解析形式，MATLAB可以使用差分的方法求导（下降方向）。

命令窗口输入对应的代码为：

OPTIONS=optimset('LargeScale','off','HessUpdate','steepdesc','MaxFunEvals',250);

x=[-1.9,2];

[x,fval,exitflag,output]=fminunc(@BanaFun,x,OPTIONS) 结果输出：

Maximum number of function evaluations exceeded; increase options.MaxFunEvals x = -1.2553 1.5640 fval = 5.1002 exitflag = 0 output =

iterations: 19 funcCount: 252 stepsize: 0.0282 firstorderopt: 10.4149

algorithm: 'medium-scale: Quasi-Newton line search' message: [1x78 char]

从计算结果可以明显看出，这对于最速下降发，有导数解析式会比没有导数解析式时，计算质量会有所提高。

四、 惩罚函数法

4.1 惩罚函数法的基本思路

惩罚函数法是应用广泛,非常有效的间接解法，又称为序列无约束极小化方法(SUMT 法)。该方法通过将原约束优化问题中的等式和不等式约束函数加权处理后与原目标函数结合,得到新的目标函数(惩罚函数)。原问题转化为新的无约束优化问题,求解该新的无约束优化问题,间接得到原约束优化问题的最优解。 程序步骤：

①选择适当的初始罚因子)0(M 、初始点)0(X 、收敛精度ε和罚因子系数c 。在本程序中分别取令迭代步数k=0。

②采用牛顿法求无约束问题),(m in )(k M X φ的极值点)()(*k M X 。

③检验迭代终止准则，若满足

ε≤--||)()(||)

1()

(*

k k M

X M

X 及 ε≤---|)]

([)]

([)]([|)1(*)1(*)(*k k k M X f M X f M X f

则停止迭代计算，输出最优点)()(**k M X X =；否则，转入步骤④。

④取)()1(k k cM M =+，)()(*)0(k M X X =，k=k+1，转入步骤②继续迭代。

4.2 算法流程图

4.3 用matlab编写源程序

Matlab程序源代码：

-----------主程序--------------------------------------- syms x1 x2 M; %M为罚因子。

m(1)=1; a(1)=20; b(1)=20; c=8; %c为递增系数。赋初值。

f=(x1-2)^2+(x2-1)^2+M*((x1^2-x2)^2+(x1+x2-2)^2);%外点罚函数f0(1)=500;

%求偏导、Hessian元素

最优化实验报告

最优化方法 课程设计报告班级：________________ 姓名： ______ 学号： __________ 成绩： 2017年 5月 21 日

目录 一、摘要 (1) 二、单纯形算法 (2) 1.1 单纯形算法的基本思路 (2) 1.2 算法流程图 (3) 1.3 用matlab编写源程序 (4) 二、黄金分割法 (7) 2.1 黄金分割法的基本思路 (7) 2.2 算法流程图 (8) 2.3 用matlab编写源程序 (9) 2.4 黄金分割法应用举例 (11) 三、最速下降法 (11) 3.1 最速下降法的基本思路 (11) 3.2 算法流程图 (13) 3.3 用matlab编写源程序 (13) 3.4 最速下降法应用举例 (13) 四、惩罚函数法 (17) 4.1 惩罚函数法的基本思路 (17) 4.2 算法流程图 (18) 4.3 用matlab编写源程序 (18) 4.4 惩罚函数法应用举例 (19) 五、自我总结 (20) 六、参考文献 (20)

一、摘要 运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。通过对数据的调查、收集和统计分析，以及具体模型的建立。收集和统计上述拟定之模型所需要的各种基础数据，并最终将数据整理形成分析和解决问题的具体模型。 最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB 这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。 关键词：优化、线性规划、黄金分割法、最速下降法、惩罚函数法

最优化方法实验报告(1)

最优化方法实验报告Numerical Linear Algebra And Its Applications 学生所在学院：理学院 学生所在班级：计算数学10-1 学生姓名：甘纯 指导教师：单锐 教务处 2013年5月

实验一 实验名称：熟悉matlab基本功能 实验时间: 2013年05月10日星期三实验成绩： 一、实验目的： 在本次实验中，通过亲临使用MATLAB，对该软件做一全面了解并掌握重点内容。 二、实验内容： 1. 全面了解MATLAB系统 2. 实验常用工具的具体操作和功能 实验二 实验名称：一维搜索方法的MATLAB实现 实验时间: 2013年05月10日星期三实验成绩： 一、实验目的： 通过上机利用Matlab数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。 二、实验背景： (一）0.618法（黄金分割法），它是一种基于区间收缩的极小点搜索

算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。 1、算法原理 黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。 2、算法步骤 用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点： 11110.382*()a b a λ=+- 11110.618*()a b a μ=+-。 （2）若k k b a ε-<，则停止计算。否则当()()k k f f λμ>时转步骤（3）。 当()()k k f f λμ≤转步骤（4）。 （3）置 11111110.382*()k k k k k k k k k k a b b a b a λλμμ+++++++=??=?? =??=+-?转步骤（5）

整数规划实验报告例文

整数规划实验报告例文 篇一：实验报告整数规划 一、实验名称：整数规划问题和动态规划问题 二、实验目的： 熟练使用Spreadsheet建立整数规划、动态规划模型，利用excel建立数学模型，掌握求解过程，并能对实验结果进行分析及评价 三、实验设备 计算机、Excel 四、实验内容 （一）整数规划 1、0-1整数规划 其中，D11=F2;D12=F3;D13=F4;D14=F5; B11=SUMPRODUCT($B$9:$E$9,B2:E2); B12=SUMPRODUCT($B$9:$E$9,B3:E3); B13=SUMPRODUCT($B$9:$E$9,B4:E4); B14=SUMPRODUCT($B$9:$E$9,B5:E5); H8==SUMPRODUCT($B$9:$E$9,B6:E6); 用规划求解工具求解：目标单元格为$H$8,求最大值，可变单元格为$B$9:$E$9，约束条件为 $B$11:$B$14<=$D$11:$D$14;$B$9:$E$9=二进制。在【选项】

果，实现最大利润为140. 2、整数规划 其中，D11=D2;D12=D3; B11=SUMPRODUCT($B$8:$C$8,B2:C2);B12=SUMPRODUCT($B$8:$ C$8,B3:C3); F7=SUMPRODUCT($B$8:$C$8,B4:C4); 用规划求解工具求解：设置目标单元格为F7,求最大值，可变单元格为$B$8:$C$8,约束条件为 $B$11:$B$12<=$D$11:$D$12;$B$8:$C$8=整数。在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果，实现最大利润为14. 3、指派问题 人数跟任务数相等： 其中， F11=SUM(B11:E11);F12=SUM(B12:E12);F13=SUM(B13:E13);F14=SU M(B14:E14); B15=SUM(B11:B14);C15=SUM(B11:B14);D15=SUM(B11:B14);E15=SU M(B11:B14); H11,H12,H13,H14,B17,C17,D17,E17单元格值均设为1. 用规划求解工具求解：设置目标单元格为$B$8,求最小值，可变单元格为$B$11:$E$14,约束条件为$B$11:$E$14=二进制； $B$15:$E$15=$B$17:$E$17;$F$11:$F$14=$H$11:$H$14. 在【选

最优化实验报告(单纯形法的matlab程序,lingo程序)

实验一：线性规划单纯形算法 一、实验目的 通过实验熟悉单纯形法的原理，掌握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

学生科学实验效果最优化的基石实验报告设计

学生科学实验效果最优化的基石实验报告设计 自然科学是以实验为基础的学科。实验是人们研究和认识自然的重要方法。因此，在自然科学的教学中，实验也是重要的教学方法之一。通过实验，不仅可以提供学生对科学现象的感性认识，更可以让学生获得初步的实验技能和观察分析问题的能力。 小学科学实验教学的设计是运用系统论的思想和方法，以学习理论、教学理论为基础，计划和安排实验教学的各个环节、要素，以实现教学效果最优化为目的的活动。通过多年来的实验教学实践与思考，我们可以让学生像科学家那样，亲历科学探究的过程，这有利于充分发挥学生的主体作用，让学生积极主动参与到观察、实验等学习活动中去，亲自感知实验所产生的各种现象和变化，提高自行获取知识的能力，而其中比较重要的一个环节就是学生实验报告的设计与记录。在学生实验的过程中，一份好的实验报告设计，就像是一盏明灯，能给学生指引实验的目标、方向，能提供给学生形成结论的分析数据，进而培养学生科学实验的基本素养，使学生的科学实验效果达到最优化。 一、观察实验报告的填写，有利于学生在实验中观察，进一步培养学生实验的责任心和有序观察能力。 教科版四下《油菜花开了》解剖花的实验中，我设计了如下实验报告，在教学中取得了很好的效果。 《解剖花》实验人

花的名称 实验方法：用镊子把花的各部分，从外向里一层层撕下，整齐排列并贴在相应的名称左边，数一数，填在相应的空格上。 个萼片 个花瓣 个雄蕊 个雌蕊 在班级（1）上课时我没有设计实验报告，就按照书本上的要求，先介绍解剖花的方法、花的结构，然后让学生按照书本要求独立解剖油菜花。在实验过程中，学生非常认真，且相当活跃，但检查结果时，学生雌雄蕊不分，萼片、花瓣不分，桌上、地上掉落的都是花瓣，实验效果之不佳显而易见。 后来，我根据班级（1）出现的情况，设计了如上实验报告，实验的效果就相当出色。在这个实验报告中，我并没有限制学生解剖何种花，但学生可以根据实验要求很清楚地完成解剖的任务。充分体现了以教师为主导、学生为主体的课堂教学思想；而且在实验的过程中，桌上有了这份实验报告，便时刻提醒着学生做实验究竟是何目的，做实验时必须仔细观察什么，做实验的观察步骤是什么。在解剖花的过程中，动作快的同学还可在老师的同意下，多取一两张实验报告单，多解剖几种花，因此既避免了学生在一旁闲着无所事事而打闹的局面，又进一步提高了这些学生的科学素质。至于个别有困难的学生，教师可在巡视的过程中

最优化方法课程实验报告

项目一 一维搜索算法（一） [实验目的] 编写加步探索法、对分法、Newton 法的程序。 [实验准备] 1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤； 3．掌握Newton 法的思想及迭代步骤。 [实验容及步骤] 编程解决以下问题： 1．用加步探索法确定一维最优化问题 1 2)(min 30 +-=≥t t t t ? 的搜索区间，要求选取2,1,000===αh t ． 加步探索法算法的计算步骤： (1)选取初始点 ]) 0[)(0[max 00t t t ，或，∈?∞+∈，计算 )(00t ??=．给出初始步长0 >h ， 加步系数1α>，令0=k 。 (2) 比较目标函数值．令k k k h t t +=+1，计算 )(11++=k k t ??，若k k ??<+1，转(3)，否则转(4)。 (3) 加大探索步长．令 k k h h α=+1，同时，令,k t t =,1+=k k t t 1k k =+，转(2)。 (4) 反向探索．若0=k ，转换探索方向，令,k k h h -=1+=k t t ，转（2）。否则，停止迭代，令 11min{}max{}k k a t t b t t ++==，，，。 加步探索法算法的计算框图

程序清单 加步探索法算法程序见附录1 实验结果 运行结果为： 2．用对分法求解 )2()(min +=t t t ?， 已知初始单谷区间]5,3[],[-=b a ，要求按精度3.0=ε，001.0=ε分别计算． 对分法迭代的计算步骤： (1)确定初始搜索区间],[b a ，要求'()0'()0a b ??<>，。 (2) 计算],[b a 的中点)(2 1 b a c +=． (3) 若0)(<'c ?，则c a = ，转(4)；若0)(='c ?，则c t =* ，转(5)；若0)(>'c ?，则c b = ，转(4)． (4) 若ε<-||b a ，则)(2 1* b a t +=，转(5)；否则转(2)． (5) 打印* t ，结束 对分法的计算框图

最优化方法(黄金分割与进退法)实验报告

一维搜索方法的MATLAB 实现 姓名： 班级：信息与计算科学 学号： 实验时间: 2014/6/21 一、实验目的： 通过上机利用Matlab 数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab 软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。 二、实验背景： 黄金分割法 它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。 1、算法原理 黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断 的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。 2、算法步骤 用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点： 11110.382*()a b a λ=+- 11110.618*()a b a μ=+-。 （2）若k k b a ε-<，则停止计算。否则当()()k k f f λμ>时转步骤（3）。 当 ()()k k f f λμ≤转步骤（4）。 （3） 11111110.382*()k k k k k k k k k k a b b a b a λλμμ+++++++=??=?? =??=+-?转步骤（5）

（4） 转步骤（5） （5）令1k k =+，转步骤（2）。 算法的MATLAB 实现 function xmin=golden(f,a,b,e) k=0; x1=a+0.382*(b-a); x2=a+0.618*(b-a); while b-a>e f1=subs(f,x1); f2=subs(f,x2); if f1>f2 a=x1; x1=x2; f1=f2; x2=a+0.618*(b-a); else b=x2; x2=x1; f2=f1; x1=a+0.382*(b-a); end k=k+1; end xmin=(a+b)/2; fmin=subs(f,xmin)

最优化计算方法课后习题答案----高等教育出版社。施光燕

习题二包括题目：P36页5（1）（4） 5（4）

习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下

5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+-

最优化方法课程实验报告

. . 项目一 一维搜索算法（一） [实验目的] 编写加步探索法、对分法、Newton 法的程序。 [实验准备] 1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤； 3．掌握Newton 法的思想及迭代步骤。 [实验容及步骤] 编程解决以下问题： 1．用加步探索法确定一维最优化问题 1 2)(min 30 +-=≥t t t t ? 的搜索区间，要求选取2,1,000===αh t ． 加步探索法算法的计算步骤： (1)选取初始点])0[)(0[max 00t t t ，或，∈?∞+∈，计算)(00 t ??=．给出初始步长0 >h ， 加步系数1α>，令0=k 。 (2) 比较目标函数值．令k k k h t t +=+1，计算 )(11++=k k t ??，若k k ??<+1，转(3)，否则转(4)。 (3) 加大探索步长．令k k h h α=+1，同时，令,k t t =,1+=k k t t 1k k =+，转(2)。 (4) 反向探索．若0=k ，转换探索方向，令,k k h h -=1+=k t t ，转（2）。否则，停止迭代， 令 11min{}max{}k k a t t b t t ++==，，，。 加步探索法算法的计算框图

. . 程序清单 加步探索法算法程序见附录1 实验结果 运行结果为： 2．用对分法求解 )2()(min +=t t t ?， 已知初始单谷区间]5,3[],[-=b a ，要求按精度3.0=ε，001.0=ε分别计算． 对分法迭代的计算步骤： (1)确定初始搜索区间],[b a ，要求'()0'()0a b ??<>，。 (2) 计算],[b a 的中点)(2 1 b a c += ． (3) 若0)(<'c ?，则c a = ，转(4)；若0)(='c ?，则c t =* ，转(5)；若0)(>'c ?，则c b = ，转(4)． (4) 若ε<-||b a ，则)(2 1* b a t +=，转(5)；否则转(2)．

《最优化方法》复习题(含答案)

x zD 天津大学《最优化方法》复习题(含答案) 第一章 概述(包括凸规划) 判断与填空题 arg max f(x)二 arg min 以儿 “ max(x): x D 二 R n 』=-min(x): x D 二 R n ； 设f : D 5 R n > R.若x ： R n ，对于一切R n 恒有f(x”)^f(x)，则称x”为 设f : D 5 R n >R.若x ” ? D ,存在x ”的某邻域N ；(x”)，使得对一切 x ?N .(x)恒有f(x”)：：： f (x)，则称x”为最优化问题 min f (x)的严格局部最 优解? 给定一个最优化问题，那么它的最优值是一个定值 ? V 非空集合D R n 为凸集当且仅当 D 中任意两点连线段上任一点属于 D . V 非空集合D R n 为凸集当且仅当D 中任意有限个点的凸组合仍属于 D . V 任意两个凸集的并集为凸集? 函数f:D R n >R 为凸集D 上的凸函数当且仅当 -f 为D 上的凹函数? V 设f : D R n >R 为凸集D 上的可微凸函数，X ：D ?则对-D ,有 f (x) - f(x )乞 f (x )T (X —X )? 若c(x)是凹函数，则 D={x^R n C(x)启0}是凸集。 V f(x)的算法A 产生的迭代序列，假设算法 A 为下降算法, 则对-k ? 5,1, 2,…匚恒有 ________________ f(x k1)乞 f(x k ) ______________ ? 算法迭代时的终止准则(写出三种) ： ___________________________________________________ 凸规划的全体极小点组成的集合是凸集。 V 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

最优化方法(试题+答案)

一、 填空题 1 ． 若 ()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ，则 =?)(x f ，=?)(2x f . ２．设f 连续可微且0)(≠?x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向。 3.向量T ) 3,2,1(关于3阶单位方阵的所有线性无关的共轭向量 有 ． 4. 设R R f n →:二次可微，则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算 法: . 6.以下约束优化问题： )(01)(..)(min 212121 ≥-==+-==x x x g x x x h t s x x f 的K-K-T 条件为： . 7．以下约束优化问题： 1 ..)(min 212 2 21=++=x x t s x x x f 的外点罚函数为(取罚参数为μ) . 二、证明题（７分+8分) 1.设1,2,1,:m i R R g n i =→和m m i R R h n i ,1,:1+=→都是线性函数,证明下 面的约束问题: } ,,1{, 0)(},1{, 0)(..)(min 1112 m m E j x h m I i x g t s x x f j i n k k +=∈==∈≥=∑= 是凸规划问题。

2.设R R f →2 :连续可微，n i R a ∈,R h i ∈,m i ,2,1=,考察如下的约束条件问题: } ,1{,0} 2,1{,0..) (min 11m m E i b x a m I i b x a t s x f i T i i T i +=∈=-=∈≥- 设d 是问题 1 ||||,0,0..)(min ≤∈=∈≥?d E i d a I i d a t s d x f T i T i T 的解，求证：d 是f 在x 处的一个可行方向。 三、计算题（每小题１2分) １.取初始点T x )1,1() 0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题 (迭代２步）: 2 2212)(m in x x x f += 2.采用精确搜索的BFGS 算法求解下面的无约束问题： 212 2212 1)(min x x x x x f -+= 3.用有效集法求解下面的二次规划问题: . 0,001..42)(min 21212 12 221≥≥≥+----+=x x x x t s x x x x x f 4．用可行方向算法(Zoutend ｉj ｋ算法或Ｆrank Wol ｆｅ算法）求解下面的问题（初值设为)0,0() 0(=x ,计算到)2(x 即可）： . 0,033..22 1)(min 212112 22121≥≥≤+-+-= x x x x t s x x x x x x f

最优化实验报告

最优化方法 课程设计报告 班级：________________ 姓名： ______ 学号： __________ 成绩： 2017年 5月 21 日 目录 一、摘要 (1)

二、单纯形算法 (2) 1.1 单纯形算法的基本思路 (2) 1.2 算法流程图 (3) 1.3 用matlab编写源程序 (3) 二、黄金分割法 (7) 2.1 黄金分割法的基本思路 (7) 2.2 算法流程图 (8) 2.3 用matlab编写源程序 (9) 2.4 黄金分割法应用举例 (10) 三、最速下降法 (10) 3.1 最速下降法的基本思路 (10) 3.2 算法流程图 (12) 3.3 用matlab编写源程序 (12) 3.4 最速下降法应用举例 (13) 四、惩罚函数法 (16) 4.1 惩罚函数法的基本思路 (16) 4.2 算法流程图 (17) 4.3 用matlab编写源程序 (17) 4.4 惩罚函数法应用举例 (19) 五、自我总结 (19) 六、参考文献 (19)

一、摘要 运筹学是一门以人机系统的组织、管理为对象，应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。通过对数据的调查、收集和统计分析，以及具体模型的建立。收集和统计上述拟定之模型所需要的各种基础数据，并最终将数据整理形成分析和解决问题的具体模型。 最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。 关键词：优化、线性规划、黄金分割法、最速下降法、惩罚函数 法

遗传算法实验报告

遗传算法实验报告 专业：自动化姓名：张俊峰学号：13351067 摘要：遗传算法，是基于达尔文进化理论发展起来的一种应用广泛、高效的随机搜索与优化方法。本实验利用遗传算法来实现求函数最大值的优化问题，其中的步骤包括初始化群体、个体评价、选择运算、交叉运算、变异运算、终止条件判断。该算法具有覆盖面大、减少进入局部最优解的风险、自主性等特点。此外，遗传算法不是采用确定性原则而是采用概率的变迁规则来指导搜索方向，具有动态自适应的优点。 关键词：串集最优化评估迭代变异 一：实验目的 熟悉和掌握遗传算法的运行机制和求解的基本方法。 遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下： （1）随机产生一个确定长度的特征字符串组成的初始种群。。 （2）对该字符春种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止： a计算种群中每个个体字符串的适应值； b应用复制、交叉和变异等遗传算子产生下一代种群。 （3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一 个解。 二：实验要求 已知函数y=f（x 1,x 2 ,x 3 ,x 4 ）=1/(x 1 2+x 2 2+x 3 2+x 4 2+1),其中-5≤x 1 ,x 2 ,x 3 ,x 4 ≤5, 用遗传算法求y的最大值。三：实验环境

操作系统：Microsoft Windows 7 软件：Microsoft Visual studio 2010 四：实验原理与步骤 1、遗传算法的思想 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。 2、算法实现步骤 ①、产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合； ②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值f，i=1,2,…,n,f越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度f为群体进化提供了依据； ③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中。此处选用轮盘算法，也就是比例选择算法，个体被选择的概率与其适应度成正比。 ④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；此处采取生成随机数决定交叉的个体与交叉的位置。 ⑤变异：以一定的概率Pm从群体P（t+1）中随机选择若干个个体，对于选中的个体随机选择某个位置，进行变异； ⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。 五：实验结果 实验结果的显示取决于判断算法终止的条件，这里可以有两种选择：1、在程序中设定迭代的次数；2在程序中设定适应值。本实验是在程序中实验者输入需要迭代的次数来判断程序终结的。

最优化算法实验报告(附Matlab程序)

最优化方法(Matlab)实验报告 ——Fibonacci 法 一、实验目的： 用MATLAB 程序实现一维搜索中用Fibonacc 法求解一元单峰函数的极小值问题。二、实验原理： （一）、构造Fibonacci 数列：设数列{}k F ，满足条件： 1、011F F == 2、11 k k k F F F +-=+则称数列{}k F 为Fibonacci 数列。（二）、迭代过程： 首先由下面的迭代公式确定出迭代点： 1 1 1 (),1,...,1(),1,...,1n k k k k k n k n k k k k k n k F a b a k n F F u a b a k n F λ---+--+=+ -=-=+ -=-易验证，用上述迭代公式进行迭代时，第k 次迭代的区间长度缩短比率恰好为 1 n k n k F F --+。故可设迭代次数为n ，因此有11121211221111223231 ()()......()()n n n n n n n n n F F F F F F b a b a b a b a b a F F F F F F F ------= -=?-==?-=-若设精度为L ，则有第n 次迭代得区间长度111 ()n n n b a L b a L F -≤-≤，即 就是 111 ()n b a L F -≤，由此便可确定出迭代次数n 。

假设第k 次迭代时已确定出区间[,]k k a b 以及试探点,[,]k k k k u a b λ∈并且k k u λ<。计算试探点处的函数值，有以下两种可能：（1）若()()k k f f u λ>，则令 111111111,,()() () k k k k k k k k n k k k k k n k a b b f f F a b a F λλμλμμ++++--++++-=====+-计算1()k f μ+的值。（2）()()k k f f u λ≤，则令 111121111,,()() () k k k k k k k k n k k k k k n k a a b f f F a b a F μμλμλλ++++--++++-=====+-计算1()k f λ+的值。 又因为第一次迭代确定出了两个迭代点，以后每迭代一次，新增加一个迭代点，这样在迭代n-1后便计算完了n 个迭代点。因此第n 次迭代中，选用第n-1次的迭代点以及辨别常数δ构造n λ和n μ： 1 1n n n n λλμλδ --==+再用同样的方法进行判断：（1）、若()n f λ>()n f μ则令 1 n n n n a b b λ-==（2）、若()n f λ<=()n f μ则令 1n n n n a a b μ-==这样便可确定出最优解的存在区间[,]n n a b 。

最优化方法(试题+答案)

一、 填空题 1.若()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ， 则=?)(x f ，=?)(2x f . 2.设f 连续可微且0)(≠?x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向。 3.向量T )3,2,1(关于3阶单位方阵的所有线性无关的共轭向量有 . 4. 设R R f n →:二次可微，则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算法： . 6.以下约束优化问题： )(01)(..)(min 212121 ≥-==+-==x x x g x x x h t s x x f 的K-K-T 条件为： . 7.以下约束优化问题： 1 ..)(min 212 2 21=++=x x t s x x x f 的外点罚函数为（取罚参数为μ） . 二、证明题（7分+8分） 1.设1,2,1,:m i R R g n i =→和m m i R R h n i ,1,:1+=→都是线性函数，证明下 面的约束问题： } ,,1{, 0)(},1{, 0)(..)(min 1112 m m E j x h m I i x g t s x x f j i n k k +=∈==∈≥=∑= 是凸规划问题。

2.设R R f →2 :连续可微，n i R a ∈，R h i ∈，m i ,2,1=，考察如下的约束条件问题： } ,1{,0} 2,1{,0..) (min 11m m E i b x a m I i b x a t s x f i T i i T i +=∈=-=∈≥- 设d 是问题 1 ||||,0,0..)(min ≤∈=∈≥?d E i d a I i d a t s d x f T i T i T 的解，求证：d 是f 在x 处的一个可行方向。 三、计算题（每小题12分） 1.取初始点T x )1,1() 0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题 （迭代2步）： 2 2212)(m in x x x f += 2.采用精确搜索的BFGS 算法求解下面的无约束问题： 212 2212 1)(min x x x x x f -+= 3.用有效集法求解下面的二次规划问题： . 0,001..42)(min 21212 12 221≥≥≥+----+=x x x x t s x x x x x f 4.用可行方向算法（Zoutendijk 算法或Frank Wolfe 算法）求解下面的问题（初值设为)0,0() 0(=x ,计算到)2(x 即可)： . 0,033..22 1)(min 21211222121≥≥≤+-+-= x x x x t s x x x x x x f

学生科学实验效果最优化的基石实验报告设计

( 实验报告) 姓名：____________________ 单位：____________________ 日期：____________________ 编号：YB-BH-054067 学生科学实验效果最优化的基The design of cornerstone experiment report for optimizing the

学生科学实验效果最优化的基石实 验报告设计 自然科学是以实验为基础的学科。实验是人们研究和认识自然的重要方法。因此，在自然科学的教学中，实验也是重要的教学方法之一。通过实验，不仅可以提供学生对科学现象的感性认识，更可以让学生获得初步的实验技能和观察分析问题的能力。 小学科学实验教学的设计是运用系统论的思想和方法，以学习理论、教学理论为基础，计划和安排实验教学的各个环节、要素，以实现教学效果最优化为目的的活动。通过多年来的实验教学实践与思考，我们可以让学生像科学家那样，亲历科学探究的过程，这有利于充分发挥学生的主体作用，让学生积极主动参与到观察、实验等学习活动中去，亲自感知实验所产生的各种现象和变化，提高自行获取知识的能力，而其中比较重要的一个环节就是学生实验报告的设计与记录。在学生实验的过程中，一份好的实验报告设计，就像是一盏明灯，能给学生指引实验的目标、方向，能提供给学生形成结论的分析数据，进而培养学生科学实验的基本素养，使学生的科学实验效果达到最优化。 一、观察实验报告的填写，有利于学生在实验中观察，进一步培养学生实验的责任心和有序观察能力。

教科版四下《油菜花开了》解剖花的实验中，我设计了如下实验报告，在教学中取得了很好的效果。 《解剖花》实验人 花的名称 实验方法：用镊子把花的各部分，从外向里一层层撕下，整齐排列并贴在相应的名称左边，数一数，填在相应的空格上。 个萼片 个花瓣 个雄蕊 个雌蕊 在班级（1）上课时我没有设计实验报告，就按照书本上的要求，先介绍解剖花的方法、花的结构，然后让学生按照书本要求独立解剖油菜花。在实验过程中，学生非常认真，且相当活跃，但检查结果时，学生雌雄蕊不分，萼片、花瓣不分，桌上、地上掉落的都是花瓣，实验效果之不佳显而易见。 后来，我根据班级（1）出现的情况，设计了如上实验报告，实验的效果就相当出色。在这个实验报告中，我并没有限制学生解剖何种花，但学生可以根据实验要求很清楚地完成解剖的任务。充分体现了以教师为主导、学生为主体的课堂教学思想；而且在实验的过程中，桌上有了这份实验报告，便时刻提醒着学生做实验究竟是何目的，做实验时必须仔细观察什么，做实验的观察步骤是什么。在解剖花的过程中，动作快的同学还可在老师的同意下，多取一两张实验报告单，多解剖几种花，因此既避免了学生在一旁闲着无所事事而打闹的局面，又进一步提高了这些学生的科学素质。至于个别有困难的学生，教师可在巡视的过程中随

《最优化方法》复习题(含答案)

附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵． 解 2(),()f x Ax b f x A ?=+?=． 2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''． 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+． 3、设方向n d R ∈是函数()f x 在点x 处的下降方向，令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???， 其中I 为单位矩阵，证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向． 证明 由于方向d 是函数()f x 在点x 处的下降方向，因此()0T f x d ?<，从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<， 所以，方向p 是函数()f x 在点x 处的下降方向． 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S ． 证明 充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令1 1k i i i x x λ+==∑， 其中,0,1,2,,1i i x S i k λ∈≥=+L ，且1 1 1k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈， 结论成立），记11 1k i i i k y x λλ=+=-∑ ，有111(1)k k k x y x λλ+++=-+，

计算方法实验报告习题1

计算方法实验报告 实验名称： 实验1 从函数表出发进行插值 1 引言 某个实际问题中，函数f (x)在区间[a,b]上存在且连续，但难以找到其表达式，只能通过实验和观测得到有限点上的函数表。有些情况虽然可以写出表达式，但结构复杂，使用不方便。所以希望构造简单函数P (x)作为f (x)的近似值。插值法是解决此类问题的一种方法。 设函数y=在插值区间[a,b]上连续，且在n+1个不同的插值节点a≤x 0,x 1,…,x n ≤b 上分别取值y 0,y 1,…,y n 。目的是要在一个性质优良、便于计算的插值函数类Φ中，求一简单函数P (x)，满足插值条件P (x i )=y i (i=0,1,…,n)，而在其他点x≠x i 上，作为f (x)近似值。求插值函数P (x)的方法称为插值法[1]。 2 实验目的和要求 运用Matlab 编写m 文件，定义三种插值函数，要求一次性输入整张函数表，并利用计算机选择在插值计算中所需的节点。分别通过分段线性插值、分段二次插值和全区间上拉格朗日插值计算f ，f ，f 的近似值。 3 算法原理与流程图 （1）原理 1.线性插值 当给定了n+1个点x 0