數(shù)學(xué)建模-面試最優(yōu)化問題

1、C題面試時(shí)間問題有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)都必須首先找公司秘書初試,然后到部門主管處復(fù)試,最后到經(jīng)理處參加面試,并且不允許插隊(duì)即在任何一個(gè)階段4名同學(xué)的順序是一樣的.由于4名同學(xué)的專業(yè)背景不同,所以每人在三個(gè)階段的面試時(shí)間也不同,如下表所示單位：分鐘：秘書和試主管制H經(jīng)理面M同學(xué)甲11L1520同學(xué)乙10201H同學(xué)內(nèi)一T20161io卜同學(xué)丁1015這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司.假定現(xiàn)在時(shí)間是早晨8:00問他們最早何時(shí)能離開公司？面試時(shí)間最優(yōu)化問題摘要：面試者各自的學(xué)歷、專業(yè)背景等因素的差異,每個(gè)面試者在每個(gè)階段的面試時(shí)間有所不同,這樣就造成了按

2、某種順序進(jìn)入各面試階段時(shí)不能緊鄰順序完成,即當(dāng)面試正式開始后,在某個(gè)面試階段,某個(gè)面試者會(huì)由于前面的面試者所需時(shí)間長而等待,也可能會(huì)由于自己所需時(shí)間短而提前完成.因此本問題實(shí)質(zhì)上是求面試時(shí)間總和的最小值問題,其中一個(gè)面試時(shí)間總和就是指在一個(gè)確定面試順序下所有面試者按序完成面試所花費(fèi)的時(shí)間之和,這樣的面試時(shí)間總和的所有可能情況那么取決于n位面試者的面試順序的所有排列數(shù)根據(jù)列出來的時(shí)間矩陣,然后列出單個(gè)學(xué)生面試時(shí)間先后次序的約束和學(xué)生間的面試先后次序保持不變的約束,并將非線性的優(yōu)化問題轉(zhuǎn)換成線性優(yōu)化目標(biāo),最后利用優(yōu)化軟件lingo變成求解.關(guān)鍵詞：排列排序0-1非線性規(guī)劃模型線性優(yōu)化一問題的提出根

3、據(jù)題意,本文應(yīng)解決的問題有：1、這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司.假定現(xiàn)在的時(shí)間是早晨8: 00,求他們最早離開公司的時(shí)間；2、試著給出此類問題的一般描述,并試著分析問題的一般解法.二問題的分析問題的約束條件主要有兩個(gè)：一是每個(gè)面試者必須完成前一階段的面試才能進(jìn)入下一階段的面試同一個(gè)面試者的階段次序或時(shí)間先后次序約束,二是每個(gè)階段同一時(shí)間只能有一位面試者不同面試者在同一個(gè)面試階段只能逐一進(jìn)行.對(duì)于任意兩名求職者P、Q,不妨設(shè)按P在前,Q在后的順序進(jìn)行面試,可能存在以下兩情況：一、當(dāng)P進(jìn)行完一個(gè)階段j的面試后,Q還未完成前一階段j-1的面試,所以j階段的考官必須等待Q完成j-1階段的

4、面試后,才可對(duì)Q進(jìn)行j階段的面試,這樣就出現(xiàn)了考官等待求職者的情況.這一段等待時(shí)間必將延長最終的總時(shí)問.二、當(dāng)Q完成j-1的面試后,P還未完成j階段的面試,所以,Q必須等待P完成j階段的面試后,才能進(jìn)入j階段的面試,這樣就出現(xiàn)了求職者等待求職者的情況.同樣的,這個(gè)也會(huì)延長面試的總時(shí)間.以上兩種情況,必然都會(huì)延長整個(gè)面試過程.所以要想使四個(gè)求職者能一起最早離開公司,即他們所用的面試時(shí)間最短,只要使考官等候求職者的時(shí)間和求職者等候求職者的時(shí)間之和最短,這樣就使求職者和考官的時(shí)間利用率到達(dá)了最高.他們就能以最短的時(shí)間完成面試一起離開公司.這也是我們想要的結(jié)果.三模型的假設(shè)1 .我們假設(shè)參加面試的求職

5、者都是平等且獨(dú)立的,即他們面試的順序與考官無關(guān)；2 .面試者由一個(gè)階段到下一個(gè)階段參加面試,其間必有時(shí)間問隔,但我們?cè)谶@里假定該時(shí)間間隔為0;3 .參加面試的求職者事先沒有約定他們面試的先后順序；4 .假定中途任何一位參加面試者均能通過面試,進(jìn)入下一階段的面試.即：沒有中途退出面試者；5 .面試者及各考官都能在8:00準(zhǔn)時(shí)到達(dá)面試地點(diǎn).四名詞及符號(hào)約束6 .aiji=1,2,3,4；j=1,2,3為求職者i在j階段參加面試所需的時(shí)間甲乙丙丁分別對(duì)應(yīng)序號(hào)i=1,2,3,47 .xiji=1,2,3,4;j=1,2,3表示第i名同學(xué)參加j階段面試的開始時(shí)問不妨把早上8:00記為面試的0時(shí)刻8 .T

