考研管理科学与工程专业通用核心知识点.pdf

硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 0 页页/共共 40 页页 硕士研究生专业通用核心知识点数据库 管理科学与工程 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 1 页页/共共 40 页页 目录目录 前言前言.4 硕士研究生专业通用核心知识点使用说明.4 1 运筹学运筹学 20 通用核心知识点通用核心知识点.6 1.1 通用核心知识点一：整数规划的数学模型.6 1.2 通用核心知识点二：0-1 型整数规划.7 1.3 通用核心知识点三：运输问题的数学模型.8 1.4 通用核心知识点四：表上作业法.9 1.5 通用核心知识点五：非平衡运输问题.11 1.6 通用核心知识点六：灵敏度分析.14 1.7 通用核心知识点七：线性规划的数学模型.14 1.8 通用核心知识点八：单纯形方法.15 1.9 通用核心知识点九：网络最大流问题.17 1.11 通用核心知识点十一：排队模型.19 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 2 页页/共共 40 页页 1.12 通用核心知识点十二：决策树.20 1.13 通用核心知识点十三：对偶单纯形法.21 1.14 通用核心知识点十四：对偶问题的基本性质.22 1.15 通用核心知识点十五：线性规划的对偶问题.22 1.16 通用核心知识点十六：矩阵对策的数学模型.24 1.17 通用核心知识点十七：动态规划问题的求解方法.25 1.18 通用核心知识点十八：动态规划问题的基本方程.26 1.19 通用核心知识点十九：确定性存贮模型.27 1.20 通用核心知识点二十：随机性存贮模型.29 2 管理信息系统管理信息系统 8 通用核心知识点通用核心知识点.30 2.1 通用核心知识点一：网络应用.30 2.2 通用核心知识点二：EXTRANET的内涵与作用.31 2.3 通用核心知识点三：信息基础知识.33 2.4 通用核心知识点四：联机分析与联机处理.34 2.5 通用核心知识点五：事务处理系统.35 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 3 页页/共共 40 页页 2.6 通用核心知识点六：商业智能.35 2.7 通用核心知识点七：管理信息系统的分类.36 2.8 通用核心知识点八：信息系统与组织的相互影响.37 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 4 页页/共共 40 页页 前言前言 硕士研究生专业通用核心知识点使用说明硕士研究生专业通用核心知识点使用说明 1 纠正错误认识，先人一步赢得比较优势纠正错误认识，先人一步赢得比较优势 在专业确定后，还需更多时间考虑更多因素才能最终决策报考学校。在定了专业却没定学校的这段时期，很多普通学生不会进行专业课学习，因为他们认为同一专业，不同学校考的不一样，在没有最终确定学校之前，无法开始学习。其实这是一个错误的认识。而对于万学海文考研高端学员来讲，应该打破和消除这种错误的认识，及早准备专业课学习，为专业课后续阶段的学习打下基础，赢得时间，修炼竞争力。2 通用核心知识点确定原则通用核心知识点确定原则 因为，虽然不同学校同一专业学习内容不全相同，但只要是同属于一个专业，无论哪个学校的考查范围，一定有 20%左右的知识点是重叠的。这不同学校都一致要求掌握的 20%相同知识点，称之为通用知识点。对于统考学科来讲，每年考查重叠的知识点，即通用知识点。通用知识点往往是基础层面的知识点，也就是在未定学校之前就应该开始学习的专业课内容。硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 5 页页/共共 40 页页 万学专门研发的专业通用核心知识点数据库，可以很好的帮助您锁定目标专业 20%的通用知识点，并让您在启动专业课整体复习之前，就获取了选超其他竞争对手的比较优势，这个比较优势，既是先人一步的时间优势，又是赢在起跑线上的竞争优势。3 通用核心知识点学习路径通用核心知识点学习路径 您在确定专业后，就应采用特殊方案锁定通用知识点，然后针对通用知识点，进行 2 轮预热理解与 1 轮初始记忆，快速理解和掌握专业通用层面的基础知识。通过通用核心知识点的学习，既要打牢基础，又要形成学科初步逻辑思路、整体框架，为整体、深入学习专业课知识，以及实战演练，提供有效的知识积淀。硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 6 页页/共共 40 页页 1 1 运筹学运筹学 2020 通用核心知识点通用核心知识点 1.1 通用核心知识点一：整数规划的数学模型通用核心知识点一：整数规划的数学模型 整数规划是一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是 0-1 规划，它的变数仅限于 0 或 1。不同于线性规划问题，整数和 01 规划问题至今尚未找到一般的多项式解法。组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、旅行推销员问题,车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。历年真题链接历年真题链接：某厂生产某厂生产 A，B 两种产品分别要经过两道化学工序，生产一个两种产品分别要经过两道化学工序，生产一个 B 的同时会产生两个副产品的同时会产生两个副产品 C，且不增，且不增加任何费用，但加任何费用，但 C 最多只能售出最多只能售出 5 个，每个盈利个，每个盈利 3 元，多于的需要销毁，每个的销毁费用为元，多于的需要销毁，每个的销毁费用为 2 元，且元，且 A，B 两种产品经两种产品经过两道工序的时间，及总的可用时间，单位利润如下：过两道工序的时间，及总的可用时间，单位利润如下：硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 7 页页/共共 40 页页 A B 可用时间可用时间 前道过程前道过程 2 3 16 后道过程后道过程 3 4 24 单位利润单位利润 4 10 试建立此问题的模型，使总收益最大。试建立此问题的模型，使总收益最大。北京大学北京大学 2007 年真题年真题 计算题计算题 分值不详分值不详 1.2 通用核心知识点二：通用核心知识点二：0-1 型整数规划型整数规划 0-1 型整数规划是整数规划中的特殊情形，它的变量 0-1 仅取值 0 或 1。这时 0-1 称为 0-1 变量，或称二进制变量。0-1 仅取值 0 或 1。在实际问题中，如果引入 0-1 变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。对 0-1 型整数规划，若有 n 个决策变量，则可以产生 2n个可能变量的组合，因此完全枚举是不可能的。求解 0-1 型整数规划问题的解法均是部分枚举法或称为隐枚举法。基本思想是：在 2n个可能的变量组合中，往往只有一部分是可行解。只要发现某个变量组合不满足其中的某一约束条件时，就不必要检验其他的约束条件是否可行。若发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界法）。在以后求解过程中，每当发现比原来更好的可行解，则依次替代原来的过滤条件（可减少运算次数，较快地发现最优解）。历年真题链接：某人求解某平衡运输问题，得到该问题的最优运输方案和最优运费，然后将某一产地的产量增加历年真题链接：某人求解某平衡运输问题，得到该问题的最优运输方案和最优运费，然后将某一产地的产量增加2020单位，同时将另一销地的销量增加单位，同时将另一销地的销量增加2020单位，其它数据不变，重新求解最优运输方案；结果发现，最有运费在运量增加单位，其它数据不变，重新求解最优运输方案；结果发现，最有运费在运量增加 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 8 页页/共共 40 页页 后反而下降，请解释为什么会发生这类现象？华中科技大学后反而下降，请解释为什么会发生这类现象？华中科技大学20072007年真题年真题 计算题计算题 2020分分 1.3 通用核心知识点三：运输问题的数学模型通用核心知识点三：运输问题的数学模型 运输问题：寻求一定的货物从多个生产地点运往多个销售地点的最经济的方法。产销平衡问题：产量等于销量的运输问题。产销不平衡问题：产量不等于销量的运输问题，有产大于销的运输问题和产小于销的运输问题两种。产销平衡问题的线性规划模型：对于产销不平衡问题，上述模型的两组函数约束方程中，有一组将改为不等式约束，即，或。硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 9 页页/共共 40 页页 对于产销平衡问题，很显然，因此，在线性规划模型中，前 个约束线形相关，其系数阵 A 的秩为，即其基本可行解中基变量的个数为 个。求解时需消除一个约束，才能够求得基本可行解，从而用单纯形法等方法求解运输问题。历年真题链接：某人求解某平衡运输问题，得到该问历年真题链接：某人求解某平衡运输问题，得到该问题的最优运输方案和最优运费，然后将某一产地的产量增加题的最优运输方案和最优运费，然后将某一产地的产量增加 2020单位，同时将另一销地的销量增加单位，同时将另一销地的销量增加 2020 单位，其它数据不变，重新求解最优运输方案；结果发现，最有运费在运量增加后单位，其它数据不变，重新求解最优运输方案；结果发现，最有运费在运量增加后反而下降，请解释为什么会发生这类现象？反而下降，请解释为什么会发生这类现象？1.4 通用核心知识点四：表上作业法通用核心知识点四：表上作业法 表上作业法是用列表的方法求解线性规划问题中运输模型的计算方法。是指线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭回路法、位势法或矩形法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。同单纯形法一样，表上作业法首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常 见的是左上角法（或西北角法）、最小元素法和Vogl 近似法(VAM)，其中，后两法的效果较好。以最小元素法为例，说明表上作业法的详细求解过程。我们通过下面的例子（见表 8-3）介绍最小元素法。根据 8-3 的数据，求如何安排使运输费最小。表 8-3 一个运输问题数据关系表 D1 D2 D3 D4 供应量 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 10 页页/共共 40 页页 S1 1000 4000 5000 S2 2500 2000 1500 6000 S3 2500 2500 需求量 6000 4000 2000 1500 13500 求出 mincij：i=1，2，3；j=1，2，3，4=c12（不止一个，适当选取一个）及 mina1，b2=b2=4000 优先满足 D2 需求。取 x12=4000，划去第二列。S1 处余 1000。求出 mincij：i=1，2，3；j=1，2，3，4=c23 及 mina2，b3=b3=2000 满足 D3 需求。取 x23=2000，划去第三列。S2 处余 4000。求出 mincij：i=1，2，3；j=1，4=c31 及 mina3，b1=a3=2500 由 S3 供应。取 x31=2500，划去第三行。D1 处余 3500。求出 mincij：i=1，2；j=1，4=c11 及 minS1 余量 1000，D1 需要量 3500=1000 从 S1 运 1000 至 D1。取 x11=1000，划去第一行。D1 处尚需 2500。求出 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 11 页页/共共 40 页页 mincij：i=2；j=1，4=c24 及 minS2 余量 4000，D1 需要量 1500=1500 从 S2 运 2500 至 D1。取 x24=1500，划去第四列。S2 处尚需 2500。运 S2 处 2500 至 D1。取 x21=2500，同时划去第二行和第一列。至此，给出了一个可行方案。此结果填入表 8?中，相应运费为 42000 元。历年真题链接：设有一个铁矿联合企业，下设三座铁矿石矿山（历年真题链接：设有一个铁矿联合企业，下设三座铁矿石矿山（A1、A2、A3）和四个炼铁厂（）和四个炼铁厂（B1、B2、B3、B4），），单位时间内矿山产量分别为单位时间内矿山产量分别为 9、8、6 个单位，炼铁厂需求分别是个单位，炼铁厂需求分别是 7、5、8、3 个个单位，单位运价如下表。问怎样调运可使单位，单位运价如下表。问怎样调运可使总运费达到最小？（用表上作业法求解）总运费达到最小？（用表上作业法求解）上海交通大学上海交通大学 2007 年真题年真题 计算题计算题 20 分分 1.5 通用核心知识点五：非平衡运输问题通用核心知识点五：非平衡运输问题 核心考点四我们介绍了标准形运输问题模型的表上作业法。所谓标准型运输问题是指，目标函数为最小值类型，同时约束条件为等式，即所谓产销平衡情形。对于非标准形式是不能使用表上作业法求解的。为应用表上作业法，可先行通过化归为标准形式后再求解，具体说明如下：用表格形式写出非平衡运输问题的模型如表 410。表 410 单位：10 元/吨 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 12 页页/共共 40 页页 本问题为产销（供过于求）情形，为了化归为标准形式，可通过虚设一个销地 B0，其销量为，相应运价均为零（因为这是个虚设的销地，各个产地都不可能往那里运货，运价自然为零），即可化为产销平衡问题。由此，便得到本问题的产销平衡表如表 411。使用表上作业法求解得最优方案为：表 411 单位：10/吨 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 13 页页/共共 40 页页 注意：意味着产地 将有 2 吨的产品送往虚设的销地，这是不可能的。我们的解释是，该产地有 2 吨产品应就地贮存。是在求解中为保证基变量个数而保留的一个基变量，因其取值为零，故本问题的解是一个所谓的退化解。这种情形在运输问题求解中是经常发生的，务请注意。因为如果少了这个基变量，将影响检验数的求出而使问题的求解遇到困难。另外，在确定初始方案时，自然虚设销地的运价最小，自然被首先作为基变量选定。但是，这种做法可能导致求解过程复杂化。因此，在开始时，找最小元素时一般先不考虑它们，到最后再加以处理。同理，对于产量小于销量情形，可虚设一个产地而化为产销平衡问题后再求解，其结果是某个销地的产品出现脱销。历年真题链接：将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设历年真题链接：将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的的_，在模型中相当于，在模型中相当于增加若干个增加若干个_变量。变量。天津大学天津大学 2007 年真题年真题 填空题填空题 5 分分 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 14 页页/共共 40 页页 1.6 通用核心知识点六：灵敏度分析通用核心知识点六：灵敏度分析 灵敏度分析是研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。因此，灵敏度分析几乎在所有的运筹学方法中以及在对各种方案进行评价时都是很重要的。对于线性规划问题：这里 max 表示求极大值，s.t.表示受约束于，X 是目标函数,xj 是决策变量。通常假定 aij，bi 和 cj 都是已知常数。但是实际上这些参数往往是一些根据估计或预测得到的数据，因而存在误差。同时，在实际过程中，这些参数还会发生不同程度的变化。例如，在处理产品搭配的线性规划问题中，目标函数中的 cj 一般同市场条件等因素有关。当市场条件等因素发生变化时，cj 也会随之而变化。约束条件中的 aij 随工艺条件等因素的变化而改变，bi 的值则同企业的能力等因素有关。线性规划中灵敏度分析所要解决的问题是：当这些数据中的一个或几个发生变化时，最优解将会发生怎样的变化。或者说，当这些数据在一个多大的范围内变化时最优解将不发生变化。历年真题链接：已知一个线性规划问题的灵敏度分析报告如下（变动单元格和约束条件），（历年真题链接：已知一个线性规划问题的灵敏度分析报告如下（变动单元格和约束条件），（1）当）当 X1 的目标的目标系数增加系数增加 2 单位，同时单位，同时 X2 的目标函数减少的目标函数减少 5 单位时最优解是否改变？（单位时最优解是否改变？（2）当第一约束的右端项减少）当第一约束的右端项减少 2 单位，同单位，同时第二约束的右端增加时第二约束的右端增加 2 单位，第三约束的右端项增加单位，第三约束的右端项增加 2 单位时目标值改变多少？（单位时目标值改变多少？（3）哪些约束是起作用约束？）哪些约束是起作用约束？第二约束的影子价格为第二约束的影子价格为-2 表示什么意义？表示什么意义？华中科技大学华中科技大学 2007 年真题年真题 计算题计算题 20 分分 1.7 通用核心知识点七：线性规划的数学模型通用核心知识点七：线性规划的数学模型 线性规划所研究的问题是：在线性约束条件下，使线性目标函数达到最优。硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 15 页页/共共 40 页页 例如：在有限资源条件下，确定生产产品的品种、数量，使产值或利润最大；在物资调配时，如何决定产地和销地之间的运输量，既满足需求，又使得运费最少；在一定库存条件下，确定库存物资的品种、数量、期限，使库存效益最高；在食品、化工、冶炼等企业，常常用几种原料，制成达到含有一定成分的产品，确定各种原料的选购量，使得成本最小，等等。为了解决实际问题，首先需要把它归结为数学问题，即建立数学模型.线性规划问题的数学模型是描述实际问题的抽象的数学形式。线性规划问题的数学模型是指求一组满足一个线性方程组（或线性不等式组，或线性方程与线性不等式混合组）的非负变量，使这组变量的一个线性函数达到最大值或最小值的数学表达式。建立数学模型的一般步骤：1.确定决策变量（有非负约束）；2.写出目标函数（求最大值或最小值）；3.写出约束条件（由等式或不等式组成）。历年真题链接：某电台广播，按照法律规定，商业节目不得少于总时间的历年真题链接：某电台广播，按照法律规定，商业节目不得少于总时间的 20%，可获利，可获利 n 元元/小时小时；新闻节目；新闻节目每小时须占每小时须占 5%,可获利可获利 m 元元/小时；音乐节目不少于小时；音乐节目不少于 10%，可获利，可获利 p 元元/小时；小时；问：问：1.按照法律规定应怎样安排电台的节目时间；按照法律规定应怎样安排电台的节目时间；2.如果不考虑法律规定，怎样安排节目播出时间获利最大如果不考虑法律规定，怎样安排节目播出时间获利最大?北京大北京大学学 2008 年真题年真题 计算题计算题 分值不详分值不详 1.8 通用核心知识点八：单纯形方法通用核心知识点八：单纯形方法 求解线性规划问题的通用方法。单纯形是美国数学家 G.B.丹齐克于 1947 年首先提出来的。它的理论根据是：线性规划问题的可行域是 n 维向量空间 Rn 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 16 页页/共共 40 页页 解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，x n 的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：存在着一个最优解；存在着无穷多个最优解；不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。单纯形法的一般解题步骤可归纳如下：把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤 3 进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有 106 个决策变量和 104 个约束条件的线性规划问题已能在计算机上解得。改进单纯形法 原单纯形法不是很经济的算法。1953 年美国数学家 G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。对偶单纯形法 1954 年美国数学家 C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为 mincx|Ax=b，x0，硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 17 页页/共共 40 页页 则其对偶问题为 maxyb|yAc。当原始问题的一个基解满足最优性条件时,其检验数 cBB-1A-c0。即知 ycBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。数学优化中，由 George Dantzig 发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是 Nelder-Mead 法或称下山单纯形法，由 Nelder 和 Mead 发现（1965 年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。这二者都使用了单纯形的概念，它是 N 维中的 N+1 个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。历年真题链接：历年真题链接：已知线性规划（已知线性规划（.）的最优单纯型表为（）的最优单纯型表为（.），（），（1）填空完成上面单纯型表，并求其对偶问题的最优解；（）填空完成上面单纯型表，并求其对偶问题的最优解；（2）求出）求出 C2和和 C3 的值，并确定的值，并确定 C3 增加多少时，线性规划有无穷多个最优解。增加多少时，线性规划有无穷多个最优解。华中科技大学华中科技大学 2007 年真题年真题 计算题计算题 20 分分 1.9 通用核心知识点九：网络最大流问题通用核心知识点九：网络最大流问题 考虑如下流网络 N=(V,A,U,D)：节点 s 为网络中唯一的源点，t 为唯一的汇点，而其它节点为转运点。如果网络中存在可行流 f，此时称流 f 的流量（或流值，flow value）为 ds（它自然也等于-dt），通常记为 v 或 v(f)，即 v=v(f)=ds=-dt。对这种单源单汇的网络，如果我们并不给定 ds和 dt（即流量不给定），则网络一般记为 N=(s,t,V,A,U)。最大流问题（maximum flow problem）就是在 N=(s,t,V,A,U)中找到流值最大的可行流（即最大流）。我们将会看到，最大流问题的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。因此，用线性规划的方法，最大流问题可以形式地描述如下：硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管理科学与工程科学与工程 本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下本文档为万学教育海文考研专业课教研中心版权所有，任何人、任何组织都不得在无万学教育海文考研专业课教研中心授权情况下传播、复制、销售本文档，违者将受法律制裁！传播、复制、销售本文档，违者将受法律制裁！第第 18 页页/共共 40 页页 Max v s.t.，Ajiuxijij),(,0.历年真题链接：历年真题链接：由网络图如下（弧旁数字为容量由网络图如下（弧旁数字为容量 C），（），（1）求网络中由发点集（）求网络中由发点集（Vs1 和和 Vs2）和收点集（）和收点集（V11 和和 V12）的最大流与最小截集。（的最大流与最小截集。（2）若弧（）若弧（v1，v3）的容量改变量为）的容量改变量为C13,试讨论对最大流量的影响。试讨论对最大流量的影响。华中科技大学华中科技大学 2007 年真年真题题 计算题计算题 20 分分 1.10 通用核心知识点十：网络方法在计划中的应用通用核心知识点十：网络方法在计划中的应用 工程项目管理就是一个计划控制的过程，先根据项目的要求制定最优的计划方案，再根据计划进行控制调整以保证计划的正确实施，一旦发现偏差则立刻进行调整或修订计划，直至项目完工。工程项目计划主要包括针对项目三大目标所制定的进度计划、费用计划和资源计划。在项目管理中，这些计划的制定通常采用网络计划的方法，即把实际的计划抽象为逻辑关系图，或称为网络图。然而初步的网络计划往往难以很好的满足项目目标的要求，因此必须需要对其进行优化。网络优化即是以网络计划为基础，在满足既定约束条件下按某一目标，通过不断改进网络计划，寻求满意的方案。网络优化的方法有很多，且已在现代项目管理中得到了大量的运用。主要包括了工期优化、费用优化和资源优化。工期优化问题就是采取措施将工期缩短到希望的期限之内；费用优化的问题是寻求费用最短的工期；资源的优化有两种：一是在资源有限条件下寻求最短工期；一类是总工期不变的条件下使资源分布均匀。历年真题链接：某施工单位提交的一项目的网络计划如下图所示历年真题链接：某施工单位提交的一项目的网络计划如下图所示，箭线下面的数字为该工作（工序）的正常工作时，箭线下面的数字为该工作（工序）的正常工作时间（天），要求工期间（天），要求工期 18 天。天。1.监理工程师在审查该图时发现工作监理工程师在审查该图时发现工作 D 的紧前工作除的紧前工作除 B 外还应有外还应有 A，请在图中把这一关系正，请在图中把这一关系正 硕士研究生专业通用核心知识点数据库：硕士研究生专业通用核心知识点数据库：管理管