Bunch of Ideas, a little bit of Maths.

I am mathematician doing market research and data science

11 minute read

JENIS OPTIMISASI

Linear Programming

Linear programming adalah bentuk metode optimisasi sederhana yang memanfaatkan relasi linear (semua fungsi dan constraints merupakan fungsi linear).

Contoh Masalah Linear Programming

Saya memiliki area parkir seluas 1.960 m^2. Luas rata-rata untuk mobil berukuran kecil adalah 4 m^2 dan mobil besar adalah 20 m^2. Daya tampung maksimum hanya 250 kendaraan, biaya parkir mobil kecil adalah Rp 7.000 per jam dan mobil besar adalah Rp 12.000 per jam. Jika dalam 1 jam area parkir saya terisi penuh dan tidak ada kendaraan yang pergi dan datang, maka berapa pendapatan maksimum yang bisa saya dapatkan dari tempat parkir itu?

Dari kasus di atas kita bisa tuliskan model matematikanya sebagai berikut:

Misal x_1 adalah mobil kecil dan x_2 adalah mobil besar.

max(7000x_1 + 12000x_2)

Dengan constraints:

4 x_1 + 20 x_2 \leq 1960

dan

x_1 + x_2 \leq 250

serta x_1 \geq 0, x_2 \geq 0.

Integer Programming

Integer programming adalah bentuk metode optimisasi di mana variabel yang terlibat merupakan bilangan bulat (integer). Jika fungsi-fungsi yang terkait merupakan linear, maka disebut dengan integer linear programming.

Sebagai contoh, variabel yang merupakan bilangan bulat adalah banyak orang.

Contoh Integer Programming

Jadwal Kebutuhan Tenaga Kesehatan

Suatu rumah sakit membutuhkan tenaga kesehatan setiap harinya dengan spesifikasi berikut:

hari Min Nakes Required Max Nakes Required
Senin 24 29
Selasa 22 27
Rabu 23 28
Kamis 11 16
Jumat 16 21
Sabtu 20 25
Minggu 12 17

Tabel Kebutuhan Nakes Harian

Di rumah sakit tersebut berlaku kondisi sebagai berikut:

  1. Setiap nakes hanya diperbolehkan bekerja selama 5 hari berturut-turut dan harus libur selama 2 hari berturut-turut.
  2. Tidak ada pemberlakuan shift bagi nakes.

Berapa banyak nakes yang harus dipekerjakan oleh rumah sakit tersebut? Bagaimana konfigurasi penjadwalannya?

Untuk memudahkan dalam mencari solusi permasalahan di atas, kita bisa membuat tabel ilustrasi berikut:

hari Min Nakes Required Max Nakes Required x1 x2 x3 x4 x5 x6 x7
Senin 24 29 x     x x x x
Selasa 22 27 x x     x x x
Rabu 23 28 x x x     x x
Kamis 11 16 x x x x     x
Jumat 16 21 x x x x x    
Sabtu 20 25   x x x x x  
Minggu 12 17     x x x x x

Konfigurasi Penjadwalan Nakes

Kolom x_i, i =1,2,3,4,5,6,7 menandakan kelompok nakes yang perlu dipekerjaan pada hari-hari tertentu. Setiap nilai x_i tersebut merupakan bilangan bulat positif x \geq 0, x \in \mathbb{Z}.

Dari ilustrasi di atas, kita bisa membuat model optimisasinya sebagai berikut:

Objective Function

\min{ \sum_{i=1}^7 x_i}

Constraints

  • Hari Senin: 24 \leq \sum x_i \leq 29, i \in \{1,4,5,6,7\}.
  • Hari Selasa: 22 \leq \sum x_i \leq 27, i \in \{1,2,5,6,7\}.
  • Hari Rabu: 23 \leq \sum x_i \leq 28, i \in \{1,2,3,6,7\}.
  • Hari Kamis: 11 \leq \sum x_i \leq 16, i \in \{1,2,3,4,7\}.
  • Hari Jumat: 16 \leq \sum x_i \leq 21, i \in \{1,2,3,4,5\}.
  • Hari Sabtu: 20 \leq \sum x_i \leq 25, i \in \{2,3,4,5,6\}.
  • Hari Minggu: 12 \leq \sum x_i \leq 17, i \in \{3,4,5,6,7\}.

Kita juga perlu perhatikan bahwa x_i \geq 0, i \in \{1,2,3,4,5,6,7\}.

Binary Programming

Binary programming adalah bentuk metode optimisasi di mana variabel yang terlibat merupakan bilangan biner (0,1). Biasanya metode ini dipakai dalam masalah penjadwalan yang memerlukan prinsip matching antar kondisi yang ada.

Contoh Binary Programming

Jadwal Tatap Muka Terbatas Sekolah

Beberapa minggu ke belakang, kasus harian Covid semakin menurun. Pemerintah mulai melonggarkan aturan PPKM yang mengakibatkan sekolah-sekolah mulai menggelar pengajaran tatap muka terbatas (PTMT) untuk siswanya secara offline.

