算法的设计（第8章迭代改进法）.pptVIP

第8章 迭代改进法 线性规划与单纯形法 二部图匹配 最大流 8.1 线性规划与单纯形法 营养搭配问题 食物 碳水化合物 蛋白质 脂肪 A 100 90 150 ￥24 B 125 150 60 ￥20 75 60 60 8.1 线性规划与单纯形法 营养搭配问题 x1 x2 x1=6/19, x2=4/19 8.1 线性规划与单纯形法 线性规划问题（标准型） 标准化: (1) 极大值 ? 极小值: 目标函数系数取反 (2) 不等式约束 ? 等式约束: 增加约束变量 (3) 正数范围限制: 变量平移 8.1 线性规划与单纯形法 线性规划问题 8.1 线性规划与单纯形法 单纯形法 求出一个基本可行解 不存在改进可能则结束 否则进行变换，转到下一个更优的顶点，而后继续上一步 8.1 线性规划与单纯形法 单纯形法 Algorithm Simplex(c, b: real[]; A: real[,]) begin let (m,n) = |A|, (B,N,R) = base(A); while (true) do let xB = b = B-1*b, cB = c[0..n-m-1], cN = c[n-m..m-1]; let fv = cB*xB, w = cB*B-1, k = -1, t1 = 0; foreach (j ? R) do let z = cB*B-1*N[k]; if (z-c[j] t1) then k ? j, t1 ? z-c[j]; if (k = -1) then return x; let y = B-1*N[k], r = -1, t2 = 0; for (i=0 to m-1) do if (y[i] t2) then r ? i, t2 ? y[j]; if (r = -1) then return x; xB ? b – y*(b[r]/y[r]), B ? B*y; end 8.2 二部图匹配 二部图G = (A,B),E 匹配 a1 a2 a3 a4 a5 b1 b2 b3 b4 8.2 二部图匹配 二部图G = (A,B),E 匹配 a1 a2 a3 a4 a5 b1 b2 b3 b4 8.2 二部图匹配 二部图G = (A,B),E 匹配 最大匹配 a1 a2 a3 a4 a5 b1 b2 b3 b4 8.2 二部图匹配 迭代改进法 找到任意一个匹配（如空匹配） 不存在改进可能则结束 寻找一个更大的匹配并继续上一步 a1 a2 a3 a4 a5 b1 b2 b3 b4 寻找增广路径 8.2 二部图匹配 迭代改进法 交错路径: 路径中任意两条相邻的边都是一条属于M而另一条不属于M a1 a2 a3 a4 a5 b1 b2 b3 b4 8.2 二部图匹配 迭代改进法 交错路径: 路径中任意两条相邻的边都是一条属于M而另一条不属于M 增广路径: 起点和终点都不在M中的交错路径 a1 a2 a3 a4 a5 b1 b2 b3 b4 8.2 二部图匹配 Algorithm BipartiteMatching(A, B: setint; E: setint?int) begin let M = {E[0]}; //初始匹配 let Q = A \ {E[0].a}; while (|Q| 0) do let u = Q[0]; let P = Augment(u, A, B, E, M); if (P = null) then then Q ? Q \ {u}; else M ? M ? P; Q ? A \ {e.a | e?M}; return M; end 迭代改进法 8.3 最大流 流网络 定义: 流网络G = V,E,c是一个有向图，其中每条边(u,v)?E上的权值c(u,v)≥0表示允许通过的最大容量。网络中存在两个特殊的顶点：源点s和汇点t 8.3 最大流 流网络 定义: 流网络G = V,E,c是一个有向图，其中每条边(u,v)?E上的权值c(u,v)≥0表示允许通过的最大容量。网络中存在两个特殊的顶点：源点s和汇点t 网络中的流: 实值函数f: V?V?R，其满足f(u,v) ≤ c(u,v)，f(u,v) = ?f(v,u)；除s和t外，其它任意顶点u满足流守恒特性∑v?V f(u,v) =0