1. 과목에서 배울 수 있는 내용
우리는 일상 속에서 수많은 선택의 순간에 놓입니다. 점심으로 무엇을 먹을지와 같이 사소한 문제부터 어떤 직장을 얻을지와 같이 중요한 문제까지 다양한 문제를 마주합니다. 그럴 때마다, 각자 처한 상황에 맞추어 판단을 한 후에 결정을 내립니다. 이 결정들은 단순해 보일지라도, 수많은 변수를 충분히 고려한 뒤에 내려지는 결정입니다.
어떤 조직에서의 의사결정은 어떨까요? 직원의 인력 배치를 어떻게 하는지부터, 자원의 구매와 분배 및 생산계획까지. 수많은 의사결정 문제에 놓이게 되는데, 이들은 그 규모가 크다는 공통점이 있습니다. 이로 인해 의사결정의 복잡성이 높아지고 결과의 영향도 커집니다. 따라서 조직을 운영하고 이끌어감에 있어 발생하는 의사결정은 견고한 근거를 바탕으로 최적의 결정이 이루어져야 합니다. 이때 철저한 조사와 방대한 데이터를 바탕으로 근거를 만들어내는 과정에서 ‘경영과학’이 등장합니다.
경영과학(Operational Research)은 과학적 최적화의 기법을 일컫는데, 의사결정 문제를 모형화하는 것부터 최적화된 해를 도출해 실제 의사결정 문제에 적용하는 것까지의 전반적인 과정을 의미합니다. ‘경영과학1’ 수업에서는 사용할 수 있는 모형, 즉 해법에서 크게 다섯 가지를 다룹니다: 선형계획 모형 (Linear Programming), 네트워크 모형 (Network Model), 정수계획 모형 (Integer Programming), 비선형계획 모형 (Non-Linear Programming), 게임 이론 (Game Theory).
(1) 의사결정 모형
가장 먼저, 의사결정 문제를 위한 모형의 기본이 되는 세 가지 요소에 대해 학습합니다.
첫 번째는 결정변수로, 의사결정을 통해 조정하고자 하는 변수 자체를 의미합니다. 대표적인 예시로 생산 제품의 가격과 구매하고자 하는 원자재의 물량이 여기에 해당됩니다. 여기서 강조되는 점은 외생변수와 분리해야 한다는 점입니다. 외생변수는 외부환경으로 인해 발생하는 변수로 통제할 수 없다는 특징이 있습니다. 따라서 이러한 변수를 결정변수에 포함시키지 않고, 더 나아가 꼭 필요한 변수만 고려함으로써 의사 결정 문제를 효율적으로 모형화하는 것이 중요합니다.
두 번째는 목적함수(효용)으로, 이루고자 하는 목표가 무엇인지에 대한 정보를 담는 요소입니다. 조직에 따라, 상황에 따라 추구하는 목표가 달라질 수 있습니다. 일부 기업은 매출의 최대화를, 다른 기업은 비용의 최소화를 추구할 수 있고, 같은 목표를 추구하더라도 어떤 계산 방법을 사용하는지도 다를 수 있습니다. 이러한 상황들은 서로 다른 최적화 해로 이어지므로, 적절한 목적함수를 찾는 것이 중요합니다.
세 번째 요소는 제약으로, 현실에서 자유로운 의사결정을 방해하는 요소입니다. 제품 생산에 필요한 원자재의 재고 물량이나 인적 자원의 유한성이 여기에 해당됩니다. 이러한 제약들은 복합적으로 작용해 효용을 변화시키기 때문에, 의사결정 상황을 더욱 복잡하게 만듭니다. 여기서, 상황을 더욱 정확하게 묘사하기 위해서는 많은 제약식을 활용해야 하지만, 그만큼 계산의 복잡성이 높아지기 때문에 그 사이의 균형이 중요합니다.
(2) 선형계획 모형 (Linear Programming)
첫 번째로 다루는 내용은 모든 모형 중 제일 기본이 되면서도 가장 오랫동안 연구되어 온 선형계획 모형 (Linear Programming)입니다. 이름에서 알 수 있듯, 선형계획 모형은 목적함수와 제약식이 모두 결정변수의 선형조합으로 표현되는 모형을 의미합니다. 예시로 아래와 같은 상황을 들 수 있습니다.
기업 A는 두 가지 종류의 제품을 생산함에 있어 최대 이익을 얻고 싶어 합니다. 이익은 아래 표와 같은데, 이때 각 제품 별로 필요한 원자재가 다르며 각 원자재의 재고량 또한 다릅니다.
이를 모형화하기 위해 해석해보자면, 결정변수는 각 제품의 생산량이고, 효용은 ‘이익의 최대화’이며 제약은 ‘원자재의 재고’입니다. 이를 바탕으로 표에 있는 값을 대입하면 아래와 같은 선형계획 모형을 얻을 수 있습니다.
선형계획 모형으로 모형화가 끝나면 프로그램을 통해 최적화 해를 도출할 수 있습니다. 본 수업에서 활용한 프로그램은 ‘Xpress’이지만, python을 비롯한 여러 프로그램 및 언어를 통해서도 풀 수 있습니다. 프로그램 내에서 선형계획 모형을 풀기 위해 사용되는 알고리즘인 심플렉스 알고리즘 (Simplex Algorithm)에 대해서도 다룹니다. 간단하게 정리해, 반복적인 동작 수행이 가능한 가우시안 소거법 (Gaussian Elimination)의 일종이라고 볼 수 있습니다.
선형계획 모형에서는 ‘민감도 분석’을 수행할 수 있습니다. ‘민감도 분석’이란 제약과 효용이 달라짐에 따라 최적화 해가 어떻게 달라지는지에 대해 분석해 주는 기능입니다. 앞선 예시에 적용해 보자면, 제약식의 우변항(가용 자원량)이나 효용 식의 계수(각 제품의 이익)가 달라짐에 따라 실제 최적해가 어떻게 달라지는지를 분석해 줍니다. 제약식의 우변항이 1 증가함에 따라 목적함수의 값이 어떻게 변하는지, 효용 식의 계수에 따라 최적화 해가 달라지는지를 분석해 주어서, 유사한 상황에서의 해가 어떻게 변할지에 대한 정성적인 분석을 시행할 수 있습니다.
(3) 정수계획 모형 (Integer Programming)
두 번째로 다루는 내용은 정수계획 모형입니다. 선형계획 모형은 가장 단순한 모형이지만 현실에서 적용하기 어려운 경우가 많습니다. 대표적인 예시로 인력 배분 계획에서의 의사결정 문제가 있습니다. 인력 배분을 계획하는 의사결정 상황에서 최적화 해는 분배 인력을 나타내므로, 이 때 도출되는 결정변수 값은 자연수이어야 합니다. 그러나 선형계획 모형의 해는 해가 자연수라는 제약이 존재하지 않기 때문에 실수 값이 출력됩니다. 따라서, 이를 보완하기 위해서는 ‘결정변수는 모두 자연수이다’라는 제약이 포함된 정수계획 모형이 활용됩니다.
그러나 제약 조건이 한 가지만 추가되었음에도 선형계획 모형과 다르게 명쾌한 알고리즘이 존재하지 않습니다. 그 이유는 선형계획 모형에서의 모든 문제는 다항시간(Polynomial Time) 안에 풀 수 있지만, 정수계획 모형은 그럴 수 없는 NP-hard에 해당되는 문제이기 때문입니다. 수학적인 관점에서는 가능한 해의 범위가 유한하므로 열거법(Enumeration)을 통해 이론적으로 풀 수 있습니다만, 이를 실제로 시행하기 위해서는 연산량이 너무 많아지기 때문에 현실적인 관점에서는 선형계획 모형보다 어려운 문제로 볼 수 있습니다.
다만, 정수계획 모형은 그 활용성이 선형계획 모형에 비해 더 넓은만큼 다방면으로 연구되고 있습니다. 본 수업에서 다루는 활용 범위로는 이진배낭문제, 집합커버문제, 세일즈맨 순회 문제, 최소비용걸침나무 문제, 논리제약 조건 문제, 퍼즐 문제가 있습니다. 이 중에서 가장 널리 알려진 세일즈맨 순회 문제 (Traveling Salesman Problem,TSP)를 소개해보고자 합니다.
세일즈맨 순회 문제는 N개의 지점을 매일 순회해야 하고 각 지점 간의 소요시간이 상이할 때, 가장 적은 소요시간으로 모든 지점을 순회하는 경로가 무엇인지에 대해 다루는 문제입니다. 여기서 효용, 즉 목적함수는 ‘소요시간을 최소화하는 것’이며, 제약은 ‘1) 단 한 번의 순회를 통해 2) 모든 지점을 통과한다’로 총 두 가지입니다. 여기에 결정변수를 순회 시 두 지점 간의 경로를 통과하는지 여부로 정한다면, 앞선 목표와 제약함수를 변환하여 아래와 같이 정수계획 모형을 설립할 수 있습니다. 아래 정수계획 모형으로 도출된 최적해대로 순회를 한다면, 모든 지점을 가장 빠르게 순회할 수 있는 것입니다.
(4) 네트워크 모형 (Network Model)
세 번째로 다루는 내용은 네트워크 모형입니다. 이전 모형과 다르게 주어진 상황을 모형화할 때 수식이 아닌 그림을 활용합니다. 이러한 특징으로 인해 직관적이면서도 유연하게 문제를 해석할 수 있다는 장점이 있습니다. 대표적으로 교통, 운송, 정보통신에서는 수많은 연결과 흐름이 복잡하게 얽혀있기 때문에 네트워크 모형이 유용하게 사용됩니다.
본 수업에서는 네트워크 모형의 5가지 문제를 다룹니다: 최단경로문제, 최대흐름문제, 최소비용흐름문제, 스타이너나무문제, 최소비용걸침나무문제. 본문에서는 최단경로문제와 스타이너나무문제에 대해 살펴보고자 합니다.
최단경로문제는 이름에서 알 수 있듯, 한 지점에서 다른 지점까지 가장 짧은 거리로 도달할 수 있는 경로를 찾는 문제를 지칭합니다. 대표적인 예시로 내비게이션의 경로 찾기 알고리즘이 여기에 해당됩니다. 지도 위의 수많은 장소를 하나의 점이라고 볼 때, 현위치에서 가고자 하는 지점까지의 거리를 최소화하는 경로를 찾는 알고리즘이 최단경로 문제의 일종입니다.
이를 풀기 위해 다음과 같은 최단경로의 필요충분조건을 활용합니다.
이를 바탕으로 하는 포드 알고리즘(Ford’s Algorithm)과디아크스트라 알고리즘(Dijkstra’s Algorithm)이 있습니다. 간단하게 설명해, 포드 알고리즘은 각 점을 연결하는 모든 호가 위 식을 만족할 때까지 계속 반복 작업을 수행하는 알고리즘이고, 디아크스트라 알고리즘은 모든 점에 대해 한 번씩 확인하는 알고리즘입니다. 전자는 다양한 상황에서의 계산이 가능한 유연성을 지닌 반면, 후자는 계산의 효율성을 챙긴 경우라고 볼 수 있습니다.
스타이너나무문제는 네트워크 상에서 원하는 지점이 최소의 비용으로 연결될 수 있는 경우를 찾는 문제를 의미합니다. 간단하게 아래 사각형 모양의 네트워크를 생각해 봅시다. 모든 호가 존재한다면 모든 꼭짓점들이 연결되는데, 여기서 가운데 대각선 호를 제거한다고 꼭짓점 간의 연결이 없어지지는 않습니다. 하지만 가운데 대각선 호는 유지하되 모든 바깥쪽 변을 제거한다면 꼭짓점들끼리의 연결이 없어집니다. 스타이너 나무 문제는 위와 같은 상황을 (1) 모든 지점이 아닌 일부 지점에 대해서 다루며 (2) 호에 부여되는 비용의 최소화와 함께 고려하는 문제라고 생각하면 됩니다.
네트워크 라우팅, 데이터의 송신을 비롯해 여러 지점 간의 효율적이면서 완전한 연결성이 중요한 경우에 자주 활용됩니다. 이 문제의 해법을 찾기 위한 알고리즘으로 스타이너 근사알고리즘을 다룹니다. 요약하자면, 임의의 지점부터 시작해 짧은 경로를 가진 호를 하나씩 선택해 가면서, 목표하는 지점들이 모두 연결될 때까지 반복하는 원리입니다. 하지만 스타이너나무문제도 NP-hard이기 때문에, 이 알고리즘의 해는 최적해를 보장하지 않습니다. 대신 이 알고리즘은 2-근사해법으로, 최적해 목적함수의 두 배를 넘지 않음을 보장하는 해를 도출합니다.
(5) 비선형계획 모형 (Non-Linear Programming) & 게임이론 (Game Theory)
이 외에도 비선형계획 모형(Non-Linear Programming)과 게임이론(Game Theory)에 대해서도 다룹니다.
비선형계획 모형은 선형계획 모형과 대치되는 모형으로 바라볼 수 있습니다. 목적함수와 제약식이 선형으로 구성되어 있지 않은 경우가 많은데, 그러한 상황을 모두 통틀어 비선형계획 모형에 해당된다고 설명합니다. 선형계획 모형과 다르게 최적해에 국지최적해(Local optimum solution)와 전역최적해(Global optimum solution)가 존재하기 때문에, 이를 풀기 위해서는 기울기 벡터를 비롯한 도구를 활용하는 다른 알고리즘이 필요합니다. 해의 도출 과정은 다소 복잡하지만, 비선형 수식도 다루기 때문에 활용 범위가 넓다는 특징이 있습니다.
게임이론은 의사결정에 있어 다른 사람과의 상호작용이 포함되는 상황에 대해 다루는 모형입니다. 같은 상황 속에 있는 상대방의 전략이 달라지면 그에 따라 나의 최적의 전략 또한 달라지므로, 복합적으로 고려하는 과정이 필수적입니다. 게임이론은 이러한 상황을 총체적으로 고려해 최적의 의사결정을 내릴 수 있는 것을 가능하게 해 줍니다.
2. 선배의 조언
수업 전반에 걸쳐 의사결정 문제를 모형화하고 그 모형의 최적해를 찾아내는 과정에서 수식을 자주 마주하게 됩니다. 하지만 수식에만 집중하면 개념에 대한 근본적인 이해를 놓치게 되고, 의사결정 문제를 다각적으로 바라볼 수 있는 유연성을 학습하기가 어려워집니다. 따라서, 수식을 보면서도 그것을 말로 변환하여 풀어내는 것이 중요합니다.
‘경영과학1’을 수강하고 최적화라는 분야에 흥미가 생겼다면, 각 모형에 대해 심도 있게 다루는 후속 강의들도 추천합니다. 대표적으로 ‘경영과학2’, ‘선형 및 비선형 최적화’, ‘게임이론’ 등이 있습니다. 각 수업에서는 본 수업에서 다룬 여러 가지 최적화 모형에서 더 다양한 종류를 다루고, 더 깊게 들어가 알고리즘에 대한 수학적인 분석을 심층적으로 다룹니다.
3. 진로 선택에 도움 되는 점
본 수업에서 다루는 내용을 기본으로 삼아 학문에 대한 연구나 현업으로의 적용이 이뤄지고 있습니다. 몇 가지 예시로, 불확실성 하에서의 최적화를 다루는 강건최적설계(Robust optimization), 이산형최적화(Discrete Optimization)의 방법론, 기존 분지절단법(Branch-and-cut)의 계산 속도를 향상할 수 있는 알고리즘의 개발을 비롯해 학술적인 분야에 해당하는 연구가 있고, 실시간 열차 스케줄링이나 열차 노선계획 문제와 같은 현실로의 적용에 대한 연구가 있습니다. [1,2]
4. 맺음말
사회의 기저가 되며 우리가 일상에서 누리고 있는 여러 가지 시스템은 임의로 짜인 것이 아니라, 최적화의 결과로 결정됩니다. 이러한 최적화는 수많은 변수를 가지고 있을뿐더러 변수 간의 관계성 또한 다양하기 때문에 모형 문제의 복잡성은 더더욱 증가하게 됩니다. ‘경영과학1’에서는 최적화라는 개념에 대해 처음 접하게 되면서, 이를 풀기 위한 이론과 전반적인 과정에 대해 간략하게 살펴볼 수 있습니다. 더 나아가, 사회 속 최적화의 역할을 느낄 수 있고, 정해지지 않은 상황을 모형으로 모델링하는 문제 해결 능력까지 함양할 수 있습니다.
본문에서는 여러 기법에 대해 간략하게 다루었지만, 수업에서는 더 자세한 개념과 근본적인 원리를 살피면서 생각해 볼만한 지점을 여럿 제공합니다. 이 글을 읽고 흥미가 생기신 분이나, 이 분야에 도전해보고 싶은 분들에게 ‘경영과학1’ 수업을 추천드리고 싶습니다.
5. 참고문헌
[1] Management Science/Optimization Lab, http://polytope.snu.ac.kr/
[2] System Optimization Lab, http://optimize.snu.ac.kr/research.html
'전공백서 > 기타 학과 및 학부' 카테고리의 다른 글
| 경영학과: 재무관리 (1) | 2023.12.29 |
|---|---|
| 과학기술학 연계전공: 미래 에너지 시스템과 과학정책 (1) | 2023.12.29 |
| 데이터사이언스대학원: 데이터사이언스를 위한 머신러닝 및 딥러닝 1 (0) | 2023.08.28 |
댓글