Masalah Maksimasi Metode Hungarian

Langkah-langkah penyelesaian dengan metode Hungarian untuk masalah maksimasi adalah sebagai berikut :

1. Ditentukan nilai terbesar dari setiap baris, lalu mengurangkan semua nilai pada setiap baris dari nilai terbesarnya.
2.  Diperiksa apakah setiap kolom telah mempunyai nilai nol. Bila sudah dilanjutkan ke langkah 3,bila belum,dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kolom tersebut dikurangkan dengan nilai terkecilnya.
3. Ditentukan apakah terdapat n elemen nol dimana tidak ada nilai nol yang berada pada baris/kolom yang sama, dimana n adalah jumlah kolom/baris. Jika ada, maka tabel telah optimal, jika tidak, dilanjutkan ke langkah 4.
4.  Dilakukan penutupan semua nilai no dengan menggunakan garis vertical/horizontal seminimal mungkin.
5. Ditentukan nilai terkecil dari nilai-nilai yang tidak tertutup garis. Lalu semua nilai yang tidak tertutup garis dikurangkan dengan nilai terkecil tersebut.
6. Kembali ke langkah 3

Contoh :

Seorang manager pemasaran ingin menempatkan empat orang salesmannya di empat daerah pemasaran produknya. Penempatan salesman tersebut didasarkan pada perolehan nilai keuntungan yang diperkirakan akan diperoleh oleh setiap salesman di setiap daerah pemasaran berdasarkan prestasi kerja mereka saat ini dan pengenalan terhadap masing-masing daerah pemasaran tersebut. Bila data perolehan keuntungan dari setiap salesman di setiap daerah pemasaran seperti yang tersaji pada Tabel 1, tentukan penugasan salesman yang harus dibuat oleh sang manager agar keuntungan yang diperoleh maksimal.

    Tabel 1 : Data

Lokasi/ Salesman	Lokasi 1	Lokasi 2	Lokasi 3	Lokasi 4
Sal. 1	1000	900	1100	900
Sal. 2	1100	1000	950	950
Sal. 3	1050	950	900	1050
Sal. 4	1150	1000	950	1000

Penyelesaian :

Tujuan yang ingin dicapai dalam penugasan salesman di atas adalah diperolehnya keuntungan yang maksimal, sehingga masalah ini tergolong dalam masalah maksimisasi.

Langkah pertama untuk menyelesaikan masalah ini dengan menggunakan Metoda Hungarian adalah menentukan nilai terbesar dari setiap baris dengan hasil sebagai berikut;

    Baris I     : 1100

    Baris II    : 1100

    Baris III   : 1050

    Baris IV    : 1150

Hal ini berarti bahwa nilai-nilai keuntungan pada baris I dikurangkan dari 1100, baris II dikurngkan dari 1100, baris III dikurangkan 1050 dan baris IV dikurngkan dari 1150. Hasil perhitungan langkah pertama ini dapat dilihat pada Tabel 2

Tabel 2 : Hasil Perbaikan Pertama

Lokasi/ Salesman	Lokasi 1	Lokasi 2	Lokasi 3	Lokasi 4
Sal. 1	100	200	0	200
Sal. 2	0	100	150	150
Sal. 3	0	100	150	0
Sal. 4	0	150	200	150

Selanjutnya diperiksa apakah setiap kolom telah mempunyai nilai nol. Ternyata pada Tabel 2 terlihat bahwa kolom II belum mempunyai nilai nol, sehingga perlu ditentukan nilai tentukan nilai terkecil dari kolom tersebut, yaitu 100. Setiap nilai pada kolom II dikurangkan dengan 100, sehingga diperoleh hasil seperti pada Tabel 3.

Tabel 3 : Tabel Akhir (Optimum)

Lokasi/ Salesman	Lokasi 1	Lokasi 2	Lokasi 3	Lokasi 4
Sal. 1	100	100	0	200
Sal. 2	0	0	150	150
Sal. 3	0	0	150	0
Sal. 4	0	50	200	150

Sekarang lihat apakah ada empat nilai nol pada Tabel 3 dimana keempat-empatnya berada pada baris dan kolom yang berbeda. Ternyata ada, sehingga Tabel 3 dapat dinyatakan sebagai tabel optimal.

Sebagai langkah terakhir aadalah penentuan penugasan salesman ke daerah pemasaran berdasarkan pada nilai-nilai nol tadi. Dimulai dengan jumlah nilai nol satu, yaitu baris I dan IV, yang berarti salesman 1 ditempatkan di daerah pemasaran 3, salesman 4 ditempatkan di daerah pemasaran 1. Untuk baris II terdapat dua nilai nol, tetapi karena daerah pemasran 1 telah diberikan kepada salesman 4, maka salesman 2 ditempatkan di daerah pemasaran 2, dan yang terakhir salesman 3 ditempatkan di daerah pemasaran 4.

Berdasarkan penugasan yang dibuat di atas maka nilai keuntungan yang akan diperoleh adalah sebesar 1100 + 1000 + 1050 + 1150 = 4300.