[数学]动态规划应用

1、天津工业大学毕业设计（论文）题目：动态规划在学生选课中的应用姓 名 学 院 专 业 指导教师 职 称 2011年 5月 28日摘 要本文主要介绍了动态规划（dynamic programming）的基本内容，详细介绍了动态规划过程中的阶段、状态变量、决策变量的定义及其选取与详细应用。本文建立了大学生选修课选课的动态规划模型，并且研究了动态规划在求解选课过程最优解的过程中的应用。本论文在阐述了多阶段动态规划模型的详细求解过程的基础上，主要解决了运用最优化方法中多阶段动态规划模型求解多阶段选课的问题。第二章是动态规划内容的详细介绍，第三章是多阶段选修课选课动态规划模型的建立与最优选课安排的得出过程

2、。本论文对于过程最优解与全局最优解的关系做出了直观的描述。这有助于系统化人性化的选课系统的建立。关键词：动态规划；最优解；阶段；决策变量；状态变量。 abstractthis article mainly introduced the dynamic programming and introduced the process of dynamic planning stage or state variables, the definition and selection decision variables with detailed applications. this paper es

3、tablished the course of college students' elective dynamic programming model., and studied the dynamic programming in solving the optimal solution of course selection process in the process of application.this paper expounded the dynamic programming model in multi-stage detailed solving process,

4、 mainly solved the basis for the use of the optimization methods of dynamic programming model to solve multiple stage of course. the second chapter is dynamic programming content detailed introduction, and the third chapter is multi-stage elective courses of dynamic programming model is established

5、and arrange the optimal selection is obtained.this paper describes process optimal solution and the global optimal solution relationship intuitively. it helps to establish systematic humanistic elective course system.keywords: dynamic planning; the optimal solution; stage; the decision variables; st

6、age variables.目 录 第一章 前言1第二章 动态规划的基本概念和基本原理22.1 动态规划的基本概念22.1.1 阶段22.1.2 状态22.1.3 决策和策略32.1.4 状态转移方程32.1.5 指标函数42.2 动态规划的基本思想与基本原理42.2.1 动态规划方法的基本思想42.2.2动态规划算法的基本步骤52.2.3 动态规划的基本方程与基本原理62.2.4动态规划的适用条件6第三章 动态规划模型的建立与求解83.1 动态规划模型的建立83.2 状态变量、决策变量的选择93.3 求解动态规划的最优解93.4 得出最优解14第四章 问题与展望15参考文献17附录118附录

7、227谢辞30 天津工业大学2007届本科生毕业设计（论文）第一章 前言动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著dynamic programming，这是

8、该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其他方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态规划过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划）只要认为的引入时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划模型的分类：离散确定型；离散随机型；连续确定型；连续随机型。本文仅运用离散确定型动态规划模型，初步解决动态规划在学生选修课选课过程中的应用，并运用数学软件进行模拟分析。第二章 动态规划的基本

9、概念和基本原理2.1 动态规划的基本概念是用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，此时我们要用到以下概念：1.阶段；2状态；3决策和策略；4状态转移；5指标函数；2.1.1 阶段将所给问题的过程，按照时间或空间特征分解成若干相互联系的阶段，以便按照次序去求每个阶段的解，常用字母k表示阶段变量。图2.1图2.1中，从a到f可以分成从a到b（b有两种选择b1，b2），从b到c（c有四种选择c1，c2，c3，c4），从c到d（d有三种选择d1，d2，d3），从d到e（e有两种选择e1，e2），再从e到f五个阶段。k=1，2，3，4，5。2.1.2 状态各阶段开始时的客观条

10、件叫做状态。描述各阶段状态的变量成为状态变量，常用表示第k阶段的状态变量，状态变量sk的取值集合成为状态集合，用sk表示。动态规划中的状态应居于如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。在例1中第一阶段状态为a，第二阶段则有两个状态：b1，b2。状态变量st的集合s1=a，后面各段的状态集合分别是：s2=b1，b2s3=c1，c2 ,c3 ,c4s4=d1，d2 ,d3s5=

