2016年河南理工大学能源科学与工程学院850运筹学(同等学力加试)考研复试题库
● 摘要
一、计算题
1． 己知世界六大城市:P e ，N ，P a ，L ，T ，M 。试在表所示交通网络的数据中确定最小树。
表
【答案】将表用图形的形式表示出来，如图所示。
图
（1）采用避圈法。从图中选取权数最小的边[L，P a ]; 从未选的边中，选取权最小的边[Pe ，T]:依次进行，并使得它们相互不构成圈，直到再也不能选取出边为止。经过五次选边，得到边集合 {[L，P a ]，[Pe ，T]，[M，N]，[L，N]，[Pe ，L]}构成了唯一的最小支撑树，如图所示，此最小支撑树的总权为119。
图
（2）采用破圈法。应用破圈法的原理，依次进行破圈，直到所有边构成的图中不含有圈为止。所得到的结 果与上述避圈法的相同。
2． 下述论断正确与否:可行流f 的流量为零，即v （f ）=0，当且仅当f 是零流。
【答案】论断错误。 流量，只表明发点的净输出量为零，可能流出等于流入，此时，但f 不是零流。
3． 建立数学模型一家汽车制造商有5家过时的工厂，管理层考虑更新这些工厂以生产一种新型轿车的发动机组、变速器和一种主要配件A 。更新每个工厂的成本和更新后的生产能力如表所示:
表
工厂可用于更新的资金为1300万元，工厂3和工厂4位于同一地区，最多只能更新一个工厂，此外，工厂1与工厂5具有相关性，工厂5所需要的某些零件必须由工厂1生产。现计划需要180万个发动机、150万个变速器及200万个配件A ，管理层应决定更新哪些工厂以达到计划生产需要，并使总成本最小。试建立该问题的数学模型。
【答案】设x i =1表示更新工厂i ，x i =0表示不更新工厂i 。根据题意，可建立如下数学模型:
4． 某规划问题
试用0一1变量将上述规划问题描述成一个完整的模型。
【答案】设
则得规划模型
5． 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。
（1）
（2）
【答案】 （1）在第二个约束条件两边同时乘以-1，得到该线性规划问题的系数矩阵
因为P 1、P 2线性无关，故有
令非基变量x 3=x4=0，解得x 1=1，x 2=2，故有基可行解x （1）=（1, 2, 0, 0）T ，z 1=8。
因为P 1、P 3线性无关，故有
令非基变量x 2=x4=0，解得因为P 1、P 4线性无关，故有
令非基变量x 2=x3=0，解得故有基可行解
故不是可行解。 。