运筹学第10章-动态规划

管理运筹学动态规划综述

动态规划是解决多阶段决策过程最优化问题的一种方法。动态规划所研究的对象是多阶段决策问题。它把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题。

综述

多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。综述

动态规划可以解决管理中的最短路径、装载问题、库存问题、资源分配、生产过程最优化问题。§1.多阶段决策过程最优化问题举例

最短路径问题:最短路径问题的应用找出A到E的最短路径

阶段划分IIVIIIII将A到E的最短路径问题，转化为三个性质完全相同，但规模较小的子问题

求解策略记SE(x)为节点x到E的最短路求解S(D1)=5，S(D2)=2

S(C1)=8；S(C2)=7；S(C3)=12D1ED2E

S(C1)=8；S(C2)=7；S(C3)=12S(B1)=20；S(B2)=14；S(B3)=19最优解BACBDBCDEC212312312511214106104131211396581052052871220141919§2.基本概念、基本方程与最优化原理一、基本概念1.阶段:用动态规划方法求解问题时,首先将问题的全过程适当地分成若干个互相联系的阶段,以便能按一定的次序去解.划分的标准是时间或空间.§2.基本概念、基本方程与最优化原理2.状态.

状态是指每个阶段开始时所处的自然状态或客观条件.在例1中某个阶段的状态就是某个阶段的始点.S2={B1,B2,B3,B4}北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3§2.基本概念、基本方程与最优化原理3.决策.

决策是某一阶段内的抉择,第N阶段的决策与第N个阶段的状态有关,通常用Xn(Sn)表示第n阶段处于Sn状态时的决策量,而这个决策量又决定第n+1阶段的状态.北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)S1s2s3s4x1x2x3§2.基本概念、基本方程与最优化原理4.策略.由所有各阶段的决策函数序列称为全过程策略,简称策略,记为p1,n(s1),能够达到总体最优的策略叫做最优策略.从第K个阶段开始到最后阶段的决策组成的决策函数序列称为K子过程策略,简称K子策略,记为Pk,N(Sk)§2.基本概念、基本方程与最优化原理5.指标函数:指标函数是衡量全过程策略或K子过程策略优劣的数量指标,指标函数的最优值称之为最优指标函数,记作f1(S1)或fk(Sk)最短距离f1(s1),最大收益fk(sk)§2.基本概念、基本方程与最优化原理6.状态转移方程:已知第N+1阶段的状态是由第N阶段的状态和第N阶段的决策所决定的,用方程表示为:Sn+1=Tn(Sn,Xn)状态转移方程.§2.基本概念、基本方程与最优化原理二、基本方程：动态规划递归方程§2.基本概念、基本方程与最优化原理二、基本方程：动态规划递归方程§2.基本概念、基本方程与最优化原理二、基本方程：动态规划递归方程三、最优化原理与动态规划的基本方法Bellman原理动态规划的基本方法逆向顺序法前向顺序法Bellman原理示意图Bellman最优性原理“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策必然形成最优子策略”

.最优策略的子策略也是最优的.Bellman最优性原理最短路径的子路径仍然是最短路径。全长最优，那么部分仍然是最优。BACBDBCDEC212312312511214106104131211396581052052871220141919AB2C1D1EAB2C1D1A到E的最优是：是A到D1的最优四、动态规划建模与求解步骤建立动态规划模型的基本要求动态规划的求解步骤一、建立动态规划模型的基本要求将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假设。确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。状态变量应当满足无后效性要求。明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。二、动态规划的求解步骤正确划分阶段。确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。确定求解的递推顺序，给出状态转移方程。确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。递推求解。与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。建立动态规划模型及求解步骤划分阶段确定状态变量及允许状态集合确定决策变量及决策空间确定状态转移方程确定转移指标函数并建立递归方程

§3动态规划应用一、资源分配问题二、背包问题三、生产与存贮问题资源分配问题例2：某公司有4个推销员在北京、上海和广州三个市场推销货物，这三个市场里推销人员数与收益的关系如表所示：试做出使决收益最大的分配方案。北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3解：1。阶段划分。分成三个阶段，K=3；并按逆向编号。广州K=1，上海K=2北京K=3，分配推销员的优先顺序为北京上海广州.或按顺向编号。广州K=3，上海K=2北京K=1，分配推销员的优先顺序为北京上海广州.北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3解：2.确定状态量Sk。状态量Sk表示第K阶段初未分配的推销员数.显然S1=4；S2,S3的取值为0--43.确定决策变量Xk.决策变量Xk表示分配给第K阶段市场的推销数.显然Xk<=Sk.北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3解：4.确定状态转移方程Sk。根据前面的定义:Sk+1=Sk-Xk

