上海交大运筹学期末考试考研复习珍贵PPT资料(适合全国高校考研和期末8464375899.ppt

此时，有 又作 第*页 由前面的逐次逼近算法得最短路为 第*页 上用最大流算法进行流的调整 在网络G中相应的增广链 第*页 此时，有 第*页 调整。 第*页 第四次标号。 第*页 调整 第*页 第五次标号。 第*页 标号过程已无法再继续。流量为1的画彩线。 第*页 工人 分别作 故最多安排四个人工作。 第*页 应用2：货物运输问题 例：现有5批货物，每批只需一条船装 运，要由 ， 所在地域运往 ， ， 地域。至于货物 从 ， 运向 ， ， 三点何处都一样，每批货物出 发日期如表1，船航行所需天数如表2。船只空载和 重载时航行时间相同。要求制定一个计划，在半个月内用 最少的船只把5批货物运过去。 地点 5 10 / / 12 1，8 地点 2 3 2 1 1 2 表1（出发日期） 表2（航行天数） 第*页 解：设 ， 分别表示每项运输任务的出发日期及 完成日期（i=1，2，3，4，5）则由表1和表2 知： 任务 路线 ① 5 7 ② 10 13 ③ 12 13 ④ 1 3 ⑤ 8 10 第*页 任务 路线 ① 5 7 ② 10 13 ③ 12 13 ④ 1 3 ⑤ 8 10 要想用较少的船只在1～15天内完成任务，关键是自上一任 务到达的时间加上返回的时间能否赶上下一个任务出发的 时间。若能，则一只船就能完成两批货物的运输任务。 以下试运行： 第*页 任务 路线 ① 5 7 ② 10 13 ③ 12 13 ④ 1 3 ⑤ 8 10 ①5号 ①7号 8号回 ⑤10号 地点 2 3 2 1 1 2 表2（航行天数） ⑤8号 12号回 ③13号 ③14号回 第*页 任务 路线 ① 5 7 ② 10 13 ③ 12 13 ④ 1 3 ⑤ 8 10 ②10号 ④3号 地点 2 3 2 1 1 2 表2（航行天数） ④1号 ②13号 ④5号回 共两只船在13号以前就把5批货物全部运了出去。 是否最优？一只船可行否？如何解决？ 第*页 作一个二部图，点集｛X｝和｛Y｝都表示这5项任务，两 点间有连线的条件是第i件任务完成后可赶上作第j件任务。 有连线即有匹配，连线越多（匹配数越大）一只船重复使 用次数多，使用船只数就越少。最大的匹配就是用最少的 船。 任务 路线 ① 5 7 ② 10 13 ③ 12 13 ④ 1 3 ⑤ 8 10 第*页 任务 路线 ① 5 7 ② 10 13 ③ 12 13 ④ 1 3 ⑤ 8 10 地点 2 3 2 1 1 2 表8-6（航行天数） 此时的m1-5,n1-5分别表示任务1－5。 第*页 此表示共两只船可完成任务： Ⅰ：④→①→② Ⅱ：⑤→③ 第*页 例：某河流中有几个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图，在一次敌对的军事行动中，问至少应炸断几座桥，才能完全切断两岸的交通。 第*页 第*页 例：（匹配问题）有三根相同的轴（编号为1，2，3），又有三个相同的齿轮（编号为4，5，6），由于精度不高，不能做到任意匹配。据图纸工艺要求，已知轴1能和齿轮4，5配合，轴2能和齿轮5，6配合，轴3能和齿轮4，5配合。要求合理选择装配方案，以得到轴与齿轮的最大匹配数。 第*页 第*页 最小费用流 第*页 在一个关于流的网络中，人们不仅需要流达到一定的数量，（甚至达到最大，即最大流）而且每一个流量要有一定的费用，流所走的路线不一样，单位费用不一样。同样数量的流量，可能走的路线不一样，总的费用不一样。从而在限定网络流的基础上，让流沿那些边走，能使总的费用最小（这里的最小费用问题又看成最短路问题）。 特别的，当最大流不惟一时，在所有最大流中求一个流f,使 总费用最低。 第*页 问 题 第*页 对偶算法的算法思想 从零流 开始，以费用作为边的长度，构造出一个长度网络，对此长度网络，用求最短路的方法，求出费用最小的可增广链，在找到的增广链上调整流量，使其流量逐步达到要求的数量。 第*页 相关定义 定义：（链的费用）已知网络 f是G上的一个可行流， 可增广链， 称为链 的费用。 定义：（流的总费用） 第*页 相关定理 定理：若f是流量为 的最小费用流， 则 得到新可行流 一定是 流量为 的可行流中的最小费用流。 的一条最小费用可增广链， 第*页 定义：（长度网络）对网络 有可行流f，保持原网络各点，按以下规则定义网络： 这样得到的一个网络称为长度网络。记为L(f) 第*页 对偶算法的步骤 （1）取0流为初始可行流 （2）若有 流量为 构造长度网络 （3）在长度网络 中求从 若不存在最短路，则 已为最大流，不存在流量 为v的流，停止；否则转（4）； （4）在G中与这条最短路相应的可增广链