단체법 (알고리즘)

선형계획법에서 단체법(單體法, 영어: simplex method 심플렉스 메소드^[*])은 선형계획 문제의 최적해를 구하는 알고리즘이다. 이 방법은 최악의 경우에는 지수 시간이 걸리지만, 평균적으로 매우 빠르게 작동하기 때문에 널리 쓰인다. 이후에 최악의 경우에도 다항 시간을 보장하는 내부점 방법이 나왔으나 단체법이 단순하고 더 빠른 경우가 있어 아직도 쓰이고 있다.

단체법은 임의의 가능해(초다면체의 정점)로부터 탐색을 시작한다. 가능해라면 어떤 해이든 상관없다. 현재의 가능해와 인접하면서 더욱 최적에 가까운 가능해로 옮겨가면서 탐색을 진행한다. 더 이상 옮겨갈 해가 없으면 최적을 찾은 것이다. 해가 존재할 수 없는 경우는 여러가지인데, 목적함수가 발산하는 경우, 순환하는 경우가 있다. 퇴행성으로 동일한 목적값을 가지는 다수의 해가 존재할 수도 있다.

예제

다음과 같은 X1과 X2에 관한 제약조건이 있고,

1. AX₁ + bX₂ <= c ··· (1) 단, 상수는 모두 양수
2. DX₁ + EX₂ <= f
3. GX₁ + HX₂ <= I
4. X₁ >= 0 ··· (4) X1은 0이거나 양수가 되어야 한다. (음수가 되는 항은 존재하지 않는다)
5. X₂ >= 0 ··· (5) X2은 0이거나 양수가 되어야 한다. (음수가 되는 항은 존재하지 않는다)

다음과 같은 목적함수 P가 있다고 가정하자.

1. Max. P = QX₁ + RX₂ ··· (6) 단, 상수 c와 d는 양수

이 때, 목적함수 Z 값을 최대화하는 해 (X₁, X₂)는 다음과 같은 방법으로 구할 수 있다.

• 다음 방정식의 해를 구한다.
  1. 식(1)와(과) 식(2)의 연립 방정식
  2. 식(1)와(과) 식(3)의 연립 방정식
  3. 식(1)와(과) 식(4)의 연립 방정식
  4. 식(1)와(과) 식(5)의 연립 방정식
  5. 식(2)와(과) 식(3)의 연립 방정식
  6. 식(2)와(과) 식(4)의 연립 방정식
  7. 식(2)와(과) 식(5)의 연립 방정식
  8. 식(3)와(과) 식(4)의 연립 방정식
  9. 식(3)와(과) 식(5)의 연립 방정식
  10. 식(4)와(과) 식(5)의 연립 방정식
• 위 10개 식에 대한 해 중에서 목적함수 P값을 최대화하는 해를 찾는다.

역사

1947년 미국의 수리경제학자인 조지 단치히가 고안하였다.