动态规划习题

　第 七 章

　动态规划

　规划问题得最终目得就就是确定各决策变量得取值,以使目标函数达到极大或极小。在线性规划与非线性规划中,决策变量都就是以集合得形式被一次性处理得;然而,有时我们也会面对决策变量需分期、分批处理得多阶段决策问题。所谓 多阶段决策问题就是指这样一类活动过程：它可以分解为若干个互相联系得阶段,在每一阶段分别对应着一组可供选取得决策集合;即构成过程得每个阶段都需要进行一次决策得决策问题。将各个阶段得决策综合起来构成一个决策序列,称为一个策略。显然,由于各个阶段选取得决策不同,对应整个过程可以有一系列不同得策略。当过程采取某个具体策略时,相应可以得到一个确定得效果,采取不同得策略,就会得到不同得效果。多阶段得决策问题,就就是要在所有可能采取得策略中选取一个最优得策略,以便得到最佳得效果。

　动态规划(dy ｎ ami ｃ

　pro ｇ ramming)同前面介绍过得各种优化方法不同，它不就是一种算法，而就是考察问题得一种途径。动态规划就是一种求解多阶段决策问题得系统技术,可以说它横跨整个规划领域(线性规划与非线性规划)。当然,由于动态规划不就是一种特定得算法，因而它不象线性规划那样有一个标准得数学表达式与明确定义得一组规则，动态规划必须对具体问题进行具体得分析处理。在多阶段决策问题中,有些问题对阶段得划分具有明显得时序性,动态规划得“动态”二字也由此而得名。动态规划得主要创始人就是美国数学家贝尔曼(Bel ｌ ma ｎ )。20 世纪 40 年代末 50 年代初,当时在兰德公司(Rand Cor ｐ orati ｏ n）从事研究工作得贝尔曼首先提出了动态规划得概念。1957 年贝尔曼发表了数篇研究论文,并出版了她得第一部著作《动态规划》。该著作成为了当时唯一得进一步研究与应用动态规划得理论源泉。１9６1 年贝尔曼出版了她得第二部著作,并于 196２年同杜瑞佛思( Ｄ reyfu ｓ )合作出版了第三部著作。在贝尔曼及其助手们致力于发展与推广这一技术得同时，其她一些学者也对动态规划得发展做出了重大得贡献,其中最值得一提得就是爱尔思(A ｒ i ｓ )与梅特顿(Mitten）。爱尔思先后于 19６1 年与 1９64 年出版了两部关于动态规划得著作,并于 1964 年同尼母霍思尔(Ne ｍ hauser）、威尔德（Wild)一道创建了处理分枝、循环性多阶段决策系统得一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义得基础性观点,并且对明晰动态规划路径得数学性质做出了巨大得贡献。

　动态规划在工程技术、经济管理等社会各个领域都有着广泛得应用,并且获得了显著得效果。在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等,就是经济管理中一种重要得决策技术。许多规划问题用动态规划得方法来处理,常比线性规划或非线性规划更有效。特别就是对于离散得问题,由于解析数学无法发挥作用,动态规划便成为了一种非常有用得工具。

　动态规划可以按照决策过程得演变就是否确定分为 确定性动态规划与 随机性动态规划;也可以按照决策变量得取值就是否连续分为 连续性动态规划与 离散性动态规划。本教材主要介绍动态规划得基本概念、理论与方法，并通过典型得案例说明这些理论与方法得应用。

　§7 7 、 1

　 动态规划得基本理论 1.1 多阶段决策过程得数学描述 有这样一类活动过程,其整个过程可分为若干相互联系得阶段，每一阶段都要作出相应得决策,以使整个过程达到最佳得活动效果。任何一个阶段（ ｓtage ,即决策点)都就是由输入( ｉnpuｔ )、决策( dｅcision )、状态转移律( trａnsfｏrmａtion fｕnctiｏn ）与输出（ oｕtput )构成得,如图 7-1(a)所示。其中输入与输出也称为状态( state )，输入称为输入状态,输出称为输出状态。

　输

　出 输

　入 决

　策 阶

　段 状态转移 S n+1

　S n

　d n

　Stage n g n

　= r(S n ,d n )

　图 7－1 由于每一阶段都有一个决策,所以每一阶段都应存在一个衡量决策效益大小得指标函数,这一指标函数称为 阶段指标函数,用 ｇ n 表示。显然 g n 就是状态变量 Ｓ n 与决策变量 d n 得函数,即 ｇ n = ｒ ( S n , d n )，如图 7-1(b）所示。显然，输出就是输入与决策得函数，即:

　 (７-1) 式(7-1)即为状态转移律。在由 N 个阶段构成得过程里,前一个阶段得输出即为后一个阶段得输入。

　1.2 动态规划得基本概念

　动态规划得数学描述离不开它得一些基本概念与符号,因此有必要在介绍多阶段决策过程得数学描述得基础上,系统地介绍动态规划得一些基本概念。

　1． 阶段( sｔａgｅ ）

　阶段就是过程中需要做出决策得决策点。描述阶段得变量称为阶段变量,常用 k 来表示。阶段得划分一般就是根据时间与空间得自然特征来进行得,但要便于将问题得过程转化为多阶段决策得过程。对于具有 Ｎ 个阶段得决策过程，其阶段变量 ｋ ＝1,2,„， Ｎ 。

　2． 状态( state ) 状态表示每个阶段开始所处得自然状况或客观条件,它描述了研究问题过程得状况。状态既反映前面各阶段系列决策得结局，又就是本阶段决策得一个出发点与依据；它就是各阶段信息得传递点与结合点。各阶段得状态通常用状态变量 S ｋ 来加以描述。作为状态应具有这样得性质：如果某阶段状态给定后,则该阶段以后过程得发展不受此阶段以前各阶段状态得影响。换句话说，过程得历史只能通过当前得状态来影响未来,当前得状态就是以往历史得一个总结。这个性质称为 无后效性( tｈe future is indｅpendenｔ of the pａst ）或 健忘性( tｈe prｏcess ｉs ｆｏrgｅtfuｌ ）。

　3． 决策（ dｅcisｉon ）

　决策就是指决策者在所面临得若干个方案中做出得选择。决策变量 ｄ k 表示第 k 阶段得决策。决策变量 d ｋ 得取值会受到状态 S ｋ 得某种限制，用 D k ( S k )表示第 k 阶段状态为 S k 时决策变量允许得取值范围,称为 允许决策集合,因而有 ｄ k ( S ｋ ) D k （ S k )。

　4． 状态转移律( trａnsfoｒmａtｉｏn fuｎctiｏn ) 状态转移律就是确定由一个状态到另一状态演变过程得方程,这种演变得对应关系记为 S k＋1

　= T ｋ ( S k

　, d k )。

　5． 策略( pｏlicy ）与子策略( sub-ｐolicy ）

　由所有阶段决策所组成得一个决策序列称为一个策略,具有 N 个阶段得动态规划问题得策略可表示为:

　从某一阶段开始到过程终点为止得一个决策子序列,称为 过程子策略或 子策略。从第 k个阶段起得一个子策略可表示为:

　6． 指标函数 指标函数有 阶段指标函数与 过程指标函数之分。阶段指标函数就是对应某一阶段决策得效率度量,用 g k ＝ ｒ ( Ｓ k , d ｋ )来表示;过程指标函数就是用来衡量所实现过程优劣得数量指标,就是定义在全过程(策略)或后续子过程(子策略)上得一个数量函数,从第 k 个阶段起得一个子策略所对应得过程指标函数常用 G k，N 来表示,即:

　构成动态规划得过程指标函数,应具有可分性并满足递推关系;即:

　这里得表示某种运算,最常见得运算关系有如下二种: （1）

　过程指标函数就是其所包含得各阶段指标函数得“与”,即:

　于就是

　（2）

　过程指标函数就是其所包含得各阶段指标函数得“积”,即:

　于就是

　7． 最优指标函数 从第个阶段起得 最优子策略所对应得过程指标函数称为最优指标函数，可以用式(7-２）加以表示:

　（7-2）

　其中“ opt ”就是最优化“ ｏptiｍｉzａtioｎ ”得缩写,可根据题意取最大“ max ”或最小“ ｍｉn ”。在不同得问题中,指标函数得含义可能就是不同得,它可能就是距离、利润、成本、产量或资源量等。

　1.3 动态规划得数学模型

　动态规划得数学模型除包括式（7－２)外，还包括阶段得划分、各阶段得状态变量与决策变量得选取、允许决策集合与状态转移律得确定等。

　如何获得最优指标函数呢?一个阶段得决策过程,具有如下一些特性: （1）

　刚好有个决策点; （2 2 ）

　对阶段而言，除了其所处得状态与所选择得决策外,再没有任何其它因素影响决策得最优性了;

　（3 3 ）

　阶段仅影响阶段得决策,这一影响就是通过来实现得;

　（4 4 ）

　贝尔曼( Beｌlman )最优化原理:在最优策略得任意一阶段上,无论过去得状态与决策如何,对过去决策所形成得当前状态而言,余下得诸决策必须构成最优子策略。

　根据贝尔曼（ Bｅllman )最优化原理,可以将式(7-２)表示为递推最优指标函数关系式（7-3)或式（7-4):

　 (7-3)

　 (7－4)

　利用式(7-3)与式(7-４)可表示出最后一个阶段（第 N 个阶段,即 ｋ=N )得最优指标函数:

　 （７-5）

　(7－6) 其中称为 边界条件。一般情况下,第阶段得输出状态已经不再影响本过程得策略，即式(7-５)中得边界条件,式(７-6)中得边界条件;但当问题第阶段得输出状态对本过程得策略产生某种影响时,边界条件就要根据问题得具体情况取适当得值,这一情况将在后续例题中加以反映。

　已知边界条件,利用式(７-３)或式(7-４）即可求得最后一个阶段得最优指标函数;有了，继续利用式(7-３)或式(7-4）即可求得最后两个阶段得最优指标函数；有了,进一步又可以求得最后三个阶段得最优指标函数;反复递推下去,最终即可求得全过程个阶段得最优指标函数，从而使问题得到解决。由于上述最优指标函数得构建就是按阶段得逆序从后向前进行得,所以也称为动态规划得 逆序算法。

　通过上述分析可以瞧出,任何一个多阶段决策过程得最优化问题，都可以用非线性规划（特殊得可以用线性规划)模型来描述;因此,从原则上讲，一般也可以用非线性规划（或线性规划）得方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什么局

　限性呢? 动态规划得优点: 第一, , 求解更容易、效率更高。动态规划方法就是一种逐步改善法,它把原问题化成一系列结构相似得最优化子问题,而每个子问题得变量个数比原问题少得多,约束集合也简单得多,故较易于确定最优解。

　第二, , 解得信息更丰富。非线性规划(或线性规划)得方法就是对问题得整体进行一次性求解得,因此只能得到全过程得解；而动态规划方法就是将过程分解成多个阶段进行求解得,因此不仅可以得到全过程得解,同时还可以得到所有子过程得解。

　动态规划得缺点: 第一，没有一个统一得标准模型。由于实际问题不同，其动态规划模型也就各有差异，模型构建存在一定困难。

　第二, , 应用条件苛刻。由于构造动态规划模型状态变量必须满足“无后效性”条件,这一条件不仅依赖于状态转移律,还依赖于允许决策集合与指标函数得结构,不少实际问题在取其自然特征作为状态变量时并不满足这一条件,这就降低了动态规划得通用性。

　第三, ,” 状态变量存在“维数障碍”。最优指标函数就是状态变量得函数,当状态变量得维数增加时,最优指标函数得计算量将成指数倍增长;因此,无论就是手工计算还就是电算“维数障碍”都就是无法完全克服得。

　§7 7 、２

　确定性动态规划问题

　确定性动态规划问题即阶段得输出状态完全由其输入状态与决策所决定得动态规划问题。确定性动态规划解决得问题可能包含经济管理得方方面面,可以就是最短路线问题,可以就是资源配置问题,也可以就是其她得规划优化问题。最短路线问题直观、具体地演示了动态规划得基本概念与基本步骤;因此,让我们首先来分析一下最短路线问题。

　２- -1 1 最短路线问题

　[ [例 例 7 7- - 1] 美国黑金石油公司( Ｔhe Bｌack Gold Pｅtroleｕｍ pａｎy )最近在阿拉斯加( Alaｓka ）得北斯洛波( Nｏrth Sｌope )发现了大得石油储量。为了大规模开发这一油田，首先必须建立相应得输运网络,使北斯洛波生产得原油能运至美国得 3 个装运港之一。在 油田得集输站（结点 Ｃ )与 装运港(结点 P １ 、 P 2 、 P ３ )之间需要若干个中间站,中间站之间得联通情况如图 7-2 所示,图中线段上得数字代表两站之间得距离（单位:1０千米)。试确定一最佳得输运线路,使原油得输送距离最短。

　解:最短路线有一个重要性质,即如果由起点 A 经过 B 点与 Ｃ 点到达终点 D 就是一条最短路线,则由 B 点经 C 点到达终点 Ｄ 一定就是 B 到 D 得最短路（贝尔曼最优化原理)。此性质用反证法很容易证明,因为如果不就是这样,则从 B 点到 D 点有另一条距离更短得路线存在,不妨假设为 B—Ｐ—D ;从而可知路线 Ａ—B—P—D 比原路线 Ａ—Ｂ—C—Ｄ 距离短,这与原路线A—B—C—D 就是最短路线相矛盾,性质得证。

　根据最短路线得这一性质,寻找最短路线得方法就就是从最后阶段开始，由后向前逐步递推求出各点到终点得最短路线,最后求得由始点到终点得最短路;即动态规划得方法就是从终点逐段向始点方向寻找最短路线得一种方法。按照动态规划得方法,将此过程划分为 4个阶段,即阶段变量;取过程在各阶段所处得位置为状态变量,按逆序算法求解。

　当时: 由结点 M ３1 到达目得地有两条路线可以选择，即选择 Ｐ 1 或 Ｐ 2 ;故:

　选择 Ｐ 2

　由结点 M ３2 到达目得地有三条路线可以选择,即选择 Ｐ 1 、 P ２ 或 P ３ ;故:

　选择 P P 2 2

　由结点 M 33 到达目得地也有三条路线可以选择，即选择 P １ 、 P ２ 或 P 3 ;故：

　选择 P P 3 3

　C P 3

　P 2

　P 1

　M 11

　M 12

　M 21

　M 22

　M 23

　M 31

　M 32

　M 33

　M 34

　10 12 8 6 9 11 10 7 6 9 7 5 11 4 6 8 6 4 3 7 7 6 5 3 4

　由结点 M ３4 到达目得地有两条路线可以选择,即选择 P 2 或 Ｐ 3 ;故:

　选择 Ｐ 2

　当时：

　由结点 M 21 到达下一阶段有三条路线可以选择,即选择 M 31 、 M 32 或 M 3３ ；故:

　选择 M ３２

　由结点 M ２2 到达下一阶段也有三条路线可以选择,即选择 M 31 、 Ｍ 32 或 M 3３ ;故:

　选择 M M ３２ 或 M M ３３

　由结点 M 23 到达下一阶段也有三条路线可以选择，即选择 M 32 、 M 33 或 M 3４ ;故:

　选择 M 33 或 M 34

　当时: 由结点 M 11 到达下一阶段有两条路线可以选择,即选择 M 21 或 Ｍ ２2 ;故:

　选择 Ｍ 2 2 ２

　由结点 M 12 到达下一阶段也有两条路线可以选择,即选择 M 22 或 Ｍ 2３ ;故:

　选择 M 22

　当时：

　由结点 C 到达下一阶段有两条路线可以选择，即选择 Ｍ １1 或 M 12 ;故:

　选择 Ｍ 1 1 １

　从而通过顺序(计算得反顺序)追踪(黑体标示)可以得到两条最佳得输运线路: C C — M M 11 —M M 2 2 ２ — Ｍ 32 — P P 2 2 ; C C — Ｍ 11 — Ｍ 22 — Ｍ 33 — P P 3 3 。最短得输送距离就是 2８0 千米。

　２- -2 2 资源分配问题

　所谓资源分配问题,就就是将一定数量得一种或若干种资源（如原材料、机器设备、资金、劳动力等)恰当地分配给若干个使用者,以使资源得到最有效地利用。设有 ｍ 种资源，总量分别为 b b i i ( i

　＝ 1,2,, m )，用于生产 n n 种产品,若用 x x ij 代表用于生产第 j j 种产品得第 i i种资源得数量( j

　= 1,2,, ｎ ),则生产第 j j 种产品得收益就是其所获得得各种资源数量得函数,即 g j

　= f （ x １j ， x 2ｊ ,,

　x mｊ )。由于总收益就是 n n 种产品收益得与,此问题可用如下静态模型加以描述：

