《数学建模与数据学实验》课件第5章.ppt

式（5.12）通常称为边界条件，为过程结束或开始时的状态。式（5.11）和式（5.12）一起被称为动态规划的基本函数方程，即动态规划的基本方程，也被称为递归方程。用动态规划方法解决实际问题，需要根据实际情况建立动态规划的数学模型，这是解决整个问题中非常重要的一步，也是很困难的一步。

建立动态规划的数学模型一般包括以下步骤：

（1）划分阶段——依据实际问题的性质，按照时间或空间的顺序，将过程划分为若干个相互联系的阶段，将求解精度和计算速度等多方面因素综合考虑，以便有效地求解。（2）确定状态变量及其取值范围——状态变量既能描述过程演变的状态，又要满足无后效性的要求，且状态变量的维数应尽量地小，一般是从限制系统运筹的条件或从问题的约束条件中去寻找，在确定状态变量后还需进一步明确变量在各阶段的取值范围，即确定允许状态集合。

（3）确定决策变量及其取值范围——决策变量是状态的函数，对于k阶段的决策变量确定后，它将影响本阶段的效应，并会影响下一阶段的初始状态，从而影响第k+1阶段到最终状态的最优指标函数。决策变量的取值范围，即确定允许决策集合。（4）建立状态转移方程——如果给定第k阶段状态变量式sk的值，则该阶段的决策变量xk一经确定，第k+1阶段的状态变量sk+1的值也就完全确定了，即状态转移方程sk+1=Tk(sk，xk)必须具有递推关系。

（5）确定阶段效应和最优指标函数，建立动态规划的函数方程——阶段效应函数rk(sk，xk)根据问题的性质，可以为收益函数或损耗函数，而第k阶段的最优指标函数fk(sk)是指从k阶段到n阶段获得的总效应，要求fk(sk)是按阶段单调的，最后建立满足式（5.11）和式（5.12）的基本函数方程。以上5个步骤全部完成后，即完成了动态规划数学模型的建立，而这并不是轻而易举的，需要读者不断地实践并总结经验，才能深刻领会，才能有效地解决此类问题。

2.动态规划的求解方法

经过长期对实际问题的研究发现，最常见的最优指标函数形式有两类,即加法型和乘法型，所以动态规划的递推形式的基本方程分别为和通过递推基本方程式（5.13）（或式（5.14））及状态转移方程（5.10）求解动态规划的过程，可以发现,是由

k=n递推至k=1，这种由后向前逐步递推的方法，称为逆序解法。逆序解法是一般常用的方法，当求出全过程的最优策略时即可得到原问题的最优解。有些问题也可采用由前向后逐步递推的方法，称为顺序解法，这时状态转移方程和基本方程（加法型的）分别为同理，与最优指标函数是乘法形式对应的基本方程，读者也可以很容易地写出。既可用逆序解法求解，又可用顺序解法求解的多阶段决策过程，称为可逆过程，如最短路线问题的求解过程就是一个可逆过程。在此主要讨论逆序解法，顺序解法类似。以下通过举例来讲述动态规划建模及求解的全过程。【例5.22】(投资分配问题)

假设某工业部门通过各种正规渠道共筹集了600万元的资金供四个老企业进行技术改造，各企业技术改造后所得的利润（万元）与投资额（百万元）大小的关系如表5.28所示。要求确定各工厂的投资资金，使得这些工厂接受后，该部门的总利润达到最大。分析：这类问题属极为典型的“资源分配”问题，即解决如何将一定数量的一种或若干种资源（如人力、资金、材料、时间等），合理分配给若干个使用者（或生产方式），使资源的投放可以达到最优。

假定有一种资源，其数量为a，现需要将它分配给n个使用者，而使总收益最大。若分配给第i个使用者的数量为xi(i=1，2，…，n)，且由此产生的收益为gi(xi)，gi(xi)自然应该是xi的非递减函数，于是该问题的数学模型为(5.17)这是一种资源的分配问题，称为一维分配问题。解这是一类静态的线性或非线性规划问题，此类问题可以看做一个多阶段决策问题，利用动态规划的方法进行求解。

建立动态规划数学模型：把资金分配给前k个工厂的过程作为第k个阶段（k=1，2，3，4），这样就将过程划分为相互联系的四个阶段。设状态变量sk为分配给第k个工厂到第n个工厂的资金总额，即k阶段初所拥有的资金额，显然可知0≤sk≤a（a=600万元，此不等式即允许状态集合）。决策变量xk为分配给第k个工厂的资金额，此处0≤xk≤sk。

状态转移方程为阶段收益函数gk(sk，xk)为第k个工厂接受xk资金后所得的利润。最优指标函数fk(sk)就是将资金sk完全