《运筹学》总复习.ppt

运筹学总复习,（1）期末考试题型（2）内容概要回顾,题目类型,选择填空(1015分)判断正误(1015分)线性规划建模与计算(1520分)灵敏度分析(1520分)动态规划建模与计算(1015分)图与网络求解计算(1015分)排队论计算与优化(1015分),第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方法解决工程线路问题时，无回路有向网络可以转化为定步数问题求解，在确定节点序号时，是以寻找根节点作为依据的。（5）有消耗的资源多阶段地在两种不同的生产活动中投放的问题属于资源的多阶段分配问题；解决生产库存问题中应特别注意的是决策变量的允许取值范围。,2、判断正误（1）最优性原理可以表述为“策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其余的决策序列必构成最优策略。”（2）对于一个DP问题，应用顺推和逆推解法可能会得出不同的最优解。（3）假如一个标准化的LP问题有5个变量和3个约束，则用DP求解是将其化为3个阶段，每个阶段的状态变量由一个5维向量组成。（4）适合用动态规划模型求解的多阶段决策问题的目标函数，必须具有关于阶段效应的可分离形式。,（5）资源的多元分配问题是指有消耗的资源多阶段在多种不同的生产活动中投放的问题。（6）DP中，定义状态应保证在各个阶段中所作决策的相互独立性。,三、数学建模工程线路问题资源的多元分配问题资源的多阶段分配问题生产库存问题设备更新问题串联系统可靠性问题背包问题,思考讨论题举例解释最优化原理状态转移方程是不是一定是数学意义上的方程？分析生产库存问题中状态变量和决策变量的允许取值范围是如何确定的。在问题求解过程中应当注意哪些问题？生产库存问题可以用线性规划模型描述和求解吗？动态规划求解的一般方法是“逆序求解”，但有些问题也可以“顺序求解”。讨论什么样的多阶段决策问题可以“顺序求解”，并写出此时的状态转移方程和动态规划基本方程的一般表达式。,（5）图1给出了两个网络最短路问题，S是起点，T是终点，请在箭头边上填上代表两点距离（或费用）的数据，然后设法求从节点S到T的最短路长和最短路线。该问题能转化为动态规划处理吗？试建立动态规划模型并讨论其求解方法。,（a）,（b）,1、选择填空Page174（1）无环也无多重边的图叫简单图。无圈且连通的图叫树。（2）已知图a，则图b是其生成子图，图c是部分树，图d是真子图。,（a）,（b）,（c）,（d）,第6-7章图论与网络分析,（3）某连通图G的各顶点的次分别是4,1,1,2,2,2,则G不是树。（4）用网络分析方法求最短路的D氏标号法使用条件是所有权非负，Ford算法的使用条件是无负回路。（5）在网络最大流问题的求解过程中，每一次标号过程所寻找的流量修正路线不一定唯一，最终求得的最大流不一定唯一，最小割也不一定唯一。最大流量是唯一确定的，最小割容量是唯一确定的。（6）用Ford-Fulkerson标记化方法求网络最大流时，标号过程的目的是寻找流量修正路线，寻求的增广链中的弧一定满足：正向非饱和、反向非零流。,2、判断正误（1）最短树是网络中总权数最短的部分树，因此它既是部分图，又是无圈的连通图。（2）部分树的余树不一定是树，最短树问题是求总权数最小的、图的部分树的问题。（3）如果一个图的支撑子图是一棵树，则这棵树就是该图的支撑树。（4）最短路算法中的D氏标号法使用条件是无回路，列表法使用条件是无负权。（5）任意一个容量网络中，从起点到终点的最大流量等于分离和的任意一个割集的容量。,（6）容量网络中满足容量限制条件和中间点平衡条件的图上的流叫做可行流。（7）求解最大流最小费用的对偶法的主要思想是：始终保持网络中的可行流是最小费用流，然后不断地在最小费用增广链上调整流量，使流量逐步增大最终成为最小费用最大流。,4、求解算法最短路问题：D氏标号法（图上标号和表格计算）Ford算法（列表法）海斯算法（最短路和最短路线）最小树问题破圈法逐步生长法最大流问题标号方法增广链调整量，最小割的确定最小费用最大流增广费用网络最小费用增广链调整流量直到等于最大流,思考讨论题,（1）图7.24中所示的无回路有向网络是否可利用D氏标号法求解从起点s到终点t的最短路？,图7.24,(2)某企业所使用的一台生产设备，在每年年底，企业都要决策下年度是购买一台新设备，还是继续使用这台旧设备。若购买新的，就要支付一笔购置费；如果使用旧设备，就要支付一笔维修费，而维修费随着设备使用年限的延长而增加。现根据以往统计资料已经估算出设备在各年年初的价格和不同使用年限的年维修费用，分别如表7.10和表7.11所示。怎样将此问题化为最短路问题？,表7.10设备的年初购置费,表7.11设备维修费,（3）最小费用最大流问题的实质是当最大流不唯一时，在这些最大流中求一个费用最小的流。试问：能否判断最大流的唯一性？如果在所有的可行流中选择费用尽量小、流量尽量大的一个流，这就成了一个两个目标的多目标规划问题，试建立一个这样的多目标规划模型。（4）最大流问题中，若将目标函数改成min的最小费用问题，试考虑求最大流的方法是否同样适用。,第8910章排队论,1、选择填空Page219（1）排队系统由输入过程、排队规则和服务台三个部分组成，系统状态指系统中的顾客数。MM/C/N指的是顾客到达按照泊松流，服务时间服从负指数分布，C个服务台，系统容量为N的排队系统。（2）,2、判断正误（1）若到达排队系统的顾客为泊松流，则依次到达的两名顾客之间的间隔时间服从负指数分布。（2）若到达排队系统的顾客来自两方面，分别服从泊松分布，则这两部分顾客合起来的顾客流仍为泊松分布。（3）对M/M/1或M/M/C的排队系统，服务完毕离开系统的顾客流也为泊松流。（4）一个排队系统，不管顾客到达和服务时间的情况如何，只要运行足够的时间后，系统将进入稳定状态。（5）排队系统中，顾客等待时间的分布不受排队服务规则的影响。,（6）在顾客到达和机构服务时间分布相同的情况下，容量有限的排队系统，顾客的平均等待时间将少于队