Operations Research란 무엇인가?

생산량을 정하거나, 배송 경로를 고르거나, 한정된 예산을 여러 곳에 배분해야 한다고 해보자. 선택지는 많지만 쓸 수 있는 시간과 자원은 제한되어 있다. 이때 필요한 질문은 단순하다.

주어진 조건을 지키면서 어떤 선택을 해야 가장 좋은 결과를 얻을 수 있을까?

Operations Research(OR)는 이런 의사결정 문제를 정량적으로 분석하는 분야다. 한국어로는 운용과학 또는 경영과학이라는 이름을 쓰기도 한다. 복잡한 계산 자체보다 중요한 것은 현실의 문제를 결정할 것, 달성할 목표, 지켜야 할 조건으로 나누어 보는 방식이다.

OR이 다루는 문제

OR은 제2차 세계대전 중 레이더 운용과 자원 배분 같은 군사 문제를 여러 분야의 전문가가 함께 분석하면서 본격적으로 발전했다. 이후 생산, 물류, 교통, 의료, 금융 등으로 적용 범위가 넓어졌다.

분야가 달라도 질문의 구조는 비슷하다. 공장에서는 어떤 제품을 얼마나 만들지, 물류망에서는 어느 경로로 운송할지, 병원에서는 제한된 인력과 공간을 어떻게 배치할지 결정해야 한다. 여러 대안이 서로 다른 결과를 낳고, 모든 대안을 무제한으로 선택할 수는 없다.

OR은 직관을 배제하기보다 대안을 비교할 수 있는 모델을 만들고, 그 모델이 제안한 선택을 현실의 맥락에서 해석하도록 돕는다.

먼저 구분할 세 가지

의사결정 문제를 수식으로 옮기기 전에 다음을 구분하면 구조가 선명해진다.

요소	질문	예시
결정(Decision)	무엇을 바꿀 수 있는가?	제품 A와 B의 생산량
목표(Objective)	어떤 결과를 좋게 만들고 싶은가?	총이익 최대화
제약(Constraint)	반드시 지켜야 할 조건은 무엇인가?	작업시간과 원재료의 한도

여기에 매개변수(Parameter)가 더해진다. 제품의 단위이익, 제품 하나에 필요한 작업시간, 사용 가능한 총 작업시간처럼 의사결정 전에 주어진 값이다. 결정변수와 달리, 하나의 모델을 푸는 동안에는 고정된 값으로 취급한다.

예를 들어 제품 A와 B의 생산량을 각각 $x$, $y$라고 하자. 두 제품의 단위이익이 5와 4라면 목표는 다음처럼 쓸 수 있다.

$$\max\; 5x+4y$$

제품 A에는 작업시간 2단위, B에는 1단위가 필요하고 총 100단위만 쓸 수 있다면 제약은 $2x+y\leq100$이다. 다른 설비의 용량이 $x+2y\leq80$이라면 전체 문제는 다음과 같다.

$$\begin{aligned} \max_{x,y}\quad &5x+4y\\ \text{subject to}\quad &2x+y\leq100,\\ &x+2y\leq80,\\ &x,y\geq0. \end{aligned}$$

여기서 $x$와 $y$는 결정변수, $5$와 $4$는 단위이익, 오른쪽의 $100$과 $80$은 사용 가능한 자원량이다. 실제 제품을 쪼개서 만들 수 없다면 $x,y$가 정수라는 조건도 추가해야 한다. 무엇을 생략하고 무엇을 조건으로 넣느냐에 따라 모델의 답이 달라진다.

현실을 모델로 바꾸는 이유

실제 생산계획에는 작업자의 숙련도, 기계 고장, 수요 변화, 전력비, 재고처럼 수많은 요소가 영향을 미친다. 이를 모두 한 번에 계산하려 하면 모델은 다루기 어려워진다.

그래서 모델링에는 추상화가 필요하다. 의사결정에 중요한 관계는 남기고, 당장의 목적에 영향이 작은 요소는 단순화한다. 같은 공장이라도 하루 생산량을 정할 때와 설비 증설을 결정할 때는 필요한 모델이 다를 수 있다. 모델은 현실의 복사본이 아니라 특정 질문에 답하기 위한 도구다.

일반적인 최적화 모형은 결정변수 $\mathbf{x}$, 목적함수 $f$, 제약식 $g_i$를 사용해 다음처럼 나타낼 수 있다.

$$\begin{aligned} \min_{\mathbf{x}}\quad &f(\mathbf{x})\\ \text{subject to}\quad &g_i(\mathbf{x})\leq b_i\quad (i=1,\ldots,m). \end{aligned}$$

목표가 이익이라면 최소화 대신 최대화를 쓴다. 등식 제약이나 정수 조건이 필요하면 그에 맞게 추가한다. 핵심은 수식의 모양을 외우는 것이 아니라 현실의 선택과 조건이 수식에서 각각 무엇을 뜻하는지 설명할 수 있는가에 있다.

익숙한 선택도 같은 구조를 가진다

