专题讲座动态规划与层次分析法

专题讲座动态规划与层次分析法内容说明以下内容在《数学建模与数学实验（第二版）》（汪晓银，周保平主编）第6章、第9章。动态规划内容提要动态规划的最优化原理动态规划的基本概念及递推公式动态规划模型举例动态规划程序例1最短路问题五十年代贝尔曼(B.E.Bellman)为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理，可归结为一个递推公式动态规划的最优化原理可以枚举出20条路径，其中最短的路径长度为16决策树法动态规划的最优化原理最优性原理“最优策略的一部分也是最优的。因此我们可以从B向回搜索最短路表现为明显的阶段性动态规划的最优化原理基本概念及递推公式状态最短路问题中，各个节点就是状态。生产库存问题中，库存量是状态。物资分配问题中，剩余的物资量是状态控制变量(决策变量)最短路问题中，走哪条路。生产库存问题中，各阶段的产品生产量。物资分配问题中，分配给每个地区的物资量。阶段的编号与递推的方向一般采用反向递推，所以阶段的编号也是逆向的当然也可以正向递推动态规划的步骤1、确定问题的阶段和编号2、确定状态变量用Sk

表示第k阶段的状态变量及其值3、确定决策变量用xk表示第k阶段的决策变量，并以xk*表示该阶段的最优决策4、状态转移方程sk-1=g(sk,xk)反向编号sk+1=g(sk,xk)正向编号5、直接效果直接一步转移的效果dk(sk,xk)6、总效果函数指某阶段某状态下到终端状态的总效果，它是一个递推公式终端的边际效果一般为f0(s0,x0)=0(2)如串联系统可靠性问题，是连乘形式，此时有终端的边际效果一般为f0(s0,x0)=1从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段hk是一般表达形式，求当前阶段当前状态下的阶段最优总效果(1)如最短路问题，是累加形式，此时有动态规划的步骤动态规划模型举例例1产品生产计划安排问题

某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。第一阶段：(即第4月份)由边界条件和状态转移方程s0=s1+x1-y1=s1+x1–6=0得

s1+x1=6或x1=6–s1估计第一阶段，即第4月份初库存的可能状态：s1

[0,5]设xk为第k阶段生产量，则有直接成本

dk(sk,xk)=ckxk+2sk状态转移公式为

sk-1=sk+xk-yk总成本递推公式动态规划模型举例第一阶段最优决策表第二阶段：最大可能库存量7件由状态转移方程：s1=s2+x2-120及x210，可知s2[2,7]，minx2=5由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6) =22+8010+456=1260得第二阶段最优决策表，如下动态规划模型举例第二阶段最优决策表第三阶段：最大可能库存量4件由状态转移方程：s2=s3+x3-72及x310，可知s3[0,4]，minx3=5由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8) =21+7210+1104=1826得第三阶段最优决策表，如下动态规划模型举例第三阶段最优决策表第四阶段：初始库存量s4=0由状态转移方程：s3=s4+x4-60可知x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322得第四阶段最优决策表，如下回溯得此表动态规划模型举例解四个季度为四个阶段，采用阶段编号与季度顺序一致。设sk

为第k季初的库存量，则边界条件为s1=s5=0设xk

为第k季的生产量，设yk

为第k季的订货量；sk，xk，yk都取实数，状态转移方程为sk+1=sk+xk-yk仍采用反向递推，但注意阶段编号是正向的

目标函数为例2生产–库存管理问题设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。动态规划模型举例第一步：(第四季度)总效果f4(s4,x4)=0.005x42+s4

由边界条件有：s5=s4+x4–y4=0，解得：x4*=1200–s4

将x4*代入f4(s4,x4)得：

f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季度)总效果f3(s3,x3)=0.005x32+s3+f4*(s4)将s4=s3+x3–500代入f3(s3,x3)得：动态规划模型举例第三步：(第二、三、四季度)总效果

f2(s2,x2)=0.005x22+s2+f3*(s3)将s3=s2+x2-700代入f2(s2,x2)得：

注意：最优阶段总效果仅是当前状态的函数，与其后的决策无关动态规划模型举例第四步：(第一、二、三、四季度)总效果

f1(s1,x1)=0.005x12+s1+f2*(s2)将s2=s1+x1–600=x1–600代入f1(s1,x1)得：由此回溯：得最优生产–库存方案

x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。动态规划模型举例例3

资源分配问题某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。解：设分配人员的顺序为市场1,2,3，采用反向阶段编号。设sk

为第k阶段尚未分配的人员数，边界条件为s3=9设xk

为第k阶段分配的推销人员数；仍采用反向递推，状态转移方程为sk–1=sk–xk

目标函数为动态规划模型举例s1有0~9种可能，第一阶段（第三市场）最优决策表如下：为什么与例1的第一阶段的表有差别？动态规划模型举例s2有0~9种可能，第二阶段最优决策表如下：动态规划模型举例

