矩陣在優化模型中的應用

付小娟，吳洪坤

(1.廣州民航職業技術學院 人文社科學院，廣東 廣州 510403；2.廣州民航職業技術學院 機務工程學院，廣東 廣州 510403)

1 問題的提出

隨著高校擴招規模的增大，許多學校都面臨著教師的引進問題，而學校專業設置不同，需要招聘的教師背景不同，采用的面試手段也有所差異，而從一個學校的角度來看，如何根據自己的需求和應聘者的專業背景等相關資料來設計一場高效的面試，這是很多專家學者亟待解決的問題.根據相關統計發現：很多學校都把面試程序設計為初試，復試、試講和面試4個階段，現以廣東某高校準備招聘6位新教師為例，根據每位應聘者的不同專業，分別預定出他們在每個階段所需的面試時間，問題是如何安排這6位面試者的面試順序才能既節省時間又提高面試效率.6位面試者時間分布表如表1所示：

表1 6位面試者的面試時間分布表 min

2 數學模型的建立

2.1 問題分析

問題就是如何根據這6位面試者的具體面試時間設計一個最節省時間的面試方案，這屬于一個最優化模型[1]21-24，根據題中所述，關鍵是如何設定6位面試者的面試順序，6個人的總面試順序有720種，而面試順序一旦確定，6位面試者在不同階段的面試就完全遵循這一順序約定，而不再更改.因此，這又是一個排序問題的最優化模型.要想節省時間，最要緊的是縮短等待時間，這里的等待時間包括求職者等待被面試的時間和面試考官等待面試求職者的時間，這兩個等待時間必然都會使總面試時間增長，而不同的面試順序將導致最終的總面試時間不同，其中，最短的總面試時間即對應最優的面試順序.

2.2 模型假設與符號約定

假設所有面試者都能夠參加完所有面試，中途不淘汰.所有面試考官都能按時參加完每一場面試.

假設每個面試者只有在進行完上一階段面試后才能進入下一階段面試.每個階段一次只能面試一個人.

假設abcdef分別表示第1、2…6人，面試順序約定為英文字母順序.

符號約定：

cBi,cBj表示矩陣B中從左到右第i條主對角線和第j條次對角線上的元素.

2.3 建模與求解

根據順序性可知，面試過程的時間段數為r=m+n-1=6+4-1=9

假設面試順序是a、b、c、d、e、f，則其對應的該面試問題的時間段圖表為表2：

表2 面試順序為abcdef時的9個面試時間段分布表 min

各時間段的意思：t3表示在此時間段內面試者a進行第三階段即試講，面試者b進行復試，而面試者c進行初試，以此類推.

由表2可知，在某個特定時間段的最大值所對應的時間內，此時間段內的所有面試都可以進行完，這里面已經涵蓋了兩種等待時間，所以，如果把各個時間段對應的最大值求和，那么其和就必然是該面試順序下的總面試時間.如果，把表一看作一個矩陣[2]135-139，設其為A，則發現表2中時間段所對應的每一列數，正是矩陣A的次對角線以及與次對角線相平行的對角線上的元素，例如：t3時間段從上到下三個時間分別是25，20，10，這正是矩陣A中從左到右的第三條次對角線上的元素，為了能使tr對應的每列元素和矩陣的主對角線元素相對應，現轉置矩陣A變為B，這時面試順序按從右到左的順序是abcdef，而其逆順序是fedcba.

A：6位面試者的面試時間分布矩陣，從上到下，面試順序是abcdef

B：矩陣A的轉置矩陣從右到左，面試順序仍然是abcdef

計算出矩陣B的主對角線及與主對角線平行的各條線上元素的最大值，再求和就可以得到第一種面試順序下的總時間：

即面試順序為abcdef時面試所花費總時間為170分；而矩陣B的次對角線以及與次對角線相平行的各條對角線上最大元素的和為：

表示面試順序為fedcabf時的面試時間為181分.更換矩陣B中第五列和第六列，面試順序變為bacdef，計算出其主對角線及與主對角線平行的各條線上元素的最大值再求和，可以得到此種面試順序的總時間，以及相反順序的總面試時間；同理，更換矩陣B的第四列和第六列得到面試順序為cbadef的總時間，以及面試順序為fedabc時的總時間；如此反復交換算出所有面試順序中所花費的總時間，其中，最小者就是總最短時間，相對應的就是最優的面試順序，由此建立目標函數：t=mintk

最后利用C++語言編程計算，經比較得出最短總時間是165分，而其所對應的面試順序為cdfbae,此即為最佳面試順序.

3 結果與分析

當面試順序為cdfbae時其對應面試時間段分布表為如下表3所示，發現其每列最大值之和剛好是165，表示總面試時間為165分，這165分已經包含了面試者等待被面試的時間和面試考官等待面試求職者的時間，在此時間內能夠完成所有6個求職者4個階段的面試，與C++程序所計算結果相吻合；而且從上表中可以看出每個面試時間段的等待時間，其中，面試者的總等待時間是64分，而面試考官的總等待時間為56分，兩者非常接近，說明此結果比較接近實際情況.見表3.

表3 面試順序為cdfbae時的面試時間段分布表 min

設面試順序為cdfbae時其對應的矩陣為E，可以發現矩陣E的每一條主對角元素剛好和表三中每一個時間段元素對應，主對角線元素中最大值分別為10，11，25，21，22，23，25，20，8，這些最大值之和為165，表明當面試順序為cdfbae時花費總時間為165分，這和表3的結果吻合，也正是C++程序所計算的結果.

4 模型推廣

此模型在處理時間方面假設的是每個階段求職者的面試順序是固定不變的，事實上，為了節省時間，再考慮到盡量不讓面試考官等待求職者，而且實際招聘情況，通常應聘者通過初試后方可以進行以后3個階段的面試，所以，此模型可以改進為第一階段固定順序，以后每一階段的面試順序靈活變動.另外，此模型通常適合于考場的安排、課程的編排[4] 240-242，[5]87-90、公司招聘人才的面試、高效擇優錄取以及產品的生產流程[6]60-62安排等方面,具有重要的應用價值.

參考文獻：

[1] 但 琦，趙 靜，付詩祿.數學建模課內容和教學方法的探討[J].工科數學，2002，18(06).

[2] 王培麟.計算機應用數學:第二版[M].北京：機械工業出版社，2007.

[3] 宏道工作室.融會貫通visual C++6.0[M].北京：人民交通出版社，2000.

[4] 王 鳳，林 杰.高校排課問題的圖論模型及算法[J].計算機工程與應用學報，2009，45(27).

[5] 陶華亭，郭 玲.用圖論方法解決排課沖突問題[J].鄭州經濟管理干部學院學報，2004，19(03).

[6] 趙家黎,梁角虎,胡赤兵.多工序制造過程錯誤工序的追溯[J].機床與液壓，2009，37(10).