期末=期初-本期发生额

5.确定直接效果函数dk(Sk,Xk).它表示第K阶段初有推销员数SK,分配给第K市场XK个推销员时所产生的直接效益,这些效益指标由于表1给出.北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3解：6.确定最优指标函数。由于三个市场的总收益等于三个市场的收益之和.所以最优指标函数为:北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3解：7.确定边界:fn+1(xn+1)=0f4(x4)=f4(s4)=0北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3各阶段计算过程如下:

第3阶段:S3=0,1,2,3,4f3(s3)=max{d3(s3,x3)+f4(s4)}=max{d3(s3,x3)}f3(0)=50,f3(1)=61,f3(2)=72,f3(3)=84,f3(4)=84各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4f2(s2)=max{d2(s2,x2)+f3(s3)}f2(0)=max{d2(0,x2)+f3(0)}=40+50=90f2(1)=max{d2(1,x2)+f3(s3)}d2(1,0)+f3(1)d2(1,1)+f3(0)=max40+6150+50=max=101各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4f2(s2)=max{d2(s2,x2)+f3(s3)}f2(2)=max{d2(2,x2)+f3(s3)}d2(2,0)+f3(2)d2(2,1)+f3(1)=max40+7250+61=max=112d2(2,2)+f3(0)60+50各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4f2(s2)=max{d2(s2,x2)+f3(s3)}f2(3)=max{d2(3,x2)+f3(s3)}d2(3,0)+f3(3)d2(3,1)+f3(1)=max40+8450+72=max=124d2(3,2)+f3(0)60+61d2(3,1)+f3(2)71+50各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4f2(s2)=max{d2(s2,x2)+f3(s3)}f2(4)=max{d2(4,x2)+f3(s3)}d2(4,1)+f3(3)d2(4,3)+f3(1)=max40+8450+84=max=134d2(4,4)+f3(0)60+72d2(4,2)+f3(2)71+61d2(4,0)+f3(4)82+50各阶段计算过程如下:

第1阶段:S3=4f1(s1)=max{d1(s1,x1)+f2(s2)}f1(4)=max{d1(4,x1)+f2(s2)}d1(4,1)+f2(3)d1(4,3)+f2(1)=max20+13432+124=max=159d1(4,4)+f2(0)47+112d1(4,2)+f2(2)57+101d1(4,0)+f2(4)66+90分配方案:北京市场2个推销员,上海0个,广州市场2个推销员,总收益为159单位元.资源分配问题有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）的关系见下表：求对三个项目的最优投资分配，使总投资效益最大。

项目A项目B项目C指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3阶段k：每投资一个项目作为一个阶段；状态变量sk：投资第k个项目前的资金余额；决策变量xk：第k个项目的投资额；决策允许集合：Dk(sk)={0≤xk≤sk}状态转移方程：sk+1=sk-xk阶段指标：vk(sk,xk)见表中所示；递推方程：fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}终端条件：f4(s4)=0k=4，f4(s4)=0;k=3，0≤x3≤s3，s4=s3-x3

k=2，0≤x2≤s2，s3=s2-x2

k=1，0≤x1≤s1，s2=s1-x1

最优解为:s1=4,x1*=1,s2=s1-x1=3,x2*=0,最大效益为60万吨s3=s2-x2*=3,x3*=3,s4=s3-x3=0机器负荷分配问题某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。

第1年s1s2s3x1x2x3第2年第3年第4年第5年s4s5s6x4x5指标值(产量)V1(s1,x1)指标值(产量)V2(s2,x2)指标值(产量)V5(s5,x5)指标值(产量)V4(s4,x4)指标值(产量)V3(s3,x3)动态规划模型构造阶段k：

运行年份（k=1,2,3,4,5,6）；状态变量xk：

第k年初完好的机器数（k=1,2,3,4,5,6）；决策变量dk：

第k年投入高负荷运行的机器数；状态转移方程：sk+1=0.7xk+0.9(sk-xk)决策允许集合：Dk(sk)={xk|0

xk

sk}阶段指标：vk(sk,xk)=8xk+5(sk-xk)终端条件：f6(s6)=0递推方程：

fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}

xk

Dk(sk) =max{8xk+5(sk-xk)+fk+1[0.7xk+0.9(sk-xk)]}

0

xk

sk第5年s5s6x5指标值(产量)V5(s5,x5)…+f6(s6)第4年s4s5x4指标值(产量)V4(s4,x4)…+f5(s5)f3(s3)=max{8x3+5(s3-x3)+f4(s4)}

0

x3

s3=max{8x3+5(s3-x3)+13.7s4}

0x3

s3=max{8d3+5(s3-d3)+13.7[0.7d3+0.9(s3-d3)]}0x3

s3=max{0.28x3+17.24s3}=17.52s30x3

s3

x3*=s3s3x3第3年s4指标值(产量)V3(s3,x3)…+f4(s4)f2(s2)=max{8x2+5(s2-x2)+f3(s3)}

0

x2

s2=max{8x2+5(s2-x2)+17.52s3}

0x2

s2=max{8x2+5(s2-x2)+17.52[0.7x2+0.9(s2-x2)]}

0x2

s2=max{-0.504x2+20.77s2}=20.77s2

0x2

s2x2*=0s2s3x2第2年指标值(产量)V2(s2,x2)…+f3(s3)f1(s1)=max{8x1+5(s1-x1)+f2(s2)}

0

x1

s1=max{8x1+5(s1-x1)+20.77s2}

0x1

s1=max{8x1+5(s1-x1)+20.77[0.7x1+0.9(s1-x1)]}

0x1

s1=max{-0.05x1+23.69s1}=23.69s1

0x1

s1x1*=0第1年s1s2x1指标值(产量)V1(s1,x1)…+f2(s2)由此可以得到：

f1(s1)=23.69s1, x1*=0

f2(s2)=20.77s2, x2*=0 f3(s3)=17.52s3, x3*=s3

f4(s4)=13.60s4, x4*=s4 f5(s5)=8s5 x5*=s5用s1=1000代入，得到五年最大产量为

f1(s1)=f1(1000)=23690每年投入高负荷运行的机器数以及每年初完好的机器数为：

s1=1000

x1*=0, s2=0.7x1+0.9(s1-x1)=900

x2*=0, s3=0.7x2+0.9(s2-x2)=810

x3*=s3=810, s4=0.7x3+0.9(s3-x3)=567

x4*=s4=567, s5=0.7x4+0.9(s4-x4)=397

x5*=s5=397, s6=0.7x5+0.9(s5-x5)=278生产－库存问题一个工厂生产某种产品，1～7月份生产成本和产品需求量的变化情况如下表：为了调节生产生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低.。

阶段k：月份，k=1,2,…,7,8；状态变量sk：第k个月初（发货以前）的库存量；决策变量xk：第k个月的生产量；状态转移方程：sk+1=sk-rk+xk；决策允许集合：Dk(sk)={xk

|xk

0,rk+1

sk+1

H} ={xk

|xk

0,rk+1

sk-rk+xk

H}；阶段指标：vk(sk,xk)=ckxk；终端条件：f8(s8)=0, s8=0；递推方程：fk(sk)=min{vk(sk,xk)+fk+1(sk+1)}

xk

Dk(sk) =min{ckxk+fk+1(sk-rk+xk)}

xk

Dk(sk)三、生产存储问题某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。时期（月）需求量（dk）12342324已知的其它条件已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。设第k月的生产量uk，存储量为Sk,则总成本为建立数学模型以月划分阶段，k=1,2,3,4各阶段决策变量为该阶段生产量uk，状态变量为该阶段存储量Sk。需求dk采用逆序算法，则状态转移方程为最低成本递推公式是第四阶段的最优解当k=4时，d4=4,因第四阶段末无存货，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生产存储01234432107654000.511.5276.565.52000000000076.565.52第三阶段最优解当k=3时，由于，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6)S3u3本期成本C3S4f4(S4)f3(S3)生产存储0234565678900000567890123476.565.521212.51313.511第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生产存储112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生产存储2012340456711111156780123476.565.52811.512.012.510.0第三阶段最优解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生产存储3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第三阶段最优解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生产存储501042.52.52.56.5345.5288.560033425第二阶段最优解当k=2时，d2=3，由于最生产能力为6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生产存储03456678900006789012311.010.58.08.01717.51617第二阶段最优解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生产存储123456567890.50.50.50.50.55.56.57.58.59.50123