运筹学课件Ch8动态规划

第八章动态规划DynamicProgramming

8.1动态规划数学模型MathematicalModelofDP

8.2资源分配问题ResourceAssignmentProblem8.3生产与存储问题Productionandinventoryproblem8.4背包问题KnapsackProblem8.5其它动态规划模型

OtherModelofDP运筹学OperationsResearch1/12/20238.1动态规划数学模型MathematicalModelofDP1/12/2023v2v3v4v7v5v9v6v8v1028512131071013112865885405847【例8.1】最短路径问题图8－1表示从起点A到终点E之间各点的距离。求A到E的最短路径。图8－1v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段1217142019Min{2+5,8+8,6+4}=71/12/20232347596810285121310710131128658854图8－21第1阶段第2阶段第3阶段第4阶段阶段：第5阶段用WinQSB软件计算时,需要对状态重新编号,如下图所示.8.1动态规划数学模型MathematicalModelofDP

1/12/202312348576910285121310M10413111128658864用WinQSB软件计算时,当某状态没有路到下阶段某状态时，添加一条虚拟决策（线条），距离很大，如下图点3到点5.8.1动态规划数学模型MathematicalModelofDP

1/12/2023动态规划问题具有以下基本特征

1.问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。2.每一阶段都有相应的“状态”与之对应。3.每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。4.每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。8.1动态规划数学模型MathematicalModelofDP

1/12/20235.状态具有无后效性当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C2908.1动态规划数学模型MathematicalModelofDP

1/12/2023动态规划基本原理是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。基本原理一方面说明原问题的最优解中包含了子问题的最优解，另一方面给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。动态规划求解可分为三个步骤：分解、求解与合并。8.1动态规划数学模型MathematicalModelofDP

1/12/2023（1）阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数k可以是确定数、不定数或无限数8.1.2基本概念（3）决策（Decision）xk：从某一状态向下一状态过度时所做的选择。决策变量记为xk，xk是所在状态sk的函数。在状态sk下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。（2）状态（State）：描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为sk。各阶段所有状态组成的集合称为状态集。8.1动态规划数学模型MathematicalModelofDP

1/12/2023(4)策略(Strategy)：从第1阶段开始到最后阶段全过程的决策构成的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。（5）状态转移方程(Statetransformationfunction)：某一状态以及该状态下的决策，与下一状态之间的函数关系，记为sk+1=T(sk,xk)（6）指标函数或收益函数(Returnfunction)：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为k阶段指标函数、k子过程指标函数及最优指标函数。8.1动态规划数学模型MathematicalModelofDP

1/12/2023k阶段指标函数

从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为vk(sk,xk)。从k阶段状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,…,xn)或Vk，n为阶段数。过程指标函数最优指标函数从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。（Opt＝optimization表示“max”或“min”

8.1动态规划数学模型MathematicalModelofDP

1/12/2023动态规划要求过程指标满足递推关系

，即(8.2)连和形式：(8.3)最优指标函数是(8.4)8.1动态规划数学模型MathematicalModelofDP

1/12/2023动态规划数学模型由式(8.4)或(8.6)、边界条件及状态转移方程构成。如连和形式的数学模型连乘形式(vj≠0)：(8.5)最优指标函数是(8.6)8.1动态规划数学模型MathematicalModelofDP

1/12/2023对于可加性指标函数，上式可以写为上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为上式称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(sn)的值。8.1动态规划数学模型MathematicalModelofDP

1/12/2023用逆序法列表求解例8.1k=n=5时，f5(v10)＝0k=4，递推方程为

s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策x4*v7v7v10v1055+0=5*5v7v10v8v8v10v1088+0＝8*8v8→v10v9v9v10v1044+0=4*4v9v108.1动态规划数学模型MathematicalModelofDP

1/12/2023k=3，递推方程为表8-2s3D3(s3)s4v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)最优决策x3*v5v5v7v5v8v5v9v7v8v92862+5=7*8+8=166+4=107v5v7v6v6v7v6v8v6v9v7v8v9125812+5=175+8=138+4=12*12v6v98.1动态规划数学模型MathematicalModelofDP

