Optimisasi Linear Programming dengan 3 Cara di R

Beberapa malam lalu saya mengobrol secara virtual dengan beberapa senior saya dan beberapa rekan-rekan mahasiswa di Matematika. Dari obrolan itu, saya menjadi teringat ada salah satu teknik dalam matematika yang berguna banget sebenarnya di dunia nyata dan hal yang menarik adalah teknik ini sudah diajarkan sejak kita (minimal saya pribadi) saat di bangku SMA.

Apa itu? Linear Programming.

Lupa yah? Saya kasih contoh berikut ya.

---

Problem Statement

Saya memiliki area parkir seluas 1.960 . Luas rata-rata untuk mobil berukuran kecil adalah 4 dan mobil besar adalah 20 . 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?

---

Math Statement

Dari kasus di atas, kita bisa menuliskan beberapa persamaan berikut:

Persamaan I: Limitasi luas area vs luas kendaraan

Persamaan II: Limitasi jumlah kendaraan

Kita harus menemukan nilai dan yang tepat sehingga memaksimalkan kondisi berikut:

Persamaan III: +

---

Bagaimana cara menyelesaikannya?

Setidaknya saya memiliki tiga cara untuk menyelesaikannya. Tentunya masing-masing memiliki kelebihan dan kekurangan. Apa saja?

Cara I: Membuat Grafik

Cara termudah yang dulu pernah diajarkan pada saat SMA adalah dengan membuat grafik dari dua persamaan garis yang ada. Lalu melihat ada berapa titik yang memenuhi kondisi yang ada.

Biasanya, solusi terbaik didapatkan pada perpotongan dua garis persamaan.

x_1 = c(0:220)

fung_1 = function(x){
  y = (1960 - (4*x))/20
  return(y)
}

fung_2 = function(x){
  y = (250 - (x))
  return(y)
}

fung_max = function(x,y){
  7000*x + 12000*y
}

data = data.frame(x = x_1)
data$y1 = sapply(data$x,fung_1)
data$y2 = sapply(data$x,fung_2)

Kita dapatkan hanya ada tiga titik yang memenuhi kondisi persamaan 1 dan 2.

Kenapa hanya tiga?

Titik yang diambil adalah titik yang berada tepat atau di bawah kedua garis.

Sekarang dari ketiga titik yang ada, kita akan hitung titik mana yang memberikan nilai persamaan III terbesar:

# Titik I:
  # 0 mobil kecil
  # 98 mobil besar
  fung_max(0,98)

## [1] 1176000

# Titik II:
  # 190 mobil kecil
  # 60 mobil besar
  fung_max(190,60)

## [1] 2050000

# Titik III:
  # 220 mobil kecil
  # 0 mobil besar
  fung_max(220,0)

## [1] 1540000

Pendapatan maksimum terjadi pada titik II, sebesar Rp 2.050.000 yakni saat area parkir dipenuhi 190 mobil kecil dan 60 mobil besar.

Kelebihan dan Kekurangan Cara I

• Kelebihan:
  • Cara ini adalah cara yang paling mudah dilakukan. Cukup bermodalkan grafik, kita bisa mendapatkan solusi dari masalah optimisasi seperti ini.
• Kelemahan:
  • Cara ini tidak bisa digunakan saat variabel yang terlibat lebih dari dua.
  • Akan sulit secara visual untuk menggambarkan persamaan garis pada dimensi 3 atau lebih.
  • Contoh: pada kasus area parkir di atas, jika ditambahkan motor dan sepeda dalam persamaannya. Maka akan sulit digambarkan ke dalam grafik.

---

Cara II: Brute Force dengan Simulasi Monte Carlo

Cara kedua ini cenderung sangat mudah dan intuitif. Proses kerjanya mirip seperti apa yang saya lakukan untuk menemukan nilai pada tulisan saya yang lalu.

Bagaimana caranya?

Saya akan membuat banyak sekali pasangan random number di rentang dan . Lalu dari sekian banyak pasangan tersebut, saya hanya akan pilih pasangan yang memenuhi kondisi. Selanjutnya akan dipilih pasangan yang memaksimalkan persamaan pendapatan.

Dengan memperbanyak pasangan titik , diharapkan saya akan mendapatkan pasangan titik solusi yang memaksimalkan pendapatan.

Kelebihan dan Kekurangan Cara II

• Kelebihan:
  • Cara ini juga mudah dilakukan. Tanpa mengetahui grafik dan pengetahuan matematika, kita bisa mendapatkan solusi dari masalah optimisasi seperti ini.
  • Cara ini juga bisa dilakukan untuk variabel yang banyak.
• Kelemahan:
  • Secara komputasi lebih lama karena harus generate semua kemungkinan yang mungkin muncul.

---

Cara III: Menyelesaikan dengan Matriks Aljabar

Salah satu kegunaan matriks dalam aljabar adalah untuk menyelesaikan sistem persamaan linear. Menggunakan R, ada satu library yang didedikasikan untuk hal ini, yakni: library(lpSolve).

# Membuat matriks
  # Berasal dari dua persamaan yang diketahui
  const.mat = matrix(c(4,20,1,1),
                     nrow = 2,
                     byrow = T)
  const.mat

##      [,1] [,2]
## [1,]    4   20
## [2,]    1    1

# Memasukkan persamaan pendapatan yang ingin dimaksimalkan
objective.in = c(7000,12000)
# define constraints
area_constraint = 1960
total_cars_constraint = 250

# RHS for the constraints
const.rhs = c(area_constraint, total_cars_constraint)

# Constraints direction
const.dir = c("<=",  "<=")

# Find the optimal solution
optimum = lp(direction="max",  objective.in, const.mat, const.dir,  const.rhs)

Kita akan mendapatkan hasil sebagai berikut:

optimum

## Success: the objective function is 2050000

optimum$solution

## [1] 190  60

190 mobil kecil dan 60 mobil besar.

Kelebihan dan Kekurangan Cara III

• Kelebihan:
  • Cara ini bisa dilakukan untuk variabel yang banyak.
  • Secara komputasi merupakan cara tercepat dibandingkan dua cara sebelumnya.
• Kelemahan:
  • Penulisan matriks bisa jadi menyulitkan bagi sebagian orang yang belum terbiasa.

---

Jika Kamu merasa tulisan ini berguna, dukung selalu blog ini agar bisa terus bertumbuh dengan cara klik iklan selepas Kamu membaca tulisan ini yah.