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

《数学建模组合优化模型.ppt》由会员分享，可在线阅读，更多相关《数学建模组合优化模型.ppt（52页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、组组 合合 优优 化化 问问 题题 建建 模模马建华2011年7月优化问题建模山东财经大学马 建 华优化问题建模v优化问题概述v数学规划模型v组合优化模型v优化算法介绍v评价方法优化问题建模山东财经大学马 建 华优化问题建模v组合优化问题概述v网络优化设计v流量安排问题v路线选择问题优化问题建模山东财经大学马 建 华组合优化问题概述v组合优化问题v常见的组合优化问题v组合优化问题建模步骤优化问题建模山东财经大学马 建 华组合优化问题v有限个可行方案中选择最优方案v最优解一定存在v可行方案的个数非常多，枚举法不可行，往往是NP-hard问题优化问题建模山东财经大学马 建 华组合优化问题v组合计数

2、问题v最小费用最大流问题v最短路问题v网络设计问题v最优匹配问题v装箱问题v旅游售货员问题v车辆路径问题优化问题建模山东财经大学马 建 华网络设计v常见网络设计管线网络、交通网络、通信网络、关系网络等v设计内容设置多少点？设在什么地方？-选址问题点之间如何链接？-网路优化v设计要求实现基本功能成本最小优化问题建模山东财经大学马 建 华网络连接方式最少用多少边可把下列点连起来？最少用多少边可把下列点连起来？优化问题建模山东财经大学马 建 华网络连接方式联通不含回路优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华最小支撑树最小支撑树优化问题建模山东财经大学马 建 华算法步骤算法

3、步骤优化问题建模山东财经大学马 建 华算例算例1452312432214优化问题建模山东财经大学马 建 华迭代过程迭代过程1452312432214145231243221414523124322141452312432214优化问题建模山东财经大学马 建 华流量安排问题v最大流问题v最小费用流问题v运输问题优化问题建模山东财经大学马 建 华最大流问题12345652332 42617优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华数学规划模型优化问题建模山东财经大学马 建 华算法步骤算法步骤优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华算例算例123

4、45652332 42617优化问题建模山东财经大学马 建 华迭代过程迭代过程1234565,22,23,23,22,2 426,21712345632,2112,2 426,217-+1,3+2,1+1,1优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华结果优化问题建模山东财经大学马 建 华最小费用流问题2,32,13,21,33,11,24,25,21,2优化问题建模山东财经大学马 建 华2,32,13,21,33,11,24,25,21,22,32,13,21,33,11,24,25,21,22222222223211V=4，费用为32V=4，费用为25优化问题建模山

5、东财经大学马 建 华线性规划形式优化问题建模山东财经大学马 建 华Scilab实现用Scilab语言求解以上算例所示网络的最小费用流Scilab语句：cleartail=11223;head=23344;g=make_graph(g,1,4,tail,head);cost=13131;max_cap=21242;优化问题建模山东财经大学马 建 华续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)优化问题建模山东财经大学马 建 华结果f

6、lag=1.phi=!2.1.1.1.2.!c=11.优化问题建模山东财经大学马 建 华运输问题运出地(n个)运入地(m个)可运出量需运入量单位运量的运输费用优化问题建模山东财经大学马 建 华运输方案v确定每个运出地向个运入地运输货物的数量，要求满足：1、运出货物总量不得超过可运货物总量；2、运入货物总量不得低于需运货物总量；3、运输总费用最小优化问题建模山东财经大学马 建 华线性规划模型优化问题建模山东财经大学马 建 华对偶规划网络分析优化问题建模山东财经大学马 建 华算法步骤算法步骤运筹学课件运筹学课件网络分析优化问题建模山东财经大学马 建 华算例算例运筹学课件运筹学课件网络分析求如图所示

7、运输问题的最优解1231234-45-20-30-30355040 8 6 9 9 9 12 13 7 14 9 16 5优化问题建模山东财经大学马 建 华模型优化问题建模山东财经大学马 建 华计算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优化问题建模山东财经

8、大学马 建 华路线选择问题v最短路问题两点之间路线选择v旅游售货员问题环线选择v车辆路径问题多个环线选择优化问题建模山东财经大学马 建 华最短有向路问题12345652332 4 26 179优化问题建模山东财经大学马 建 华数学规划模型优化问题建模山东财经大学马 建 华算法步骤算法步骤优化问题建模山东财经大学马 建 华算例算例12345652332 426179优化问题建模山东财经大学马 建 华计算的迭代过程计算的迭代过程1234565233242617059312345652332426 1705109539912345652332426 17056953912345652332426 1

9、70568539优化问题建模山东财经大学马 建 华12345652332426 17056 8539优化问题建模山东财经大学马 建 华旅游售货员问题v旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,vn各一次最后返回v0的最短路线和最短路程。优化问题建模山东财经大学马 建 华动态规划方法现把它看成一个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用（vi,V）表示状态，vi是所处的点，V是还没有经过的点集合

10、。在状态（vi,V）的决策集合中，取决策vjV，获得的效益是vi到vj的距离dij，转入下一个状态（vj,Vvj），现在用最优化原理来找递推公式。优化问题建模山东财经大学马 建 华续(1)用fk(vi,V)表示从vi点出发，经过V中的点各一次，最后回到v0点的最短路程，V是一个顶点集合，|V|=k，dij是vi到vj的弧长，则优化问题建模山东财经大学马 建 华问题描述车辆路径问题是指一定数量的顾客，各自有不同数量的货物需求，配送中心向顾客提供货物，由一个车队负责分送货物，组织适当的行车路线，满足顾客的需求，并在一定的约束条件下，达到一定的目标（如路程最短、成本最小、耗费时间尽量少等）。优化问题建模山东财经大学马 建 华基本问题描述v有一个车场，n个客户，每个客户的需求为di，m辆车，车的载重量为q，各客户之间以及客户与车场之间的距离为cijv安排车辆的路径使各车辆行车路程之和最小优化问题建模山东财经大学马 建 华问题的模型优化问题建模山东财经大学马 建 华模型