第六章 物流系统模型及分析.ppt

《第六章 物流系统模型及分析.ppt》由会员分享，可在线阅读，更多相关《第六章 物流系统模型及分析.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 物流系统模型及分析物流系统模型及分析 主要内容：主要内容：1 1线性规划法线性规划法(Linear Programming Method)Linear Programming Method)2 2运输调配法运输调配法(Transportation Programming Method)Transportation Programming Method)3 3指派问题指派问题(Assignment Problem)Assignment Problem)4 4威门法威门法(WimmertWimmert Method)Method)5 5动态规划法动态规划法(Dynamic Progr

2、amming Method)Dynamic Programming Method)引引 言言 本章将介绍设备位置规划和物料移动规划的量本章将介绍设备位置规划和物料移动规划的量化分析方法。由于这些方法都涉及到应用数学，特化分析方法。由于这些方法都涉及到应用数学，特别是运筹学别是运筹学(Operation Research)Operation Research)，目前已经有专目前已经有专著进行介绍，这里仅就量化方法的构架予以介绍，著进行介绍，这里仅就量化方法的构架予以介绍，并通过设备配置或物料移动有关的例子加以说明，并通过设备配置或物料移动有关的例子加以说明，最后对这种技术在实际运用上进行评估与比

3、较，为最后对这种技术在实际运用上进行评估与比较，为日后从事这方面分析、研究时选择采用的依据。日后从事这方面分析、研究时选择采用的依据。一般而言，计量方法通常是衡量效果的一个基一般而言，计量方法通常是衡量效果的一个基准，例如运输距离准，例如运输距离(Traffic Distance)Traffic Distance)、运输作功运输作功或运输成本等，然而这些方法并不保证一定能求得或运输成本等，然而这些方法并不保证一定能求得最优解，但可提供较优解。最优解，但可提供较优解。量化方法的型式量化方法的型式 量化方法的型式量化方法的型式 确定型确定型(Deterministic)概率型概率型(Probabi

4、listic)线性确定型线性确定型(Linear-deterministic)非线性确定型非线性确定型(Nonlinear-deterministic)线性概率型线性概率型(Linear-probabilistic)非线性概率型非线性概率型(Nonlinear-probabilistic)6-26-2 线性规划法线性规划法(Linear Programming)Linear Programming)线性规划是作业研究中最常用的量化分析线性规划是作业研究中最常用的量化分析技术。用在资源或能量有限时，用数学方法进技术。用在资源或能量有限时，用数学方法进行最佳的调配，以达到最小成本或最大效益的行最佳

5、的调配，以达到最小成本或最大效益的要求目标。线性规划可应用在寻求非自动化或要求目标。线性规划可应用在寻求非自动化或输送带式物料搬运系统的最优化。输送带式物料搬运系统的最优化。一、模型的假设条件一、模型的假设条件1 1确定确定性性(deterministic)deterministic)在模型中有关的技术状况、资源及策略均为已知而不是呈在模型中有关的技术状况、资源及策略均为已知而不是呈现某种概率分配，例如特定场所或区域有良好的储存和仓储位现某种概率分配，例如特定场所或区域有良好的储存和仓储位置；搬运距离、成本或时间为确定，可做为衡量的基准等。置；搬运距离、成本或时间为确定，可做为衡量的基准等。2

6、 2线性线性(linearity)linearity)模型中的目标函数与约束结构型式均为线性函数，即各种模型中的目标函数与约束结构型式均为线性函数，即各种成本、距离等参数关系为一次关系。成本、距离等参数关系为一次关系。3 3可分割性可分割性(divisibility)divisibility)模型中的决策变量假定为连续性变量，因此具有分割性。模型中的决策变量假定为连续性变量，因此具有分割性。即模型中变量的解不一定是整数，而可以是小数。即模型中变量的解不一定是整数，而可以是小数。4 4非负性非负性(NonnegativityNonnegativity)模型中的变量不能有负值，变量的值最小为零。模

7、型中的变量不能有负值，变量的值最小为零。5 5比例性比例性(Proportionality)Proportionality)模型中变量的边界贡献或单位成本是固定常数，并不因使模型中变量的边界贡献或单位成本是固定常数，并不因使用量的变动而变动。用量的变动而变动。二、线性规划模型二、线性规划模型 (1)(1)目标函数目标函数 或或 (2)2)结构约束条件结构约束条件 或或(3)(3)非负约束条件非负约束条件以上各符号意义如下：以上各符号意义如下：Z Z ：目标函数值；目标函数值；c cj j ：目标函数系数，计有目标函数系数，计有n n个，指第个，指第j j个决策变量的权重贡献或个决策变量的权重贡

