数学建模动态规划求解

-56-

第四章动态规划

§1 引言

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

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

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

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

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

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

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

实验报告 ----计算科学实验室

1、一奶制品加工厂生产A1,A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，

或者在设备乙上用8小时加工成4公斤A2。

根据市场需求，生产A1,A2能够全部售出，且每公斤 A1获利24元，每公斤A2获利16元。

现加工厂每天能得到50桶牛奶的供应，每天正式工人总劳动时间为480小时， 并且设备甲每天至多能加工 100公斤A1，

设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：

1）若用35元可以买到1桶牛奶，应否做这项投资？若投资，每天最多购买多少桶牛奶？

2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时多少元？

3）由于市场需求变化，公斤A1的获利增加道 30元，是否应改变生产计划？ 2、问题1中给出的A1,A2两种奶制品的生产条件，利润及工厂的“资源”限制全都不便，为增加工厂获利，开发了奶制品的深加工技术：用2小时和3元加工费，可将1公斤A1加工成0.8公斤高级奶制品B1,也可以将1公斤A2加工成0.75公斤高级奶制品 B2，每公斤B1获利44元，每公斤B2获利32元 ，试为该厂制定一个生产销售计划，使每天净利润最

机械工程学院工业工程专业

学号： 姓名：

线性规划问题建模与求解

一．实验目的

1． 掌握线性规划问题建模基本方法。

2． 熟练应用Excel“规划求解”功能对线性规划问题进行建模与求解。

3．掌握线性规划问题的对偶理论和灵敏度分析。

二．实验设备 硬件：PC机。

软件：Microsoft Excel。

三．实验内容

1．建立线性规划问题的数学模型。

2．利用Excel“规划求解”功能对线性规划问题进行建模与求解。 3．根据实验优化结果，进行灵敏度及经济分析。

四．实验步骤

某出版单位有4500个空闲的印刷机时和4000个空闲的装订工时，拟用于下列4种图书的印刷和装订。已知各种书每册所需的印刷和装订工时如表2所示。

表2 印刷和装订工时数据表

工 序 书 印刷 装订 预期利润（千元/千册） 问：

①该出版单位为了实现利润最大化，如何安排4种图书的生产？ ②该单位是否愿意出50元的加班费，让工人加班1小时？

③由于管理工作的进步，使得第1种产品成本每件下降0.2元，此时得最优生产方案是否有变化，总利润是多少？

④出版第2种书的方案之一是降低成本，若第2种书的印刷加装订成本合计每册6元，则第2种书的成本为多少时，

动态规划的特点及其应用

目 录 (点击进入) §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页

【摘要】

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

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

数学建模中运用matlab的具体方法。

数学建模竞赛

数学建模中运用matlab的具体方法。

几种常见的数学方法及软件求解一、曲线拟合及MATLAB软件求解 已知离散点上的数据集 [( x1 , y1 )( x2 , y2 ) ( xn , yn )],

求得一解析函数y=f(x)使y=f(x)在原离散点 xi 上尽可能 接近给定 yi 的值，这一过程叫曲线拟合。最常用的 曲线拟合是最小二乘法曲线拟合，拟合结果可使误差的 平方和最小，即找出使

i 1

n

f ( xi ) yi

2

最小的f(x).

数学建模中运用matlab的具体方法。

格式：p=polyfit(x,y,n). 说明：求出已知数据x,y 的n次拟合多项式f(x)的系 数p,x 必须是单调的。 例1 已知某函数的离散值如表xi yi 0.5 1.75 1.0 2.45 1.5 3.81 2.0 4.80 2.5 7.00 3.0 8.65

求二次拟合多项式. 先画函数离散点的图形 输入命令 ： >> x=[0.5 1.0 1.5 2.0 2.5 3.0]; >> y=[1.75 2.45 3.81 4.80 7.00 8.60]; >> scatter(x,y,5) 结果见图3

天大,考研,运筹学,管理科学与工程

例1 求解下列整数规划的最优解：

maxZ 4x1 5x2 6x3

3x1 4x2 5x3≤10s..t xj≥0 j 1,2,3 ,xj为整数.

解 （1）建立动态规划模型：

阶段变量：将给每一个变量xj赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3. 设状态变量sk表示从第k阶段到第3阶段约束右端最大值，则sj 10. 设决策变量xk表示第k阶段赋给变量xk的值(k 1,2,3). 状态转移方程：s2 s1 3x1,s3 s2 4x2.

阶段指标：u1(s1,x1) 4x1,u2(s2,x2) 5x2,u3(s3,x3) 6x3. 基本方程；

fk(sk) max uk sk,xk fk 1 sk 1 sk k 3,2,1 0≤x3≤

ak

