15.082期末考试 2003春季 姓名 答题说明 1.请回答考试册提供的所有间题。 2.请仔细预算您的时间。首先阅读整个考试内容经常是个好主意，以便您能首先做 用时量最小的问恩。 3.分值列在每个句题上
15.082 期末考试 2003 春季 姓名_________________________________ 答题说明 1. 请回答考试册提供的所有问题。 2. 请仔细预算您的时间。首先阅读整个考试内容经常是个好主意，以便您能首先做 用时量最小的问题。 3. 分值列在每个问题上
部分1.(45分) 1.(15分，部分a,b和c2分.部分d,e和f3分)考虑以下预流推进算法给出 的最大流问题。距离标号在左边给出。结点上面或下面的数字是超额。在弧上的数 字表示剩余容量， X ② 丑.结点的标号是否有效？为什么是或为什么不是？ b.可进入弧是什么？ c.I 哪些结点是活跃的？ d.如果使用最高层的推进算法，下一个被选结点是什么？进行推进重标号，然 后在首次不饱和推进后停止。说明中间步骤。 e.假设使用超额调整(excess scaling),我们有8-调整阶段，因此没有结点 有超过8的超额，每次不饱和推进有至少4个单位的流。根据课堂上给出 的超额调整算法，在下次推进时应该选择幂个（哪些）结点。 f.课堂上和教科书上使用势函数增广米证明0（如m)时间边界。势函数是什么？ 评估对当前预流的势函数
部分 1. (45 分) 1. (15 分, 部分a, b 和 c 2分。部分d, e 和f 3分) 考虑以下预流推进算法给出 的最大流问题。距离标号在左边给出。结点上面或下面的数字是超额。在弧上的数 字表示剩余容量。 a. 结点的标号是否有效？为什么是或为什么不是？ b. 可进入弧是什么？ c. 哪些结点是活跃的？ d. 如果使用最高层的推进算法，下一个被选结点是什么？进行推进重标号，然 后在首次不饱和推进后停止。说明中间步骤。 e. 假设使用超额调整(excess scaling)，我们有 8-调整 阶段。因此没有结点 有超过 8 的超额，每次不饱和推进有至少 4 个单位的流。根据课堂上给出 的超额调整算法，在下次推进时应该选择哪个(哪些)结点。 f. 课堂上和教科书上使用势函数增广来证明O(n2 m) 时间边界。势函数是什么？ 评估对当前预流的势函数
2.(12分)以下是在最小代价流问题中某一选代的可行流。假设在每条弧上的下界 是0·回忆弧(1，)的尾是结点i,头是结点j: 尾头容量流代价 12651 245 5 -2 437 4 2 137 5 2 23443 4。(行分)写出剩余网络，在利余网路中寻找一条负代价图，说明圈的容量，如 果没有负代价弧，说明为什么， b.(2分)用以上给出的蓬是可行的事实判定结点j=1,2,3,4的供应/需求 b(iD。 心.(5分)以上流和一生成树解有对应关系吗？如果没有，为什么没有？如果 有，基本可行结构是什么？结点势和非基本弧的即约代价是什么？ 3.(8分，每部分4分)考虑以下最小代价生成树问圈的网络。 5 2 3 2 6 6 8 4 3 5 a.最小代价生成树是什么？列举通过Kruskal算法颗序添加的最小代价生成树 的弧。您不需要说明算法的步骤。 h.考虑从结点1开始的最小代价生成树的Prim算法，以通过Prim算法添加到树 的顺序列举最小代价生成树的弧。您不需要说明算法的步骤
2. (12分) 以下是在最小代价流问题中某一迭代的可行流。假设在每条弧上的下界 是 0 。回忆弧 (i, j) 的尾是结点 i，头是结点j。 尾 头 容量 流 代价 1 2 6 5 1 2 4 5 5 -2 4 3 7 4 2 1 3 7 5 2 2 3 4 4 3 a. (5 分) 写出剩余网络，在剩余网络中寻找一条负代价圈，说明圈的容量。如 果没有负代价弧，说明为什么。 b. (2 分) 用以上给出的流是可行的事实判定结点 j = 1, 2, 3,4 的供应/需求 b(j)。 c. (5 分) 以上流和一生成树解有对应关系吗？如果没有，为什么没有？ 如果 有,基本可行结构是什么？结点势和非基本弧的即约代价是什么？ 3. (8分, 每部分 4 分) 考虑以下最小代价生成树问题的网络。 a. 最小代价生成树是什么？列举通过Kruskal 算法顺序添加的最小代价生成树 的弧。您不需要说明算法的步骤。 b.考虑从结点1开始的最小代价生成树的 Prim 算法。以通过Prim 算法添加到树 的顺序列举最小代价生成树的弧。您不需要说明算法的步骤
4.(10分，每部分5分)考虑在以下图的多品种流间题. 5个单 3 5个单 的商 位的商 品 品1 2 0 4个单 4个单 位的商 6 位的商 6 品2 弧的数目是代价，需要从结点1发送5单位的商品到结点4，需要从结点3发送 4单位的商品2到结点6。另外，在弧(1,2)，(2,5)，和(5.6)上有绑定约束。 ue=4,g=6,和w=3. a写出多品种流问题的路径公式。（这是使用列生成的公式，和在第二次关于多品种 流的课中讨论的一样)。 b.假设第一个受限主问题包括路径1-4和36.此受限主问避的最优解是什么？导 致的乳通行费是什么？假设算法能从每个有品添加一条路径。什么路径应该语加到 受限主问题的旁边？请证明您的回答
4. (10 分, 每部分 5 分) 考虑在以下图的多品种流问题。 弧的数目是代价。需要从结点 1 发送5 单位的商品到结点 4 。需要从结点 3 发送 4 单位的商品2 到结点 6。另外，在弧 (1, 2), (2, 5), 和 (5, 6)上有绑定约束。 u12 = 4, u25 = 6, 和 u56 = 3. a.写出多品种流问题的路径公式。(这是使用列生成的公式，和在第二次关于多品种 流的课中讨论的一样)。 b. 假设第一个受限主问题包括路径1-4 和 3-6。此受限主问题的最优解是什么？导 致的弧通行费是什么？假设算法能从每个商品添加一条路径。什么路径应该添加到 受限主问题的旁边？请证明您的回答
部分2(25分)建模和变换 5.(10分)考虑在网络G=NA)的通常最大流问题的简单变体，它中的页上的流 有正的下界1：以及正的上界，，不是从s到t发送最大的流量，在这中 的目标是从s到t发送最小单位的流，同时满足不是s和1的其他结点的下界 钓束和守恒。解释通过最大流算法的两个应用如何解决这个问题。（提示：首 先解释如何使用在网络G中最大流算法的一个应用来判定原问题的可行流，其 中，G和网络G密切相关。) 6.(15分，每部分5分)。考虑受限于单侧约束的最小代价网络流问避， =min ∑c (0) subject to ∑x,-∑xg=b,forieN (1) 示4 ∑sT 2) ( OSX S Hy for all (i,j)eA (3) 龙 integral (4) 假设以上整数规划有一可行解。 a.如果我们和(1)关联一乘子的向量口，拉格朗日问题L(μ)是什么？对于 所有的4L(u)≤x‘是否为真？说明拉格朗日乘子问题，令L表示拉格 朗日乘子问题的最优解。（看部分c)。 山.如果我们为单独的限制2)关联一标量1，拉格朗日间题L(1)是什么？对于 所有的A,L(入)≤名”是否为真？如果不是，为真的是什么？注意符号入。 说明拉格朗日乘子问题，另L:表示拉格朗日乘子问题的最优解。（请看部分 c)o C,令x”是通过松池限制(4)的到的LP松弛的最优解。我们能得出结论z”■L? 我们使得出结论z”=1:?证明在两种情况下的您的回答
部分 2 (25 分) 建模和变换 5. (10 分) 考虑在网络 G = (N,A)的通常最大流问题的简单变体，它中的弧上的流 有正的下界lij 以及正的上界uij 。不是从 s 到 t 发送最大的流量，在这中 的目标是从 s 到 t 发送最小单位的流，同时满足不是s和t的其他结点的下界 约束和守恒。解释通过最大流算法的两个应用如何解决这个问题。(提示: 首 先解释如何使用在网络G’中最大流算法的一个应用来判定原问题的可行流，其 中，G’和网络G密切相关。) 6. (15分, 每部分 5 分)。考虑受限于单侧约束的最小代价网络流问题。 假设以上整数规划有一可行解。 a. 如果我们和 (1) 关联一乘子的向量 μ，拉格朗日问题 L(μ)是什么? 对于 所有的μ L(μ) ≤ z* 是否为真? 说明拉格朗日乘子问题，令 L* 1 表示拉格 朗日乘子问题的最优解。 (看部分 c)。 b.如果我们为单独的限制(2)关联一标量λ ，拉格朗日问题L(λ)是什么？对于 所有的λ， L(λ) ≤ z* 是否为真？如果不是，为真的是什么？注意符号λ。 说明拉格朗日乘子问题，另L* 2 表示拉格朗日乘子问题的最优解。 (请看部分 c)。 c. 令 z’ 是通过松弛限制(4)的到的LP松弛的最优解。我们能得出结论z’ = L* 1? 我们能得出结论z’ = L* 2 ?证明在两种情况下的您的回答
部分3。(30分)解答. 7.(7分)假设在有■条烈和日个结点的网络G=N,)上的广义流问题，且有至 少一条圈是盈亏平衡国，更进一步假设有一可行解，首先描述盈亏平衡国是什么。 下一步描述基本结构是什么，在基F中有多少条弧。 &(8分)在全局最小割集算法中，我门通过求解一系列最小切割问题，它们的总运 行时间是和求解单独最大流问愿一样，米寻找有结点】在切割的5侧的最小切 割。假设第一最小切割问愿是寻找最小-2切割。其在(5，T)的T边有结点2。 解释第二切割问愿的网铬是否和第一切割题不同。如果这样，它们是如何不同 的？) 9.(15分，每部分5分)考虑最小代价流问题G=N,)有代价c和上界山，和侯 应/需求向量是b。令x*是最优流，令黑是结点势的最优集合，也就是(x*,月) 满足最优性条件。弧(i,j》称为向上临界的(upward critical),如果增加在 (,》的容量，却减少（也就是，严格改良）最优目标值一个单位， a.根据即约代价写出的最小代价流问题的最优性条件。 b说明如何通过判定在图G”中存在的和G(x)剩余网络密切相关的负代价国米 判定弧)是向上临界的。说明如何修改G(x)来获得G'。 C说明如何通过求解在相关的图G”上的最短路径问愿来判定弧是(，)向上 临界的。解释如何修改G(x)来获得G
部分 3。 (30 分) 解答。 7. (7分) 假设在有m条弧和 n 个结点的网络 G = (N, A)上的广义流问题，且有至 少一条圈是盈亏平衡圈。更进一步假设有一可行解。首先描述盈亏平衡圈是什么。 下一步描述基本结构是什么，在基 F 中有多少条弧。 8. (8 分)在全局最小割集算法中，我们通过求解一系列最小切割问题，它们的总运 行时间是和求解单独最大流问题一样，来寻找有结点 1 在切割的 S 侧的最小切 割。 假设第一最小切割问题是寻找最小1-2 切割, 其在（S,T）的T边有结点2。 解释第二切割问题的网络是否和第一切割问题不同。如果这样，它们是如何不同 的？) 9. (15分, 每部分 5 分) 考虑最小代价流问题 G = (N,A)有代价c 和上界u, 和供 应/需求向量是 b。令 x* 是最优流，令π 是结点势的最优集合，也就是(x*, π) 满足最优性条件。弧 (i,j) 称为向上临界的(upward critical)，如果增加在 (i,j)的容量, 却减少(也就是，严格改良)最优目标值一个单位， a. 根据即约代价写出的最小代价流问题的最优性条件。 b 说明如何通过判定在图G’ 中存在的和G(x) 剩余网络密切相关的负代价圈来 判定弧(i,j) 是向上临界的。说明如何修改 G(x) 来获得 G’。 C 说明如何通过求解在相关的图 G’’上的最短路径问题来判定弧是 (i,j) 向上 临界的。解释如何修改 G(x) 来获得G