运筹学课件动态规划

运筹学课件动态规划2511214106104131112396581052C1C3D1AB1B3B2D2EC2最短路径问题求从A到E的最短路径从起点A到终点E要经过A、B、C、D、E五站，每一站可以在不同的备选地点停留。每一站的备选地点，每个地点和下一站的各备选地点之间的距离如下图。第2页,共43页，2024年2月25日，星期天动态规划用一种全新的思路来考虑这样的问题。首先，把一个复杂的问题归结为若干个与原问题性质完全相同，但规模较小的子问题，每一个子问题又可以递归地归结为性质相同，规模更小的下层子问题。如此不断进行，一直到子问题非常简单，可以解决为止。然后，从这些最简单的子问题出发，依次计算上一层子问题的最优解，直到求出原问题的最优解。以最短路径问题为例，来说明动态规划的基本思想。第3页,共43页，2024年2月25日，星期天从A到E的最短路径S(A)，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径，记为S(B1),S(B2),S(B3)。121410B1131112B36104B2396581052C1C3D1D2EC2251A第4页,共43页，2024年2月25日，星期天A2121410B11131112B356104B2396581052C1C3D1D2EC2第5页,共43页，2024年2月25日，星期天121410B1131112B36104B2396581052C1C3D1D2EC2同样，计算S(B1)、S(B2)、S(B3)又可以归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题S(Ci)(i=1,2,3)。第6页,共43页，2024年2月25日，星期天121410B1396581052C1C3D1D2EC2第7页,共43页，2024年2月25日，星期天6104B2396581052C1C3D1D2EC2第8页,共43页，2024年2月25日，星期天131112B3396581052C1C3D1D2EC2第9页,共43页，2024年2月25日，星期天39C1810C352D1D2E65C2计算S(Ci)又可以归结为求从D1和D2到E的最短路径S(D1)和S(D2)这两个子问题。第10页,共43页，2024年2月25日，星期天39C152D1D2E第11页,共43页，2024年2月25日，星期天52D1D2E65C2第12页,共43页，2024年2月25日，星期天810C352D1D2E第13页,共43页，2024年2月25日，星期天S(D1)和S(D2)是已知的，它们分别是：S(D1)=5，S(D2)=2。因而，可以从这两个值开始，逆向递归计算S(A)的值。5D12D2E第14页,共43页，2024年2月25日，星期天[引例]马车驿站问题124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段44个阶段EED1

D2D1

D2D1

D2D1

D2C2

C3

C4C1

C2

C31D1E1D2E2C4D1

C4D22C3D1

C3D22C2D1

C2D22C1D1

C1D23B2C2

B2C3

B2C43B1C1

B1C2

B1C3B1

B22AB1

AB2AB2B1C4C3C2C1D1D24321终点路线数可选路线起点阶段一共有2×3×2×1=12条不同的路线f(E)=0f(D1)=2f(D2)=1f(C1)=8f(C2)=5f(C3)=4f(C1)=5f(B1)=8f(B2)=11f(A)=13回顾分析过程:1.将分析对象划分成4阶段;2.每阶段始点状态与终点状态有关,而不考虑始终点状态如何形成(无记忆性);3.每阶段各始点状态为终点状态与始点至终点距离之和的最小值(状态转移)这种最优化方法称为动态规划,由美国数学家贝尔曼等人于20世纪50年代创立.第15页,共43页，2024年2月25日，星期天13.1.1动态规划的基本概念1.阶段:把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。[导入案例]中k=1,2,3,42.状态变量:每个阶段开始所处的自然状况或客观条件(用点集表示).如引例:

第1阶段的状态就是起点A,记为s1={A};

第2阶段有2个状态{B1,B2},记为s2={B1,B2};

第3阶段有4个状态{C1,C2,C3,C4},记为s3={C1,C2,C3,C4};

第4阶段有2个状态{D1,D2},记为s4={D1,D2};3.决策变量:在某一阶段的某个状态时的不同选择,如引例中B1状态下有3种选择:

B1—C1,B1—C2,B1—C3

