《物流运筹学》第5章-物流动态规划

第5章物流动态规划

5.1动态规划5.2动态规划数学模型的建立5.3动态规划应用举例第5章物流动态规划本章重点：动态规划是一种研究多阶段决策问题的最优化理论与方法。本章中学生要了解多阶段决策问题，动态规划方法的含义及动态规划的特点；了解动态规划的解题思想，理解其最优性原理；掌握动态规划模型的组成内容、建立方法及求解步骤；掌握动态规划方法在物流领域的应用。下一页返回第5章物流动态规划动态规划是一种研究多阶段决策问题的理论和方法。所谓多阶段决策问题是指这样一类决策过程：它可以分为若干个互相联系的阶段，在每一阶段分别对应着一组可以选取的决策，当每个阶段的决策选定以后，过程也就随之确定。把各个阶段的决策综合起来，构成一个决策序列，称为一个策略。显然由于各个阶段选取的决策不同，对应整个过程就可以有一种不同的策略。当对过程采取某一策略时，可以得到一个确定的（或期望的）效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中间选取一个最优的策略，使在预定的标准下得到最好的效果。上一页下一页返回第5章物流动态规划在物流活动中，有一类过程由于其特殊性，可被分为若干个相互联系的阶段，在每个阶段赌要做出决策，使整个过程达到最好的状态。当然，各个阶段决策的选取不是任意确定的，它依赖于当前的状态，又影响以后的发展。当各个阶段的决策都确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。例5-1某物流公司承担从A市到E市的大批汽车货运如图5-1所示。从A市到E市之间需经过B、C、D三个地区。B地区有三个城市，C地区有四个城市，D地区有二个城市。问公司如何选择由A到E的运输线路，能使总的运输距离最小？上一页返回5.1动态规划5.1.1动态规划的基本概念1.阶段把所给问题的整个过程，恰当地分为若干个既相互联系又相互区别的子过程，以便能按一定的次序去求解，这就是阶段。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程转化为多阶段决策的过程。如上例问题可分为4个阶段来求解，k=1、2、3、4。下一页返回5.1动态规划2.状态状态表示每个阶段开始时的自然状况或客观条件，它描述所研究问题的过程的状况，是不可控因素。在上例问题中，状态就是某阶段的出发位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。通常一个阶段有若干个状态，第一阶段有一个状态就是点A，第二阶段有三个状态，即点集合｛B1，B2，B3

｝，一般第k阶段的状态就是第k阶段所有始点的集合。描述状态的变量称为状态变量，它可用一个数、一组数或一个向量（多维情形）来描述。常用表示第K阶段的状态变量。上一页下一页返回5.1动态规划状态应具有无后效性，即如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各阶段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前状态是以往历史的总结（即马尔科夫性）。如果状态仅仅描述过程的具体特征，则并不是任何实际过程都能满足无后效性的要求。所以，在构造决策过程的动态规划模型时，不能仅从描述过程的具体特征这点着眼去规定状态变量，而要充分注意是否满足无后效性的要求。如果状态的某种规定方式可能导致不满足无后效性，应适当地改变状态的规定方法，达到无后效性的要求。上一页下一页返回5.1动态规划3.决策当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而决定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，它可用一个数、一组数或一个向量来描述。常用表示第K阶段当状态处于时的决策变量，它是状态变量的函数。在实际问题中，决策变量的取值往往被限制在某一范围之内，此范围称为允许决策集合。常用表示第K阶段从状态出发的允许决策集合，显然有。上一页下一页返回5.1动态规划4.策略策略是一个按顺序排列的决策所组成的集合。在实际问题中，可供选择的策略有一定的范围，这个范围称为允许策略集合，一般用表示。从允许策略集合中找出的达到最优效果的的策略称为最优策略。上一页下一页返回5.1动态规划5.状态转移方程状态转移方程是用来确定过程是如何由一个状态到另一个状态演变的。给定第K阶段状态变量的值，如果该段决策变量一经确定，第K+1阶段状态变量的值也就完全确定。即的值随和的值变化而变化。这种确定的对应关系，记为。它描述了由K阶段到K+1阶段的状态转移规律，称为状态转移方程，称为状态转移函数。上一页下一页返回5.1动态规划6.指标函数用来衡量所实现过程优劣的数量指标称为指标函数，常用表示。即：

