应用运筹学-6

1、动态规划动态规划动态规划动态规划是解决多阶段决策过程最优化的数学方法是解决多阶段决策过程最优化的数学方法动态规划概述动态规划概述产生于上世纪产生于上世纪50年代，由年代，由R. Bellman 等人提出等人提出基本思想基本思想： 把多阶段决策问题变换为一系列互相联系的单阶段问题，然把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决；后逐个加以解决；“最优性原理最优性原理”动态规划动态规划的方法，在工程技术、企业管理、工农业生的方法，在工程技术、企业管理、工农业生产及军事等部门有着广泛的应用，并获得了显著的效产及军事等部门有着广泛的应用，并获得了显著的效果。在企业管理方面：果。在

2、企业管理方面：最优路径问题最优路径问题资源分配问题资源分配问题生产调度问题生产调度问题库存问题库存问题装载问题装载问题排序问题排序问题设备更新和生产过程最优控制等设备更新和生产过程最优控制等动态规划的基本方法动态规划的基本方法多阶段决策过程及实例多阶段决策过程及实例动态规划的基本概念和基本方程动态规划的基本概念和基本方程动态规划的最优性原理动态规划的最优性原理动态规划和静态规划的关系动态规划和静态规划的关系多阶段决策过程：多阶段决策过程：在生产和科学实验中，有一类活动过程，可将其分为若干个在生产和科学实验中，有一类活动过程，可将其分为若干个互相联系的阶段，在其每一个阶段都需要作出决策，从而使互

3、相联系的阶段，在其每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果；整个过程达到最好的活动效果；各阶段决策的选取不是任意确定的，它依赖于当前面临的状各阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展；态，又影响以后的发展；当各阶段决策确定后，就组成了一个决策序列，因而也就决当各阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动线路；定了整个过程的一条活动线路；这种把一个问题看作是一个前后关联具有链状结构的多阶段这种把一个问题看作是一个前后关联具有链状结构的多阶段过程，称为多阶段决策过程。过程，称为多阶段决策过程。一、多阶段决策过程及实例一、多

4、阶段决策过程及实例1状态状态决策决策2状态状态决策决策状态状态n状态状态决策决策状态状态最短路线问题最短路线问题多阶段决策问题的实例多阶段决策问题的实例2511214106104131112396581052C1C3D1AB1B3B2D2EC2求从求从A到到E的最短路径的最短路径机器负荷分配问题机器负荷分配问题某种机器可以在高低两种不同负荷下进行生产。某种机器可以在高低两种不同负荷下进行生产。在高负荷下进行生产时，产品的年产量在高负荷下进行生产时，产品的年产量g和投入生产的机器和投入生产的机器数量数量u1的关系为的关系为g=g(u1)这时，机器的年完好率为这时，机器的年完好率为a(0a1)在低

5、负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产的机器数量和投入生产的机器数量u2的关系为的关系为h=h(u2)相应的机器完好率为相应的机器完好率为b(0ab1)假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1，要求制定一个，要求制定一个五年计划，在每年开始时，决定如何重新分配完好的五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。品的总产量达到最高。多阶段决策问题的实例多阶段决策问题的实例( (续续) )阶段阶段把所给问题的过程，恰当地分为若干个相互

6、把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序求解。联系的阶段，以便能按一定的次序求解。阶段变量阶段变量k状态状态每个阶段开始所处的自然状况或客观条件，每个阶段开始所处的自然状况或客观条件，它描述了研究问题的状况，又称不可控因素。一般指它描述了研究问题的状况，又称不可控因素。一般指某阶段的出发位置；事实上，它既是该阶段某支路的某阶段的出发位置；事实上，它既是该阶段某支路的起点，又是前一阶段某支路的终点。起点，又是前一阶段某支路的终点。Sk 第第k阶段的状态变量，阶段的状态变量，可达状态集合可达状态集合无后效性无后效性(马尔科夫性马尔科夫性)如果某阶段状态给定后，则在这个阶

