심플렉스 알고리즘 수학 원리: 선형계획법 최적해를 슬랙 변수와 가우스 소거로 찾는 법

핵심 메시지

• 심플렉스 알고리즘은 원점에서 출발해 수익을 늘리는 이웃 꼭짓점으로 옮겨가며, 더 이상 늘지 않을 때까지 반복해 선형계획법의 최적해를 찾는다.
• 먼저 실현가능영역·목적함수·제약을 세운다. 변수는 0 이상이어야 하고, 제약이 선형이라 두 점을 잇는 선분이 영역을 벗어나지 않아야 알고리즘이 작동한다.
• ≥ 제약은 양변에 -1을 곱해 ≤로 바꾸고, 등호 제약은 ≤와 ≥ 두 부등식으로 쪼갠다. 모든 제약을 ≤로 통일하면 매 단계에서 경우를 나눠 검사할 필요가 없어진다.
• 각 부등식에 슬랙 변수를 더해 등식으로 바꾸고 계수를 행렬로 만든 뒤, 첫 행에서 가장 큰 음수를 찾아 이동 방향을 정하고, 총량을 해당 열의 양수로 나눈 최소 비율로 이동 거리를 정한다.
• 가우스 소거(행 축소)로 행렬을 갱신해 좌표와 수익을 읽고, 첫 행에 음수가 없어질 때까지 반복한다. 쿠키·도넛 예시는 (10,10)에서 수익 50, 3변수 예시는 (9,9,4)에서 수익 22가 최적이었다.

쉽게 이해하기

영상은 심플렉스 알고리즘의 큰 그림에서 출발한다. 알고리즘은 원점에서 시작해 수익이 늘어나는 이웃 꼭짓점으로 이동하고, 더 이상 늘지 않는 곳에서 멈춘다. 이번 편은 그 과정의 수학적 디테일, 즉 행렬 위에서 실제로 무슨 계산이 일어나는지를 다룬다.

문제 설정부터 짚는다. 실현가능한 해들의 영역을 실현가능영역, 최대화하려는 식(여기서는 수익)을 목적함수, 나머지 조건을 제약이라 부른다. 변수는 음수가 될 수 없고, 제약은 선형이어야 한다. 두 점을 잇는 선분이 영역 밖으로 튀어나가면 알고리즘이 제대로 작동하지 않으며, 변수를 지수로 쓸 수도 없다.

다음은 표준형으로의 변환이다. 모든 제약을 ≤ 형태로 통일하는데, ≥ 제약은 양변에 -1을 곱해 부호를 뒤집고, 등호 제약은 ≤와 ≥ 두 부등식으로 쪼갠 뒤 ≥ 쪽을 다시 -1로 뒤집는다. 그다음 각 부등식에 슬랙 변수를 더해 등식으로 바꾼다. 예컨대 쓸 수 있는 밀가루 10kg 중 8kg만 썼다면 차이 2kg를 슬랙 변수가 채워 좌우변을 맞춘다. 계수와 총량을 행렬에 담고 첫 행에 -1을 곱해 준비를 마친다.

이동 규칙은 세 단계다. 먼저 첫 행에서 가장 큰 음수가 있는 열로 이동 방향을 정한다. 다음으로 총량을 그 열의 양수 값들로 나눈 비율을 모두 구해 가장 작은 값을 택하는데, 더 큰 값은 영역 밖이기 때문이다. 마지막으로 가우스 소거(행 축소)로 선택한 열을 1과 0들로 정리하면, 행렬에서 그 꼭짓점의 좌표와 그때의 수익을 바로 읽을 수 있다.

이 과정을 반복한다. 쿠키·도넛 예시에서는 원점에서 (0,10)으로 옮겨 수익 30을 얻고, 다시 (10,10)으로 옮겨 수익 50에 이르렀을 때 첫 행에 음수가 없어 종료했다. 도넛·쿠키·브라우니 세 변수를 x·y·z로 둔 예시에서는 (9,9,4)에서 수익 22가 최적이었다. 첫 행에 더 이상 음수가 없으면 어느 방향으로 가도 수익이 늘지 않으므로 그 점이 최적해다.

주요 인사이트

• 알고리즘은 '눈이 없다.' 어느 꼭짓점이 실현가능영역 안인지 볼 수 없으므로, 총량을 열의 양수로 나눈 비율을 모두 계산하고 가장 작은 값을 택해 영역을 벗어나지 않게 한다.
• ≤로의 통일과 슬랙 변수 도입은 알고리즘을 단순화하는 장치다. 부등호 방향에 따라 경우를 나누지 않아도 되게 하고, 부등식을 등식·행렬 연산으로 다룰 수 있게 만든다.
• 심플렉스의 핵심 반복은 사실상 가우스 소거다. 선택한 열을 1과 0들로 만드는 행 축소가 꼭짓점의 좌표와 그때의 수익을 행렬에서 바로 읽게 해준다.
• 종료 조건은 명확하다. 첫 행에 더 이상 음수가 없으면 어느 방향으로 가도 수익이 늘지 않는다는 뜻이므로 그 점이 최적해다.

자주 묻는 질문

관련 AI 소식