11、e1，e2 当某段的初始状态已选定某个点时，从这个点以后的路径选择只与该点有关，不受以前的路径的影响，所以满足状态的无后效性。2.1.3 决策和策略当各段的状态去顶以后，就可以做出不同的决策（或选择），从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，产用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，常用dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有uk(sk)dk(sk)。在例1中，从第二阶段的状态b1出发，可选择下一段的c1，c2，c3，即其允许决策集合为：d2(b1)=c

12、1，c2，c3如我们选择c3，则可表为：u2(b1)=c3各段决策确定后，整个问题的决策序列就构成一个策略，用p1，n u1(s1)，u2(s2)，un(sn)表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作p1，n，使整个问题达到最优效果的策略就是最优策略。2.1.4 状态转移方程 动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。如果给定了第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用下式表示：sk+1=tk(sk,uk)由于它表示了由k段到k+1段的状态转移规律，所以称为状态转移方程。例1中，状态转移方

13、程为：sk+1= uk(sk)2.1.5 指标函数用于衡量所选定策略优劣的淑玲指标称为指标函数。它分为阶段指标函数和过程指标函数两种。阶段指标函数是指第k段，从状态sk出发；采取决策uk时的效益，用d（sk,uk）表示。而一个n段决策过程，从1到n叫做问题的原过程，对于任意一个给定的k（1kn），从第k段到第n段的过程称为原过程的一个后部子过程。v1,n(s1,p1,n)表示初始状态为s1采用策略p1，n时原过程的指标函数值，而vk,n(sk,pk,n)表示在第k段，状态为sk采用策略pk，n时，后部子过程的指标函数值。最优指标函数记为fk(sk)，它表示从第k段状态sk，采用最优策略p*k，

14、n到过程中止是的最佳效益值。fk(sk)与vk,n(sk,pk,n)间的关系为：fksk=vk,nsk,pk,n*=optpk,npk,nvk,n(sk,pk,n)上式中opt表示最优化，根据具体问题分别表示为max或min。在例1中，指标函数是距离。如第二阶段，状态为b1是d(b1,c2)表示由b1出发。采用决策到下一段c2点的两点间距离，v2,5(b1)表示从b1到f的距离，而f2(b1)则表示从b1到f的最短距离。本问题的总目标是求f1(a)，即从a到终点f的最短距离。2.2 动态规划的基本思想与基本原理2.2.1 动态规划方法的基本思想一般来说，只要问题可以划分成规模更小的子问题，并且

15、原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决【1】。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子问题)，因此一旦递归地求出各子问题的解后，

16、便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方

17、法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。2.2.2 动态规划算法的基本步骤设计一个标准的动态规划算法，通常可按以下几个步骤进行：1) 将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量以及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。2) 求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。在每一个子问题求解时，都

18、要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。3) 动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优策略选取是从全局考虑的，与该段的最优选择一般是不同的。【4】动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。2.2.3 动态规划的基本方程与基本原理动态规划的基本方程为：fksk=optukdk(sk)vksk,uk+fk+1sk+1 k=n,n-1,1fn+1sn+1=0 动态规划方法基于贝尔曼等人提出的最优化原理，它可表述为：一个过程的最优策略具有这样的性质：即无论初始状

19、态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略【3】。2.2.4 动态规划的适用条件任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划

20、方法计算。动态规划的最优化理在其指标函数的可分离性和单调性中得到体现。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。2.无后向性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。有些问题乍一看好像有后向性，但如果按照某种合理的方式重新划分阶段，就可以发现其本质上是无后向性的，所以关键是阶段的合理划分，这一点将在动态规划的技巧中详细阐述。3.子问题的重叠性动态规划可以将原来具有指数级复杂度的搜索算法改进成具有多项式时间

21、的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。以bitonic旅行路线问题为例，这个问题也可以用搜索算法来解决。动态规划的时间复杂度为o(n2)，搜索算法的时间复杂度为o(n!) ，但从空间复杂度来看，动态规划算法为o(n2)，而搜索算法为o(n)，搜索算法反而优于动态规划算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，