6、為完成全部面試所花費(fèi)的最少時(shí)間(五)模型的建立設(shè)s1,s2,s3,s4為4位面試者的一個(gè)面試順序,面試者si參加第j個(gè)階段面試所需時(shí)間為aij根據(jù)問題的2個(gè)約束條件,可作出n位面試者在s1,s2,s3,s4)面試順序下參加3個(gè)面試階段的進(jìn)展過程表,4位面試者按序s1,s2,s3,s4參加3個(gè)階段的面試進(jìn)展過程表面試者T1T2T3T4T5T6s1as1,1as1,2as1,3s2as2,1as2,2as2,3s3as3,1as3,2as3,3s4as4,1as4,2as4,3表中Ti(i=l,2,?,P)表示能同時(shí)進(jìn)行面試的人員所占用的時(shí)間段,如T3,表示面試者si在第3個(gè)面試場(chǎng),s2在第2個(gè)面

7、試場(chǎng),s3,在第1個(gè)面試場(chǎng)、其余人員在等待的那一個(gè)時(shí)間段.根據(jù)順序性可知整個(gè)面試過程的時(shí)間段數(shù)為3+4-1=6模式：以各面試者結(jié)束全部面試階段的時(shí)間為根底(以表的行為根底)目標(biāo)函數(shù)minT=maxxi3+ai3約束條件(1)面試階段約束,即必須先完成上一階段面試才能進(jìn)人下一階段面試.xij+aijxi,j+1i=l,2,3,4；j=1,2,3)(2)同一階段只能有一個(gè)面試者xij+aij-xkiTyikxkj+akj-xijT(1-yik)(i,k=l,2,3,4,ixi3+ai3;i=l,2,3,4其中y是O-1變量.表示第k個(gè)面試者是否排在第i個(gè)面試者的前面,0表示否,l表示是.由此,就將

8、問題中的約束條件“同一面試階段只能有一個(gè)面試者改用“面試者的先后次序來表示解決了問題中難于表達(dá)的約束條件,反響的關(guān)系清楚,而且在模型求解的,T值就是最小總面試時(shí)間,根據(jù)全部y值就可以排出所有面試者使T最小的面試順序.(3)(六)模型的求解編寫的lingo程序如下：model:title面試問題；sets:!person=被面試者集合,stage=面試階段集合；person/1,2,3,4/;stage/1,2,3/;!a=面試所需時(shí)間,x面試開始時(shí)間；pxs(person,stage):a,x;!y(i,k)=1:k排在i前,0:否那么；pxp(person,person)|&1#lt#&2:

9、y;endsetsdata:a=13152010201820161081015;enddatamin=maxa;!maxa是面試最后結(jié)束時(shí)間；maxa=max(pxs(i,j)|j#eq#size(stage):x(i,j)+a(i,j);!完成前一段才能進(jìn)入下一段；for(pxs(i,j)|j#lt#size(stage):x(i,j)+a(i,j)x(i,j+1);!同一時(shí)間只能面試一位同學(xué)；forfor(stage(j):for(pxp(i,k):x(i,j)+a(i,j)-x(k,j)maxa*y(i,k);(pxp(i,k):x(k,j)+a(k,j)-x(i,j)maxa*(1-y

10、(i,k););for(pxp(i,k):bin(y(i,k);endLingo結(jié)果如下：Localoptimalsolutionfound.Objectivevalue:84.00000Extendedsolversteps:43Totalsolveriterations:1681ModelTitle:面試問題VariableValueReducedCostMAXA84.000000.000000A(1,1)13.000000.000000(4)A(1,2)15.000000.000000A(2,1)10.000000.000000A(2,2)20.000000.000000A(2,3)18

11、.000000.000000A(3,1)20.000000.000000A(3,2)16.000000.000000A(3,3)10.000000.000000A(4,1)8.0000000.000000A(4,2)10.000000.000000A(4,3)15.000000.000000X(1,1)8.0000000.000000X(1,2)21.000000.000000X(1,3)36.000000.000000X(2,1)26.000000.000000X(2,2)36.000000.000000X(2,3)56.000000.000000X(3,1)38.000000.000000

12、X(3,2)58.000000.000000X(3,3)74.000000.000000X(4,1)0.0000000.9999970X(4,2)11.000000.000000X(4,3)21.000000.000000Y(1,2)0.000000-83.99950Y(1,3)0.0000000.000000Y(1,4)1.00000083.99950Y(2,3)0.000000-83.99950Y(2,4)1.0000000.000000Y(3,4)1.0000000.000000RowSlackorSurplusDualPrice184.00000-1.00000020.0000000.

13、999997030.0000000.999997040.0000000.999997050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000093.0000000.000000100.0000000.000000115.0000000.0000001217.000000.0000001363.000000.000000142.0000000.0000001548.000000.0000001626.000000.0000001756.000000.0000001834.000000.000000190.000000

14、0.99999702052.000000.0000002118.000000.0000002230.000000.000000230.0000000.0000002422.000000.0000002559.000000.000000262.0000000.0000002739.000000.0000002821.000000.0000002949.000000.0000003031.000000.000000310.0000000.0000003246.000000.0000003315.000000.0000003437.000000.000000350.0000000.999997036

15、18.000000.0000003749.000000.000000380.0000000.99999703931.000000.0000004021.000000.0000004146.000000.0000004236.000000.000000430.0000000.0000004456.000000.0000004520.000000.0000004638.000000.000000計(jì)算結(jié)果為：所有面試完成至少需要84min.面試序號(hào)為丁-甲-乙-丙.早上8:00面試,最早9:24面試可以完成.(七)模型的推廣該模式是時(shí)間最優(yōu)化的模型,有推廣的價(jià)值.例如：車間生產(chǎn)的流水線作業(yè),多(6)個(gè)部件如何根據(jù)先