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