8、献或 单位成本。单位成本。x xj j：决策变量，计决策变量，计有有n n个；个；a aijij：技术系数，指第技术系数，指第j j个决策变量所需投入的第个决策变量所需投入的第i i种资源的数量。种资源的数量。b bi i：常数，指第常数，指第i i种资源的数量，共有种资源的数量，共有m m种。种。三、线性规划法例三、线性规划法例l某公司现有类似功能的设备在甲、乙两地，下游的某公司现有类似功能的设备在甲、乙两地，下游的两个部门两个部门A A与与B B，各设备的产量、部门的需求量以及各设备的产量、部门的需求量以及设备至部门间的单位成本资料如下：设备至部门间的单位成本资料如下：试求在运输成本最低的

9、目标下，各设备与各部门间试求在运输成本最低的目标下，各设备与各部门间的运输量应为多少的运输量应为多少?部部 门门供应量供应量(S Si i)A AB B设设备备甲甲x x11115 5x x121212122020乙乙x x21211010 x x22228 83030需求量需求量(D Dj j )1010404050=50=D Dj j=S Si i三、线性规划法例三、线性规划法例解：根据以上资料建立解：根据以上资料建立线性规划模式如下：线性规划模式如下：S.t.S.t.根据线性规划的方法，可根据线性规划的方法，可根据线性规划的方法，可根据线性规划的方法，可将此模型变成下列形式：将此模型变成

10、下列形式：将此模型变成下列形式：将此模型变成下列形式：S.t.S.t.S.t.S.t.三、线性规划法例三、线性规划法例S.t.S.t.S.t.S.t.x x1111x x1212x x2121x x2222Z Z0 0-5-5-12-12-10-10-8-8x x3 320201 11 10 00 0 x x4 430300 00 01 11 1x x5 510101 10 01 10 0 x x6 6-60-60-2-2-1-1-2-2-1-1初解表初解表 x6出，所以x12进 三、线性规划法例三、线性规划法例x11x6x21x22Z72019-12144x3-40-11-2-1x43000

11、11x5101010 x12602-121x11进进，x5出出 x5x6x21x22Z530-19-12-54x3-3011-1-1x4300011x11101010 x1240-2-101x22进进，x4出出 三、线性规划法例三、线性规划法例x5x6x21x4Z410-19-12-9-4x301101x22300011x11101010 x1210-2-1-1-1 基变量的解值均大于或等于零，目标函数的系数基变量的解值均大于或等于零，目标函数的系数均小于或等于零，因此，此表为最优解表，最优解为：均小于或等于零，因此，此表为最优解表，最优解为：x x1111=10=10 x x1212=10=

12、10 x x2222=30=30 设备设备部门部门数量数量单位运输成本单位运输成本运输成本运输成本甲甲A A10105 55050甲甲B B10101212120120乙乙B B30308 8240240总运输成本总运输成本410410四、线性规划法的实用评估四、线性规划法的实用评估 线性规划能广泛地应用在物料分线性规划能广泛地应用在物料分(Distribution)Distribution)，设施位置选择设施位置选择(Location)Location)，设备配置设备配置(Allocation)Allocation)，产品组合产品组合(Product Mix)Product Mix)，设备更

13、新设备更新(Replacement)Replacement)和模型规划上，然而在工厂布置上，线性规划缺乏真和模型规划上，然而在工厂布置上，线性规划缺乏真实的衡量单位。在大多数的问题上，时间与成本是我实的衡量单位。在大多数的问题上，时间与成本是我们要求最优化的值，但在实际运用上，这些值往往已们要求最优化的值，但在实际运用上，这些值往往已被任意选取，以致造成以时间与成本来当作衡量标准被任意选取，以致造成以时间与成本来当作衡量标准是否最合适的问题。是否最合适的问题。6-6-3 3 运输调配法运输调配法(Transportation Programming)Transportation Program