22、而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。第三章 动态规划模型的建立与求解3.1 动态规划模型的建立建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程。成功地应用动态规划方法的关键，在于识别问题的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状态变量具有递推的状态转移关系sk+1=t

23、k(sk,uk)。本论文主要选取了某学生在大学四年期间所感兴趣的选修课，要求其每学期只能选择一门选修课，并且使其对所有选修课的满意程度达到最大。图3.1表3.1 平均喜好程度非常喜欢1喜欢0.7一般0.5不喜欢0.3完全不喜欢0.1且要求每一学年所修学分数达到8个学分图3.2图3.2为图3.1的关系图，其中ai,bi,ci,di,ei,fi,gi,hi（i=1,2,3,4）分别代表对应学期所选择的对应的选修课程，在课程名下方的红色数字代表所选修课程的对应学分数；在课程之后的数字为对下一门课程的平局喜好程度（见表3.1），数字顺序对应下一学期可选修课程的顺序，*代表在选择本门课程时，不可选修*位

24、置所指示的课程。本文主要运用动态规划算法解决该选课问题的最优解，即最大喜好程度。3.2 状态变量、决策变量的选择阶段k：在这里，k取1,2,3,4,5,6,7,8状态变量sk：第k阶段可以选择的选修课决策变量xk：第k阶段可选的选修课的满意度3.3 求解动态规划的最优解这是一个八阶段的动态规划模型，在求解这个模型的最优解时，采用逆序递推方法求解，逐步求出各段各点到终点h的最短路线，最后求得o点到h点的最短路线。1. 第一步，从k=8开始，状态变量s8可取两种状态g1，g2，它们到h点的平均喜好程度分别为0.3,0.7，即：f8g1=0.3 f8g2=0.7由于g(g2)+g(h)=7<8

25、，则只保留f8g1=0.3。2. 第二步，k=7，状态变量s7可取三种状态f1，f2，f3，它们到h点的平均喜好程度分别为：f7f1=0.1+0.3=0.4f7f2=0.5+0.3=0.8f7f3=0.5+0.3=0.83. 第三步，k=6，状态变量s6可取四个值e1，e2，e3，e4 。从e1到h有两条路线，需加以比较，取其中平均喜好程度最大的，即：f6e1=maxde1,f1+f6f1de1,f2+f6f2=max0.1+0.40.7+0.8=1.5这说明由e1到h的最大满意度为1.5，其路径为e1f2g1h，相应决策为u6*e1=f2。从e2到h有两条路线，需加以比较，取其中平均喜好程度

26、最大的，即：f6e2=maxde2,f1+f6f1de2,f2+f6f2=max0.3+0.40.7+0.8=1.5由于g(e2)+g(f2)=7<8，不符合第三学年的学分要求，则舍去此解。从而有f6(e2)=0.7。这说明由e2到h的最大满意度为0.7，其路径为e2f1g1h，相应决策为u6*e2=f1。从e3到h有三条路线，需加以比较，取其中平均喜好程度最大的，即：f6e3=maxd(e3,f1)+f6(f1)d(e3,f2)+f6(f2)d(e3,f3)+f6(f3)=max0.3+0.41+0.80.7+0.8=1.8由于g(e3)+g(f2)=7<8，不符合第三学年的学分

27、要求，则舍去此解。从而有f6(e3)=1.5。这说明由e3到h的最大满意度为1.5，其路径为e3f3g1h，相应决策为u6*e3=f3。从e4到h有两条路线，需加以比较，取其中平均喜好程度最大的，即：f6e4=maxde4,f1+f6f1de4,f2+f6f2=max0.3+0.30.5+0.5=1由于g(e4)+g(f1)=7<8，不符合第三学年的学分要求，则舍去此解。由于g(e4)+g(f2)=6<8，不符合第三学年的学分要求，则舍去此解。从而舍去此决策。4. 第四步，k=5，状态变量s5可取五个值d1，d2，d3，d4 ,d5。从d1到h有四条路线，需加以比较，取其中平均喜好

