当前位置:首页 >> 理学 >>

动态规划习题


第七章

动态规划

规划问题的最终目的就是确定各决策变量的取值, 以使目标函数达到极大或极小。 在线 性规划和非线性规划中,决策变量都是以集合的形式被一次性处理的;然而,有时我们也会 面对决策变量需分期、 分批处理的多阶段决策问题。 所谓多阶段决策问题是指这样一类活动 过程: 它可以分解为若干个互相联系的阶段, 在每一阶段分别对应着一组可供选取的决策集 合; 即构成过程的每个阶段都需要进行一次决策的决策问题。 将各个阶段的决策综合起来构 成一个决策序列,称为一个策略。显然,由于各个阶段选取的决策不同,对应整个过程可以 有一系列不同的策略。当过程采取某个具体策略时,相应可以得到一个确定的效果,采取不 同的策略,就会得到不同的效果。多阶段的决策问题,就是要在所有可能采取的策略中选取 一个最优的策略,以便得到最佳的效果。动态规划(dynamic programming)同前面介绍过 的各种优化方法不同,它不是一种算法,而是考察问题的一种途径。动态规划是一种求解多 阶段决策问题的系统技术,可以说它横跨整个规划领域(线性规划和非线性规划) 。当然, 由于动态规划不是一种特定的算法, 因而它不象线性规划那样有一个标准的数学表达式和明 确定义的一组规则,动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中, 有些问题对阶段的划分具有明显的时序性,动态规划的“动态”二字也由此而得名。动态规 划的主要创始人是美国数学家贝尔曼(Bellman) 。20 世纪 40 年代末 50 年代初,当时在兰 德公司(Rand Corporation)从事研究工作的贝尔曼首先提出了动态规划的概念。1957 年贝 尔曼发表了数篇研究论文,并出版了他的第一部著作《动态规划》 。该著作成为了当时唯一 的进一步研究和应用动态规划的理论源泉。 1961 年贝尔曼出版了他的第二部著作, 并于 1962 年同杜瑞佛思(Dreyfus)合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广 这一技术的同时, 其他一些学者也对动态规划的发展做出了重大的贡献, 其中最值得一提的 是爱尔思(Aris)和梅特顿(Mitten) 。爱尔思先后于 1961 年和 1964 年出版了两部关于动态 规划的著作,并于 1964 年同尼母霍思尔(Nemhauser) 、威尔德(Wild)一道创建了处理分 枝、 循环性多阶段决策系统的一般性理论。 梅特顿提出了许多对动态规划后来发展有着重要 意义的基础性观点,并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、 经济管理等社会各个领域都有着广泛的应用, 并且获得了显著的 效果。在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问 题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等,是经济管理中 一种重要的决策技术。 许多规划问题用动态规划的方法来处理, 常比线性规划或非线性规划 更有效。特别是对于离散的问题,由于解析数学无法发挥作用,动态规划便成为了一种非常 有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划; 也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要 介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用。

§7.1

动态规划的基本理论

1.1 多阶段决策过程的数学描述 有这样一类活动过程, 其整个过程可分为若干相互联系的阶段, 每一阶段都要作出相应 的决策,以使整个过程达到最佳的活动效果。任何一个阶段(stage,即决策点)都是由输 入(input) 、决策(decision) 、状态转移律(transformation function)和输出(output) 构成的,如图 7-1(a)所示。其中输入和输出也称为状态(state) ,输入称为输入状态, 输出称为输出状态。





dn













Sn

Stage n

Sn+1

状态转移 (a) 图 7-1

gn = r(Sn,dn) (b )

由于每一阶段都有一个决策,所以每一阶段都应存在一个衡量决策效益大小的指标函 数,这一指标函数称为阶段指标函数,用 gn 表示。显然 gn 是状态变量 Sn 和决策变量 dn 的函 数,即 gn = r(Sn,dn) ,如图 7-1(b)所示。显然,输出是输入和决策的函数,即:

S n?1 ? f (S n , d n )

(7-1)

式(7-1)即为状态转移律。在由 N 个阶段构成的过程里,前一个阶段的输出即为后一个阶 段的输入。 1.2 动态规划的基本概念 动态规划的数学描述离不开它的一些基本概念与符号,因此有必要在介绍多阶段决策 过程的数学描述的基础上,系统地介绍动态规划的一些基本概念。 1. 阶段(stage) 阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量,常用 k 来表示。 阶段的划分一般是根据时间和空间的自然特征来进行的, 但要便于将问题的过程转化为多 阶段决策的过程。对于具有 N 个阶段的决策过程,其阶段变量 k=1,2,?,N。 2. 状态(state) 状态表示每个阶段开始所处的自然状况或客观条件,它描述了研究问题过程的状况。 状态既反映前面各阶段系列决策的结局, 又是本阶段决策的一个出发点和依据; 它是各阶段 信息的传递点和结合点。各阶段的状态通常用状态变量 Sk 来加以描述。作为状态应具有这 样的性质: 如果某阶段状态给定后, 则该阶段以后过程的发展不受此阶段以前各阶段状态的 影响。换句话说,过程的历史只能通过当前的状态来影响未来,当前的状态是以往历史的一 个总结。这个性质称为无后效性(the future is independent of the past)或健忘性(the process is forgetful) 。 3. 决策(decision) 决策是指决策者在所面临的若干个方案中做出的选择。决策变量 dk 表示第 k 阶段的决 策。决策变量 dk 的取值会受到状态 Sk 的某种限制,用 Dk(Sk)表示第 k 阶段状态为 Sk 时决 策变量允许的取值范围,称为允许决策集合,因而有 dk(Sk)?Dk(Sk) 。 4. 状态转移律(transformation function) 状态转移律是确定由一个状态到另一状态演变过程的方程,这种演变的对应关系记为 = Tk(Sk , dk) 。

