수송 문제 - 실험 도서관

수송 문제는 선형계획법에서 자주 다루는 특수한 문제 중 하나로, 상품을 여러 공급지에서 여러 수요지로 어떻게 배분할지 결정하는 문제이다. 이는 주어진 자원과 제한된 수송 비용을 최소화하면서 효율적인 배분 방안을 찾는 것이 핵심 목표이다. 수송 문제는 다음과 같은 수학적 모델로 정의할 수 있다.

문제 정의

수송 문제는 다음과 같은 변수들을 포함한다.

$m$ : 공급지의 수
$n$ : 수요지의 수
$a_i$ : 공급지 $i$ 에서 공급할 수 있는 최대량 (즉, 공급 능력)
$b_j$ : 수요지 $j$ 에서 필요한 수요량
$c_{ij}$ : 공급지 $i$ 에서 수요지 $j$ 로 물품을 운송하는 비용
$x_{ij}$ : 공급지 $i$ 에서 수요지 $j$ 로 운송하는 물품의 양 (결정 변수)

따라서, 수송 문제의 목표는 전체 운송 비용을 최소화하는 것이다. 이를 수학적으로 표현하면 다음과 같다.

목적 함수

최소화할 목적 함수는 총 운송 비용이며, 이는 다음과 같다.

$\text{Minimize} \quad \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}$

여기서 $x_{ij}$ 는 공급지 $i$ 에서 수요지 $j$ 로 운송할 물품의 양을 나타내고, $c_{ij}$ 는 해당 경로에서의 단위 비용을 의미한다.

제약 조건

수송 문제의 제약 조건은 공급지와 수요지 각각에서의 제한 사항을 반영한다.

1. 공급 능력 제약

각 공급지에서 운송하는 총 물품의 양은 해당 공급지의 공급 능력을 초과할 수 없다. 이를 수학적으로 표현하면:

$\sum_{j=1}^{n} x_{ij} \leq a_i \quad \text{for all} \, i = 1, 2, \dots, m$

2. 수요 충족 제약

각 수요지에서 요구하는 수요는 반드시 충족되어야 한다. 이를 수학적으로 표현하면:

$\sum_{i=1}^{m} x_{ij} = b_j \quad \text{for all} \, j = 1, 2, \dots, n$

3. 비음성 제약

각 경로에서 운송되는 물품의 양은 음수가 될 수 없으므로:

$x_{ij} \geq 0 \quad \text{for all} \, i = 1, 2, \dots, m \quad \text{and} \quad j = 1, 2, \dots, n$

표준 형태

위 수송 문제는 다음과 같은 표준 형태의 선형계획 문제로 변환할 수 있다:

$\begin{aligned} \text{Minimize} \quad & \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \\ \text{subject to} \quad & \sum_{j=1}^{n} x_{ij} \leq a_i \quad \text{for all} \, i = 1, 2, \dots, m \\ & \sum_{i=1}^{m} x_{ij} = b_j \quad \text{for all} \, j = 1, 2, \dots, n \\ & x_{ij} \geq 0 \quad \text{for all} \, i = 1, 2, \dots, m \quad \text{and} \quad j = 1, 2, \dots, n \end{aligned}$

초기 해의 탐색

수송 문제는 일반적으로 처음부터 최적해를 구하지 않고, 먼저 초기 해를 탐색하는 과정이 필요하다. 초기 해를 구하는 대표적인 방법은 다음과 같다:

1. 북서 코너법 (Northwest Corner Rule)

북서 코너법은 공급지와 수요지를 행렬로 배치했을 때, 왼쪽 상단 모서리(북서 코너)에서부터 시작해 가능한 물량을 할당해 나가는 방법이다. 이 과정은 아래와 같다.

행렬의 $(1, 1)$ 위치에서 가능한 한 많은 물품을 할당한다.
할당한 후 남은 공급량과 수요량을 계산한다.
수요 또는 공급 중 하나가 0이 되면, 다음 열 또는 행으로 이동하여 다시 할당을 진행한다.
이러한 과정을 통해 전체 공급과 수요를 모두 처리할 때까지 할당을 반복한다.

