16运筹学复习提纲

自考《运筹学基础》章节复习要点2016自考《运筹学基础》章节复习要点为帮助考生们更好、更有准备地参加2016年10月自学考试，下面是YJBYS店铺搜索整理的关于2016自考《运筹学基础》章节复习要点，欢迎参考复习，希望对大家有所帮助!想了解更多相关信息请持续关注我们应届毕业生培训网!第五章线性规划5.1 概述线性规划是一种合理利用资源，合理调配资源的应用数学方法。

任务：1计划任务确定，用最少的资源来实现任务。

2资源数量确定，合理利用，使完成的任务最大。

综合来说，是研究投入产出的极值问题，就是用最少的劳力和物力消耗，获得更多更好的社会需求产品。

5.2 线性规划的模型结构线性规划的定义：线性规划是一组变量的值，在满足一组约束条件下，求得目标函数的最优解，使决策目标达到最优。

5.2.1 线性规划的模型结构：1变量 2目标函数 3约束条件 4线性规划的变量应为正值5.2.2线性规划建模的步骤：1明确问题，确定目标，列出约束因素2收集资料，确立模型3模型求解与检验4优化后分析5.3 线性规划的图解法5.4线性规划问题的单纯形法：它是一种解线性规划多变量模型的常用方法，是通过一种数学的迭代过程，逐步求得最优解的方法。

第六章运输问题运输问题的内容是在供应点与几个需求点之间，运输品种，规格，质量等相同的货物时，选择最佳的运输方案，以达到总的运输费用最低或所获得的利润最大等目标。

6.1运输问题及其特殊结构在单纯形法的基础上，创造出一种专门用来解决运输问题的简便方法，称为表上作业法。

6.2 需要量等于供应量的运输问题 P981 建立运输图2 求得一个最初的运输方案(西北角法，也称阶石法或登石法)有数字的方格叫数字格或石方格，数目是m+n-1，变量为0的方格叫空格或无石方格。

3 寻求改进方案：阶石法：1对每一个空格求改进路线和改进指数。

改进路线就是从某一个空格开始，所寻求的那一条企图改变原来的运输方案的路线。

改进指数是指循着改进路线，当货物的运输量坐一个单位的变化时，会引起总运费的该变量。

运筹学期末考试知识点绪论1.运筹学的研究对象，研究内容（运筹学的分支）；线性规划2.可行解、基解、基可行解的基本含义、性质及区别；3.单纯形法求解LP问题的基本思路，单纯形法求解；4.解的判断（唯一最优解、多重最优解、无界解、无可行解）；对偶及灵敏度分析5.求某一LP问题的对偶问题，对偶问题和原问题之间的关系；6.强弱对偶理论等相关定理与推论；7.对偶单纯形法的求解思路；8.根据单纯形表得出原问题和对偶问题的最优解；9.灵敏度分析包含的内容，掌握目标函数价值系数c、右端向量b的灵敏度分析的计算；运输问题10.运输问题模型的特点；11.运输问题检验数的实际含义；12.产销不平衡、道路不通的运输问题的处理；存储论13.描述存储策略的指标；评价存储策略优劣的指标；14.掌握4种确定性存储模型的存储状态图；15.4种确定性存储模型的T0、Q0、C0的求解；16.有批发折扣价存储模型的求解；17.K、R、P、c1、c2、c3等参数的改变对T0、Q0、C0的影响；18.报童问题的特点；动态规划；19.动态规划的研究对象、基本思路及包含的几类典型问题；20.理解阶段变量、状态变量、决策变量、状态转移方程、阶段指标函数、过程指标函数、边界条件等的含义以及根据具体问题定义上述变量；21.两类动态规划问题（资金分配问题和资源动态分配问题）的求解；排队论22.熟练掌握排队系统的分类（X/Y/Z/A/B/C），了解其中每个符号的含义；23.理解λ和μ的含义，掌握λ和μ的确定方法；24.理解ρ的含义；25.求解M/M/1 排队系统的各运行指标ρ、p0、L、L q、W、W q等。

考试时间：120分钟；考试形式：闭卷（允许带计算器）；考试题型及分值：是非题（每题1分×10题=10分）单选题（每题2分×10题=20分）线性规划综合题（15分）动态规划（20分）存储论（20分）排队论（15分）练习题1、求解以下线性规划问题Max z＝2x1＋3x2＋x3x1＋x2＋x3≤3s.t. x1＋4x2＋7x3≤9x j≥02、已知某LP问题单纯形法求解过程如下表，求：（1）本问题的最优解；其对偶问题的最优解；（2）对c1进行灵敏度分析；（3）当资源系数b1由6变为8时，最优解是否变化？最优基是否变化？3、某公司有资金4万元，可向A、B、C三个项目投资，已知各项目的投资回报如下，求最大回报。