28、程度最大的，即：f5d1=maxdd1,e1+f5e1dd1,e2+f5e2dd1,e3+f5e3dd1,e4+f5e4=max0.3+1.50.5+1.50.7+1.80.5+1=2.5这说明由d1到h的最大满意度为2.5，其路径为d1e3f3g1h，相应决策为u5*d1=e3。从d2到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f5d2=maxdd2,e1+f5e1dd2,e2+f5e2dd2,e3+f5e3dd2,e4+f5e4=max0.3+1.50.5+1.50.7+1.80.3+1=2.5这说明由d2到h的最大满意度为2.5，其路径为d2e3f3g1h，相应决策为u5*

29、d2=e3。从d3到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f5d3=maxdd3,e1+f5e1dd3,e2+f5e2dd3,e3+f5e3dd3,e4+f5e4=max0.5+1.50.3+1.50.7+1.80.5+1=2.5这说明由d3到h的最大满意度为2.5，其路径为d3e3f3g1h，相应决策为u5*d3=e3。从d4到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f5d4=maxdd4,e1+f5e1dd4,e2+f5e2dd4,e3+f5e3dd4,e4+f5e4=max0.5+1.50.5+1.51+1.80.5+1=2.8这说明由d4到h的最大满意

30、度为2.8，其路径为d4e3f3g1h，相应决策为u5*d4=e3。从d5到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f5d5=maxdd5,e1+f5e1dd5,e2+f5e2dd5,e3+f5e3dd5,e4+f5e4=max0.5+1.50.7+1.51+1.80.7+1=2.8这说明由d5到h的最大满意度为2.8，其路径为d5e3f3g1h，相应决策为u5*d5=e3。5. 第五步，k=4，状态变量s4可取四个值c1，c2，c3，c4 。从c1到h有五条路线，需加以比较，取其中平均喜好程度最大的，即：f4c1=maxdc1,d1+f4d1dc1,d2+f4d2dc1,d3

31、+f4d3dc1,d4+f4d4dc1,d5+f4d5=max0.3+2.50.1+2.50.5+2.50.7+2.81+2.8=3.8由于g(c1)+g(d5)=7<8，不符合第二学年的学分要求，则舍去此解。从而有f4(c1)=3.5。这说明由c1到h的最大满意度为3.5，其路径为c1d4e3f3g1h，相应决策为u4*c1=d4。从c2到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f4c2=maxdc2,d2+f4d2dc2,d3+f4d3dc2,d4+f4d4dc2,d5+f4d5=max0.5+2.50.5+2.50.3+2.80.7+2.8=3.5由于g(c2)+g

32、(d5)=7<8，不符合第二学年的学分要求，则舍去此解。这说明由c2到h的最大满意度为3.0，其路径为c2d4e3f3g1h，相应决策为u4*c2=d4。从c3到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f4c3=maxdc3,d2+f4d2dc3,d3+f4d3dc3,d4+f4d4dc3,d5+f4d5=max0.1+2.50.5+2.50.5+2.80.7+2.8=3.5这说明由c3到h的最大满意度为3.5，其路径为c3d5e3f3g1h，相应决策为u4*c3=d5。从c4到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f4c4=maxdc4,d2+f4d2

33、dc4,d3+f4d3dc4,d4+f4d4dc4,d5+f4d5=max0.7+2.51+2.50.7+2.80.5+2.8=3.5由于g(c4)+g(d2)=6<8，不符合第二学年的学分要求，则舍去此解。由于g(c4)+g(d4)=7<8，不符合第二学年的学分要求，则舍去此解。由于g(c4)+g(d5)=6<8，不符合第二学年的学分要求，则舍去此解。这说明由c4到h的最大满意度为3.5，其路径为c4d3e3f3g1h，相应决策为u4*c4=d3。6. 第六步，k=3，状态变量s3可取三个值b1，b2，b3 。从b1到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：

