第二部分动态规划（DymamicProgramming）第三章动态规划动态规划是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径，而不是一种算法（如LP单纯形法）。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定性、离散随机性、连续确定性和连续随机性。§1动态规划的基本概念和最优化原理一、引例（最短路线问题）B15A35B22163874C18C23586D13466CC33ED2D4B3A1B25E上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到E的铺管线路，使总距离最短（或总费用最小）。将该问题划分为4个阶段的决策问题，即第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。如果用完全枚举法，则可供选择的路线有31×3×2×1=18（条），将其一一比较才可找出最短路线：A→B1→C2→D3→E其长度为15。显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：第四阶段，由D1到E只有一条路线，其长度f4（D1）=4，同理f4（D2）=3。第三阶段，由Cj到Di分别均有两种选择，即?6+4???CD+f4(D1)?f3(C1)=min?11=min??=10，决策点为D1??C1D2+f4(D2)??8+3??CD+f3(C2)=min?21?C2D2+?CD+f3(C3)=min?31?C3D2+f4(D1)??8+4??=min?5+3??=8，决策点为D2f4(D2)???f4(D1)??3+4*??=min?5+3?=7,决策点为D1f4(D2)???第二阶段，由Bj到Cj分别均有三种选择，即：?B1C1+f3(C1)??1+10??BC+f(C)?=min?*?=10，决策点为Cf2(B1)=min?22232??3+7??B3C3+f3(C3)??6+8??????B2C2+f3(C1)??8+10??BC+f(C)?=min?*?=14，决策点为C或Cf2(B2)=min?222332??7+7???B3C3+f3(C3)??6+8??????B3C1+f3(C1)??2+10??BC+f(C)?=min?*?=11，决策点为Cf2(B3)=min?32232??4+7??B3C3+f3(C3)??6+8?????第一阶段，由A到B，有三种选择，即：2?AB1+f2(B2)??5+10??f1(A)=min?AB2+f2(B2)?=min?3+14?=15，决策点为B1?????AB5+f2(B5)??5+11?????f1(A=15)说明从A到E的最短铺管线长为1，最短路线的确定可按计算顺序反推而得。即A→B1→C2→D1→E上述最短路线问题的计算过程，也可借助于图形直观的表示出来：1010B1C1453D141514730AB2C2E3D211B38C3图中各点上方框的数，表示该点到E的最短距离。图中双箭线表示从A到E的最短路线。从引例的求解过程可以得到以下启示：①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的多个阶段的决策问题。所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：决策状态1状态2决策状态状态n决策状态②在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要3注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。③各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。④决策过程是与阶段发展过程逆向而行。二、动态规划的基本概念1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常用自然数k表示。如引例可划分为4个阶段