1、面試順序問題一、摘要本文立足現(xiàn)實(shí)生活中面試排序問題的特點(diǎn)，站在面試者的角度，要求整個面試過程中使用時間最短，即所有面試者能最早離開公司，分析問題。首先，本文的問題概述如下：有4名同學(xué)到一家公司參加三個階段的面試：公司要求每個同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個階段4名同學(xué)的順序是一樣的）。已知每個同學(xué)在各個階段面試所需時間（詳見附錄三）。各同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在時間是早晨8:00，問他們最早何時能離開公司。針對這一問題，由于面試人數(shù)較少，運(yùn)算量不大，故可以運(yùn)用枚舉法將所有面試的情況列舉出來。根據(jù)題目可知

2、，共有4名同學(xué)參加面試，不難得出，4名同學(xué)面試順序的所有情況共有24種，然后計(jì)算出所有情況下的面試結(jié)束時間，根據(jù)比較，可以得出題目要求下的最優(yōu)結(jié)果，枚舉法雖然解題效率相對要低，但是考慮的情況較為全面，得出的結(jié)果是可靠的。根據(jù)以上我們提到的枚舉法解決該問題，可能做了很多的無用功，浪費(fèi)了寶貴的時間，效率低下。為此我們可以進(jìn)行優(yōu)化，對于枚舉法產(chǎn)生的弊端，我們可以運(yùn)用0-1整數(shù)規(guī)劃方法進(jìn)行優(yōu)化，根據(jù)題意建立較為優(yōu)化的模型，建立相應(yīng)的目標(biāo)函數(shù)和約束條件，并且對目標(biāo)函數(shù)進(jìn)行進(jìn)一步的改善，能夠提高解題的效率，簡化解決問題的過程，最后將我們的模型在lingo中求解，得出結(jié)果與枚舉法相一致，即4名同學(xué)面試完成的

3、最短時間是84分鐘，并且給出面試時間最短排序（丁-甲-乙-丙），為公司面試安排提供具有一定指導(dǎo)意義的建議。關(guān)鍵詞：面試問題 枚舉法 0-1整數(shù)線性規(guī)劃二、問題重述題目給出有4名同學(xué)到一家公司參加三個階段的面試，公司要求每位同學(xué)都必須首先找到公司秘書初試，然后到主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一階段，4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以每人在三個階段的面試時間也不同。表 1秘書初試主觀面試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201610同學(xué)丁81015根據(jù)題意這四名同學(xué)約定他們?nèi)棵嬖囃瓿珊笠黄痣x開公司，現(xiàn)在時間是早晨8:00，本題需

4、要我們給出一種最合理的排序方案，使得他們最早能夠離開公司。三、問題分析與基本假設(shè)在社會工作和生活中，面試順序問題十分常見。題目中的面試流程分為三個階段，每一位面試官同時期只能面試一位同學(xué)，下一名同學(xué)面試之前需要等待上一位該階段面試結(jié)束，由于4名同學(xué)在任何一階段的順序是一樣的，公司在安排面試順序的時候只需要考慮一次，使得總面試時間最短。由于數(shù)據(jù)較少運(yùn)用枚舉法可以得出真正正確的解。同時，這也是一個整數(shù)線性規(guī)劃問題，針對本題，聯(lián)系實(shí)際，可引入0-1變量，對目標(biāo)函數(shù)進(jìn)行優(yōu)化求解。在進(jìn)行數(shù)據(jù)分析時，不可能通過幾個簡單的假設(shè)就建立出一個完美的數(shù)學(xué)模型，這就需要對現(xiàn)有數(shù)據(jù)進(jìn)行一個篩選，并在此基礎(chǔ)上建立出簡易

