線型計劃法에 대한 Khachiyan 方法의 응용연구

Abstract

L.G. Khachiyan's algorithm for solving a system of strict (or open) linear inequalities with integral coefficients is described. This algorithm is based on the construction of a sequence of ellipsoids in Rn of decreasing n-dimensional volume and containing feasible region. The running time of the algorithm is polynoinial in the number of bits of computer core memory required to store the coefficients. It can be applied to solve linear programming problems in polynomially bounded time by the duality theorem of the linear programming problem. But it is difficult to use in solving practical problems. Because it requires the computation of a square roots, besides other arithmetic operations, it is impossible to do these computations exactly with absolute precision.