Pemrograman linear bilangan bulat campuran (MILP)

Pengantar Optimasi di Python

Jasmin Ludolf

Content Developer

Pemrograman linear bilangan bulat campuran

  • MILP
  • Teknik optimasi saat variabel kendala bersifat diskret
Pengantar Optimasi di Python

Gaun atau tuksedo

  • Permintaan:

    • Gaun: Maksimal $20$ dengan harga $\$ 1000$
    • Tuksedo: Maksimal $12$ dengan harga $\$ 600$

  • Produksi gaun:

    • Kain $\$ 110$
    • Pak S 6 jam pada $\$40/jam$
    • Bu T 3 jam pada $\$35/jam$
  • Produksi tuksedo:
    • Kain $\$ 75$
    • Pak S 4 jam pada $\$40/jam$
    • Bu T 1 jam pada $\$35/jam$

Sepasang orang mengenakan gaun dan tuksedo

Pengantar Optimasi di Python

Gaun atau tuksedo

  • Kendala:
    • Pak S maksimal 40 jam
    • Bu T maksimal 20 jam

 

  • Tentukan jumlah gaun dan tuksedo optimal untuk memaksimalkan laba

Seseorang memegang kain merah dan memasangkannya pada manekin untuk membuat gaun

Pengantar Optimasi di Python

Objektif dan kendala

  • $g$: jumlah gaun per minggu
  • $t$: jumlah tuksedo per minggu

  • $C$: biaya kain + upah Pak S + biaya peluang Bu T

  • Biaya peluang: biaya memilih menjahit dibanding tugas lain

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

$C=455g+270t$

Biaya Kain Pak S Bu T
Gaun $\$110$ $\$40/h \times 6h = \$240$ $\$35/h \times 3h = \$105$
Tuksedo $\$75$ $\$40/h \times 4h = \$160$ $\$35/h \times 1h = \$35$
Pengantar Optimasi di Python

Objektif dan kendala

  • Pendapatan: $R=1000g+600t$
  • Biaya: $C=455g+270t$
  • Laba: $\Pi=R-C=(1000g+600t)-(455g+270t)=545g+330t$

 

  • Kendala:

    • Permintaan: $g\leq20$, $t\leq12$

    • Pasokan: $6g+4t\leq40$, $3g+t\leq20$

Pengantar Optimasi di Python

MILP di SciPy

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]))
Pengantar Optimasi di Python

MILP di SciPy

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
Pengantar Optimasi di Python

Keutuhbilangan

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
Pengantar Optimasi di Python

Dampak mengabaikan keutuhbilangan

  • Solusi usulan 6,67 gaun dan 0,00 tuksedo $\rightarrow$

    • Pembulatan ke 7 gaun dan 0 tuksedo

      • Pak S: $6g+4t=6\times7 + 4\times0 = 42$
      • $42 \gt 40$

    • Pemangkasan ke 6 gaun dan 0 tuksedo

      • Pak S: $6g+4t=6\times6 + 4\times0 = 36$
      • Bu T: $3g+1t=3\times6 + 1\times0 = 18$
      • $\Pi=545g+330t=545\times 6+330 \times 0=3270$
      • Kehilangan laba $330 (hampir 10%)!
Pengantar Optimasi di Python

Ayo berlatih!

Pengantar Optimasi di Python

Preparing Video For Download...