5、的數(shù)學(xué)模型。因此，我們假設(shè)如下：（1）假設(shè)早晨時間8:00為0時刻。（2）假設(shè)上一位同學(xué)面試結(jié)束后，下一位同學(xué)立刻開始該階段面試，且時間間隔為0。（3）假設(shè)整個面試過程中任何一位面試官都連續(xù)工作。（4）假設(shè)面試過程中沒有任何同學(xué)退出。（5）假設(shè)同學(xué)和面試官都在早晨八點(diǎn)準(zhǔn)時到場。（6）各位同學(xué)和各位面試官沒有事先約定好面試順序，整個過程公平公正四、基本符號說明枚舉法符號說明：表示第個人在第j輪面試結(jié)束的時間表示第個人在第j輪面試所經(jīng)歷的時間表示每個面試順序中每個面試者每輪面試結(jié)束時間矩陣表示各個同學(xué)完成各階段面試的時刻為每個面試順序所對應(yīng)的離開時間最優(yōu)化方法符號說明：表示第個人面試第階段所用的時

6、間；表示第個人面試第階段的開始時間；表示4個人面試完成的總時間；表示第個人是否排在第個人之前， =1，表示第個人排在第個人之前，否則，=0=1,2,3,4; =1,2,3,4; =1,2,3五、模型建立與求解（一）枚舉法1.模型概述設(shè)第個人在第j輪面試結(jié)束的時間為，所經(jīng)歷的時間為， 每個面試順序中每個面試者每輪面試結(jié)束時間設(shè)為矩陣（，），則第一個人在第一輪結(jié)束的時間為，則為最終結(jié)束時間。首先根據(jù)排列組合原理，可知所有面試順序排列共有種。 確定每一種排序的面試結(jié)束時間為枚舉對象，則每個矩陣中最后一行最后一列的時間即最早離開時間。根據(jù)題意編制模型如下： 利用matlab求解結(jié)果，得出每一種順序下每

7、位面試者結(jié)束時間矩陣（去掉了第一行第一列的固定時間）。2.模型求解與算法流程圖為了使過程更加顯而易見，我們制作了簡易的算法流程圖，其想法是全排列出每一種面試排序方法，然后建立計(jì)算公式分別計(jì)算每個面試者的結(jié)束時間。圖 1根據(jù)此思路我們用matlab編寫了相應(yīng)程序得出最優(yōu)解，此順序的面試者結(jié)束時間矩陣為3.模型的優(yōu)點(diǎn)（1）結(jié)合了企業(yè)面試時的要求和特點(diǎn)，一一列舉所有可能，得到的結(jié)果肯定是正確的。（2）算法直觀，容易理解，易于證明其正確性。（3）模型穩(wěn)定，結(jié)果貼近實(shí)際。5.模型的缺點(diǎn)和改進(jìn)由于枚舉法窮舉了所有可能，運(yùn)算量比較大，解題效率低下，如果枚舉范圍太大，在時間上就難以承受， 所以我們可以在以下方

8、面進(jìn)行改進(jìn)：（1）減少狀態(tài)總數(shù)（即減少枚舉變量和枚舉變量的值域），如采用隱枚舉法可以設(shè)定條件減持。（2）減少重復(fù)計(jì)算。（3）將原問題化為更小的問題，比如考慮等待時間最小即結(jié)束時間最少的算法實(shí)現(xiàn)。（二）優(yōu)化模型1.模型建立由于已知同學(xué)數(shù)量和階段面試時間，只考慮固定一種順序的情形，記表示第個同學(xué)面試第階段所用的時間，表示第個同學(xué)面試第階段的開始時間。引入0-1變量，表示第個人是否排在第個同學(xué)之前，=1，表示第個人排在第個同學(xué)之前，否則，=0。則為第個同學(xué)面試第3階段所用時間,為第個同學(xué)面試第3階段的開始時間，要求四人完成面試后同時離開則可知表示四人完成面試后的結(jié)束時間，設(shè)為為目標(biāo)函數(shù)。這樣越小則離

