运筹学复习要点.docVIP

任我行 运筹学复习要点 线性规划与单纯形法 标准型：规定具有下述条件的线性规划问题为标准型式的线性规划问题：1、目标函数为求最大；2、约束条件为等式约束；3、决策变量为非负。 线性规划问题具有的特征：1、每一问题都用一组决策变量（x1, x2, . . . , xn）表示某一方案；2这组决策变量的值就代表一个具体方案，一般这些变量值是非负的；3、存在一定的约束条件，它们可用线性等式或不等式表示；4、都有一个要求达到的目标，它们可用决策变量的线性函数表示，称目标函数。根据问题不同，要求目标函数实现最大化或最小化。 图解法的结论：1、可行域一定是凸集，即该区域内任意两点间连线上的点仍在该区域内；2、线性规划最优解不可能在凸集内的点上实现；3、线性规划问题有可能存在无穷多最优解；4、如果可行域无界，则最优解可能是无界解；5、如果不存在可行域，则没有可行解，也一定不存在最优解；6图解法只适用于两个决策变量的情况。 单纯形法：其基本思路是首先确定一个初始基可行解，然后判断该基可行解是否为最优解。如果是最优解，则求解过程结束；如果不是最优解，则在此基础上变换找出另一个基可行解，该基可行解的目标函数值应该优于原基可行解。再判断新的基可行解是否为最优解，如果是最优解，则求解过程结束；如果不是最优解，则在此基础上变换再找出另一个新基可行解，如此进行下去，直到找到最优解为止。 最优性检验与解的形式：最优解的判别定理，若X(0) = (b′1, b′2, ……… , b′m, 0, …… , 0)T为对应于基B的一个基可行解，且对于一切j = m + 1, …… , n，有σj 6 0，则X(0)为最优解，称σj为检验数。无穷最多解判别定理，若X(0) = (b′1, b′2, …… , b′m, 0, …… , 0)T为对应于基B的一个基可行解，且对于一切j = m + 1, …… , n，有σj 6 0，又存在某个非基变量的检验数σm+k = 0，则线性规划问题有无穷多最优解。无界解的判别定理，若X(0) = (b′1, b′2, ……… , b′m, 0, …… , 0)T为一个基可行解，有一个σm+k 0,且对i = 1, 2, …… , m，有ai m+k ≤ 0，那么该线性规划问题具有无界解（或称为无最优解）。 对偶理论与灵敏度分析 写出对偶??式：P37 互补松弛性定理：若X0,Y0分别是原问题和对偶问题的可行解，则当且仅当X0,Y0为最优解时存在Y0Xs＝0，YsX0＝0. 对偶变量：根据导数来的。Y=CB^-1 灵敏度分析：三个参数只变一个，但会出两个相关的。 整数规划 整数规划：在一般的线性规划模型中，变量为非负，而在整数规划模型中，全部或部分变量不仅为非负，而且还要求为整数。如果所有的变量都为正整数或零，称为全整数规划，如果仅其中一部分变量要求为正整数或零，则称其为混合整数规划；（整数条件下的最优解一定不优于非整数条件下的最优解）。 关于整数归划的问题：为什么取整、四舍五入不可以？ 指派问题：从原效率矩阵的某行（或列）减去一个常数后得到的新矩阵与原矩阵求得的最优解不变。匈牙利解法：效率矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。匈牙利法使用是有条件的，如果不满足要先调整 运输问题 简答题，位势法的原理：P67 计算：1、表格找方案；2、产销不平衡转化为平衡（及增减产地或增加库房和销售地）。 运输问题本质上是线性规划问题，但总是存在着可行解运输问题的有效约束只有m + n ? 1个。 最小元素法的思想：是就近供应，即从单位运价中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止 伏格尔法原理：用最小元素法确定的初始基可行解仅考虑了最小运费，但有时选择了最小运费的机会成本很大，即选择了一种调运路径，必然放弃其他可能的选择，这样有可能因其他运输路径单位运费增长过大从而使总的运费加大。所以要进行最小运费路径与其他可能运输路径间的协调。 运输问题：实质上是具有m+n-1个线性约束方程的目标函数求最小的问题。在运输问题中，满足约束条件且基变量个数恰好为m+n-1个的解即为基可行解。而从任意一个基可行解出发经过换基迭代过程总是可以找到最优解的，所以说运输问题一定存在最优解。 动态规划 最短路问题：标号法。 一维资源分配问题：只有一种资源的分阶段决策。 图论 最短路问题：Dijkstra标号法P103. 网络最大流问题：标号法P116. 网络规划 计算时间参数，要会画网络图。 两种方法：单标号法，双标号法，耒唯一的起点和终点，尽量少的虚线。 网络规划中统筹方法的基本原理是：从需要管理的任务的总进度着眼，以任务中各工作所需要的工时为时间因素，按照工作的先后顺序和相互关系做出网络图，以反映任务全貌，