선형계획법·심플렉스 알고리즘 쉽게 이해하기: 최적화의 기본 원리

핵심 메시지

• 선형계획법은 여러 제약 조건 아래에서 목표값(예: 매출)을 최대화하거나 최소화하는 최적화 기법이다.
• 가능한 모든 해가 이루는 영역의 최적값은 항상 그 영역의 꼭짓점(vertex)에서 나온다.
• 내부의 점이나 변(edge) 위의 점은 최댓값이 될 수 없으므로, 꼭짓점만 확인하면 된다.
• 변수와 제약이 많아지면 도형을 그릴 수 없고 모든 꼭짓점을 계산하는 무차별 대입은 너무 느려진다.
• 심플렉스 알고리즘은 원점에서 시작해 매출이 늘어나는 이웃 꼭짓점으로만 이동하며 최적점을 빠르게 찾는다.

쉽게 이해하기

영상은 항공편 스케줄, 창고 재고, 작물 선택처럼 우리가 흔히 접하는 최적화 문제들이 사실은 선형계획법의 영역이라고 설명한다. 예시로 쿠키 반죽 1kg당 3달러, 도넛 반죽 1kg당 2달러의 매출이 발생하고, 매출은 3×쿠키 + 2×도넛으로 계산된다고 가정한다.

무작정 많이 만들 수는 없다. 밀가루가 10kg뿐이고, 쿠키 반죽 1kg은 밀가루 0.4kg, 도넛 반죽 1kg은 0.5kg을 쓰기 때문이다. 이 제약을 그래프로 그리면 실행 가능한 조합들이 노란색 영역을 이루고, 그 모서리들이 꼭짓점(vertex)이 된다.

각 꼭짓점의 매출을 계산해 보면 원점(0,0)은 0, 쿠키만 25kg 만들 때 75, 도넛만 20kg 만들 때 40이 나온다. 변 위나 내부의 점은 항상 꼭짓점보다 매출이 낮거나 같으므로, 최댓값을 찾으려면 꼭짓점만 확인하면 충분하다.

제약이 밀가루뿐 아니라 설탕·초콜릿까지 늘어나면 영역의 모양이 복잡해지고 꼭짓점도 늘어난다. 변수가 3개(쿠키·도넛·브라우니)면 3차원 도형이 되고, 그 이상이면 아예 그림으로 볼 수조차 없다.

이때 등장하는 것이 심플렉스 알고리즘이다. 원점에서 시작해 단위당 매출이 가장 큰 방향으로 이웃 꼭짓점으로 이동하고, 더 이상 매출이 늘지 않을 때 멈춘다. 영상 속 예시에서는 쿠키·도넛을 각각 10kg씩 만드는 꼭짓점(10,10)에서 매출 50으로 최적해에 도달한다.

주요 인사이트

• 최적해가 꼭짓점에 있다는 성질 덕분에, 무한히 많은 실행 가능한 조합을 일일이 계산하지 않고 유한한 꼭짓점만 살펴봐도 된다.
• 방향 선택 기준(단위당 매출이 큰 쪽)이 여러 개여도, 매출이 늘어나는 쪽으로 계속 이동하면 결국 같은 최적 꼭짓점에 도달한다.
• 무차별 대입은 저차원에서는 가능하지만 고차원·다제약 문제에서는 비현실적이며, 심플렉스 같은 알고리즘이 실용성을 만든다.
• 두 번째 예시(변수 3개, 제약 5개)에서는 12개 꼭짓점 중 단 4번의 이동으로 최적점을 찾아, 알고리즘의 효율성을 보여준다.

자주 묻는 질문

관련 AI 소식