运筹学参考答案

第 1 页 共 29 页 《运筹学》复习参考资料

资料加工、整理人——杨峰（函授总站高级讲师）

要求掌握的各部分知识点

第一部分 线性规划问题的求解（相当于教材的第一章）

——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法

第二部分 动态规划问题的求解（相当于教材的第三章）

——重要算法：图上标号法

第三部分 网络分析问题的求解（相当于教材的第四章）

——重要算法：破圈法、TP标号法、寻求网络最大流的标号法

第四部分 存储论简介（相当于教材的第七章）

※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。

非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解

一、两个变量的线性规划问题的图解法：

㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。

㈡图解法：

图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；

2、确定可行解域；

3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；

注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）

例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：

《运筹学》习题答案

一、单选题

1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ ）B

A.任意网络 B.无回路有向网络 C.混合网络 D.容量网络

2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（ ）B

A.非线性问题的线性化技巧 B.静态问题的动态处理

C.引入虚拟产地或者销地 D.引入人工变量

3.静态问题的动态处理最常用的方法是？B

A.非线性问题的线性化技巧 B.人为的引入时段

C.引入虚拟产地或者销地 D.网络建模

4.串联系统可靠性问题动态规划模型的特点是（ ）D

A.状态变量的选取 B.决策变量的选取

C.有虚拟产地或者销地 D.目标函数取乘积形式

5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。C

A.降低的 B.不增不减的 C.增加的 D.难以估计的

6.最小枝权树算法是从已接接点出发，把( )的接点连接上C

A.最远 B.较远 C.最近 D.较近

7.在箭线式网络固中，( )的说法是错误的。D

A.结点不占用时间也不消耗资源

B.结点表示前接活动的完成和后续活动的开始

C.箭线代表活动

D.结点的最早出现时间和最迟出现时间是同一个时间

8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。C

A.1200 B.1400 C.1300 D.1700

9.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（ ）。D

A.最短路线—定通过A点 B.最短路线一定通过B点

C.最短路线一定通过C点 D.不能判断最短路线通过哪一点

10.在一棵树中，如果在某两点间加上条边，则图一定( )A

A.存在一个圈 B.存在两个圈 C.存在三个圈 D.不含圈

运筹学试题

(代码：8054)

一、填空题(本大题共8小题，每空2分，共20分)

1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加___的方法来产生初始可行基。

2．线性规划模型有三种参数，其名称分别为价值系数、___和___。

3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。

4．求最小生成树问题，常用的方法有：避圈法和 ___。

5．排队模型M／M／2中的M，M，2分别表示到达时间为___分布，服务时间服从负指数分布和服务台数为2。

6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为____型决策。

7．在风险型决策问题中，我们一般采用___来反映每个人对待风险的态度。

8．目标规划总是求目标函数的___信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的____。

二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。

9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题 【 】

A．有唯一的最优解 B．有无穷多最优解

C．为无界解 D．无可行解

10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 【 】

A．b列元素不小于零 B．检验数都大于零

C．检验数都不小于零 D．检验数都不大于零

11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为 【 】

A．3 B．2

C．1 D．以上三种情况均有可能

12．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【 】

2004年运筹学试题

题目大概：

1、简答3道：中国邮路问题；存贮问题概念；？

2、线性规划（简单）

3、运输问题（简单，一步到位的那种）

4、动态规划（书上例题） （可惜我做错了，20分啊，想起来都心疼）

5、图论：最小截集最大流定理证明（较难）

6、论述：运筹学的应用 2005年运筹学试题

六道大题

1.利用对偶理论和互不松弛理论解一个线性规划问题，单纯形法也应该

可以做，但是过于复杂。

2.矩阵对策问题，悲观主义决策准则，乐观主义决策准则

3.一个建模问题，比较简单

4.一个简单的求最短路问题

5.动态规划问题，很简单

6.非线性规划，类似清华大学出版社出版的《运筹学》第七章例一

总体感觉偏基础原理 2006年运筹学试题

1.不记得了

2.分支定界问题（真正算起来还是比较麻烦的）

3.动态规划问题（书上的原题）

4.最大流最小截定理的证明（这个比较麻烦，貌似以前考过的）

5.运输问题（比较容易）

6.对偶问题的优缺点，写对偶单纯形的算法（麻烦）

7.图论里一笔划问题的证明，是书上的定理连通图是欧拉图的充要条件

的证明。这个比较麻烦，然后还要写一个欧拉圈的找法，写出步骤，这个比较麻烦。

8.还有一个kt条件的题，这个不是最后一题，是中间的一题,很容易～

2007年运筹学试题:

2007年的运筹学试题出题思路与往年不是很一样,在基础题上,多加了一

点难度,还考了两道考试范围之外的题，一共是七大题：

基础题: 难度和书上的例题还有课后题差不多。

1.用单纯形法解线性规划问题：很基础，但有一定的计算量；

2.两维Kt条件问题：感觉同上

偏难的一些题：在基础上更大难度，难度和那本“运筹学习题集”一样。

3.求最短路问题，是“运筹学习题”上的一个原题：不记得是哪道了，书

也没有了。大家可以去找找：已知有几个村，村村之间的距离dij，每个

村的学生数，求找一个村建学校，以解得上学的总路（每个学生走的路

程之和）最小。

4.动态规划问题：我一直没有找到原题，但可以记得是两维的，两种资