这3种选择构成了允许决策的集合。不同状态下允许决策的集合也不同，故决策变量是状态变量的函数，即xk(sk)∈D(sk)124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段44个阶段4.策略按顺序排列的决策组成的集合，由过程的第k阶段开始到终止状态为止的过程(或k子过程),k子过程的策略称子策略，记为Pk,n(sk),即Pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}当k=1时，即为全过程的一个策略。如引例中：D—E，即4到5过程起始有2个状态，D1和D2，因此有P4,5={D1—E，D2—E}5.状态转移方程确定过程是由一个状态到另一个状态的演变过程。第k阶段状态变量值给定后，如果确定决策变量，第k+1阶段状态变量值就完全确定。即：sk+1=T(sk,xk)如引例中：若对A—B1,A—B2选择了A—B1,则s2=5,B1到C有3种选择:B1—C1、B1—C2、B1—C3，若选择了B1—C2,则s3=s2+d(B1,C2)=86.指标函数用来衡量所实现过程优劣的一种数量指标。其基本方程有加法和乘法两种形式，通常加法形式用的较多，其公式为：7.边界条件起始或终止条件。第16页,共43页，2024年2月25日，星期天13.1.2动态规划的基本原理124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段44个阶段最优化原理

(Optimalityprinciple):最优策略具备这样的性质:无论初始状态与初始决策如何,以后诸决策对以第一个决策所形成的状态作为初始状态的过程而言,必然构成最优策策略.通俗地说:最优策略的子策略也是最优的.例如，在导入案例中，最优策略是A—B1—C2—D1—E,最短距离为13,其子策略:B1—C2—D1—E,C2—D1—E,D1—E也是最优的。依据这一原理，从后往前推各阶段最优子过程，从而得到全程最优过程。设f(i)表示从点i到终点E的最短距离,d(i,j)表示点i,j之间的距离.显然f(E)=0,为该问题的边界条件.k=4决策：D1Ek=3决策：D2E决策：C1D1决策：C2D1k=2决策：C3D2决策：C4D2决策：B1C2决策：B2C3k=1决策：AB1最短路线:AB1C2D1E最短路长:13第17页,共43页，2024年2月25日，星期天动态规划用一种全新的思路来考虑这样的问题。首先，把一个复杂的问题归结为若干个与原问题性质完全相同，但规模较小的子问题，每一个子问题又可以递归地归结为性质相同，规模更小的下层子问题。如此不断进行，一直到子问题非常简单，可以解决为止。然后，从这些最简单的子问题出发，依次计算上一层子问题的最优解，直到求出原问题的最优解。第18页,共43页，2024年2月25日，星期天Bellman最优性原理“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策必然形成最优子策略”一个最优策略的子策略总是最优的。第19页,共43页，2024年2月25日，星期天划分阶段确定状态变量及允许状态集合确定决策变量及决策空间确定状态转移方程确定最优指标函数并建立递归方程

13.2.1动态规划模型的建立第20页,共43页，2024年2月25日，星期天例：最短路径问题找出A到E的最短路径

第21页,共43页，2024年2月25日，星期天（1）分为四阶段，k=1,2,3,4。（2）令Sk

（k→n）为k阶段初所处的位置。（3）令决策变量xk为处于某阶段某位置时，选择下一个位置。（4）状态转移方程

（5）递归方程（k→n）第22页,共43页，2024年2月25日，星期天1、划分为4个阶段2、用点集表示各阶段的状态S1=｛A｝;s2=｛B1,B2,B3｝,s3=｛C1,C2,C3｝;s4=｛D1,D2｝3、指标函数：Vk，4（i）为第k阶段第i点到E点的距离4、最优值函数fk（i）为i点到E的最短距离5、决策变量xk=d[i,j]为第k阶段第i状态的选择6、边界条件：f5（E）=07、基本方程：fk（i）=min｛d[i,j]+fk+1（j）｝(k=1,2,3,4)第23页,共43页，2024年2月25日，星期天模型求解逆序法已知边界条件终点顺序法已知始点边界条件第24页,共43页，2024年2月25日，星期天逆序法求解k=4第25页,共43页，2024年2月25日，星期天

k=3第26页,共43页，2024年2月25日，星期天

