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

一、计算题

1． 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如表所示。设司机和乘务人员分别在各时间区段一开始时上班，并连续工作8h ，问该公交线路至少需配备多少名司机和乘务人员。列出这个问题的线性规划模型。

表

【答案】设x i （i=1，2，…，6）为从第i 班次开始上班的司机和乘务员的人数，则可建立数学模型为:

2． 利用库恩一塔克条件求解以下问题:

（l ）试写出库恩一塔克条件。

（2）a 满足什么条件以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（l ）所求问题变形为

故库恩一塔克条件为

（2）由约束条件可知，（3）

时，存在最优解

时，时，解得

由且

目标函数值

目标函数值为

，故

其余情况均不符合 故当当

时，最优解为

时，最优解为

3． 用Gomory 切割法解以下问题。

【答案】（1）在该线性规划问题的约束条件中分别加入松弛变量x 3，x 4，化为标准型

先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。

表

此时的最优解为最优目标值。

由表中最终单纯形表可得变量间的关系式：

将系数和常数项都分解成整数和非负数真分数之和，移项，则以上两式变为

要求x 1，x 2，x 3，x 4为非负整数，从上述两式看来，等式左边是整数，等式右边括号内是正数，所以等式右边必须是负数，则上述第二个等式的右端可由下式代替：

即

加入松弛变量x 5，即得到切割方程:

表

将该约束条件加入到上表的最终单纯形表中，并进行进一步求解，如下表所示。