数学建模组合优化模型学习教案.pptx
会计学1数学数学(shxu)建模组合优化模型建模组合优化模型第一页，共51页。组合优化问题组合优化问题组合优化问题组合优化问题(wnt)(wnt)概述概述概述概述n n组合优化问题n n常见(chn jin)的组合优化问题n n组合优化问题建模步骤第2页/共51页第二页，共51页。组合组合(zh)优化问题优化问题n n有限个可行方案中选择最优方案有限个可行方案中选择最优方案n n最优解一定最优解一定(ydng)(ydng)存在存在n n可行方案的个数非常多，枚举法不可行，往往是可行方案的个数非常多，枚举法不可行，往往是NP-hardNP-hard问题问题第3页/共51页第三页，共51页。组合组合(zh)优化问题优化问题n n组合计数问题组合计数问题(wnt)(wnt)n n最小费用最大流问题最小费用最大流问题(wnt)(wnt)n n最短路问题最短路问题(wnt)(wnt)n n网络设计问题网络设计问题(wnt)(wnt)n n最优匹配问题最优匹配问题(wnt)(wnt)n n装箱问题装箱问题(wnt)(wnt)n n旅游售货员问题旅游售货员问题(wnt)(wnt)n n车辆路径问题车辆路径问题(wnt)(wnt)第4页/共51页第四页，共51页。网络网络(wnglu)设计设计n n常见网络设计常见网络设计n n 管线网络、交通网络、通信网络、关系网络等管线网络、交通网络、通信网络、关系网络等n n设计内容设计内容n n 设置设置(shzh)(shzh)多少点？设在什么地方？多少点？设在什么地方？-选址问选址问题题n n 点之间如何链接？点之间如何链接？-网路优化网路优化n n设计要求设计要求n n 实现基本功能实现基本功能n n 成本最小成本最小第5页/共51页第五页，共51页。网络连接方式网络连接方式(fngsh)最少用多少边可把下列最少用多少边可把下列(xili)点连起来点连起来？第6页/共51页第六页，共51页。网络连接方式网络连接方式(fngsh)联通不含回路(hul)第7页/共51页第七页，共51页。第8页/共51页第八页，共51页。最小支撑最小支撑(zh chng)树树第9页/共51页第九页，共51页。算法算法(sun f)步骤步骤 第10页/共51页第十页，共51页。算例算例 1452312432214第11页/共51页第十一页，共51页。迭代迭代(di di)过程过程 1452312432214145231243221414523124322141452312432214第12页/共51页第十二页，共51页。流量安排流量安排(npi)问题问题n n最大流问题(wnt)n n最小费用流问题(wnt)n n运输问题(wnt)第13页/共51页第十三页，共51页。最大流问题最大流问题(wnt)12345652332 42617第14页/共51页第十四页，共51页。第15页/共51页第十五页，共51页。数学规划数学规划(guhu)模型模型第16页/共51页第十六页，共51页。算法算法(sun f)步骤步骤 第17页/共51页第十七页，共51页。第18页/共51页第十八页，共51页。算例算例 12345652332 42617第19页/共51页第十九页，共51页。迭代迭代(di di)过程过程 1234565,22,23,23,22,2 426,21712345632,2112,2 426,217-+1,3+2,1+1,1第20页/共51页第二十页，共51页。第21页/共51页第二十一页，共51页。结果结果(ji gu)第22页/共51页第二十二页，共51页。最小费用最小费用(fi yong)流流问题问题stdcba2,32,13,21,33,11,24,25,21,2第23页/共51页第二十三页，共51页。stdcba2,32,13,21,33,11,24,25,21,2stdcba2,32,13,21,33,11,24,25,21,22222222223211V=4，费用(fi yong)为32V=4，费用(fi yong)为25第24页/共51页第二十四页，共51页。线性规划线性规划(xin xn u hu)形式形式第25页/共51页第二十五页，共51页。ScilabScilab实现实现实现实现(shxin)(shxin)用用ScilabScilab语语言言求求解解以以上上算算例例所所示示网网络络(wnglu)(wnglu)的的最小费用流最小费用流ScilabScilab语句：语句：clearcleartail=1 1 2 2 3;tail=1 1 2 2 3;head=2 3 3 4 4;head=2 3 3 4 4;g=make_graph(g,1,4,tail,head);g=make_graph(g,1,4,tail,head);cost=1 3 1 3 1;cost=1 3 1 3 1;max_cap=2 1 2 4 2;max_cap=2 1 2 4 2;第26页/共51页第二十六页，共51页。续续g(edge_cost)=cost;g(edge_cost)=cost;g(edge_max_cap)=max_cap;g(edge_max_cap)=max_cap;demd=-3,0,0,3;demd=-3,0,0,3;g(node_demand)=demd;g(node_demand)=demd;c,phi,flag=min_lcost_flow2(g)c,phi,flag=min_lcost_flow2(g)第27页/共51页第二十七页，共51页。结果结果(ji gu)flag =1.flag =1.phi =!2.1.1.1.2.!phi =!2.1.1.1.2.!c =11.c =11.第28页/共51页第二十八页，共51页。运输运输(ynsh)问题问题运出地(n个)运入地(m个)可运出量需运入量单位(dnwi)运量的运输费用第29页/共51页第二十九页，共51页。运输运输(ynsh)方案方案n n确定每个运出地向个运入地运输(ynsh)货物的数量，要求满足：n n 1、运出货物总量不得超过可运货物总量；n n 2、运入货物总量不得低于需运货物总量；n n 3、运输(ynsh)总费用最小 第30页/共51页第三十页，共51页。线性规划线性规划(xin xn u hu)模型模型第31页/共51页第三十一页，共51页。对偶对偶(du u)规划规划网络分析第32页/共51页第三十二页，共51页。算法算法(sun f)步骤步骤运筹学课件运筹学课件网络分析第33页/共51页第三十三页，共51页。算例算例 运筹学课件运筹学课件网络分析求如图所示运输(ynsh)问题的最优解1231234-45-20-30-30355040 8 6 9 9 9 12 13 7 14 9 16 5第34页/共51页第三十四页，共51页。模型模型(mxng)第35页/共51页第三十五页，共51页。计算计算(j sun)modelmodel:minmin=8*x11+6*x12+9*x13+9*x14=8*x11+6*x12+9*x13+9*x14+9*x21+12*x22+13*x23+7*x24+9*x21+12*x22+13*x23+7*x24+14*x31+9*x32+16*x33+5*x34;14*x31+9*x32+16*x33+5*x34;x11+x12+x13+x14=35;x11+x12+x13+x14=35;x21+x22+x23+x24=50;x21+x22+x23+x24=50;x31+x32+x33+x34=40;x31+x32+x33+x34=45;x11+x21+x31=45;x12+x22+x32=20;x12+x22+x32=20;x13+x23+x33=30;x13+x23+x33=30;x14+x24+x34=30;x14+x24+x34=30;endend第36页/共51页第三十六页，共51页。路线选择路线选择(xunz)问题问题n n最短路问题两点之间路线选择(xunz)n n旅游售货员问题环线选择(xunz)n n车辆路径问题多个环线选择(xunz)第37页/共51页第三十七页，共51页。最短有向路问题最短有向路问题(wnt)12345652332 4 26 179第38页/共51页第三十八页，共51页。数学规划数学规划(guhu)模型模型第39页/共51页第三十九页，共51页。算法算法(sun f)步骤步骤 第40页/共51页第四十页，共51页。算例算例 12345652332 426179第41页/共51页第四十一页，共51页。计算计算(j sun)的迭代过程的迭代过程 1234565233242617059312345652332426 1705109539912345652332426 17056953912345652332426 170568539第42页/共51页第四十二页，共51页。12345652332426 17056 8539第43页/共51页第四十三页，共51页。旅游旅游(lyu)售货员问题售货员问题n n旅行(lxng)售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,vn各一次最后返回v0的最短路线和最短路程。第44页/共51页第四十四页，共51页。动态动态(dngti)规划方法规划方法现现把把它它看看成成一一个个多多阶阶段段决决策策问问题题。从从v0v0出出发发，经经过过n n个个阶阶段段，每每个个阶阶段段的的决决策策是是选选择择下下一一个个点点。如如果果用用所所在在的的位位置置来来表表示示状状态态，那那么么状状态态与与阶阶段段数数就就不不能能完完全全决决定定决决策策集集合合了了，因因为为走走过过的的点点不不需需要要(xyo)(xyo)再再走走，所所以以决决策策集集合合与与以以前前选选的的决决策策有有关关。用用（vi,Vvi,V）表表示示状状态态，vi vi是是所所处处的的点点，V V是是还还没没有有经经过过的的点点集集合合。在在状状态态（vi,Vvi,V）的的决决策策集集合合中中，取取决决策策vjVvjV，获获得得的的效效益益是是vi vi到到vj vj的的距距离离dijdij，转转入入下下一一个个状状态态（vj,Vvjvj,Vvj），现现在在用用最最优优化化原原理理来来找找递递推推公式。公式。第45页/共51页第四十五页，共51页。续续(1)用用fk(vi,V)fk(vi,V)表表示示从从vi vi点点出出发发，经经过过V V中中的的点点各各一一次次，最最后后(zuhu)(zuhu)回回到到v0v0点点的的最最短短路路程程，V V是是一个顶点集合，一个顶点集合，|V|=k|V|=k，dijdij是是vi vi到到vj vj的弧长，则的弧长，则第46页/共51页第四十六页，共51页。问题问题(wnt)描述描述车辆路径问题是指一定数量的顾客，各自有不同数量的货物需求，配送中心向顾客提供货物，由一个车队(ch du)负责分送货物，组织适当的行车路线，满足顾客的需求，并在一定的约束条件下，达到一定的目标（如路程最短、成本最小、耗费时间尽量少等）。第47页/共51页第四十七页，共51页。基本问题基本问题(wnt)描述描述n n有一个车场，有一个车场，n n个客户个客户(k h)(k h)，每个客户，每个客户(k h)(k h)的需的需求为求为di di，mm辆车，车的载重量为辆车，车的载重量为q q，各客户，各客户(k h)(k h)之间之间以及客户以及客户(k h)(k h)与车场之间的距离为与车场之间的距离为cijcijv安排车辆(chling)的路径使各车辆(chling)行车路程之和最小第48页/共51页第四十八页，共51页。问题问题(wnt)的的模型模型第49页/共51页第四十九页，共51页。模型模型(mxng)第50页/共51页第五十页，共51页。感谢您的观看感谢您的观看(gunkn)！第51页/共51页第五十一页，共51页。