14、ming)运输调配是针对单一运输调配是针对单一商品自不同供应点分配到商品自不同供应点分配到不同需求点，而其总运输不同需求点，而其总运输成本为最低。成本可以用成本为最低。成本可以用距离、时间或金额来表示。距离、时间或金额来表示。123(1)(2)(3)(4)本问题的型式仅允许自供运本问题的型式仅允许自供运点连至目的地。假定有点连至目的地。假定有m m个供应点，个供应点，每一供应点每一供应点i i可以供应的数量为可以供应的数量为a ai i个个(i i=l=l，2 2，m m)；需求点有需求点有n n个，每一需求点需要个，每一需求点需要b bj j个个(j j=l=l，2 2，n n)，则运输成本

15、有则运输成本有m mn n个，个，每一个分别代表自每一供应点运每一个分别代表自每一供应点运一个至每一需求点的成本。运输一个至每一需求点的成本。运输问题的目标在用完供应点的物料问题的目标在用完供应点的物料而满足需求点的物料需求，且其而满足需求点的物料需求，且其总运输成本为最小。总运输成本为最小。一、运输调配模型一、运输调配模型 (1)(1)供应点的总供应量必等于需求点的需求量。供应点的总供应量必等于需求点的需求量。(2)2)由任一供应点运至各需求点的总量必等于此一供应点总量。由任一供应点运至各需求点的总量必等于此一供应点总量。(i i=l=l，2 2，m m)(3)(3)每一需求点的需求量必由各

16、供应点运来加以完全满足。每一需求点的需求量必由各供应点运来加以完全满足。(j j=1=1，2 2，n n)(4)(4)对所有的对所有的i i和和jxjxijij00，(5)(5)目标成本函数目标成本函数 c cijij表示供应点表示供应点i i运至需求点运至需求点j j每一个的成本。每一个的成本。x xijij表示由表示由i i运至运至j j的个数。的个数。由上面模型可知，总共有由上面模型可知，总共有m mn n个决策变量，有个决策变量，有m m+n n个个约束条件，但这约束条件，但这m m+n n个约束条件因为有个约束条件因为有 的关系，因而真正只有的关系，因而真正只有m m+n-n-1 1

17、个约束条件是独立的，个约束条件是独立的，换言之，在换言之，在m m+n n个约束条件中只要有个约束条件中只要有m m+n n-l-l个成立的话，个成立的话，剩下来的那个约束条件式也必然成立。因此，只要取剩下来的那个约束条件式也必然成立。因此，只要取m m+n n个约束条件中任意个约束条件中任意m m+n n-1-1个来求解即可，也就是说个来求解即可，也就是说将会得到将会得到m m+n n-l-l个非负的基变量解值。个非负的基变量解值。二、运输调配法例二、运输调配法例 假设厂内物料搬假设厂内物料搬运系统使用相同的叉运系统使用相同的叉车和容器，由甲、乙、车和容器，由甲、乙、丙三个储存区运至丙三个储

18、存区运至A A、B B、C C、D D四个工作区，四个工作区，假设容器由叉车一次假设容器由叉车一次搬运一个，且搬运后搬运一个，且搬运后不再可用，下表所示不再可用，下表所示各区的容器储存量、各区的容器储存量、需求量和搬运单位成需求量和搬运单位成本，试在最低的目标本，试在最低的目标下决定由各储存区至下决定由各储存区至各工作区的运送量。各工作区的运送量。运输问题成本矩阵运输问题成本矩阵 运输问题可用西北角法、最低成本运输问题可用西北角法、最低成本法、简捷法法、简捷法(Simplex method)Simplex method)或差或差额法来求得最优解。本例以差额法额法来求得最优解。本例以差额法求解求

19、解 。此法的进行是分别计算各行各列中成本此法的进行是分别计算各行各列中成本最小与次小间的差额，再从各差额中找最小与次小间的差额，再从各差额中找出最大者，从差额最大的那行或那列填出最大者，从差额最大的那行或那列填起，只要某行或某列满足了，即将该行起，只要某行或某列满足了，即将该行或该列划掉，再重新计算各行各列中未或该列划掉，再重新计算各行各列中未划线地方的最小与次小成本差额。直到划线地方的最小与次小成本差额。直到各行各列均满足为止。各行各列均满足为止。二、运输调配法例二、运输调配法例总运输成本为总运输成本为 10105+85+825+1225+125+105+1025+725+715+815+8

