심플렉스법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

심플렉스법(simplex method)은 선형계획법에서 최적해를 구하는 알고리즘으로, 1947년 미국의 수리경제학자인 조지 단치히가 고안하였다. 이 방법은 최악의 경우에는 지수 시간이 걸리지만, 평균적으로 매우 빠르게 작동하기 때문에 널리 쓰인다. 이후에 최악의 경우에도 다항 시간을 보장하는 내부점 방법이 나왔으나 심플렉스법이 단순하고 더 빠른 경우가 있어 아직도 쓰이고 있다.

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

예제[편집]

이 문단의 내용출처가 분명하지 않습니다. 지금 바로 이 문단을 편집하여, 참고하신 문헌이나 신뢰할 수 있는 출처를 주석 등으로 표기해 주세요. 검증되지 않은 내용은 삭제될 수도 있습니다. 내용에 대한 의견이 있으시다면 토론 문서에서 나누어 주세요.

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

  1. AX1 + bX2 <= c ··· (1) 단, 상수는 모두 양수
  2. DX1 + EX2 <= f
  3. GX1 + HX2 <= I
  4. X1 >= 0 ··· (4) X1은 0이거나 양수가 되어야 한다. (음수가 되는 항은 존재하지 않는다)
  5. X2 >= 0 ··· (5) X2은 0이거나 양수가 되어야 한다. (음수가 되는 항은 존재하지 않는다)

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

  1. Max. P = QX1 + RX2 ··· (6) 단, 상수 c와 d는 양수

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

  • 다음 방정식의 해를 구한다.
    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값을 최대화 하는 해를 찾는다.