关于 P.Gács 和 L.Lovász 的一个引理及其推广

文献[1]对哈奇安算法给出了完整的证明.本文首先指出[1]中引理3的证明过程中存在的问题并重新给出了证明,然后在新结果的基础上作了推广。最后给出一个改进哈奇安算法的实用结果。研究由线性规划问题导出的不等式系统:及其相应的扰动系统:Ax<b+2^(-L),L是Ax≤b的输入长度。A、b分别为m×n和m×1阶整数矩阵。 P. Gacs和L. Lovdsz在[1]中证明了如下结果[1,引理3]。定理1 若系统Ax<b+2^(-L)有解,则系统Ax≤b有解。