运筹学第五章动态规划课件.ppt

《运筹学第五章动态规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第五章动态规划课件.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学第五章动态规划第1页，此课件共86页哦 美国数学家贝尔曼美国数学家贝尔曼（Richard.Bellman)创始时间上个世纪上个世纪50年代年代创始人第2页，此课件共86页哦多阶段决策过程的最优化多阶段决策过程的最优化第一节第一节第3页，此课件共86页哦 动态规划是用来解决动态规划是用来解决多阶段决策过程多阶段决策过程最优化最优化的一种数量方法的一种数量方法 这类活动可以按这类活动可以按时间时间顺序分解成若干个相互联系顺序分解成若干个相互联系的阶段，每个阶段都有若干个方案可供选择的阶段，每个阶段都有若干个方案可供选择多阶段决策过程的多阶段决策过程的最优化的目标最优化的目标：达到整个活动过程

2、的总体效果最优达到整个活动过程的总体效果最优第4页，此课件共86页哦 系统的动态过程可以按照系统的动态过程可以按照时间时间进程分为进程分为状态状态相互相互联系而又相互区别的各个联系而又相互区别的各个阶段，阶段，每个阶段都要进行每个阶段都要进行决决策策,目的是使整个过程的决策达到最优效果。目的是使整个过程的决策达到最优效果。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策阶段阶段阶段阶段阶段阶段第5页，此课件共86页哦分类分类动态规划动态规划离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型 根据决策过程的根据决策过程的时间参数时间参数是离散的还是连续

3、的、是离散的还是连续的、过程的演变过程的演变是确定性的还是随机性的是确定性的还是随机性的第6页，此课件共86页哦 动态规划动态规划是求解某类问题的一种方法是求解某类问题的一种方法，是，是考察问题的一种途径，而考察问题的一种途径，而不是一种算法不是一种算法。必须对具体问题进行具体分析，运用动必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。后再用动态规划方法去求解。注意：注意：第7页，此课件共86页哦1.1.生产决策问题生产决策问题：企业在生产过程中，由于需求是：企业在生产过程中，由于需求是随时间变化的，因此企

4、业为了获得全年的最佳生产效随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地益，就要在整个生产过程中逐月或逐季度地根据库根据库存和需求决定生产计划。存和需求决定生产计划。多阶段决策问题的典型例子：多阶段决策问题的典型例子：第8页，此课件共86页哦 这时，机器的年完好率为这时，机器的年完好率为a，即如果年初完好机器的数量为，即如果年初完好机器的数量为u，到年终完好的机器就为到年终完好的机器就为au,0a1。在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产的机器数量和投入生产的机器数量u2的关系为的关系为 h=h(u2)假定开始生产时完好的

5、机器数量为假定开始生产时完好的机器数量为s s1 1。要求制定一个五年计划，。要求制定一个五年计划，在在每年开始时，决定如何重新分配每年开始时，决定如何重新分配完好的完好的机器在两种不同的负机器在两种不同的负荷下生产的数量荷下生产的数量，使在五年内产品的总产量达到最高。，使在五年内产品的总产量达到最高。相应的机器年完好率相应的机器年完好率b b,0,0b b11。2.2.机机器器负负荷荷分分配配问问题题：某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产产品品的的年年产产量量g和和投投入入生生产产的的机机器数量器数

6、量u1的关系为的关系为g=g(u1)第9页，此课件共86页哦 不包含时间因素的静态决策问题（本质上是不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。作为多阶段的决策问题用动态规划方法来解决。3.线性规划、非线性规划线性规划、非线性规划等静态的规划问题也可等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法以通过适当地引入阶段的概念，应用动态规划方法加以解决。加以解决。第10页，此课件共86页哦4.最短路问题最短路问题：给定一个交通网络图如下，其中两点之间的：给定一个交

7、通网络图如下，其中两点之间的数字表示距离（或花费），试求从数字表示距离（或花费），试求从A点到点到G点的最短距离点的最短距离（总费用最小）。（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643第11页，此课件共86页哦第二节第二节 基本概念和基本原理基本概念和基本原理12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策阶段阶段阶段阶段阶段阶段策略策略状态转移状态转移指标函数指标函数基本概念基本概念第12页，此课件共86页哦设从甘肃要铺一条煤气管道到北京，途中须经过三个省：陕西、设从甘肃要铺

