算法设计分析动态规划实例讲解.ppt

一、动态规划的基本思想 （二）、动态规划的基本思想 二、最短路径问题 三、非线性规划问题 【例7-4】 用动态规划方法解下列非线性规划问题 解： 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。 　　按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3 　　设状态变量为s1，s2，s3，s4并记s1≤c 　　取问题中的变量x1，x2，x3为决策变量 状态转移方程为： s3=x3 s3+x2=s2 s2+x1=s1≤c 允许决策集合为： x3=s3 0≤x2≤s2 0≤x1≤s1 　各阶段指标函数为：v1（x1）=x1 v2（x2）=x22 v3（x3）=x3， 　各指标函数以乘积方式结合，最优指标函数fk（sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为： 用逆序解法由后向前依次求解： k=3时， 　　　　　　　　 x3*=s3 k=2时， 令h2（s2，x2）=x22（s2－x2） 用经典解析法求极值点： 解得：　　　　　　　　　　　 x2=0（舍） 所以 　　　是极大值点。 k=1时， 令 解得：　　　　　　x1=s1（舍） 所以 是极大值点。 由于s1未知，所以对s1再求极值， 显然s1=c时，f1（s1）取得最大值 反向追踪得各阶段最优决策及最优值： s1=c 所以最优解为： 一般地，如果阶段指标函数vk（sk，uk）是线性函数或凸函数时，最优指标函数fk（sk）的表达式比较容易得到，但是当vk（sk，uk）不具备上述特性时，最优指标函数fk（sk）的表达式不易得到，就需要采用数值法，即对连续变量进行离散化处理，再分散求解。 例如静态规划模型 其动态规划基本方程为： 状态转移方程为sk+1=sk－xk s1=a 状态变量sk及决策变量xk都是连续变量，对其进行离散化处理，具体做法是： 1. 对区间[0，a]进行分割，分割数m= ，其中Δ是分割后的小区间的长度，其大小可以根据所求解问题要求的精度及计算机运算能力而定，分割点为0，Δ，2Δ，…，mΔ= a。 2. 规定状态变量sk及决策变量xk仅在离散点0，Δ，2Δ，…，mΔ处取值，最优指标函数fk（sk）也定义在这些离散点上。动态规划基本方程可以写为： 其中sk=qΔ，xk=pΔ。 3. 由后向前逐段递推，直至求出整个过程最优解。 【例7-5】 解 按变量个数将原问题分为三个阶段，阶段变量k=1，2，3； 选择xk为决策变量； 状态变量sk表示第k阶段至第3阶段决策变量之和； 取小区间长度Δ=1，小区间数目m=6/1=6，状态变量sk的取值点为： 状态转移方程：sk+1=sk－xk； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ k=1，2，3 xk，sk均在分割点上取值； 　阶段指标函数分别为：g1（x1）=x12 　　　　　　g2（x2）=x2 　　g3（x3）=x33， 　　　最优指标函数fk（sk）表示从第k阶段状态sk出发到第3阶段所得到的最大值，动态规划的基本方程为： 　　k=3时， 　　s3及x3取值点较多，计算结果以表格形式给出，见表7-1所示。 表7－1　取值 k=2时， 计算结果见表7-2 　　k=1时， 其中s1=6，计算结果见表7-3所示。 　　由表7-3知，x1*=2，s1=6，则s2= s1－x1*=6－2=4，查表7-2得：x2*=1，则s3= s2－x2*=4－1=3，查表7-1得：x3*=3，所以最优解为：x1*=2，x2*=1，x3*=3，f1(s1)=108。 　　　本例也可用经典解析法求得各段的极值，读者可自行求解，二者结论完全相同。需要指出的是当连续变量离散化处理以后，由于状态变量和决策变量只在给定的离散点上取值，故有可能漏掉最优解，因此需要慎重选择参数m与Δ。 四、资源分配问题 　　　假设有一种资源，数量为a，将其分配给n个使用者，分配给第i个使用者数量xi时，相应的收益为gi（xi），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为： 　　　这是一个静态规划问题，应用动态规划方法求解时人为赋予时间概念，将其看作是一个多阶段决策问题。 按变量个数划分阶段，k=1，2，…，n； 设决策变量uk=xk，表示分配给第k个使用者的资源数量； 设状态变量为sk，表示分配给第k个至第n个使用者的总资源数量； 状态转移方程：sk+1=sk－xk，其中s1=a； 允许