Combinatorial Problem

Combinatorial problem (masalah kombinatorial)

Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi terlebih dahulu seperti permutasi atau kombinasi.
pada kehidupan sehari-hari kombinatorial dan peluang diskrit banyak sekali ditemui. Misalnya saja untuk menyelesaikan Vehicle Routing Problem (VRP) dan beberapa games sederhana yaitu Blackjack .

Kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum) adalah dua kaidah dasar untuk memecahakan persoalan menghitung dalam Kombinatorial.

1.      Kaidah perkalian

Bila percobaan ke-1 menghasilkan p kemungkinan jawaban, dan percobaan ke-2 menghasilakan q kemungkinan, maka apabila percobaan ke-1 dan ke-2 akan menghasilakan p x q kemungkinan jawaban yang mungkin terjadi.

2.      Kaidah penjumlahan

Bila percobaan ke-1 menghasilkan p kemungkinan jawaban, dan percobaan ke-2 menghasilakan q kemungkinan, maka apabila percobaan ke-1 atau ke-2 akan menghasilakan p + q kemungkinan jawaban yang mungkin terjadi.

Kata yang di garis bawahi yaitu dan serta atau. Kedua kata ini adalah kata kunci untuk mengidentifikasi apakah suatu persoalan menghitung dapat diselesaikan dengan kaidah perkalian atau kaidah penjumlahan. Kaidah perkalian menyatakan bahwa kedua percobaan dilakukan secara simultan atau serempak, sedangkan pada kaidah penjumlahan, kedia percobaan dilakukan tidak simultan.

Dalam kombinatorial juga terdapat prinsip Inklusi- Eksklusi. Prinsip ini juga dapat digunakan untuk menyelesaikan persoalan kombinatorial. rumus dari Prinsip Inklusi – Eksklusi adalah :

      |A U B|=|A| + |B| -|A∩B|

Beberapa Aplikasi mengunakan kombinatorial

A.      VRP (Vehicle Routing Problem)

Vehicle Routing Problem (VRP) merupakan permasalahan optimasi penentuan rute dengan keterbatasan kapasitas kendaraan.  Pada permasalahan ini, ada sebuah depot awal dan sejumlah n tempat untuk dikunjungi dengan demand yang dapat berbeda-beda. Sebuah kendaraan diharapkan untuk memenuhi permintaan setiap tempat tersebut dari depot.

Secara ringkas, karakterristik permasalah VRP adalah sebagai berikut :

a.      Perjalanan berawal dan berakhir dari dan ke depot awal seperti pada gambar di atas.

b.      Apabila kendaraan sudah terpakai dan tidak dapat melayani tempat berikutnya, kendaraan dapat kembali ke depot untuk memenuhi kapasitas kendaraan dan melayani tempat berikutnya.

c.       Tujuan dari permasalahan ini adalah meminimumkan total jarak yang ditempuh kendaraan dengan mengatur urut-urutan tempat yang harus dikunjungi beserta kapan kembalinya kendaraan kedepot.

Contoh dari pengunaan PRV adalah route Bus Parawisata.

Referensi  

1.      Munir,  Rinaldi, Matematika  Diskrit  Edisi  Ketiga.  Bandung  : Penerbit Informatika

https://en.wikipedia.org/wiki/Vehicle_routing_problem