Operasi Riset atau Operations Research adalah pendekatan ilmiah pengambilan keputusan dengan mencari desain dan pengoperasian sistem terbaik, biasanya dalam kondisi dimana membutuhkan alokasi sumber daya yang terbatab. Pendekatan ilmiah untuk pengambilan keputusan ini membutuhkan penggunaan satu atau lebih model matematika optimasi (yaitu representasi dari situasi aktual) guna membuat keputusan optimal. Model pengoptimalan berusaha menemukan nilai variabel keputusan yang mengoptimalkan (memaksimalkan atau meminimalkan) dimana fungsi objektifnya diantara kumpulan semua nilai untuk variabel keputusan yang memenuhi batasan yang telah diberikan.

Tiga komponen utamanya adalah:

  1. Fungsi objektif: fungsi yang akan dioptimalkan (dimaksimalkan atau diminimalkan)
  2. Variabel keputusan: variabel yang dapat dikontrol yang memengaruhi kinerja sistem
  3. Batasan: sekumpulan pembatasan (yaitu ketidaksetaraan linear atau kesetaraan) variabel keputusan. Batasan non-negativitas membatasi variabel keputusan untuk mengambil nilai positif (misalnya Anda tidak dapat menghasilkan jumlah item negatif x1, x2, dan x3).

Solusi dari model pengoptimalan disebut solusi yang layak optimal (optimal feasible solution).

Langkah-langkah Pemodelan

Pemodelan secara akurat riset operasional harus mewakili hal-hal yang paling signifikan-dan kadang-kadang tugasnya yang paling sulit. Model yang salah akan mengarah pada solusi yang salah, dan dengan demikian, tidak akan menyelesaikan masalah aslinya. Langkah-langkah berikut harus dilakukan oleh anggota tim operational research yang berbeda-beda bidang keahlian yang berbeda guna mendapatkan pandangan yang akurat dan lebih besar tentang model:

  1. Definisi masalah: mendefinisikan ruang lingkup proyek dan mengidentifikasi bahwa hasilnya adalah identifikasi tiga elemen: deskripsi variabel keputusan, penentuan tujuan dan penentuan batasan (yaitu batasan).
  2. Konstruksi model: menerjemahkan definisi masalah ke dalam hubungan matematika.
  3. Solusi model: menggunakan algoritma pengoptimalan standar. Setelah mendapatkan solusi, analisis sensitivitas harus dilakukan untuk mengetahui perilaku solusi karena perubahan beberapa parameter.
  4. Validitas model: memeriksa apakah model berfungsi seperti yang seharusnya.
  5. Implementasi: menerjemahkan model dan hasilnya ke dalam rekomendasi solusi.

Pemrograman Linear

Pemrograman linear (juga disebut LP) adalah teknik penelitian operasi yang digunakan ketika semua tujuan dan batasannya linear (dalam variabel) dan ketika semua variabel keputusan sudah berkesinambungan. Dalam hierarki, pemrograman linier dapat dianggap sebagai teknik penelitian operasi termudah.

Metode Grafis

Metode grafis mewakili algoritma pengoptimalan untuk memecahkan masalah pemrograman linear yang berisi dua variabel keputusan (x1 dan x2). Ini adalah salah satu pendekatan paling populer untuk memecahkan masalah pemrograman linier sederhana.

Contoh:

Selesaikan permasalahan matematika dibawah ini:

Max Z = 4x1 + 5x2, dimana

6x1 + 6x2 <= 36

x1 + 2x2 <= 10

x1 <= 4

x1, x2 <= 0

Sehingga kita rubah menjadi:

x2 = 6 – x1

x2 = 5 – 1/2x1

x1 = 4

x1 = 0

x2 = 0

Code R:

# Definisikan Batasannya
cons.1 <- function(x) 6 - x  
cons.2 <- function(x) 5 - 0.5*x
# cons.3 x1 = 4 (plotted using geom_vline)
# cons.4 x1 = 0 (defined by setting x1 axis limits)
# cons.5 x2 = 0 (defined by setting x2 axis limits)
# Import ggplot2 package
library(ggplot2)

# plot
p <- ggplot(data = data.frame(x = 0), aes(x = x)) +
  
  # Tambah axes
  geom_vline(xintercept = 0) +
  geom_hline(yintercept = 0) +
  
  # Tambah constraints lines
  stat_function(colour = "Red", fun = cons.1) +
  stat_function(colour = "Blue", fun = cons.2) +
  geom_vline(xintercept = 4, colour = "Green") +
  
  # Specifikasi axes breaks dan limits
  scale_x_continuous(breaks = seq(0, 10, 1), lim = c(0, 10)) +
  scale_y_continuous(breaks = seq(0, 10, 1), lim = c(0, 10)) +
  
  # Define labels
  labs(title = "Optimization Problem",
       subtitle = "Graphical Method",
       x = "x1",
       y = "x2") +
  
  # Gunakan black and white theme
  theme_bw()

# Print plot
print(p)
Gambar 1

Sekarang persamaan batasan telah diplot, langkah berikutnya terdiri dari mendefinisikan wilayah yang layak, yaitu poligon (yaitu plot area) di mana semua membatasi ketidaksetaraan asli terpenuhi:

options(warn=-1)
# Definisi feasible region polygon
feasible_region = data.frame(x = c(0, 4, 4, 2, 0), y = c(0, 0, 2, 4, 5))

# Tambahkan feasible region ke current plot
p <- p + geom_polygon(data = feasible_region, mapping = aes(x = x, y = y), fill = "#dddddd") +
  geom_point(data = feasible_region, aes(x = x, y = y), color = "Black")

