动态规划的基本原理

二动态规划的基本原理对最短路问题：来源于动态规划的最优化原理最短路问题的基本方程：k=4,3,2,1由后向前迭代递推公式（一）例见PPT最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略对最短路问题：A○○B1○F○B2○B3○C1○C2○C3○D2○D1○E2○E1则不论前面A如何到达B，B又如何到达C1上堂课的主要内容：一、动态规划的基本概念1、阶段：指对整个过程的自然划分，用k表示2、状态变量skSk={sk}第k阶段的状态集合：第k阶段开始时所处的自然状况3、决策变量：当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策4、状态转移方程sk第k阶段的状态变量状态转移方程：5、策略：由各阶段的决策组成的序列称为策略——允许策略集合6、指标函数用于衡量所选定的策略优劣的数量指标称为指标函数最优策略二、最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略对最短路问题：A○○B1○F○B2○B3○C1○C2○C3○D2○D1○E2○E1则不论前面A如何到达B，B又如何到达C1对最短路问题：○C1○A○B1○E○B2○B3○C2○C3○D2○D18458961610967738423最短路问题的基本方程：k=4,3,2,1动态规划方法即基于这种思想，这种从终点逐段向始点方向寻找最短路线的方法，称为逆序算法例3（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产j个单位产品的费用为

每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。阶段k=1，2，3，4状态变量sk=第k个月月初的库存量i月1234g(i)需求2324状态转移方程：当k=4时，u4(s4)对应的总费用=生产费+库存费i月1234g(i)需求2324库存费E(i)=0.5i，最大库存容量为3个单位，最大生产能力为6个单位，计划开始和计划期末库存量为零012347436.5326215.51当k=3时，i月1234g(i)需求2324库存费E(i)=0.5i，最大库存容量为3个单位，最大生产能力为6个单位，计划开始和计划期末库存量为零012301230u3(3)对应的总费用=生产费+库存费i月1234g(i)需求2324库存费E(i)=0.5i，最大库存容量为3个单位，最大生产能力为6个单位，计划开始和计划期末库存量为零023451212.51313.51221123411.51212.51311.5120123811.51212.580301288011.512012347436.5326215.51当k=2时，i月1234g(i)需求2324u2(s2)对应的总费用=生产费+库存费023451212.51313.51221123411.51212.51311.5120123811.51212.5803012811.51280k=3当k=2时，012334561818.51617165234517.51815.516.5123417012313.51714.515.515.5415313.5017.51516当k=1时，i月1234g(i)需求2324u1(0)对应的总费用=生产费k=2012334561818.51617165234517.51815.516.512341717.51516012313.51714.515.515.5415313.50当k=1时，023452221.5212212