20、25=86525=865。6 6-4 4 指派问题指派问题(Assignment Problem)Assignment Problem)指派问题为线性规划的特殊情况，用以指指派问题为线性规划的特殊情况，用以指派派n n个工作到个工作到n n部设备。每一个工作对每一部设部设备。每一个工作对每一部设备的效益为已知。其目标在使每一部设备仅能备的效益为已知。其目标在使每一部设备仅能指派一个工作，而其目标的效益为最佳。指派一个工作，而其目标的效益为最佳。一、指派问题模型一、指派问题模型 约束条件为：约束条件为：由指派问题的模型可知：指派问题是运输问题的由指派问题的模型可知：指派问题是运输问题的一个特例。

21、因为一个特例。因为a ai i=b bj j=1=1，且且m m=n n，则则a ai i=b bj j=n n，所所以在矩阵表中各行各列均只有一个以在矩阵表中各行各列均只有一个x xijij=l=l，且同一行或且同一行或同一列中均只有一个同一列中均只有一个x xijij=l=l，其他的其他的x xijij均等于零，故知均等于零，故知在在n nn n的指派问题中，共有的指派问题中，共有n n+n n个约束条件，但只有个约束条件，但只有n n个是相互独立的，也只有个是相互独立的，也只有n n个基变量解值为个基变量解值为 l l，换言之，换言之，另外有另外有n n个基变量退化了。个基变量退化了。二

22、、指派问题解题的原理二、指派问题解题的原理 对于指派问题的解法，早有学者对于指派问题的解法，早有学者(K KW WKuhn)Kuhn)提出一套方法，称之为匈牙利法提出一套方法，称之为匈牙利法(Hungarian Method)Hungarian Method)。匈牙利法是以最小平匈牙利法是以最小平衡问题为基础，至于不是最小平衡的问题，衡问题为基础，至于不是最小平衡的问题，仍应先化成最小平衡之后再用匈牙利法来解，仍应先化成最小平衡之后再用匈牙利法来解，其基本道理与矩阵减化法是相似的。其基本道理与矩阵减化法是相似的。三三、指指派派问问题题解解题题的的流流程程四、指派问题例四、指派问题例 布置设计师

23、拟增布置设计师拟增三部新设备三部新设备A A，B B，C C到到现有布置上。叉车负现有布置上。叉车负荷大小是每次仅能一荷大小是每次仅能一个单位。车子移动受个单位。车子移动受限于通道而为直角方限于通道而为直角方向。图中的向。图中的X X，Y Y，Z Z为为新机器的可能候选位新机器的可能候选位置，置，而而l l，2 2，3 3，4 4，5 5为现有机器位置。为现有机器位置。现有机器位置现有机器位置(方块方块)与与新机器候选位置新机器候选位置(圆圈圆圈)四、指派问题例四、指派问题例新新机机器器现现 有有 机机 器器1 12 23 34 45 5A A25258 84 40 03030B B0 07

24、7101012128 8C C8 85 560600 01616候选候选机器机器现现 有有 机机 器器X XY YZ Z1 12 21 16 62 22 23 34 43 34 43 32 24 46 67 72 25 59 96 63 3距离数据距离数据(矩阵矩阵)交通数据交通数据(矩阵矩阵)效益矩阵效益矩阵效益矩阵效益矩阵=交通矩阵交通矩阵距离矩阵距离矩阵HungarianHungarian法求解法求解 减去该行的最小值减去该行的最小值 241241减去该行的最小值减去该行的最小值 9696减去该行的最小值减去该行的最小值 236 236X XY YZ Z A A3523522412412

25、80280 B B1981981831839696 C C410410299299236236各行均已出现了各行均已出现了“0 0”，再观察列：就，再观察列：就是是第一列还未出现第一列还未出现“0 0”。第一列。第一列减去该列的最小值减去该列的最小值 102 102X XY YZ ZA A1111110 03939B B10210287870 0C C17417463630 0X XY YZ Z A A9 90 03939 B B0 087870 0 C C727263630 0最佳布置可以出来：最佳布置可以出来：A A到到Y Y；B B可以到可以到X X或或Z Z；C C可以分派到可以分派到

