이 글에서는 엑셀(Excel)에서 정수 선형 계획법(Integer Linear Programming)을 해결하는 방법을 알아보겠습니다. 마이크로소프트 엑셀에서는 솔버(Solver) 추가 기능을 활용하면 정수 선형 계획 문제의 해답을 빠르고 쉽게 구할 수 있습니다. 이번 포스팅에서는 간단하고 명확한 단계별 과정을 통해 실습 방법을 설명하고, 마지막 섹션에서는 혼합 정수 선형 계획법(Mixed-Integer Linear Programming) 문제 예시도 함께 다룹니다. 그럼 바로 시작해 보겠습니다.
연습용 파일 다운로드
아래 링크에서 연습용 워크북을 내려받아 직접 따라 해볼 수 있습니다.
정수 선형 계획법이란 무엇인가?
정수 선형 계획법은 정수(integer) 변수와 선형 목적 함수, 그리고 선형 방정식으로 구성된 수학적 최적화 기법입니다. 선형 계획법을 활용하면 주어진 조건 아래에서 문제의 최솟값 또는 최댓값을 도출할 수 있으며, 제한된 자원을 가장 효율적으로 배분하는 방법을 찾는 데 유용한 도구입니다.
모든 선형 계획법에는 다음과 같은 핵심 요소가 포함됩니다.
- 결정 변수(Decision Variables): 목적 함수를 최소화하거나 최대화하기 위해 우리가 결정하는 변수입니다.
- 목적 함수(Objective Function): 결과와 변수 사이의 관계를 나타내며, 결정 변수의 값을 구하는 기준이 되는 함수입니다.
- 제약 조건(Constraints): 가능한 해들이 반드시 만족해야 하는 여러 조건을 나타내는 함수입니다.
이번 글에서는 정수 선형 계획법 외에도 연속 변수와 정수 변수가 동시에 사용되는 혼합 정수 선형 계획법의 예시도 살펴보겠습니다.
엑셀에서 정수 선형 계획법을 푸는 단계별 방법
단계별 절차를 설명하기 위해 아래 예제 문제를 사용하겠습니다. 먼저 문제를 꼼꼼히 읽고 제약 조건과 목적 함수를 직접 도출해 보세요.
어떤 기계 하나가 서로 교환 가능한 두 가지 제품을 생산한다고 가정합니다. 기계의 일일 생산 능력은 첫 번째 설정에서 제품 1을 최대 20개, 제품 2를 최대 10개까지 생산할 수 있습니다. 반면, 기계를 재조정하면 하루에 제품 1을 최대 12개, 제품 2를 최대 25개까지 생산할 수 있습니다. 시장 분석에 따르면 두 제품의 합산 일일 최대 수요는 35개입니다. 두 제품의 개당 이익이 각각 $10과 $12라면, 어느 기계 설정을 선택해야 할까요?
1단계: 문제 분석 및 데이터 세트 만들기
- 먼저 주어진 정수 선형 계획 문제를 정확히 이해하고 분석합니다.
- 문제를 분석하면 다음과 같은 요소들을 도출할 수 있습니다.
결정 변수:
- X1: 제품 1의 생산량
- X2: 제품 2의 생산량
- Y: 첫 번째 설정을 선택하면 1, 두 번째 설정을 선택하면 0
목적 함수:
목적 함수는 다음과 같습니다.
Z = 10X1 + 12X2
제약 조건:
위 문제에서 크게 3가지 제약 조건을 찾을 수 있습니다.
- X1 + X2 <= 35
두 제품의 합산 일일 최대 수요가 35개이기 때문입니다. - X1 - 8Y <= 12
이 조건은 제품 1에 관한 제약입니다. - X2 + 15Y <= 25
이 조건은 제품 2에 관한 제약입니다. - Y = {0, 1}
Y의 값은 0 또는 1만 가질 수 있습니다. - X1, X2 >= 0
제품의 생산량은 음수일 수 없습니다.
- 다음으로, 위의 제약 조건, 함수, 변수를 고려하여 아래 그림과 같은 데이터 세트를 작성합니다. 필요에 따라 자유롭게 수정해서 사용하세요.
2단계: 엑셀에서 솔버(Solver) 추가 기능 활성화
- 다음으로 엑셀에서 솔버 추가 기능을 로드해야 합니다. 이미 활성화되어 있다면 바로 3단계로 넘어가세요.
- 파일(File) 탭을 클릭합니다.
- 화면 왼쪽 하단의 옵션(Options)을 선택합니다.
- 엑셀 옵션(Excel Options) 창이 열립니다.
- 엑셀 옵션 창에서 추가 기능(Add-ins)을 선택합니다.
- 그런 다음 엑셀 추가 기능(Excel Add-ins)을 선택하고, 하단의 관리(Manage) 상자에서 이동(Go)을 클릭합니다.
- 추가 기능 대화상자가 나타납니다.
- Solver 추가 기능(Solver Add-in)에 체크하고 확인(OK)을 누릅니다.
- 이제 데이터(Data) 탭의 분석(Analysis) 섹션에서 솔버(Solver) 기능을 확인할 수 있습니다.
3단계: 제약 조건과 목적 함수의 계수 입력
- 세 번째로, 데이터 세트에 제약 조건과 목적 함수를 채워 넣습니다.
- 여기서는 제약 조건과 목적 함수의 계수(coefficients)를 입력합니다.
- 첫 번째 제약 조건은 X1 + X2 <= 35입니다. 즉, 첫 번째 설정이 선택된 경우 두 제품 생산량의 합이 35 이하가 되어야 한다는 의미입니다.
- 따라서 X1의 계수는 1, X2의 계수는 1입니다.
- 또한 이 식은 첫 번째 설정을 나타내므로 Y의 계수는 -8이 됩니다.
- 부등호는 <=이고, 한계값은 35입니다.
- 같은 방식으로 모든 제약 조건의 계수를 채워 넣습니다.
- 그다음 E10 셀을 선택하고 아래 수식을 입력합니다.
=SUMPRODUCT($B$6:$D$6,B10:D10)
이 수식에서는 SUMPRODUCT 함수를 사용하여 결정 변수와 해당 제약 조건 계수를 곱한 후 모두 더합니다. 즉, B6 셀 × B10 셀, C6 셀 × C10 셀, D6 셀 × D10 셀을 계산한 뒤 그 결과를 모두 합산합니다.
- Enter 키를 누른 후 채우기 핸들(Fill Handle)을 아래로 드래그합니다.
- 이제 B16~C16 셀에 목적 함수의 계수를 입력합니다.
- 이 예제의 목적 함수는 Z = 10X1 + 12X2입니다.
- 다시 E16 셀을 선택하고 아래 수식을 입력합니다.
=SUMPRODUCT($B$6:$D$6,B16:D16)
- 마지막으로 Enter 키를 누르면 계수와 수식이 모두 입력된 데이터 세트를 확인할 수 있습니다.
4단계: 솔버 매개 변수 입력
- 4단계에서는 데이터 탭으로 이동하여 분석 섹션에서 솔버를 선택합니다. 솔버 매개 변수(Solver Parameters) 창이 열립니다.
- 목표 값 설정(Set Objective) 상자에는 목적 함수 값이 들어갈 셀을 입력합니다.
- 여기서는 $E$16을 입력했습니다.
- 우리는 최대 결과를 구하려고 하므로 최대값(Max)을 선택합니다.
- '변경할 변수 셀(By Changing Variable Cells)'에는 결정 변수가 있는 $B$6:$D$6을 입력합니다.
5단계: 제약 조건 추가
- 5단계에서는 제약 조건을 추가합니다.
- 변수가 이진수(binary)인지 정수(integer)인지, 그리고 제약 조건의 관계식을 지정해야 합니다.
- 이를 위해 추가(Add) 버튼을 클릭하면 제약 조건 추가(Add Constraint) 대화상자가 열립니다.
- 제약 조건 추가 창에서 셀 참조(Cell Reference) 상자에 $D$6을 입력하고 드롭다운 메뉴에서 bin(이진수)을 선택합니다.
- D6 셀은 0 또는 1의 값을 갖는 Y를 저장하며, 이는 이진수에 해당합니다. 그렇기 때문에 bin을 선택한 것입니다.
- 확인(OK)을 클릭해 진행합니다.
- 다시 추가(Add)를 클릭합니다.
- 이번에는 셀 참조 상자에 $E$10:$E$12를 입력하고, 드롭다운 메뉴에서 <= 기호를 선택한 뒤, 제약 조건 상자에 =$G$10:$G$12를 입력합니다.
- 그런 다음 확인을 클릭합니다.
- 다시 한번 솔버 매개 변수 창에서 추가를 클릭합니다.
- 이제 셀 참조 상자에 $B$6:$C$6을 입력하고 드롭다운 메뉴에서 int(정수)를 선택합니다.
- B6과 C6 셀은 정수인 X1과 X2의 값을 저장합니다.
- 다시 확인을 클릭합니다.
6단계: 해결 방법 선택
- 6단계에서는 '해결 방법 선택(Select a Solving Method)' 섹션에서 Simplex LP를 선택하고 풀기(Solve)를 클릭합니다.
- '제약 조건이 없는 변수를 음수가 아닌 값으로 설정(Make Unconstrained Variables Non-Negative)' 옵션에 체크되어 있는지 확인하세요.
- 풀기를 클릭하면 솔버 결과(Solver Results) 창이 나타납니다.
- 거기서 확인을 선택합니다.
7단계: 정수 선형 계획법의 해답 확인
- 마침내 원하는 셀에서 최적해를 확인할 수 있습니다.
- 이 예제에서는 두 번째 기계 설정이 가장 좋은 결과를 제공합니다.
8단계: 답안 보고서 생성
- 추가로 답안 보고서(answer report)를 생성할 수도 있습니다.
- 이를 위해 솔버 결과 창의 보고서(Reports) 섹션에서 답안(Answer)을 선택하고 확인을 클릭합니다.
- 마지막으로 새 시트에서 생성된 보고서를 확인할 수 있습니다.
엑셀에서 혼합 정수 선형 계획법 예제
이 섹션에서는 엑셀에서 혼합 정수 선형 계획법을 푸는 간단한 예제를 살펴보겠습니다. 아래 단계를 따라 하면 혼합 정수 선형 계획 문제도 쉽게 해결할 수 있습니다. 먼저 이 예제의 목적 함수와 제약 조건을 확인하세요.
목적 함수:
Z = 2.39X1 + 1.99X2 + 2.99X3 + 300Y1 + 250Y2 + 400Y3
제약 조건:
- X1 + X2 + X3 = 1000
- X1 - 400Y1 <= 0
- X2 - 550Y2 <= 0
- X3 - 600Y3 <= 0
여기서 X1, X2, X3는 정수이고, Y1, Y2, Y3는 이진수(0 또는 1)입니다. 또한 우리는 Z의 최솟값을 구해야 합니다.
아래 단계를 따라 예제 전체를 학습해 보겠습니다.
단계:
- 먼저 결정 변수, 제약 조건, 목적 함수의 계수를 저장할 데이터 세트를 만듭니다.
- 다음으로 목적 함수 변수들의 혼합 계수를 입력합니다.
- 세 번째로, 아래 그림과 같이 제약 조건 변수들의 계수를 입력합니다. 이때 합계(Total) 열은 비워 둡니다.
- 그다음 H10 셀을 선택하고 아래 수식을 입력합니다.
=SUMPRODUCT($B$6:$G$6,B10:G10)
- Enter 키를 누른 후 채우기 핸들을 아래로 드래그합니다.
- 이제 H6 셀에 아래 수식을 입력합니다.
=SUMPRODUCT($B$6:$G$6,B10:G10)- Enter 키를 누릅니다.
- 다음 단계에서는 데이터 탭으로 이동하여 솔버를 선택합니다. 솔버 매개 변수 창이 열립니다.
- 솔버 매개 변수 창에서 목표 값을 $H$6 셀로 설정하고, 변경할 변수 셀을 $B$6:$G$6으로 지정한 뒤 최소값(Min)을 선택합니다.
- 그런 다음 추가를 클릭합니다.
- 이제 제약 조건을 하나씩 추가하고, 해결 방법으로 Simplex LP를 선택합니다.
- 풀기를 클릭해 진행합니다.
- 그 결과 솔버 결과 창이 나타납니다.
- 거기서 확인을 클릭합니다.
- 마지막으로 결과가 아래 그림과 같이 표시됩니다.
결론
이 글에서는 엑셀에서 정수 선형 계획법을 해결하는 단계별 방법을 자세히 살펴보았습니다. 이 가이드를 통해 여러분의 업무를 더욱 쉽게 처리할 수 있기를 바랍니다. 또한 글 초반부에 연습용 파일을 첨부했으니, 이를 내려받아 직접 실력을 점검해 보세요. 더 많은 관련 글을 원하신다면 ExcelDemy 웹사이트를 방문해 주세요. 마지막으로 제안이나 궁금한 점이 있다면 아래 댓글 섹션에서 언제든지 질문해 주세요.