Sk+1

5. 策略(policy)与子策略(sub-policy) 由所有阶段决策所组成的一个决策序列称为一个策略,具有 N 个阶段的动态规划问题 的策略可表示为:

{d1 (S1 ), d 2 (S 2 ),?, d N (S N )}
从某一阶段开始到过程终点为止的一个决策子序列,称为过程子策略或子策略。从第 k 个阶段起的一个子策略可表示为:

{d k (S k ), d k ?1 (S k ?1 ),?, d N (S N )}
6. 指标函数 指标函数有阶段指标函数和过程指标函数之分。阶段指标函数是对应某一阶段决策的 效率度量,用 gk = r(Sk,dk)来表示;过程指标函数是用来衡量所实现过程优劣的数量指 标,是定义在全过程(策略)或后续子过程(子策略)上的一个数量函数,从第 k 个阶段起 的一个子策略所对应的过程指标函数常用 Gk,N 来表示,即:

Gk , N ? R(S k , d k , S k ?1 , d k ?1 ,?, S N , d N )
构成动态规划的过程指标函数,应具有可分性并满足递推关系;即:

Gk , N ? g k ? Gk ?1, N
这里的 ? 表示某种运算,最常见的运算关系有如下二种: (1) 过程指标函数是其所包含的各阶段指标函数的“和” ,即:

Gk , N ? ? g j
j ?k

N

于是

Gk , N ? g k ? Gk ?1, N
(2) 过程指标函数是其所包含的各阶段指标函数的“积” ,即:

Gk , N ? ? g j
j ?k

N

于是

Gk , N ? g k ? Gk ?1, N
7. 最优指标函数 从第 k 个阶段起的最优子策略所对应的过程指标函数称为最优指标函数,可以用式 (7-2)加以表示:

f k (S k ) ? opt{g k ? g k ?1 ? ? ? g N }
dk ~ N

(7-2)

其中“opt”是最优化“optimization”的缩写,可根据题意取最大“max”或最小“min” 。 在不同的问题中,指标函数的含义可能是不同的,它可能是距离、利润、成本、产量或资源 量等。

1.3 动态规划的数学模型 动态规划的数学模型除包括式(7-2)外,还包括阶段的划分、各阶段的状态变量和决 策变量的选取、允许决策集合和状态转移律的确定等。 如何获得最优指标函数呢?一个 N 阶段的决策过程,具有如下一些特性: (1) 刚好有 N 个决策点; (2) 对阶段 k 而言,除了其所处的状态 S k 和所选择的决策 d k 外,再没有任何其它 因素影响决策的最优性了; (3) 阶段 k 仅影响阶段 k ? 1 的决策,这一影响是通过 S k ?1 来实现的; (4) 贝尔曼(Bellman)最优化原理:在最优策略的任意一阶段上,无论过去的状态 和决策如何,对过去决策所形成的当前状态而言,余下的诸决策必须构成最优 子策略。 根据贝尔曼(Bellman)最优化原理,可以将式(7-2)表示为递推最优指标函数关系式 (7-3)或式(7-4) :

f k (S k ) ? opt{g k ? g k ?1 ? ? ? g N } ? opt{g k ? f k ?1 (S k ?1 )}
dk ~ N dk

(7-3) (7-4)

f k (S k ) ? opt{g k ? g k ?1 ? ? ? g N } ? opt{g k ? f k ?1 (S k ?1 )}
dk ~ N dk

利用式(7-3)和式(7-4)可表示出最后一个阶段(第 N 个阶段,即 k=N)的最优指标 函数:

f N (S N ) ? opt{g N ? f N ?1 (S N ?1 )}
dN

(7-5) (7-6)

f N ( S N ) ? opt{g N ? f N ?1 ( S N ?1 )}
dN

其中 f N ?1 (S N ?1 ) 称为边界条件。一般情况下,第 N 阶段的输出状态 S N ?1 已经不再影响本过 程的策略, 即式 (7-5) 中的边界条件 f N ?1 (S N ?1 ) ? 0 , 式 (7-6) 中的边界条件 f N ?1 (S N ?1 ) ? 1; 但当问题第 N 阶段的输出状态 S N ?1 对本过程的策略产生某种影响时, 边界条件 f N ?1 (S N ?1 ) 就要根据问题的具体情况取适当的值,这一情况将在后续例题中加以反映。 已知边界条件 f N ?1 (S N ?1 ) ,利用式(7-3)或式(7-4)即可求得最后一个阶段的最优 指标函数 f N (S N ) ;有了 f N (S N ) ,继续利用式(7-3)或式(7-4)即可求得最后两个阶段 的最优指标函数 f N ?1 (S N ?1 ) ;有了 f N ?1 (S N ?1 ) ,进一步又可以求得最后三个阶段的最优指 标函数 f N ?2 (S N ?2 ) ; 反复递推下去, 最终即可求得全过程 N 个阶段的最优指标函数 f1 ( S1 ) , 从而使问题得到解决。 由于上述最优指标函数的构建是按阶段的逆序从后向前进行的, 所以 也称为动态规划的逆序算法。 通过上述分析可以看出, 任何一个多阶段决策过程的最优化问题, 都可以用非线性规划 (特殊的可以用线性规划)模型来描述;因此,从原则上讲,一般也可以用非线性规划(或 线性规划)的方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什么 局限性呢? 动态规划的优点:第一,求解更容易、效率更高。动态规划方法是一种逐步改善法,它 把原问题化成一系列结构相似的最优化子问题,而每个子问题的变量个数比原问题少得多, 约束集合也简单得多,故较易于确定最优解。第二,解的信息更丰富。非线性规划(或线性 规划)的方法是对问题的整体进行一次性求解的,因此只能得到全过程的解;而动态规划方