k=1，2，…，n（1）阶段指标函数用表示第k阶段处于状态时所作决策为时的指标。（2）过程指标函数用表示第k阶段段过程的指标函数。上一页下一页返回5.1动态规划7.最优值函数用表示第k阶段过程的指标函数的最优值，即：其中是最优化（optimization）的缩写，可根据题意取min或max。上一页下一页返回5.1动态规划5.1.2动态规划的基本思想把动态规划方法的基本思想如下：（1）动态规划方法的重点在于正确地写出基本的递推关系式（基本方程）。要做到这一点，必须先将问题的过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量以及定义最优值函数，从而把一个大的问题化成一族同类型的子问题，然后各个求解，即从后向前，逐段递推寻优。在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得到的最优解，就是整个问题的最优解。上一页下一页返回5.1动态规划（2）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取都是从全局来考虑的，与单独考虑本段时的最优选择答案不一定相同。（3）在求解整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，所以最优策略所经过的各段状态便可以通过逐次变换得到，从而确定了最优策略。上一页下一页返回5.1动态规划5.1.3动态规划的最优化原理20世纪50年代时，R·Bellman等人根据研究一类多阶段决策问题，提出了最优性原理作为动态规划的理论基础，它能解决许多类型决策过程的优化问题。动态规划的最优化原理为：作为整个过程的最优化策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。最优化原理的基本思路是：把寻求最优策略看作连续递推的过程，从最终阶段开始，逆着实际过程的进展方向逐段求解，每一段求解中都要利用刚求解完那段的结果，直到初始阶段求出结果，返回始点为止。这种方法又被称为逆序解法。上一页返回5.2动态规划数学模型的建立5.2.1根据最优化原理建立动态规划的数学模型的步骤1.划分阶段，并正确地定义各阶段状态变量使之具有描述性、无后效性和可知性3个特性，同时确定状态集合；2.定义状态变量；3.确定决策变量；4.建立状态转移方程；5.确定指标函数；6.建立逆序递推方程。下一页返回5.2动态规划数学模型的建立下面对例5-1用逆序递推法求解解：其中称为边界条件。第一步当k＝4时递推关系简化成其中状态，决策；由于对状态，都只有唯一决策，所以有上一页下一页返回5.2动态规划数学模型的建立第二步当k＝3时，递推方程为：其中状态，决策，这时从状态C1，C2

，C3

，C4任一点都有两条路线，需加以比较，取其中最短的，即：上一页下一页返回5.2动态规划数学模型的建立这说明由C1到终点E最短距离为5，其路径为。相应决策为。这说明由C2到终点E最短距离为8，其路径为。相应决策为.上一页下一页返回5.2动态规划数学模型的建立这说明由C3到终点E最短距离为5，其路径为。相应决策为.这说明由C4到终点E最短距离为6，其路径为。相应决策为.类似可算出：k＝2时，有上一页下一页返回5.2动态规划数学模型的建立k＝1时只有一个状态点A，则即从A到E的最短距离为12，本段决策为或。上一页下一页返回5.2动态规划数学模型的建立再按计算机顺序反推可得最优决策序列，即时，，，；最优路线为。时，，，；最优路线为。例5-1说明有两条路线到达终点距离最短。上一页下一页返回5.2动态规划数学模型的建立5.2.2动态规划方法的优点1.减少计算量。计算例5-1问题若用穷举法，就要对24条路线进行比较；用动态规划的方法来计算只需要10次。2.丰富了计算结果。在动态规划方法中，物流管理人员得到不仅仅是由起点出发到终点的最短路线及相应的最短距离。这就是说，求出的不仅仅是一个最优策略，而且是一族最优策略，这对于许多实际问题是很有用处的，有利于帮助分析所得到的结果。上一页返回5.3动态规划应用举例5.3.1资源分配问题所谓资源分配问题，就是要将数量一定的一种或若干种资源（例如原材料、资金、机器设备、劳动力、食品等），恰当地分配给若干个使用者，从而使目标函数为最优。例如：某物流公司在某一运输路线上发运一辆汽车，汽车的重上限为a公斤。设该条路线上有n种物品需发运，可以选择性装载，这n种物品编号为1、2、…、n。已知第i种物品每件重量为，可为公司创造的效益是装载数量的函数。问此时应如何选择装载的物品（各几件），使之为公司创造效益最大？这就是著名的车辆装载问题，如流通加工中的下料问题，人造卫星内的物品装载问题等问题都可以归为本类问题。下一页返回5.3动态规划应用举例设为第i种物品的装载件数，则本问题的数学模型为

