서지주요정보
(A) new lower bound updating scheme in karmarkar's algorithm = Karmarkar 알고리즘에서의 새로운 하한개선 기법에 관한 연구
서명 / 저자 (A) new lower bound updating scheme in karmarkar's algorithm = Karmarkar 알고리즘에서의 새로운 하한개선 기법에 관한 연구 / Hang Cho.
저자명 Cho, Hang ; 조항
발행사항 [대전 : 한국과학기술원, 1991].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8001891

소장위치/청구기호

학술문화관(문화관) 보존서고

MMGS 9124

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Karmarkar's algorithm is known to have some practical deficiency in spite of its polynomial complexity. It requires prior knowledge of the exact optimal value and it does not generate the optimal dual solutions. Ye and Kojima developed a standard form variant of Karmarkar's algorithm that generates a dual solution through successive lower bound updating scheme of the unknown optimal objective value. In this thesis, to improve the algorithm of Ye and Kojima further, Karmarkar's algorithm is joined with the ellipsoid method using dualcontaining ellipsoid. A dual-containing ellipsoid contains all of the optimal dual solutions, and this ellipsoid shrinks at a fixed ratio. Our method, then finds dual feasible solutions contained in this ellipsoid and uses them to generate a new lower bound of the optimal objective value. This boudn is utilized in the Ye and Kojima's scheme to improve its computational efficiency. Our method has been tested on 12 example problems. We observed that the number of iterations has been reduced significantly in all test problems. However, the total CPU times did not reduced due to the additional computational times required in the process of obtaining a dual feasible solution.

Karmarkar 알고리즘은 polynomial complexity 에도 불구하고 약간의 실제적 문제가 있는 것으로 알려져 있다. 즉, 사전적으로 최적해가 알려져 있어야 하며 쌍대최적해를 구하지 못한다는 것이다. Ye 와 Kojima 는 최적해를 모르는 경우 하한을 계속적으로 개선해가며 쌍대값을 구해내는 기법을 개발하였다. 이 논문에서는 Ye 와 Kojima 의 방법을 개선하기 위해 Karmarkar 알고리즘과 ellipsoid 방법을 쌍대포함타원체 (dual-containing ellipsoid) 를 사용하여 이론적으로 연계하였다. 이 쌍대포함타원체는 쌍대최적해를 모두 포함하고 있으며 일정한 비율로 체적이 줄어든다는 것이 알려져 있다. 그래서, 우리는 쌍대포함타원체 안에 있으면서 쌍대실행가능한 해 (dual feasible solutions) 를 구해서 새로운 하한을 구해내고, 계산상의 효율성을 제고하기 위해 Ye와 Kojima 의 방법에 이 하한을 사용하였다. 이 기법을 12개의 문제에 적용해 본 결과 모든 문제에서 계산횟수 (iteration) 가 현저하게 줄어드는 것을 관찰하였다. 그러나, 쌍대실행가능해를 구하는 과정에서의 부가적인 계산량 때문에 전체적인 계산시간은 줄어들지 않았다.

서지기타정보

서지기타정보
청구기호 {MMGS 9124
형태사항 [ii], 44 p. ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 조항
지도교수의 영문표기 : Se-Hun Kim
지도교수의 한글표기 : 김세헌
학위논문 학위논문(석사) - 한국과학기술원 : 경영과학과,
서지주기 Reference : p. 40-44
주제 Ellipsoid.
Algorithm.
수리 계획법. --과학기술용어시소러스
하한. --과학기술용어시소러스
알고리즘. --과학기술용어시소러스
Mathematical optimization.
QR CODE qr code