Di SMA dulu ada bab yang ngebahas soal seperti ini : Pada lahan persegi panjang yang 3 sisinya harus diberi pagar, tentukan panjang dan lebar lahan agar luasnya maksimum jika tersedia pagar sepanjang 50 meter. Artinya, dengan batasan x+2y = 50, tentukan x dan y agar x*y maksimum. Kasus linear seperti itu (karena kalau digambar grafik luas lahan terhadap x terlihat garis lurus) bisa diselesaikan dengan rumus standar, kalkulator, dan sedikit corat-coret.
Nah, kalau kasusnya kompleks, seperti TSP (bagi yang belum tahu, bayangkan ada beberapa tujuan yang harus dikunjungi, lalu tentukan urutan tujuan agar panjang perjalanan minimum) masalahnya bukan linear (digambar di grafik nggak akan ada polanya). Mencoba satu-satu seluruh urutan tujuan nggak akan selesai, untuk 15 tujuan saja ada 43 milyar permutasi yang mungkin. Kasus lain misal urutan penjadwalan kuliah agar perjalanan dosen dan mahasiswa antar ruang kelas minimum, penentuan kapasitas mesin pabrik agar jam kerja operator minimum, dan pembagian penumpang antar penerbangan agar keuntungan maskapai sebesar mungkin.
Salah satu cara yang (relatif) sederhana untuk kasus macam TSP adalah algoritma genetik (algen). Kalau urutan kota diperlakukan sebagai kromosom, maka kromosom-kromosom awal (acak) bisa saling dikawinkan (ambil 2 kromosom, hasilkan kromosom baru dengan awalan dari kromosom pertama dan akhiran dari kromosom kedua), dimutasi (tukar posisi secara acak), membuat generasi baru setelah membuang kromosom yang jelek (perjalanan terpanjang), terus menerus sampai ditemukan kromosom dengan perjalanan yang relatif pendek (kalau mau sampai minimum sama saja mencoba semua kemungkinan) atau sampai setelah beberapa generasi tidak ada perkembangan.
Dari segi pemrograman, algen termasuk mudah diterapkan, hanya menentukan batasan dan tujuan, tidak perlu mencari sifat matematis lain. Dengan program matematika sejenis Matlab, algen termasuk fitur “tinggal pakai”. Tapi bagaimana dengan kebanyakan orang yang hanya tahu Excel? Sama seperti Analysis ToolPak (add-in Excel untuk analisa statistik) yang bisa menggantikan fungsi (sebagian kecil, tapi termasuk fungsi yang paling banyak dipakai) SPSS sejak Office XP, di Office 2010 Solver add-in bisa nggantiin (sebagian kecil, tapi termasuk fungsi yang paling banyak dipakai) program matematis untuk algen. Solver sendiri sudah tersedia di versi-versi sebelumnya, hanya di versi 2010 ini ditambahkan fitur untuk algen (sejak versi lama sudah ada algen, tapi di Solver Premium, bukan yang ada di Excel).
Solver defaultnya tidak diload pada Excel, untuk mengaktifkan, klik File-Options, di bagian Add-Ins, pilih Manage Excel Add-Ins dan Go, centang Solver Add-in (dan Analysis Toolpak kalau mau) lalu klik OK. Di tab Data sekarang ada tombol Solver dalam grup Analysis. Cara pakainya, pertama buat dulu cell-cell untuk parameter, dengan 1 cell yang berisi hasil perhitungan (menggunakan fungsi Excel). Lalu, klik Solver, tentukan cell hasil dan tujuan yang diinginkan (minimum, max, atau nilai tertentu), parameter yang bisa diubah, dan batasan-batasan mereka, kemudian metode yang dipakai (Evolutionary untuk algen). Contoh file Excel yang menunjukkan kasus TSP dan pemakaian Solver ada disini.
Pada file yang didownload, kolom A dan B menyatakan posisi X dan Y tujuan, sementara kolom C menyatakan urutan tujuan. Lalu, kolom D dan E menyatakan posisi X dan Y tiap urutan tujuan. Kolom F menyatakan jarak antar tujuan kedua dan pertama, tujuan ketiga dan kedua, dst sampai tujuan ke-12 dan ke-11. Anda bisa bereksperimen sendiri dengan mengubah-ubah nilai di kolom A,B dan C, pastikan nilai di kolom C selalu diantara 1 dan 12, dan tidak ada perulangan. Nah, untuk melihat Solver beraksi, klik Solver, pilih Load/Save, dan pilih area J1 sampai J8. Jika ditanya Replace/Merge, pilih Replace. Coba klik Solve, perhatikan di bawah akan ada Incumbent yang menurun perlahan-lahan, sampai stagnan di nilai tertentu. Kalau dibiarkan, Solver akan berhenti setelah stagnan melebihi waktu yang ditentukan. Untuk langsung menghentikan, tekan Esc. Di dialog yang muncul, ada pilihan untuk memakai nilai yang dihasilkan atau mengembalikan ke nilai semula, dan membuat sheet berisi laporan proses (centang Outline Reports dan pilih reports yang ada diatasnya) .
Keterbatasan Solver terletak pada kemampuan Excel. Kasus yang perlu dipecahkan harus bisa dijelaskan dengan fungsi standar Excel atau VBA 7 (secara teori, kasus apapun, tapi ini sama saja mengatakan secara teori Pasifik bisa diseberangi dengan kayak). VBA 7 bisa memanggil fungsi/kelas dalam bahasa pemrograman lain, meski di titik ini lebih mudah untuk langsung memakai/membuat framework algen di bahasa pemrograman tersebut (untuk programmer .NET, coba AForge.NET).
Baca Selengkapnya..
Posts
