第7章 动态规划.ppt

第七章动态规划§1多阶段决策过程最优化问题举例一、基本概念：
1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。
2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。
3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。
决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。
4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。
5、状态转移方程sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。
6、阶段指标函数vk(sk,xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。
过程指标函数Vk,n(sk,xk,xk+1,…,xn)：从状态sk出发，选择决策xk,
xk+1,…,xn所产生的过程指标。动态规划要求过程指标具有可分离
性，即Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,…,xn)
称指标具有可加性，或Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)×Vk+1(sk+1,
xk+1,…,xn)称指标具有可乘性。

二、基本方程：
最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指
标Vk,n的最优值，即

对于可加性指标函数，上式可以写为

上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以
写为

以上式子称为动态规划最优指标的递推方程，是动态规划的基本
方程。
终端条件：为了使以上的递推方程有递推的起点，必须要设定最
优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。
三、最优化原理
作为整个过程的最优策略具有如下性质：
不管在此最优策略上的某个状态以前的状
态和决策如何，对该状态来说，以后的所有决
策必定构成最优子策略。就是说，最优策略的
任意子策略都是最优的。一、资源分配问题
例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工
厂。各工厂获得此设备后，预测可创造的利润如表所示，问这
5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？

表10-5
二、背包问题
设有n种物品，每一种物品数量无限。第i种物品每件
重量为wi公斤，每件价值ci元。现有一只可装载重量为W
公斤的背包，求各种物品应各取多少件放入背包，使背
包中物品的价值最高。
这个问题可以用整数规划模型来描述。设xi为第i种
物品装入背包的件数（i=1,2,…,n），背包中物品的总
价值为z，则
Maxz=c1x1+c2x2+…+cnxn
s.t.w1x1+w2x2+…+wnxn≤W
x1,x2,…,xn0且为整数。下面用动态规划逆序解法求解它。设
阶段变量k：第k次装载第k种物品（k=1,2,…,n）
状态变量sk：第k次装载时背包还可以装载的重量；
决策变量uk=xk：第k次装载第k种物品的件数；
决策允许集合：Dk(sk)={xk|0xksk/wk，xk为整数}；
状态转移方程：sk+1=skwkxk；
阶段指标：vk=ckxk；
最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使
用价值；
递推方程： fk(sk)=max{ckxk+fk+1(sk+1)}
=max{ckxk+fk+1(skwkxk)}；
xDk(sk)
终端条件：fn+1(sn+1)=0。例3.某咨询公司有10个工作日可以去处理四种类型的咨
询项目，每种类型的咨询项目中待处理的客户数量、处理每个
客户所需工作日数以及所获得的利润如表所示。显然该公
司在10天内不能处理完所有的客户，它可以自己挑选一些客
户，其余的请其他咨询公司去做，应如何选择客户使得在这10
个工作日中获利最大？

实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：

S.T.

且为整数。

我们不妨用此模型去求解例3，也一定得出同样的结果。

三、生产与存贮问题
例4.某公司为主要电力公司生产大型变压器，由于电力
采取预订方式购买，所以该公司可以预测未来几个月的需求
量。为确保需求，该公司为新的一年前四个月制定一项生产
计划，这四个月的需求如表1所示。
生产成本随着生产数量而变化。调试费为4，除了调度费
用外，每月生产的头两台各花费为2，后两台花费为1。最大
生产能力每月为4台，生产成本如表2所示。
表1表2

每台变压器在仓库中由这个月存到