9、開時間越早，于是對0-1整數(shù)線性規(guī)劃模型進(jìn)行改善，改寫為同時根據(jù)面試中的四人必須同時離開，可以建立約束此外，結(jié)合原題（1）每個人必須面試完上一輪才能開始下一輪面試（2）每個階段只能面試一個人:用0-1變量表示第個人是否排在第個人之前，即第個人排在第個人之前，=1；否則，=0。若=0，排在后面若=1，則排在前面綜上所述，可得加上之前的一個約束，綜上，最終得出一個0-1整數(shù)線性規(guī)劃模型s.t. 2.模型求解該題是一個0-1整數(shù)線性規(guī)劃問題，直接利用lingo編程求解。計(jì)算結(jié)果見圖2和附錄二。圖 2根據(jù)結(jié)果，能使四人最早同時離開的面試排序用時84分鐘，同時計(jì)算并匯總出各同學(xué)面試時間和開始時間如下表2

10、。表 2各階段開始時間各階段使用時間各階段結(jié)束時間甲（秘書初試）81321甲（主管初試）211536甲（經(jīng)理面試）362036乙（秘書初試）361036乙（主管初試）362056乙（經(jīng)理面試）561874丙（秘書初試）362056丙（主管初試）561672丙（經(jīng)理面試）741084?。貢踉嚕?88?。ㄖ鞴艹踉嚕?1018?。ń?jīng)理面試）211536圖 3圖4顯示了每位同學(xué)在各階段面試時間長短的排序，可以看出甲的主管面試、乙的秘書面試、丁的經(jīng)理面試，還有甲的經(jīng)理面試、乙的主管面試、丙的秘書初試，都分別是同時結(jié)束的。表 3variablevaluem(s1,s2)0.000000m(s1,s3)

11、0.000000m(s1,s4)1.000000m(s2,s3)0.000000m(s2,s4)1.000000m(s3,s4)1.000000又根據(jù)表5的0-1變量運(yùn)算結(jié)果可知最優(yōu)面試排序?yàn)槎?、甲、乙、丙，顯然計(jì)算結(jié)果與枚舉法模型結(jié)果相一致，確定正確。（三）結(jié)果分析通過枚舉法和規(guī)劃方法，最終可以確定，公司應(yīng)該安排四位同學(xué)按照丁、甲、乙、丙這樣的順序進(jìn)行面試可以達(dá)到用時最短時間的效果，即84分鐘，早晨9:24面試結(jié)束.枚舉結(jié)果如下。表 4序號面試順序完成面試所用時間序號面試順序完成面試所用時間1丁丙乙甲10213乙丙丁甲932丁丙甲乙9714乙丙甲丁963丁乙丙甲8915乙丁丙甲934丁乙甲丙

12、8616乙丁甲丙935丁甲乙丙8417乙甲丁丙936丁甲丙乙9518乙甲丙丁937丙丁乙甲10419甲丙乙丁1028丙丁甲乙9920甲丙丁乙979丙乙丁甲10921甲乙丙丁9110丙乙甲丁10922甲乙丁丙9111丙甲乙丁10423甲丁乙丙9112丙甲丁乙10424甲丁丙乙95如此一來同學(xué)可以完成共同離開的心愿，且公司可以以最高效率工作。但是連續(xù)工作可能會導(dǎo)致面試官疲憊，公司可以適當(dāng)在面試過程中添加休息時間，比如在56分鐘時進(jìn)行休息，此時剛好第一、二位同學(xué)丁和甲三輪面試結(jié)束，乙第二輪面試結(jié)束，丙第二輪面試尚未開始，所有人可以共同休息調(diào)整狀態(tài)。圖 4圖2為所有排序方法的結(jié)束用時計(jì)算結(jié)果，可以看出

13、各種順序的用時差別相當(dāng)大，當(dāng)面試人數(shù)更多的時候，這一差距會更加顯著，所以企業(yè)合理安排面試順序的具有重要現(xiàn)實(shí)意義。六、模型評價與改進(jìn)本文首先通過枚舉法列舉出24種排序方案，并計(jì)算出每一種排序方式的所用時間，雖然計(jì)算量較大，但程序較為容易實(shí)現(xiàn)，其正確性也較容易證明。但是可以運(yùn)用隱枚舉法進(jìn)行改進(jìn)，提高解題效率。其次，構(gòu)建了面試排隊(duì)決策的優(yōu)化模型，通過目標(biāo)函數(shù)，從而建立成了一個線性規(guī)劃模型，求地了所有同學(xué)排序情況下，被排在最后的一個同學(xué)面試完時所用總時間t（也即排序后，從第一個同學(xué)參加第一階段面試時開始計(jì)時，到最后一個同學(xué)面試完最后一階段的這段時間）中最小的一個，然后，又建立了一個0-1變量表示其約束

