运筹学图与网络分析PPT幻灯片

第1，5章图论和网络分析，图表的基本概念，网络分析，最小支持树问题最短路径问题网络最大流问题，第2，图论起源：戈涅斯堡7条腿问题，问题：走路的人可以从哪条土地上走7条腿，每条腿只能走一次，最后回到起点吗，结论：与每个节点连接的边数是偶数，3，1图的基本概念，由点和边组成，记录为G=(V，e)。其中V=(v1，v2，VN)是节点的集合，E=(e1，E2，em)是边的集合。点表示研究对象，方面表示研究对象之间的特定关系。1.图，p114，4，图，无向图，G=(V，e)，有向图，D=(V，a)，示例1:哥尼堡桥问题的图是无向图。带有直接示意图的边称为圆弧。2，图形的分类，5，示例，图1，6，图2，7，3，链和道路，圆和循环，链，点边交错的序列，道路，点弧交错的序列，循环，起点=终点道路，例如：10，G2是G1的子图形。例如，11，6、授权图表(网络)、图形的每个角都有表示特定实际含义的权重，称为授权图表。记录为D=(V，a，c)。示例：12，2最小支持树问题，此部分的主要内容为：树，支持树，最小支持树，13，树：无圆连接图，t。首先，树的概念和属性，树的属性：(1)树的两点之间只有一条链。(2)从树中移除一侧，使其无法连接。因此，树保持图形连接，具有最小边数的一种图形(3)在树中不相邻的两点之间添加一条边。(4)如果树t有m个顶点，则t有m-1个边。14，图G=(V，E)的支撑子地物T=(V，E)构成树时，T也称为G的支撑树或生成树。第二，图支撑，是，15，是某处新建5个住宅，将修复道路连接5，调查后道路可以铺成图。问5个居民点都要铺多少条路，以便连接道路。解决：此问题实际上需要为图中的支撑树问题铺设共4条道路。使用图中的支持树应用示例，16，破圆方法查找下图中的生成树之一。17、最小支持树：查找网络的支持树并设置其权重和最小值。第三，最小支持树问题，算法1(破圆法):在给定权重的连接图中查找圆；从发现的圆中删除权重最大的边之一(如果两个或更多的边是权重最大的边，则随机删除其中一个):如果剩下的图不包含圆，则计算结束，剩下的图是最小支撑。否则，回到。18，示例以上示例中的最小支持树，解决方案：5，5.5，v1，v2，v3，v4，V5，20，最小生成树示例：6个城市之间的道路网络必须沿已知长度的道路连接6个城市的电话线路网络，以便总电话线路长度最短，如下所示：21，v1，v2，v3，v4，V5，1，4，2，3，1，3，5，2，设计一条最经济的燃气管道，并要求所需的总成本。23，练习现在有加油站a，向一个小区供应煤气，居民区的每个用户所在的地方，如图所示，各用户所在的地方铺设煤气管道所需的费用(单位：万韩元)在图中。设计一条最经济的燃气管道，并要求所需的总成本。24，例现在有加油站a，向一个小区供应煤气，居民区各用户所在的地方如图所示，各用户所在的地方铺设煤气管道所需的费用(单位：万韩元)显示在图边缘的数字上。设计一条最经济的燃气管道，并要求所需的总成本。25、例现在有加油站a，向一个小区供应煤气，居民区各用户所在的地方如图所示，各用户地点铺设煤气管道所需的费用(单位：万韩元)显示在图边缘的数字中。设计一条最经济的燃气管道，并要求所需的总成本。26、例现在有加油站a，向一个小区供应煤气，居民区每个用户所在的地方如图所示，放置每个用户地点的煤气管道所需的费用(单位：万韩元)显示在图前的数字中。设计一条最经济的燃气管道，并要求所需的总成本。27、例现在有加油站a，向一个小区供应煤气，居民区每个用户所在的地方如图所示，放置每个用户地点的煤气管道所需的费用(单位：万韩元)显示在图前的数字中。设计一条最经济的燃气管道，并要求所需的总成本。28、例现在有加油站a，向一个小区供应煤气，居民区每个用户所在的地方，如图所示，放置每个用户地点的煤气管道所需的费用(单位：万韩元)显示在图边缘的数字中。设计一条最经济的燃气管道，并要求所需的总成本。该路径是最经济的天然气管道路径，所需的总成本为25万元，29，3最短路径问题，最短路径问题是在一个网络(授权图)上找到从起点到节点之间的最短路径。/需要从1到/6的最短路径。30，基本思路：从起点vs开始，逐步指定每个节点的VJ标签dj，vi。其中DJ是起点vs到VJ的最短距离，VI是该最短路径上的上一个节点。在端点vt上显示dt，vi时，从v1到vt的最短路径可以反向跟踪该段落长度到dt，最短路径可以相对于标签vi进行反向跟踪，最短路径可以相对于标签VI进行反向跟踪Dijstra解决方案(磁盘类)，31，0，v1，(1)考虑起始v1标签0，v1、0，v1、1，v1、(3) VI和VJ。其中，选择VI-va，VJ-VB以选择起始v1和最短距离(mindi cij)的VJ，标记VJ，(4)到结束VN标记中的编号dn，VI(2)，(1)起始v1标签0，v1，3，v1，34，0，v1，1，v1，3，v1 标记为V5的12表示V1vn的最短距离，反向跟踪的最短路径，39，0，v1，1，v1，3，v1，5，v3，6 ，41，主要线路：1 . v1-v2-v4-V6-v282 . v1-v2-v4-V7-V8最短段落长度：12，42，教室练习无向图方案在网络中位于v1-v4-v4-V7-V8，43，课堂练习无向图方案，v1，v2，v3，v4，购买设备需要每年支付购买费用。如果继续使用旧设备，则必须支付维修和操作费用。如表所示，在计划期间(5年)内的年购买费、保管费和运营费，工厂应在未来5年制定设备更新计划，并询问哪些方案可以将包括购买费、保管费和运营费在内的总费用降至最低。46，应用段落模型设备更新问题，分析：节点：V=v1，v6，VI表示I年初；圆弧：A=(vi，vj)表示在I秒购买并在j年初使用。I=1，5；J=2，6，加权cij: I年初至j年初成本，即cij=i年初采购成本(j-i)年度内的保管费用，渠道：表示一个更新策略。例如，v1-v2-v6表示第二年更新用于购买第一年，47，应用短路模型设备更新问题，0，v1，16，v1， 保管费用和运营费用，练习：设备更新问题，50，28，v1，v2，v3，v4，V5 弧未连接的点之间假定存在权限为的弧连接。从V1到vj的最短路径是从v1开始，沿此路径沿特定点vi和圆弧(VI，VJ)到VJ。从V1到VI的这条路也只能是从v1到VI的所有路中最短路的。V1到VJ的最短路长度为P1j，v1到VI的最短路长度为P1i，方程式如下：(2) Ford方法(连续逼近法) (可以使用负值)，52，起始处v1到VJ的直接距离的初始解决方案。从第二步开始使用递归公式：找到，在执行步骤t时，如果出现，则为从v1到每个点的最短路径。停止计算，53，示例：使用递归公式，55，从第二步开始使用递归公式，56，这样，从vs到VJ的最短路径是(vs、VI，vk，VJ)，d (v1，V8)=6，d(v1，v6) w68=(-1) 7记录v6为d(v1，v3) w36，59，4网络最大流量问题，引用：下图为V1到V6的交通网络，权限表示该运输线的最大通过能力，制定了使V1到V6的运输产品数量最多的方案。60，已知网络D=(V，a，C)，其中V是顶点集，a是圆弧集，C=cij是容量集，cij是圆弧(VI，VJ)上的容量。现在，d必须通过流f=fij。其中fij是圆弧(VI，VJ)的流速。问题：如何放置流fij以最大化从d通过的总流v？1，一般公式法，61，2，最大流问题的数学模型，maxv=v(f)，容量约束，平衡约束，P125，满足上述所有约束的流成为可执行流。62，(1)容量条件：每个圆弧(vi，VJ)A具有0fijcij。(2)平衡条件：取货点对、取货点vt、中间点、可实现流f的流(取货点净输出或取货点净输入)，1，满足以下条件的流f为可执行流，第三，基本概念和清理，63，可执行流特性：(1)(2)每个中间点流入和流出的代数和0。(转运角色)(3)始发点的总流出和收款点的总流入必须相同。任何网络上的可执行流始终存在。例如，零流v(f)=0是符合上述条件的可行流。网络系统中最大的流问题是查找给定网络中达到最大流v(f)的可执行流f。64，在可行流中，fij=cij的弧称为饱和弧。Fij 0弧称为非零流弧。Fij=0的圆弧称为零流圆弧。2，饱和弧和零流弧，65，f生成可执行流，u生成从vs到vt的链，u=正向弧，u-=反向弧。如果u中间弧未满，u中间弧不是0，则u称为f的延伸链。3，扩展链，66，扩展链，显然图中至少有一个扩展链，67，扩展链，68，容量网络D=(V，a，c)v除以两个非空集合，所有起点都属于V1，端点是圆弧的集合，称为分离的vs和vt中的截面。4、切口集和切口集中的切口是连