北航最优化方法大作业参考

-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'()97fxx24()(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函数