运筹学总结

1、运筹学的特点

（1）以最有性和合理性为核心 （2）以数量化和模型化为基本方法 （3）具有强烈的系统性、交叉性特征 （4）以计算机为重要的技术支持 2、运筹学模型求解方法 知道迭代算法的原理步骤 3、运筹学模型

（1）运筹学模型使用较多的是符号或数学模型，大多数为优化模型。 （2）模型的一般结构

（3）模型的三大要素：决策变量、目标函数及优化方向、约束条件 （4）了解模型的分类

4、建立优化模型解决实际问题

（1）要求能对简单的实际问题建立优化模型。主要涉及：一般线性规划模型，整数（特别是0-1规划）规划模型。 5、了解运筹学运用领域。

第二部分：

1、线性规划模型的几种表示形式及特点 2、线性规划模型的标准形式及如何标准化 3、线性规划模型的各种解的概念及关系 4、线性问题有关解的基本定理 （1）不一定都有最优解

（2）若有，一定是在基本可行解上达到 （3）基本可行解的个数有限小于等于Cnm （4）并非所有最有解都是基本可行解

（5）了解凸集与凸组合的概念，理解两个最优解的凸组合都是最优解 （6）可行解为基本可行解的充要条件 5、线性规划单纯形法

（1）制作初始单纯形表（注意非基变量检验系数的求法，特别注意求有待定系数时的检验数）

（2）各种解的判别条件，对于最大化目标函数问题，包括：唯一最优解：&j<0 有最优解&j<=0 无穷多最优解&j<=0存在一个k有&j=0(或称之为线性规划问题存在可择最优解） 无界解 存在k有&k>0且pk<=0

(3)线性规划问题求解结果中解的情况

有最优解（唯一最优解，无穷多最优解），无界解，无可行解 （4）基变换中入基变量的确定 A、入基变量的必要条件（&j>=0)

B、最速上升准则的理解，不是使目标函数改进最大，而是使目标函数改进速度最大。 （5）最小比值确定出基变量的目的：保证基变换后新的基本解是可行的 （6）会单纯形迭代计算求解线性规划问题

6、什么是线性规划问题退化为题？会引起什么样的后果？ 7、大M法（罚函数法）：（1）辅助问题目标函数的构造

（2）辅助问题解与问题解的关系 （3）能用大M法求解线性规划问题 8两阶段法：（1）第一阶段的目的 判断原问题是否有可行解，当目标函数数值为0时，第一阶段问题的人工基变量已退出基变量，其最优解即为原问题的一个基本可行解，在计算表中为典型形式。若第一阶段最优解值》0说明原问题无可行解

（2）第一阶段的规划模型的目标函数 本部分的典型计算题：

（1）利用单纯形法完整求解线性规划问题 （2）利用大M法完整求解线性规划问题

（3）给定单纯形计算表，其中有部分未知参数，计算含参数的线性规划问题单纯表中各非基变量的检验系数，并判断参数在什么范围变化时有（1）最优解（2）唯一最优解（3）无界解

第三部分 对偶问题、对偶单纯形法与灵敏度分析 1、对偶问题与原问题的转换关系 （1）约束条件数为对方决策变量数

（2）无界性（可根据一个问题有无界解-》另一问题无可行解）

（3）对偶定理：原问题与对偶问题，若一个问题有最优解，则另一个问题也有最优解，且目标函数值相等。

应用：用于判断某个问题无最优解 3、互补松弛定理及应用 （1）定理内容

（2）应用之一：已知一个问题的最优解，不用单纯形法，用解代数方程的方法，求对偶问题的最优解

（3）经济意义解释

4、影子价格概念及经济意义

5、对偶单纯形法（求解特殊线性规划问题） （1）适用条件 （2）会计算

（3）在最优单纯形法下增加一个约束条件，如何转化成能用对偶单纯形法求解的单纯形表形式，并用对偶单纯形法求解。 6、关于灵敏度分析计算要求

（1）计算cj的变化范围，使最优基不改变

（2）给定cj从原值变化为新值时，判断最优基是否改变，若改变，可继续单纯形法，在原最优解表的基础上求新的最优解

（3）计算bi的变化范围，使最优基不改变

（4）具体给定某bi从原值变化到新值时，判断最优基是否改变，若改变，可将B-1b’换最优解表中对应b列数据，并利用对偶单纯形法求解

（5）增加一个约束条件，如何判断最优基是否改变，若改变，如何在原最优解表下求新的最优解。

第四部分 运输问题

1.一些基本概念

（1）运输问题一定有最优解（无论是平衡还是非平衡，但线性规划问题则不一定） （2）分类：平衡、非平衡；产大于销、销大于产 （3）表上作业法确定初始调运方案

方法三种：西北角法、最小元素法、福格尔法

（4）表上作业法所确定的基变量（数字格）的个数=m+n-1 （5）退化情况及处理方法

2、掌握平衡运输问题表上作业法的计算（最小元素+位势法） 3、如何将不平衡问题转化为平衡问题

4、对于在求初始调运方案时，产生的退化情况如何处理：在同时划去的行列中任选一个空格填上运量0即可

第五部分 整数规划与指派问题 1、基本概念

（1）整数规划为题的定义及分类 （2）求解方法的特性 A舍位取整------不能用 B穷举法------无效

C一般有效，方法的思路----增加约束，隐去若干非整数解，求解伴随问题 2、分支定界法

要求掌握一些相关术求解原理步骤，不要求具体求解。 （1）分枝约束条件的增加 （2）如何确定上下界

（3）在分枝定界过程中，上下界的变化规律：上界不断减小，下界不断增加 （4）在该方法中，某分解结果出现什么情况时，需要舍去该分枝 3、割平面方法

（1）掌握如何利用伴随问题

（2）增加割平面约束后，如何利用对对偶单纯形法求最优解 4、如何利用0-1决策变量表示项目选择中一些特殊约束 5、指派问题的匈牙利算法计算题（要会计算） （1）该算法适用情况

A、目标函数为最小化情况

B、效率矩阵为元素均大于等于0的方阵 （2）要会计算

（3）对最大化指派问题如何转换成最小化指派问题 （4）了解人数与事件数不等时的指派问题处理方法

第六部分 存贮论基础 只要求确定性存贮模型

1、最基本的EOQ模型公式及计算

2、允许缺货，即时补充的EOQ模型公式及计算 3、连续供货速率的EOQ模型公式及计算