선형계획·수송·할당 문제로 설계하는 운영 최적화

운영 제약을 목적함수와 제약식으로 옮기는 방법

생산량, 운송 물량, 작업자 배치처럼 서로 맞물린 의사결정은 감각적인 우선순위만으로 일관되게 처리하기 어렵다. 선형계획(Linear Programming, LP), 수송 문제(Transportation Problem), 할당 문제(Assignment Problem)는 이 문제를 목적함수와 제약식으로 표현해 비용 최소화 또는 효용 최대화를 구하는 방법이다.

LP는 선형 목적함수와 선형 제약식으로 최적화 문제를 구성하며, 연속 변수를 중심으로 다룬다. 심플렉스나 내점법처럼 범용적인 해법을 적용할 수 있고, 정수 조건이 필요한 경우에는 혼합정수계획으로 확장한다.

수송 문제는 여러 공급지에서 여러 수요지로 물량을 보내는 비용 최소화 문제다. 네트워크 흐름의 특수형으로 볼 수 있으며, 공급과 수요가 맞지 않을 때는 더미 노드를 추가해 비균형 상태를 다룬다.

할당 문제는 작업과 자원을 1:1로 연결하는 문제다. 총 비용을 줄이거나 효용을 높이는 것이 목적이며, 헝가리안 알고리즘은 O(n^3) 복잡도로 해를 구한다. 전이행계수 구조에서는 LP 이완으로도 정수해가 보장된다.

모델을 풀기 전에 맞춰야 할 조건

모형의 결과는 입력 데이터와 제약식의 품질을 넘을 수 없다. 수요·공급·비용 매핑을 먼저 확인하고, 단위와 스케일을 일치시켜야 한다. 결측치와 이상치도 이 단계에서 처리한다.

정식화에서는 의사결정변수, 목적함수, 수지균형·용량·금지·강제·SLA 제약을 명확히 둔다. 이후 차원, 부호, 경계 조건을 점검하고 테스트 인스턴스로 최적해가 재현되는지 확인한다.

현업 규칙은 하드 제약과 소프트 제약으로 나누는 편이 낫다. 반드시 지켜야 하는 조건은 하드 제약으로 두고, 조정 가능한 조건은 벌점 비용으로 모델링하면 해가 없어진 상황에서도 유연성을 확보할 수 있다. 우선순위, 역량 적합, 시간창 같은 규칙은 추가 제약이나 다목적 가중 합수로 반영한다.

문제 구조에 맞는 해법 선택

LP는 해석이 필요한 경우 심플렉스를, 대규모 안정성이 필요한 경우 내점법을 선택할 수 있다. 혼합정수계획이 필요한 모델에는 Branch-and-Bound 또는 Branch-and-Cut이 사용된다.

수송 문제는 Northwest나 Vogel 방식으로 초기해를 만들고, MODI로 개선할 수 있다. 규모가 커지면 네트워크 심플렉스를 활용한다.

할당 문제는 헝가리안 알고리즘이 기본 선택지다. 다만 부가 제약이 많아지면 MIP나 라그랑지안 휴리스틱을 함께 사용해야 한다.

⤢✕

물류·생산·인력 운영에서의 활용

물류와 유통에서는 공장→센터→매장으로 이어지는 다단계 수송비를 줄이고, 라스트마일 구역 할당이나 재고 재분배에 적용할 수 있다. 제조 환경에서는 제품-라인 생산계획, 작업자-설비 할당, 셋업 시간과 캠페인 제약을 함께 다룬다.

서비스 운영에서는 콜센터 교대편성, 기술자와 작업 요청의 매칭, 현장 방문 루트와 결합한 배정에 사용된다. 조달과 구매에서는 공급자-품목-물량 분할, 빈티지·품질 제약, 운임 테이블에 따른 래인 최적화가 대상이 된다.

ERP, WMS, TMS, HRIS와는 배치 또는 API로 연계할 수 있다. 배포 후에는 비용, OTIF, 가동률을 KPI로 삼아 시뮬레이션과 시나리오 생성을 반복하고, 모델을 재보정·재학습한다. 모델과 데이터의 버전, 민감도·듀얼가격 리포트, 변경 이력도 함께 관리해야 감사 추적성을 확보할 수 있다.

성능과 운영 특성의 차이

항목	LP(범용)	수송 문제	할당 문제
성능	대규모는 내점법 유리, 혼합정수화 시 급증	네트워크 특화로 빠름, MODI/네트워크 심플렉스	헝가리안 O(n^3)로 안정적
확장성	다목적·복합 제약 유연, MIP 시 난이도↑	다단계·용량·시간창 추가 시 MIP 혼용 필요	부가 제약 많으면 MIP 전환 필요
일관성	정형 리포트·민감도 분석 우수	균형/더미 노드로 구조적 일관성	완전매칭 구조로 해의 정수성 보장
안정성	스케일링·사전처리 필요	비용 구조 왜곡 시 퇴화 주의	코스트 타이 처리·벌점 설계 중요
운영 편의	범용 모델 템플릿 재사용성 높음	표준 테이블(공급·수요·비용)로 운용 용이	비용 행렬 기반 UI로 현업 친화

현실성을 유지하면서 계산 가능하게 만드는 법

단가, 거리, 시간창의 단위는 일관되게 맞추고 0/음수 비용은 금지한다. 이상치는 윈저라이징으로 다루며, 수요와 공급이 비균형일 때는 더미 노드와 벌점 비용으로 현실적인 완화 조건을 둔다.

강한 비선형 또는 불연속 비용은 구간 선형화로 근사할 수 있다. 이때 최적성 손실과 계산시간 사이의 절충이 발생한다. 라우팅과 스케줄링을 함께 풀어야 한다면 할당→경로의 2단계 접근으로 계산 부하를 분리할 수 있다.

시간 제한과 MIP 갭 허용 설정은 SLA 준수에 사용하고, 긴급 배치에는 휴리스틱 초기해를 적용한다. 반복 계산에서는 Warm start, 프리솔브, 컷 전략으로 성능을 개선한다. 솔버는 상용 제품의 성능·지원과 오픈소스의 비용·확장성을 총소유비용 관점에서 비교하며, 배포는 컨테이너 기반으로 구성할 수 있다.

물류 총비용은 515% 절감되고 차량·창고 가동률은 1020%p 개선된 유사 산업 사례가 있다. 생산 계획에서는 변동비 38% 절감, 마감 준수율 510%p 향상이 제시된다. 할당은 O(n^3) 스케일로 처리할 수 있으며, 수송 네트워크 심플렉스는 수십만 아크까지 실무 적용 사례가 다수다.

비용만이 아니라 의사결정의 투명성과 일관성도 함께 얻을 수 있다. 듀얼가격과 민감도 분석은 결과를 설명하는 근거가 되고, 시나리오 기반 검토는 정책 변경 시 재계산과 협업을 돕는다.