PENENTUAN RUTE BUS KARYAWAN MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER
ZIL’ARIFAH
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
PENENTUAN RUTE BUS KARYAWAN MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER
ZIL’ARIFAH G54050899
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
ABSTRAK ZIL’ARIFAH. Penentuan Rute Bus Karyawan Menggunakan Pemrograman Linear Integer. Dibimbing oleh PRAPTO TRI SUPRIYO dan FARIDA HANUM. Tulisan ini memberikan formulasi masalah penentuan rute bus karyawan menggunakan pemrograman linear integer. Rute setiap bus berawal dan berakhir di suatu tempat (depot) untuk menjemput karyawan melalui beberapa pos. Setiap pos dikunjungi tepat sekali oleh suatu bus dengan memperhatikan kapasitas setiap bus dan jarak tempuh maksimum setiap bus sehingga dapat dipastikan bahwa bus sampai depot (tempat kerja) sebelum jam kerja dimulai. Fungsi objektif masalah ini adalah meminimumkan biaya operasional seluruh bus yang dioperasikan. Biaya operasional setiap bus diasumsikan sepadan dengan biaya perawatan tetap dan biaya penggunaan yang sesuai dengan jarak perjalanan bus tersebut. Pada contoh studi kasus dengan menggunakan data hipotetik dalam karya ilmiah ini, biaya yang paling minimum diperoleh jika digunakan 4 unit bus. Total jarak yang ditempuh oleh keempat unit bus dalam menjemput atau mengantar karyawan adalah 247 km. Total biaya yang harus dikeluarkan untuk biaya operasional bus karyawan per harinya adalah 894000 rupiah.
ABSTRACT ZIL'ARIFAH. Employee Bus Route Determination Using Integer Linear Programming. Supervised by PRAPTO TRI SUPRIYO and FARIDA HANUM. This paper gives formulation of the problem in determining an employee bus route using integer linear programming. Each bus route begins and ends in one place (depot) to pick some postal employees. Each post will be visited once by a bus according to the capacity and maximum mileage of each bus, so it can be ascertained that the bus arrives before work begins. Objective function of this problem is to minimize operating costs of all of the buses. The result of case study using hypothetical data shows that the minimum cost is obtained when four buses are used. The total distance traveled by the four buses is 247 km with total daily operating costs 894,000 rupiahs.
PENENTUAN RUTE BUS KARYAWAN MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER
ZIL’ARIFAH G54050899
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012
Judul
: Penentuan Rute Bus Karyawan Menggunakan Pemrograman Linear Integer Nama : Zil’Arifah NIM : G54050899
Menyetujui, Pembimbing I
Pembimbing II
Drs. Prapto Tri Supriyo, M.Kom. NIP. 19630715 199002 1 002
Dra. Farida Hanum, M.Si. NIP. 19651019 199103 2 002
Mengetahui: Ketua Departemen
Dr. Berlian Setiawaty, M.S. NIP. 19650505 198903 2 004
Tanggal Lulus :
KATA PENGANTAR Puji syukur penulis panjatkan ke hadirat Allah SWT atas segala nikmat, karunia, izin, dan pertolongan-Nya, sehingga penulis dapat menyelesaikan karya ilmiah yang berjudul “Penentuan Rute Bus Karyawan Menggunakan Pemrograman Linear Integer”. Karya ilmiah ini merupakan syarat untuk menyelesaikan studi pada Departemen Matematika, Fakultas Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Terima kasih penulis ucapkan kepada: 1. Sang pencipta, Tuhan semesta alam Allah SWT, atas maha karya-Nya, 2. Nabi besar Muhammad SAW sebagai penutup para nabi, 3. Bapak dan Ibu tercinta; Drs. Ermasdi dan Brata Graha, atas segala dukungan, motivasi, pembelajaran, masukan, dan segala kasih sayang yang diberikan kepada penulis, juga adikadikku tersayang, Rozaanah, Fauzan Aziman, dan Hanifatul Khairiyah, atas segala kasih sayangnya dan keceriaannya, 4. Bapak Drs. Prapto Tri Supriyo, M. Kom dan Ibu Dra. Farida Hanum, M.Si, selaku dosen pembimbing, atas segala kesabaran dan masukan serta doanya selama membimbing penulis, tak lupa kepada Bapak Drs. Siswandi, M. Si selaku penguji yang telah memberikan ilmu, saran, dan doanya, 5. semua dosen Departemen Matematika, terima kasih atas semua ilmu yang telah diberikan, 6. staf Departemen Matematika: Bapak Yono, Bapak Hery, Bapak Deni, Ibu Ade, Bapak Epul, Bapak Bono dan Ibu Susi atas semangat dan doanya, 7. keluarga besar Ibu Sulastri, Mama El, Mama Af, Etek Am, Om Eri, Etek Pit, Etek Ira, Etek Eda, Etek Nel, Etek Adek, Pa Etek Razak, Pa Etek Am, dan Pa Etek Fadly, 8. keluarga besar Bapak M. Yusuf, terutama Ibu Maemunah, Mamang Sabeni, Bibi Lilis, Uwa Isah, Siska, Syukri, dan Fajar, 9. keluarga besar Bapak Mardani, terutama Ibu Hj. Masna Ulyanah Mardani, Aa Dicky, Mas Risyad, Aa Fikri, Kang Ade, Wildan, dan Algifari, 10. Chandra yang selalu mendampingi serta memberikan semangat, dukungan, dan doanya, 11. Afat yang selalu memberikan semangat, dan doanya, 12. sahabat-sahabatku tersayang yang selalu memberi semangat; Kiky, Warno, Mega, Dhani, dan Aa Dede, atas segala tawa dan tangis, manis dan pahit, suka dan duka selama persahabatan kita, 13. teman-teman mahasiswa angkatan 42: Riyu, Ricken, Agnes, Hikmah, Dian, Titi, Mira, Octa, Rita, Vita, Vera, Gita, Luri, Rima, Hesti, Ayu, Nyoman, Lisda, Ida, Achi, Dewi, Septiwi, Erlin, Eyyi, Hapsari, Jane, Lela, Lina, Mega, Niken, Nola, Nofi, Oby, Ocoy, Pipit, Siti, Tia, Vino, Yuni, Ety, Yudi, Danu, Sapto, Dendi, Ardy, Septian, Awi, Eko, Rendy, Boy, Jawa, Arif, Makinun, Ridwan, Yusep, Bima, Ilyas, Iput, Fachri, Warno, Heri, Acuy, dan Bayu, atas segenap dukungan, suka duka dan keceriaan selama penulis menempuh studi di Departemen Matematika IPB, 14. kakak-kakak mahasiswa matematika angkatan 40, terutama kak Rusli, atas segala bantuannya dalam mengajarkan Lingo; kakak-kakak mahasiswa angkatan 41, terutama kak Aji, atas bantuannya; adik-adik mahasiswa angkatan 43, terutama Slamet atas bantuannya dan Faizal yang telah bersedia menjadi pembahas, dan adik-adik mahasiswa angkatan 44, 15. keluarga besar BEM FMIPA IPB angkatan 2006-2007 dan angkatan 2007-2008, atas segenap dukungan, doa, dorongan semangat, dan warna warni dalam kebersamaan kita, 16. keluarga besar pengurus Gumatika IPB, atas dukungan dan doanya, 17. pembimbing dan asisten pengajar Kumon Taman Yasmin; bu Yani, pak Bambang, mbak Berti, mbak Eka, mbak Era, mbak Sri, mbak Iis, mbak Nining, mbak Mira, mbak Tina, mbak Titi, mbak Oy, Susi, Roby, Mia, Dwi, Wiwi, Eyyi, dan Riska, 18. teman-teman penghuni Maharlika Depan; Vina, Ayu, Veza, Yuyun, Icha, Ninu’, Almira dan Isna, 19. semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan, oleh karena itu penulis mengharapkan kritik dan saran yang membangun dari pembaca. Semoga tulisan ini dapat bermanfaat. Bogor, Februari 2012 Zil’Arifah
RIWAYAT HIDUP Penulis dilahirkan di Batusangkar pada 23 September 1986 dari pasangan Drs. Ermasdi dan Brata Graha. Penulis merupakan anak pertama dari empat bersaudara. Pada tahun 1999 penulis lulus dari SD Negeri 22 Batusangkar kemudian tahun 2002 lulus dari SLTP Negeri 1 Batusangkar. Tahun 2005 penulis lulus dari SMA Negeri 1 Padang Panjang dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur USMI (Undangan Seleksi Masuk IPB). Pada tahun 2006, penulis memilih Mayor Matematika dan Minor Statistika Industri, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis aktif dalam kegiatan kemahasiswaan, di antaranya pada tahun 2006-2007 menjabat sebagai staf Departemen Pengembangan Sumber Daya Mahasiswa dan pada tahun 2007-2008 sebagai staf Departemen Sosial Badan Eksekutif Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam (BEM FMIPA) IPB. Selain itu, penulis juga terlibat dalam Organisasi Mahasiswa Daerah Ikatan Pelajar Mahasiswa Minang (IPMM) sebagai staf Dewan Penasehat IPMM tahun 2006-2007 dan tahun 2007-2008. Penulis juga terlibat dalam organisasi Ikatan Mahasiswa Serambi Makkah dan Pagaruyung (IMASEREMPAG) sebagai sekretaris pada tahun 2007-2008 dan tahun 2008/2009, serta mengikuti kepanitiaan dari beberapa kegiatan selama rentang waktu 2006-2008. Pada tahun 2008 penulis pernah mengajar di SMK IZZATA Depok dan pada tahun 2009 penulis pernah mengajar di SMK Wira Buana Citayam dan asisten PT KIE Indonesia (Kumon).
DAFTAR ISI
Halaman DAFTAR TABEL
viii
DAFTAR GAMBAR
viii
DAFTAR LAMPIRAN
viii
I
PENDAHULUAN 1.1 Latar Belakang 1.2 Tujuan
1 1
II LANDASAN TEORI 2.1 Fungsi Linear dan Pertidaksamaan Linear 2.2 Pemrograman Linear 2.3 Pemrograman Integer (Integer Programming) 2.4 Relaksasi Pemrograman Linear 2.5 Graf 2.6 Masalah Path Terpendek 2.7 Traveling Salesman Problem (TSP) 2.8 Metode Branch-and-Bound
1 1 3 3 3 4 5 6
III DESKRIPSI DAN FORMULASI MASALAH 3.1 Deskripsi Masalah Rute Bus Karyawan 3.2 Model Masalah Rute Bus Karyawan
9 9
IV STUDI KASUS
12
V SIMPULAN DAN SARAN 5.1 Simpulan 5.2 Saran
15 15
DAFTAR PUSTAKA
15
LAMPIRAN
16
vii
