Beriklan di Blog Ini? .
MURAH DAN MUDAH.
Info Lebih Lanjut [ KONTAK KAMI]

Contoh Soal dan Penyelesaian Metode Hungarian

Pada terbitan sebelumnya telah ditulis mengenai langkah penyelesaian metode Hungarian dan teorema dasar dalam penyelesaian metode Hungarian. Demi menambah pemahaman kita bersama, berikut akan diberikan contoh soal dan pembahasan tentang metode Hungarian (Hungarian Method) ini. Silakan baca langkah penyelesaian di : Permodelan Matematika Masalah Penugasan dan Metode Hungarian.

Problem:

Sebuah perusahaan konstruksi memiliki 4 Bulldozer yang terletak di 4 lokasi berbeda. Bulldozer tersebut akan digunakan ke 4 lokasi pembangunan. Jarak antara lokasi bulldozer dengan lokasi pembangunan sebagai berikut,
Buldozer - Lokasi
A
B
C
D
I
90
75
75
80
II
35
85
55
65
III
125
95
90
105
IV
45
110
95
115

Bagaimana cara pembagian Bulldozer tersebut ke masing masing lokasi pembangunan agar jarak yang ditempuh minimal?

Solusi:

Langkah 1
Kurangkan masing masing baris dengan entri terkecil pada baris tersebut. Sehingga bisa ditulis,
Langkah 2
Kurangkan masing masing entri kolom dengan entri terkecil pada kolom tersebut, sehingga bisa ditulis.

Langkah 3
Buat garis yang menutupi entri 0 pada matriks terakhir yang anda peroleh sehingga menjadi,
Akan jadi pertanyaan bagi anda kenapa kolom 2 dan kolom 4 tidak saya beri garis. Ini karena nol pada kolom tersebut telah dipakai/tergaris saat menggaris baris pertama.

Langkah 4
Karena banyaknya garis 3, sementara n=4, maka lanjutkan dengan langkah ke-5.

Langkah 5.
Kurangkan dengan entri terkecil yang tak tergaris masing masing baris. Perhatikan, entri terkecil adalah 5. Jadi baris 2,3,4 masing masing entri dikurangi dengan 5. 
Lalu kolom yang tergaris ditambahkan ditambahkan dengan 5 dan hasilnya,
Selanjutnya kembali ke langkah 3.

Langkah 3.1
Langkah 4.1
Karena banyak garis masih saja 3 dan kurang dari n=4. Maka lanjutkan ke langkah 5.

Langkah 5.1
Entri terkecil yang tidak dikenai garis adalah 20. Baris 2 dan 4 kita kurangkan semua entrinya dengan 20.
Lanjutkan dengan menambahkan 20 pada kolom yang digarisi (kolom 1).
Kembali ke langkah 3

Langkah 3.2
Baris dan kolom dengan entri 0 di garis
Langkah 4.2
Alhasil telah didapat 4 garis untuk problem n=4. Artinya kita telah menemukan penyelesaian. Kembli ke teorema dasar metode Hungarian, dimana nilai minimum pada matriks 'di-operasikan' posisinya sama dengan posisi nilai minimum pada matriks semula.
Posisi ini dibandingkan dengan matriks semula akan ditemukan,
Jadi penempatan bulldozer tersebut agar jarak tempuh minimal adalah:
Buldozer - Lokasi
A
B
C
D
I
90
75
75
80
II
35
85
55
65
III
125
95
90
105
IV
45
110
95
115




Jadilah Komentator Pertama untuk "Contoh Soal dan Penyelesaian Metode Hungarian"

Post a Comment