論指派問題及其應用

趙青青

【摘要】指派問題是運籌學中的一個重要的線性規劃問題，它屬于特殊的運輸問題。運籌學已經成為各行各業進行管理決策的一個基本工具，其目的是根據實際問題的具體要求，通過定量的分析與運算，對資源運用、籌劃及相關決策等問題最初綜合最優的合理安排，以使有限的資源發揮更大的效益或作用。而我們所研究的指派問題旨在解決生活中所出現的形形色色的資源配置問題。

【關鍵詞】指派問題 匈牙利算法 資源配置

一、模型的處理

（一）建立模型

指派問題AP：今有n個工人和n件工作，第i個工人做第j件工作的費用（如成本，時間，效能等）為cij，i，j=1，2，…，n.問；應如何制定一個工人和工作之間的指派方案，才能使完成這n件工作的總費用最少？

（二）算法步驟

1.知識準備

步驟1 約化費用矩陣C為C'：將C的每一行的各元素都減去本行最小的元素，每一列的各元素都減去本列的最小元素，轉步驟2.

步驟2 找獨立格子集Q：若C'的某行（列）只有一個零元素，則將其圈起，并將與其同列的其余零元素畫×，如此重復，直到C'的所有的零元素都被圈起或畫×為止.令Q={tij|c'ij=0被圈起）.若|Q|=n，則得指派問題AP的最優解為xij=1.tok∈Q 0，否則，停；否則，轉步驟3.

步驟3 找覆蓋C'的所有零元素的數目最少的直線；若某行無圈起的零元素，則在此行打√；在打√的列中，對圈起的零元素所在的行打√.如此重復，直到再也不存在可打√的行或列為止.對未打√的行畫一橫線，對打√的列畫一豎線。

繼續約化C'：令C'的未被直線覆蓋的最小元素θ，將未被直線覆蓋的元素所在的行（或列）的各元素都減去θ.為消除負元素，可將負元素所在的列（或行）的各元素都加上θ。

二、指派問題的應用

（排課表問題）今有4個教師A，B，C，D和4門課程：數學分析，高等代數，概率論和解析幾何.不同的教師上不同的課程的課時費（單位：元）如下：

三、總結

本文主要介紹了運籌學中指派問題的求解過程，又以例題的形式充分又具體的說明了這個問題的在實際中的應用。指派問題的總體思想是求解具體情境下的最優策略，這也是運籌學的總體目的。在實際中掌握指派問題的求解方法至關重要，可以提高資源的利用率，也可以使人力調配方面得到更充分的利用，總而言之，可以使生活中的具體問題實現效益最大化。而我們指派問題可能還存在很多問題沒有考慮到，有許多不確定因素沒有考慮，因此以后可能會發現更為簡潔的方法。

參考文獻：

[1]王繼強.運籌學教程[M].北京：國防工業出版社，2014.95-112.

[2]吳祈宗.運籌學[M].北京：機械工業出版社，2006.92-114.

[3]吳振華.運籌學[M].北京：北京理工大學出版社，2014.68-90.