资源描述
组组 合合 优优 化化 问问 题题 建建 模模马建华年7月第1页优化问题建模v优化问题概述v数学规划模型v组合优化模型v优化算法介绍v评价方法第2页组合优化建模v组合优化问题概述v网络优化设计v流量安排问题v路线选择问题第3页组合优化问题概述v组合优化问题v常见组合优化问题v组合优化问题建模方法第4页组合优化问题v有限个可行方案中选择最优方案v最优解一定存在v可行方案个数非常多，枚举法不可行，往往是NP-hard问题第5页组合优化问题v组累计数问题v最小费用最大流问题v最短路问题v网络设计问题v最优匹配问题v装箱问题v旅游售货员问题v车辆路径问题第6页组合优化问题建模方法v数学规划方法v图与网络优化方法v组合优化算法第7页图基本概念v图与子图v图连通性v图计算机表示第8页无向图基本概念无向图无向图G：一个有序二元组(N,E),记为G=(N,E)G点集合：点集合：N=（1，2，3，4）是一个无向图点集合G边边集集合合：E=eij且eij=ni,nj为无序二元组称ni和nj为eij端点，且称eij 连接点 ni和nj 3412abcde第9页点边关系关联关联：一条边端点称为这条边关联点，顶点1与边a和b邻邻接接：与同一条边关联端点称为是邻接，如点1和2，同时假如两条边有一个公共端点，则称这两条边是邻接，如边a和b。3412abcde第10页完全图完全图：每一对点之间都有一条边相连图二二分分图图 G=(N,E)：存在一个二分划(S,T)，使得G每条边有一个端点在S中，另一个端点在T中完全二分图完全二分图 G=(S,T,E)：S中每个点与T中每个点都相连简单二分图简单图简单图G G补图补图:与G有相同顶点集合简单图，且 中两个点相邻当且仅当它们在G中不相邻返回完全图完全二分图补图第11页有向图与网络有向图有向图G：一个有序二员组(N,A)，记为G=(N,A)G G弧集合弧集合：A=aij且aij=ni,nj为有序二元组，若aij=ni,nj，则称aij从ni连向nj，ni称为aij尾，nj为 aij头，ni称为nj先辈，nj称为 ni后继有向图有向图G G基本图基本图：对于G每条弧用一条边代替后得到无向图网络网络G G：对（有向）图G每条边（弧）都赋予一个实数，并称为边（弧）权，则连同它边（弧）上权称为（有向）网络第12页关联矩阵第13页关联矩阵示例134521342返回第14页邻接矩阵第15页邻接矩阵示例返回134521342第16页子图第17页Scilab中输入图v命令：g=make_graph(name,directed,n,tail,head)其中：name：图名称，字符串graph1directes：有向无向，0-无向图，1-有向图n：顶点个数tail向量，各边尾部head向量，各边头部第18页例子123456abcdefghi a b c d e f g h i 1 2 1 1 3 3 4 4 52 5 4 3 4 6 5 6 6边尾点头点第19页第20页第21页第22页惯用函数vg1=add_edge(i,j,g)/加边vg1=add_node(g,xy,name)/加点vg1=delete_arcs(ij,g)/删除边vg1=delete_nodes(v,g)/删除点vma=edge_number(g)/边数vg2=graph_union(g,g1)/图并vg1=line_graph(g)/反图vn=node_number(g)/点数第23页关联矩阵和邻接矩阵va=graph_2_mat(g,mat)v其中g:图vmat:字符串,node-arcornode-nodeva:点边关联矩阵或点点邻接矩阵第24页第25页第26页vg=mat_2_graph(a,directed,mat)v其中a:点边关联矩阵或点点邻接矩阵vdirected:integer,0(无向)or1(有向)vmat:字符串,node-arcornode-nodevg:graphlist第27页图性图性v图连通图连通 无向图无向图 有向图有向图v 图割集图割集 概概 念念 主要结论主要结论第28页无向图路135426图图G G中路中路：一个点和边交替序列(ni,eij,nj,nk,ekl,nl)，简单路简单路：边不重路 初级路初级路：点不重路 回路：回路：在G中，一条最少包含一个边而且ni=nl ni,nl路简单回路：简单回路：边不重回路初级回路初级回路：点不重回路第29页连通性点点i i和和j j点是连通点是连通：G中存在一条（i，j）路G G是连通是连通：G中任意两点都是连通 连通分支连通分支：G极大连通子图 返回第30页有向路134256有向图有向图G G中一条有向路中一条有向路：个点和弧交织序列 (ni,aij,nj,nk,akl,nl)，记为(ni,nl)有向路 简单有向路简单有向路：弧不重有向路 初级有向路初级有向路：点不重有向路 有向回路有向回路：最少包含一条弧且ni=nj(ni,nj)有向路 简单有向回路简单有向回路：弧不重有向回路 初级有向回路初级有向回路：点不重有向回路第31页点点i i和点和点j j是强连通是强连通：G中存在一条(i,j)有向路，也存在一条(j,i)有向路G G是强连通是强连通：G中任意两点都是强连通 G G强连通分支强连通分支：G极大连通子图返回强连通性强连通性第32页vp=find_path(i,j,g)第33页割集第34页网络设计v常见网络设计管线网络、交通网络、通信网络、关系网络等v设计内容设置多少点？设在什么地方？-选址问题点之间怎样链接？-网路优化v设计要求实现基本功效成本最小第35页网络设计实例-交巡警平台网络v交巡警平台个数v交巡警平台位置v交巡警平台与路口连接关系第36页网络设计供给链网络设计v供给链节点企业数量v关键物流设施位置v物流配送任务分配第37页网络设计实例水管网络设计v考虑某县富春乡自来水村村通工程，自来水管已经铺设到乡驻地，下列图是各村之间铺设管道需要长度，请给出管网设计方案。1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第38页可行方案v支撑树连通水要送达每个村庄不含回路总长度最小1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第39页最优方案v最小支撑树-边长度之和最小支撑树1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第40页最小支撑树性质v下面方案一定不是最小支撑树。1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第41页最小支撑树判定条件最小支撑树判定条件1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第42页算法思绪v先给一个支撑树v对树外面每条边找出对应回路，判断是否是回路中最大边，假如是则看下一个边，不然去掉回路中最大边把该边加到树中，得一新支撑树，重新检验。v假如每条树外面边都是对应回路中最大边，则得到最小支撑树。第43页更简单算法思绪贪心算法v全部边从小到大排序v从小开始选边，假如新选边与已选边不组成回路，则把该边加入已选边集合，不然考虑下一条边v当选了n-1条边就得到一个最小支撑树没有选择边都与前面边组成回路，前面边权重小，因而没选择边一定是回路中权重最大第44页1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第45页1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第46页1.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.01.61.92.31.72.02.21.81.91.42.61.80.82.12.03.12.0第47页算法步骤算法步骤第48页Scilab实现用Scilab语句求解以下网络最小树t=min_weight_tree(g)1452312432214第49页Scilab命令及结果第50页第51页第52页总结v最小支撑树在网络设计中有广泛应用v最小支撑树算法比较简单，编程难点是怎样判断是否组成回路。vScilab能够直接求解最小支撑树问题，但需要先把图和权重输入程序。第53页流量安排问题v最大流问题v最小费用流问题v运输问题第54页最大流问题12345652332 42617第55页第56页数学规划模型第57页算法步骤算法步骤第58页第59页算例算例12345652332 42617第60页迭代过程迭代过程1234565,22,23,23,22,2 426,21712345632,2112,2 426,217-+1,3+2,1+1,1第61页第62页结果第63页最小费用流问题stdcba2,32,13,21,33,11,24,25,21,2第64页stdcba2,32,13,21,33,11,24,25,21,2stdcba2,32,13,21,33,11,24,25,21,22222222223211V=4，费用为32V=4，费用为25第65页线性规划形式第66页Scilab实现用Scilab语言求解以上算例所表示网络最小费用流Scilab语句：cleartail=11223;head=23344;g=make_graph(g,1,4,tail,head);cost=13131;max_cap=21242;第67页续g(edge_cost)=cost;g(edge_max_cap)=max_cap;demd=-3,0,0,3;g(node_demand)=demd;c,phi,flag=min_lcost_flow2(g)第68页结果flag=1.phi=!2.1.1.1.2.!c=11.第69页运输问题运出地(n个)运入地(m个)可运出量需运入量单位运量运输费用第70页运输方案v确定每个运出地向个运入地运输货物数量，要求满足：1、运出货物总量不得超出可运货物总量；2、运入货物总量不得低于需运货物总量；3、运输总费用最小第71页线性规划模型第72页对偶规划网络分析第73页算法步骤算法步骤第74页模型第75页计算model:min=8*x11+6*x12+9*x13+9*x14+9*x21+12*x22+13*x23+7*x24+14*x31+9*x32+16*x33+5*x34;x11+x12+x13+x14=35;x21+x22+x23+x24=50;x31+x32+x33+x34=45;x12+x22+x32=20;x13+x23+x33=30;x14+x24+x34=30;end第76页路线选择问题v最短路问题两点之间路线选择v旅游售货员问题环线选择v车辆路径问题多个环线选择第77页最短有向路问题12345652332 4 26 179第78页数学规划模型第79页算法步骤算法步骤第80页算例算例12345652332 426179第81页计算迭代过程计算迭代过程1234565233242617059312345652332426 1705109539912345652332426 17056953912345652332426 170568539第82页12345652332426 17056 8539第83页旅游售货员问题v旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,vn各一次最终返回v0最短路线和最短旅程。第84页动态规划方法现把它看成一个多阶段决议问题。从v0出发，经过n个阶段，每个阶段决议是选择下一个点。假如用所在位置来表示状态，那么状态与阶段数就不能完全决定决议集合了，因为走过点不需要再走，所以决议集合与以前选决议相关。用（vi,V）表示状态，vi是所处点，V是还没有经过点集合。在状态（vi,V）决议集合中，取决议vjV，取得效益是vi到vj距离dij，转入下一个状态（vj,Vvj），现在用最优化原理来找递推公式。第85页续(1)用fk(vi,V)表示从vi点出发，经过V中点各一次，最终回到v0点最短旅程，V是一个顶点集合，|V|=k，dij是vi到vj弧长，则第86页问题描述车辆路径问题是指一定数量用户，各自有不一样数量货物需求，配送中心向用户提供货物，由一个车队负责分送货物，组织适当行车路线，满足用户需求，并在一定约束条件下，到达一定目标（如旅程最短、成本最小、花费时间尽可能少等）。第87页基本问题描述v有一个车场，n个客户，每个客户需求为di，m辆车，车载重量为q，各客户之间以及客户与车场之间距离为cijv安排车辆路径使各车辆行车旅程之和最小第88页问题模型第89页模型第90页
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
