운송·할당·동적 계획법으로 자원 배분 최적화하기

자원 제약을 모델로 옮기는 방식

제조, 물류, 스케줄링에서는 비용·시간·자원 제약을 동시에 다뤄야 한다. Transportation Problem(TP), Assignment Problem(AP), Dynamic Programming(DP)은 이 제약을 각각 네트워크 흐름, 1:1 매칭, 순차 의사결정의 형태로 정식화한다.

TP는 여러 공급지에서 여러 수요지로 물량을 보낼 때 운송비 합계를 최소화하는 문제다. 공급·수요 제약 아래 연속변수를 두는 선형계획이며, 특수한 네트워크 구조를 갖는다. 총공급과 총수요가 같은 균형형과, 더미 노드가 필요한 비균형형으로 나뉜다. North-West나 Vogel 방식으로 초기해를 구한 뒤 MODI 또는 우수성 테스트로 해를 개선한다.

AP는 작업 n개와 자원 n개를 1:1로 연결해 총비용을 최소화하거나 효익을 최대화한다. 0–1 정수계획의 특수 사례지만, 비용 행렬을 입력으로 받는 헝가리안 알고리즘으로 O(n^3)에 해결할 수 있다. 행이나 열이 부족할 때는 더미 행·열로 정사각 행렬을 만들며, 제약이 더해지면 이진 제약을 포함한 MIP 모델로 옮긴다.

DP는 단계별 의사결정을 부분문제로 분리해 최적 부분구조와 중복 부분문제를 활용한다. 메모이제이션 또는 탭ulation으로 다항 또는 준다항 시간에 접근할 수 있으며, 배낭 문제, 최단경로, 시계열 재고, 설비 교체 시점에 적용된다. 구현은 상태 정의, 전이함수, 경계조건, 해 복원의 순서로 설계한다.

모델은 목적함수보다 데이터 구조에서 먼저 흔들린다

TP와 AP의 목적은 대개 비용의 합을 최소화하는 데 있고, DP는 재귀적으로 누적 보상을 최대화하는 형태를 취한다. 제약도 다르다. TP에는 공급·수요 보존 조건이, AP에는 각 행과 열의 합이 1이 되는 조건이, DP에는 상태 전이와 용량·기한 제한이 들어간다.

입력 데이터도 모델에 맞아야 한다. TP와 AP는 비용·용량을 행렬로 다루고, DP는 상태 공간과 전이 비용을 다룬다. 비용 이상치, 누락값, 공급·수요 불균형을 탐지하는 규칙을 먼저 정하고, 더미 노드와 패널티 비용으로 데이터 정합성을 맞춘다.

해를 낸 뒤에는 보존 제약 충족 여부를 확인하고, 이중변수인 그림자 가격을 검토한다. 감도 분석은 비용 변동을 어느 범위까지 수용할 수 있는지 파악하는 데 사용한다.

문제 구조에 따라 알고리즘을 바꾼다

TP는 Vogel 등의 초기해를 O(mn)에 구한 뒤 MODI 개선을 반복한다. 대규모 문제에서는 네트워크 심플렉스나 LP 솔버가 적합하다. 다원가, 시간창, 고정비·개시비가 들어가면 MIP로 확장하며, 불확실성이 있으면 로버스트 또는 스톡스틱 모델을 고려한다.

AP는 헝가리안 알고리즘이 O(n^3)으로 안정적으로 작동한다. 희소 구조이거나 추가 제약이 있으면 MIP 전환이 필요하다. 다대다 배정, 시차, 교대, 휴일 제약도 사이드 제약을 둔 MIP 형태로 다룬다.

DP의 복잡도는 O(상태×전이)다. 상태 차원이 늘면 차원의 저주가 발생할 수 있어 상태 축소나 근사가 필요하다. 다중 상태와 확률 전이는 MDP로 확장할 수 있고, 할인 보상과 정책 반복은 강화학습과 연결된다.

물류부터 IT 운영까지의 적용 범위

물류와 제조에서는 TP로 공장, DC, 소매점을 잇는 최소 운송비 네트워크를 설계한다. 수요·공급·운임을 넣으면 발송량을 해로 얻고, 노선 계획과 비용을 출력할 수 있다. AP는 라인별 작업자 배치, 기계와 작업의 매칭, 품질 등급별 테스트 장비 할당에 쓰인다. DP는 수요 예측 분포를 반영한 다기간 생산·재고 결정과 예방정비 주기 최적화에 맞는다.

서비스와 IT 운영에서도 같은 구조가 나타난다. TP는 클라우드 리전 간 데이터 전송·스토리지 비용을 줄이는 라우팅에, AP는 티켓과 엔지니어의 매칭 또는 배치 작업과 서버 슬롯의 할당에 적용된다. DP는 캐시 용량 배분과 리스크·성과 균형을 고려한 점진적 롤아웃 단계 설계에 사용할 수 있다.

프로젝트와 인사 영역에서는 AP로 프로젝트와 스킬을 연결하면서 가용시간 제약을 함께 고려한다. DP는 교육 커리큘럼의 단계별 투자나 기간별 예산 배분처럼 연속된 선택이 필요한 문제를 다룬다.

