运筹学基础串讲讲义.doc

运筹学基础串讲讲义课程介绍一、课程性质运筹学是计算机、数学和经济管理等近20个专业本科生和专科生的必修课程之一。运筹学基础是全国高等教育自学考试计算机信息管理专业的专业基础课，是一门理论与实际结合的课程。通过本课程的学习，能够理论联系实际，把书本上的知识可以直接应用到日常生活中去，提高分析和解决问题的能力。在考试中出现的考题并不难，跨章节的考题很少，但是题量很大，学员在学习的过程中要熟练掌握各章的例题和课后练习题，并提高计算速度。二、教材的选用自学教材：运筹学基础，全国高等教育自学考试指导委员会组编，张学群主编，经济科学出版社 2002年版三、章节体系计算机体系结构共11章，可分为三部分：第1章为第一部分，介绍运筹学的基本概念、决策过程的步骤，提出问题、分析问题和解决问题。第二部分主要内容为预测，即利用以前和现在的资料，应用不同的方法预测将来要发生的事情并做好准备，主要包含：第2章、第3章、第9章和第11章。第三部分主要内容为优化，即如何利用现有资源，合理安排之后设计可行方案，达到所耗资源最少或获得利润最大的问题，主要包含：第4章、第5章、第6章、第7章、第8章和第10章。考情分析一、题型与分值从题型与分值来看，本课程共有四种题型模式：单项选择，填空，名词解释和计算，计算又分计算题、计算题、计算题和计算题。题型与分值情况如下：单选（共15小题，每题1分，共15分）；填空（共10小题，每题1分，共10分）；名词解释（共5小题，每题3分，共15分）；计算题（共3小题，每题5分，共15分）；计算题（共3小题，每题5分，共15分）；计算题（共2小题，每题7分，共14分）； 计算题（共2小题，每题8分，共16分）。二、知识点分布从知识点分布来看，本课程试题覆盖了教材11章的全部内容。1、单选题：覆盖面最广，15个选择题中每章12题，每章都要涉及考察基本知识点，利用排除法很容易拿分，是一个主要的得分点，尽量不丢分。2、填空题：共10个，以书中原话为主，11章中除了1章（每年都有变化）外每章出一个。这也是一个得分点，主要以平时积累为主。3、名词解释题：主要是考查学生掌握基本概念的能力，可以把名词解释题看成是单选和填空的翻版，只不过是换了一个形式考查，名词解释的分布基本上能够覆盖5章的内容这部分分值不好好拿。4、计算题：共10题，除了第一章基本上每章一题，能够覆盖10章的内容基本题型教材中都有，考试中试题换汤不换药，仅仅改变说法与数值，掌握基本方法后这一部分是最重要的得分点，题量较大。整体来看，第一章概论会出填空和选择，没有计算，后面10章各种题型都会覆盖，知识点分布均匀，从每章23个知识点中考察1个。重点章节主要是第2章，第3章，第4章，第5章，第6章，第7章，第8章，第10章。第1章和第11章是知识点考查最少的两章。三、试题难度从试题难度来看，试题绝大部分属于大面知识。对于重点知识每年都会重复出现，只是以不同的形式，或者考查不同的内容。这一点大家要特别注意，不要以为以前考过的知识点就不会再考。虽然每年均有偏题出现，一般是属于课程涉及的较细的内容，但所占比例较低，属于正常情况。总体而言，试题较为容易。需特别注意细节问题，且题量比较大，考生应做好心理准备。注意：最后提醒考生注意答题的规范要求。答题是需要答在答题卡上的，考试中注意填写要求。四、本课程的复习方法在最后的临考复习阶段，学员应着重注意以下问题：1. 依据运筹学基础考试大纲的要求，在前面系统学习的基础上，对重点章节要仔细阅读，对重考率高的考点要重点理解和记忆。2. 参考历年考题在对教材有一定的把握后，学员应当参阅以前年度的考试试题，透过历年的考题了解题型、了解不同类型的考题的相关知识点。3. 系统训练解决应试教育的方法离不开习题的训练。到目前这个阶段，学员应多做综合性的模拟题，考查自己对整体教材内容融会贯通的掌握程度。回顾并复习以往的错题，弥补不足和弱点。注意：该门课程考试计算量较大，考生可携带计算器。第一章 导论复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题和名词解释题型都要加以练习。重要考点：运筹学定义、决策方法分类和进行决策的步骤等。1.1 概述1、运筹学：Operations Research,简称OR，是一门研究如何有效地组织和管理人及系统的科学。运筹学利用计划方法和有关多学科的要求，把复杂功能关系表示成数学模型，其目的就是通过定量分析为决策和揭露新问题提供数量根据。2、决策方法分类 定性决策：根据决策人员的主管经验或感受到的感觉或知识而制定的决策。 定量决策：借助于某些正规的计量方法而做出的决策。 混合性决策：运用定性和定量两种方法才能制定的决策。1.2 应用运筹学进行决策过程的几个步骤1、观察待决策问题所处的环境 问题域的环境有内部环境和外部环境（1） 内部环境：问题域内部人、财、物之间的交互活动。（2） 外部环境：问题域界面与外界的人、财、物之间的交互活动。注意两者的区别。2、分析和定义待决策的问题3、拟定模型 这个工作是OR项目中最费时的部分。4、选择输入资料5、提出解并验证它的合理性 敏感度实验：一旦有了模型的解答，就要试图改变模型及输入，并注视将要发生什么样的输出，一般把这样的过程叫做敏感度实验。6、实施最优解本章总结：本章涉及到考试内容比较少，最多出1个选择、1个填空和1个名词解释，没有计算题，同学们只需留意几个概念即可。第二章 预测复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：预测定义；预测方法的分类；预测的程序；专家小组法和特尔斐法；时间序列预测法；回归模型预测法等。2.1 预测的概念和程序一、预测的概念预测：对未来不确定的事件进行估计或判断。预测是决策的基础。二、预测方法的分类 从内容分类：1、经济预测：又分为宏观经济预测和微观经济预测。 2、科技预测：又分为科学预测和技术预测。 3、社会预测：研究社会发展有关的问题，如人口增长预测等。 4、军事预测：研究与战争有关的问题。 从应用方法分类：1、定性预测：利用直观材料，依靠个人经验的主观判断和分析能力，对未来的发展 进行预测，又称之为直观预测，主要有专家小组法和特尔斐法。2、定量预测：根据历史数据和资料，应用数理统计方法或者利用事物发展的因果关系来预测事物的未来。利用历史数据来预测称为外推法，常用的有时间序列分析法；利用事物内部因素的因果关系来预测称为因果法，常用的有回归分析法、经济计量法、投入产出分析法等。从预测时间期限分类：1、 长期预测2、 中期预测3、 短期预测（又叫近期预测）预测期限划分标准不统一，需要记住的有：经济预测35年为长期，13年为中期，年内为短期；科技预测3050年以上为长期，1030年为中期，510年为短期。 三、预测的程序 1、确定预测的对象或目标。 2、选择预测的周期。 3、选择预测的方法。 4、收集有关资料。 5、进行预测。2.2 定性预测法一、特尔斐法1、定义：又称函询调查法，是希望在“专家群”中取得比较一致的意见的方法。2、特尔斐法的实施程序 （1）确定课题。 （2）选择专家：该“专家”不是全指学者、教授、高级工程师等，而是也指熟悉预测课题的人。 （3）设计咨询表。 （4）逐轮咨询和信息反馈。 （5）采用统计分析方法，对预测结果进行定量评价和描述。 3、特尔斐法需要时间比较长，适用于长期或中期预测。二、专家小组法 1、定义：又称座谈会法，是在接受咨询的专家之间组成一个小组，面对面的进行讨论与磋商，最后对需要预测的课题得出比较一致的意见。 2、专家小组法的预测过程比较紧凑，适用于短期预测。2.3 时间序列预测法一、滑动平均预测法 1、简单滑动平均预测法：算数平均数 （1）横向比较法：同一时间自己跟别人比 【例题计算题】某新产品要确定其市场价格，同行参考价格为1.5元、1.2元、0.9元、0.7元0.5元，则该产品价格可定为多少？【答案】我们可采用同行的平均数来作为我们的参考价格： 元【解析】横向比较法就是求平均数，用平均数作为参考。（2）纵向比较法：简单滑动平均预测法 【例题计算题】上述电池厂在生产和销售该电池6个月后，得到前后顺序排列的6个出厂价格：1元、1.1元、1.1元、1.2元、1.2元、1.3元，试预测第7个月的出厂价格，只参考就近三个月价格。【答案】元【解析】纵向比较法也是求平均数。二、加权平均预测法根据不同数值所占比重不同，在简单滑动平均预测法中加入相应权值即可加权平均数计算公式为：三、指数平滑预测法指数平滑预测法的公式为： 其中：，t+1期，t期的预测值； t期的实际值； 平滑系数。 的取值范围一般为：；当我们发现t期的预测值与实际值误差较大时，我们可以加大平滑系数的值，若误差不大，可取的小一些；在特殊情况下，即当商品的价格看涨或看跌时，亦可取大于1的数。2.4 回归模型预测法一、基本概念回归分析法：依据事物发展的内部因素变化的因果关系来预测事物未来的发展趋势，它是研究变量间相互关系的一种定量预测方法。线性回归方程分类：（1）一元线性回归：一个自变量与一个因变量间线性关系的回归方程。（2）多元线性回归：多个自变量与一个因变量间线性关系的回归方程。（3）非线性回归：变量之间不是线性而是非线性关系。二、一元线性回归模型预测法 设出回归方程：； 确定系数：a,b也称为回归模型的参数。 系数确定的原则应用最小二乘法最小二乘法：寻求使误差平方和为最小的配合趋势线的方法。 运用最小二乘法，得出系数的计算公式： 求出回归方程后，根据题目中所给的某一变量的数据，带入即可求出另一变量的值。 置信区间：实际值位于这个区间范围的概率应达到95%以上，若大致符合正态分布，则置信区间为：。 本章总结：本章节各种题型都要涉及到，选择填空主要从预测的分类、特尔斐法和专家小组法的区别、平滑系数的取值及最小二乘法的定义出题；名词解释从几个基本定义中出题（可能有也可能没有）；计算题本章共三个知识点：1、滑动平均预测法；2、指数平滑预测法；3、回归模型预测法。历年考试都是从这三个知识点中挑一个考察，考生需每种方法都要掌握。第三章 决 策复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：决策定义；决策的分类；决策的程序；不同环境下的决策；决策树等。3.1 决策的概念和程序一、决策的概念 决策：针对具有明确目标的决策问题，经过调查研究，根据实际与可能，拟定多个可行方案，然后运用统一的标准，选定最佳方案的全过程。二、决策的分类 1、按决策方法不同分类：常规性决策和特殊性决策。 2、按计划和控制的关系分类：计划性决策和控制性决策。三、决策的程序 1、确定目标； 2、拟定多个可行方案； 3、预测可能发生的自然状态，计算不同方案在不同状态下的收益值，编制决策收益表； 4、一决策收益表为依据，运用不同的决策标准进行决策分析，选择最优解。3.2 在不同条件下的决策环境分类： 1、确定条件：只有一种自然状态。 2、不确定条件：存在一个以上的自然状态，概率分配不全知道。 3、风险条件：存在一个以上的自然状态，概率分配全部知道。3.3 不确定条件下的决策一、不确定条件下的决策有四种不同的决策标准，分别为： 1、最大最大决策标准：又称为乐观主义者的决策标准，决策时，只考虑将来会发生最好的自然状态即把最好的自然状态发生的概率定为1，其他状态的概率定为0。 它的决策程序是：首先从每个方案中选择一个最大的收益值，然后从方案中选出的最大收益值中再选择最大值，做为备选方案，故又称为大中选大。 2、最大最小决策标准：又称为保守主义者的决策标准，决策时，只考虑最差情况，即把最差的自然状态发生的概率定为1，其余为0. 它的决策程序是：首先从每个方案中选择一个最小的收益值，然后再从这些最小的收益值所代表的不同方案中，选择一个收益值最大的方案作为备选方案，又称为小中取大。 3、最小最大遗憾值决策标准： 遗憾值：在决策过程中，当某一种自然状态可能出现时，决策者由于决策失误没有选择最好的方案，而是选了其他方案，因而会感到遗憾，这两个方案的收益值之差叫遗憾值。 它的决策程序是：先把收益表转换为遗憾值表，以遗憾值为基础，大中取小。 4、现实主义决策标准：也称为折中主义决策标准，它把未来出现最好的状态的概率定为，最差的状态的概率为1-，其它中间状态的概率定为0，即考虑两头的情况。 它的决策程序是：计算每个方案的折中收益值，选择折中后最大的收益值对应的方案作为备选方案。 【例题计算题】某公司准备销售某新产品。拟定的价格有A1、A2、A3三个方案，预计进入市场后可能的销售状况（自然状态）也有三种，收益值如表。试以最大最大决策标准作出该产品价格的决策选择。销路较好销路一般销路较差较高价格出售A118000100006000中等价格出售A216000130008000较低价格出售A3120001200012000【答案】用最大最大决策标准决策如下： 销路较好销路一般销路较差按行取最大值较高价格出售A11800010000600018000中等价格出售A21600013000800016000较低价格出售A312000120001200012000按最后列取最大值18000 选择A1方案作为决策方案。【解析】最大最大决策方案就是大中取大。3.4 风险条件下的决策 风险条件下的决策一般又叫统计型决策或随机型决策，主要是根据多种不同的自然状态可能发生的概率来决策，所依据的标准主要是期望值标准。 在风险条件下进行决策，一般最常用的决策标准就是期望利润标准，也叫贝叶斯标准。主要包含最大期望利润值标准和最小期望损失值标准。这两个标准对于同一个问题的决策结果往往是一致的，但不确定条件下的四个决策标准得到的结果往往不一致。 【例题计算题】某月饼厂自销一种新月饼，每箱成本40元，售价90元，但当天卖不掉的产品要报废。据以往统计资料预计新月饼销售量的规律见下表： 需求数100箱110箱120箱130箱占的比例0.20.30.40.1(1)今年每天应当生产多少箱可获利最大(2)具有精确情报时的收益【答案】（1）编制决策收益表，并计算每种方案的期望值为： 销售100箱销售110箱销售120箱销售130箱期望值0.20.30.40.1生产100箱50005000500050005000生产110箱46005500550055005320生产120箱42005100600060005370生产130箱38004700560065005060所以，由决策收益表中可以看出，当每天生产120箱时，可获利最大为5370元. （2）具备精确情报时，生产多少就能卖多少，不存在损失，因此收益表为 销售100箱销售110箱销售120箱销售130箱期望值0.20.30.40.1生产100箱50001000生产110箱55001650生产120箱60002400生产130箱36500650最大期望收益5700 具备精确情报时，最大期望收益值为5700元。【解析】重点考察期望值的计算。3.5 决策树决策树的基本结构为：方案枝状态枝 概率方案枝方案枝决策点收益值本章总结：本章所有题型都要涉及，前三个题型考察基本定义、性质和不同方法的区别；计算题知识点主要有三个：1、利用不确定条件下的四个标准进行决策；2、利用期望值标准进行决策；3、利用决策树进行决策。其中前两个是重点考察对象，第三个决策树很少出现，同学们把这三个考点熟练掌握即可。第四章 库存管理复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：库存管理的作用和意义；存货台套法和ABC分类管理；经济订货量的计算；订货时间的确定等。4.1 库存管理的作用和意义一、库存管理的作用库存管理的最基本的一个方面就是保证工业企业的生产能够正常的、连续的、均衡的进行。分以下几种：（1） 适应原材料的季节性（2） 适应产品销售的季节性（3） 适应运输上的合理性和经济性（4） 适应生产上的合理安排（5） 适应批发量的大小二、库存管理的意义1、保证企业按科学的计划实现均衡生产，不要因缺少原材料或其它物资而停工停产。2、使库存总费用达到最低。4.2 库存管理的存货台套法与ABC分类管理一、存货台套法的内容以存货台套作为存货管理的单位，在某个存货台套中可以包括有关的各种单项存货。它简化了工作的内容，并可保证供应的成套性。二、ABC分类管理 按各种存货的价值和数量不同，将它们分成A、B、C三类。 A类：数量10%，价值70%，特殊物品如防火设备、易燃易爆物品、剧毒及辐射性物品等，对该类物品应细致的加强管理。 B类：数量30%，价值20%。 C类：数量60%，价值10%。 对B和C类在管理上可以适当粗略一些，只要不缺货，不影响正常生产即可。 4.3 库存费用分析和平均库存的概念一、库存费用分析 1、原材料库存费用模型 库存费用=订货费+保管费 其中：订货费=（年需要量/订货量）*一次订货费 保管费=平均库存量*单位物资保管费=平均库存额*保管费率 2、半成品和成品库存费用模型 库存费用=工装调整费+保管费 其中：工装调整费=（年计划产量/生产批量）*一次工装调整费 保管费=平均库存量*单位物资保管费=平均库存额*保管费率 4.4 经济订货量的计算方法 经济订货量（EOQ）:是使总的存货费用达到最低的为某个台套或某个存货单元确定的最佳的订货批量。主要方法：1、表格计算法。（了解）2、图解法。（了解）3、数学方法： 由 库存费用=订货费+保管费=（年需要量/订货量）*一次订货费+平均库存量*单位物资保管费 可推导出当 订货费=保管费 时库存总费用达到最低，带入已知数据可计算出经济订货量。其中平均库存量=订货批量的一半，平均库存额=平均库存量*单价。【例题计算题】某工厂需要某种零件，每年需要量为1200个，每次订货的订货费用为300元，每个零件保管费为2元，求每次的最佳订货批量。【答案】设最佳订货批量为X个/次则当保管费=订货费时，库存费用最低即 X=600个/次所以每次的最佳批量为600个.【解析】由库存费用=订货费+保管费=（年需要量/订货量）*一次订货费+平均库存量*单位物资保管费 可推导出当订货费=保管费时库存总费用达到最低，带入已知数据可计算出经济订货量。4.5 订货时间的确定 1、再订货点：有两种含义，一种是时间上的含义，即什么时间再订货；另一种为存货水平上的含义。 2、前置时间：是提前时间的同义词，亦可称为订货提前期。 3、前置时间内的需求量：前置时间内的使用量就是需求量。4、缺货：指仓库中已没有某项存货可以满足生产需求或销售需求时的状况。缩短前置时间容易引起缺货。5、安全库存量：为了预防可能出现的缺货现象而保持的额外库存量。4.6 正确估价供应商所提供的数量折扣 一、大批采购的优缺点 1、大批采购的优点 （1）可以按较低的单位价格采购 （2）减少订货次数，降低订货费用 （3）大批采购，也可大批量运输，可获得运价优惠 （4）进货批量大，缺货可能性就减少。 2、大批量采购的缺点 （1）大批量进货，保管费用较高 （2）占用更多的资金 （3）库存货物会变的陈旧、过时。 （4）库存货物的更换率低 （5）适应时尚的灵活性较低 （6）损耗增大，贬值的可能性也会增大。二、正确评价供应者提供的数量折扣 经济订货量是使我们库存费用最低的订货批量，但供应商往往提出如果提高一次订货量，那么会在产品价格方面做出优惠，此时库存费用会增加，我们需要比较才能确定出哪种方案更合适。【例题计算题】某企业年需采购轴承200台套，每台套500元，每次的订货费用为250元，保管费用率为125%，供应商提出，若每次订货100台套，则轴承的进厂价可降为490元/台套。试问能否接受这种优惠，每次订货100台套? （2008.7真题）【答案】设经济订货量为X台套/次则 X=40台/次此时库存费用为2500元成本为200500=100000元总费用为102500元优惠后库存费用为总成本为200490=98000总费用为3562.5+98000=101562.5所以接受这种优惠 【解析】分别计算不同方案下的总费用，选择费用较少的方案。本章总结：本章各种题型都要涉及，选择、填空和名词解释主要从基本概念和性质中出题，计算题考点有两个（实质上是一个）：1、经济订货量的计算（包含数量、次数和时间的计算）；2、是否接受数量折扣。第五章 线性规划复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：线性规划的模型结构；线性规划的图解法和线性规划的单纯形法等。5.1 概 述 1、规划的目的：在现有人力、物力和财力等资源条件下，如何合理地加以利用和调配使我们在实现预期目标的过程中，耗费资源最少，获得受益最大。 2、线性规划的基本特点：基本特点是模型中的线性函数。 3、线性规划：“线性”是用来描述两个或多个变量之间的关系是直接成正比例的；“规划”是指使用某种数学方法使有限资源的运用达到最优化。线性规划是一种合理利用资源、合理调配资源的应用数学方法。5.2 线性规划的模型结构一、线性规划的模型结构1、变量：根据需求自己设出变量；2、目标函数：把想要实现的目标公式化；3、约束条件：实现目标的限制因素；4、变量非负：变量的取值应大于等于0。 二、线性规划建模的步骤 1、明确问题，确定目标，列出约束因素。 2、收集资料，确立模型。 3、模型求解与检验。 4、优化后分析。 其中较为困难的是建立模型；建模的关键是提出问题，明确问题，确定目标；花时间、精力最大的是收集资料和数据。5.3 线性规划的图解法图解法又称为几何解法，适用于23个变量的线性规划问题，再多就画不出图来了。1、可行解：满足约束条件的解。2、可行解区：全部可行解所分布的区域。3、等值线：过过可行解区的凸交点并平行于目标函数的直线，分为等成本线和等利润线。【例题计算题】用图解法解线性规划问题：max F=2X1+4X2s.t. 4X1+5X240 2X1102X28【答案】如图所示2x2x11028(2,6.4)(7.5,2)(2,2)如图所示，当X1=2,X2=6.4时，取得最大值为29.6。【解析】图中阴影部分为可行解区，若有最优解，则最优解在可行解区的凸交点上，过交点画平行于目标函数的等值线（这里为等利润线，图中虚线），原点距离等利润线越远，说明利润越大，所以最远那条等利润线经过的那个交点即为最优解。5.4 线性规划问题的单纯形法一、单纯形法的一般步骤 1、引入剩余变量或松弛变量，把约束方程中的不等式变为等式，新变量在目标函数中系数为零；2、观察有无基变量，若有则本步省略，如无则引入人工虚拟变量，凑出基变量，人工变量在目标函数中系数为M，是个极大的正数；3、列出单纯形表进行迭代： （1）判定是否最优：表中最后一行为判别指数行，求最大值时，数值都小于等于0时最优，最小值时相反；若最优则停止，不是最优继续下一步； （2）确定入基变量和出基变量：最后一行数值正数中最大的（或负数中最小的）所对应的列变量做为最大值问题（或最小值问题）的入基变量；最后一列数值与入基变量多对应系数比值最小的数值对应的行变量做为出基变量； （3）迭代：入基变量取代出基变量进行系数转换。 （4）重复（1）、（2）、（3）过程直至最优。 二、几个概念 1、设约束方程的个数为m，变量的个数为n，mn时，可把变量分为基变量和非基变量两部分，基变量个数=方程个数=m，非基变量个数=n-m。 2、所有的非基变量都等于0时求出的特解我们称为基解或基础解，基解非负要求时叫做非负基解，也叫可行基解。3、一个线性规划问题若有最优解，那么此最优解必定是某个基变量组的可行基解，由于每个基变量组的基解，不一定是可行的，即使是可行的，也不一定是最优的，所以求最优解的任务就在于：在许多可行基解中，找到最优的可行基解。 三、应用示例 【例题计算题】 用单纯形法求解 目标函数： MaxZ=2X1+X2 约束条件：X2 10；2X1+5X2 60；X1+X2 18；3X1+X2 44；X1，X2 0。答案：引入松弛变量X3，X4，X5，X6把不等式变为等式。 X2+X3=10； 2X1+5X2+X4=60； X1+X2+X5=18； 3X1+X2+X6=44； X1，X2 ，X3，X4，X5，X60初始单纯形表为：Cj210000Z基变量X1X2X3X4X5X6常数0X3011000100X4250100600X5110010180X631000144Zj0000000Cj-Zj210000Z进行迭代求解第一次迭代：Cj210000Z基变量X1X2X3X4X5X6常数0X3011000100X4013/2010-2/392/30X502/3001-1/310/32X111/30001/344/3Zj22/30002/388/3Cj-Zj01/3000-2/3Z-88/3第二次迭代：Cj210000Z基变量X1X2X3X4X5X6常数0X30010-1.50.550X40001-6.51.591X201001.5-0.552X11000-0.50.513Zj21000.50.531Cj-Zj0000-0.5-0.5Z-31所以最优解为X1=13，X2=5，X3=5，X4=9，X5=X6=0时，MaxZ=31。【解析】该问题为一个完整的单纯形法求解过程，考试过程中从中间挑出一部分作为考试题目. 本章总结：本章内容选择、填空和名词解释都会涉及，计算题考察主要有三个知识点：1、根据材料建立模型（不需求解）；2、利用图解法求解；3、单纯形法求解。本章计算题经常会考其中2个，分值比较大，需特殊注意。第六章 运输问题复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：西北角法；闭合回路法和修正分配法等。6.1 运输问题及其特殊结构一、运输问题产销平衡表 销地 产地B1B2 .Bn产量A1X11X12X1na1 .AmXm1Xm2Xmnan销量b1b2bn每一格中的具体运输数量我们不确定，我们可以设为Xij，代表从第i个产地运往第j个销售地点的运输数量，对于不同的运输数量，会产生不同的总运费，我们的目地就是找出所有满足要求限制的可能的运输数量的分配方案，然后从这些运输方案中选择最优的即总运费最低的方案。运输问题的解：使得总运费最低的具体运输数量。单位运价表 销地 产地B1B2 .BnA1C11C12C1n .AmCm1Cm2Cmn单位运价表中每一个数据代表从不同产地运输一单位产品到不同销售地点所产生的运费，我们用Cij表示。产销平衡表和单位运价表是一一对应的，我们可以把这两个表合为一个表称为平衡表。二、表上作业法该方法分为下面三个步骤：1、找到一个初始方案 2、根据判定标准判断是否最优3、若不是最优，对该案进行改进，然后重复第2、3步直到求出最优解来为止。6.2 供需平衡的运输问题运输问题存在供需平衡、供大于需和供小于需三种情况其模型结构是不同的。我们先来看供需平衡问题，下面举例予以说明：某一运输问题的产销平衡表和单位运价表如下图所示平衡表B1B2B3产量A110203050A230204060销量205040110该表是产销平衡表和单位运价表合起来的，每一格中右上角小格对应的是单位运费。1、求的一个初始的运输方案利用西北角法求的初始方案：B1B2B3产量A1102030502030A2302040602040销量205040110数字格数=m+n-1,该问题数字格数=2+3-1=5，若不相等则称出现了退化现象，总格数为mn，除了数字格数，剩下的mn-（m+n-1）为空格数。方案确定了，该方案对应的总运费就确定了，此时产生的运输费用为：, Z=20*10+30*20+20*20+40*40=2800 但此方案一般不是最优方案（即总运费是否最小），需要我们进一步的判断。2、判定是否最优判定标准：（1）改进路线：从某一空格开始，所寻求的那一条企图改变原来运输方案的路线。例如A1B3空格，字母公式表达：LA1B3=+A1B3-A2B3+A2B2-A1B2 ; +代表增加运输数量，-代表减少运输数量，注意，每条改进路线中只包含一个空格。同理我们可以找到余下空格的改进路线。每一个空格对应一条改进路线，要把所有的改进路线全部找出来。（2）改进指数：沿着改进路线，当货物的运输量做一个单位的改变时，会引起的总运输费用的该变量。以A1B3格来举例，在沿着改进路线的格中，又增加运费的，也有减少运费的，总的变化量为：IA1B3=+30-40+20-20=-10，这个数值即为改进指数，为负值说明沿着这条路线改变一个单位可以减少10的总运费，同时表明既然能减少运费，说明原来的方案还有改进的空间，所以原来的方案那就不是最优方案，所以说改进指数就是判别的标准，为负值说明还能改进，为正值说明再改的结果为增加运费，原来的方案就是最优方案。当然这里要求每个空格的改进指数都要求出来都为正值才能说明原方案是最优方案，有一个为负值就不是最优方案。3、寻求改进方案 寻求改进方案的方法主要有闭合回路法和修正分配法（1）闭合回路法在所有空格中，挑选绝对值最大的负改进指数所在的空格作为调整格，沿着该空格的改进路线，挑选是负号格的最小运量为调整运量。（2）修正分配法 修正分配法也叫位势法。把原来的运输图进行一些改进，在图的顶上加上一行，在图的左侧加上一列.K1=10K2=20K3=40B1B2B3产量R1=0A1102030502030R2=0A2302040602040销量205040110根据数字格列出方程：C=R+K R1+K1=10 R1+K2=20 R2+K2=20 R2+K3=40令R1=0，依次解出剩下的为：K1=10，K2=20，R2=0，K3=40对空格求改进指数（位势差）位势差=C-R-KIA1B3=30-0-40=-10IA2B1=30-0-10=20 在所有空格中，挑选绝对值最大的负改进指数所在的空格作为调整格，沿着该空格的改进路线，挑选是负号格的最小运量为调整运量进行改进，得到新方案再重复判定、改进过程即可。6.3 需求量不等于供应量的运输问题解决供需不平衡的运输问题的思路为虚设站点把不平衡的改为平衡的在做。一、需求量小于供应量 1、虚设一个需求点 2、虚设的需求点的需求量=总供应量-总需求量 3、虚设点的单位运费为0二、需求量大于供应量1、虚设一个供应点 2、虚设的供应点的供应量=总需求量-总供应量 3、虚设点的单位运费为0 总结起来就是谁少补谁。本章总结：本章内容选择、填空和名词解释都会涉及，计算题考察主要有三个知识点：1、西北角法建立初始方案并判定是否最优；2、闭合回路法；3、修正分配法。在考试过程中在改进时若没有特殊指明需要用哪种方法，则同学们根据自己擅长的方法求解即可。第七章 网络计划技术复习建议本章在历年考试中，处于相当重要的地位，建议学员全面掌握,重点复习。从题型来讲包括单项选择题、填空题、名词解释和计算题题型都要加以练习。重要考点：网络图；关键路线；网络时间与时差的计算等。7.1 网络图计划评核术：简称PERT，是对计划项目进行核算、评价，然后选定最优计划方案的一种技术。关键路线法：简称CPM,是在错综复杂的工作中，抓住其中的关键路线进行计划安排的一种方法。一、网络图的分类 1、箭线式网络图：箭线代表活动，结点代表活动的开始或完成。 2、结点式网络图：结点代表活动，箭线表示各活动之间的先后承接关系。二、箭线式网络图的构成 1、活动：指作业或工序，用箭线表示，箭线的方向表示前进的方向。 虚活动：即虚设的活动，不消耗资源，不占用时间。 2、结点：起点或终点、两个活动的交接点，用圆圈表示。只有一个始点和一个终点。 3、线路：从始点出发，顺着箭线的方向，经过互相连接的结点和箭线，直到终点的一条连线。 （1）总作业时间：在一条线路上，把各个活动的作业时间加起来就是该线路的总作业时间，也叫路长。 （2）关键线路：总作业时间最长的线路就是关键线路。三、箭线式网络图的编绘 【例题计算题】某工程工序活动明细如下表所示:工序 紧前工序工作时间（天）A无20B无15CA,B15DA15EA,B10FD,E10GC,F25HD,E15 【答案】10 0935 45320 20520 25735 351145 451370 70A20D15H15G25B15C15F 10E10【解析】当然若只要求编绘网络图，去掉图中的结点时间即可。注意虚活动没有严格意义上的限制，在表达不出现歧义的基础上，能省则省即可。7.2 网络时间的计算一、符号表示：ESi:结点的最早开始时间EFi:结点的最早完成时间LSi:结点的最迟开始时间LFi:结点的最迟完成时间ESij:活动的最早开始时间EFij:活动的最早完成时间LSij:活动的最迟开始时间LFij:活动的最迟完成时间Tij:作业时间 :结点符号10 ：活动的最早开始或最早完成符号 ：活动的最迟开始或最迟完成符号二、网络时间计算EFij10LFij iESi LFi jESj LFjESij10LSijTij （1）作业时间：三种时间估计法 Tij=（a+4m+b）/6 其中：a最乐观时间，即最短时间 b最保守时间，即最长时间 m最可能时间（2）结点时间：ESj=maxESi+Tij LFi=minLFj-Tij（3）活动时间：ESij= ESi；LFij= LFj；EFij=ESij+Tij; LSij=LFij-Tij。【例题计算题】下图是截取网络图的一部分，在图中空白处填入有关活动和结点的网络时间（单位：天）。 E11D10101010107 195 1737 【答案】E11D1071071710177108181019718 19517 17 1737 7【解析】考