面試順序問題復(fù)習(xí)過程

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)用枚舉法將所有面

2、試的情況列舉出來。根據(jù)題目可知，共有 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中求

3、解，得出結(jié)果與枚舉法相一致，即4名同學(xué)面試完成的最短時間是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é)約定他們

4、全部面試完成后一起離開公司，現(xiàn)在時間是早晨 8:00,本題需要我們給出一種最合理的排序方案，使得他們最早能夠離開公 司。三、問題分析與基本假設(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è)就建立出

5、一個完美的數(shù)學(xué)模型，這就需要對現(xiàn)有數(shù)據(jù)進(jìn)行一個篩選，并在 此基礎(chǔ)上建立出簡易的數(shù)學(xué)模型。因此，我們假設(shè)如下：(1)假設(shè)早晨時間8:00為0時刻。(2)假設(shè)上一位同學(xué)面試結(jié)束后，下一位同學(xué)立刻開始該階段面試，且時間問隔為00(3)假設(shè)整個面試過程中任何一位面試官都連續(xù)工作。(4)假設(shè)面試過程中沒有任何同學(xué)退出。(5)假設(shè)同學(xué)和面試官都在早晨八點(diǎn)準(zhǔn)時到場。(6)各位同學(xué)和各位面試官沒有事先約定好面試順序，整個過程公平公正四、基本符號說明枚舉法符號說明：tj表示第i個人在第j輪面試結(jié)束的時間Xij表示第i個人在第j輪面試所經(jīng)歷的時間Tk表示每個面試順序中每個面試者每輪面試結(jié)束時間矩陣Time表示各個

6、同學(xué)完成各階段面試的時刻Timel. finaltime為每個面試順序所對應(yīng)的離開時間最優(yōu)化方法符號說明：Xj表示第i個人面試第j階段所用的時間；Tj表示第i個人面試第j階段的開始時間；T表示4個人面試完成的總時間；M ik表示第k個人是否排在第i個人之前，M ik =1 ,表示第k個人排在第i個人之前，否則，Mik=0i=1,2,3,4;k=1,2,3,4; j =1,2,3五、模型建立與求解(一)枚舉法.模型概述設(shè)第i個人在第j輪面試結(jié)束的時間為tj,所經(jīng)歷的時間為Xj ,每個面試順序中每個面試者每輪面試結(jié)束時間設(shè)為矩陣Tk ( 0 k 24, 24 A：),則第一個人在第一輪結(jié)束的時間為

7、tij Xij , tij Xj max t i-1 j, ti j,1 ,則t43為最終結(jié)束時間。首先根據(jù)排列組合原理，可知所有面試順序排列共有A 4 24種。確定每一種排序的面試結(jié)束時間為枚舉對象，則每個矩陣中最后一行最后 一列的時間即最早離開時間。根據(jù)題意編制模型如下： TOC o 1-5 h z Xji1, j1Time j iXiji1,2j4Timejj Timei 1 jxjj1,2i3xj max Timei 1 j ,Timei j 12i 3,2j 4利用MATLA求解結(jié)果，得出每一種順序下每位面試者結(jié)束時間矩陣（去掉 了第一行第一列的固定時間）。.模型求解與算法流程圖為了

8、使過程更加顯而易見，我們制作了簡易的算法流程圖，其想法是全排 列出每一種面試排序方法，然后建立計(jì)算公式分別計(jì)算每個面試者的結(jié)束時 問。笥日至小道.即信草能定開的肥間根據(jù)此思品&我們用MATLA踹寫了相應(yīng)程序得出81015131520102018201610最優(yōu)解X5,此順序的面試者結(jié)束時間矩陣為Time58 1821 3631 5651 725374843,模型的優(yōu)點(diǎn)(1)結(jié)合了企業(yè)面試時的要求和特點(diǎn)，一一列舉所有可能，得到的結(jié)果肯定是 正確的。(2)算法直觀，容易理解，易于證明其正確性。(3)模型穩(wěn)定，結(jié)果貼近實(shí)際。5,模型的缺點(diǎn)和改進(jìn)由于枚舉法窮舉了所有可能， 運(yùn)算量比較大，解題效率低下，

