PENGGUNAAN METODE CUTTING PLANE UNTUK MENYELESAIKAN MINIMUM SPANNING TREE DENGAN KENDALA BOBOT PADA GRAF K_n

Dewi Suhika(1*), Wamiliana Wamiliana(2),

(1) Institut Teknologi Sumatera
(2) Universitas Lampung
(*) Corresponding Author


Abstract


This study aims to determine the minimum spanning tree of a complete graph K_n with weight constraints and completion using the cutting plane method. The cutting plane method is one of the algorithms included in the exact method. This algorithm works by reducing the solution area so that it becomes narrower. As a result, the feasible solutions that will be investigated become less and less. This is because the cutting plane method works based on the optimal linear programming solution of relaxation solved by the simplex method. In this paper we give illustration of the algorithm applied for two cases, one for K_4 and one for K_5.

Keywords


complete graph; cutting plane method; minimum spanning tree; tree

References


Bronson, R. 1996. Teori dan Soal-Soal Operation Research. Jakarta: Erlangga.

Deo, N. 1989. Graph Theory with Aplications to Engineering and Computer Science. Prentice Hall, Inc. Englewood Cliffs, New Jersey. Hal. 461.

Henn, T. S. 2007. Weight-Constrained Minimum Spanning Tree Problem. Diploma Thesis: University of Kaiserslautern Departement of Mathematics. Hal 7-25.

Munir, R. 2012. Matematika Diskrit. Bandung: Informatika.

Nurbaiti, Wahyuni. 2015. Aplikasi Minimum Spanning Tree Pada Jaringan Listrik Di Perumahan Mutiara Indah Village. Jurnal MSA. Vol. 3 No. 1, Hal 47-56.

Siang, J.J. 2009. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta: ANDI

Subagyo, P., Asri, M., Handoko, T.H. 2009. Dasar-Dasar Operations Research. Yogyakarta: BPEE.

Wamiliana. 2015. Program Linear Teori dan Terapannya. CV Anugrah Utama Raharja (AURA), Bandar Lampung.




DOI: http://dx.doi.org/10.24127/ajpm.v7i1.1353

Refbacks

  • There are currently no refbacks.