네트워크 問題의 雙對解法에 관한 硏究

Abstract

네트워크 문제는 산업전반에 걸쳐 발생하는 현상으로 여러가지 유형의 문제에 관한 많은 연구가 이루어져 왔다. 최근에 와서는 쌍대구조에 바탕을 둔 쌍대해법에 관한 연구가 활발히 진행되고 있다. 이를 크게 두가지로 나누어 보면, 하나는 원문제를 선형계획문제로 완화하여 쌍대문제로 바꾼 후 쌍대문제의 구조를 이용하여 쌍대향상 방법으로 해를 구하는 방법?隔?,나머지 하나는 네트워크문제의 계약식 일부를 라그란지안 쌍대변수를 이용하여 목적함수식으로 을린 후. 비교적 간단해진 구조를 이용하여 해를 구하는 방법이다. 본 연구에서는 여러가지 형태의 네트워크 문제들을 살펴보고 이들의 해법에 관하여 조사연구하였다.

There are many studies about the network design problems that are applied to numerous areas of industry. Recently dual algorithms that are based on the structure of the dual problem are studied for numerous types of network problem. There are two types of dual algorithms. First. the dual ascent algorithm is based on the dual structure of primal problem, second the Lagrangian relaxation method dualize the complicate constraints with the Lagrangian dual multipliers, and adjust the multipliers with the subgradient method or the dual ascent method .

We studied the numerous types of network problems and the dual algorithms of network problems.

There are many studies about the network design problems that are applied to numerous areas of industry. Recently dual algorithms that are based on the structure of the dual problem are studied for numerous types of network problem. There are two types of dual algorithms. First. the dual ascent algorithm is based on the dual structure of primal problem, second the Lagrangian relaxation method dualize the complicate constraints with the Lagrangian dual multipliers, and adjust the multipliers with the subgradient method or the dual ascent method .

We studied the numerous types of network problems and the dual algorithms of network problems.