一種求解一維裝箱問題的擬人算法畢業(yè)論文

《一種求解一維裝箱問題的擬人算法畢業(yè)論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、擬建中的阜陽市中國(guó)XXXX國(guó)際服裝城依托中國(guó)XX國(guó)際服裝城，擬建成為皖西北地區(qū)規(guī)格最高、規(guī)模最大、商務(wù)及功能最優(yōu)的現(xiàn)代化、國(guó)際化服裝專業(yè)市場(chǎng)，建設(shè)規(guī)模占地約128畝，建筑面積約25萬平方米，項(xiàng)目總投資約5億元人民幣。經(jīng)過1--2年的開發(fā)建設(shè)，能達(dá)到正常運(yùn)營(yíng)期的中國(guó)XX.XX國(guó)際服裝城將吸納全國(guó)和世界各地的經(jīng)銷商、代理商企業(yè)物流總部等500—1000家，預(yù)計(jì)年交易額實(shí)現(xiàn)68億元人民幣，每年實(shí)現(xiàn)稅收8000—10000萬元人民幣，每年實(shí)現(xiàn)利潤(rùn)1.68億元人民幣，實(shí)現(xiàn)就業(yè)和創(chuàng)業(yè)人員約2萬以上。摘要一維裝箱問題來源于人們

2、的長(zhǎng)期以來的生產(chǎn)實(shí)踐，是一種組合優(yōu)化問題。給定有窮個(gè)物體，每個(gè)物體的重量是已知的正實(shí)數(shù)。給定足夠多個(gè)空箱子，問題是要在滿足兩個(gè)約束條件的前提下，將所有物體放到箱子中去，使得所用箱子的個(gè)數(shù)盡可能地少。兩個(gè)約束條件是：第一，每個(gè)物體均保持完整，恰好放到一個(gè)箱子中去。不能將物體分割成幾塊。第二，每個(gè)箱子中所放的物體的重量之和均不能超過一個(gè)相同的上限，這個(gè)上限是一個(gè)已知的正實(shí)數(shù)。一維裝箱問題具有很高的理論價(jià)值和實(shí)際價(jià)值。一方面，學(xué)者已經(jīng)證明一維裝箱問題是一個(gè)NP難度問題，因此一維裝箱問題具有很高的理論價(jià)值。另一方面，一維

3、裝箱問題出現(xiàn)在實(shí)際生產(chǎn)的一些領(lǐng)域，因此也具有很高的實(shí)際價(jià)值。迄今為止，國(guó)內(nèi)外學(xué)者提出了許多用來求解一維裝箱問題的嚴(yán)格算法和近似算法。一方面，嚴(yán)格的最優(yōu)算法所花時(shí)間太長(zhǎng)，實(shí)際部門無法忍受。另一方面，近似算法由于可能快速地生成最優(yōu)解或者接近最優(yōu)解而為實(shí)際生產(chǎn)部門所廣泛采用。人類把物體往容器中裝，已有幾千年以上的經(jīng)驗(yàn)。這些生活經(jīng)驗(yàn)可引導(dǎo)出高效率的算法。本文提出了一種擬人算法。算法由三個(gè)部分組成。第一部分是降序最佳適合算法，用于生成初始解。第二部分是鄰域搜索算法。給定一個(gè)解，用鄰域搜索算法可以通過迭代改進(jìn)這個(gè)解。本文的鄰

4、域定義的思想來源于“天之道損有余而補(bǔ)不足”。第三部分是跳坑策略。跳坑策略用于跳出局部最優(yōu)解，將搜索引向有希望的區(qū)域，從而提高算法的效率。跳坑策略的思想來源是“三十六計(jì)走為上”。本文的程序計(jì)算了一組共17個(gè)國(guó)際公認(rèn)的問題實(shí)例。這組問題實(shí)例分為兩類。第一類為8個(gè)問題實(shí)例，目前尚未確定其客觀最優(yōu)解。第二類為9個(gè)問題實(shí)例，目前已經(jīng)確定了其客觀最優(yōu)解。擬人算法對(duì)第一類問題實(shí)例中的6個(gè)問題實(shí)例找出了與當(dāng)前已知最好解質(zhì)量相同的解。擬人算法還證明了TEST0068這個(gè)問題實(shí)例的目前已知最好解正是客觀最優(yōu)解。擬人算法快速地找出了第

5、二類問題實(shí)例中全部9個(gè)問題實(shí)例的客觀最優(yōu)解。計(jì)算結(jié)果表明，擬人算法是一種有效的求解一維裝箱問題的近似算法。關(guān)鍵詞：NP難度；擬人；鄰域搜索；跳坑；裝箱經(jīng)濟(jì)增長(zhǎng)：在優(yōu)化結(jié)構(gòu)、提高效益和降低消耗的基礎(chǔ)上，“十一五”期市GDP年均增長(zhǎng)12%以上（現(xiàn)14%以上），2010年達(dá)到650億元以上，人均GDP力爭(zhēng)1000美元；財(cái)政收入達(dá)到80億元；規(guī)模以上工業(yè)銷售達(dá)到550億以上；全社會(huì)固定資產(chǎn)投資年均長(zhǎng)20%，五年累計(jì)1000億元；社會(huì)消費(fèi)品銷售額260億元，年均增長(zhǎng)20%，外貿(mào)進(jìn)口總額2.5億美元，年均增長(zhǎng)15%；五年累計(jì)

6、招商引資突破500億元，力爭(zhēng)達(dá)到600億元III擬建中的阜陽市中國(guó)XXXX國(guó)際服裝城依托中國(guó)XX國(guó)際服裝城，擬建成為皖西北地區(qū)規(guī)格最高、規(guī)模最大、商務(wù)及功能最優(yōu)的現(xiàn)代化、國(guó)際化服裝專業(yè)市場(chǎng)，建設(shè)規(guī)模占地約128畝，建筑面積約25萬平方米，項(xiàng)目總投資約5億元人民幣。經(jīng)過1--2年的開發(fā)建設(shè)，能達(dá)到正常運(yùn)營(yíng)期的中國(guó)XX.XX國(guó)際服裝城將吸納全國(guó)和世界各地的經(jīng)銷商、代理商企業(yè)物流總部等500—1000家，預(yù)計(jì)年交易額實(shí)現(xiàn)68億元人民幣，每年實(shí)現(xiàn)稅收8000—10000萬元人民幣，每年實(shí)現(xiàn)利潤(rùn)1.68億元人民幣，實(shí)現(xiàn)就業(yè)

7、和創(chuàng)業(yè)人員約2萬以上。AbstractTheonedimensionalbinpackingproblem,whichisafamouscombinatorialoptimizationproblem,comesfromlongtermpracticeofhumanbeing.Thedefinitionoftheonedimensionalbinpackingproblemdiscussedinthispaperisasfollowing.Givenitemsandenoughidenticalbins,thew

8、eightofeachitemisaknownpositiverealnumber.Thecapacitiesofallbinsareequal.Theproblemistopackallitemsintothebinswiththeobjectiveofminimizingthenumberofoccupiedbins,subjecttotwofollowingcons