运筹学复习大纲

运筹学复习大纲

1． 线形规划部分

（1） 会求一般线性规划问题的标准形式。要求见37页表格。 （2） 了解线形规划的可行解、基解、基可行解、最优解等概念。 （3） 知道单纯形法的几个基本定理。

（4） 掌握大M法与两阶段法求解线性规划问题的方法步骤。

（5） 知道线性规划问题唯一最优解，有无界解，无穷多最优解，无可行解的判别方

法。

2． 对偶理论

（1） 会求原规划问题的对偶问题。 （2） 了解对偶原理。

（3） 知道对偶单纯形法的迭代步骤。

（4） 灵敏度分析部分：会对增加变量与增加约束条件情况进行分析。 3． 运输问题

（1） 知道运输问题的数学模型。

（2） 掌握运输问题的表上作业法（初始方案的确定，最优性检验，调运方案的调整）。 （3） 会处理产大于销的运输问题。 4． 指派问题

（1） 知道匈牙利法解决分配问题的理论依据，掌握匈牙利法求解指派问题的方法。 （2） 知道人多任务少时的处理方法及人比任务少一个时的处理方法。 5． 整数规划

（1）会用割平面法求解整数规划问题 6． 目标规划

（1）会建立目标规划数学模型，会解释目标约束的意义。 7． 图论部分

（1） 了解图的基本概念：简单图、完全图、偶图、子图、部分图等，次（度）、链、

路、圈、回路等。

（2） 知道树的概念和基本性质。知道求图的最小部分树的理论依据和方法。 （3） 会求最短路。

（4） 会求网络的最大流与最小割。 （5） 会求最小费用流。 8. 动态规划

（1）了解动态规划的基本概念及最优化原理. （2）知道动态规划的求解方法. 9．存储论

（1）了解存储论的相关概念.

（2）掌握确定型存贮模型.

1

运筹学复习题

一、填空题

1． 在线性规划标准形式中，要求约束条件右侧常数bi(i1,2,,m)为_____ 数。 在化线性规划为

标准形式时，需将自由变量x作变化为__________。

naijxjbi(i1,2,,m) 2．线性规划问题中满足j1的解称为 。

xj0,j1,2.n 3．线性规划问题的可行解集必为 集。

4．线性规划的最优解若存在，必在可行域的某个 取得。

5．用单纯形方法求解线形规划问题时，判定问题无可行解的条件是 ；判定问题具有无界解的条件是 ；具有无穷最优解的条件是 ；具有唯一最优解的条件是 。

6．求解分配问题匈牙利法的依据之一是：如果从分配问题的效率矩阵aij的每一行元素中分别减去（或

加上）一个常数ui，从每一列分别减去（或加上） 一个常数vj，得到一个新的效率矩阵bij，则 。

7．若矩阵A中的元素可分为“0”与非“0”两部分，则覆盖所有“0”元素的最少直线数等于 。

8．分配问题中，若工作人员数多于任务数时，则采取 的办法。

9．在整数规划的割平面法中，非整数解变量分数部分最大的一个基变量x2 的相应约

x2111x3x42222， 则可得相应的Gomory约束

为 。

10．求解产大于销的运输问题时，要化为平衡运输问题，具体的做法是 。

mind11．目标规划中目标约束的意义是 。2x13x2dd15mind的意义是 。 2x13x2dd15mindd 的意义是 。 2x13x2dd1512．简单图是指 。

13．树的定义是 。将树增加一条边，则会出现 ，若减少一条边，则会出现 。 14．具有n个顶点的树，其边数为 条。

15.平衡运输问题中，变量的个数为 个，约束条件的个数是 ，基变量的个数是 。 16．G2V2,E2是G1V1,E1的部分图，那么V2与V1的关系是 ； E2与E1的关系是 。 17．可行流的条件。

18．线性规划原问题与对偶问题最优解的关系。

19．动态规划基本方程是 。 二、相关练习题

P10,例6; P17,例8; P18,例9; P34,例4; P37,例7; P39,例8; P44,例1; P51,例2; P62,例3; P65,例5; P87,例2,3; P90,例5; P95,例8; P98,例10; P118,例2, P120,例3.

2