天大2000年硕士研究生入学考试试题答案

天津大学研究生院2000年招收硕士生入学试题答案

考试科目：运筹学基础 一、 填空（36%）

1. 线性规划单纯形算法的基本步骤是：（1）（2

，改善解值的。对偶单纯形法每次迭代保持解的 ，改善解值的 。

解：确定一个初始基可行解；检验一个基可行解是否为最优解；寻找一个更好基可行解；可行性；最优性。

2. 设有线性规划问题 min f CX,X R X|AX b,X 0 ，有一可行基B（为A

中的前m列），记相应基变量为X ，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X= ；用非基变量来表示基变量的表达式为XB= ；用非基变量表示目标函数的表达式为f= ，B为最优基的条件是 。

B 1b 1 1 1 1 1解： ,Bb BNXN,CBBb (CN CBBN)XN,CN CBBN 0

0

3. 线性规划（Min型）问题有多重最优解时，其最优单纯形表上的特征为： 解：所有检验数 j 0,而某一个非基变量xk检验数 j 0.

4. 用表上作业法求解m个发点和n个收点的平衡运输问题，其方案表上有数格的个数

为 ，空格的个数为 ；若从检验数为-2的某空格调整，调量为2，则调后可使总运费下降 。 解：m+n-1, (m-1)(n-1), 4.

5. 目标规划模型的特点是引入了（大还是小）化，模型的约束中也含有用这种变量表示的 约束。 解：偏差变量；极小；目标（软）.

6. 某足球队要从1，2，3，4，5号五名队员中挑选若干名上场。令

1第i号上场xi

1，2，3，4，5 0第i号不上场，i＝

请用xi的线性表达式表示下列要求：（1）从1，2，3中至多选2名： （2）

如果2号和3号都上场，则5号不上场： （3）只有4号上场,1号才上场： 解：x1 x2 x3 2,

x4 x5 0,x1 x4 1.

7. 请在下图所示的最短路问题求解过程中进行一步：下一步给 节点标号，标号为 。

[0

第1页下一页