运筹学 第2版 作者 沈荣芳 第七章 动态规划.pptVIP

表　7-6 例2　 表　7-7 例2　 表　7-8 例2　 例3　 表　7-9 解　这类问题一般称为背包问题。 表　7-10 表　7-11 解　这类问题一般称为背包问题。 表　7-12 解　这类问题一般称为背包问题。 表　7-13 解　这类问题一般称为背包问题。 例4 设某商店有5万元资金，拟在三个地区筹建售货点，由于各地点的环境不同，使用资金所能获得的收益也不同，具体年收益和投资的数据如表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年内所获总利润最大。 表　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+x3≤6 x1，x2，x3≥0 解　这是个几何规划问题。 可以利用几何规划的方法求解，但这里仍用动态规划方法求解。 将问题分成3个阶段，x k是阶段k的决策变量。本例用顺序法求解。 首先增加一个0阶段，得出其递推关系和状态转移函数。 例 可靠性问题 设某种仪器由3种不同的元件串连而成，任一元件的故障都将造成整台仪器的故障。每种元件又都有3种不同规格可供选择。设第i种元件的第j种规格的可靠性为rij，0＜rij＜1，所需费用为cij，生产每台仪器的资金限额为E。试求在资金限额以内，如何选用元件，可使仪器的可靠性最大? 表　7-25 表　7-26 表　7-27 例 可靠性问题 第六节　随机型动态规划问题 某厂同有关部门签订了一个新产品的试制合同，如果3个月生产不出一个合格的新产品，则要罚款2000元。每次试制的周期为一个月，每次试制中试制的产品个数不限，试制一个产品的成本为100元，并且要到一个试制周期结束后才能检验。设每个试制品的合格率为0.4，每次试制的开始费用为200元。问如何安排试制，才能使费用的期望值最小? 表　7-28 表　7-29 表　7-30 第六节　随机型动态规划问题 第七章　动态规划 第一节　最短线路问题第二节　动态规划的基本概念和原理第三节　动态规划应用举例 第四节　决策变量连续的动态规划问题第五节　乘积形式的目标函数第六节　随机型动态规划问题 在线教务辅导网： 教材其余课件及动画素材请查阅在线教务辅导网 QQ:349134187 或者直接输入下面地址： 第一节　最短线路问题 一、最短线路问题及其解法 图7-1是一个线路网络图。从A到E要修建一条石油管道。管道必须在B、C、D三处设立加压站。在B处有B1，B2，B3三个不同地址可供选择作为建站点。当然，从A到这3个点的距离是不同的；同样，C和D处也都有不同的地址可供选择。图上的圆圈称为节点，表示地址，两个节点之间的箭线称为线或边，表示可以修建管道，线上的数字表示两个地址之间的距离。现在的问题是在许多条从A到E的线路中，找出一条最短的，称为最短线路问题。 一、最短线路问题及其解法 1.逆序法2.顺序法 一、最短线路问题及其解法 图　7-1 1.逆序法 图　7-2 2.顺序法  图　7-3 第二节　动态规划的基本概念和原理 一、多阶段决策问题二、动态规划的基本概念三、最优化原理与动态规划方程 一、多阶段决策问题 如果一个问题的求解过程可以按空间(例如最短线路问题)、按时间(例如后面将要讨论的生产计划问题)，或者按问题的要求可以划分成相互关联的若干阶段，而每个阶段都需要作出决策，当所有阶段的决策都确定后，整个问题的求解策略也就确定了，那么这样的问题称为多阶段决策问题。不论按哪种因素分段，统称为时段，于是问题成为按时段的变动而作出决策的问题，这就是“动态”的含义。 二、动态规划的基本概念 1.阶段和阶段变量2.状态和状态变量3.决策和决策变量4.策略和子策略5.状态转移函数6.阶段