数学建模动态规划模型例题

-56-

第四章动态规划

§1 引言

1.1 动态规划的发展及研究内容

动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪50 年代初R. E. Bellman 等人在研究多阶段决策过 程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of

optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程 优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这 是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动 态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时

间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为 多阶段决策过程，也可以用动态规划方法方便地求解。

应指出，动态规划是求解某类问题的一种方法，是

1、生产库存问题

例 某厂在年末估计，下年4个季度市场对该厂某产品的需求量均为dk=3 (k=1,2,3,4)，该厂每季度生产此产品的能力为bk=5 (k=1,2,3,4,)。每季度生产这种产品的固定成本为F=13（不生产时为0），每一产品的单位变动成本为C=2。本季度产品如不能售出，则需发生库存费用g=1/件，仓库能贮存产品的最大数量Ek=4。试问如何安排4个季度的生产，以保证在满足市场需求的前提下，使生产和库存总量用最小?

解：首先分析一下这类问题。设xk—第k季度的计划生产量，sk—第k季度初的库存，?1,xk?0，可以得到数学模型： yk??0,x?0k?4?13yk?2xk?sk?1?min?k?1?s.t.sk?1?sk?xk?3??。 ?xk?(3?4)yk?xk?5??sk?4??xk,sk?0,yk?0or1k?1,2,3,4??显然，这个问题是一个混合整数规划。但由于这类问题可以按时间先后顺序分成四个阶段，故可用动态规划方法求解。

(1) 将每个季度看作一个阶段，就有一个四阶段的决策问题。

(2)Sk--第k季度初的仓库库存量，在问题中，s1=s5=0, 0?sk?E?3,k=2,3,4。 (3) xk--第k季度的生产

实验05 数学规划模型㈡（2学时）

（第4章 数学规划模型）

1.（求解）汽车厂生产计划（LP，整数规划IP）p101~102

(1) (LP)在模型窗口中输入以下线性规划模型

max z = 2x1 + 3x2 + 4x3 s.t. 1.5x1 + 3x2 + 5x3 ≤ 600

280x1 + 250x2 + 400x3 ≤ 60000

x1, x2, x3 ≥ 0

并求解模型。

★(1) 给出输入模型和求解结果（见[101]）：

model: TITLE汽车厂生产计划（LP）; !文件名：p101.lg4; max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3<600; 280*x1+250*x2+400*x3<60000; end (2) (IP)在模型窗口中输入以下整数规划模型

max z = 2x1 + 3x2 + 4x3 s.t. 1.5x1 + 3x2 + 5x3 ≤ 600

280x1 + 250x2 + 400x3 ≤ 60000

x1, x2, x3均为非负整数 并求解模型。

LINGO函数@gin见提示。

★(2) 给出输入模型和求解结果（见[102]模型、结果）：

model: TITLE汽车厂生产计划（IP）; 1

!文件名：p102.lg4; max=2*x1+3*x2+4*x3; 1.5*x1+3*x

实验05 数学规划模型㈡（2学时）

（第4章 数学规划模型）

1.（求解）汽车厂生产计划（LP，整数规划IP）p101~102

(1) (LP)在模型窗口中输入以下线性规划模型

max z = 2x1 + 3x2 + 4x3 s.t. 1.5x1 + 3x2 + 5x3 ≤ 600

280x1 + 250x2 + 400x3 ≤ 60000

x1, x2, x3 ≥ 0

并求解模型。

★(1) 给出输入模型和求解结果（见[101]）：

model: TITLE汽车厂生产计划（LP）; !文件名：p101.lg4; max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3<600; 280*x1+250*x2+400*x3<60000; end (2) (IP)在模型窗口中输入以下整数规划模型

max z = 2x1 + 3x2 + 4x3 s.t. 1.5x1 + 3x2 + 5x3 ≤ 600

280x1 + 250x2 + 400x3 ≤ 60000

x1, x2, x3均为非负整数

1

并求解模型。

LINGO函数@gin见提示。

★(2) 给出输入模型和求解结果（见[102]模型、结果）：

model: TITLE汽车厂生产计划（IP）; !文件名：p102.lg4; max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3

一、人体重变化

某人的食量是10467焦/天，最基本新陈代谢要自动消耗其中的5038焦/天。每天的体育运动消耗热量大约是69焦/（千克? 天）乘以他的体重（千克）。假设以脂肪形式贮存的热量100% 地有效，而1千克脂肪含热量41868焦。试研究此人体重随时间变化的规律。 一、 问题分析

人体重W（t）随时间t变化是由于消耗量和吸收量的差值所引起的，假设人体重随时间的变化是连续变化过程，因此可以通过研究在△t时间内体重W的变化值列出微分方程。

二、 模型假设

1、 以脂肪形式贮存的热量100%有效

2、 当补充能量多于消耗能量时，多余能量以脂肪形式贮存 3、 假设体重的变化是一个连续函数 4、 初始体重为W0

三、 模型建立

假设在△t时间内：

体重的变化量为W（t+△t）-W(t)；

身体一天内的热量的剩余为（10467-5038-69*W（t）） 将其乘以△t即为一小段时间内剩下的热量；

转换成微分方程为：d[W(t+△t)-W(t)]=(10467-5038-69*W(t))dt；