k=2第27页,共43页，2024年2月25日，星期天k=1最优路径为最短距离为19第28页,共43页，2024年2月25日，星期天最优解第29页,共43页，2024年2月25日，星期天总结：逆序法最优值函数f(k):从k阶段到E的最短距离；阶段指标函数,即该阶段选择不同路线的距离。从后向前推。S1={A}S2={B1,B2}S3={C1,C2,C3,C4}S4={D1,D2}S5={E}f5(E)=0同理f4(D1)=2,f4(D2)=1同理f3(C2)=5,f3(C3)=4,f3(c4)=5同理f2(B2)=11124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段4第30页,共43页，2024年2月25日，星期天13.2.2动态规划问题的解法:顺序法124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段4最优值函数f(k):从A到k阶段的最短距离；阶段指标函数,即该阶段选择不同路线的距离。从前向后推。S0={A}S1={B1,B2}S2={C1,C2,C3,C4}S3={D1,D2}S4={E}最优值函数:f0(A)=0f1(B1)=5,f2(B2)=3f2(C1)=7,f3(C2)=8,f3(C3)=10,f3(c4)=9f3(D1)=11,f4(D2)=13第31页,共43页，2024年2月25日，星期天案例---资源分配解把生产第k种产品看成是第k阶段，划分为n个阶段.设sk表示第k阶段初资源可用量（状态变量）

xk表示分配给第k阶段资源的数量（决策变量），显然有：允许决策集合

sk+1=sk-xk

（状态转移方程）s1=a

（边界条件）指标函数：若fk(sk)表示数量为sk资源分配给第k种产品时，从第k阶段到第n阶段总收益，则有：设某公司有某种原料，其数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi（xi）。问应如何分配，才能使生产n种产品的总收入最大？第32页,共43页，2024年2月25日，星期天例1资源分配问题5台设备分配给3个工厂，盈利表如下，如何分配可使获利最大？

台数工厂012345甲乙丙00045389711119111211111212分析3个工厂看成3个阶段.阶段变量k(k=1,2,3)；状态变量sk表示为分配给第k个工厂至第n个工厂的设备台数；决策变量xk

表示分配给第k个工厂的设备台数；则有sk+1=sk-xk；Pk(xk)表示为xk

台设备分配到第k个工厂所得赢利值；fk(sk)表示为台设备分配给第k个工厂至第n个工厂所得到的最大赢利值。则有:第33页,共43页，2024年2月25日，星期天k=3x3s3P3(x3)f3(s3)x3*0123450123450379111203791112012345k=2x2s2P2(x2)+f3(s2-x2)f2(s2)x2*01234501234500+30+70+90+110+125+05+35+75+95+119+09+39+79+911+011+311+712+012+312+00591216180121，222，3k=1x1s1P1(x1)+f2(s1-x1)f1(s1)x1*01234550+184+168+1211+911+511+0201，2，3012345甲乙丙00045389711119111211111212方案一:1,2,2方案二:2,1,2方案三:2,2,1方案四:3,2,0第34页,共43页，2024年2月25日，星期天案例2设备负荷问题某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=9x，其中x为投入生产的机器数量，季度完好率为a=0.65，在低负荷下生产的产量函数为h=4y，其中y为投入生产的机器数量，季度完好率为b=0.95。设资源拥有量100.解4季度看成4阶段

sk第k季初拥有完好机器数

xk第k季分配给高负荷机器数,则低负荷分配数sk-xk

下季度初完好机器数sk+1=0.65xk+0.95(sk-xk)

第k季产量vk=6xk+4(sk-xk)第35页,共43页，2024年2月25日，星期天k=4f4是x4的增函数,故最大值解为x4*=s4,相应地有f4(s4)=9s4k=3f3是x3的增函数,故最大值解为x3*=s3,相应地有f3(s3)=14.85s3第36页,共43页，2024年2月25日，星期天k=2f2是x2的增函数,故最大值解为x2*=s2,相应地有f2(s2)=18.6525s2k=1f1是x1的减函数,故最大值解为x1*=0,相应地有f1(s1)=21.719875s1=2172反向推算，由s1=100，x1﹡=0，知s2=95，x2﹡=95，s3=61.75，x3﹡=61.75，s4=40.14，x4﹡=40.14，s5=26.09。即第1季度设备100%全部分配给低负荷第2季度初完好设备为95%，全部分配给高负荷第3季度完好设备为61.75%，全部分配给高负荷第4季度完好设备为40.14%，全部分配给高负荷。全年结束后，设备完好率为26.09%.最大产量2172。第37页,共4