运筹学复习提纲

2010年运筹学复习提纲

考试范围：

上海财经大学出版社（第二版）运筹学 第一章、第二章、第六章和第八章 考试要求：

要求会用运筹学的有关原理和方法解决实际中的某些最优化问题。 考试重点：

1. 理解单纯形法的解题步骤，会用单纯形法求解最大化线性规划问题； 2. 会根据单纯形表写出基可行解，

3. 会在计算过程中，判断问题是否存在唯一解，多个最优解、无解、退化解。 4. 理解表上作业法的解题步骤，会用该法解决供求平衡的运输问题；

5. 会用最小元素法，最大差额法求初始方案，会用位势法和闭合回路法判断该方案是

否是最优方案，会用闭合回路法加以调整。 6. 会用匈牙利算法解决生活中的某些分配问题。

7. 会用运筹学的有关知识解决最短路径问题、最小树问题、最大流问题和中国邮递员

问题；

8. 会根据工序间的逻辑关系画出所给工程的工程网络图； 9. 理解风险型决策中的期望值标准，预期值标准；

10. 理解不定型决策中的保守主义，乐观主义，现实主义等五个常见标准，会根据这些

标准进行决策。

考试题型：

选择题（20分），填空题（20分），画图题（18分），计算题（42分）。 考试样题： 一、选择题

1. 某游客从公园的正门进入游览区，要求参观完每条线路的每个景点，最后再从正门出来，如何选择旅游路线，才使所走的路线最短？该问题可归结为（ ）问题得到解决。 A. 最短路问题 B. 最大流问题， C. 最优树问题 D. 中国邮递员问题 2.下列有关树的叙述中，错误的是（ ） A. 树是具有相同顶点的边数最小的连通图； B. 树是具有相同顶点的边数最多的无圈图；

C. 最小生成树是具有相同顶点的权数最小的连通图 D. n个顶点的树中各顶点的次数之和为2n-2; 3. 有关图的概念中，叙述不正确的是（ ） A. 没有自回路和平行边的图称为简单图。 B. 任一图中奇点的个数必为偶数； C. 有奇点的图一定不可以一笔画

D. 工程网络图主要由工作、事项和路线三部分组成。

4. 某影星从广州出发，途径香港和开罗，去巴黎参加奥斯卡奖颁奖仪式，她选择一条什么路线才使空中旅程最短。此问题可采用（ ）得到解决。

A. 狄克斯屈标号算法 B.破圈法 C. 奇偶点图上作业法 D. 最小元素法 5.关于线性规划模型的可行解区，叙述正确的为（ ） A.可行解区必有界 C.可行解区必是凸的

B.可行解区必然包括原点 D.可行解区内必有无穷多个点

6. 关于线性规划问题，叙述正确的为（ ） A.其可行解一定存在 C.其可行解必是最优解

B.其最优解一定存在

D.其最优解若存在，在可行解中必有最优解

7. 在运输问题中如果总需求量小于总供应量，则求解时应（ ） A.虚设一些供应量

C.根据需求短缺量，虚设多个需求点 8..虚活动是（ ） A.占用时间，但不消耗资源 C.不占用时间，但消耗资源

B.不占用时间,也不消耗资源 D.既消耗资源，也消耗时间 B.虚设一个供应点 D.虚设一个需求点

9.一个居民住宅区的道路构成图是（ ）

A.树 B.不连通图 C.连通图 D.有向图

10. 在解运输问题时，若已求得各个空格的改进路线和改进指数，则选择调整格的原则是（ ）

A.在所有空格中，挑选绝对值最大的正改进指数所在的空格作为调整格 B.在所有空格中，挑选绝对值最小的正改进指数所在的空格作为调整格 C.在所有空格中，挑选绝对值最大的负改进指数所在的空格作为调整格 D.在所有空格中，挑选绝对值最小的负改进指数所在的空格作为调整格 11. 对工程网络图而言，叙述正确的是（ ）