34、f3b1=maxdb1,c1+f3c1db1,c2+f3c2db1,c3+f3c3db1,c4+f3c4=max0.3+3.80.3+3.50.3+3.50.7+3.5=4.2这说明由b1到h的最大满意度为4.2，其路径为b1c4d3e3f3g1h，相应决策为u3*b1=c4。从b2到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f3b2=maxdb2,c1+f3c1db2,c2+f3c2db2,c3+f3c3db2,c4+f3c4=max0.7+3.80.3+3.50.3+3.51+3.5=4.5这说明由b2到h的最大满意度为4.5，其路径为b2c4d3e3f3g1h，相应决策为u

35、3*b2=c4。从b3到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f3b3=maxdb3,c1+f3c1db3,c2+f3c2db3,c3+f3c3db3,c4+f3c4=max0.7+3.80.5+3.50.5+3.51+3.5=4.5这说明由b3到h的最大满意度为4.5，其路径为b3c4d3e3f3g1h，相应决策为u3*b3=c4。7. 第七步，k=2，状态变量s2可取三个值a1，a2，a3 。从a1到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f2a1=maxda1,b1+f2b1da1,b2+f2b2da1,b3+f2b3=max0.3+4.20.5+4.2

36、1+4.5=5.5由于g(a1)+g(b3)=7<8，不符合第二学年的学分要求，则舍去此解。这说明由a1到h的最大满意度为4.7，其路径为a1b2c4d3e3f3g1h，相应决策为u2*a1=b2。从a2到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f2a2=maxda2,b1+f2b1da2,b2+f2b2da2,b3+f2b3=max0.5+4.20.5+4.20.7+4.5=5.2由于g(a2)+g(b3)=6<8，不符合第二学年的学分要求，则舍去此解。由于g(a2)+g(b2)=7<8，不符合第二学年的学分要求，则舍去此解。这说明由a2到h的最大满意度为5

37、.2，其路径为a2b1c4d3e3f3g1h，相应决策为u2*a2=b1。从a3到h有四条路线，需加以比较，取其中平均喜好程度最大的，即：f2a3=maxda3,b1+f2b1da3,b2+f2b2da3,b3+f2b3=max1+4.20.7+4.20.5+4.5=5.2由于g(a3)+g(b3)=6<8，不符合第二学年的学分要求，则舍去此解。由于g(a3)+g(b2)=7<8，不符合第二学年的学分要求，则舍去此解。这说明由a3到h的最大满意度为5.2，其路径为a3b1c4d3e3f3g1h，相应决策为u2*a3=b1。8. 第八步，k=1，只有一个状态点o，则 f1o=maxd

38、o,a1+f2a1do,a2+f2a2do,a3+f2a3=max0.5+5.50.5+5.51+5.2=6.2即从o到h的最大满意程度为6.2，本段决策为u1*o=a3。所以此动态规划的最优路线为：oa3b1c4d3e3f3g1h。3.4 得出最优解从而可以得出所可以选择的最优课程选择为：第一学年：web应用程序设计，数据结构第二学年：朋辈心理学，数学建模第三学年：运筹学，最优化方法第四学年：xml应用程序设计，java web应用程序设计第四章 问题与展望4.1 结果分析本文运用动态规划原理解决了该大学生选修课的选择问题，为其四年的选修课找到了一个最优选择。同时也说明了动态规划在解决选课问

39、题方面具有的可行性。在本论文中，创新的使用了平均喜好程度这一概念作为选修课选择的标准，既将对于某课程的喜好程度进行了量化，又成为解决选修课的选择的重要标准。4.2 本文的不足与尚可改进之处本文所建立的动态规划模型具有一定的局限性，只考虑了具体某一个同学的选课问题。而且在选课过程中，默认的认为一定能选到所要选择的课程，不考虑抽签过程。在本论文基础上，可以通过matlab编程实现最优解的求解过程，从而建立新型选课系统程序。4.3 matlab 简介与程序实现4.3.1 matlab软件简介matlab是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它

