Apabila suatu suatu masalah Linear Programming (LP) mengandung 2 kegiatan (variabel-variabel keputusan) saja, maka dapat diselesaikan dengan metode grafik, tapi bila melibatkan lebih dari dua kegiatan maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan metode simpleks.
Metode simpleks merupakan cara yang lazim dipakai untuk menentukan kombinasi optimal dari 3 variabel atau lebih.
Mengenal Metode Simpleks
Langkah-langkah Metode Simpleks
1. Mengubah Fungsi Tujuan dan Batasan-batasan
Contoh:
Fungsi tujuan; maksimum Z = 6X1 + 8X2
Batasan:
- 3X1 + 5X2 ≤ 260
- 5X1 + 6X2 ≤ 380
- 4X1 + 3X2 ≤ 200
Fungsi tujuan diubah menjadi fungsi implisit, artinya semua CjXij digeser ke kiri. Maksimumkan Z = 6X1 + 8X2, maka menjadi Z - 6X1 - 8X2 = 0
Pada bentuk standar, semua batasan mempunyai tanda ≤, ketidaksamaan ini harus diubah menjadi kesamaan. Caranya dengan menambahkan Slack Variabel (yaitu variabel tambahan yang mewakili tingkat pengangguran atau kapasitas yang merupakan batasan).
Variabel Slack ini adalah Xn+1, Xn+2, ... Xn+m. Kadangkala Slack Variabel diberi tanda huruf lain, misalnya S1, S2, ...., dan seterusnya.
Fungsi-fungsi batasan:
- 3X1 + 5X2 ≤ 260 menjadi → 3X1 + 5X2 + X3 = 260
- 5X1 + 6X2 ≤ 380 menjadi → 5X1 + 6X2 + X4 = 380
- 4X1 + 3X2 ≤ 200 menjadi → 4X1 + 3X2 + X5 = 200
2. Menyusun Persamaan Ke Dalam Tabel
Setelah formulasi diubah kemudian disusun ke dalam tabel, tabel dalam bentuk simbol sebagai berikut:
| Variabel Dasar | Z | X1 | X2 | … | Xn | Xn+1 | Xn+2 | … | Xn+m | NK |
|----------------|---|-----|-----|---|-----|------|------|---|------|----|
| Z | 1 | -C1 | -C2 | … | -Cn | 0 | 0 | … | 0 | 0 |
| Xn+1 | 0 | a11 | a12 | … | a1n | 1 | 0 | … | 0 | b1 |
| Xn+2 | 0 | a21 | a22 | … | a2n | 0 | 1 | … | 0 | b2 |
| . | . | . | . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . | . | . | . |
| Xn+m | 0 | am1 | am1 | … | amn | 0 | 0 | … | 1 | bm |NK adalah Nilai Kanan persamaan, yaitu nilai dibelakang tanda (=). Variabel Dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan.
Contoh menggunakan soal diatas:
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | X5 | NK |
|----------------|---|----|----|----|----|----|-----|
| Z | 1 | -6 | -8 | 0 | 0 | 0 | 0 |
| X3 | 0 | 3 | 5 | 1 | 0 | 0 | 260 |
| X4 | 0 | 5 | 6 | 0 | 1 | 0 | 380 |
| X5 | 0 | 4 | 3 | 0 | 0 | 1 | 200 |3. Memilih Kolom Kunci
Kolom kunci adalah kolom yang merupakan dasar untuk mengubah tabel diatas. Pilihlah kolom pada baris fungsi tujuan (Z) yang mempunyai nilai negatif dengan angka terbesar, berilah tanda segi empat pada kolom tersebut.
Contoh menggunakan soal diatas:
4. Memilih Baris Kunci
Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel tersebut diatas. Terlebih dahulu carilah indeks tiap-tiap baris dengan cara membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada kolom kunci.
Indeks = Nilai Kolom NK / Nilai Kolom Kunci
Pilih baris yang mempunyai indeks positif dengan angka terkecil.
Tabel Pemilihan Baris Kunci
5. Mengubah Nilai-nilai Baris Kunci
Nilai baris kunci diubah dengan cara membaginya dengan angka kunci, gantilah variabel dasar pada baris yang terpilih dengan variabel yang terdapat dibagian atas kolom kunci.
Dengan kata lain nilai yang terdapat pada irisan / perpotongan baris kunci dan kolom kunci adalah terpilih sebagai nilai kunci.
Tabel cara mengubah nilai baris kunci
6. Mengubah nilai-nilai selain baris kunci
Nilai-nilai baris, selain baris kunci dapat diubah dengan rumus sebagai berikut:
Baris Baru = Baris Lama - (Koefisien pada kolom kunci) x Nilai baru baris kunci
Contoh, menggunakan soal diatas, nilai baru baris pertama (Z) sebagai berikut:
Tabel Pertama nilai lama dan tabel kedua nilai baru,
7. Re-Optimasi
Ulangi langkah-langkah perbaikan / perubahan mulai dari langkah 3 s/d. langkah 6, hingga didapatkan baris fungsi tujuan (baris pertama) tidak ada yang bernilai negatif. Jika baris Z sudah bernilai positif semua, maka proses dihentikan.
Tabel Pemilihan Kolom dan Baris Kunci dari tabel perbaikan pertama, dan nilai baru baris kunci hasil perbaikan kedua;
Nilai baru selain baris kunci:
Tabel hasil perubahan / perbaikan kedua. Tabel pertama nilai lama, tabel kedua nilai baru.
Tabel yang diperoleh dari tabel pertama s/d. perbaikan / perubahan terakhir:
Karena pada baris fungsi tujuan (Z) sudah tidak ada yang bernilai negatif (-), maka sudah dianggap optimal dengan nilai X1 = 20, X2 = 40 dan Z max = 440.
Kesimpulan:
Maka produk P (Z1) diproduksi sebanyak 20 unit dan produk Q (X2) diproduksi sebanyak 40 unit dengan laba maksimal 440 x Rp.10.000,- = Rp.4.400.000,-
Latihan
Penyelesaian Metode Simpleks vs. Grafik
Referensi:
Modul Riset Operasi, (B) "Metode Simpleks", disusun oleh Minawarti, ST.