406. 선형 프로그래밍과 심플렉스 (Simplex) 알고리즘

핵심 인사이트 (3줄 요약)

본질: 선형 프로그래밍(Linear Programming, LP)은 자원이 한정된 상황에서 이익을 최대화하거나 비용을 최소화하는 문제를 부등식(직선)으로 표현하고, 이 직선들이 만들어낸 다각형(다면체) 영역 안에서 최적의 해답을 찾는 수리 최적화 모델이다.

가치: 심플렉스(Simplex) 알고리즘은 이 다각형 영역 내부의 수많은 점을 다 조사하는 무식한 짓을 버리고, "정답은 무조건 다각형의 뾰족한 꼭짓점(Vertex) 중 하나에 있다"는 위대한 수학적 발견을 바탕으로 꼭짓점만 타고 다니며 빛의 속도로 정답을 찾아냈다.

판단 포인트: 심플렉스법은 최악의 경우(Worst-case) 꼭짓점을 너무 많이 돌아서 연산 시간이 지수 시간으로 터지는 치명적 버그가 존재하므로, 최근 빅데이터 풀이에서는 행렬 내부를 관통해버리는 **내부점 법(Interior Point Method)**으로 아키텍처를 교체하는 추세다.

Ⅰ. 개요 및 필요성

공장에서 책상과 의자를 만든다. 책상은 나무 2개, 철 1개가 필요하고 이익은 5만 원이다. 의자는 나무 1개, 철 2개가 필요하고 이익은 4만 원이다. 창고에는 나무 100개, 철 80개밖에 없다. 어떤 조합으로 만들어야 이익이 최대가 될까?

이걸 수학적으로 쓰면, $2x + y \le 100$ (나무 제한), $x + 2y \le 80$ (철 제한)이라는 제약 조건(Constraints) 하에, $5x + 4y$ 라는 **목적 함수(Objective Function)**를 최대로 만드는 $x, y$를 구하는 문제다. 그래프를 그리면 부등식들이 교차하면서 하나의 다각형 모양 영토가 생기는데, 이 영토 안에서 가장 높은 산봉우리를 찾는 과정이 바로 **선형 프로그래밍(LP)**이다.

📢 섹션 요약 비유: 부모님이 주신 용돈(제약 조건) 안에서, 가장 맛있는(목적 함수) 과자 조합을 고르는 쇼핑의 기술이다. 이 쇼핑 기술을 수천억 원짜리 공장 생산 라인에 적용한 것이 LP다.

Ⅱ. 아키텍처 및 핵심 원리

선형 프로그래밍의 정답을 찾는 심플렉스(Simplex) 알고리즘은 다면체의 '꼭짓점(Vertex)'만 밟고 지나가는 놀라운 파이프라인을 쓴다.

┌────────────────────────────────────────────────────────┐
│             [ 심플렉스(Simplex) 알고리즘의 최적화 파이프라인 ]  │
├────────────────────────────────────────────────────────┤
│ 1. 슬랙 변수 (Slack Variable) 투입                      │
│    - "2x + y <= 100" 이라는 꼴 보기 싫은 부등식을            │
│      "2x + y + s1 = 100" 처럼 억지로 등식(=)으로 바꿈!       │
│                                                        │
│ 2. 초기 기저해 (Initial Basic Feasible Solution)        │
│    - 원점 (x=0, y=0)에서 탐색 시작. (아무것도 안 만든 상태)     │
│    - 다각형(다면체)의 가장 구석탱이 꼭짓점에 서 있는 것임.         │
│                                                        │
│ 3. 피벗 연산 (Pivoting) : 꼭짓점 이동                    │
│    - "현재 꼭짓점 주변의 다른 꼭짓점으로 이동하면 이익이 오르는가?"│
│    - 이익이 오르는 방향의 모서리(Edge)를 타고 다음 꼭짓점으로 점프!│
│                                                        │
│ 4. 최적성 검사 (Optimality Test)                        │
│    - 주변 꼭짓점 어딜 둘러봐도 지금 내 자리보다 이익이 낮다?      │
│    - "찾았다! 여기가 최적해(Global Optimum)다!" 하고 종료.     │
└────────────────────────────────────────────────────────┘

