BAB 1
PENDAHULUAN
1.1 Latar Belakang
Transportasi telah menjadi salah satu kebutuhan penting dalam sehari-hari di kehidupan bermasyarakat. Kemajuan teknologi informasi yang ada sekarang dapat dipergunakan sebagai sarana untuk meningkatkan pelayanan umum , diantaranya para pengguna transportasi dapat memperoleh informasi lalu-lintas dengan cara yang mudah. Masalah transportasi tidak akan jauh dari masalah Bahan Bakar Minyak, karena BBM saat ini sangat langkah dan harus lebih dihemat penggunaannya.
Makalah ini membahas masalah penghematan BBM tanpa merasa rugi untuk meninggalkan atau melewatkan tempat yang ingin dilewati agar terjadi optimasi minimum penghematan BBM dengan menggunakan Metode Hongaria dalam mata kuliah Aljabar Linier II.
Pembuatan makalah ini untuk memenuhi tugas Ujian Tengah Semester perkuliahan Aljabar Linier II. Dengan mengaplikasikan Metode Hongaria terhadap masalah permasyarakatan.
1.2 Permasalahan
Bagaimana cara menentukan lintasan terpendek dari tempat wisata satu ke tempat wisata yang lainnya untuk menghemat atau meminimumkan penggunaan Bahan Bakar Minyak(BBM) dengan menggunakan Metode Hongaria.
1.3 Tujuan
· untuk menyelesaikan solusi optimasi jarak guna meminimumkan penggunaan Bahan Bakar Minyak.
· Memahami Metode Hongaria
· sebagai prasyarat untuk memenuhi tugas Aljabar Linier II
1.4 Manfaat
Dapat memehami dan megaplikasikan Metode Hongaria kedalam masalah kehidupan masyarakat. Khususnya dalam penghematan Bahan Bakar Minyak.
BAB 2
TINJAUAN PUSTAKA
Masalah penetapan adalah untuk mencari penetapan optimal dalam sebuah matriks biaya. Misalnya dalam menetapkan n peralatan kepada n tempat konstruksi, maka cij dapat merupakan jarak diantara peralatan ke-i dan tempat konstruksi ke-j. Sebuah penetapan optimal adalah penetapan untuk mana jarak seluruhnya yang ditempuh untuk memindahkan n peralatan tersebut adalah yang minimum (Howard Anton, 1988 : 60).
Richard Bronson (1996 : 1) menyatakan bahwa masalah optimasi merupakan masalah memaksimumkan atau meminimumkan sebuah besaran tertentu yang disebut tujuan objektif (objective) yang bergantung pada sejumlah berhingga variabel masukan (input variables). Variabel-variabel ini dapat tidak saling bergantung, atau saling bergantung melalui satu atau lebih kendala (constrains). Persoalan optimasi merupakan persoalan mencari nilai numerik terbesar (maksimasi) atau nilai numerik terkecil (minimasi) yang mungkin dari sebuah fungsi dari sejumlah variabel tertentu (Akbar Sutawidjaja, 2004:1).
Masalah penetapan (assignment problem) adalah suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas (kegiatan), sehingga dengan demikian biaya yang dikeluarkan untuk pelaksanaan tugas tersebut dapat diminimalkan (N. Soemartojo, 1994 : 309).
Masalah penetapan tugas mensyaratkan bahwa fasilitas sama banyaknya dengan tugas, katakanlahsama dengan n. Dalam hal ini maka ada n! cara yang berlainan untuk menetapkan tugas kepada fasilitas berdasarkan penetapan satu-satu (one-toone basic). Banyaknya penetapan ini adalah n! karena terdapat n cara untuk menetapkan tugas pertama, n-1 cara untuk menetapkan tugas kedua, n-2 cara untuk menetapkan tugas ketiga, dan seterusnya yang jumlah seluruhnya adalah:
n.(n-1).(n-2)…3.2.1 = n!
penetapan yang mungkin. Diantara ke n! penetapan-penetapan yang mungkin ini kita harus mencari satu penetapan yang optimal. Untuk mendefinisikan penetapan yang optimal secara tepat, maka kita akan memperkenalkan kuantitas–kuantitas berikut ini misalkan:
cij = biaya untuk menetapkan tugas ke-j kepada fasilitas ke-i,
untuk i, j = 1, 2, …, n.
Satuan dari cij dapat berbentuk rupiah, dollar, mil, jam, dan lain-lain, satuan apapun yang sesuai dengan masalahnya. Kita mendefinisikan matriks biaya (cost matrix) sebagai matriks n x n:
(Howard Anton, 1988 : 59).
Persyaratan bahwa sebuah tugas yang unik harus ditetapkan kepadasetiap fasilitas berdasarkan satu-satu adalah ekivalen dengan syarat bahwa tidak ada dua cij yang bersangkutan berasal dari baris yang sama atau kolom yang sama.
Definisi 1 :
Jika diketahui sebuah matriks biaya C yang berdimensi n x n maka penetapan (assignment) adalah sebuah himpunan dari entri dimana tidak ada dua diantara entrinya yang berasal dari baris yang sama atau kolom yang sama.
Maka sebuah penetapan optimal akan didefinisikan sebagai berikut :
Definisi 2 :
Jumlah n entri dari sebuah penetapan dinamakan biaya (cost) penetapan tersebut. Penetapan biaya yang paling kecil dinamakan penetapan optimal (optimal assignment) (Howard Anton, 1988 : 60). Masalah penetapan adalah untuk mencari penetapan optimal dalam sebuah matriks biaya. Misalnya dalam menetapkan n peralatan kepada n tempat konstruksi, maka cij dapat merupakan jarak diantara peralatan ke-i dan tempat konstruksi ke-j. Sebuah penetapan optimal adalah penetapan untuk mana jarak seluruhnya yang ditempuh untuk memindahkan n peralatan tersebut adalah yang minimum (Howard Anton, 1988 : 60).
Hardi Suyitno (1997: 218) menyatakan bahwa langkah-langkah dalam menjalankan metode Hongaria adalah sebagai berikut.
1. Menyusun matriks biaya.
2. Mengurangkan elemen-elemen pada setiap baris dengan elemen terkecil pada baris yang sama.
3. Mengurangkan elemen-elemen pada setiap kolom dengan elemen terkecil pada kolom yang sama. Langkah ini akan menghasilkan biaya opportunity keseluruhan Total Opportunity Cost (TOC).
4. Tutup elemen-elemen bernilai nol pada TOC dengan garis-garis mendatar atau tegak. Misalkan n adalah banyaknya baris atau kolom dan banyaknya garis penutup elemen nol sekurang-kurangnya k, maka:
Jika k = n, berarti sudah diperoleh program optimal. Proses dihentikan dan susun penugasan.
Jika k < n, maka proses dilanjutkan dengan mengikuti langkah 5.
5. Cari bilangan terkecil dari bilangan-bilangan yang tak tertutup garis, misalkan e. Selanjutnya:
Semua elemen yang tak tertutup garis dikurangi e.
Semua elemen yang tertutup oleh satu garis tidak diubah.
Semua elemen yang tertutup oleh dua garis ditambah dengan e.
Setelah diperoleh tabel baru kembali ke langkah ke-4 (Hardi Suyitno,1997: 218).
BAB III
METODOLOGI ILMIAH
3.1 Data
Data yang digunakan dalam makalah ini adalah data yang diambil dari skripsi Mahasiswa Fakultas Matematika dan Ilmu pengetahuan Alam, Universitas Jember dengan nama: Amalia Dwi Wardani, NIM: 051810101045 dengan judul skripsi " Pencarian Lintasan terpendek menggunakan Algoritma BELLMAN-FORD" (studi kasus pada kunjungan wisata di Kabupaten dan Kota Probolinggo). Data dalam skripsi tersebut diperoleh dari Dinas Kebudayaan dan Pariwisata Kabupaten Probolinggo. Data tersebut menjelaskan tetntang cara meminimalisir pengeluaran BBM dan menghemat waktu untuk melancong dari tempat satu ke tempat lain.
3.2 Analisis Data
Data yang diperoleh dihitung dengan menggunakan Metode Hongaria dengan Langkah-langkah sebagai berikut:
· Langkah 1 : Kurangkan entri terkecil dalam setiap baris dari semua entri barisnya (setelah langkah ini, setiap baris mempunyai sedikit-dikitnya satu entri nol dan semua entri lainnya tak negatif).
· Langkah 2 : Kurangkan entri terkecil dalam setiap kolom dari semua entri kolomnya(setelah langkah ini, setiap baris dan kolom mempunyai sedikit-dikitnya satu entri nol dan semua entri lainnya adalah tak negatif).
· Langkah 3 : Tarik garis-garis melalui baris dan kolom yang sesuai sehingga semua entri nol dari matrik biaya itu telah terlibat dan jumlah minimum dari garis-garis seperti itu telah digunakan
· Langkah 4 : Uji Optimalitas
(i) jika jumlah minimum dari garis liputan adalah n, maka sebuah penetapan optimal akan mungkin dan perhitungan telah selesai
(ii) jika jumlah minimum dari garis liputan lebih sedikit daripada n, maka sebuah penetapan optimal dari bilangan-bilangan nol belum mungkin. Lanjut ke langkah 5
· Langkah 5 : Tentukan entri terkecil yang tidak terdapat oleh garis manapun. Kurangkan entri ini dari semua entri yang terdapat dan kemudian tambahkan entri itu pada semua entri yang terdapat oleh sebuah garis horisontal dan garis vertikal. Kembali ke langkah 3
BAB IV
HASIL DAN PEMBAHASAN
4.1 Hasil
TEMPAT WISATA 2 | |||||
GL | GB | CK | CJ | ||
TEMPAT WISATA 1 | ATM | 14.8 | 15 | 65.4 | 68.4 |
AK | 46.6 | 46.8 | 41.4 | 44.7 | |
PTT | 48.6 | 47.4 | 39.5 | 42.4 | |
PB | 52.1 | 44.1 | 28.7 | 25 | |
Ket : dalam satuan Kilometer
TEMPAT WISATA 2 | |||||
GL | GB | CK | CJ | ||
TEMPAT WISATA 1 | ATM | 148 | 150 | 654 | 684 |
AK | 466 | 468 | 414 | 447 | |
PTT | 486 | 474 | 395 | 42.7 | |
PB | 52.1 | 441 | 287 | 250 | |
Ket : dalam satuan Hektometer
Keterangan tempat wisata :
NAMA TEMPAT | KETERANGAN |
ATM | AIR TERJUN MADAKARIPURA |
AK | ALUN-ALUN KOTA |
PTT | PELABUHAN TANJUNG TEMBAGA |
PB | PANTAI BENTAR |
GL | GUA LAWA |
GB | GUNUNG BROMO |
CK | CANDI KEDATON |
CJ | CANDI JABUNG |
dari data diatas dibuat ke dalam bentuk matrik (i) sebagai berikut:
matrik (i)
matrik (ii)
matrik (iii)
Langkah 3: Tutupilah entri-entri nol dari matrik (iii) dengan sejumlah minimum garis vertikal dan horisontal. hal ini dapat dilakukan dengan pertama-tama mencoba menutupi bilangan-bilangan nol tersebut dengan garis, kemudian dengan 2 garis dan akhirnya dengan 3 garis.
Langkah 4: karena jumlah minimal dari garis yang digunakan dalam langkah 3 adalah 3, maka penetapan optimal dari bilangan-bilangan nol masih belum mungkin.
Langkah 5: kurangi 52, yakni entri terkecil yang tidak tertutupi dari matrik (iii), dari setiap entrinya yang tidak ditutupi dan tambahkan entri terkecil itu kepada kedua entri yang ditutupi dua kali dengan garis-garis.
matrik (iv)
Langkah 6: (ulangi langkah 3). Tutupilah entri – entri nol dari matrik (iv) dengan sejumlah minimum garis vertikal dan garis horisontal,
Langkah 7: Karena entri-entri nol dari matrik (iv) tidak dapat ditutupi dengan garis-garis yang banyaknya kurang dari empat, maka matrik itu harus mengandung penetapan optimal dari bilangan-bilangan nol
dengan cara coba-coba, didapat dua hasil penetapan optimal dari bilangan – bialngan nol yang berikut dalam matrik:
· penetapan (1) menghasilkan jarak dari tempat wisata 1 (sebagai tempat wisata awal) ke tempat wisata 2 (sebagai tempat wisata tujuan:
Air Terjun Madakaripura è Gua Lawa
Alun-alun Kota è Gunung Bromo
Pelabuhan Tanjung Tembaga è Candi Kedaton
Pantai Bentar è Candi Jabung
dengan jarak minimum yang ditempuh untuk menghemat BBM adalah
148+468+394+250 = 1260 Hm
= 126 Km
· penetapan (2) menghasilkan jarak dari tempat wisata 1 (sebagai tempat wisata awal) ke tempat wisata 2 (sebagai tempat wisata tujuan:
Air Terjun Madakaripura è Gunung Bromo
Alun-alun Kota è Gua Lawa
Pelabuhan Tanjung Tembaga è Candi Kedaton
Pantai Bentar è Candi Jabung
dengan jarak minimum yang ditempuh untuk menghemat BBM adalah
150+466+394+250 = 1260 Hm
= 126 Km
