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). Baca entri selengkapnya »