Metode Simpleks (Tanpa Kendala)

Pengantar

Meskipun jarang, terdapat situasi di mana masalah optimasi tidak memiliki kendala. Dalam kasus seperti ini, fokus utama kita adalah pada fungsi objektif yang ingin kita maksimalkan atau minimalkan.

Teori Dasar

Masalah Optimasi Linear Tanpa Kendala: Masalah optimasi linear tanpa kendala hanya melibatkan fungsi objektif yang ingin dimaksimalkan atau diminimalkan tanpa adanya kendala.
Metode Simpleks: Meskipun metode Simpleks dirancang untuk menangani masalah optimasi linear dengan kendala, tetapi dapat juga diterapkan pada masalah tanpa kendala dengan modifikasi yang tepat.

Langkah-langkah Metode Simpleks untuk Masalah Tanpa Kendala

Inisialisasi: Mulai dengan solusi awal yang memenuhi kebutuhan masalah tanpa kendala.
Pemilihan Variabel Masuk (Entering Variable): Pilih variabel yang akan memasuki basis untuk meningkatkan atau mengurangi nilai fungsi objektif.
Pemilihan Variabel Keluar (Leaving Variable): Tentukan variabel yang akan keluar dari basis untuk mempertahankan konsistensi dalam solusi.
Reflection: Langkah ini mengatur variabel masuk dan keluar untuk mencapai solusi yang lebih baik, walaupun dalam kasus ini kemungkinan solusi yang lebih baik hanya melibatkan perubahan nilai fungsi objektif.
- Reflection Step: Menghitung refleksi terhadap titik tengah dari solusi yang ada untuk menemukan solusi yang lebih baik.
Expansion: Ekspansi adalah langkah di mana kita memperbesar atau memperpanjang langkah yang telah diambil dalam pencarian solusi.
Contraction: Ekspansi adalah langkah di mana kita mempersempit langkah yang telah diambil dalam pencarian solusi (kebalikan ekspansi).
Pengecekan Kriteria Terminasi: Periksa apakah kriteria konvergensi terpenuhi. Jika ya, berhenti, jika tidak, kembali ke langkah 3.

Fungsi Simplex based on Rao Book (Hal. 328)

Fungsi ini dibuat mandiri di R sesuai pemahaman pribadi, jadi jika ada kekurangan bisa diperbaiki mandiri juga (tapi sejauh ini outputnya sesuai dengan 2 iterasi pertama di buku Rao).

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

Minimumkan \(f(x) = x_1 - x_2 + 2x_1^2 + 2x_1x_2 + x_2^2\), Titik koordinat inisial didefinisikan sebagai berikut, \(x_1 = (4,4)\), \(x_2=(5,4)\), \(x_3=(4,5)\) dan \(\alpha=1, \beta=0.5, 𝛾=2\). Sebagai sarat konvergensi, ditetapkan \(𝜀 = 0.2\).

Definisikan fungsi dan nilai inisial

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

Masukkan ke dalam fungsi

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

Dua iterasi pertama sesuai dengan hasil pada Buku Rao hal. 333-334, tapi stop.iter = max.iter, berarti sebenarnya belum konvergen, maka max.iter perlu diperbesar. Sudah dicoba tetapi untuk case ini juga tidak konvergen, jadi dicoba ketika rasio antara jarak \(x_r\) dengan \(x_0\) terhadap jarak \(x_h\) dengan \(x_0\) diperkecil (nilai \(\alpha=0.1\)) serta ketika rasio antara jarak \(x_e\) dengan \(x_0\) terhadap jarak \(x_r\) dengan \(x_0\) diperkecil (nilai \(\gamma=0.2\)) .

simptron(f,eps=0.2,x1=x1,x2=x2,x3=x3,trace=T,max.iter=20, 
   alpha=0.1,beta=0.5,gamma=0.2)

## 
## TRACING
## ------ Iter: 1 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 2 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 3 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 4 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 5 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 6 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 7 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 8 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 9 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 10 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 11 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 12 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 13 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 14 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 15 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 16 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 17 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 18 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 19 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89
## 
## ------ Iter: 20 -----
## x1: 4 4
## x2: 5 4
## x3: 4 5
## Q: 12.89

## Warning in ifelse(i == max.iter, return(list(optim = x0, f.optim = f(x0), :
## stop.iter sama dengan max.iter yaitu pada iterasi ke-20

## $optim
##      [,1]
## [1,]  4.0
## [2,]  4.5
## 
## $f.optim
## [1] 87.75
## 
## $warning
## [1] "stop.iter sama dengan max.iter yaitu pada iterasi ke-20"
## 
## $Q
## [1] 12.89299

Bgaimana hasilnya? Bagaimana jika \(\alpha\) dan \(\gamma\) diperbesar? Bagaimana jika yang diubah adalah \(\beta\)? Interpretasikan dan jelaskan bagaimana pengaruhnya?

Modul Praktikum Opstat - Pekan 5

Muhammad Nachnoer Novatron Fitra Arss

2024-03-08