运筹学试卷I试题.doc
《运筹学试卷I试题.doc》由会员分享，可在线阅读，更多相关《运筹学试卷I试题.doc（6页珍藏版）》请在冰点文库上搜索。
装
订
线
中国计量学院200~200学年第一学期
《运筹学》课程考试试卷（I）
F
X2
X1
J
I
H
E
G
C
D
B
A
-3-2-10123456
6
5
4
3
2
1
一、选择题（20分，每题2分）
对于如下的线性规划问题
minz=-x1+2x2
s.t.2x1+3x212
（1）
3x1+x26
（2）
-x1+3x23（3）
x10，x20
x1
的图解如右图所示。
三个约束对应的松弛变量分别为
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、（x1x2x3）B、（x2x3x4）C、（x3x4x5）D、（x1x2x5）
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、（y1y5）
10、F点对应的对偶变量，大于零的是（），小于零的是（）。
A、（y3、y2）B、（y1、y2）C、（y4、y5）D、（y2、y5）
单项选择题答题表
二、判断及改错题，正确打√，错误打×，并将修改建议简写在对应题号下的改错栏。
（共20分，每题2分）
1、任何线形规划总可用两阶段单纯形法求解。
（）
2、若原问题为极小化，当第i个约束是约束,则对偶变量yi0。
（）
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分）
4.如何理解动态规划问题中的“阶段”的概念？
（3分）
四、解下表所示的供需平衡的运输问题（20分）
运价（元/吨）
B1
B2
B3
B4
供应量（吨）
A1
9
12
10
8
240
A2
14
7
6
11
80
A3
5
13
15
20
180
需求量（吨）
90
120
130
160
1、（15分）求出使总的运费最小的最优运输方案以及最小运输费用；
2、（5分）从A1到B1的运价C11=9在什么范围内变化，以上最优解保持不变？
装
订
线
五.（18分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。
（1）找出所有关键路线及对应的关键工序；（13分）
（2）求项目的完工期。
（5分）
六、（10分）以下题目任选一道，多做只给一道题目的分。
1、（10分）求以下网络从节点1到节点12的最短路径。
347
①②③④
6251
198
⑤⑥⑦⑧
4863
⑨⑩⑾⑿
724
2、（10分）求以下网络的最大流的流量。
6
②⑤
74310
964
①③⑥⑧
31
485
④⑦
一、选择题（20分，每题2分）
1、A2、B3、C4、D5、B6、D7、B8、C9、D10、A
题号
1
2
3
4
5
6
7
8
9
10
答案
√
×
×
√
×
√
×
√
√
×
改错
对偶变量yi0
取整后不一定是原问题的最优解
变量应为6个
等于关键工序时间之和
最优解变化
三、简答题（共12分，每题3分）
1.为什么在线性规划问题标准型中通常记约束方程组AM*N（m≤n）的秩为r（Ａ）＝m？
（3分）
答：
Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，通常设A的秩r（A）=m，且m即AX=b中所包含的m个方程式彼此独立，没有多余方程，且方程个数小于未知量个数。
2.在普同单纯形法中使用最小比值定理的作用是什么？
（3分）
答：
在普同单纯形法中，求解出基变量时通常使用最小比值定理，是为了保持原始问题的可行性不变，即右端的资源向量始终大于等于零。
3.什么是影子价格？
可以用于哪些经济活动的分析？
（3分）
答：
影子价格（Shadowprice）是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量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分）求出使总的运费最小的最优运输方案以及最小运输费用；
运价（元/吨）
B1
3
B2
11
B3
10
B4
8
供应量（吨）
A1
0
6
9
1
12
[80]
10
[160]
8
240
A2
-4
5
14
[30]
7
[50]
6
7
11
80
A3
2
[90]
5
[90]
13
3
15
10
20
180
需求量（吨）
90
120
130
160
最优解为：
X13=80X14=160X22=30X23=50X31=90X32=90minz=4210
（求出初始解为7分，过程为5分，结果为3分）
（2）（5分）从A1到B1的运价C113范围内变化，以上最优解保持不变；
五、（18分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。
解：
（1）关键路线及对应的关键工序
关键路线有两条，第一条：
①→②→⑤→⑥→⑦→→；关键工序：
B,E,G,H,K,M
第二条：
①→④→⑧→⑨→→；关键工序：
C,F,L,M
（2）项目的完工期为62天。
六、（共10分）以下题目任选一道，多做只给一道题目的分。
1、（共10分）最短路径为1-2-3-4-8-12，路径为18。
（其中最短路步骤为5分，结果为5分）
2、（共10分）
[6]6
②⑤
[7]74[1][3]310[9]
6[6]
①[7]9③⑥[4]4⑧
3[2][1]1
[4]48[6]5[5]
④⑦
最大流流量为18，最小割集容量为18，割集为x{1,2,3,4},x～{,5,6,7,8}。
（其中最大流步骤为5分，结果为5分）
中国计量学院200~~~200学年第学期《运筹学》课程试卷（I）第6页共6页
升级会员 