数学建模组合优化模型省名师优质课赛课获奖课件市赛课一等奖课件.ppt

组组 合合 优优 化化 问问 题题 建建 模模马建华年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:字符串,nodearcornode-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.0221.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页