2016年河海大学商学院702,运筹学(同等学力加试)复试笔试仿真模拟题
● 摘要
一、计算题
1． 给一个连通的赋权图G ，类似于求G 的最小支撑树的Kruskal 方法，给出一个求G 的最大支撑树的方法。
【答案】类似于避圈法。
第一步选一条最大权边，之后每步均从未被选取的边中选最大权边，加入到树的边的集合中，并要求不能与 已选取的边构成圈（若在某步中存在两条及以上的边都是最大权边，则从中任选一条）。
2． 某电视机厂为生产电视机而需生产喇叭，生产以万只为单位，据以往记录，一年的四个季度需要喇叭分别为3万只，2万只，3万只，2万只。设每万只存放在仓库内一个季度的存储费为0.2万元，每生产一批的装配费为2万元，每万只的生产成本费为1万元，问应该怎样安排四个季度的生产，才能使总的费用最小。
【答案】生产成本函数与库存费用函数分别为:
用再生产点解此问题。
（2）
或3
所以，最小总费用为14.8万元，最优生产决策为: ①当②当
时，时，由
得m=2，则
3． 用破圈法和避圈法求下列图中各图的最小树。
【答案】（l ）给图10一4（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 ）所示。
相关内容
相关标签