运筹学复习提纲

1、运筹学 1复习提纲第一章规划问题的三要素 线性规划问题的条件线性规划问题的标准形式标准化方法线性规划和单纯形法1.2.3.4.5.6.可行解、可行域、最优解7.向量、基变量、非基变量、基解、基可行解（至多作用在目标函数中的系数松弛变量化不等式约束为等式约束0人工变量使系数矩阵有矩阵-M（大 M 法）第二章 线性规划的对偶理论1、原问题的基本形式对偶问题的基本形式2、原问题与对偶问题的互化3、对偶问题的基本性质1)2)3)4)5)6)弱对偶性最优性性 强对偶性互补松弛性（由松得紧性）互补的基解4、利用对偶理论求最优解的方法5、价格6、灵敏度分析（不考）1)2)3)分析 Cj，可使最优解不变分析

2、bi，可使最优基不变增加一个变量的分析2.1(a,b),2.2,2.4,2.9(a,b,c)第三章1、问题的已知条件：产销平衡表，问题有最优解的条件：产销平衡问题运价表2、m 产 n 销的问题有 mn 个决策变量，有 m+n 个约束条件，有 m+n-1 个基变量（有数字格），有 mn-(m+n-1)个非基变量（空格） 3、调运方案表（基可行解）：有数字格，空格4、空格的闭回路的闭回路的作用：计算检验数改进方案5、利用检验数判断调运方案的最优性若有负检验数，则此方案要改进；若无负检验数，则此方案为最优方案。6、表上作业法的步骤1)2)3)4)确定初始方案：最小元素法或求检验数：闭回路法或位势法判

3、断最优性改进方案法7、产销不平衡的问题的处理若产大于销，则增加虚拟的销地，其销量为总产量-总销量，从各产地至该销地的单价为 0；若销大于产，则增加虚拟的产地，其产量为总销量-总产量，从该产地至刚性销地的单价为 M，至弹性销地的单价为 0.3.1,3.5(a,b,c),3.6,3.7,3.10第四章 整数规划与分配问题1、整数规划2、整数规划的分类：纯整数规划和混合整数规划3、整数规划的松弛问题4、松弛问题的最优解与整数规划最优解的关系5、0-1 变量（逻辑变量）0-1 规划6、0-1 变量在建模中的作用7、分配问题已知条件：m 阶的效率矩阵，独立 0 元素M 阶标准分配问题有个 0-1 变量，

4、有 2m 个约束条件，是特殊的LP/IP/TP/0-1 规划，一定有最优分配方案8、匈牙利法m21)2)3)适用范围步骤：造 0，划直线，打破僵局两个说明：对于目标极大化的分配问题；当人数大于工作数时，增加虚拟的工作，每个人完成虚拟工作的时间为 0；当工作数大于人数时，增加虚拟的人，虚拟的人完成各项工作的时间为 0或 M 或其它。4.1，4.2，4.3，4.5，4.6，4.13，4.16第六章 图与网络分析(无向)图 G=V,E,点,边,点与边之间的关联关系图的阶网络图(赋权图)简单图连通图零图,完全图,完全偶图,树点的次,孤立点,悬挂点子图,部分图,部分树树的相关结论1.2.3.4.5.6.7.8.9.最小部分树的求法:避圈法,破圈法最短路或最短距离的求法:狄克斯屈拉(dijkstra)标号算法有向图 D=V,A，点的分类，弧的容量，弧的流量，可行流的条件，总流量，网络的最大流，割，割的容量，前向弧，后向弧，增广链的条件，重要结论：最小割的容量=最大流的流量； 最大流的判断方法：是