단체법 (Simplex Method)

한 줄 정의: 선형계획법 문제의 실행가능영역의 꼭짓점들을 따라 이동하며 최적해를 찾는 대표적인 풀이 알고리즘입니다.

쉽게 풀면

선형계획법 문제를 그림으로 그리면 여러 개의 꼭짓점을 가진 다각형(또는 다면체) 모양의 실행가능영역이 나타납니다. 최적해는 항상 이 꼭짓점 중 하나에 있다는 성질을 이용해, 단체법은 한 꼭짓점에서 목적함수가 더 좋아지는 이웃 꼭짓점으로 계속 옮겨가며 답을 찾습니다. 더 이상 개선되는 이웃이 없으면 그 지점이 최적해입니다. 변수가 많아 그림으로 그릴 수 없는 경우에도 같은 원리를 계산적으로 적용합니다.

왜 중요한가

단체법은 선형계획법의 표준 풀이 알고리즘으로, 생산계획·수송문제·자원배분 등 다양한 산업공학 최적화 문제를 실제로 계산 가능하게 만들어주는 핵심 도구입니다. 이후 등장한 여러 최적화 알고리즘과 상용 솔버의 기초가 되었습니다.

논문에서는 이렇게 쓰입니다

"본 연구의 선형계획 모형은 단체법(Simplex Method)을 이용하여 최적 생산배합을 도출하였다."

여러 제품의 생산량을 결정하는 선형계획 문제를 단체법으로 풀었다는 뜻입니다.

"단체법 기반 알고리즘을 통해 각 반복(iteration)마다 목적함수 값이 단조 증가함을 확인하였다."

단체법이 꼭짓점을 옮겨갈 때마다 해가 점점 개선되는 과정을 검증했다는 의미입니다.

조금 더 깊게 보면

단체법은 표준형으로 변환한 문제에 기저해(basic feasible solution) 개념을 적용해 반복적으로 개선하는 방식으로 동작합니다. 최악의 경우 이론적 계산 시간이 지수적으로 늘어날 수 있다는 사실이 알려져 있지만, 실제 문제에서는 대체로 효율적으로 작동하는 것으로 알려져 있습니다. 이후 다항시간 알고리즘인 내점법(interior point method) 등도 대안으로 함께 사용됩니다.

주의할 점

단체법은 선형계획법에 특화된 방법으로, 정수 제약이나 비선형 요소가 있는 문제에는 그대로 적용되지 않으며 별도의 확장 기법이 필요합니다.