1/12/2023k=2，递推方程为表8-3s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策x2*v2v2v5v2v6v5v6101310+7=17*13+12=2517v2v5v3v3v5v3v6v5v67107+7=14*10+12=2214v3v5v4v4v5v4v6v5v6131113+7=20*11+12=2320v4v58.1动态规划数学模型MathematicalModelofDP

1/12/2023k=1，递推方程为表8-4s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策x1*v1v1v2v1v3v1v4v2v3v42852+17=19*8+14=225+20=2519v1v2最优值是表8-4中f1(s1)的值，从v1到v10的最短路长为19。最短路线从表8-4到表8-1回朔，查看最后一列最优决策，得到最短路径为：v1

v2

v5

v7v108.1动态规划数学模型MathematicalModelofDP

1/12/2023作业：教材P188T2下一节：资源分配问题8.1动态规划数学模型MathematicalModelofDP

1/12/20238.2资源分配问题ResourceAssignmentProblem1/12/2023【例8.2】公司有资金8万元，投资A、B、C三个项目，一个单位投资为2万元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C的投资效益(万元)和投入资金（万元）的关系见表8-5。求对三个项目的最优投资分配，使总投资效益最大。

8.2资源分配问题ResourceAssignmentProblem项目投入资金ABC2万元89104万元1520286万元3035358万元384043表8-5【解】设xk为第k个项目的投资，该问题的静态规划模型为1/12/2023阶段k：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设的阶段状态变量sk：投资第k个项目前的资金数决策变量xk：第k个项目的投资额决策允许集合：0≤xk≤sk状态转移方程：sk+1=sk－xk阶段指标：vk(sk，xk)见表8-5中的数据递推方程：

终端条件：f4(s4)=0数学模型为

8.2资源分配问题ResourceAssignmentProblem1/12/2023k=4，终端条件f4(s4)=0。k=3，0≤x3≤s3，s4=s3－x3

状态s3决策x3(s3)状态转移方程s4=s3－x3阶段指标v3(s3,x3)过程指标v3(s3,x3)+f4(s4)最优指标f3(s3)最优决策x3*00000+0=00020200+0=0102201010+0=10*40400+0=0284221010+0=10402828+0=28*60600+0=0356241010+0=10422828+0=28603535+0=35*80800+0=0438261010+0=10442828+0=28623535+0=35804343+0=43*8.2资源分配问题ResourceAssignmentProblem1/12/2023s2x2(s2)s3v2(s2,x2)f3(s3)v2(s2,x2)+f3(s3)f2(s2)x2*000000+0=0002020100+10=10*10020909+0=94040280+28=28*280229109+10=194020020+0=206060350+35=35372249289+28=37*42201020+10=306035035+0=358080430+43=43484269359+35=4444202820+28=48*62351035+10=458040040+0=40k=2，0≤x2≤s2，s3=s2－x2

8.2资源分配问题ResourceAssignmentProblem1/12/2023k=1，0≤x1≤s1，s2=s1－x1

s1x1(s1)s2v1(s1,x1)f2(s2)v1(s1,x1)+f2(s2)f1(s1)x1*8080480+48=48*480268378+37=4544152815+28=4362301030+10=408038038+0=38最优解为:s1=8,x1*=0,s2=s1－x1=8,x2*=4,s3=s2－x2*=4,x3=4,s4=s3－x3=0。投资的最优策略是，项目A不投资，项目B投资4万元，项目C投资4万元，最大效益为48万元

8.2资源分配问题ResourceAssignmentProblem1/12/2023【例8.3】某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为x,产量为g=10x，设备年完好率为a=0.75；在低负荷下投入生产的设备数量为y，产量为h=8y，年完好率为b=0.9。假定开始生产时完好的设备数量s1=100。制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。

