管理运筹学讲义动态规划

管理运筹学讲义动态规划第1页，共47页，2023年，2月20日，星期二第七章动态规划动态规划DynamicProgramming研究多阶段决策的最优化问题的方法。多阶段决策问题含有一个描述过程时序或空间演变的阶段变量，将复杂问题划分成若干阶段，根据“最优性原理”，逐段解决而最终实现全局最优。经济、管理、工业生产、工程技术等领域，许多问题可归结为多阶段决策问题。一些用线性规划、非线性规划处理有困难的问题，往往可以用动态规划方便地求解。动态规划是美国运筹学家贝尔曼(R.Bellman)等人1959年提出的。2第2页，共47页，2023年，2月20日，星期二第一节多阶段决策问题多阶段决策：经济管理决策中，有些管理决策问题可以按时序或空间演变划分成多个阶段，呈现出明显的阶段性；于是可把这类决策问题分解成几个相互联系的阶段，每个阶段即为一个子问题；原有问题的求解就化为逐个求解几个简单的阶段子问题；每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。

例如：企业生产物流：可分为物料供应、生产制造、分销零售等阶段。最短路问题：可以按空间顺序划分阶段。一、问题的提出

3第3页，共47页，2023年，2月20日，星期二第一节多阶段决策问题从生产厂Q到某公司T选择那条路线,使总运费最低(路程最短)？最短路问题QTA1A2A3B1B2B3C1C124374642442514633334生产商某公司出口港进口港城市阶段1阶段2阶段3阶段44第4页，共47页，2023年，2月20日，星期二第一节多阶段决策问题这是一个多阶段决策问题，它可分为四个阶段：第一阶段：从Q(制造厂)到A(出口港)；第二阶段：从A(出口港)到B(进口港)；第三阶段：从B(进口港)到C(城市)；第四阶段：从C(城市)到T(某公司)。每个阶段选取的路线不同，对应从Q到T就有一系列不同的运输路线:从始点Q到终点T共有3×3×2×1=18条不同路线现在的问题是如何选择一条费用最小的路线？5第5页，共47页，2023年，2月20日，星期二例一、从A

地到D

地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114二、最短路径问题第6页，共47页，2023年，2月20日，星期二

解：整个计算过程分三个阶段，从最后一个阶段开始。

第一阶段（C→D）：C

有三条路线到终点D

。

AB1B2C1C2C3D24333321114DC1C2C3显然有f1(C1)

=1；

f1(C2)

=3；

f1(C3)

=4

7第7页，共47页，2023年，2月20日，星期二

d(B1,C1)+f1(C1)

3+1f2(B1)=mind(B1,C2

)+f1(C2)

=min3+3

d(B1,C3)+f1(C3)1+44=min6=45第二阶段（B→C）：B到C

有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B1→C1→D)8第8页，共47页，2023年，2月20日，星期二

d(B2,C1)+f1(C1)

2+1f2(B2)=mind(B2,C2

)+f1(C2)

=min3+3

d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B2→C1→D)9第9页，共47页，2023年，2月20日，星期二第三阶段（

A→B

）：A到B有二条路线。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路线为A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A10第10页，共47页，2023年，2月20日，星期二AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为A→B1→C1→D

路长为611第11页，共47页，2023年，2月20日，星期二第一节多阶段决策问题最短路径：Q→A3→B1→C1→T二、动态规划的标号法

QTA1A2A3B1B2B3C1C224374642442514633334阶段1阶段2阶段3阶段403,T4,T4,C17,C26,C111,B1,B28,B18,B111,A312第12页，共47页，2023年，2月20日，星期二第一节多阶段决策问题最短路的基本特征从始点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。三、多阶段决策的基本特征

13第13页，共47页，2023年，2月20日，星期二第二节动态规划原理阶段(stage)处理多阶段决策，需将全过程划为若干阶段，每个阶段进行一次抉择。各阶段按一定顺序联接在一起组成统一的整体。用k表示阶段变量。阶段编号顺序编号逆序编号一、动态规划的基本概念

14第14页，共47页，2023年，2月20日，星期二第二节动态规划原理状态(state)状态表示过程发展中某阶段的起始状况。过程的发展可以通过各阶段状态的演变来描述。状态可用一个变量来描述，称为状态变量，用Sk表示。选取的状态变量必须满足无后效性。某阶段的状态给定后，则过程未来发展不受该阶段以前各阶段状态的影响。

第k

阶段可能有若干状态，用Sk表示阶段k的状态集合，sk(i)表示第k阶段的第i

个状态。15第15页，共47页，2023年，2月20日，星期二第二节动态规划原理决策(decision)从上一阶段某状态演变到下一阶段某状态要作一次选择，称为决策。用变量xk(sk)表示第k阶段状态为sk时的决策，称为决策变量，简记xk决策变量的取值被限制在某一范围内，此范围称为允许决策集合Xk(sk)