　若 x x ｉj j 就是连续变量,当 g j

　＝ f （ ｘ 1j , x 2ｊ ,,

　x ｍj )就是线性函数时,该模型就是线性规划模型；当 g j

　= f ( ｘ 1j , x 2j ,,

　x mｊ )就是非线性函数时,该模型就是非线性规划模型。若 x x ij就是离散变量或(与) g j

　= f （ x 1j ， x ２j ,,

　x mj )就是离散函数时,此模型用线性规划或非线性规划来求解都将就是非常麻烦得。然而在此情况下,由于这类问题得特殊结构,可以将它瞧成为一个多阶段决策问题,并利用动态规划得递推关系来求解。

　本教材只考虑一维资源得分配问题,设状态变量 Ｓ k 表示分配于从第 k 个阶段至过程最终(第 N 个阶段)得资源数量,即第 k 个阶段初资源得拥有量;决策变量 ｘ k 表示第 k 个阶段资源得分配量。于就是有状态转移律:

　允许决策集合：

　最优指标函数(动态规划得逆序递推关系式）:

　利用这一递推关系式,最后求得得即为所求问题得最大总收益，下面来瞧一个具体得例

　子。

　[ [例 例 7 7- - 2] 某公司拟将 500 万元得资本投入所属得甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应得增长，增长额如表 7-1 所示。试确定 5０0 万元资本得分配方案,以使公司总得年利润增长额最大。

　表７－1 投资额 １００万元 ２０0 万元 3０0 万元 40０万元 5０0 万元 甲 3

　 乙 5

　１0 丙 4

　0 解:将问题按工厂分为 三个阶段,设 状态变量()代表从第个工厂到第 3 个工厂得投资额,决策变量代表第个工厂得投资额。于就是有 状态转移率、 允许决策集合与递推关系式:

　当时: :

　 于就是有表 7-2，表中表示第三个阶段得最优决策。

　表 7-2

　 ( 单位:百万元 ）

　0

　1 2 ３ 4 ５

　0 1 2 3 4 5

　0 0、4 0、６ 1、1 1、２ １、2 当时: :

　 于就是有表 7-3。

　表 7-３

　( 单位:百万元 ）

　ｘ 2

　Ｓ 2

　g 2 (x ２ )＋ｆ 3 (ｓ 2 － x 2 )

　 0 １ 2 ３ 4 5 0 ０＋0

　0 0 １ 0＋0、4 0、5+0

　 ０、５ １ ２ 0+0、6 ０、5+0、4 1、0+0

　１、０ 2 ３ 0+１、1 0、５＋0、6 1、0+0、4 １、1+0

　 １、４ 2 4 ０+1、２ 0、５＋1、1 1、0+０、6 1、1+0、４ 1、1＋0

　1、６ 1,2 5 0+1、2 0、５+1、2 1、0+１、1 １、1＋０、6 １、1+0、4 1、１＋0 ２、1 2 当时: :

　 于就是有表 7-4。

　表 7-４ x 1

　Ｓ 1

　ｇ 1 (x 1 ）+f 2 （s １ – ｘ 1 ）

　 0 １ 2 ３ 4 ５ 5 0＋2、1 ０、３+１、6 0、7+１、4 0、9+１、0 1、2+0、5 1、3+0 ２、1 0,2

　然后按计算表格得顺序反推算，可知最优分配方案有两个:（1）甲工厂投资２0０万元，乙工厂投资 200 万元,丙工厂投资 100 万元;(2）甲工厂没有投资,乙工厂投资 200 万元,丙工厂投资 300 万元。按最优分配方案分配投资（资源),年利润将增长２１０万元。

　这个例于就是决策变量取离散值得一类分配问题，在实际问题中,相类似得问题还有销售店得布局（分配)问题、设备或人力资源得分配问题等。在资源分配问题中,还有一种决策变量为连续变量得资源分配问题,请见例 7－3。

　［例 7 7- -3 3 ］

　机器负荷分配问题。某种机器可在高低两种不同得负荷下进行生产,设机器在高负荷下生产得产量(件)函数为,其中为投入高负荷生产得机器数量,年度完好率(年底得完好设备数等于年初完好设备数得７０%);在低负荷下生产得产量（件)函数为,其中为投入低负荷生产得机器数量,年度完好率。假定开始生产时完好得机器数量为 1000 台,试问每年应如何安排机器在高、低负荷下得生产,才能使 5 年生产得产品总量最多？ 解：设 阶段表示年度(); 状态变量为第年度初拥有得完好机器数量(同时也就是第年度末时得完好机器数量）。

　决策变量为第年度分配高负荷下生产得机器数量，于就是为该年度分配在低负荷下生产得机器数量。这里得与均为连续变量，它们得非整数值可以这样理解:如就表示一台机器在第年度中正常工作时间只占全部时间得 60%；就表示一台机器在第年度中只有 30%得工作时间在高负荷下运转。

　状态转移方程为: k k k k k k k k kx S x S x x S x S 2 . 0 9 . 0 ) ( 9 . 0 7 . 0 ) (1        

　允许决策集合:

　设 阶段指标为第年度得产量，则:

　过程指标就是阶段指标得与,即：

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

　边界条件。

　当时: :

　 因就是关于得单调递增函数，故取，相应有。

　当时：

　 因就是关于得单调递增函数,故取,相应有;依次类推，可求得: 当时: :, 当时: :, 当时: :,

　计算结果表明最优策略为:,,,,;即前两年将全部设备都投入低负荷生产,后三年将全部设备都投入高负荷生产,这样可以使 5 年得总产量最大,最大产量就是 23７00 件。

　有了上述最优策略，各阶段得状态也就随之确定了,即按阶段顺序计算出各年年初得完好设备数量。

　 上面所讨论得过程始端状态就是固定得,而终端状态就是自由得,实现得目标函数就是

　5 年得总产量最高。如果在终端也附加上一定得约束条件,如规定在第 5 年结束时,完好得机器数量不低于３5０台(上面得例子只有 278 台),问应如何安排生产,才能在满足这一终端要求得情况下使产量最高呢？ 解：

　阶段表示年度(); 状态变量为第年度初拥有得完好机器数量； 决策变量为第年度分配高负荷下生产得机器数量; 状态转移方程为: k k k k k k k k kx S x S x x S x S 2 . 0 9 . 0 ) ( 9 . 0 7 . 0 ) (1        

　终端约束:

　允许决策集合: : “加”第阶段得终端递推条件

　对于,考虑终端递推条件有:

　 同理其她各阶段得允许决策集合可在过程指标函数得递推中产生。

　设 阶段指标:

　过程指标:

　最优值 函数:

　边界条件。

　当时: :

　 因就是关于得单调递增函数,故取，相应有:

　即：

　， 当时: :

　由可得,又因就是关于得单调递减函数,故取,相应有:

　 , 当时: :

　 由可得，又因就是关于得单调递减函数,故取,相应有:

　 由于，所以就是恒成立得,即。

　,

　当时: :

　因就是关于得单调递减函数，而得取值并不对有下界得约束,故取,相应有: , 当时：

　 因就是关于得单调递减函数,故取,相应有：

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

　,，

　(2）第 2 年将全部设备都投入低负荷生产。

　,,

　（３)第 3 年将台完好设备投入高负荷生产,将剩余得台完好设备投入低负荷生产。

　 (4）第４年将台完好设备均投入高负荷生产，将剩余得 1 台完好设备均投入低负荷生产。

　 (5)第 5 年将,即将台完好设备均投入高负荷生产。

　2 2- -3 3 存贮控制问题

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

　例 ［例 7 7- - ４ ] 某鞋店销售一种雪地防潮鞋,以往得销售经历表明,此种鞋得销售季节就是从 10 月 1 日至 3 月３1 日。下个销售季节各月得需求预测值如表 7-5 所示。

　表 7-5

　 ( 单位:双 ) 月份 10 １１ 12 1 2 3 需求 ４

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

　表 7－6 进货批量 1 箱 2 箱 ３箱 4 箱 5 箱 数量折扣 4% 5％ 1０％ ２0% 25% 假设需求就是按一定速度均匀发生得,订货不需时间,但订货只能在月初办理一次，每次订货得采购费(与采购数量无关）为 10 美元。月存贮费按每月月底鞋得存量计，每双 0、2美元。由于订货不需时间,所以销售季节外得其她月份得存贮量为“0”。试确定最佳得进货

　方案,以使总得销售费用最小。

　解:阶段：将销售季节 6 个月中得每一个月作为一个阶段,即； 状态变量:第阶段得状态变量代表第个月初鞋得存量; 决策变量：决策变量代表第个月得采购批量； 状态转移律：(就是第个月得需求量); 边界条件：,; 阶段指标函数:代表第个月所发生得全部费用,即与采购数量无关得 采购费、与采购数量成正比得 购置费与 存贮费。其中: ;; 最优指标函数:最优指标函数具有如下递推形式

　 当时( ( ３月) ): 表 7-７ S ６

　０ １0 20 x 6

　20 10 0 f 6 ( S 6 ）

　86 ４8 0 当时( ( ２月) )：

　表 7-８ x 5 S 5

　0

　204

　 １

　 0 １42 2

　１22 ３０ 86 98 90

　0 ８6 ４０ 50 52

　 ０ ５0 50 4

　0 4 当时（1 1 月) ): 表 7－9 x 4 S 4

　2 1

　 ０、4０ 282 ２

　５2 20 ２５0 3

　 ３0 ２18 1０ 2１2 ４

　1

　 ５

　76 152

　0 1４4 6

　３2

　 0 1２6 当时 (1 ２月) ): 表 7-１0 ｘ 3 S ３

　 0 414 1

　８４ 50 38４ 2

　 ６2 ３3２ 5０ 332

　3

　42 310 3１4 0 ３02 4

　９

　 当时1 (11 月) ): 表 7-11 x 2 Ｓ 2

　68 5０ 468 1

　 ４6 452 4０ 4４６ 当时0 (10 月) ): 表７-１2 x 1 S 1

　６ 利用状态转移律,按上述计算得逆序可推算出最优策略:10 月份采购４箱（40 双)，11月份采购 5 箱（50 双),１2 月份不采购，1 月份采购 4 箱（４０双)，2 月份采购５箱(50 双),3月份不采购；最小得销售费用为 606 美元。

