Model Penugasan dan Analisis Matriks Payoff

Pengertian Umum

Model penugasan (assignment model) adalah salah satu tipe program linear yang bertujuan menentukan cara terbaik menugaskan sejumlah pekerja (atau sumber daya) ke sejumlah tugas sehingga total biaya atau total keuntungan menjadi optimal. Model ini sangat relevan dalam perencanaan produksi, penjadwalan, alokasi tenaga kerja, dan logistik.

Sedangkan matriks payoff (atau matriks hasil) merupakan representasi tabel yang menunjukkan nilai hasil (payoff) yang akan diperoleh apabila suatu kombinasi pekerjatugas dipilih. Nilai payoff dapat berupa biaya, waktu, profit, atau nilai utilitas lain yang relevan.

Model Penugasan

Model penugasan klasik dapat dituliskan dalam bentuk program linear berikut:

            Min     cij xij            s.t.   xij = 1   untuk semua i                   xij = 1   untuk semua j                  xij  {0,1}        

Dimana:

• c_ij = biaya (atau payoff negatif) menugaskan pekerja i ke tugas j.
• x_ij = variabel keputusan biner; 1 bila penugasan dipilih, 0 bila tidak.
• Setiap pekerja hanya boleh ditugaskan ke satu tugas, dan setiap tugas hanya boleh menerima satu pekerja.

Penyelesaian model ini biasanya menggunakan algoritma Hungarian (Algoritma KuhnMunkres) yang memiliki kompleksitas O(n) dan sangat efisien untuk ukuran sedang.

Matriks Payoff

Matriks payoff menampilkan nilai c_ij pada posisi baris i, kolom j. Contoh sederhana untuk tiga pekerja dan tiga tugas:

Angkaangka tersebut dapat mewakili biaya (semakin kecil lebih baik) atau profit (semakin besar lebih baik). Jika menggunakan profit, fungsi tujuan menjadi Max p_ij x_ij dan algoritma yang sama tetap berlaku dengan mengubah sign atau menggunakan transformasi p' = max(p)+1p.

Metode Analisis Matriks Payoff

Ada beberapa teknik yang dapat dipadukan dengan model penugasan untuk analisis lebih mendalam:

1. Analisis Sensitivitas memeriksa seberapa besar perubahan pada elemen matriks payoff (c_ij) sebelum solusi optimal berubah. Pada algoritma Hungarian, nilai potensi (potential) pada baris dan kolom membantu menghitung batas toleransi.
2. Penggunaan Nilai Kriteria bila terdapat faktor kualitatif (misalnya keahlian, preferensi), dapat dikonversi menjadi skor numerik dan digabungkan ke dalam payoff.
3. Model MultiObjective ketika terdapat lebih dari satu tujuan (biaya + waktu), dapat menggunakan metode weighted sum atau Pareto frontier setelah matriks payoff masingmasing disiapkan.
4. Stokastik / Uncertain Payoff bila nilai payoff tidak pasti, teknik simulasi MonteCarlo atau pendekatan robust optimization dapat diterapkan pada model penugasan.

Contoh Implementasi

Catatan: Model penugasan dapat diperluas menjadi masalah transportasi, alokasi sumber daya proyek, atau penempatan fasilitas. Kuncinya adalah menyiapkan matriks payoff yang akurat dan memastikan bahwa setiap baris dan kolom mewakili satusatu hubungan yang diperlukan.