# Print plot
print(p)
Gambar 2

Wilayah yang layak di atas berisi semua kemungkinan kombinasi x1 dan x2 yang memenuhi batasan yang diberikan. Namun, solusi optimal dari masalah akan terletak di salah satu titik sudutnya, baik (0,0), (4,0), (4,2), (2,4) atau (0,5).

Untuk mengidentifikasi titik sudut yang mewakili solusi optimal, fungsi objektif perlu diplot berikutnya. Setelah diplot, garis fungsi objektif akan secara bertahap digusur ke kanan sepanjang jalan sebelum keluar dari wilayah yang layak. Titik terakhir garis fungsi objektif menyentuh sebelum keluar dari bidang yang layak mewakili solusi optimal dari masalah (yaitu kombinasi nilai x1 dan x2 yang memaksimalkan nilai z).

options(warn=-1)
# Definisikan Fungsi Tujuan
z1 <- function(x) -0.8*x + 2 # (the + 2 constant is just for displacement visualization purposes)

# Visualize objective function displacement
p <- p + stat_function(colour = "Black", fun = z1, lty=2)

# Print plot
print(p)
Gambar 3

Berdasarkan plot di atas, garis fungsi objektif dapat digeser lebih ke kanan.

options(warn=-1)
# Definiskan kembali Fungsi Tujuan
z2 <- function(x) -0.8*x + 4 # (the + 4 constant is just for displacement visualization purposes)

# Visualize objective function displacement again
p <- p + stat_function(colour = "Black", fun = z2, lty=2)

# Print plot
print(p)
Gambar 4

Sekali lagi, berdasarkan plot di atas, garis fungsi objektif dapat digeser lebih ke kanan.

options(warn=-1)
# Visualize objective function displacement again
z.solution <- function(x) -0.8*x + 5.6   # (the + 5.6 constant is just for displacement visualization purposes)\

# Visualize objective function displacement - solution
p <- p + stat_function(colour = "Black", fun = z.solution, lty=2)

# Print plot
print(p)
Gambar 5

Pada titik ini, garis fungsi objektif tidak dapat digeser lebih jauh lagi ke kanan karena akan keluar dari wilayah yang layak, dengan demikian, solusi optimal telah dicapai pada (2, 4). Karena titik menyentuh garis fungsi objektif milik garis batasan pertama dan kedua (yaitu garis merah dan biru), batasan ini mewakili batasan pengikatan, yang berarti bahwa tidak ada surplus atau kendur di dalamnya (yaitu mereka telah mencapai nilai maksimum / minimum yang dapat diterima).
Solusinya dapat dikonfirmasi dengan menerapkan algoritma simpleks menggunakan paket lpSolve R:

options(warn=-1)
# Import lpSolve package
library(lpSolve)

# Set coefficients of the objective function
f.obj <- c(4, 5)

# Set matrix corresponding to coefficients of constraints by rows
f.con <- matrix(c(1, 2,
                  6, 6,
                  1, 0), nrow = 3, byrow = TRUE)

# Set unequality/equality signs
f.dir <- c("<=", "<=", "<=")

# Set right hand side coefficients
f.rhs <- c(10, 36, 4)

# Final value (z)
lp("max", f.obj, f.con, f.dir, f.rhs)

# Variables final values
solution <- lp("max", f.obj, f.con, f.dir, f.rhs)$solution

# Highlight optimum solution in plot
p <- p + geom_point(aes(x = solution[1], y = solution[2]), color = "red", size = 4)

# Print plot
print(p)

Hasil Outputnya:

Gambar 6

Seperti yang terlihat pada plot di atas, hasil akhir algoritma simpleks adalah (2, 4), sama dengan hasil yang dicapai menggunakan metode grafis. Titik merah (yaitu solusi simpleks) cocok dengan titik terakhir garis fungsi objektif (yaitu garis putus-putus hitam) menyentuh sebelum keluar dari wilayah yang layak, sehingga, mengkonfirmasi bahwa x1 = 2 dan x2 = 4 memimpin nilai maksimum yang mungkin z, 28.

Kesimpulan
Metode grafis mewakili satu pendekatan guna memecahkan masalah pemrograman linier. Namun, pendekatan ini terbatas pada masalah pengoptimalan yang hanya mengandung dua variabel keputusan karena kendala diplot dalam ruang dua dimensi. Setiap variabel keputusan tambahan akan menambah dan ruang tambahan dalam plot dan nanti akan mempersulit visualisasinya.

Pada kenyataannya, sebagian besar masalah pengoptimalan akan berisi lebih dari dua variabel keputusan dari berbagai jenis (misalnya linear, bilangan bulat, biner) dengan batasan yang lebih kompleks, membatasi penerapan metode grafis untuk memecahkannya.

Membangun plot ruang dua dimensi dan menggusur garis fungsi objektif di sepanjang wilayah yang layak untuk menemukan titik ekstrem yang optimal memakan waktu dan bukan pendekatan yang paling efektif. Penerapan algoritma pengoptimalan lainnya dalam beberapa program komputer (misalnya R, GAMS, AMPL, LINDO) mengurangi secara signifikan waktu yang dihabiskan untuk memecahkan masalah pengoptimalan sekaligus bisa mendapatkan informasi berharga lainnya (misalnya analisis sensitivitas).

Insya Allah dibahas lagi…

admin

By admin

Leave a Reply

Your email address will not be published. Required fields are marked *