数学建模动态规划理解和心得

-56-

第四章动态规划

§1 引言

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

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

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

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

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

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

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

动态规划的特点及其应用

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

【摘要】

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

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

一、 问题的重述

某国政府要为其牛奶、奶油和奶酪等奶制品定价。所有这些产品都直接或间接的来自国家的原奶生产。原奶首先要分离成脂肪和奶粉两种组合，去掉生产出口产品和农场消费的产品后，余下的共有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

实验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

实验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

第五章 动态规划（Dynamic Programming）

第一节 离散时间系统的动态规划

一 简单例子 行车问题

穷举法：从S到F共有条路径，每条路径共有3次加法。故共有3?8?24，2n?1.(n?1) 次加法。 动态规划法：

首先计算最后阶段的时间最短的路径：x2(3)?F,可以计算出J(x1(3))=4，J(x2(3))=3 再计算第三阶段的最短路径：x1(2)?x2(3)?F可以计算出J(x1(2))+1+3，

J(x2(2))=2+3。只需要计算x1(2)到J(x1(3))，J(x2(3))及x2(2)到J(x1(3))，J(x2(3))的

最短时间。其中J(xi(.))代表xi(.)到F的最短距离。

然后计算第二阶段的最短路径：x2(1)?x1(2)?x2(3)?F,计算

x1(1?)x2?(2J)2x(和(2))x1(1)?x1(2)?J(x1(2))，取小的

J(x1(1))x2(1)?x1(2)?J(x1(2))和x2(1)?x2(2)?J(x2(2))，取小的J(x2(1))

最后计算第一阶段的最短路径：S?x2(1)?x1(2)?x2(3)?F，计算

S?x1(2)?J(x1(1))和S?x2(1)?J(x2(1)

function [p_opt,fval]=dynprog(x,DecisFun,SubObjFun,TransFun,ObjFun) % x为状态变量，一列代表一个阶段的状态

% M_函数DecisFun（k,x)表示由阶段k的状态值x求出相应的允许决策集合 % M_函数SubObjFun（k,x,u)表示阶段k的指标函数

% M_函数TransFun（k,x,u)是状态转移函数，其中x是阶段k的状态值，u是其决策集合 % M_函数ObjFun（v,f)是第k阶段到最后阶段的指标函数，当ObjFun（v,f)=v+f时，输入ObjFun（v,f)可以省略

% 输出p_opt由4列组成，p_opt=[序号组，最优轨线组，最优策略组，指标函数值组]; % 输出fval是列向量，各元素分别表示p_opt各最优策略组对应始端状态x的最优函数值

k=length(x(1,:)); % k为阶段数 x_isnan=~isnan(x);

f_opt=nan*ones(size(x));

% f_opt为不同阶段、状态下的最优值矩阵，初值为非数

d_opt=f_opt;

线性规划

数学建模案例之线性规划 奶制品的生产与销售

2010.10

线性规划

引优化问题及其一般模型：

言

优化问题是人们在工程技术、经济管理和科学研究等领域中 最常遇到的问题之一。例如： 设计师要在满足强度要求等条件下选择材料的尺寸， 使 结构总重量最轻； 公司经理要根据生产成本和市场需求确定产品价格，使所获 利润最高； 调度人员要在满足物质需求和装载条件下安排从各供应点 到需求点的运量和路线，使运输总费用最低； 投资者要选择一些股票,债券下注,使收益最大,而风险最小 …………

线性规划

引

言

一般地，优化模型可以表述如下：

min z f ( x ) s.t . gi ( x ) 0 ,= 1, , i 2, m这是一个多元函数的条件极值问题，其中 x = [ x 1 , x 2 , … , x n ]。

许多实际问题归结出的这种优化模型，但是其决策变量个数 n 和约束条件个数 m 一般较大，并且最优解往往在可行域的边界上取得，这样就不 能简单地用微分法求解，数学规划就是解决这类问题的有效方法。

线性规划

引数学规划模型分类:

言

“数学规划是运筹学和管理科学中应用及其广泛的分支。在许多情况下， 应用数学规划取得的如此成功，以致它的用途

数学建模 非线性规划(xin)

非线性规划 (Nonlinear Programming)第一章 一般的非线性规划问题§1.1 问题概论

(模型) min s .t

f (x)

g i ( x ) 0, i 1,..., m h j ( x ) 0, j 1,..., n1

数学建模 非线性规划(xin)

(两类问题)无约束极值问题与约束极值问题

(一些基本定义)梯度

df df T f ( x) ( ,..., ) dx1 dxn

Hesse矩阵

H ( x)

f11 f m1

f1n f mn

Jaccobi矩阵

f1T F ( x ) f T n 2

数学建模 非线性规划(xin)

§ 1.2 最优解分类 (注：不一定存在)

定义1.2.1 整体(全局)最优解 定义1.2.2 局部最优解 (已有算法基本都是求局部 最优解的)§ 1.3 凸集与凸函数 定义1.3.1 凸集 定义1.3.2 (严格)凸函数 称定义在凸集K上的实值 ，有： 函数f (x)为凸函数，若 x1,x2 K及 01 f ( x1