“管理運(yùn)籌學(xué)”指派問題解法探析*

黃 毅 ，鄧志英

(湖南工程學(xué)院a.管理學(xué)院；b.經(jīng)濟(jì)學(xué)院，湖南 湘潭 411104)

“管理運(yùn)籌學(xué)”指派問題解法探析*

黃 毅a，鄧志英b

(湖南工程學(xué)院a.管理學(xué)院；b.經(jīng)濟(jì)學(xué)院，湖南 湘潭 411104)

指派問題是管理運(yùn)籌學(xué)教學(xué)過程中重要章節(jié)，匈牙利法是解決此類問題的基本方法，在教學(xué)過程中有學(xué)生提出了自己的看法和解題思路，嚴(yán)格按照匈牙利法基本步驟和調(diào)整之后的步驟進(jìn)行了對(duì)比，結(jié)果顯示學(xué)生的解法有一定的優(yōu)勢(shì)但也有缺陷；嚴(yán)格按照匈牙利法則過程復(fù)雜但不會(huì)面臨選擇困難，結(jié)果準(zhǔn)確但明顯速度慢于學(xué)生的方法。

管理運(yùn)籌學(xué)；指派問題；匈牙利法；最優(yōu)解

“管理運(yùn)籌學(xué)”是一門管理科學(xué)和現(xiàn)代化管理方法相結(jié)合的、注重實(shí)踐應(yīng)用的課程。在教學(xué)實(shí)踐中，一些教師習(xí)慣于教條主義，過分嚴(yán)謹(jǐn)，授課內(nèi)容都是千篇一律，從定義到定理，再到證明，最后是例題講解，這樣不僅課堂缺乏生氣，學(xué)生上課也除了記錄就無需理解和思考，很難真正理解所學(xué)知識(shí)點(diǎn)，更不能靈活運(yùn)用。[1]因此鍛煉學(xué)生解決問題能力，開發(fā)他們創(chuàng)新思考解決問題的方法，將使我們的教學(xué)手段和方法得到提升，在“管理運(yùn)籌學(xué)”指派問題的教學(xué)過程中我們就充分發(fā)揮學(xué)生的主觀能動(dòng)性，讓他們主動(dòng)解決問題，主動(dòng)發(fā)現(xiàn)新的方法，以下討論的就是在教學(xué)過程中學(xué)生發(fā)現(xiàn)的解題方法。

生活中經(jīng)常會(huì)遇到這樣的問題：有m個(gè)人恰好可以完成m項(xiàng)任務(wù)，一項(xiàng)任務(wù)由一個(gè)人完成，一個(gè)人只完成一項(xiàng)任務(wù)，由于對(duì)象特點(diǎn)與能力不盡相同，完成任務(wù)的效率和收益也不相同。[2]因此，安排適當(dāng)?shù)娜送瓿蛇m當(dāng)?shù)娜蝿?wù)，獲取最佳經(jīng)濟(jì)效益成為此類問題的關(guān)鍵，這類問題我們稱為指派問題或分派問題。指派問題是教材“管理運(yùn)籌學(xué)”一個(gè)章節(jié)，是現(xiàn)實(shí)世界經(jīng)常遇到的問題，解決指派問題的方法是由匈牙利數(shù)學(xué)家考尼格提出的，因此稱為匈牙利法。

一 匈牙利法基本思想

匈牙利法的理論根據(jù)是考尼格提出并證明了的兩個(gè)定理：[3]

定理1：設(shè)一個(gè)指派問題的效益矩陣(Cij)的行(或列)的各元素中分別減去該行(或列)的最小元素后得到一個(gè)新矩陣(Bij),則以(Bij)為效益矩陣的指派問題與原問題有相同的最優(yōu)解。

定理2：若一方陣中的一部分元素為0，一部分元素為非0，則覆蓋方陣內(nèi)所有0元的最少直線數(shù)恰好等于那些位于不同行、不同列的0元的最多個(gè)數(shù)。

二 匈牙利法基本步驟

第一，效益矩陣的初始變換——0元素獲??；

第二，最優(yōu)性檢驗(yàn)；

第三，找出能覆蓋非最優(yōu)矩陣中所有0元素的最少直線集合；

第四，非最優(yōu)矩陣變換——0元素移動(dòng)。

匈牙利法針對(duì)的是標(biāo)準(zhǔn)的指派問題，即必須滿足以下三個(gè)條件：

1.目標(biāo)要求為min；

2.效益矩陣(Cij)為n階方陣；

3.陣中所有元素Cij≥0，且為常數(shù)。

如果沒滿足以上三個(gè)條件，則必須把效益矩陣化成標(biāo)準(zhǔn)指派問題。但在本科教學(xué)過程中，我們發(fā)現(xiàn)解題過程中出現(xiàn)一系列問題在此探討。

例如：我們安排甲、乙、丙、丁四人完成三項(xiàng)任務(wù)A、B、C，一個(gè)人只能做一項(xiàng)任務(wù)，他們完成任務(wù)的利潤情況如表一所示，其中“-”表示不能勝任該項(xiàng)工作。

表一 四人完成任務(wù)利潤

在解決此類指派問題時(shí)很多同學(xué)提出自己的看法，我們?cè)诖送ㄟ^比較來回答一些同學(xué)提出的疑問，即我們首先按照匈牙利法進(jìn)行求解，然后再按照一些同學(xué)提出的思路進(jìn)行解答。

三 按照匈牙利法基本步驟求解

用表一中的最大元素去減表中每一個(gè)元素，然后增加一列使得原矩陣變成標(biāo)準(zhǔn)型指派問題如下：

每行每列減去每行每列中最小元素得到：