法是将过程分解成多个阶段进行求解的, 因此不仅可以得到全过程的解, 同时还可以得到所 有子过程的解。 动态规划的缺点:第一,没有一个统一的标准模型。由于实际问题不同,其动态规划 模型也就各有差异,模型构建存在一定困难。第二,应用条件苛刻。由于构造动态规划模型 状态变量必须满足“无后效性”条件,这一条件不仅依赖于状态转移律,还依赖于允许决策 集合和指标函数的结构,不少实际问题在取其自然特征作为状态变量时并不满足这一条件, 这就降低了动态规划的通用性。第三,状态变量存在“维数障碍” 。最优指标函数 f k ( S k ) 是 状态变量的函数, 当状态变量的维数增加时, 最优指标函数的计算量将成指数倍增长; 因此, 无论是手工计算还是电算“维数障碍”都是无法完全克服的。

§7.2

确定性动态规划问题

确定性动态规划问题即阶段的输出状态完全由其输入状态和决策所决定的动态规划问 题。确定性动态规划解决的问题可能包含经济管理的方方面面,可以是最短路线问题,可以 是资源配置问题,也可以是其他的规划优化问题。最短路线问题直观、具体地演示了动态规 划的基本概念和基本步骤;因此,让我们首先来分析一下最短路线问题。 2-1 最短路线问题 [例 7-1] 美国黑金石油公司(The Black Gold Petroleum Company)最近在阿拉斯加 (Alaska)的北斯洛波(North Slope)发现了大的石油储量。为了大规模开发这一油田, 首先必须建立相应的输运网络, 使北斯洛波生产的原油能运至美国的 3 个装运港之一。 在油 田的集输站(结点 C)与装运港(结点 P1、P2、P3)之间需要若干个中间站,中间站之间的 联通情况如图 7-2 所示,图中线段上的数字代表两站之间的距离(单位:10 千米) 。试确定 一最佳的输运线路,使原油的输送距离最短。 解: 最短路线有一个重要性质, 即如果由起点 A 经过 B 点和 C 点到达终点 D 是一条最短 路线,则由 B 点经 C 点到达终点 D 一定是 B 到 D 的最短路(贝尔曼最优化原理) 。此性质用 反证法很容易证明,因为如果不是这样,则从 B 点到 D 点有另一条距离更短的路线存在,不 妨假设为 B—P—D;从而可知路线 A—B—P—D 比原路线 A—B—C—D 距离短,这与原路线 A —B—C—D 是最短路线相矛盾,性质得证。 根据最短路线的这一性质, 寻找最短路线的方法就是从最后阶段开始, 由后向前逐步递 推求出各点到终点的最短路线, 最后求得由始点到终点的最短路; 即动态规划的方法是从终 点逐段向始点方向寻找最短路线的一种方法。 按照动态规划的方法, 将此过程划分为 4 个阶 段,即阶段变量 k ? 1,2,3,4 ;取过程在各阶段所处的位置为状态变量 S k ,按逆序算法求解。 10 8 M11 12
C

M31 6 4

8
P1

M21 6

7 M32 7 5 7 M33 4

6 M22

9

3 7 6 5
P2

10 M12

9 11 M23

11

6 M34 k=3

3 4 k=4

P3

k=1

k=2

当 k ? 4 时: 由结点 M31 到达目的地有两条路线可以选择,即选择 P1 或 P2;故:

?8? f 4 ( S 4 ? M 31 ) ? min? ? ? 6 ?6?
?4 ? ? ? f 4 ( S 4 ? M 32 ) ? min?3? ? 3 ?7 ? ? ? ?7 ? ? ? f 4 ( S 4 ? M 33 ) ? min?6 ? ? 5 ?5 ? ? ?

选择 P2

由结点 M32 到达目的地有三条路线可以选择,即选择 P1、P2 或 P3;故:

选择 P2

由结点 M33 到达目的地也有三条路线可以选择,即选择 P1、P2 或 P3;故:

选择 P3

由结点 M34 到达目的地有两条路线可以选择,即选择 P2 或 P3;故:

?3? f 4 ( S 4 ? M 34 ) ? min? ? ? 3 ?4?

选择 P2

当 k ? 3 时: 由结点 M21 到达下一阶段有三条路线可以选择,即选择 M31、M32 或 M33;故:

?10 ? 6? ? ? f 3 ( S 3 ? M 21 ) ? min? 7 ? 3 ? ? 10 ?6?5? ? ? ?9 ? 6? ? ? f 3 ( S 3 ? M 22 ) ? min?7 ? 3? ? 10 ?5 ? 5? ? ? ?11 ? 3? ? ? f 3 ( S 3 ? M 23 ) ? min? 4 ? 5 ? ? 9 ?6?3? ? ?
当 k ? 2 时:

选择 M32

由结点 M22 到达下一阶段也有三条路线可以选择,即选择 M31、M32 或 M33;故:

选择 M32 或 M33

由结点 M23 到达下一阶段也有三条路线可以选择,即选择 M32、M33 或 M34;故:

选择 M33 或 M34

由结点 M11 到达下一阶段有两条路线可以选择,即选择 M21 或 M22;故:

?8 ? 10? f 2 (S 2 ? M 11 ) ? min? ? ? 16 ?6 ? 10? ?9 ? 10? f 2 (S 2 ? M 12 ) ? min? ? ? 19 ?11? 9 ?

选择 M22

由结点 M12 到达下一阶段也有两条路线可以选择,即选择 M22 或 M23;故: 选择 M22

当 k ? 1 时: 由结点 C 到达下一阶段有两条路线可以选择,即选择 M11 或 M12;故:

?12 ? 16? f1 ( S1 ? C ) ? min? ? ? 28 ?10 ? 19?

选择 M11