四、 模型求解

d(5429-69W)/(5429-69W)=-69dt/41686 W(0)=W0 解得：

(-69t/41686)

5429-69

中国人口增长预测模型的建立与分析

摘要

针对我国人口发展过程中出现的老龄化进程加快，出生人口性别比持续升高，乡村人口城镇化的新特点，我们基于LESLIE 矩阵，着重考虑城镇与乡村间的人口迁移及女性人口比例变化对我国人口增长的影响，经过两次改进建立了便于计算机求解的差分方程模型，对我国2005年以后45年的人口增长进行了预测。随后利用时间段参数设置法，对差分方程模型又进行了一次改进。然后运用等维灰色系统预测法对该差分方程模型的中短期预测进行了检验，同时根据2001年人口基本数据运用此模型对2001年～2005年进行了预测，并用实际数据对预测结果进行了检验。

我们将预测区间分为2006～2020年、2021～2035年、2036～2050年三个区间，以量化短期、中期与长期。通过调整模型中相关参数及输入条件，定量地分析了男女性别比例、老龄化和乡村人口城镇化对我国人口增长的影响。预测结果表明，从短期来看，我国的出生性别比变化不明显，将在短期内维持基本不变，老龄化进程在15年内在上升了8个百分点，人口扶养比持续升高，这将加重我国的人口压力，乡村人口城镇化水平进展缓慢；从中期来看，总人口性别比将保持在1与1.1之间，老龄化进程将呈线性增加趋势，乡村人口城镇化水

动态规划的特点及其应用

目 录 (点击进入) §1动态规划的本质 §1.1多阶段决策问题 §1.2阶段与状态 §1.3决策和策略 §1.4最优化原理与无后效性 §1.5最优指标函数和规划方程 §2动态规划的设计与实现 §2.1动态规划的多样性 §2.2动态规划的模式性 §2.3动态规划的技巧性 §3动态规划与一些算法的比较 §3.1动态规划与递推 §3.2动态规划与搜索 §3.3动态规划与网络流 §4结语 【附录：部分试题与源程序】 1.“花店橱窗布置问题”试题 2.“钉子与小球”试题 3.例2“花店橱窗布置问题”方法1的源程序 4.例2“花店橱窗布置问题”方法2的源程序 5.例3“街道问题”的扩展 6.例4“mod 4最优路径问题”的源程序 7.例5“钉子与小球”的源程序 8.例6的源程序,“N个人的街道问题” 【参考文献】 第 1 页 共 29页

【摘要】

动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。

文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三

教 案

课题 名称 第一节 数学建模(模型)概述（上） 进 度 时 数 2 教学目标 应知应会重点难点本课程主要内容、学习目标、学习方法 数学建模的基本概念 简单数学模型的分析 数学模型概念的理解 数学模型的建立 讲授 教学教学资源 内容 教材 教具 时间分配 30’ 15’ 45’ 教材分析教学方法 一、数学模型的概念 二、一个简单的数学模型实例 实例分析、求解 第一节 数学建模(模型)概述 教学后记作业

1

内容 备 注 第5章 数学建模简介 最近几十年，随着各种科学技术尤其是计算机技术的发展，数学正以其神奇的魅力进入各种领域。它的功效显著，其解决问题的卓越能力甚至使它渗透到一些非物理领域，诸如交通、生态、社会学等。数学作为一种“技术”，日益受到人们的重视。 在新的形式下，大学的数学教学也面临着改革。为了使毕业生尽快地适应工作岗位，能够较好地解决各种实际问题，数学课程的设置不能仅仅只为了教会学生们一些数学的定理和方法，更重要的是，要教会他们怎样运用手中的数学武器去解决实际中的问题，这便是数学建模这门课程的目的。作为一门新型的学科，数学建模正日益焕发出其独特的魅力。 第一节 数学建

2010大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. LI 2. JIANG

逻辑分析,构建数学模型,适合非专业学生

题目：体检时间安排的合理性讨论

某高校教职工（现教职工1604人）每二年到医院体检中心体检。体检时间早晨7：00——8：30，单位安排见体检安排表。体检项目：内科、外科、眼科、五官科、血压、血常规、胸片、心电图、腹部B超等，体检各项所需时间（不含等待时间，下同）：内科1-2分钟、外科1-2分钟、眼科1-3分钟、五官科1-3分钟、血压2-3分钟、血常规（抽血）1-2分钟、胸片1-2分钟、心电图1-3分钟、腹部B超2-5分钟。用于体检的医生（设备）数量：内科2个、外科1个、眼科1个、五官科1个、血压1个、血常规（抽血）2个、胸片2个、心电图2个、腹部B超3个。 体检程序：体检者体检当天在体检中心取体检表（所需时间1-2分钟，有两个窗口），再按规定的体检项目自行前往体检各科室进行相应检查（体检项目无先后顺序），体检结束后将体检表交体检中心服务台。

假定教职工一般在7：00——8：00到中心体检，且每个人当天做完所有（或部分）检查，不会改天再来；因有课、有事不能按照单位安排时间内体检的，则在学校体检时间范围内自行选择体检时间；每个机关处室人数大约8-12人，后勤管理处、后勤服务总公司大约120人。

请你建立模型分析在规