2단계 단체법 (Two-Phase Simplex Method)

한 줄 정의: 1단계에서 인위변수 합을 최소화해 실행가능 기저해를 찾고, 2단계에서 원래 목적함수를 최적화하는 단체법입니다.

쉽게 풀면

단체법을 시작할 출발점이 없을 때 쓰는 방법입니다. 1단계에서는 원래 목표는 잠시 접어 두고 '임시로 넣은 인위변수들을 모두 0으로 만들기'만 목표로 풉니다. 성공하면 그 결과를 출발점 삼아 2단계에서 원래 목적함수를 최적화합니다.

왜 중요한가

빅엠법과 함께 단체법의 초기해 문제를 다루는 표준 방법이며, 큰 수 M을 쓰지 않아 수치적으로 안정적입니다. 선형계획 소프트웨어가 실행불가능성을 판정하는 원리를 이해하는 데도 도움이 됩니다.

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

"1단계 문제의 최적 목적함수 값이 0보다 커서 해당 생산계획 모형이 실행불가능함을 확인하였다."

인위변수를 모두 0으로 만들 수 없었으므로 제약을 모두 만족하는 해가 없다는 뜻입니다.

조금 더 깊게 보면

1단계 목적함수는 인위변수들의 합을 최소화하는 것입니다. 1단계 최적값이 0이면 실행가능 기저해를 얻은 것이고, 양수면 원 문제는 실행불가능합니다. 1단계가 끝났는데 값이 0인 인위변수가 기저에 남아 있으면 이를 기저에서 빼내거나 중복 제약으로 처리하는 추가 절차가 필요합니다.

주의할 점

빅엠법은 벌점 M을 붙여 한 번에 풀고, 2단계 단체법은 문제를 두 단계로 나누어 푼다는 점이 가장 가까운 항목과의 차이입니다. 두 방법 모두 (M이 충분히 크면) 같은 최적해에 도달하므로 해법의 차이를 결과의 차이로 오해하지 않아야 합니다.