数学建模题目080420.ppt

;玩具、照片、飞机、火箭模型… …;你碰到过的数学模型——“航行问题”;航行问题建立数学模型的基本步骤;数学模型 (Mathematical Model) 和 数学建模（Mathematical Modeling);1.3 数学建模的重要意义;数学建模的具体应用; 数学建模的基本方法; 数学建模的一般步骤;模 型 假 设;模型 求解;数学建模的全过程; 近几年全国大学生数学建模竞赛题;;;;;;;;图论与网络优化;哥尼斯堡七桥问题;例：中国邮递员问题(CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题. ;图与网路的基本概念;所有边都没有方向的图称为无向图 在无向图中 eij=eji，或 (vi, vj)=(vj, vi) 当所有边都有方向时，称为有向图，用G(V,A)表示 在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识 图中既有边又有弧，称为混合图;;返回;顶点的次数;例 在一次聚会中，认识奇数个人的人数一定是偶数。;子图;关联矩阵;邻接矩阵;返回;例 甲、乙、丙、丁、戊五个球队比赛情况。;某单位储存八种化学药品，其中某些药品不能存放在同一个仓库，考虑所需最少仓库数;边与顶点均不重复的通路称为路径 ;返回;无圈连通图;树图与最小生成树;例 在五个村庄之间修路，使任一村庄可到其余各村庄。已知各村庄间修路所需费用如下图，考虑费用最省方案。;最小生成树求解方法：避圈法；破圈法;v2;权矩阵;权矩阵;一、问题的提法及应用背景;二、最短路算法：;最短路问题(非负权);;可化为最短路问题的多阶段决策问题;返回; 选址问题--中心问题;S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5; 选址问题--重心问题;e3;图G(V,E)有Euler环游充要条件是图G(V,E)无奇点 ;V7;中国邮递员问题-算法;V7;;（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．;;返回;哈 密 尔 顿 图;推销员问题-定义;定义　在加权图G=(V,E)中， （１）权最小的哈密尔顿圈称为最佳H圈． （２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．;;推销员问题近似算法：二边逐次修正法：;