| |||
 1.1 多阶段决策问题在研究社会经济、经营管理和工程技术领域内的有关问题中&＃xff0c;有一类特殊形式的动态决策问题—多阶段决策问题。在多阶段决策过程中&＃xff0c;系统的动态过程可以按照时间进程分为相互联系而又相互区别的各个阶段&＃xff0c;在每个阶段都要进行决策。系统在每个阶段存在许多不同的状态&＃xff0c;在某个时点的状态往往要依某种形式受到过去某些决策的影响&＃xff0c;而系统的当前状态和决策又会影响系统过程今后的发展。因而在寻求多阶段决策问题的最优解时&＃xff0c;重要的是不能仅仅从眼前的局部利益出发进行决策&＃xff0c;而需要从系统所经过的整个期间的总效应出发&＃xff0c;有预见性地进行动态决策&＃xff0c;找到不同时点的最优决策及整个过程的最优策略。  下面举例说明什么是多阶段决策问题。 | |||
 例1&＃xff08;最短路线问题&＃xff09;在线路网络图5—1中&＃xff0c;从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离&＃xff0c;为使总运费最少&＃xff0c;必须找出一条由A至E总里程最短的路线。
| |||
| 为了找到由A至E的最短线路&＃xff0c;可以将该问题分成A—B—C—D—E 4个阶段&＃xff0c;在每个阶段都需要作出决策&＃xff0c;即在A点需决策下一步到B1还是到B2或B3&＃xff1b;同样&＃xff0c;若到达第二阶段某个状态&＃xff0c;比如B1 &＃xff0c;需决定走向C1还是C2 &＃xff1b;依次类推&＃xff0c;可以看出&＃xff1a;各个阶段的决策不同&＃xff0c;由A至E的路线就不同&＃xff0c;当从某个阶段的某个状态出发作出一个决策&＃xff0c;则这个决策不仅影响到下一个阶段的距离&＃xff0c;而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策&＃xff0c;使这些决策序列所决定的一条路线对应的总路程最短。 | |||
| 例2&＃xff08;带回收的资源分配问题&＃xff09;某厂新购某种机床125台。据估计&＃xff0c;这种设备5年后将被其它设备所代替。此机车如在高负荷状态下工作&＃xff0c;年损坏率为1/2&＃xff0c;年利润为10万元&＃xff1b;如在低负荷状态下工作&＃xff0c;年损坏率为1/5&＃xff0c;年利润为6万元。问应如何安排这些机床的生产负荷&＃xff0c;才能使5年内获得的利润最大&＃xff1f; | |||
| 本问题具有时间上的次序性&＃xff0c;在五年计划的每一年都要作出关于这些机床生产负荷的决策&＃xff0c;并且一旦作出决策&＃xff0c;不仅影响到本年利润的多少&＃xff0c;而且影响到下一年初完好机床数&＃xff0c;从而影响以后各年的利润。所以在每年初作决策时&＃xff0c;必须将当年的利润和以后各年利润结合起来&＃xff0c;统筹考虑。 与上面例1、例2类似的多阶段决策问题还有资源分配、生产存贮、可靠性、背包、设备更新问题等等。 | |||
1.2 动态规划的基本概念 1.阶段动态规划问题通常都具有时间或空间上的次序性&＃xff0c;因此求解这类问题时&＃xff0c;首先要将问题按一定的次序划分成若干相互联系的阶段&＃xff0c;以便能按一定次序去求解。如例1&＃xff0c;可以按空间次序划分为A—B—C—D—E 4个阶段&＃xff0c;而例2&＃xff0c;按照时间次序可分成5个阶段。 2.状态在多阶段决策过程中&＃xff0c;每阶段都需要作出决策&＃xff0c;而决策是根据系统所处情况决定的。状态是描述系统情况所必需的信息。如例1中每阶段的出发点位置就是状态&＃xff0c;例2中每年初拥有的完好机床数是作出机床负荷安排的根据&＃xff0c;所以年初完好机床数是状态。一般地&＃xff0c;状态可以用一个变量来描述&＃xff0c;称为状态变量。记第k 阶段的状态变量为  ,k&＃61;1,2, …,n.3.决策多阶段决策过程的发展是用各阶段的状态演变来描述的&＃xff0c;阶段决策就是决策者从本阶段某状态出发对下一阶段状态所作出的选择。描述决策的变量称为决策变量&＃xff0c;当第k 阶段的状态确定之后&＃xff0c;可能作出的决策要受到这一状态的影响。这就是说决策变量  还是状态变量 的函数&＃xff0c;因此&＃xff0c;又可将第k阶段状态下的决策变量记为()。在实际问题中&＃xff0c;决策变量的取值往往限制在某一范围之内&＃xff0c;此范围称为允许决策变量集合&＃xff0c;记作Dk( )。如例2中取高负荷运行的机床数为决策变量&＃xff0c;则0≤≤&＃xff08;是k阶段初完好机床数&＃xff09;为允许决策变量集合。4.状态转移方程在多阶段决策过程中&＃xff0c;如果给定了k 阶段的状态变量 和决策变量&＃xff0c;则第k&＃43;1阶段的状态变量 也会随之而确定。也就是说是xk和函数&＃xff0c;这种关系可记为 &＃61;T(xk, ) 称之为状态转移方程。 | |||
| 5.策略 在一个多阶段决策过程中&＃xff0c;如果各个阶段的决策变量 () &＃xff08;k&＃61;1&＃xff0c;2&＃xff0c;…&＃xff0c;n&＃xff09;都已确定&＃xff0c;则整个过程也就完全确定。称决策序列 为该过程的一个策略&＃xff0c;从阶段k到阶段n的决策序列称为子策略&＃xff0c;表示成 。如例1中&＃xff0c;选取一路线 就是一个策略&＃xff1a;
由于每一阶段都有若干个可能的状态和多种不同的决策&＃xff0c;因而一个多阶段决策的实际问题存在许多策略可供选择&＃xff0c;称其中能够满足预期目标的策略为最优策略。例1中存在12条不同路线&＃xff0c;其中  是最短线路。6.指标函数用来衡量过程优劣的数量指标&＃xff0c;称为指标函数。在阶段k的 状态下执行决策&＃xff0c;不仅带来系统状态的转移&＃xff0c;而且也必然对目标函数给予影响&＃xff0c;阶段效应就是执行阶段决策时给目标函数的影响。 多阶段决策过程关于目标函数的总效应是各阶段的阶段效应累积形成的。常见的全过程目标函数有以下两种形式&＃xff1a;&＃xff08;1&＃xff09;全过程的目标函数等于各阶段目标函数的和&＃xff0c;即&＃xff1a;
 &＃xff08;2&＃xff09;全过程的目标函数等于各阶段目标函数的积&＃xff0c;即&＃xff1a; 指标函数的最优值&＃xff0c;称为最优函数值。一般&＃xff0c;  &＃xff08;x1&＃xff09;表示从第1阶段 状态出发至第n阶段&＃xff08;最后阶段&＃xff09;的最优指标函数&＃xff0c;  &＃xff08;&＃xff09;表示从第k阶段状态出发至第n阶段的最优指标函数(k&＃61;1&＃xff0c;2&＃xff0c;…&＃xff0c;n&＃xff09;。 |
§ 2 动态规划的基本概念和最优化原理 | ||||||||
| 多阶段决策过程的特点是每个阶段都要进行决策&＃xff0c;具有n个阶段的决策过程的策略是由n个相继进行的阶段决策构成的决策序列。由于前阶段的终止状态又是后一阶段的初始状态&＃xff0c;因此确定阶段最优决策不能只从本阶段的效应出发&＃xff0c;必须通盘考虑&＃xff0c;整体规划。就是说&＃xff0c;阶段k的最优决策不应只是本阶段的最优&＃xff0c;而必须是本阶段及其所有后续阶段的总体最优&＃xff0c;即关于整个后部子过程的最优决策。 对此&＃xff0c;贝尔曼在深入研究的基础上&＃xff0c;针对具有无后效性的多阶段决策过程的特点&＃xff0c;提出了著名的多阶段决策的最优性原理&＃xff1a; “整个过程的最优策略具有这样的性质&＃xff1a;即无论过程过去的状态和决策如何&＃xff0c;对前面的决策所形成的状态而言&＃xff0c;余下的诸决策必须构成最优策略。” 简而言之&＃xff0c;最优性原理的含意就是&＃xff1a;最优策略的任何一部分子策略也必须是最优的。 | ||||||||
如例1&＃xff0c;是由A到E的最短路线&＃xff0c;我们在该路线上任取一点 &＃xff0c;按照最优性原理 应该是到E的最短路。很容易用反证法证明这一结论的正确性&＃xff0c;从而说明最优性原理的正确性。按最优性原理&＃xff0c;可以将例1分成A—B—C—D—E 4个阶段&＃xff0c;由后向前逐步求出各点到E的最短线路&＃xff0c;直至求出A至E的最短线路。 例1的路线图  | ||||||||
K&＃61;4时&＃xff0c;出发点有D1&＃xff0c;D2&＃xff0c;D3&＃xff0c;记
K&＃61;3时&＃xff0c;出发点有C1&＃xff0c;C2&＃xff0c;C3
| ||||||||
为了找出最短线路&＃xff0c;再按计算顺序反推回去&＃xff0c;可求出最优决策序列&＃xff0c;即由 组成最优策略&＃xff0c;也就是最短线路为&＃xff1a;
| ||||||||
从上面的例子不难看出&＃xff0c;对于最短线路问题&＃xff0c;有如下的递推关系&＃xff08;函数方程&＃xff09;&＃xff1a;
| ||||||||
一般情况下&＃xff0c;多阶段决策问题存在下面的递推关系&＃xff1a;
| ||||||||
这里 (,  )是第阶段采用决策产生的阶段效应&＃xff1b; 是边界条件&＃xff1b;“&＃xfe61;”号大多数情况下是 “&＃43;”号&＃xff0c;也可能是“×”号。称上述递推关系为动态规划的基本方程&＃xff0c;这个方程是最优化原理的具体表达形式。 | ||||||||
在基本方程中&＃xff0c; 都是已知函数&＃xff0c;最优子策略&＃xff08;&＃xff09;与 之间是递推关系&＃xff0c;要求出&＃xff08;&＃xff09;及&＃xff0c;需要先求出&＃xff0c;这就决定了应用动态规划基本方程求最优策略总是逆着阶段的顺序进行的。 | ||||||||
| 另一方面&＃xff0c;由于k&＃43;1阶段的状态
|
§ 3 建立动态规划数学模型的步骤 | |||
| “最优化原理”是动态规划的核心,所有动态规划问题的递推关系都是根据这个原理建立起来的,并且根据递推关系依次计算,最终可求得动态规划问题的解。 一般来说&＃xff0c;利用动态规划求解实际问题需先建立问题的动态模型&＃xff0c;具体步骤如下&＃xff1a; ⒈将问题按时间或空间次序划分成若干阶段。有些问题不具有时空次序&＃xff0c;也可以人为地引进时空次序&＃xff0c;划分阶段。⒉正确选择状态变量。这一步是形成动态模型的关键&＃xff0c;状态变量是动态规划模型中最重要的参数。一般来说&＃xff0c;状态变量应具有以下三个特性&＃xff1a;⑴要能够用来描述决策过程的演变特征。 ⑵要满足无后效性。即如果某阶段状态已给定后&＃xff0c;则以后过程的进展不受以前各状态的影响&＃xff0c;也就是说&＃xff0c;过去的历史只通过当前的状态去影响未来的发展。 ⑶递推性。即由k阶段的状态变量 及决策变量uk可以计算出k&＃43;1阶段的状态变量。⒊确定决策变量及允许决策变量集合Dk()。⒋根据状态变量之间的递推关系&＃xff0c;写出状态转移方程&＃xff1a;
⒌建立指标函数。一般用(, )描写阶段效应&＃xff0c;&＃xff08;&＃xff09;表示k—n阶段的最优子策略函数。 ⒍建立动态规划基本方程&＃xff1a; 以上是建立动态规划模型的过程&＃xff0c;这个过程是正确求解动态规划的基础。 在动态规划基本方程中&＃xff0c; (, )&＃xff0c; &＃61;T(, )都是已知函数&＃xff0c;最优子策略&＃xff08;&＃xff09;与 &＃xff08;&＃xff09;之间是递推关系&＃xff0c;要求出&＃xff08;&＃xff09;及()&＃xff0c;需要先求出&＃xff08;&＃xff09;&＃xff0c;这就决定了应用动态规划基本方程求最优策略总是逆着阶段的顺序进行的。由后向前逐步计算&＃xff0c;最终可以算出全过程的最优策略函数值及最优策略。 | |||
| 另一方面&＃xff0c;由于k&＃43;1阶段的状态&＃61;T(, )是由前面的状态和决策所形成的&＃xff0c;在计算&＃xff08;&＃xff09;时还不能具体确定的值&＃xff0c;所以&＃xff0c;这就要求必须就k&＃43;1阶段的各个可能状态计算&＃xff08;&＃xff09;&＃xff0c;因此动态规划方法不但能求出整个问题的最优策略和最优目标值&＃xff0c;而且还能求出决策过程中所有可能状态的最优策略及最优目标值。 | |||
| 下面就按上述步骤求解例2。 | |||
| 例2&＃xff08;带回收的资源分配问题&＃xff09;某厂新购某种机床125台。据估计&＃xff0c;这种设备5年后将被其它设备所代替。此机床如在高负荷状态下工作&＃xff0c;年损坏率为1/2&＃xff0c;年利润为10万元&＃xff1b;如在低负荷状态下工作&＃xff0c;年损坏率为1/5&＃xff0c;年利润为6万元。问应如何安排这些机床的生产负荷&＃xff0c;才能使5年内获得的利润最大&＃xff1f; | |||
解&＃xff1a;以年为阶段&＃xff0c;k&＃61;1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c; 取k年初完好的机床数为状态变量&＃xff0c; 以k年初投入高负荷运行的机床数为决策变量&＃xff0c;则低负荷运行机床数是-&＃xff0c;于是状态转移方程为&＃xff1a;
以利润为目标函数&＃xff0c;则k年利润为&＃xff1a;
记 &＃xff08;&＃xff09;为k年至5年末最大总利润&＃xff0c;则动态规划基本方程为&＃xff1a;
| |||
| 以上是建立动态模型的过程&＃xff0c;下面具体求解。 注意动态规划基本方程为&＃xff1a;     | |||
至此已算得最大总利润2790万元&＃xff0c;再按与计算过程相反的顺序推回去&＃xff0c;可得最优计划如下表所示&＃xff1a; |
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 
