运筹学知识重点、重要结论.docVIP

第一章 线性规划问题 知识重点： 1 ．将给定的线性规划问题化为标准型 2 ．能根据简单的实际问题，建立线性规划问题的数学模型，并用单纯形法求解 3 ．几个重要结论 1 ）若线性规划问题存在最优解，它一定在可行域的某个顶点得到。 2 ）若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。 3 ）线性规划问题的每个基可行解对应可行域的一个顶点。 4 ）线性规划问题的可行解如为最优解，则该可行解一定是基可行解。 第二章 对偶理论与灵敏度分析 知识重点： 1 ．对于给定的线性规划问题，能写出它的对偶问题 2 ．给定原问题（或对偶问题）的最优解，求对偶问题（或原问题）的最优解 。 3 ．对偶单纯形法 4 ．对偶问题的经济解释，影子价格 5 ．几个重要结论 1 ）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 2 ）若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。 3 ）若线性规化的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 4 ）当对偶问题无可行解时，其原问题无最优解。 5 ）若线性规划问题和对偶问题都具有可行解，则该线性规划问题一定具有无限最优解或有限最优解。 第三章 运输问题 知识重点： ?? 平衡问题的求解方法————表上作业法 ?? 不平衡问题的求解方法： 先将其转换为平衡问题，然后用表上作业发求解。 3 ．表上作业法分三个步骤： 1 ）确定初始方案 ————最小元素法 2 ）进行最优性检验—————位势法 3 ）调整、改进非最优方案——闭回路法 4 ．几个重要结论 ?? 运输问题是一种特殊的线性规划问题，它一定有最优解 ?? 用表上作业法求解运输问题时要求：产、销平衡 ?? 当所有产地的产量和销地的销量均为整数值时，运输问题的最优解也为整数值 ?? 表上作业法与单纯形法在求解最优解的问题上没有本质的区别 第四章 目标规划 知识重点： ?? 根据简单的实际问题，建立目标规划模型 ?? 目标规划模型的求解方法：图解法，单纯形法 ?? 分析目标规划的优先因子变化对原满意解的影响 ?? 重要结论 线性规划问题是目标规划问题的一种特殊形式。 第五章 整数规划 知识重点： ?? 求解纯整数规划问题和混合整数规划问题的方法——分枝定界法 ?? 纯整数规划的求解方法——割平面法 ?? 0 － 1 型整数规划求解方法——隐枚举法 ?? 极小化指派问题的求解方法——匈牙利法 5 ．几个重要结论 1 ）分枝定界法既可以用来求解纯整数规划问题，也可以用来求解混合整数规划问题 2 ）割平面法只能用来求解纯整数规划问题 3 ）用割平面法求解纯整数规划时，构造的割平面不会切割掉不属于最优解的整数解 第六章 图与网络分析 知识重点： ?? 求图的支撑树的方法：避圈法，破圈法 ?? 求图的最小支撑树的方法：避圈法，破圈法 ?? 求最短路的方法： Dijkstra 方法 ?? 如何求网络的最大流 第七章 排队论 知识重点： 1 ．单服务台的情况 1 ）标准的 ( ) 2 ）系统的容量有限制 ( ) 3 ）顾客源为有限 ( ) 2 ．多服务台的情况 1 ）标准的 的模型 ( ) 2 ）系统的容量有限制 ( ) 3 ．几个重要结论 4 ．标准的 ( ) 的主要公式： 1 ） ，表示服务机构的繁忙程度； 2 ） ，表示服务机构空闲的概率 3 ）在系统中的平均顾客数（队长期望值）： 4 ）在队列种等待的平均顾客数（队列长期期望值）： 5 ）在系统中顾客逗留时间的期望值： 6 ）在队列中顾客等待时间的期望值： 5 ．几个重要结论： 1）若排队系统中顾客相继到达的时间间隔服从负指数分布，则输入过程为普阿松流 2 ）若到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾客流仍为普阿松分布 3 ）若排队系统中到达的顾客为普阿松流，则依次到达的两个顾客之间的间隔时间一定服从负指数分布