Permasalahan optimasi (optimization problems) yaitu permasalahan yang menuntut pencarian solusi optimum. Solusi optimum (terbaik) adalah solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin terjadi. Dalam jaringan distribusi listrik, masalah tuntutan pencapaian kondisi optimum kinerja operasi sistem adalah sangat penting. Salah satu faktor yang perlu dipertimbangkan dalam desain jaringan distribusi listrik primer adalah biaya. Biaya berkaitan erat dengan panjang kabel yang digunakan. Hal ini menyebabkan pentingnya menghitung panjang minimum kabel yang dibutuhkan dari suatu jaringan. Selain panjang kabel yang dipergunakan seminimal mungkin, juga perlu dipertimbangkan pengaturan penataan kabel tersebut. Dalam kenyataannya, dalam mengatur pemasangan kabel, seringkali lebih memilih jalur yang lebih panjang. Salah satu cara pencapaian kondisi optimasi adalah dengan menggunakan algoritma untuk menentukan pohon merentang minimum (minimum spanning tree) dari sistem jaringan distribusi listrik primer. Dalam penelitian ini algoritma yang digunakan adalah algoritma Prim. Algoritma Prim adalah sebuah algoritma dalam teori graf untuk mencari pohon merentang minimum untuk sebuah graf terhubung berbobot, dengan kata lain sebuah himpunan bagian dari cabang-cabang yang membentuk suatu pohon yang terdiri dari semua titik/simpul, di mana bobot keseluruhan semua cabang dalam pohon adalah paling kecil. Penelitian ini dilakukan dengan cara merancang model graf jaringan distribusi listrik primer sesuai dengan data yang diperoleh, kemudian dari graf tersebut diberi bobot masing-masing berupa jarak atau panjang kabel jaringan dengan menggunakan program ArcView GIS 3.3 dan program Delphi 7. Selanjutnya dihitung dan disimulasikan oleh komputer untuk mendapatkan pohon merentang minimum jaringan distribusi listrik primer dengan menggunakan algoritma Prim. Langkah selanjutnya dengan mengkaji kompleksitas waktu implementasi algoritma Prim pada jaringan distribusi listrik primer sehubungan dengan efisiensi algoritma tersebut. Algoritma Prim termasuk dalam kategori algoritma yang baik atau efisien, karena kompleksitas waktunya berbentuk polinomial dalam n, dengan n adalah ukuran jumlah simpul atau sisi. Berdasarkan hasil pengujian terlihat bahwa waktu komputasi yang dihasilkan untuk mencari pohon merentang minimum jaringan distribusi listrik primer bersifat kuadratik, sehingga terbukti bahwa algoritma Prim memiliki kompleksitas waktu O(n2).

Optimization problem is the demanding problem for optimum solutions. The optimum (best) solution is a solution with minimum values, or maximum among a set of possible alternative solutions. In electrical distribution network, problem of demanding achievement of optimum condition of system operational performance is essential. One of the factors necessary to consider in the designing of the primary electrical distribution network is cost. Cost is closely related to length of cable used. It highlights the importance of calculating the minimum length of cable required in a network. The cable should be not only with as minimal as possible in length, but also regulated for better arrangement. Actually, in regulating the cable installation, longer path is more frequently selected. One of the ways of achieving optimization condition is to use algorithm to determine a minimum spanning tree of the primary electrical distribution network system. In this study, the algorithm used is Prim’s algorithm—an algorithm in graph theory to seek a minimum spanning tree for a weighted connected graph. In other word, it is a set of parts from branches of a tree consisting of all vertices, where the entire weight of all the branches of tree is the lowest. The study was conducted by designing a graph model of primary electrical distribution network in appropriate with the data obtained. Based on the graph, each was weighted for distance or length of network cable by using the ArcView GIS 3.3 and Delphi 7. The data were then calculated and simulated by using computer to gain a minimum spanning tree of the primary electrical distribution network using the Prim’s algorithm. Finally, time complexity in implementation of Prim’s algorithm in the primary electrical distribution network was studied in relation to efficiency of the algorithm. Prim’s algorithm is a good or efficient category of algorithm because the shape of polynomial time complexity in n, where n is the number of vertex or edge. Based on result of the test, it can be concluded that the resulting computation time of seeking a minimum spanning tree of primary electrical distribution network is a quadratic. Thus, it is evidenced that Prim’s algorithm had a time complexity of O(n2).

Kata Kunci : Pohon merentang minimum,Algoritma prim,Kompleksitas waktu