Optimisasi Statistika - Metode Simpleks Tanpa Kendala

Video Pembelajaran - P5

Video Pembelajaran dapat diakses melalui link berikut : https://ipb.link/materiopstat

Pengantar

Masalah optimasi tanpa kendala adalah salah satu masalah yang sering ditemui dalam dunia nyata, terutama ketika tidak ada batasan eksternal yang mengatur ruang solusi. Contohnya:

  • Optimasi Produksi: Sebuah perusahaan ingin memaksimalkan keuntungan hanya berdasarkan jumlah barang yang diproduksi tanpa mempertimbangkan batasan sumber daya.

  • Pemodelan Keuangan: Mengoptimalkan portofolio investasi tanpa ada batasan jumlah investasi pada aset tertentu.

Dalam optimasi ini, kita hanya fokus pada fungsi objektif: \[ f(x) = c_1x_1 + c_2x_2 + \dots + c_nx_n, \] di mana:

  • \(x = (x_1, x_2, \dots, x_n)\): adalah vektor variabel keputusan.

  • \(c_i\): adalah koefisien dari masing-masing variabel.

Tidak adanya batasan membuat pendekatan ini lebih sederhana dibandingkan metode optimasi dengan kendala.

Prinsip Dasar

Konsep Metode Simpleks Metode Simpleks adalah metode iteratif yang dimulai dari solusi awal dan berlanjut menuju solusi optimal. Pada setiap langkah, kita mencari titik yang lebih baik dengan memperbaiki nilai fungsi objektif \(f(x)\).

Langkah-Langkah Utama

  1. Inisialisasi Titik Awal:
    Dimulai dari beberapa titik \(x_1, x_2, x_3\), yang mewakili himpunan solusi awal.

  2. Refleksi (\(x_r\)):
    Hitung refleksi dari titik terburuk \(x_h\) terhadap rata-rata titik lainnya \(x_0\): \[ x_0 = \frac{1}{n-1} \sum_{i=1}^{n-1} x_i, \] dan: \[ x_r = (1 + \alpha)x_0 - \alpha x_h, \] di mana \(\alpha\) adalah koefisien refleksi.

  3. Ekspansi (\(x_e\)):
    Jika refleksi membaik secara signifikan (nilai fungsi objektif menurun), maka langkah ekspansi dilakukan untuk memperbesar jarak: \[ x_e = \gamma x_r + (1 - \gamma)x_0, \] dengan \(\gamma > 1\).

  4. Kontraksi (\(x_c\)):
    Jika refleksi gagal memberikan solusi yang lebih baik, kita melakukan kontraksi dengan mengecilkan jarak: \[ x_c = \beta x_h + (1 - \beta)x_0, \] di mana \(\beta < 1\).

  5. Kriteria Konvergensi:
    Periksa apakah solusi telah konvergen berdasarkan kriteria: \[ Q = \sqrt{\frac{1}{n} \sum_{i=1}^{n} (f(x_i) - f(x_0))^2}. \] Jika \(Q < \epsilon\), maka algoritma berhenti.

simptron<-function(f,eps=0.2,Q=1,x1,x2,x3,trace=T,max.iter=100,alpha=0.1,gamma=0.1,beta=0.1){
  if(trace==T)cat("\nTRACING\n")
  i<-0
  d<-t(data.frame(f(x1),f(x2),f(x3)))
  while(Q>eps & i<max.iter){
    nxl<-rownames(d)[which.min(d[,1])]
    nxh<-rownames(d)[which.max(d[,1])]
    
    #menyesuaikan mana yang akan menjadi xl, xh, xg
    if(nxl=="f.x1."){xl<-x1}else if(nxl=="f.x2."){xl<-x2}else{xl<-x3}
    if(nxh=="f.x1."){xh<-x1}else if(nxh=="f.x2."){xh<-x2}else{xh<-x3}
    if((nxl=="f.x1." & nxh=="f.x2.")||(nxl=="f.x2." & nxh=="f.x1.")){xg<-x3}else
      if((nxl=="f.x2." & nxh=="f.x3.")||(nxl=="f.x3." & nxh=="f.x2.")){xg<-x1}else{xg<-x2}
    
    #x0
    x0<-0.5*(xl+xg)
    
    #reflection
    xr<-(1+alpha)*x0-(alpha*xh)
    
    #expansion
    if(f(xr)<f(xl)){
      xe<-gamma*xr+(1-gamma)*x0
      if(f(xe)<f(xl)){
      xh<-xe
    }
    }
    
    #contraction
    if(f(xr)>f(xg) & f(xl)>f(xl) & f(xr)<f(xh)){
      xh<-xr
      xc<-beta*xh+(1-beta)*x0
      if(f(xc)<min(f(xh),f(xr))){
        xh<-xc
      }else{
        xl<-(xl+xl)/2
        xg<-(xg+xl)/2
        xh<-(xh+xl)/2
      }
    }
    
    #konversi sesuai format input awal    
    if(all(xl==x1) & all(xg==x2)){
      x3<-xh
      x2<-xg
      x1<-xl
    }
    else if(all(xl==x2) & all(xg==x1)){
      x3<-xh
      x2<-xl
      x1<-xg
    }
    else if(all(xl==x1) & all(xg==x3)){
      x3<-xg
      x2<-xh
      x1<-xl
    }
    else if(all(xl==x3) & all(xg==x1)){
      x3<-xl
      x2<-xh
      x1<-xg
    }
    else if(all(xl==x2) & all(xg==x3)){
      x3<-xg
      x2<-xl
      x1<-xh
    }
    else if(all(xl==x3) & all(xg==x2)){
      x3<-xl
      x2<-xg
      x1<-xh
    }
    Q<-sqrt(((f(x1)-f(x0))^2+(f(x2)-f(x0))^2+(f(x3)-f(x0))^2)/3) #acuan konvergensi
    i<-i+1 #iterasi lanjut
    dd<-t(data.frame(x1,x2,x3))
    d<-t(data.frame(f(x1),f(x2),f(x3)))
    if(trace==T) {
      cat("------","Iter:",i,"-----");cat("\n")
      cat("x1:",x1);cat("\n")
      cat("x2:",x2);cat("\n")
      cat("x3:",x3);cat("\n")
      cat("Q:",round(Q,2));cat("\n")
      cat("\n")
    }
  }
  cat("\n")
  
  #jika belum konvergen diberi warning
  ifelse(i==max.iter, return(list(optim=x0,f.optim=f(x0),warning=warning("stop.iter sama dengan max.iter yaitu pada iterasi ke-",i),Q=Q)),return(list(optim=x0,f.optim=f(x0),stop.iter=i,Q=Q)))
}

