Network model (operations research) — 네트워크 모델

From Systems analysis Wiki
Jump to navigation Jump to search

네트워크 모델 (운용 과학 분야; 영어: Network models) — 문제를 그래프(네트워크) 형태로 표현하는 수학적 모델의 한 범주로, 꼭짓점(노드)은 객체 또는 상태를 나타내고 간선(호)은 그들 사이의 관계 또는 과정을 나타낸다[1]. 최적화의 맥락에서 네트워크는 흔히 방향 그래프를 의미하며, 운용 분석에서는 이를 직접 '네트워크'라 부른다. 이러한 네트워크의 꼭짓점은 노드라 하고, 간선은 호(arc)라 한다[2].

네트워크 모델은 물류, 통신, 프로젝트 관리, 금융 등의 분야에서 복잡한 시스템을 분석하고 최적화하는 강력한 도구이다. 그 강점은 높은 수준의 추상화에 있다. 노드는 도시, 컴퓨터 라우터 또는 프로젝트의 단계를 나타낼 수 있으며, 호는 도로, 통신 채널 또는 기술적 작업을 나타낼 수 있다.

정의 및 용어

네트워크 모델의 기반은 그래프 이론이다. 핵심 개념은 다음과 같다:

  • 흐름 네트워크 (영어: flow network): 각 간선에 용량 (capacity)과 흐름 (flow)이 부여된 방향 그래프. 그래프에는 두 개의 특수한 꼭짓점이 존재한다. 흐름이 발생하는 소스 (source)와 흐름이 유입되는 싱크 (sink)가 그것이다[1].
  • 흐름 보존 법칙: 소스 또는 싱크가 아닌 임의의 꼭짓점에서, 총 유입 흐름은 총 유출 흐름과 같아야 한다. 이 조건은 물리적 보존 법칙의 이산적 유사체이다[3].
  • 네트워크 계획법: 프로젝트를 상호 연관된 작업(호)과 사건(노드)의 집합으로 표현하는 모델. 이러한 네트워크는 방향 비순환 그래프(DAG)이며, 이는 작업의 수행 순서를 반영한다[4].

주요 속성 및 정리

네트워크 모델은 고효율 알고리즘의 적용을 가능하게 하는 여러 특수한 속성을 지닌다.

  • 해의 정수성: 많은 네트워크 최적화 문제(예: 최대 흐름 문제 또는 최단 경로 문제)는 제약 행렬의 완전 유니모듈러 성질을 갖는다. 이 덕분에 문제의 매개변수(용량, 길이)가 정수인 경우, 선형 계획법으로 구한 최적해는 추가적인 정수 제약 없이도 정수해가 된다[5][6].
  • 최대 흐름-최소 컷 정리: 흐름 이론의 핵심 결과. 소스에서 싱크로의 최대 흐름 값은 소스와 싱크를 분리하는 모든 컷 중 최소 용량과 같다고 주장한다. 이 정리는 흐름의 최적성 기준을 확립하며 많은 알고리즘의 기반이 된다[6][7].
  • 최단 경로에 대한 최적성 원리: A에서 C로의 경로가 최단 경로라면, 그 경로의 임의의 부분(예: 중간 지점 B에서 C까지)도 해당 꼭짓점들 사이의 최단 경로이다. 동적 계획법의 기반이 되는 이 속성은 다익스트라 알고리즘과 같은 알고리즘의 정확성을 보장한다[8].
  • 최소 신장 트리(MST)의 속성:
  • 컷 속성: 그래프의 임의의 컷에 대해, 컷을 가로지르는 최소 가중치 간선은 적어도 하나의 MST에 속한다.
  • 사이클 속성: 그래프의 임의의 사이클에서, 최대 가중치 간선은 어떤 MST에도 속하지 않는다.

이러한 속성에 기반하여 프림 알고리즘과 크루스칼 알고리즘의 정확성이 성립한다[9].

네트워크 최적화의 주요 문제

  • 최단 경로 문제: 두 개의 주어진 노드 사이에서 총 길이(가중치)가 최소인 경로를 구한다. 다익스트라 알고리즘(비음수 가중치의 경우) 또는 벨만-포드 알고리즘(임의의 가중치의 경우)으로 해결된다[8].
  • 최대 흐름 문제: 주어진 호의 용량 하에서 소스에서 싱크로의 최대 가능 흐름을 결정한다. 대표적인 해결 방법은 포드-풀커슨 알고리즘이다[6].
  • 최소 신장 트리 문제: 네트워크의 모든 꼭짓점을 연결하면서 간선의 총 비용이 최소인 부분 그래프를 구한다.
  • 주공정법 (CPM): 네트워크 계획 모델에서, 전체 프로젝트의 최소 완료 시간을 결정하는 가장 긴 작업 순서를 구한다. 이 경로상의 작업들은 여유 시간이 0이다[10].

예시

  • 최단 경로: 도시 지도에서 두 지점 사이의 최적 경로를 내비게이션 시스템이 탐색하는 경우. 도시는 노드, 도로는 거리 또는 이동 시간을 가중치로 갖는 호이다.
  • 최대 흐름: 파이프라인 네트워크의 최대 처리 용량을 결정하는 경우. 펌프 스테이션은 노드, 파이프는 제한된 용량을 가진 호이다.
  • 최소 신장 트리: 여러 도시를 최소 총 케이블 길이로 연결하기 위한 통신 네트워크(예: 광섬유 케이블 포설) 설계.
  • 주공정: 주택 건설 프로젝트에서, 작업(기초 공사, 벽 시공, 지붕 설치)이 정해진 기간과 기술적 선후 관계를 가질 때, 주공정은 최소 완공 기간을 결정한다. 이 경로상의 임의의 작업이 지연되면 전체 프로젝트가 지연된다[10].

같이 보기

  • 운용 과학
  • 그래프 이론
  • 수송 문제
  • 주공정법
  • PERT

각주

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
  3. ↑ "Транспортная сеть". Википедия. [3]
  4. ↑ "Сетевое планирование". Википедия. [4]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]
Retrieved from "https://systems-analysis.info/int/index.php?title=Network_model_(operations_research)_—_네트워크_모델&oldid=4873"