运筹学试卷A

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.动态规划问题：我一直没有找到原题，但可以记得是两维的，两种资

《运筹学》-期末考试-试卷A-答案

《运筹学》试题样卷（一）

题号 一 二 三 四 五 六 七 八 九 十 总分

得分

一、判断题（共计10分，每小题1分，对的打√，错的打X）

1. 无孤立点的图一定是连通图。

2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解，

另一个也一定有最优解。

3. 如果一个线性规划问题有可行解，那么它必有最优解。

4．对偶问题的对偶问题一定是原问题。

5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与对应的变量都可以被选作换入变量。

6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷

多个最优解。

7. 度为0的点称为悬挂点。

8. 表上作业法实质上就是求解运输问题的单纯形法。

9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。

10. 任何线性规划问题都存在且有唯一的对偶问题。

① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨

二、建立下面问题的线性规划模型（8分）

某农场有100公顷土地与15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡《运筹学》-期末考试-试卷A-答案

时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工与收入情况如下表所示：

大豆 玉米 麦子

秋冬季需人日数

春夏季需人日数

试卷A 共（4）页 第（1）页

《运筹学》期末考试试卷(A)

学院 班级学号

题号 一 二 三 四 五 六 七 八 九 总分

得分

一、填空题

以下是关于目标函数求最大值的单纯行表的一些结论，请根据所表述的意思判断解的情况：

1.所有的检验数非正，这时的解是。

2.有一个正检验数所对应的列系数均非正，这时线性规划的解。

3.非基变量检验数中有一个为零时，线性规划的解。

4.在两阶段法中，如果第一阶段的最优表中的基变量中有人工变量，则该线性规划。

6.基变量取值为负时的解为。

7.最优表中的非基变量检验数的相反数就是。

8.已知一个线性规划两个最优解是：（3，2），和（5，9），请写出其他解：

9.线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。

10.在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4。 试卷A 共（4）页 第（2）页 11.“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错

12.如果某一整数规划：

MaxZ=X1+X2

X1+9/14X2≤51/14

-2X1+X2≤1/3

X1,X2≥0且均为整数

所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在要对X1进行分枝，应该分为 X1≤1 和 X1≥2 。

13.在用逆向解法求动态规划时，fk(sk)的含义是： 从第k个阶段到第n个阶段的最优解。

14. 假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D和B的关系为 D 包含 B

15. 已知下表是制订生产计划问题的一LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X3,X4,X5为松驰变量。

XB b X1 X2 X3 X4 X5

中国计量学院200 ~~~200 学年第 学期《 运筹学 》课程试卷（ A ）第 1 页 共 6页

中国计量学院200 ~ 200 学年第 学期

《 运筹学 》课程考试试卷（ A ）

开课二级学院： 经管学院 ，考试时间： 年___月__日 时

考试形式：闭卷√、开卷，允许带 计算器、钢笔（圆珠笔）、学生证 入场

考生姓名： 学号： 专业： 班级：

题序 一 二 三 四 五 六 总分

得分

评卷人

一、单项选择题（共20分，每题2分）

1、线性规划问题的可行域的顶点均是（ ）

A、非基础解 B、最优解 C、基础可行解 D、非可行解

2、线性规划的约束条件为 X1 + X2 + X3 = 3 ，2X1+ 2X2+ X4= 4，Xi≥0（i=1-4）,则基本可行解是（ ）

A、（0，0，4， 3） B、（0，0，3，4） C、（2，1，0，-2） D、（3，0，0，-2）

3. 普通单纯形法的最小比值定理的应用是为了保证（ ）

A、使原问题保持可行 B、使对偶问题保持可行

C、逐步消除原问题不可行性 D、逐步消除对偶问题的不可行性

4、原问题与对偶问题都有可行解，则有（ ）

A、原问题有最优解，对偶问题可能没有最优解

B、原问题与对偶问题可能都没有最优解

C、可能一个问题有最优解，另一个问题具有无界解

D、原问题与对偶问题都具有最优解

5、求解整数规划问题的分支定界法中，有（ ）

A、最大值问题的目标值是各分支的上界

B、最大值问题的目标值是各分支的下界

C、最小值问题的目标值是各分支的上界

D、以上结论都不对