全国大学生数学建模竞赛常用建模方法探讨-毕业论文.doc

邯郸学院本科毕业论文邯郸学院本科毕业论文 题题 目目 全国大学生数学建模竞赛常用建模方法探讨 郑重声明郑重声明 本人的毕业论文 设计 是在指导教师 闫峰 的指导下独立撰写完 成的 如有剽窃 抄袭 造假等违反学术道德 学术规范和侵权的行为 本 人愿意承担由此产生的各种后果 直至法律责任 并愿意通过网络接受公众 的监督 特此郑重声明 毕业论文 设计 作者 签名 年 月 日 I 全国大学生数学建模竞赛常用建模方法探讨全国大学生数学建模竞赛常用建模方法探讨 摘 要 请单击此处 然后输入中文摘要内容 关键词 关键词 数学建模竞赛 初等方法 建模方法 微分方程 图论 线性规划 II Commonly used modeling method of the National Mathematical Contest in Modeling Chai yunfei Directed by Professor Yanfeng ABSTRACT 在此处输入英文摘要内容 KEY WORDS mathematical contest elementary method modeling method differential equations graph theory linear programming 1 目目 录录 全国大学生数学建模竞赛常用建模方法探讨 I 前 言 1 1 初等数学建模方法 2 1 1 走路问题 2 1 2 银行复利问题 3 2 微分方程建模方法 5 2 1 微分方程建模原理和方法 5 2 2 人才分配问题模型 7 3 差分和代数建模方法 8 3 1 Malthus 人口模型 8 3 2 线性差分方程的解法 9 4 数据差值与拟合方法 10 4 1 拉格朗日插值法 11 4 2 最小二乘法 12 5 线性规划建模方法 14 5 1 线性规划的一般理论 14 5 2 合理下料问题 16 6 图论建模方法 17 6 1 图论的基本概念和简单的图论模型 17 6 2 最短轨道问题 18 6 3 求最小生成树 18 6 4 模拟退火法原理 19 6 5 应用举例 19 参考文献 21 附 录 22 致 谢 23 1 前前 言言 全国大学生数学建模竞赛创办于 1992 年 每年一届 目前已成为全国高校规模最大 的基础性学科竞赛 也是世界上规模最大的数学建模竞赛 竞赛题目一般来源于工程技 术和管理科学等方面经过适当简化加工的实际问题 不要求参赛者预先掌握深入的专门 知识 只需要学过高等学校的数学课程 题目有较大的灵活性供参赛者发挥其创造能力 参赛者应根据题目要求 完成一篇包括模型的假设 建立和求解 计算方法的设计和计 算机实现 结果的分析和检验 模型的改进等方面的论文 赛题一般涉及面宽 有社会 经济 管理 生活 环境 自然现象 工程技术 现代科学中出现的新问题等 一般都 有一个比较确切的现实问题 本文将主要介绍一些常用的数学建模方法 包括初等数学 建模方法 微分方程建模方法 差分和代数建模方法 数据差值与拟合方法 线性规划 建模方法 图论建模方法等 2 1 初等数学建模方法 在数学建模竞赛中 常会涉及到初等数学建模方法 对于一些机理简单的问题 常 常应用静态 线性或逻辑的方法即可建立模型 使用初等数学方法或简单的微积分知识 即可求解 此类模型称之为初等数学模型 初等数学建模方法很多 有比例关系 状态 转移 量纲分析 类比建模等 本章主要列举了走路问题与银行复利问题 问题中涉及 到了一些方法 通过这些知识方法的巧妙应用 可以开拓思路 提高分析解决实际问题 的能力 1 1 走路问题 人在匀速行走时 步行多大最省劲 把人行走时做的功看作是人体重心的势能和两 脚运动的动能之和 试在此基础上 建立数学模型并对所得结果进行评价 设人体重 M 腿重为 腿长为 步长为 速度为 单位时间内步数为 n 则mlxv nxv 由已知 人行走时所作的功是抬高人体重心所需势能与两腿运动所需动能之和 计算人体重心升高的势能 将人的行走简化 设重心升高为 h 则 lllh cos 2 sin1 ll 2 2 4 1 l x 当较小时 取泰勒公式展开式前两项 得 l x 2 1 llh 2 2 8l x l x 8 2 于是单位时间内重心升高所需势能为 E 势 nMgMghn l x 8 2 l Mgxv 8 计算腿运动的动能 如果将行走视为腿 均为直径 绕腰部的转动 则单位时间的动能为 E In 动 2 1 2 3 其中 I 为转动惯量 I l l 1 0 2 r dm 1 0 2 rdr 3 1 3 3 m 2 为角速度 m l 所以 l v E l mv 动 2 n 3 m 2 2 2 l v 6 n 2 x mv 6 3 于是单位时间行人行走所作的功为 P E E 势动 l Mgxv 8x mv 6 3 这是一个数学模型 问题转化为欲求 x 为多大时 P 最小 在 中 求 P 的驻点 令 0 解得 x v 由 nx v 得 dx dp Mg ml 3 4 n Mg ml 3 4 若取 M m 4 1 代入且近似取 l 1 米 可得 n 5 即每秒 5 步 显然太快了 模型修改 是腿重集中在脚上 人行走所需动能为脚的直线运动的动能 则有 mv n E 动能 2 1 2 x v 2 m 3 其中 P l Mgxv 8x v 2 m 3 同上解得 3 这比较符合实际 n Mg ml 3 4 1 2 银行复利问题 一个人为了积累养老金 他每月按时到银行存 100 元 银行的年利率 2 且可以任 意分段按复利计算 试问此人 5 年后共积累了多少养老金 如果存款和复利按日计算 则他又有多少养老金 如果复利和存款连续计算呢 试建立数学模型并求解 按月存款和利息时 每月的利息为 12 1 100 2 600 1 记 x 为第 k 月末时的养老金数 则由题意得 k x 100 1 4 x 100 100 1 2 600 1 x 100 100 1 100 1 3 600 1 600 1 2 x 100 100 1 100 1 n 600 1 600 1 1 n 五年末养老金为 x 100 60000 1元 6629 9 元 60 60 600 1 1 1 600 1 1 1 60 600 1 1 当复利和存款按日计算时 记 y 为第 k 天的养老金数 则每天的存款额为 a k 每天的利率为 r 第 k 1 天的养老金数量与第 k 天的养老金数量的关系为 365 1200 36500 2 y y 1 r y 1 1 k 365 1200 k 365 1200 k 36500 2 从第一天开始递推为 y a 1 y a a 1 r 2 y a a 1 r a 1 r 3 2 y a a 1 r a 1 r a 1 r a 1 n 21 n n r r 1 1 1 1 r a n r 1 在 5 年末时的养老金数为 5 年 5 365 1825 y 1 1 6614 68 元 1825 r a 1825 1 r 365 1200 2 36500 1825 36500 2 1 当存款和复利连续计算时 将 1 年分成 m 个相等的时间区间 则在每个时间区间 中 存款为 每个区间的利息为 记第 k 个区间养老金的数目为 z 类似与前 m 1200 m100 2 k 面分析 5 年后养老金为 z m5 m 1200 m m m 5 100 2 1 1 100 2 1 1 m 1200 1 100 2 1 2 100 5 m m m 5 60000 元 60000 1 100 2 1 5 m m 1 50 1 1 5 m m 令 m 即得连续存款和利息时 5 年后的养老金为 Z 60000 60000 e 1 元 6642 08 元 lim m 1 100 2 1 5m m 10 1 观察这三种不同情况下复利的计算问题 可以看出 将 1 年份为 m 等份 得出的计 算公式 具有一般性 当 m 分别取 12 和 365 时 就是前两种情况下的计算公式 另外 是 m 的单调函数 所以计算间隔越小 5 年后的养老金数就越多 但不会超过 m m 5 50 1 1 连续存款和计息的极限值 由于存款和计息的间隔越小时 收益越大 且不需要一次到银行存较多的现金而是分 批逐渐存入 对投资者的资金周转有利 所以在银行按复利计算时 建议存款者尽量采 用小间隔的策略 2 微分方程建模方法 在大多赛题中 要直接找出某些量之间的关系往往比较困难 但有时考虑其微小增 量或变化率与这些变量之间的关系确是容易的 这种情形下我们常常采用微分关系式去 描述其关系 2 1 微分方程建模原理和方法 一般来说 任何事变问题中随时间变化发生变化的量与其它一些量之间的关系经常 以微分方程的形式来表现 看这样一个问题 有一容器装有某种浓度的溶液 以流量 v 1注入该容器浓度为 c1的同样溶液 假定溶液立即被搅拌均匀 并以 v2的流量流出混合 后的溶液 试建立反映容器内浓度变化的数学模型 注意到 溶液浓度 溶液体积 溶质质量 因此 容器中溶液浓度会随溶质质量和溶液体积变化而发生变化 不妨设 t 时刻容器 中溶质质量为 s t 初始值为 s t 时刻容器中溶液体积为 V t 初始值为 V 则这段时 00 6 间内有 1 ttt tvtvV tvctvcs 21 2211 其中 c 表示单位时间内注入溶液的浓度 c 表示单位时间内流出溶液的浓度 当 12 t 很小时 在内 ttt c 2 2 tV ts tvvV ts 210 对式 1 两端同除以 令 0 则有t t 3 00 21 2211 0 0 VVss vv dt dV vcvc dt ds 此即问题的数学模型 它是针对液体溶液变化建立的 但它对气体和固体浓度变化 同样适用 实际中 对面许多时变问题都可取微小的时间段 t 去考察某些量之间的变化 规律 从而建立问题的数学模型 这是数学建模中微分建模常用手段之一 通过对上述例子的了解 下面介绍几种常用微分方程建模方法 1 按实验定律或规律建立的微分方程模型 刺激按摩充分依赖于各个学科领域中有关实验定律或规律以及某些重要的已知定理 此法建模要求建模者有宽广的知识视野才能对耨写具体问题采用某些熟知的实验定律 2 分析微元变化规律建立微分方程模型 求解某些实际问题时 寻求一些微元之间的关系可以建立问题的数学模型 如上述 问题中考察时间微元 t 从而建立的反应溶液浓度随时间变化的模型 此建模方法的出 发点是考察某一变量的微小变化 即微元分析 找出其他一些变量与该微元间的关系式 从微分定义出发建立问题的数学模型 3 近似模拟法 在许多实际问题中 有些现象的规律性并非一目了然 或有所了解亦是复杂的 这 类问题常用近似模拟方法来建立问题的数学模型 一般通过一定的模型假设近似模拟实 际现象 将问题做某些规范化处理后建立微分方程模型 然后分析 求解再与实际问题 作比较 观察模型能否近似刻画实际现象 近似模拟法建模思路是建立能够近似刻画或 反映实际现象的数学模型 因此在建模过程中经常做一些较合理的模型假设使问题简化 然后通过简化建立近似反映实际问题的数学模型 7 2 2 人才分配问题模型 每年大学毕业生中都要有一定比例的人员留在学校充实教师队伍 其余人员将分配到 国民经济其他部门从事经济和管理工作 设 t 年教师人数为 1 tx 科学技术和管理人员数目 为 2 tx 又设 1 外教员每年平均培养 个毕业生 每年人教育 科技和经济管理岗位 退休 死亡或调出人员的比率为 10 表示每年大学生毕业生中从事教师职业所 占比率 10 于是有方程 11 1 xx dt dx 1 21 2 1 xx dt dx 2 方程 1 有通解 t eCx 11 3 若设 0 1 01 xx 则 1 01 xC 于是得特解 t exx 1 01 4 将 4 代入 2 方程变为 t exx dt dx 1 02 2 1 5 求解方程 5 得通解 tt e x eCx 1 0 22 1 6 若设 0 2 02 xx 则 1 1 0 2 02 xxC 于是得特解 tt exexxx 1 0 1 0 2 02 11 7 4 式和 7 式分别表示在初始人数分别为 0 0 21 xx 情况 对应于 的取值 在 t 年教 师队伍的人数和科技经济管理人员人数 从结果看出 如果取 1 即毕业生全部留在教 8 育界 则当 t 时 由于 必有 1 tx 而 0 2 tx 说明教师队伍将迅速增加 而科技和经济管理队伍不断萎缩 势必要影响经济发展 反过来也会影响教育的发展 如 果将 接近于零 则 0 1 tx 同时也导致 0 2 tx 说明如果不保证适当比例的毕业生充 实教师选择好比率 将关系到两支队伍的建设 以及整个国民经济建设的大局 3 差分和代数建模方法 在一些问题中 许多数据都是以等间隔时间周期统计的 例如 银行中的定期存款 是按设定的时间等间隔计息 外贸出口额按月统计 国民收入按年统计 产品的产量按 月统计 等等 这些量是变量 通常这些变量为离散型变量 描述离散型变量之间的关 系的数学模型为离散型模型 对取值是离散化的经济变量 差分方程是研究他们之间变 化规律的有效方法 3 1 Malthus 人口模型 1798 年 英国人口学家和政治经济学家马尔萨斯以两个假设为前提 第一 食物为 人类生存所必须 第二 人的性本能几乎无法限制 提出了闻名于世的人口指数增长模 型 即 Malthus 人口模型 人口总数为 tp 人口的出生率为 b 死亡率为 d 任取时段 t t dt 在此时段中 的出生人数为 b tp dt 死亡人数为 d tp dt 假设出生数及死亡数与 tp 及dt均成正 比 而且以矩形取代了曲边梯形的面积 在时段 t t dt 中 人口增加量为 dttp tp d tp 它应等于此时段中的出生人数与死亡人数之差 即 d tp b tp dt d tp dt a tp dt 其中a b d 称为人口的净增长率 于是 tp 满足微分方程 dt tdp a tp 1 若已知初始时刻t t0 时的人口总数为 p0 那么 tp 还满足初始条件 9 t t0 时 tp p0 2 可以求得微分方程 1 满足初始条件 2 的解为 设a是常数 tp p0e 0 tta 3 即人口总数按指数增长 模型参数的意义和作用 t0 为初始时刻 初始年度 p0 为初始年度t0 的人口总数 a为每年的人口净增长率 b 为人口出生率 d 为人口死亡率 Malthus 人口模型所说的人 口并不一定限于人 可以是认可一个生物群体 只要满足类似的性质即可 3 2 线性差分方程的解法 方程 110 nbxaxaxa nkknkn 1 其中 k aaa 10 为常数 称方程 1 为常系数线性方程 又称方程 0 110 nkknkn xaxaxa 2 为方程 1 对应的齐次方程 如果 2 有形如 n n x 的解 带入方程中可得 0 1 1 10 kk kk aaaa 3 称方程 3 为方程 1 2 的特征方程 显然 如果能求出 3 的根 则可以得到 2 的解 基本结果如下 若 3 有 k 个不同的实根 则 2 有通解 n kk nn n cccx 2211 若 3 有 m 重根 则通解中有构成项 n m mn cncc 1 21 若 3 有一对单复根 i 令 i e arctan 22 则 2 的通解中有构成项 ncnc nn sincos 21 10 若有 m 重复根 i i e 则 2 的通项中有成项 nncnccnncncc nm mmm nm m sin cos 1 221 1 21 综上所述 由于方程 3 恰有 k 个根 从而构成方程 9 的通解中必有 k 个独立的任意常数 通解可记为 n x 如果能得到方程 1 的一个特解 n x 则 1 必有通解 n x n x n x 11 1 的特解可通过待定系数法来确定 例如 如果 npnpbnb mm n 为 n 的多项式 则当 b 不是特征根时 可设成 形如 nqb m n 形式的特解 其中 nqm 为 m 次多项式 如果 b 是 r 重根时 可设特解 rnn b nqm 将其代入 8 中确定出系数即可 4 数据差值与拟合方法 在生产实践和科学研究中 常常有这样的问题 由实验或测量得到变量间的一批离 散样点 要求由此建立变量之间的函数关系或得到样点之外的数据 与此有关的一类问 题是当原始数据 1100nn yxyxyx 精度较高 要求确定一个初等函数 xPy 一般用多项式或分段多项式函数 通过已知各数据点 节点 即 nixPy ii 1 0 或要求得函数在另外一些点 插值点 处的数值 这便是插值问 题 4 1 拉格朗日插值法 数据建模有两大方法 一类是插值方法 另一类是拟合函数一般的说 插值法比较 适合数据准确或数据量小的情形 然而 Lagrange 插值有很多种 1 阶 2 阶 n 阶 我们 可以利用拉格朗日插值求方程 根据它的程序求原方程的图像 下面我具体介绍分析一 下拉格朗日插值的算法设计及应用 11 已知函数 y f x 在若干点 i x 的函数值 i y i xf i 0 1 n 一个差值问题就是求一 简单 的函数 p x p i x i y i 0 1 n 1 则 p x 为 f x 的插值函数 而 f x 为被插值函数会插值原函数 0 x 1 x 2 x n x 为 插值节点 式 1 为插值条件 如果对固定点 x求 f x 数值解 我们称 x为一个插值节 点 f x p x 称为 x点的插值 当 x min 0 x 1 x 2 x n x max 0 x 1 x 2 x n x 时 称为内插 否则称为外插式外推 特别地 当 p x 为不超过 n 次多项式时称为 n 阶 Lagrange 插值 线性插值公式 1 1 L 设已知 0 x 1 x 及 0 y f 0 x 1 y f 1 x 1 xL 为不超过一次 多项式且满足 01 xL 0 y 11 xL 1 y 几何上 1 xL 为过 0 x 0 y 1 x 1 y 的直线 从而得到 1 xL 0 y 01 01 xx yy x 0 x 2 为了推广到高阶问题 我们将式 2 变成对称式 1 xL 0 l x 0 y 1 l x 1 y 其中 0 l x 10 1 xx xx 1 l x 01 0 xx xx 均为 1 次多项式且满足 0 l x 1 且 1 l x 0 或 0 l x 0 且 1 l x 1 两关系式可统一写成 ii xl ji ji 0 1 3 n 阶 Lagrange 插值公式 xLn 设已知 0 x 1 x 2 x n x 及 i y f i x i 0 1 n xLn 为不超过 n 次多项式且满足 iin yxL i 0 1 n 易知 xLn 0 l x 0 y xln n y 其中 xli 均为 n 次多项式且满足式 3 i j 0 1 n 再由 j x j i 为 n 次多项 12 式 xli 的 n 个根知 xli c n ii j j xx 0 最后 由 1 0 n ij j jiji xxcxl c n ij j ji xx 0 1 i 0 1 n 总之 xLn i n i i yxl 0 xli 0 n ij j ji j xx xx 式为 n 阶 Lagrange 插值公式 其中 xli i 0 1 n 称为 n 阶 Lagrange 插值的基函数 4 2 最小二乘法 在两个观测量中 往往总有一个量精度比另一个高得多 为简单起见把精度较高的 观测量看作没有误差 并把这个观测量选作 x 而把所有的误差只认为是 y 的误差 设 x 和 y 的函数关系由理论公式 y f x c1 c2 cm 0 0 1 给出 其中 c1 c2 cm 是 m 个要通过实验确定的参数 对于每组观测数据 xi yi i 1 2 N 都对应于 xy 平面上一个点 若不存在测量误差 则这些 数据点都准确落在理论曲线上 只要选取 m 组测量值代入式 0 0 1 便得到方程组 yi f x c1 c2 cm 0 0 2 式中 i 1 2 m 求 m 个方程的联立解即得 m 个参数的数值 显然 Nm 的情况下 式 0 0 2 成为矛盾方程组 不能直接用解方程的方法求得 m 个参数值 只能用曲线拟合的方法来处理 设测量中不存在着系统误差 或者说已经修 正 则 y 的观测值 yi 围绕着期望值 摆动 其分布为正态分 布 则 yi 的概率密度为 2 2 21 2 exp 2 1 i mii i i cccxfy yp 式中 i 是分布的标准误差 为简便起见 下面用 C 代表 c1 c2 cm 考虑各 次测量是相互独立的 故观测值 y1 y2 cN 的似然函数 N i i i N N Cxfy L 1 2 2 21 2 1 exp 2 1 13 取似然函数 L 最大来估计参数 C 应使 min 1 1 2 2 N i ii i Cxfy 0 0 3 取最小值 对于 y 的分布不限于正态分布来说 式 0 0 3 称为最小二乘法准则 若为正态分布的情况 则最大似然法与最小二乘法是一致的 因权重因子 2 1 ii 故 式 0 0 3 表明 用最小二乘法来估计参数 要求各测量值 yi 的偏差的加权平方和为最 小 根据式 0 0 3 的要求 应有 mkCxfy c cc N i ii ik 2 10 1 1 2 2 从而得到方程组 mk C Cxf Cxfy cc N i k ii i 2 10 1 1 2 0 0 4 解方程组 0 0 4 即得 m 个参数的估计值 m ccc 21 从而得到拟合的曲线方程 m cccxf 21 然而 对拟合的结果还应给予合理的评价 若 yi 服从正态分布 可引入拟合的 x2 量 N i ii i Cxfyx 1 2 2 2 1 0 0 5 把参数估计 m cccc 21 代入上式并比较式 0 0 3 便得到最小的 x2 值 N i ii i cxfyx 1 2 2 2 min 1 0 0 6 可以证明 2 min x 服从自由度 v N m 的 x2 分布 由此可对拟合结果作 x2 检验 由 x2 分布得知 随机变量 2 min x 的期望值为 N m 如果由式 0 0 6 计算出 2 min x 接近 N m 例如 mNx 2 min 则认为拟合结果是可接受的 如果 2 2 min mNx 则认 为拟合结果与观测值有显著的矛盾 14 5 线性规划建模方法 线性规划建模方法主要用于解决生活 生产中的资源利用 人力调配 生产安排等 问题 它是一种重要的数学模型 线性规划是运筹学中研究较早 发展较快 应用广泛 方法较成熟的一个重要分支 它是辅助人们进行科学管理的一种数学方法 研究线性约 束条件下线性目标函数的极值问题的数学理论和方法 5 1 线性规划的一般理论 一般的优化问题是指用 最好 的方式 使用或分配有限的资源即劳动力 原材料 机器 资金等 使得费用最小或利润最大 优化模型的一般形式为 min 或 max z f x 1 s t g x 0 i 1 2 m 2 x x1 x2 xn T 由 1 2 组成的模型属于约束优化 若只有 1 式就是无约束优化 f x 称 为目标函数 gi x 0 称为约束条件 在优化模型中 如果目标函数 f x 和约束条件 gi x 都是线性函数 则该模型称 为线性规划 实际问题的线性规划模型的步骤 第一步 设置要求解的决策变量 决策变量选取得当 不仅能顺利地建立模型而且 能方便地求解 否则很可能事倍功半 第二步 找出所有的限制 即约束条件 并用决策变量的线性方程或线性不等式来 表示 当限制条件多 背景比较复杂时 可以采用图示或表格形式列出所有的已知数据 和信息 从而避免 遗漏 或 重复 所造成的错误 第三步 明确目标要求 并用决策变量的线性函数来表示 标出对函数是取极大还 是取极小的要求 决策变量的非负要求可以根据问题的实际意义加以确定 需要特别说明的是 要使用线性规划方法来处理一个实际问题 必须具备下面的条件 1 优化条件 问题的目标有极大化或极小化的要求 而且能用决策变量的线性函数来 15 表示 2 选择条件 有多种可供选择的可行方案 以便从中选取最优方案 3 限制条件 达到目标的条件是有一定限制的 比如 资源的供应量有限度等 而 且这些限制可以用决策变量的线性等式或线性不等式表示出来 此外 描述问题的决策变量相互之间应有一定的联系 有可能建立数学关系 即这 些变量之间是内部相关的 这一点自然是不言而喻的 为了便于研究线性规划问题的理论与一般解法 人们需要将任意一个线性规划问题 化为标准形式 n 个变量的线性规划问题的标准形式为 Max s n j jjx c 1 1 ts n j ijij bxa 1 mi 3 2 1 2 j x 0 i b 是 0 的常数 3 线性规划问题的标准形式 简记 LP 问题 可通过以下手段将线性规划问题的一般形式转化为标准形式 1 目标函数转化 若问题的目标函数是求其极小值 即求 Min z c1x1 c2x2 cnxn 则可转化为求极大值问题 即求 max z z c1x1 c2x2 cnxn 2 约束条件转换 如果某一约束条件是线性不等式 n j ijij bxa 1 或 n j ijij bxa 1 则通过引入松弛变量 x 1 i 0 将它转化为 n j iinjij bxxa 1 或 n j iinjij bxxa 1 其中的x 1 i 也称为剩余变量 x1 i 0 反之 若有必要 也可等式约束 n j ijij bxa 1 等价的转化为两个不等式约束 即 n j ijij bxa 1 或 n j ijij bxa 1 3 变量的转换 若某个变量的约束条件为x i 1 l 或x i 1 l 则可令 16 j y j x j l 或 j y jj xl j y 变为非负变量 若某个变量 i x 无非负限制 称为自由变量 则可令 0 jj jjj xx xxx 代入原问题 将自由变量替换掉 5 2 合理下料问题 假定有一批某种型号的圆钢长 8 厘米 需要截成 2 5 厘米的毛坯 100 根 长 1 3 厘米 的毛坯 200 根 问应该怎样选择下料方式才能既满足需要又使总用料最少 根据经验 可将各种可能的方案列出来 解 设决策变量 j x 4 3 2 1 j 表示第 j 种方式所用的原材料根数 则问题的数 学模型可归结为 求 j x 4 3 2 1 j 使得 min 4321 xxxxz 4 3 2 1 0 200642 10023 432 321 jx xxx xxx ts j 结果为 0 3 100 3 100 0 3 200 4321 xxxxz 注 此问题结果不唯一 即可有多种方案 将结果应用到实际 由实际情况所限 根数为整数 也有多种选择 但最少用 67 根 考虑 还有没有其他标准 可以使切割后剩余的总余料最少 此时 相应的模型应 为什么 这类问题的一般提法是 设某种原材料截取零件为 n AAA 21 的毛坯 由以往的经 验 在一件原材料上可以有 n BBB 21 种不同的下料方式 每种下料方式可截得各种毛 坯的个数以及每种零件的需要量已经给出 问应如何下料 才能既满足需要又使原材料 消耗最少 另外 还有 合理配料问题 食谱问题 等也可归结为类似形式 17 6 图论建模方法 图论作为离散数学的一个重要分支 在工程技术 自然科学和经济管理中的许多方 面都能提供有力的数学模型来解决实际问题 所以吸引了很多研究人员去研究图论中的 方法和算法 应该说 我们对图论中的经典例子或多或少还是有一些了解的 比如 哥 尼斯堡七桥问题 中国邮递员问题 四色定理等等 图论方法已经成为数学模型中的重 要方法 许多难题由于归结为图论问题被巧妙地解决 而且 从历年的数学建模竞赛看 出现图论模型的频率极大 比如 AMCM90B 扫雪问题 AMCM91B 寻找最优 Steiner 树 AMCM92B 紧急修复系统的研制 最小生成树 AMCM94B 计算机传输数据的最小时间 边染色问题 CMCM93B 足球队排名 特征向量法 CMCM94B 锁具装箱问题 最大独立顶点集 最小覆盖等用来证明最优性 CMCM98B 灾情巡视路线 最优回路 等等 这里面都直接或是间接用到图论方面的知识 要说明的是 这里图论只是解 决问题的一种方法 而不是唯一的方法 6 1 图论的基本概念和简单的图论模型 首先给出图论中的一些基本概念 1 一个图 G 由一个顶点集 V 和一个边的集 E 组成 E 中每个元素 e 是连接顶点集 V 中两个顶点 u 和 v 的边 称 e 与 u v 关联 我们规定连接两个顶点 u v 至多有一条边 且一条边的两个顶点不重合 这种图称为简单图 2 顶点集为 V 边集为 E 的图 G 通常记为 G V E 图 G1 V1 E1 称为 G 的子图 如果 V1V E1E 3 顶点 v 的度 或 次 是指与 v 相关联的边的个数 图 G 的度数之和为边数的两 倍 4 若图 G 中任意两个顶点 u v 之间都存在连接它们的路 称 G 为连通图 5 W v0e1v1e2 ekvk 其中 ei E vj V ei 与 vi 1 vi 关联 称 W 是图 G 的一 条道路 v0 是起点 vk 是终点 各边相异的道路叫做行迹 各顶点相异的道路叫做轨道 起点和终点重合的道路为回路 起点和终点重合的轨道为圈 包含图中每条边的回路称 为 Euler 回路 含 Euler 回路的图称为 Euler 图 18 6 一个无圈的连通图称为树 树是最简单而最重要的一类图 树有下列重要性质 7 如果图 G V E 的子图 Gt Vt Et 是一个树 且 Vt V 称 G t 是 G 的生成 树 G 连通的充要条件是 G 有生成树 生成树一般而言数量很大 8 设对图 G V E 的每一条边 e 赋予一个实数 W e 称为 e 的权 G 称为赋权 图 加权图 假设 G 是连通的赋权图 要找 G 的连通子图 G V E 使得 W G Ee eW 为最小 显然 G 应为 G 的一个生成树 G 的权最小的生成树称为 G 的最小生成树 6 2 最短轨道问题 背景 给定连接若干城市的铁路网 寻求从指定城市 v0 到各城 v 去的最短道路 数学模型 图 G 为一赋权图 对任给的 v V G 寻求轨道 P v0 v 使得 W P v0 v min W P P 取自所有 v0 到 v 的轨道集合 其中 W P 是轨道 P 上各边权之和 这一问题可用迪克斯特拉 Dijkstra 算法解决 基本思想 从起点 v0 开始 逐步寻找到达各点的最短路 在每一步都对顶点记录一 个数 称之为该点的标号 它表示 v0 到该点的最短距离的上界 或就是 v0 到该点的最 短距离 实际上每一步都通过把至少一个具有 T 标号的点变成 P 标号 即把一个不是最短 距离标号的顶点变成是最短距离标号的顶点 这样最多经过 V G 1 步就可完成 步骤 记 l v 为 v0 到 v 的距离 1 l v0 0 l v v v0 S0 v0 i 0 2 对 v Si min l v l vi w viv 代替 l v 这样找到点 vi 1 使得 l v 取最小值 v i 1 Si 的余集 令 S i 1 Si v i 1 3 i V G 1 时停止 否则 i 1 转到 2 实例 CMCM94A 公路选址问题 6 3 求最小生成树 背景 筑路选线问题 欲修筑连接 n 个城市的铁路 已知 i 城与 j 城之间的铁路造 价为 Cij 设计一个线路图 使总造价最低 分析 选线问题的数学模型是在连通加权图上求权最小的连通生成子图 显然 权 最小的连通生成子图是一个生成树 即求取连通加权图上的权最小的生成树 这就归结 为最小生成树问题 这个问题可由克罗斯克尔 Kruskal 算法解决 思路 从 边 着手选最小生成树 19 步骤 设 G 为由 m 个节点组成的连通赋权图 1 先把 G 中所有的边按权值大小由小到大重新排列 并取权最小的一条边为树 T 中的边 即选 e1 E 使得 w e1 min 2 从剩下的边中按 1 中的排列取下一条边 若该边与前面已取进 T 中的边构成一个 回路 则舍弃该边 否则也把它取进 T 中 若 e1 e2 ei 已经选好 则从 E e1 e2 ei 中选取 ei 1 使得 G e1 e2 ei ei 1 中无圈 且 w ei 1 min 3 重复步骤 2 直到 T 中有 m 1 条边为止 则 T 为 G 的最小生成树 该算法的复杂度为 O eloge 其中 e 是图 G 中的边数 6 4 模拟退火法原理 模拟退火法 Simulated annealing SA 是模拟热力学中经典粒子系统的降温过程 来求 解极值问题 当孤立粒子系统的温度以足够慢的速度下降时 系统近似处于热力学平衡 状态 最后系统将达到本身的最低能量状态 即基态 这相当于能量函数的全局极小点 其步骤如下 也称为 Metropolis 过程 1 给定初始温度 T0 及初始点 计算该点的函数值 f x 2 随机产生扰动 x 得到新点 x x x 计算新点函数值 f x 及函数值差 f f x f x 3 若 f 0 则接受新点 作为下一次模拟的初始点 4 若 f 0 则计算新点接受概率 产生 0 1 区 间上均匀分布的伪随机数 r r 0 1 如果 p f r 则接受新点作为下一次模拟的初始 点 否则放弃新点 仍取原来的点作为下一次模拟的初始点 6 5 应用举例 1 CMCM91B 通讯网络中的极小生成树 是一个求 STEINER 生成树问题 2 CMCM 97A 题 97 年全国大学生数模竞赛 A 题 零件的参数设计 可以归结为非线性规划模型 由 于目标函数很复杂 且又是一个多维函数 因此求解比较困难 为应用模拟退火法进行 求解 将 7 个自变量的取值范围进行离散化 取步长为 0 0001 这样 所有 7 个变量取 值就组成了一个极为庞大的离散空间 而这个问题变成组合优化模型 这个问题算法的状态调整规则是 每次从 7 个自变量中随机选取 1 4 个 让选