資源描述:
《面試時間最優(yōu)模型.doc》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、評分:廣州大學(xué)2010年數(shù)學(xué)建模暑期培訓(xùn)答題卡學(xué)員姓名葉麗梅學(xué)院及年級數(shù)學(xué)學(xué)院組號題目類型數(shù)學(xué)規(guī)劃模型2日期7-31請在表格下面書寫答案評語題目:秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲121518同學(xué)乙101815同學(xué)丙201614同學(xué)丁810151、這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在的時間是早晨8:00,問他們最早何時能離開公司?2、試著給出此類問題的一般描述,并試著分析問題的一般解法。答案:面試時間最短模型問題重述有4名同學(xué)到一家公司參加三個階段的面試。面試要求為:每個同學(xué)應(yīng)依次找秘書、主管、經(jīng)理進(jìn)行初試、復(fù)試、面試;每個同學(xué)都不允許插隊。每人在三個階段的面試時間都不
2、同,具體如下表所示(單位:分鐘):秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲121518同學(xué)乙101815同學(xué)丙201614同學(xué)丁81015根據(jù)題意,本文應(yīng)解決的問題有:1、這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在的時間是早晨8:00,求他們最早離開公司的時間;2、試著給出此類問題的一般描述,并試著分析問題的一般解法。問題分析由題意易知,求4名同學(xué)最早離開公司的時間,即求4名同學(xué)在公司面試完畢所需的最短時間。由于每人在三個階段的面試時間不同且每個同學(xué)都不允許插隊,故可知道面試總時間的長短是由面試順序決定的。而4名同學(xué)的面試順序有4!=24種情況,也就是說本題可以用窮舉法一一列出然后
3、取使面試總時間最小的順序,不難發(fā)現(xiàn)這樣做的工作是冗雜的,且若面試人數(shù)很大時,這個方法就顯得不科學(xué)。考慮到本題求其所用時間的最小值也就是關(guān)于面試時間的最優(yōu)解問題,所以本文采用規(guī)劃模型,并利用LINGO軟件輔助求解。符號說明表示第n個同學(xué)第m階段的面試時間;表示第n個同學(xué)第m階段開始面試的時刻;表示若第j個同學(xué)排在第n個同學(xué)之前,記為,否則為;表示4名參加面試的同學(xué)同時離開公司的時間;分別表示取最小值和最大值;附:,,模型假設(shè)1、假設(shè)面試者均能在8:00準(zhǔn)時到達(dá)面試地點,且記此時為0時刻;2、每個面試者由一個階段到下一個階段,肯定有時間間隔(如若兩階段的面試地點有一段距離,那走到下一面試
4、地點就要用一定的時間,或面試者和面試官中途上洗手間等),這里假設(shè)這個時間間隔為0;3、假設(shè)面試途中沒有被淘汰的面試者,即面試中途沒有人退出。模型建立與求解模型建立由題意可知,求4名同學(xué)在公司面試完畢所需的最短時間,考慮到面試總時間的長短是由面試順序決定的,即要找一個面試順序使得在取最后一階段4名同學(xué)面試完畢的4個時刻的最大值這一情況時所用的面試總時數(shù)最短。故由(分鐘)~第n個同學(xué)第m階段的面試時間(如下表):12151810181520161481015及(第n個同學(xué)第m階段開始面試的時刻)可建立目標(biāo)函數(shù)為:(1)的規(guī)劃模型。其中約束條件有:(1)、首先易知有:(即第n個同學(xué)第m階段
5、面試完畢所用的時間小于等于總時間)(2)(2)、由每個同學(xué)的各階段面試順序是確定的可得:(3)(3)、由(第j個同學(xué)排在第n個同學(xué)之前,記為,否則為)及同一時刻只能面試一個面試者可得:(時即可理解為第n個同學(xué)在m階段面試完畢的時刻減去第j個同學(xué)在m階段開始面試的時刻得到的第j、n個同學(xué)在m階段面試的時間總和要小于等于總時間)(4)(時即可理解為第j個同學(xué)在m階段面試完畢的時刻減去第n個同學(xué)在m階段開始面試的時刻可知即為同一時刻結(jié)果為0)(5)模型求解由目標(biāo)函數(shù)(1)式和約束條件(2)(3)(4),利用LINGO軟件求解可得:Globaloptimalsolutionfoundatit
6、eration:680Objectivevalue:83.00000VariableValueReducedCostNS4.0000000.000000NP3.0000000.000000TMAX83.000000.000000C(S1,P1)12.000000.000000C(S1,P2)15.000000.000000C(S1,P3)18.000000.000000C(S2,P1)10.000000.000000C(S2,P2)18.000000.000000C(S2,P3)15.000000.000000C(S3,P1)20.000000.000000C(S3,P2)16.00
7、0000.000000C(S3,P3)14.000000.000000C(S4,P1)8.0000000.000000C(S4,P2)10.000000.000000C(S4,P3)15.000000.000000X(S1,P1)8.0000000.000000X(S1,P2)20.000000.000000X(S1,P3)36.000000.000000X(S2,P1)20.000000.000000X(S2,P2)35.000000.000000X(S