7、如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响。段以后过程的发展不受这个阶段以前各段状态的影响。决策决策当过程处于某一阶段的某个状态时，可作出当过程处于某一阶段的某个状态时，可作出不同的决定，从而确定下一阶段的状态。或称为控制。不同的决定，从而确定下一阶段的状态。或称为控制。决策变量决策变量uk(sk) 第第k阶段当状态处于阶段当状态处于sk时的决策变量时的决策变量允许决策集合允许决策集合Dk(sk) 第第k阶段从状态阶段从状态sk出发的允许决策集合出发的允许决策集合uk(sk) Dk(sk) ， 或或uk(sk)是一多值函数是一多值函数 2.1动态规划的基本概

8、念动态规划的基本概念策略策略一个按顺序排列的决策组成的一个按顺序排列的决策组成的集合。集合。k子过程子过程由过程的第由过程的第k阶段开始到终止状态阶段开始到终止状态为止的过程。为止的过程。k子过程策略子过程策略pk,n(sk)由由k子过程每段的决策子过程每段的决策按顺序排列组成的决策函数序列按顺序排列组成的决策函数序列uk(sk), un(sn)，即，即pk,n(sk)= uk(sk), un(sn)允许策略集合允许策略集合P最优策略最优策略策略策略状态移动方程状态移动方程确定过程由一个状态确定过程由一个状态到另一个状态的演变过程。到另一个状态的演变过程。若给定若给定第第k阶段状态变量阶段状态

