多阶段决策问题与动态规划和科学决策与信息分析

4动态规划

4.1多阶段决策问题与动态规划4.2动态规划的基本概念4.3动态规划的步骤4.4动态规划的应用

1求解静态规划问题2资源分配问题3不确定性采购问题4排序问题

例2机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产．在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝g(u),这时机器的年完好率为a（0<a<1)．在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝h(v),这时机器的年完好率为b（a<b<1）．假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。4.1多阶段决策问题与动态规划多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。(1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。(2)状态（state）状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。(3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。4.2动态规划的基本概念（一）(4)策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n＝{u1,u2,……,un}称为全过程策略，简称策略；而在k子过程上的决策序列pk,n＝{uk,uk+1,……,un}称为k子过程策略，也简称子策略。(5)状态转移方程若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1＝Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。4.2动态规划的基本概念（二）(6)指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量，用vk(sk,uk)表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值，记为

Vk,n＝Vk,n(sk,uk,sk+1,uk+1,……,sn,un)

动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是：①各阶段指标函数的和Vk,n＝∑vj(sj,uj)；②各阶段指标函数的积Vk,n＝∏vj(sj,uj)。

把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态sk的函数，称为最优值函数，记为fk(sk)。即

fk(sk)＝optVk,n(sk,uk,……,sn,un)uk,…,un式中的“opt”（optimization）可根据具体问题而取min或max。(7)基本方程通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,n＝∑vj(sj,uj)，则有fk(sk)＝opt{vk(sk,uk)+fk+1(sk+1)}

uk∈Dk(sk)(k＝n,n-1,…,1)

递推方程

fn+1(sn+1)＝0边界条件递推方程和边界条件一起称为动态规划的基本方程。可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解。此问题的基本方程为fk(sk)＝Min{dk(uk)+fk+1(sk+1)}

uk∈Dk(sk)

k＝6,5,4,3,2,1f7(s7)＝04.3动态规划的步骤（一）当k=6时按基本方程由后向前继续递推有:当k=5时当k=4时当k=3时当k=2时当k=1时由此可以看出，A到G的最短路长为18，路径为：A→B1→C2→D1→E2→F2→G现在把动态规划法的步骤归纳如下：(1)将所研究问题的过程划分为n个恰当的阶段，

k＝1,2,…,n；(2)正确地选择状态变量Sk，并确定初始状态S1的值；(3)确定决策变量uk以及各阶段的允许决策集Dk(Sk)；(4)给出状态转移方程；(5)给出满足要求的过程指标函数Vk,n及相应的最优值函数；(6)写出递推方程和边界条件，建立基本方程；(7)按照基本方程递推求解。以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。4.3动态规划的步骤（二）例：机器负荷问题某种机器可以在高低两种不同的负荷下进行生产．在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7．在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9．假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。(1)按年数划分为5个阶段，k=1,2,3,4,5(2)取第k年初完好的机器数sk为状态变量,s1=1000(3)取第k年投入高负荷的机器数xk为决策变量,0≤xk≤sk(4)状态转移方程为sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指标函数为Vk,5=∑[8xj+5(sj-xj)]=∑(5sj+3xj)(6)基本方程为

fk(sk)＝max{5sj+3xj+fk+1(sk+1)}k=5,4,3,2,1

0≤xk≤sk

f6(s6)＝0解:当k=5时f5(s5)＝max{5s5+3x5+f6(s6)}=max{5s5+3x5}=8s5(x5*=s5)0≤x5≤s50≤x5≤s5当k=4时f4(s4)＝max{5s4+3x4+8s5}=max{5s4+3x4+8(0.9s4-0.2x4)}0≤x4≤s40≤x4≤s4=max{12.2s4+1.4x4}=13.6s4(x4*=s4)0≤x4≤s4当k=3时f3(s3)＝max{5s3+3x3+13.6s4}=max{5s3+3x3+13.6(0.9s3-0.2x3)}0≤x3≤s30≤x3≤s3=max{17.24s3+0.28x3}=17.5s3(x3*=s3)0≤x3≤s3当k=2时f2(s2)=max{5s2+3x2+17.52s3}=max{5s2+3x2+17.52(0.9s2-0.2x2)}0≤x2≤s20≤x2≤s2=max{20.77s2-0.504x2}=20.7s4(x2*=0)0≤x2≤s2当k=1时f1(s1)=23.7s1(x1*=0)f1(1000)=23700s1=1000,x1*=0s2=900,x2*=0s3=810,x3*=810s4=576,x4*=576s5=397,x5*=397某些静态规划问题可用动态规划法来求解。

例用动态规划法求解maxz=x12.x22.x3x1+x2+x3=cxi≥0i=1,2,34.4动态规划的应用(一)1求解静态规划问题资源分配问题可描述如下：设有某种原料，总数量为a，分配给n个使用者。已知第i个使用者得到数量xi的资源，可创造的收益为gi（xi）。问应如何分配该资源，才能使总收益最大。4.4动态规划的应用(二)用动态规划法处理这种问题时，通常把给一个使用者分配资源的过程看成一个阶段，按n个使用者分成先后n个决策阶段。即先给第1个使用者分配资源，为第一阶段；再给第2个使用者分配，为第2阶段；依此类推，最后给第n个使用者分配，为第n阶段。2资源分配问题例某工业部门根据国家计划安排，拟将五台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器，才能使各厂的总效益最大。某单位准备在以后的n个时期内采购一批物资。各时期的价格不是确定的，而是按照某种已知的概率分布取值。试制定采购策略，确定在哪一时期以什么价格采购，能使采购价的数学期望值最低。这类问题也适合用动态规划法进行处理。下面通过实例加以说明。例7某厂生产上需要在近五周内采购一批原料，而估计在未来五周的价格有波动，其浮动价格和概率策得如下表。试确定该厂应在哪一周以什么价格购入，能使其采购价的数学期望值最小，并求出期望值。4.4动态规划的应用(三)3不确定性采购问题设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1≤i≤n)在A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找。即使如此，所有可能的方案仍有n!个，这是一个不小的数，用穷举法是不现实的。4.4动态规划的应用(四)4排序问题用动态规划法可以推出，工件i应该排在工件j之前的条件为min(ai,bj)≤min(aj,bi)。根据这个条件，构造下列排序方法：

a1a2…an1)建立工时矩阵M=b1b2…bn2)在工时矩阵M中找出最小元素（若不止一个可任选其一），若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置。3)将排定位置的工件所对应的列从M中划去，然后对余下的工件再按2)进行排序。如此进行下去，直到把所有工件都排完为止。当加工顺序排定之后，工件在A上没有等待时间，而在B上则常常需要等待。因此，寻求最优排序方案只有尽量减少在B上等待加工的时间，才能使总加工时间最短。