모서리(Vertex)의 정리: 선형 계획법이 그리는 영토(Feasible Region)는 완벽하게 굽은 곳이 없는 다면체(Polyhedron)다. 수학적으로 "목적 함수(직선)가 다면체와 가장 마지막에 맞닿는 곳은 무조건 모서리일 수밖에 없다"는 정리가 심플렉스의 심장이다.
지역 최적해(Local Minima) 없음: 선형 계획법은 다면체가 볼록(Convex)하기 때문에, 가짜 웅덩이(Local Minima)가 절대 존재하지 않는다. 꼭짓점을 타고 가다가 멈추는 곳이 100만 퍼센트 진짜 정답(Global Minima)이다.

📢 섹션 요약 비유: 거대한 크리스털 보석(다면체)이 있을 때, 가장 높은 꼭짓점을 찾으려고 보석 전체를 더듬어보는 게 아니라, 맨 밑바닥 꼭짓점에서 시작해서 위로 향하는 모서리만 따라 계속 타고 올라가면 결국 꼭대기(최적해)에 도착한다는 마법이다.

Ⅲ. 비교 및 연결

수리 최적화를 푸는 3대 알고리즘의 발전 계보를 비교해 본다.

비교 항목	심플렉스법 (Simplex)	정수 계획법 (분기 한정법)	내부점 법 (Interior Point Method)
정답의 제약	소수점 무한 허용	무조건 정수(Integer) 여야 함	소수점 무한 허용
탐색 경로	다각형의 바깥 모서리(꼭짓점)를 타고 다님	선형 완화 후 트리(Tree)를 쪼개며 탐색	다각형의 내부(허공)를 뚫고 직진함
최악의 시간 복잡도	지수 시간 ($O(2^N)$) 터짐	지수 시간 ($O(2^N)$) 터짐	다항 시간 ($O(N^3)$) 내에 무조건 보장
활용 도메인	수천 개 변수 수준의 최적화	트럭 대수, 스케줄링 등	수백만 개 변수의 빅데이터 최적화 표준

1947년에 나온 심플렉스는 완벽해 보였지만, 변수(차원)가 10만 개가 되면 10만 차원의 꼭짓점을 수백만 번 타고 다녀야 해서 가끔 컴퓨터가 뻗어버리는 최악의 치명적 결함(Worst-case Exponential Time)이 있었다. 이를 해결하기 위해 1984년 카마르카르가 발명한 **내부점 법(Interior Point)**은 꼭짓점을 타지 않고 다면체 안쪽 허공을 가로질러 정답으로 직진하는 기술로 현대 빅데이터 수리 최적화의 제왕이 되었다.

📢 섹션 요약 비유: 미로(다각형)의 밖을 빠져나갈 때, 심플렉스법은 눈을 감고 '벽(모서리)'을 짚어가며 뱅뱅 돌아서 나가는 방식이고, 내부점 법은 미로 한가운데서 GPS를 켜고 허공(내부)을 날아서 한 번에 출구로 날아가는 혁명이다.

Ⅳ. 실무 적용 및 기술사 판단

실무 적용 시나리오: 카카오 쿠팡 같은 물류 센터에서 내일 전국 각지로 10만 개의 물건을 쏘는 운송 최적화(Transportation Problem)를 짠다. "출발지 재고 <= 배송지 수요"라는 선형 제약 조건과 "배송 거리 최소화"라는 목적 함수를 Gurobi나 CPLEX 솔버에 넣는다. 내부의 심플렉스 알고리즘이 희소 행렬(Sparse Matrix) 연산을 태우며 10만 개의 변수 조합 꼭짓점을 1초 만에 타다닥 타고 넘어가 "A트럭은 강남으로, B트럭은 부산으로 가라"는 최소 비용 배차표를 엑셀로 뱉어낸다.