阶段k：运行年份（k=1,2,3,4,5,6），k=1表示第一年初，k=6表示第五年末（即第六年初）；状态变量sk：第k年初完好的机器数（k=1,2,3,4,5,6），也是第k－1年末完好的机器数，其中s6表示第五年末（即第六年初）的完好机器数，s1＝100。决策变量xk：第k年初投入高负荷运行的机器数；状态转移方程：sk+1=0.75xk+0.9(sk－xk)8.2资源分配问题ResourceAssignmentProblem1/12/2023决策允许集合：Dk(sk)={xk|0xksk}阶段指标：vk(sk，xk)=10xk+8(sk－xk)终端条件：f6(s6)=0递推方程：8.2资源分配问题ResourceAssignmentProblem1/12/20238.2资源分配问题ResourceAssignmentProblem1/12/20238.2资源分配问题ResourceAssignmentProblem1/12/2023因为s1=100，五年的最大总产量为f1(s1)=25.7525×100＝3443.75。由x1*=x2*=x3*=0，x4*＝s4，x5*＝s5，设备的最优分配策略是，第一年至第三年将设备全部用于低负荷运行，第四年和第五年将设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每年初完好的机器数为：s1=100x1*=0, s2=0.75x1+0.9(s1－x1)=90x2*=0, s3=0.75x2+0.9(s2－x2)=81x3*=0，s4=0.75x3+0.9(s3－x3)=73x4*=s4=73，s5=0.75x4+0.9(s4－x4)=55x5*=s5=55，s6=0.75x5+0.9(s5－x5)=41第五年末还有41台完好设备。8.2资源分配问题ResourceAssignmentProblem1/12/2023一般地，设一个周期为n年，高负荷生产时设备的完好率为a，单台产量为g；低负荷完好率为b，单台产量为h。若有t满足则最优设备分配策略是：从1～t－1年，年初将全部完好设备投入低负荷运行，从t～n年，年初将全部完好设备投入高负荷运行，总产量达到最大.在例8.3中，n=5，a=0.75，b=0.9，g=10，h=8，(g-h)/g(b-a)=1.3333式(8.7)的求和式是完好率a的i次方累加.由a0=1＜1.3333＜a0+a1＝1.75知，n－t－1＝0，t=4，则1~3年低负荷运行，4~5年为高负荷运行8.2资源分配问题ResourceAssignmentProblem(8.7)1/12/2023作业：教材P188T1，6，8，98.2资源分配问题ResourceAssignmentProblem下一节：生产与存储问题1/12/20238.3生产与存储问题Productionandinventoryproblem1/12/20238.3生产与存储问题Productionandinventoryproblem【8.4】一个工厂生产某种产品，1～6月份生产成本和产品需求量的变化情况见表8-9月份(k)123456需求量(dk)203035402545单位产品成本(ck)151216191816表8-9没有生产准备成本，单位产品一个月的存储费为hk＝0.6元，月底交货。分别求下列两种情形6个月总成本最小的生产方案。（1）1月初与6月底存储量为零，不允许缺货，仓库容量为S=50件，生产能力无限制；（2）其它条件不变，1月初存量为101/12/20238.3生产与存储问题Productionandinventoryproblem【解】动态规划求解过程如下。阶段k：月份，k=1,2,…,7状态变量sk：第k个月初的库存量决策变量xk：第k个月的生产量状态转移方程：sk+1=sk+xk－dk

决策允许集合:阶段指标：终端条件：f7(s7)=0,s7=0递推方程：1/12/20238.3生产与存储问题Productionandinventoryproblem当k=6时，因为s7=0，有当k=5时，由于s5≤50，则当25－s5＜0时x5的值取“0”，决策允许集合为1/12/20238.3生产与存储问题Productionandinventoryproblemk=4时，决策允许集合为1/12/20238.3生产与存储问题Productionandinventoryproblem显然该决策不可行,x5=0，s4+x4=65＝d4+d5，s5=s4+x4－d4=25，x6=45，与s5>25矛盾。因此有k=3，当0≤s4≤40时，1/12/20238.3生产与存储问题Productionandinventoryproblem当40≤s4≤50时，当k=2时，由x2的决策允许集合为1/12/20238.3生产与存储问题Productionandinventoryproblem当k=1时，由只要期初存量s1≤20，则x1的决策允许集合为(1)期初存储量s1=0，由各阶段的最优决策xj*及状态转移方程，回朔可求出最优策略。1/12/20238.3生产与存储问题Productionandinventoryproblemx1=20，s2=s1+x1－d1=0+20－20＝0，x2=80，s3=s2+x2－d2=0+80－30＝50，x3=85－50＝35，s4=s3+x3－d3=50+35－35＝50＞40，x4＝0，s5=50－0－40＝10＜25，x5＝25－s5＝15，s6=10＋15－25＝0，x6＝45。

