和图有关的优化问题.ppt

[数学模型] s.t. [模型计算] sets: nodes/1..6/:; hu(nodes,nodes)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,4 5,6/:f,c; endsets data: c=8 7 9 5 9 2 5 6 10; enddata max=flow; flow=@sum(hu(i,j)|i#eq#1:f(i,j)); @for(hu(i,j):@bnd(0,f,c)); @for(nodes(i)|i#ne#1#and#i#ne#6:@sum(hu(i,j):f(i,j))=@sum(hu(j,i):f(j,i))); 计算结果 Global optimal solution found. Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( 1, 2) 7.000000 0.000000 F( 1, 3) 7.000000 0.000000 F( 2, 3) 2.000000 0.000000 F( 2, 4) 5.000000 -1.000000 F( 3, 5) 9.000000 -1.000000 F( 4, 6) 5.000000 0.000000 F( 5, 6) 9.000000 0.000000 结果分析 s t v1) v2 v3 v4 (8,7) (7,7) (5,2) (2,0) (9,5) (9,9) (5,5) (6，0) (10,9) 将求解的每条管道的流量写在图上，进一步分析 由每条边的(c,f)值可以看出，只要(v2,v4)边扩容一个单位，整个网络流量就会扩大一个单位！瓶颈所在！！这种模型专门研究车流量、信息流量、金融流量、货物流量、汛期河水流量等问题，用以寻找瓶颈所在，以供改造网络！！ 五、最小费用最大流 例6 由于输油管道长短不一或者地质等原因，使得每条管道上运费也不同，因此除了要考虑输油管道的最大流外，还需要考虑输油管道输送最大流的费用。如图所示是带有单位运费的网络，其中第一个数字是网络的容量，第二个数字就是网络的单位费用。 s t v1 v2 v3 v4 (8,2) (7,8) (5,5) (2,1) (9,2) (9,3) (5,6) (6,4) (10,7) 最小费用最大流问题 [变量设置] fij表示弧(i,j)上的流量; cij为弧(i,j)上的单位运费，uij为弧(i,j)上的容量; Fv 为网络的实际流量. [建立模型] [模型计算] dian/s,v1,v2,v3,v4,t/:; hu(dian,dian)/s,v1 s,v2 v1,v2 v1,v3 v2,v4 v3,v2 v3,t v4,v3 v4,t/:c,f,u; endsets min=@sum(hu(i,j):c(i,j)*f(i,j)); @sum(hu(i,j)|i#eq#1:f(i,j))=14; n=@size(dian); @sum(hu(i,j)|j#eq#n:f(i,j))=14; @for(dian(i)|i#ne#1#and#i#ne#n:@sum(hu(i,j):f(i,j))=@sum(hu(j,i):f(j,i))); @for(hu(i,j):@bnd(0,f,u)); data: u=8,7,5,9,9,2,5,6,10; c=2,8,5,2,3,1,6,4,7; enddata 计算结果 Global optimal solution found. Objective value: 205.0000 Variable