且为整数它是一个整数规划问题。如果只取0或1，则又称为0-1配载问题。下面用动态规划的方法来求解。上一页下一页返回5.3动态规划应用举例设按可装入物品的n个种类划分为n个阶段；状态变量表示用于装第1种物品至第k种物品的总重量；决策变量表示装入第k种物品的件数。则状态转移方程为，允许决策集合为

最优值函数是当总装载重量不超过时，车辆中可以装入第1种到第k种物品能为公司创造的最大效益值。即且为整数。上一页下一页返回5.3动态规划应用举例因而可写出动态规划的顺序递推关系为然后，逐步计算出、…

及相应的决策函数、…，最后得出的就是所求的最大效益，其相应的最优策略由反推运算即可得出。下面用实际例子求动态规划问题。上一页下一页返回5.3动态规划应用举例例5-2现在载重量为20吨的卡车，可装3种不同的货物。已知这3种货物的重量和装载收费如表所示，又规定货物2和货物3至多装两件。问如何装载这3种货物，可使该车一次运输收费最多。如表5-1所示。解：设为k货物的装载件数，于是可得下列整数规划：上一页下一页返回5.3动态规划应用举例现在，应用动态规划方法来求解，把这个装载问题分成3个阶段，在第k阶段需要确定k货物的装载件数，令－对k货物允许的装载重量；－k货物的装载件数；－k货物装载件时的收益：；－－对k货物允许载重时采取最佳决策所能获得的最大收益，递归方程为：上一页下一页返回5.3动态规划应用举例下面用逆序解法求解第一步k＝3，有方程显然，，由于3货物至多装载2件，因此，决策集合为上一页下一页返回5.3动态规划应用举例由表5-2给出。的计算过程如表5-3所示。第二步k＝2，有方程上一页下一页返回5.3动态规划应用举例显然，，由于2货物至多装载2件，且，因此，决策集合为它由表5-4给出。上一页下一页返回5.3动态规划应用举例在列举本阶段的可能状态时，希望将那些具有相同值的状态合并成一类，以减少计算次数，如果只孤立地考虑阶段2，则根据表5-4，将划分成3个子集，和，各个子集中的状态的决策集合相同，但是发现，同一个子集中的状态相应的值并不相同：例如和在同一个子集中，而表5-5告诉我们，。上一页下一页返回5.3动态规划应用举例所以，对的划分，要同时结合的划分来考虑，由表5-4和表5-5知：划分点向量。划分点向量。于是，计算关于的划分点如表5-6所示。将划分成9个子集：，，，，。的计算过程由表5-7给出。上一页下一页返回5.3动态规划应用举例第三步k＝1，有方程显然，，，的计算过程如表5-8所示。由顺序追踪法可知，本问题的最优策略为：或即最优装载方案有2个：方案I：货物1装4件，货物2装2件，货物3不装；方案II：货物1装5件，货物2不装，货物3装1件。装载收费26。上一页下一页返回5.3动态规划应用举例5.3.2生产计划与存贮问题在物流经营管理中，经常遇到要合理地安排生产与库存的问题，既要满足社会的需要，又要尽是降低成本费用。因此，正确制定生产策略，确定不同时期的生产量和库存量，以使总的生产成本费用与库存费用之和最小，这就是生产与存贮问题的最优化目标。例5-3某农药厂生产某种产品，该产品未来4个月的销售量预测如表5-9所示。上一页下一页返回5.3动态规划应用举例已知生产该产品的生产准备成本为50万元，生产每吨产品的变动成本为1万元。假设期初（即1月份开始）的存货为100吨，库存成本每吨每月1万元。试求该厂四个月的最佳生产计划，目标为总成本最小。另外，此题还提出两个限制条件：其一要求4月末没有库存；其二每月最多能生产500吨。在正式求解之前，先对题意进行一下分析，首先，本题给出的生产成本和变动成本与产品生产数量的关系是：如果生产该种产品，则生产准备成本50万元仅与生产与否有关而与产品数量无关，变动成本则与产品数量成线性关系；其二，库存成本与库存量成线性关系；其三，总成本包括库存成本、生产准备成本和变动成本三部分，但如生产数量、月初设圈套睡本月销售量配合得好，最终还是表现库存成本的多少，所以应以库存成本最小为目标函数，下面转入正式求解。上一页下一页返回5.3动态规划应用举例解：设代表阶段变量；－代表第k月月初库存量；－代表第k月生产数量（决策变量）；－代表库存下的最佳生产量；－代表的销售量（预测值）；－代表第k月的库存为时，从第k月到4月的最佳生产计划的总成本；－代表第k月末（或k+1月初）的库存量，而上一页下一页返回5.3动态规划应用举例－代表的成本，包括生产与库存两项，且根据最优化原理，给出动态规划基本方程如下：根据基本方程，从第4月开始往回推算，即k＝4（第4月）。上一页下一页返回5.3动态规划应用举例依题要求4月末库存为0，故，所以由于代表月初库存，为保证吨，生产数量来确定。为简便起见，设，计算结果如表5-10所示。k＝3（第3个月）；第3个月的销售数量变了，其基本方程为：上一页下一页返回5.3动态规划应用举例第3个月的计算与第4个月的计算不同这处是月末允许有库存，且库存数量应与4月初库存相等，以保持阶段之间的有机联系。为此，当时，则。详细计算结果如表5-11所示。k＝2（第2个月份）：上一页下一页返回5.3动态规划应用举例注：方案设计取。由于第2月份预测销售量为500吨，再考虑第3月份的库存量，第2月份的方案设计及计算结果如表5-12所示。注：取值在相等情况下取小值。k＝1（第1月份）：1月份月初库存已知。一月份预测销售量为，因此，1月份的生产数量吨。于是有如下基本方程：上一页下一页返回5.3动态规划应用举例根据的取值范围，取，详细计算结果如表5-13所示。由表5-13计算结果可知，1月份最佳生产量为吨，本月总成本450万元，月末库存，以后各月总成本万元，总成本为1600万元，这是最佳的生产计划，根据表5-13提供的信息，便可给出2～4月份的最佳生产计划，本月生产总成本等信息。上一页下一页返回5.3动态规划应用举例首先，根据，在表5-12中知：，，由表5-11中知，有三个方案，取总成本最小的方案，即，，由表5-10知，的方案是最佳生产计划。将上面优化结果统列于表5-14，以供领导决策参考。上一页下一页返回5.3动态规划应用举例5.3.3采购问题在生产中，经常需要采购原材料，如果欲采购的某种商品在未来各个周期其价格变动不定，但该商品未来每期可能的价格及其发生的概率分布是可知的，那么在规定的采购期限以内何时购买才能使期望价格最低。例5-4某生产企业在近5周内购买一批原料，以保证生产需要。根据过去的统计资料，其浮动价格和概率已知如表5-15所示，问何时采购，使其采购价格的数学期望值最小。上一页下一页返回5.3动态规划应用举例解：代表阶段变量。为第k周的原料实际价格。为第k周的决策，（采购）或（等待）。另外用表示：当第k周决定等待，而在以后采购时的价格期望值。最优指标函数。表示k周实际价格为时，从第k周至第5周的最低期望价格。逆序递推关系式为：

