1流量工程问题
1.1问题重述
定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，
其余元素为0。再令b
m =(b
m1
,…,b
mN
)T，f
m
=(f
m1
,…,f
mE
)T，则可将等式约束表示成：
Af m=b m
本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5 (5)
1×13
)T，
根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x
12,x
13
,…,x
75
)
1×13
)。
图 1 网络拓扑和流量需求
1.27节点算例求解
1.2.1\
T）
1.2.2算例1（b1=[4;-4;0;0;0;0;0]
转化为线性规划问题：
Minimize c T x1
Subject to Ax1=b1
x1>=0利用Matlab编写对偶单纯形法程序，可求得:
最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T
对应的最优值c T x1=20
1.2.3算例2（b2=[4;0;-4;0;0;0;0]T）
Minimize c T x2
Subject to Ax2=b2
\
X2>=0利用Matlab编写对偶单纯形法程序，可求得:
最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T
对应的最优值c T x2=20
1.2.4算例3（b3=[0;-4;4;0;0;0;0]T）
Minimize c T x3
Subject to Ax3=b3
X3>=0利用Matlab编写对偶单纯形法程序，可求得:
最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T
@
对应的最优值c T x3=40
1.2.5算例4（b4=[4;0;0;0;0;0;-4]T）
Minimize c T x4
Subject to Ax4=b4
X4>=0
利用Matlab编写对偶单纯形法程序，可求得:
最优解为x4*=[4 0 0 4 0 0 0 0 0 4 0 0 0]T
对应的最优值c T x4=60
1.3计算结果及结果说明
1.3.1算例1（b1=[4;-4;0;0;0;0;0]T）
\
算例1中，由b1可知，节点2为需求节点，节点1为供给节点，由节点1将信息传输至节点2的最短路径为弧1。
图 2 算例1最优传输示意图
求得的最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]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。
图 3 算例2最优传输示意图
求得的最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T，即只经过弧2运输4个单位流量，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为20。
经分析，计算结果合理可信。
1.3.3，
T）
1.3.4算例3（b3=[0;-4;4;0;0;0;0]
算例3中，由b3可知，节点2为需求节点，节点3为供给节点，由节点3将信息传输至节点2的最短路径为弧5->弧1。
图 4 算例3最优传输示意图
求得的最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T，即经过弧5运输4个单位流量至节点1，再经弧1运输4个单位流量至节点2，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为40。
经分析，计算结果合理可信。
1.3.5算例4（b4=[4;0;0;0;0;0;-4]T）
算例4中，由b4可知，节点7为需求节点，节点1为供给节点，由节点1将信息传
输至节点7的最短路径为弧1->弧4->弧10。
图 5 算例3最优传输示意图
求得的最优解为x4*=[4 0 0 4 0 0 0 0 0 4 0 0 0]T，即经过弧1运输4个单位流量至节点2，再经弧4运输4个单位流量至节点5，最后经弧5运输4个单位流量至节点7，其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为60。
;
经分析，计算结果合理可信。
2重要算法编写与观察
2.1习题
（a）初值为（0,0）时
本算法令g的2范数在<10-4时，停止迭代，经过86次迭代收敛。
收敛因子（f(k+1)-f*）/（f(k)-f*）=
图 6 收敛因子截图
（b）初值为（,0）时
本算法令g的2范数在<10-4时，停止迭代，经过112次迭代收敛。
·
收敛因子（f(k+1)-f*）/（f(k)-f*）=
