面試時間最短模型面試時間最短模型面試時間最短模型面試時間最短模型編制僅供參考審核批準生效日期地址：電話：傳真:郵編:面試時間最短模型問題提出有4名同學到一家公司參加三個階段的面試。面試要求為：每個同學應依次找秘書、主管、經(jīng)理進行初試、復試、面試；每個同學都不允許插隊。每人在三個階段的面試時間都不同，具體如下表所示（單位：分鐘）：秘書初試主管復試經(jīng)理面試同學甲121518同學乙101815同學丙201614同學丁81015根據(jù)題意，本文應解決的問題有：這4名同學約定他們全部面試完以后一起離開公司。假定現(xiàn)在的時間是早晨8：00，求他們最早離開公司的時間；問題分析由題知，求4名同學最早離開公司的時間，即求4名同學都在公司面試完畢所需的最短時間。由于每人在3個階段的面試時間不同且每個同學都不允許插隊，故可知道面試總時間的長短是由面試順序決定的。而4名同學的面試順序有4！=24種情況，也就是說本題可以用窮舉法一一列出然后取使面試總時間最小的順序，但是明顯這樣做的法會很麻煩，所以我想出用規(guī)劃的方法并借助Lingo來解決這個問題。符號說明Tij表示第i個同學第j階段的面試時間；Xij表示第i個同學第j階段開始面試的時刻；Yik表示若第k個同學排在第i個同學之前，記為Yik=1，否則為Yik=0；T表示4名參加面試的同學同時離開公司的時間；MinMaX分別表示取最小值和最大值；附：i=1，2，3，4；j=1，2，3；k=1，2，3，4基本假設假設面試者均能在8:00準時到達面試地點，且記此時為0時刻；假設每個面試者由一個階段到下一個階段的時間間隔為0；假設面試中途沒有被淘汰，也沒人中途沒退出。模型建立模型建立求4名同學在公司面試完畢所需的最短時間，考慮到面試總時間的長短是由面試順序決定的，即要找一個面試順序使得4名同學面試完畢的4個時刻的最大值這一情況時所用的面試總時數(shù)最短。故由Tij（分鐘）～第i個同學第j階段的面試時間（如下表）：Tijj=1j=2j=3i=1131520i=2102018i=3201610i=481015Xij（第i個同學第j階段開始面試的時刻）可建立目標函數(shù)為：MinT=MaX{Xij+Tij}①的規(guī)劃模型。其中約束條件有：（1）時間先后次序約束（沒人只有參加完前一個階段的面試才能進入下一個階段）：Xij+Tij<=Xi，j+1（i=1，2，3，4；j=1，2）（2）每個階段j同一時間只能面試一名同學：用變量Yik表示第k個同學排在第i個同學之前，記為Yik=1，否則為Yik=0，則有：Xij+Tij-Xkj<TYik(i,k,j=1,2,3;i<k)②Xkj+Tkj-Xij<T(1-Yik)(i,k,j=1,2,3;i<k)③模型求解模型求解由目標函數(shù)①式和約束條件②③，利用LINGO軟件求解可得：由結果可知：面試所用總時間為84分鐘，即他們同時離開公司的時刻為上午9:24，根據(jù)Y12=0,Y13=0,Y14=1,Y23=0,Y24=1,Y34=1,可知面試順序為4-1-2-3，即：丁-甲-乙-丙。結果檢驗按照丁-甲-乙-丙這一面試順序，利用題中表里的數(shù)據(jù)，計算得面試所用時間剛好為84分鐘。模型改進方向（略）參考文獻（略）附錄：源代碼model:min=T;X41+8<=X42;X42+10<=X43;X31+20<=X32;X32+16<=X33;X21+10<=X22;X22+20<=X23;X11+13<=X12;X12+15<=X13;T>=X43+15;T>=X33+10;T>=X23+18;T>=X13+20;X31+20-X41<T*Y34;X32+16-X42<T*Y34;X33+10-X43<T*Y34;X21+10-X31<T*Y23;X22+20-X32<T*Y23;X23+18-X33<T*Y23;X21+10-X41<T*Y24;X22+20-X42<T*Y24;X23+18-X43<T*Y24;X11+13-X21<T*Y12;X12+15-X22<T*Y12;X13+20-X23<T*Y12;X11+13-X31<T*Y13;X12+15-X32<T*Y13;X13+20-X33<T*Y13;X11+13-X41<T*Y14;X12+15-X42<T*Y14;X13+20-X43<T*Y14;X41+8-X31<T*(1-Y34);X42+10-X32<T*(1-Y34);X43+15-X33<T*(1-Y34);X41+8-X21<T*(1-Y24);X42+10-X22<T*(1-Y24);X43+15-X23<T*(1-Y24);X31+20-X21<T*(1-Y23);X32+16-X22<T*(1-Y23);X33+10-X23<T*(1-Y23);X21+10-X11<T*(1-Y12);X22+20-X12<T*(1-Y12);X23+18-X13<T*(1-Y12);X31+20-X11<T*(1-Y13);X32+16-X12<T*(1-Y13);X33+10-X13<T*(1-Y