上一页下一页返回5.3动态规划应用举例第一步k＝5，此时只有唯一决策，按该周价格采购。第二步k＝4时，此时有两种决策：采购或等待。上一页下一页返回5.3动态规划应用举例则第三步k＝3时上一页下一页返回5.3动态规划应用举例则第四步k＝2时上一页下一页返回5.3动态规划应用举例则第五步k＝1时上一页下一页返回5.3动态规划应用举例则根据以上结果得到的最优采购策略为：若前三周原料价格为500元，应立即采购，否则应等待；在第四周时，价格为500元或600元，应立即采购，否则就等待；在第五周时，无论什么价格都要采购。依据上述最优策略进行采购时，价格的数学期望值为：上一页下一页返回5.3动态规划应用举例且上一页返回图5-1路线图返回表5-1货物质量与运输收费表返回货物重量（吨）收费134245356表5-2决策集合返回0~45~910~20表5-3计算过程返回0~4---005~90+06+0-6110~200+06+012+0122表5-4决策集合返回0~34~78~20表5-5计算过程返回40+05+05150+65+060表5-6子集划分返回00485591310101418表5-7计算过程返回0~30+0--0040+00+5-515~70+65+0-6080+65+010+010290+65+610+011110~120+125+610+0120130+125+610+616214~170+125+1210+617