从而通过顺序(计算的反顺序)追踪(黑体标示)可以得到两条最佳的输运线路:C— M11—M22—M32—P2;C—M11—M22—M33—P3。最短的输送距离是 280 千米。 2-2 资源分配问题 所谓资源分配问题, 就是将一定数量的一种或若干种资源 (如原材料、 机器设备、 资金、 劳动力等)恰当地分配给若干个使用者,以使资源得到最有效地利用。设有 m 种资源,总量 分别为 bi(i = 1,2,?,m) ,用于生产 n 种产品,若用 xij 代表用于生产第 j 种产品的第 i 种资源的数量(j = 1,2,?,n) ,则生产第 j 种产品的收益是其所获得的各种资源数量的函 数,即 gj = f(x1j,x2j,?, xmj) 。由于总收益是 n 种产品收益的和,此问题可用如下静态模 型加以描述:

max z ? ? g j
j ?1

n

?x
j ?1

n

ij

? bi

(i ? 1,2,?, m) (i ? 1,2,?, m; j ? 1,2,?, n)

xij ? 0

若 xij 是连续变量,当 gj = f(x1j,x2j,?, xmj)是线性函数时,该模型是线性规划模型; 当 gj = f(x1j,x2j,?, xmj)是非线性函数时,该模型是非线性规划模型。若 xij 是离散变量 或(和)gj = f(x1j,x2j,?, xmj)是离散函数时,此模型用线性规划或非线性规划来求解都 将是非常麻烦的。然而在此情况下,由于这类问题的特殊结构,可以将它看成为一个多阶段 决策问题,并利用动态规划的递推关系来求解。 本教材只考虑一维资源的分配问题,设状态变量 Sk 表示分配于从第 k 个阶段至过程最 终(第 N 个阶段)的资源数量,即第 k 个阶段初资源的拥有量;决策变量 xk 表示第 k 个阶 段资源的分配量。于是有状态转移律:

S k ?1 ? S k ? xk
允许决策集合:

Dk (S k ) ? {xk | 0 ? xk ? S k }
最优指标函数(动态规划的逆序递推关系式) :

f k ( S k ) ? max {g k ( x k ) ? f k ?1 ( S k ?1 )}
0 ? xk ? S k

(k ? N , N ? 1, N ? 2,?,1)

f N ?1 (S N ?1 ) ? 0
利用这一递推关系式,最后求得的 f1 ( S1 ) 即为所求问题的最大总收益,下面来看一个 具体的例子。 [例 7-2] 某公司拟将 500 万元的资本投入所属的甲、乙、丙三个工厂进行技术改造, 各工厂获得投资后年利润将有相应的增长, 增长额如表 7-1 所示。 试确定 500 万元资本的分 配方案,以使公司总的年利润增长额最大。 表 7-1
投资额 甲 乙 丙 100 万元 200 万元 300 万元 400 万元 500 万元

30 50 40

70 100 60

90 110 110

120 110 120

130 110 120

解:将问题按工厂分为三个阶段 k ? 1,2,3 ,设状态变量 S k ( k ? 1,2,3 )代表从第 k 个 工厂到第 3 个工厂的投资额,决策变量 xk 代表第 k 个工厂的投资额。于是有状态转移率

S k ?1 ? S k ? xk 、允许决策集合 Dk (S k ) ? {xk | 0 ? xk ? S k } 和递推关系式:
f k ( S k ) ? max {g k ( x k ) ? f k ?1 ( S k ? x k )}
0? xk ? S k

(k ? 3,2,1)

f 4 (S 4 ) ? 0
当 k ? 3 时:

f 3 ( S 3 ) ? max {g 3 ( x3 ) ? 0} ? max {g 3 ( x3 )}
0? x3 ? S3 0? x3 ? S 3

? 于是有表 7-2,表中 x3 表示第三个阶段的最优决策。

表 7-2

(单位:百万元) 2 2 0.6 3 3 1.1 4 4 1.2 5 5 1.2

S3
? x3

0 0 0

1 1 0.4

f 3 (S 3 )

当 k ? 2 时:

f 2 ( S 2 ) ? max {g 2 ( x 2 ) ? f 3 ( S 2 ? x2 )}
0? x2 ? S 2

于是有表 7-3。 表 7-3 (单位:百万元)
x2

g2(x2)+f3(s2 - x2)
0 0+0 0+0.4 0+0.6 0+1.1 0+1.2 0+1.2 当 k ? 1 时: 0.5+0 0.5+0.4 0.5+0.6 0.5+1.1 0.5+1.2 1.0+0 1.0+0.4 1.0+0.6 1.0+1.1 1.1+0 1.1+0.4 1.1+0.6 1.1+0 1.1+0.4 1.1+0 1 2 3 4 5

S2
0 1 2 3 4 5

f 2 (S 2 )
0 0.5 1.0 1.4 1.6 2.1

? x2

0 1 2 2 1,2 2

f1 ( S1 ) ? max {g1 ( x1 ) ? f 2 ( S1 ? x1 )}
0? x1 ? S1

于是有表 7-4。 表 7-4
x1

g1(x1)+f2(s1 – x1)
0 0+2.1 1 0.3+1.6 2 0.7+1.4 3 0.9+1.0 4 1.2+0.5 5 1.3+0

S1
5

f1 ( S1 )
2.1

? x1

0,2

