Contoh Soal dan Penyelesaian Metode Hungarian

martha yunanda contoh soal

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.