您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 信息化管理 > 北航最优化方法大作业参考
-1-1流量工程问题1.1问题重述定义一个有向网络G=(N,E),其中N是节点集,E是弧集。令A是网络G的点弧关联矩阵,即N×E阶矩阵,且第l列与弧里(I,j)对应,仅第i行元素为1,第j行元素为-1,其余元素为0。再令bm=(bm1,…,bmN)T,fm=(fm1,…,fmE)T,则可将等式约束表示成:Afm=bm本算例为一经典TE算例。算例网络有7个节点和13条弧,每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对,具体的源节点、目的节点信息如图所示。这里为了简单,省区了未用到的弧。此外,弧上的数字表示弧的编号。此时,c=((5,5…,5)1×13)T,根据上述四个约束条件,分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1×13)。图1网络拓扑和流量需求-2-1.27节点算例求解1.2.1算例1(b1=[4;-4;0;0;0;0;0]T)转化为线性规划问题:MinimizecTx1SubjecttoAx1=b1x1=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x1*=[4000000000000]T对应的最优值cTx1=201.2.2算例2(b2=[4;0;-4;0;0;0;0]T)MinimizecTx2SubjecttoAx2=b2X2=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x2*=[0400000000000]T对应的最优值cTx2=201.2.3算例3(b3=[0;-4;4;0;0;0;0]T)MinimizecTx3SubjecttoAx3=b3X3=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x3*=[4000400000000]T对应的最优值cTx3=40-3-1.2.4算例4(b4=[4;0;0;0;0;0;-4]T)MinimizecTx4SubjecttoAx4=b4X4=0利用Matlab编写对偶单纯形法程序,可求得:最优解为x4*=[4004000004000]T对应的最优值cTx4=601.3计算结果及结果说明1.3.1算例1(b1=[4;-4;0;0;0;0;0]T)算例1中,由b1可知,节点2为需求节点,节点1为供给节点,由节点1将信息传输至节点2的最短路径为弧1。图2算例1最优传输示意图求得的最优解为x1*=[4000000000000]T,即只经过弧1运输4个单位流量,其余弧无流量。又因为,每条弧的费用均为5,所以最小费用为20。经分析,计算结果合理可信。1.3.2算例2(b2=[4;0;-4;0;0;0;0]T)算例2中,由b2可知,节点3为需求节点,节点1为供给节点,由节点1将信息传输至节点2的最短路径为弧2。-4-图3算例2最优传输示意图求得的最优解为x2*=[0400000000000]T,即只经过弧2运输4个单位流量,其余弧无流量。又因为,每条弧的费用均为5,所以最小费用为20。经分析,计算结果合理可信。1.3.3算例3(b3=[0;-4;4;0;0;0;0]T)算例3中,由b3可知,节点2为需求节点,节点3为供给节点,由节点3将信息传输至节点2的最短路径为弧5-弧1。图4算例3最优传输示意图求得的最优解为x3*=[4000400000000]T,即经过弧5运输4个单位流量至节点1,再经弧1运输4个单位流量至节点2,其余弧无流量。又因为,每条弧的费用均为5,所以最小费用为40。经分析,计算结果合理可信。1.3.4算例4(b4=[4;0;0;0;0;0;-4]T)算例4中,由b4可知,节点7为需求节点,节点1为供给节点,由节点1将信息传输至节点7的最短路径为弧1-弧4-弧10。-5-图5算例3最优传输示意图求得的最优解为x4*=[4004000004000]T,即经过弧1运输4个单位流量至节点2,再经弧4运输4个单位流量至节点5,最后经弧5运输4个单位流量至节点7,其余弧无流量。又因为,每条弧的费用均为5,所以最小费用为60。经分析,计算结果合理可信。-6-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)时本算法令g的2范数在10-4时,停止迭代,经过112次迭代收敛。收敛因子(f(k+1)-f*)/(f(k)-f*)=0.81-7-图7收敛因子截图(c)初值为(10,0)时本算法令g的2范数在10-4时,停止迭代,经过5次迭代收敛。收敛因子(f(k+1)-f*)/(f(k)-f*)=3.9022e-4图8收敛因子截图-8-(d)初值为(11,0)时本算法令g的2范数在10-4时,停止迭代,经过2次迭代收敛。收敛因子(f(k+1)-f*)/(f(k)-f*)=0图9收敛因子截图图10自变量(x1,x2)截图-9-总结:最速降线法的收敛因子随着初值的不同而变化,对于个别初值(如本习题初值取(11,0)时),算法可迅速收敛。因此,初值的选取对于最速降线法的收敛速度有较大影响。2.2习题5.7(a)由()94ln(7)fxxx可得:4'()97fxx24()(7)fxx故,牛顿迭代法的确切公式为:24974(7)xsx(b)从以下五个初值开始迭代(1)x(0)=7.40表1初值1牛顿法迭代结果表迭代次数x值梯度值17.4-127.44-0.0909090937.4444-0.0009000947.4444444-9.00E-0857.4444444-9.00E-08(2)x(0)=7.20表2初值2牛顿法迭代结果表迭代次数x值梯度值17.2-1127.31-3.90322580637.403775-0.90650733747.440723-7.60E-0257.444413-0.000631068(3)x(0)=7.01表3初值3牛顿法迭代结果表迭代次数x值梯度值17.01-391-10-27.019775-193.275600537.03867-94.4389946447.073976-4.51E+0157.135638-20.49016561(4)x(0)=7.80表4初值4牛顿法迭代结果表迭代次数x值梯度值17.8427.16-1637.2624-6.24390243947.369879-1.81E+0057.431934-0.260664533(5)x(0)=7.88表5初值5牛顿法迭代结果表迭代次数x值梯度值17.884.45454545527.0176-218.272727337.034503-106.931813547.066328-5.13E+0157.122757-23.58481436(c)本问题的最优值为7.4444444。由上述五个初值点的前五步迭代可以看出:当初值点在区间(7.4444444,7.8888)内时,第二次迭代点将落在(7,7.4444444)之间,随后逐渐增加,直至逼近最优值。当初值点在区间(7,7.4444444)内时,则迭代点逐渐增加,逼近最优值。当取初值不在(7,7.8888)内时,牛顿法不收敛。2.3习题5.8(a)没有线搜索的牛顿法μ=0.1时,μ=1时,(b)具有线搜索的牛顿法μ=0.1时,-11-μ=1时,(未完成)2.4习题5.9(a)初值选(1.2,1.2)时,最速降线法:本算法令g的2范数在10-2时,停止迭代,经过3262次迭代得到以下结果。图11最速降线法初值为(1.2,1.2)的等值线图及迭代轨迹牛顿法:本算法令s的4范数在10-6时,停止迭代,经过4次迭代得到以下结果。-12-图12牛顿法初值为(1.2,1.2)的等值线图及迭代轨迹(b)初值选(-1.2,1)时,最速降线法:本算法令g的4范数在10-2时,停止迭代,经过6835次迭代得到以下结果。图13最速降线法初值为(-1.2,1)的等值线图及迭代轨迹-13-牛顿法:本算法令s的4范数在10-6时,停止迭代,经过6次迭代得到以下结果。图14牛顿法初值为(-1.2,1)的等值线图及迭代轨迹2.5习题5.19N=5迭代6次后,满足收敛条件。表6N=5时,各迭代点x值迭代次数/分量1444510000040.7744410.7744410.7744410.7744410.7744414-1.744581.0449944.4054814.8945444.45495444.740748-14.4459-4.780467.94544517.419445-4.8061445.656-86.4661-46.19499.441765.000468-140640.0001-1140640.000175-140640-1140640N=8迭代19次后,满足收敛条件。表7N=8时,各迭代点x值迭代次数/分量1444567810000000040.7544940.7544940.7544940.7544940.7544940.7544940.7544940.7544944-1.714480.4868491.186971.7445094.1075684.4845444.5988544.77040844.619757-7.74774-5.18495-1.1844.6614656.0744949.04446111.64715-14-5-4.5694948.44644-40.4749-44.1741-44.1857-1.644645.1444954.749864.577401-74.4411199.8408-9.99548-174.858-171.851-10.8654469.47447-4.15904104.8461-645.041081.886446.6416-1014.4-914.4591401.4468-5.65084154.4884-874.6011478.11445.7144-1444.46-1156.481454.9449-5.64898154.4878-874.6011478.108445.7146-1444.47-1156.481454.944106.688844-489.1174810.06-9974.6514761.111879.748-15549.98487.119116.744416-489.4544810.494-9974.1114764.741880.191-15541.78488.07146.789876-489.4814811.108-9976.4614765.091880.84-15544.48489.454147.645489-445.6814087.908-6008.644107.69416980.64-46494.611414.66147.405147-181.141454.897-1497.76-10051.444195.97-48554.514876.44155.044404-90.441479.065814858.444-47184.458454.08-55845.619754.9716-7.98171504.7645-7559.4146199.76-148600416414.8-16816751480.4617-7.99416504.8604-7559.6446199.85-148600416415.4-16816851480.1618-7.99414504.8646-7559.6446199.85-148600416415.4-16816851480.1519-8.00048504.9999-756046400-148600416416-1681685148040-8.00004504.0004-756046400-148600416416-16816851480N=14迭代49次后,满足收敛条件。(表略)N=40迭代74次后,满足收敛条件。(表略)2.6习题5.27调用MATLAB自带的lsqnonlin.m函数
本文标题:北航最优化方法大作业参考
链接地址:https://www.777doc.com/doc-5874532 .html