例设有5个工件需在机床A、B上加工，加工的次序为先A后B，每个工件需要的加工时间如下表。试安排加工顺序，使总加工时间最少，并求出总加工时间。第3章科学决策与信息分析主要内容：信息分析在决策中的作用；各类型决策中的信息保障；信息分析的工作流程。基本要求：了解各类决策中信息利用的重要性；了解不同决策阶段信息服务的特点；理解决策对信息的基本要求；掌握信息分析工作的基本流程。3.1信息分析在决策中的作用3.1.1决策活动中的信息利用信息分析:是对情报进行定向浓集和科学抽象的一种科学劳动.信息在军事战略制定中的作用；信息在制定地区经济发展规划中的作用；信息在科学管理中的作用；信息在对外贸易中的作用；信息在制定生产计划中的作用；信息在提高产品质量、发展花色品种中的作用。3.1信息分析在决策中的作用3.1.2不同决策阶段的信息服务决策阶段信息服务的内容与特点决策前（超前服务）促成决策及早完成（快）；有助于决策者掌握预测性信息（准）；有助于决策者更新知识、增强判断力（增）决策中（跟踪服务）确立目标阶段；决策方案准备阶段；选定决策方案阶段。决策后（反馈服务）跟踪反馈；循环反馈；同步追踪反馈。3.1信息分析在决策中的作用3.1.3决策对信息的基本要求可靠性（可信度）——信息的真实性和准确性。信息源；信息获取手段；信息获取的条件。完整性（完全度）——包括决策对象全部的信息全面收集历史的、现实的和未来的信息；兼顾反映正面的和反面问题的信息。精确性（精确度）——反映事物特征的细微化程度。不同决策对信息的精确度要求不同；划定范围，确定上限和下限。3.2各类型决策中的信息保障3.2.1新产品研制的信息保障创意产生与筛选阶段的信息保障创意产生于对信息的收集、吸收和理解；创意孕育着新产品，要尽可能多的收集；筛选是从多个创意中选择出具有开发价值项目的过程，其要求是：新意；可行；实用；有效。3.2各类型决策中的信息保障3.2.1新产品研制的信息保障开发决策阶段的信息保障主要任务是针对经过初步筛选出的几个创意中的每一个新产品开发构想收集信息；主要目的是从若干初步入选的新产品开发设想中挑选一个，作为本企业的新产品研制项目。新产品设计阶段的信息保障方案设计：正确选型，确定新产品的基本结构和基本参数。技术设计：确定产品的具体结构和形式，进行各部分、各部件的设计和组装设计。施工设计：绘制新产品试制所需的全套图纸，编制有关制造工艺的全部文件。3.2各类型决策