2. 최소 비용법 (Least Cost Method)

최소 비용법은 모든 경로의 비용을 고려하여, 가장 낮은 비용을 가지는 경로에 먼저 물품을 할당하는 방법이다. 이 방법은 다음과 같은 절차로 진행된다:

가장 낮은 $c_{ij}$ 값을 가진 경로를 찾는다.
해당 경로로 가능한 최대 물품을 할당한다.
할당 후 남은 공급량 또는 수요량을 업데이트하고, 다시 가장 낮은 비용의 경로를 찾아 할당을 반복한다.

수송 문제의 균형 여부

수송 문제는 종종 공급 총량과 수요 총량이 일치하지 않는 경우가 발생할 수 있다. 이때, 다음과 같이 두 가지 상황을 처리한다:

1. 공급 초과의 경우

공급 총량이 수요 총량보다 클 경우, 가상의 수요지를 추가하여 초과 공급량을 흡수하는 방법을 사용한다. 이때 가상의 수요지에 대한 운송 비용은 0으로 설정된다.

2. 수요 초과의 경우

수요 총량이 공급 총량보다 클 경우, 가상의 공급지를 추가하여 초과 수요를 충당하는 방법을 사용한다. 이때 가상의 공급지에 대한 운송 비용 역시 0으로 설정된다.

수송 문제의 최적화 방법

초기 해를 구한 후, 최적해에 도달하기 위한 방법으로 주로 사용하는 것은 수송 단체법(Transportation Simplex Method) 이다. 이는 단체법(Simplex Method)의 변형된 형태로, 수송 문제에 특화된 알고리즘이다. 이 과정은 비용을 최소화하면서 해를 개선하는 방법을 제시한다.

1. 배선법 (Stepping-Stone Method)

배선법은 초기 해로부터 출발하여 개선된 해를 찾는 방법 중 하나이다. 이를 통해 각 경로에서의 비용을 검토하고, 개선이 가능한지 여부를 확인한다.

개선 절차

배선 경로 찾기: 공급지와 수요지를 연결하는 폐회로(Cycle)를 형성한다. 이 때, 배선 경로는 물품이 운송되는 경로뿐만 아니라 비어 있는 경로도 포함해야 한다.
증감량 결정: 폐회로 내에서의 경로에 대해 양의 증감량과 음의 증감량을 번갈아가며 설정한다. 이로 인해 각 경로에 운송량이 더해지거나 줄어든다.
최소 증감량 결정: 음의 증감량 중 가장 작은 값을 찾아 해당 경로에 대한 물품의 양을 감소시킨다.
경로 업데이트: 최소 증감량을 각 경로에 적용한 후, 새로운 해를 계산한다.
개선 판단: 개선된 해가 더 나은 해인지 확인하고, 그렇지 않다면 다른 배선 경로를 찾는다.

비용 계산

각 배선 경로의 비용을 계산하여, 만약 비용이 줄어들 경우 그 경로로의 물품 이동을 최적화할 수 있다. 이를 통해 전체 운송 비용을 점진적으로 감소시킨다.

배선법은 경로를 계속해서 개선해 나가기 때문에, 초기 해에서 최적해로의 수렴 과정이 비교적 빠르고 직관적이다.

2. 잠재 비용법 (Modified Distribution Method, MODI)

잠재 비용법은 각 경로에서 운송할 물품의 비용을 재배치하는 방식이다. 이는 단체법의 교체변수를 사용하는 방식과 유사하며, 각 경로의 잠재 비용을 계산하여 이를 기반으로 비용을 최소화하는 방법이다.

절차

잠재 비용 계산: 초기 해에서 각 경로에 대해 잠재 비용을 계산한다. 이는 공급지 $i$ 의 잠재 비용 $u_i$ 와 수요지 $j$ 의 잠재 비용 $v_j$ 을 이용해 계산된다. 각 경로에 대한 잠재 비용은 다음과 같이 정의된다.

$c_{ij} = u_i + v_j$

비용 차이 계산: 잠재 비용과 실제 비용 간의 차이를 계산하여, 경로가 최적 상태에 있는지 확인한다.

