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

一、填空题

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

【答案】G 是连通图

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

3． 当极大化线性规划模型达到最优时。某非基变量x j 的检验数为马. 当价格系数为c j 的变化量为△c j 时，原 线性规划问题最优解保持不变的条件是_____。 【答案】

，极大化 2． 图G=（V ，E ）有生成树的充分必要条件是___。 【解析】x j 为非基变量，其价格系数变化△c j 后，其检验数变为

条件的右端常数项的对偶价格为:_____。

【答案】-12 4． 某极小化线性规划问题的对偶问题的最优解的第1个分量为y l =-12，则该问题的第1个约束

【解析】由对偶问题的经济解释可知，原问题约束条件的右端常数项的对偶价格等于对偶问题的最优解中相 应的分量的值。

二、计算题

5． 某工厂的100台机器，拟分四个周期使用，在每一周期有两种生产任务。据经验，把x 1台机器投入第一种生产任务，则在一个生产周期中将有x 1/3台机器报废; 余下的机器全部投入第二种生产任务，则有1/10机器报废，如果于第一种生产任务每台机器可收益10，于第二种生产任务每台机器可收益7，问怎样分配机器，使总收入最大?

【答案】按周期将该问题划分为四个阶段，第k 阶段为第k 周期分配机器; 状态变量

周期初的完好机器数:决策变量表示第k 个周期用于第一种任务的机器台数，

第 2 页，共 46 页 表示第k 表示第k

周期用于第二种任务的机器台数;

状态转移方程为:

; 阶段指标

务的总收益，

大值。于是有递推关系：

其中k=3, 2, 1；f 5（s 5）=0。

，最优解为

，最优解为

，最优解为

因为s 1=100，所以最大总收益

反推出最优策略为:第1周期100台机器全部用于第二种生产任务; 第2周期90台机器全部用于第二种生 产任务; 第3周期81台机器全部用于第一种生产任务; 第4周期54台机器全部用于第一种生产任务。

6． 开发公司拟为一企业承包新产品的研制与开发任务，但为得到合同必须参加投标。己知投标的准备费用 为4万元，能得到合同的可能性是40%。如果得不到合同，准备费用得不到补偿。如果得到合同，可采用两种 方法进行研制开发:方法1成功的可能性为80%，费用为26万元; 方法2成功的可能性为50%，费用为16万元。如果研制开发成功，按合同开发公司可得到60万元，如果得到合同但未研制开发成功，则开发公司许赔偿 10万元。问题是:

（1）是否参加投标?

第 3 页，共 46 页 表示第k 个周期台机器用于第一种任务， 台机器用于第二种任最优值函数f k （s k ）表示第k 周期初完好机器台数为s k 时，从第k 周期至第4个周期的总收益最

，最优解为

（2）若中标了，采用哪种方法研制开发?

【答案】D 点处的值为:

E 点处的值为:

由于

B 点处的值为:

又因

望收益为40000元。

, 故在A 点处的决策为选择投标。 , 故在C 点处的决策为方法l 计算结果表明该开发公司首先应该参加投标，在中标的条件下应采用方法1进行开发研制，总期

图

7． 用破圈法和避圈法求下列图中各图的最小树。

【答案】（l ）给图10一4（a ）的点和边编号v i 和e j ，如图（al ）所示。

第 4 页，共 46 页