算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第8章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第8章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章迭代改进法线性规划与单纯形法二部图匹配最大流8.1线性规划与单纯形法营养搭配问题食物碳水化合物蛋白质脂肪A10090150￥24B12515060￥207560608.1线性规划与单纯形法营养搭配问题x1x2x1=6/19,x2=4/198.1线性规划与单纯形法线性规划问题（标准型）标准化:(1)极大值极小值:目标函数系数取反(2)不等式约束等式约束:增加约束变量(3)正数范围限制:变量平移8.1线性规划与单纯形法线性规划问题8.1线性规划与单纯形法线性规划问题x1=200/3,x2=100/38.1线性规划与单纯形法线性规划问题问题的可行域:n维空间中的一个凸多边形（凸集）问

2、题的最优解总:在凸多边形的顶点上获得8.1线性规划与单纯形法单纯形法求出一个基本可行解不存在改进可能则结束否则进行变换，转到下一个更优的顶点，而后继续上一步8.1线性规划与单纯形法单纯形法AlgorithmSimplex(c,b:real[];A:real[,])beginlet(m,n)=

3、A

4、,(B,N,R)=base(A);while(true)doletxB=b'=B-1*b,cB=c[0..n-m-1],cN=c[n-m..m-1];letfv=cB*xB,w=cB*B-1,k=-1,t1=0;foreach(jR)doletz=cB*B-1*N[k];if(z-c[j]>t

5、1)thenkj,t1z-c[j];if(k=-1)thenreturnx;lety=B-1*N[k],r=-1,t2=0;for(i=0tom-1)doif(y[i]>t2)thenri,t2y[j];if(r=-1)thenreturnx;xBb'–y*(b'[r]/y[r]),BB*y;end8.2二部图匹配二部图G=<(A,B),E>匹配a1a2a3a4a5b1b2b3b48.2二部图匹配二部图G=<(A,B),E>匹配a1a2a3a4a5b1b2b3b48.2二部图匹配二部图G=<(A,B),E>匹配最大匹配a1a2a3a4a5b1b2b3b48.2二部图匹配迭代改

6、进法找到任意一个匹配（如空匹配）不存在改进可能则结束寻找一个更大的匹配并继续上一步a1a2a3a4a5b1b2b3b4寻找增广路径8.2二部图匹配迭代改进法交错路径:路径中任意两条相邻的边都是一条属于M而另一条不属于Ma1a2a3a4a5b1b2b3b48.2二部图匹配迭代改进法交错路径:路径中任意两条相邻的边都是一条属于M而另一条不属于M增广路径:起点和终点都不在M中的交错路径a1a2a3a4a5b1b2b3b48.2二部图匹配AlgorithmBipartiteMatching(A,B:set;E:set)beginletM={E[0]};//初始匹配le

7、tQ=A{E[0].a};while(

8、Q

9、>0)doletu=Q[0];letP=Augment(u,A,B,E,M);if(P=null)thenthenQQ{u};elseMMP;QA{e.a

10、eM};returnM;end迭代改进法8.3最大流流网络定义:流网络G=是一个有向图，其中每条边(u,v)E上的权值c(u,v)≥0表示允许通过的最大容量。网络中存在两个特殊的顶点：源点s和汇点t8.3最大流流网络定义:流网络G=是一个有向图，其中每条边(u,v)E上的权值c(u,v)≥0表示允许通过的最大容量。网络中存在两个特殊的顶点：源点

11、s和汇点t网络中的流:实值函数f:VVR，其满足f(u,v)≤c(u,v)，f(u,v)=−f(v,u)；除s和t外，其它任意顶点u满足流守恒特性∑vVf(u,v)=08.3最大流最大流问题输入：一个流网络G=，其源点和汇点分别为s和t输出：G中从s到t的最大值流f8.3最大流迭代改进法初始时令f为一个空流如不能再增加流量则结束对流进行扩充并继续上一步寻找增广路径8.3最大流迭代改进法残留网络:由f导出的G的残留网络为Gf=，其中Ef={(u,v)E

12、cf(u,v)>0},cf(u,v)=c(u,v)−f(u,v)引理8.1:设若Gf是由f导出的G

13、的残留网络，且f′为Gf中的一个流，那么f+f′是G中的一个流，其值

14、f+f′

15、=

16、f

17、+

18、f′

19、推论8.1:设P是Gf中的一条增广路径，那么f′=f+fP是G中的一个流，且

20、f′

21、>

22、f

23、8.3最大流AlgorithmFord-Fulkerson(V:set;E:set;c:int[,];s,t:int)beginletn=

24、V

25、,m=

26、E

27、,f=newint[n,n],f’=newint[n,n];f