运筹学自考复习纲要.doc

2009年1月运筹学与系统分析自考复习纲要（一） 题型一、单选（1分*15个）二、判断、改错题（2分*10个，判断1分，改错1分）（判断、多选10分、填空10分三择一）三、名词解释（3分*3个）四、解答（5分1个，5到6个）五、一道问答题，10分六、3个计算题，总分30分（二） 重点章节一、计算题70%、80%来源于第一章、第二章、第八章，少部分来源于网络分析于系统评价二、解答、问答第一章（线性规划及其应用）：线性规划的求解过程；对偶问题的理论第三章（网络分析）：概述、计划（重点）第四章（系统与系统工程）：系统与系统工程第五章（系统分析原理及其应用）：2节原理；3节应用第六章（系统模型与系统仿真）：2节、4节第七章（系统评价）：2节、3节第八章（决策分析）：解答、问答2、3、5节（三） 具体内容（80%覆盖）第一章 线性规划及其应用*（重点）：“单纯形”法必考（求解），参见P32例1-20，考试时一般3个变量、2到3个约束条件，便于化简，参见运筹学与系统分析模拟试题集P139第25题P17、18：应用题建模（只要求建模）产品配套问题、下料问题、配料问题P44：定理1-6、1-7、1-8，掌握定理，能做到例1-27P50：系数变化，例1-31，给了问题与最终表，在变b、变c条件下要求变表P54：运输问题，最小元素法、西北角法，例1-37第二章 动态规划P64：简单概念：阶段、状态、变量、方程P71：资源分配问题，例2-4：方程、求解第三章 网络分析P96：网络计划图，给表，画网络计划图；对时间参数的计算，一般不要求；编制步骤：要理解记忆第四章 系统与系统工程P107：特征（大点，阐述）P108：分类：3、动态与静态；4、封闭系统与开放系统第五章 系统分析原理及其应用P120：“霍尔三维结构”（时间维、逻辑维、知识维）理解、阐述P121：“切克兰德方法论”*：霍尔三维结构与切克兰德方法论的比较P123-P124：系统分析6要素P124：系统过程（图5-3）第六章 系统模型与系统仿真P132：建立模型的基本要求P133：结构模型P135：构造解释结构模型的步骤P135、P136：邻接矩阵与可达矩阵的概念P142、143：直线趋势与二次曲线趋势概念P153：连续性与离散性区别*：离散仿真的概念P156：伪随机数的概念P165：系统动力学模型建模步骤P167：流程图与结构方程（从概念上区分）第七章 系统评价P175、176：论述（对价值的认识）、价值的概念、价值的特点，（1）（2）（3）P180：不确定性理论、效用理论概念P182：（单选、判断、解答题）（1）加法评分法、（2）连乘评分法、（3）加乘评分法第八章 决策分析P206：风险型、不确定型的特点、区别、方法P207：不确定型分析法（计算题）：（1）乐观法、（2）悲观法、（3）、后悔值法P212：风险型能画决策树（多级决策树，最多3级），如例8-4P215：风险系数的估计与计算（标准差），如例8-5P218：信息的价值，例8-8（考试接近例题）P221：“效用”的理解（第 1段话）（用教材的理论、要点及自己的话来阐述）P223：辨优（比系数）P224：例8-10（计算题，可以计算数，而不必在曲线上去找）P228：“线性插值法”概念附录：2007年7月复习要点及参考答案一、单项选择题（1分15）1、C（P27） 2、C（P44、45） 3、D（P46） 4、A 5、C 6、C（P66） 7、C 8、A（P122） 9、D（P153） 10、B（P45） 11、D 12、C（P120） 13、A（P59） 14、D（P123） 15、B（P135、136）二、多项选择题（2分5）1、ABDE（P132） 2、ACD（P182） 3、ABDE（P44、45） 4、ABD（P132） 5、BCD（P190） 6、ABCE（P27、28） 7、ABCE（P123） 8、AE（P210）三、名词解释（5分3）四、解答题（6分5）1、线性规划的基本概念（P8）如线性规划的定义：“求一组决策变量，使之满足线性约束条件和非负条件，并且使线性目标函数具有最优值”的一类优化问题。又如线性规划问题数学模型的一般形式了解线性规划最优解存在的几种情况（P36）最优解存在，从数量上或者1个，或者至少2个，由“线性规划问题有两不同的最优解可推有无穷多个最优解”定理（P36），显然线性规划最优解存在时只有两种情况：（1）有唯一最优解（一定在某一顶点处取得）（2）有无穷多最优解。了解线性规划最优解的存在的各种情况在单纯形法求解过程中的表现（P35、36例1-21说明）在单纯形法每次迭代时，显然基变量的检验数，若存在检验数的非基变量，以该非基变量进基作为新的基变量继续迭代，会得到一个与不进基换基时所得最优解不同的另一最优解。由“线性规划问题有两不同的最优解可推有无穷多个最优解”定理知，此时该问题有多重解。反之，如果在每次迭代时，不存在检验数的非基变量，则没有非基变量进基作为新的基变量，也即基变量是唯一确定的，这样迭代下去，如果最优解存在的话，就只能得出一个唯一的最优解。单纯形法的基本原理（P25、29）（1）线性规划模型约束条件的线性特点决定了可行域边界的线性性，可行域总是凸多边形、凸多面体或超凸多面体，单纯形正是最简单、最典型的多面凸集。（2）由于多面凸集的可行域顶点个数有限，当约束方程中含个决策变量个方程时，可行域顶点数不会超过个。因此，可以采用“对顶点逐步转移”的方法（即从可行域的一个顶点开始，转移到另一个顶点，同时使目标函数值逐步优化），当目标函数达到最优值时，线性规划问题就得到了最优解，这是单纯形法的基本思想。（3）由“可行域非空有界，则线性规划的目标函数一定可以在可行域顶点上达到最优值”定理，我们在线性规划的最优解的寻找方法上可以从根本思路上加以突破不是从无限多个可行解中去寻找最优解，而是从可行域的有限个顶点（数量）中去寻找最优解，从而把一个无限的问题转化为一个有限的问题，这是单纯形法的理论根据。可行解、最优解的基本概念（P27）满足线性规划约束条件和非负条件的决策变量的一组取值，称为线性规划的可行解，其中使线性规划目标函数达到最优值的可行解称为线性规划的最优解。2、对偶单纯形法的基本思想（P46）对偶单纯形法是在原问题的单纯形表格上，应用对偶原理求解原始线性规划最优解的一种方法。当原始问题的基既是原始问题可行基又是对偶问题可行基时，就是最优基。因此，单纯形法求解过程正是在保持原始可行（解答列基变量取值均为非负）的条件下，通过迭代逐步实现对偶可行性（非基变量检验数向量，从而成为对偶可行基）。在对偶关系中，由于和互换位置，因此设想能否在保持检验数非正条件下，逐步消除基本解的负分量，使之成为可行解，这样，该基本解就成为基本最优解。总之，对偶单纯形法的基本思想就是在保持对偶可行性条件下，通过逐步迭代实现原始可行性。对称形式的线性规划问题构造其对偶问题的一般规则（P43）若原问题为：、条件为和，则对偶问题为：、条件为和。根据这一定义，容易得到对称形式的线性规划问题构造其对偶问题的一般规则：（1）“上下交换”原问题与对偶问题中价值系数和约束条件中右端的常数交换位置；（2）“左右换位”原问题中决策向量均在价值系数和约束条件系数矩阵的右边，而在对偶问题中的决策向量均在常数向量和系数矩阵的左边；（3）“约束不等式换向”原问题的约束条件为类型，而对偶问题的约束条件变为类型；（4）“极大变极小”原问题目标函数为极大化类型，而对偶问题的目标函数变为极小化类型。线性规划的灵敏度分析的基本概念（P48）研究线性规划模型中某些系数或限制量的变化对最优解的影响及其影响程度的分析称为灵敏度分析，又称优化后分析。在线性规划求解时，目标函数和约束条件中决策变量前的系数及右端常数（即限制量）都是确定值，而最优解正是在此基础上计算得到的。但在实际中，这些系数及约束限制量并非一成不变的。例如，价值系数往往随市场情况而变动；技术革新及生产的合理组织等可以影响各种资源的消耗定额；而资源限制量往往是通过预测甚至估算得到的，加上资金变化、配制变化等因素，因而在现实中是容易变化的。现在的问题是：当这些系数发生变化时，最优解会受到什么影响？这些系数在什么范围内变化时，最优解或最优基保持不变？如果系数超出了范围，怎样才能简便、快速求出新的最优解？当资源限制有所放宽的情况下，会带来多少效益？所有这些都是灵敏度分析要讨论的内容。3、运输问题中退化解、多重解的情况（P27、57；P36）我们知道“个产地、个销地”的运输问题中，系数矩阵与其增广矩阵的秩都为，由此易知，个决策变量中，基变量一定是个，非基变量个数为个。显然非基变量都取0，而基变量取值也有可能为0。当基本解的非零分量个数小于基变量的个数时（即基变量有一个或多个以上取0），称之为退化基本解。所以在上述运输问题中，如果作业表中数字格的数目小于，也即取非0值的基变量个数小于（即有基变量取0值），则称出现了“退化现象”，该基本解称为退化（基本）解。退化在表上作业过程中的形态是：当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入运量时同时划去运输表的一行和一列，这就出现了退化（如P57表1-31）。在运输问题中，每次迭代时，如果有某非基变量的检验数等于0，则可以把该非基变量进基作为新的基变量，会得出一个与不进基换基时所得最优解不同的另一最优解，由“线性规划问题有两不同的最优解可推有无穷多个最优解”定理知，此时该问题有多重解。产销平衡运输问题的基本概念，该类问题数学模型上的特征（P57）多阶段决策问题的最优性原理（即动态规划最优化原理）（P66）动态规划最优化原理的叙述为：一个过程的最优决策具有这样的性质无论其初始状态及初始决策如何，其以后诸决策对以前所形成的状态作为初始状态的过程而言，必然构成最优决策。最优化原理的含义是：最优策略的任何一个子策略也是相应初始状态的最优策略。那么，对于具有无后效性的多阶段决策过程，如果按照子过程最优的原则来求个阶段状态的最优决策，这样构成的最优决策序列（即最优策略）肯定具有最优化原理所揭示的性质。下面用一个简单例子给以说明。设实线AB是由节点A到节点B的最优路线，在该线上任取一点M，则实线MB一定是状态M到B的最优路线。反证：若不然，设M到B有一条更优的路线，如图中的虚线MB；从A出发，先走实线AM，再走虚线MB，则显然比走实线AMB更优，与实线AMB是A到B的最优路线矛盾。确定结点间的作业时间的方法（P98）关键路线（关键线路）的基本概念（P101）4、系统工程的基本概念（P114）用定量和定性相结合的系统思想和方法处理大型复杂系统的问题，无论是系统的设计或组织建立，还是系统的经营管理，都可以统一的看成是一类工程实践，统称为系统工程。系统工程是合理开发、改造和管理大规模复杂系统所需思想、程序、方法与技术的总称。系统模型的基本概念（P131）所谓系统模型就是把构成系统的各个要素（或子系统），通过适当的筛选后，用数学方程、图表以及实物形式来描述系统的结构和系统未来行为的一种简明映像。系统仿真的基本概念（P152）所谓系统仿真，就是根据系统分析的目的，在分析系统各要素性质及其相互关系的基础上，建立能描述系统结构或行为过程的、且具有一定逻辑关系或数学方程的仿真模型，据此进行试验或定量分析，以获得正确决策所需要的各种信息。系统工程研究问题的主要观点（P120）霍尔三维结构。（1）霍尔三维结构是1969年美国学者霍尔提出来的，其内容反映在可以直观展示系统工程各项工作内容的三维结构图中，即时间维、逻辑维、知识维或专业维。（2）霍尔三维结构强调明确目标，核心内容是最优化，并认为现实问题基本上都可归纳成工程系统问题，应用定量分析手段，求得最优解。该方法论具有研究方法上的整体性（三维）、技术应用上的综合性（知识维）、组织管理上的科学性（时间维和逻辑维）和系统工程工作的问题导向性（逻辑维）等突出特点。（3）霍尔三维结构集中体现了系统过程方法的总体化、综合化、最优化、程序化和标准化的特点，是所有系统工程基本工作过程的集中体现。切克兰德方法论。（1）切克兰德方法论是70年代中期英国切克兰德教授在霍尔方法论的基础上提出来的一种软系统工程方法论，主要针对社会问题和“软科学问题”。（2）其主要内容和工作过程如下：认识问题、根底主义、建立概念模型、比较与探寻、选择、设计与实施、评估与反馈。（3）切克兰德方法论的核心是比较与探寻（比较学习），它强调从“理想”模式（概念模型）与现实状况的比较中，探寻改善现状的途径，使决策者满意。霍尔三维结构与切克兰德方法论的异同点（P122）霍尔三维结构与切克兰德方法论均为系统工程的方法论，均以问题为起点，具有相应的逻辑过程。不同点：（1）霍尔方法论主要以工程系统为研究对象，而切克兰德方法更适合于对社会经济和经营管理等“软”系统问题的研究；（2）前者的核心内容是优化分析，后者的核心内容是比较学习；（3）前者更多关注定量分析方法，而后者比较强调定性或定性与定量有机结合的基本方法。系统分析的要素（P123）（1）问题（2）目的与目标（3）方案（4）模型（5）评价（6）决策者。（阐述见教材）邻接矩阵、可达矩阵的基本概念（P135）邻接矩阵是用矩阵描述各节点（要素）间的邻接状态的一种矩阵。矩阵元素定义如下：要素与具有邻接关系，即可以一步到达（或直接影响、直接导致等），则令；要素与不相邻接，则令。所谓可达矩阵，是指用矩阵反映有向连接图各节点（要素）之间，通过一定路线可以到达的程度。矩阵元素定义如下：节点经过有限步后可以到达节点，则令；节点经过有限步后不能到达节点，则令。蒙塔卡罗法的概念（P153）蒙塔卡罗法是一种适用于对离散事件动态系统进行仿真的方法。这种方法的基本思想是运用一连串随机数来表示一项随机事件的概率分配，然后利用任意取得的随机数，从该项概率分配中获得相应的随机变量值。随机数的基本概念（P156）随机数是指在区间（一般为）之间的随机采样值。所谓伪随机数是指：用一种递推型算法的公式来产生“随机”数。但它不具有真正的随机性，因此称作“伪随机数”。系统决策的灵敏度分析的基本概念（P216）在决策分析开始阶段，由于各行动方案所造成的结果（益损值）还不是既成事实，而只是根据过去的统计资料和经验，来预测和判断某种自然状态可能出现的概率，即主观概率。至于如何选择最优方案，还需要进行有关计算和分析。灵敏度分析就是这种计算和分析的一个方面。解释结构模型化（ISM）技术基本思想（P134）解释结构模型法是美国华费尔教授于1973年开发的，用于分析和揭示复杂关系结构的有效方法。其特点是把复杂的系统分解成若干子系统或系统要素，利用人们的实践经验和知识，借助电子计算机为工具，最终将系统分成一个“多级递阶形式”的解释结构模型。其步骤为：（1）组织ISM工作小组；（2）设定问题；（3）选择系统要素；（4）建立邻接矩阵和可达矩阵；（5）分解可达矩阵，建立结构模型；（6）根据结构模型建立解释结构模型。5、决策树法的基本概念（P211）所谓决策树法就是利用树形图模型来描述决策分析问题，并直接在决策树图上进行决策分析的一种方法。其决策准则可以是益损期望值，或者是经过变化的其它指标值。其步骤是：（1）绘制决策树图；（2）计算各方案的益损期望值，并将计算结果标注在相应的状态节点上；（3）将计算所得的各方案的益损值加以比较，选择其中最大的期望值标注在决策节点上。决策所需的信息类型及其价值（P217）决策所需的信息一般分为两类，一类是完全信息，即据此可以得到完全肯定的状态信息，这样有助于正确的决策，从而能获得最优的方案。但现实生活中，在多数情况下要获得这类完全信息的费用是很大的，或者根本不可能做到。另一类是抽样信息，这是一类随机抽样所得到的信息，据此用统计方法来推断状态出现的概率。抽样信息虽不十分精确可靠，但为获得此类信息所要付出的代价相对是比较小的，且在实际生活中的多数情况下，也只能获得此类信息以供决策之用。不确定决策的基本条件（P206、207）（1）存在决策人期望达到的决策目标；（2）有两个或两个以上不以决策人意志为转移的自然状态；（3）有两个或两个以上可供决策人选择的行动方案；（4）不同的行动方案在各种自然状态下其益损值可以定量的估算出来；（5）各种自然状态，未来发生哪一种自然状态，决策人无法肯定，同时缺少各种自然状态出现的概率信息。化多目标为单目标的方法，其原理及应用时注意的问题（P226）五、计算题（10分3）1、单纯形法求解线性规划问题，线性规划问题的建模（即应用题）（应用题参见教材P11第二节，如P18例1-8下料问题）（计算参见P32例1-20、P48例1-30）2、对偶单纯形法求解（参见教材P47例1-29）3、写出对偶问题，应用对偶理论求原问题（参见教材P45例1-27、1-28，P47例1-29）4、目标函数变化（即价值系数c变），右侧常量变化（即约束条件b变化）的灵敏度分析（参见教材P48例1-31、P50例1-31、1-32）思路：（1）非基变量价值系数变化，基检验数为0不会变，其它非基变量的检验数也不变，只有该变化价值系数的非基变量的检验数在变。故价值系数变化的范围应该不影响最优解为前提、为尺度，换言之（一般情况）要求变化的检验数也小于等于0，就给出非基变量价值系数变化范围。（2）基变量价值系数变化，基检验数为0不会变，其它非基变量的检验数都要变。同理，（一般情况）要求变化的检验数也小于等于0，就给出基变量价值系数变化范围。（3）b在变，用最优基逆矩阵的方法更新基本解，令基本解大于等于0，就可得保持最优基不变（即定性不变，生产品种不变，数量一般要变，函数值也要变）的b范围。5、运输问题，表上作业法（参见教材P55例1-37及补充材料的例题）6、求最短路（参见教材P81例3-1、P86例3-3）思路：应用最优化原理 两个基本算法：狄克斯拉算法（固定标号、临时标号）P81、表格算法P857、悲观法、乐观法、后悔值法（P207算法、例8-2）决策分析的类型及方法知识结构 例4、（参见教材P32例1-20、P48例1-30）引入松弛变量，将线性规划化为标准型：，满足，由此可以列出初始表并迭代出最优解，过程如下。初始表CBXB 步骤（考试可以不必写出） 2 1（1）基变量x3x4x5，计算；基变量x3x4x5检验数为0，计算非基变量x1x2的检验数（2）因为非基变量检验数不是“全部小于等于0”，且不是“最优解无界”，知算法还要继续（3）在非基变量检验数2、4中取大者4，第二列作为主元列（4）做方程右端系数列（即列，基向量解答列）与主元列对应元素的比值（5）选最小比值5，第二行作为主元行，为主元素 检验数进行基变换，（主元列对应的变量）进基，（主元行对应的变量）出