8、一条煤气管道到北京，途中须经过三个省：陕西、山西、河北，每省设一个中间站。各省建站可供选择的地点及山西、河北，每省设一个中间站。各省建站可供选择的地点及各段距离如下图，现要求选择一条甘肃到北京的铺管线路各段距离如下图，现要求选择一条甘肃到北京的铺管线路 使使总距离最短。总距离最短。12345678910北京河北山西陕西甘肃8458961610967738423最短路问题多阶段决策问题135810路长=21146910路长=16每一个阶段的决策合在一起构成一个铺设方案每一个阶段的决策合在一起构成一个铺设方案铺设方案铺设方案1：铺设方案铺设方案2：一个策略每个策略对应一个路长每个策略对应一个路长寻

9、找寻找最优策略最优策略寻找路长最短的铺设方案寻找路长最短的铺设方案策略第13页，此课件共86页哦1、阶段阶段：12345678910北京河北山西陕西甘肃8458961610967738423如最短路问题：如最短路问题：问题分成4个阶段：通常用通常用k表示阶段表示阶段，是指对整个过是指对整个过程的自然划分程的自然划分k=1，2，3，412，13，145 8，7968，59，69，78，划分阶段的规则：根据时间顺序或空间特征来划分阶段根据时间顺序或空间特征来划分阶段目的：目的：以便按次序来解优化问题以便按次序来解优化问题线路：第一阶段，甘肃 陕西第三阶段：山西 河北 线路：k=1：k=3：第14页

10、，此课件共86页哦2、状态、状态：第一阶段的状态：第一阶段的状态：1第二阶段的状态：第二阶段的状态：234状态变量状态变量描述各阶段状态的变量描述各阶段状态的变量12345678910北京河北山西陕西甘肃8458961610967738423如最短路问题：sk第第k阶段的状态变量阶段的状态变量s4第4阶段的初始状态变量s4=第4阶段的初始状态为 8Sk=sk第第k阶段的状态集合阶段的状态集合S3=s3=，注：n个阶段的决策过程有个n+1状态变量sn+1,表示sn演变的结果，简称为状态，简称为状态各阶段各阶段开始开始时所处的自然状况或客观条件时所处的自然状况或客观条件S5=第15页，此课件共86

11、页哦动态规划中的动态规划中的状态应具有以下性质状态应具有以下性质：1、能描述过程的特征、能描述过程的特征2、具有无后效性、具有无后效性(马尔可夫性马尔可夫性)当某阶段的状态给定时，这个阶段以后过当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关程的演变与该阶段以前各阶段的状态无关3、状态是直接或间接可以观测的、状态是直接或间接可以观测的第16页，此课件共86页哦3、决策、决策：当一个阶段的状态确定后，可以作出各种选当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择从而演变到下一阶段的某个状态，这种选择手段称为决策择手段称为决策 12345678

12、910北京河北山西陕西甘肃8458961610967738423决策变量描述决策的变量描述决策的变量决策第第2阶段当状态为阶段当状态为时的决策变量时的决策变量可取值为：可取值为：，=，简称为决策，简称为决策允许决策集合第17页，此课件共86页哦4、策略：由各阶段的决策组成的序列称为策略由各阶段的决策组成的序列称为策略12345678910北京河北山西陕西甘肃8458961610967738423最短路问题：最短路问题：策略=铺设方案如 允许策略集合允许策略集合最优策略最优策略：使整个问题达到最优效果的策略：使整个问题达到最优效果的策略策略：最优策略最优策略=最短的铺设路线最短的铺设路线策略第1

13、8页，此课件共86页哦策略：策略：由各阶段的决策组成的序列称为策略由各阶段的决策组成的序列称为策略原过程：原过程：一个一个n段决策过程，从段决策过程，从1到到n叫作问题的原过程叫作问题的原过程原过程的一个原过程的一个后部子过程后部子过程：对于任意给定的对于任意给定的k k（1 kn1 kn），从第），从第k k段到第段到第n n段段的过程称为原过程的一个后部子过程的过程称为原过程的一个后部子过程原过程的策略原过程的策略原过程的一个后部子过程的策略：原过程的一个后部子过程的策略：第19页，此课件共86页哦12345678910北京河北山西陕西甘肃8458961610967738423最短路问题：

14、原过程的一个策略：原过程的一个策略：后部子过程的策略后部子过程的策略后部子过程的策略 ，=p1，4（），第20页，此课件共86页哦 5 5、状态转移方程：、状态转移方程：是确定过程由一个状态到另一个状态是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。的演变过程，描述了状态转移规律。sk第k阶段的状态变量状态转移方程：第21页，此课件共86页哦6、指标函数、指标函数用于衡量所选定的策略优劣的数量指标称为指标函数用于衡量所选定的策略优劣的数量指标称为指标函数最优策略最优策略第22页，此课件共86页哦动态规划的基本原理动态规划的基本原理第23页，此课件共86页哦最优化原理：一个过程的

