运筹学期末复习大纲

第一章*

AAA:线性规划图解法

AA:P10图解法所揭示的，线性规划解的四种情况。

AA:P13线规标准化的方法。

B:P14可行解，基，基可行解，可行基的概念。

A:P16凸集，凸组合的概念，以及第二节若干定理的结论（不看证明，只记结论）。

AAA:P24线规解的三种情况的判别，以及P32无解的判别。

AA:原始单纯形法P31。

B:P33，P34大M法和两阶段法。

C:P36避免死循环的勃兰特法则。

B:P36表1-9

求最大值的线性规划的迭代准则：先大后小。

重点例题：P31-P32对例1的迭代表。

重点书后习题：1.9-1.11

第二章*

AA:P56例3，写出对偶线规的方法。口诀：大横小竖，等号对应无约束。

A:P57对偶问题基本性质的结论。

B:互补松弛性。P59例5。

AA:检验数行和对偶问题最优解的对应关系。

B:影子价格和松弛变量检验数的对应关系，以及影子价格的经济解释。

AAA:P62例6对偶单纯形法。

AAA:灵敏度分析中b的变化P65例7，和C的变化P66例6。

A:技术系数aij的变化。

求最小值的线性规划的迭代原则：双小原则。

对偶单纯形法的迭代原则：双小原则。

重点书后习题：2.2，2.6，2.9(1)(2)(3)。

第三章 运输问题*

A:运输问题约束方程的秩为m+n-1

A:闭回路上的变量所对应的系数列向量线性相关。

运输问题的求解AAA

一，首先判断是否产销平衡

二，求初解：

AAA:最小元素法，

A:差额元素法

初解必须：是m+n-1个，不含闭回路。

三，求检验数：

AAA:闭回路法，

AAA:位势法，位势是对偶问题决策变量的取值，位势具有多解，通常令u1=0，或V1=0，求解位势。

四，调整：AAA闭回路法

五，如果出现退化现象要“补零”以保证基变量的个数为m+n-1不变。

单位运价表价格的设定A

六，A:通常虚拟产销地的运价定为零。

七，A:不论任何情况下，对于不可能和不允许的事情，单位运价要定为M。

八，A:对于有若干种要求的产销地要合理的拆分。

九，A:对单位运价表的行列“加减”任意常数，最优解不变。

一十，AA:运输问题是针对最小值问题的，如果求解“利润最大化”等最大值问题的，要对单位运价变号。MaxCij-Cij

十一，B:有转运的运输问题的初始表，参考表3-40。

重点例题：P80-P87所有内容。

重点书后习题：3.2，3.3表3-46，3.7

第4章目标规划

AAA:目标规划的图解法。口诀:同下反上，小大大小。

重点例题：P103例3，

重点课后习题：P111,4.2

第5章整数规划*

A:分支定界法的思想P117图5-4

AA:添加割平面方程的方法。

AAA:0-1型整数规划的隐枚举法。P124例6

AAA:指派问题的求解方法。P128例8，

口诀:来到全串行，一口肉串一口饼，最后撑死不会吃的行家。

重点书后习题：5.6(1)，5.7

第8章动态规划

A:给定初始或终止状态，选择顺推或逆推的原则。

A:动态规划的基本方程，和基本递推方法。

重点例题：P204例3，P206例4.

重点课后习题：无。

第9章动态规划应用举例*

重点例题：例1，例6，例7，例8

重点课后习题：9.3，9.13(1)，9.14，9.15

第十章 图与网络**

A:P254定理1，定理2。

AA:树的概念及其定理，P257定理5定理6。

AAA:最小支撑树的求法

AAA:无负权的最短路问题的标号法

A:负权最短路的求法，以及摹乘法。

AAA:网络最大流问题的求法

AA:可行流的条件P269，

AA:最大流最小截集定理，给定一个图，能找出所有截集。

B:最小费用最大流的求法AA:欧拉链，欧拉圈及欧拉图的概念。

AA:中国邮路问题的奇偶点作业法，对最优解的判别准则,P279   重点例题：P259例8，P261例10，P273例14    重点课后习题：10.10，10.11，10.12