입력에서 운영 반영까지의 흐름

⤢✕

데이터 파이프라인은 ETL로 자동화하고, 시나리오별 배치 실행 결과는 API로 제공할 수 있다. 운영 환경에는 실패 복구, 불가능해 탐지, 휴리스틱 기반 대안 생성을 넣어야 한다.

식과 제약으로 보는 문제 구조

TP에서는 공급 (s_i), 수요 (d_j), 비용 (c_{ij})를 입력으로 받고 발송량 (x_{ij})를 결정한다. 목적은 (\Sigma c_{ij}x_{ij}) 최소화다. 공급 제약은 각 공급지에서 (\Sigma_j x_{ij} \le s_i), 수요 제약은 각 수요지에서 (\Sigma_i x_{ij} \ge d_j)로 둔다. 모든 변수는 비음수이며, 균형형에서는 등호를 사용하고 비균형형에서는 더미 노드를 추가한다. 초기해를 만든 뒤 폐루프 개선을 반복해 MODI 최적성 조건을 만족하면 종료한다.

AP는 비용 행렬 (C(n×n))과 이진 의사결정 변수 (y_{ij} \in {0,1})를 둔다. (\Sigma C_{ij}y_{ij})를 최소화하면서 각 행과 열에 대해 각각 (\Sigma_j y_{ij}=1), (\Sigma_i y_{ij}=1)을 만족시킨다. 헝가리안 알고리즘은 행·열 최소값을 감산하고, 0을 커버하며, 필요한 조정을 반복한 뒤 배정을 복원한다.

DP는 상태 (S_t), 결정 (a_t), 전이 (f(S_t,a_t)), 보상 (r_t(S_t,a_t)), 경계조건으로 구성한다. 점화식은 (V_t^(S)=\max/\min\ \text{over}\ a{r_t+V_{t+1}^(S')}) 형태다. 순방향 또는 역방향 탭ulation으로 구현할 수 있으며, 라운딩·도메인 축약으로 상태를 줄이거나 그리디·롤링호라이즌 근사를 적용한다.

전용 알고리즘과 범용 솔버 사이의 선택

헝가리안 알고리즘과 MODI 같은 전용 알고리즘은 문제 구조가 정형적일 때 높은 성능을 낸다. 대신 제약이 추가되면 적용하기 어렵다. LP와 MIP 같은 범용 솔버는 모델 확장이 쉽지만, 대형 인스턴스에서는 MIP 가분해와 컷이 필요하다.

속도와 결정 품질도 함께 판단해야 한다. 실시간 처리가 필요하면 휴리스틱이나 라운딩을 사용하고, 정기 일괄 최적화로 기준계획을 산출할 수 있다. 단일 시나리오 대신 로버스트 또는 확률 제한 모델을 쓰면 과잉보수화될 위험이 있으므로 서비스 수준 제약과 패널티 비용을 교차 검토한다.

단위, 환율, 캘린더 정합성은 표준화하고 이상치 감지 후 수동 승인 워크플로우를 연결한다. 이 운영 규칙이 없으면 모델이 맞더라도 결과의 신뢰성을 유지하기 어렵다.

문제별 운영 특성

항목	Transportation Problem	Assignment Problem	Dynamic Programming
성능(복잡도)	네트워크 심플렉스 준선형~다항, MODI 실무 고속	O(n^3) 안정	상태×전이, 차원의 저주 가능
확장성	대규모 노드/호 가능, 다중 제약 시 MIP	수천 규모도 실용	상태 축소·근사 필수
일관성(최적 보장)	선형·볼록 시 보장	전용 알고리즘으로 보장	점화식·가정 만족 시 보장
안정성(데이터 민감)	운임 변동에 민감, 감도 분석 필요	비용 행렬 잡음에 중간	전이·보상 추정 오차에 민감
운영 편의	데이터 파이프라인 표준화 용이	행렬 입력 간단	모델링 자유도 높으나 유지 난이도 높음

물류·배차 비용은 사례 기반 범위에서 515% 절감되고, OTIF(정시납품)는 28%p 개선될 수 있다. 설비·인력 가동률은 512% 향상되며, 자동화를 기준으로 계획 산출 시간은 5090% 단축된다. 수치 효과와 함께 의사결정의 일관성과 투명성이 높아지고, 시나리오 비교가 쉬워진다. 불가능해와 병목을 조기에 찾아 운영 리스크를 낮추고 협업 효율을 높이는 효과도 기대할 수 있다.

정형 문제에서 순차 의사결정으로 확장하기

초기에는 TP와 AP처럼 구조가 분명한 문제에 전용 알고리즘을 적용하고 데이터를 표준화한다. 이후 사이드 제약과 불확실성을 반영해야 하면 MIP와 로버스트 모델로 확장한다. 다기간·순차 의사결정에는 DP와 롤링 호라이즌을 결합한다.

품질 보증에는 벤치마크 인스턴스와 합성 데이터를 이용한 회귀 테스트를 두고, 감도·스트레스 테스트를 정례화한다. ETL 스케줄러, 컨테이너화, 파라미터·로그 버전관리를 운영 체계에 포함하며, 실패 시 사용할 휴리스틱 폴백 규칙도 지정한다.