动态规划0-1背包和资源分配

动态规划张起控制工程动态规划的基本概念动态规划原理值0-1背包问题发电厂设备分配问题结果讨论动态规划动态规划的基本概念01动态规划是运筹学的重要分支之一，是解决多阶段决策过程最优化的一种方法。对于一个多阶段决策过程，可以根据问题的特点，把整个过程分为几个相互联系的阶段，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的变化，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。一、什么是动态规划？动态规划法将求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段。一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，就可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。为了达到这个目的，可以用一个表来记录所有已解决的子问题的解，这就是动态规法的设计思想。具体的动态规划法是多种多样的，但是他们具有相同的填表形式。二、动态规划的设计思想最优化子结构性质：若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构的性质（即满足最优化原理）能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的子问题重叠性质：在用递归算法对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次，动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效利用。二、动态规划的实质——记忆化搜索02动态规划原理之0-1背包问题0-1背包问题问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。请问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？对于0-1背包问题，每种物品i都只有一件，可以选择装入或者是不装入背包。不能将物品i装入背包多次，也不能只装入部分。0-1背包问题基本思路0-1背包问题，特点就是：每种物品仅有一件，可以选择放或者是不放，其状态转移方程就是：M(i,v)=max{第i件物品不放入背包,第i件物品放入背包}M(i,v)=max{M(i-1,C),M(i-1,C–W(i)+V(i)}用子问题定义状态：即M(i,v)表示前i件物品恰好放入一个容量为C的背包可以获得的最大价值。M(i,v)=max{(不放入物品i)将前i-1件物品放入容量为C的背包中的最大价值，(放入物品i)将前i-1件物品放入容量为C-W(i)的背包中的最大价值+V(i)}0-1背包问题实例详解有5个物品，其重量分别是{2,2,6,5,4}，价值分别为{6,3,5,4,6}，背包的容量为10.0-1背包问题判断下一个物品是放还是不放；不放时：M(i,v)=M(i-1,C)；放时：M(i,v)=max{M(i-1,C),M(i-1,C–W(i)+V(i)}0-1背包问题MATLAB实现结果03动态规划应用之资源分配问题发电机组分配问题问题描述：现有5套发电机组分配给甲乙丙三个发电厂，各个发电厂利润与发电机组数量之间的关系如下表所示，请问如何分配可使3个发电厂的总利润最大化？动态规划的基本组成（1）阶段：将所给问题的过程，按照时间或空间特征分解成若干相互联系的阶段，以便于按次序求解最有阶段的解，每个阶段就是一个子问题，常用字母K表示阶段变量（2）状态：各阶段开始时的客观条件叫做状态，描述各阶段的变量叫做状态变量，常用Sk表示第k阶段的状态变量，状态变量Sk的取值集合称为状态集合，用Sk表示。（3）决策：当各段的状态确定以后，就可以做出不同的选择，从而确定下一阶段的状态，这种决定称为决策，表示决策的变量叫做决策变量，常用Uk表示第k阶段状态为Sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，称此范围为允许决策集合，常用Dk(Sk)表示第k阶段从状态sk出发的允许决策集合，显然有“Uk∈Dk(Sk)．（4）策略：一个由每个阶段的决策所组成的集合称为策略，用P表示，即P(s1)={u1(s1),u2(s2),……,un(sn)}一个n阶段决策过程，从1到n叫作问题的原过程．对于任意给定的k(1≤k≤n)，从第k阶段状态sk到第n阶段状态sn的过程称为原过程的一个后部子过程．后部子过程的策略记为pk(sk)={uk(sk),uk+1(sk+1),......,un(sn)}，在实际问题中，可供选择的策略有一定的范围，此范围成为允许策略集合。允许策略集合中达到最优效果的策略成为最优策略.(5)状态转移：动态规划中本阶段往往是上一阶段状态和上一阶段的决策进行综合的结果．如果给定了第k段的状态sk，且该阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定．它们的关系可表示为：sk+1=Tk(sk,uk)由于上式表示了由k阶段到k+1阶段的状态转移规律，所以称该式为状态转移方程动态规划的基本组成（6）指标函数用于衡量所选定策略优劣的数量指标称为指标函数．一个n阶段决策过程，从1到n叫作问题的原过程．对于任意一个给定的k(1≤k≤n)，从第k阶段到第n阶段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时原过程的指标函数值。而Vk,n(sk,pk,n)表示在第k阶段，状态为sk采用策略pk,n时后部子过程的指标函数值．最优指标函数记为fk(sk)，它表示从第k阶段状态sk采用最优策略pk,n到过程终止时的最佳效益值．fk(sk)与Vk,n(sk,pk,n)间的关系为：fk(sk)=Vk,n(sk,pk,n)=optimizeVk,n(sk,pk,n)当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数．动态规划的基本组成问题描述：现有5套发电机组分配给甲乙丙三个发电厂，各个发电厂利润与发电机组数量之间的关系如下表所示，请问如何分配可使3个发电厂的总利润最大化？发电机组分配问题建立动态规划的数学模型1、阶段K：按发电厂划分阶段，k=1,2,3（分别代表甲乙丙发电厂）2、状态变量Sk：表示可用于分配给第k个发电厂的发电机组的数量3、决策变量Uk：表示分配给第k阶段（发电厂）的发电机组数量4、状态转移Tk：Sk+1=Sk-Uk5、阶段指标Vk：第k阶段的指标函数，表示分配给第k个发电厂Uk台设备所获的利益发电机组分配问题综上可知，基本方程为同时可知：s1={5}s2={0,1,2,3,4,5}s3={0,1,2,3,4,5}发电机组分配问题发电机组分配问题MATLAB实现结果第一阶段，Sk=5，Uk=2，Vk=7第二阶段，Sk=3，Uk=2，Vk=10第三阶段，Sk=1，Uk=1，Vk=4Vk（max）=7+10+4=21发电机组分配问题结果讨论041、由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，也很难求出全局解，而动态规划可以把全过程化为一系列结构显示的子问题，变量大大减少，约束集合变简单，易于得到全局最优解。2、实际问题往往是动态的，而动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。结果讨论动态规划优缺点1、动态规划没有同意的模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则，因此只能凭借经验具体分析，这也带来了应用上的局限性。2、用数值方法求解时，对于状态变量取值的n维问题，对每个状态都要计算，就存在维数灾问题，动态规划对于这一类问题是无效的动态规划的应用动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题。动态规划最优化原理作为整个过程最优策略具有这样的性质：无论过去的状态和决策如何，对前面的决策所形成的的状态而言，余下的决策必须构成最优策略电力项目投资、发电机组负荷优化以提高经济性、供电系统无功优化、配电网电压无功控制、配电网开关优化配置等方面有着广泛的应用010203结果讨论动态规划在电网上的应用