91动态规划

管理运筹学动态规划华东交大经济管理学院ECJTU2第八章动态规划•动态规划DynamicProgramming研究多阶段决策的最优化问题的方法。多阶段决策问题含有一个描述过程时序或空间演变的阶段变量，将复杂问题划分成若干阶段，根据“最优性原理”，逐段解决而最终实现全局最优。经济、管理、工业生产、工程技术等领域，许多问题可归结为多阶段决策问题。一些用线性规划、非线性规划处理有困难的问题，往往可以用动态规划方便地求解。动态规划是美国运筹学家贝尔曼(R.Bellman)等人1959年提出的。华东交大经济管理学院ECJTU3第一节多阶段决策问题•多阶段决策：经济管理决策中，有些管理决策问题可以按时序或空间演变划分成多个阶段，呈现出明显的阶段性；于是可把这类决策问题分解成几个相互联系的阶段，每个阶段即为一个子问题；原有问题的求解就化为逐个求解几个简单的阶段子问题；每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。•例如：企业生产物流：可分为物料供应、生产制造、分销零售等阶段。最短路问题：可以按空间顺序划分阶段。一、问题的提出华东交大经济管理学院ECJTU4第一节多阶段决策问题•从生产厂Q到某公司T选择那条路线,使总运费最低(路程最短)？•最短路问题QTA1A2A3B1B2B3C1C124374642442514633334生产商某公司出口港进口港城市阶段1阶段2阶段3阶段4华东交大经济管理学院ECJTU5第一节多阶段决策问题•这是一个多阶段决策问题，它可分为四个阶段：第一阶段：从Q(制造厂)到A(出口港)；第二阶段：从A(出口港)到B(进口港)；第三阶段：从B(进口港)到C(城市)；第四阶段：从C(城市)到T(某公司)。•每个阶段选取的路线不同，对应从Q到T就有一系列不同的运输路线:从始点Q到终点T共有3×3×2×1=18条不同路线现在的问题是如何选择一条费用最小的路线？华东交大经济管理学院ECJTU6第一节多阶段决策问题•最短路径：Q→A3→B1→C1→T二、动态规划的标号法QTA1A2A3B1B2B3C1C224374642442514633334阶段1阶段2阶段3阶段403,T4,T4,C17,C26,C111,B1,B28,B18,B111,A3华东交大经济管理学院ECJTU7第一节多阶段决策问题•最短路的基本特征从始点Q到终点T的最短路径：Q→A3→B1→C1→T，则从中点A3到终点T的最短路径必为：A3→B1→C1→T，从中点B1到终点T的最短路径必为：B1→C1→T，…。推广：从始点Q到终点T的最短路径：Q→S1→S2→…→Sk→Sk+1→…→Sn→T，则从中点Sk到终点T的最短路径必为：Sk→Sk+1→…→Sn→T。三、多阶段决策的基本特征华东交大经济管理学院ECJTU8第二节动态规划原理•阶段(stage)处理多阶段决策，需将全过程划为若干阶段，每个阶段进行一次抉择。各阶段按一定顺序联接在一起组成统一的整体。用k表示阶段变量。阶段编号一、动态规划的基本概念华东交大经济管理学院ECJTU9第二节动态规划原理•状态(state)状态表示过程发展中某阶段的起始状况。过程的发展可以通过各阶段状态的演变来描述。状态可用一个变量来描述，称为状态变量，用Sk表示。选取的状态变量必须满足无后效性。•某阶段的状态给定后，则过程未来发展不受该阶段以前各阶段状态的影响。第k阶段可能有若干状态，用Sk表示阶段k的状态集合，sk(i)表示第k阶段的第i个状态。华东交大经济管理学院ECJTU10第二节动态规划原理•决策(decision)从上一阶段某状态演变到下一阶段某状态要作一次选择，称为决策。用变量xk(sk)表示第k阶段状态为sk时的决策，称为决策变量，简记xk决策变量的取值被限制在某一范围内，此范围称为允许决策集合Xk(sk)华东交大经济管理学院ECJTU11第二节动态规划原理•策略(policy)多阶段决策过程中，每一阶段均有一个决策，依序组合成一个全过程的决策序列，称为全过程策略。p1,n(s1)={x1(s1),x2(s2),…,xn(sn)}，简记p1,n={x1,x2,…,xn}从过程的某个阶段开始到最终阶段结束称为后部子过程。从第k阶段开始的后部子策略称为第k子过程策略。pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}，简记pk,n={xk,xk+1,…,xn}每一阶段有若干状态,每个状态又有若干个不同的决策,即有许多策略可供选择。全体策略构成允许策略集合Pk,n(sk)。能使预期目标达到最优效果的策略称为最优策略P*k,n，构成最优策略的各决策称为相应阶段的最优决策x*k。华东交大经济管理学院ECJTU12第二节动态规划原理•状态转移方程下一阶段状态sk+1是本阶段状态变量sk和决策变量xk的函数，即sk+1=T(sk,xk(sk))=T(sk,xk)从状态sk出发到下一阶段状态sk+1的转移规律称为状态转移方程。华东交大经济管理学院ECJTU13第二节动态规划原理•指标函数用来衡量每一阶段决策效果的优劣的数量指标，称为阶段指标函数vk，阶段指标是状态变量和相应决策变量的函数，即vk=vk(sk,xk)。•最短问题是运费或路程。对阶段的不同状态，采取不同的决策，运费不同。•指标函数也可以是利润、成本、产量等。从第k阶段的状态sk出发到最后阶段结束，各阶段绩效综合起来反映这个后部子过程的绩效，称为过程指标函数，记为Vk,n。•Vk,n的大小取决于从第k阶段到最后阶段所采取的子策略。即Vk,n=Vk,n(sk,xk,sk+1,xk+1,…,sn)•根据实际问题的性质，指标函数Vk,n可以是各个阶段指标的和或积。从状态sk出发，选取最优策略所得的指标函数值称为最优指标函数值。•fk(sk)=opt{Vk,n}=opt{vk(sk,xk)+fk+1(sk+1)}•opt表示最优化，取最大max或最小min。华东交大经济管理学院ECJTU14第二节动态规划原理•逆序算法：逆着阶段顺序的方向，由后向前推算。把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实际过程的进展方向逐段求解；在每一阶段求解过程中都是其后部子过程最优策略的基础上，再考虑本阶段的指标函数，求出本阶段的最优策略；直到第一阶段为止。•最优性原理：美国运筹学家贝尔曼提出无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。将决策问题划分为若干个阶段，全过程的优化问题就分解为子过程的优化问题，由后向前逐步倒推，最优化的子过程逐渐成为全过程最优。作为全过程的最优策略P*1,n的组成部分的任一子策略P*k,n(Sk)，一定是从状态Sk出发直至终点的最优策略。二、动态规划方法的基本思路华东交大经济管理学院ECJTU15第二节动态规划原理•据最优性原理，阶段k的阶段指标vk(sk,xk)加上(或乘以)从下一阶段k+1开始到过程结束采取最优策略取得的最优指标函数值fk+1(sk+1)，再从中选出最优，便是阶段k从状态sk出发到全过程结束的最优指标函数值。0)()(),()(),(1111)(,nnkkkkkSXxkknkiiiinksfsfxsvsfxsvVoptkkk边界条件：基本方程：指标之和，过程指标等于各阶段若1)()(),()(),(1111)(,nnkkkkkSXxkknkiiiinksfsfxsvsfxsvVoptkkk边界条件：基本方程：指标之积，过程指标等于各阶段若华东交大经济管理学院ECJTU16第二节动态规划原理阶段1阶段2阶段k阶段k+1阶段n……状态S1决策x1状态S2v1决策x2状态S3v2决策xk状态Sk+1vk决策xk+1vk+1决策xnvn寻求最优解的方向0)(11nnsf边界条件：)(),()(11)(kkkkkSXxkksfxsvsfoptkkk递推方程：华东交大经济管理学院ECJTU17第二节动态规划原理•建模步骤（小结）对问题进行阶段划分，确定阶段变量k确定状态变量sk确定决策变量xk、允许决策集合Xk(sk)写出状态转移方程sk+1=Tk(sk,xk)写出指标函数的基本递推方程明确边界条件•动态规划模型分类三、动态规划模型过程变量确定随机离散连续离散确定型离散随机型连续确定型连续随机型华东交大经济管理学院ECJTU18第三节应用举例•资源分配问题：把有限的资源(如资金、材料、设备、人力等)分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。资源可以有一种或若干种，只有一种资源可供分配的问题称之为一维资源分配问题。•一维资源分配问题一、资源分配问题设备台数分厂0123456I0356765II04678910III0259887如何分配设备，可使获利最大？各分厂在不同设备台数下所获利润华东交大经济管理学院ECJTU19第三节应用举例•动态规划的数学模型将三个分厂看作是三个阶段，即阶段变量k=1,2,3;状态变量sk表示第k阶段初可分配的设备台数,0≤sk≤6;决策变量xk表示第k阶段分配给分厂k的设备台数，允许决策集合Xk(sk)={xk︱0≤xk≤sk};状态转移方程为sk+1=sk-xk;阶段指标vk(sk,xk)表示第k阶段从sk台设备中分配给k分厂xk台设备的阶段效益;最优指数函数fk(sk)表示第k阶段从sk开始到最后阶段采用最优分配策略取得的最大的效益值;递推方程函数式0)()(),()(4411)(maxsfsfxsvsfkkkkkSXxkkkkk边界条件：基本方程：华东交大经济管理学院ECJTU20第三节应用举例•逆序求解K=3x3s3v3(s3,x3)f3(s3)x3*第III分厂在不同设备台数下所获利润01234560123456002025025902598025988025988702599990123333华东交大经济管理学院ECJTU21第三节应用举例k=2x2s2v2(s2,x2)+f3(s3)f2(s2)x2*第II分厂在不同设备台数下所获利润01234560123456004046046704678046789046789100469131516011,20,1123第III分厂在设备台数为s3下所获得的最大利润0+00+24+00+54+26+00+94+56+27+00+94+96+57+28+00+94+96+97+58+29+00+94+96+97+98+59+210+0华东交大经济管理学院ECJTU22第三节应用举例k=1x1s1v1(s1,x1)+f2(s2)f1(s1)x1*第I分厂在不同设备台数下所获利润0123456第II分厂在设备台数为s2下所获得的最大利润60356765181,2顺序递推，得出结论•第I分厂1套或2套•第II分厂2套或1套•第III分厂3套0+163+155+136+97+66+45+0华东交大经济管理学院ECJTU23背包问题是指对于N种具有不同重量和不同价值的物品,在携带物品总重量的情况下,决定这N种物品中每一种物品多少数量装入背包内,使得装入背包物品的总价值最大.二、背包问题华东交大经济管理学院ECJTU24第三节应用举例企业一年中的产品生产往往是分期分批生产的。组织每批产品的生产，都要花费一些生产准备费和存贮费用。•若某一时期增大生产批量则可减少生产批次，从而降低生产成本。•与此同时，批量大了，必然增加库存而使存贮费用增加。在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。二、生产与存储问题华东交大经济管理学院ECJTU25第三节应用举例•例，某工厂与用户签订了4个月的交货合同如表所示该厂生产能力为每月5万