기술사 판단 포인트 (Trade-off): 최적화 아키텍처를 도입할 때 기술사는 **'심플렉스(Simplex)'와 '내부점 법(Interior Point)'**을 벤치마킹하여 스위칭해야 한다.

변수(Column)가 적고, 제약 조건(Row)만 많은 경우: 심플렉스법(특히 쌍대 심플렉스, Dual Simplex)이 압도적으로 빠르다.
변수가 수십만 개 이상인 거대 네트워크(빅데이터) 문제: 심플렉스는 꼭짓점을 돌다가 영원한 루프에 빠질 수 있다. 기술사는 솔버의 하이퍼파라미터를 조정해 무조건 **내부점 법(Barrier Method)**으로 엔진을 강제 교체하여 다항 시간 내에 수렴하도록 아키텍처를 방어해야 한다.

📢 섹션 요약 비유: 심플렉스는 좁은 동네 골목길에서 오토바이로 벽치기를 하며 배달하는 게 제일 빠르고, 내부점 법은 대륙 간 이동을 할 때 골목길 대신 비행기로 상공을 가로지르는 게 훨씬 빠른 것과 같다. 데이터의 스케일에 맞춰 배달 수단(알고리즘)을 바꿔야 한다.

Ⅴ. 기대효과 및 결론

선형 프로그래밍(LP)과 조지 단치히(George Dantzig)가 발명한 심플렉스 알고리즘은 2차 세계대전 이후 전 세계 산업 공학과 경영 과학(OR)을 통째로 갈아엎은 20세기 최고의 발명품 중 하나다. 자원은 항상 부족하고 욕망은 항상 무한한 인간 세상에서, 가장 낭비 없이 톱니바퀴를 맞물리게 하는 마법의 수식이었다.

결론적으로 딥러닝이 활개 치는 오늘날에도 머신러닝은 수리 최적화를 이기지 못한다. 인공지능이 "내일 우산이 100개 팔릴 것이다"라고 예측(Prediction)할 수는 있지만, "그 100개의 우산을 만들기 위해 A공장과 B공장을 몇 대 몇으로 돌려야 가장 비용이 적게 드는가?"라는 처방(Prescription)은 오직 선형 프로그래밍과 심플렉스법만이 완벽한 정답(Global Optimum)을 보장하기 때문이다. 기술사는 AI의 예측 결과를 이 최적화 솔버에 태우는 '예측-처방 파이프라인'을 그릴 줄 아는 통찰을 가져야 한다.

📢 섹션 요약 비유: 딥러닝이 일기예보를 맞추는 '기상청'이라면, 선형 프로그래밍은 그 날씨를 보고 우산과 장화를 전국 매장에 10원도 손해 안 보고 완벽하게 배달시키는 무결점 '물류 센터장'이다.

📌 관련 개념 맵

상위 개념: 수리 최적화 (Mathematical Optimization), 경영 과학 (Operations Research)
하위 개념: 목적 함수 (Objective Function), 제약 조건 (Constraints), 슬랙 변수 (Slack Variable)
연결 개념: 정수 계획법 (IP), 내부점 법 (Interior Point Method), Gurobi 솔버

👶 어린이를 위한 3줄 비유 설명

1만 원으로 떡볶이와 탕수육을 가장 배부르게 사 먹으려고 해요.
심플렉스 알고리즘은 가능한 모든 메뉴 조합을 다 먹어보는 바보 같은 짓을 하지 않아요.
무조건 "떡볶이만 다 샀을 때"나 "탕수육만 다 샀을 때"처럼 그래프의 가장 뾰족한 끝점(꼭짓점)만 몇 개 톡톡 찔러보면, 그중에 100% 진짜 정답이 있다는 걸 알려주는 수학 천재랍니다!