40、将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如c、fortran）的编辑模式，代表了当今国际科学计算软件的先进水平 【6】。matlab所具有的优点：1. 高效的数值计算及符号计算功能,能使用户从繁杂的数学运算分析中解脱出来；2. 具有完备的图形处理功能,实现计算结果和编程的可视化；3. 友好的用户界面及接近数学表达式的自然化语言,使学者易于学习和掌握；4. 功能丰富的应用工具箱(如信号处理工具箱、

41、通信工具箱等) ,为用户提供了大量方便实用的处理工具【7】。4.3.2 动态规划的matlab程序本文中的动态规划模型可以用matlab程序编程实现，由于时间问题以及8阶段的动态规划模型程序过于复杂，所以在此仅附一个四阶段的动态规划模型的matlab实现程序见附录2。参考文献1 徐光辉. 运筹学基础手册.北京：科学出版社，1999 2 胡运权. 运筹学基础及应用（第4版）.北京：高等教育出版社，20043 郭耀煌. 运筹学原理与方法.程度：西南交通大学出版社，19944 弗雷德里克·s. 任建标译.数据、模型与决策.北京：中国财政经济出版社，20015 王日爽. 应用动态规划.北京：

42、国防工业出版社,19876 刘则毅. 科学计算技术与matlab. 北京：科学出版社，2001.7 张志涌. 精通matlab 6. 5 版m . 北京:北京航空航天大学出版社,2003.8 bellman r e. dynamic programming. princeton university press,19579 peterman m l. markov decision process-stochastic dp. john wileysons,1994附录附录1：参考英文及译文：原文dynamic programming: from novice to advancedan im

43、portant part of given problems can be solved with the help of dynamic programming (dp for short). being able to tackle problems of this type would greatly increase your skill. i will try to help you in understanding how to solve problems using dp. the article is based on examples, because a raw theo

44、ry is very hard to understand. note: if you're bored reading one section and you already know what's being discussed in it - skip it and go to the next one. introduction (beginner)what is a dynamic programming, how can it be described? a dp is an algorithmic technique which is usually based

45、on a recurrent formula and one (or some) starting states. a sub-solution of the problem is constructed from previously found ones. dp solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc. now let's see the base o

46、f dp with the help of an example: given a list of n coins, their values (v1, v2, . , vn), and the total sum s. find the minimum number of coins the sum of which is s (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up

47、 to s. now let's start constructing a dp solution: first of all we need to find a state for which an optimal solution is found and with the help of which we can find the optimal solution for the next state. what does a "state" stand for? it's a way to describe a situation, a sub-so

48、lution for the problem. for example a state would be the solution for sum i, where is. a smaller state than state i would be the solution for any sum j, where j<i. for finding a state i, we need to first find all smaller states j (j<i) . having found the minimum number of coins which sum up to

49、 i, we can easily find the next state - the solution for i+1. how can we find it? it is simple - for each coin j, vji, look at the minimum number of coins found for the i-vjsum (we have already found it previously). let this number be m. if m+1 is less than the minimum number of coins already found

50、for current sum i, then we write the new result for it. for a better understanding let's take this example:given coins with values 1, 3, and 5.and the sum s is set to be 11. first of all we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. we then go to sum

51、 1. first, we mark that we haven't yet found a solution for this one (a value of infinity would be fine). then we see that only coin 1 is less than or equal to the current sum. analyzing it, we see that for sum 1-v1= 0 we have a solution with 0 coins. because we add one coin to this solution, we

52、'll have a solution with 1 coin for sum 1. it's the only solution yet found for this sum. we write (save) it. then we proceed to the next state - sum 2. we again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. the optimal solution found for s

53、um (2-1) = 1 is coin 1. this coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins. this is the best and only solution for sum 2. now we proceed to sum 3. we now have 2 coins which are to be analyzed - first and second one, having values of 1 and 3. let&

54、#39;s see the first one. there exists a solution for sum 2 (3 - 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. now let's take the second co

55、in with value equal to 3. the sum for which this coin needs to be added to make 3 , is 0. we know that sum 0 is made up of 0 coins. thus we can make a sum of 3 with only one coin - 3. we see that it's better than the previous found solution for sum 3 , which was composed of 3 coins. we update it and mark it as having o