运筹学复习提纲第一章线性规划1、线性规划的三个要素目标函数、决策变量、约束条件一般形式，标准形式（转化）2、求解线性规划的图解法3、线性规划解的可能性唯一最优解、无穷多最优解、无界解、无可行解(原因)4、单纯形法（必考点）基，基变量，基本解，基本可行解，可行解，最优解，最优基单纯形法解题思路、步骤，最优解的判定定理，单纯形法的管理启示大M法的可能结果图解法。

大M法。

线性规划数学模型的建立？（建模）第二章线性规划讨论1、线性规划灵敏度分析价值系数、资源向量第三章 对偶规划 1、对偶模型 2、对偶性质对称性定理，弱对偶定理，强对偶定理，互补松驰定理 3、影子价值对偶问题的最优解，影子价值的经济含义 （课后习题69页，5）1、 求该问题产值最大的最优解和最优值2、 求出该问题的对偶问题和最优值3、 给出两种资源的影子价格，说明其经济含义：第一只能够资源限量由2 变为4 ，最优解是否改变？4、 代加工产品丁，每单位产品需要消耗第一种资源两单位，消耗第二种资源3单位，应该如何定价？ 解：1、先转化成标准型：利用单纯形法求解：123123123123max 42832..68,,0Z x x x x x x s t x x x x x x =++++≤⎧⎪++≤⎨⎪≥⎩1234512341235max 4200832..680;1,2,,5jZ x x x x x x x x x s t x x x x x j =++++⎧+++=⎪+++=⎨⎪≥=⎩该问题有唯一最优解： 2、利用对偶问题的性质求解对偶问题的最优解和最优值：第一种资源影子价格为2，表明第一种资源增加1个单位，产值(或利润)增加2个单位，即第一种资源为紧缺资源(x 4 = 0)； 第二种资源影子价格为0，表明第二种资源增加1个单位，产值(或利润)增加0个单位，第二种资源有剩余(x 5 = 6) 。

3、对偶问题数学模型：其对偶模型为：*(0,0,2,0,6)TX =*4Z =*(2,0,12,5,0)Y =*4Z =123123123123max 42832..68,,0Z x x x x x x s t x x x x x x =++++≤⎧⎪++≤⎨⎪≥⎩121212min 2886431W y y y y y y =++≥⎧⎪+≥⎪，根据题意：(4)设产品丁的产量为x6第四章整数规划1、整数规划的含义2、整数规划的类型及求解方法3、整数规划问题建模 0-1规划建模4、分枝定界法第五章目标规划1、目标规划问题建模2、目标规划图解法（满意解）问：在材料不能超用的条件下，企业如何安排生产计划？要求尽可能满足下列目标：(1)力求使利润指标不低于80元；(2)考虑到市场需求, 两种产品的产量需保持1:1的比例；(3)设备A既要求充分利用，又尽可能不加班；(4)设备B必要时可以加班，但加班时间尽可能少。

1. 原问题与对偶问题的关系.(问题对偶形式,解的关系)2. 掌握线性规划问题的单纯形法.3. 问题的灵敏度分析.4. 运输问题的表上作业法.5. 指派问题的匈牙利法.6. 多目标规划的解法.(图解法，单纯形法)7. 动态规划的解法，动态规划的模型.8. 了解求一般整数线性规划的方法. 例题练习1. 写出下述线性规划的对偶问题⎪⎪⎩⎪⎪⎨⎧≥≤=+≥+--≤-+-+=取值无约束32132321321321,0,073523132.5max x x x x x x x x x x x t s x x x z 2.求解下列线性规划问题.(1) ⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0,1551641222.32max 21212121x x x x x x t s x x Z ,(2) ⎪⎪⎩⎪⎪⎨⎧≥≤+≤≤+=0,18231224.52max 21212121x x x x x x t s x x z3.已知线性规划问题3212max x x x z +-=⎪⎩⎪⎨⎧≥≤+-≤++0,,46.32121321x x x x x x x x t s 先用单纯形法求出最优解，，再分析在下列条件变化的情况下最优解的变化（1） 目标函数变为32132max x x x z++=；（2） 约束右端项由⎪⎪⎭⎫⎝⎛46变为⎪⎪⎭⎫⎝⎛43；（3） 增添一个新的约束条件0231≥+-x x .4.1某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量，各销售点的销售量(单位.t)以及各工厂到各销售点的单位运价(元/t)示于下表中，要求研究产品如何调运才能使总运量最小？由于业务能力、经验和其他情况的不同，四位业务员处理这四项业务的费用各不相同，如表5.有四项工作要甲、乙、丙、丁四个人去完成，每项工作只允许一个人去完成，每个人只完成其中一项工作.已知每个人完成各项工作时间如表所示。