然后按计算表格的顺序反推算,可知最优分配方案有两个: (1)甲工厂投资 200 万元, 乙工厂投资 200 万元,丙工厂投资 100 万元; (2)甲工厂没有投资,乙工厂投资 200 万元, 丙工厂投资 300 万元。按最优分配方案分配投资(资源) ,年利润将增长 210 万元。 这个例于是决策变量取离散值的一类分配问题, 在实际问题中, 相类似的问题还有销售 店的布局(分配)问题、设备或人力资源的分配问题等。在资源分配问题中,还有一种决策 变量为连续变量的资源分配问题,请见例 7-3。 [例 7-3] 机器负荷分配问题。某种机器可在高低两种不同的负荷下进行生产,设机器 在高负荷下生产的产量(件)函数为 g1 ? 8x ,其中 x 为投入高负荷生产的机器数量,年度 完好率 ? ? 0.7 (年底的完好设备数等于年初完好设备数的 70%) ;在低负荷下生产的产量 (件)函数为 g 2 ? 5 y ,其中 y 为投入低负荷生产的机器数量,年度完好率 ? ? 0.9 。假定 开始生产时完好的机器数量为 1000 台,试问每年应如何安排机器在高、低负荷下的生产, 才能使 5 年生产的产品总量最多? 解:设阶段 k 表示年度( k ? 1,2,3,4,5 ) ;状态变量 S k 为第 k 年度初拥有的完好机器数 量(同时也是第 k ? 1 年度末时的完好机器数量) 。决策变量 xk 为第 k 年度分配高负荷下生 产的机器数量,于是 S k ? xk 为该年度分配在低负荷下生产的机器数量。这里的 S k 和 xk 均 为连续变量,它们的非整数值可以这样理解:如 S k ? 0.6 就表示一台机器在第 k 年度中正 常工作时间只占全部时间的 60%; xk ? 0.3 就表示一台机器在第 k 年度中只有 30%的工作时 间在高负荷下运转。状态转移方程为:

S k ?1 ? ?xk ? ? (S k ? xk ) ? 0.7 xk ? 0.9(S k ? xk ) ? 0.9S k ? 0.2xk
允许决策集合:

Dk (S k ) ? {xk | 0 ? xk ? S k }

设阶段指标 Qk (S k , xk ) 为第 k 年度的产量,则:

Qk (S k , xk ) ? 8xk ? 5(S k ? xk ) ? 5S k ? 3xk
过程指标是阶段指标的和,即:

Qk ~5 ? ? Q j
j ?k

5

令最优值函数 f k ( S k ) 表示从资源量 S k 出发, 采取最优子策略所生产的产品总量, 因而有逆 推关系式:

f k ( S k ) ? max {5S k ? 3xk ? f k ?1 (0.9S k ? 0.2 x k )}
xk ?Dk ( S k )

边界条件 f 6 (S 6 ) ? 0 。 当 k ? 5 时:

f 5 ( S 5 ) ? max {5S 5 ? 3x5 ? f 6 ( S 6 )} ? max {5S 5 ? 3x5 }
0? x5 ? S5 0? x5 ? S5

因 f 5 ( S 5 ) 是关于 x5 的单调递增函数,故取 x ? S5 ,相应有 f 5 (S5 ) ? 8S5 。 当 k ? 4 时:

? 5

f 4 ( S 4 ) ? max {5S 4 ? 3x 4 ? f 5 (0.9S 4 ? 0.2 x4 )}
0 ? x4 ? S 4

? max {5S 4 ? 3x 4 ? 8(0.9S 4 ? 0.2 x 4 )}
0 ? x4 ? S 4

? max {12.2S 4 ? 1.4 x 4 }
0 ? x4 ? S 4

? 因 f 4 ( S 4 ) 是关于 x4 的单调递增函数,故取 x4 ? S 4 ,相应有 f 4 (S 4 ) ? 13.6S 4 ;依次类推, 可求得:

