《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第七章 动态规划》由会员分享，可在线阅读，更多相关《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第七章 动态规划（57页珍藏版）》请在金锄头文库上搜索。
1、第七章 动态规划,第一节 最短线路问题 第二节 动态规划的基本概念和原理 第三节 动态规划应用举例 第四节 决策变量连续的动态规划问题 第五节 乘积形式的目标函数 第六节 随机型动态规划问题,第一节 最短线路问题,一、最短线路问题及其解法 图7-1是一个线路网络图。从A到E要修建一条石油管道。管道必须在B、C、D三处设立加压站。在B处有B1，B2，B3三个不同地址可供选择作为建站点。当然，从A到这3个点的距离是不同的；同样，C和D处也都有不同的地址可供选择。图上的圆圈称为节点，表示地址，两个节点之间的箭线称为线或边，表示可以修建管道，线上的数字表示两个地址之间的距离。现在的问题是在许多条从A到
2、E的线路中，找出一条最短的，称为最短线路问题。,一、最短线路问题及其解法,1.逆序法 2.顺序法,一、最短线路问题及其解法,图 7-1,1.逆序法,图 7-2,2.顺序法,图 7-3,第二节 动态规划的基本概念和原理,一、多阶段决策问题 二、动态规划的基本概念 三、最优化原理与动态规划方程,一、多阶段决策问题,如果一个问题的求解过程可以按空间(例如最短线路问题)、按时间(例如后面将要讨论的生产计划问题)，或者按问题的要求可以划分成相互关联的若干阶段，而每个阶段都需要作出决策，当所有阶段的决策都确定后，整个问题的求解策略也就确定了，那么这样的问题称为多阶段决策问题。不论按哪种因素分段，统称为时段
3、，于是问题成为按时段的变动而作出决策的问题，这就是“动态”的含义。,二、动态规划的基本概念,1.阶段和阶段变量 2.状态和状态变量 3.决策和决策变量 4.策略和子策略 5.状态转移函数 6.阶段损益和策略效益,二、动态规划的基本概念,正确地划分阶段是运用动态规划求解问题的基础。一般说来，如何划分并没有固定的模式，只能依靠经验和技巧。有的问题，虽不能像最短线路问题那样明显地分段，但适当增加节点可以转化为多阶段决策问题来求解。例如图7-4所示求A到G的最短线路问题。从网络图上看不出明显的阶段划分，但增加节点后，将问题化为图7-5所示的情况，便成为多阶段决策问题。,1.阶段和阶段变量,图 7-4,
4、1.阶段和阶段变量,图 7-5,2.状态和状态变量,在多阶段决策过程中，每个阶段的起始位置或状况称为该阶段的状态。每个阶段的初始状况又是前一个阶段的一个终止状况(当然，第一阶段除外)。因而，一旦各个阶段的状态都确定之后，整个过程也就完全确定。从这个意义上说，多阶段决策过程也就是各个状态的演变过程。应当注意，不同的问题，其状态的含义也不同。,3.决策和决策变量,知道了阶段k的状态s k后，就要作出关于这一个阶段的决策。所谓决策，就是从本阶段的状态出发，如何演变到下一阶段状态所作的抉择。描述决策的变量称为决策变量。通常用x k表示第k个阶段的决策。,4.策略和子策略,对一个多阶段决策问题，由第1个
5、阶段到最后阶段(设为阶段n)，当每一个阶段的决策都确定后，构成的决策序列称为一个整体策略，简称策略。由于每个阶段都有若干个可能的状态和不同的可能决策，因而具有许多不同的策略可供选择。其中能够满足预期目标的子策略，称为从s k出发的最优子策略。,5.状态转移函数,顺序状态转移函数与逆序状态转移函数统称为状态转移函数。多阶段决策问题有的可以用逆序法，即状态转移用顺序状态转移函数来求解；也可以用顺序法求解，但有的问题却只能用逆序法来求解，因此我们主要讨论逆序法求解。用逆序法求解，要用顺序状态转移函数，因此，如不加说明，以后总是指顺序状态转移函数。,6.阶段损益和策略效益,前面在最短线路问题中已经指出
6、，从A到E的最优线路有这样的特点：如果最短线路经过第k阶段的状态s k，那么从s k出发到达终点的这条线路对于从s k出发到达终点的所有线路来说，必是最短线路。在实际生活中具有这样特点的问题很多。美国科学家贝尔曼研究了这类问题，提出了求解多阶段决策问题的最优化原理。,三、最优化原理与动态规划方程,最优化原理 对于多阶段决策问题，作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，就前面决策所形成的状态而言，余下的诸决策必然构成一个最优子策略。 用动态规划求解多阶段决策问题的基本思想是：利用最优化原理，建立动态规划方程，即建立动态规划的数学模型，然后求得其最优解。,三、最优化原理与动
7、态规划方程,基本步骤为： (1)将问题的求解过程恰当地分成若干阶段，一般可按问题所处的空间或时间进行划分，并确定阶段变量，对n个阶段问题来说，k=1,2,n。 (2)正确地选择状态变量sk，它应当满足无后效性等三个条件，并确定状态集合Sk。 (3)确定决策变量xk(sk)及阶段的允许决策集合Dk(sk)。 (4)写出状态转移函数 (5)根据题意，列出指标函数Fk,n,fk(sk),F1,n,f1(s1)。,三、最优化原理与动态规划方程,第三节 动态规划应用举例,例1 生产与存储问题 一个工厂生产的某种产品，在一定的时期内，增大生产批量，能够降低产品的单位成本，但若超过市场的需求量，就会造成产品
8、的积压而增加存储的费用。因此如何正确地制定生产计划，使得在整个计划期内，生产和存储的总费用最小，这就是生产与存储问题。,第三节 动态规划应用举例,举例如下： 假设某厂生产的一种产品，以后四个月的订单如表7-1所示。合同规定在月底前交货，生产每批产品的固定成本为3千元，每批生产的产品件数不限。每件产品的可变成本为1千元，每批产品的最大生产能力为5件。产品每件每月的存储费为0.5千元。设1月初有库存产品1件，4月底不再留下产品。试在满足需要的前提下，如何组织生产才能使总的成本费用最低。,第三节 动态规划应用举例,例2 某建筑公司拟建造甲,乙,丙三类住宅出售。甲类住宅每栋耗资100万元，售价200万
9、元；乙类住宅每栋耗资60万元，售价110万元；丙类住宅每栋耗资30万元，售价70万元。由于有关规定，建造每类住宅不得超过3栋。该公司拥有建房资金350万元，问应如何安排资金，可使该公司的售房收益最大？ 解 在这个问题中，并没有明显的时间和空间上的阶段性。但可以人为地赋予它“时段”的概念，即把考虑甲,乙,丙三类住宅的建造计划视为3个阶段，这样同样可以运用动态规划的方法来求解。,第三节 动态规划应用举例,例3 今有一辆载重量为15t的卡车，用来装载4种需要运输的货物，如果已知这4种货物的重量和价值如表7-9所示。在载重允许的条件下，每车装载每种货物的件数不限，问应如何搭配这4种货物，才能使每车装载
10、货物的价值最大。 解 这个问题中，是把卡车的载重能力看做一种资源，这类问题一般称为背包问题。,例1 生产与存储问题,表 7-1,表 7-2,例1 生产与存储问题,表 7-3,例1 生产与存储问题,表 7-3,例1 生产与存储问题,表 7-4,例1 生产与存储问题,表 7-5,例1 生产与存储问题,表 7-6,例2,表 7-7,例2,表 7-8,例2,例3,表 7-9,解 这类问题一般称为背包问题。,表 7-10,表 7-11,解 这类问题一般称为背包问题。,表 7-12,解 这类问题一般称为背包问题。,表 7-13,解 这类问题一般称为背包问题。,例4,设某商店有5万元资金，拟在三个地区筹建售
11、货点，由于各地点的环境不同，使用资金所能获得的收益也不同，具体年收益和投资的数据如表7-14所示。,表 7-14,例4,表 7-15,表 7-16,例4,表 7-17,例4,表 7-18,例5利用动态规划求解问题,表 7-19,例5利用动态规划求解问题,表 7-20,例5利用动态规划求解问题,表 7-21,例5利用动态规划求解问题,表 7-22,例5利用动态规划求解问题,例6,某厂新购某种器具125件，这种器具5年后将被其他新器材所取代，此种器具在高负荷下工作，年损坏率为0.5，年利润为10万元；如在低负荷下工作，年损坏率为0.2，年利润为6万元。问如何安排这些器具的生产负荷，才能使5年内所获
12、总利润最大。,表 7-23,例6,第四节 决策变量连续的动态规划问题,例7 设某厂生产A、B两种产品，由于该厂仓库及其他设备条件的限制，对于两种不同的日产量x1和x2(单件：百件)，日生产成本分别为(单位：千元)c1(x1)=3x1+x21，c2(x2)=4x2+2x22 又知两种产品的售价分别为10千元/百件和15千元/百件。两种产品的工时定额消耗均为1百件/h。如果每天总生产时间不超过8h的条件下，产品A和B应各生产多少小时，才能使总的利润最大?,第五节 乘积形式的目标函数,例 利用动态规划方法求解,极大化z=x21x2x33 满足x1+x2+x36 x1，x2，x30,解 这是个几何规划
13、问题。,可以利用几何规划的方法求解，但这里仍用动态规划方法求解。 将问题分成3个阶段，x k是阶段k的决策变量。本例用顺序法求解。 首先增加一个0阶段，得出其递推关系和状态转移函数。,例 可靠性问题,设某种仪器由3种不同的元件串连而成，任一元件的故障都将造成整台仪器的故障。每种元件又都有3种不同规格可供选择。设第i种元件的第j种规格的可靠性为rij，0rij1，所需费用为cij，生产每台仪器的资金限额为E。试求在资金限额以内，如何选用元件，可使仪器的可靠性最大?,表 7-25,表 7-26,表 7-27,例 可靠性问题,第六节 随机型动态规划问题,某厂同有关部门签订了一个新产品的试制合同，如果3个月生产不出一个合格的新产品，则要罚款2000元。每次试制的周期为一个月，每次试制中试制的产品个数不限，试制一个产品的成本为100元，并且要到一个试制周期结束后才能检验。设每个试制品的合格率为0.4，每次试制的开始费用为200元。问如何安排试制，才能使费用的期望值最小?,表 7-28,表 7-29,表 7-30,第六节 随机型动态规划问题,