26、Z Z，因此，其最佳的因此，其最佳的布置可行解为布置可行解为 A A机器指派到机器指派到Y Y位置位置 B B机器指派到机器指派到X X位置位置 C C机器指派到机器指派到Z Z位置位置 五、指派问题的实用评估五、指派问题的实用评估 l指派法对于设备布置与物料搬运问题是具有相当的实指派法对于设备布置与物料搬运问题是具有相当的实证价值，而且数学运算也很容易，也可处理设备与候证价值，而且数学运算也很容易，也可处理设备与候选位置数目不相等以及限制指派位置的问题。然而，选位置数目不相等以及限制指派位置的问题。然而，指派问题的处理也有其极限，它无法处理设备非为独指派问题的处理也有其极限，它无法处理设备非

27、为独立的状况，因为若两设备间有直接的物料搬运相连接，立的状况，因为若两设备间有直接的物料搬运相连接，在模型建立时无法结合其需求而设定在模型中。在模型建立时无法结合其需求而设定在模型中。l指派问题的另一个缺点是缺乏考虑空间有效利用或限指派问题的另一个缺点是缺乏考虑空间有效利用或限制空间大小的能力，它可能使得小设备被指派到大空制空间大小的能力，它可能使得小设备被指派到大空间而导致地面空间的浪费，对此缺点有一部分可由成间而导致地面空间的浪费，对此缺点有一部分可由成本矩阵的数字来控制，但不完全。本矩阵的数字来控制，但不完全。6-56-5 威门法威门法(WIMMERT Method)WIMMERT Me

28、thod)威门法是指派问题的另一种处理方法，此威门法是指派问题的另一种处理方法，此法是由法是由R RJ JWIMMERTWIMMERT于于19571957年所提出，也是年所提出，也是针对针对n n个部门个部门(或设备或设备)放置放置于于n n个区域的布置组个区域的布置组合问题，其主要着眼点是要使部门间的距离与合问题，其主要着眼点是要使部门间的距离与运送量的乘积为最小。运送量的乘积为最小。一、威门法的假设条件一、威门法的假设条件WIMMERTWIMMERT模型的假设条件：模型的假设条件：(1)1)各个部门的位置是可互换的。各个部门的位置是可互换的。(2)2)二个部门间的距离与方向无关，亦即由二个

29、部门间的距离与方向无关，亦即由A A部部门到门到B B部门的距离与由部门的距离与由B B部门到部门到A A部门的距离是一样的。部门的距离是一样的。(3)3)搬运成本与距离成正比例。搬运成本与距离成正比例。二、二、WIMMERTWIMMERT方法简介方法简介 WIMMERTWIMMERT的处理方式先将各区域间的搬运的处理方式先将各区域间的搬运距离距离B B1 1，B B2 2，B Bt t以单调非减以单调非减(Monotonic Monotonic NondecreasingNondecreasing)的次序排列，而各部门间的搬的次序排列，而各部门间的搬运重量运重量A A1 1，A A2 2，A

