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

一、计算题

1． 已知线性规划问题，

写出其对偶问题，且当其最优解为X=（-5, 0, -1）时，求k 值; 【答案】对偶问题是:

当其最优解为x=（-5，0，-1）时，则约束2应该是取等号的。即: -xl +x2-kx 3=6，将X=（-5，0，-1）代入，得k=1

2． 设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目的地，其间的运输成本如图中所标的数字，试求运费最低的路线。

图

【答案】设阶段变量k=1，2，3，4，依次表示4个阶段选择路线的过程; 状态变量s k 表示第k 阶段初可能处的位置; 决策变量x k 表示第k 阶段初可能选择的路线; 最优值函数第k 阶段点s k 开始至终点E 的最少运费， 则有

表示从

同理，

由此，可得出三条最优的运输路线:

3． 已知世界六大城市: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）采用破圈法。应用破圈法的原理，依次进行破圈，直到所有边构成的图中不含有圈为止。所得到的结 果与上述避圈法的相同。

4． 线性规划问题

当t l =t2=0时，该问题的最优单纯型表如表所示。

表

（l ）确定所有参数，并写出该线性规划问题; （2）当t 2=0时，分析使最优解不变的t 1的变化范围; （3）当t 1=0时，分析使最优基不变的t 2的变化范围。

【答案】（l ）由最优单纯型表得出，x l 和x 3为基变量x B ，则对应初始单纯形表中为:

由最优单纯型表得到由由由由

，得, 得

, 得, 得

, 所以, 求得, 解得, 解得

，即

,

综上，当t l =t2=0时，线性规划为