Dalam menyelesaikan masalah program linear, metode grafik hanya bisa kita gunakan untuk masalah yang memiliki dua variabel peubah keputusan. Untuk itu, hadir metode lain yang bisa digunakan untuk penyelesaian masalah program linear yang memiliki 2 atau lebih variabel keputusan, salah satunya adalah metode simpleks.
Metode Simpleks adalah suatu metode yang secara matematis dimulai dari suatu pemecahan dasar yang layak/feasibel ke pemecahan dasar layak lainnya dan dilakukan secara berulang-ulang (iteratif), sehingga akhirnya diperoleh suatu pemecahan dasar yang optimal. Metode simpleks merupakan metode yang digunakan untuk mengatasi kelemahan pada metode grafik dimana pada metode simpleks jumlah variabel yang digunakan bisa lebih dari 2 variabel.
Langkah-langkah menyelesaikan masalah program linear dengan metode simpleks maksimum secara manual adalah sebagai berikut.
- Fungsi tujuan Zmaks ditambahkan variabel dasar sesuai dengan banyaknya jumlah kendala
- Fungsi kendala ditambahkan dengan matriks identitas sesuai dengan banyaknya kendala
- Buat tabel simpleks
CJ Basis Quantity Rasio Variabel X1 X2 S1 S2 Iterasi S1 S2 ZJ CJ-ZJ CJ Basis Quantity Rasio Variabel X1 X2 X3 S1 S2 S3 Iterasi S1 S2 S3 ZJ CJ-ZJ - Menentukan nilai Zj, kolom tabel dikali dengan baris variabel CJ-Zj
- Menentukan kolom kunci (kk), dilihat pada baris CJ-ZJ yang nilainya paling besar (positif)
- Menentukan rasio (R) dengan rumus R = Quantity/kolom kunci
- Menentukan baris kunci (bk), dilihat pada nilai Rasio yang paling kecil (positif)
- Pertemuan antar kolom kunci dan baris kunci menghasilkan anak kunci (ak)
- Kolom kunci selain anak kunci dijadikan bernilai 0, anak kunci dijadikan bernilai 1
- Baris kunci dibagi anak kunci
- Untuk menjadikan kolom kunci lainnya bernilai 0, maka
Bi(baru) = Bi(lama) – Koefisien × Baris kunci baru
10. Variabel kolom kunci menggantikan variabel baris kunci dan variabel
11. Selanjutnya kembali ke langkah ke-4 sampai baris CJ -ZJ ≤ 0
Namun, kita juga bisa menyelesaikan masalah program linear dengan metode simpleks kasus maksimum menggunakan POM for Windows. Berikut contoh kasus PL yang dapat diselesaikan menggunakan POM for Windows.
Contoh kasus maksimasi
Toko Berkah Jaya akan membuat 3 macam paket murah yaitu paket A, B, dan C. Paket tersebut berisi sirup, biskuit, dan permen. Paket A berisi 1 botol sirup, 2 bungkus biskuit dan 3 bungkus permen dan dijual Rp 80.000,00 per paket. Paket B berisi 1 botol sirup, 2 bungkus biskuit dan 2 bungkus permen dijual Rp 75.000,00. Paket C berisi 2 botol sirup, 1 biskuit dan 2 bungkus permen dijual Rp 70.000,00. Banyaknya sirup, biskuit dan permen yang tersedia berturut-turut adalah 17 botol, 22 bungkus biskuit dan 30 bungkus permen. Toko Berkah Jaya ingin memperoleh hasil penjualan yang sebesar-besarnya. Tentukan banyaknya masing-masing paket dengan asumsi semua paket terjual habis.
Penyelesaian:
Perumusan model dari masalah
- Misalkan: X1 = Jumlah paket A yang terjual
X2 = Jumlah paket B yang terjual
X3 = Jumlah paket C yang terjual
- Fungsi tujuan
Zmaks = 80000X1 + 75000X2 + 70000X3
- Sistem Fungsi Kendala
Kendala utama
Jumlah sirup (botol) : X1 + X2 + 2X3 ≤ 17
Jumlah biskuit (bungkus) : 2X1 + 2X2 + X3 ≤ 22
Jumlah permen (bungkus) : 3X1 + 2X2 + 2X3 ≤ 30
Kendala tak negatif
X1 ≥ 0; X2 ≥ 0; X3 ≥ 0
Penyelesaian dengan POM For Windows
- Buka aplikasi POM for Windows, klik Module dan pilih Linear Programming.
- Klik File –> New lalu tampil gambar berikut
- Isi Number of Constraints dengan banyaknya kendala (3), dan Number of Variables dengan banyaknya Variabel keputusan (3), dan dibagian Objective pilih Maximize.
Klik Oke
- Isi sesuai dengan model yang telah dibuat
- Klik Solve dan tampilannya seperti gambar berikut ini, lalu pilih 4 Iterations
- Tampilannya iterasinya seperti gambar berikut
Kesimpulan:
Dari iterasi yang diperoleh, terlihat bahwa Toko Berkah Jaya akan mendapatkan keuntungan maksimum sebesar Rp975.000,00 jika Toko Berkah Jaya menjual Paket A sebanyak 4 Paket, Paket B sebanyak 5 Paket, dan Paket C sebanyak 4 Paket.