Skripsi matematika : Metode Hongaria dan Aplikasinya pada Kasus Minimasi

Trio Sungkowo Andi W. 2005, Skripsi jurusan matematika, Fakultas Mipa, Universitas Negeri Semarang.

Masalah penetapan (penugasan) merupakan salah satu persoalantransportasi yang merupakan kasus khusus dari masalah program linear. Untukmenyelesaikan masalah penetapan biasanya menggunakan metode umum yaitudengan cara permutasi dari n buah fasilitas dengan n buah jenis pekerjaan.Sehingga akan diperoleh n! cara pengaturan atau alternatif. Metode ini mudahdilakukan kalau n kecil, tetapi kalau sudah menyangkut untuk n yang besarmetode tersebut kurang efektif, karena harus mencari alternatif dari n! buahkemungkinan yang harus dipilih. Oleh karena itu diperlukan metode lain untukmemecahkan masalah penetapan tersebut.

Tujuan dari penelitian ini adalah untuk menjelaskan bagaimana caramenyelesaikan masalah penetapan pada kasus cacah baris sama dengan cacahkolom (m = n) dan pada kasus-kasus khusus dengan menggunakan metodeongaria.

Dalam penelitian ini untuk menjelaskan penggunaan metode Hongariadigunakan beberapa contoh kasus (soal) masalah penetapan sehinggamemudahkan dalam pemahaman. Dengan metode Hongaria, untuk menyelesaikanmasalah penetapan yang pertama dilakukan adalah membuat matriks biaya atasmasalah yang dihadapi. Kemudian dari matriks itu, kurangkan entri terkecil dalamsetiap baris dan kolom dari semua entri baris dan kolomnya sehingga mempunyaisedikit-dikitnya satu entri nol pada setiap baris dan kolom dan entri lainnya adalahtidak negatif. Kemudian menarik garis-garis melalui baris dan kolom sehinggasemua entri nol dari matriks telah terlibat. Jika jumlah minimum dari garis yangdapat ditarik adalah sama dengan cacah baris atau cacah kolom, maka sebuahpenetapan optimal telah tercapai. Tetapi jika jumlah minimum dari garis lebihsedikit, maka ditentukan entri terkecil yang tidak terdapat oleh garis manapununtuk mengurangkan semua entri yang tidak terdapat oleh garis danmenambahkannya pada semua entri yang menjadi perpotongan garis vertikal dangaris horizontal. Proses dilanjutkan sampai didapatkan jumlah garis minimumyang dapat ditarik adalah sama dengan cacah baris dan kolom.

Dari hasil pembahasan didapatkan bahwa dalam menyelesaikan masalahpenetapan pada kasus m = n menggunakan metode Hongaria terdiri dari tigatahap, yaitu tahap penyusunan tabel biaya opportunity, analisis kelayakanpenetapan optimum, dan penyusunan ulang tabel biaya opportunity. Sedangkanuntuk menyelesaikan masalah penetapan pada kasus-kasus khusus, ada sedikittambahan dalam proses penyelesaiannya. Pada masalah memaksimalkanpenetapan, agar masalah memaksimumkan menjadi masalah meminimumkanmaka setiap entri dari matriks biaya dikalikan dengan -1. Pada masalah cacahbaris dan cacah kolom yang tidak sama (m ≠ n) maka ditambahkan baris dummy(baris semu) atau kolom dummy pada baris atau kolom tabel penetapan sehinggadiperoleh m = n. Dan pada masalah penetapan yang diblokir, sel yang diblokirdiberi notasi misalkan M dan sel ini tidak perlu dievaluasi lebih lanjut karenabiayanya sangat tinggi. Untuk prosedur yang lain adalah sama seperti prosedurpada kasus m = n. Akan lebih akurat dan efisien jika kasus tersebut diselesaikandengan program komputer (Lindo ataupun TORA).