《数学建模组合优化模型.ppt》由会员分享，可在线阅读，更多相关《数学建模组合优化模型.ppt（52页珍藏版）》请在三一办公上搜索。
1、组 合 优 化 问 题 建 模,马建华 2011年7月,优化问题建模,优化问题概述数学规划模型组合优化模型优化算法介绍评价方法,优化问题建模,组合优化问题概述网络优化设计流量安排问题路线选择问题,组合优化问题概述,组合优化问题常见的组合优化问题组合优化问题建模步骤,组合优化问题,有限个可行方案中选择最优方案最优解一定存在可行方案的个数非常多，枚举法不可行，往往是NP-hard问题,组合优化问题,组合计数问题最小费用最大流问题最短路问题网络设计问题最优匹配问题装箱问题旅游售货员问题车辆路径问题,网络设计,常见网络设计 管线网络、交通网络、通信网络、关系网络等设计内容 设置多少点？设在什么地方？-
2、选址问题 点之间如何链接？-网路优化设计要求 实现基本功能 成本最小,网络连接方式,最少用多少边可把下列点连起来？,网络连接方式,联通不含回路,最小支撑树,算法步骤,算例,迭代过程,流量安排问题,最大流问题最小费用流问题运输问题,最大流问题,数学规划模型,算法步骤,算例,迭代过程,-,+1,3,+2,1,+1,1,结果,最小费用流问题,2,2,2,2,2,2,2,2,2,3,2,1,1,V=4，费用为32,V=4，费用为25,线性规划形式,Scilab实现,用Scilab语言求解以上算例所示网络的最小费用流Scilab语句：cleartail=1 1 2 2 3;head=2 3 3 4 4;
3、g=make_graph(g,1,4,tail,head);cost=1 3 1 3 1;max_cap=2 1 2 4 2;,续,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),结果,flag=1.phi=!2.1.1.1.2.!c=11.,运输问题,运出地(n个),运入地(m个),可运出量,需运入量,单位运量的运输费用,运输方案,确定每个运出地向个运入地运输货物的数量，要求满足：1、运出货物总量不得超过可运货物总量；2、运入货物
4、总量不得低于需运货物总量；3、运输总费用最小,线性规划模型,对偶规划,网络分析,算法步骤,运筹学课件,网络分析,算例,运筹学课件,网络分析,求如图所示运输问题的最优解,-45,-20,-30,-30,35,50,40,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=45;x12+x22+x32=20;x13+x23+x33=30;x14+x24+x34=30;end,路线选
5、择问题,最短路问题两点之间路线选择旅游售货员问题环线选择车辆路径问题多个环线选择,最短有向路问题,9,数学规划模型,算法步骤,算例,9,计算的迭代过程,9,9,旅游售货员问题,旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,vn各一次最后返回v0的最短路线和最短路程。,动态规划方法,现把它看成一个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用（vi,V）表示状态，vi是所处的点，V是还没有经过的点集合。在
6、状态（vi,V）的决策集合中，取决策vjV，获得的效益是vi到vj的距离dij，转入下一个状态（vj,Vvj），现在用最优化原理来找递推公式。,续(1),用fk(vi,V)表示从vi点出发，经过V中的点各一次，最后回到v0点的最短路程，V是一个顶点集合，|V|=k，dij是vi到vj的弧长，则,问题描述,车辆路径问题是指一定数量的顾客，各自有不同数量的货物需求，配送中心向顾客提供货物，由一个车队负责分送货物，组织适当的行车路线，满足顾客的需求，并在一定的约束条件下，达到一定的目标（如路程最短、成本最小、耗费时间尽量少等）。,基本问题描述,有一个车场，n个客户，每个客户的需求为di，m辆车，车的载重量为q，各客户之间以及客户与车场之间的距离为cij,安排车辆的路径使各车辆行车路程之和最小,问题的模型,模型,