Suatu sekolah memiliki kelas berisi 20 orang siswa. Mereka hendak menggelar PTMT dengana aturan sebagai berikut:

  1. PTMT digelar dari Senin hingga Jumat (5 hari).
  2. Dalam sehari, siswa yang boleh hadir dibatasi 4-8 orang saja.
  3. Dalam seminggu, diharapkan siswa bisa hadir 2-3 kali.
  4. Siswa yang hadir di selang sehari baru bisa hadir kembali.

Dari uraian di atas, kita bisa membuat model optimisasinya sebagai berikut:

Saya definisikan x_{i,j} \in (0,1) sebagai bilangan biner di mana i \in \{1,2,..,20\} menandakan siswa dan j \in \{1,2,..,5\} menandakan hari. Berlaku:

x_{i,j} = \left\{\begin{matrix} 0, \text{ siswa i tidak masuk di hari j}\\ 1, \text{ siswa i masuk di hari j} \end{matrix}\right.

Objective Function

Tujuan utama kita adalah memaksimalkan siswa yang hadir.

\max{\sum_{j=1}^5 \sum_{i=1}^{20} x_{i,j} }

Constraints

Dalam sehari, ada pembatasan jumlah siswa yang hadir.

4 \leq \sum_i x_{i,j} \leq 8, j \in \{1,2,..,5\}

Dalam seminggu, siswa hadir dalam frekuensi tertentu.

2 \leq \sum_j x_{i,j} \leq 3, i \in \{1,2,..,20\}

Ada jeda sehari agar siswa bisa masuk kembali.

x_{i,j} + x_{i,j+1} \leq 1

Jangan lupa bahwa x_{i,j} \geq 0.

Mixed Integer Linear Programming

Pada bagian sebelumnya, kita telah membahas masalah optimisasi dengan variabel berupa diskrit dan kontinu. Permasalahan real yang ada di kehidupan sehari-hari biasanya merupakan memiliki variabel yang mixed antara keduanya. Oleh karena itu, ada metode yang disebut dengan mixed integer linear programming. Pada masalah optimisasi tipe ini, decision variables yang terlibat bisa saja berupa binary, integer, dan continuous sekaligus.

Menyelesaikan MILP

MILP secara eksak bisa diselesaikan dengan metode simplex dengan dikombinasikan dengan teknik branch and bound. Penjelasan terkait ini akan dibahas pada bab 6.

Contoh MILP

Pemilihan dan Penentuan Item Produksi

Suatu pabrik makanan dan minuman berencana untuk membuat tiga produk baru yang bisa diproduksi di dua plants yang berbeda.

Produk Runtime Plant 1 Runtime Plant 2
Item 1 3 4
Item 2 4 6
Item 3 2 2

Tabel Runtime Item Produk per Plant (harian - dalam jam)

Plant 1 memiliki maksimum working hours sebesar 30 jam perhari.

Plant 2 memiliki maksimum working hours sebesar 40 jam perhari.

Produk Profit per ton Sales potential per ton
Item 1 5 7
Item 2 7 5
Item 3 3 9

Tabel Profit dan Potensi Sales Item Produk

Masalah timbul saat mereka harus memilih dua dari tiga produk baru tersebut yang harus di produksi. Selain itu, mereka juga harus memilih satu dari dua plants yang memproduksi items tersebut.

Misalkan saya definisikan:

  • x_i \geq 0, i = 1,2,3 sebagai berapa ton yang harus diproduksi dari item i.
  • y_i \in [0,1], i = 1,2,3 sebagai binary.
    • Jika bernilai 0, maka produk i tidak dipilih.
    • Jika bernilai 1, maka produk i dipilih.
  • z \in [0,1] sebagai binary.
    • Jika bernilai 0, maka plant pertama dipilih.
    • Jika bernilai 1, maka plant kedua dipilih.

Saya akan mendefinisikan suatu variabel dummy M = 99999 berisi suatu nilai yang besar. Kelak variabel ini akan berguna untuk reinforce model (metode pemberian penalty) agar bisa memilih items dan plants secara bersamaan.

Objective function dari masalah ini adalah memaksimalkan profit.

\max{ \sum_{i=1}^3 x_i \times \text{profit}_i }

Constraints dari masalah ini adalah:

Tonase produksi tidak boleh melebihi angka sales potential per items.

x_i \leq \text{sales potential}_i, i = 1,2,3

Kita akan memilih dua produk sekaligus menghitung tonase. Jika produk tersebut dipilih, maka akan ada angka tonase produksinya. Sebaliknya, jika produk tersebut tidak dipilih, maka tidak ada angka tonase produksinya.

x_i - y_i \times M \leq 0, i = 1,2,3

\sum_{i=1}^3 y_i \leq 2

Kita akan memilih plant dari waktu produksinya.

3x_1 + 4x_2 + 2x_3 - M \times z \leq 30

4x_1 + 6x_2 + 2x_3 + M \times z \leq 40 + M

You May Also Enjoy

Geocoding di R Menggunakan tidygeocoder

7 minute read

Di blog ini saya sudah menuliskan berbagai macam metode dan teknik pengambilan data longlat dari alamat (vice versa). Istilah kerennya itu geocoding.