Metode Simpleks

METODE SIMPLEKS

Digunakan untuk menyelesaikan masalah pemrograman linier yang mempunyai 2 variabel atau lebih.

Diperkenalkan oleh George B. Dantzig.

Didasarkan pada proses iterasi, dimana diawali dengan penentuan solusi awal.

Tahapan :

Masalah Pemrograman Linier

|

ν

Formulasi Model Pemrograman Linier

(Pada umumnya berbentuk maksimisasi)

|

ν

Bentuk Baku Pemrograman Linier

|

ν

Prosedur Algoritma Simpleks

Dalam metode simpleks, terdapat istilah yang dikenal dengan fungsi kendala. Fungsi kendala ini berbentuk

nx=1 aixcx ≤ b,           ⅀nx=1 aixcx ≥ bi, nx=1 aixcx = bi

Selain fungsi kendala, di dalam metode simpleks juga terdapat variabel slack (bentuk kanonik). Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan  pertidaksamaan ≤ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.  Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan  pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama  dengan  jumlah fungsi pembatas (tanpa fungsi non negatif).

Berikut adalah contoh variabel slack

nx=1 aixcx ≤ bi →     ⅀nx=1 aixcx + si =  bi

nx=1 aixcx ≥ bi →       ⅀nx=1 aixcx – si =  bi

LANGKAH – LANGKAH METODE SIMPLEKS :

  1. Mengubah fungsi tujuan

F = a1x1 + . . . + anxn →             F – a1x1 – . . . – anxn = 0

Dengan kata lain, kita menegatifkan konstanta dari variabel-variabel tersebut sehingga hasilnya sama dengan nol.

2. Mengubah fungsi batasan ke bentuk kanonik (slack variable)

a11x1 + a12x2 ≤ b1 a11x1 + a12x2 + s1 = b1

a21x1 + a22x2 ≤ b2 a21x1 + a22x2 + s2 = b2

3.Mengisi tabel simpleks

Tabel simpleks berbentuk seperti berikut :

VB X1 X2 S1 S2 S3 NK
F -a1 -a2 0 0 0 0
S1 a11 a12 1 0 0 b1
S2 a21 a22 0 1 0 b2
S3 a31 a32 0 0 1 b3

4. Menentukan kolom kunci

Kolom kunci ditentukan dengan cara mencari nilai yang kolom paling kecil dari F. Kita misalkan X2 adalah nilai yang paling terkecil, jadi tabelnya akan berbentuk seperti berikut :

VB X1 X2 S1 S2 S3 NK
F -a1 -a2 0 0 0 0
S1 a11 a12 1 0 0 b1
S2 a21 a22 0 1 0 b2
S3 a31 a32 0 0 1 b3

5. Menentukan baris kunci

Pertama, kita harus menentukan index dengan cara membagi NK dengan kolom kunci (NK/kolom kunci). Setelah itu, cari nilai dari index tersebut yang terkecil. Maka kita akan memperoleh baris kunci. Kita misalkan S2.

VB X1 X2 S1 S2 S3 NK INDEX
F -a1 -a2 0 0 0 0 0/-a2
S1 a11 a12 1 0 0 b1 b1/a12
S2 a21 a22 0 1 0 b2 b2/a22
S3 a31 a32 0 0 1 b3 b3/a32

6. Menentukan angka kunci

Angka kunci merupakan pertemuan antara kolom kunci dengan baris kunci. Jadi, kita memperoleh a22 sebagai angka kunci.

7. Membuat baris kunci baru

Baris kunci bari diperoleh dengan cara membagi baris S2 dengan angka kunci. Seperti pada tabel berikut :

VB X1 X2 S1 S2 S3 NK
F -a1 -a2 0 0 0 0
S1 a11 a12 1 0 0 b1
X1 a21/ a22 1 0/ a22 1/ a22 0/ a22 b2/ a22
S3 a31 a32 0 0 1 b3

8. OBE tabel

VB X1 X2 S1 S2 S3 NK
F -a1 -a2 0 0 0 0
S1 a11 a12 1 0 0 b1
X1 a21/ a22 1 0/ a22 1/ a22 0/ a22 b2/ a22
S3 a31 a32 0 0 1 b3

Baris F ditambah a2 kali baris X1

Baris S1 dikurang a12 kali baris X1

Baris S3 dikurang a32 kali baris X1

9. Menguji optimasi atau mengecek kepositifan dari baris F

VB X1 X2 S1 S2 S3 NK
F -a1 -a2 0 0 0 0
S1 a11 a12 1 0 0 b1
X1 a21/ a22 1 0/ a22 1/ a22 0/ a22 b2/ a22
S3 a31 a32 0 0 1 b3

Jika baris F bernilai positif,maka langkah telah selesai. Tapi,jika masih ada nilai dari baris F yang bernilai negatif, maka ulangi lagi dari langkah 4 yaitu menentukan kolom kunci.



Satu Tanggapan to “Metode Simpleks”

  1. tira Says:

    bagus ko.eh kulagi cari judul skripsi ini tentang masalah metode simpleks.temanya insyaallah ada,tapi masih belim srek. mungkin punya ya atau mgkn kamu di situ ada sripsi yang bisa kujadikan pedoman


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: