blognya komarudin bin sayuti

blognya komarudin bin sayuti header image 2

Algoritma Simplex untuk programa linier (ver 0.2.6)

July 13th, 2011 · 5 Comments

Permasalahan programa linier LP merupakan permasalahan yang sangat penting di dunia operations research. Hal ini dikarenakan permasalahan LP sangat luas digunakan dan dapat menjadi pondasi dasar bagi permasalahan optimasi lainnya. Selain itu, penggunaan simplex untuk menyelesaikan LP memiliki sifat-sifat yang menarik.

Pentingnya algoritma simpleks

Dengan sedikit relaksasi linier, banyak problem dapat dimodelkan menjadi programa linier. Sebagai contoh, one dimensional cutting stock problem dapat dimodelkan menjadi programa linier dengan tingkat galat (error) kurang dari jumlah pola. Selain itu, programa linier sudah digunakan untuk persoalan terapi radiasi, dan persoalan-persoalan programa integer yang memiliki sifat total unimodularity.

Peran algoritma simpleks lainnya adalah algoritma tersebut menjadi pondasi penyelesaian pada metode branch and bound untuk programa integer. Setiap kendala variabel yang harus integer akan dicabangkan menjadi dua programa linier baru. Percabangan akan terus dilakukan selama bound belum menunjukkan ketidakoptimalan atau belum semua kendala integer dipenuhi. Programa integer ini memiliki penggunaan yang sangat luas di bidang operations research, seperti transportasi, layout, perencanaan produksi, dan lain-lain.

Karakteristik algoritma simpleks sangat menarik dikaji. Dalam sudut pandang computer science, worst case dari algoritma simpleks termasuk algoritma NP (nonpolynomial deterministic). Artinya dalam worst case, jumlah iterasi dan jumlah waktu komputasi yang dibutuhkan algoritma simpleks akan bertambah secara eksponensial seiring dengan bertambahnya variable yang harus dicari. Akan tetapi, hal ini jarang sekali terjadi. Secara rata-rata, performa algoritma simpleks adalah linier. Selain itu, algoritma simpleks menjamin solusi global optimum dapat dicapai.

Penjelasan tentang algoritma simpleks

Algoritma simplex memiliki tiga bagian utama, yakni:

  1. Initialization
  2. Iteration, dan
  3. Termination.

Untuk memulai algoritma simpleks, kita perlu mengubah LP problem menjadi bentuk umum terlebih dahulu. Hal ini biasanya dicapai dengan pengubahan tujuan optimasi menjadi maximization. Pengubahan ini sebenarnya tidak harus, tetapi menjadi penting kalau kita ingin menyeragamkan aturan pencarian leaving variable. Kemudian, ruas kanan dari constraints harus diubah menjadi positif. Selain itu, kita perlu menambahkan variabel slack, surplus dan artificial sebagai pengubahan dari pertidaksamaan menjadi persamaan dan juga sebagai relaksasi dari persamaan dalam constraints.

Pada initialization, simplex berusaha mencari nilai solusi yang feasible. Hal ini didapat dengan menjadikan nilai variable slack/surplus/artificial sebagai basic variable. Sehingga, nilai-nilai dari variable lainnya (biasanya variable yang ingin kita cari) menjadi nol karena mereka menjadi nonbasic variable. Jika kita memiliki constraints yang semuanya memiliki tanda <=, maka solusi awal akan mudah didapat. Akan tetapi, jika kita memiliki persoalan LP yang memiliki constraints dengan tanda = atau >=, maka kita perlu menggunakan metode Big M atau metode dua fase agar mendapatkan solusi awal yang fesible.

Iterasi simpleks ditujukan untuk mencari adakah solusi lain yang lebih baik dari solusi yang sekarang. Hal ini dicapai dengan mencari entering variable dan leaving variable. Jika kedua variabel tersebut dapat ditemukan, maka posisi kedua variabel akan ditukar. Variabel entering yang tadinya nonbasic variable diubah menjadi basic variabel, sedangkan leaving variable yang tadinya basic variable diubah menjadi nonbasic variable.

Pada maximization, entering variable diidentifikasi dengan melihat Zj – cj yang bernilai negatif. Biasanya nilai yang paling negatif akan dipilih sebagai entering variabel. Kemudian,  ratio untuk tiap-tiap baris dicari dengan membagi nilai ruas kanan dengan koefisien yang berada di kolom entering variable. Baris dengan nilai ratio paling kecil akan ditentukan sebagai leaving variable. Entering variable dipilih yang paling negatif agar diharapkan peningkatan Z menjadi paling besar. Sementara nilai ratio dipilih yang paling kecil karena merupakan batasan yang paling ketat diantara constraints yang ada.

Setalah didapat entering variable dan leaving variabel, maka simplex tableau akan di-update. Koefisien perpotongan antara baris leaving variable dengan kolom variable akan diubah menjadi satu (dengan membagi baris leaving variable dengan koefisien tersebut). Setelah itu, baris2 lainnya termasuk baris Z juga diupdate dengan me-nol-kan nilai koefisien yang berada diatas dan dibawah koefisien perpotongan. Cara update simplex tableau ini serupa dengan operasi Gauss-Jordan pada matkul aljabar linier dasar yang melelahkan.