总成本为2876(2)期初存储量s1=10，与前面计算类似，得到x1＝10，x2＝80，x3＝35，x4＝0，x5＝15，x6＝45。1～6月份生产、存储详细计划表见表8-10所示。1/12/20238.3生产与存储问题Productionandinventoryproblem表8-10月份(k)123456合计需求量(dk)203035402545195单位产品成本(ck)151216191816单位存储费hk0.60.60.60.60.60.6产量xk20803501545195期初存量sk005050100110生产成本CK(xk)30096056002707202810存储成本Hk(sk)0030306066合计28761/12/20238.3生产与存储问题Productionandinventoryproblem1/12/20238.3生产与存储问题Productionandinventoryproblem作业：教材P189T7下一节：背包问题1/12/20238.4背包问题KnapsackProblem1/12/20238.4背包问题KnapsackProblem背包问题数学模型为式中：ck为第k种物品的单位价值，wk是第k种物品的单位重量或体积，W是背包的重量或体积限制。动态规划的有关要素如下。阶段k：第k次装载第k种物品（k=1,2,…,n）状态变量sk：第k次装载时背包还可以装载的重量(或体积)决策变量xk：第k次装载第k种物品的件数决策允许集合：Dk(sk)={dk|0

xksk/wk，xk为整数}状态转移方程：sk+1=sk－wkxk阶段指标：vk=ckxk1/12/20238.4背包问题KnapsackProblem递推方程：终端条件：fn＋1(sn＋1)=0【例8.5】用动态规划方法求解下列整数规划【解】终端条件：f4(x4)=0k=3时，递推方程1/12/20238.4背包问题KnapsackProblem表8-11s3D3(s3)={x3|[s3/5]}s460x3+f4(s4)f3(s3)x3*0000+0=0001010+0=000………………………0501500+0=060+0=60*0601………………………11001210500+0=6060+0=60120+0=120*1202最优决策是；s3为0～4时，x3＝0，s3为5～9时，x3＝1，s3＝10时，x3＝2。k=2时，递推方程1/12/20238.4背包问题KnapsackProblem表8-12

s2D2(s2)s340x2+f3(s3)f2(s2)x2*0000+f3(0)=0+0=0*001010+0＝000201200+0=040+0=40*401301310+0=040+0=40*40140124200+0=040+0=4080+0=8080250125310+60=6040+0=4080+0=80*802………………………1001234510864200+120=12040+60=10080+60=140120+0=120160+0=160200+0=200*20051/12/2023第2阶段的最优决策见表8-13表8-13s2012345678910f2(s2)0040408080120120160160200x200112233445k=1时，递推方程8.4背包问题KnapsackProblem1/12/2023s1＝10，w1=3，D1(s1)={0，1，2，3}，计算结果见表8-14表8-14s1D1(s1)s260x1+f2(s2)f1(s1)x1*100123107410+f2(10)=0+200=200*60+120=180120+80=200*180+0=1802000,2由表8-14、8-13、8-11，得到两个最优解：X1＝（0，5，0），X2＝（2，2，0），最优值Z＝200。8.4背包问题KnapsackProblem1/12/2023作业：教材P189T58.4背包问题KnapsackProblem下一节：其它动态规划模型1/12/20238.5其它动态规划模型

OtherModelofDP1/12/20238.5其它动态规划模型

OtherModelofDP8.5.1求解线性规划模型【例8.6】用动态规划方法求解下列线性规划【解】首先将问题转化为动态规划模型阶段数为3，决策变量为xk，状态变量为第k阶段初各约束条件右端常数的剩余值，用s1k和s2k表示，状态转移方程为s1,k+1=s1