指派問題（匈牙利算法）

問題描述：

在生活中經常遇到這樣的問題，某單位需完成n項任務，恰好有n個人可承擔這些任務。由于每人的專長不同，各人完成任務不同(或所費時間)，效率也不同。于是產生應指派哪個人去完成哪項任務，使完成n項任務的總效率最高(或所需總時間最小)。這類問題稱為指派問題或分派問題。

指派問題也是0-1規劃，線性規劃用到的是官網scipy.optimize庫函數。

示例： cost matrix = [ [1? 4 3], [2 0 5], [3 2 2]]

python 解決方案中，用到的是scipy.optimize.linear_sum_assignment(cost_matrix)

代碼實現：

from scipy.optimize import linear_sum_assignmentcost =np.array([[4,1,3],[2,0,5],[3,2,2]])
row_ind,col_ind=linear_sum_assignment(cost)
print(row_ind)#開銷矩陣對應的行索引
print(col_ind)#對應行索引的最優指派的列索引
print(cost[row_ind,col_ind])#提取每個行索引的最優指派列索引所在的元素，形成數組
print(cost[row_ind,col_ind].sum())#數組求和　　

輸出：
[0 1 2]

[1 0 2]?

[1 2 2]?

5