数学建模 组合优化模型(2011).ppt

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语句： clear tail=1

3、 1 2 2 3; head=2 3 3 4 4; 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个),可运出量,需运入量,单位运量的运输费用,运输方案,确定每

4、个运出地向个运入地运输货物的数量，要求满足： 1、运出货物总量不得超过可运货物总量； 2、运入货物总量不得低于需运货物总量； 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=4

5、5; x12+x22+x32=20; x13+x23+x33=30; x14+x24+x34=30; end,路线选择问题,最短路问题两点之间路线选择 旅游售货员问题环线选择 车辆路径问题多个环线选择,最短有向路问题,9,数学规划模型,算法步骤,算例,9,计算的迭代过程,9,9,旅游售货员问题,旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,vn各一次最后返回v0的最短路线和最短路程。,动态规划方法,现把它看成一个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因

6、为走过的点不需要再走，所以决策集合与以前选的决策有关。用（vi,V）表示状态，vi是所处的点，V是还没有经过的点集合。在状态（vi,V）的决策集合中，取决策vjV，获得的效益是vi到vj的距离dij，转入下一个状态（vj,Vvj），现在用最优化原理来找递推公式。,续(1),用fk(vi,V)表示从vi点出发，经过V中的点各一次，最后回到v0点的最短路程，V是一个顶点集合，|V|=k，dij是vi到vj的弧长，则,问题描述,车辆路径问题是指一定数量的顾客，各自有不同数量的货物需求，配送中心向顾客提供货物，由一个车队负责分送货物，组织适当的行车路线，满足顾客的需求，并在一定的约束条件下，达到一定的目标（如路程最短、成本最小、耗费时间尽量少等