빅엠법 (Big-M Method)

한 줄 정의: 인위변수에 매우 큰 벌점 M을 붙여 단체법이 실행가능해를 찾도록 하는 선형계획 해법입니다.

쉽게 풀면

≥ 제약이나 등식 제약이 있으면 단체법을 시작할 초기 해를 바로 만들기 어렵습니다. 그래서 임시로 '인위변수'를 넣어 출발점을 만들고, 목적함수에 이 변수 × 엄청나게 큰 수 M을 벌점으로 붙입니다. 최적화가 진행되면 벌점을 피하려고 인위변수가 자연히 0이 됩니다.

왜 중요한가

선형계획법 수업에서 단체법의 초기 기저해 문제를 해결하는 기본 방법으로 반드시 배웁니다. 또 정수계획 모형에서 '만약 ~이면 ~' 같은 논리 조건을 표현할 때도 큰 수 M을 쓰는 기법이 널리 쓰여 모형화 논문에서 자주 보입니다.

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

"설비 가동 여부를 나타내는 이진변수와 생산량을 Big-M 제약으로 연결하였다."

설비가 꺼져 있으면 생산량이 0이 되도록 큰 수 M을 이용해 제약을 만들었다는 뜻입니다.

조금 더 깊게 보면

최소화 문제라면 목적함수에 +M×(인위변수)를 더합니다. 최종 해에서 인위변수가 양수로 남으면 원래 문제는 실행불가능하다고 판단합니다. 컴퓨터로 풀 때 M을 너무 크게 잡으면 수치 오차가 생기고, 정수계획의 논리 제약에서도 M이 지나치게 크면 LP 완화가 느슨해져 계산이 느려지므로 가능한 한 작으면서도 올바른 값을 쓰는 것이 좋습니다.

주의할 점

2단계 단체법은 인위변수 제거를 별도의 1단계 문제로 처리해 M 값 선택 문제를 피한다는 점이 다릅니다. 선형계획의 빅엠법과 정수계획의 Big-M 제약은 같은 발상을 쓰지만 목적이 달라 구분해 이해해야 합니다.