Masalah Penugasan Untuk Kasus Maksimasi Tidak Normal

Seperti masalah transportasi, masalah penugasan (assigment problem) merupakan suatu kasus khusus dari masalah linear programing pada umunnya. Dalam dunia usaha (bisnis) dan industri, manajemen sering menghadapi masalah-masalah yang berhubungan dengan penugasan optimal dari bermacam-macam sumber yang produktif atau personalia yang mempunyai tingkat efisiensi yang berbeda-beda untuk tugas–tugas yang berbeda-beda pula. Metode Hungarian (Hungarian Method) adalah salah satu dari beberapa teknik-teknik pemecahan yang tersedia untuk masalah-masalah penugasan. Metode ini mula-mula dikembangakan oleh seorang ahli Matematika berkebangsaan Hungaria yang bernama D. König pada tahun 1916.
Untuk dapat menerapakan metode ini, jumlah sumber-sumber yang ditugaskan harus sama persis dengan jumlah tugas yang akan diselesaikan. Selain itu, setiap sumber harus ditugaskan hanya untuk satu tugas. Jadi, masalah penugasan akan mencakup sejumlah n sumber yang memiliki n tugas. Karena berpasanagn satu-satu, maka dalam suatu kasus akan terdapat n! (n faktorial) penugasan yang mungkin. Masalah ini dapat dijelaskan dengan mudah dalam bentuk matriks segi, dimana baris pada matriks menunjukan sumber-sumber, dan kolom pada matris menunjukan tugas-tugas.
Masalah penugasan dapat dinyatakan secara matematis dalam suatu bentuk linear programing sebagai berikut:

Minimumkan atau maksimumkan:
Dengan batasan: dan dimana adalah tetapan yang telah diketahui. Masalah maksimasi Selain diterapkan pada kasus minimasi, metode Hungarian dapat pula diterapkan untuk kasus maksimasi, dimana elemen-elemen matriks menunjukan tingkat keuntungan (indeks produktivitas). Masalah maksimasi adalah suatu permasalahan dimana kita akan memaksimumkan tingkat keuntungan dari setiap pekerjaan yang akan ditugaskan pada setiap pekerjaan. Untuk memenuhi persyaratan suatu matriks segi empat bujur sangkar, agar metode Hungarian dapat diterapkan, bila terdapat jumlah pekerjaan lebih besar dari jumlah karyawan, maka harus ditambahkan suatu karyawan semu (dummy worker). Biaya semu adalah sama dengan nol., karena tidak akan terjadi biaya bila suatu pekerjaan ditugaskan ke karyawan semu. Atau dengan kata lain karena sebenarnya pekerjaan tersebut tidak dilaksanakan. Sebaliknya bila jumlah karyawan lebih besar dari jumlah pekerjaan, maka harus ditambahkan suatu pekerjaan semu (dummy job).

Contoh soal:
Sebuah perusahaan kecil memiliki 5 (lima) produk yang berbeda untuk dijual oleh 4 (empat) Sales Promotion Girl (SPG) .
Bagaimana cara penugasan untuk tiap-tiap SPG yang harus diambil perusahaan untuk memperoleh penjualan maksimum?

Langkah 1
Karena penugasan ini tidak seimbang, maka perlu ditambahkan variabel dummy menjadi :
Tabel penjualan produk oleh masing -masing SPG setelah ditambahkan variable dummy
a. Matriks keuntungan
b. Matriks opportunity-loss
Dengan mengurangkan seluruh elemen dalam tiap tiap baris dengan nilai maksimum dari baris yang sama, setelah itu hasil dari pengurangan di harga mutlakkan sehingga semua hasil dari pengurangan bernilai positif
c. Matriks total-opportunity-loss
Seluruh elemen dalam tiap kolom dikurangi dengan nilai minimum dari kolom yang sama, sehingga diperoleh matriks total-opportunity-loss
d. Matriks test for optimalityKarena, jumlah garis = 4 sedangkan jumlah baris atau kolom = 5.
Sehingga solusi belum layak, diperlukan revisi pada matriks.
e. Matriks hasil revisi dan test-for-optimality
Elemen terkecil yang belum terliput garis yaitu 2, digunakan untuk mengurangi seluruh elemen yang terliput garis. Kemudian, nilai ini juga ditambahkan pada elemen dengan dua garis berpotongan, yaitu 0, 0 dan 0 sehingga berturut turut menjadi 2, 2 dan 2.
Karena, jumlah garis = 4, maka jumlah garis ≠ jumlah baris atau kolom yang ada, yaitu 5 (lima), sehingga solusi yang diperoleh belum layak, diperlukan revisi lagi pada matriks hasil revisi pertama, dengan langkah-langkah seperti sebelumnya.
Dari matriks diatas, telah diperoleh suatu solusi optimum yang layak, sebab jumlah garis = jumlah baris atau kolom yang ada, yaitu 5 (lima).
Pola penugasan optimum dengan penjualan total tertinggi
tidak ada satupun SPG ditugaskan untuk menjual produk 3 (tiga). Dan pada pola penugasan optimum alternative, tidak ada satupun SPG yang ditugaskan untuk menjual produk 4 (empat).

untuk contoh soal KLIK DISINI