...wd......wd......wd...體能測試時間安排優(yōu)化模型摘要本文討論了一類時間表優(yōu)化問題。首先.我們根據(jù)機(jī)器測試時間和臺數(shù)求得所需總時間段數(shù)的下屆為4。在同一個班級人數(shù)不進(jìn)行分組的前提下.將56個班級分成19個小組.計(jì)算出每個小組測試完所有工程所需的時間。然后建設(shè)了0-1規(guī)劃模型.將這19個小組的時間段放入每天的兩個測試時間段內(nèi).使得全部放完這19個小組的時段所需要的總測試時間段數(shù)最少.并求得最少測試時間段數(shù)恰好為下屆4段。其次.為了節(jié)省學(xué)生等待時間.我們將每個班級人數(shù)進(jìn)展分組.每組為20人.共分成103組。由于這20人最多來自兩個不同的班級.我們求得完成20人的時間只可能為425秒、430秒、435秒這三種情況。這樣將原來問題轉(zhuǎn)化為假設(shè)何用最少時間段數(shù)放入102個435秒。通過求解得到的時間段數(shù)為4段..等待時間最長的同學(xué)僅需等待2.6分鐘.從而說明了分組的必要。最后.通過給出了每項(xiàng)測試的人均時間應(yīng)該相等的結(jié)論.用來配置機(jī)器臺數(shù).并討論了場地容量對所需時段和等待時間的影響。關(guān)鍵詞：等待時間時間段數(shù)時間等級分組問題重述某校按照教學(xué)方案安排各班學(xué)生進(jìn)展體能測試.以了解學(xué)生的身體狀況。測試包括身高與體重、立定跳遠(yuǎn)、肺活量、握力和臺階試驗(yàn)共5個工程.均由電子儀器自動測量、記錄并保存信息。該校引進(jìn)身高與體重測量儀器3臺.立定跳遠(yuǎn)、肺活量測量儀器各1臺.握力和臺階試驗(yàn)測量儀器各2臺。身高與體重、立定跳遠(yuǎn)、肺活量、握力4個工程每臺儀器每個學(xué)生的平均測試〔包括學(xué)生的轉(zhuǎn)換〕時間分別為10秒、20秒、20秒、15秒.臺階試驗(yàn)每臺儀器一次測試5個學(xué)生.需要3分30秒。每個學(xué)生測試每個工程前要錄入個人信息.即學(xué)號.平均需時5秒。儀器在每個學(xué)生測量完畢后學(xué)號將自動后移一位.于是如果前后測試的學(xué)生學(xué)號相連.就可以省去錄入時間.而同一班學(xué)生的學(xué)號是相連的。學(xué)校安排每天的測試時間為8：00－12：10與13：30－16：45兩個時間段。5項(xiàng)測試都在最多容納150個學(xué)生的小型場所進(jìn)展.測試工程沒有固定的先后順序。參加體能測試的各班人數(shù)見附表。學(xué)校要求同一班的所有學(xué)生在同一時間段內(nèi)完成所有工程的測試.并且在整個測試所需時間段數(shù)最少的條件下.盡量節(jié)省學(xué)生的等待時間。請你用數(shù)學(xué)符號和語言表述各班測試時間安排問題.給出該數(shù)學(xué)問題的算法.盡量用清晰、直觀的圖表形式為學(xué)校工作人員及各班學(xué)生表示出測試時間的安排方案.并且說明該方案假設(shè)何滿足學(xué)校的上述要求和條件。最后.請對學(xué)校以后的體能測試就以下方面提出建議.并說明理由：如引進(jìn)各項(xiàng)測量儀器的數(shù)量；測試場所的人員容量；一個班的學(xué)生是否需要分成幾個組進(jìn)展測試等。附表參加體能測試的各班人數(shù)班號123456789101112131415人數(shù)414544442644422020383725454545班號161718192021222324252627282930人數(shù)442030393538382825303620243233班號313233343536373839404142434445人數(shù)413351392020443738394240375050班號4647484950515253545556人數(shù)4243414245421939751717二、問題分析首先.我們在不考慮將一個班級的學(xué)生分成幾個小組的情況下.求解最小的時間段數(shù)和學(xué)生等待時間。通過對機(jī)器臺數(shù)、每個工程測試時間和場地容量等因素的分析計(jì)算.我們將所有的56個班級人數(shù)劃分成19個小組.其中最后一個小組只有2個班級.其余小組的班級數(shù)量均為3。并且.每個小組內(nèi)的班級人數(shù)對比接近.這樣可以減少等待時間。我們算出每個小組測試所需要的最少時間.然后將19個小組的時間段進(jìn)展合理組合.以便得到最少的時間段數(shù)能包含這所有的19個時間段。其次.在保證時間段數(shù)最少的情況下.假設(shè)我們將同一班級人數(shù)進(jìn)展合理的分組.按照我們定義的等待時間.沒有進(jìn)入測試場所的同學(xué)不算是等待.這樣可較大程度上節(jié)約學(xué)生的等待時間.從而說明分組是必要的。模型假設(shè)和符號約定忽略人員進(jìn)入和離開測試場地所用時間；假設(shè)學(xué)生等待時間指該生進(jìn)入測試場地后開場的等待時間.不考慮其在未進(jìn)入測試場地之前的時間；把身高與體重、立定跳遠(yuǎn)、肺活量、握力、臺階實(shí)驗(yàn)測試分別稱為第一、二、三、四、五項(xiàng)測試；五個測試工程沒有先后順序；任何班級的學(xué)生做完所有測試即可離開場地；——第輪測試所花費(fèi)的時間；——第個班級的人數(shù)。模型的建設(shè)與求解由于56個班級的總?cè)藬?shù)為2036.假設(shè)每臺機(jī)器不停頓工作.所有人完成第一項(xiàng)測試至少需要2036×10÷3+56×5=7066.67〔s〕。同理可得所有人完成第二、三、四、五項(xiàng)測試至少需要的時間分別為41000、41000、15550、43036秒。那么.至少需要43036秒才能讓所有人完成全部的測試工程。由于時間段長一次為15000秒、11700秒.因此至少需要4個時間段才能完成所有人的測試工程.即時間段的下屆為4段。在不對單個班級進(jìn)展分組的前提下.由于第五項(xiàng)每次可以測5名學(xué)生.且有兩臺機(jī)器.則對不同班級的總?cè)藬?shù).可得班級測試完第五項(xiàng)所需時間分布表：表1班級總?cè)藬?shù)〔單位：人〕測試完臺階實(shí)驗(yàn)所需時間〔單位：秒〕1～10215112042521～3063531～4084341～50105551～60126561～70147571～801685當(dāng)人數(shù)多余80時.可以依次類推班級人數(shù)為n時測試臺階實(shí)驗(yàn)所需時間計(jì)算公式為：t=+5定義：在只進(jìn)展第五項(xiàng)測試時.把所有人數(shù)可能不同但測試完第五項(xiàng)所需時間一樣的班級稱為一個時間等級。例如：班級人數(shù)為35和40的兩個班級分別做完第五項(xiàng)測試所用時間均為845秒.那么按照.這兩個班級為同一時間等級。命題1：假設(shè)同一班級的人數(shù)不在進(jìn)展分組.假設(shè)每次同時進(jìn)入測試場地的班級數(shù)為3.且每個班級的人數(shù)不小于17人時.那么有：同時進(jìn)入場地的3個班級全部完成第二項(xiàng)、第三項(xiàng)、第五項(xiàng)測試所需時間與這3個班級完成所有五項(xiàng)測試所需時間一樣。證明：假設(shè)同時入場的班級分別為、、.其人數(shù)分別為、、。現(xiàn)讓這三個班級分別去做第二、三、五項(xiàng)測試.這三個班級都已經(jīng)完成各自的測試稱為第一輪；第一輪測試完成后.讓班去做第三項(xiàng)測試.讓班去做第五項(xiàng)測試.讓班去做第二項(xiàng)測試.這三個班級都已經(jīng)完成各自的測試稱為第二輪；第二輪完畢后.依次類推.讓班去做第五項(xiàng)測試.讓班去做第二項(xiàng)測試.讓班去做第三項(xiàng)測試.這三個班級都已經(jīng)完成各自的測試稱為第三輪。如表2所示：表2第二項(xiàng)測試第三項(xiàng)測試第五項(xiàng)測試第一輪第二輪第三輪在第一輪中.班的第一個學(xué)生在做完第二項(xiàng)測試后.該同學(xué)完全可以利用等待該班第二位同學(xué)的第二項(xiàng)測試的時間去進(jìn)展第一項(xiàng)測試〔共需要10+5秒〕.而當(dāng)他測試完第二項(xiàng)時.班第二位同學(xué)依然在進(jìn)展第二項(xiàng)測試.而此時班的第一個同學(xué)再去做第四項(xiàng)測試.由于班的人數(shù)不小于17.因此班還有局部同學(xué)尚未完成第二項(xiàng)測試。班的第二個同學(xué)完全按照該班第一個同學(xué)的路線進(jìn)展.以此類推。那么該班級除了后兩位同學(xué).其余均可以在班全部測完第二項(xiàng)之前.也完成第一、四項(xiàng)的測試。倒數(shù)后兩位可以在第二輪開場.即進(jìn)展第三項(xiàng)測試時.離開班隊(duì)列去做完第一、四項(xiàng)測試.然后回到對列繼續(xù)等待第三項(xiàng)測試。由于第三項(xiàng)測試的機(jī)器為三臺.第四項(xiàng)測試的機(jī)器為二臺.完全足夠.并且在第一輪中和班分別做第二、三項(xiàng)的時間均為20秒每人.班的同學(xué)的路線與班相似。對于班也可以在第一、二、三輪測試的間隙完成第一、四項(xiàng)的測試。另外.第二、三項(xiàng)測試需要20秒.而第五項(xiàng)測試序言210秒.但可以同時測試5人且有2臺機(jī)器.那么人均耗時約為21秒。并有以上的命題討論我們知道假設(shè)三個班級的人數(shù)相差不大.則對比節(jié)約時間.因此我講56個班級分組.每組的班級同時入場。表3組號班級編號對應(yīng)的人數(shù)第1組〔525556〕〔191717〕第2組〔273536〕〔202020〕第3組〔8917〕〔202020〕第4組〔122428〕〔252524〕第5組〔25235〕〔302826〕第6組〔322918〕〔333230〕第7組〔262030〕〔363533〕第8組〔113843〕〔373737〕第9組〔212239〕〔383838〕第10組〔405310〕〔393838〕第11組〔421934〕〔403939〕第12組(13148)(414141)第13組〔464951〕〔424242〕第14組〔47741〕〔434242〕第15組〔61637〕〔444444〕第16組〔4350〕〔444445〕第17組〔131415〕〔454545〕第18組〔24544〕〔455050〕第19組〔5433〕〔7551〕按照表3.可以分一下兩種情況討論：情況一：假設(shè)該組中的三個班級人數(shù)為、、均處于同一時間等級.則完成第一輪測試所需時間為：=210+5〔這里「」是上取整數(shù)函數(shù)〕；這是因?yàn)榧僭O(shè)班級人數(shù)、、處于同一時間等級.則顯然有：20×210×；再加上第一位同學(xué)錄入學(xué)號的5秒.則完成第一輪總共所需時間為：=210+5同理可得第二、三輪時間分別為=210+5和=210+5;則完成三輪測試所需的時間為：=++=「」+15〔1〕有上面的分組我們可以知道除了第6、19兩組.其他分組均出在同一時間等級.可按照〔1〕式計(jì)算完成時間〔結(jié)果見表5〕情況二：假設(shè)三個班級不全處于同一時間等級.則由于人數(shù)不同有多種情況出現(xiàn).具體情況時具體計(jì)算這里不給出計(jì)算公式。表3中有兩組的班級不同一時間等級.這兩組為第6組和第19組。現(xiàn)在分別計(jì)算器完成時間：表4第二項(xiàng)測試第三項(xiàng)測試第五項(xiàng)測試每輪測試所需要的時間〔秒〕班級編號〔人數(shù)〕所需時間〔秒〕班級編號〔人〕所需時間〔秒〕班級編號〔人〕所需時間〔秒〕第一輪32〔33〕66529(32)64518(30)635665第二輪18〔30〕60532〔33〕66529〔32〕845845第三輪29〔32〕64518〔30〕60532(33)845845由表4得完成三輪測試所需的總時間T=665+845+845=2355秒。同理可得第19組完成三輪測試所需的總時間T=4695秒。綜合上面兩種情況.我們得到所有組合做完全部測試的時間如下表所示：表5組號班級編號對應(yīng)的人數(shù)測試所需時間第1組〔525556〕〔191717〕1275第2組〔273536〕〔202020〕1275第3組〔8917〕〔202020〕1275第4組〔122428〕〔252524〕1905第5組〔25235〕〔302826〕1905第6組〔322918〕〔333230〕2355第7組〔262030〕〔363533〕2535第8組〔113843〕〔373737〕2535第9組〔212239〕〔383838〕2535第10組〔405310〕〔393838〕2535第11組〔421934〕〔403939〕2535第12組(13148)(414141)3165第13組〔464951〕〔424242〕3165第14組〔47741〕〔434242〕3165第15組〔61637〕〔444444〕3165第16組〔4350〕〔444445〕3165第17組〔131415〕〔454545〕3165第18組〔24544〕〔455050〕3165第19組〔5433〕〔7551〕4695現(xiàn)在問題轉(zhuǎn)化為：將上述19個時間按照某種組合方式全部填入每天的兩個時間段.從而使得所需的總時間段數(shù)最少。設(shè)表示所需的時間段總數(shù).表示表5中第個組合所需時間.表示第個時間段長度.其中=1.2....19；=1.2.....顯然有：=.進(jìn)一步假設(shè)0-1變量:=.其中=1.2....19；=1.2.....即得到0-1規(guī)劃模型一：min,=1;=1,2,...,19;;=1.2.....上述模型中：第一個約束表示每個組能且只能安排在某一時段;第二個約束表示安排進(jìn)任一時段的所有組的測試總時間必不大于該時段長度。利用LINGO編程解得結(jié)果如下：表6組號班級號班級人數(shù)測試時間安排第一天上午第1組〔525556〕〔191717〕8:00:00～8:21:15第2組〔273536〕〔202020〕8:21:15～8:42:30第7組〔262020〕〔363533〕8:42:30～9:24:45第8組〔113843〕9373737)9:24:45～10:07:00第9組(212239)(383838)10:07:00～10:49:15第19組〔5433〕〔7551〕10:49:15～12:07:30下午第5組〔25235〕〔302826〕13:30:00～14:01:45第15組〔61637〕〔444444〕14:01:45～14:54:30第16組〔4350〕〔444445〕14:54:30～15:47:15第17組(131415)(454545)15:47:15～16:40:00第二天上午第3組(8917)(202020)8:00:00～8:21:15第4組〔122428〕〔252524〕8:21:15～8:53:00第10組〔405310〕〔393838〕8:53:00～9:35:15第11組〔421934〕〔403939〕9:35:15～10:17:30第13組〔464951〕〔424242〕10:17:30～11:10:15第14組(47741)〔434242〕11:10:15～12:03:00下午第6組〔322918〕〔333230〕13:30:00～14:2109:15第12組〔13148〕〔414141〕14:009:15～15:02:00第18組〔24544〕〔455050〕15:02:00～15:54:45由結(jié)果可知整個測試所需時間段數(shù)最少為4段。由于已經(jīng)知道所需時段的下限也是4.故以上結(jié)果為最優(yōu)方案。對于以上的方案.基于假設(shè)〔2〕和〔5〕.每個組最后一名離開的同學(xué)〔在該組中等待時間最長〕等待時間完全由分組情況決定.與該組進(jìn)入次序無關(guān)。因?yàn)樽詈笠幻瑢W(xué)的等待時間即為該組所需時間減去275秒〔每個同學(xué)完成五項(xiàng)測試的時間〕。則由表5可得.每組等待時間最長的同學(xué)的等待時間。第一組最后一名同學(xué)總等待時間為1275-275=1000秒；第19組最后一名同學(xué)總等待時間為4420秒〔約1.23個小時〕。等待時間較長.需要改良.當(dāng)班級人數(shù)較多時.假設(shè)不對同一個班級的學(xué)生分組會使得學(xué)生的等待時間較長。為了減少學(xué)生的等待時間.可以將同一個班級人數(shù)分組進(jìn)入場地進(jìn)展測試。現(xiàn)在考慮對同一班級學(xué)生進(jìn)展分組的情況。命題2：假設(shè)每次同時進(jìn)入場地的人數(shù)為20人.且這20人學(xué)好順序相連.則完成這20人全部的5項(xiàng)測試最少需要425秒.且可以到達(dá)425秒。證明：首先證明至少425秒。因?yàn)榧词共豢紤]其他4項(xiàng).只做完第五個工程.這20人就需要425秒〔見表1〕。其次證明可以到達(dá)425秒。我們假設(shè)這20人的學(xué)號次序?yàn)閺?到20.則讓學(xué)號為1到5的學(xué)生測試第一臺臺階試驗(yàn)機(jī).與此同時讓學(xué)號為6到10的學(xué)生測試立定跳遠(yuǎn).讓學(xué)號為11到15的同學(xué)測試第二臺臺階實(shí)驗(yàn)機(jī).讓學(xué)號為16到20的同學(xué)測試肺活量。如以以以下列圖所示：立定跳遠(yuǎn)肺活量臺階實(shí)驗(yàn)臺階實(shí)驗(yàn)學(xué)號學(xué)號學(xué)號學(xué)號6161117172128183139194141020515這樣16～20號與6～10號同時測完〔都用了105秒〕。兩個交換測試工程每次同時測完(都用了105秒).這兩輪共用了210秒.而測試臺階的兩個組由于要用215秒.因此第二輪進(jìn)展太極實(shí)驗(yàn)測試的組還在繼續(xù)測試。過程如以以以下列圖所示：立定跳遠(yuǎn)肺活量臺階實(shí)驗(yàn)臺階實(shí)驗(yàn)學(xué)號學(xué)號學(xué)號學(xué)號16611117721218831319941420105156～10.16～20這兩組在等待了5秒后有同時去做臺階實(shí)驗(yàn)測試.由于學(xué)號剛好能銜接.不需要輸入學(xué)號時間。做完臺階實(shí)驗(yàn)測試的兩組去做剩余項(xiàng)的測試。過程如以以以下列圖所示：立定跳遠(yuǎn)肺活量臺階實(shí)驗(yàn)臺階實(shí)驗(yàn)學(xué)號學(xué)號學(xué)號學(xué)號1116162127173138184149195151020這樣