畫0元素得到：

?表示畫圈的0元素，由此可知我們沒有得到最優(yōu)解，必須通過畫直線來尋找最優(yōu)解，通過畫三條直線覆蓋所有0元素，然后得知沒有被直線覆蓋的最小元素是1，沒有被直線覆蓋的元素減去1，被直線十字交叉覆蓋的元素加1得到新的矩陣如下：

再畫0元素得到最優(yōu)解：

則最優(yōu)解為甲做B任務(wù)，乙做A任務(wù)，丙做C任務(wù)，總的利潤是6個(gè)單位。但在給本科生教學(xué)過程中，有的學(xué)生提出如果先每行每列減去每行每列最小元素，再化標(biāo)準(zhǔn)指派問題求解，過程簡單，一步就可以求到最優(yōu)解，不用再畫直線進(jìn)行調(diào)整，可直接得到最優(yōu)解。

四 匈牙利法調(diào)整之后步驟求解

用原矩陣中最大元素減矩陣中每一個(gè)元素得到如下矩陣：

每行每列減去每行每列中最小元素得到：

再補(bǔ)充一行0元素得到標(biāo)準(zhǔn)指派問題矩陣：

畫0元素得到矩陣：

這時(shí)第三行和第四行都剩下兩個(gè)0元素，第三列和第四列也是兩個(gè)0元素，不同的選擇會(huì)有不同的結(jié)果，這時(shí)我們必須回頭看一下原始矩陣才能做出正確選擇，原始矩陣中丙做C任務(wù)的利潤是1個(gè)單位，而丁做C任務(wù)的利潤是0單位，因此我們選擇丙做C任務(wù)，這樣我們就得到了最優(yōu)矩陣如下：

五 結(jié) 語

這個(gè)最優(yōu)矩陣的結(jié)果與我們完全按照匈牙利法基本步驟結(jié)果是一樣的，但解題過程相對(duì)簡單，不一樣的地方是他必須面臨選擇，這種選擇是必須回頭看原始矩陣才能正確做出。這種方法在教學(xué)過程中被很多學(xué)生使用，且結(jié)果正確，只是在使用時(shí)都必須面臨選擇。如果嚴(yán)格按照匈牙利法的基本步驟則不會(huì)面臨選擇，只是可能一次性得不到最優(yōu)解，要進(jìn)行調(diào)整再尋找最優(yōu)解。兩種方法的差別在于嚴(yán)格按照匈牙利法是先補(bǔ)充一行0元素，再每行每列減每行每列最小元素；而調(diào)整之后的方法是先每行每列減每行每列最小元素，再補(bǔ)充一行0元素。兩種方法都能得到最優(yōu)解，只不過前一種方法不會(huì)面臨選擇，但過程復(fù)雜；后一種方法過程簡單，但面臨選擇。我們?cè)儆脙煞N方法分別對(duì)“管理運(yùn)籌學(xué)”教材173頁課后第六題進(jìn)行計(jì)算，結(jié)論相同。通過在教學(xué)過程中積極引導(dǎo)學(xué)生思考、培養(yǎng)學(xué)生創(chuàng)新解決問題的能力，減少了學(xué)生對(duì)“管理運(yùn)籌學(xué)”恐懼感和厭學(xué)情緒，調(diào)動(dòng)了學(xué)生的積極性和學(xué)習(xí)熱情，提升了教學(xué)效率[4]。同時(shí)，通過建立教師和學(xué)生的雙向聯(lián)動(dòng)與引導(dǎo)機(jī)制進(jìn)而取得了更為優(yōu)良的教學(xué)效果，最終使學(xué)生準(zhǔn)確、有效地掌握“管理運(yùn)籌學(xué)”這門知識(shí)。

[1] 郭建華.高校轉(zhuǎn)型發(fā)展時(shí)期經(jīng)管類專業(yè)《管理運(yùn)籌學(xué)》課程教學(xué)改革探索[J].教育教學(xué)論壇，2015(7):113-114.

[2] 董銀紅，付麗麗. 管理運(yùn)籌學(xué)[M].大連：東北財(cái)經(jīng)大學(xué)出版社，2014：128-141.

[3] 韓大衛(wèi). 管理運(yùn)籌學(xué)[M].大連：大連理工大學(xué)出版社，2006：164-170.

[4] 李 穎. 財(cái)經(jīng)類院?！豆芾磉\(yùn)籌學(xué)》課程教學(xué)的改革與實(shí)踐[J].教育教學(xué)論壇，2015(12):281-282.

Analysis of Assignment Problem in Managerial Operations Research

HUANG Yia,DENG Zhiyingb

(a. School of Management， b. School of Economics, Hunan Institute of Engineering, Xiangtan 411104, China)

Assignment problem is an important chapter in the teaching process of Managerial Operations Research. The Hungarian Method is the basic method to solve problems. In the process of teaching, students put forward their views and problem-solving ideas. This paper compares with the two ways between Hungarian Method and the adjusted Hungarian Method. The results show that the students' solution has certain advantages, but also has flaws. Hungary Method turns out to be a complicated proless, easy to select, but wth slow speed and exact result.

Managerial Operations Research; assignment problem; Hungarian Method; optimal solution

2016-02-26

2016年湖南省高校教學(xué)改革研究立項(xiàng)項(xiàng)目(湘教通[2016]400號(hào)，序號(hào)602)；2014年湖南省教育科學(xué)規(guī)劃項(xiàng)目(XJK014BGD016)。

黃毅(1973-)，男，博士，副教授，碩士生導(dǎo)師，研究方向：高等教育。

G642.0

A

1671-1181(2016)04-0080-03