A.从始点出发，经过连续相接的活动，直到终点的一条连线称为线路 B.从始点出发，经过连续相接的活动，到某个结点终止的连线称为线路

C.从某个结点出发，经过若干个连续相接活动，直到终点的一条连线称为线路 D.任意两个始点之间，由若干个连续相接活动组成的连线称为线路 12．在工程网络图中，叙述不正确的是（ ） ．．．A.网络图中任何一个结点都表示前一活动的结束和后一活动的开始 B.活动的总时差越大，则表明该活动在整个网络中的机动时间也越大 C.活动的最早开始时间等于该活动箭尾事项的最早开始时间 D.结点时差等于0的结点称为关键结点

13. 决策标准中，需要决策者确定概率的是（ ） A.最大最大决策标准 B.最小最大遗憾值决策标准 C.现实主义决策标准 D.最大最小决策标准 14. 现有三种备选方案Ⅰ、Ⅱ、Ⅲ，其收益情况如表： 方案 Ⅰ Ⅱ Ⅲ 最大收益(万元) 15 12 14 最小收益(万元) 8 10 9 若使用最大最小决策标准选取方案，则在未来遇到最佳的自然状态时，其收益值为（ ） A.10万元 B.12万元 C.14万元 D.15万元 15.一个含有圈的5个点的连通图的线数（ ） A.至少为4 B.至少为5 C.等于5 D.至多为5

16.某配电站要向由其供电的五个小区铺设电缆，此时应采用的方法是（ ）

A.最短路线法 B狄克斯屈标号法 C.最大流量法 D.决策树法 二、填空题

1．在单纯形法的任一次迭代中，若换入基变量所在一列中的元素都是 时，可以确定解是无界的。

2. 在最终单纯形表中，若非基变量所对应的检验数为 时，说明问题有多个最优解。 3．检验某调运方案是否最优的方法通常有 和位势法（乘数法）两种。 4. 若图中任意两点之间至少存在一条链，则该图为 图。

5. 在运输问题中，若非零基变量的个数小于n+m-1,则此种现象称为 。 6. 在进行决策时，若存在一个以上自然状态，且各种自然状态的概率值能够估算，则应采用_______决策。

7网络计划技术综合运用了计划评核术和_______。 8. 在一个城市中敷设有线电视网，宜采用_______法。

9.. 由位势法算得的改进指数与由闭合回路法算得的改进指数是__________的。

10．在运输问题中，如果总需求量大于总供应量，则求解时应先虚设一个 ，然后再求解。

11．匈牙利算法是由匈牙利数学家 提出来的；奇偶点图上作业法是由中国数学家 首先提出来用以解决中国邮递员问题的。

2.已知某工程的活动明细列题40表如下。试编制网络图，并找出关键线路。

题40表 工序 A B C D E 紧前工序 无 无 A，B B C 工作时间（天） 5 2 4 4 2 F D 3 .4.某运输问题的产销平衡表和单位运价表如表所示：

求：(1)用最小元素法建立初始调运方案；

(2)用位势法判断该初始调运方案是否是最优方案；若不是，则作一次调整。

5. 工程由七道工序组成，其有关资料如表所示： 试求：(1)画出该工程的箭线式网络图；

(2)通过计算结点和工序的网络时间，确定关键线路。

工序 作业时间(天) 紧前工序 A 5 无 B 9 A C 13 A D 8 B E 6 C、D F 12 无 G 4 E、F 6．已知甲、乙、丙、丁四位老师去担任英语、法语、德语、俄语四门课程的教学，其中丁不能胜任德语，丙不胜任法语，并且其成本矩阵如下：

求最优分配方案。 6.第138页2-15， 7.第87页 1-4

8.第269页6-8,6-13,6-14,6-17 9.第343页，8-6

10.第32页 四.几种特殊情况的解。 11．第92页 1-29

12. 第244页 增广链的概念及其充要条件。

本文来源：https://www.bwwdw.com/article/d7yt.html