? 当 k ? 3 时: x3 ? S3 , f 3 (S 3 ) ? 17.5S 3
? 当 k ? 2 时: x2 ? 0 , f 2 (S 2 ) ? 20.8S 2 ? 当 k ? 1 时: x1 ) ? 23.7S1 ? 23700 ? 0 , f1 (S1 ? 1000 ? ? ? ? ? 计算结果表明最优策略为: x1 ? 0 , x2 ? 0 , x3 ? S 4 , x5 ? S 3 , x4 ? S5 ;即前两

年将全部设备都投入低负荷生产, 后三年将全部设备都投入高负荷生产, 这样可以使 5 年的 总产量最大,最大产量是 23700 件。 有了上述最优策略,各阶段的状态也就随之确定了,即按阶段顺序计算出各年年初的 完好设备数量。

S1 ? 1000 S 2 ? 0.9S1 ? 0.2 x1 ? 0.9 ?1000? 0.2 ? 0 ? 900 S3 ? 0.9S 2 ? 0.2x2 ? 0.9 ? 900? 0.2 ? 0 ? 810 S 4 ? 0.9S3 ? 0.2x3 ? 0.9 ? 810? 0.2 ? 810 ? 567 S5 ? 0.9S 4 ? 0.2x4 ? 0.9 ? 567? 0.2 ? 567 ? 397 S6 ? 0.9S5 ? 0.2x5 ? 0.9 ? 397? 0.2 ? 397 ? 278 上面所讨论的过程始端状态 S1 是固定的,而终端状态 S 6 是自由的,实现的目标函数是
5 年的总产量最高。如果在终端也附加上一定的约束条件,如规定在第 5 年结束时,完好的 机器数量不低于 350 台(上面的例子只有 278 台) ,问应如何安排生产,才能在满足这一终 端要求的情况下使产量最高呢? 解: 阶段 k 表示年度 ( k ? 1,2,3,4,5 ) ; 状态变量 S k 为第 k 年度初拥有的完好机器数量; 决策变量 xk 为第 k 年度分配高负荷下生产的机器数量;状态转移方程为:

S k ?1 ? ?xk ? ? (S k ? xk ) ? 0.7 xk ? 0.9(S k ? xk ) ? 0.9S k ? 0.2xk
终端约束:

S 6 ? 350
0.9S5 ? 0.2x5 ? 350 x5 ? 4.5S5 ? 1750
允许决策集合: Dk (S k ) ? {xk | 0 ? xk ? S k } “加”第 k 阶段的终端递推条件 对于 k ? 5 ,考虑终端递推条件有:

D5 (S5 ) ? {x5 | 0 ? x5 ? 4.5S5 ? 1750? S5 } 500 ? S5 ? 389
同理其他各阶段的允许决策集合可在过程指标函数的递推中产生。 设阶段指标:

Qk (S k , xk ) ? 8xk ? 5(S k ? xk ) ? 5S k ? 3xk
过程指标:

Qk ~5 ? ? Q j
j ?k

5

最优值函数:

f k ( S k ) ? max {5S k ? 3xk ? f k ?1 (0.9S k ? 0.2 x k )}
xk ?Dk ( S k )

边界条件 f 6 (S 6 ) ? 0 。 当 k ? 5 时:

f 5 ( S 5 ) ? max {5S 5 ? 3x5 ? f 6 ( S 6 )} ? max {5S 5 ? 3x5 }
x5 ?D5 ( S5 ) x5 ?D5 ( S5 )

? 因 f 5 ( S 5 ) 是关于 x5 的单调递增函数,故取 x5 ? 4.5S5 ? 1750,相应有:

0 ? 4.5S5 ? 1750? S5
即:

389 ? S5 ? 500
? x5 ? 4.5S5 ? 1750, f 5 (S5 ) ? 18.5S5 ? 5250

当 k ? 4 时:

f 4 ( S 4 ) ? max {5S 4 ? 3x 4 ? f 5 (0.9S 4 ? 0.2 x4 )}
x4 ?D4 ( S 4 )

? max {21.65 S 4 ? 0.7 x4 ? 5250}
x4 ?D4 ( S 4 )

由 S5 ? 0.9S 4 ? 0.2x4 ? 500 可得 x4 ? 4.5S 4 ? 2500,又因 f 4 ( S 4 ) 是关于 x4 的单调
? 递减函数,故取 x4 ? 4.5S 4 ? 2500,相应有:

0 ? 4.5S 4 ? 2500? S 4 556 ? S 4 ? 714
? x4 ? 4.5S 4 ? 2500, f 4 (S 4 ) ? 18.5S 4 ? 3500

当 k ? 3 时:

f 3 ( S 3 ) ? max {5S 3 ? 3x3 ? f 4 (0.9S 3 ? 0.2 x3 )}
x3 ?D3 ( S3 )

? max {21.65 S 3 ? 0.7 x3 ? 3500}
x3?D3 ( S3 )

由 S 4 ? 0.9S3 ? 0.2x3 ? 714可得 x3 ? 4.5S3 ? 3570, 又因 f 3 ( S 3 ) 是关于 x3 的单调递
? 减函数,故取 x3 ? 4.5S3 ? 3570,相应有:

0 ? 4.5S3 ? 3570? S3 793? S3 ? 1020
由于 S1 ? 1000,所以 S 3 ? 1020是恒成立的,即 S 3 ? 793。
? x3 ? 4.5S3 ? 3570, f 3 (S3 ) ? 18.5S3 ? 1001

当 k ? 2 时:

f 2 ( S 2 ) ? max {5S 2 ? 3x 2 ? f 3 (0.9S 2 ? 0.2 x2 )}
x2 ?D2 ( S 2 )

? max {21.65 S 2 ? 0.7 x 2 ? 1001}
x2 ?D2 ( S 2 )

因 f 2 ( S 2 ) 是关于 x2 的单调递减函数,而 S 3 的取值并不对 x2 有下界的约束,故取
? x2 ? 0 ,相应有: ? x2 ? 0 , f 2 (S 2 ) ? 21.65S 2 ? 1001

当 k ? 1 时:

f1 ( S1 ) ? max {5S1 ? 3x1 ? f 2 (0.9S1 ? 0.2 x1 )}
x1?D1 ( S1 )

? max {24.485 S1 ? 1.33 x1 ? 1001}
x1?D1 ( S1 )

因 f1 ( S1 ) 是关于 x1 的单调递减函数,故取 x1 ? 0 ,相应有:

?

? ) ? 24.485S1 ? 1001? 23484 x1 ? 0 , f1 (S1 ? 1000

计算结果表明最优策略为: (1)第 1 年将全部设备都投入低负荷生产。

S1 ? 1000, x1 ? 0 , S 2 ? 0.9S1 ? 0.2 x1 ? 0.9 ?1000? 0.2 ? 0 ? 900 Q1 (S1 , x1 ) ? 5S1 ? 3x1 ? 5 ?1000? 3 ? 0 ? 5000
(2)第 2 年将全部设备都投入低负荷生产。

S 2 ? 900, x2 ? 0 , S3 ? 0.9S 2 ? 0.2x2 ? 0.9 ? 900? 0.2 ? 0 ? 810
Q2 (S 2 , x2 ) ? 5S 2 ? 3x2 ? 5 ? 900? 3 ? 0 ? 4500
? (3)第 3 年将 x3 ? 4.5S3 ? 3570? 4.5 ? 810? 3570? 75台完好设备投入高负荷生 ? 产,将剩余的 S3 ? x3 ? 810? 75 ? 735台完好设备投入低负荷生产。

Q3 (S3 , x3 ) ? 5S3 ? 3x3 ? 5 ? 810? 3 ? 75 ? 4275 S 4 ? 0.9S3 ? 0.2x3 ? 0.9 ? 810? 0.2 ? 75 ? 714
? (4)第 4 年将 x4 ? 4.5S 4 ? 2500 ? 4.5 ? 714 ? 2500 ? 713台完好设备均投入高负荷

生产,将剩余的 1 台完好设备均投入低负荷生产。

Q4 (S 4 , x4 ) ? 5S 4 ? 3x4 ? 5 ? 714? 3 ? 713 ? 5709

S5 ? 0.9S 4 ? 0.2x4 ? 0.9 ? 714? 0.2 ? 713 ? 500
? (5)第 5 年将 x5 ? 4.5S5 ? 1750? 4.5 ? 500? 1750? 500 ,即将 S 5 ? 500台完好设

备均投入高负荷生产。

Q5 (S5 , x5 ) ? 5S5 ? 3x5 ? 5 ? 500? 3 ? 500 ? 4000 S6 ? 0.9S5 ? 0.2x5 ? 0.9 ? 500? 0.2 ? 500 ? 350
f1 ( S1 ? 1000 ) ? ? Q j ( S j , x j ) ? 23484
j ?1 5

2-3 存贮控制问题 由于供给与需求在时间上存在差异,需要在供给与需求之间构建存贮环节以平衡这种 差异。存贮物资需要付出资本占用费和保管费等,过多的物资储备意味着浪费;而过少的储 备又会影响需求造成缺货损失。 存贮控制问题就是要在平衡双方的矛盾中, 寻找最佳的采购

批量和存贮量,以期达到最佳的经济效果。 [例 7-4] 某鞋店销售一种雪地防潮鞋,以往的销售经历表明,此种鞋的销售季节是从 10 月 1 日至 3 月 31 日。下个销售季节各月的需求预测值如表 7-5 所示。 表 7-5
月份 需求

(单位:双) 1 40 2 30 3 20

10 40

11 20

12 30

该鞋店的此种鞋完全从外部生产商进货,进货价每双 4 美元。进货批量的基本单位是 箱,每箱 10 双。由于存贮空间的限制,每次进货不超过 5 箱。对应不同的订货批量,进价 享受一定的数量折扣,具体数值如表 7-6 所示。 表 7-6
进货批量 数量折扣 1箱 2箱 3箱 4箱 5箱

4%

5%

10%

20%

25%

假设需求是按一定速度均匀发生的,订货不需时间,但订货只能在月初办理一次,每次 订货的采购费(与采购数量无关)为 10 美元。月存贮费按每月月底鞋的存量计,每双 0.2 美元。由于订货不需时间,所以销售季节外的其他月份的存贮量为“0” 。试确定最佳的进货 方案,以使总的销售费用最小。 解:阶段:将销售季节 6 个月中的每一个月作为一个阶段,即 k ? 1,2,?,6 ; 状态变量:第 k 阶段的状态变量 S k 代表第 k 个月初鞋的存量; 决策变量:决策变量 xk 代表第 k 个月的采购批量; 状态转移律: S k ?1 ? S k ? xk ? d k ( d k 是第 k 个月的需求量) ; 边界条件: S1 ? S 7 ? 0 , f 7 (S 7 ) ? 0 ; 阶段指标函数: rk (S k , xk ) 代表第 k 个月所发生的全部费用,即与采购数量无关的采购 费 C k 、与采购数量成正比的购置费 Gk 和存贮费 Z k 。其中:

0, xk ? 0 ; Gk ? p x ? xk ; Z k ? 0.2(S k ? xk ? d k ) Ck ? { 10, xk ? 0
最优指标函数:最优指标函数具有如下递推形式

f k ( S k ) ? min{C k ? Gk ? Z k ? f k ?1 ( S k ?1 )
xk

? min{C k ? Gk ? 0.2( S k ? x k ? d k ) ? f k ?1 ( S k ? x k ? d k )}
xk

当 k ? 6 时(3 月) : 表 7-7

S6 x6 f6(S6)
当 k ? 5 时(2 月) :

0 20 86

10 10 48

20 0 0

表 7-8

x5 S5

0

10

20

30

40

50

? x5

f 5 (S 5 )

0 10 20 30 40 50 86 50 4 134 98 52 172 136 90

204 168 122

188 142

164

50 40 30 0 0 0

164 142 122 86 50 4

当 k ? 4 时(1 月) : 表 7-9

x4 S4
0 10 20 30 40 50 60

0

10

20

30

40 302

50 304 286 252 218 170

? x4

f 4 (S 4 )
302 282 250 212 164 144 126

40 30、40 20 10 0 0 0

282 250 212 164 144 126 192 174 140 230 212 178 144 262 244 210 176 132

282 264 230 196 152

当 k ? 3 时(12 月) : 表 7-10

x3 S3
0 10 20 30 40

0

10

20

30 420

40 422 392 362 310 292

50 414 384 332 314 298

? x3

f 3 (S 3 )
414 384 332 302 284

50 50 50 0 0

388 350 302 284 332 302 370 340 310

402 372 342 290

当 k ? 2 时(11 月) : 表 7-11

x2 S2
0 10

0

10

20 500

30 504 454

40 474 446

50 468 452

? x2

f 2 (S 2 )
468 446

50 40

462

472

当 k ? 1 时(10 月) : 表 7-12

x1 S1
0

0

10

20

30

40 606

50 608

? x1

f1 ( S1 )
606

40

利用状态转移律,按上述计算的逆序可推算出最优策略:10 月份采购 4 箱(40 双) ,

11 月份采购 5 箱(50 双) ,12 月份不采购,1 月份采购 4 箱(40 双) ,2 月份采购 5 箱(50 双) ,3 月份不采购;最小的销售费用为 606 美元。 2-4 用动态规划求解非线性规划问题 非线性规划问题的求解(在第六章中已讨论)是非常困难的;然而,对于有些非线性 规划问题,如果转化为用动态规划来求解将是十分方便的。 [例 7-5] 用动态规划求解
2 max z ? x1 ? x2 ? x3

x1 ? x2 ? x3 ? 36

x1 , x2 , x3 ? 0
解:阶段:将问题的变量数作为阶段,即 k ? 1,2,3 ; 决策变量:决策变量 xk ; 状态变量:状态变量 S k 代表第 k 阶段的约束右端项,即从 xk 到 x3 占有的份额; 状态转移律: S k ?1 ? S k ? xk ; 边界条件: S1 ? 36 , f 4 ( S 4 ) ? 1 ; 允许决策集合: 0 ? xk ? S k 当 k ? 3 时:

f 3 ( S 3 ) ? max {x3 ? f 4 ( S 4 )} ? max {x3 } ? S 3 | x? ? S
0? x3 ? S3 0? x3 ? S3
3

3

当 k ? 2 时:
2 2 f 2 ( S 2 ) ? max {x2 ? f 3 ( S 3 )} ? max {x2 ( S 2 ? x2 )} 0 ? x2 ? S 2 0? x2 ? S 2

设 h ? x (S 2 ? x2 ) ,于是
2 2
2

dh dx2

? 2 x2 ( S 2 ? x2 ) ? x

2 2

2 dh 令 dx ? 2 x2 ( S 2 ? x2 ) ? x2 ? 0 ,可得 x2 ? 0 或 2 3 S2
h ? 2( S 2 ? x 2 ) ? 2 x 2 ? 2 x 2 ? 2S 2 ? 6 x 2 ,所以: 又因 d dx 2
2 2

d 2h 2 x2 ? 0 dx 2

|

? 2 S 2 ? 0 , x2 ? 0 是 f 2 ( S 2 ) 的极小值点

d 2h 2 x2 ? 2 S dx2 3 2

|

? 2S 2 ? 4S 2 ? ?2S 2 ? 0 , x2 ? 2 是 f 2 ( S 2 ) 的极大值点 3 S2
f 2 (S 2 ) ?
4 27 3 S2 | x? ? 2 S
2 3

于是:
2

当 k ? 1 时:
4 f1 ( S1 ) ? max{x1 ? f 2 ( S 2 )} ? max{x1 ? 27 ( S1 ? x1 ) 3 } 0? x1 ? S1 0? x1 ? S1

同上可得:

f1 ( S1 ? 36) ?
?

1 64

S14 ?

1 64

? 36 4 ? 26244 | x? ? 1 S ?9
1 4 1

? 2 由 S 2 ? S1 ? x1 ? 36 ? 9 ? 27 ,有 x2 ?2 3 S 2 ? 3 ? 27 ? 18

由 S3 ? S 2 ? x2 ? 27 ? 18 ? 9 ,有 x3 ? S3 ? 9

?

?

于是得到最优解 X ? ? (9,18,9) ,最优值 z ? 26244。

?

习题: 1. 某公司打算向它的三个营业区增设 6 个销售店,每个营业区至少增设 1 个。各营业区每 年增加的利润与增设的销售店个数有关,具体关系如表 1 所示。试规划各营业区应增设 销售店的个数,以使公司总利润增加额最大。 表1 增设销售店个数 1 2 3 4 营业区 A 100(万元) 160 190 200 营业区 B 120(万元) 150 170 180 营业区 C 150(万元) 165 175 190

2. 某工厂有 100 台机器,拟分 4 个周期使用,在每一周期有两种生产任务,据经验把机器 投入第一种生产任务, 则在一个周期中将有六分之一的机器报废, 投入第二种生产任务, 则有十分之一的机器报废。如果投入第一种生产任务每台机器可收益 1 万元,投入第二 种生产任务每台机器可收益 0.5 万元。问怎样分配机器在 4 个周期内的使用才能使总收 益最大? 3. 某公司生产一种产品,估计该产品在未来四个月的销售量分别为 300、400、350 和 250 件。生产该产品每批的固定费用为 600 元,每件的变动费用为 5 元,存储费用为每件每 月 2 元。假定第一个月月初的库存为 100 件,第四个月月底的存货为 50 件。试求该公 司在这四个月内的最优生产计划。


赞助商链接
相关文章:
动态规划习题答案
动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案2.某公司有资金 4 百万元向 A,B 和 C3 ...
动态规划题目
动态规划题目_销售/营销_经管营销_专业资料。动态规划的经典题和部分题解机器分配 总公司拥有高效生产设备 M 台,准备分给下属的 N 个公司.各分公司若获得这些设备...
动态规划习题
45页 20财富值 动态规划题目 38页 2财富值 动态规划_各种类型题 102页 10财富值 动态规划题 9页 免费如要投诉或提出意见建议,请到百度文库投诉中心反馈。 ...
动态规划习题集全
动态规划习题集全_理学_高等教育_教育专区。动态规划专题训练 护卫队【问题描述】 护卫车队在一条单行的街道前排成一队,前面河上是一座单行的桥。因为街道是一条...
动态规划
第10章 动态规划 76页 免费 第4章动态规划 35页 2财富值喜欢此文档的还喜欢 动态规划习题详解 32页 5财富值 动态规划经典问题 70页 1财富值 动态规划基础讲解...
动态规划题目
temp3); } cout<<dp[len1][len2]<<endl; delete[] dp; } return 0; } 心得体会: 我觉得适合动态规划解决的问题有两个要素: 最优子结构和子问 题...
动态规划 练习题
动态规划练习题 23.(11 分) 请用动态规划逆序求解法求解下列问题:求出下图中从 A 到 E 的最短路线及 长度。在图中标出每个点到终点的最短距离。 24. (...
动态规划总结经典题目(经典中的经典)
l=mid+1:r=mid-1; } f[l]=a[i]; } } printf("%d\n",s); } } 12:Pku acm 1157 LITTLE SHOP OF FLOWERS 该题也是经典的动态规划,题目叙述的...
经典的动态规划入门练习题
经典的动态规划入门练习题_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 经典的动态规划入门练习题_工学_高等教育_教育专区。动态规划入门练习题 ...
动态规划习题
acm_动态规划算法 30页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 动态规划习题 简单的动归习题一套。简单...
更多相关标签: