最優分派問題(optimal assignment problem) 亦稱第二類分派問題，一種特殊的運輸問題。
舉例
人員分派問題：某公司準備分派n個工人X1,X2,...,Xn做n件工作Y1,Y2,...,Yn，已知這些工人中每個人都勝任一件或幾件工作。試問能不能把所有的工作都分派做一件他所勝任的工作？這就是人員分派問題。
對於上述人員分派問題，可以構作一個具有二分類(X，Y)的偶圖G，這裡X=(X1,X2,...Xn) , Y=(Y1,Y2,...Yn)，並且Xi和Yj相連若且唯若工人Xi勝任工作Yj，於是問題轉化為確定G是不有完美匹配的問題。按照Hall定理（設G為具有二分類（X，Y）的偶圖，則G包含飽和X的每個頂點的匹配若且唯若|N(S)|
|S|對所有S⊆X成立），或者G有這樣的匹配，或者存在X的子集S。可以使用匈牙利方法解決上述問題。
最優分派問題：如果在人員分派問題中還指望把工作人對各種工作的效率考慮進去（也許這種效率可以用收益來衡量），以便使得工作們的總效率達到最大。尋找這種分派問題即為最優分派問題。
對於最優分派問題，可以考察一個具有二分類(X，Y)的賦權完全偶圖，這裡X=(X1,X2,...Xn) , Y=(Y1,Y2,...Yn)，邊XiYj有權
ij={xi,yj}，表示工作Xi在做工作Yj時的效率。最優分派問題顯然等價於在這個賦權圖中尋找一個有最大權的完美匹配，我們稱為最優匹配。
Kuhn(1955)和Munkres(1957)提出 了在賦權完全偶圖中尋找最優匹配的一個算法（Kuhn-Munkres算法，參見“庫恩-曼克爾斯算法”）
