Hungarian : Masalah Minimisasi (Minimal)


Langkah-langkah penyelesaian dengan metoda Hungarian untuk masalah minimisasi adalah sebagai berikut :

  1. Ditentukan nilai terkecil dari setiap baris, lalu mengurangkan semua nilai dalam baris tersebut dengan nilai terkecilnya.
  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 kilom 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 nol 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 pelatih renang ingin membentuk tim renang yang tangguh untuk terjun di nomor 400m estafet gaya ganti pada suatu pertandingan tingkat nasional. Ada empat perenang di bawah asuhannya, yang merupakan perenang terbaiknya yang menguasai dengan baik keempat gaya yang dipertandikan. Pelatih ingin melakukan penugasan satu perenang pada satu gaya berdasarkan data waktu terbaik mereka untuk tiap gaya nomor 100m yang tersaji pada tabel 2, dengan bantuan metoda Hungarian

Tabel 1 Data Perolehan Waktu (dalam detik)

Perenang/

Gaya

Budi

Giri

Koko

Fajar

Kupu-Kupu

52,4

48,3

55,6

49,5

Dada

55,4

58,2

59,1

57,3

Punggung

62,7

62,5

60,9

63,2

Bebas

47,7

49,1

53,5

52,1

Penyelesaian:

Pada suatu pertandingan renang selau diinginkan waktu tercepat yang mungkin dapat dilakukan, sehingga masalah ini masuk ke dalam masalah minimisasi.

Berdasarkan data yang tersaji pada Tabel 1, maka langkah pertama yang dilakukan adalah menentukan nilai terkecil dari setiap baris. Hasil penentuan nilai terkecil tersebut adalah sebagai berikut :

Baris I    : 48,3

Baris II    : 55,4

Baris III    : 60,9

Baris IV    : 47,7

Sehingga setiap nilai pada baris I dikurngkan dengan 48,3 setiap nilai pada baris II dikurangkan dengan 55,4, setiap nilai pada baris II dikurangkan dengan 60,9 dan setiap baris IV dikurangkan dengan 47,7. Hasil perhitungan langkah pertama ini dapat dilihat pada Tabel 2.

Tabel 2 : Hasil Perbaikan Pertama

Perenang/

Gaya

Budi

Giri

Koko

Fajar

Kupu-Kupu

4,1

0

7,3

1,2

Dada

0

2,8

3,7

1,9

Punggung

1,8

1,6

0

2,3

Bebas

0

1,4

5,8

4,4

Selanjutnya dilakukan pemeriksaan apakah setiap kolom telah mempunyai nilai nol. Ternyata pada kolom IV belum terdapat nilai nol, sehingga dilakukan penentuan nilai terkecil dari kolom ini, yaitu 1,2 , kemudian setiap nilai pada kolom IV ini dikurngkan dengan 1,2 , sehingga diperoleh nilai seperti yang tersaji pada Tabel 3

Tabel 3 : Hasil Perbaikan Kedua

Perenang/

Gaya

Budi

Giri

Koko

Fajar

Kupu-Kupu

4,1

0

7,3

0

Dada

0

2,8

3,7

0,7

Punggung

1,8

1,6

0

1,1

Bebas

0

1,4

5,8

3,2

Langkah berikutnya adalah memeriksa apakah telah terdapat suatu penugasan yang layak. Bila diperhatikan akan ditemui sejumlah 5 nilai nol pada tabel 3. Tetapi dari kelima nilai nol tersebut, tidak ada empat nilai nol yang keempat-empatnya terdapat pada baris dan kolom yang berbeda. Misalnya kita ambil nilai pada kotak (1,2),(2,1),(3,3) dan (4,1), kita masih menemukan adanya dua nilai nol yang berada pada kolom yang sama yaoti nilai nol pada kotak (2,1) dan (4,1). Hal yang sama juga akan terjadi pada kemungkinan-kemungkinan yang lainya. Ini menandakan bahwa tabel belum optimal, sehingga perlu dilakukan langkah-langkah selanjutnya guna mendapatkan tabel yang optimal.

Langkah selanjutnya adalah menutup seluruh nilai nol dengan garis vertical dan horizontal seminimal mungkin, seperti yang terlihat pada tabel 4.

Tabel 4 Hasil Perbaikan Ketiga

Perenang/

Gaya

Budi

Giri

Koko

Fajar

Kupu-Kupu

4,1

0

7,3

0

Dada

0

2,8

3,7

0,7

Punggung

1,8

1,6

0

1,1

Bebas

0

1,4

5,8

3,2

Pada Tabel 4 terlihat bahwa jumlah garis yang menutup nilai nol tersebut ada tiga dan ini merupakan jumlah yang minimal, karena tidak mungkin menutup semua nilai nol dengan hanya dua garis vertical/horizontal.

Setelah seluruh nilai nol tertutup oleh garis vertiukal/horizontal, mka dilakukan penentuan nilai terkecil dari nilai-nilai yang tidak tertutup garis. Bila diperhatikan Tabel 4, maka nilai terkecil yang dimaksud adalah 0,7. Selanjutnya kita kurangkan setiap nilai yang tidak tertutup garis dengan 0,7. Langkah ini menghasilkan nilai seperti yang tersaji pada Table 5.

Tabel 5 Tabel Akhir (Optimal)

Perenang/

Gaya

Budi

Giri

Koko

Fajar

Kupu-Kupu

4,1

0

7,3

0

Dada

0

2,1

3,0

0

Punggung

1,8

1,6

0

1,1

Bebas

0

0,7

5,1

2,5

Berikutnya kembali dilakukan pemeriksaan apakah telah terdapat suatu penugasan yang layak yang memberikan solusi optimal. Pada Tabel 5 terlihat bahwa terdapat sejumlah empat nilai nol yang keempat-empatnya berada pada baris dan kolom yang berbeda sehingga dapat dikatakan bahwa tabel telah optimal. Dengan telah diperolehnya tabel yang optimal, maka ini diberikan kepada pasangan assigne-assignment pada kotak yang bernilai nol pada tabel optimal.

Penentuan penugasan sebaiknya dimulai dari baris yang hanya mengandung satu nilai nol. Pada Tabel 5, baris yang dimaksud adalah baris ke-3 dan ke-4. Hal ini berarti gaya punggung ditugaskan kepada Koko dan gaya bebas kepada Budi. Kemudian untuk baris ke-2, karena Budi telah mendapatkan tugas di gaya bebas, maka gaya dada diberikan kepada Fajar, sedangkan gaya kupu-kupu, pada baris ke-1, diberikan kepada Giri. Berdasarkan pada penugasan tersebut, maka perolehan waktu yag diperkirakan pada nomor estafet gaya ganti adalah 48,3 + 57,3 + 60,9 + 47,7 = 214,2


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s