2019《运筹学》总复习课件.ppt

《2019《运筹学》总复习课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《运筹学》总复习（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）基变量的系数列向量与

2、非基变量的系数列向量（9）LP的标准型，其可行解不一定是基本可行解；（10）最优解一定是可行解；（11）最优解一定可以在可行域的顶点上达到；（12）最优解不一定是基本可行解；（13）线性规划标准型（14）大M法和两阶段法的原理二、判断正误（√or×）（1）若线性规划问题的可行域无界，则该现系功能规划问题一定没有最优解。（2）基本可行解的个数不会超过变量的个数。（3）用单纯形法求解线性规划问题时，必须要有单位阵作为初始可行基。（4）线性规划数学模型中的决策变量必须是非负的。（5）若线性规划问题有解，则约束方程的个数小于等于决策变量的个数。（6）若最

3、优单纯形表中非基变量的检验数为零，则相应问题的最优解有无穷多个。（7）单纯形法的迭代计算是从一个基本可行解转换到目标函数值更大的另一个基本可行解。（8）一旦人工变量在迭代中变为非基变量后，该变量及其相应的系数列就可以从单纯形表中删去，不影响计算结果。三、LP建模（1）产品计划问题（2）产品配套问题（3）合理下料问题（4）合理配料问题（5）进货与销售计划问题求解算法单纯形法大M法两阶段法思考讨论题（1）判断是否为可行域的顶点（2）标准型及其转化方法（3）从最优单纯形表格中，如何确定原问题有唯一解、无穷多个最优解、无解、无有限最优解？第2章对偶原理与

4、灵敏度分析一、选择填空（知识点）（1）原问题与对偶问题的关系（2）弱对偶定理（3）有关“界”的判定（4）最优性准则定理（5）影子价格的经济含义二、判断正误（1）若线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。（2）若线性规划的对偶问题无可行解，则原问题也一定无可行解。（3）若线性规划的原问题与对偶问题都具有可行解，则原问题和对偶问题一定具有有限最优解。（4）已知线性规划问题。若是它的一个基本解，是其对偶问题的基本解，则恒有。三、求解算法对偶单纯形法最优单纯形表格中的可用信息灵敏度分析四、思考讨论题对偶单纯形方法与原始单纯形方法的解题思

5、路有何不同？技术系数变化的灵敏度分析通常在什么情况下是必要的？影子价格通常可以为决策者提供哪些有用信息？应如何理解对偶问题与原问题之间的对应关系？第3章运输问题一、选择填空闭回路的特点有关闭回路的理论结果运输问题系数矩阵的秩个变量构成基变量的充要条件二、求解算法初始基本可行解（最小元素法和西北角法）求检验数（闭回路法和位势法）思考与讨论题（1）采用最小元素法或西北角法确定运输问题初始方案过程中，为什么按照规定步骤产生的一组变量必定不构成闭回路，且总数是个？在划去“行”或划去“列”的过程中，是否会出现要同时划去一行和一列的情况？如何处理？（2）写出

6、运输问题的对偶问题，然后讨论位势变量的含义。（3）若运输问题的单位运价表第r行的Cij都加上一个常数k，问最优解是否发生变化？目标函数值变化多大？（4）若运输问题的单位运价表第p列的Cij都加上一个常数k，问最优解是否发生变化？目标函数值变化多大？第4-5章动态规划1、选择填空（考点）Page135一个前提＋四个条件＋一个方程最优化原理（1）动态规划的研究对象是多阶段决策问题。（2）动态规划的建模过程就是在明确①状态变量及其可能集、②决策变量及其可能集、③状态转移方程、④阶段效应的基础上建立⑤动态规划基本方程。（3）求解DP的一般方法是逆序解法或

7、顺序解法，求解最终应给出①最优路线或最优状态序列、②最优策略或最优决策序列、③最优目标函数值。（4）用DP方法解决工程线路问题时，无回路有向网络可以转化为定步数问题求解，在确定节点序号时，是以寻找根节点作为依据的。（5）有消耗的资源多阶段地在两种不同的生产活动中投放的问题属于资源的多阶段分配问题；解决生产－库存问题中应特别注意的是决策变量的允许取值范围。2、判断正误（1）最优性原理可以表述为“策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其余的决策序列必构成最优策略。”（2）对于一个DP问题，应用顺推和逆推解

8、法可能会得出不同的最优解。（3）假如一个标准化的LP问题有5个变量和3个约束，则用DP求解是将其化为3个阶段，每个阶段的状态变量由一个5