运筹学教材课件(第四章-动态规划)

运筹学（普通高等教育运筹学（普通高等教育“十二五十二五”经经济与管理类专业核心课程规划教材）济与管理类专业核心课程规划教材）n主编：主编：郭鹏n出版社：出版社：西安交通大学出版社n出版时间：出版时间：2013-12-01运 筹 学运 筹 学n 绪论n 第1章 线性规划n 第2章 线性规划的对偶理论n 第3章 特殊线性规划n 第第4 4章章 动态规划动态规划n 第5章 图与网络分析n 第6章 排队论n 第7章 库存论n 第8章 决策论n 第9章 对策论运 筹 学n4.1 动态规划的范例n4.2 动态规划的模型n4.3 动态规划的应用n4.4 本章小结 第4章 动态规划杜黎制作杜黎制作 动态规划（动态规划（DynamicProgramming）是解决）是解决多阶段决策多阶段决策过程最优化问题过程最优化问题的一种方法，该方法是由美国数学家贝尔曼的一种方法，该方法是由美国数学家贝尔曼等人在等人在20世纪世纪50年代初提出的。由于其独特的解题思路，成年代初提出的。由于其独特的解题思路，成为了运筹学的一个重要分支。为了运筹学的一个重要分支。4.1 动态规划的范例 多阶段决策过程多阶段决策过程最优化问题的最优化问题的目标目标是要整个活动过程的是要整个活动过程的总目标达到最优。由于每个阶段的决策都将影响到下一阶段总目标达到最优。由于每个阶段的决策都将影响到下一阶段的决策，甚至于总目标，所以，决策者在每阶段决策时，不的决策，甚至于总目标，所以，决策者在每阶段决策时，不能只考虑本阶段最优，还需考虑对总目标的影响，从而作出能只考虑本阶段最优，还需考虑对总目标的影响，从而作出使总目标达到最优的决策。使总目标达到最优的决策。4.1 动态规划的范例 动态规划是解决动态规划是解决多阶段决策过程最优化问题多阶段决策过程最优化问题的一种方法，的一种方法，而多阶段决策过程是指其活动过程可以按照时间进程分为若而多阶段决策过程是指其活动过程可以按照时间进程分为若干相互联系的阶段，在每个阶段决策者都要进行决策，全部干相互联系的阶段，在每个阶段决策者都要进行决策，全部阶段的决策组成了一个决策序列。阶段的决策组成了一个决策序列。动态规划动态规划本质上本质上是一个是一个递推方程递推方程，把问题的各阶段联系，把问题的各阶段联系起来，保证每个阶段的最优可行解对于整个问题是可行的也起来，保证每个阶段的最优可行解对于整个问题是可行的也是最优的。动态规划的计算递推进行，以便让一个子问题的是最优的。动态规划的计算递推进行，以便让一个子问题的最优解作为下一个子问题的输入，当最后一个子问题求解完最优解作为下一个子问题的输入，当最后一个子问题求解完成，也就得到了整个问题的最优解。成，也就得到了整个问题的最优解。4.1 动态规划的范例 相较于线性规划和非线性规划方法，动态规划通过把一相较于线性规划和非线性规划方法，动态规划通过把一个多变量问题分解成若干个阶段，个多变量问题分解成若干个阶段，每个阶段是一个单变量每个阶段是一个单变量（或少变量）的子问题（或少变量）的子问题，来求出这个多变量问题的最优解。，来求出这个多变量问题的最优解。这种分解的好处是，每个阶段的优化问题涉及变量少，从计这种分解的好处是，每个阶段的优化问题涉及变量少，从计算上来说比同时处理多个变量更加简单。算上来说比同时处理多个变量更加简单。这种方法可用于解决最优路径问题、资源分配问题、生这种方法可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题。产计划与库存、投资、装载、排序等问题。4.1 动态规划的范例例例4.1最短路径问题最短路径问题一位旅行者准备从一位旅行者准备从A地前往地前往H地，图地，图4-1给出了从给出了从A地到地到H地所有可能的路径，地所有可能的路径，B地至地至G地表示这些路径途中需要经过地表示这些路径途中需要经过的城市，城市之间的数字表示两地之间的距离，请帮助旅行的城市，城市之间的数字表示两地之间的距离，请帮助旅行者选择一条最短路径。者选择一条最短路径。4.1 动态规划的范例例例4.1最短路径问题最短路径问题分析：分析：可以可以在每个连续阶段选择最短路径在每个连续阶段选择最短路径，从而挑选出一条，从而挑选出一条从从A地到地到H地的路径，例如，地的路径，例如，ADGH=15。但是，采用。但是，采用这种方法得到的路径未必是最短路径这种方法得到的路径未必是最短路径。例。例如如，ADFH=13要比要比15更短些。更短些。4.1 动态规划的范例例例4.1最短路径问题最短路径问题分析：分析：也可以用也可以用枚举法枚举法列出从列出从A地到地到H地的所有路径，通过地的所有路径，通过对比找出最短路径。但是，对于大的网络来说，采用枚举法对比找出最短路径。但是，对于大的网络来说，采用枚举法其计算量将会大的难以处理。其计算量将会大的难以处理。4.1 动态规划的范例例例4.1最短路径问题最短路径问题分析：分析：下面采用动态规划来求解这个问题。首先，将这个问下面采用动态规划来求解这个问题。首先，将这个问题分解成题分解成3个阶段，见图个阶段，见图4-2。4.1 动态规划的范例例例4.1最短路径问题最短路径问题分析：分析：确定最短路径的一般思路是，从第一阶段开始，对每确定最短路径的一般思路是，从第一阶段开始，对每个阶段的所有终止点，计算出从起点到该阶段各终止点的最个阶段的所有终止点，计算出从起点到该阶段各终止点的最短距离，然后利用这些最短距离计算从起点到下一阶段所有短距离，然后利用这些最短距离计算从起点到下一阶段所有终止点的最短距离，直至原问题的终止点。由于问题求解过终止点的最短距离，直至原问题的终止点。由于问题求解过程与活动发展进程顺序一致，所以将这种解法称为程与活动发展进程顺序一致，所以将这种解法称为顺序解法顺序解法。还有一种解法，其问题求解过程与活动发展进程顺序相反，还有一种解法，其问题求解过程与活动发展进程顺序相反，将这种解法称为逆序解法。我们将在后面介绍这种解法。将这种解法称为逆序解法。我们将在后面介绍这种解法。4.1 动态规划的范例例例4.1最短路径问题最短路径问题解：解：阶段阶段1有三个终点，有三个终点，B地、地、C地和地和D地。各点距离地。各点距离A地只有地只有一条路径。于是一条路径。于是，有有从从A地到地到B地的最短距离地的最短距离=5（百公里）（百公里）（从（从A地出发）地出发）从从A地到地到C地的最短距离地的最短距离=4（百公里）（百公里）（从（从A地出发）地出发）从从A地到地到D地的最短距离地的最短距离=3（百公里）（百公里）（从（从A地出发）地出发）4.1 动态规划的范例例例4.1最短路径问题最短路径问题解：解：阶段阶段2有三个终点，有三个终点，E地、地、F地和地和G地。先考虑地。先考虑E地。从图地。从图4-2可以看出，可以看出，E地可以经过地可以经过B地或者地或者C地地2条不同路径到达。条不同路径到达。4.1 动态规划的范例例例4.1最短路径问题最短路径问题解：解：利用上一阶段得到的结果（从利用上一阶段得到的结果（从A地分别到达地分别到达B地和地和C地的地的最短距离），再加上最短距离），再加上B地和地和C地分别到达地分别到达E地的距离，我们就地的距离，我们就能确定出从能确定出从A地到达地到达E地的最短距离为地的最短距离为从从A地到地到E地的最短距离地的最短距离=从从A地到地到i地的最短距离地的最短距离+从从i地地到到E地的距离地的距离4.1 动态规划的范例因此因此，从从A地出发到达地出发到达E地，途地，途中经中经C地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：类似的，类似的，F地可以经过地可以经过B地和地和D到达。到达。因此，因此，从从A地到地到F地的最短距离地的最短距离=从从A地到地到i地的最短距离地的最短距离+从从i地地到到F地的距离地的距离4.1 动态规划的范例因此，因此，从从A地出发到达地出发到达F地，途中经地，途中经D地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：而而G地可以经过地可以经过B地、地、C地或地或D地到达，有地到达，有从从A地到地到G地的最短距离地的最短距离=从从A地到地到i地的最短距离地的最短距离+从从i地地到到G地的距离地的距离4.1 动态规划的范例因而，因而，从从A地出发到达地出发到达G地，途中经地，途中经D地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：因此，在阶段因此，在阶段2，从从A地到地到E地的最短距离地的最短距离=8（百公里）（百公里）从从C地出发地出发从从A地到地到F地的最短距离地的最短距离=8（百公里）（百公里）从从D地出发地出发从从A地到地到G地的最短距离地的最短距离=6（百公里）（百公里）从从D地出发地出发4.1 动态规划的范例例例4.1最短路径问题最短路径问题解：解：阶段阶段3只有一个终点，只有一个终点，H地。地。H地可以经过地可以经过E地、地、F地或者地或者G地地3条不同路径到达。利用上一阶段得到的结果，再加上分条不同路径到达。利用上一阶段得到的结果，再加上分别从别从E地地,F地和地和G地到达地到达H地的距离。于是，我们有地的距离。于是，我们有从从A地到地到H地的最短距离地的最短距离=从从A地到地到i地的最短距离地的最短距离+从从i地地到到H地的距离地的距离4.1 动态规划的范例因此因此，从从A地出发到达地出发到达H地，地，途中经途中经F地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：综上所述综上所述，从，从A地到地到H地的最短距离是地的最短距离是13百公里。为了得百公里。为了得到最优路径，我们可以根据求解结果从后向前逆推，阶段到最优路径，我们可以根据求解结果从后向前逆推，阶段3的的最优解表示从最优解表示从A地出发经地出发经F地到达地到达H地是最短距离，阶段地是最短距离，阶段2的最的最优解表示从优解表示从A地出发经地出发经D地到达地到达F地是最短距离，阶段地是最短距离，阶段1的最优的最优解表示从解表示从A地出发到达地出发到达D地是最短距离，即最短路径为地是最短距离，即最短路径为ADFH。4.1 动态规划的范例通过通过最短路径问题最短路径问题，可以看出动态规划方法的，可以看出动态规划方法的基本特性基本特性：(1)计算从计算从A地到当前阶段各终点的最短距离时需要用到上一地到当前阶段各终点的最短距离时需要用到上一阶段的计算结果；阶段的计算结果；(2)每个阶段所做的计算都是该阶段可行路径的函数。每个阶段所做的计算都是该阶段可行路径的函数。4.1 动态规划的简介与范例若若用数学公式来表示上例中的递推关系用数学公式来表示上例中的递推关系：4.1 动态规划的简介与范例n表示表示阶段阶段，n=1,2,3sn表示第表示第n阶段的阶段的起点起点fn(sn)表示第表示第n阶段从阶段从A地到达地到达sn+1地的地的最短距离最短距离dn(sn,sn+1)为从为从sn地地到到sn+1的的距离（若从距离（若从sn到到sn+1没有通路，令没有通路，令dn(sn,sn+1)=)于是，于是，fn(sn+1)可以从下面的递推公式计算出来：可以从下面的递推公式计算出来：上面，用顺序解法从阶段上面，用顺序解法从阶段1到阶段到阶段3由前向后逐步计算，由前向后逐步计算，这个例子也可以用逆序解法从阶段这个例子也可以用逆序解法从阶段3到阶段到阶段1由后向前逐步计由后向前逐步计算。无论是采用顺序解法，还是采用逆序解法，得到的解都算。无论是采用顺序解法，还是采用逆序解法，得到的解都是相同的。是相同的。4.1 动态规划的简介与范例 顺序解法较符合逻辑，但在动态规划文献中普遍采用逆顺序解法较符合逻辑，但在动态规划文献中普遍采用逆序解法。逆序解法的求解思路与顺序解法刚好相反，从最后序解法。逆序解法的求解思路与顺序解法刚好相反，从最后一个阶段开始，对每个阶段的所有起点，计算出该阶段所有一个阶段开始，对每个阶段的所有起点，计算出该阶段所有起点至终点的最短距离，然后利用这些最短距离计算下一阶起点至终点的最短距离，然后利用这些最短距离计算下一阶段所有起点至终点的最短距离，直至第一阶段。下面，我们段所有起点至终点的最短距离，直至第一阶段。下面，我们用用逆序解法逆序解法来求解例来求解例4-1。例例4.1最短路径问题最短路径问题解：解：阶段阶段3有有3个起点，个起点，E地、地、F地和地和G地。从地。从E地、地、F地和地和G地地出发分别只有出发分别只有1条路径至条路径至H地。因此，阶段地。因此，阶段3的结果可归结为的结果可归结为从从E地到地到H地的最短距离地的最短距离=6（百公里）（百公里）（连接至（连接至H地）地）从从F地到地到H地的最短距离地的最短距离=5（百公里）（百公里）（连接至连接至H地）地）从从G地到地到H地的最短距离地的最短距离=9（百公里）（百公里）（连接至（连接至H地）地）4.1 动态规划的范例例例4.1最短路径问题最短路径问题解：解：阶段阶段2有有3个起点，个起点，B地、地、C地和地和D地。地。先考虑先考虑B地。从图地。从图4-2可以看出，可以看出，B地可以经过地可以经过E地、地、F地或者地或者G地地3条不同路径到达条不同路径到达H地地。4.1 动态规划的范例例例4.1最短路径问题最短路径问题解：解：利用从利用从B地出发分别到达地出发分别到达E地、地、F地和地和G地的距离再加上地的距离再加上从从E地、地、F地和地和G地出发至地出发至H地的最短距离，我们就能确定出地的最短距离，我们就能确定出从从B地出发到达地出发到达H地的最短距离为地的最短距离为从从B地到地到H地的最短距离地的最短距离=从从B地到地到i地的距离地的距离+从从i地到地到H地的最短距离地的最短距离4.1 动态规划的范例因此因此，从从B地出发到达地出发到达H地，地，途中经途中经F地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：类似的，类似的，C地可以经过地可以经过E地或者地或者G地地2条不同路径到达条不同路径到达H地地。因此，。因此，从从C地到地到H地的最短距离地的最短距离=从从C地到地到i地的距离地的距离+从从i地到地到H地的最短距离地的最短距离4.1 动态规划的范例因此因此，从从C地出发到达地出发到达H地，地，途中经途中经E地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：最后，最后，D地可以经过地可以经过F地或者地或者G地地2条不同路径到达条不同路径到达H地。地。于是，于是，从从D地到地到H地的最短距离地的最短距离=从从D地到地到i地的距离地的距离+从从i地到地到H地的最短距离地的最短距离4.1 动态规划的范例因此因此，从从D地出发到达地出发到达H地，地，途中经途中经F地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：由此可知，在阶段由此可知，在阶段2，从从B地到地到H地的最短距离地的最短距离=9（百公里）（百公里）（连接至（连接至F地）地）从从C地到地到H地的最短距离地的最短距离=10（百公里）（百公里）（连接至（连接至E地）地）从从D地到地到H地的最短距离地的最短距离=10（百公里）（百公里）（连接至连接至F地）地）4.1 动态规划的范例例例4.1最短路径问题最短路径问题解：解：阶段阶段1只有一个起点，只有一个起点，A地。地。A地可以经过地可以经过B地、地、C地或地或D地地3条不同路径到达条不同路径到达H地。从地。从A地出发分别到达地出发分别到达B地、地、C地和地和D地的距离再加上从地的距离再加上从B地、地、C地和地和D地出发至地出发至H地的最短距离，地的最短距离，就能确定出从就能确定出从A地出发到达地出发到达H地的最短距离为地的最短距离为从从A地到地到H地的最短距离地的最短距离=从从A地到地到i地的距离地的距离+从从i地到地到H地的最短距离地的最短距离4.1 动态规划的范例因此因此，从从A地出发到达地出发到达H地，地，途中经途中经D地的距离最短地的距离最短。例例4.1最短路径问题最短路径问题解：解：阶段阶段1的结果表示从的结果表示从A地到地到H地的最短距离为地的最短距离为13百公里，百公里，其最优解表示从其最优解表示从A地出发至地出发至D地，阶段地，阶段2的最优解表示从的最优解表示从D地地出发至出发至F地，阶段地，阶段3的最优解表示从的最优解表示从F地出发至地出发至H地，即最短地，即最短路径为路径为ADFH，这个结果与顺序解法得到的最短路径，这个结果与顺序解法得到的最短路径一样一样。4.1 动态规划的范例最后，给出该问题逆序解法的递推方程最后，给出该问题逆序解法的递推方程：4.1 动态规划的简介与范例n表示表示阶段阶段，n=1,2,3sn表示第表示第n阶段的阶段的终终点点fn(sn)表示第表示第n阶段从阶段从sn地出发到达地出发到达H地的地的最短距离最短距离dn(sn,sn+1)为从为从sn地地到到sn+1的的距离（若从距离（若从sn到到sn+1没有通路，令没有通路，令dn(sn,sn+1)=)于是，于是，fn(sn)可以从下面的递推公式计算出来：可以从下面的递推公式计算出来：4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念(1)阶段阶段，将所给问题的过程，按时间或空间特征分解成将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。描述若干相互联系的阶段，以便按次序去求每阶段的解。描述阶段的变量称为阶段的变量称为阶段变量阶段变量，常用，常用n表示。表示。阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数(2)状态状态，表示，表示每阶段开始时每阶段开始时系统所处于系统所处于的客观条件的客观条件。用用sn表示第表示第n阶段的阶段的状态变量状态变量，Sn表示状态变量表示状态变量sn的取值的取值集合，称为集合，称为状态可能集状态可能集。4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 状态状态变量变量应具有如下性质：当某阶段状态给定后，该阶段应具有如下性质：当某阶段状态给定后，该阶段以后的过程发展不受该阶段以前各阶段状态的影响。以后的过程发展不受该阶段以前各阶段状态的影响。无后效性无后效性4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数(3)决策决策，指决策者根据本阶段的状态所作出的行动选择。，指决策者根据本阶段的状态所作出的行动选择。用用xn(sn)表示第表示第n阶段当状态为阶段当状态为sn时的时的决策变量决策变量，Dn(sn)表示第表示第n阶段从状态阶段从状态sn出发的出发的允许决策集合允许决策集合。4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 策略策略各阶段的决策确定后，整个问题的决策序列就构各阶段的决策确定后，整个问题的决策序列就构成了一个策略。成了一个策略。策略有策略有全过程策略全过程策略和和n-子策略子策略之分之分。全过程全过程策略表示为策略表示为：p1,N u1(s1),u2(s2),uN(sN)允许策略集合：允许策略集合：P1,N使问题达到整体最优的策略就是使问题达到整体最优的策略就是最优策略最优策略。4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数(4)状态转移方程状态转移方程，描述从阶段，描述从阶段n到阶段到阶段n+1的状态转移规的状态转移规律的表达式。动态规划中本阶段的状态往往是上一阶段的律的表达式。动态规划中本阶段的状态往往是上一阶段的状态和决策的共同结果。状态和决策的共同结果。它可用下面的公式表示：它可用下面的公式表示：sn+1=Tn(sn,un)4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数(5)指标函数指标函数，用于衡量所选择策略优劣的数量指标，用于衡量所选择策略优劣的数量指标，它分为它分为阶段指标函数阶段指标函数和和过程指标函数过程指标函数两种。两种。4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 阶段指标函数阶段指标函数是指第是指第n阶段从状态阶段从状态sn出发，采取决策出发，采取决策un时在本阶段所获得的效益，用时在本阶段所获得的效益，用rn(sn,un)表示。表示。4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 对于一个对于一个n阶段决策过程，从第阶段决策过程，从第1阶段到第阶段到第n阶段称为问题的阶段称为问题的原过程原过程。用用V1,N(s1,p1,N)表示表示第第1阶段从状态阶段从状态s1出发采取策略出发采取策略p1,N时时原过程的指标函数值原过程的指标函数值。4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 对于任一给定对于任一给定n，从第，从第n阶段到第阶段到第N阶段称为原过程的一个阶段称为原过程的一个后后部子过程部子过程。用用Vn,N(sn,p1,N)表示表示第第n阶段从状态阶段从状态sn出发采取策略出发采取策略pn,N时时后部子过程的指标函数值后部子过程的指标函数值。4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 若过程指标函数值是阶段指标若过程指标函数值是阶段指标和和的形式，那么的形式，那么若过程指标函数值是阶段指标若过程指标函数值是阶段指标连乘连乘的形式，那么的形式，那么4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 用用fn(sn)表示表示最优指标函数，即第最优指标函数，即第n阶段从状态阶段从状态sn出发采取最出发采取最优策略优策略p*n,N到过程终止时的最佳效益值。到过程终止时的最佳效益值。fn(sn)和和Vn,N(sn,pn,N)之间的关系：之间的关系：4.2 动态规划模型的建立和求解4.2.1动态规划的基本概念动态规划的基本概念 阶段；状态；决策和策略；状态转移方程；指标函数阶段；状态；决策和策略；状态转移方程；指标函数 若过程指标函数值是阶段指标若过程指标函数值是阶段指标和和的形式，那么的形式，那么若过程指标函数值是阶段指标若过程指标函数值是阶段指标连乘连乘的形式，那么的形式，那么4.2 动态规划模型的建立和求解4.2.2动态规划的动态规划的求解求解逆序解法逆序解法从过程的最后一阶段开始，由后向前递推，逐步从过程的最后一阶段开始，由后向前递推，逐步求出各阶段的最优决策及相应的最优值，最后求得的结果就求出各阶段的最优决策及相应的最优值，最后求得的结果就是整个问题的最优解。是整个问题的最优解。顺序解法顺序解法从过程的第一阶段开始逐段向后递推，最后一段从过程的第一阶段开始逐段向后递推，最后一段的结果即是全过程的最优结果。的结果即是全过程的最优结果。4.2 动态规划模型的建立和求解逆序解法和顺序解法的区别逆序解法和顺序解法的区别(1)阶段划分是一样的。阶段划分是一样的。(2)状态变量的选取不同。状态变量的选取不同。在逆序解法中，将每一阶段初系统所处的客观条件作为在逆序解法中，将每一阶段初系统所处的客观条件作为状态变量。在顺序解法中刚好相反，以每一阶段末系统处状态变量。在顺序解法中刚好相反，以每一阶段末系统处于的客观条件于的客观条件sn+1作为状态变量。因此，当初始状态给定时，作为状态变量。因此，当初始状态给定时，用逆序解法；当终止状态给定时，用顺序解法。用逆序解法；当终止状态给定时，用顺序解法。4.2 动态规划模型的建立和求解(3)决策变量的选取不同。决策变量的选取不同。既然状态变量不一样，决策变量作为状态变量的函数，既然状态变量不一样，决策变量作为状态变量的函数，它的选取以及允许决策集也都是不一样的。在逆序解法中，它的选取以及允许决策集也都是不一样的。在逆序解法中，决策变量为决策变量为xn(sn)，允许决策集为，允许决策集为Dn(sn)；而在顺序解法中，；而在顺序解法中，决策变量为决策变量为xn(sn+1)，允许决策集为，允许决策集为Dn(sn+1)。逆序解法和顺序解法的区别逆序解法和顺序解法的区别4.2 动态规划模型的建立和求解(4)状态转移方程不同。状态转移方程不同。在逆序解法中，第在逆序解法中，第n阶段的输入状态为阶段的输入状态为sn，决策为，决策为xn(sn)，输出状态为输出状态为sn+1，所以，状态转移方程为，所以，状态转移方程为sn+1=Tn(sn,xn(sn)。在顺序解法中，第在顺序解法中，第n阶段的输入状态为阶段的输入状态为sn+1，决策为，决策为xn(sn+1)，输出状态为，输出状态为sn，所以，状态转移方程为，所以，状态转移方程为sn=Tn(sn+1,xn(sn+1)。逆序解法和顺序解法的区别逆序解法和顺序解法的区别4.2 动态规划模型的建立和求解(5)阶段指标函数的表示不同。阶段指标函数的表示不同。在逆序解法中，阶段指标函数记为在逆序解法中，阶段指标函数记为rn(sn,xn)，它表示第，它表示第n阶段状态为阶段状态为sn、采用决策、采用决策xn时本阶段获得的指标函数值。时本阶段获得的指标函数值。在顺序解法中，阶段指标函数记为在顺序解法中，阶段指标函数记为rn(sn+1,xn)，它表示第，它表示第n阶段末系统状态为阶段末系统状态为sn+1、采用决策、采用决策xn时本阶段获得的指标时本阶段获得的指标函数值。函数值。逆序解法和顺序解法的区别逆序解法和顺序解法的区别4.2 动态规划模型的建立和求解(6)最优指标函数的定义不同。最优指标函数的定义不同。在逆序解法中，最优指标函数在逆序解法中，最优指标函数fn(sn)表示从第表示从第n阶段状态阶段状态sn出发到第出发到第N阶段末采用最优策略产生的最优指标函数值阶段末采用最优策略产生的最优指标函数值，f1(s1)是是从第从第1阶段状态阶段状态出发到全过程结束的整体最优指标出发到全过程结束的整体最优指标函数值。在顺序解法中，最优指标函数函数值。在顺序解法中，最优指标函数fn(sn+1)表示从第表示从第1阶段起到第阶段起到第n阶段末状态阶段末状态sn+1采用最优策略产生的最优指标采用最优策略产生的最优指标函数值函数值，fN(sN+1)是整体最优指标函数值。是整体最优指标函数值。逆序解法和顺序解法的区别逆序解法和顺序解法的区别4.2 动态规划模型的建立和求解4.2.2动态规划的动态规划的求解求解顺序解法的顺序解法的DPDP基本方程基本方程若过程指标函数值是阶段指标若过程指标函数值是阶段指标和和的形式，那么的形式，那么若过程指标函数值是阶段指标若过程指标函数值是阶段指标连乘连乘的形式，那么的形式，那么例例4-2 4-2 请分别用逆序解法和顺序解法求解下面的问题请分别用逆序解法和顺序解法求解下面的问题。4.2 动态规划模型的建立和求解解解 (1)采用逆序解法采用逆序解法。由目标函数可以看出，这是一个。由目标函数可以看出，这是一个3阶段阶段决策过程问题，且过程指标函数是阶段指标函数连乘的形式。决策过程问题，且过程指标函数是阶段指标函数连乘的形式。设状态变量为设状态变量为sn，n=1,2,3。由约束条件。由约束条件x1+x2+x3=c,知知s1=c。设决策变量为设决策变量为xn，由约束条件由约束条件x1+x2+x3=c和和xn0知知，0 xnsn，n=1,2,3。状态转移方程。状态转移方程sn+1=sn-xn；阶段指标函数；阶段指标函数rn(sn,xn)=xn。由于基本方程是连乘的形式，故边界条件。由于基本方程是连乘的形式，故边界条件f4(s4)=1。于是，由边界条件开始，从最后一个阶段逐步向于是，由边界条件开始，从最后一个阶段逐步向前逆推。前逆推。4.2 动态规划模型的建立和求解阶段阶段3，根据约束条件知，根据约束条件知,0 x3s3。因而，有因而，有对应的最优解为对应的最优解为x3*=s3。阶段阶段2，由状态转移方程，由状态转移方程s3=s2-x2知，知，对上式求导可知，当对上式求导可知，当x*2=s2/2时，上式取最大值即时，上式取最大值即f2(s2)=s22/4。阶段阶段1，由，由s2=s1-x1和和s1=c，有，有对上式求导可得，当对上式求导可得，当x*1=c/3时，上式取最大时，上式取最大值，值，f1(s1)=c3/27。再按计算过程反推之，可得最优解分别为再按计算过程反推之，可得最优解分别为x1*=x2*=x3*=c/3。4.2 动态规划模型的建立和求解(2)采用顺序解法采用顺序解法。用。用sn表示状态变量，表示状态变量，s4=c；用；用xn表示决表示决策变量，策变量，n=1,2,3。状态转移方程。状态转移方程sn=sn+1-xn；阶段指标函数；阶段指标函数rn(sn+1,xn)=xn。我们从第。我们从第1阶段阶段f0(s1)=1开始，逐步向后顺推开始，逐步向后顺推计算。计算。阶段阶段1，有，有对应的最优解为对应的最优解为x1*=s2。4.2 动态规划模型的建立和求解阶段阶段2，由约束条件，由约束条件s2=s3-x2知，知，对上式求导可得，当对上式求导可得，当x*2=s3/2时，时，f2(s3)取最大值，即取最大值，即f2(s3)=s23/4.阶段阶段3，由，由s3=s4-x3和和s4=c，有，有对上式求导可得，当对上式求导可得，当x*3=c/3时，时，f3(s4)取最大值，即取最大值，即f3(s4)=c3/27。再按计算过程反推之，得到最优解再按计算过程反推之，得到最优解x1*=x2*=x3*=c/3。4.2 动态规划模型的建立和求解（一）资源平行分配问题（一）资源平行分配问题 所谓所谓资源平行分配问题资源平行分配问题，就是将一定数量的一种或若干，就是将一定数量的一种或若干种资源（例如原材料、资金、设备、人力等）同时分配给若种资源（例如原材料、资金、设备、人力等）同时分配给若干个使用者（例如项目、工作等）使得目标函数达到最优。干个使用者（例如项目、工作等）使得目标函数达到最优。4.3 动态规划应用举例4.3.1资源分配问题资源分配问题例例4-3某厂销售部门有某厂销售部门有6个推销员个推销员，销售经理现要将他们分，销售经理现要将他们分配到全国三个不同地区。表配到全国三个不同地区。表4-1中给出了销售量（单位：百件）中给出了销售量（单位：百件）随销售人员的变化情况。经理决定，每个地区至少一名推销随销售人员的变化情况。经理决定，每个地区至少一名推销员。那么，他应该如何分配这员。那么，他应该如何分配这6名推销员以使得总销售量达名推销员以使得总销售量达到最大。到最大。4.3 动态规划应用举例销量销量推销员推销员地区地区1231302025250403536560504758070表4-1分析：分析：这是一个人力资源分配问题，显然，这个问题与时间这是一个人力资源分配问题，显然，这个问题与时间无明显关系。为了应用动态规划方法求解，我们需要人为的无明显关系。为了应用动态规划方法求解，我们需要人为的引入引入“时段时段”的概念。将的概念。将3个地区排序，依次考虑给地区个地区排序，依次考虑给地区1,2,3分配推销员。于是，这个问题就转化为了一个分配推销员。于是，这个问题就转化为了一个3阶段决阶段决策过程问题，每个阶段决定为该地区分配多少位推销员。阶策过程问题，每个阶段决定为该地区分配多少位推销员。阶段变量段变量n=1,2,3。4.3 动态规划应用举例状态变量状态变量一般为累计量或随递推过程变化的量。这里，一般为累计量或随递推过程变化的量。这里，把第把第n阶段可供分配的推销员人数定义为状态变量阶段可供分配的推销员人数定义为状态变量sn。由题。由题意知，意知，0sn6，初始状态，初始状态s1=6。根据问题根据问题“如何分配这如何分配这6名推销员名推销员”，把，把决策变量决策变量xn定定义为第义为第n阶段分配给地区阶段分配给地区n的推销员数的推销员数，0 xnsn且取整数。且取整数。状态转移方程状态转移方程是描述从第是描述从第n阶段到第阶段到第n+1阶段状态转移阶段状态转移规律的表达式。也就是说，如果第规律的表达式。也就是说，如果第n阶段初可供分配的推销阶段初可供分配的推销员人数为员人数为sn、分配给地区、分配给地区n的推销员为的推销员为xn，那么第，那么第n+1阶段初阶段初可供分配的推销员人数为可供分配的推销员人数为sn-xn，即该问题的状态转移方程，即该问题的状态转移方程sn+1=sn-xn。4.3 动态规划应用举例阶段指标函数阶段指标函数rn(sn,xn)表示给地区表示给地区n分配分配xn名推销员时名推销员时他所带来的产品销售量。他所带来的产品销售量。由题意知，过程指标函数是阶段由题意知，过程指标函数是阶段指标函数和的形式，即指标函数和的形式，即 。用用fn(sn)表示表示最优指标函数最优指标函数，即第，即第n阶段可分配推销员数阶段可分配推销员数为为sn时，分配给地区时，分配给地区n至地区至地区N所获得的最大产品销售量。所获得的最大产品销售量。在此基础上，可以得到该问题的动态规划的基本方程在此基础上，可以得到该问题的动态规划的基本方程：4.3 动态规划应用举例从最后一个阶段开始，采用逆序解法逐步计算出从最后一个阶段开始，采用逆序解法逐步计算出f3(s3),f2(s2),f1(s1),以及相应的最优决策以及相应的最优决策u3*(s3),u2*(s2),u1*(s1)，最后得到的，最后得到的f1(6)就是所求得的最大销售量；再按计算过就是所求得的最大销售量；再按计算过程反推算，即可得到程反推算，即可得到6名推销员的最佳分配方案。名推销员的最佳分配方案。4.3 动态规划应用举例4.3 动态规划应用举例s30123456x3*0123444f3(s3)0253550707070表4-3解解采用逆序解法从最后一个阶段开始向前逆推计算。采用逆序解法从最后一个阶段开始向前逆推计算。阶段阶段3，给地区，给地区3分配推销员。现有分配推销员。现有s3名推销员名推销员,0s36。此时，只考虑给一个地区分配推销员，由于产品销售量。此时，只考虑给一个地区分配推销员，由于产品销售量与推销员成正比的关系，因此，有多少名推销员就全部分与推销员成正比的关系，因此，有多少名推销员就全部分配给地区配给地区3是最优的。其数值计算如表是最优的。其数值计算如表4-3所示。所示。阶段阶段2，给地区，给地区2分配推销员。这时，可分配给地区分配推销员。这时，可分配给地区2和和地区地区3的推销员人数为的推销员人数为s2，0s26。若分配给地区。若分配给地区2的推销员的推销员人数为人数为x2(0s26)名，本阶段产生的销售为名，本阶段产生的销售为r2(x2)，而在下一，而在下一阶段可分配给地区阶段可分配给地区3的推销员人数为的推销员人数为s3=s2-x2，其对应的最大，其对应的最大销售量为销售量为f3(s3)。给定。给定s2，根据，根据动态规划基本方程动态规划基本方程确定最优决策以及对应的最大销售量。具体计算过程见表确定最优决策以及对应的最大销售量。具体计算过程见表4-4。4.3 动态规划应用举例4.3 动态规划应用举例s201234x2001012012301234r2(x2)+f3(s3)025 203545 40505565 60 70 7075 85 80f2(s2)025456585x2*00123s256x20123450123456r2(x2)+f3(s3)70 90 9095105807090110110115 105 80f2(s2)105115x2*44表4-4阶段阶段1，给地区，给地区1分配推销员。已知现有分配推销员。已知现有6名推销员可分名推销员可分配给地区配给地区1、地区、地区2和地区和地区3，即，即s1=6。若分配给地区。若分配给地区1x1(0s26)名推销员，本阶段产生的销售量为名推销员，本阶段产生的销售量为r1(x1)，而在下，而在下一阶段可分配给地区一阶段可分配给地区2和和3的推销员人数为的推销员人数为s2=s1-x1。利用在。利用在第第2阶段得到的结果，根据阶段得到的结果，根据确定最优决策以及对应的最大销售量。具体计算过程见表确定最优决策以及对应的最大销售量。具体计算过程见表4-5。4.3 动态规划应用举例4.3 动态规划应用举例s16x10123456r1(x1)+f2(s2)115 135 135 130 120 100 75f1(s1)135x1*1或者或者2表4-5 最后得到的最后得到的f1(s1)=135(百件百件)即是产品最大销售量；即是产品最大销售量；再按计算过程反推，可以得到再按计算过程反推，可以得到6名推销员的最优分配方名推销员的最优分配方案。该问题的最优分配方案有两个案。该问题的最优分配方案有两个,x1*=1,x2*=4,x3*=1和和x1*=1,x2*=4,x3*=1。有关有关资源平行分配问题资源平行分配问题的一般提法是：设有某种总量为的一般提法是：设有某种总量为M的资源，已知对第的资源，已知对第n项活动的资源投放量为项活动的资源投放量为xn时，从该项活时，从该项活动中可获得的收益为动中可获得的收益为rn(xn),rn(xn)为为xn的非递减函数），的非递减函数），n=1,2,N。请问如何分配资源可使总收益达到最大？。请问如何分配资源可使总收益达到最大？4.3 动态规划应用举例此类问题可写成静态规划问题此类问题可写成静态规划问题：当当rn(xn)都是线性函数时，它是一个线性规划问题；当都是线性函数时，它是一个线性规划问题；当rn(xn)都是非线性函数时，它是一个非线性规划问题，可采用都是非线性函数时，它是一个非线性规划问题，可采用前面学过的知识对该问题进行求解。但是，当前面学过的知识对该问题进行求解。但是，当N比较大时，比较大时，具体求解还是比较复杂的。具体求解还是比较复杂的。由于这类问题的特殊结构，也可以采用动态规划方法将由于这类问题的特殊结构，也可以采用动态规划方法将其包括多个变量的问题转变为多阶段、每个阶段单变量的问其包括多个变量的问题转变为多阶段、每个阶段单变量的问题来进行求解。一般来说，用动态规划方法对此类问题进行题来进行求解。一般来说，用动态规划方法对此类问题进行求解相对会容易很多，其建模过程与例求解相对会容易很多，其建模过程与例4-3相似，具体分析见相似，具体分析见下下表。在此基础上，再采用逆序解法对问题的动态规划基本表。在此基础上，再采用逆序解法对问题的动态规划基本方程进行求解。方程进行求解。4.3 动态规划应用举例4.3 动态规划应用举例大前提大前提阶段变量阶段变量把每一种活动作为一个阶段，把每一种活动作为一个阶段，N种生产活动构成种生产活动构成N个阶段。个阶段。由于每个阶段都要确定对该项活动的资源投放量，从而构由于每个阶段都要确定对该项活动的资源投放量，从而构成多阶段决策问题成多阶段决策问题条件条件I状态变量状态变量n阶段初拥有的资源量，即从第阶段初拥有的资源量，即从第n阶段到第阶段到第N阶段这阶段这N-n种活种活动中可进行分配的资源量，动中可进行分配的资源量，0snM,s1=M条件条件II决策变量决策变量对第对第n种生产活动的资源投放量，种生产活动的资源投放量，0 xnsn条件条件III状态转移状态转移sn+1=sn-xn条件条件IV阶段指标阶段指标对活动对活动n投放资源投放资源xn时产生收益时产生收益rn(sn,xn)=gn(xn)过程指标过程指标方程方程DP基本基本方程方程表4-2（二）资源动态投放问题（二）资源动态投放问题有关有关资源动态投放问题资源动态投放问题的一般提法是：假定拥有某种的一般提法是：假定拥有某种总量为总量为M的资源，计划投入的资源，计划投入A和和B两种活动。已知在两个活两种活动。已知在两个活动中投入资源量分别为动中投入资源量分别为xa和和xb时，可获得的阶段收益分别时，可获得的阶段收益分别g(xa)和和h(xb)；又知每阶段两个活动结束后，资源还可回收再；又知每阶段两个活动结束后，资源还可回收再投入使用，两个活动的资源完好率分别为投入使用，两个活动的资源完好率分别为a和和b(0a,bd0。一般地，高收益率对应低回报率，。一般地，高收益率对应低回报率，因此假设资源回收率因此假设资源回收率0abd，故，故x*N=sN，即在最后一个阶段将全部资源投，即在最后一个阶段将全部资源投入高收益率的活动入高收益率的活动A，这时有，这时有fN(sN)=csN。第第N-1阶段阶段，4.3 动态规划应用举例因此，当因此，当c-dc(b-a)时，时，x*N-1=sN-1，即在第，即在第N-1阶段将全阶段将全部资源投入高收益率的活动部资源投入高收益率的活动A，这时有，这时有x*N-1=0；否则，当；否则，当c-dc(1+a)(b-a)时时，x*N-2=sN-2，即在第，即在第N-2阶段将阶段将全部资源投入高收益率的活动全部资源投入高收益率的活动A，这时有，这时有fN-2(sN-2)=c(1+a+a2)sN-2；否则，当；否则，当c-dc(1+a)(b-a)成立时，有成立时，有c-dc(b-a)，所以当第，所以当第N-2阶段将全部资源投入高收益率的活动阶段将全部资源投入高收益率的活动A时，第时，第N-1阶段、第阶段、第N阶段的最优决策也为将全部资源投入高收益率的活动阶段的最优决策也为将全部资源投入高收益率的活动A。依此类推，可以得到该资源动态投放问题的最优分配方案，依此类推，可以得到该资源动态投放问题的最优分配方案，即当阶段即当阶段n满足以下条件时满足以下条件时，4.3 动态规划应用举例全部资源投入高收益率的活动全部资源投入高收益率的活动A，在此阶段之前，全部资源，在此阶段之前，全部资源投入低收益率的活动投入低收益率的活动B。（三）多维资源分配问题（三）多维资源分配问题 有关有关二维资源分配问题二维资源分配问题的一般提法是：现有总量分的一般提法是：现有总量分别为别为M1和和M2的两种资源，准备分配给的两种资源，准备分配给N项活动。已知当分配项活动。已知当分配给第给第n项活动的两种资源量分别为项活动的两种资源量分别为xn和和yn(n=1,2,N)时，从时，从第第n项活动中可获得的收益为项活动中可获得的收益为rn(xn,yn)。请问应如何分配这两。请问应如何分配这两种资源以使总收益达到最大。种资源以使总收益达到最大。4.3 动态规划应用举例分析：分析：当用动态规划方法处理该问题时，与前面求解一维资当用动态规划方法处理该问题时，与前面求解一维资源分配问题的方法类似。首先，将给每一项活动分配资源量源分配问题的方法类似。首先，将给每一项活动分配资源量作为一个阶段，作为一个阶段，N项活动构成项活动构成N个阶段，阶段变量个阶段，阶段变量n=1,2,N。因为投放两种资源，所以状态变量和决策变量都要取二维的。因为投放两种资源，所以状态变量和决策变量都要取二维的。设设(sn,tn)为状态变量，它表示第为状态变量，它表示第n阶段初拥有的两种资源的数阶段初拥有的两种资源的数量，即从第量，即从第n阶段到第阶段到第N阶段末对阶段末对N-n种资源可进行分配的两种资源可进行分配的两种资源的数量种资源的数量，0snM，s1=M1；0tnM2，t1=M2；(xn,yn)为为决策变量，它表示第决策变量，它表示第n阶段分配给第阶段分配给第n项活动的两种资源的项活动的两种资源的数量，数量，0 xnsn，0yntn。4.3 动态规划应用举例相应的，状态转移方程也有两个，相应的，状态转移方程也有两个，sn+1=sn-xn和和tn+1=tn-yn，它们分别表示第，它们分别表示第n阶段初，当两种资源的数量为阶段初，当两种资源的数量为sn和和tn、分、分配给第配给第n项活动的资源量为项活动的资源量为xn和和yn时，下阶段初两种资源的数时，下阶段初两种资源的数量。设量。设(xn,yn)为阶段指标函数，过程指标函数为阶段指标函为阶段指标函数，过程指标函数为阶段指标函数和的形式。用数和的形式。用fn(sn,tn)表示最优指标函数，表示最优指标函数，指指第第n阶段初可阶段初可分配的第一种资源量为分配的第一种资源量为sn、第二种资源量为、第二种资源量为tn，分配给第，分配给第n项项活动至第活动至第N项活动时所能获得的最大总收益。由此，可写出项活动时所能获得的最大总收益。由此，可写出该问题的动态规划基本方程该问题的动态规划基本方程：4.3 动态规划应用举例 从最后一个阶段开始，采用逆序解法逐步计算出从最后一个阶段开始，采用逆序解法逐步计算出fN(sN,tN),f2(s2,t2),f1(s1,t1)，最后求得的，最后求得的f1(s1,t1)为所求问为所求问题的最大总收益；再按计算过程反推算，可以得到该问题的题的最大总收益；再按计算过程反推算，可以得到该问题的最优分配方案。最优分配方案。在实际问题中，由于在实际问题中，由于r(x,y)的复杂性以及状态变量和决策的复杂性以及状态变量和决策变量维数的增加导致较难计算。因此，常采用变量维数的增加导致较难计算。因此，常采用拉格朗日乘数拉格朗日乘数法法、逐次逼近法逐次逼近法、粗格子点法粗格子点法（疏密法疏密法）对决策变量进行降）对决策变量进行降维和简化处理，以求得它的解或近似解。维和简化处理，以求得它的解或近似解。4.3 动态规划应用举例4.3.2背包问题背包问题问题的名称来源于有一个徒步旅行者需要携带多种物品，问题的名称来源于有一个徒步旅行者需要携带多种物品，各种物品的重量不同，产生的价值也不相同，他必须决定要各种物品的重量不同，产生的价值也不相同，他必须决定要在背包里携带哪些物品以使得产生的总价值最大。在背包里携带哪些物品以使得产生的总价值最大。有关有关背包问题背包问题的一般提法是：假设背包可携带物品的总的一般提法是：假设背包可携带物品的总重量为重量为W公斤。现有公斤。现有N种物品可供他选择，已知第种物品可供他选择，已知第n种物品每种物品每件重量为件重量为xn公斤，其价值是携带数量公斤，其价值是携带数量rn(xn)的函数的函数，n=1,2,N。试问旅行者应如何选择携带物品种类和数量以。试问旅行者应如何选择携带物品种类和数量以使物品所起的总价值最大。使物品所起的总价值最大。4.3 动态规划应用举例 下面，利用动态规划方法对此问题进行求解。首先，可下面，利用动态规划方法对此问题进行求解。首先，可按物品的选择过程来划分阶段，每装入一种物品看作一个阶按物品的选择过程来划分阶段，每装入一种物品看作一个阶段，共有段，共有N种物品，故该问题可描述为一个种物品，故该问题可描述为一个N阶段决策过程阶段决策过程问题，问题，n=1,2,N。设设sn为状态变量，它表示第为状态变量，它表示第n阶段开始时，背包中允许装阶段开始时，背包中允许装入的第入的第n种物品至第种物品至第N种物品的总重量，种物品的总重量，0snw，s1=w。设设xn为决策变量，它表示第为决策变量，它表示第n种物品的携带数种物品的携带数量量，xn取整数。取整