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

组 合 优 化 问 题 建 模马建华 2011年7月优化问题建模山东财经大学马 建 华优化问题建模v优化问题概述v数学规划模型v组合优化模型v优化算法介绍v评价方法优化问题建模山东财经大学马 建 华优化问题建模v组合优化问题概述v网络优化设计v流量安排问题v路线选择问题优化问题建模山东财经大学马 建 华组合优化问题概述v组合优化问题v常见的组合优化问题v组合优化问题建模步骤优化问题建模山东财经大学马 建 华组合优化问题v有限个可行方案中选择最优方案v最优解一定存在v可行方案的个数非常多，枚举法不可行，往往是 NP-hard问题优化问题建模山东财经大学马 建 华组合优化问题v组合计数问题v最小费用最大流问题v最短路问题v网络设计问题v最优匹配问题v装箱问题v旅游售货员问题v车辆路径问题优化问题建模山东财经大学马 建 华网络设计v常见网络设计管线网络、交通网络、通信网络、关系网络 等v设计内容设置多少点？设在什么地方？--选址问题点之间如何链接？--网路优化v设计要求实现基本功能成本最小优化问题建模山东财经大学马 建 华网络连接方式最少用多少边可把下列点连起来？优化问题建模山东财经大学马 建 华网络连接方式联通不含回路优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华最小支撑树优化问题建模山东财经大学马 建 华算法步骤 优化问题建模山东财经大学马 建 华 算例 145231 24322 14优化问题建模山东财经大学马 建 华迭代过程 145231 24322 14145231 24322 14145231 24322 14145231 24322 14优化问题建模山东财经大学马 建 华流量安排问题v最大流问题v最小费用流问题v运输问题优化问题建模山东财经大学马 建 华最大流问题1234565233 242617优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华数学规划模型优化问题建模山东财经大学马 建 华算法步骤 优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华算例 1234565233 242617优化问题建模山东财经大学马 建 华迭代过程 1234565,22,23,23,2 2,2426,21712345632,211 2,2426,217 -∞+1,3+2,1+1,1优化问题建模山东财经大学马 建 华优化问题建模山东财经大学马 建 华 结果优化问题建模山东财经大学马 建 华最小费用流问题stdcba2,32,13,21,33,11,24,25,21,2优化问题建模山东财经大学马 建 华stdcba2,32,13,21,33,11,24,25,21,2stdcba2,32,13,21,33,11,24,25,21,22222222 223211V=4，费用为32V=4，费用为25优化问题建模山东财经大学马 建 华 线性规划形式优化问题建模山东财经大学马 建 华Scilab实现用Scilab语言求解以上算例所示网络的最小费用流 Scilab语句：clear tail=[1 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个)可运出量需运入量单位运量的运输费用优化问题建模山东财经大学马 建 华 运输方案v确定每个运出地向个运入地运输货物的数量 ，要求满足：1、运出货物总量不得超过可运货物总量；2、运入货物总量不得低于需运货物总量；3、运输总费用最小 优化问题建模山东财经大学马 建 华 线性规划模型优化问题建模山东财经大学马 建 华 对偶规划网络分析优化问题建模山东财经大学马 建 华算法步骤运筹学课件网络分析优化问题建模山东财经大学马 建 华算例 运筹学课件网络分析 求如图所示运输问题的最优解1231234-45-20-30-30355040869 9912137149165优化问题建模山东财经大学马 建 华 模型优化问题建模山东财经大学马 建 华计算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优化问题建模山东财经大学马 建 华路线选择问题v最短路问题—两点之间路线选择v旅游售货员问题—环线选择v车辆路径问题—多个环线选择优化问题建模山东财经大学马 建 华最短有向路问题1234565233 242617 9优化问题建模山东财经大学马 建 华数学规划模型优化问题建模山东财经大学马 建 华算法步骤 优化问题建模山东财经大学马 建 华算例 1234565233 2426179优化问题建模山东财经大学马 建 华计算的迭代过程 1234565233 242617 05∞9∞31234565233 242617 0510953991234565233 242617 05695391234565233 242617 0568539优化问题建模山东财经大学马 建 华1234565233 242617 0568539优化问题建模山东财经大学马 建 华旅游售货员问题v旅行售货员问题是图论中一个著名问题， 就是在网络N上找一条从v0点出发，经过 v1,v2,…,vn各一次最后返回v0的最短路线和最 短路程。

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