运筹学总复习.pptVIP

《运筹学》总复习 （1）期末考试题型 （2）内容概要回顾 题目类型 选择填空(10~15分) 判断正误(10~15分) 线性规划建模与计算(15~20分) 灵敏度分析(15~20分) 动态规划建模与计算(10~15分) 图与网络求解计算(10~15分) 排队论计算与优化(10~15分) 第1章 LP的数学模型与单纯形法 一、选择填空 （1） LP模型的判定 Page44 （2） 有无可行解的判断 （3）基本可行解的判定 （4）LP有解、无解、唯一解、无穷多解、无界解判定 （5）基本解与可行解 （6）可行解与基本可行解 （7）线性规划问题基、可行基、对偶可行基、最优基 （8）基变量的系数列向量与非基变量的系数列向量 （9）LP的标准型，其可行解不一定是基本可行解； （10）最优解一定是可行解； （11）最优解一定可以在可行域的顶点上达到； （12）最优解不一定是基本可行解； （13）线性规划标准型 （14）大M法和两阶段法的原理 二、判断正误（√or ×） （1）若线性规划问题的可行域无界，则该现系功能规划问题一定没有最优解。 （2）基本可行解的个数不会超过变量的个数。 （3）用单纯形法求解线性规划问题时，必须要有单位阵作为初始可行基。 （4）线性规划数学模型中的决策变量必须是非负的。 （5）若线性规划问题有解，则约束方程的个数小于等于决策变量的个数。 （6）若最优单纯形表中非基变量的检验数为零，则相应问题的最优解有无穷多个。 （7）单纯形法的迭代计算是从一个基本可行解转换到目标函数值更大的另一个基本可行解。 （8）一旦人工变量在迭代中变为非基变量后，该变量及其相应的系数列就可以从单纯形表中删去，不影响计算结果。 三、LP建模 （1）产品计划问题 （2）产品配套问题 （3）合理下料问题 （4）合理配料问题 （5）进货与销售计划问题 求解算法 单纯形法 大M法 两阶段法 思考讨论题 （1）判断是否为可行域的顶点 （2）标准型及其转化方法 （3）从最优单纯形表格中，如何确定原问题有唯一解、无穷多个最优解、无解、无有限最优解？ 第2章 对偶原理与灵敏度分析 一、选择填空（知识点） （1）原问题与对偶问题的关系 （2）弱对偶定理 （3）有关“界”的判定 （4）最优性准则定理 （5）影子价格的经济含义 二、判断正误 （1）若线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。 （2）若线性规划的对偶问题无可行解，则原问题也一定无可行解。 （3）若线性规划的原问题与对偶问题都具有可行解，则原问题和对偶问题一定具有有限最优解。 （4）已知线性规划问题 。若 是它的一个基本解， 是其对偶问题的基本解，则恒有 。 三、求解算法 对偶单纯形法 最优单纯形表格中的可用信息 灵敏度分析 四、思考讨论题 对偶单纯形方法与原始单纯形方法的解题思路有何不同？ 技术系数变化的灵敏度分析通常在什么情况下是必要的？ 影子价格通常可以为决策者提供哪些有用信息？ 应如何理解对偶问题与原问题之间的对应关系？ 第3章 运输问题 一、选择填空 闭回路的特点 有关闭回路的理论结果 运输问题系数矩阵的秩 个变量构成基变量的充要条件 二、求解算法 初始基本可行解（最小元素法和西北角法） 求检验数（闭回路法和位势法） 思考与讨论题 （1）采用最小元素法或西北角法确定运输问题初始方案过程中，为什么按照规定步骤产生的一组变量必定不构成闭回路，且总数是 个？在划去“行”或划去“列”的过程中，是否会出现要同时划去一行和一列的情况？如何处理？ （2）写出运输问题的对偶问题，然后讨论位势变量的含义。 （3）若运输问题的单位运价表第r行的Cij都加上一个常数k，问最优解是否发生变化？目标函数值变化多大？ （4）若运输问题的单位运价表第p列的Cij都加上一个常数k，问最优解是否发生变化？目标函数值变化多大？ 第4-5章 动态规划 1、选择填空（考点） Page135 一个前提＋四个条件＋一个方程 最优化原理 （1）动态规划的研究对象是多阶段决策问题。 （2）动态规划的建模过程就是在明确①状态变量及其可能集、②决策变量及其可能集、③状态转移方程、④阶段效应的基础上建立⑤动态规划基本方程。 （3）求解DP的一般方法是逆序解法或顺序解法，求解最终应给出①最优路线或最优状态序列、②最优策略或最优决策序列、③最优目标函数值。 （4）用DP方法解决工程线路问题时，无回路有向网络可以转化为定步数问题求解，在确定节点序号时，是以寻找根节点作为依据