f(s) 0. 44

其中a1 3,a2 4,a3 5. （1） 用逆序法求解： 当k 3时，

f3 s3 max 6x3 f4 s4 maxs

s

3 0≤x3

5

3

0≤x3≤

5

6x3 ,

而s3 0,1,2,3,4,5,6,7,8,9,10 . x 表示不超过x的最大整数。因此，当s3 0,1,2,3,

中国传媒大学 2010 学年第 一 学期

数学建模与数学实验 课程

数学建模与数学实验

题 目 Pristine湖污染问题的建模与求解

学生姓名 学 号 班 级 学生所属学院 任课教师 教师所属学院 成 绩

Pristine湖污染问题的建模与求解

摘要

本文讨论了湖水污染浓度变化趋势的预测问题。 通过分析水流输入输出湖泊的过程，建立了湖水污染浓度随时间变化的含参变量的微分方程模型，在河水污染浓度恒定和自然净化速率呈线性关系的情况下，求得其精确解，带入具体数据得到结论：在PCA声称的河水污染浓度下，湖的环境不会恶化；在工作

2.关于“规划求解”

2.1 规划求解介绍

“规划求解”是Excel中的一个加载宏，借助“规划求解”，可求得工作表上某个单元格（被称为目标单元格）中公式（公式:单元格中的一系列值、单元格引用、名称或运算符的组合，可生成新的值。公式总是以等号（=）开始）的最优值。“规划求解”将对直接或间接目标单元格中公式相关联的一组单元格中的数值进行调整，最终在目标单元格公式中求得期望的结果。“规划求解”通过调整所指定的可更改的单元格（可变单元格）中的值，从目标单元格公式中求得所需的结果。在创建模型过程中，可以对“规划求解”中的可变单元格数值应用约束条件（约束条件：“规划求解”中设置的限制条件。可以将约束条件应用于可变单元格、目标单元格或其它与目标单元格直接或间接相关的单元格。而且约束条件可以引用其它影响目标单元格公式的单元格。使用“规划求解”可通过更改其它单元格来确定某个单元格的最大值或最小值。）

Microsoft Excel的“规划求解”工具取自德克萨斯大学奥斯汀分校的Leon Lasdon 和克里夫兰州立大学的Allan Waren共同开发的Generalized Reduced Gradient(GRG2)非线性最优化代码。线性和整数规划问题取自Fr

一、 问题的重述

某国政府要为其牛奶、奶油和奶酪等奶制品定价。所有这些产品都直接或间接的来自国家的原奶生产。原奶首先要分离成脂肪和奶粉两种组合，去掉生产出口产品和农场消费的产品后，余下的共有60万吨脂肪和70万吨奶粉，可用于生产牛奶、奶油和两种奶酪，供国内全年消费。其中，各种产品的百分比以及去年销售量和价格分别见表(表1、表2)

表一 产品\\成分 脂肪 奶粉 水 牛奶 奶油 奶酪1 奶酪2

表二 产品 牛奶 奶油 奶酪1 奶酪2 消费（千吨） 4820 320 210 70 价格（元/吨） 297 720 1050 815 1、价格的变化会影响消费需求。为表现这方面的规律，定义需求的价格伸缩性 E：

E=需求降低百分数/价格提高百分数；

各种产品的E值，可以据往年的价格和需求变化情况的统计数据，用数理统计方法求出。

2、两种奶酪的需求，随它们价格的相对变化，在某种程度上可以相互替代。表现这一规律要用需求关于价格的交叉伸缩性EAB其定义为：

EAB=A需求提高百分数/B价格提高百分数。

3、已知四种产品的E值分别为：0.4，2.7，1.1，0.4 以及EAB=0.1，EBA=0.4

4 80 35 25 9 2 30 40 87

第七章 动态规划

习题七

7.1计算如图所示的从A到E的最短路线及其长度（单位：km）：

（1） 用逆推解法； （2） 用标号法。 3 B1 4 D1 2 3 4 C1 3 A 2 B2 1 1 5 D2 1 E 3 3 C2 4 2 5 3 1 B3 5 3 D3

7.2 用动态规划方法求解下列问题

（1） max z ＝x12x2 x33

x1＋x2＋x3 ≤6

xj≥0 （j＝1,2,3）

（2）min z ＝ 3x12＋4x22 ＋x32

x1x2 x3 ≥ 9

xj ≥0 （j＝1,2,3）

7.3 利用动态规划方法证明平均值不等式：

(x1?x2???xn)?(x1x2?xn)n

n设xi ≥0，i＝1，2，?，n。

7.4 考虑一个有m个产地和n个销地的运输问题。设ai（i＝1，2，?，m）为产地i可发运的物资数，bj（j＝1，2