西安电子科技大学数学建模讲义.pptx

数学建模专题讲座数学建模专题讲座最优化模型最优化模型 -动态规划动态规划动态规划 1 动态规划的基本概念和方法动态规划的基本概念和方法基本概念与名词解释基本概念与名词解释最优化原理与动态规划的基本方法最优化原理与动态规划的基本方法 2 动态规划模型的建立与求解步骤动态规划模型的建立与求解步骤 建立动态规划模型的基本要求建立动态规划模型的基本要求动态规划的求解步骤动态规划的求解步骤 3 动态规划的应用举例动态规划的应用举例定价问题定价问题资源分配问题资源分配问题生产存储问题生产存储问题第一节第一节 动态规划的基本概念与方法动态规划的基本概念与方法1 1 动态规划的基本概念动态规划的基本概念一、动态决策问题：一、动态决策问题：决决策策过过程程具具有有阶阶段段性性和和时时序序性性(与与时时间间有有关关)的的决决策问题。即决策过程可划分为明显的阶段。策问题。即决策过程可划分为明显的阶段。二、什么叫动态规划二、什么叫动态规划(D.P.(D.P.Dynamic Program)Dynamic Program)：多阶段决策问题最优化的一种方法。多阶段决策问题最优化的一种方法。广广泛泛应应用用于于工工业业技技术术、生生产产管管理理、企企业业管管理理、经经济、军事等领域。济、军事等领域。三、动态规划三、动态规划(D.P.)(D.P.)的起源：的起源：19511951年年,美美国国数数学学家家R.Bellman(R.Bellman(贝贝尔尔曼曼)等等人人提提出出最最优优化化原原理理，从从而而建建立立动动态态规规划划，他他的的名名著著动动态态规规划划于于19571957年出版。年出版。四、动态决策问题分类：四、动态决策问题分类：1 1、按数据给出的形式分为：、按数据给出的形式分为：离散型动态决策问题。离散型动态决策问题。连续型动态决策问题。连续型动态决策问题。2 2、按决策过程演变的性质、按决策过程演变的性质分为：分为：确定型动态决策问题。确定型动态决策问题。随机型动态决策问题。随机型动态决策问题。名词解释l例例1 某公司欲将一批货物从城市某公司欲将一批货物从城市A运到城市运到城市E去，去，如图所示，走哪条路线最好如图所示，走哪条路线最好？1、阶段、阶段(stage)k：把所给问题的过程，恰当地分成若把所给问题的过程，恰当地分成若干个相互联系的阶段。描述阶段的变量称为阶段变量，干个相互联系的阶段。描述阶段的变量称为阶段变量，常用常用k表示。表示。k=1、2、3、4。2、状态、状态(state)Sk：状态表示每个阶段开始所处的状态：状态表示每个阶段开始所处的状态,即是每一阶段的出发位置即是每一阶段的出发位置.阶段的起点阶段的起点.通常一个阶段通常一个阶段有多个状态有多个状态.记为记为Sk.S1=A，S2=B1,B2,B3，S3=C1,C2,C3,S4=D1,D2。3、决策、决策(decision)uk(sk)：从一个阶段某状态演变到下一个阶段某：从一个阶段某状态演变到下一个阶段某状态的选择状态的选择.常用常用uk(sk)表示第表示第k阶段当状态处于阶段当状态处于sk时的决策变量时的决策变量.决决策集用策集用Dn(Sk)表示表示.就是就是阶段的终点阶段的终点.D1(S1)=u1(A)=B1,B2,B3=S2，D2(S2)=U2(B1),U2(B2),U2(B3)=C1,C2;C1,C2,C3;C2,C3 =C1,C2,C3=S3，D3(S3)=U3(C1),U3(C2),U3(C3)=D1,D2;D1,D2,D3;D1,D2,D3 =D1,D2,D3=S4，D4(S4)=U4(D1),U4(D2),U4(D3)=E1,E2;E1,E2;E1,E2 =E1,E2=S5，D5(S5)=X5(E1),X5(E2)=F;F=F。4 4、策略策略(policy)：全过程中各个阶段的决策：全过程中各个阶段的决策Un组成的有序总体组成的有序总体 Un.如如 A B2 C1 D1 E 5、子策略、子策略(sub-policy)：剩下的：剩下的M个阶段构成个阶段构成M子过程子过程,相应的相应的 决策系列叫决策系列叫M子策略子策略.如如 C1 D1 E6、状态转移方程：前一阶段的终点、状态转移方程：前一阶段的终点(决策决策)是后前一阶段的起点是后前一阶段的起点 (状态状态).UkSk+17、指标函数：各个阶段的数量指标、指标函数：各个阶段的数量指标,记为记为Vk,n(sk,Uk).如上例中如上例中,用用dk(sk,Uk)表示距离表示距离.d2(B3,C2)=8,d3(C2,D2)=2 等等.8、目标函数、目标函数:策略的数量指标值策略的数量指标值,记为记为 Z=optv1(s1,u1)*vn(sn,un).其中：其中：opt为为max或或min，*为运算符号为运算符号.如上例中，如上例中，Z=mind1(s1,u1)+dn(sn,un)=mind1+d2+dn 一、一、R.Bellman最优化原理：最优化原理：作作为为整整个个过过程程的的最最优优策策略略，无无论论过过去去的的状状态态和和决决策策如如何何，对对前前面面的的决决策策形形成成状状态态而而言言，余余下的诸决策必构成最优策略。下的诸决策必构成最优策略。即即：若若M是是从从A到到B最最优优路路线线上上的的任任一一点点，则从则从M到到B的路线也是最优路线。的路线也是最优路线。A MB最优化原理最优化原理二、指标递推方程：二、指标递推方程：fn*(Sn)=opt vn(sn,un)*vn(sn,un),xnDn(Sn)如上例：如上例：fn*(Sn)=min vn(sn,un)+fn+1*(Sn+1),n=3、2、1 xnDn(Sn)f4*(S4)=min v4(s4,u4)x4D4(S4)三、求解过程：三、求解过程：用用反反向向嵌嵌套套递递推推法法：从从最最后后一一个个阶阶段段开开始始，依依次次对对各各子子过过程程寻寻优优，直直至至获获得得全全过过程程的的最最优优，形成最优策略，获得最优策略指标值。形成最优策略，获得最优策略指标值。一、建立动态规划模型的基本要求一、建立动态规划模型的基本要求l将问题划分成若干阶段。有的问题的阶段性将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假很明显，有的则不明显，需要分析后人为假设。设。l确定各阶段的状态变量，并给出状态转移方确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一程，状态转移方程的形式应当与递推顺序一致。致。l状态变量应当满足无后效性要求。状态变量应当满足无后效性要求。l明确指标函数，给出最优函数递推方程，递明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。推方程的形式应当与递推顺序一致。二、动态规划的求解步骤二、动态规划的求解步骤l正确划分阶段。正确划分阶段。l确定状态变量和决策变量，并给出状态变确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。量和决策变量的可行集合。l确定求解的递推顺序，给出状态转移方程。确定求解的递推顺序，给出状态转移方程。l确定阶段、子过程确定阶段、子过程(子策略子策略)的指标函数，确的指标函数，确定最优值函数的递推方程和边界条件。定最优值函数的递推方程和边界条件。l递推求解。递推求解。l与递推过程反向求出最优策略与递推过程反向求出最优策略(最优决策变最优决策变量值系列量值系列)和最优状态变化路线。和最优状态变化路线。例例2 2：求下列图中：求下列图中A A到到F F的最短路线及最短路线值。的最短路线及最短路线值。AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141 1、阶段、阶段(stage)n(stage)n：n=1n=1、2 2、3 3、4 4、5 5。2 2状态、状态(state)S(state)Sn n：S S1 1=A=A，S S2 2=B=B1 1,B,B2 2,B,B3 3，S S3 3=C=C1 1,C,C2 2,C,C3 3，S S4 4=D=D1 1,D,D2 2,D,D3 3，S S5 5=E=E1 1,E,E2 2。3 3、决策、决策(decision)X(decision)Xn n：决策集：决策集D Dn n(S(Sn n)。D D1 1(S(S1 1)=X)=X1 1(A)=B(A)=B1 1,B,B2 2,B,B3 3=S=S2 2，D D2 2(S(S2 2)=X)=X2 2(B(B1 1),X),X2 2(B(B2 2),X),X2 2(B(B3 3)=C)=C1 1,C,C2 2;C;C1 1,C,C2 2,C,C3 3;C;C2 2,C,C3 3 =C =C1 1,C,C2 2,C,C3 3=S=S3 3，D D3 3(S(S3 3)=X)=X3 3(C(C1 1),X),X3 3(C(C2 2),X),X3 3(C(C3 3)=D =D1 1,D,D2 2;D;D1 1,D,D2 2,D,D3 3;D;D1 1,D,D2 2,D,D3 3=D=D1 1,D,D2 2,D,D3 3=S=S4 4，D D4 4(S(S4 4)=X)=X4 4(D(D1 1),X),X4 4(D(D2 2),X),X4 4(D(D3 3)=E)=E1 1,E,E2 2;E;E1 1,E,E2 2;E;E1 1,E,E2 2=E=E1 1,E,E2 2=S=S5 5，D D5 5(S(S5 5)=X)=X5 5(E(E1 1),X(E),X(E2 2)=F;F=F)=F;F=F。AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144、状态转移方程：、状态转移方程：Xn=Sn+15、指标函数、指标函数(距离距离)：dn(sn,xn).d2(B3,C2)=1,d3(C2,D3)=6 等。等。6、指标递推方程：、指标递推方程：fn*(Sn)=min dn(sn,Xn)+fn+1*(Sn+1)，n=4、3、2、1 UnDn(Sn)f5*(S5)=min V5(s5,X5)X5D5(S5)AB1B2B3C1C2C3D1D2D3E1E2F3549543517158464422269751411F22F4+1=52+2=44 E26+1=79+2=117E17+1=85+2=77E2AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141+4=55+7=12 /5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16 /14C14+5=93+11=145+8=139C1 /1+11=127+8=15 12C2AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143+14=175+9=144+12=16 14B2最短路线值为：最短路线值为：f f1 1*(s(s1 1)=14)=14最短路线求解如下：最短路线求解如下：11F22F4+1=52+2=44 E26+1=79+2=117E17+1=85+2=77E21+4=55+7=12 /5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16 /14C14+5=93+11=145+8=139C1 /1+11=127+8=15 12C23+14=175+9=144+12=16 14B2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即：即：A B2 C1 D1 E2 F 第三节第三节 动态规划的应用举例动态规划的应用举例l定价问题定价问题l资源分配问题资源分配问题l生产存储问题生产存储问题一、定价问题一、定价问题l某公司考虑为某新产品定价，该产品的单价拟从某公司考虑为某新产品定价，该产品的单价拟从每件每件5元、元、6元、元、7元和元和8元这四个中选取一个，每元这四个中选取一个，每年允许价格有年允许价格有1元幅度的变动，该产品预计畅销元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表五年，据预测不同价格下各年的利润如表3-1所示。所示。表表3-2 每年预计利润额每年预计利润额单价第一年 第二年 第三年 第四年 第五年5元6元7元8元1012141612131415151616152020181425241814建立数学模型l按年划分阶段，按年划分阶段，k=1,2,.,5l每阶段的状态变量为本年每阶段的状态变量为本年(上一年已确定上一年已确定)的价格，的价格，状态变量的可行集合状态变量的可行集合Sk=(5,6,7,8)。l决策变量为每年依据当年价格为下一年度决定价决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是：格，根据题意决策变量的可行集合是：l采用逆序算法，因此状态转移方程是采用逆序算法，因此状态转移方程是l最优值函数递推方程为最优值函数递推方程为进行各阶段的计算进行各阶段的计算l采用逆序法，设采用逆序法，设 l当当k=5时，时，S5=(5,6,7,8)，由表，由表3-1得到得到l当当k=4时，时，S4=(5,6,7,8)，由递推方程，由递推方程l得得继续求解继续求解l同理得其它各阶段的最优解同理得其它各阶段的最优解反推得最优路线反推得最优路线l按照与求最优值函数方向相反的顺序求按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。即从第最优状态路线：最优决策变量。即从第一年单价应为一年单价应为8元开始，向后推算。元开始，向后推算。l得第二年定价得第二年定价8元，第三年定价元，第三年定价7元，第元，第四年定价四年定价6元，第五年定价元，第五年定价5元。元。l最大利润值为最大利润值为92万元。万元。也可用决策图求解二、资源分配问题二、资源分配问题l某公司将某公司将5台加工中心分配给甲、乙、丙、丁四台加工中心分配给甲、乙、丙、丁四个工厂，各工厂利用设备后可产生如表个工厂，各工厂利用设备后可产生如表3-2所示所示的利润，应怎么分配设备可使公司总利润最大的利润，应怎么分配设备可使公司总利润最大？工厂设备数甲乙丙丁012345067101215037912130510111111046111212建立数学模型建立数学模型l按工厂次序划分阶段，按工厂次序划分阶段，k=1，2，3，4l状态变量为各阶段可用于分配的设备总台数状态变量为各阶段可用于分配的设备总台数l决策变量是分配给第决策变量是分配给第k工厂的设备数工厂的设备数l采用逆序算法，状态转移方程采用逆序算法，状态转移方程l最优值函数递推方程最优值函数递推方程第4阶段的最优解l当k=4时，S4=(0,1,2,3,4,5)012345012345046111212046111212012345第第3阶段的最优解阶段的最优解l当当k=3时，时，S3=(0,1,2)000000010105404551201205106406910102第3阶段的最优解（续）l当k=3时，S3=3301230510111164011111411142第3阶段的最优解（续）l当k=3时，S3=44012340510111112116401216161511161，2第3阶段的最优解（续）l当k=3时，S3=550123450510111111121211640121721171511212第2阶段的最优解l当k=2时，S2=(0,1,2)000000010103505350201203710501087100第2阶段的最优解（续）k=2时，S2=33012303791410501413129140第2阶段的最优解（续）当k2时，S2=4401234037912161410501617171412171，2第2阶段的最优解（续）当k=2时，S2=55012345037912132116141050211921191715210，2第1阶段的最优解（续）当k=1时，S1=5 50123450671012152117141050212321201715231 反向求最佳状态路线方案一方案二工厂名分配设备数工厂名分配设备数甲乙丙丁1121甲乙丙丁1220三、生产存储问题三、生产存储问题l某公司生产并销售某产品。根据市场预某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表测，今后四个月的市场需求量如表3-7所所示。示。时期（月）需求量（dk）12342324已知的其它条件l已知生产一件产品的成本是已知生产一件产品的成本是1千元，每批产品千元，每批产品的生产准备成本是的生产准备成本是3千元，每月仅能生产一批，千元，每月仅能生产一批，每批每批6件。每件存储成本为件。每件存储成本为0.5千元，且第一个千元，且第一个月初无存货，第四个月末的存货要求为零。月初无存货，第四个月末的存货要求为零。求最优生产计划。求最优生产计划。l设第设第k月的生产量月的生产量uk，存储量为，存储量为Sk,则总成本为则总成本为建立数学模型l以月划分阶段，以月划分阶段，k=1,2,3,4l各阶段决策变量为该阶段生产量各阶段决策变量为该阶段生产量uk，状态变量，状态变量为该阶段存储量为该阶段存储量Sk。l采用逆序算法，则状态转移方程为采用逆序算法，则状态转移方程为l最低成本递推公式是最低成本递推公式是第四阶段的最优解第四阶段的最优解l当当k=4时，时，d4=4,因第四阶段末无存货，因第四阶段末无存货，因此因此S4=(0,1,2,3,4)S4u4本期成本本期成本C4S5f5(S5)f4(S4)生产生产存储存储01234432107654000.511.5276.565.52000000000076.565.52第三阶段最优解l当当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第二阶段最优解第二阶段最优解l当当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.50123411.010.58.08.08.016.51715.516.517.5第二阶段最优解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生产存储2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0第二阶段最优解:S2=3S2u2本期成本C2S3f3(S3)f2(S2)生产存储3012345604567891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5第二阶段最优解:S2=4S2u2本期成本C2S3f3(S3)f2(S2)生产存储4012345045678222222267891012345610.58.08.08.08.05.012.51415161715第一阶段最优解l当k=1时，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生产存储0234565678900000567890123416.015.515.012.512.52121.52220.521.5最优解l从第一阶段向后反推最优路线，总结可得从第一阶段向后反推最优路线，总结可得时期K期初存货期末存货最优生产量该期成本总成本SkSk+1123403043040506081.59220.512.5112