Apa Itu Metode Simpleks?
Metode Simpleks adalah algoritma numerik yang dirancang oleh George Dantzig pada tahun 1947 untuk menemukan nilai optimum (maksimum atau minimum) dari fungsi tujuan linear di bawah kendala linear. Metode ini bekerja pada ruang solusi yang berbentuk polihedron dan secara sistematis berpindah dari satu titik sudut (vertex) ke titik sudut lainnya yang meningkatkan nilai fungsi tujuan hingga tidak ada peningkatan lagi.
Prinsip Dasar
- Representasi standar: Semua masalah LP diubah menjadi bentuk standar dengan fungsi tujuan maksimalisasi, semua kendala sebagai persamaan dengan variabel surplus/slack, dan variabel keputusan nonnegatif.
- Basis dan variabel nonbasis: Pada setiap iterasi, sebagian variabel (basis) menyelesaikan sistem persamaan, sedangkan sisanya (nonbasis) bernilai nol.
- Pivoting: Proses memilih variabel masuk (entering variable) dan keluar (leaving variable) untuk memperbaiki nilai fungsi tujuan.
LangkahLangkah Metode Simpleks
- Formulasi standar: Ubah semua kendala menjadi persamaan dengan menambahkan variabel slack atau surplus.
- Matriks awal: Buat tabel Simpleks (atau tableau) yang memuat koefisien fungsi tujuan, koefisien kendala, dan nilai RHS (righthand side).
- Pilih variabel masuk: Pilih kolom dengan koefisien paling negatif pada baris fungsi tujuan (untuk maksimisasi).
- Pilih variabel keluar: Hitung rasio RHS / koefisien positif pada kolom masuk; baris dengan rasio terkecil menjadi variabel keluar.
- Pivot: Lakukan operasi baris elementer sehingga elemen pivot menjadi 1 dan semua elemen lain di kolom pivot menjadi 0.
- Ulangi: Kembali ke langkah 3 sampai tidak ada lagi koefisien negatif pada baris fungsi tujuan.
Contoh Sederhana
Masalah:
Maksimum Z = 3x + 5xsubject to 2x + 3x 8 4x + x 8 x, x 0
Langkah 1 Tambah variabel slack s, s:
2x + 3x + s = 84x + x + s = 8
Tableau awal:
| x | x | s | s | RHS | |
|---|---|---|---|---|---|
| Persamaan 1 | 2 | 3 | 1 | 0 | 8 |
| Persamaan 2 | 4 | 1 | 0 | 1 | 8 |
| Z | -3 | -5 | 0 | 0 | 0 |
Iterasi pertama memilih x sebagai variabel masuk (koefisien -5 paling negatif). Rasio RHS/koefisien positif: 8/3 2.67 dan 8/1 = 8 baris 1 keluar (s). Pivot pada elemen 3 menghasilkan tableau baru, dan seterusnya sampai semua koefisien di baris Z tidak negatif. Hasil akhir: x = 1, x = 2, Z = 13.
Kelebihan & Keterbatasan
Kelebihan
- Menjamin menemukan solusi optimal bila solusi optimum ada.
- Implementasi sederhana dan banyak dipelajari di bidang operasi riset.
- Dapat dioptimalkan secara numerik dengan teknik presolve dan anticycling.
Keterbatasan
- Kompleksitas terburuk eksponensial, meski ratarata sangat cepat.
- Kurang cocok untuk masalah sangat besar (ribuan variabel) bila tidak dipadukan dengan metode interiorpoint.
- Memerlukan data numerik yang stabil; koefisien sangat besar/ kecil dapat menimbulkan kesalahan pembulatan.
Aplikasi Praktis
Metode Simpleks banyak dipakai dalam:
- Perencanaan produksi dan penjadwalan.
- Optimasi transportasi dan distribusi.
- Manajemen persediaan.
- Pengalokasian sumber daya dalam proyek konstruksi.
- Analisis jaringan aliran maksimumminimum.
Berbagai perangkat lunak seperti LINGO, Gurobi, CPLEX, dan bahkan spreadsheet Excel menyediakan solver Simpleks yang dapat diakses dengan antarmuka grafis.
Penutup
Metode Simpleks tetap menjadi fondasi penting dalam optimasi linear. Memahami cara kerja pivot, pemilihan basis, dan interpretasi hasil membantu profesional di bidang logistik, manufaktur, keuangan, dan ilmu data untuk membuat keputusan yang lebih baik. Meskipun algoritma baru seperti interiorpoint menawarkan kecepatan pada skala sangat besar, Simpleks tetap relevan karena kesederhanaannya, transparansi solusi, dan kemampuan memberikan insight struktural tentang masalah yang dihadapi.
