Karma tamsayılı doğrusal programlama (MILP)

Python ile Optimizasyona Giriş

Jasmin Ludolf

Content Developer

Karma tamsayılı doğrusal programlama

MILP
Değişkenler ayrık olduğunda kullanılan optimizasyon tekniği

Elbise mi smokin mi

Talep:
- Elbise: En fazla $20$, fiyat $\$ 1000$
- Smokin: En fazla $12$, fiyat $\$ 600$
Elbise üretimi:
- Kumaş $\$ 110$
- Bay S 6 saat, $\$40/s$
- Bayan T 3 saat, $\$35/s$
Smokin üretimi:
- Kumaş $\$ 75$
- Bay S 4 saat, $\$40/s$
- Bayan T 1 saat, $\$35/s$

Bir elbise ve smokin giymiş bir çift

Elbise mi smokin mi

Kısıtlar:
- Bay S en fazla 40 saat
- Bayan T en fazla 20 saat

Kârı maksimize etmek için en iyi elbise ve smokin sayısını bulun

Kırmızı bir kumaşı mankene giydirerek elbise yapan kişi

Amaç ve kısıtlar

$g$: haftalık elbise sayısı
$t$: haftalık smokin sayısı
$C$: kumaş maliyeti + Bay S ücreti + Bayan T fırsat maliyeti
Fırsat maliyeti: dikimi seçmenin diğer işlere göre maliyeti

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

$C=455g+270t$

Maliyet	Kumaş	Bay S	Bayan T
Elbise	$\$110$	$\$40/s \times 6s = \$240$	$\$35/s \times 3s = \$105$
Smokin	$\$75$	$\$40/s \times 4s = \$160$	$\$35/s \times 1s = \$35$

Amaç ve kısıtlar

Gelir: $R=1000g+600t$
Maliyet: $C=455g+270t$
Kâr: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

Kısıtlar:
- Talep: $g\leq20$, $t\leq12$
- Arz: $6g+4t\leq40$, $3g+t\leq20$

SciPy ile 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 ile MILP

print(result.message)
print(f'Üretilen en iyi elbise sayısı: {result.x[0]:.2f}')
print(f'Üretilen en iyi smokin sayısı: {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

Tamsayılılık

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

Tamsayılılığı yok saymanın sonuçları

Önerilen çözüm 6,67 elbise ve 0,00 smokin $\rightarrow$
- Yuvarla: 7 elbise, 0 smokin
  - Bay S: $6g+4t=6\times7 + 4\times0 = 42$
  - $42 \gt 40$
- Kes: 6 elbise, 0 smokin
  - Bay S: $6g+4t=6\times6 + 4\times0 = 36$
  - Bayan T: $3g+1t=3\times6 + 1\times0 = 18$
  - $\Pi=545g+330t=545\times 6+330 \times 0=3270$
  - $330 (yaklaşık %10) kâr kaçtı!

Hadi pratik yapalım!

Python ile Optimizasyona Giriş