《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第七章动态规划 第一节基本概念》由会员分享，可在线阅读，更多相关《物流运筹方法与工具 教学课件 ppt 作者 彭秀兰 毛磊第七章动态规划 第一节基本概念（24页珍藏版）》请在金锄头文库上搜索。
1、第七章 物流预测和决策,第一节 动态规划的基本概念和最优性原理 第二节 动态规划模型的建立与求解步骤 第三节 资源分配问题 第四节 生产与存贮问题 第五节 车辆配载问题 第六节 工程路线问题,了解多阶段决策问题、动态规划方法的含义及动态规划的特点。 了解动态规划的解题思想、理解其最优性原理。 掌握动态规划模型的组成内容、建立方法及求解的一般性步骤。 掌握动态规划方法在物流领域的应用。,-本章知识点-,加吉公司的送货路径,加吉公司是一家大型第三方物流公司，要承担从A市到G市的 大批汽车货运。从A市到G市之间需经过B、C、D、E和F五个地 区。B地区有两个城市B1、B2，C地区有四个城市C1、C2
2、、C3、 C4，D地区有三个城市D1、D2、D3，E地区有三个城市E1、E2、 E3，F地区有两个城市F1、F2，城市之间的运输距离如图7-1所 示。,图7-1 加吉公司的运输线路图,-导引案例-,加吉公司的送货路径,问加吉公司应如何选择由A市到G市的运输线路，能使总的运输距离最低。 这个问题当然可以用穷举法、线性规划等方法求解。但是在解决实际问题时，首先，即使指标函数的形式比较简单，约束条件却往往很多，所确定的约束集合就十分复杂，因此用穷举法、线性规划等方法求解就比较困难，其次，这些方法是整体求解，是单阶段进行的，只能得到全过程解，不能得到包括子过程的一族解，而这个解族却正是分析某些实际问题
3、时所需要的，还有，这些方法不能反映过程之间前后演变的关系。为解决这些问题，人们提出了一种新的解题方法，这就是本章所要介绍的动态规划方法。,-导引案例-,一、多阶段决策与动态规划,在物流活动中，有一类过程，由于其特殊性，可被分为若干 个相互联系的阶段，在每个阶段都需要做出决策，使整个过程达 到最好的状态。当然，各个阶段决策的选取不是任意确定的，它 依赖于当前的状态，又影响以后的发展。当各个阶段决策确定 后，就组成了一个决策序列，因而也就决定了整个过程的一条活 动路线。这种把一个问题看做是一个前后关联具有链状结构的多 阶段过程（如图7-2）就称为多阶段决策过程，也称序贯决策过 程。这种问题就被称为
4、多阶段决策问题。,图7-2多阶段决策过程,- 第一节动态规划的基本概念和最优性原理 -,一、多阶段决策与动态规划,在多阶段决策问题中，各个阶段采取的决策，一般说来是和时间有关的，决策依赖于当前的状态，又随即引起状态的变化，一个决策序列就是在变化的状态中产生的，故有“动态”的含义，因此，把处理它的方法称为动态规划方法。其实，一些与时间没有关系的静态规划（如线性规划、非线性规划）问题，只要人为地引入“时间”因素，也可以把它视为多阶段决策，用动态规划的方法去处理。 如引例问题，求A到G的最短路线问题是动态规划中一个较为直观的典型例子。现通过讨论它的解法，来说明动态规划方法的基本思想，并阐述它的基本概
5、念。,- 第一节动态规划的基本概念和最优性原理 -,一、多阶段决策与动态规划,由图7-1可知，从A点到G点可以分为6个阶段从A到B为第一阶段，从B到C为第二阶段从F到G为第六阶段。在第一阶段，A为起点，终点有B1、B2，两个，因而这时走的路线有两个选择，一是走到B1；一是走到B2。若选择走到B2的决策，则B2就是第一阶段在我们决策之下的结果。它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对应于B2点就有一个可供选择的终点集合C2，C3，C4；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点同理递推下去，可看到：各个阶段的决策
6、不同，运输路线就不同。很明显，当某阶段的始点给定时，将直接影响着后面各阶段的行进路线和整个路线的长短而后面各阶段的路线的发展不受这点以前各阶段路线的影响故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的决策序列所决定的路线的总路程最短。,- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,（一）阶段 把所给问题的过程，恰当地分为若干个即相互联系又相互区别的子过程，以便能一定的次序去求解，这就是阶段。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来划分。但要便于把问题的过程能转化为多阶段决策的过程。 如引例问题可分为6个阶段来
7、求解，k=1、2，3、4、5、6,- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,（二）状态 状态表示每个阶段开始时的自然状况或客观条件，它描述所研究问题的过程的状况，是不可控因素。在引例问题中，状态就是某阶段的出发位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点通常一个阶段有若干个状态，第一阶段有一个状态就是点A，第二阶段有两个状态，即点集合B1，B2，一般第k阶段的状态就是第k阶段所有始点的集合。 描述状态的变量称为状态变量，它可用一个数、一组数或一向量(多维情形)来描述常用Sk表示第k阶段的状态变量如在引例问题中第三阶段有四个状态，则状态变量Sk可取四个值，
8、即C1、C2、C3、C4。,- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,状态应具有无后效性，即如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前状态是以往历史的总结(即马尔科夫性)。 如果状态仅仅描述过程的具体特征，则并不是任何实际过程都能满足无后效性的要求。所以，在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点着眼去规定状态变量，而要充分注意是否满足无后效性的要求。如果状态的某种规定方式可能导致不满足无后效性，应适当地改变状态的规定方法，达到无后效性的要求。,
9、- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,（三）决策 决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而决定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，它可用一个数、一组数或一向量来描述常用uk(sk)表示第k阶段当状态处于sk时的决策变量。它是状态变量的函数。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有uk(sk)Dk(sk)。 如在引例问题的第二阶段中，若从状态B2出发，就可作出三种不同的决策，其允许决策集合D2（B2）C2，C
10、3，C4，若选取的点为C2，则C2是状态B2在决策u2（B2）作用下的一个新的状态，记作u2（B2）C2。,- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,（四）策略 策略是一个按顺序排列的决策所组成的集合。 在实际问题中，可供选择的策略有一定的范围，这些范围称为允许策略集合，一般用P表示。从允许策略集合中找出达到最优效果的的策略称为最优策略。,- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,（五）状态转移方程 状态转移方程是用来确定过程是如何由一个状态到另一个状态演变的。若给定第k阶段状态变量sk的值，如果该段决策变量uk一经确定，第k1阶段状态变
11、量sk1的值也就完全确定。即sk1的值随sk和uk的值变化而变化这种确定的对应关系，记为sk1Tk（sk，uk）。它描述了由k阶段到k十1阶段的状态转移规律，称为状态转移方程。Tk称为状态转移函数。如在引例问题中，状态转移方程为sk1uk(sk)。,- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,（六）指标函数和最优值函数 用来衡量所实现过程优劣的数量指标称为指标函数，常用Vk，n表示。即Vk，nVk，n（sk，uk，uk1，un） k1，2，n 对于要构成动态规划模型的指标函数，应具有可分离性，并满足递推关系，即Vk，n可以表示为sk、uk、Vk1，n的函数，记为 Vk
12、，n（sk，uk，uk1，un）ksk，uk，Vk，n（sk，uk，un） 在实际问题中，很多指标函数都符合这个性质。,- 第一节动态规划的基本概念和最优性原理 -,二、动态规划的基本概念,常见的指标函数的形式是： （1）过程和它的任一子过程的指标是它所包含的各阶段的指标的和。 （2）过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。 指标函数的最优值，称为最优值函数，记为fk(sk)。它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即 fk(sk) opt Vk，n(sk，uk，un) 其中opt是最优化（optimization）的缩写，可
13、根据题意取min或max。 在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产品的产量或资源消耗等。,- 第一节动态规划的基本概念和最优性原理 -,三、动态规划的基本思想和基本方程,现在，再结合解决引例的最短路线问题来介绍动态规划方法的基本思想。生活中的常识告诉我们，最短线路有一个重要特性：如果由A点经P点和H点到达终点G是一条最短线路，则由点P出发经过H点到达终点G的这条路线，对于从点P出发到达终点G的所有可能选择的不同路线来说，必定也是最短路线。例如，在最短路线问题中，若找到了AB1C2D1E2F2G是由起点A到终点G的最短路线，则D1E2F2G应该是由Dl出发到G点的所
14、有可能选择的不同路线中的最短路线。（此特性用反证法易证） 根据最短路线这一特性，寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法，求出各点到终点G的最短路线，最后求得由A点到G点的最短路线。所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法如图7-3所示。,- 第一节动态规划的基本概念和最优性原理 -,三、动态规划的基本思想和基本方程,图7-3 动态规划法的解题步骤,下面按照动态规划的方法，将引例问题从最后一段开始计算，由后向前逐步推移至A点。 当k6时，由F1到终点G只有一条路线，故f6(F1)=4，同理，f6(F2)=3。,- 第一节动态规划的基本概念和最优性
15、原理 -,三、动态规划的基本思想和基本方程,当k5时，出发点有E1、E2、E3三个若从E1出发，则有两个选择，一是至F1，一是至F2，则,其相应决策为u5(E1)F1，这说明，由E1出发到终点G的最短距离为7，最短路线为E1F1G。 同理，从E2和E3出发，则有,其相应决策为u5(E2)F2，,其相应决策为u5(E3)F2，,- 第一节动态规划的基本概念和最优性原理 -,三、动态规划的基本思想和基本方程,类似地，可算得 当k4时，有f4(D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2 当k3时，有f3(C1)=13 u3(C1)=D1 f3(C2)=10 u3(C2)=D1 f3(C3)=9 u3(C3)=D2 f3(C4)=12 u3(C4)=D3 当k2时，有 f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3 当k1时，出发点只有一个A点，则有,- 第一节动态规划的基本概念和
