北航最优化大作业

最优化大作业1周京成2020年1月8日1问题重述定义网络G为(N,A),其中N表示节点集，A表示弧集。对每条弧l=(i,j)∈A设其容量是cl,代表每条弧上所能承受负载的上界.已知供给点−需求点对(xm,ym),m=1,2,···,M且(xm,ym)的供给需求是dm,这表示物资在节点xm流入网络，然后在节点ym流出网络的平均运输量.后面，我们用符号N和E分别表示集合N和A的数量。将供给点−需求对(xm,ym)沿弧l的物资流m是fm.找到流指派满足条件:fl=M∑m=1fml≤cl,∀l∈A(1)∑l:l=(i,j)∈Afml−∑l:l=(j,i)∈Afml=bmi,m=1,2,···,M,∀i∈N(2)fml≥0,m=1,2,···,M,∀l∈A(3)其中(2)代表流平衡约束，即从节点i流出的物资减去从节点i流出的物资即为要运出的物资量。考虑下图中的网络。令A是网络G的点弧关联矩阵即N×E阶矩阵，且第l列与弧l=(i,j)对应，仅第i行的元素为1，第j行的元素为−1，其余元素为0。再令bm=(bm1,bm2,···,bmN)T,fm=(fm1,fm2,···,fmN)T则可将等式约束(2)表示成Afm=bm图1显示的是TE中的一个经典例子。我们用这个例子来说明这个约束.这个网络有7个节点13条弧，每条弧的容量是5个单位.此外有四个需求量均为4个单位的源－目的对(M=4)，具体的源节点、目的节点信息如图所1示.这里为了简单，省去了未用到的弧.此外，弧上的数字表示弧的编号，此时c=((5,5···,5)1×13)TA=1110−100000000−10010000100000−10011000000000−10001100−100000−100−101100−100000−10−100110000000000−10−11b1=4−400000b2=40−40000b3=0−440000b4=400000−42极小化MAU极小化MAU可以表述成minimizezsubjectto4∑m=1fmlcl−z≤0,∀l∈AAfm=bm,m=1,2,3,4(4)用matlab求解此线性规划，代码如下：c=ones(1,52)*0c(53)=1b=ones(13,1)*0A=ones(13,52)*0e=ones(13,1)*(-1)A=[A,e]Aeq=[1,1,1,0,-1,0,0,0,0,0,0,0,0;-1,0,0,1,0,0,0,0,-1,0,0,0,0;0,-1,0,0,1,1,0,0,0,0,0,0,0;0,0,-1,0,0,0,1,1,0,0,-1,0,0;20,0,0,-1,0,0,-1,0,1,1,0,0,-1;0,0,0,0,0,-1,0,-1,0,0,1,1,0;0,0,0,0,0,0,0,0,0,-1,0,-1,1]n=1j=Aeqwhile(n=3)j=blkdiag(j,Aeq)n=n+1endAeq=jm=ones(28,1)*0Aeq=[Aeqm]a=1while(a=13)k=1while(k=52)A(a,k+a-1)=0.2k=k+13enda=a+1;endbeq=[4,-4,0,0,0,0,0,4,0,-4,0,0,0,0,0,-4,4,0,0,0,0,4,0,0,0,0,0,-4]lb=ones(53,1)*0ub=ones(52,1)*5ub(53)=1[x,fval]=linprog(c,A,b,Aeq,beq,lb)代码得到的解x为[f1,f2,f3,f4,z],如下图：343极小化FT成本函数minimize∑l∈Azlsubjectto4∑m=1fml−zl≤0,∀l∈A34∑m=1fml−zl≤23cl,∀l∈A104∑m=1fml−zl≤163cl,∀l∈A704∑m=1fml−zl≤1783cl,∀l∈A5004∑m=1fml−zl≤14683cl,∀l∈A50004∑m=1fml−zl≤163183cl,∀l∈AAfm=bm,m=1,2,3,4(5)用matlab求解线性规划，代码如下：c=ones(1,52)*0c=[cones(1,13)*1]b1=ones(13,1)*0b2=ones(13,1)*(10/3)b3=ones(13,1)*(80/3)b4=ones(13,1)*(890/3)b5=ones(13,1)*(7340/3)b6=ones(13,1)*(81590/3)b=[b1;b2;b3;b4;b5;b6]A=ones(13,52)*0Aeq=[1,1,1,0,-1,0,0,0,0,0,0,0,0;-1,0,0,1,0,0,0,0,-1,0,0,0,0;0,-1,0,0,1,1,0,0,0,0,0,0,0;0,0,-1,0,0,0,1,1,0,0,-1,0,0;0,0,0,-1,0,0,-1,0,1,1,0,0,-1;0,0,0,0,0,-1,0,-1,0,0,1,1,0;50,0,0,0,0,0,0,0,0,-1,0,-1,1]n=1j=Aeqwhile(n=3)j=blkdiag(j,Aeq)n=n+1endAeq=jm=ones(28,13)*0Aeq=[Aeqm]a=1while(a=13)k=1while(k=52)A(a,k+a-1)=1k=k+13enda=a+1;endA1=A*3A2=A*10A3=A*70A4=A*500A5=A*5000A=[A;A1;A2;A3;A4;A5]e=ones(1,13)*(-1)E=diag(e)E1=[E;E;E;E;E;E]A=[AE1]beq=[4,-4,0,0,0,0,0,4,0,-4,0,0,0,0,0,-4,4,0,0,0,0,4,0,0,0,0,0,-4]lb=ones(52,1)*0lb=[lb;ones(13,1)*(-Inf)]ub=ones(52,1)*5ub=[ub;ones(13,1)*(+Inf)][x,fval]=linprog(c,A,b,Aeq,beq,lb,ub)得到的解x为[f1,f2,f3,f4,zl1,···,zl13],如下图:64数值结果解释4.1极小化MAU货物f11条路：1⃝→2⃝，数量为4货物f21条路：1⃝→3⃝，数量为4货物f31条路：3⃝→6⃝→7⃝→5⃝→2⃝，数量为4货物f41条路：1⃝→4⃝→5⃝→7⃝，数量为47所有货物的路径没有重复，flcl最大为0.84.2极小化FT函数货物f12条路：1⃝→2⃝，数量为2361⃝→4⃝→5⃝→2⃝，数量为16货物f21条路：1⃝→3⃝，数量为4货物f33条路：3⃝→1⃝→2⃝，数量为233⃝→6⃝→→4⃝→5⃝→2⃝，数量为533⃝→6⃝→→7⃝→5⃝→2⃝，数量为53货物f42条路：1⃝→4⃝→5⃝→7⃝，数量为731⃝→4⃝→6⃝→7⃝，数量为53得到目标函数最小值27838