선형계획과 잠재가격
Linear Optimization and Shadow Prices
비즈니스 애널리틱스 · 6주차 (보강 1)
최적화 모형의 활용
- 최적화 모형: 정해진 제약 안에서 목표를 가장 좋게 하는 결정을 수식으로 찾는 방법
- 활용 분야
- 생산계획: 원료·설비 한도 안에서 제품별 생산량
- 배합: 비용이 가장 적게 드는 원료 배합 비율
- 운송·배분: 공장에서 창고로 보내는 물량
- 인력 배치: 수요를 채우는 최소 인원의 근무표
- 예측 모형과의 차이: 미래 값을 맞히는 대신, 무엇을 얼마나 할지 결정을 직접 냄
- 선형계획(linear optimization, LP): 목적과 제약이 모두 결정 변수의 일차식인 최적화 모형
이번 주의 결정 문제
논리 칩과 메모리 칩을 몇 개씩 만들고, 원료를 더 산다면 어느 원료에 얼마까지 낼 것인가
- 자료: MO-book 2장의 반도체 회사 BIM 생산계획 예제
- 필요한 도구
- 결정을 변수, 목표, 제약으로 옮긴 선형계획 모형
- 모형을 푸는 solver
- 원료 1단위의 가치를 알려 주는 쌍대 문제와 잠재가격
강의 구성
- 선형계획 모형 세우기
- 그림으로 보는 실행 가능 영역과 최적해
- Pyomo와 solver로 풀기
- 쌍대 문제
- 잠재가격의 해석과 유효 범위
- 모든 계산 예제: BIM 생산계획, 교재(MO-book 2장 노트북)와 같은 문제
예제: BIM의 마이크로칩 생산
| 원료 | 논리 칩 1개당 | 메모리 칩 1개당 | 보유량 |
|---|---|---|---|
| 규소(silicon) | 1 g | 0 g | 1,000 g |
| 게르마늄(germanium) | 0 g | 1 g | 1,500 g |
| 플라스틱(plastic) | 1 g | 1 g | 1,750 g |
| 구리(copper) | 4 g | 2 g | 4,800 g |
| 1개당 이익 | 12 € | 9 € |
- 질문: 보유한 원료 안에서 이익이 가장 큰 생산량
- 논리 칩이 1개당 이익은 크지만 구리를 두 배로 씀
선형계획 모형의 구성 요소
| 구성 요소 | 정의 | BIM의 예 |
|---|---|---|
| 결정 변수 | 정해야 할 양 | \(x_1\): 논리 칩 수, \(x_2\): 메모리 칩 수 |
| 목적함수 | 최대 또는 최소로 만들 값 | 이익 \(12x_1+9x_2\) |
| 제약식 | 결정 변수가 지켜야 할 조건 | 원료 사용량 ≤ 보유량, \(x_1,x_2\ge0\) |
| 실행 가능 해 | 모든 제약을 지키는 결정 | \((x_1,x_2)=(500,500)\) |
| 최적해 | 실행 가능 해 가운데 목적함수가 가장 좋은 해 | 뒤에서 구함 |
- 선형: 목적함수와 제약식이 모두 결정 변수의 일차식, 곱이나 제곱이 없음
BIM의 선형계획 모형
모형
\[\begin{aligned}
\max\quad & 12x_1+9x_2\\
\text{s.t.}\quad & x_1\le1{,}000\\
& x_2\le1{,}500\\
& x_1+x_2\le1{,}750\\
& 4x_1+2x_2\le4{,}800\\
& x_1,\,x_2\ge0
\end{aligned}\]
- 목적: 이익 최대화
- 제약 1: 규소, 논리 칩만 1 g씩 사용
- 제약 2: 게르마늄, 메모리 칩만 1 g씩 사용
- 제약 3: 플라스틱, 두 칩 모두 1 g씩 사용
- 제약 4: 구리, 논리 칩 4 g, 메모리 칩 2 g
- s.t.: subject to, 제약식의 시작 표시
실행 가능 영역
- 정의: 모든 제약을 지키는 \((x_1,x_2)\)의 집합, 그림의 색칠한 다각형
- 제약식 하나 = 직선 하나의 한쪽 면
- 점선: 이익이 17,700인 점들, \(12x_1+9x_2=17{,}700\)
- 이익을 키우면 점선이 오른쪽 위로 평행 이동함
- 점선이 영역에 마지막으로 닿는 점이 최적해: \((650,\ 1{,}100)\)
꼭짓점과 최적해
- 성질: 최적해가 있으면 실행 가능 영역의 꼭짓점 가운데 하나에 있음
| 꼭짓점 \((x_1,x_2)\) | 만나는 제약 | 이익 |
|---|---|---|
| (0, 0) | \(x_1,x_2\ge0\) | 0 |
| (1,000, 0) | 규소 | 12,000 |
| (1,000, 400) | 규소, 구리 | 15,600 |
| (650, 1,100) | 플라스틱, 구리 | 17,700 |
| (250, 1,500) | 게르마늄, 플라스틱 | 16,500 |
| (0, 1,500) | 게르마늄 | 13,500 |
- 최적해: 논리 칩 650개, 메모리 칩 1,100개, 이익 17,700 €
행렬 형태
정의결정 변수 \(n\)개, 제약 \(m\)개인 선형계획을 벡터와 행렬로 씀
\[\max\ c^\top x\quad \text{s.t.}\quad Ax\le b,\ \ x\ge0\]
\[c=\begin{pmatrix}12\\9\end{pmatrix},\quad
A=\begin{bmatrix}1&0\\0&1\\1&1\\4&2\end{bmatrix},\quad
b=\begin{pmatrix}1{,}000\\1{,}500\\1{,}750\\4{,}800\end{pmatrix}\]
- \(A\)의 행 = 원료, 열 = 칩, 원소 = 칩 1개당 원료 사용량
- 제품과 원료가 늘어도 같은 꼴: 한 가지 solver로 모든 문제를 풂
- 교재 노트북의 행렬 형태: 최대화를 \(-c\)의 최소화로, \(\le\)를 양변에 \(-1\)을 곱한 \(\ge\)로 바꾼 같은 문제
Pyomo와 solver로 풀기
model = pyo.ConcreteModel()
model.x1 = pyo.Var(domain=pyo.NonNegativeReals)
model.x2 = pyo.Var(domain=pyo.NonNegativeReals)
model.profit = pyo.Objective(
expr=12 * model.x1 + 9 * model.x2,
sense=pyo.maximize)
model.silicon = pyo.Constraint(expr=model.x1 <= 1000)
model.germanium = pyo.Constraint(expr=model.x2 <= 1500)
model.plastic = pyo.Constraint(expr=model.x1 + model.x2 <= 1750)
model.copper = pyo.Constraint(expr=4 * model.x1 + 2 * model.x2 <= 4800)
SOLVER.solve(model)
- Pyomo: 모형을 파이썬 코드로 적는 도구
- solver: 모형을 받아 최적해를 계산하는 프로그램, 교재는 HiGHS
- 코드와 모형의 대응
Var: 결정 변수Objective: 목적함수Constraint: 제약식
- 결과: \(x=(650.0,\ 1{,}100.0)\), 이익 17,700.0
제약의 상태: binding과 여유
| 원료 | 최적해의 사용량 | 보유량 | 여유(slack) | 상태 |
|---|---|---|---|---|
| 규소 | 650 | 1,000 | 350 | 여유 있음 |
| 게르마늄 | 1,100 | 1,500 | 400 | 여유 있음 |
| 플라스틱 | 650 + 1,100 = 1,750 | 1,750 | 0 | binding |
| 구리 | 4×650 + 2×1,100 = 4,800 | 4,800 | 0 | binding |
- binding 제약: 최적해에서 등호로 성립하는 제약, 다 써 버린 원료
- 여유(slack): 보유량 − 사용량, 남는 원료
- 이익을 더 늘리려면 다 써 버린 플라스틱이나 구리가 더 있어야 함
쌍대 문제의 아이디어: 이익의 상한
- 제약식에 0 이상의 수를 곱해 더하면 이익의 상한을 만들 수 있음
- 예: 플라스틱 제약에 6, 구리 제약에 1.5를 곱해 더함
\[\begin{aligned}
6(x_1+x_2)+1.5(4x_1+2x_2)&\le 6\times1{,}750+1.5\times4{,}800\\
12x_1+9x_2&\le 17{,}700
\end{aligned}\]
- 좌변이 이익 \(12x_1+9x_2\)와 같아지므로, 어떤 실행 가능 해의 이익도 17,700을 넘지 못함
- 최적해의 이익도 17,700: 이 상한이 가장 낮은 상한
- 쌍대 문제: 이런 곱하는 수 가운데 가장 낮은 상한을 주는 것을 찾는 문제
쌍대 문제의 정의
쌍대 문제제약마다 변수 \(y_i\ge0\)을 두고, 곱해 더한 좌변이 이익 계수 이상이 되게 하면서 상한을 최소화하는 문제
\[\begin{aligned}
\min\quad & 1{,}000y_1+1{,}500y_2+1{,}750y_3+4{,}800y_4\\
\text{s.t.}\quad & y_1+y_3+4y_4\ge12\\
& y_2+y_3+2y_4\ge9\\
& y_1,y_2,y_3,y_4\ge0
\end{aligned}\]
- 원래 문제: primal, 쌍대 문제: dual
- \(y_i\): 원료 \(i\) 1 g에 매기는 값, 순서대로 규소·게르마늄·플라스틱·구리
- 쌍대의 해: \(y=(0,\ 0,\ 6,\ 1.5)\), 최솟값 17,700 = 원래 문제의 최댓값 17,700
- 강한 쌍대성: 원래 문제에 최적해가 있으면 두 값이 같음
잠재가격의 정의
잠재가격shadow price, 제약의 우변을 1단위 늘릴 때 최적 목적함수 값이 늘어나는 양, 쌍대 변수의 최적값과 같음
| 원료 | 잠재가격 | 확인: 보유량을 1 g 늘려 다시 풀기 |
|---|---|---|
| 규소 | 0 €/g | 여유 350 g, 더 있어도 이익 그대로 |
| 게르마늄 | 0 €/g | 여유 400 g, 더 있어도 이익 그대로 |
| 플라스틱 | 6 €/g | 1,751 g: 해 (649, 1,102), 이익 17,706 (+6) |
| 구리 | 1.5 €/g | 4,801 g: 해 (650.5, 1,099.5), 이익 17,701.5 (+1.5) |
- 여유가 있는 제약의 잠재가격은 0, binding 제약만 양수가 될 수 있음
- 코드:
model.dual = pyo.Suffix(direction=pyo.Suffix.IMPORT)뒤model.dual[model.plastic]
잠재가격으로 내리는 결정
- 원료를 추가로 살 때 낼 수 있는 최대 가격 = 잠재가격
- 플라스틱: 1 g에 6 €보다 싸면 사는 것이 이익
- 구리: 1 g에 1.5 €보다 싸면 사는 것이 이익
- 규소·게르마늄: 이미 남으므로 살 이유가 없음
- 두 원료를 같은 값에 판다면 플라스틱을 먼저 확보
- 반대로 원료를 팔 때 받아야 할 최소 가격도 잠재가격
해석 시 주의: 잠재가격의 유효 범위
| 원료 | 잠재가격 | 유효 범위(보유량) | 범위를 넘으면 |
|---|---|---|---|
| 플라스틱 | 6 €/g | 1,400 ~ 1,950 g | 1,950 g부터 게르마늄이 binding, 플라스틱을 더 사도 이익 18,900에서 멈춤 |
| 구리 | 1.5 €/g | 4,000 ~ 5,500 g | 5,500 g부터 규소가 binding, 구리를 더 사도 이익 18,750에서 멈춤 |
- 잠재가격은 binding 제약의 조합이 바뀌지 않는 범위에서만 그대로임
- 예: 플라스틱을 200 g(1,750 → 1,950)까지는 1 g에 6 €씩 이익이 늘지만, 그 뒤로는 늘지 않음
- 범위 밖의 결정은 보유량을 바꿔 모형을 다시 풀어 확인
해석 시 주의: 모형의 가정
- 선형성: 칩 1개당 이익과 원료 사용량이 생산량과 관계없이 일정하다고 가정
- 연속 변수: 칩 수를 소수로도 허용, BIM의 최적해는 우연히 정수
- 모형 밖의 제약: 설비 시간, 수요 한도처럼 모형에 넣지 않은 조건은 결과에 반영되지 않음
- 입력 값의 정확성: 이익과 원료 사용량이 바뀌면 최적해와 잠재가격도 바뀜
정리
| 개념 | 정의 | BIM의 값 |
|---|---|---|
| 선형계획 | 일차식 목적과 일차식 제약으로 된 최적화 모형 | \(\max 12x_1+9x_2\), 원료 제약 4개 |
| 최적해 | 실행 가능 영역의 꼭짓점 가운데 목적이 가장 좋은 점 | (650, 1,100), 이익 17,700 € |
| binding 제약 | 최적해에서 등호로 성립하는 제약 | 플라스틱, 구리 |
| 쌍대 문제 | 제약을 곱해 더한 이익 상한의 최소화 | \(y=(0,0,6,1.5)\), 최솟값 17,700 |
| 잠재가격 | 우변 1단위 증가에 따른 최적값의 증가 | 플라스틱 6 €/g, 구리 1.5 €/g |
| 유효 범위 | 잠재가격이 그대로인 우변의 범위 | 플라스틱 1,400~1,950 g, 구리 4,000~5,500 g |