Studi Kasus

Kasus Optimasi
Misalkan fungsi objektif yang akan diminimalkan adalah: \[ f(x) = x_1 - x_2 + 2x_1^2 + 2x_1x_2 + x_2^2. \] Kita diberikan:

  • Titik awal:
    \[ x_1 = (4, 4), \, x_2 = (5, 4), \, x_3 = (4, 5), \]

  • Parameter: \[ \alpha = 1, \, \beta = 0.5, \, \gamma = 2, \, \epsilon = 0.2. \]

Langkah-Langkah:

  1. Hitung Rata-Rata Titik Non-Maksimal: \[ x_0 = \frac{x_1 + x_2}{2}. \]

  2. Refleksi: \[ x_r = (1 + \alpha)x_0 - \alpha x_h. \]

  3. Ekspansi (jika refleksi membaik): \[ x_e = \gamma x_r + (1 - \gamma)x_0. \]

  4. Kontraksi (jika refleksi gagal): \[ x_c = \beta x_h + (1 - \beta)x_0. \]

  5. Cek Kriteria Konvergensi: \[ Q = \sqrt{\frac{1}{3} \left[(f(x_1) - f(x_0))^2 + (f(x_2) - f(x_0))^2 + (f(x_3) - f(x_0))^2\right]}. \]

Implementasi R

f<-function(x){x[1]-x[2]+(2*x[1]^2)+(2*x[1]*x[2])+x[2]^2}
x1<-matrix(c(4,4));x2<-matrix(c(5,4));x3<-matrix(c(4,5));x1;x2;x3
##      [,1]
## [1,]    4
## [2,]    4
##      [,1]
## [1,]    5
## [2,]    4
##      [,1]
## [1,]    4
## [2,]    5
simptron(f,eps=0.2,x1=x1,x2=x2,x3=x3,trace=T,max.iter=10, 
   alpha=1,beta=0.5,gamma=2)
## 
## TRACING
## ------ Iter: 1 -----
## x1: 4 4
## x2: 2 5.5
## x3: 4 5
## Q: 19.05
## 
## ------ Iter: 2 -----
## x1: 4 4
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.05
## 
## ------ Iter: 3 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 20.51
## 
## ------ Iter: 4 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.66
## 
## ------ Iter: 5 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.66
## 
## ------ Iter: 6 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.66
## 
## ------ Iter: 7 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.66
## 
## ------ Iter: 8 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.66
## 
## ------ Iter: 9 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.66
## 
## ------ Iter: 10 -----
## x1: -3.5 6.625
## x2: 2 5.5
## x3: 1 4.25
## Q: 26.66
## $optim
##         [,1]
## [1,] -1.2500
## [2,]  5.4375
## 
## $f.optim
## [1] 12.41016
## 
## $warning
## [1] "stop.iter sama dengan max.iter yaitu pada iterasi ke-10"
## 
## $Q
## [1] 26.6631

Kesimpulan

  • Kelebihan:
    Metode Simpleks tanpa kendala memberikan pendekatan iteratif yang efisien untuk fungsi objektif sederhana.
  • Kekurangan:
    Sulit diterapkan pada fungsi non-linear kompleks tanpa adaptasi tambahan.
  • Aplikasi:
    Cocok untuk optimasi fungsi ekonomi, keuangan, dan produksi sederhana tanpa pembatasan.