Riset Operasi... (i) Mengenal Simplex

Riset operasi merupakan cabang ilmu matematika yang berusaha mengoptimalkan sesuatu untuk menemukan suatu solusi yang terbaik. Kata kuncinya terletak pada kata "optimal" dan "solusi".

Sesungguhnya, kalian pasti sudah pernah belajar riset operasi. Di SMA, ada pelajaran yang bernama "Pemrograman Matematika". Itu adalah nama lain dari "Riset Operasi". Beberapa artikel di blog ini, juga merupakan kasus dari riset operasi:
1. Cara Memanggang Roti Secara Efisien
2. Cara Membeli Tiket Sang Profesor
3. Menghitung Volume Minimum Kerucut
4. Membantu Perancang Jalan Raya
5. Lintasan Terpendek Salesman (TSP/ Traveling Salesman Problem)
Dan, masih banyak lagi kasus lainnya....

Meskipun, Riset Operasi secara mendalam dipelajari di kuliah, tak ada salahnya kan kita belajar ini. Pelajaran ini sungguh menarik dan menyenangkan. :)

---

Algoritma Simplex adalah algoritma yang digunakan untuk mengoptimalkan fungsi objektif dan memperhatikan semua persamaan kendala. Di SMA, kita sudah belajar hal ini dengan menggunakan grafik 2D, namun algoritma ini lebih ampuh, karena dapat menyelesaikan sebanyak apapun kendala yang diberikan. Selain itu, algoritma ini memberikan informasi lebih (dual price) dalam mengambil keputusan. Algoritma ini ditemukan oleh George Dantizg dari USA (1950) yang didasarkan oleh konsep matriks invers.

Mari kita lihat bagaimana cara menggunakan algoritma Simplex ini dengan suatu masalah yang sederhana.

Suatu perusahaan ingin memproduksi 2 jenis barang, yaitu kursi dan meja. 1 Kursi membutuhkan material: 2 kg kayu, 1 kg plastik, dan 1 kg besi. 1 meja membutuhkan material 1 kg kayu, 2 kg plastik, dan 3 kg besi. Ternyata, perusahaan itu setiap jamnya hanya mampu menyediakan maksimal 16 kg kayu, 11 kg plastik, dan 15 kg besi. Untuk penjualan, 1 kursi dapat dijual seharga 30$, sedangkan 1 meja dapat dijual seharga 50$. Jadi, berapa banyak kursi dan meja yang harus diproduksi oleh perusahaan itu setiap jamnya agar keuntungannya maksimum?

[JAWAB]
Coba kalian kerjakan kasus sederhana tersebut dengan cara SMA..

Pertama-tama, buat tabel yang merepresentasikan kasus di atas, lalu buatlah kalimat matematikanya.

Fungsi Objektif:

Kendala:

Kendala variabel:

Kemudian, gambarkan grafiknya.

Dapat dilihat dari grafik bahwa ada 5 titik potong, yaitu: (0,0), (0,5), (3,4), (7,2), dan (8,0). (Titik (3,4) dan (7,2) sebenarnya didapat dengan cara substitusi/ eliminasi).

Dengan memasukkan kelima titik itu dalam fungsi objektif, maka kita menemukan titik optimumnya... :)
(0,0) Z = 0
(0,5) Z = 250
(3,4) Z = 290
(7,2) Z = 310
(8,0) Z = 240

Titik optimumnya adalah (7,2). Artinya:
Setiap jam, jumlah kursi yang diproduksi haruslah sebanyak 7, dan jumlah meja yang diproduksi haruslah sebanyak 2, sehingga dapat menghasilkan keuntungan sebesar 310$.

Cara menyelesaikan masalah seperti di atas memang terlihat mudah, karena cukup mencari titik potong dan tinggal memasukkannya ke fungsi objektifnya. Namun, ada kekurangan yang sangat fatal: Metode grafik tidak bisa digunakan jika variabelnya lebih dari 2.. Maka, kita gunakan metode simpleks, yang akan menutupi kekurangan itu.

Berikut akan dijelaskan cara menggunakan metode simpleks.

Pertama-tama, buat kalimat matematikanya:

Fungsi Objektif:

Kendala:

Kendala variabel:

Persamaan yang seperti di atas disebut juga sebagai SIMPLEKS STANDAR, karena fungsinya sudah bersifat maksimum, semua kendala variabelnya "", semua ruas kanan dari kendala merupakan konstanta yang , dan lambang kendala-kendalanya semuanya adalah "".

Kalau sudah standar seperti di atas, kita bisa langsung menyelesaikannya dalam simpleks. Jika belum standar, maka sebaiknya kita modifikasi terlebih dahulu (akan dijelaskan kemudian)..