$d_{ij} = c_{ij} - (u_i + v_j)$

여기서 $d_{ij}$ 가 음수일 경우, 해당 경로는 운송 비용을 줄일 수 있는 여지가 있음을 의미한다.

경로 개선: 비용 차이가 음수인 경로로 물품을 재배치하여 최적화를 시도한다.
잠재 비용 업데이트: 경로의 개선 후, 새로운 잠재 비용을 계산하고, 반복적으로 비용 차이를 확인하여 최적해를 찾는다.

변형된 수송 문제

수송 문제의 다양한 변형은 실제 산업에서 자주 발생한다. 몇 가지 주요 변형 사례는 다음과 같다.

1. 비용 함수의 변형

일부 수송 문제에서는 경로에 따라 비용 함수가 선형적이지 않거나, 운송량에 따라 비용이 비선형적으로 증가할 수 있다. 예를 들어, 대량의 물품을 운송할 때 비용이 단순히 비례하지 않고, 추가적인 비용이 발생하는 경우가 있을 수 있다. 이를 해결하기 위해 비선형 선형계획법이나 계층적 비용 함수를 적용할 수 있다.

2. 다목적 수송 문제

하나의 목표만을 최적화하는 것이 아니라, 여러 목표를 동시에 고려해야 하는 경우가 많다. 예를 들어, 비용뿐만 아니라 배송 시간, 재고 관리 비용, 환경적 요인 등을 함께 고려해야 하는 경우가 있다. 이러한 다목적 수송 문제는 목표계획법(Goal Programming)이나 다목적 최적화(Multi-Objective Optimization)를 통해 해결된다.

3. 시간 제약이 있는 수송 문제

운송 과정에서 특정 시간 제약을 만족해야 하는 경우, 수송 문제는 더욱 복잡해진다. 예를 들어, 상품이 특정 시간 내에 목적지에 도착해야 하거나, 운송 경로가 실시간으로 변경될 수 있는 문제들이 포함될 수 있다. 이를 해결하기 위해 시간 창(time windows)을 포함한 모델링을 도입할 수 있다.

4. 네트워크 흐름 문제로의 확장

수송 문제는 네트워크 흐름 문제(Network Flow Problem)로 확장될 수 있다. 이 경우, 각 경로는 단순한 출발지와 목적지를 연결하는 것이 아니라, 중간 경로나 허브를 거쳐가는 경우가 있을 수 있다. 네트워크 흐름 문제는 다양한 산업 분야에서 널리 적용되며, 주로 최소 비용 네트워크 흐름 문제(Minimum Cost Network Flow Problem)로 해결된다.

5. 동적 수송 문제

동적 수송 문제는 시간에 따라 공급, 수요, 그리고 비용이 변동하는 경우를 다룬다. 예를 들어, 시간에 따라 공급량이 증가하거나, 비용이 달라지는 경우가 있을 수 있다. 이때, 수송 문제는 동적 최적화 기법을 적용하여 해결한다. 동적 수송 문제는 동적 계획법(Dynamic Programming)을 통해 해결되는 경우가 많다.

정수형 수송 문제

일부 수송 문제에서는 운송량이 정수로 제한되어야 하는 경우가 있다. 이는 현실적으로 물품을 나눠서 운송할 수 없는 경우에 발생하는 제약이다. 예를 들어, 차량 한 대에 실을 수 있는 물품의 단위가 정해져 있거나, 상품이 분할 불가능한 경우가 해당된다. 이와 같은 문제를 정수형 수송 문제(Integral Transportation Problem)라고 한다.

정수형 수송 문제에서는 결정 변수 $x_{ij}$ 가 정수 제약을 가지며, 다음과 같이 표현된다:

$x_{ij} \in \mathbb{Z}^{+} \quad \text{for all} \, i, j$

이와 같은 문제는 일반적인 선형계획법으로는 해결할 수 없으며, 정수계획법의 기법이 필요하다. 대표적으로 사용되는 기법으로는 분지한정법(Branch and Bound Method)과 절단평면법(Cutting Plane Method)이 있다.

