图与网络优化模型

1、第十章图与网络优化模型在图论中通常用v 表示点， e 表示边（无向） ，a 表示弧（有向） ，g 表示图，点和边构成的图称为无向图，g=（v，e） ，点和弧构成的图称为有向图,g=(v,a)。对图 g 的边（或弧）标上权数，称为赋权图。求 1 到 7 的最短路。本图是个有向图， 弧上的数字不妨理解为距离。目前用于求解最短路的算法有多种，如：动态规划法， dijkstra 算法， 0-1 规划方法等。下面只介绍0-1 规划法设 1 为起点， 7 为终点。引入1 , 0ijx表示：若弧 (i,j) 在最短路上 ,1ijx,否则，0ijxz 为目标函数上各弧的路程之和。起点 1 必定有一条弧出发,所

2、以121njjx终点 n 必定有一条弧到达,所以111niinx其它点有两种情况：(1) 该点不在最短路上， 即无进线弧， 也无出线弧。 满足：0, 1nkiiikx， 且0, 1nkiikix(2) 该点在最短路上，即有进线弧，也有出线弧。满足：1, 1nkiiikx，且1, 1nkiikix改写上述两个等式为：0,1, 1iinjkjnkiiikxxx1 , 0,.,2, 1, 01 ,11. .min111111,ijiinijiniijniinniinjiijijxnixnjxxxxtsxwzmodel : sets: city/1.7/;! 定义 7个城市 ;links(city,c

3、ity):dist,x;! 定义各城市之间的距离表( 若城市 i 到城市 j 无路 , 用一个大数表示 ),决策变量 ;endsetsdata: dist=0 2 10 1000 1000 1000 1000 1000 0 7 3 1000 1000 1000 1000 1000 0 1000 4 1000 1000 1000 1000 1000 0 1000 1000 8 1000 1000 5 1000 0 3 7 1000 1000 1000 1000 1000 0 12 1000 1000 1000 4 1000 3 0 ; enddatan= size (city); min =su

