PENGGUNAAN PROGRAM LINEAR DUAL UNTUK MENYELESAIKAN MASALAH LOKASI FASILITAS TAK TERBATAS

TYAS AGUSTINA, Dr. Irwan Endrayanto, S.Si, M.Sc.

2014 | Skripsi | MATEMATIKA

Pada tugas akhir ini akan dibahas mengenai penyelesaian masalah lokasi fasilitas tak terbatas. Masalah tersebut terdiri dari penempatan lokasi fasilitas dan pengalokasikan himpunan pelanggan ke lokasi tersebut sedemikian sehingga meminimumkan total biaya serta penentuan besar biaya yang harus dikeluarkan oleh setiap pelanggan agar dapat terhubung oleh suatu fasilitas. Oleh sebab itu, metode yang didasari oleh program linear dual digunakan untuk menyelesaikan masalah lokasi fasilitas tak terbatas. Metode tersebut terdiri dari tiga algoritma yang digunakan berturut-turut untuk mendapatkan solusi optimal. Pertama, algoritma dual ascent untuk mencari penyelesaian program linear dual. Kedua, algoritma primal untuk menentukan lokasi fasilitas yang akan dibuka dan mengalokasikan himpunan pelanggan ke lokasi fasilitas tersebut. Ketiga, algoritma dual adjustment untuk memperbaiki solusi dual apabila algoritma dual ascent dan algoritma primal belum dapat mencapai solusi optimal. Sebagai ilustrasi, pada bagian terakhir skripsi ini disajikan penerapan tiga algoritma tersebut dalam menyelesaikan contoh numerik masalah lokasi fasilitas tak terbatas.

In this thesis, we present a solution of an uncapacitated facility location problem. The problem consists of choosing some facilities and allocating a set of customers to these facility locations such that minimizing the total cost and computing the total price paid by each customer. Accordingly, the problem is solved by using a method based on dual linear programming. The method consists of three algorithms that is done and consecutively. First, the dual ascent algorithm is used to compute a solution of dual linear programming. Second, the primal algorithm is used to determine some of facility locations that will be opened and to allocate a set of customers to these facility locations. Third, the dual adjustment algorithm is used to adjust the dual solution in case the dual ascent algorithm and the primal algorithm cannot find an optimal solution. As an illustration, at the end of this thesis we present an implementation of the three algorithms.

Kata Kunci : -