1. 분지한정법

분지한정법은 해 공간을 분할하여 각각의 분기에서 최적해를 탐색하는 기법이다. 이 방법은 다음과 같이 동작한다:

초기 문제 해결: 먼저, 정수 제약이 없는 상태에서 문제를 해결하여 초기 해를 구한다.
분기(branch): 초기 해에서 정수가 아닌 변수에 대해 두 가지 경우로 분기한다. 하나는 해당 변수를 내림한 경우, 다른 하나는 올림한 경우이다.
한정(bound): 각각의 분기에서 계산한 해가 기존의 최적해보다 나쁠 경우, 해당 가지를 더 이상 탐색하지 않고 자릅니다.
탐색 반복: 위 과정을 반복하여 정수 제약을 만족하는 최적해를 찾는다.

2. 절단평면법

절단평면법은 선형계획법의 해를 개선해 나가며 정수해를 찾는 방법이다. 선형계획의 해가 정수해가 아닐 경우, 추가적인 제약 조건(절단평면)을 도입하여 해를 점차 정수해로 수렴시키는 방법이다.

수송 문제의 그래프 표현

수송 문제는 이분 그래프(Bipartite Graph)로 표현될 수 있다. 이 그래프는 한쪽에는 공급지, 다른 쪽에는 수요지를 배치하고, 각각의 경로는 연결선(edge)으로 표현된다. 각 경로에는 해당 경로의 운송 비용이 가중치로 부여된다.

다음은 수송 문제의 이분 그래프에 대한 예시이다.

graph TD A[공급지 1] -->|c_11| B[수요지 1] A -->|c_12| C[수요지 2] D[공급지 2] -->|c_21| B D -->|c_22| C

위 그래프에서 각 공급지와 수요지 간의 경로는 운송 비용 $c_{ij}$ 를 나타내며, 물품은 이 경로를 따라 수송된다. 그래프는 수송 문제를 직관적으로 이해할 수 있도록 돕는다.

허브를 포함한 수송 문제

현실 세계에서는 공급지와 수요지 사이에 허브(hub)를 포함한 네트워크 구조가 자주 발생한다. 허브는 중앙에서 여러 경로로 물품을 분배하거나 통합하는 역할을 하며, 이를 통해 복잡한 물류 네트워크를 간단하게 표현할 수 있다.

허브를 포함한 수송 문제는 다음과 같은 방식으로 모델링된다:

허브 위치 선택: 중앙에 위치할 허브를 선택하며, 각 공급지와 수요지는 이 허브를 통해 물품을 주고받는다.
경로 최적화: 허브를 거치는 경로와 직접적인 경로 중, 비용이 더 낮은 경로를 선택하여 최적화를 수행한다.

허브 네트워크의 그래프 표현

허브를 포함한 수송 문제는 다음과 같은 그래프로 표현할 수 있다.

graph TD A[공급지 1] -->|c_1h| H[허브] B[공급지 2] -->|c_2h| H H -->|c_h1| C[수요지 1] H -->|c_h2| D[수요지 2]

여기서 $c_{1h}$ 는 공급지 1에서 허브까지의 비용, $c_{h1}$ 는 허브에서 수요지 1까지의 비용을 나타낸다. 허브를 통한 경로를 최적화하여 전체 비용을 줄일 수 있다.

네트워크 흐름 문제로의 확장

수송 문제는 네트워크 흐름 문제로 확장될 수 있으며, 이는 복잡한 네트워크 구조에서 발생하는 문제를 해결하는 데 사용된다. 네트워크 흐름 문제는 다음과 같은 요소를 포함한다:

정점(vertex): 공급지, 수요지, 허브 등을 나타낸다.
간선(edge): 각 경로를 나타내며, 운송 비용과 용량(capacity)을 포함한다.
용량 제한: 각 경로에서 운송할 수 있는 최대 물품의 양이 제한되는 경우가 많다.

네트워크 흐름 문제는 최소 비용 네트워크 흐름 문제(Minimum Cost Network Flow Problem)로 변형될 수 있으며, 각 경로의 비용과 용량을 고려하여 최적화된다.