14、條件，并使用lingo軟件求解，所得結(jié)果具有一定的正確性和指導(dǎo)意義。但是，本文只討論了四個同學(xué)面試三個階段的合理排序方法，而沒有討論更多同學(xué)面試更多的階段的合理排序的解決方案，從而使得面試總時間最短。在實(shí)際應(yīng)用中還存在許多更復(fù)雜但是類似相關(guān)的情形，此時，若還用本文中的解決方案未必是合理的。因此，對更多同學(xué)面試更多的階段的合理排序的解決方案是進(jìn)一步應(yīng)該研究和改進(jìn)的方向。七、參考文獻(xiàn)1 姜啟源，謝金星，葉俊.數(shù)學(xué)模型（3版）.北京：高等教育出版社，2003.2 徐玖平，胡知能.運(yùn)籌學(xué)-數(shù)據(jù)決策.北京：科學(xué)出版社，2006.3 茆詩松，程依明，濮曉龍.概率論與數(shù)理統(tǒng)計(jì)（第二版）.北京:高等教育出版社

15、，20024 趙靜，但琦，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn).北京:高等教育出版社，2003.5 frank r.giordano，maurice d.weir，william p.fox(美).數(shù)學(xué)建模.葉其孝，姜啟源等譯.北京：機(jī)械工業(yè)出版社，20056 宋兆基等.matlaba在科學(xué)計(jì)算中的應(yīng)用.北京：清華大學(xué)出版社。2005.八、附錄附錄一：matlab程序：student(1).shijian=13 15 20;student(2).shijian=10 20 18;student(3).shijian=20 16 10;student(4).shijian=8 10 15;%將各學(xué)生面試時間存到結(jié)

16、構(gòu)體studentt=pailie(4,student)%求到所有面試順序所對應(yīng)的面試時間存到結(jié)構(gòu)體tfor i=1:24for i=1:24string = sprintf(x%d, i) = t(i).rearray; ;eval(string);endend%將所有面試順序所對應(yīng)的面試時間保存為矩陣附錄1（pailie.m的內(nèi)容)：function t = pailie( k,s)%k為進(jìn)行全排列的個數(shù)a=1:k;q=perms(a);%對a進(jìn)行全排列得到的數(shù)組m,n=size(q);%得到q的大小for i=1:m a=q(i,1); b=q(i,2); c=q(i,3); d=q(i

17、,4);t(i).rearray=s(a).shijian;s(b).shijian;s(c).shijian;s(d).shijian; %將全排列得到的面試者面試時間存到t結(jié)構(gòu)體endendfor k=1:24string = sprintf(time%d(1,1), k) sprintf( = x%d(1,1);,k) ;eval(string);%對每一個面試順序中第一個面試者中秘書初始結(jié)束時間string = sprintf(time%d(1,2), k) sprintf( = x%d(1,1),k) sprintf(+x%d(1,2);,k) ;eval(string);%對每一個

18、面試順序中第一個面試者中主管復(fù)試結(jié)束時間string = sprintf(time%d(1,3), k) sprintf( = x%d(1,1),k) sprintf(+x%d(1,2),k) sprintf(+x%d(1,3);,k) ;eval(string);%對每一個面試順序中第一個面試者中經(jīng)理面試結(jié)束時間string = sprintf(time%d(2,1), k) sprintf( = x%d(1,1),k) sprintf(+x%d(2,1);,k) ;eval(string);%對每一個面試順序中第二個面試者中秘書初始結(jié)束時間string = sprintf(time%d(3

19、,1), k) sprintf( = x%d(1,1),k) sprintf(+x%d(2,1),k) sprintf(+x%d(3,1);,k) ;eval(string);%對每一個面試順序中第二個面試者中秘書初始結(jié)束時間string = sprintf(time%d(4,1), k) sprintf( = x%d(1,1),k) sprintf(+x%d(2,1),k) sprintf(+x%d(3,1),k) sprintf(+x%d(4,1);,k) ;eval(string);%對每一個面試順序中第二個面試者中秘書初始結(jié)束時間endfor k=1:24for i=2:4for j=

