서지주요정보
(A) new subgradient algorithm for multicommodity minimal cast network flow problems = 다품목 네트웍 흐름 비용 최소화 문제의 새로운 해법에 대한 연구
서명 / 저자 (A) new subgradient algorithm for multicommodity minimal cast network flow problems = 다품목 네트웍 흐름 비용 최소화 문제의 새로운 해법에 대한 연구 / Hyung-Dae Seo.
발행사항 [서울 : 한국과학기술원, 1986].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

4103963

소장위치/청구기호

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

MMGS 8615

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

This thesis presents a new subgradient algorithm for the multicommodity network flow problems. The primal resource-directive procedure suggested by Kennington and Shalabey is refined. Adopting a circular formulation and using the concept of artificial arc, an primal-dual algorithm with which reoptimization is easy is used for solving the subproblems. For improving the lower bound of the objective value, a Largrangean dual procedure is developed. The new algorithm which is a hybrid of the primal and the dual procedure is coded with PASCAL, and some computational experiments are performed.

본 논문은 다품목 네트웍 흐름 비용 최소화 문제( MMCNF : Multicommodity Minimal Cost Network Flow problem) 의 새로운 해법에 관한 연구이다. 본 연구의 contribution은 다음과 같다. 1. Kennington 과 Shalabey는 MMCNF 문제에 적용된 Resource-Direvtive Decomposition의 주문제를 풀기 위한 subgradient algorithm을 제시 하였는데, 본 연구에서는 이 문제에 대한 circular formulation의 적용과 artificial arc의 개념을 이용하여 subproblem의 해법으로 Primal-Dual algorithm이 쓰일 수 있게 하였다. 2. 대부분의 계산이 부문제인 single commodity problem 을 푸는 과정에서 이루어 진다. Bertekas 가 최근에 제시한 Framework 에 기초하여 부문제를 풀기위해 reoptimization 이 쉬운 Primal-Dual algorithm 을 개발하였다. 3. 보다 나은 lower bound를 얻기 위해, Lagrangean Dual procedure가 개발되었다. 최적 목적함수값에 가까운 lower bound 는 algorithm의 실제적인 이용을 위해 필수적이다. primal procedure 와 dual procedure 를 결합함으로써, Subgrdient method의 장점인 비교적 적은 memory requirement와 계산 속도면에서의 효율성을 갖는 algorithm 을 개발하였다.

서지기타정보

서지기타정보
청구기호 {MMGS 8615
형태사항 [iii], 45 p. ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 서형대
지도교수의 영문표기 : Dong-Wan Tcha
지도교수의 한글표기 : 차동완
학위논문 학위논문(석사) - 한국과학기술원 : 경영과학과,
서지주기 Reference : p. 42-45
주제 Network analysis (Planning)
Mathematical optimization.
Lagrange 승수법. --과학기술용어시소러스
네트워크. --과학기술용어시소러스
최적화 문제. --과학기술용어시소러스
Lagrangian functions.
QR CODE qr code