当前位置：问答库＞考研试题

一、填空题

1． 现有m 个约束条件，若某模型要求在这m 个条件中取”个条件作为约束，用，1变量来实现 该问题的约束条件组为:_____。

【答案】

【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:

。

2． 图G=（V ，E ）有生成树的充分必要条件是_____。

【答案】G 是连通图

【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。

3． 网络中如果树的节点个数为z ，则边的个数为_____。

【答案】z-l

【解析】由树的性质可知，树的边数=数的节点数-1

4． 在用对偶单纯形法求解某线性规划问题时, 当进基变量x i 确定后，出基变量的选取原则是:_____。

【答案】

二、计算题

5． 已知运价表如表所示:

表

求解总运费最小的最优解（注:求解方法不限，要求写出必要的计算过程）。

【答案】此问题是一个产销不平衡的运输问题，首先增加一个假想的产地戊，其产量为30，运价为0，化为产销平衡问题如表所示:

表

采用伏格尔法，求得初始解如下:

表

采用位势法检验，得下表:

表

表中还有负检验数，说明未得最优解，用闭回路法进行改进，如表所示:

表

确定调入量θ=min（50，20，30）=20。按闭回路上的正负号，加入和减去20，得到调整方案，如表所示:

表

对上表结果在采用位势法求各空格的检验数，如表所示:

表

此时所有检验数都非负，即达到最优，最小运费为:

40×2+30×2+20×4+60×3+30×5=580

6． 某厂准备将具有下列成分的几种现成合金混合起来，成为一种含铅30%，含锌20%，含锡50%的新合金。有关数据见表。

表

应如何混合这些合金，使得既满足新合金的要求又花费最小? 试建立此问题的线性规划模型。