Metode Simpleks
Salah satu teknik penentuan solusi optimal yang
digunakan dalam pemrograman linier adalah metode simpleks. Penentuan solusi optimal menggunakan metode
simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi
optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara
perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks
dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya
tergantung dari iterasi sebelumnya (i-1).
Ada beberapa istilah yang sangat sering digunakan
dalam metode simpleks, diantaranya :
- Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.
- Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas dalam sistem persamaan.
- 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).
- Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas awal yang ada, karena aktivitas belum dilaksanakan.
- 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.
