學生面試時間最優(yōu)規(guī)劃模型

學生面試時間最優(yōu)規(guī)劃模型摘要本文主要研究面試時間最優(yōu)問題，并建立0-1非線性規(guī)劃模型。首先我們對給出的面試時間表格進行分析將題中數(shù)據(jù)構(gòu)成原始時間矩陣，然后列出單個學生面試時間先后次序的約束和學生間的面試先后次序保持不變約束，并將非線性的優(yōu)化目標改寫成線性優(yōu)化目標。最后利用Lingo編程求解，得出丁、甲、乙、丙的順序為最優(yōu)方案，共用84分鐘。即4名同學可在9：24一起離開公司。關鍵詞：排列排序0-1非線性規(guī)劃模型線性優(yōu)化問題重述如何安排好面試時間使其達到最優(yōu)是目前面試者和面試部門值得考慮的問題。安排好時間，才能是個人和公司的利益達到最大化，因此研究并解決這類問題具有重要的意義。有4名學生到一家公司參加三階段的面試：公司要求每個同學都必須首先找公司秘書初試，然后到部門主管出復試，最后到經(jīng)理出參加面試，并且不允許插隊（即A(ij)=a11a12a21a31a41A(ij)=13152010201820161081015優(yōu)化目標：MinT=max(x(i3)+t(j3))約束條件：x(i,j)+t(i,j)<=x(i,j+i);i=1,2,3,4;j=1,2(每個同學只能參加完前一階段才能進入下一階段的面試)每階段j同一時間只能面試i名同學；0-1變量y(i,k)表示第k名同學是否排在第i名同學前面（1表示“是”，0表示“否”）x(i,j)+t(i,j)-x(k,j)<=200*y(i,k);i,k=1,2,3,4;i<k,j=1,2,3x(k,j)+t(k,j)-x(i,j)<=200*(1-y(i,k));i,k=1,2,3,4;i<k,j=1,2,3將非線性的優(yōu)化目標改寫成線性的優(yōu)化目標：Min Ts.tT>=x(i3)+t(i3),i=1,2,3,4模型求解根據(jù)建立的模型，編寫出lingo程序代碼（見附錄），通過lingo軟件運行結(jié)果如下：LINGO程序結(jié)果：Globaloptimalsolutionfound.Objectivevalue:84.00000Extendedsolversteps:12Totalsolveriterations:476VariableValueReducedCostNs4.0000000.000000Np3.0000000.000000TMAX84.000000.000000T(S1,P1)13.000000.000000T(S1,P2)15.000000.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,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)58.000000.000000X(S3,P3)74.000000.000000X(S4,P1)0.0000001.000000X(S4,P2)11.000000.000000X(S4,P3)21.000000.000000Y(S1,S2)0.000000-200.0000Y(S1,S3)0.0000000.000000Y(S1,S4)1.000000200.0000Y(S2,S3)0.000000-200.0000Y(S2,S4)1.0000000.000000Y(S3,S4)1.0000000.000000RowSlackorSurplusDualPrice10.0000000.00000020.0000000.00000035.0000000.0000004172.00000.00000050.0000001.0000006165.00000.00000070.0000000.0000008162.00000.000000915.000000.00000010152.00000.0000001122.000000.00000012147.00000.0000001318.000000.00000014152.00000.00000015179.00000.000000160.0000001.000000最短時間為84分鐘，即4名同學一起離開公司的時間是9：24.模型推廣本模型的建立思路清晰、簡單，是一個非常典型的0-1非線性規(guī)劃模型。該模型就有實用性，能使個人和公司的利益達到最大化，因此次模型及其推廣對研究并解決這類問題具有重要的意義。參考文獻朱旭、李煥琴，MATLAB軟件與基礎數(shù)學實驗；姜啟源、謝金星、葉俊，數(shù)學模型（第三版）；姜啟源、謝金星、葉俊，數(shù)學模型習題解答（第三版）肖華勇，實用數(shù)學建模與軟件應用附錄model:sets:students;！學生集三階段面試模型；phases;！階段集；sp(students,phases):t,x;ss(students,students)|&1#LT#&2:y;endsetsdata:students=s1..s4;phases=p1..p3;t=131520,102018,201610,81015;enddatans=@size(students);！學生數(shù)；np=@size(phases);！階段數(shù)；！單個學生面試時間先后次序的約束；@for(sp(i,j)|j#LT#np: