혼합 정수 선형계획법(MILP)

Python으로 배우는 Optimization 입문

Jasmin Ludolf

Content Developer

혼합 정수 선형계획법

MILP
제약 변수들이 이산 변수일 때 사용하는 최적화 기법

가운 vs 턱시도

수요:
- 가운: 최대 $20$, 가격 $\$ 1000$
- 턱시도: 최대 $12$, 가격 $\$ 600$
가운 생산:
- 원단 $\$ 110$
- Mr. S 6시간, $\$40/h$
- Ms. T 3시간, $\$35/h$
턱시도 생산:
- 원단 $\$ 75$
- Mr. S 4시간, $\$40/h$
- Ms. T 1시간, $\$35/h$

드레스와 턱시도를 입은 한 커플

가운 vs 턱시도

제약식:
- Mr. S 최대 40시간
- Ms. T 최대 20시간

이익 극대화를 위한 가운/턱시도 최적 생산량 구하기

붉은 천을 마네킹에 대어 드레스를 만드는 사람

목표함수와 제약식

$g$: 주당 가운 수
$t$: 주당 턱시도 수
$C$: 원단비 + Mr. S 임금 + Ms. T 기회비용
기회비용: 재봉을 선택해 다른 일을 못 하는 비용

$C=110g+240g+105g+75t+160t+35t$

$C=455g+270t$

비용	원단	Mr. S	Ms. T
가운	$\$110$	$\$40/h \times 6h = \$240$	$\$35/h \times 3h = \$105$
턱시도	$\$75$	$\$40/h \times 4h = \$160$	$\$35/h \times 1h = \$35$

목표함수와 제약식

매출: $R=1000g+600t$
비용: $C=455g+270t$
이익: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

제약식:
- 수요: $g\leq20$, $t\leq12$
- 공급: $6g+4t\leq40$, $3g+t\leq20$

SciPy에서의 MILP

from scipy.optimize import milp, Bounds, LinearConstraint


result = milp([-545, -330],

              integrality=[1, 1],

              bounds=Bounds([0, 0], [20, 12]),

              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))

SciPy에서의 MILP

print(result.message)
print(f'The optimal number of gowns produced is: {result.x[0]:.2f}')
print(f'The optimal number of tuxedos produced is: {result.x[1]:.2f}')

Optimization terminated successfully. (HiGHS Status 7: Optimal)
The optimal number of gowns produced is: 6.00
The optimal number of tuxedos produced is: 1.00

정수성

result = milp([-545, -330],  
              bounds=Bounds([0, 0], [20, 12]), 
              constraints=LinearConstraint([[6, 4], [3, 1]], ub=[40, 20]))
...

The optimal number of gowns produced is: 6.67
The optimal number of tuxedos produced is: 0.00

정수성 누락의 결과

제안 해: 가운 6.67, 턱시도 0.00 $\rightarrow$
- 반올림: 가운 7, 턱시도 0
  - Mr. S: $6g+4t=6\times7 + 4\times0 = 42$
  - $42 \gt 40$
- 내림: 가운 6, 턱시도 0
  - Mr. S: $6g+4t=6\times6 + 4\times0 = 36$
  - Ms. T: $3g+1t=3\times6 + 1\times0 = 18$
  - $\Pi=545g+330t=545\times 6+330 \times 0=3270$
  - 이익 $330(약 10%)$ 손실!

Ayo berlatih!

Python으로 배우는 Optimization 입문