9、如果枚舉范圍太大，在時間上就難以承受，所以我們可以在以下方面進(jìn)行改進(jìn)：(1)減少狀態(tài)總數(shù)(即減少枚舉變量和枚舉變量的值域)，如采用隱枚舉法可以設(shè)定條件減持。(2)減少重復(fù)計(jì)算。(3)將原問題化為更小的問題，比如考慮等待時間最小即結(jié)束時間最少的算法 實(shí)現(xiàn)。(二)優(yōu)化模型.模型建立由于已知同學(xué)數(shù)量和階段面試時間，只考慮固定一種順序的情形，記Xj表示第i個同學(xué)面試第j階段所用的時間，Tj表示第i個同學(xué)面試第j階段的開始 時間。引入0-1變量Mik, Mik表示第k個人是否排在第i個同學(xué)之前，Mik=1,表示第k個人排在第i個同學(xué)之前，否則，Mik=0。(i 1,2,3,4; j1,2,3,4)1,第

10、k個人排在第i個同學(xué)之前Mik 0,第k個人排在第i個同學(xué)之后則Xi3為第i個同學(xué)面試第3階段所用時間，13為第i個同學(xué)面試第3階段的開始時間，要求四人完成面試后同時離開則可知Max(Xi3/3)表示四人完成面試后的結(jié)束時間，設(shè)為為目標(biāo)函數(shù)T Max(Xi3 Ti3)。這樣T越小則離開時間越早，于是對 0-1整數(shù)線性規(guī)劃模型進(jìn)行改善，改寫為MinTMax(Xi3 Ti3)同時根據(jù)面試中的四人必須同時離開，可以建立約束X13 T13 TX23 T23 TX33 T33 TX43 T43 T此外，結(jié)合原題(1)每個人必須面試完上一輪才能開始下一輪面試Xij Tj Xj 1(i 1,2,3,4; j

11、 1,2)(2)每個階段j只能面試一個人：用0-1變量M ik表示第k個人是否排在第i個人之前，即第k個人排在第i個人之前，Mik=1;否則，Mik =0若Mik=0, k排在i后面X T八 j1 ijX kjTkj若Mik=1,則k排在i前面XkjXijX jTjX kjX kj Tkj0(i,k1,2,3,4;j1,2,3; ik)T(i,k1,2,3,4;j1,2,3; ik)T(i,k1,2,3,4;j1,2,3;ik)0(i,k1,2,3,4;j1,2,3;ik)綜上所述，可得XjTjXkjTM ik(i,k1,2,3,4; j1,2,3; ik)XkjTkjXjTM ik(i,k1

12、,2,3,4; j1,2,3; ik)加上之前的一個約束，綜上，最終得出一個 0-1整數(shù)線性規(guī)劃模型MinT Max(Xi3 Ti3)s.t. TOC o 1-5 h z XjTjXkjTMik,(i,k1,2,3,4;j1,2,3;ik)XkjTkjXjTMik,(i,k1,2,3,4;j1,2,3;ik)X13T13TX23T23TX33T33TX 43T43T1,第k個人排在第i個同學(xué)之前Mik0,第k個人排在第i個同學(xué)之后.模型求解該題是一個0-1整數(shù)線性規(guī)劃問題，直接利用lingo編程求解。計(jì)算結(jié)果 見圖2和附錄二。UNGO 11.0 Sall/er Status Lingo 1So

13、htr StatusILTKalISonline uv；0Global OptLtfig4rs6jjectlre.94pCrtntrai ntsasilili q；4部Ln1 S32L1B-014598t。：49DiiiiMsr：0Ki力，胖日弋Nr 32SilvarBandE94G 孫*rtnr Man cry l5*J 與0l J E OIJJLd ：Q4270Elapsed timt:me I.EK： nm： ss)0OC：Q0-OCIiitemipt 5jlverl Close圖2根據(jù)結(jié)果，能使四人最早同時離開的面試排序用時 84分鐘，同時計(jì)算并匯總出各同學(xué)面試時間和開始時間如下表 2

14、。表2各階段開始時間各階段使用時間各階段結(jié)束時間甲(秘書初試)81321甲(主管初試)211536甲（經(jīng)理面試）362036乙（秘書初試）361036乙（主管初試）362056乙（經(jīng)理面試）561874丙（秘書初試）362056丙（主管初試）561672丙（經(jīng)理面試）741084?。貢踉嚕?88丁（主管初試）81018?。ń?jīng)理面試）211536各同學(xué)各階段面試時間及排序*空、之3 51、望、玄、壹飛微、 工廠3 t tS j&-B，1.及我上人余力金傘圖3圖4顯示了每位同學(xué)在各階段面試時間長短的排序，可以看出甲的主管面試、 乙的秘書面試、丁的經(jīng)理面試，還有甲的經(jīng)理面試、乙的主管面試、內(nèi)的秘