30、 At t以单调非增以单调非增(Monotonic Monotonic NonincreasingNonincreasing)的次序排列，然后依据搬运距的次序排列，然后依据搬运距离与搬运重量做成一阶的特殊矩阵离与搬运重量做成一阶的特殊矩阵(其中其中t=c(nt=c(n，2)2)，以此一特殊矩阵作为讨论的基础，如以此一特殊矩阵作为讨论的基础，如后表所示：后表所示：(其中其中X Xijij=A Ai iB Bj j)B B1 1B B2 2B Bj jB Bk kB Bt-1t-1B Bt tA A1 1X X1,11,1X X1,21,2X X1,j1,jX X1,k1,kX X1,t-11,t

31、-1X X1,t1,tA A2 2X X2,12,1X X2,22,2X X2,j2,jX X2,k2,kX X2,t-12,t-1X X2,t2,tA Am mX Xm,1m,1X Xm,2m,2X Xm m,j,jX Xm m,k,kX Xm,t-1m,t-1X Xm m,t,tA Ai iX Xi,1i,1X Xi,2i,2X Xi i,j,jX Xi i,k,kX Xi,t-1i,t-1X Xi i,t,tA At-1t-1X Xt-1,1t-1,1X Xt-1,2t-1,2X Xt-1,jt-1,jX Xt-1,kt-1,kX Xt-t-1,t-11,t-1X Xt-1,tt-1,t

32、A At tX Xt,1t,1X Xt,2t,2X Xt t,j,jX Xt t,k,kX Xt,t-1t,t-1X Xt t,t,t搬运距离与搬运重量合成的特殊矩阵搬运距离与搬运重量合成的特殊矩阵 其方法是先将原来其方法是先将原来n n!个可行的布置组合，透过个可行的布置组合，透过此特殊矩阵放大为此特殊矩阵放大为t t!个解个解(包含了非可行解包含了非可行解)，在在t t!解中，先删去不可能成为最优解中一元的解中，先删去不可能成为最优解中一元的元素，同时亦删去元素，同时亦删去n n!个可行解中不可能成为最个可行解中不可能成为最优解的布置组合，并以划记的方法求得某部门优解的布置组合，并以划记的

33、方法求得某部门不可能放在那些位置，进而求得最佳或接近最不可能放在那些位置，进而求得最佳或接近最佳的布置组合出来。佳的布置组合出来。三、威门法的实例三、威门法的实例 某公司新建一厂房，经过规划之后，将整个厂房某公司新建一厂房，经过规划之后，将整个厂房划分成四个区域划分成四个区域(位置位置)，而且也将整个工厂的组织分，而且也将整个工厂的组织分成四个部门，各个位置成四个部门，各个位置(Location)Location)间的距离如距离表间的距离如距离表所示的距离矩阵所示的距离矩阵(D D矩阵矩阵)，而各个部门间的搬运量如搬，而各个部门间的搬运量如搬运量表所示的搬运量矩阵运量表所示的搬运量矩阵(P P

34、矩阵矩阵)。位置位置1 12 23 34 41 10 04242141422222 20 0303020203 30 010104 40 0距离矩阵距离矩阵距离矩阵距离矩阵(D D D D矩阵矩阵矩阵矩阵)D=D=部门部门A AB BC CD DA A0 0404070702020B B15150 030305050C C656550500 07070D D3030323260600 0搬运量矩阵搬运量矩阵搬运量矩阵搬运量矩阵(P P P P矩阵矩阵矩阵矩阵)P=P=三、威门法的实例三、威门法的实例 总搬运量矩阵：由于部门间的搬运与方向无关，总搬运量矩阵：由于部门间的搬运与方向无关，因而可将搬

35、运量表的搬运量矩阵中相关的部门间的因而可将搬运量表的搬运量矩阵中相关的部门间的搬运作一合并，得总搬运量表，该表无方向性搬运作一合并，得总搬运量表，该表无方向性(L L矩矩阵阵)。部门部门A AB BC CD DA A0 055551351355050B B0 095958282C C0 0130130D D0 0L=L=合成的特殊矩阵合成的特殊矩阵部门部门i到到j部门间的部门间的搬运量搬运量3-41-32-41-42-31-2位置位置101420223042距离距离A-C135 W1350 V1890 W2700 U2970 T3050 S5670C-D130130018202600 W286

36、0 U3900 T5460B-C95 95013301900 V2090 W2850 U3990B-D82 S 820 W1148 V1640 T1804 U2460 W3444A-B55 T 550 7701100 U1210 W1750 2310A-D50 U 500 7001000 W1100 V1500 2100东北角主对角线3次对角线2次对角线1次对角线A-CA-C在在1-31-3B-CB-C在在l-4l-4B-DB-D在在2-42-4A-DA-D在在2-32-3根据上列的分配可知，部门与位置根据上列的分配可知，部门与位置的最佳组合为：的最佳组合为：部门部门 位置位置 A A 在在

37、3 3 B B 在在 4 4 C C 在在 l l D D 在在 2 2四、威门法的实用评估四、威门法的实用评估 威门法对布置问题有极高的实用性，无需繁杂的威门法对布置问题有极高的实用性，无需繁杂的计算，仅以简单划记的方法，配合特殊的矩阵即可求计算，仅以简单划记的方法，配合特殊的矩阵即可求得最佳或接近最佳的布置方案，且其以运输作功为衡得最佳或接近最佳的布置方案，且其以运输作功为衡量的标准，具有代表意义，是符合实际的基准选择。量的标准，具有代表意义，是符合实际的基准选择。尤其适合大型布置极易以计算机来求解。尤其适合大型布置极易以计算机来求解。其其缺点缺点则由于划记的次序是依特殊矩阵的位置而则由于

