최적화(자원 배분) 문제 - 엑셀의 해 찾기(solver)

제가 교육 업무 현업에 있을 때 대략 다음과 같은 문제에 자주 맞닥드리게 되었습니다. 

상황 1. 연간 기본 교육 계획 수립

문제 

주어진 총 예산은 1,000만원이다. 교육 프로그램의 종류가 4가지가 있는데, 제일 비싼 것 A는 100만원, 그 다음 B가 60만원, 그 다음 C가 30만원, 가장 가벼운 프로그램 D는 20만원이다. 예산 1,000만원을 다 쓰는 범위 내에서 각 프로그램을 몇 회 씩 운영해야 할 지 계획을 세워라. 

단, 모든 프로그램은 모두 연간 2회 이상 운영해야 하고, 가장 비싼 프로그램은 최대 3회 이내에서 운영할 수 있고, 가장 가벼운 프로그램도 최대 30회 이내에서 운영해야 한다.

문제 분해

이런 문제가 전형적인 최적화 문제입니다. 즉, 목표치가 주어지고, 목표치와 몇 가지 제약 조건에 맞추어서 주어진 자원을 어떻게 배분하느냐의 문제이지요. 엑셀, 구글 시트, 리브레오피스의 캘크의 "해 찾기(solver)" 기능으로 답을 찾을 수 있습니다. 

• 목표: 연간 예산 총액 1,000만원에 맞추기
• 변수: A, B, C, D 프로그램의 운영 횟수 (각각 a, b, c, d라고 하겠습니다.)
• 제약 조건:
• a, b, c, d는 모두 정수(integer)이다.
• a, b, c, d는 모두 2 이상이다.
• a는 3 이하이다.
• d는 30 이하이다.
• 방정식: 100a + 60b + 30c + 20d = 1000 을 만족하는 미지수 a, b, c, d를 구하라. 
• 미지수가 여러 개인 다항식이기 때문에 일차 방정식이지만 해가 여러 개 존재한다. 
• 따라서, 주어진 목표값에 이르기 위한 입력값을 여러 가지로 변화시켜보는 목표 탐색 기법을 써야 한다.

엑셀의 해 찾기에 대입

엑셀 (2024년 8월 28일 현재, Microsoft 365 기준)의 '해 찾기'에 이 문제를 넣기 위해 아래와 같은 표를 만들었습니다. 

목표는 총합이 천만원(분홍색 E7)이 되는 것이고, 변수는 횟수(노란색 D열)이다.

목표 셀에 커서를 놓은 상태에서, 엑셀의 해 찾기를 실행합니다. 

• 제일 위에 E7이라고 지정한 것이 목표 셀입니다. 바로 밑에서 목표 지정값으로 10,000,000원을 주었습니다. 
• 중간에 변수들의 범위를 지정합니다. 운영 횟수, 즉 D3 ~ D6가 변수 부분입니다.
• 마지막으로, 특별히 제약 조건이 무엇인지 지정합니다. 예를 들면, 변수는 모두 정수이고, 2 이상이고 등 총 4가지 제약 조건이 들어가 있습니다. 

엑셀의 해 찾기 대화 상자

이렇게 해서 해 찾기를 실행하면, 아래와 같은 계산 결과가 나옵니다. 

해 찾기를 했더니 노란색 D열의 운영 횟수가 채워졌습니다.

이런 결과가 마음에 들지 않으면, 다시 해 찾기를 실행하거나, 제약 조건을 더 추가해서 실행하면 다른 해를 찾아줍니다.

상황 2. 팀간 예산 균등 배분

문제 

(네이버 지식인에 누군가 질문을 해서 풀어본 문제입니다.)

사무실 소모품(과자, 물티슈, 휴지 등)으로 10만원의 예산을 썼다. 사후에 이것을 3개의 팀에 되도록 공평하게 부담시키려고 한다. 즉, 대략 3.3만원 내외에서 이미 써버린 항목들을 각 팀에 배분해야 한다. 어떤 항목을 어떤 팀에 배분해야 하는가?

예산 균등 배분 문제: 노란색에 팀 번호가 들어가면, 해당 팀의 배분액에 금액이 들어간다. 각 팀에 최대한 비슷하게 예산이 배분되어야 한다.

문제 분해

이 문제는 앞의 문제와는 달리 명확한 목표가 잘 안 보입니다. "3개 팀에 공평하게 배분"한다는 것을 어떻게 단일한 목표값으로 치환할 수 있을까요? 

제가 쓴 방법은 "세 팀의 예산 배분액의 표준편차를 최소화"하는 단일한 목표를 설정함으로써 문제를 단순화했습니다!

• 목표: 3개 팀 예산 배분액 합의 표준편차가 최소가 되도록 한다. (아래 그림에서 E12, F12, G12의 표준편차가 최소가 되도록)
• 변수: 각 항목별 팀 배정 번호(내역)
• 제약 조건:
• 모든 번호는 정수이다.
• 모든 번호는 1 이상이다.
• 모든 번호는 3 이하이다.

표준편차의 최소화라는 단일한 목표를 세웠습니다.

엑셀의 해 찾기 실행

목표 셀인 C13에 커서를 두고, 해 찾기를 실행합니다. 

해 찾기 대화상자. 목표값을 최소로 하는 해를 찾는다. 해법은 Evolutionary를 사용

• 목표 셀은 C13 (3개 팀 배분액의 표준편차)입니다. 이번에는 목표 값을 지정한 것이 아니고, 목표값이 최소가 되도록 요구하였습니다.
• 변수는 각 항목별 팀 배정 번호인 D3 ~ D11 노란색 부분이죠.
• 제약사항은 변수들이 정수로서 1, 2, 3 중에 하나의 값을 갖도록 하였습니다. 
• 해법 선택: 이번에는 해를 찾는 방법에 '단순 LP'나 'GRG 비선형' 대신에 'Evolutionary'를 선택했습니다. 각 방법의 차이는 수학적으로 좀 복잡하니 여기서는 다루지 않겠습니다.

계산 결과

표준편차가 289라는 작은 값으로 각 팀에 예산이 배분되었다.

위 그림과 같이 표준편차가 289라는 상당히 작은 값으로, 세 개의 팀에 3만3천5백원, 3만3천5백원, 3만3천원으로 거의 비슷하게 예산이 배분되었습니다. 

예시에 사용된 엑셀 파일: 예산 균등 배분 - 해 찾기.xlsx

해 찾기 기능을 이용하면, 이외에도 경영상에 부딫히는 수많은 최적화 문제, what-if 문제를 해결할 수 있습니다. 여러분의 문제 해결에도 써보시기 바랍니다.