15.082J/6.855J模拟考试 春季2003 考试结构 期末考试分成3部分 ·部分1.算法回顾问愿，(35分 ·部分2.建慎和变换。(30分) ·部分3.简答（可能稍微长点的回答），包括真假问题。(5分) 既燃有很大比例的真-假建模问题，考试也许产生比期中考试低的“原始分数”， 我们仍然计划以评分在曲线上，大概40%到50%的学生能得到A。 考试不覆盖期中考试覆盖的内容，除了在以后的主题中需要的材料。例如，最短路 径的最优性条件对理解最小代价流问题的最优性条件是必需的，且这是合理的。基 数堆期中考时后没有使用，不在期末考试中覆盖。 答题纸每个学生允许带四页答愿纸，只能在一边写或打字。 计算器在考试中不允许使用. 部分1.算法回顾问题。(35分)在这部分，我们将间5到7个阿题，要求你添出 各种问题的下一步或者下面一些步骤， 算法将从以下部分选取： ·最大流包括超额博整)慎流推进 ·整体最小切制 ·最小代价流的圈消除 ·连续最小路径和容量调整 ·网络单纯形 ·最小代价生成树算法 ·广义流间题的单纯形流算法 ·多品种流控格朗日松池算法 ·多品种流的列生成 为了学习这些，最好看动面，确保你能判断下一步。我们列亭的例子问题是有代表性的。 但是这些月题不打算穷层全部月恩， 1,在图XX(在真实考试中，我们提供图)考虑最大流问题的预流。如果实施()最高层的 预流推进，)超额调整下一个选择的结点是什么？ 2.考电在图XX中给出的全同最小切割预流月题。下一个选取的结点是什么？
15.082J/6.855J 模拟考试 春季 2003 考试结构 期末考试分成 3 部分 • 部分 1. 算法回顾问题。 (35分). • 部分 2. 建模和变换。(30分). • 部分 3. 简答 (可能稍微长点的回答)，包括真-假问题。(35 分) 既然有很大比例的 真-假 建模问题，考试也许产生比期中考试低的“原始分数”。 我们仍然计划以评分在曲线上，大概 40% 到 50% 的学生能得到A。 考试不覆盖期中考试覆盖的内容，除了在以后的主题中需要的材料。例如，最短路 径的最优性条件对理解最小代价流问题的最优性条件是必需的，且这是合理的。基 数堆期中考时后没有使用，不在期末考试中覆盖。 答题纸 每个学生允许带四页答题纸，只能在一边写或打字。 计算器 在考试中不允许使用。 部分 1. 算法回顾问题。(35 分). 在这部分，我们将问5 到 7 个问题，要求你添出 各种问题的下一步或者下面一些步骤。 算法将从以下部分选取： • 最大流(包括超额调整)预流推进 • 整体最小切割 • 最小代价流的圈消除 • 连续最小路径和容量调整 • 网络单纯形 • 最小代价生成树算法 • 广义流问题的单纯形流算法 • 多品种流拉格朗日松弛算法 • 多品种流的列生成 为了学习这些，最好看动画，确保你能判断下一步。我们列举的例子问题是有代表性的。 但是这些问题不打算穷尽全部问题。 1. 在图XX(在真实考试中，我们提供图)考虑最大流问题的预流。如果实施(a)最高层的 预流推进，(b)超额调整下一个选择的结点是什么？ 2. 考虑在图 XX 中给出的全局最小切割预流问题。下一个选取的结点是什么？
3.或者判定在图XX给出的当前最小代价流是最优的成者判定一个改善的解， 4.在图X父中是在最小代价流付题的容量调整算法的8博整后的流。在沿着最短路径 的第一次增广前的4调整阶段中的流是什么？ 5.在图XX中是最小代价流的基本结构。计算基本可行流，相美结点的势。进行恰好 一次主元变换。 6.在图XX中是最小生成树问题的部分解。下一个选择的弧是什么？间如果我门使 用Pim算法？()如果我们使用Kruskal算法？ 7.在图XX中是一广义流的基本可行结构。和此基相关的流是什么？结点势是 什么？ 8.在图XX中是多品种流问题，当前解以及通行费集。如果我们使用亚梯度优 化以及设置步长是5，下一集合的弧通行费是什么？ 9.在图XX中是多品种瓷问题的列集和通行费集。对商品1产生的下一列是什么？证 明你的同答。 部分2.建慎和变换30分) 21(10分，每个5分)考虑网路G=N,A)上的最小代价流问题。 Minimize EDEA Cu x可 subject to EG:GDeAXg -E6:GDeA)X=b(i) for alli N xisu for all (ij)EA a.说明如何把此最小代价逢问题转化为每条弧的下界都是0的等价问愿 b.假设下界都是0，至少一个供应是严格的正的。说明如何把这个最小代价流 问愿转化为恰好有一个正供应结点的等价问圈。 22(10分)一条航线有P航站，且希望用尽可能少的飞机服务：为了做此事，必须 判断最有效的绑定这些航站到航班调度方式。航班ⅰ的开始时向是妇，结束时 问是b,飞机从航班1的目的点返回到航班」的起始点需要「小时，把这公 式化为网路流问题。您应该清楚地说明如何从给出的数据构建网络，并证明你 的公式化正确地建模了问题。 23(10分，每部分5分)假设N个结点，每个分配K种顾色中的一种。为了方便 假设顾色标号为1,2，.，，K。令Ak)表示结点i的颜色是k的所有的弧
3. 或者判定在图 XX 给出的当前最小代价流是最优的或者判定一个改善的解。 4. 在图 XX 中是在最小代价流问题的容量调整算法的8-调整后的流。在沿着最短路径 的第一次增广前的4-调整阶段中的流是什么？ 5. 在图XX 中是最小代价流的基本结构。计算基本可行流，相关结点的势。进行恰好 一次主元变换。 6. 在图XX 中是最小生成树问题的部分解。下一个选择的弧是什么？ (i) 如果我们使 用Prim 算法? (ii) 如果我们使用 Kruskal 算法? 7. 在图 XX 中是一广义流的基本可行结构。和此基相关的流是什么？结点势是 什么？ 8. 在图 XX 中是多品种流问题，当前解以及通行费集。如果我们使用亚梯度优 化以及设置步长是 .5 ，下一集合的弧通行费是什么？ 9. 在图 XX 中是多品种流问题的列集和通行费集。对商品1产生的下一列是什么？证 明你的回答。 部分 2. 建模和变换(30 分). 2.1 (10分, 每个5 分) 考虑网络G = (N，A)上的最小代价流问题。 a. 说明如何把此最小代价流问题转化为每条弧的下界都是 0 的等价问题。 b. 假设下界都是 0，至少一个供应是严格的正的。说明如何把这个最小代价流 问题转化为恰好有一个正供应结点的等价问题。 2.2 (10分) 一条航线有 p 航站，且希望用尽可能少的飞机服务。为了做此事，必须 判断最有效的绑定这些航站到航班调度方式。航班 i 的开始时间是a i ，结束时 间是b i 。飞机从航班 i 的目的点返回到航班 j 的起始点需要 r ij 小时。把这公 式化为网络流问题。您应该清楚地说明如何从给出的数据构建网络，并证明你 的公式化正确地建模了问题。 2.3 (10 分, 每部分 5 分). 假设N个结点，每个分配 K 种颜色中的一种。为了方便 假设颜色标号为 1, 2, . . ., K。 令 A(k) 表示结点 i 的颜色是 k的所有的弧
():因此A(k)表示所有从颜色为k的结点发出的弧 考虑以下不同的最小代价圈问题： Minimize E4eACy到 (8a subject to E6:在eA两-E50eA)=07ieN (86) 2aeA列三1 (8e) xa is 0 or 1 for all (ij)eA. (8d a.公式化通过()松弛b(问松弛8e获得的拉格朗日松跑。在情况()中令口 代表拉格朗日乘子集合。在情况（中令表示拉格朗日乘子集， b.如何部分比较（①和（面）的拉格朗日乘子何题的最优解和通过抛弃8d中的整数 约束的LP边界？简要证明你的回答。 Pt3.短和可能长的回答，包括真假问题。(35分) 31.真/假问愿(20分，每个5分)对于如下的每个句愿：判定是否为真成假。对于 为真的问题，请给出简单证明。对于假的问愿。请提供反例成给出简短描述说 明为什么为假。 a假设T是网络G=(N,A)的最小生成树.令：(k)是有代价恰好等于k的 T幸的弧的数目。假设T是另一个和G相关的最小代价生成树，令(k)是 代价恰好等于K的T*的页的个数。那么对于所有的k(k)=k) b.令i是在网络中的结点，令m是和结点ⅰ关联的弧的数日。假设我们运 行预流推进算法。那么对于任何一般预流推进算法的实现，从结点：开始的 饱和推进数Onm)· C.假设x·是网络G=N,A)的最小代价流.假设x*也是生成树结构(T,LU) 的生成树解。令π是单纯形乘子的向量，那么它必须是满足最优性条件的即 约代价，（注释：这不是不重要的陈习，因为我们没有优先程设x·满足最优 化条件，我们只是假设x·有最小代价) d如果算法运行在Om)时问内，它也运行在m)时问内，不论是否n<m 32.简答题(5分) 我们演示了势函数增广，它说顶流推进算法的非饱和推进的数目是Om)。简单 国顾增广，包括解释在势函数中的边界的改变能证明关于运行时间的上界。 33最小代价流的灵敏度(10分，每个S分)
(i,j) ；因此 A(k) 表示所有从颜色为 k 的结点发出的弧。 考虑以下不同的最小代价圈问题： a. 公式化通过(i) 松弛 8b (ii) 松弛8c 获得的拉格朗日松弛。在情况(i)中令 μ 代表拉格朗日乘子集合。在情况 (ii) 中令λ 表示拉格朗日乘子集。 b. 如何部分比较(i) 和 (ii)的拉格朗日乘子问题的最优解和通过抛弃8d中的整数 约束的LP边界？ 简要证明你的回答。 Part 3. 短和可能长的回答，包括真假问题。 (35 分) 3.1. 真/假问题. (20 分, 每个5 分). 对于如下的每个问题：判定是否为真或假。对于 为真的问题，请给出简单证明。对于假的问题，请提供反例或给出简短描述说 明为什么为假。 a. 假设 T*是 网络 G = (N,A) 的最小生成树。令t f*(k) 是有代价恰好等于 k 的 T* 的弧的数目。假设 T’ 是另一个和G相关的最小代价生成树，令 f’(k) 是 代价恰好等于 K 的T* 的弧的个数。那么对于所有的k f*(k) = f’(k) . b. 令 i 是在网络中的结点，令 m i 是和结点 i 关联的弧的数目。假设我们运 行预流推进算法。那么对于任何一般预流推进算法的实现，从结点 i 开始的 饱和推进数是O(nmi ) 。 c. 假设 x* 是网络 G = (N,A)的最小代价流, 假设 x* 也是生成树结构 (T, L, U) 的生成树解。令π 是单纯形乘子的向量，那么它必须是满足最优性条件的即 约代价。 (注释: 这不是不重要的练习，因为我们没有优先假设x* 满足最优 化条件。我们只是假设 x* 有最小代价) d. 如果算法运行在O(nm)时间内，它也运行在 O(m 2 ) 时间内，不论是否 n < m. 3.2. 简答题(5 分) 我们演示了势函数增广，它说预流推进算法的非饱和推进的数目是O(n 2 m)。简单 回顾增广，包括解释在势函数中的边界的改变能证明关于运行时间的上界。 3.3 最小代价流的灵敏度(10 分, 每个 5 分)
假设一最小代价流问愿被最优化地解决了，且最优解是x·。更进一步假设最优 结点势集合是。和网络流问愿相关的代价是©，且容量的向量是u。 a假设页（仔，）的容量从“，变为“，+1。说明通过求解单最短路径问题如何 找到变换问愿的最佳流和最佳结点势集。清楚地说明最短路径问题，以及如 何修改流和结点势会导致最短路径问愿的最优解。 b假设在a部分没有变化.而(5,9)的代价从©，变为Cw··说明通过求解单独 最大流间恩，如何找到变换间题的最优流和最优结点势集合。清楚说明最大 流问避，以及如何修改流和结点势会导致最大流问题的最优解
假设一最小代价流问题被最优化地解决了，且最优解是 x*。更进一步假设最优 结点势集合是 π。 和网络流问题相关的代价是 c, 且容量的向量是u。 a. 假设弧 (3, 7) 的容量从 u 37 变为 u 37 + 1。说明通过求解单最短路径问题如何 找到变换问题的最佳流和最佳结点势集。清楚地说明最短路径问题，以及如 何修改流和结点势会导致最短路径问题的最优解。 b. 假设在 a 部分没有变化。而(5,9)的代价从c 59 变为 c 59 + 1。说明通过求解单独 最大流问题，如何找到变换问题的最优流和最优结点势集合。清楚说明最大 流问题，以及如何修改流和结点势会导致最大流问题的最优解