38、划记的次序是依特殊矩阵的位置而非数值而定，因此其形成的布置组合为近似最佳解，非数值而定，因此其形成的布置组合为近似最佳解，并不一定是最佳解；其次，它的三个假设条件在实际并不一定是最佳解；其次，它的三个假设条件在实际运用上有时不完全符合实际情况，这也是这一方法的运用上有时不完全符合实际情况，这也是这一方法的缺点。缺点。6-66-6 动态规划法动态规划法(Dynamic Programming)Dynamic Programming)动态规划在决策上是一新的技术，它不动态规划在决策上是一新的技术，它不仅牵涉的变量多，又有多个约束条件，更须仅牵涉的变量多，又有多个约束条件，更须考虑到这一阶段的决策对

39、下一阶段状况的连考虑到这一阶段的决策对下一阶段状况的连带影响的决策技术。它与其它方法最大的不带影响的决策技术。它与其它方法最大的不同点是以往是一个问题有同点是以往是一个问题有n n个变量的处理方法。个变量的处理方法。而动态规划是处理而动态规划是处理n n个问题有个问题有n n个变量。个变量。一、动态规划的问题特性一、动态规划的问题特性动态规划方法是动态规划方法是Richard BellmanRichard Bellman在在19621962年提出的。年提出的。l动态规划问题可以划分成数个阶段动态规划问题可以划分成数个阶段(Stage)Stage)。所谓所谓阶段可以是指不同的时期，也可以是指连续

40、决策阶段可以是指不同的时期，也可以是指连续决策的不同步骤，必须根据问题的性质而作不同地划的不同步骤，必须根据问题的性质而作不同地划分。而且在每一个阶段均需做出决策，一旦决策分。而且在每一个阶段均需做出决策，一旦决策制订之后便限制了后面阶段的可行方案，因此，制订之后便限制了后面阶段的可行方案，因此，在做决策之前应作整体的考虑。在做决策之前应作整体的考虑。l每个阶段都存在数个不同的状态每个阶段都存在数个不同的状态(State)State)。l在任何一个状态的最佳决策与其以前所做的决策在任何一个状态的最佳决策与其以前所做的决策无关，是所谓的无记忆无关，是所谓的无记忆性性(MemorylessMemo

41、ryless)。基于这基于这一原理以及整体的考虑，动态规划问题的求解往一原理以及整体的考虑，动态规划问题的求解往往是采用倒推的方式来进行，也即由最后阶段开往是采用倒推的方式来进行，也即由最后阶段开始，逐步往前面的阶段推算。始，逐步往前面的阶段推算。二、动态规划问题的模型与求解二、动态规划问题的模型与求解 l状态函数状态函数 决策的间断程序是由有限个阶段决策的间断程序是由有限个阶段(Stage)Stage)n n所构所构成，且每一个阶段各有不同的状态成，且每一个阶段各有不同的状态(State)State)。第一第一个决策个决策q qn n是发生在程序的第是发生在程序的第n n个阶段，而其状态为个

42、阶段，而其状态为p pn n。而状态而状态p pi i是程序在状态是程序在状态p pi i+1+1，下决策下决策q qi i+1+1的结果，的结果，其函数关系式表示如下：其函数关系式表示如下：p pi i=T T(p pi i+1+1，q qi i+1+1)l报酬函数报酬函数 决策的程序需要有评估的基础，这种评估的基决策的程序需要有评估的基础，这种评估的基础称为础称为报酬函数报酬函数，如投资报酬率，利润，时间的节，如投资报酬率，利润，时间的节省，距离、资金及其它任何价值的衡量等。报酬函省，距离、资金及其它任何价值的衡量等。报酬函数是因变于一连串的状态和决策，表示如下：数是因变于一连串的状态和决

