数学建模组合优化模型.ppt

组 合 优 化 问 题 建 模 马建华 2011年7月 优化问题建模 优化问题概述 数学规划模型 组合优化模型 优化算法介绍 评价方法 组合优化建模 组合优化问题概述 网络优化设计 流量安排问题 路线选择问题 组合优化问题概述 组合优化问题 常见的组合优化问题 组合优化问题建模方法 组合优化问题 有限个可行方案中选择最优方案 最优解一定存在 可行方案的个数非常多，枚举法不可行，往往是NP-hard问题 组合优化问题 组合计数问题 最小费用最大流问题 最短路问题 网络设计问题 最优匹配问题 装箱问题 旅游售货员问题 车辆路径问题 组合优化问题建模方法 数学规划方法 图与网络优化方法 组合优化算法 图的基本概念 图与子图 图的连通性 图的计算机表示 无向图的基本概念 无向图G：一个有序二元组(N,E),记为G=(N,E) G的点集合： N=（1，2，3，4）是一个无向图 的点的集合 G的边集合：E={eij}且eij={ni,nj}为 无序二元组称ni和nj为eij的端点，且称eij 连接点 ni和nj 点边关系 关联：一条边的端点称为这条边的关联点，顶点1与边a和b 邻接：与同一条边关联的端点称为是邻接的，如点1和2，同时如果两条边有一个公共端点，则称这两条边是邻接的，如边a和b。 完全图：每一对点之间均有一条边相连的图 二分图 G=(N,E)：存在的一个二分划(S,T)，使得G的每条边有一个端点在S中，另一个端点在T中 完全二分图 G=(S,T,E)：S中的每个点与T中的每个点都相连的简单二分图 简单图G的补图 :与G有相同顶点集合的简单图，且 中的两个点相邻当且仅当它们在G中不相邻 有向图与网络 关联矩阵 关联矩阵示例 邻接矩阵 邻接矩阵示例 子图 Scilab中输入图 命令： g = make_graph(name,directed,n,tail,head) 其中： name：图的名称，字符串‘graph1’ directes：有向无向，0-无向图，1-有向图 n：顶点个数 tail向量，各边的尾部 head向量，各边的头部 例子 常用函数 g1 = add_edge(i,j,g) //加边 g1 = add_node(g,[xy,name])//加点 g1 = delete_arcs(ij,g)//删除边 g1 = delete_nodes(v,g)//删除点 ma = edge_number(g) //边数 g2 = graph_union(g,g1) //图的并 g1 = line_graph(g)//反图 n = node_number(g)//点数 关联矩阵和邻接矩阵 a = graph_2_mat(g,mat) 其中g : 图 mat : 字符串, node-arc or node-node a :点边关联矩阵或点点邻接矩阵 g = mat_2_graph(a,directed,[mat]) 其中 a : 点边关联矩阵或点点邻接矩阵 directed : integer, 0 (无向) or 1 (有向) mat : 字符串, node-arc or node-node g : graph list 图的性 ?图的连通 无向图 有向图 图的割集 ? 概 念 主要结论 无向图的路 连通性 点i和j点是连通的：G中存在一条（i，j）路 G是连通的：G中任意两点都是连通的 连通分支：G的极大连通子图 有向路 点i和点j是强连通的：G中存在一条(i,j)有向路，也存在一条(j,i)有向路 G是强连通的：G中任意两点都是强连通的 G的强连通分支：G的极大连通子图 p = find_path(i,j,g) 割 集 网络设计 常见网络设计 管线网络、交通网络、通信网络、关系网络等 设计内容 设置多少点？设在什么地方？--选址问题 点之间如何链接？--网路优化 设计要求 实现基本功能 成本最小 网络设计实例-交巡警平台网络 交巡警平台的个数 交巡警平台的位置 交巡警平台与路口的连接关系 网络设计—供应链网络设计 供应链节点企业的数量 关键物流设施的位置 物流配送任务分配 网络设计实例—水管网络设计 考虑某县富春乡自来水村村通工程，自来水管已经铺设到乡驻地，下图是各村之间铺设管道需要的长度，请给出管网设计方案。 可行方案 支撑树 连通—水要送达每个村庄 不含回路—总长度最小 最优方案 最小支撑树-边长度之和最小的支撑树 最小支撑