20、2:3formatspec=time%d(i,j)=x%d(i,j)+max(time%d(i-1,j),time%d(i,j-1);str=sprintf(formatspec,k,k,k,k);eval(str);%把每個面試順序中每個面試者每輪面試剩下4個結(jié)束時間endendend則每個矩陣中最后一行最后一列的時間即最早離開時間for i=1:24time(i).final=t(i).rearray(4,3);end for i=1:24format=time(i).finaltime=time%d(4,3);str1=sprintf(format,i);eval(str1);end%把

21、24種面試順序最終離開跌時刻輸出為一個結(jié)構(gòu)體bar(time.finaltime)%把最終離開時刻做成一張柱狀圖運(yùn)行結(jié)果：其余數(shù)值結(jié)果冗長，故不予表述。附錄二：lingo程序：model:sets:students; !學(xué)生集三階段面試模型;phases; !階段集;sp(students,phases):t,x;ss(students,students)|&1 #lt# &2:m;end setsdata:students=s1.s4;phases=p1.p3;t=13 15 2010 20 1820 16 108 10 15;end datans=size(students); !學(xué)生數(shù);

22、np=size(phases); !階段數(shù);!單個學(xué)生面試時間先后次序的約束;for(sp(i,j)|j #lt# np:x(i,j)+t(i,j)=x(i,j+1);!學(xué)生間的面試先后次序保持不變的約束;for(ss(i,k): for(phases(j): x(i,j)+t(i,j)-x(k,j)=200*m(i,k); x(k,j)+t(k,j)-x(i,j)=200*(1-m(i,k); );!目標(biāo)函數(shù);min=tmax;for(students(i): x(i,3)+t(i,3)=tmax);!把y定義0-1變量;for(ss:bin(m);end運(yùn)行結(jié)果：global optima

23、l solution found. objective value: 84.00000 objective bound: 84.00000 infeasibilities: 0.1532108e-13 extended solver steps: 8 total solver iterations: 598variable value reduced cost ns 4.000000 0.000000 np 3.000000 0.000000 tmax 84.00000 0.000000t( s1, p1) 13.00000 0.000000t( s1, p2) 15.00000 0.0000

24、00t( s1, p3) 20.00000 0.000000t( s2, p1) 10.00000 0.000000t( s2, p2) 20.00000 0.000000t( s2, p3) 18.00000 0.000000t( s3, p1) 20.00000 0.000000t( s3, p2) 16.00000 0.000000t( s3, p3) 10.00000 0.000000t( s4, p1) 8.000000 0.000000t( s4, p2) 10.00000 0.000000t( s4, p3) 15.00000 0.000000x( s1, p1) 8.00000

25、0 0.000000x( s1, p2) 21.00000 0.000000x( s1, p3) 36.00000 0.000000x( s2, p1) 26.00000 0.000000x( s2, p2) 36.00000 0.000000x( s2, p3) 56.00000 0.000000x( s3, p1) 36.00000 0.000000x( s3, p2) 56.00000 0.000000x( s3, p3) 74.00000 0.000000x( s4, p1) 0.000000 1.000000x( s4, p2) 8.000000 0.000000x( s4, p3)

26、 21.00000 0.000000m( s1, s2) 0.000000 -200.0000m( s1, s3) 0.000000 0.000000m( s1, s4) 1.000000 200.0000m( s2, s3) 0.000000 -200.0000m( s2, s4) 1.000000 0.000000m( s3, s4) 1.000000 0.000000row slack or surplus dual price1 0.000000 0.0000002 0.000000 0.0000003 5.000000 0.0000004 172.0000 0.0000005 0.000000 1.0000006 165.0000 0.0000007 0.000000 0.0000008 162.0000 0.0000009 15.00000 0.00000010 152.0000 0.