수송 과학

수송문제

• n개의 출발지에서 n개의 목적지까지 최소한의 비용을 제품을 수송할 수 있는 경로를 찾는 수리적 모형
• 수송비용을 최소화하여 각 origin에서 공급향과 각 destination에서의 수용의 균형을 유지하는 수송전략을 찾는 문제

수송 전략

• origin : 최소한의 수송비용으로 destination으로 제품을 수송하려는 노력
• destination : 최소한의 수송비용으로 origin으로부터 제품을 공급받고자 노력
• 양쪽 모두의 관점, 전체의 관점에서 수송비용을 최소화 시켜야 함
  -> 그렇지 않으면 수요와 공급의 불균형을 초해

P&T company 예제

• 3개의 생산 공장
• 4곳의 분배 창고
• 운송비 절감

데이터 추정

• 각 통조림 공장의 생산량
• 각 창고의 배정량
• 각 공장에서 창고로의 트럭 한대의 운송 비용

• 각 근원지는 고정된 공급향을 가진다( si)
• 각 목적지는 고정된 수요량을 가진다(di)
• 특정 source로부터 특정 destination까지의 운송비용은 운송되는 단위에 비례한다

의사결정 변수

• x ij : 출발지 i에서 목적지 j까지 수송할 제품의 양

목적함수

• C ij Xij : 출발지 i에서 목적지 j까지 발생하는 수송비용
• origin에서 destination까지 모든 pair간 운송량의 총 운송비용
  

제약식

• origin i에서 모든 destination으로 shipping되어서 나가는 양
  

• 이 양은 공급량 Si를 초과할 수 없으므로
  

• detination j의 수요향 D j를 초과할 수 없으므로
  

따라서

선형 계획 모형

• 모든 origin은 갖고 있는 제품 전체를 수송할 수 있음
• 모든 destination은 원하는 수량 전체를 공급받을 수 있음

다음 조건을 만족해야 한다

• 항상 feasible한지,
• 총 수요량 == 총 공급향인 실행가능 필요충분 조건인지 확인
• 정수해 속성 : 수송문제의 모든 기저 가능해는 변수들이 정수값을 가져야 함

조건이 불만족할 경우(수요 공급이 불균형일 경우)

• 가상의 source/destination을 추가한다

할당 문제

• 한 종류의 resource를 다른 종류의 resource에 하나씩 할당
• 피할당인 i 가 과업 j 를 수행하는데 비용 cij 발생
• 총 비용을 최소화 하는 것이 할당 방법

네트워크

• node와 node들을 연결하는 arc들로 이루어진 망 구조
• 방향성이 있는 경우 G = (N, a)
• 방향성이 있는 경우 G = (N, E)

해결해야 하는 문제
어떤 경로를 통해야 출발 노드 -> 도착노드까지

• 가장 빠르고
• 가장 많은 양을
• 가장 적은 비용으로

보낼 수 있는가?

수송 문제

네트워크 모델 중 하나

어떻게 가장 적은 비용으로 운송할 수 있는가?
• 운송은 origin에서 destination으로만
• Origin node 사이, destination node 사이의 운송은 없다.

definition and terminology

tail, heads(directed arc)

degree of a node

• Indegree : incoming arc의 수
• Outdegree : outgoing arc의 수
• Undirected network :
  

walk

• 노드와 아크가 번갈아 나타남
• 노드에서 시작해서 노드에서 끝남

Path

• 노드의 중복이 발생하지 않는 walk

directed path

• 노드의 중복이 발생하지 않는 directed walk
• No backward arc

cycle

• 반복되는 path

Connectivity

• 두개의 노드 i와 j사이의 최소 하나의 path가 존재하면 두 노드는 연결되어 있다고 함
• 모든 서로 다른 두개의 노드들이 모두 connected 되어 있으면 connected 네트워크

tree

• cycle에서 하나의 arc를 지우면 tree가 됨

최단 경로 문제

가중치를 고려하여 최단 경로를 탐색

• 디익스트라 알고리즘이 대표적