下载文档原格式
第5章风险型决策如果有坏事可能发生，那么它一定会发生。
——墨菲定理5.1风险型决策基本原理一项决策所产生的后果,取决于两方面因素: (1) 决策者所选择的行动方案;(2) 决策者所无法控制(或无法完全控制)的客观因素。
前者通常称为决策变量,后者称为自然状态。
风险型决策(随机型决策),是决策者根据几种不同自然状态可能发生的概率所进行的决策。
决策者所采用的任何一个行动方案都会遇到一个以上自然状态所引起的不同后果,这些后果出现的机会用自然状态出现的概率表示。
不论决策者采用何种方案,都要承担一定的风险,所以,这种决策属于风险型决策。
一般风险型决策中,所利用的概率包括客观概率与主观概率。
本节仅考虑离散情况下的风险决策。
采用风险型决策模型假设:(1) 决策者的策略集A中有m个可行方案,即A = {A i} (1 ≤ i ≤ m);(2) 方案A的自然状态集合R,对应A都有n种可能的结局R j (1 ≤ j ≤ n),即R = {R j}(1 ≤ j ≤ n);(3) 当自然状态R j采取策略A时,对应的决策效用函数为:u(A i, R j) = u ij;(4) 对应A i (1 ≤ i ≤ m)的n种结局R j (1 ≤ j ≤ n)的发生概率P(R j) = p j已知,且p1+ p2+…+ p n = 1。
自然状态、策略与收益等要素可用损益矩阵表示如表6.1所示:表6.1 风险型决策损益矩阵风险型决策即在此约束条件下,寻求使F(A)最优的策略A*。
5.2最大可能性法则最大可能性法则(the most probable state principle)以最可能状态作为选择方案时考虑的前提条件。
按照最大可能性法则,在最可能状态下,可实现最大收益值的方案为最佳方案。
所谓最可能状态,是指在状态空间中具有最大概率的那一个状态。
例1:某酒厂对推出一种新型啤酒的问题进行决策分析。
拟采取的方案有3种:(1)大规模投资,年生产能力2500万瓶,每年固定成本费用300万元;(2)小规模投资,年生产能力1000万瓶,每年固定成本费用100万元;(3)不推出该种啤酒。
动态规划_多阶段决策问题的求解方法1.构造状态网络; :一:解决多阶段决策最优化的过程为动态规划方法在程序设计中，有一类活动的过程，由于它的特殊性，可将过程2.根据状态转移关系和状态转移方程建立最优值的分成若干个互相联系的阶段，在它的每一阶段都需要做出决策，从而3.按阶段的先后次序计算每个状态的最优值。
使整个过程达到最好的活动效果。
因此各个阶段决策的选取不能任逆向思维法是指从问题目标状态出发倒推回初始意确定，它依赖于当前面临的状态，又影响以后的发展。
当各个阶段态的思维方法。
动态规划的逆向思维法的要点可归纳为以决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条 1.分析最优值的结构，刻画其结构特征; 活动路线。
这种把一个问题看作是一个前后关联具有链状结构的多 2.递归地定义最优值; 阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。
3.按自底向上或自顶向下记忆化的方式计算最优在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列如果原问题可以分解成几个本质相同、规模较小的就是在变化的状态中产生出来的，故有"动态"的含义，我们称这种就会联想到从逆向思维的角度寻求问题的解决。
一般解决多阶段决策最优化的过程为动态规划方法。
策问题多采用动态规划逆向思维方法解决。
二、举:二:动态规划最优化原理 pascal 语例说明本文以信息学奥赛用语言——最优化原理是动态规划的基础。
任何一个问题，如果失去了这言为编程个最优化原理的支持，就不可能用动态规划方法计算。
这个“最优化说明，其他编程语言编写方法相同，语句类似。
原理”如果用数学化一点的语言来描述的话，就是:假设为了解决某 :一:问题描述一优化问题，需要依次作出 n 个决策 D1，D2，，Dn，如若这个决策设有 N 个不相同的整数组成的数列，记为: 序列是最优的，对于任何一个整数 k，1 < k < n，不论前面 k 个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即 ()且 ?? a1 a2 an aiajij以后的决策 Dk+1，Dk+2，，Dn 也是最优的。
理学院本科课程教学大纲理学院本科课程教学大纲339《运筹学》教学大纲一、基本信息一、基本信息课程名称课程名称 运筹学运筹学课程编号课程编号 MATH4117 英文名称英文名称 Operational research 课程类型课程类型 本专业推荐选修课本专业推荐选修课 总学时总学时 54 理论学时理论学时54实验学时实验学时实践学时实践学时学 分3预修课程预修课程 高等数学高等数学 线性代数线性代数 适用对象适用对象 信息与计算科学、统计学信息与计算科学、统计学课程简介课程简介运筹学是一门研究人类对各种广义资源的运用及筹划活动的新兴学科，是系统科学中一个非常重要的分支门类，其目的在于了解和发现这种运用及筹划活动的基本规律，以便更有效发挥有限资源的效益，从而达到总体或全局有效或平衡的目标。
20世纪90年代中后期，特别进入21世纪以后，随着改革开放的进一步深入以及进入信息时代的脚步加快，运筹学教育受到了前所未有的重视。
几乎所有大学都开设了运筹学课程，成为商学院、工学院以及应用数学、计算机等专业的基本课程之一。
二、教学目标及任务二、教学目标及任务《运筹学》是管理类专业必修的专业基础课，是一门为决策机构决策时提供以数量化科学方法为基础的学科，是应用数学的一个分支。
其教学目的，是让学生掌握运筹学的思维方式，能应用系统的、科学的数学分析方法对系统进行定量化分析。
通过建立数学模型和模拟模型，应用计算机技术求解数学模型来解决现实生活中比较复杂的问题，达到资源优化配置、获得最优决策的目的。
的问题，达到资源优化配置、获得最优决策的目的。
通过本课程的学习，要求学生掌握线性规划、线性规划的对偶理论、运输问题、整数规划、动态规划、图与网络分析等的基本概念、基本理论和基本方法，熟悉运筹学模型在实践中的应用。
在实践中的应用。
三、学时分配学时分配教学课时分配章 节 章节内容章节内容讲课讲课实验实验 实践实践 合计合计 绪 论 运筹学的简史、模型、内容运筹学的简史、模型、内容 2 2 第一章第一章 线性规划基本性质线性规划基本性质6 6 第一节第一节 线性规划一般模型和图解法线性规划一般模型和图解法3 第二节第二节 线性规划的标准形式、解和应用模型线性规划的标准形式、解和应用模型 3 第二章第二章 单纯形法单纯形法6 6 第一节第一节 单纯形法的基本思想单纯形法的基本思想 2 第二节第二节 单纯形法的计算过程单纯形法的计算过程 2 第三节第三节 人工变量法和单纯形法补遗人工变量法和单纯形法补遗 2 第三章第三章 对偶原理对偶原理6 6 第一节第一节 线形规划的对偶关系和对偶性质线形规划的对偶关系和对偶性质 4 第二节第二节 对偶单纯形法对偶单纯形法 2 第四章第四章 灵敏度分析灵敏度分析 2 2 第一节第一节 引言引言1 第二节第二节 参数,i i b c 的影响范围的影响范围 1 第五章第五章 运输问题运输问题6 6 第一节第一节 运输问题及数学模型运输问题及数学模型 1 第二节第二节 表上作业法及应用表上作业法及应用 5 第六章第六章 整数规划整数规划4 4 第一节第一节 整数规划问题及数学模型整数规划问题及数学模型 1 第二节第二节 分支定界法分支定界法 2 第三节第三节指派问题指派问题1章 节 章节内容章节内容讲课讲课 实验实验 实践实践 合计合计 第七章第七章 动态规划动态规划4 4 第一节第一节 多阶段决策问题多阶段决策问题 1 第二节第二节 基本概念基本概念 1 第三节第三节 动态规划的应用动态规划的应用 2 第八章第八章 网络分析网络分析6 6 第一节第一节 图的基本概念和最小树图的基本概念和最小树 1 第二节第二节 最短路问题最短路问题 2 第三节第三节 最大流问题最大流问题 3 第九章第九章 决策论决策论 3 3 第一节第一节 基本概念基本概念1 第二节第二节信息分析和效用决策信息分析和效用决策2第十章第十章 对策论介绍对策论介绍 3 3复习及习题评讲复习及习题评讲6 6 合 计5454四、教学内容及教学要求四、教学内容及教学要求绪论 运筹学的简史、模型、内容（了解） 本章重点、难点：运筹学的性质特点和应用运筹学的性质特点和应用本章教学要求：了解运筹学的性质及特点、运筹学的发展历史、运筹学方法的应用、学习运筹学的意义。
（完整版）多阶段决策过程最优化问题多阶段决策过程最优化问题——动态规划的基本模型在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。
因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。
当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。
这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。
【例题1】最短路径问题。
图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。
现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、 B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。
用dk(x k，x k+1)表示在第k阶段由初始状态x k 到下阶段的初始状态x k+1的路径距离，Fk(x k)表示从第k阶段的x k 到终点E的最短距离，利用倒推方法求解A到E的最短距离。
具体计算过程如下：S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3S2: K=3，有：F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8F3(C3)=d3(C3,D3)+f4(D3)=8+3=11F3(C4)=d3(C4,D3)+f4(D3)=3+3=6S2: K=2，有F2(B1)=min{d2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+ F3(C3)}=min{9,12,14}=9F2(m)=min{d2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)}=min{16,10} =10 S4：k=1，有：F1(A)=min{d1(A,B1)+F2(B1),d1(A,B2)+F2(B2)}=min{13,13}=13 因此由A点到E点的全过程的最短路径为A—>B2一>C4—>D3—>E。
多阶段决策问题
应用条件应用条件
从起始点到终点最短距离
最优子结构性质：任何最短路径的子路径都是相对于子路径的始点和终点
的最短路径
子问题重叠性质：任何中间节点到终点的距离都被前面的节点多次使用基本思想步骤
常见的实现形式搜索，备忘录，递推
搜索，备忘录，递推搜索，备忘录，递推
搜索，备忘录，递推0-1背包问题（1）
0-1
最长子序列（
最长子序列（最长子序列（最长子序列（邮局问题（
邮局问题（
状态选择
状态选择时间与空间的权衡学习动态规划的方法。
