北航最优化方法大作业Word格式.docx

1、算例1中，由b1可知，节点2为需求节点，节点1为供给节点，由节点1将信息传输至节点2的最短路径为弧1。图 2 算例1最优传输示意图求得的最优解为x1*=4 0 0 0 0 0 0 0 0 0 0 0 0T，即只经过弧1运输4个单位流量，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为20。经分析，计算结果合理可信。1.3.2 算例2（b2=4;算例2中，由b2可知，节点3为需求节点，节点1为供给节点，由节点1将信息传输至节点2的最短路径为弧2。图 3 算例2最优传输示意图求得的最优解为x2*=0 4 0 0 0 0 0 0 0 0 0 0 0T，即只经过弧2运输4个单位流量，其余弧无流

2、量。1.3.3 算例3（b3=0;算例3中，由b3可知，节点2为需求节点，节点3为供给节点，由节点3将信息传输至节点2的最短路径为弧5-弧1。图 4 算例3最优传输示意图求得的最优解为x3*=4 0 0 0 4 0 0 0 0 0 0 0 0T，即经过弧5运输4个单位流量至节点1，再经弧1运输4个单位流量至节点2，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为40。1.3.4 算例4（b4=4;算例4中，由b4可知，节点7为需求节点，节点1为供给节点，由节点1将信息传输至节点7的最短路径为弧1-弧4-弧10。图 5 算例3最优传输示意图求得的最优解为x4*=4 0 0 4 0 0 0

3、 0 0 4 0 0 0T，即经过弧1运输4个单位流量至节点2，再经弧4运输4个单位流量至节点5，最后经弧5运输4个单位流量至节点7，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为60。2 重要算法编写与观察2.1 习题5.6（a） 初值为（0,0）时本算法令g的2范数在10-4时，停止迭代，经过86次迭代收敛。收敛因子（f（k+1）-f*）/（f（k）-f*）=0.7623图 6 收敛因子截图（b） 初值为（-0.4,0）时10-4时，停止迭代，经过112次迭代收敛。收敛因子（f（k+1）-f*）/（f（k）-f*）=0.81图 7 收敛因子截图（c） 初值为（10,0）时10-4

4、时，停止迭代，经过5次迭代收敛。收敛因子（f（k+1）-f*）/（f（k）-f*）=3.9022e-4图 8 收敛因子截图（d） 初值为（11,0）时10-4时，停止迭代，经过2次迭代收敛。收敛因子（f（k+1）-f*）/（f（k）-f*）= 0图 9 收敛因子截图图 10 自变量（x1,x2）截图总结：最速降线法的收敛因子随着初值的不同而变化，对于个别初值（如本习题初值取（11,0）时），算法可迅速收敛。因此，初值的选取对于最速降线法的收敛速度有较大影响。2.2 习题5.7（a） 由可得：故，牛顿迭代法的确切公式为：（b）从以下五个初值开始迭代（1）x（0）=7.40表 1 初值1牛顿法迭代

5、结果表迭代次数x值梯度值17.4-127.44-0.0909090937.4444-0.0009000947.4444444-9.00E-085（2）x（0）=7.20表 2 初值2牛顿法迭代结果表7.2-117.31-3.9032258067.403775-0.9065073377.440723-7.60E-027.444413-0.000631068（3）x（0）=7.01表 3 初值3牛顿法迭代结果表7.01-3917.019775-193.27560057.03867-94.438994647.073976-4.51E+017.135638-20.49016561（4）x（0）=7.8

6、0表 4 初值4牛顿法迭代结果表7.87.16-167.2624-6.2439024397.369879-1.81E+007.431934-0.260664533（5）x（0）=7.88表 5 初值5牛顿法迭代结果表7.884.4545454557.0176-218.27272737.034503-106.93181357.066328-5.13E+017.122757-23.58481436（c）本问题的最优值为7.4444444。由上述五个初值点的前五步迭代可以看出：当初值点在区间（7.4444444，7.8888）内时，第二次迭代点将落在（7，7.4444444）之间，随后逐渐增加，直至