4、m(links:dist*x); sum(city(i):x(1,i)=1; sum(city(i):x(i,n)=1; for (city(i)|i#gt#1 #and# i#lt#n: sum(city(j):x(i,j)=sum(city(j):x(j,i); for (city(i):x(i,i)=0); for (links:bin (x); end 10.2 旅行售货员 tsp 模型有一个旅行推销员，从某个城市出发，要遍访若干城市各一次且仅一次，最后返回原来出发城市。已知从城市i 到城市 j的旅费为ijc，问如何安排旅行路线使总旅费最小？分析：巡回 - 能到每个城市一次，且仅一次的

5、一条线路称为一个巡回。子巡回 - 从一个起点出发, 到若干 ( 不是全部 ) 城市一次 , 且仅一次 ,又回到起点的一条线路称为一个子巡回. 定理 1: 含有一个子巡回, 必定至少有两个子巡回. 定理 2:tsp模型的一条最优巡回, 必定不含子巡回. 证明 : 如果含有子巡回, 则必存在一个子巡回有这种情况: 有一个城市要经过二次, 才能回到起点城市 . 如何用数学表达式来描述子巡回与总体巡回的区别呢? 显然 ,有子巡回的线路必然有一个城市( 这个城市却不是起点城市) 要经过二次 , 而不含子巡回的线路只有起点城市才经过二次. 假设有一条线路: 没有子巡回的情形:121.xxxxn有子巡回的情

6、形:113321.xxxxxxxxnii引入变量iu, 对上述线路上的各城市按序给予编号,1iui, 每个城市只编一次号. 没有子巡回的情形1iiuu:-1,-1,-1,.,-1,-1 有子巡回的情形1iiuu:-1,-1,-1,.,m,.,-1,-1 m不等于 -1. 定理 3: 设1 ,0ijx表示是否从城市i 到城市 j, 约束条件 :jijiuunnxuujiijji,.,3, 2,.,2 , 1, 0, 1则:(1)任何含有子巡回的路线必然不满足上述约束条件( 不管iu如何取值 ) (2)不含子巡回的线路都可以满足上述约束条件.( 只要iu取适当值 ) tsp 模型如下 : 不含子巡

7、回njixjinixjinjxtsxczijnjijniijnjiijij,.,3 ,2 , 1, 1 , 0,.,3 ,2, 1, 1,.,3 ,2, 1, 1. .min111,具体例子 : 已知六个城市之间的路程如下表: a b c d e f a 0 702 454 2396 1196 842 b 0 324 1093 2136 764 c 0 1137 2180 798 d 0 1616 1857 e 0 2900 f 0 求一条 tsp 线路 ? model : sets: city/1.6/:u;! 定义六个城市 ,u 是tsp线路的编号 ;links(city,city):di

8、st,x;!dist距离列表 ,x 为决策变量 ;endsetsdata: !u=0,1,2,3,4,5;dist=0 702 454 842 2396 1196 702 0 324 1093 2136 764 454 324 0 1137 2180 798 842 1093 1137 0 1616 1857 2396 2136 2180 1616 0 2900 1196 764 798 1857 2900 0 ; enddatan= size (city); min =sum(links:dist*x); for (links:bin (x);!x 为0-1 变量 ;for (city(i)

9、:sum(city(j)|i#ne#j:x(i,j)=1); for (city(i):sum(city(j)|i#ne#j:x(j,i)=1); for (city(i):for (city(j)|j#gt#1 #and# i#ne#j:u(i)-u(j)+n*x(i,j)=n-1);); for (city(i):u(i)=1; sum(node(i)|i#gt#1:x(i,1)=0; for (node(k)|k#gt# 1:sum(node(i)|i#ne#k:x(i,k)=1;); for (link(i,k)|i#gt#k:x(i,k)+x(k,i)=1;); for (node(

10、i):x(i,i)=0;); sum(link:x)=n-1; u(1)=0; for (link:bin (x); for (node(i)|i#gt#1:u(i)=sum(node(k):u(k)*x(k,i)+1); for (node(i)|i#gt#1:u(i)=n-1;); end 10.4 最大流问题定义 1：给一个有向图g= （v， e），在 v中指定一个点，称为发点（记为sv），和另一个点，称为收点（记为tv），其余的点称为中间点。对于每一个弧evvji),(，赋权0),(jivvw称为弧容量。这样的d叫做一个网络，记g=(v,e,w) 。网络是赋权的有向图。发点只有流出弧，

11、没有流进弧；收点只有流入弧，没有流出弧，这样的网络称为运输网络。设),(jivvf是定义在网络 g=（v ，e，w ）的边集 e上的一个实数函数，满足：（1）),(),(jijivvwvvf- 每条边的流量不超过该边大弧容量。（2）tsjjiivxvxxvfvxf, ),(),(- 中间点流入与流出平衡。（3）jtjiisvvfvvfq),(),(- 发点总流出与收点总流入平衡。称),(jivvf为网络 g 的流。 q 为总流量。最大流问题就是在上述（1）（ 2）（ 3）的条件下，如何使q 最大。求网络最大流在图论中有ford-fulkerson算法，但是网络最大流也是一个线性规划问题。其数学

12、模型：2), 1 (maxiifq-由发点 1到其它点的流出量总和。n表示收点 . nkkifikfnjiwjiftsiiij,.,2,1, ),(),(,.,3 ,2 ,1,),(0.例：求下列从 s到t的最大流model : sets: node/1.5/;! 定义节点 ;link(node,node)/1,2 1,3 1,4 2,3 3,2 3,4 2,5 4,5/:w,f; endsetsdata: w=2 9 3 7 6 4 8 5; enddatan= size (node); max=sum(link(i,j)|i#eq#1:f(i,j); for (link(i,j):f(i,

13、j)=w(i,j); for (node(i)|i#gt#1#and#i#lt#n:sum(link(j,i):f(j,i)=sum(link(i,j):f(i,j); sum(link(i,j)|i#eq#1:f(i,j)=sum(link(i,j)|j#eq#n:f(i,j); end 10.5 最小费用最大流网络最大流中不涉及费用问题，在实际问题中，在网络中的各边的运输费用是各不相同的，在满足最大流的情况下，求出最小费用，就是最小费用最大流问题。下图所示是最小费用最大流问题。每一条边上有两个数字，前者表示容量， 后者表示单位费用。求最小费用最大流可以用线性规划问题模型，分两步：1 先求没

14、有费用的最大流。model : sets: node/1.6/;! 定义节点 ;link(node,node)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,6 5,4/:w,f; endsetsdata: w=8 7 5 9 9 2 5 6 10; enddatan= size (node); max=sum(link(i,j)|i#eq#1:f(i,j); for (link(i,j):f(i,j)=w(i,j); for (node(i)|i#gt#1#and#i#lt#n:sum(link(j,i):f(j,i)=sum(link(i,j):f(i,j); sum(lin

15、k(i,j)|i#eq#1:f(i,j)=sum(link(i,j)|j#eq#n:f(i,j); end 最大流为 11。2 把最大流当作一个约束条件，求费用最小值。model : sets: node/1.6/;! 定义节点 ;link(node,node)/1,2 1,3 2,3 2,4 3,5 4,3 4,6 5,6 5,4/:c,w,f; endsetsdata: w=8 7 5 9 9 2 5 6 10; c=2 8 5 2 3 1 6 4 7; enddatan= size (node); max=sum(link(i,j):c(i,j)*f(i,j); sum(link(i,j)|i#eq#1:f(i,j)=11; for (link(i,j):f(i,j)=w(i,j