运筹学试卷I试题

中国计量学院运筹学试卷

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

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

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

对于如下的线性规划问题

min z = -x1 + 2x2

s.t. 2x1 + 3x2 12 (1) 3x1 + x2 6 (2) -x1 + 3x2 3 (3) x1 0， x2 0

的图解如右图所示。三个约束对应的松弛变量分别为

x3、x4、x5；三个约束条件对应的对偶变量分别

为y1、y2、y3

1、这个问题的可行域为（ ）；

A、（IHFE） B、（EGCA） C、（EAD） D、（ICA） 2、该问题的最优解为（ ）；

A、（G） B、（F） C、（H） D、（C） 3、这个问题的基础解为（ ）；

A、（ABCDEFGH） B、（ABCEFGHIJ） C、（ABCDEFGHIJ） D、（EFHI） 4、这个问题的基础可行解为（ ）；

A、（ICA） B、（EGCA） C、（EAD） D、（IHFE） 5、G点对应的解中，小于零的变量为（ ）； A、（x3） B、（x4） C、（x5） D、（x1） 6、C点对应的解中，小于零的变量为（ ）；

A、（x3，x5） B、（x4，x3） C、（x5, x2） D、（x5, x4） 7、E点对应的基变量为（ ）；

A、（x1 x2 x3） B、（x2 x3 x4） C、（x3 x4 x5） D、（x1 x2 x5） 8、从I到E的单纯形叠代，进基变量为（ ），离基变量为（ ）； A、（x1、x2） B、（x2、x3） C、（x3、x5） D、（x2、x5） 9、F点对应的对偶变量，等于零的是（ ）;

A、（y1、y2） B、（y4、y3） C、（y3、y5） D、（y1 y5）

10、F点对应的对偶变量，大于零的是（ ），小于零的是（ ）。

A、（y3、y2） B、（y1、y2） C、（y4、y5） D、（y2、y5）

单项选择题答题表

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

中国计量学院运筹学试卷

二、判断及改错题，正确打√，错误打×，并将修改建议简写在对应题号下的改错栏。 （共20分，每题2分）

1、 任何线形规划总可用两阶段单纯形法求解。（ ）

2、 若原问题为极小化，当第i个约束是 约束,则对偶变量yi 0。（ ） 3、 整数规划的最优解是先求相应的线形规划的最优解然后取整得到。( ) 4、 系统约束中最多含有一个正或负的偏差变量。（ ）

5、 产地数为3，销地数为4的平衡运输中，变量组｛X11，X13，X22，X33，X34｝可作

为一组基变量。（ ）

6、 割集中弧的容量之和称为割量。（ ）

7、 网络计划中的总工期等于各工序时间之和。（ ）

8、 动态规划中，定义状态时应保证各个阶段中所作的决策相互独立。（ ） 9、 在折衷主义原则中，乐观系数α的确定与决策者对风险的偏好有关。（ ） 10、 在指派问题的效率表的某行乘以一个大于零的数最优解不变。（ ）

三、简答题（共12分，每题3分）

1. 为什么在线性规划问题标准型中通常记约束方程组AM*N（m≤n）的秩为r(Ａ)＝m？（3分）

2. 在普同单纯形法中使用最小比值定理的作用是什么？（3分）

3.什么是影子价格？可以用于哪些经济活动的分析？（3分）

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

中国计量学院运筹学试卷

4.如何理解动态规划问题中的“阶段”的概念？（3分）

四、解下表所示的供需平衡的运输问题（20分）

1、（15分）求出使总的运费最小的最优运输方案以及最小运输费用； 2、（5分）从A1到B1的运价C11=9 在什么范围内变化，以上最优解保持不变？

五.（18分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。

（1）找出所有关键路线及对应的关键工序；（13分） （2）求项目的完工期。（5分）

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

中国计量学院运筹学试卷

六、（10 1、（10分）求以下网络从节点1到节点12的最短路径。

3 4 7

①④ 6 2 1 1 9 8

⑤⑥ 4 8 3

⑨⑩⑿

7 2 4 2、（10分）求以下网络的最大流的流量。 6

7 4 9 6 4

⑧ 3 4 8 5

④

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

中国计量学院运筹学试卷

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

1、A 2、B 3、C 4、D 5、B 6、D 7、B 8、C 9、D 10、A 三、简答题（共12分，每题3分）

1. 为什么在线性规划问题标准型中通常记约束方程组AM*N（m≤n）的秩为r(Ａ)＝m？（3分） 答：Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，

通常设A的秩r（A）= m，且m < n。 即AX=b中所包含的 m个方程式彼此 独立，没有多余方程，且方程个数小于未知量个数。 2. 在普同单纯形法中使用最小比值定理的作用是什么？（3分）

答：在普同单纯形法中，求解出基变量时通常使用最小比值定理，是为了保持原始问题的可

行性不变，即右端的资源向量始终大于等于零。

3. 什么是影子价格？可以用于哪些经济活动的分析？（3分）

答：影子价格(Shadow price)是企业生产过程中一种隐含的潜在价值，经济学中称为影子价

格，即对偶问题中的决策变量yi的值（1分）。正确理解影子价格，利用影子价格作下

列经济活动分析．（1）调节生产规模．例如，目标函数Z表示利润（或产值），当第i种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模．（2）生产要素对产出贡献的分解．通过影子价格分析每种资源获得多少产出．例如，企业获得100万元的利润，生产过程中产品的直接消耗的资源有材料A、材料B、设备和工时，这些资源各产生多少利润，由影子价格可以大致估计出来．（3）由性质2.5知，第i个松弛变量大于零时第i个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解为第i种资源有剩余时再增加该资源量不能给企业带来利润或产值的增加．（ 4）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念．同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样．（5）影子价格是一种边际产出，与bi的基数有关，在最优基B不变的条件下yi不变，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之发生变化．（说对两个以上给2分） 4.如何理解动态规划问题中的“阶段”的概念？（3分）

答：阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数k可以是确定数、不定数或无限数 四、(20分）

（1）（15分）求出使总的运费最小的最优运输方案以及最小运输费用；

中国计量学院运筹学试卷

131422233132 （求出初始解为7分，过程为5分，结果为3分）

（2）（5分）从A1到B1的运价C11 3范围内变化，以上最优解保持不变； 五、（18分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。 解：（1）关键路线及对应的关键工序

11→○12；关键工序：B,E,G关键路线有两条，第一条：①→②→⑤→⑥→⑦→○,H,K,M 11→○12；关键工序：C,F,L,M 第二条：①→④→⑧→⑨→○

（2）项目的完工期为62天。

六、（共10分）以下题目任选一道，多做只给一道题目的分。

1、（共10分） 最短路径为1-2-3-4-8-12，路径为18。（其中最短路步骤为5分，结果为5分） 2、（共10分）

{,5,6,7,8}。

（其中最大流步骤为5分，结果为5分）

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

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