Sekarang, kita akan mencoba ber-simpleks ria. :).
Lihat kembali persamaan kendala di atas. Ambil salah satu, misalnya: . Kita akan mencoba membuat pertidaksamaan itu menjadi persamaan. Artinya, akan muncul suatu variabel baru yang nilainya tidak diketahui. Kita namakan variabel itu sebagai variabel Slack, karena berfungsi untuk menampung nilai sisa.
Jadi, dapat dibentuk menjadi: dimana .
Jika kalian masih bingung, silakan coba-coba mengecek kebenaran persamaan di atas.
___Misalkan apabila k = 1 dan m=3, maka:
______2 (1) + 3 ≤ 16 5 ≤ 16 BENAR
______2 (1) + 3 + S1 = 16 S1 = 11 S1 ≥ 0 BENAR
___Misalkan apabila k = 8 dan m=1, maka:
______2 (8) + 1 ≤ 16 17 ≤ 16 SALAH
______2 (8) + 1 + S1 = 16 S1 = -1 S1 ≥ 0 SALAH

Dengan demikian, kita dapat menulis kembali semua kendala dalam bentuk "=", sehingga menjadi:

Fungsi Objektif:

Kendala:

Kendala variabel:

,
, ,

Langkah terakhir yaitu: mengubah fungsi objektif sedemikian rupa nilai kanannya adalah konstanta. (Konstanta tidak harus positif.)..

Pindahkan ruas kanan ke ruas kiri, menjadi:

Dengan demikian, kita dapat menuliskan kembali persamaan matematikanya menjadi:

Fungsi Objektif:

Kendala:

Kendala variabel:

,
, ,

Setelah ini, kita tinggal memasukkannya ke TABLE AWAL SIMPLEKS:

Hmmm... Tentunya, tak ada masalah bukan memasukkan konstanta yang sudah ada ke dalam tabel? Sekarang, kita lihat tabel di atas. Sebenarnya, dari tabel di atas, kita seharusnya sudah tahu nilai dari masing-masing variabel, yaitu: Z = 0, k=0, m=0, S1 = 16, S2 = 11, dan S3 = 15. Inilah solusi awal simpleks, yaitu (k,m) = (0,0). Selain itu, baik kolom Z, S1, S2, dan S3, semuanya membentuk matriks identitas . Artinya, Z, S1, S2, dan S3 adalah variabel yang berhubungan dengan RHS, sedangkan variabel selain itu (k dan m) akan bernilai nol. Variabel yang membentuk matriks identitas ini disebut juga sebagai variabel basis.

Maka, dari tabel di atas, kita dapat menambahkan 1 kolom baru: Variabel Basis, menjadi seperti berikut:

Tabel 1: Iterasi I: TABLE AWAL SIMPLEKS

Selanjutnya, gunakan TAHAPAN-TAHAPAN SIMPLEKS berikut:

1.	Dari baris Z pilih angka yang negatif dan paling negatif. Maka kolom itu menjadi kolom kunci.
2.	Hitung rasio tiap baris. Pilih yang terkecil dan positif. Maka baris itu menjadi baris kunci. Perpotongan baris kunci dan kolom kunci dinamakan pivot.
3.	Ubah pivot menjadi 1 dengan operasi perkalian.
4.	Ubah sel-sel pada kolom kunci (kecuali pivot) menjadi nol dengan operasi matematika.
5.	Ubah variabel basis menjadi yang sesuai.
6.	Jika di baris Z, masih ada sel yang negatif maka ulangi langkah nomor 1. Jika semua sel sudah positif, maka iterasi selesai, dan kondisi optimum sudah terpenuhi.

Jika membaca langkah-langkah di atas membuat kalian bingung, maka lebih baik di-skip, dan kita akan langsung ke contoh saja.

ITERASI PERTAMA:
Tabel awal:

1.	Di baris Z ada 2 nilai negatif, yaitu -30 dan -50. Karena -50 adalah yang paling negatif, maka kita pilih kolom m sebagai kolom kunci.
2.	Sekarang, kita hitung rasio di tiap baris kendala. Rasio tiap baris dihitung dengan membagi RHS dengan sel di kolom kunci. Rasio yang terkecil dan positif adalah 5. Artinya kendala ke-3 menjadi baris kunci. Pivot adalah perpotongan antara baris kunci dan kolom kunci.
3.	Supaya pivot menjadi "1", maka bagilah baris ke-4 dengan 3, maka menjadi:
4.	Selanjutnya, usahakan agar sel-sel yang berada di kolom kunci semuanya menjadi nol. (kecuali pivot). Caranya, seperti eliminasi Gauss-Jordan. Baris pertama yang baru = baris pertama yang lama + 50 * baris ke-4. Baris kedua yang baru = baris kedua yang lama - baris ke-4 Baris ketiga yang baru = baris ketiga yang lama - 2* baris ke-4. Maka, hasilnya adalah sebagai berikut:
5.	Langkah ini sungguh mudah. Cukup mengeluarkan "S3" dari variabel basis dan menggantinya dengan "m".
6.	Ternyata, di baris Z masih terdapat sel negatif, yaitu -13.333. Oleh karena itu, kita lakukan iterasi berikutnya dengan menggunakan langkah yang sama seperti pada nomor 1 s/d 6, namun menggunakan tabel yang terakhir diperoleh.