由边界条件s3=9，第三阶段最优决策表如下：得决策过程：x3*=2,x2*=0,x1*=7,f3*=218即市场1分配2人，市场2不分配，市场3分配7人最优解与分配的顺序有关吗？动态规划模型举例层次分析法背景层次分析法的基本步骤层次分析法的广泛应用层次分析法内容提要

日常工作、生活中的决策问题

涉及经济、社会等方面的因素

作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化

Saaty于1970年代提出层次分析法AHP(AnalyticHierarchyProcess)

AHP——一种定性与定量相结合的、系统化、层次化的分析方法背景目标层O(选择旅游地)P2黄山P1桂林P3北戴河准则层方案层C3居住C1景色C2费用C4饮食C5旅途层次分析法的基本步骤例.选择旅游地如何在3个目的地中按照景色、费用、居住条件等因素选择.“选择旅游地”思维过程的归纳

将决策问题分为3个层次：目标层O，准则层C，方案层P；每层有若干元素，

各层元素间的关系用相连的直线表示。

通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。将上述两组权重进行综合，确定各方案对目标的权重。层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。层次分析法的基本步骤成对比较阵和权向量元素之间两两对比，对比采用相对尺度设要比较各准则C1,C2,…,Cn对目标O的重要性A~成对比较阵A是正互反阵要由A确定C1,…,Cn对O的权向量选择旅游地层次分析法的基本步骤成对比较的不一致情况一致比较不一致允许不一致，但要确定不一致的允许范围成对比较阵和权向量层次分析法的基本步骤考察完全一致的情况层次分析法的基本步骤成对比较完全一致的情况满足的正互反阵A称一致阵，如成对比较阵和权向量层次分析法的基本步骤

A的秩为1，A的唯一非零特征根为n

A的任一列向量是对应于n的特征向量

A的归一化特征向量可作为权向量对于不一致(但在允许范围内)的成对比较阵A，建议用对应于最大特征根的特征向量作为权向量w，即一致阵性质层次分析法的基本步骤2468比较尺度aij

Saaty等人提出1~9尺度——aij

取值1,2,…,9及其互反数1,1/2,…,1/9尺度13579相同稍强强明显强绝对强aij=1,1/2,,…1/9的重要性与上面相反

便于定性到定量的转化：成对比较阵和权向量层次分析法的基本步骤

心理学家认为成对比较的因素不宜超过9个用1~3,1~5,…1~17,…,1p~9p

(p=2,3,4,5),d+0.1~d+0.9(d=1,2,3,4)等27种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现，1~9尺度较优。层次分析法的基本步骤一致性检验对A确定不一致的允许范围已知：n阶一致阵的唯一非零特征根为n可证：n阶正互反阵最大特征根

n,且

=n时为一致阵定义一致性指标:CI越大，不一致越严重层次分析法的基本步骤RI000.580.901.121.241.321.411.451.491.51

n1234567891110为衡量CI的大小，引入随机一致性指标RI——随机模拟得到aij,形成A，计算CI即得RI。定义一致性比率CR=CI/RI当CR<0.1时，通过一致性检验Saaty的结果如下层次分析法的基本步骤“选择旅游地”中准则层对目标的权向量及一致性检验准则层对目标的成对比较阵最大特征根权向量(特征向量)w=(0.263,0.475,0.055,0.090,0.110)T一致性指标随机一致性指标RI=1.12(查表)一致性比率CR通过一致性检验层次分析法的基本步骤组合权向量记第2层（准则）对第1层（目标）的权向量为同样求第3层(方案)对第2层每一元素(准则)的权向量方案层对C1(景色)的成对比较阵方案层对C2(费用)的成对比较阵…Cn…Bn最大特征根1

2

…

n

权向量w1(3)w2(3)…

wn(3)层次分析法的基本步骤第3层对第2层的计算结果k10.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.082230.1420.4290.42933.0090.1750.1930.633430.6680.1660.1665组合权向量RI=0.58(n=3),

CIk

均可通过一致性检验w(2)

方案P1对目标的组合权重为方案层对目标的组合权向量为(0.300,0.246,0.456)T层次分析法的基本步骤组合权向量第1层O第2层C1,…Cn第3层P1,…Pm第2层对第1层的权向量第3层对第2层各元素的权向量构造矩阵则第3层对第1层的组合权向量第s层对第1层的组合权向量其中W(p)是由第p层对第p-1层权向量组成的矩阵层次分析法的基本步骤1）建立层次分析结构模型深入分析实际问题，将有关因素自上而下分层（目标—准则或指标—方案或对象），上层受下层影响，而层内各因素基本上相对独立。2）构造成对比较阵用成对比较法和1~9尺度，构造各层对上一层每一因素的成对比较阵。3）计算权向量并作一致性检验对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，则特征向量为权向量。4）计算组合权向量（作组合一致性检验*）组合权向量可作为决策的定量依据。层次分析法的基本步骤

应用领域：经济计划和管理，能源政策和分配，人才选拔和评价，生产决策，交通运输，科研选题，产业结构，教育，医疗，环境，军事等。