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

《北航最优化方法大作业参考》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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)

2、T，根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1×13)。图1网络拓扑和流量需求-19-1.17节点算例求解1.1.1算例1（b1=[4;-4;0;0;0;0;0]T）转化为线性规划问题：MinimizecTx1SubjecttoAx1=b1x1>=0利用Matlab编写对偶单纯形法程序，可求得:最优解为x1*=[4000000000000]T对应的最优值cTx1=201.1.2算例2（b2=[4;0;-4;0;0;0;0]T）MinimizecTx2SubjecttoAx2=b2X2>=0利用Matlab编写对偶

3、单纯形法程序，可求得:最优解为x2*=[0400000000000]T对应的最优值cTx2=201.1.3算例3（b3=[0;-4;4;0;0;0;0]T）MinimizecTx3SubjecttoAx3=b3X3>=0利用Matlab编写对偶单纯形法程序，可求得:最优解为x3*=[4000400000000]T对应的最优值cTx3=40-19-1.1.1算例4（b4=[4;0;0;0;0;0;-4]T）MinimizecTx4SubjecttoAx4=b4X4>=0利用Matlab编写对偶单纯形法程序，可求得:最优解为x4*=[4004000004000]T对

4、应的最优值cTx4=601.2计算结果及结果说明1.2.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.2.2算例2（b2=[4;0;-4;0;0;0;0]T）算例2中，由b2可知，节点3为需求节点，节点1为供给节点，由节点1将信息传输至节点2的最短路径为弧2

5、。-19-图3算例2最优传输示意图求得的最优解为x2*=[0400000000000]T，即只经过弧2运输4个单位流量，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为20。经分析，计算结果合理可信。1.1.1算例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

6、，所以最小费用为40。经分析，计算结果合理可信。1.1.2算例4（b4=[4;0;0;0;0;0;-4]T）算例4中，由b4可知，节点7为需求节点，节点1为供给节点，由节点1将信息传输至节点7的最短路径为弧1->弧4->弧10。-19-图5算例3最优传输示意图求得的最优解为x4*=[4004000004000]T，即经过弧1运输4个单位流量至节点2，再经弧4运输4个单位流量至节点5，最后经弧5运输4个单位流量至节点7，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为60。经分析，计算结果合理可信。-19-1重要算法编写与观察1.1习题5.6（a）初值为（

7、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-19-图7收敛因子截图（a）初值为（10,0）时本算法令g的2范数在<10-4时，停止迭代，经过5次迭代收敛。收敛因子（f(k+1)-f*）/（f(k)-f*）=3.9022e-4图8收敛因子截图-19-（a）初值为（11,0）时本算法令g的2范数在<10

8、-4时，停止迭代，经过2