图的优化问题剖析.ppt

图的优化问题优化问题之一舒兴明定义一个图是由点集 V={v i}和V中元素的无序对的一个集合 E={ e k} 所构成的二元组,记为 G=(V,E) ,V中元素 v i叫做顶点, E中的元素e k叫做边。 v 1v 2v 3v 4e 1e 2e 3e 4e 5e 6图 1 无向图 G=(V,E) V={v 1 ,v 2 ,v 3 ,v 4} E={e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6}其中: e1=(v1,v1) e2=(v1,v2) e3=(v1,v3) e4=(v2,v3) e5=(v2,v3) e6=(v3,v4) 边集图 2 有向图 v 1v 2v 3v 4 G=(V,E) V={v 1 ,v 2 ,v 3 ,v 4} E={e 1 ,e 2 ,e 3 ,e 4}其中: e1=(v1,v3) e2=(v1,v4) e3=(v2,v3) e4=(v2,v4) e 1e 2e 3e 4弧集无向图或有向图都用来表示事物之间的关系,在优化中, 不严格按照图论知识去研究问题,而是遇到问题根据问题解释边和点的意义。 1、存在转运的运输问题例题 1 有两个工厂 A1,A2 ,产量分别等于 9,8个单位;四个顾客 B1,B2,B3,B4 ,其需求量分别为 3,5,4,5;三个仓库 M1,M2,M3 ,三个仓库的最大库存量分别为 7,6,7 ,货物必须从工厂先运往仓库配送到顾客手中。从工厂到仓库,从仓库到顾客的运费单价如下表,求总运费最少的运输方案。仓库工厂或顾客 A1 A2 B1 B2 B3 B4 M1 1 3 5 7 - 5 M2 2 1 9 6 7 4 M3 - 2 - 6 7 - 注:表中”-”表示没有道路连接。[问题分析] 凡是遇到有中转的运输问题,尽可能先画出图来表示产地、中转、销地直接的(道路)连接关系的有向图。 A1 A2 M1 M2 B1 M3 B2 B4 B3 两个工厂、三个中转、四个顾客的转运问题[变量设置] ai:表示第 i个工厂的产量,i=1,2; bj:表示第 j个顾客的需求量,j=1,2,3,4; mk : 表示第 k个中转的仓库上限,k=1,2,3; Xik :表示从工厂 i运到仓库 k的运输量; Ykj :表示从仓库 k运到顾客 j的运输量; C1ik :表示从工厂 i运到仓库 k的单位运费; C2kj :表示从仓库 k运到顾客 j的单位运费; [建立模型]总运费最小: ????????? 31k 41j kj kj 21i 31k ik iky2cx c1 min 工厂约束: 2,1i,ax i 31k ik????中转仓库的约束: 3,2,1k,yx 41j kj 21i ik??????顾客约束: 4,3,2,1j,by j 31k kj????特殊道路的要求: ,0yyyx 34 13 31 13????变量约束: 4,3,2,1j;3,2,1k;2,1i,0y,x kj ik????[计算程序及其结果] sets: gch/1..2/:a; zhzh/1..3/:m; gk/1..4/:b; link1(gch,zhzh):x,c1; link2(zhzh,gk):y,c2; endsets data: a=9,8;b=3,5,4,5;m=7,6,7; c1=1 2 0 3 1 2; c2=5 7 0 5 9 6 7 4 0 6 7 0; enddata min=***@sum(link1:x * c1)+***@sum(link2:y * c2); @ for(gch(i):***@sum(zhzh(k):x(i,k ))< a(i )); @ for(gk(j):***@sum(zhzh(k):y(k,j ))> b(j )); @ for(zhzh(k):***@sum(gch(i):x(i,k ))>@ sum(gk(j):y(k,j ))); x(1,3)=0;y(3,1)=0;y(1,3)=0;y(3,4)=0; Global optimal solution found at iteration: 11 Objec