여행 가방에 넣을 물건을 고를 때는 각 물건의 가치가 다르고 가방이 견딜 수 있는 무게는 한정되어 있다. 물건 $i$를 가져가면 $x_i=1$, 아니면 $x_i=0$으로 두면 배낭 문제(Knapsack Problem)는 다음처럼 표현된다.

$$\begin{aligned} \max\quad &\sum_i p_i x_i\\ \text{subject to}\quad &\sum_i w_i x_i\leq W,\\ &x_i\in\{0,1\}. \end{aligned}$$

$p_i$는 물건의 가치, $w_i$는 무게, $W$는 가방의 최대 허용 무게다. 목표는 가져간 물건의 총가치를 높이는 것이고, 무게 한도와 물건을 가져갈지 말지의 선택 방식이 제약이다.

최단 경로 문제(Shortest Path Problem)에서는 출발지에서 목적지까지 어느 길을 지날지 결정한다. 각 구간의 이동시간을 더한 값이 목적함수가 되고, 선택한 구간들이 끊어지지 않은 하나의 경로를 이뤄야 한다는 조건이 필요하다. 이동시간을 최소화하는 수식만 적고 경로 연결 조건을 빠뜨리면, 출발지와 목적지를 잇지 않는 구간들까지 답으로 고를 수 있다.

대학 시간표도 비슷하다. 수강 과목을 결정변수로 두고 등교일 수를 줄이는 것을 목표로 삼을 수 있다. 다만 필수 과목, 학점, 시간 충돌 같은 조건을 함께 반영해야 한다. 목표만 정해서는 의사결정 문제가 완성되지 않는다.

최적의 답이 아니라 가능한 답을 찾는 문제

모든 문제에 최대화·최소화 목표가 필요한 것은 아니다. 스도쿠에서는 점수를 높이기보다 규칙을 만족하는 숫자 배치를 하나 찾으면 된다.

칸 $(i,j)$에 숫자 $k$를 넣으면 $x_{ijk}=1$, 아니면 $0$이라고 두자. 각 칸에 숫자가 하나씩 들어가고, 각 행·열·$3\times3$ 블록에 1부터 9까지의 숫자가 한 번씩 나오도록 조건을 세울 수 있다. 이런 문제는 실행 가능성 문제(Feasibility Problem)다. 형식적으로 목적함수를 $\max 0$으로 둘 수 있지만, 중요한 것은 조건을 만족하는 해의 존재 여부다.

반대로 식단 문제(Diet Problem)에는 분명한 비용 목표가 있다. 음식 $j$를 먹는 양을 $x_j$, 가격을 $c_j$, 음식에 포함된 영양소 $i$의 양을 $a_{ij}$, 필요한 최소 섭취량을 $r_i$라고 하면 다음과 같다.

$$\begin{aligned} \min\quad &\sum_j c_jx_j\\ \text{subject to}\quad &\sum_j a_{ij}x_j\geq r_i\quad\text{(각 영양소 }i\text{)},\\ &x_j\geq0. \end{aligned}$$

영양 기준을 충족하면서 식비를 최소화하는 모델이다. 실제 식단에 적용하려면 섭취 가능한 양, 식품 조합, 개인의 건강 상태 같은 조건도 검토해야 한다. 수식이 낸 최저 비용이 곧바로 실행할 만한 식단을 뜻하지는 않는다.

OR은 최적화보다 넓다

OR을 최적화와 같은 말로 생각하기 쉽지만, 정량적인 의사결정을 돕는 방법은 더 다양하다.

• 최적화는 주어진 조건에서 가장 좋은 선택을 찾는다.
• 시뮬레이션은 복잡한 시스템이 시간에 따라 어떻게 움직이는지 실험한다.
• 확률 모형은 수요, 도착 간격, 고장처럼 불확실한 요소를 다룬다. 대기행렬·재고·마르코프 모형이 여기에 속한다.
• 통계와 데이터 분석은 모델에 필요한 값을 추정하고 결과를 검증하는 데 쓰인다.

현실에서는 미래 수요나 작업시간을 정확히 알 수 없는 경우가 많다. 하나의 최적해를 계산하는 것만으로 끝내지 않고, 가정이 달라졌을 때 답이 얼마나 바뀌는지 확인해야 한다. 모델을 만든 뒤 입력값 검증, 민감도 분석, 현장 적용 가능성 확인이 이어지는 이유다.

정리

OR을 시작할 때는 알고리즘보다 질문의 순서를 먼저 익히는 편이 좋다.

1. 무엇을 결정할 수 있는가?
2. 어떤 결과를 좋게 만들고 싶은가?
3. 어떤 조건을 반드시 지켜야 하는가?
4. 모델의 가정과 계산 결과가 현실에서도 타당한가?

이 질문에 답하며 현실의 문제를 모델로 옮기고, 대안을 분석한 뒤, 결과를 다시 현실의 언어로 해석한다. 이후 배우게 되는 선형계획, 정수계획, 네트워크 모형, 동적계획도 이 기본 흐름 위에서 이해할 수 있다.