第十章动态规划ppt课件.ppt

-4-2-3-3,行变换,列变换,-1,-1-1,+1,-1-1,+1,+1,-1,X*=,Z*=7+2+3+3=15,复习指派问题的匈牙利解法:,第十章,Dynamic Programming,概 述,动态规划是解决多阶段决策过程最优化问题的一种方法，该方法是由美国数学家贝尔曼（R Bellman)等人20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支，即动态规划。,例1、最短路径问题,求从A到E的最短距离和最短路径,例2 多阶段资源分配问题,设有数量为x的某种资源，将它投入两种生产方式A和B中：以数量y投入生产方式A，剩下的量投入生产方式B，则可得到收入g(y)+h(x-y)，其中g(y)和h(x-y)是已知函数，并且g(0)=h(0)=0；同时假设以y与x-y分别投入两种生产方式A，B后可以回收再生产，回收率分别为a与b。试求进行n个阶段后的最大总收入？,若以y与x-y分别投入生产方式A与B，在第一阶段生产后回收的总资源为x1=ay+b(x-y)，再将x1投入生产方式A和B，则可得到收入:g(y1)+h(x1-y1)继续回收资源x2=ay1+b(x1-y1)，若上面的过程进行n个阶段，我们希望选择n个变量y,y1,y2,yn-1，使这n个阶段的总收入最大。,分 析,因此，我们的问题就变成：求y,y1,y2,yn-1，以使g(y)+h(x-y)+g(y1)+h(x1-y1)+g(yn-1)+h(xn-1-yn-1)达到最大，且满足条件 x1=ay+b(x-y)x2=ay1+b(x1-y1)xn-1=ayn-2+b(xn-2-yn-2)yi与xi均非负(i=1,2,n-1),分 析,多阶段决策问题 所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。,动态规划的研究对象,动态规划是现代企业管理中的一种重要决策方法：,资源分配问题生产计划与库存问题装载问题生产过程的最优控制问题,独特的解题思路,离散决策过程,连续决策过程,确定性决策过程,随机性决策过程,离散确定性决策过程,离散随机性决策过程,连续确定性决策过程,连续随机性决策过程,动态规划模型的分类：,第十章 动态规划,第一节 动态规划基本概念第二节 动态规划基本原理第三节 动态规划模型的建立与求解第四节 动态规划在经济管理中的应用,（1）阶段：将所给问题的全过程按照时间或空间特征分解成若干相互联系的部分，以便按次序去求解每部分的解，称为阶段，一般用n表示阶段总数，用k表示阶段变量，k=1,2,n。,第一节 动态规划基本概念,k=1,k=2,k=3,k=4,（2）状态：每个阶段开始时所处的自然状况或客观条件称为该阶段的状态。描述各阶段状态的变量称为状态变量，常用sk表示；状态变量的取值集合称为状态集合，用Sk表示,第一节 动态规划基本概念,k=1,k=2,k=3,k=4,当k=1时，s1=A S1=A当k=2时，s2=B1或B2或B3 S2=B1,B2,B3 当k=3时，s3=C1或C2或C3 S3=C1,C2,C3 当k=4时，s4=D1或D2 S4=D1,D2,第一节 动态规划基本概念,第一节 动态规划基本概念,（3）决策：某一阶段内的选择。当各阶段的状态取定以后，就可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定称为决策。表示决策的变量称为决策变量，常用xk(sk)表示第k阶段当状态为sk时的决策变量；在实际问题中,决策变量的取值往往限制在一定范围内,称此范围为允许决策集合，常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有：xk(sk)Dk(sk),k=1,k=2,k=3,k=4,x1(s1)：x1(A)=B1或B2或B3 D1(A)=B1,B2,B3 x2(s2)：x2(B1)=C1或C2或C3 D2(B1)=C1,C2,C3 x2(B2)=C1或C2或C3 D2(B2)=C1,C2,C3 x2(B3)=C1或C2或C3 D2(B3)=C1,C2,C3.,（4）状态转移函数：动态规划中本阶段的状态往往是由上一阶段状态和上一阶段的决策决定的。如果给定了第k阶段的状态sk，本阶段的决策xk(sk)，则第k+1阶段的状态sk+1也就完全确定了，它们关系可用方程表示为：sk+1=Tk(sk xk)由于它表示了由k段到k+1段的状态转移规律，所以称为状态转移方程。,第一节 动态规划基本概念,k=1,k=2,k=3,k=4,s1=A x1(A)=B1或B2或B3s2=B1或B2或B3 x2(B1)=C1或C2或C3 x2(B2)=C1或C2或C3 x2(B3)=C1或C2或C3所以状态转移方程为：sk+1=xk(sk),（5）策略：每个阶段的决策确定以后，就得到一个决策序列，称为策略。由所有各阶段的决策组成的决策函数序列称为全过程策略，简称策略，记为p1,n(s1)；对每个实际问题，可供选择的策略有一定的范围，称为允许策略集合，记作P1,n，使整个问题能够达到最优效果的策略就是最优策略；从第k阶段开始到最后阶段的决策组成的决策函数序列称为k子过程策略，简称k子策略，记为pk,n(sk)。,第一节 动态规划基本概念,k=1,k=2,k=3,k=4,p1.4(A)=A,B1,C1,D1,E,是一条全过程策略p2.4(B1)=B1,C1,D1,E,是一条2子策略,（6）指标函数：衡量全过程策略或k子过程策略优劣的数量指标称为指标函数。它分为阶段指标函数和过程指标函数两种。阶段指标函数是指第k段，从sk状态出发，采取决策xk时的效益，用dk(sk,xk)表示。对于一个n段的过程，从1到n叫做问题的原过程，对于任意一个给定的k(1kn)，从第k段到第n段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时原过程的指标函数值；Vk,n(sk,pk,n)表示在第k阶段，初始状态为sk采用策略pk,n时，后部子过程的指标函数值；,（7）最优指标函数：最优指标函数记为fk(sk)，它表示从第k阶段初始状态sk采用最优策略p*k,n到过程终止时的最佳效益值。fk(sk)与Vk,n(sk,pk,n)间的关系为：fk(sk)=Vk,n(sk,p*k,n)=opt Vk,n(sk,pk,n)pk,n Pk,n当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数。,动态规划的研究对象是多阶段决策问题，而多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。,p*k,n,f1(s1),温馨提示,动态规划方法基于贝尔曼(R Bellman)等人提出的最优化原理：“一个过程的最优策略具有这样的性质：即无论其初始状态及其初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。”,第二节 动态规划基本原理,最优化原理,最优化原理的理解,对于多阶段决策问题的最优策略，任一子策略都是最优的。如：最短路径上，从路径上任一点到终点的部分路径（最短路上的子路）也一定是从该点到终点的最短路径（最短子路）,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,利用这个原理，可以把多阶段决策问题求解过程表示成一个连续的递推过程，由后向前逐步计算。在求解时，前面的各状态与决策，对后面的子过程来说，只相当于初始条件，并不影响后面子过程的最优决策。一般动态规划基本方程可以表示为：,动态规划基本方程,边界条件,将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。求解时从边界条件开始，逆过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已经求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。,动态规划基本思想,第三节 动态规划模型的建立与求解,建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程。成功地应用动态规划方法的关键，在于识别问题的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状态变量具有递推的状态转移关系sk+1=Tk(sk,xk),第三节 动态规划模型的建立与求解,求解动态规划的基本步骤：（一）建立动态规划逆序递推基本方程1、划分阶段：n k2、定义状态变量及其状态集合：sk Sk3、定义决策变量及其允许决策集合：xk*(sk)Dk*(sk)4、确定状态转移关系：sk+1=Tk(sk,xk)5、定义最优指标函数：阶段指标dk(sk,xk)、最优指标函数fk(sk)及其f1(s1)6、建立动态规划逆序递推基本方程,（二）求解f1(s1)：k=n,n-1,1，注意标出最优决策xk*(sk)（三）确定最优策略:结合状态转移方程顺推最优决策,例1：最短路径问题,求从A到E的最短路径和最短距离,第三节 动态规划模型的建立与求解,k=1,k=2,k=3,k=4,解（一）建立动态规划逆序递推基本方程1、划分阶段：将原问题按照空间划分为四个阶段，即n=4，阶段变量 k=1,2,3,4,k=1,k=2,k=3,k=4,当k=1时，s1=A S1=A当k=2时，s2=B1或B2或B3 S2=B1,B2,B3 当k=3时，s3=C1或C2或C3 S3=C1,C2,C3 当k=4时，s4=D1或D2 S4=D1,D2,2、定义状态变量sk：令sk表示各阶段的起始位置，则各阶段的状态变量sk及其状态集合Sk为:,k=1,k=2,k=3,k=4,3、定义决策变量xk(sk)：令xk(sk)表示从阶段k的sk出发所做的选择。,x1(s1)：x1(A)=B1或B2或B3 D1(A)=B1,B2,B3 x2(s2)：x2(B1)=C1或C2或C3 D2(B1)=C1,C2,C3 x2(B2)=C1或C2或C3 D2(B2)=C1,C2,C3 x2(B3)=C1或C2或C3 D2(B3)=C1,C2,C3 x3(s3)：x3(C1)=D1或D2 D3(C1)=D1,D2 x3(C2)=D1或D2 D3(C2)=D1,D2 x3(C3)=D1或D2 D3(C3)=D1,D2x4(s4)：x4(D1)=E D4(D1)=E x4(D2)=E D4(D2)=E,各阶段的决策变量xk(sk)及其允许决策集合Dk(sk)为:,4、确定状态转移方程：,k=1,k=2,k=3,k=4,状态转移方程：sk+1=xk,5、定义指标函数：,阶段指标：令 dk(sk,xk)-表示相邻两个城市之间的距离最优指标函数：fk(sk)-表示从第k阶段的sk到终点E的最短距离;f1(s1)即f1(A)-表示从A到终点E的最短距离;,k=1,k=2,k=3,k=4,F4(s4),F3(s3),F2(s2),F1(s1),6、建立逆序递推基本方程：,动态规划的逆序递推算法的基本方程为：fk(sk)=min dk(sk,xk)+fk+1(sk+1)k=4,3,2,1 xk Dk(sk)f5(s5)=0,下面从边界条件出发逐段求得原问题的最短距离,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,边界条件：f5(E)=0,（二）计算f1(A),D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,s4=D1或D2,f4(D1)=mind4(D1,E)+f5(E)=min5+0=5 x4*(D1)=E,f4(D2)=mind4(D2,E)+f5(E)=min2+0=2 x4*(D2)=E,f4(D2)=2,D1,E,D2,E,当k=4时 f4(s4)=min d4(s4,x4)+f5(s5)x4 D4(s4),f3(C1)=8,s3=C1或C2或C3,最优决策x3*(C1)=D1,D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,当k=3时 f3(s3)=min d3(s3,x3)+f4(s4)=min d3(s3,x3)+f4(x3)x3 D3(s3)x3 D3(s3),f3(C2)=7,最优决策x3*(C2)=D2,f3(C1)=8,D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,C2,当k=3时 f3(s3)=min d3(s3,x3)+f4(s4)=min d3(s3,x3)+f4(x3)x3 D3(s3)x3 D3(s3),f3(C3)=12,f3(C2)=7,f3(C1)=8,D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,C2,C3,最优决策x3*(C3)=D2,当k=3时 f3(s3)=min d3(s3,x3)+f4(s4)=min d3(s3,x3)+f4(x3)x3 D3(s3)x3 D3(s3),f2(B1)=20,f3(C3)=12,f3(C2)=7,f3(C1)=8,D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,C2,C3,B1,最优决策x2*(B1)=C1,s2=B1或B2或B3,当k=2时 f2(s2)=min d2(s2,x2)+f3(s3)=min d2(s2,x2)+f3(x2)x2 D2(s2)x2 D2(s2),f2(B2)=14,最优决策x2*(B2)=C1,f2(B1)=20,f3(C3)=12,f3(C2)=7,f3(C1)=8,D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,C2,C3,B1,B2,当k=2时 f2(s2)=min d2(s2,x2)+f3(s3)=min d2(s2,x2)+f3(x2)x2 D2(s2)x2 D2(s2),f2(B3)=19,f2(B2)=14,f2(B1)=20,f3(C3)=12,f3(C2)=7,f3(C1)=8,D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,C2,C3,B1,B2,最优决策x2*(B3)=C2,B3,当k=2时 f2(s2)=min d2(s2,x2)+f3(s3)=min d2(s2,x2)+f3(x2)x2 D2(s2)x2 D2(s2),f1(A)=19,f2(B3)=19,f2(B2)=14,f2(B1)=20,f3(C3)=12,f3(C2)=7,f3(C1)=8,D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,C2,C3,B1,B2,B3,最优决策x1*(A)=B2,A,s3=A,当k=1时 f1(s1)=min d1(s1,x1)+f2(s2)=min d1(s1,x1)+f2(x1)x1 D1(s1)x1 D1(s1),顺推最优决策：状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,f1(A)=19,f2(B3)=19,f2(B2)=14,f2(B1)=20,f3(C3)=12,f3(C2)=7,f3(C1)=8,D1,5,10,6,10,12,3,5,10,5,2,C1,C3,D1,A,B1,B3,B2,C2,f4(D1)=5,f5(E)=0,f4(D2)=2,D1,E,D2,E,C1,C2,C3,B1,B2,B3,A,12,A x1*(A)=B2 B2 x2*(B2)=C1 C1 x3*(C1)=D1 D1 x4*(D1)=E E从A到E的最短路径为19，路径为AB 2C1 D1 E,（三）推导最优策略,第三节 动态规划模型的建立与求解,求解动态规划的基本步骤：（一）建立动态规划逆序递推基本方程1、划分阶段：n k2、定义状态变量及其状态集合：sk Sk3、定义决策变量及其允许决策集合：xk(sk)Dk(sk)4、确定状态转移关系：sk+1=Tk(sk,xk)5、定义最优指标函数：阶段指标dk(sk,xk)、最优指标函数fk(sk)及其f1(s1)6、建立动态规划逆序递推基本方程,（二）求解f1(s1)：k=n,n-1,1，注意标出最优决策xk*(sk)（三）确定最优策略:结合状态转移方程顺推最优决策,最短路径问题资源分配问题背包问题生产计划与库存问题,第四节 动态规划在经济管理中的应用,生产过程的最优控制问题机器负荷分配问题装载问题系统可靠性问题,例2、资源分配问题,某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？,资源分配问题,解：（一）建立动态规划逆序递推基本方程（1）划分阶段：将问题按甲、乙、丙三个工厂划分为三个阶段：,k=1,k=2,k=3,甲,乙,丙,n=3,k=1,2,3,资源分配问题,（2）定义状态变量sk：令sk表示可分配给第k至第3个工厂的设备总台数(k=1,2,3),k=1,k=2,k=3,甲,乙,丙,s1,s2,s3,s1=5 S1=5s2=0,1,2,3,4,5 S2=0,1,2,3,4,5s3=0,1,2,3,4,5 S3=0,1,2,3,4,5,资源分配问题,（3）定义决策变量xk：令xk表示分配给第k个工厂的设备台数(k=1,2,3),k=1,k=2,k=3,甲,乙,丙,s1,s2,s3,x3,x2,x1,则0 xk sk x1(s1):x1(5)=0,1,2,3,4,5x2(s2):x2(0)=0 x2(1)=0,1 x2(2)=0,1,2 x2(3)=0,1,2,3 x2(4)=0,1,2,3,4 x2(5)=0,1,2,3,4,5,x3(s3):x3(0)=0 x3(1)=1 x3(2)=2 x3(3)=3 x3(4)=4 x3(5)=5,资源分配问题,（4）确定状态转移方程：sk+1=Tk(sk xk),k=1,k=2,k=3,甲,乙,丙,s1,s2,s3,x3,x2,x1,sk表示分配给第k个工厂至第3个工厂的设备台数(k=1,2,3)xk表示分配给第k个工厂的设备台数(k=1,2,3),s2=s1 x1s3=s2 x2s4=0所以 sk+1=sk xk(k=1,2,3),资源分配问题,（5）确定最优指标函数：,k=1,k=2,k=3,甲,乙,丙,s1,s2,s3,x3,x2,x1,令dk(xk)表示给第k个工厂分配xk台设备能够获得的利润;令fk(sk)表示将sk台设备分配给第k到第3个工厂采用最优分配策略时所创造的最大利润(k=1,2,3);设f1(s1)即f1(5)表示将5台设备分配给3个工厂采用最优分配策略时所创造的最大利润;则动态规划的逆序递推算法的基本方程为:,f3(s3),f2(s2),f1(s1),（二）计算f1(s1)从边界条件出发逐段求得原问题的最大利润：,（6）建立逆序递推基本方程：,fk(sk)=maxd k(xk)+fk+1(sk+1)(k=3,2,1)0 xksk f4(s4)=0,当k=3时 f3(s3)=maxd 3(x3)+f4(s4)=maxd 3(x3)0 x3 s3 x3=s3,s3=0,1,2,3,4,5,x3(s3):x3(0)=0 x3(1)=1 x3(2)=2 x3(3)=3 x3(4)=4 x3(5)=5,f3(0)=maxd 3(x3)=maxd 3(0)=0 x3=0,d 3(1),=max,f3(1)=maxd 3(x3)=max,x3=1,4,=4,=max,f3(2)=maxd 3(x3)=max,x3=2,6,=6,d 3(2),x3*(2)=2,x3*(1)=1,x3*(0)=0,=max,f3(3)=maxd 3(x3)=max,x3=3,11,=11,=max,f3(4)=maxd 3(x3)=max,x3=4,=12,d 3(4),=max,f3(5)=maxd 3(x3)=max,x3=5,=12,d 3(3),12,12,d 3(5),x3*(5)=5,x3*(4)=4,x3*(3)=3,当k=3时 f3(s3)=maxd 3(x3)+f4(s4)=maxd 3(x3)0 x3 s3 x3=s3,当k=2时 f2(s2)=maxd 2(x2)+f3(s3)0 x2 s2,s2=0,1,2,3,4,5,x2(s2):x2(0)=0 x2(1)=0,1 x2(2)=0,1,2 x2(3)=0,1,2,3 x2(4)=0,1,2,3,4 x2(5)=0,1,2,3,4,5,f2(0)=maxd 2(x2)+f3(0-x2)=maxd2(0)+f3(0-0)=0 0 x2 0,d 2(0)+f3(1-0),d 2(1)+f3(1-1),=max,f2(1)=maxd 2(x2)+f3(1-x2)=max,0 x2 1,0+4,5+0,=5,d 2(0)+f3(2-0),d 2(1)+f3(2-1),=max,f2(2)=maxd 2(x2)+f3(2-x2)=max,0 x2 2,0+6,10+0,=10,d 2(2)+f3(2-2),5+4,x2*(2)=2,x2*(1)=1,x2*(0)=0,=maxd 2(x2)+f3(s2-x2)0 x2 s2,d 2(0)+f3(3-0),d 2(1)+f3(3-1),=max,f2(3)=maxd 2(x2)+f3(3-x2)=max,0 x2 3,0+11,11+0,=14,=max,f2(4)=maxd 2(x2)+f3(4-x2)=max,0 x2 4,0+12,10+6,=16,d 2(4)+f3(4-4),5+11,d 2(0)+f3(5-0),d 2(1)+f3(5-1),=max,f2(5)=maxd 2(x2)+f3(5-x2)=max,0 x2 5,=21,x2*(5)=2,d 2(2)+f3(5-2),d 2(2)+f3(3-2),d 2(3)+f3(3-3),5+6,10+4,d 2(1)+f3(4-1),d 2(2)+f3(4-2),d 2(0)+f3(4-0),d 2(3)+f3(4-3),11+4,11+0,10+11,5+12,11+6,11+4,0+12,11+0,d 2(3)+f3(5-3),d 2(4)+f3(5-4),d 2(5)+f3(5-5),x2*(3)=2,x2*(4)=1或2,当k=2时 f2(s2)=maxd 2(x2)+f3(s3)0 x2 s2,=maxd 2(x2)+f3(s2-x2)0 x2 s2,当k=1时 f1(s1)=maxd 1(x1)+f2(s1-x1)0 x1 s1,s1=5,d 1(0)+f2(5-0),d 1(1)+f2(5-1),=max,f1(5)=maxd 1(x1)+f2(5 x1)=max,0 x1 5,=21,d 1(2)+f2(5-2),7+14,3+16,9+10,12+5,0+21,13+0,d 1(3)+f2(5-3),d 1(4)+f2(5-4),d 1(5)+f2(5-5),所以 x1*(5)=0或2,x1(5)=0,1,2,3,4,5,（三）推导最优策略(顺推确定最优策略),由上可见最大利润为f1(5)=21 此时s1=5 x1*(5)=0或2当x1*(5)=0时,由状态转移方程s2=s1-x1=5-0=5,查得x2*(5)=2;又s3=s2-x2=5-2=3,查得x3*(3)=3;所以x1*=0，x2*=2，x3*=3是一组解当x1*(5)=2时,由状态转移方程s2=s1-x1=5-2=3,查得x2*(3)=2;又s3=s2-x2=3-2=1,查得x3*(1)=1;所以x1*=2，x2*=2，x3*=1也是一组解可见原方程有两个最优分配方案：x1*=0，x2*=2，x3*=3，或 x1*=2，x2*=2，x3*=1这两种分配方案都能得到最高的总利润21万元,课堂练习,某公司有资金4万元，可向A、B、C三个项目投资，已知各项目不同投资额的相应效益值如表所示，问如何分配资金可使总效益最大？,杭州网通公司正在计划如何安排在15天时间里对3个小区进行网络调试，要求每天只能安排一个小区的调试，每个小区至少需要调试4天，已知花费在各个小区的时间与将来创造的利润（万元）的关系如下表，问如何安排时间使得将来所获得的利润最高？,资源分配问题例 3,（1）划分阶段：按小区将原问题划分为三个阶段，则n=3,k=1,2,3,（2）确定状态变量：sk表示分配用于第k个小区到第三个小区的总的网络调试天数，则：s1=15;s2=8，9，10，11;s3=4，5，6，7;s4=0;,（一）建立动态规划逆序递推基本方程,（3）确定决策变量：xk(sk)表示分配给第k个小区的调试天数，则：x1(s1)：x1(15)=4，5，6，7；D1(15)=4，5，6，7,x2(s2)：x2(8)=4；D2(8)=4 x2(9)=4，5；D2(9)=4，5 x2(10)=4，5，6；D2(10)=4，5，6 x2(11)=4，5，6，7；D2(11)=4，5，6，7x3(s3)：x3(4)=4；D3(4)=4 x3(5)=5；D3(5)=5 x3(6)=6；D3(6)=6 x3(7)=7；D3(7)=7,阶段指标：dk(xk,)-表示第k阶段调试天数为xk天时创造的利润；最优指标函数：fk(sk)-表示第k阶段用于第k到第3阶段调试总天数为sk天时,采用最优策略时，创造的最大利润；最优指标函数：f1(s1)-表示第1阶段用于第1到第3阶段调试总天数为s1天时,采用最优策略时，创造的最大利润；则动态规划逆序递推基本方程为：,fk(sk)=max dk(xk)+fk+1(sk+1)k=3,2,1 xk Dk(sk)f 4(s4)=0,(4)确定状态转移方程：由分析可知该问题的状态转移方程为：sk+1=sk xk（5）确定最优指标函数：,当k=3时：f3(s3)=maxd3(x3)+f4(s4)=maxd3(x3)x3 D3(s3)x3=s3,f3(5)=maxd3(x3)=maxd3(5)=max5=5 x3=5,f3(6)=maxd3(x3)=maxd3(6)=max8=8 x3=6,f3(7)=maxd3(x3)=maxd3(7)=max10=10 x3=7,（二）计算f1(s1),f3(4)=maxd3(x3)=maxd3(4)=max2=2 x3=4,当k=2时：f2(s2)=maxd2(x2)+f3(s3)x2 D2(s2),f2(9)=maxd2(x2)+f3(9-x2)x2 4,5,f2(8)=maxd2(x2)+f3(8-x2)x2 4,=maxd2(4)+f3(8-4),=max5+2=7,=maxd2(x2)+f3(s2-x2)x2 D2(s2),f2(10)=maxd2(x2)+f3(10-x2)x2 4,5,6,f2(11)=maxd2(x2)+f3(11-x2)x2 4,5,6,7,当k=1时：f1(s1)=maxd1(x1)+f2(s2)x1 D1(s1),=maxd1(x1)+f2(s1-x1)x1 D1(s1),f1(15)=maxd1(x1)+f2(15-x1)x1 4,5,6,7,注:可以通过倒推减少计算量,（三）推导最优策略：因为s1=15，从上述最优结果中查得：,根据状态转移方程：s2=s1-x1=15-5=10,从上述最优结果中又查得：,又根据状态转移方程：s3=s2-x2=10-4=6,从上述最优结果中又查得：,综上所述，,即杭州网通公司正在对第1个小区进行网络调试5天，第2个小区4天，第3个小区6天，使得将来所获得的利润最高，最高利润为19万元。,背包问题,背包问题的一般提法是:一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a千克,现有n种物品可供他选择装入背包，第i种物品的单价重量为ai千克,其价值(可以是表明本物品对登山的重要性的数量指标)是携带数量xi的函数ci(xi)(i=1,2,n),问旅行者应如何选择携带各种物品的件数,以使总价值最大？背包问题等用于车、船、人造卫星等工具的最优装载等,有广泛的实用意义.,背包问题的分析,设xi为第i种物品装入的件数，则背包问题可归纳为如下形式的整数规划模型：,下面用动态规划逆序解法建摸求解,背包问题的求解,解：（一）建立动态规划逆序递推基本方程（1）划分阶段：按照可装入物品的顺序划分为n个阶段，每段装一种物品，即k=1,2,n,k=1,k=2,k=n,.,（2）定义状态变量sk：令sk表示装入第k至第n种物品的总重量sk a,（3）定义决策变量xk：令xk表示装入第k种物品的件数 允许决策集合:Dk(xk)=xk|0akxksk,xn,x2,x1,s1,s2,s3,sn,sn+1,背包问题的求解,（4）确定状态转移方程：sk+1=Tk(sk xk),s2=s1 a1 x1s3=s2 a2x2所以 sk+1=sk akxk(k=1,2,n)由题意sn=anxn sn+1=0,k=1,k=2,k=n,.,xn,x2,x1,s1,s2,s3,sn,an xn,a2 x2,a1 x1,sn+1,背包问题的求解,（5）确定最优指标函数：,令ck(xk)表示第k阶段携带物品数量为xk时这些物品的价值令fk(sk)表示第k至第n种物品总重量为sk时采用最优装入策略时的最大使用价值;设f1(s1)即f1(a)表示装入n种物品限量为a千克采用最优装入策略时的最大使用价值;,fn(sn),f2(s2),f1(s1),k=1,k=2,k=n,.,xn,x2,x1,s1,s2,s3,sn,an xn,a2 x2,a1 x1,sn+1,fk(sk)=maxck(xk)+fk+1(sk-akxk)(k=n,n-1,2,1)fn+1(sn+1)=0,根据状态转移方程sk+1=sk-akxk得：,（二）计算f1(s1)从边界条件出发逐段求得原问题的最大使用价值：,（6）建立逆序递推基本方程：,fk(sk)=maxc k(xk)+fk+1(sk+1)(k=n,n-1,2,1)fn+1(sn+1)=0,背包问题的求解,（三）推导最优策略:根据最优决策顺推最优策略,xkDk xk为整数,xkDk xk为整数,有一辆最大货运量为10吨的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表所示。应如何装载可使总价值最大？,背包问题举例（一）,设第i种货物装载的件数为xi(i=1,2,3)，则问题可归纳为：,背包问题，可用前述方式建立动态规划模型并求解。,背包问题举例（一）,解：（一）建立动态规划逆序递推基本方程（1）划分阶段：将可装入货物的顺序划分为3个阶段，每段装一种物品，即n=3 k=1,2,3,k=1,k=2,k=3,（2）定义状态变量sk：令sk表示装入第k至第3种货物的总重量sk 10,s1,s2,s3,s4,背包问题举例（一）,状态变量是整数,状态集合 S1=10 S2=0,1,2,3,4,5,6,7,8,9,10 S3=0,1,2,3,4,5,6,7,8,9,10,k=1,k=2,k=3,x3,x2,x1,s1,s2,s3,s3,s4,（3）定义决策变量xk：令xk表示装入第k种货物的件数 允许决策集合：Dk(xk)=xk|0akxksk(xk为整数),根据题意：D1(s1)=x1|03x1s1(x1为整数)=x1|0 x1s1/3 D2(s2)=x2|04x2s2(x2为整数)=x2|0 x2s2/4 D3(s3)=x3|5x3=s3(x3为整数)=x3|x3=s3/5,背包问题举例（一）,（4）确定状态转移方程：sk+1=Tk(sk xk),s2=s1 3 x1s3=s2 4x2s4=s3 5x3由题意s3=5x3 s4=0,k=1,k=2,k=3,x3,x2,x1,s1,s2,s3,5 x3,4 x2,3 x1,s4,背包问题举例（一）,（5）确定最优指标函数：,令dk(xk)表示第k阶段装载货物数量为xk时这些货物的价值 d1(x1)=4x1 d2(x2)=5x2 d3(x3)=6x3 令fk(sk)表示第k至第3种货物总重量为sk时采用最优装载策略时的最大总价值;设f1(s1)即f1(10)表示装入3种货物限量为10吨采用最优装载策略时的最大总价值;,f3(s3),f2(s2),f1(s1),k=1,k=2,k=3,x3,x2,x1,s1,s2,s3,5 x3,4 x2,3 x1,s4,f4(s4),背包问题举例（一）,（6）建立逆序递推基本方程：,fk(sk)=maxd k(xk)+fk+1(sk+1)(k=3,2,1)f4(s4)=0,当k=3时 f3(s3)=maxd3(x3)+f4(s4)=max6x3=6 s3/5,x3=s3/5x3为整数,（二）计算f1(s1)从边界条件出发逐段求得原问题的最大使用价值：,x3=s3/5x3为整数,xkDk xk为整数,背包问题举例（一）,f3(0)=60/5=0 x3*(0)=0 f3(1)=61/5=0 x3*(1)=0 f3(2)=62/5=0 x3*(2)=0f3(3)=63/5=0 x3*(3)=0f3(4)=64/5=0 x3*(4)=0f3(5)=65/5=6 x3*(5)=1f3(6)=66/5=6 x3*(6)=1 f3(7)=67/5=6 x3*(7)=1f3(8)=68/5=6 x3*(8)=1f3(9)=69/5=6 x3*(9)=1f3(10)=610/5=12 x3*(10)=2,x3=s3/5 x3为整数,当k=3时 f3(s3)=max6x3=6s3/5,背包问题举例（一）,f2(s2)=max5x2+f3(s2-4x2)0 x2s2/4,根据状态转移方程 s3=s2-4x2 指标函数 d2(x2)=5x2 允许决策集合 D2(x2)=x2|0 x2s2/4 得：,当k=2时 f2(s2)=maxd2(x2)+f3(s3),x2D2 x2为整数,背包问题举例（一）,当k=2时 f2(s2)=max5x2+f3(s2-4x2)0 x2s2/4,f2(0)=max5x2+f3(0-4x2)=0+f3(0)=0 x2=0,x2*(0)=0,f2(1)=max5x2+f3(1-4x2)=0+f3(1)=0 x2=0,x2*(1)=0,f2(2)=max5x2+f3(2-4x2)=0+f3(2)=0 x2=0,x2*(2)=0,f2(3)=max5x2+f3(3-4x2)=0+f3(3)=0 x2