运筹学_暑期培训课件.ppt

图论模型 灾情巡视路线 问题分析 题目给出了某县的公路网络图，要求在不同条件下设计出最优的灾情巡视路线。将每个乡(镇)或村看作一个图的顶点，各乡镇、村之间的公路看作对应顶点的边，各条公路的长度(或行驶时间)看作对应边上的权，使得公路网络图转化为加权网络图，问题转化为图论中的分组旅行员推销问题(TSP)，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次后又回到点O，使得总权最小。 由于图中各点之间的连接关系比较复杂，显然，在巡视过程中，有些路线是不需要经过的。因此，考虑对图中的连接关系进行简化，对于任何一个点，都要考虑从县政府出发，能够经过尽可能短的路线到达该点。 图中数据较多，如果考虑用计算机处理，首先需要解决以下问题： （1）图在计算机中是如何存储的？ （2）如何化简所给图？ （3）如何给出巡视路线？ 返回 图的计算机表示： 一般情况下，当利用计算机处理图的问题时，通常将 图的拓扑结构利用关联矩阵或邻接矩阵来表示。 关联矩阵 邻接矩阵 图论常用问题及算法 一、最短线路问题 两个指定顶点之间的最短路径-----Dijkstra算法 若从v1到某个顶点vi的最短路是 {v1,v2,…,vi-1,vi},则{v1,v2,…,vi-1,vi}必然是vi到vi-1的最短路，所以要求v1过vi-1到vi的最短路，必须先求出v1到vi-1的最短通路.如果用L1,k表示vi到vk点的最短通路的长，则 　　　 L1,k=min{L1,k-1+wk-1,k} 例　 v1,v2,…,v8,v9九个城市间的公路网如图所示，假定有一批货物需要用卡车由v1分别运到v9 ，问各走哪条路最短？ ｖ１ ｖ２ ｖ３ ｖ４ ｖ５ ｖ６ ｖ７ ｖ８ ｖ９ １ ２ ３ ３ ４ ２ ３ ３ ４ ５ ２ ３ ３ 2.5 ３ ｖ１ ｖ２ ｖ３ ｖ４ ｖ５ ｖ６ ｖ７ ｖ８ ｖ９ １ ２ ３ ３ ４ ２ ３ ３ ４ ５ ２ ３ ３ 2.5 ３ （0） 3 4 重复（２）中的步骤，直到图上全部没有T标号为止。 任意顶点之间的最短路径-----Floyd算法 二、最小树 最小树 三、最大流问题 如果把有向网络看作一个交通网，其中点表示车站，弧表示道路，则弧权就表示两个车站间道路的通过能力。于是，给定一个有向网络，需求指定两点间的最大流量，即最大流问题。 * 优化与网络模型 优化方法 图论 什么是最优化？ 决策变量 目标函数 约束条件 优化问题是工程技术、经济管理、科学研究等领域最常遇到的一类问题。它研究在有限或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。 达到最优目标的方案，称为最优方案，有哪些信誉好的足球投注网站最优方案的方法，称为最优化方法。建立的寻求最优的数学表达式，称为最优化模型。 一、优化问题的基本形式及分类 形式： 分类： （1）约束优化和无约束优化； （2）线性规划、非线性规划、二次规划等。 解法： 枚举法，有哪些信誉好的足球投注网站法，启发式算法。 二、线性规划及求解 标准型： 其它形式化为标准型的方法： 解法：单纯形法，对偶单纯形法，两阶段法等。 Matlab中的标准型： 或 求解命令： x=linprog(c,A,b) %返回的值x就是优化问题的最优解。 化标准型的方法： 目标函数：max--------min 只需令： 则目标变为： 约束条件： ： 不等式两端同乘-1 “=”: 利用两个不同方向的不等式约束代替 变量范围约束：每一个变量的范围约束看作独立的 约束条件 例： s.t. 标准型： 从而 x=linprog(c,A,b) 执行命令： 其它命令： [x,fval]=linprog(c,A,b,Aeq,beq,LB,UB) 说明：该命令可将不等式约束与等式约束以及变量 的范围限制分别输入。 A , b: 不等式约束的系数矩阵和右端项； Aeq , beq：等式约束的系数矩阵和右端项； LB , UB：变量的范围限制； x , fval：分别返回最优解和最优值。 注意：linprog()还有其它形式的用法，具体可在Matlab 指 令窗运行 help linprog ，就能看到所有的函数调用形式 。 例： 利用上述方法处理后，可令 ， ， 执行命令： [x,fval]=linprog(c,A,b,Aeq,beq,LB,UB) 三、整数规划及求解 规划中的变量（部分或全