Catatan untuk Thesis: Semua Hal tentang Optimisasi part II

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:

Setiap nakes hanya diperbolehkan bekerja selama 5 hari berturut-turut dan harus libur selama 2 hari berturut-turut.
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:

PTMT digelar dari Senin hingga Jumat (5 hari).
Dalam sehari, siswa yang boleh hadir dibatasi 4-8 orang saja.
Dalam seminggu, diharapkan siswa bisa hadir 2-3 kali.
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$ .
sebagai binary.
- Jika bernilai 0, maka produk $i$ tidak dipilih.
- Jika bernilai 1, maka produk $i$ dipilih.
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$

Twitter Facebook LinkedIn

Bunch of Ideas, a little bit of Maths.