第三部分动态规划（书第五部分） 动态规划为运筹学的一个分支，是解决多阶段决策过程最优化问题的一种数学方法，产生于50年 代。美R.Bellman(1951),将多阶段决策问题转化为一系列互相联系的单阶段问题，然后逐个加以解决， 提出了“最优性原理”，并研究了许多实际问题，创立了动态规划。 动态规划是现代企业管理中的一种重要的决策方法，可用来求解最优路线问题、资源分配问题、生 产调度问题、库存问题、排序问题、生产过程最优控制问题，特别对于离散性问题较有效，是有用的工 具。 动态规划是求解某类问题的一种方法，考察问题的一种途径，而不是一种特殊算法（不像线性规划）。 因而不像线性搞活那样有标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处 理。应以丰富的想象力去建立模型，用创造性的技巧去求解。 动态规划的模型分类： 1.离散决策过程和连续决策过程（根据多阶段决策过程的时间参量是离散的还是连续的变量）。 2.确定性决策过程和随机性决策过程（根据决策过程的演变是确定性的还是随机性的）。 组合起来有：离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。 本部分主要研究确定性决策过程，第四章介绍动态规划的基本概念、理论和方法，第五章将通过典 型问题来说明它的应用。 第四章动态规划的基本方法（书第8章) §4.1多阶段决策过程及实例（书§8.1） 有一类活动的过程，可分为若干个互相联系的阶段，在它的每一个阶段都需要做出决策，从而使整 个过程达到最好的活动效果，因此各个阶段的决策不是任意确定的，它依赖于当前面临的状态，又影响 以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动 路线。这种将一个问题看作是一个前后关联具有链状结构的多阶段过程，称为多阶段决策过程。 决策 决策 决策 状态 状态……状态 ·状态 在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态， 又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，因此把 处理它的方法称为“动态规划方法”。 一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因 素，也可把它视为多阶段决策问题，用动态规划方法去处理。 例4.1.1（最短路线问题，P192图8-2）给定一个线路网络，两点之间连线上的数字表示两点间的距 离（或费用）。试求一条由A到G的路线，使总距离为最短（或总费用最小）。 例4.1.2（机器负荷分配问题）某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生 产时，产品的年产量g和投入生产的机器数量u的关系为g=g(),这时机器的年完好率为a,0<a<1,即 如果年初完好机器的数量为“，到年终时完好的机器就为au。在低负荷下生产时，产品的年产量h和投 入生产的机器数量u的关系为h=h(),这时机器的年完好率为b,0<b<1,即如果年初完好机器的数量为 弘，到年终时完好的机器就为b。假定开始时完好的机器数量为S1。要求制定一个五年计划，在每年开 始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最 高。1 第三部分 动态规划（书第五部分） 动态规划为运筹学的一个分支，是解决多阶段决策过程最优化问题的一种数学方法，产生于 50 年 代。美 R.Bellman(1951)，将多阶段决策问题转化为一系列互相联系的单阶段问题，然后逐个加以解决， 提出了“最优性原理”，并研究了许多实际问题，创立了动态规划。 动态规划是现代企业管理中的一种重要的决策方法，可用来求解最优路线问题、资源分配问题、生 产调度问题、库存问题、排序问题、生产过程最优控制问题，特别对于离散性问题较有效，是有用的工 具。 动态规划是求解某类问题的一种方法，考察问题的一种途径，而不是一种特殊算法（不像线性规划）。 因而不像线性搞活那样有标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处 理。应以丰富的想象力去建立模型，用创造性的技巧去求解。 动态规划的模型分类： 1.离散决策过程和连续决策过程（根据多阶段决策过程的时间参量是离散的还是连续的变量）。 2.确定性决策过程和随机性决策过程（根据决策过程的演变是确定性的还是随机性的）。 组合起来有：离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。 本部分主要研究确定性决策过程，第四章介绍动态规划的基本概念、理论和方法，第五章将通过典 型问题来说明它的应用。 第四章 动态规划的基本方法（书第 8 章） §4.1 多阶段决策过程及实例(书§8.1) 有一类活动的过程，可分为若干个互相联系的阶段，在它的每一个阶段都需要做出决策，从而使整 个过程达到最好的活动效果，因此各个阶段的决策不是任意确定的，它依赖于当前面临的状态，又影响 以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动 路线。这种将一个问题看作是一个前后关联具有链状结构的多阶段过程，称为多阶段决策过程。 决策 决策 决策 状态 状态 … … 状态 状态 在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态， 又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，因此把 处理它的方法称为“动态规划方法”。 一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因 素，也可把它视为多阶段决策问题，用动态规划方法去处理。 例 4.1.1 (最短路线问题，P192 图 8-2)给定一个线路网络，两点之间连线上的数字表示两点间的距 离（或费用）。试求一条由 A 到 G 的路线，使总距离为最短（或总费用最小）。 例 4.1.2（机器负荷分配问题）某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生 产时，产品的年产量 g 和投入生产的机器数量 u 的关系为 g=g(u)，这时机器的年完好率为 a,0<a<1, 即 如果年初完好机器的数量为 u, 到年终时完好的机器就为 au。在低负荷下生产时，产品的年产量 h 和投 入生产的机器数量 u 的关系为 h=h(u)，这时机器的年完好率为 b,0<b<1, 即如果年初完好机器的数量为 u, 到年终时完好的机器就为 bu。假定开始时完好的机器数量为 s1。要求制定一个五年计划，在每年开 始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最 高