《运筹学》教学课件 第八章 动态规划.pdfVIP

Operations Research 第八章 动态规划 cmLiu@shufe Operations Research 第八章 动态规划 8.1 多阶段决策问题与动态规划 8.2 动态规划的基本概念 8.3 动态规划的基本思想和最优化原理 8.4 动态规划的应用 8.5 电子表格的建模和求解 8.6 案例分析 最优生产流程的选择 cmLiu@shufe Operations Research 8.1 多阶段决策问题与动态规划 8.1.1 多阶段决策问题 8.1.2 动态规划 cmLiu@shufe Operations Research 8.1.1 多阶段决策问题 在企业管理中，某些问题的决策过程可以划分为若干个 相互联系的阶段，每个阶段需要作出决策，从而使整个决 策过程达到最优。由于各个阶段不是孤立的，而是有机联 系的，即本阶段的决策结果是下一阶段进行决策的依据和 出发点，从而影响整个决策过程的结果。因此决策者在进 行决策时不仅要考虑决策方案使本阶段最优，而且还要考 虑本阶段决策对最终目标产生的影响，从而做出使全局达 到最优的决策。当每个阶段的决策确定以后，全部过程的 决策就是这些阶段决策所组成的一个决策序列，这样就确 定了整个决策过程的一条活动路线。 cmLiu@shufe Operations Research 8.1.1 多阶段决策问题 我们把这种可分解成若干个具有链状结构的相互联系的阶段 的决策问题称为多阶段决策问题，其决策过程见下图。 多阶段决策问题中，各个阶段一般是和时间有关系的，即随 着时间的发展而产生各个阶段的决策，从而形成决策序列，这 就是动态的含义。与时间有关的活动过程称为动态过程，其优 化方法称为动态规划。在一些与时间无关的静态问题中（如非 线性规划等），可以通过人为地赋予时间的概念，使其成为一 个多阶段决策问题，再用动态规划方法处理。 cmLiu@shufe Operations Research 8.1.1 多阶段决策问题 例8.1 最短路问题 某运输商要将货物从A地运往E地，中间通过B、C、 D三个区域，在区域内有多条路径可供选择，具体的网络如下图所示， 两点之间连线上的数字表示两点间的距离（或费用），问题是求一条 由A到E的线路，使总距离最短（或总费用最小）。 cmLiu@shufe Operations Research 8.1.1 多阶段决策问题 例8.2 车辆负荷问题 某货运公司有500辆卡车负责货物的运输任务，在 超负荷工作（即每天满载行驶500km 以上）情况下，每辆卡车每年可 获利润30万元，这时客车的年完好率为0.6；在低负荷工作（即每天 行驶300km 以下）情况下，每辆卡车每年可获利润20万元，这时客车 的年完好率为0.8。现在要求制定一个5年运输计划，问每年应投入到 两种负荷工作中的卡车数量是多少，才能使5年内总利润达到最大？ 例8.3 资源分配问题 假设有一种资源，其数量为a，现将它分配给n个使 用者。若分配给第i个使用者的数量为xi (i 1,2,,n )，产生的相应收益 g x 为 ( ) i i ，问如何分配使总收益最大？ 投资决策问题、生产存储问题、采购问题、设备更新问题等也都具有多阶 段决策问题的特征。