network modeling 의 정의와 활용방법

 

 

정의

 

네트워크(network) 형태의 그래프로 표현한

여러 비즈니스 문제들을 의미합니다.

대표적으로 아래와 같은 문제들을 다룹니다.

• Transshipment Problems (중계 운송 문제)
  여러 중간 지점을 거쳐 물자나 상품을 운송하는 최적 경로와 비용을 찾는 문제.
• Shortest Path Problems (최단 경로 문제)
  한 지점에서 다른 지점까지 이동할 때 가장 짧은(또는 가장 비용이 적은) 경로를 찾는 문제.
• Maximal Flow Problems (최대 유량 문제)
  네트워크를 통해 한 지점에서 다른 지점으로 보낼 수 있는 **최대 흐름량(예: 물, 데이터, 자원 등)**을 구하는 문제.
• Transportation / Assignment Problems (수송 및 할당 문제)
  생산지에서 소비지로 물자를 가장 효율적으로 보내거나, 사람이나 작업을 가장 효율적으로 배치하는 문제.
• Generalized Network Flow Problems (일반화된 네트워크 흐름 문제)
  각 경로에서 흐름이 손실되거나 증폭될 수 있는 상황까지 포함하는, 보다 복잡한 네트워크 흐름 문제.
• The Minimum Spanning Tree Problem (최소 신장 트리 문제)
  모든 지점을 연결하면서 전체 연결 비용의 합이 최소가 되도록 하는 네트워크 구조를 찾는 문제.

 

원칙 및 계산법

 

1) 화살표(arc) 와 원(nod)으로 표현됩니다.

2) 노드에는 고유의 번호가 매겨집니다.

3) 보통 아크는 변수, 노드는 제약식이 됩니다.

(모든 노드는 제약식, 모든 아크는 변수로)

만약 노드와 제약식이 맞지 않으면

추가로 파이트를 연결하기도 합니다.

 

예를 들어 이런 모델이 있는 경우

7개의 노드(원) 각각이 제약식이 되고

노드 사이의 화살표(아크) 들이 변수가 됩니다.

 

최소를 구하는 값이 목적식인 경우는

아래와 같이 표시됩니다.

 

목적식(MIN)

30 x12 + 40 x14 + 50 x23 + 35 x35

+ 40 x53 + 30 x54 + 35 x56 + 25 x65

+ 50 x74 + 45 x75 + 50 x76

 

제약식

-x12 -x14 >= -200

x12-x2 >= 100

x23 + x53 - x35 >=60

x14 + x54 + x74 >=80

x35 + x65 + x75 - x53 -x54 -x56 >= 170

x56 +x76 - x65 >= 70

-x74 -x75 -x76 >= -300

 

 

실전 활용 (엑셀)

 

예시 : 컴퓨터 훈련 소프트웨어

• 회사에서는 컴퓨터를 최소 2년에 한 번씩 교체한다.
• 현재 두 가지 임대(리스) 계약이 검토되고 있다.
• 공통 사항으로 그 계약 모두 초기비용은 $62,000이다.

🔹 계약 1 (Contract 1)

• 가격은 매년 6%씩 상승한다.
• 1년 된 장비는 60%의 보상판매(trade-in) 가치가 있다.
• 2년 된 장비는 15%의 보상판매 가치가 있다.

🔹 계약 2 (Contract 2)

• 가격은 매년 2%씩 상승한다.
• 1년 된 장비는 30%의 보상판매 가치가 있다.
• 2년 된 장비는 10%의 보상판매 가치가 있다.

.

 

이를 네트워크로 표현하면 위와 같습니다.

 

이를 엑셀로 표현하면 위와 같습니다.

 

- 덧 -

 

변수(arc)가 부족하여 노드 숫자만큼 제약식이 나오지 않으면

가상의 arc를 추가하여 풀기도 합니다.

대표적으로 최대(최소)수송량 문제가 있습니다. 

 

상황에 따라서는 가격이나 비율 단일이 아닌

가격과 비율 두 변수를 활용하는 문제도 있으나

다른 문제와 동일한 방식으로 풀어 주시면 됩니다.

 

이상으로

network modeling 의 정의와 활용방법

포스팅을 마칩니다.