線型計劃法에 대한 Khachiyan 方法의 응용연구
The Application of Khachiyan's Algorithm for Linear Programming: State of the Art

Cited 0 time in webofscience Cited 0 time in scopus
강석호; 박하영
Issue Date
한국경영과학회 = The Korean Operations Research and Management Science Society
한국OR학회지, 제6권, 제1호(1981), pp. 65-70
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.
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.