15、書 初試，都分別是同時結(jié)束的。表3VariableValueM(S1,S2)0.000000M(S1,S3)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廳P面試順序完成面試所用時間廳P面試順序完成面試

16、所用時間1丙乙甲10213乙丙甲932丙甲乙9714乙丙甲丁963乙丙甲8915乙丙甲934乙甲丙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é)束，內(nèi)第二輪面試尚未開始，

17、所有人可以共同休息調(diào)整狀。4圖2為所有排序方法的結(jié)束用時計(jì)算結(jié)果，可以看出各種順序的用時差別 相當(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ì)時， 到最

18、后一個同學(xué)面試完最后一階段的這段時間）中最小的一個，然后，又建立 了一個0-1變量表示其約束條件，并使用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ù)決策.北京

19、：科學(xué)出版社，2006.3其詩松，程依明，濮曉龍.概率論與數(shù)理統(tǒng)計(jì)（第二版）.北京：高等教育出 版社，20024趙靜，但琦，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn).北京：高等教育出版社，2003.5 Frank R.Giordano , Maurice D.Weir , W川iam 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).shiji

20、an=20 16 10;student(4).shijian=8 10 15;%等各學(xué)生面試時間存到結(jié)構(gòu)體studentT=pailie(4,student)%t到所有面試順序所對應(yīng)的面試時間存到結(jié)構(gòu)體T for i=1:24 for i=1:24 string = sprintf(X%d, i) = T(i).rearray; eval(string); end end%等所有面試順序所對應(yīng)的面試時間保存為矩陣附錄 1 (pailie.m 的內(nèi)容)：function T = pailie( k,S)%k為進(jìn)行全排列的個數(shù)A=1:k;Q=perms(A);m,n=size(Q);for i=1

21、:m%t A進(jìn)行全排列得到的數(shù)組%馬到Q的大小a=Q(i,1);b=Q(i,2);c=Q(i,3);d=Q(i,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( =

22、X%d(1,1),k)sprintf(+X%d(1,2);,k);eval(string);%寸每一個面試順序中第一個面試者中主管復(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);%寸每

23、一個面試順序中第二個面試者中秘書初始結(jié)束時間string = sprintf(Time%d(3,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);%寸每一個面試順序中

24、第二個面試者中秘書初始結(jié)束時間endfor k=1:24for i=2:4for j=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);%ffi每個面試順序中每個面試者每輪面試剩下4個結(jié)束時間endendend則每個矩陣中最后一行最后一列的時間即最早離開時間for i=1:24time(i).final=T(i).rearray(4,3);end for i=1:24format=Time(i).finaltime=Time%d

25、(4,3);str1=sprintf(format,i);eval(str1);end喏巴24種面試順序最終離開跌時刻輸出為一個結(jié)構(gòu)體bar(Time.finaltime)%f巴最終離開時刻做成一張柱狀圖運(yùn)行結(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 1

26、5;end datans=size(students); !學(xué)生數(shù);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);!JEYm義0-1變量；for(ss

27、: bin(m);end運(yùn)行結(jié)果：Global optimal solution found.Objective value:84.00000Objective bound:84.00000Infeasibilities:0.1532108E-13Extended solver steps:8Total solver iterations:598VariableValueReduced CostNS4.0000000.000000NP3.0000000.000000TMAX84.000000.000000T( S1, P1)13.000000.000000T( S1, P2)15.000000

28、.000000T( S1, P3)20.000000.000000T( S2, P1)10.000000.000000T( S2, P2)20.000000.000000T( S2, P3)18.000000.000000T( S3, P1)20.000000.000000T( S3, P2)16.000000.000000T( S3, P3)10.000000.000000T( S4, P1)8.0000000.000000T( S4, P2)10.000000.000000T( S4, P3)15.000000.000000X( S1, P1)8.0000000.000000X( S1,

29、P2)21.000000.000000X( S1, P3)36.000000.000000X( S2, P1)26.000000.000000X( S2, P2)36.000000.000000X( S2, P3)56.000000.000000X( S3, P1)36.000000.000000X( S3, P2)56.000000.000000X( S3, P3)74.000000.000000X( S4, P1)0.0000001.000000X( S4, P2)8.0000000.000000X( S4, P3)21.000000.000000M( S1, S2)0.000000-200.0000M( S1, S3)0.0000000.000000M( S1, S4)1.000000200.0000M( S2, S3)0.000000-200.0000M( S2, S4)1.0000000.000000M( S3, S4)1.0000000.000000RowSlack