Iterasi simpleks tersebut akan diulang terus sampai dipenuhinya kondisi terminasi. Kondisi terminasi ada tiga macam:

  1. Kondisi optimum simplex tableau, didapat apabila tidak diperolehnya entering variable dan semua constraints awal terpenuhi (nilai artificial variable menjadi nol)
  2. Kondisi unbounded simplex tableau, didapat apabila diperolehnya entering variable tetapi tidak diperolehnya leaving variable. Hal ini menandakan Z dapat ditingkatkan terus tanpa melanggar constraints yang ada
  3. Kondisi infeasible simplex tableau, didapat apabila tidak diperolehnya entering variable akan tetapi ada pelanggaran terhadap constraint (nilai artificial variable yang masih > 0)

Untuk mempermudah mencerna uraian diatas, saya sampaikan diagram alir algoritma simpleks sebagai berikut:

 

 

Program untuk algoritma simpleks

Untuk mempermudah kita dalam belajar dan menggunakan metode simpleks, berikut saya sampaikan penerapan algoritma simpleks tersebut dalam excel. Silahkan download disini:

Simplex ver_0.2.6

Algoritma ini memang masih belum sempurna dan memerlukan sumbang saran dan perbaikan dari rekan-rekan semua. Karakteristik, fitur dan batasan pada penerapan algoritma simplex di atas adalah sebagai berikut:

  • penyelesaian LP dengan algoritma simplex
  • setiap LP diselesaikan dengan mode maximization
  • semua variabel dianggap memiliki batasan >= 0
  • hubungan dalam constraints hanya dapat memiliki <=, >= dan =
  • angka right hand side yg negatif diubah menjadi positif
  • penambahan slack, surplus dan artificial variabel secara otomatis
  • Metode Big M digunakan apabila solusi dasar tidak feasible
  • identifikasi solusi akhir sebagai optimum, unbounded atau infeasible
  • fitur laporan iterasi
  • fitur batasan jumlah iterasi dan waktu komputasi

Selain itu, ada beberapa hal yang bisa digunakan:

  • variable yang boleh bernilai angka positif dan negatif dapat dimodelkan (secara manual) sebagai x = x_plus – x_min 

 

Berikut adalah cara penggunaan template tersebut:

Misalkan kita memiliki permasalahan LP sebagai berikut:

objective function: maximize 5x_1 + x_2 + 3x_3 + 4x_4

dengan constraints:

x_1 + 3x_2 + 4x_3 + 3x_4 = 20

4x_1 + 6x_2 + 5x_3 – 4x_4 <= 40

2x_1 – 3x_2 + 3x_3 + 8x_4 >= 50

 
Permasalahan tersebut diinput ke dalam excel diatas sebagai berikut:

 

 

Kemudian setelah di-run, kita akan mendapatkan beberapa worksheet sebagai berikut:

  • worksheet 'Model' yang berisi model awal ditambahkan variable slack, surplus, dan artificial. Selain itu, setiap problem akan diubah menjadi maximization
  • worksheet 'Initialization', berisi tentang solusi awal dari simplex tableau
  • worksheet 'SimplexIteration', berisi tentang iterasi dari simplex tableau
  • worksheet 'Solution', berisi hasil solusi yang berasal dari simplex tableau iterasi terakhir

 

Worksheet model:

 

Worksheet initialization:

 

Worksheet SimplexIteration:

 

Worksheet Solution:

Print Friendly, PDF & Email

Tags: Linear Programming

5 responses so far ↓

  • 1 eko hariyanto // Jul 16, 2011 at 10:26 pm

    Pak Komaruddin,
    Apa yang Bapak hasilkan benar-benar bermanfaat.

    terimakasih,
    Eko H

  • 2 Forecasting: Moving Average dan Weighted Moving Average // Sep 28, 2011 at 3:13 am

    […] Selain dapat digunakan untuk proses forecasting, template excel diatas juga dapat digunakan untuk mencari parameter yang paling tepat bagi kedua metode tersebut. Untuk MA, template tersebut akan mencari jumlah periode yang dapat menghasilkan MAPE yang paling rendah. Sedangkan untuk WMA, selain mencari jumlah periode, template tersebut dapat mencari bobot-bobot bulan sebelumnya demi mendapatkan akurasi yang tinggi. Fitur yang pertama hanya mencoba semua kemungkinan yang disediakan oleh pengguna, sedangkan fitur yang kedua menggunakan algoritma simpleks yang pernah dibahas disini. […]

  • 3 Teknik Big-M dan teknik Two-phase dalam algoritma simplex // Apr 3, 2012 at 4:03 am

    […] postingan sebelumnya, kita telah membahas secara singkat tentang algoritma simplex. Akan tetapi, ketika fase […]

  • 4 Degeneracy dan cycling pada algoritma simplex // Apr 17, 2012 at 1:34 pm

    […] solusi global optimum dapat tercapai (seperti disebutkan di post ini), ada keadaan ketika algoritma simpleks mengalami kemacetan. Ada dua istilah yang berkaitan dengan […]

  • 5 teknik kimia // Jan 19, 2013 at 6:55 am

    masih bingung caranya