2017年成都理工大学管理运筹学(同等学力加试)复试仿真模拟三套题
● 摘要
一、简答题
1． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
2． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;
第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。
二、计算题
3． 用破圈法和避圈法求下列图中各图的最小树。
【答案】（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}构成的子图就是原图的一个最小支撑树，此最小支撑图正是先前的图（b2）。
（3）给图（c ）中的顶点和边编号v i 和e j ，如图（cl ）所示。
①采用避圈法。按照图中的边的权的大小，依次从小到大逐步选取边，并使之不构成圈，直到不能选取时， 经过九次选取后，得到的边集合{e1，e 2，e 5，e 6，e 8，e 9，e 10，e 11，e 15}构成的图即为图c 的一个最小支撑树，如图（c2）所示，此支撑树的权为19。
②采用破圈法。应用破圈原理，经过七次破圈，去掉了权数较大的七条边:e 3，e 4，e 13，e 9，e 14，e 12和e 16。而余下的边集合{e1，e 2，e 5，e 6，e 7，e 8，e 10，e 11，e 15}构成了一个无圈的图即为图4（c ）的另一个最小支撑树，如图（c3）所示。此支撑树的权仍然为19，这说明，图（c ）的最小支撑树不惟一，但其总权均为19。