　２－4 4 用动态规划求解非线性规划问题

　非线性规划问题得求解(在第六章中已讨论)就是非常困难得；然而,对于有些非线性规划问题，如果转化为用动态规划来求解将就是十分方便得。

　[ [例 例 7 7 － 5] 用动态规划求解

　解:阶段:将问题得变量数作为阶段,即; 决策变量：决策变量; 状态变量:状态变量代表第阶段得约束右端项,即从到占有得份额; 状态转移律:; 边界条件:,; 允许决策集合 ：

　当时: :

　 当时: :

　 设,于就是 令,可得或 又因,所以：

　，就是得极小值点 ，就是得极大值点 于就是:

　当时: :

　 同上可得:

　由，有 由，有

　于就是得到最优解,最优值。

　习题: :

　1． 某公司打算向它得三个营业区增设 6 个销售店，每个营业区至少增设１个。各营业区每年增加得利润与增设得销售店个数有关,具体关系如表１所示。试规划各营业区应增设销售店得个数,以使公司总利润增加额最大。

　表 1 增设销售店个数 营业区 Ａ

　营业区 B

　营业区 C

　1 1００(万元) １2０(万元) 150(万元）

　２ １６０ 150 １65 3 19０ 170 175 4 200 180 1９０ 2． 某工厂有 100 台机器，拟分 4 个周期使用,在每一周期有两种生产任务，据经验把机器投入第一种生产任务,则在一个周期中将有六分之一得机器报废,投入第二种生产任务，则有十分之一得机器报废。如果投入第一种生产任务每台机器可收益 1 万元，投入第二种生产任务每台机器可收益 0、5 万元。问怎样分配机器在 4 个周期内得使用才能使总收益最大？ 3． 某公司生产一种产品,估计该产品在未来四个月得销售量分别为３00、４００、350 与２５０件。生产该产品每批得固定费用为 6０0 元,每件得变动费用为 5 元，存储费用为每件每月２元。假定第一个月月初得库存为 100 件,第四个月月底得存货为 5０件。试求该公司在这四个月内得最优生产计划。