數(shù)學(xué)建模論文29626

PAGEPAGE25多臺(tái)設(shè)備同時(shí)故障的最優(yōu)維修次序一、摘要本文是關(guān)于多臺(tái)設(shè)備同時(shí)故障時(shí)維修次序的優(yōu)化設(shè)計(jì)問題，即在給定每臺(tái)設(shè)備所需維修時(shí)間和停工造成損失的條件下，確定維修次序，使企業(yè)經(jīng)濟(jì)損失降到最低。我們以經(jīng)典的排列論為基礎(chǔ)，利用數(shù)值模擬技術(shù)，將影響設(shè)備維修次序的兩個(gè)離散型的數(shù)學(xué)變量（維修時(shí)間和每小時(shí)造成的損失）用計(jì)算機(jī)實(shí)值模擬，建立了相應(yīng)的排隊(duì)論數(shù)學(xué)模型，用窮舉技術(shù)得到設(shè)備的所有維修次序，進(jìn)而從中選取最優(yōu)值，實(shí)值模擬方案如下：方案一：一個(gè)工人維修七臺(tái)故障設(shè)備時(shí)，根據(jù)排隊(duì)論知識(shí)，可以將它抽象為七個(gè)不同的對(duì)象排隊(duì)列，最終由計(jì)算機(jī)模擬數(shù)據(jù)可得最佳維修次序?yàn)椋?563147，而最小損失為：199.90（萬(wàn)元）；方案二：在結(jié)論一的基礎(chǔ)之上，我們將維修工人擴(kuò)展到甲乙兩人，我們繼續(xù)對(duì)排隊(duì)論技術(shù)進(jìn)行進(jìn)一步改進(jìn)，最終得到了甲乙兩人維修時(shí)最小損失：117.30（萬(wàn)元）;最佳維修次序甲：5614乙：237方案一，二維修次序的編號(hào)與損失之間的關(guān)系在下圖中對(duì)比展示；方案三：在方案一的基礎(chǔ)上，將故障設(shè)備數(shù)量擴(kuò)展到n，而由組合數(shù)學(xué)可知故障設(shè)備數(shù)目與維修方案種數(shù)之間滿足函數(shù)f（n）=n!；當(dāng)n取值較小時(shí)，用數(shù)值模擬技術(shù)可以得到極為精確而可靠的最優(yōu)解，而當(dāng)n值很大時(shí)，得到最優(yōu)解會(huì)很困難，此種情況稱之為“組合爆炸”，為此我們采取函數(shù)嵌套遞歸來(lái)實(shí)現(xiàn)組合爆炸問題的求解。二、問題的重述對(duì)于生產(chǎn)企業(yè)而言，其生產(chǎn)設(shè)備都會(huì)在壽命期內(nèi)出現(xiàn)各種原因的故障，需要進(jìn)行維修方能繼續(xù)進(jìn)行正常生產(chǎn)，對(duì)設(shè)備進(jìn)行維修不僅需要企業(yè)負(fù)擔(dān)一定數(shù)額的維修成本，而且因設(shè)備維修耽擱生產(chǎn)會(huì)給企業(yè)造成巨大的經(jīng)濟(jì)損失，因此為了使企業(yè)的經(jīng)濟(jì)損失降到最低，一旦出現(xiàn)設(shè)備故障就應(yīng)及時(shí)對(duì)設(shè)備進(jìn)行維修，使其盡快投入生產(chǎn)，但如果發(fā)生多臺(tái)設(shè)備同時(shí)出現(xiàn)故障由于工人數(shù)量有限，就只能按照一定的次序進(jìn)行維修，維修好的設(shè)備馬上投入生產(chǎn)，維修工人再接著維修其它受損設(shè)備。在這種情形下，由于不同的的設(shè)備停工給企業(yè)造成的經(jīng)濟(jì)損失不同，維修所需要的時(shí)間也不同，此時(shí)設(shè)備的維修次序就顯得至關(guān)重要。因此尋求一種最優(yōu)的維修次序，把企業(yè)的經(jīng)濟(jì)損失降到最低就顯得相當(dāng)重要?，F(xiàn)考慮一個(gè)具體問題：某一生產(chǎn)企業(yè)同時(shí)有七臺(tái)設(shè)備出現(xiàn)故障，每臺(tái)設(shè)備維修所需要的時(shí)間和停工給企業(yè)造成的損失如下表所列：機(jī)器編號(hào)1234567維修所需時(shí)間（小時(shí)）58784813停工造成損失（萬(wàn)元/小時(shí)）0.61.81.20.80.81.71.0針對(duì)這一具體的設(shè)備維修問題解決一下問題：（1）.如果維修工人只有一名，試建立數(shù)學(xué)模型求解使總損失達(dá)到最小的設(shè)備維修次序；（2）.如果維修工人有兩名，每臺(tái)機(jī)器的維修只能由一個(gè)人單獨(dú)完成，試重新回答問題（1）；（2）.對(duì)該問題進(jìn)行簡(jiǎn)單推廣，如果同時(shí)有n臺(tái)設(shè)備需要維修，而每臺(tái)設(shè)備的維修時(shí)間和停工造成的損失都是已知的，并且在只有一名維修工人的情形下，建立使總損失達(dá)到最小的數(shù)學(xué)模型，并給出求解該問題的算法；三、問題的分析3.1我們首先依次對(duì)七臺(tái)受損設(shè)備進(jìn)行編號(hào)：1,2,3,4,5,6,7，在第一問中將工人甲用a表示，再將每臺(tái)儀器所對(duì)應(yīng)的維修時(shí)間和單位時(shí)間（每小時(shí)）內(nèi)的損失記為a(n).time和a(n).sh，當(dāng)工人數(shù)目增加到兩人時(shí)再引入b1,b2,b3,b4,b5,b6,b7;則其相應(yīng)的維修時(shí)間和單位時(shí)間內(nèi)的損失就為b(n).time和b(n).sh；3.2再依次讓a1,a2,a3,a4,a5,a6,a7不重復(fù)的取遍1,2,3,4,5,6,7七個(gè)數(shù)據(jù)，然后用計(jì)算機(jī)對(duì)這些數(shù)據(jù)進(jìn)行維修過程的模擬，用c語(yǔ)言編程來(lái)模擬維修過程，得出所有可能的維修次序以及對(duì)應(yīng)的損失，再通過比較得出最佳維修次序；3.3在第一問的基礎(chǔ)上，引入變量b，對(duì)算法進(jìn)行改進(jìn)，讓a和b分別在編號(hào)1,2,3,4,5,6,7,的設(shè)備中按照一定的規(guī)則取適合的設(shè)備進(jìn)行維修，用c語(yǔ)言進(jìn)行編程模擬兩人維修的過程，同樣得出所有種可能的維修次序，經(jīng)過比較即可求得最優(yōu)解；3.4對(duì)于第三問，當(dāng)用計(jì)算機(jī)解決此類節(jié)點(diǎn)數(shù)目過于龐大的問題時(shí)，根據(jù)排列論原理可知其組合數(shù)種數(shù)超出計(jì)算機(jī)的求解能力，即出現(xiàn)組合爆炸問題，因此對(duì)于此類人工智能問題，我們采取函數(shù)多層嵌套遞歸的方法，運(yùn)用較排列論更為先進(jìn)的搜索技術(shù)——深度優(yōu)先搜索，登山搜索，最小代價(jià)搜索來(lái)設(shè)計(jì)算法，以達(dá)到求解此類數(shù)據(jù)過于膨脹的問題，其算法設(shè)計(jì)我們會(huì)在下文中詳細(xì)展開；四、模型假設(shè)4.1假設(shè)在維修過程中，每個(gè)人能夠在規(guī)定時(shí)間內(nèi)獨(dú)立完成各自維修任務(wù)，并且不會(huì)發(fā)生其他影響維修進(jìn)度的意外事件；4.2假設(shè)工人在休息時(shí)，企業(yè)也停止生產(chǎn)，即在下班時(shí)間故障設(shè)備不會(huì)對(duì)企業(yè)的生產(chǎn)造成損失；4.3假設(shè)故障設(shè)備在維修好后馬上投入生產(chǎn)，其間不存在時(shí)間差；4.4假設(shè)故障設(shè)備在維修其間，其維修時(shí)間不會(huì)發(fā)生變動(dòng)；4.5假設(shè)故障設(shè)備在維修完成后，直到整個(gè)維修過程結(jié)束該設(shè)備不會(huì)再損壞；4.6假設(shè)第二種情況下，甲具有優(yōu)先選擇的權(quán)利，即當(dāng)甲乙二人同時(shí)面對(duì)同一臺(tái)故障設(shè)備時(shí)，該設(shè)備的維修工作交給甲來(lái)做；五、符號(hào)說明i：故障設(shè)備的編號(hào)，它可以取值1,2,3,4,5,6,7；ai:甲維修的故障設(shè)備的編號(hào)，從i中選??；ai.time:甲所維修的第i臺(tái)設(shè)備所需要的時(shí)間，已知；ai.sh:甲所維修的第i臺(tái)設(shè)備對(duì)企業(yè)造成的損失，已知；bi：乙所維修設(shè)備的編號(hào)，已知；bi.time：乙所維修的第i臺(tái)設(shè)備所需要的時(shí)間，已知；：表示函數(shù)fun（i,n），其功能是在n個(gè)數(shù)據(jù)中隨機(jī)不重復(fù)的選取i個(gè)；A:表示維修故障設(shè)備時(shí)可以參取的所有維修方案的種數(shù)；A7:表示當(dāng)有七臺(tái)設(shè)備出現(xiàn)故障時(shí)，所有可能的維修方案的種數(shù)；Zsh：?jiǎn)挝粫r(shí)間內(nèi)所有故障設(shè)備對(duì)企業(yè)的生產(chǎn)所造成的損時(shí)；Shn：采用第n種維修方案進(jìn)行維修，當(dāng)整個(gè)維修過程完成后所有故障設(shè)備給企業(yè)生產(chǎn)造成的損失；Bestsh:表示所有維修方案中的最小損失，也即維修損失的最優(yōu)解；Fc(n)：函數(shù)，其功能是實(shí)現(xiàn)求n個(gè)元素中的最小值；Cxn：采用第n種維修方案進(jìn)行維修，當(dāng)整個(gè)維修過程完成后，所采用的該種維修次序；Bestcx：所有維修方案之中的最佳維修次序，即維修次序的最優(yōu)解；Fcx:輸出函數(shù)，功能是實(shí)現(xiàn)將每一種維修方案所對(duì)應(yīng)的維修次序輸出；Si:一段臨時(shí)存儲(chǔ)空間，當(dāng)甲乙二人合作維修故障設(shè)備時(shí)，為其提供選擇的基礎(chǔ)；Bj:用來(lái)識(shí)別該設(shè)備是否已維修完成的一個(gè)標(biāo)志性屬性；Fnone:表示所有標(biāo)記bj為零的故障設(shè)備的損失之和；Shti：表示t時(shí)刻故障設(shè)備對(duì)生產(chǎn)造成的損失；六、模型的建立及求解6.1根據(jù)排隊(duì)論建立單個(gè)工人情況下維修七臺(tái)故障設(shè)備的模型6.1.1由題目第一問可知，先對(duì)七臺(tái)故障設(shè)備編號(hào)為1,2,3,4,5,6,7,用i來(lái)表示，相應(yīng)的對(duì)工人甲，其每次可以選擇其中任何一臺(tái)設(shè)備進(jìn)行維修，即ai=i（i=1,2,3,4,5,6,7）該過程描述為:a1=i(i=1,2,3,4,5,6,7,));即第一次時(shí)，甲可以從七臺(tái)故障設(shè)備中隨機(jī)選擇一種進(jìn)行維修；a2=i(i=);即在上一次選擇的基礎(chǔ)上，甲從剩余的六臺(tái)設(shè)備隨機(jī)選擇一臺(tái)進(jìn)行維修；a3=i(i=(……));在上一次選擇的基礎(chǔ)上，甲從剩余的五臺(tái)設(shè)備中隨機(jī)選擇一臺(tái)進(jìn)行維修；a4=i(i=(……));在上一次選擇的基礎(chǔ)上，甲從剩余的四臺(tái)設(shè)備中隨機(jī)選擇一臺(tái)進(jìn)行維修；a5=i(i=(……));在上一次選擇的基礎(chǔ)上，甲從剩余的三臺(tái)設(shè)備中隨機(jī)選擇一臺(tái)進(jìn)行維修；a6=i(i=(……));在上一次選擇的基礎(chǔ)上，甲從剩余的兩臺(tái)設(shè)備中隨機(jī)選擇一臺(tái)進(jìn)行維修；a7=i(i=(……));最后甲將取最后一臺(tái)故障設(shè)備進(jìn)行維修，維修完成則整個(gè)維修過程全部結(jié)束；根據(jù)組合論原理可知維修方案種數(shù)A與故障設(shè)備數(shù)目n之間存在如下關(guān)系：A==n所以當(dāng)n取值為7時(shí)：===7！=5040即，對(duì)于七臺(tái)故障設(shè)備，它共有5040種不同的維修方案，設(shè)備數(shù)目與維修方案之間的關(guān)系用下圖描述：6.1.2根據(jù)題意可知：如當(dāng)：ai（）=1,2,3,4,5,6,7時(shí)，每一個(gè)ai都對(duì)應(yīng)各自的維修時(shí)間ai.time和該設(shè)備在單位時(shí)間內(nèi)對(duì)企業(yè)成產(chǎn)造成的損失ai.sh;因?yàn)槠吲_(tái)設(shè)備在整個(gè)維修過程中所需要的總時(shí)間是固定不變的，則在這一種維修方案之下所有故障設(shè)備在單位時(shí)間內(nèi)對(duì)企業(yè)造成的損失也是確定不變的，我們把這個(gè)值設(shè)為zsh；則由題意知：Zsh=則當(dāng)選擇第n種方案進(jìn)行維修時(shí)，當(dāng)整個(gè)維修過程完成后所有故障設(shè)備對(duì)企業(yè)的生產(chǎn)造成的損失Shn為：Shn=同時(shí)當(dāng)選擇第n種方案進(jìn)行維修時(shí)，它所對(duì)應(yīng)的維修次序Cxn為Cxn=(a1,a2,a3,a4,a5,a6,a7)6.1.3上面已經(jīng)得到每一種方案所對(duì)應(yīng)的損失Shn值，現(xiàn)在所有A7種維修方案之中尋求對(duì)企業(yè)生產(chǎn)造成的損失最小的損失值Bestsh；Bestsh=Fc（（1=1,2,3,4……n））現(xiàn)在最小損時(shí)Bestsh值已經(jīng)找到，然后根據(jù)維修損失的最優(yōu)解Bestsh，即可得到其所對(duì)應(yīng)的最佳維修次序，最佳維修次序Bestce如下表示：Bestcx=Fcx（Bestsh）到此，一個(gè)工人面對(duì)七臺(tái)故障設(shè)備時(shí)的最佳維修方案成功得到。6.1.4圖像將在下面甲乙兩人同時(shí)維修此七臺(tái)設(shè)備的情況下對(duì)比展示！6.2根據(jù)排列論和循環(huán)檢索技術(shù)建立甲乙兩人同時(shí)維修七臺(tái)故障設(shè)備的模型5.2.1當(dāng)甲乙二人合作維修七臺(tái)故障設(shè)備時(shí)，分析所有種可能的維修方案我們?nèi)匀贿\(yùn)用5.1.1中所設(shè)變量a1,a2,a3,a4,a5.a6,a7;在引入另一個(gè)變量bi分別為b1,b2,b3,b4,b5,b6,b7.當(dāng)甲乙兩人同時(shí)面對(duì)七臺(tái)故障設(shè)備時(shí)，a1,a2,a3,a4,a5,a6,a7和b1,b2,b3,b4,b5,b6,b7,可分別從編號(hào)i=1234567的七臺(tái)故障設(shè)備中取適當(dāng)?shù)脑O(shè)備進(jìn)行維修，顯然ai與bi共同取夠i=1234567中的所有值，且ai不等于bi；則根據(jù)第一問中我們已經(jīng)求得的當(dāng)七種設(shè)備故障時(shí)其不同的維修次序有A7=7！=5040種方法，那么我們是否也可以再次以這5040種不同的維修次序作為基礎(chǔ)，讓ai與bi分別在每種不同的維修次序中再去取值，即假設(shè)現(xiàn)有一種維修次序?yàn)椋篿1=1,i2=2,i3=3,i4=4,i5=5,i6=6,i7=7;則我們可以采用“頭尾逼近法則”讓a1=i1,b1=i7;然后通過比較故障設(shè)備a1即i1所對(duì)應(yīng)的維修時(shí)間a1.time和故障設(shè)備b1即i7所對(duì)應(yīng)的維修時(shí)間b1.time來(lái)確定那臺(tái)設(shè)備先維修完成，這樣我們就可以讓ai和bi實(shí)現(xiàn)都從i中選擇不同的數(shù)據(jù)，所以采用這種以A7種不同的維修次序?yàn)榛A(chǔ)的方法是科學(xué)的，也是合理的；所以我們可以仍然將第一問中的部分結(jié)果用到這里來(lái)；6.2.2首先我們開辟一塊臨時(shí)的存儲(chǔ)空間Si，來(lái)存儲(chǔ)七臺(tái)故障設(shè)備的任意一種排列方式，也即用這樣一段臨時(shí)存儲(chǔ)空間來(lái)建立一個(gè)隊(duì)列基礎(chǔ)來(lái)供甲乙二人選擇。然后再取兩段永久的存儲(chǔ)空間ai和bi來(lái)分別存儲(chǔ)甲和乙各自維修的設(shè)備設(shè)備以下幾組屬性：ai.time表示甲所維修的該臺(tái)故障設(shè)備所花費(fèi)的時(shí)間；ai.sh表示甲所維修的該臺(tái)設(shè)備對(duì)企業(yè)生產(chǎn)造成的損失；bi.time表示乙所維修的該臺(tái)故障設(shè)備所花費(fèi)的時(shí)間；bi.sh表示乙所維修的該臺(tái)設(shè)備對(duì)企業(yè)生產(chǎn)造成的損失；為了便于求解該種維修次序之下的總損失，我們?yōu)槊颗_(tái)設(shè)備添加另一個(gè)屬性bj，即ai.bj和bi.bj,用來(lái)識(shí)別該設(shè)備是否已維修完成，便于甲乙兩人進(jìn)行下一次的選擇，在使用之初可將ai.bj和bi.bj都置零，等到此故障設(shè)備維修完成后再將其置為一。另外對(duì)于ai和bi，因?yàn)槠淙≈禂?shù)目具有很大的被動(dòng)性，所以維修之初我們先將ai很bi都置為零，當(dāng)它們有值可取時(shí)，再用ai的真值去替換另即可，當(dāng)維修結(jié)束后只輸出ai和bi不為零的值即為甲或乙所維修的故障設(shè)備的最佳維修次序；又根據(jù)假設(shè)條件當(dāng)甲乙二人同時(shí)面對(duì)一臺(tái)故障設(shè)備時(shí)，甲具有優(yōu)先選擇權(quán)，則維修之初將ai和bi均置零,然后令：甲：a1=s1,乙：b1=s7;令a=ai.time,b=bi.time然后比較a1.time和b1.time執(zhí)行如下算法：當(dāng)ai.time大于bi.time時(shí)，就說明乙所選故障設(shè)備所需維修時(shí)間較短，那么可以將此設(shè)備標(biāo)記屬性bi.bj置為一，則在這段時(shí)間內(nèi)故障設(shè)備對(duì)生產(chǎn)造成的損失的計(jì)算方法如下：Sht1=bi.time*bi.sh+bi.time*Fnone該臺(tái)設(shè)備維修結(jié)束后乙立刻得選取下一臺(tái)設(shè)備，此時(shí)b2取值為s6；當(dāng)a.time小于b.time時(shí)，就說明甲所選的故障設(shè)備所需要的維修時(shí)間較短，那么我們可以將此設(shè)備標(biāo)記ai.bj置為一，則在這段時(shí)間之內(nèi)故障設(shè)備對(duì)生產(chǎn)造成的損失為：Sht2=ai.time*ai.sh+ai.time*Fnone該臺(tái)設(shè)備維修結(jié)束后甲立刻得選取下一臺(tái)設(shè)備，此時(shí)a2取值為s2；而當(dāng)ai.time等于bi.time時(shí)，就表示甲乙此時(shí)所選故障設(shè)備維修完成所需時(shí)間相同，那么此時(shí)可將ai.bj和bi.bj均值為一，而在這段時(shí)間內(nèi)故障設(shè)備對(duì)生產(chǎn)造成的損失為：Sht3=ai.time*(ai.sh+bi.sh)+ai.time*Fnone甲乙所選故障設(shè)備維修結(jié)束后立刻得選取下一臺(tái)設(shè)備，此時(shí)a3取值為s3，b3取值為s5；然后讓ai和bi循環(huán)將所有故障設(shè)備的序號(hào)都取完，此時(shí)的Zsh就為：Zsh=而相應(yīng)的甲和乙所維修的故障設(shè)備各自的維修次序也就得到確定；到此我們就解決了一種排序之下的總損失，也得到了甲乙二人各自的維修次序，而對(duì)于算法設(shè)計(jì)中的一些瑣碎問題，在此不再贅述。6.2.3上面已經(jīng)得到所有A7種不同排列方式的維修次序所對(duì)應(yīng)的損失Zshn值，現(xiàn)，在所有A7種維修方案之中尋求對(duì)企業(yè)生產(chǎn)造成的損失最小的損失值Bestsh；Bestsh=Fc（（i=1,2,3,4……n））現(xiàn)在最小損時(shí)Bestsh值已經(jīng)找到，然后根據(jù)維修損失的最優(yōu)解Bestsh，即可得到其所對(duì)應(yīng)的最佳維修次序，最佳維修次序Bestce如下表示：a.bestcx=Fcxa（Bestsh）b.bestcx=Fcxb（Bestsh）到此甲乙兩人合作維修故障設(shè)備的情況下的最優(yōu)解已找到。6.2.4在第一第二種情況下以求得7臺(tái)故障設(shè)備所有可能的維修方案，由于一人維修和兩人合作維修所采用的基礎(chǔ)是一樣的，即在同一種維修方案之下計(jì)算機(jī)對(duì)他們的處理方式是相同的，因此我們可以對(duì)每種維修方案進(jìn)行編號(hào)，而每種方案則各對(duì)應(yīng)兩個(gè)故障設(shè)備對(duì)生產(chǎn)造成的損失值，其一是一個(gè)人單獨(dú)完成時(shí)的，而另一個(gè)值則是甲乙兩人合作完成時(shí)的，我們用Matlab將這種對(duì)應(yīng)關(guān)系對(duì)比展示在同一張圖上，來(lái)描述兩種情況的關(guān)系；對(duì)應(yīng)關(guān)系展示如下：6.3在第一問的基礎(chǔ)上，將故障設(shè)備數(shù)量擴(kuò)展到n，求解一個(gè)工人維修n臺(tái)故障設(shè)備的最優(yōu)解6.3.1對(duì)問題進(jìn)行分析，建立多分枝多層次的樹型結(jié)構(gòu)模型眾所周知，根據(jù)組合數(shù)學(xué)定理，N個(gè)對(duì)象的排列總數(shù)等于N?。∟的階乘）。３3個(gè)對(duì)象的排列種數(shù)是３3?。ǎ?），４4對(duì)象是４4?。ǎ保?4），5５對(duì)象是5５?。?20１２０），6６對(duì)象是6６?。?20７２０），7７對(duì)象是7７?。?040５０４０）。以此類推，１０００對(duì)象的排列種數(shù)是天文數(shù)字。）。以此類推，100對(duì)象的排列種數(shù)已是天文數(shù)字。下圖圖中的趨勢(shì)形象的表示了人工智能研究者稱為組合爆炸的現(xiàn)象。對(duì)象總數(shù)逼近數(shù)百時(shí)，很快就不可能再研究（甚至枚舉）各種組合了，同時(shí)，原先總是正確的窮盡搜索法也因占用的計(jì)算時(shí)間和資源太多而變得不再實(shí)用。（對(duì)象N和排列數(shù)N!之間的關(guān)系如圖所示：）為此我們對(duì)組合數(shù)做以下轉(zhuǎn)化：實(shí)用由組合數(shù)學(xué)定理 =*，=**，……從而當(dāng)n為偶數(shù)時(shí) =***……**當(dāng)n為奇數(shù)時(shí) =***……**這就是說我么可以將加以轉(zhuǎn)化將其建成一棵多分枝多層次的樹型結(jié)構(gòu)模型，最終成為我們?cè)谀Ｐ鸵恢衅吲_(tái)故障設(shè)備的排列問題，運(yùn)用我們已經(jīng)很成熟的解決方案解決即可，然后應(yīng)用深度優(yōu)先搜索或者其他搜索技術(shù)進(jìn)行搜索即可解決人工智能組合爆炸問題；6.3.2搜索算法的比較和選擇◆深度優(yōu)先搜索 ◆登山搜索 ◆寬度優(yōu)先搜索 ◆最小代價(jià)搜索。下面逐一進(jìn)行分析說明：深度優(yōu)先搜索:盡量沿一條路徑向深處探測(cè)，在失敗之前不管其他路徑上的結(jié)點(diǎn)。寬度優(yōu)先搜索:寬度優(yōu)先搜索先檢查一層的所有結(jié)點(diǎn)后再查下層結(jié)點(diǎn)。登山搜索:登山算法屬于啟發(fā)式搜索范疇，它把顯得離目的地最近（離當(dāng)前地最遠(yuǎn)）的結(jié)點(diǎn)選作下步點(diǎn)。這種算法得名于把搜索局勢(shì)比喻成登山者黑夜中在半山腰迷路。假設(shè)登山營(yíng)地在山頂時(shí)，即使在黑夜中，登山者也知道向上判斷呢個(gè)是正確的方向。最小代價(jià)搜索:也屬于啟發(fā)式搜索范疇，這種策略類似于足登冰鞋站在大斜坡中間的情況，滑旱冰者明顯感到向下滑行比向上滑行輕松很多。綜上所述，平均情況下，啟發(fā)式搜索趨于比盲目搜索有更好的性能。然而，因?yàn)槿狈Υ_認(rèn)下一結(jié)點(diǎn)可能在路徑上的信息，有時(shí)無(wú)法實(shí)用啟發(fā)式搜索，也就只能運(yùn)用非啟發(fā)式搜索方法了。相比之下，登山法產(chǎn)生的解路徑上結(jié)點(diǎn)一般更少，最小代價(jià)法產(chǎn)生的解路徑一般開銷更小。然而，需要接近最優(yōu)解又不能承擔(dān)窮盡搜索的開銷時(shí)，一個(gè)有效的辦法就是逐次使用上述四種方法，取逐解中的最優(yōu)解。因?yàn)閹追N搜索的原理都有實(shí)質(zhì)的差別，在各種方法產(chǎn)生的解解中選優(yōu)是合理的。由組合數(shù)學(xué)定理 =*，=**，……從而當(dāng)n為偶數(shù)時(shí) =***……**當(dāng)n為奇數(shù)時(shí) =***……***6.3.2樹形結(jié)構(gòu)模型算法設(shè)計(jì)1首先定義一個(gè)長(zhǎng)度為n的全局結(jié)構(gòu)體數(shù)組變量s[n](n為常量)，用來(lái)存放n個(gè)對(duì)象的所有詳細(xì)信息，再次給其同樣添加一個(gè)標(biāo)記性的屬性s[i].bj,將其全部置零，作為初始化；2.根據(jù)=**……*的轉(zhuǎn)化關(guān)系，我們可以將，，，……，放在在不同的函數(shù)體內(nèi)，采用遞歸算法，將算法中心放在最深的那個(gè)函數(shù)，即實(shí)現(xiàn)功能的函數(shù)內(nèi)部，再設(shè)一個(gè)全局性結(jié)構(gòu)體變量，用來(lái)在是存儲(chǔ)一種a1，a2,a3,a4a5······an的取值，在最深層函數(shù)內(nèi)部計(jì)算總損失，并將維修次序和總損失存儲(chǔ)下來(lái)，可以將它寫入文件，這樣就不會(huì)發(fā)生數(shù)組長(zhǎng)度超過計(jì)算機(jī)底線的事情，并數(shù)據(jù)進(jìn)行編號(hào)以便求出最優(yōu)解；3現(xiàn)在描述最外層函數(shù)的算法設(shè)計(jì)：建立數(shù)組an[n]和a(n-1)[n-1](n為題目中已給出的對(duì)象總數(shù))，實(shí)現(xiàn)時(shí)用兩層循環(huán)嵌套，當(dāng)a1和a2分別取到s[n]中的兩個(gè)數(shù)據(jù)時(shí)，將這兩個(gè)數(shù)據(jù)所對(duì)應(yīng)的標(biāo)記改為一，并將這兩個(gè)對(duì)象的序號(hào)個(gè)拷貝一份到an[0]和a(n-1)[0]種，作為一種記憶形式；做完這一步之后調(diào)用下一個(gè)函數(shù)來(lái)實(shí)現(xiàn)，這個(gè)函數(shù)內(nèi)部所有結(jié)構(gòu)應(yīng)同完全相同，當(dāng)函數(shù)由最深一層返回后還需再做一步，即重新將s[i]對(duì)應(yīng)的所有標(biāo)記都再次初始化，下一次開始給a1,a2取值時(shí)首先比較an[i]和a(n-1)[i]中數(shù)據(jù)，確保不會(huì)發(fā)生重復(fù)；4函數(shù)全部運(yùn)行結(jié)束，在此不再用c語(yǔ)言來(lái)實(shí)現(xiàn)算法；6.3.3下面將此算法的簡(jiǎn)易流程描述如下七、設(shè)計(jì)規(guī)范合理性的討論7.1合理的方面：（1）該設(shè)計(jì)規(guī)范在分析對(duì)象有限時(shí)(<100時(shí))利用窮盡搜索方法，由于采用比較成熟和可靠的排列論為基礎(chǔ)，其窮舉作為主要思想，因此在解決問題時(shí)得心應(yīng)手，安全可靠；而當(dāng)分析對(duì)象很大時(shí)，由于會(huì)發(fā)生“組合爆炸”問題，所以使用函數(shù)嵌套遞歸循環(huán)把問題分塊分層次解決，每塊求解出分塊自身中的最優(yōu)解，然后對(duì)這些最優(yōu)解進(jìn)行排序從而找出最小損失時(shí)的維修次序。在分塊求解時(shí)又可根據(jù)條件采用登山搜索、最小代價(jià)搜索等方法，精簡(jiǎn)了程序，減少了計(jì)算機(jī)的工作量，因此是完全合理的。該模型綜合運(yùn)用多種方法對(duì)問題進(jìn)行求解，其中窮舉法簡(jiǎn)單易懂，數(shù)據(jù)量較小時(shí)用計(jì)算機(jī)編程求解，僅僅幾秒鐘就可以完成；而概率、圖論、組合數(shù)學(xué)等方面理論性較強(qiáng)，易于為大家所接受。而當(dāng)運(yùn)用到實(shí)際問題的解決時(shí)，其結(jié)果出錯(cuò)可能性小，結(jié)果精確可靠，可以推廣；八、結(jié)果和誤差分析本文根據(jù)排列數(shù)學(xué)理論建立的模型，得到了單人維修7臺(tái)設(shè)備時(shí)維修的次序：2563147和對(duì)應(yīng)的最小損失199.9000萬(wàn)元，得到了雙人維修7臺(tái)設(shè)備時(shí)，甲工人的維修次序5614和乙工人的維修次序237以及最小損失117.3000萬(wàn)元。顯然此結(jié)果可把工廠的損失降到最小。九、模型推廣此模型建立于一個(gè)工人維修七臺(tái)設(shè)備是的情況，只要在計(jì)算機(jī)計(jì)算能力范圍內(nèi)，就可以將其擴(kuò)展到多臺(tái)設(shè)備的情況。同樣，有方案二，我們實(shí)現(xiàn)了兩個(gè)工人維修七臺(tái)設(shè)備的最優(yōu)解的求解，那么我我們就可以將它擴(kuò)展到多個(gè)工人多臺(tái)設(shè)備的情況下，因此此模型具有很強(qiáng)的適用性，和可利用性，擴(kuò)展空間大。（3）題目考慮的只是已知每臺(tái)設(shè)備維修所需的時(shí)間，及每臺(tái)設(shè)備在損壞時(shí)每小時(shí)對(duì)企業(yè)造成的經(jīng)濟(jì)損失時(shí)求最優(yōu)解的情況，但由于模型是以排列論及窮舉法為基礎(chǔ)建立的，因此可以將它擴(kuò)展到其他兩個(gè)甚至多個(gè)離散型變量的實(shí)際問題中去，由此可見此模型具有很廣泛的用途。十、模型的優(yōu)缺點(diǎn)該模型是運(yùn)用組合數(shù)學(xué)定理和登山搜索等搜索方法以及窮舉法經(jīng)過嚴(yán)格的論證建立起來(lái)的。此模型的結(jié)果很精確，保證了多臺(tái)設(shè)備同時(shí)故障時(shí)維修損失的最優(yōu)化，能很好地符合題目的要求，也適合于其它主要應(yīng)用排列論和窮舉法求解的優(yōu)化問題，比如如何給球隊(duì)排名次等，因此有很強(qiáng)的適應(yīng)性和實(shí)用性。但因?yàn)榇四Ｐ椭饕⒃谟?jì)算機(jī)計(jì)算之上，所以當(dāng)數(shù)據(jù)對(duì)象很大時(shí)，會(huì)受到計(jì)算機(jī)本身的限制而無(wú)法得到我們所需要的答案，因此還是有它的局限性存在。十一、參考文獻(xiàn)[1]譚浩強(qiáng).C程序設(shè)計(jì).清華大學(xué)出版社.1991,7(306~320).[2]雷功炎.數(shù)學(xué)模型講義.北京大學(xué)出版社.1999,4(161~185)[3]李桂成.計(jì)算方法.電子工業(yè)出版社.2009,7(218~267).[4]美HerbertSchildt著.王子恢,戴健鵬譯.最新C語(yǔ)言精華(第三版)電子工業(yè)出版社.1997,2(423~458).十二、附錄部分附件1第一問程序代碼：#defineN7;#include<stdio.h>#include<math.h>structs//機(jī)器類別{ intxh;//機(jī)器序號(hào) double time;//維修時(shí)間 doublesh;//損失}s[7];structcx//不同的維修次序{ inta[8];}cx[10000];main(){ inti,j=1,k,bestcx; inta1,a2,a3,a4,a5,a6,a7; doublesum[10000],jc1=1,jc2,zsh=0.0;//sum表示不同次序造成的損失 doublemin; FILE*fp; if((fp=fopen("E://a.txt","w"))==NULL) { printf("文件打開失敗！\n"); return0; } printf("pleaseenterthedate!\n"); for(i=1;i<=7;i++) { scanf("%lf%lf",&s[i].time,&s[i].sh); } for(k=1;k<=7;k++) { zsh+=s[k].sh; } for(i=1;i<=7;i++) jc1*=i;//求總共有多少種排列方式 a1=2;a2=5;a3=6;a4=3;a5=1;a6=4;a7=7; for(a1=1;a1<=7;a1++) for(a2=1;a2<=7;a2++) for(a3=1;a3<=7;a3++) for(a4=1;a4<=7;a4++) for(a5=1;a5<=7;a5++) for(a6=1;a6<=7;a6++) for(a7=1;a7<=7;a7++) { if(a1==a2||a1==a3||a1==a4||a1==a5||a1==a6||a1==a7)continue; if(a2==a3||a2==a4||a2==a5||a2==a6||a2==a7)continue; if(a3==a4||a3==a5||a3==a6||a3==a7)continue；if(a4==a5||a4==a6||a4==a7)continue;if(a5==a6||a5==a7)continue;if(a6==a7)continue;sum[j]=s[a1].time*zsh+s[a2].time*(zsh-s[a1].sh)+s[a3].time*(zsh-s[a1].sh-s[a2].sh)+s[a4].time*(zsh-s[a1].sh-s[a2].sh-s[a3].sh)+s[a5].time*(s[a5].sh+s[a6].sh+s[a7].sh)+s[a6].time*(s[a6].sh+s[a7].sh)+s[a7].time*s[a7].sh;cx[j].a[1]=a1;cx[j].a[2]=a2;cx[j].a[3]=a3;cx[j].a[4]=a4;cx[j].a[5]=a5;cx[j].a[6]=a6;cx[j].a[7]=a7;fprintf(fp,"%.2lf\n",sum[j]);for(i=1;i<=7;i++)fprintf(fp,"%d",cx[j].a[i]);fprintf(fp,"\n");j++; }jc2=j-1;// for(j=1;j<jc2;j+=100)//fprintf(fp,"%.2lf\n",sum[j]);min=sum[1];for(i=1;i<=jc2;i++){ if(min>sum[i]) min=sum[i]; }for(j=1;j<=jc2;j++)if(min==sum[j])break; bestcx=j;//尋找最佳維修次序的存儲(chǔ)位置 printf("最小損失：%lf\n",min); printf("最佳維修次序："); for(i=1;i<=7;i++) printf("%d",cx[bestcx].a[i]); printf("\n"); fclose(fp); return0; }//50.681.871.280.840.891.7131附件二第二問程序源代碼：#defineN7#include<stdio.h>typedefstructdate//機(jī)器信息{ intbj; intxh; doubletime; doublesh; };typedefstructwxcx//維修次序{intcx1[N];//假的維修次序 intcx2[N];//乙的維修次序 doublesum;};fun(structdate*s,structwxcx*p,intn){inti=1,j=7,w=1,q=1,k; doubleb,sum=0,item=0,t,tz=0; doublea; for(intm=0;m<N;m++)//將空出來(lái)零，以便輸出序號(hào)的序號(hào)位置 { p[n].cx1[m]=0; p[n].cx2[m]=0; } a=s[i].time; b=s[j].time; p[n].cx1[w]=s[i].xh; p[n].cx2[q]=s[j].xh; while(i<=j) { if(a>b) { if(i==j) { sum+=a*s[i].sh; p[n].cx2[q]=0; p[n].sum=sum; return0;} s[j].bj=1; sum+=b*s[j].sh; t=b; a=a-b; b=s[--j].time;p[n].cx2[++q]=s[j].xh; if(i==j) b=0; gotoloc; } elseif(a<b) { if(i==j) { sum+=b*s[j].sh; p[n].cx1[w]=0; p[n].sum=sum; return0;} s[i].bj=1; sum+=a*s[i].sh; t=a; b=b-a; a=s[++i].time; p[n].cx1[++w]=s[i].xh; if(i==j) a=0; gotoloc; } else { if(i==j) { sum+=a*s[i].sh;//假設(shè)當(dāng)甲乙兩人同時(shí)面對(duì)同一機(jī)器時(shí)，由甲來(lái)完成 p[n].cx2[q]=0; p[n].sum=sum; return0; } s[i].bj=1; s[j].bj=1; t=a; sum+=t*(s[i].sh+s[j].sh); a=s[++i].time; b=s[--j].time; p[n].cx1[++w]=s[i].xh; p[n].cx2[++q]=s[j].xh; gotoloc; }loc: item=0; for(k=1;k<=7;k++) { if(s[k].bj==0) item+=s[k].sh; } sum+=t*item; tz+=t; } p[n].sum=sum; return0;}main(){ inti,k,n=1,locate; doublemin; inta1,a2,a3,a4,a5,a6,a7; dates[8],s1[8]; wxcxp[10000]; FILE*fp; //voidfun(date*,wxcx*,int); if((fp=fopen("E://b.txt","w"))==NULL) { return0; } printf("pleaseenterthedate!\n"); for(i=1;i<=7;i++) { scanf("%lf%lf",&s1[i].time,&s1[i].sh); fprint