运筹学教程五动态规划素材

1、第1，5章动态计划，不要过河拆桥，第2，动态计划动态计划，50年代牙齿代表贝尔曼(B. E. Bellman)的研究结果可以归结为一系列以长期利益为目标的决策最优化原理，这是现代控制理论的一部分。5.1动态编程的最优化原理和解决算法5.1.1牙齿多级决策过程的方法示例可以列举20条路径，例如5.1.1最短路问题、3、决策树方法、最短路径长度16，4、示例5.1.1最短路问题等。无论如何到达牙齿状态，都可以从B向后搜索，以找到最短路径、5，5.1.2动态计划的基本概念和迭代公式、1，基本概念1)阶段。将多阶段决策问题分为互连的多个阶段。通常，K是2)状态，即每个阶段开始时的状态。一个阶段的状态由

2、状态变量s k表示，k阶段的所有状态集由S k表示，每个阶段的所有状态集由S表示。s k S kS，动态计划的状态必须满足非滞后性。3)决定：特定阶段K状态s k的决定用决定变量x k(s k)表示。K阶段状态s k的允许判定集由D k(s k)表示，K阶段每个状态的允许判定集由D k表示，所有阶段每个状态的允许判定集由D表示。x k(s k)d k(s k)d k d 4)策略。也就是说，从特定阶段的特定状态到端点按顺序排列的决策组合的集合。Pk(s k)=x k(s k)、x k-1(s k-1)、x 1(s 1)表示从K阶段状态s k到端点的子策略。k阶段状态s k到端点允许的策略集为P

3、。Pk(s k)P。5)状态转移方程：反映两个相邻阶段的状态和决定变量之间的相互关系。s k-1=Tks k，x k(s k)=g(sk，x k)，6，5.1.2动态计划的基本概念和迭代公式，6) 7)总效果函数：子战略Pk(s k)的函数，从k阶段状态s k到结束Vk=Vk Pk(s k) 8)最佳效果函数：表示从特定阶段的特定状态采用最佳策略到终点的最佳效果值。2、记住最优化原理和动态计划迭代关系1、最优化原理：最优策略的子策略也是最优的。2，递归关系：7，3，动态规划阶段，1)分割阶段将研究的问题划分为K阶段，并对阶段编号。通常使用逆向编号进行编号。2)正确识别状态变量s k确定状态变量

4、s k，以便同时说明过程的演变和非滞后性。3)写决定变量x k(s k)和允许的决定集d k (s k)决定4)状态转移方程S K-1=G (S K，x k)。5)确定直接效果函数6)列出最佳金志洙函数的迭代关系7)边界条件确定，8，5.2动态计划模型示例，5.2.1资源分配问题示例5.2.1一家公司有4名在北京、上海和广州三个市场销售商品的销售人员，在牙齿三个市场中职员数和收益的关系如表5.2.1销售人员数和收益，解释1，和收益的关系2，确定状态变量s k状态变量s k表示在步骤K开始时未分配的销售人员数。显然，s3=4、S2和S1的可能范围为0 4。9，3，决策决策变量x k决策变量x k

5、表示分配给k阶段市场的销售人员数量。很明显，x k s k4，根据确定状态转移方程之前定义的状态变量s k和确定变量x k的含义，状态转移方程为S K-1=S K-X K。5.确定直接效果函数d k (s k，x k)表示在K阶段初期，销售人员数s k分配给K市场x k销售人员时产生的直接效果。这些收益指标见表5.2.1。6.最佳指标函数是金志洙函数累积的形式，因为三个市场的总收益等于三个市场的总收益之和。因此，最佳金志洙函数为7，边界条件F0 (s 0)=0。每个阶段的计算过程是教材P(138139)，10，5.2.2项目选择问题某工厂预计明年将有4个新项目A，B，C，D，每个项目的投资额w

6、k和投资后收益vk显示在右侧表格中。投资总额为30万韩元，问如何选择项目才能最大化总收益。上述问题的静态计划模型如下：这是0-1计划问题。牙齿问题是经典的旅行背包问题。牙齿问题是NP-complete，11。解决方案：项目选择顺序为A、B、C、D。步骤1K=1、2、3、4分别对应于项目D、C、B、A的选择过程2、K的状态sk，表示步骤K开始时未分配的投资额3、K的决策变量xk。指示k阶段项目是否被选定为4，状态转移表达式是否为SK1。Xk)=vk或0 6，总收益递归公式，牙齿问题的难点在于确定每个阶段的状态，随着阶段的增加，状态数呈指数增长。以下使用决策树确定每个步骤的可能状态：12，13，5

7、.2.3生产和库存管理问题一家工厂生产特定产品的月生产能力为10件，据了解，今后4个月的产品成本和销售量列在表中。如果本月产量超过销售量，可以储存，以后每月销售，一个产品的月存储费为2元，制定每月生产计划，1，保证满足每月销售量，计划开始和期末库存为0。2、计划生产能力允许范围内的每月生产计划，以最小化产品总成本(即生产成本存储成本)。14，实例1产品生产计划日程表，如果将xk设置为k阶段生产，则直接成本dk(sk，xk)=CK xk 2sk状态转移公式sk-1=sk xk- yk总成本迭代公式，步骤1:(四月)边界条件和状态转移公式s0=为了降低产品的次品率，为了最大限度地提高产品的成品率指

8、标，决定支出5万韩元进行技术改造。目前提出了以下四个茄子改进方案：方案1:不支出，机器保持原状。房间2:安装监视设备，每台机器需要1万韩元。房间3:安装设备，每台机器需要2万元。方案4:同时安装监视和控制设备，每台机器需要3万元。采用各方案后，各机器的次品率如下表所示。16，5.2.5连续性变量动态计划问题解决，计划一家工厂全年生产某种产品A。那个第四季度的订购量分别为600公斤、700公斤、500公斤、1200公斤。已知产品A的生产成本与产品的平方成正比，系数为0.005。工厂内有可以存放商品的仓库，仓储费为每公斤一元。寻求最佳生产安排，将年度总成本降至最低。解决方案：第4季度包含4个步骤，

9、使用工序号和分支顺序。如果将Sk设置为K季度现有量，则边界条件设置为s1=s5=0，xk设置为K季度产量，yk设置为K季度订货量。Sk，xk，yk均为实数，状态转换方程sk 1=sk xk-yk仍使用反向递归，但步骤编号为正向目标函数17，生产库存管理问题(连续变量)，步骤1:(第4季度)总效果F4 (SK解决方法：x4*)F4 *(S4)=0.005(1200 S4)2 S4=7200 11 S4 0.005 s42第二个X3)=0.005 x32 S3 F4 *(S4)S4=S3 X3 500至f3(s3X3*=800，S4 *=300X4*=900。20，5.2.6动态计划方法非线性计划解决，解决：这是资源分配问题。将分配顺序设置为x1、x2、x3、阶段向前编号，但反向迭代可以从约束条件中获得边界条件s1=27、s4=0。步骤3:(指定x3)，边界条件和状态切换方程式为s4=s3x3=0，即x3 *=s3是。因此，步骤2:(x2分配)，在状态转换方程中：s3=s2x2，替代表达式，21，5.2.6解析动态计划方法非线性计划，步骤1:(x1分配)2，fk*(sk)是从步骤k到步骤3的最佳1)状态转移方程式：sk=sk-1-xk-1，s1=10，s4=0 2) F3*(s3)=4x3=步骤4 S3 2 F2(S2)