下载文档原格式
运筹学教案动态规划一、引言1.1 课程背景本课程旨在帮助学生掌握运筹学中的动态规划方法，培养学生解决实际问题的能力。
1.2 课程目标通过本课程的学习，学生将能够：（1）理解动态规划的基本概念和原理；（2）掌握动态规划解决问题的方法和步骤；（3）能够应用动态规划解决实际问题。
二、动态规划基本概念2.1 定义动态规划（Dynamic Programming，DP）是一种求解最优化问题的方法，它将复杂问题分解为简单子问题，并通过求解子问题的最优解来得到原问题的最优解。
2.2 特点（1）最优子结构：问题的最优解包含其子问题的最优解；（2）重叠子问题：问题中含有重复子问题；（3）无后效性：一旦某个给定子问题的解确定了，就不会再改变；（4）子问题划分：问题可以分解为若干个子问题，且子问题之间是相互独立的。
三、动态规划解决问题步骤3.1 定义状态状态是指某一阶段问题的一个描述，可以用一组变量来表示。
3.2 建立状态转移方程状态转移方程是描述从一个状态到另一个状态的转换关系。
3.3 确定边界条件边界条件是指初始状态和最终状态的取值。
3.4 求解最优解根据状态转移方程和边界条件，求解最优解。
四、动态规划应用实例4.1 0-1背包问题问题描述：给定n个物品，每个物品有一个重量和一个价值，背包的最大容量为W，如何选择装入背包的物品，使得背包内物品的总价值最大。
4.2 最长公共子序列问题描述：给定两个序列，求它们的最长公共子序列。
4.3 最短路径问题问题描述：给定一个加权无向图，求从源点到其他各顶点的最短路径。
5.1 动态规划的基本概念和原理5.2 动态规划解决问题的步骤5.3 动态规划在实际问题中的应用教学方法：本课程采用讲授、案例分析、上机实践相结合的教学方法，帮助学生深入理解和掌握动态规划方法。
教学评估：课程结束后，通过课堂讨论、上机考试等方式对学生的学习情况进行评估。
六、动态规划算法设计6.1 动态规划算法框架介绍动态规划算法的基本框架，包括状态定义、状态转移方程、边界条件、计算顺序等。
6.1试用动态规划方法，求解图6-2 从Q 到T 的最短路。
解：由上图可知，从Q 到T 的最短路是8用逆序解法，由题意，递推方程为()(){}()1,2,3,4,min )(11=+=++k x f u x w x f k k k k k k k终端条件为()05=T f当k=4时，()30314=+=C f()10124=+=C f()50534=+=C f当 k=3时， ()()()()()()113342414135352min C B u C f C f C f B f ==⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=()()()()()()123342414234241min C B u C f C f C f B f ==⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=当k=2时，()()()()()212231312734min B A u B f B f A f ==⎭⎬⎫⎩⎨⎧++=()()()()()122231322731min B A u B f B f A f ==⎭⎬⎫⎩⎨⎧++=()()()()()132231332853min B A u B f B f A f ==⎭⎬⎫⎩⎨⎧++=当k=1 时，()()()()()()2132221218123min A Q u A f A f A f Q f ==⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=最优解策略为()2*1A Q u = ()12*2B A u = ()11*3C B u = ()T C u =1*4最短路长为86.2用动态规划方法求解 （1）3221max x x x F ⋅⋅=⎩⎨⎧=≥=++3,2,1,04..321i x x x x t s i解：3211x x x S ++=322x x S += 33x S = 121x S S +=232x S S += 33x S =()(){}3max 22022222f x s f sx ⋅=≤≤=(){}2220222max x s x sx -⋅≤≤由导数法求得，当3222s S =时，()22x f 有最大值27432s ()(){}22140111max x f x s f x ⋅=≤≤=()⎭⎬⎫⎩⎨⎧⋅=≤≤274max 32140111s x s f x =()()⎭⎬⎫⎩⎨⎧-⋅=≤≤2744max 31140111x x s f x解得：11=x 时，()4max 11=x f∴ ()⎪⎩⎪⎨⎧+==++322323241x x x x x∴⎩⎨⎧==1232x x ∴1,2,1321===x x x （2）321232223222124222min x x x x x x x x F ---+-++=⎩⎨⎧=≥=++3,2,1,03..321i x x x x t s i解： 31=S 112x S S -= 223x S S -=()(){}41min 23333--==x s f x s =(){}4123--s()()(){}4112min 2322222--+-=≤s x s f x x=()(){}411222222---+-x s x=1422224222222222222+-+-+-++-x s x x s s x x()()⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧⎪⎭⎫ ⎝⎛-+⎪⎭⎫ ⎝⎛-+-=≤222221413423221min 1s s x s f x =()⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧-⎪⎭⎫ ⎝⎛--+⎪⎭⎫ ⎝⎛--+-≤1342632321min 21212141x x x x=()()112194219212221211121--+-++-++-x x x x x x =96930915121+-x x =30301-x =011=x6.3 有四台设备分给甲，乙，丙，丁四厂，各厂盈利如表6-6所示。
运筹学动态规划运筹学是一门综合运筹学、优化学、决策学和统计学等多学科知识的学科，它的核心内容是对决策问题进行建模和分析，并通过数学方法进行求解和优化。
动态规划是运筹学中的一种重要方法，它通过将问题划分为相互重叠的子问题，并通过解决子问题的最优解来求解原问题的最优解。
下面将详细介绍运筹学中的动态规划方法。
动态规划方法的核心思想是将原问题分解为若干个相互重叠的子问题，并通过求解子问题的最优解来求解原问题的最优解。
为了可以使用动态规划方法，必须满足以下两个条件：子问题的最优解可以作为原问题的最优解的一部分；子问题之间必须具有重叠性，即一个子问题可以被多次使用。
动态规划方法的具体步骤如下：首先，将原问题分解为若干个子问题，并定义出每个子问题的状态和状态转移方程；其次，通过迭代求解每个子问题的最优解，直到求解出原问题的最优解；最后，根据子问题的最优解和状态转移方程，得到原问题的最优解。
动态规划方法的应用非常广泛，可以用于求解各种各样的优化问题。
例如，在物流配送中，可以使用动态规划方法求解最短路径问题；在生产计划中，可以使用动态规划方法求解最优生产计划；在股票投资中，可以使用动态规划方法求解最优投资策略等。
动态规划方法的优点是可以通过求解子问题的最优解来求解原问题的最优解，避免了穷举法的复杂性。
此外，动态规划方法还可以通过引入一定的约束条件，来对问题进行更精确的建模和求解。
然而，动态规划方法也存在一些局限性。
首先，动态规划方法要求问题能够满足子问题的最优解可以作为原问题的最优解的一部分，这限制了动态规划方法的应用范围。
其次，动态规划方法通常需要建立较为复杂的状态转移方程，并进行复杂的计算，使得算法的实现和求解过程比较困难。
综上所述，动态规划是运筹学中的一种重要方法，通过将问题划分为相互重叠的子问题，并通过解决子问题的最优解来求解原问题的最优解。
动态规划方法的优点是可以高效地求解优化问题，但同时也存在一些局限性。
第六章 动态规划主要内容：1、动态规划的基本概念2、动态规划的最优性原理和基本方程3、动态规划的模型及其应用重点与难点：动态规划的状态转移方程、基本方程；动态规划的建模思路与方法；运用递推原理确定最优解的方法与技巧。
要 求：理解动态规划的基本概念，掌握动态规划的建模步骤和求解方法，能够创造性地建立数学模型，并能运用动态规划方法解决实际问题。
§1 动态规划的基本概念例1 最短线路问题。
给定一个运输网络（如图），两点之间的数字表示两点间的距离，试求一条从A 0到A 4的运输线路，使总距离为最短?1、阶段对于一给定的多阶段过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。
描述阶段的变量称为阶段变量，常用K 表示。
1）阶段数固定的问题称为定期多阶段决策问题；如例1，可分为四个阶段。
2）阶段数不固定的问题称为不定期多阶段决策问题。
如2、状态状态表示某阶段的出发位置。
它既是某阶段过程演变的起点，又是前一阶段决策的结果。
例1中，第一阶段有一种状态即A 0点，第二阶段有三个状态，即点集合{A 1，B 1，C 1}，一般第K 阶段的状态就是第K 阶段所有始点的集合。
描述过程状态的变量称为状态变量。
第K 阶段的状态变量，记为k x 。
3、决策决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决A 0A 1B 1C 1A 2B 2C 2B 3A 3A 420 40 3070 5030 2040 40 1050 10 4060 3030 3030 40B ACDE4 724 2621 1定称为决策。
描述决策的变量称为决策变量，常用)(k k x u 表示处于状态k x 时的决策变量，它是状态变量的函数。
如： 21A B → ， 记为()212A B U =决策变量可取值的全体，称为允许决策集合。
常用()k k x D 表示状态k x 的允许决策集合。
如：(){}22212,,C B A B D = ，(){}2212,C A A D =4、策略全过程的各个阶段上所选择的决策组成的全体称之为全过程策略，记为n P ,1。
若43210A A A A A →→→→为一决策，则全过程策略()()(){}442211,1,,,x u x u x u P n =由过程的第K 阶段开始到终止状态为止的过程，称为问题的后子过程（或K 子过程）。
其决策函数序列{})(,),(),(11n n k k k k x u x u x u ++称为k 子过程策略，简称子策略，记为)(,k n k x p 。
即{})(,),(),()(11,n n k k k k k n k x u x u x u x p ++=在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，用P 表示。
从允许策略集合中找出达到最优效果的策略称为最优策略。
5、状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。
它描述了由K 阶段到K+1阶段的状态转移规律，称之为状态转移方程，记为()k k k k u x T x ,1=+。
6、指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数。
它是定义在全过程和所有后部子过程上确定的数量函数，常用n k V ,表示。
即()n k x u x u x V V n k k k k n k n k ,,2,1,,,,,111,, ==+++动态规划的指标函数，应具有可分离性，并满足递推关系。
即()n k k k nk V u x V,!,,,+=φ过程和它的任一子过程的指标是它所包含的各阶段的指标和，即()∑==nkj j jjn k u xV V ,, 指标函数具有可加性其中()j j j u x V ,表示第j 阶段的阶段指标∴ 上式可写成：()()1111,,,,,+++++=n k k k k k k n k x u x V u x V V由于给定了过程的初始状态及策略，则指标函数也随之确定，所以指标函数是初始状态和策略的函数，记为()[]kn k k n k x P x V ,,,，()k n k x P , ——子策略∴上式也可写成[]()[]n k k n k k k k n k k n k P x V u x V p x V ,11,1,,,,,++++=指标函数的最优值，称为最优值函数，记为()k k x f ，即()()1,,,,+=n k k nk k k x u x optVx f()()(){}1,,1,,,11 -=+=++∈n n k x f u x V optk k k k k x D u kk k§2 基本定理和基本方程一、最优性原理——作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。
简而言之，一个最优策略的子策略总是最优的。
这是动态规划的理论基础。
在例1中，如果43210A B A B A →→→→是40A A 到的最短路线，则4321A B A B →→→一定是由B 1到A 4的最短路线。
二、基本方程()()()(){}()()⎪⎩⎪⎨⎧==-=+=+++++∈k k k k n n k k k k k x D u k k u x T x x f n n k x f u x V opt x f k k k ,01,,1,,,11111其中边界条件—§3 动态规划的模型及求解因为动态规划没有一个标准的数学表达式，所以建立动态规划的模型比它的计算更为困难。
一、建立模型的步骤 （1）选择阶段变量K按时间或空间的先后顺序将问题划分为满足某种递推关系的若干阶段。
（2）选择状态变量k x状态变量应满足可知性和无后效性。
可知性是指过程的各阶段状态变量的取值，都能直接或间接的确定；无后效性是指如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。
通常选择随递推关系累计的量或按某种规律变化的量作为状态变量。
（3）选择决策变量k u （4）写出状态转移方程式 （5）列出动态规划的基本方程二、逆序解法与顺序解法动态规划的求解有两种基本方法：逆序解法（后向动态规划方法）、顺序解法（前向动态规划方法）。
使用上述两种方法求解时，除了求解的行进方向不同外，在建模时要注意以下区别：1、状态转移方式不同逆序解法中第k 段的输入状态为k x ,决策为k u ，输出状态为1+k x ，即第k+1阶段的状态，所以状态转移方程为：)(,1k k k k u x T x =+，阶段指标为),(k k k u x v 。
顺序解法中第k 段的输入状态为1+k x ,决策为k u ，输出状态为k x ，所以状态转移方程为：)(,1k k k k u x T x +=，阶段指标为),(1k k k u x v + 。
2、指标函数的定义不同逆序解法中，最优指标函数)(k k x f 表示第k 段从状态k x 出发，到终点后部子过程最优效益值。
)(11x f 是整体最优函数值。
顺序解法中，最优指标函数)(1+k k x f 表示第k 段时从起点到状态1+k x 的前部子过程最优效益值。
)(1+n n x f 是整体最优函数值。
3、基本方程形式不同（1）当指标函数为阶段指标和形式，逆序解法中，∑==nkj j j jn k u x vV ),(,，则基本方程为：()()(){}()⎪⎩⎪⎨⎧=-=+=++++∈01,,1,,,1111n n k k k k k D u k k x f n n k x f u x V opt x f kk 顺序解法中， ∑=+=kj j j jk u x vV 11,1),( ，基本方程为：()()(){}()⎪⎩⎪⎨⎧==+=-+∈+0,,2,1,,10111x f n k x f u x V opt x f k k k k k D u k k kk （2）当指标函数为阶段指标积形式，逆序解法中， nkj j j jn k u x vV ==),(,，则基本方程为：()()(){}()⎪⎩⎪⎨⎧=-=∙=++++∈11,,1,,,1111n n k k k k k D u k k x f n n k x f u x V opt x f kk 顺序解法中， nkj j j jk u x vV =+=),(1,1 ，基本方程为：()()(){}()⎪⎩⎪⎨⎧==∙=-+∈+1,,2,1,,10111x f n k x f u x V opt x f k k k k k D u k k kk 例1 解：当k=4时，334,B A x =(){}(){}434434A B D A A D ==()055=x f()()(){}4434,min344u x V A f A D U ∈=∴(){}4343:30,min A A A A V →==优决策最()()(){}4434,min344u x V B f B D U ∈=(){}4343:40,min A B A B V →==最优决策 当k=3时,2223,,C B A x =()()(){}33232323,B A C D B D A D ===()()()(){}443223,min233x f U A V A f A D U +=∈()()()(){}34323432,,,min B f B A V A f A A V ++={}32:404040,3010min A A →=++=最优决策()()()(){}443223,min233x f U B V B f B D U +=∈()()()(){}34323432,,,min B f B B V A f A B V ++={}32:7040303060min B B →=++=最优决策，()()()(){}443223233minx f U C V C f C D U ++=∈()()()(){}44323432,,,min B f B C V A f A C V ++= ()32:604030,3030min A C →=++=最优决策当k=2时,1112,,C B A x =(){}2212,C A A D =()()()(){}()⎪⎩⎪⎨⎧==+=++∈1,2,3,40,min5511k x f x f u x V x f k k k k x D u k k kk k()(){}2221212,,C B A C D B D ==()()()(){}332112,min122x f u A V A f A D u +=∈()()()(){}23212321,,,min C f C A V A f A A V ++= {}2121:1106050,4070min C A A A →→=++=最优决策()()()(){}332112,min122x f u B V B f B D u +=∈()()()()()(){}23212312321,,2,,,min C f C B V B f B B V A f A B V +++= {}21706040,7020,4030min A B →=+++=最优决策： ()()()(){}332212,min122x f U C V C f C D U +=∈()()()()()(){}232123212321,,,,,min C f C C V B f B C V A f A C V +++= {}2121:806050,7010,4040min B C A C →→=+++=最优决策当k=1时，(){}1110101,,C B A A D A x ==()()()(){}221001,min11x f u A V A f A D u +=∈()()()()()(){}121012101210,,,,,min C f C A V B f B A V A f A A V +++={}1010:1108030,7040,11020min C A B A →→=+++=最优决策∴40A A →的最短距离为110，最短路为：43210A A A B A →→→→43210A A A C A →→→→ 43210A B B C A →→→→例2 多阶段资源分配问题有1000台机器生产A 、B 两种产品，用Y 台机器生产A 产品，可获得收入5Y ，用Y 台机器生产B 产品，可获得收入4Y ，一年后，生产A 产品的机器完好率为0.8，生产B 产品的机器完好率为0.9，问五年内如何安排生产A 、B 两种产品，使得总收入最大？ 解：设k 表示年度k x 为第k 年初完好机器数（亦即第k-1年未完好机器数）k u 为第k 年安排生产A 产品的机器数（生产B 产品的机器数为k k u x -）则允许决策集合(){}k k k k k x u u x D ≤≤=0 状态转移方程为()k k k k k k u x u x u x 1.09.09.08.01-=-+=+∴基本方程为()()()(){}()()(){}()⎪⎪⎩⎪⎪⎨⎧==+-+=+=++∈++∈1,2,3,4,5045max ,max 661111k x f x f u x u x f u x V x f k k k k k x D u k k k k x D u k k k k k k k k其中k k k u x x 1.09.01-=+ 当k=5时,()()(){}6655505545max 55x f u x u x f x u +-+=≤≤{}555054m a x 55x u x x u =+=≤≤最优决策5*5x u =，即第五年所有设备都用于生产A 产品。
