Menurut Lawler (1976), analisis kombinatorial adalah studi matematika tentang pengaturan, pengelompokan, pemesanan, atau pemilihan objek diskrit, biasanya terbatas jumlahnya (finite in number).
Contoh:
- Diberikan: Set poin dalam pesawat Euklidean
- Tujuan: Menemukan perjalanan putaran terpendek
Catatan:
- putaran atau lingkaran perjalanan sesuai dengan urutan poin
- solution component: perjalanan segmen terdiri dari dua poin
- yang dikunjungi satu langsung setelah yang lain
- candidate solution: perjalanan
- solution: pulang-pergi dengan panjang minimal
Contoh lain permasalah kombinatorial :
- mencari perjalanan keliling terpendek/termurah (TSP)
- menemukan model formula propositional (SAT)
- Perencanaan, penjadwalan, waktu-tabling.
- routing paket data internet
- Prediksi struktur protein
- penentuan pemenang lelang Kombinatorial
Salah satu bentuk dari masalah kombinatorial adalah TSP (Travelling Salesman Problem). TSP sebagai masalah yang mudah dipahami tapi sulit untuk dipecahkan (mendapat solusi optimal). Dengan semakin banyaknya jumlah kota yang dilibatkan, pencarian solusi untuk pemilihan rute terbaik untuk mengunjungi n kota akan semakin sukar. Oleh karena itu dibutuhkan suatu program yang dapat menyelesaikan tugas tersebut. Metode enumerasi lengkap harus menguji n! kemungkinan solusi. Untuk masalah sederhana dengan n = 20 ada lebih dari 2, 4 × 1018 kemungkinan solusi. Jika dengan menggunakan perhitungan komputer mungkin memerlukan waktu lebih dari 5 jam untuk melakukan enumerasi lengkap, sebuah hal yang tidak bisa diterima secara praktis. Algoritma pendekatan dalam berbagai literatur telah sukses diterapkan pada berbagai masalah kombinatorial seperti perencanaan dan penjadwalan produksi pada industri manufaktur. Meskipun solusi optimum tidak diperoleh, tetapi solusi yang mendekati optimum bisa didapatkan dalam waktu yang relatif singkat dan dapat diterima secara praktis.
Referensi :
Selanjutnya :
No comments:
Post a Comment