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 teladan soal dan pembahasan ihwal metode Hungarian (Hungarian Method) ini. Silakan baca langkah penyelesaian di : Permodelan Matematika Masalah Penugasan dan Metode Hungarian.

Problem:

Sebuah perusahaan konstruksi mempunyai 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 semoga jarak yang ditempuh minimal?

Solusi:

Langkah 1

Kurangkan masing masing baris dengan entri terkecil pada baris tersebut. Sehingga sanggup ditulis,

Langkah 2

Kurangkan masing masing entri kolom dengan entri terkecil pada kolom tersebut, sehingga sanggup 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 aku beri garis. Ini alasannya ialah nol pada kolom tersebut telah dipakai/tergaris ketika 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 ialah 5. Makara 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 ialah 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.