Riset Operasi: Metode Jaringan Rentang Pohon Minimum (Minimal Spanning Tree)

Jaringan lahir karena berbagai keperluan seperti: transportasi, listrik, komunikasi, perencanaan proyek, aliran air, pembuatan jalan, dan lain-lain. Saat ini jaringan sangat penting, sebab dengan jaringan maka masalah yang besar dan rumit dapat disederhanakan. Ada beberapa jaringan yang dapat diselesaikan dengan permasalahan program linear. Pada kajian di sini akan dibahas tiga masalah jaringan, yaitu: permasalahan lintasan terpendek, masalah diagram pohon terpendek, masalah aliran maksimum.

Dalam menggambarkan suatu jaringan kerja digunakan tiga buah simbol sebagai berikut:

Anak panah (arrow), menyatakan sebuah kegiatan atau aktivitas. Kegiatan di sini didefinisikan sebagai hal yang memerlukan jangka waktu tertentu dalam pemakaian sejumlah sumber daya (sumber tenaga, peralatan, material, biaya)
Lingkaran kecil (node), menyatakan sebuah kejadian atau peristiwa atau event. Kejadian didefinisikan sebagai ujung atau pertemuan dari satu atau beberapa kegiatan.
Anak panah terputus-putus, menyatakan kegiatan semu atau dummy . Dummy tidak mempunyai jangka waktu tertentu, karena tidak memakai sejumlah sumber daya.

Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum. Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titikdalam jaringan tersebut pada total jarak (panjang) minimum.

Prosedur Minimal Spanning Tree

Pilih sembarang node (atau untuk lebih konsisten pilih node pertama)
Hubungkan node tersebut dengan node terdekat
Kemudian, cari dan hubungkan node terdekat yang belum terhubungi.
Ulangi langkah ketiga hingga semua node terhubung

Contoh Kasus:

Andaikan perusahaan air minum daerah membangun jaringan pipa yang melewati beberapa node. Semua node harus terhubungi Dalam kasus ini seluruh node harus dapat dihubungkan, sehingga dapat diselesikan dengan metode Minimal Spanning Tree. Jalur pipa dan jarak antar node ditampilkan pada jalur berikut ini:

Jika daerah tersebut akan dipasang jaringan pipa maka jalur pipa yang harus dipasang adalah sebagai berikut:

Asumsikan titik/ stasiun A merupakan tempat awal. Kemudian buatlah tabel untuk perhitungan dari setiap stasiun.
Kemudian pilihlah jarak cabang yang memiliki jarak terpendek dari setiap stasiun.
Tandailah stasiun-staisun terpendek tersebut dengan garis atau menggunakan warna garis yang berbeda. Apabila percabangan dari suatu stasiun menuju ke stasiun berikutnya membuat sirkuit dengan stasiun sekitarnya, maka jalur stasiun tersebut tidak dapat digunakan. Dalam kasus ini, kita dapatkan jarak terpendek sebagai berikut:
Hapuslah garis yang tidak diperlukan untuk membuat spanning tree.