面試等候最短時間建模

1、實驗六1.問題重述有4名同學(xué)到一家公司參加三個階段的面試：公司要求每個同學(xué)都必須首先到公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階段4名同學(xué)的順序都是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以沒人在三個階段的面試時間不同，如表6所示（單位：min）:表6秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201610同學(xué)丁81015這4名同學(xué)約定他們?nèi)棵嬖囃旰笠黄痣x開公司。假定現(xiàn)在時間是早上8:00，問他們最早何時能離開公司？2.基本假設(shè)：1. 每個面試的同學(xué)都必須按照先到公司秘書處初試，然后到主管處復(fù)試，最后到經(jīng)理處面試的順序進(jìn)行；

2、2. 在面試的任何一個階段都不存在插隊現(xiàn)象，即在任何一個階段4名同學(xué)的順序都是一樣的；3. 每個階段一次只能面試一個同學(xué)；4. 面試的每個過程都順利進(jìn)行，相鄰兩個過程之間沒有間隔時間。3.符號說明第名同學(xué)參加第階段面試所需要的時間第名同學(xué)參加第階段面試開始時刻（記早上8:00面試開始為0時刻）所有同學(xué)參加完面試所需時間0-1變量，表示第名同學(xué)是否排在第名同學(xué)前面4.模型建立與求解4.1模型建立目標(biāo)函數(shù)： 其中，約束條件：1）每人只有參加完前一個階段的面試才能進(jìn)入下一階段的面試： 2）每個階段同一時間只能面試1名同學(xué)，用0-1變量表示第名同學(xué)是否排在第名同學(xué)前面：其中，因此，基本模型可以表示為：

3、 4.2模型求解：將原模型進(jìn)行修改后，用lingo求解，可得求解結(jié)果如下：Global optimal solution found. Objective value: 84.00000 Objective bound: 84.00000 Infeasibilities: 0.1532108E-13 Extended solver steps: 8 Total solver iterations: 598 Variable Value Reduced Cost NS 4.000000 0.000000 NP 3.000000 0.000000 TMAX 84.00000 0.000000 S(

4、 1) 0.000000 0.000000 S( 2) 0.000000 0.000000 S( 3) 0.000000 0.000000 S( 4) 0.000000 0.000000 P( 1) 0.000000 0.000000 P( 2) 0.000000 0.000000 P( 3) 0.000000 0.000000 T( 1, 1) 13.00000 0.000000 T( 1, 2) 15.00000 0.000000 T( 1, 3) 20.00000 0.000000 T( 2, 1) 10.00000 0.000000 T( 2, 2) 20.00000 0.000000

5、 T( 2, 3) 18.00000 0.000000 T( 3, 1) 20.00000 0.000000 T( 3, 2) 16.00000 0.000000 T( 3, 3) 10.00000 0.000000 T( 4, 1) 8.000000 0.000000 T( 4, 2) 10.00000 0.000000 T( 4, 3) 15.00000 0.000000 X( 1, 1) 8.000000 0.000000 X( 1, 2) 21.00000 0.000000 X( 1, 3) 36.00000 0.000000 X( 2, 1) 26.00000 0.000000 X(

6、 2, 2) 36.00000 0.000000 X( 2, 3) 56.00000 0.000000 X( 3, 1) 36.00000 0.000000 X( 3, 2) 56.00000 0.000000 X( 3, 3) 74.00000 0.000000 X( 4, 1) 0.000000 1.000000 X( 4, 2) 8.000000 0.000000 X( 4, 3) 21.00000 0.000000 Y( 1, 2) 0.000000 -200.0000 Y( 1, 3) 0.000000 0.000000 Y( 1, 4) 1.000000 200.0000 Y( 2

7、, 3) 0.000000 -200.0000 Y( 2, 4) 1.000000 0.000000 Y( 3, 4) 1.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 0.000000 0.000000 3 5.000000 0.000000 4 172.0000 0.000000 5 0.000000 1.000000 6 165.0000 0.000000 7 0.000000 0.000000 8 162.0000 0.000000 9 15.00000 0.000000 10 152.000

8、0 0.000000 11 20.00000 0.000000 12 149.0000 0.000000 13 18.00000 0.000000 14 152.0000 0.000000 15 179.0000 0.000000 16 0.000000 1.000000 17 172.0000 0.000000 18 3.000000 0.000000 19 165.0000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 170.0000 0.000000 23 0.000000 0.000000 24 164.0000 0.00

9、0000 25 0.000000 1.000000 26 172.0000 0.000000 27 164.0000 0.000000 28 18.00000 0.000000 29 152.0000 0.000000 30 18.00000 0.000000 31 147.0000 0.000000 32 20.00000 0.000000 33 144.0000 0.000000 34 28.00000 0.000000 35 136.0000 0.000000 36 38.00000 0.000000 37 137.0000 0.000000 38 38.00000 0.000000 3

10、9 84.00000 -1.000000 40 28.00000 0.000000 41 10.00000 0.000000 42 0.000000 1.000000 43 48.00000 0.000000 44 0.000000 1.000000 45 0.000000 0.000000 46 0.000000 0.000000 47 0.000000 1.000000 48 0.000000 0.000000 49 2.000000 0.000000 50 0.000000 0.000000 51 3.000000 0.0000004.3結(jié)果分析：由上述結(jié)果可知，當(dāng)面試順序為丁-甲-乙-丙時，四人的面試時間可以達(dá)到最短，最短時間為84分鐘。附錄：源代碼：model:sets:students/1.4/:s;phases/1.3/:p;sp(students,phases):t,x;ss(students,students)|&1 #LT# &2:y;endsetsdata:t=13152010201820161081015;enddatans=size(students);np=size(phases);for(sp(i,j)|j #LT# np:x(i,j)+t(i