Materi
Masalah penugasan memasangkan setiap pekerja dengan tepat satu tugas dan setiap tugas dengan paling banyak satu pekerja, supaya total biaya sekecil mungkin. Kamus algoritma NIST mendefinisikannya sebagai pencocokan berbobot minimum atau maksimum pada graf bipartit; salah satu algoritma klasiknya adalah algoritma Munkres, yang juga disebut algoritma Hungaria.
SciPy menyediakannya sebagai scipy.optimize.linear_sum_assignment(cost_matrix, maximize=False). Masukannya matriks biaya dengan baris sebagai pekerja dan kolom sebagai tugas; keluarannya dua array, row_ind dan col_ind, dan total biayanya cost_matrix[row_ind, col_ind].sum(). Dokumentasinya menyebut bahwa matriks boleh persegi panjang: bila baris lebih banyak daripada kolom, tidak semua baris mendapat tugas. Dengan maximize=True fungsi itu mencari total terbesar, misalnya untuk skor kecocokan.
Panduan pengguna SciPy memberi contoh tim estafet renang dan menunjukkan kenapa memilih waktu tercepat di setiap gaya tidak cukup: satu perenang bisa menjadi yang tercepat di dua gaya sekaligus, padahal ia hanya boleh berenang sekali. Jumlah minimum tiap baris karenanya hanya batas bawah, belum tentu penugasan yang sah.
import numpy as np
from scipy.optimize import linear_sum_assignment
biaya = np.array([[4, 2, 8], [6, 3, 7], [3, 5, 6]]) # kurir x paket
baris, kolom = linear_sum_assignment(biaya)
print(kolom, biaya[baris, kolom].sum()) # [1 2 0] 12