15、最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略对最短路问题：AB1 FB2B3C1C2C3D2D1E2E1则不论前面A如何到达B，B又如何到达C1第24页，此课件共86页哦对最短路问题：来源于动态规划的最优化原理最短路问题的基本方程：k=4,3,2,1由后向前迭代递推公式第25页，此课件共86页哦建立动态规划模型的步骤建立动态规划模型的步骤 1 1、划分阶段、划分阶段划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先

16、先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对对于于静静态态问问题题要要人人为为地地赋赋予予“时时间间”概概念念，以便划分阶段。以便划分阶段。2 2、正确选择状态变量、正确选择状态变量选选择择变变量量既既要要能能确确切切描描述述过过程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状状态态变变量量的的选择是从过程演变的特点中寻找。选择是从过程演变的特点中寻找。3 3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决

17、决策策变变量量，同同时时要要给给出出决决策变量的取值范围，即确定允许决策集合。策变量的取值范围，即确定允许决策集合。第26页，此课件共86页哦 4 4、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变量，状阶段状态变量，状态转移方程应当具有递推关系。态转移方程应当具有递推关系。5 5、确定阶段指标函数和最优指标函数，建立动态规划、确定阶段指标函数和最优指标函数，建立动态规划基本方程基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是指从阶段的收益，最优指标函数是指从第第k 阶段状态出发到第阶段状态出发

18、到第n 阶段末所获得收益的最优值，最阶段末所获得收益的最优值，最后写出动态规划基本方程。后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。践总结，才能较好掌握建模方法与技巧。第27页，此课件共86页哦例一、从例一、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过两

19、级中间其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？择什么路线，使总距离最短？AB1B2C1C2C3D24333321114最短路径问题最短路径问题第28页，此课件共86页哦 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段（第一阶段（C D）：）：C 有三条路线到终点有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f1(C1)=1 ；f1(C2)=3 ；f1(C3)=4 第29页，此课件

20、共86页哦 d(B1,C1)+f1(C1)3+1 f2(B1)=min d(B1,C2)+f1(C2)=min 3+3 d(B1,C3)+f1(C3)1+4 4 =min 6 =4 5第二阶段（第二阶段（B C）：）：B 到到C 有六条路线。有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)第30页，此课件共86页哦 d(B2,C1)+f1(C1)2+1 f2(B2)=min d(B2,C2)+f1(C2)=min 3+3 d(B2,C3)+f1(C3)1+4 3 =min 6 =3 5AB1B2C1C2C3D243333211

