《北航最优化方法大作业参考.pdf》由会员分享，可在线阅读，更多相关《北航最优化方法大作业参考.pdf（19页珍藏版）》请在三一文库上搜索。
1、1 1 流量工程问题 1.1 问题重述 定义一个有向网络G=(N,E) ，其中 N 是节点集， E 是弧集。令 A 是网络 G 的点弧关 联矩阵，即 NE 阶矩阵，且第 l 列与弧里 (I,j)对应，仅第 i 行元素为 1，第 j 行元素为 -1， 其余元素为 0。再令 bm=(bm1,bmN)T，fm=(fm1,fmE)T，则可将等式约束表示成： Afm=bm 本算例为一经典 TE 算例。算例网络有7 个节点和 13 条弧，每条弧的容量是5 个单 位。此外有四个需求量均为4 个单位的源一目的对，具体的源节点、目的节点信息如图所 示。 这里为了简单，省区了未用到的弧。此外， 弧上的数字表示弧的
2、编号。 此时， c=(5,5 ,5)1 13) T ， 根据上述四个约束条件， 分别求得四个情况下的最优决策变量x=(x12,x13,x75)113)。 图 1 网络拓扑和流量需求 2 1.2 7 节点算例求解 1.2.1 算例 1（b1=4;-4;0;0;0;0;0 T） 转化为线性规划问题： Minimize c Tx1 Subject to Ax1=b1 x1=0 利用 Matlab 编写对偶单纯形法程序，可求得: 最优解为 x1*=4 0 0 0 0 0 0 0 0 0 0 0 0 T 对应的最优值 cTx1=20 1.2.2 算例 2（b2=4;0;-4;0;0;0;0 T） Min
3、imize c Tx2 Subject to Ax2=b2 X2=0 利用 Matlab 编写对偶单纯形法程序，可求得: 最优解为 x2*=0 4 0 0 0 0 0 0 0 0 0 0 0 T 对应的最优值 cTx2=20 1.2.3 算例 3（b3=0;-4;4;0;0;0;0 T） Minimize c Tx3 Subject to Ax3=b3 X3=0 利用 Matlab 编写对偶单纯形法程序，可求得: 最优解为 x3*=4 0 0 0 4 0 0 0 0 0 0 0 0 T 对应的最优值 c Tx3=40 3 1.2.4 算例 4（b4=4;0;0;0;0;0;-4 T ） Min
4、imize c Tx4 Subject to Ax4=b4 X4=0 利用 Matlab 编写对偶单纯形法程序，可求得: 最优解为 x4*=4 0 0 4 0 0 0 0 0 4 0 0 0 T 对应的最优值 c Tx4=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、 其余弧无流量。又因为，每条弧的费用均为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*=0 4 0 0 0 0 0 0 0 0 0 0 0 T，即只经过弧 2 运输 4 个单位流量， 其余弧无流量。又因为，每条弧的费用均为5，所以最小费用为20。 经分析，计算结果合理可信。 1.3.3 算例 3（b3=0;-4;4;0;0;0;0 T）
6、算例 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.4 算例 4（b4=4;0;0;0;0;0;-4 T ） 算例 4 中，由 b4 可知，节点 7 为需求节点，节点1 为供给节点，由节点1 将信息传 输
7、至节点 7 的最短路径为弧 1-弧 4-弧 10。 5 图 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。 经分析，计算结果合理可信。 6 2 重要算法编写与观察 2.1 习题 5.6 （a） 初值为（ 0,0）时 本算法令 g 的 2 范数在 =0 flag=0; sol=zeros(1,nA); for i=1:mA-1 sol(N
8、(i)=A(i,nA); end val=sol*(B(mA,:); else for i=1:mA-1 if A(i,nA)=0 disp(have infinite solution! ); flag=0; break ; end end if flag temp=0; for i=1:mA-1 if A(i,nA)temp temp=sita(i); inb=i; end end for i=1:mA-1 if i=outb N(i)=inb; end end A(outb,:)=A(outb,:)/A(outb,inb); for i=1:mA if i=outb A(i,:)=A(i
9、,:)-A(outb,:)*A(i,inb); A(mA,nA)=0; end end end end end 3.2 最速降线法求 Rosenbrock函数最小值 matlab 程序如下： function rb = rbfun(x,y) rb=100*(y-x2)2+(1-x)2 end 17 clear clc syms x y g G g=gradient(rb(x,y),x y) %定义梯度向量 G=hessian(rb(x,y),x y) %定义海森阵 X(1,:)=-1.4 1; %定义初始点 x=X(1,1);y=X(1,4); A(1,:)=subs(g) %给梯度赋初值 i
10、=1 while(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+1 end 3.3 牛顿法求 Rosenbrock函数
11、最小值 matlab 程序如下： function rb = rbfun(x,y) rb=100*(y-x2)2+(1-x)2 end clear clc syms x y g G g=gradient(rb(x,y),x y) %定义梯度向量 18 G=hessian(rb(x,y),x y) %定义海森阵 X(1,:)=-1.4 1; %定义初值 x=X(1,1);y=X(1,4); A(1,:)=subs(g) % 给梯度赋初值 H=subs(inv(G) %得到海森阵初值 S(1,:)=-A(1,:)*H %得到 s 初值 i=1 while (norm(S(i,:),4)10(-6)
12、 %收敛条件 f(i)=rb(x,y) %定义函数值 X(i+1,:) = X(i,:)+S(i,:) %得到下一迭代点 x=X(i+1,1);y=X(i+1,4) %给 x,y 分别赋值 A(i+1,:)=subs(g) %得到新的梯度值 H=subs(inv(G) %得到新的海森阵 S(i+1,:)=-A(i+1,:)*H %得到新的增量 s i=i+1 end 3.4 共轭梯度法求解习题5.19 程序如下： clear clc K=40 G=zeros(K,K) for m = 1: K for n = 1: K G(m,n)=1/(m+n-1) end end X(1,:)=zeros
13、(1,K) b=ones(1,K) A(1,:)=X(1,:)*G-b 19 P(1,:)=-A(1,:) i=1 while (norm(A(i,:),4)10(-6) %收敛条件 d=P(i,:)*G fz(i)=A(i,:)*A(i,:) % 精确搜索法步长的分子 fm(i)=P(i,:)*d %精确搜索法步长的分母 a(i)=fz(i)/fm(i) %精确搜索法步长 X(i+1,:) = X(i,:)+a(i)*P(i,:) %产生新的点 A(i+1,:)=A(i,:)+a(i)*d beta(i+1)=(A(i+1,:)*A(i+1,:)/(A(i,:)*A(i,:) P(i+1,:)=-A(i+1,:)+beta(i+1)*P(i,:) i=i+1 end