问应如何安排，使总的消耗时间最少？（用匈牙利法）⎪⎪⎩⎪⎪⎨⎧=≥=-+=-+=-++++=+-+-+-+--+++3,2,1,0,,,1430402.)2(,min 2133222111213323211i d d x x d d x d d x d d x x st d P d d P d P z i i7.某公司计划在A 、B 、C 三个地区新设4个超市。

运筹学复习提纲复习内容：绪论、第一章线性规划、第二章线性规划的进一步研究、第三章运输问题、第六章决策分析、第九章对策论。

重点内容：运筹学的定义特征、线性规划问题的数学模型、线性规划问题单纯形法的求解过程、对偶问题及理论、对偶单纯形法的求解过程、运输问题的数学模型、表上作业法的求解过程、风险型决策分析和完全不确定型决策分析、效用理论、二人有限零和博弈。

管理运筹学重在对实际问题的理解的基础上对问题进行建模，并用适宜的办法对问题进行求解。

管理运筹学是一门决策的科学。

从决策环境的角度来讲，可以将问题分为确定型决策和非确定性决策。

其中本期前面的内容，线性规划问题和运输问题可以理解为确定型决策。

非确定型决策又可以分为风险型决策和完全不确定型决策，这在本书第六章有介绍。

附：部分复习题一、简答题1简述运筹学的定义和特征2、比较可行解、基本解与基可行解之间的区别3、简述对偶问题的基本性质4、简述表上作业法的求解过程5、简述单纯形法的求解过程6、简述影子价格对决策的作用7、、简述运输问题中最优解的判定方法8简述完全不确定型决策的准则二、计算题1某工厂利用原材料甲、乙、丙生产产品A、B、C,有关资料见表2-23 .(1)怎样安排生产，使利润最大.(2)若增加1kg原材料甲，总利润增加多少.【解】(1)设X I、X2、X3分别为产品A、B、C的月生产量，数学模型为max Z 4x x2 3x3‘2% +1x2 +x3兰200% + 2x2+ 3x3兰5002为x2 x3乞600% _ 0,x2 _0,x3 _0最优单纯形表:最优解X=(20,0,160),Z=560。

工厂应生产产品A20件，产品C160种，总利润为丿元。

9 2(2)则最优表可知，影子价格为y1, y2, y3= 0 ,故增加利润1.8元。

5 52、用对偶单纯形法求解下列线性规划问题560mi nZ = 3% 4x2 5x3x12X2 3x3 _ 8I2X12X2 x3 _ 10X「X2,X3 一0【解】将模型化为min Z =3为4X25X3-X i -2X2_3X3 ' X4 = _ 8« —2为—2x2—x3+疋=—10X j K0, j =1,2,3,4,5对偶单纯形表：b列全为非负，最优解为X= (2 , 3, 0); Z = 183、给出如下运输问题(1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案。

运筹学复习大纲1．线形规划部分（1）会求一般线性规划问题的标准形式。

要求见37页表格。

（2）了解线形规划的可行解、基解、基可行解、最优解等概念。

（3）知道单纯形法的几个基本定理。

（4）掌握大M法与两阶段法求解线性规划问题的方法步骤。

（5）知道线性规划问题唯一最优解，有无界解，无穷多最优解，无可行解的判别方法。

2．对偶理论（1）会求原规划问题的对偶问题。

（2）了解对偶原理。

（3）知道对偶单纯形法的迭代步骤。

（4）灵敏度分析部分：会对增加变量与增加约束条件情况进行分析。

3．运输问题（1）知道运输问题的数学模型。

（2）掌握运输问题的表上作业法（初始方案的确定，最优性检验，调运方案的调整）。

（3）会处理产大于销的运输问题。

4．指派问题（1）知道匈牙利法解决分配问题的理论依据，掌握匈牙利法求解指派问题的方法。

（2）知道人多任务少时的处理方法及人比任务少一个时的处理方法。

5．整数规划（1）会用割平面法求解整数规划问题6．目标规划（1）会建立目标规划数学模型，会解释目标约束的意义。

7．图论部分（1）了解图的基本概念：简单图、完全图、偶图、子图、部分图等，次（度）、链、路、圈、回路等。

（2）知道树的概念和基本性质。

知道求图的最小部分树的理论依据和方法。

（3）会求最短路。

（4）会求网络的最大流与最小割。

（5）会求最小费用流。

8.动态规划（1）了解动态规划的基本概念及最优化原理.（2）知道动态规划的求解方法.9．存储论（1）了解存储论的相关概念.（2）掌握确定型存贮模型.运筹学复习题一、填空题1． 在线性规划标准形式中，要求约束条件右侧常数),,2,1(m i b i =为_____ 数。

在化线性规划为标准形式时，需将自由变量x 作变化为__________。

2．线性规划问题中满足⎪⎩⎪⎨⎧=≥==∑=n j x m i b x a j nj i j ij .2,1,0),,2,1(1的解称为 。

3．线性规划问题的可行解集必为 集。