16第16页，共47页，2023年，2月20日，星期二第二节动态规划原理策略(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。17第17页，共47页，2023年，2月20日，星期二第二节动态规划原理状态转移方程下一阶段状态sk+1是本阶段状态变量sk和决策变量xk的函数，即sk+1=T(sk,xk(sk))=T(sk,xk)从状态sk出发到下一阶段状态sk+1的转移规律称为状态转移方程。18第18页，共47页，2023年，2月20日，星期二第二节动态规划原理指标函数用来衡量每一阶段决策效果的优劣的数量指标，称为阶段指标函数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。19第19页，共47页，2023年，2月20日，星期二第二节动态规划原理逆序算法：逆着阶段顺序的方向，由后向前推算。把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实际过程的进展方向逐段求解；在每一阶段求解过程中都是其后部子过程最优策略的基础上，再考虑本阶段的指标函数，求出本阶段的最优策略；直到第一阶段为止。最优性原理：美国运筹学家贝尔曼提出无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。将决策问题划分为若干个阶段，全过程的优化问题就分解为子过程的优化问题，由后向前逐步倒推，最优化的子过程逐渐成为全过程最优。作为全过程的最优策略P*1,n的组成部分的任一子策略P*k,n(Sk)，一定是从状态Sk

出发直至终点的最优策略。二、动态规划方法的基本思路

20第20页，共47页，2023年，2月20日，星期二第二节动态规划原理基本递推方程据最优性原理，阶段k的阶段指标vk(sk,xk)加上(或乘以)从下一阶段k+1开始到过程结束采取最优策略取得的最优指标函数值fk+1(sk+1)，再从中选出最优，便是阶段k从状态sk出发到全过程结束的最优指标函数值。21第21页，共47页，2023年，2月20日，星期二第二节动态规划原理阶段1阶段2阶段k阶段k+1阶段n……状态S1决策x1状态S2v1决策x2状态S3v2决策xk状态Sk+1vk决策xk+1vk+1决策xnvn寻求最优解的方向22第22页，共47页，2023年，2月20日，星期二第二节动态规划原理建模步骤（小结）对问题进行阶段划分，确定阶段变量k确定状态变量sk确定决策变量xk

、允许决策集合Xk(sk)写出状态转移方程sk+1=Tk(sk,xk)写出指标函数的基本递推方程明确边界条件动态规划模型分类三、动态规划模型

过程变量确定随机离散连续离散确定型离散随机型连续确定型连续随机型23第23页，共47页，2023年，2月20日，星期二第三节应用举例资源分配问题：把有限的资源(如资金、材料、设备、人力等)分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。资源可以有一种或若干种，只有一种资源可供分配的问题称之为一维资源分配问题。一维资源分配问题一、资源分配问题

设备台数分厂0123456I0356765II04678910III0259887如何分配设备，可使获利最大？各分厂在不同设备台数下所获利润24第24页，共47页，2023年，2月20日，星期二第三节应用举例动态规划的数学模型将三个分厂看作是三个阶段，即阶段变量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开始到最后阶段采用最优分配策略取得的最大的效益值;递推方程函数式25第25页，共47页，2023年，2月20日，星期二第三节应用举例逆序求解K=3x3s3v3

(s3,x3)f3

(s3)x3*第III分厂在不同设备台数下所获利润0123456012345600202502590259802598802598870259999012333326第26页，共47页，2023年，2月20日，星期二第三节应用举例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+027第27页，共47页，2023年，2月20日，星期二第三节应用举例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+028第28页，共47页，2023年，2月20日，星期二第三节应用举例企业一年中的产品生产往往是分期分批生产的。组织每批产品的生产，都要花费一些生产准备费和存贮费用。若某一时期增大生产批量则可减少生产批次，从而降低生产成本。与此同时，批量大了，必然增加库存而使存贮费用增加。在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。二、生产与存储问题

29第29页，共47页，2023年，2月20日，星期二第三节应用举例例，某工厂与用户签订了4个月的交货合同如表所示

该厂生产能力为每月5件，该厂仓库的存货能力为4件。已知生产费用为c=1千元/件，在进行生产的月份，工厂要支出固定费用b=2千元，每月仓库保管费用h=0.2千元/件/月。假定开始时及4月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小？月1234需求量dk(件)323230第30页，共47页，2023年，2月20日，星期二第三节应用举例动态规划的数学模型每个月为一个阶段，即阶段变量k=1,2,3,4分别表示这四个月;状态变量sk表示第k

月初的产品库存量，0≤sk≤4;决策变量xk表示第k月的生产量，允许决策集合Xk(sk)={xk︱0≤

xk

≤5};状态转移方程为sk+1=sk+xk

–

dk;阶段指标vk(sk,xk)表示第k月的费用：本月若不安排生产，则仅需支出保管费；本月若安排生产，则需支出生产费用和固定费，同时还需交付保管费。当xk

=0时，vk(sk,xk)=h·sk=0.2sk当xk

＞0时，vk(sk,xk)=b+c·xk+h·sk=2+xk+0.2sk

最优指数函数fk(sk)表示第k阶段从sk开始到最后阶段采用最优生产策略实现的最低生产费用;31第31页，共47页，2023年，2月20日，星期二第三节应用举例逆序求解K=4x4s4v4

(s4,x4)=0.2

s4v4

(s4,x4)=2+

x4+0.2

s4f4(s4)x4*012012----4--3.2--0.4----43.20.4210d4=2，4月末无库存则s5=0，状态转移方程s5=s4+

x4–d4，则s4=

d4–x4=

2–x4x4≥0,则s4=

2–x4={0,1,2}s4≥0,则x4=

2–s4={0,1,2}32第32页，共47页，2023年，2月20日，星期二第三节应用举例k=3x3s30.2

s3+f4(s4)v3

(s3,x3)+f4(s4)=2+

x3+0.2

s3+f4(s4)f3(s3)x3*012340123457.46.65.84.64.254300-----9.09.27.4----8.28.46.6----7.47.65.8----4.66.85.0------44.2--------d3=3，0≤s4≤

2，状态转移方程s4=s3+

x3–d3，则0≤

s3+

x3–

d3

≤

2，即3≤

s3+

x3≤

50≤s3≤4，则s3={0,1,2,3,4}生产能力限制0≤x3≤

5，则x3={0,1,2,3,4,5}4月在库存量为s4下的最低生产成本33第33页，共47页，2023年，2月20日，星期二第三节应用举例k=2x2s20.2

s2+f3(s3)v2

(s2,x2)+f3(s3)=2+

x2+0.2

s2+f3(s3)f2

(s2)x2*01201234511.410.67.8210----11.411.611.811.6--10.610.811.010.811.27.810.010.210.010.4--d2=2，0≤s3≤

4，状态转移方程s3=s2+

x2–d2，则0≤

s2+

x2–

d2≤

4，即2≤

s2+

x2≤

6s1=0，则s2=s1+

x1–d1=x1–3；

x1

≤5，则s2≤2生产能力限制0≤x2≤

5，则x2={0,1,2,3,4,5}3月在库存量为s3下的最低生产成本34第34页，共47页，2023年，2月20日，星期二第三节应用举例k=1x1s1v1

(s1,x1)+f2(s2)=2+

x2+0.2

s2+f2(s2)f1

(s1)x1*3452月在库存量为s2下的最低生产成本014.85顺序递推，得出结论第1月生产5万件s2=s1+

x1–d1=0+5-3=2，第2月不生产s3=s2+

x2–d2=2+0-2=0，第3月生产5万件s4=s3+

x3–d3=0+5-3=2，第4月不生产16.416.614.8d1=3，s1=0，状态转移方程则s2=s1+

x1–d1=x1–3；s2≥0，则x1

≥

3，生产能力限制x1≤

5，则3≤

x1

≤5，x1={3,4,5}35第35页，共47页，2023年，2月20日，星期二第三节应用举例有一种设备可以在高低两种不同的负荷下运行，在高负荷下生产时，产品的年产量Q1与投入生产的设备台数x1的关系为：Q1=9x1

，年完好率(折损后)a=0.75；在低负荷下生产时，年产量Q2与投入生产的设备台数x2的关系为:Q2=6x2

，年完好率为b=0.96，若开始时拥有完好机器台数为100台，要求制定一个4年计划，在每年初时应决定如何重新分配设备在高低不同的负荷下生产，使得4年内产品的总产量达到最高。三、机器负荷问题

36第36页，共47页，2023年，2月20日，星期二第三节应用举例动态规划的数学模型每年为一个阶段，即阶段变量k=1,2,3,4;状态变量sk表示第k年初所拥有的完好机器台数，s1=100;决策变量xk表示第k年投入高负荷生产的机器数，允许决策集合Xk(sk)={xk︱0≤

xk

≤sk};状态转移方程为sk+1=axk+b(sk

–

xk)=0.75xk+0.96(sk

–

xk)=0.96sk–0.21xk;阶段指标vk(sk,xk)表示第k年的产量：vk(sk,xk)=9xk+6(sk

–

xk)=6sk+3xk;最优指数函数fk(sk)表示第k阶段从sk开始到最后阶段采用最优分配策略实现的最大产量;37第37页，共47页，2023年，2月20日，星期二第三节应用举例K=4f4(s4)是关于x4

的单增函数，故x*4=s4

时，f4(s4)最大，f4(s4)=9s4K=3f3(s3)是关于x3

的单增函数，故x*3=s3

时，f3(s3)最大，f3(s3)=15.75s338第38页，共47页，2023年，2月20日，星期二第三节应用举例K=2f2(s2)是关于x2的单减函数，故x*2=0

时，f2(s2