21、14DC1C2C3B1B2(最短路线为最短路线为B2C1 D)第31页，此课件共86页哦第三阶段（第三阶段（A B）：）：A 到到B 有二条路线。有二条路线。f3(A)1=d(A,B1)f2(B1)246 f3(A)2=d(A,B2)f2(B2)437 f3(A)=min =min6,7=6d(A,B1)f2(B1)d(A,B2)f2(B2)(最短路线为最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A第32页，此课件共86页哦AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为

22、6第33页，此课件共86页哦练习练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：最优路线为：A B1 C2 D1 E2 F2 G 路长路长18求从求从A到到G的最短路径的最短路径3第34页，此课件共86页哦k=5k=5，出发点，出发点E1E1、E2E2、E3E3u5(E1)=F1E1 F1 GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6

23、 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=3第35页，此课件共86页哦k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2,f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13 u3(C1)=D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B

24、1u2(B1)=C2u3(C2)=D1u4(D1)=E2第36页，此课件共86页哦u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643第37页，此课件共86页哦求从求从A到到E的最短路径的最短路径路线为路线为AB2C1 D1 E，最短路径为最短路径为1919AB2B1B3C1C3D1D2EC2521411261

25、0104312111396581052练习练习2：1第38页，此课件共86页哦 生产与存储问题生产与存储问题：某工厂生产并销售某种产品。已知：某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产今四个月市场需求预测如下表，又每月生产j j个单位产品个单位产品的费用为的费用为 每月库存每月库存i i个单位产品的费用个单位产品的费用E(i)=0.5i(E(i)=0.5i(千元），该千元），该厂最大库存容量为厂最大库存容量为3 3个单位，每月最大生产能力为个单位，每月最大生产能力为6 6个个单位，计划开始和计划期末库存量都是零，试制定单位，计划开始和计划期末库存量都是零，试制定四个月

26、的生产计划，在满足用户需求条件下，使总四个月的生产计划，在满足用户需求条件下，使总费用最小。费用最小。阶段阶段k=1，2，3，4第第k阶段的阶段的状态变量状态变量ski月1234g(i)需求2324S1=0，S2=0,1,2,3，S3=0,1,2,3，S4=0,1,2,3=第第k个月月初的库存量个月月初的库存量第39页，此课件共86页哦 生产与存储问题生产与存储问题 某工厂生产并销售某种产品。已知某工厂生产并销售某种产品。已知今后四个月市场需求预测及每月生产今后四个月市场需求预测及每月生产j个单位产品的费个单位产品的费用如下：用如下：月1234需求2324k=1，2，3，4sk=第k个月月初的

27、库存量S1=0S2=0,1,2,3S3=0,1,2,3S4=0,1,2,3=2,3,4,5每月库存每月库存i个单位产品的费用个单位产品的费用E(i)=0.5i(千元），该厂最千元），该厂最大库存容量为大库存容量为3个单位，每月最大生产能力为个单位，每月最大生产能力为6个单位，个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。计划，在满足用户需求条件下，使总费用最小。=2,3,4,5=0,1,2,3=3第40页，此课件共86页哦生产与存储问题生产与存储问题 某工厂生产并销售某种产品。已知今四个月市

28、场某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产需求预测如下表，又每月生产j个单位产品的费用为个单位产品的费用为 每月库存每月库存i个单位产品的费用个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为千元），该厂最大库存容量为3个单位，每月最大生产能力为个单位，每月最大生产能力为6个单位，计划开始和计划期末库存个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。总费用最小。i月1234g(i)需求2324k=1，2，3，4sk=第第k个月月初的库存量个月月初

29、的库存量一个策略=一个生产方案2，5，0，42，3，2，4费用：21（千元）费用：23（千元）最优策略：使总费用最小的生产方案使总费用最小的生产方案第41页，此课件共86页哦 生产与存储问题生产与存储问题 某工厂生产并销售某种产品。已知今四个月市场需求某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产预测如下表，又每月生产j个单位产品的费用为个单位产品的费用为 每月库存每月库存i个单位产品的费用个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为千元），该厂最大库存容量为3个单位，每月最大生产能力为个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都个单位

30、，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。小。阶段k=1，2，3，4状态变量sk=第k个月月初的库存量i月1234g(i)需求2324状态转移方程：第42页，此课件共86页哦当k=4时，u4(s4)对应的总费用=生产费+库存费i月1234g(i)需求2324库存费E(i)=0.5i，最大库存容量为3个单位，最大生产能力为6个单位，计划开始和计划期末库存量为零012347436.5326215.51第43页，此课件共86页哦当k=3时，i月1234g(i)需求2324库存费E(i)=

31、0.5i，最大库存容量为3个单位，最大生产能力为6个单位，计划开始和计划期末库存量为零012301230u3(3)对应的总费用=生产费+库存费第44页，此课件共86页哦i月1234g(i)需求2324库存费E(i)=0.5i，最大库存容量为3个单位，最大生产能力为6个单位，计划开始和计划期末库存量为零02 3 4 51212.51313.512211 2 3 411.51212.51311.5120 1 2 38 11.5 12 12.58030 1 288011.512012347436.5326215.51第45页，此课件共86页哦当k=2时，i月1234g(i)需求2324u2(s2)对

32、应的总费用=生产费+库存费第46页，此课件共86页哦02 3 4 51212.51313.512211 2 3 411.51212.51311.5120 1 2 38 11.5 12 12.58030 1 28 11.5 1280k=3当k=2时，0123 3 4 5 61818.516171652 3 4 517.5 18 15.5 16.5 1 2 3 4170 1 2 313.5 17 14.5 15.515.5415313.5017.5 1516第47页，此课件共86页哦当k=1时，i月1234g(i)需求2324u1(0)对应的总费用=生产费第48页，此课件共86页哦k=20123

33、3 4 5 618 18.516171652 3 4 517.5 18 15.5 16.5 1 2 3 417 17.5 15 160 1 2 313.5 17 14.5 15.515.5415313.50当k=1时，02 3 4 522 21.52122121.5第49页，此课件共86页哦生产存储问题的基本方程：第50页，此课件共86页哦最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略最短路问题的基本方程：k=4,3,2,1生产存储问题的基本方程为：第51页，此课件共86页哦k=n,n-1,n-2,3,2

34、,1动态规划的基本方程为：其中opt为最优，可取min或max第52页，此课件共86页哦 现有数量为现有数量为a（万元）的资金，计划分配给（万元）的资金，计划分配给n 个工厂个工厂,用用于扩大再生产。于扩大再生产。假设：假设：xi 为分配给第为分配给第i 个工厂的资金数量（万元）个工厂的资金数量（万元）；gi(xi)为第为第i 个工厂得到资金后提供的利润值（万元）。个工厂得到资金后提供的利润值（万元）。问题是如何确定各工厂的资金数，使得总的利润为最大。问题是如何确定各工厂的资金数，使得总的利润为最大。据此，有下式：据此，有下式：投资分配问题投资分配问题第53页，此课件共86页哦 令：令：fk(

35、x)=以数量为以数量为x 的资金分配给前的资金分配给前k 个工厂，所得到的个工厂，所得到的最大利润值。最大利润值。用动态规划求解，就是求用动态规划求解，就是求 fn(a)的问题。的问题。当当 k=1 时，时，f1(x)=g1(x)（因为只给一个工厂）（因为只给一个工厂）当当1kn 时，其递推关系如下：时，其递推关系如下：设：设：y 为分给第为分给第k 个工厂的资金（其中个工厂的资金（其中 0y x），此时还剩），此时还剩 x y（万元）的资金需要分配给前（万元）的资金需要分配给前 k-1 个工厂个工厂,如果采取最优如果采取最优策略，则得到的最大利润为策略，则得到的最大利润为fk1(xy),因此

36、总的利润为：因此总的利润为：gk(y)fk1(xy)第54页，此课件共86页哦 如果如果a 是以万元为资金分配单位，则式中的是以万元为资金分配单位，则式中的y 只取非负只取非负整数整数0，1，2，x。上式可变为：。上式可变为：所以，根据动态规划的最优化原理，有下式：所以，根据动态规划的最优化原理，有下式：第55页，此课件共86页哦 例题：例题：设国家拨给设国家拨给60万元投资，供四个工厂扩建使用，每个工万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。如下表所示。投资利润0102030405060

37、g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，是要求解：依据题意，是要求 f4(60)。第56页，此课件共86页哦按顺序解法计算。按顺序解法计算。第一阶段：求第一阶段：求 f1(x)。显然有。显然有 f1(x)g1(x)，得到下表，得到下表 投资利润0102030405060f1(x)g1(x)0205065808585最优策略0102030405060第二阶段：求第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行。此时需考虑第一、第二个工厂如何进行投资分配，以取得最

38、大的总利润。投资分配，以取得最大的总利润。第57页，此课件共86页哦最优策略为（最优策略为（40，20），此时最大利润为），此时最大利润为120万元。万元。同理可求得其它同理可求得其它 f2(x)的值。的值。第58页，此课件共86页哦最优策略为（最优策略为（30，20），此时最大利润为），此时最大利润为105万元。万元。第59页，此课件共86页哦最优策略为（最优策略为（20，20），此时最大利润为），此时最大利润为90万元。万元。最优策略为（最优策略为（20，10），此时最大利润为），此时最大利润为70万元。万元。第60页，此课件共86页哦最优策略为（最优策略为（10，0）或（）或（0，10）

39、，此时最大利润为，此时最大利润为20万元。万元。f2(0)0。最优策略为（最优策略为（0，0），最大利润为），最大利润为0万元。万元。得到下表得到下表最优策略为（最优策略为（20，0），此时最大利润为），此时最大利润为50万元。万元。第61页，此课件共86页哦 投资利润0102030405060f2(x)020507090105120最优策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三阶段：求第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。进行投资

40、分配，以取得最大的总利润。第62页，此课件共86页哦最优策略为（最优策略为（20，10，30），最大利润为），最大利润为155万元。万元。同理可求得其它同理可求得其它 f3(x)的值。得到下表的值。得到下表第63页，此课件共86页哦 投资利润0102030405060f3(x)0256085110135155最优策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四阶段：求第四阶段：求 f4(60)。即问题的最优策略。即问题的最优策略。第64页，此课件共86页哦最优策略为（最优策略为（20，0，30，10），最大利润为），

41、最大利润为160万元。万元。第65页，此课件共86页哦 练习：练习：求投资分配问题得最优策略，其中求投资分配问题得最优策略，其中a50 万元，其余资料万元，其余资料如表所示。如表所示。投资利润01020304050g1(x)02140528085g2(x)015365073100g3(x)02560656870第66页，此课件共86页哦例：某公司打算在例：某公司打算在3个不同的地区设置个不同的地区设置4个销售点，根据市个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每到的利润如表

42、所示。试问在各地区如何设置销售点可使每月总利润最大。月总利润最大。地地区区销售点销售点01234123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 第67页，此课件共86页哦 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公斤，公斤，设有设有n 种物品可供他选择装入包中。已知每种物品的重量种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？（各几件），使所起作用（使用价值）

43、最大？物品 1 2 j n重量（公斤/件）a1 a2 aj an每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。输中的货物装载问题、人造卫星内的物品装载问题等。四、背包问题四、背包问题第68页，此课件共86页哦设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学模种物品的装件数（非负整数）则问题的数学模型如下：型如下：用动态规划方法求解，令用动态规划方法求解，令 fx(y)=总重量不超过总重量不超过 y 公斤，包中只装有前公斤，包中只装有前k 种物品时的最种

44、物品时的最大使用价值。大使用价值。其中其中y 0，k 1,2,n。所以问题就是求所以问题就是求 fn(a)第69页，此课件共86页哦其递推关系式为：其递推关系式为：当当 k=1 时，有：时，有：第70页，此课件共86页哦例题：求下面背包问题的最优解例题：求下面背包问题的最优解物品 1 2 3重量（公斤）3 2 5使用价值 8 5 12解：解：a5 ，问题是求，问题是求 f3(5)第71页，此课件共86页哦第72页，此课件共86页哦第73页，此课件共86页哦第74页，此课件共86页哦第75页，此课件共86页哦所以，最优解为所以，最优解为 X（1.1.0），），最优值为最优值为 Z=13。第76页

45、，此课件共86页哦 练习练习1：某厂生产三种产品，各种产品重量与利润的关：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过总重量不超过 6 吨，问如何安排运输，使总利润最大吨，问如何安排运输，使总利润最大？种类 1 2 3重量（吨/公斤）2 3 4 单件利润（元）80 130 180最优方案：最优方案：X1=（0.2.00.2.0）X2=（1.0.11.0.1）Z=260=260第77页，此课件共86页哦 练习练习2：求下列问题的最优解：求下列问题的最优解 X=(2.1.0)最优值为最优值为 Z

46、=13第78页，此课件共86页哦 排序问题指排序问题指n 种零件经过不同设备加工是的顺序问题。其种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。目的是使加工周期为最短。1、n 1 排序问题排序问题 即即n 种零件经过种零件经过1 种设备进行加工，如何安排？种设备进行加工，如何安排？14682023交货日期（交货日期（d）45173加工时间（加工时间（t）零件代号零件代号例一、例一、五、排序问题五、排序问题第79页，此课件共86页哦 （1）平均通过设备的时间最小）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将按零件加工时间非负次序排列顺序，其时间最小。（

47、即将加工时间由小到大排列即可）加工时间由小到大排列即可）零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1481320 交货时间交货时间82314620 平均通过时间平均通过时间第80页，此课件共86页哦延迟时间延迟时间=13 6=7 （2）按时交货排列顺序）按时交货排列顺序零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间56101720 交货时间交货时间82314620 平均通过时间平均通过时间延迟时间延迟时间=0第81页，此课件共86页哦 （3）既满足交货时间，又使平均通过时间最小）既满足交货时间，又使平均通过时间最小零件加工顺序

48、零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1691320 交货时间交货时间82314620延迟时间延迟时间=0 平均通过时间平均通过时间第82页，此课件共86页哦 2、n 2 排序问题排序问题 即即n 种零件经过种零件经过2 种设备进行加工，如何安排？种设备进行加工，如何安排？例二、例二、49523B53786A 零件零件设备设备ABT第83页，此课件共86页哦经变换为经变换为49523B53786A 零件零件设备设备加工顺序图如下：加工顺序图如下：ABT3756895432+2+2-5 加工周期加工周期 T=3+7+5+6+8+2=31第84页，此课件共86页哦 3、n 3 排序问题排序问题 即即n 种零件经过种零件经过 3 种设备进行加工，如何安排？种设备进行加工，如何安排？例三、例三、3468564683579310CBA第85页，此课件共86页哦ABCT变换变换4+36+45+86+56+48+65+37+53+910+3B+CA+B第86页，此课件共86页哦