9、变量sk值，如果该阶段值，如果该阶段的决策变量的决策变量uk一经确定，第一经确定，第k+1阶段状态变阶段状态变量量sk+1的值也完全确定的值也完全确定sk+1 = Tk(sk , uk)状态转移方程状态转移方程指标函数指标函数用来衡量所实现过程优劣的一种数值指用来衡量所实现过程优劣的一种数值指标。它是定义在全过程和所有后部子过程上确定的数标。它是定义在全过程和所有后部子过程上确定的数量函数。用量函数。用Vk,n表示表示Vk,n= Vk,n(sk , uk , sk+1, sn+1)k=1,2,n.Vk,n应具有可分离性，并满足递推关系，即应具有可分离性，并满足递推关系，即 Vk,n(sk ,

10、uk , sk+1, sn+1)= k (sk , uk , Vk+1,n (sk+1, sn+1)常见的指标形式常见的指标形式最优值函数，最优值函数，fk(sk)指标函数与最优值函数指标函数与最优值函数 nkjjjjnkkkknkusvsususV,111, nkkkknkVusvV,1, nkjjjjnkkkknkusvsususV,111, nkkkknkVusvV,1, 111,1 nkkkknkuuukksususVoptsfnkk最短路线的一个特征最短路线的一个特征如果由起点如果由起点A经过经过P点和点和H点而到达终点点而到达终点G是一条最短路线，则是一条最短路线，则由点由点P出发

11、经过出发经过H点到达终点点到达终点G的这条子路线，对于从点的这条子路线，对于从点P出发出发到达终点到达终点G的所有可能选择的不同路线来说，必定也是最短路的所有可能选择的不同路线来说，必定也是最短路线。线。2.2动态规划的基本思想和基本方程动态规划的基本思想和基本方程2511214106104131112396581052C1C3D1AB1B3B2D2EC2AB2 C1 D1 E寻找最短路线的方法寻找最短路线的方法从最后一段开始，由后向前逐步递推，求出各点到终点的最短从最后一段开始，由后向前逐步递推，求出各点到终点的最短路线，最后求得由起点到终点的最短路线。路线，最后求得由起点到终点的最短路线。

12、上例的求解上例的求解寻找最短路线寻找最短路线最短路线：最短路线：AB2 C1 D1 E 2,542414 DfDfk时，当 12,782953min22,111,1min33323434313 CfCfDfDCdDfDCdCfk时，当 19,14201210714812min33,122,111,1min2322232323212 BfBfCfCBdCfCBdCfCBdBfk时，当 19191145202min33,22,11,min12121211 BfBAdBfBAdBfBAdAfk时，当将多阶段决策过程划分阶段，恰当地选取状态变量、将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及

13、定义最优指标函数，从而把问题化成一族决策变量及定义最优指标函数，从而把问题化成一族同类问题的子问题，然后逐个求解；同类问题的子问题，然后逐个求解；求解时从边界条件开始，逆求解时从边界条件开始，逆(或顺或顺)过程行进方向，逐过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前段递推寻优。在每一个子问题求解时，都要使用它前面已得出的最优结果，最后一个子问题的最优解，就面已得出的最优结果，最后一个子问题的最优解，就是整个问题的最优解。是整个问题的最优解。动态规划方法是既把当前一段与未来各段分开，又把动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法

14、，当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。最优选择一般是不同的。动态规划方法的基本思想动态规划方法的基本思想动态规划的基本方程是递推逐段求解的根据，其一般动态规划的基本方程是递推逐段求解的根据，其一般形式为形式为指标函数为阶段指标和形式，即指标函数为阶段指标和形式，即动态规划的基本方程动态规划的基本方程 01 ,1,1111nnkkkkksDukksfnnksfusvoptsfkkk则基本方程为则基本方程为 nkjjjjnkusvV,指标函数为阶段指标积形式，即指标函数为阶

15、段指标积形式，即 nkjjjjnkusvV, 11 ,1,1111nnkkkkksDukksfnnksfusvoptsfkkk则基本方程为则基本方程为逆序解法逆序解法(后向动态规划方法后向动态规划方法)寻优的方向与多阶段决策过程的实际行进方向相反，从最寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略。后一段开始计算逐段前推，求得全过程的最优策略。顺序解法顺序解法(前向动态规划方法前向动态规划方法)寻优的方向与多阶段决策过程的实际行进方向相同，计算寻优的方向与多阶段决策过程的实际行进方向相同，计算时从第一段开始逐段向后递推，计算后一段要用到前一段时从

16、第一段开始逐段向后递推，计算后一段要用到前一段的求优结果，最后一段的计算结果就是全过程的最优结果。的求优结果，最后一段的计算结果就是全过程的最优结果。逆序解法和顺序解法逆序解法和顺序解法q动态规划的最优性原理动态规划的最优性原理q作为整个过程的最优策略具有这样的性质：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面的无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必决策所形成的状态而言，余下的诸决策必须构成最优策略。须构成最优策略。q一个最优策略的子策略总是最优的。一个最优策略的子策略总是最优的。q一点说明一点说明q最优性原理不是对任何决策过程都普遍成

17、最优性原理不是对任何决策过程都普遍成立的。立的。3.1最优性原理最优性原理动态规划应用举例动态规划应用举例资源分配问题资源分配问题背包问题背包问题排序问题排序问题货郎担问题货郎担问题一、一、资源分配问题资源分配问题所谓分配问题，就是将数量一定的一种或若干种资源，所谓分配问题，就是将数量一定的一种或若干种资源，恰当地分配给若干个使用者，而使目标函数为最优。恰当地分配给若干个使用者，而使目标函数为最优。问题：设有某种原料，总数量为问题：设有某种原料，总数量为a，用于生产，用于生产n种产品。若分种产品。若分配数量配数量 xi 用于生产第用于生产第i种产品，其收益为种产品，其收益为 gi(xi) 。问

18、应如何分。问应如何分配，才能使生产配，才能使生产n种产品的总收入最大？种产品的总收入最大？ nixaaxxgziniiniii, , ,2 2, ,1 10 00 0m ma ax x1 11 1非线性规划模型非线性规划模型动态规划模型：动态规划模型：设状态变量设状态变量sk用于生产第用于生产第k种产品至第种产品至第n种产品的原材料数量种产品的原材料数量决策变量决策变量uk用于生产第用于生产第k种产品的原材料数量，种产品的原材料数量， uk = xk nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkkmax)(1,.,1,)(max10资源分配问题资源分配问题举例举例某种机器可以

19、在高低两种不同负荷下进行生产。在高负荷下生产某种机器可以在高低两种不同负荷下进行生产。在高负荷下生产的产量函数为的产量函数为g=8u1，其中，其中u1为投入生产的机器数量，年完好率为投入生产的机器数量，年完好率为为a=0.7。在低负荷下生产的产量函数。在低负荷下生产的产量函数h =5u2 ，其中，其中u2为投入生为投入生产的机器数量，年完好率为产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1 =1000台，试问每年如何安台，试问每年如何安排机器在高低负荷下的生产，使在五年内产品的总产量达到最高。排机器在高低负荷下的生产，使在五年内产品的总产量

20、达到最高。构建动态规划模型：构建动态规划模型：设阶段序数设阶段序数k表示年度表示年度状态变量状态变量sk第第k年度初拥有的完好机器数量年度初拥有的完好机器数量决策变量决策变量uk第第k年度中分配高负荷下生产的机器数量，年度中分配高负荷下生产的机器数量， sk uk 为为k为该年度中分配低负荷下生产的机器数量；为该年度中分配低负荷下生产的机器数量；状态转移方程为状态转移方程为sk+1 = 0.7uk +0.9(sk-uk ) k=1,2,5指标函数指标函数 515,1,kkkkusvV 5 55 55 55 55 51 10 05 58 8m ma ax x) )( (1 1, ,. . . .

21、, ,4 4, ,9 9. .0 07 7. .0 05 58 8m ma ax x5 55 5ususfkusufususfsukkkkkkksukkkk其中其中vk=8uk+5(sk-uk)二维资源分配问题二维资源分配问题设有两种原料，数量各为设有两种原料，数量各为a和和b，需要分配用于生产，需要分配用于生产n种产品。若种产品。若第一种原材料以数量第一种原材料以数量 xi 为单位，第二种原材料以数量为单位，第二种原材料以数量 yi 为单位，为单位，用于生产第用于生产第i种产品，其收益为种产品，其收益为 gi(xi ,yi) 。问应如何分配这两种原。问应如何分配这两种原料，才能使生产料，才能

22、使生产n种产品的总收入最大？种产品的总收入最大？ 。 且且为为整整数数, ,. . . ., ,2 2, ,1 10 0, ,0 0, ,m ma ax x1 11 11 1niyxbyaxyxgziiniiniiniiii非线性规划模型非线性规划模型二维资源分配问题的动态规划模型二维资源分配问题的动态规划模型设状态变量设状态变量 : 表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n种产品的第一种原材料的单位种产品的第一种原材料的单位数量数量 表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n种产品的第二种原材料的单位种产品的第二种原材料的单位数量数量决策变量决策变量(x

23、k,yk):xk 表示分配用于生产第表示分配用于生产第k种产品的第一种原材料的单位数量种产品的第一种原材料的单位数量yk 表示分配用于生产第表示分配用于生产第k种产品的第二种原材料的单位数量种产品的第二种原材料的单位数量状态转换关系：状态转换关系： kykykkxkxkyssxss 11 1,.,1,max,max,1100nkysxsfyxgssfssgssfkykkxkkkkksysxykxkkynxnnynxnnykkxkk ykxkss, xks yks逆推关系：逆推关系：二、背包问题二、背包问题有一个人带一个背包上山，其可携带物品重量的限度有一个人带一个背包上山，其可携带物品重量的限

24、度为为a公斤。设有公斤。设有n种物品可供他选择装入背包中，这种物品可供他选择装入背包中，这n种物品的编号为种物品的编号为1,2,n。已知第。已知第i种物品每件种物品每件 wi 公斤，公斤，在上山过程中的作用在上山过程中的作用(价值价值)是携带数量是携带数量 xi 的函数的函数 ci(xi) 。问此人应如何选择携带的物品问此人应如何选择携带的物品(各几件各几件)，使所起作用，使所起作用(总价值总价值)最大？最大？设设xi第第i种物品的装入件数，则该问题的数学模型为种物品的装入件数，则该问题的数学模型为 nixaxwtsxcfiniiiniii,.,2, 10.max11且为整数背包问题的动态规划

25、求解背包问题的动态规划求解设按可装入物品的设按可装入物品的n种划分为种划分为n个阶段；个阶段；状态变量状态变量 sk 表示所装的第表示所装的第1种物品至第种物品至第k种物品的总重种物品的总重量；量；决策变量决策变量 xk 表示装入第表示装入第k种物品的件数，则状态转移种物品的件数，则状态转移方程为方程为 sk-1 =sk xkwk动态规划的顺序递推关系为动态规划的顺序递推关系为 nkxwsfxcsfxcsfkkkkkkwsxkkwsxkkk 2,maxmax1/,.,1,011/,.,1,011111背包问题举例背包问题举例有一辆最大货运量为有一辆最大货运量为10t的卡车，用以装载三种货物，的

26、卡车，用以装载三种货物，每种货物的单位重量及相应单价如下表。问应如何装每种货物的单位重量及相应单价如下表。问应如何装载可使总价值最大？载可使总价值最大？设设xi第第i种物品的装入件数，则该问题的数学模型为种物品的装入件数，则该问题的数学模型为 3,2, 1010543.654max321321ixxxxtsxxxzi且为整数动态规划求解动态规划求解当k=1时，当当k=2时，时， 3/44max113011111sxsfxsx 为整数 2212402245max222xsfxsfxsx 为整数动态规划求解动态规划求解(续续)当k=3时， 13012,56,13max012,56,10max510

27、6max102223232,1,033 fffxfxfx0, 1, 2*3*2*1 xxx最优策略：三、排序问题三、排序问题设有设有n个工件需要在机床个工件需要在机床A,B上加工，每个工件都必须上加工，每个工件都必须经过先经过先A而后而后B的两道加工工序。以的两道加工工序。以ai、bi分别表示工分别表示工件件i(1 i n)在在A,B上的加工时间。问应如何在两机床上上的加工时间。问应如何在两机床上安排各工件加工的顺序，使在机床安排各工件加工的顺序，使在机床A上加工第一工件上加工第一工件开始到在机床开始到在机床B上将最后一个工件加工完为止，所用上将最后一个工件加工完为止，所用的加工时间最少？的加

28、工时间最少？结论：结论：最优排序方案只能在机床最优排序方案只能在机床A,B上加工顺序相同上加工顺序相同的排序中寻找。的排序中寻找。当加工顺序确定后，工件在当加工顺序确定后，工件在A上加工时没有等待时间，而在上加工时没有等待时间，而在B上常常需要等待。上常常需要等待。寻求最优排序方案：尽量减少寻求最优排序方案：尽量减少B上的等待时间，这样才能使总上的等待时间，这样才能使总加工时间最短。加工时间最短。最优排序规则最优排序规则作工件的加工时间的工时矩阵作工件的加工时间的工时矩阵 nnbbbaaaM2121在工时矩阵在工时矩阵M中找出最小元素中找出最小元素(若最小的不止一个，可若最小的不止一个，可任选

29、其一任选其一)；若它在上行，则将相应的工件排在最前；若它在上行，则将相应的工件排在最前位置；若它在下行，则将相应的工件排在最后位置；位置；若它在下行，则将相应的工件排在最后位置；将排定位置的工件所对应的列从将排定位置的工件所对应的列从M中划掉，然后对余中划掉，然后对余下的工件重复按下的工件重复按2)进行。但此时的最前位置进行。但此时的最前位置(或最后位或最后位置置)是在已排定的工件之后是在已排定的工件之后(或之前或之前)。如此继续，直至。如此继续，直至把所有工件都排完为止。把所有工件都排完为止。排序问题举例排序问题举例设有设有5个工件需要在机床个工件需要在机床A,B上加工，工件的加工顺上加工，

30、工件的加工顺序是先序是先A后后B。每个工件所需加工时间如下表。问如。每个工件所需加工时间如下表。问如何安排加工的顺序，使机床连续加工完所有工件的何安排加工的顺序，使机床连续加工完所有工件的加工总时间最少？并计算最少加工时间。加工总时间最少？并计算最少加工时间。475354743272631BA加工时间加工时间机机床床工件号码工件号码排序问题求解排序问题求解工件的加工时间的工时矩阵工件的加工时间的工时矩阵 4372675473M25143工件加工顺序：工件加工顺序：13 5 4 2总加工时间：总加工时间：28小时小时四、货郎担问题四、货郎担问题有一个串村走户的的卖货郎，他从某个村庄出发，通有一个

31、串村走户的的卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问应如何选择行走路线，能使总的行程最短。庄，问应如何选择行走路线，能使总的行程最短。设有设有n个城市，以个城市，以1、2、n表示之。表示之。dij 表示从表示从i城城到到j城的距离。一个推销员从城市城的距离。一个推销员从城市1出发到其他每个城出发到其他每个城市去一次且仅仅一次，然后回到城市市去一次且仅仅一次，然后回到城市1。问他如何选择。问他如何选择行走路线，使总的行程最短？行走路线，使总的行程最短？规定推销员从城市规定推销员从城市1出发，设推销员走到出发，设推销员走到i城，记城，记Ni=2,3,i-1,i+1,n表示由表示由1城到城到i城的中间城市集合。城的中间城市集合。S表示到达表示到达i城之前中途所经过的城市的集合，则有城之前中途所经过的城市的集合，则有S Ni货郎担