論指派問(wèn)題及其應(yīng)用

趙青青

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

【關(guān)鍵詞】指派問(wèn)題 匈牙利算法 資源配置

一、模型的處理

（一）建立模型

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

（二）算法步驟

1.知識(shí)準(zhǔn)備

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

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

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

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

二、指派問(wèn)題的應(yīng)用

（排課表問(wèn)題）今有4個(gè)教師A，B，C，D和4門(mén)課程：數(shù)學(xué)分析，高等代數(shù)，概率論和解析幾何.不同的教師上不同的課程的課時(shí)費(fèi)（單位：元）如下：

三、總結(jié)

本文主要介紹了運(yùn)籌學(xué)中指派問(wèn)題的求解過(guò)程，又以例題的形式充分又具體的說(shuō)明了這個(gè)問(wèn)題的在實(shí)際中的應(yīng)用。指派問(wèn)題的總體思想是求解具體情境下的最優(yōu)策略，這也是運(yùn)籌學(xué)的總體目的。在實(shí)際中掌握指派問(wèn)題的求解方法至關(guān)重要，可以提高資源的利用率，也可以使人力調(diào)配方面得到更充分的利用，總而言之，可以使生活中的具體問(wèn)題實(shí)現(xiàn)效益最大化。而我們指派問(wèn)題可能還存在很多問(wèn)題沒(méi)有考慮到，有許多不確定因素沒(méi)有考慮，因此以后可能會(huì)發(fā)現(xiàn)更為簡(jiǎn)潔的方法。

參考文獻(xiàn)：

[1]王繼強(qiáng).運(yùn)籌學(xué)教程[M].北京：國(guó)防工業(yè)出版社，2014.95-112.

[2]吳祈宗.運(yùn)籌學(xué)[M].北京：機(jī)械工業(yè)出版社，2006.92-114.

[3]吳振華.運(yùn)籌學(xué)[M].北京：北京理工大學(xué)出版社，2014.68-90.