43、策，表示如下：R R(p p1 1，p p2 2，p pn n；q q1 1，q q2 2，q qn n)l我们的目标是要使报酬函数为最大或最小。我们的目标是要使报酬函数为最大或最小。总报酬来自于一连串的个别决策的报酬，分别为：总报酬来自于一连串的个别决策的报酬，分别为：总报酬来自于一连串的个别决策的报酬，分别为：总报酬来自于一连串的个别决策的报酬，分别为：g g g g1 1 1 1(p p p p1 1 1 1，q q q q1 1 1 1)，g g g g2 2 2 2(p p p p2 2 2 2，q q q q2 2 2 2)，g g g gn n n n(p p p pn n n

44、n，q q q qn n n n)基于个别决策是报酬函数的共同参数，且整体决策基于个别决策是报酬函数的共同参数，且整体决策基于个别决策是报酬函数的共同参数，且整体决策基于个别决策是报酬函数的共同参数，且整体决策的总数报酬是个别报酬的总和设，则的总数报酬是个别报酬的总和设，则的总数报酬是个别报酬的总和设，则的总数报酬是个别报酬的总和设，则 R R R R(p p p p1 1 1 1，p p p p2 2 2 2，p p p pn n n n；q q q q1 1 1 1，q q q q2 2 2 2，q q q qn n n n)=g g g g1 1 1 1(p p p p1 1 1 1，q

45、 q q q1 1 1 1)+)+)+)+g g g g2 2 2 2(p p p p2 2 2 2，q q q q2 2 2 2)+)+)+)+g g g gn n n n(p p p pn n n n，q q q qn n n n)二、动态规划问题的模型与求解二、动态规划问题的模型与求解二、动态规划问题的模型与求解二、动态规划问题的模型与求解l函数的方程式函数的方程式 上式为函数方程式的一般式。则决策上式为函数方程式的一般式。则决策q qn n的报酬为的报酬为g gn n(p pn n，q qn n)，此结果使得程序由此结果使得程序由p pn n改变至改变至p pn n-l-l，且仅且仅剩

46、剩(n n-1)-1)阶段。而剩余阶段。而剩余(n n-1)-1)个决策的报酬必同时为个决策的报酬必同时为状态状态p pn n-l-l的最大值。的最大值。二、动态规划问题的模型与求解二、动态规划问题的模型与求解l动态规划的求解动态规划的求解 动态规划的最佳性原则是不论最初的状态和动态规划的最佳性原则是不论最初的状态和决策如何，所谓最优解必是以第一个决策和状态决策如何，所谓最优解必是以第一个决策和状态的条件下，其余决策以最优化所求得的解。基于的条件下，其余决策以最优化所求得的解。基于最优性原则，由问题的最后阶段往前逐段运算至最优性原则，由问题的最后阶段往前逐段运算至开始阶段，以求出整体的最优解。

47、开始阶段，以求出整体的最优解。三、动态规划问题例三、动态规划问题例 假设运输问题的运输成本是由运输成本假设运输问题的运输成本是由运输成本(二次式二次式)和运输准备成本所构成。运输准备成本与运输数量无和运输准备成本所构成。运输准备成本与运输数量无关，但若不运送，则此成本不会发生。成本与需求列关，但若不运送，则此成本不会发生。成本与需求列在表中。每一个函数在表中。每一个函数g gijij(x x)，此此x x代表运送数量，成本代表运送数量，成本函数为：函数为：g gijij(x x)=)=A Aijijx x+B Bijijx x2 2+C Cijij(x x)C Cijij=运输准备成本。运输准

48、备成本。(若若x x=0=0，则则C Cijij=0)=0)A Aijij=从供应点从供应点i i运送一个单位到需求点运送一个单位到需求点j j的成本。的成本。B Bijij=从供应点从供应点i i运送一个单位到需求点运送一个单位到需求点j j的二次成本因的二次成本因素。素。供应点与需求点间成本值供应点与需求点间成本值 到需到需求点求点由供应点由供应点1 1由供应点由供应点2 2需求量需求量准备成本准备成本x xx x2 2准备成准备成本本x xx x2 21 12 23 34 45 56 67 78 89 910101 110108 81.01.02.02.03.03.01.51.52.52

49、.55.05.03.03.06.06.06.06.06.06.00.010.01-0.01-0.010.050.052 25 53.13.14.14.12.12.11.11.12.62.63.03.01.01.02.02.02.02.05.05.04 40.10.10.20.20.00.0l l10102525454515155 515152020151510102020由供应点由供应点1 1运送运送x x数量到需求点数量到需求点3 3的成本为的成本为 g g1313(x x)=3)=3x x+0.01+0.01x x2 2。供应点供应点2 2运送到需求点运送到需求点7 7的成本为的成本为 g

50、 g2727(x x)=5+)=5+x x+0.2+0.2x x2 2 当当x x0 0 g g2727(x x)=0 )=0 当当x x=0=0 运输问题应用动态调配的解运输问题应用动态调配的解 供应点供应点1 1运送运送100100单位，供应点单位，供应点2 2运送运送8080单位的最优解。单位的最优解。到需求点到需求点从供应点从供应点1 1从供应点从供应点2 2成本成本累计成本累计成本1 110100 0101010102 225250 0515161613 345450 0155.25155.25216.25216.254 415150 022.522.5238.75238.755 5