PENYELESAIAN MASALAH TRANSPORTASI UNTUK MENCARI SOLUSI OPTIMAL DENGAN PENDEKATAN MINIMUM SPANNING TREE (MST) MENGGUNAKAN ALGORITMA KRUSKAL DAN ALGORITMA PRIM


Yusufiani Nurlinawati Dili(1*), Elis Ratna Wulan(2), Fadilah Ilahi(3)

(1) UIN Sunan Gunung Djati Bandung, Indonesia
(2) UIN Sunan Gunung Djati Bandung, Indonesia
(3) UIN Sunan Gunung Djati Bandung, Indonesia
(*) Corresponding Author

Abstract


Penelitian ini membahas tentang penyelesaian masalah transportasi dengan pendekatan Minimum Spanning Tree (MST) menggunakan algoritma Kruskal dan algoritma Prim untuk mencari solusi optimal. Algoritma Kruskal dan algoritma Prim merupakan algoritma dalam teori graf untuk mencari Minimum Spanning Tree (MST). Langkah algoritma Kruskal yaitu mengurutkan biaya dari yang terkecil hingga terbesar. Selanjutnya, pilih biaya yang paling terkecil. Kemudian, lakukan perhitungan dengan melihat sumber persediaan dan permintaan di setiap tujuan sampai semuanya terpenuhi, sehingga terlihat bentuk Minimum Spanning Tree (MST) dari algoritma Kruskal. Sedangkan langkah algoritma Prim yaitu dengan memilih sembarang titik atau sumber. Selanjutnya, pilih active edge dengan biaya terkecil. Kemudian, lakukan perhitungan dengan melihat sumber persediaan dan permintaan di setiap tujuan sampai semuanya terpenuhi, sehingga terlihat bentuk Minimum Spanning Tree (MST) dari algoritma Prim. Bentuk dari Minimum Spanning Tree (MST) menghasilkan solusi yang optimal. Dari hasil penelitian ini, pendekatan Minimum Spanning Tree (MST) dengan algoritma Prim yang lebih unggul.

 


Keywords


Minimum Spanning Tree (MST), Graf, Solusi Optimal, Algoritma Kruskal, Algoritma Prim

Full Text:

PDF

References


Akpan and Iwok, "A Minimum Spanning Tree Approach of Solving a Transportation Problem," International Journal of Mathematics and Statistics Invention (IJMSI), vol. 5, no. 3, pp. 08-17, 2017

S. Johannes, Riset Operasi untuk pengambilan keputusan, Jakarta: Salemba empat, 1988

J. J. Siang, Riset Operasi dalam Pendekatan Algoritmis, Yogyakarta: C.V Andi Offset, 2011

R. Munir, Matematika Diskrit edisi ketiga revisi keempat, Bandung, 2010.

J. Erickson, Algorithms, USA: Department of Computer Science University of Illinois Urbana-Champaign, 2013.

Y. S. Kusumah, Matematika Diskrit, Bandung: CV. Andira, 1998.

J. J. Siang, Matematika Diskrit dan Aplikasinya Pada Ilmu Komputer, Yogyakarta: C.V Andi, 2002.

N. Girmay and T. Shaima, "Balance An Unbalanced Transportation Problem By A Heuristic Approach," International Journal of Mathematics and Its Applications (IJMAA), vol. 1, pp. 12-18, 2013.

K. Aljanabi and A. Jasim, "An Approach for Solving Transportation Problem Using Modified Kruskal's Algorithm," International Journal of Science and Research (IJSR), vol. 4, no. 7, 2015.

D. M. Alkubaisi, "Modified VOGEL Method to Find Initial Basic Feasible Solution (IBFS) Introduction a New Methodology to Find Best IBFS," Business and Management Research, vol. 4, no. 2, 2015.

A. Quddos, S. Javaid and M. Khalid, "A Revised Version of ASM-Method For Solving Transportation Problem," International Journal of Agricultural and Statistical Sciences, vol. 12, pp. 267-272, 2016.




DOI: https://doi.org/10.15575/kubik.v6i1.13907

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 Yusufiani Nurlinawati Dili, Elis Ratna Wulan, Fadilah Ilahi

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.


Journal KUBIK: Jurnal Publikasi Ilmiah Matematika has indexed by:

SINTA DOAJ Dimensions Google Scholar Garuda Moraref DOI Crossref

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.