求最小生成树已有成熟的算法.ppt

运输问题与分派问题 是图论（二分图）问题，有图论方面的算法。 也可以用数学规划解决，比如05年B题： 最短路径问题 例：求以下带权图从V0到V6最短路径。 求最短路已有成熟的算法：迪杰斯特拉（Dijkstra）算法。具体可见数据结构或者图论方面的参考书。 数学规划方法，用Lingo解决： 最大流问题 例：求以下带权有向图从V1到V4的最大流。 求最大流已有成熟的算法：标号法 （ Ford-Fulkerson算法）。具体可见图论方面的参考书。 数学规划方法，用Lingo解决： 最小生成树问题 例：求以下带权图的最小生成树。 求最小生成树已有成熟的算法：prim算法和Kruskal算法。具体可见图论方面的参考书。 数学规划方法，用Lingo解决： 旅行商(TSP)问题 一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？ 旅行商问题图论中没有成熟的算法，有改良圈算法，但几乎不能找到最优解。 数学规划方法，用Lingo解决： 关键路径问题 如下图，某个项目由4个作业（边）完成，每项作业需要一定时间（边的权值）完成，并且每项作业都需要在一定的状态（顶点）下才能开始，即要完成所有先行作业（所有进入该顶点的边）。求完成这个项目的最短时间。 无回路有向赋权图中的最长路径：关键路径。 关键路径问题图论中已有成熟的算法，具体可见数据结构或者图论方面的参考书。 数学规划方法，用Lingo解决： 为了得到每个作业的最早开工时间和最迟开工时间，可更改模型如下： 图论其他问题 图的遍历：深度优先，广度有限 平面图,着色问题 二分图 树：二叉树，二叉树遍历，编码，表达式 作业排序问题 （题目在书134页，代码在lingo教程.doc）有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最早何时能离开公司? 记tij为第i名同学参加第j阶段面试需要的时间（已知），令xij表示第i名同学参加第j阶段面试的开始时刻（早上8点为0时刻）： 实验 见实验指导。 * * 邻接矩阵M 权值表示两点之间的长度 起点多一条边出去 终点多一条边进入 其他点进入的边数等于出去的边数 权值表示两点之间的流量限制 1 4 2 3 12 13 7 100 8 5 除去源点和汇点的流量等于网络总流量之外，其他点所有流入的流量和流出的流量相等。 1 4 2 3 12 13 7 100 8 5 根至少有一条边连接到其他点 除根外,每个点只有一条边进入 每个点只有一条边出去 每个点只有一条边进入 除起点和终点外，不构成回路。 lingo教程.doc 只能在有哈密顿回路的情况下。 1 4 2 3 12 13 7 100 设xi是作业i的开始时间。 目标：最后一个作业的开始时间最小。 1 4 2 3 12 13 7 100 全部作业的开始时间最小 当sij0时，说明对应的作业的开始时间可以推迟sij，从而得到每个作业i的最迟开工时间。 关键路径还可以看成最长路，用求最短路径的方法来求解。 1 4 2 3 12 13 7 100 ? 秘书初试 主管复试 经理面试 同学甲 13 15 20 同学乙 10 20 18 同学丙 20 16 10 同学丁 8 10 15 目标：最后一阶段的最迟面试结束时间最小。 每人只有参加完前一阶段的面试后才能进入下一阶段： 每个阶段j同一时间只能面试1名同学：用0-1变量yik表示第k名同学是否排在第i名同学前面：