서지주요정보
(A) lagrangian heuristic method for a multifacility capacity expansion model with conversion = 설비 전환이 있는 복수설비의 확장문제에 관한 발견적 해법
서명 / 저자 (A) lagrangian heuristic method for a multifacility capacity expansion model with conversion = 설비 전환이 있는 복수설비의 확장문제에 관한 발견적 해법 / Chul Kim.
발행사항 [서울 : 한국과학기술원, 1986].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

4103957

소장위치/청구기호

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

MMGS 8608

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

This thesis describes a multifacility capacity expansion model with conversion. Each facility type is used to satisfy a variety of deterministic demand over a finite number of discrete time periods. An example of the model is the cable sizing problem associated with the planning of communication network. Since the problem is NP-complete, it is time consumptive to find an exact optimum solution using ordinary mixed integer programming algorithm. We decompose the problem with respect to each facility, using the special Lagrangian relaxation technique of introducing integrated variables. The integrated variable is defined as the sum of independent variables. For each facility, the decomposed problem is solved by a dynamic programming method. We develop a heuristic method of constructing a good feasible solution from the solution of relaxed problems. Computational results show that the average tolerance is 2.66%. Compared with the average tolerances of other problems, it is reasonable. And we successfully solve the realistic problems with large-sizes within reasonable computation times.

본 논문은 설비전환이 있는 복수설비의 확장문제를 다룬다. 설비전환은 한 설비의 용량을 다른 설비의 수요를 충족시키기 위하여 사용하는 것을 의미한다. 이러한 문제의 응용은 전선의 크기를 정하는 문제에서 볼 수 있다. 제안된 모형은 NP-Complete하여 최적해를 구하는 것은 시간이 오래 걸린다. 본 논문에서는 결합변수 (integrated variable) 를 도입하여 문제를 완화 (relax) 시켜서 푼다. 완화된 문제는 설비별로 부문제 (subproblem) 로 나누어지고 부문제는 동적 계획법을 이용하여 해를 구한다. 완화된 문제를 푼 해를 이용하여 좋은 가능해를 만드는 것은 발견적 해법 (heuristic method) 를 이용하여 해결한다. 예제를 통해 본 가능해와 계산시간은 본 논문의 해법이 효율적이라는 것을 보여 준다.

서지기타정보

서지기타정보
청구기호 {MMGS 8608
형태사항 [iii], 42 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 김철
지도교수의 영문표기 : Se-Hun Kim
지도교수의 한글표기 : 김세훈
학위논문 학위논문(석사) - 한국과학기술원 : 경영과학과,
서지주기 Reference : p. 38-42
주제 Heuristic.
Industrial capacity.
Algorithms.
설비 계획. --과학기술용어시소러스
최적화 문제. --과학기술용어시소러스
알고리즘. --과학기술용어시소러스
Lagrangian functions.
QR CODE qr code