2017年杭州电子科技大学管理学院832运筹学考研题库
● 摘要
一、选择题
1． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。
A. 松弛变量 B. 多余变量 C. 闭回路 D. 圈 【答案】C
【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。
2． 网络计划中的某工序（i ，j ），估计的最乐观时间为a ，最可能时间为m ，最保守时间为b ，则该工序的 期望工时和方差可以按下面（ ）计算。
【答案】A
3． 一般卖报童模型的假设条件，不包括以下（ ）。
A. 买入一件物品的成本是固定并已知的 B. 卖出一件物品的收入是固定并己知的
C. 若物品在一个周期中卖不出去，折价收入是固定并己知的 D. 物品的销售数量是己知的 【答案】D
【解析】报童问题为需求是随机离散的存储问题，所以其假设中不可能包括物品的销售数量是己知的。
4． 单纯形法中，关于松弛变量和人工变量，以下说法正确的是（ ）。
A. 在最后的解中，松弛变量必须为0，人工变量不必为0 B. 在最后的解中，松弛变量不必为0，人工变量必须为0 C. 在最后的解中，松弛变量和人工变量都必须为0 D. 在最后的解中，松弛变量和人工变量都不必为0 【答案】B
【解析】松弛变量是在约束不等式号的左端加入的，在最后的解中，其值可以不必为0; 人工变量是在原约束条件为等式的情况下加入的，只有基变量中不再含有非零的人工变量时，原问题才有解，所有最后的解中人工变量必须为0。
二、计算题
5． 用破圈法和避圈法求下列图中各图的最小树。
【答案】（l ）给图（a ）的点和边编号v i 和e j ，如图（al ）所示。
①采用避圈法。首先从图（al ）中选取最小边e l3=1，以后每一步从未选出的边中选出一个边上权最小的边，并使之与前面己选的边不构成圈（若在某一步中，有两条或两条以上的最小权的
，直到不能选出为止。 边时，则从中任选取一条）
于是，以{el3，e 15，e 3，e 9，e 10，e 5，e l7}为边构成的图恰好就是一个支撑树，如图（a2）所示，其权为16。
，从中去掉权最大的边（此处②采用破圈法。在图（al ）中任取一个圈，例如（v 1，v 2，v 3）
，在 余下的图中，重复上述步骤，直到此图不再含圈为止。其具体过程如下: 去掉边e 2=8）
，去掉最大边e 2=8; ①取圈（v l ，v 2，v 3）
，，去掉最大边e l =7; ②取圈（v l ，v 2，v 3，v 4）
，去掉最大边e 8=2; ③取圈（v 2，v 3，v 7）
，去掉最大边e 7=7; ④取圈（v 2，v 4，v 6）
，去掉最大边e 11=3; ⑤取圈（v 3，v 7，v 8）
，去掉最大边e 4=6; ⑥取圈（v l ，v 4，v 5）
，去掉最大边e 12=5; ⑦取圈（v 6，v 7，v 8）
，去掉最大边e 16=4; ⑧取圈（v 2，v 4，v 6，v 8，v 7，v 3）
，去掉最大边e 6=4; ⑨取圈（v l ，v 4，v 5，v 6）
，去掉最大边e l4=6。 ⑩取圈v 5，v 6，v 8）
，这就是一个最小支撑树。
在图（al ）中通过10次破圈后留下来的图仍然还是（a2）
（2）给图（b ）中的顶点和边编号v i 和e j ，如图（bl ）所示。
①采用避圈法。类似于（l ）的避圈法，最后，由边集合{e3，e 2，e 5，e 7，e 9，e 8}构成的子图（见图（b2））是一个最小支撑树，其权为12。
②采用破圈法。与（l ）中的破圈思路相同，通过破去图中e l ，e 4，e 6，e l0和e 1l ; 这五条边以后余下的边集 {e2，e 3，e 5，e 7，e 9，e 8}构成的子图就是原图的一个最小支撑树，此最小支撑图正是
相关内容
相关标签