资源描述：
《数学建模 组合优化模型(2011)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、组合优化问题建模马建华2011年7月优化问题建模优化问题概述数学规划模型组合优化模型优化算法介绍评价方法优化问题建模组合优化问题概述网络优化设计流量安排问题路线选择问题组合优化问题概述组合优化问题常见的组合优化问题组合优化问题建模步骤组合优化问题有限个可行方案中选择最优方案最优解一定存在可行方案的个数非常多，枚举法不可行，往往是NP-hard问题组合优化问题组合计数问题最小费用最大流问题最短路问题网络设计问题最优匹配问题装箱问题旅游售货员问题车辆路径问题网络设计常见网络设计管线网络、交通网络、通信网络、关系网络等设计内容设置
2、多少点？设在什么地方？--选址问题点之间如何链接？--网路优化设计要求实现基本功能成本最小网络连接方式最少用多少边可把下列点连起来？网络连接方式联通不含回路最小支撑树算法步骤算例1452312432214迭代过程1452312432214145231243221414523124322141452312432214流量安排问题最大流问题最小费用流问题运输问题最大流问题1234565233242617数学规划模型算法步骤算例1234565233242617迭代过程1234565,22,23,23,22,2426,2171234
3、5632,2112,2426,217-∞+1,3+2,1+1,1结果最小费用流问题stdcba2,32,13,21,33,11,24,25,21,2stdcba2,32,13,21,33,11,24,25,21,2stdcba2,32,13,21,33,11,24,25,21,22222222223211V=4，费用为32V=4，费用为25线性规划形式Scilab实现用Scilab语言求解以上算例所示网络的最小费用流Scilab语句：cleartail=[11223];head=[23344];g=make_graph('g
4、',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)结果flag= 1.phi= !2.1.1.1.2.!c= 11.运输问题运出地(n个)运入地(m个)可运出量需运入量单位运量的运输费用运输方案确定每个运出地向个运入地运输货物的数量，要求满足：1、运出货物
5、总量不得超过可运货物总量；2、运入货物总量不得低于需运货物总量；3、运输总费用最小线性规划模型对偶规划网络分析算法步骤运筹学课件网络分析算例运筹学课件网络分析求如图所示运输问题的最优解1231234-45-20-30-303550408699912137149165模型计算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;x3
6、1+x32+x33+x34<=40;x11+x21+x31>=45;x12+x22+x32>=20;x13+x23+x33>=30;x14+x24+x34>=30;end路线选择问题最短路问题—两点之间路线选择旅游售货员问题—环线选择车辆路径问题—多个环线选择最短有向路问题12345652332426179数学规划模型算法步骤算例12345652332426179计算的迭代过程123456523324261705∞9∞312345652332426170510953991234565233242617056953912345
7、65233242617056853912345652332426170568539旅游售货员问题旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,…,vn各一次最后返回v0的最短路线和最短路程。动态规划方法现把它看成一个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用（vi,V）表示状态，vi是所处的点，V是还没有经过的点集合。在状态（vi
8、,V）的决策集合中，取决策vjV，获得的效益是vi到vj的距离dij，转入下一个状态（vj,V{vj}），现在用最优化原理来找递推公式。续(1)用fk(vi,V)表示从vi点出发，经过V中的点各一次，最后回到v0点的最短路程，V是一个顶点集合，
9、V
10、=k，dij是vi到vj的弧长，则问题
