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

发布 2021-02-28 22:07:28 阅读 9823

定义一个有向网络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 网络拓扑和流量需求。

转化为线性规划问题:

minimize ctx1

subject to ax1=b1

x1>=0

利用matlab编写对偶单纯形法程序,可求得:

最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]t

对应的最优值ctx1=20

minimize ctx2

subject to ax2=b2

x2>=0

利用matlab编写对偶单纯形法程序,可求得:

最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]t

对应的最优值ctx2=20

minimize ctx3

subject to ax3=b3

x3>=0

利用matlab编写对偶单纯形法程序,可求得:

最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]t

对应的最优值ctx3=40

minimize ctx4

subject to ax4=b4

x4>=0

利用matlab编写对偶单纯形法程序,可求得:

最优解为x4*=[4 0 0 4 0 0 0 0 0 4 0 0 0]t

对应的最优值ctx4=60

算例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。

经分析,计算结果合理可信。

算例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。

经分析,计算结果合理可信。

算例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。

经分析,计算结果合理可信。

算例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。

经分析,计算结果合理可信。

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 收敛因子截图。

c) 初值为(10,0)时。

本算法令g的2范数在<10-4时,停止迭代,经过5次迭代收敛。

收敛因子(f(k+1)-f*)/f(k)-f*)=3.9022e-4

图 8 收敛因子截图。

d) 初值为(11,0)时。

本算法令g的2范数在<10-4时,停止迭代,经过2次迭代收敛。

收敛因子(f(k+1)-f*)/f(k)-f*)=0

图 9 收敛因子截图。

图 10 自变量(x1,x2)截图。

总结:最速降线法的收敛因子随着初值的不同而变化,对于个别初值(如本习题初值取(11,0)时),算法可迅速收敛。因此,初值的选取对于最速降线法的收敛速度有较大影响。

a) 由可得:

故,牛顿迭代法的确切公式为:

b)从以下五个初值开始迭代。

1)x(0)=7.40

表 1 初值1牛顿法迭代结果表。

2)x(0)=7.20

表 2 初值2牛顿法迭代结果表。

3)x(0)=7.01

表 3 初值3牛顿法迭代结果表。

4)x(0)=7.80

表 4 初值4牛顿法迭代结果表。

5)x(0)=7.88

表 5 初值5牛顿法迭代结果表。

c)本问题的最优值为7.4444444。由上述五个初值点的前五步迭代可以看出:

当初值点在区间(7.4444444,7.8888)内时,第二次迭代点将落在(7,7.4444444)之间,随后逐渐增加,直至逼近最优值。

当初值点在区间(7,7.4444444)内时,则迭代点逐渐增加,逼近最优值。

当取初值不在(7,7.8888)内时,牛顿法不收敛。

a) 没有线搜索的牛顿法。

=0.1时,=1时,b) 具有线搜索的牛顿法。

=0.1时,=1时,未完成)

a)初值选(1.2,1.2)时, 最速降线法:

本算法令g的2范数在<10-2时,停止迭代,经过3262次迭代得到以下结果。

图 11 最速降线法初值为(1.2,1.2)的等值线图及迭代轨迹。

牛顿法:本算法令s的4范数在<10-6时,停止迭代,经过4次迭代得到以下结果。

图 12 牛顿法初值为(1.2,1.2)的等值线图及迭代轨迹。

b)初值选(-1.2,1)时, 最速降线法:

本算法令g的4范数在<10-2时,停止迭代,经过6835次迭代得到以下结果。

图 13 最速降线法初值为(-1.2,1)的等值线图及迭代轨迹。

牛顿法:本算法令s的4范数在<10-6时,停止迭代,经过6次迭代得到以下结果。

图 14 牛顿法初值为(-1.2,1)的等值线图及迭代轨迹。

迭代6次后,满足收敛条件。

表 6 n=5时,各迭代点x值。

迭代19次后,满足收敛条件。

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

定义一个有向网络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算例。算例网...

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

定义一个有向网络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算例。算例网...

作业 最优化方法课程设计

确定性存贮模型。在讨论确定性模型前,首先对一些常用符号的含义作必要的说明。c 单位时间平均运营费用 或称单位时间平均总费用 r 单位时间物品需求量 或称需求速度 p 单位时间物品生产量 或称生产速度 k 物品单价 外部订购 或单位物品成本费用 内部生产 q 订货量 外部订购 或生产量 内部生产 c1...