7、逼近最优值。当初值点在区间（7，7.4444444）内时，则迭代点逐渐增加，逼近最优值。当取初值不在（7,7.8888）内时，牛顿法不收敛。2.3 习题5.8（a） 没有线搜索的牛顿法=0.1时，=1时，（b） 具有线搜索的牛顿法（未完成）2.4 习题5.9 （a）初值选（1.2,1.2）时， 最速降线法：10-2时，停止迭代，经过3262次迭代得到以下结果。图 11 最速降线法初值为（1.2,1.2）的等值线图及迭代轨迹 牛顿法：本算法令s的4范数在10-6时，停止迭代，经过4次迭代得到以下结果。图 12 牛顿法初值为（1.2,1.2）的等值线图及迭代轨迹（b）初值选（-1.2,1）时，本算

8、法令g的4范数在=0 flag=0; sol=zeros（1,nA）; for i=1:mA-1 sol（N（i）=A（i,nA）; end val=sol*（B（mA,:）; else if A（i,nA） disp（have infinite solution!）; break; if flag temp=0;temp temp=A（i,nA）; outb=i; sita=zeros（1,nA-1）;nA-1 if A（outb,i） sita（i）=A（mA,i）/A（outb,i）; temp=-inf; if sita（i） temp=sita（i）; inb=i; if i=out

9、b N（i）=inb; A（outb,:）=A（outb,:）/A（outb,inb）;mA if i=outb A（i,:）=A（i,:）-A（outb,:）*A（i,inb）; A（mA,nA）=0;end3.2 最速降线法求Rosenbrock函数最小值matlab程序如下：function rb = rbfun（x,y）rb=100*（y-x2）2+（1-x）2clearclcsyms x y g Gg=gradient（rb（x,y）,x y） %定义梯度向量G=hessian（rb（x,y）,x y） %定义海森阵X（1,:）=-1.4 1; %定义初始点x=X（1,1）;y=X（

10、1,4）;A（1,:）=subs（g） %给梯度赋初值i=1while（norm（A（i,:）,4）10（-4） %收敛条件f（i）=rb（x,y） %记录函数值P（i,:）=-A（i,:） %得到迭代方向fz（i）=-A（i,:）*P（i,:） %-gT*p %精确搜索法步长的分子fm（i）=P（i,:）*subs（G）*P（i,: %精确搜索法步长的分母a（i）=fz（i）/fm（i） %精确搜索法步长X（i+1,:） = X（i,:）+a（i）*P（i,:） %产生新的点x=X（i+1,1）;y=X（i+1,4）A（i+1,:）=subs（g） %产生新的梯度i=i+13.3 牛顿法求R

11、osenbrock函数最小值matlab程序如下： %定义初值H=subs（inv（G） %得到海森阵初值S（1,:）=-A（1,:）*H %得到s初值while （norm（S（i,:10（-6） %收敛条件f（i）=rb（x,y） %定义函数值）+S（i,:） %得到下一迭代点y=X（i+1,4） %给x,y分别赋值）=subs（g） %得到新的梯度值H=subs（inv（G） %得到新的海森阵S（i+1,:）=-A（i+1,:）*H %得到新的增量s3.4 共轭梯度法求解习题5.19程序如下：K=40G=zeros（K,K）for m = 1: Kfor n = 1:G（m,n）=1/（m+n-1）end ）=zeros（1,K）b=ones（1,K）=X（1,:）*G-bP（1,:） while （norm（A（i,:10（-6） %收敛条件d=P（i,:）*Gfz（i）=A（i,:）*A（i,: %精确搜索法步长的分子）*d）+a（i）*dbeta（i+1）=（A（i+1,:）*A（i+1,:）/（A（i,:）P（i+1,:）+beta（i+1）*P（i,: