BAB I PENDAHULUAN
1.1. Latar Belakang Masalah Masalah keputusan ekonomi mengenai pemilihan dan/atau penempatan fasilitas yang tepat untuk memenuhi permintaan secara efisien, banyak sekali terjadi dalam kehidupan perekonomian. Kapasitas fasilitas, pengalokasian depot, gudang, pemadam kebakaran, rumah sakit, perpustakaan, dan stasiun pelayanan wireless (seperti layanan telepon seluler), merupakan sebagian contoh permasalahan terkait keputusan ekonomi. Permasalahan-permasalahan tersebut memiliki kesamaan yaitu terdapat himpunan fasilitas dengan posisi tertentu dan akan dipilih posisi terbaik dengan tujuan untuk memenuhi permintaan (pelanggan) atau untuk menambah tingkat permintaan. Salah satu aspek yang diperhatikan dalam masalah lokasi fasilitas adalah kapasitas fasilitas. Masalah lokasi fasilitas yang berasumsi bahwa fasilitas dapat memenuhi tak terbatas permintaan dinamakan dengan masalah lokasi fasilitas tak terbatas. Masalah lokasi fasilitas tak terbatas bertujuan untuk meminimumkan total biaya, yang meliputi biaya tetap untuk pembukaan suatu fasilitas dan biaya servis. Biaya servis tersebut merupakan jumlahan biaya transportasi dan total biaya permintaan dari pelanggan. Peminimuman total biaya dapat diwujudkan dengan menentukan penempatan fasilitas yang tepat dari himpunan terbatas lokasi potensial fasilitas dan menghubungkan setiap pelanggan ke satu dari lokasi-lokasi yang telah dipilih untuk dibuka fasilitas sedemikian sehingga dapat memenuhi seluruh permintaan pelanggan. Tujuan lain yang ingin dicapai adalah menentukan besar biaya yang harus dikeluarkan oleh setiap pelanggan agar dapat terhubung oleh suatu fasilitas. Tujuan tersebut tidak dapat dicapai hanya dengan menyelesaikan program linear primal, karena program linear primal hanya dapat
1
2
memberikan informasi mengenai total biaya yang dikeluarkan dari semua pelanggan yang terhubung pada suatu fasilitas bukan biaya yang harus dikeluarkan oleh setiap pelanggan untuk dapat terhubung pada suatu fasilitas. Dengan demikian, diperlukan program linear dual untuk memberikan informasi apakah diperlukan biaya lain selain biaya servis yang harus dikeluarkan oleh pelanggan, dan total biaya yang diperlukan setiap pelanggan untuk dapat terhubung pada suatu fasilitas. Hal-hal tersebut di atas yang kemudian mendasari penulisan skripsi ini. Pada skripsi ini diperkenalkan metode yang didasari oleh program linear dual untuk menyelesaikan masalah lokasi fasilitas tak terbatas. Lebih lanjut, metode tersebut memberikan solusi optimal dual yang sering kali berhubungan langsung dengan solusi optimal program linear bilangan bulat (primal) dalam menentukan fasilitas yang harus dibuka sedemikian sehingga memenuhi semua permintaan dengan total biaya yang minimum.. 1.2. Perumusan Masalah Pada skripsi ini, akan dibahas fasilitas tak terbatas
fasilitas dan
mengenai penyelesaian masalah lokasi pelanggan dengan menggunakan metode
yang didasari oleh program linear dual. Rumusan masalah yang terdapat dalam skripsi ini adalah : 1. Model matematika masalah lokasi fasilitas tak terbatas beserta dualnya. 2. Cara mendapatkan formulasi metode yang didasari oleh program linear dual yang meliputi algoritma dual ascent, algoritma primal dan algoritma dual adjustment untuk menyelesaikan masalah lokasi fasilitas tak terbatas. 3. Penyelesaian ilustrasi masalah masalah lokasi fasilitas tak terbatas dengan metode yang didasari oleh program linear dual.
1.3. Batasan Masalah Pada penulisan skripsi ini, dibatasi masalah pada pembahasan yaitu mengenai metode penyelesaian yang didasari oleh program linear dual untuk masalah lokasi fasilitas tak terbatas. Masalah lokasi fasilitas tak terbatas pada
3
pembahasan skripsi ini adalah masalah lokasi fasilitas yang solusi optimalnya dapat ditemukan dengan cara pengaturan solusi dual (algoritma dual adjustment), apabila solusi optimal tidak dapat ditemukan dengan algoritma dual ascent dan dengan algoritma primal. Selain itu, ilustrasi masalah lokasi fasilitas dibatasi pada skala kecil yang kemudian akan diselesaikan dengan metode yang didasari oleh program linear dual.
1.4. Maksud dan Tujuan Secara
umum
penelitian
ini
bertujuan
untuk
mempelajari
cara
menyelesaikan masalah lokasi fasilitas tak terbatas dengan menggunakan metode yang didasari oleh program linear dual. Adapun tujuan khusus penelitian ini adalah : 1.
Membahas masalah lokasi fasilitas tak terbatas sebagai bentuk khusus dari masalah lokasi fasilitas.
2.
Membahas model matematika masalah lokasi fasilitas tak terbatas beserta bentuk dualnya.
3.
Membahas metode penyelesaikan masalah lokasi fasilitas tak terbatas, yaitu metode yang didasari oleh dual.
4.
Memberikan ilustrasi masalah lokasi fasilitas tak terbatas dalam kehidupan nyata.
1.5. Tinjauan Pustaka Permasalahan pada skripsi ini mengangkat tentang masalah lokasi fasilitas tak terbatas. Dalam membuat rumusan model matematika masalah lokasi fasilitas tak terbatas, dibutuhkan informasi terkait masalah lokasi tersebut untuk mengidentifikasi masalah yang terjadi. Berbagai penelitian telah diusulkan untuk masalah ini. Weber (1909) mengatakan bahwa pemilihan lokasi industri didasarkan atas prinsip minimasi biaya. Penelitian berkaitan dengan model matematika dilakukan oleh Stollsteimer (1963), Kuehn & Hamburger (1963) dan Balinski (1965) mengenai Simple Plant Location Problem. Simple plant location problem dikenal sebagai masalah lokasi fasilitas tak terbatas yang menjadi salah
4
satu model dasar dan paling banyak dipelajari. Penelitian yang berhubungan dengan sifat dan solusi model matematika maslaah lokasi fasilitas terus dilakukan. Penelitian terbaru mengenai masalah lokasi fasilitas dilakukan oleh Li et al. (2013) dengan judul Heuristic Algorithms for General k-level Facility Location Problems, Patel (2013) Approximation Algorithms for Facility Location Problems dengan judul Contreras et al. (2011) dengan judul Benders Decomposition for Large-Scale Uncapacitated Hub Location dan Aktas et al. (2011) dengan judul Optimizing Fire Station for the Istanbul Metropolitan Municipality. Penulisan skripsi ini mengacu pada beberapa jurnal dan juga buku. Jurnal utama dalam skripsi ini adalah jurnal dengan karangan Erlenkotter (1978) yang berjudul A Dual-Based Procedure for Uncapacitated Facility Location. Pada jurnal tersebut dijelaskan tentang algoritma-algoritma yang berdasarkan pada program linear dual untuk menyelesaikan masalah lokasi fasilitas tak terbatas. Beberapa jurnal pendukung di gunakan untuk memahami formulasi algoritmaalgoritma dan aplikasinya seperti, Efficient Primal-Dual Heuristic for A Dynamic Location Problem karangan Dias et al. (2005), A Dual-Based Procedure for Dynamic Facility Location karangan Roy et al. (1982), dan Uncapacitated Facility Location Problem with Self-Serving Demands karangan Monabbati (2013). Kemudian, untuk memahami model matematika masalah lokasi fasilitas tak terbatas diambil dari beberapa jurnal seperti, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems karangan Jain dan Vazirani (1999), dan Approximation Algorithms for Facility Location Problems karangan Shmoys (1997). Untuk lebih jelasnya, masalah lokasi fasilitas tak terbatas ini melibatkan duality gap. Konsep dasar mengenai duality gap diambil dari beberapa jurnal seperti A Note on Duality Gap in Simple Plant Location Problem karangan Mladenovic et al. (2006), Primal-Dual Variable Neighborhood Search for the Simple PlantLocation Problem karangan Hansen et al. (2007). Pada dasar teori skripsi ini, konsep-konsep dasar dari lokasi fasilitas penulis dapatkan melalui beberapa jurnal diantaranya jurnal karangan Daskin (2008) dan Weber (1929). Untuk dasar-dasar masalah program linear bilangan
5
bulat, program linear relaksasi, dualitas beserta sifat-sifatnya, dan set covering, penulis menggunakan buku karangan Winston (1993) dan Taha (2008). Selain itu, penulis juga mempelajari aplikasi masalah lokasi fasilitas tak terbatas dari beberapa jurnal.
1.6. Metodologi Penelitian Penulisan skripsi ini diawali dengan memahami jurnal-jurnal dan bukubuku terkait relaksasi program linear, dualitas, sifat-sifat yang berhubungan dengan kondisi complementary slackness, set covering, dan model matematika masalah lokasi fasilitas pada kasus permintaan terbatas dan kasus permintaan tak terbatas secara umum. Setelah penulis memahami tentang hal-hal tersebut, langkah selanjutnya adalah mempelajari tentang bentuk dual model matematika masalah fasilitas tak terbatas dan duality gap. Selanjutnya, penulis melakukan langkah-langkah, seperti memahami cara menyelesaikan program linear dual masalah lokasi fasilitas, menentukan lokasi fasilitas yang akan dibuka, dan lokasi-lokasi pelanggan yang akan dihubungkan ke suatu fasilitas sehingga sering kali secara langsung dapat diperoleh solusi program linear primalnya, kemudian memahami bagaimana agar mencapai solusi optimal jika terjadi pelanggaran kondisi complementary slackness.
1.7. Sistematika Penulisan Pada penulisan skripsi ini, penulis menggunakan sistematika sebagai berikut : BAB I
PENDAHULUAN
Bab satu membahas tentang latar belakang permasalahan, perumusan dan batasan masalah, tujuan penulisan, tinjauan pustaka, metodologi penelitian dan sistematika penulisan. BAB II
DASAR TEORI
Bab dua membahas tentang teori-teori penunjang yang digunakan untuk menyelesaikan masalah pada bab-bab selanjutnya. Teori-teori yang dibahas pada Bab dua adalah program linear, program linear bilangan bulat, program linear
6
relaksasi, dualitas program linear, dualitas program linear tak normal, dan masalah lokasi fasilitas secara umum. BAB III
MASALAH LOKASI FASILITAS TAK TERBATAS
Bab tiga berisi pembahasan model matematika masalah lokasi fasilitas tak terbatas, duality gap, dan algoritma-algoritma yang didasari oleh program linear dual
untuk menyelesaian masalah lokasi fasilitas tak terbatas. Pada bab ini,
dijelaskan tentang cara mendapatkan algoritma-algoritma untuk menyelesaikan masalah lokasi fasilitas tak terbatas. BAB IV
APLIKASI
Bab empat berisi pembahasan ilustrasi masalah lokasi fasilitas tak terbatas pada masalah lokasi gudang, serta penyelesaiannya dengan menggunakan algorimaalgoritma yang telah dijelaskan pada Bab tiga BAB V
PENUTUP
Bab lima berisi kesimpulan yang merupakan ringkasan pembahasan materi.