ITERASI KEDUA:
Tabel awal:

Dengan menggunakan langkah-langkah yang sama persis seperti di atas, maka kita dapatkan hasil akhir iterasi kedua, sbb:

Karena masih ada sel yang negatif di baris Z, maka kita lakukan iterasi berikutnya.

ITERASI KETIGA:
Tabel awal yang digunakan sama seperti hasil akhir iterasi kedua. Langkah-langkah yang digunakan tetap sama. Maka kita dapatkan hasil akhir iterasi ketiga sbb:

Karena semua sel di baris Z sudah semuanya non-negatif, maka iterasi berakhir, dan penyelesaian didapat dengan melihat variabel basis dan RHS yang bersesuaian:

k = 7, m = 2 dengan Z(maks)= 310

---

1.	Sebenarnya, apakah yang dilakukan iterasi-iterasi simpleks pada contoh di atas? Ans: Supaya jelas, kita lihat kembali tabel-tabel simpleks di atas dari iterasi awal hingga akhir: Iterasi 1 awal: ====== k = 0, m=0, Z = 0 ====== Iterasi 2 awal: ====== k = 0, m=5, Z = 250 ====== Iterasi 3 awal: ====== k = 3, m=4, Z = 290 ====== Iterasi 4 (3 akhir): ====== k = 7, m=2, Z = 310 ====== Dapat dilihat bahwa semakin iterasi, maka nilai Z akan semakin meningkat. Lebih jauh lagi, jika dilihat dari grafik, sebenarnya iterasi simpleks berjalan mengitari daerah yang dibatasi oleh titik-titik pojok dan dia akan berhenti jika dia tidak dapat bergerak lagi. Perhatikan gambar di bawah: Dan, kalau ditanya, apakah simpleks selalu berjalan berlawanan arah jarum jam, maka jawabannya "tidak".. Itu tergantung pada pemilihan kolom kunci..
2.	Mengapa kolom kunci dipilih yang negatif dan terkecil? Kolom kunci yang negatif menandakan bahwa fungsi Z masih bisa ditingkatkan lagi. Jika memilih kolom yang positif, justru akan mengurangi nilai Z. Mengapa harus terkecil? Sebenarnya, tidak harus terkecil. Yang penting dia negatif. Pemilihan terkecil dilakukan karena akan menghasilkan nilai Z yang terbesar di iterasi berikutnya.
3.	Mengapa rasio yang diambil adalah rasio yang positif dan terkecil? Rasio negatif akan mengurangi nilai Z. Rasio nol tidak mempengaruhi nilai Z. Jadi, rasio positif diambil agar menambah nilai Z. Dipilih yang terkecil karena jika diambil yang lebih besar, maka menyebabkan adanya RHS yang negatif, sehingga kondisi menjadi tidak layak.
4.	Apakah yang dimaksud dengan kondisi yang layak dan kondisi yang tidak layak? Kondisi layak (feasible solution) adalah kondisi di mana variabel basis (solusi) sesuai dengan kendalanya, sebaliknya jika variabel basis tidak sesuai dengan kendala, maka kondisi tersebut tidak layak. Secara grafik, kondisi layak dinyatakan dalam daerah arsir. Contoh: Diberikan kendala sbb: Maka, k= 1 dan m=0 adalah solusi yang layak, karena berada dalam range kendala, sedangkan k=11 dan m=0 bukan solusi yang layak karena 2(11) + 0 lebih dari 16 sehingga melanggar salah satu kendala yang diberikan.

---

Dengan menggunakan metode simpleks "yang mudah", kerjakan soal-soal berikut. :)

1.	Maksimumkan fungsi dengan kendala sebagai berikut:
2.	Maksimumkan fungsi dengan kendala sebagai berikut:

Berikut adalah jawaban dari kedua soal di atas:

1.
2.

---

CLOSING

Demikian post MENGENAL SIMPLEKS.. Akan lebih baik jika kalian dibekali dengan pengetahuan mengenai "Eliminasi Gauss-Jordan" karena setiap iterasi simpleks akan menggunakan cara tersebut.

Jika merasa kesulitan mengenai pengerjaan simpleks standar, silakan tanya saya..

Jika kalian sudah 100% paham mengenai Simpleks Standar dan sudah bisa mengerjakan soal latihan yang diberikan di post ini, maka kalian bisa melanjutkan membaca post berikutnya -- yang lebih menarik. :)

Riset Operasi...(ii) SIMPLEKS NON STANDAR