《运筹学知识点要求》由会员分享，可在线阅读，更多相关《运筹学知识点要求（4页珍藏版）》请在金锄头文库上搜索。
1、运筹学知识点要求第一部分 结论1、运筹学的特点（1）以最优性或合理性为核心。（2）以数量化、模型化为基本方法。（3）具有强烈的系统性、交叉性特征。（4）以计算机为重要的技术支持。2、运筹学模型求解方法： 知道迭代算法的原理步骤。3、运筹学模型（1）运筹学模型：使用较多的是符号或数学模型，大多数为优化模型。（2）模型的一般结构（3）模型的三大要素 决策变量、目标函数及优化方向、约束条件。（4）了解模型的分类4、建立优化模型解决实际问题（1）要求能对较简单的实际问题建立优化模型。主要涉及：一般线性规划模型，整数（特 别是 01 规划）规划模型。5、了解运筹学运用领域。第二部分 线性规划1、线性规划
2、模型的几种表示形式及特点2、线性规划模型的标准形式及如何标准化3、线性规划问题各种解的概念及关系（关系图示） （可行解、非可行解、基本解、基本可行解、最优解，基本可行解的个数小于等于 C m ）4、线性问题有关解的基本定理（主要是概念理解）n（1）不一定都有最优解（2）若有，一定会在基本可行解上达到（3）基本可行解的个数有限小于等于 C m（4）并非所有最优解都是基本可行解 n（5）了解凸集与凸组合的概念，理解两个最优解的凸组合都是最优解。（6）可行解为基本可行解的充要条件5、线性规划单纯形法（1）制作初始单纯表（注意非基变量检验系数的求法，特别注意求有待定系数时的检验系 数）（2）各种解的判
3、别条件，对于最大化目标函数问题，包括：唯一最优解：b .v 0有最优解b .v 0无穷多最优解0存在一个k有：0 （或称之为线性规划问题存在可择最优解） 无界解，存在k有:b 0 ,且p 0 ）B、最速上升准则的理解，不是使目标函数改进最大，而是使目标函数改进速度最大。(5) 最小比值确定出基变量的目的：保证基变换后新的基本解是可行的。(6) 会单纯形迭代计算求解线性规划问题6、什么是线性规划问题退化情况？会引起什么样后果？7、大M法(罚函数法)：(1)辅助问题目标函数的构造，(2)辅助问题解与问题解的关系 (3)能用大M法(罚函数法)求解线性规划问题。8、两阶段法：(1)第一阶段的目的 判断
4、原问题是否有可行解，当目标函数值为0时，第一阶段问题的人工基变量已退出基变量， 其最优即为原问题的一个基本可行解，在计算表中为典型形式。若第一阶段最优解值0 说 明原问题无可行解。(2) 第一阶段的规划模型的目标函数(不要求利用两阶段法完整求解线性规划问题) 本部分的典型计算题;(1) 利用单纯形法完整求解线性规划问题(2) 利用大M法完整求解线性规划问题(3) 给定单纯形计算表，其中有部分未知参数，计算含参数的线性规划问题单纯表中各非 基变量的检验系数，并判断参数在什么范围变化时有(1)最优解(2)唯一最优解(3)无 界解第三部分 对偶问题、对偶单纯形法与灵敏度分析1、对偶问题与原问题的转换
5、关系(1) 约束条件数为对方决策变量数(2)约束条件不等号与变量正负号关系(3) 自由变量与等式约束的对应关系(4) 要能直接写出对偶问题2、对偶问题的性质(几个基本概念)(1) 对偶问题的对偶问题为原问题( 2)无界性(可根据一个问题有无界解另一问题无可行解)(4) 对偶定理：原问题与对偶问题，若一个问题有最优解，则另一个问题也有最优解，且 目标函数值相等。应用：用于判断某个问题无最优解，(见书上P75题3.7)3、互补松驰定理及应用( 1 )定理内容(2) 应用之一：已知一个问题的最优解，不用单纯形法，用解代数方程的方法，求对偶问 题(或另一对应问题)的最优解。(见P74练习题3.3)(
6、3)经济意义解释4、影子价格概念及经济意义5、对偶单纯形法(求解特殊线性规划问题)(1) 适用条件( 2)会计算(3) 在最优单纯形表下增加一个约束条件，如何转化成能用对偶单纯形法求解的单纯形表 形式，并用对偶单纯形法求解。6、关于灵敏度分析计算要求(1) 计算cj (包括基变量系数或非基变量系数)的变化范围，使最优基不改变(2) 给定cj从原值变化为新值时，判断最优基是否改变，若改变，可继续用单纯形法，在 原最优解表的基础上求新的最优解(3) 计算bi (约束条件右端项)的变化范围，使最优基不改变（4）具体给定某bi从原值变化到新值时，判断最优基是否改变，若改变，可将B ib 换最优解表中对
7、应b列数据，并利用对偶单纯形法求解（注意B的逆矩阵可直接从单纯形 中看出）（5）增加一个约束条件，如何判断最优基是否改变，若改变，如何在原最优解表下求新的 最优解。可将原最优解代入新约束，若满足，则不改变，否则，最优基将改变。改变时，可将新 增约束标准化，在原最优解表中加一行与一列，消去该行中原基变量，该行bi值一定是一 个负数，可利用对偶单纯形法求解。上述要求内容可参看 PPT 相关内容与例子。第四部分 运输问题1、一些基本概念（ 1）运输问题一定有最优解（无论是平衡还是非平衡运输问题，但线性规划问题则不一定）（2）分类：平衡，非平衡：产大于销与销大于产。（ 3）表上作业法确定初始调运方案
8、方法三种：西北角法、最小元素法、伏格尔法（一般情况下，此法与最优方案较接近）（4）表上作业法所确定的基变量（数字格）的个数=m+n-l（ 5）退化情况及处理方法2、掌握平衡运输问题表上作业求解法的计算（最小元素+位势法）3、如何将不平衡运输问题转化为平衡运输问题注意：（1）对于产大于销时，某产地产品必须运出多时，如何转换（只转换不求解）（2）产大于销时，若给出各产地产品就地存贮时的单位存贮费用，如何转化为平衡运输问 题，并要求能求解此类问题（仍然用表上作业法：即用最小元素求初始调运方案，用位势法 求检验系数，用闭合回路法调整调运方案）（3）销大于产时，某地需求必须得到满足时如何转换（只转换不求
9、解）（4）需求有上下限时非平衡运输问题如何转化为平衡运输问题（只转换不求解）4、对于在求初始调运方案时，产生的退化情况如何处理：在同时划去的行列中任选一个空 格填上运量 0 即可。第五部分 整数规划与指派问题1 、基本概念（1）整数规划问题的定义及分类（2）求解方法的特牲A、舍位取整一一不能用B、穷举法无效C、一般有效，方法的思路一一增加约束，隐去若干非整数解，求解伴随问题 2、分枝定界法要求掌握一些相关概念术求解原理步骤，不要求具体求解。（1）分枝约束条件的增加，如xi=bi非整数，可分别增加约束A、xi=bi+1B、xi=bi将上个规划问题分为两个规划问题（即两枝）（ 2）如何确定上、下界
10、（3）在分枝定界过程中，上下界的变化规律：上界不断减小，下界不断增加。（4）在该方法中，某分解结果出现什么情况时，需要舍去该分枝（即进行剪枝）A、无可行解B、最优解小于下界C、该枝最优解已是整数解3、割平面方法（1）掌握如何利用伴随问题（注：将整数规划问题的整数约束条件去掉，从而得伴随规划 问题的过程有的书又称之为松驰过程。对应伴随规划问题被称之为松驰问题）最优单纯形表 中取非整数约束行系数，构造一个割平面约束不等式（或称为割平面方程） （2）增加割平面约束后，如何利用对偶单纯形法求最优解。4、如何利用01决策变量xi i=l,2,n表示项目选择中一些特殊约束：如n个项目中， 最多选择 8 个
11、，最少选择 3 个。项目 3 与项目 5 互斥。项目 6 的选择以项目 2 的选择为前提 条件等。5、指派问题的匈牙利算法计算题（要会计算）（1）该算法适用情况A、目标函数为最小化情况（否则将转换成最小化问题）B、效率矩阵为元素均大于等于0的方阵（ 2）要会计算（3）对最大化指派问题如何转换成最小化指派问题（用效率矩阵中最大元素减各元素得到 新的效率矩阵，则将原最大化问题转换为等价的最小化目标函数问题。）（4）了解人数与事件数不等时的指派问题处理方法。第六部分 存贮论基础只要求确定性存贮模型1 、最基本的 EOQ 模型公式及计算2、允许缺货，即时补充的 EOQ 模型公式及计算3、连续供货速率的 EOQ 模型公式及计算
