本文關(guān)鍵詞：具有不同價格的裝箱問題

  更多相關(guān)文章： 不同價格的箱子 (漸近)近似算法 復(fù)雜性 MATLAB程序

【摘要】：裝箱問題是一種經(jīng)典的組合優(yōu)化問題。一維裝箱問題是：給定n個尺寸在(0,1]之間的物品序列L,提供容量為1的箱子若干,把L中的物品裝入這些箱子中,要求每個箱子所裝的物品尺寸之和不超過1,目標(biāo)是使得所使用箱子個數(shù)達(dá)到最少。 具有不同價格的裝箱問題是一維裝箱問題的一種推廣形式,具體描述如下：給定n個尺寸在(0,1]之間的物品序列L,提供k種不同容量和不同價格的箱子,每類箱子若干,箱子的容量在(0,1]之間,把L中的物品裝入這些箱子中,要求每個箱子所裝物品尺寸之和不超過箱子的容量,目標(biāo)是使得所使用箱子價格總和達(dá)到最小。 本論文利用FFD算法思想,設(shè)計了一個漸近近似算法來解決具有不同價格的裝箱問題,得出的結(jié)論是：在一般情況下,該算法的漸近近似值為2；在兩種特殊情況下,該算法的漸近近似值都為3/2,并且,算法復(fù)雜性為O(nlogn),最后對這個算法進(jìn)行了MATLAB編程,并利用該程序?qū)崿F(xiàn)算例。
【關(guān)鍵詞】：不同價格的箱子 (漸近)近似算法 復(fù)雜性 MATLAB程序
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157
【目錄】：

• 摘要3-4
• Abstract4-7
• 第一章 引言7-12
• 1.1 理論背景7-9
• 1.2 相關(guān)術(shù)語9-10
• 1.3 主要結(jié)果10-11
• 1.4 論文結(jié)構(gòu)11-12
• 第二章 預(yù)備知識12-22
• 2.1 組合最優(yōu)化理論12-14
• 2.2 近似算法理論14-16
• 2.3 一維裝箱問題及其算法16-18
• 2.4 具有不同容量的裝箱問題及其算法18-22
• 第三章 具有不同價格的裝箱問題及其算法22-26
• 3.1 問題描述22
• 3.2 解決具有不同價格的裝箱問題的算法22-26
• 第四章 FFDL算法及正確性證明26-37
• 4.1 FFDL算法26-27
• 4.2 主要結(jié)果及證明27-34
• 4.3 FFDL算法與IFFD算法和FFC算法的比較34
• 4.4 算例34-37
• 結(jié)論37-38
• 附錄38-41
• 參考文獻(xiàn)41-43
• 致謝43

【共引文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 梁伍七;矩陣鏈乘積最優(yōu)計算次序問題的算法及其復(fù)雜性分析[J];安徽廣播電視大學(xué)學(xué)報;2003年02期

2 毛影;黃明和;徐斌;;對啟發(fā)式算法實現(xiàn)圖著色的優(yōu)化[J];江西師范大學(xué)學(xué)報(自然科學(xué)版);2009年06期

3 徐振明,劉莉;繪制PERT網(wǎng)絡(luò)圖自動布點算法的研究[J];成都信息工程學(xué)院學(xué)報;2005年01期

4 曹志光;華容道的廣度優(yōu)先搜索求解——散列查找和啟發(fā)式搜索的應(yīng)用[J];電力學(xué)報;2005年01期

5 楊元生,張成學(xué);在有向圖中尋找哈密頓回路的快速回溯法[J];大連理工大學(xué)學(xué)報;1989年02期

6 潘大志;張世祿;;一個實用排序算法的構(gòu)造與實現(xiàn)[J];電腦學(xué)習(xí);2007年02期

7 司慶福;程書偉;;表達(dá)式求值算法比較[J];電腦學(xué)習(xí);2010年01期

8 張代遠(yuǎn);快速和高精度的前饋網(wǎng)絡(luò)學(xué)習(xí)算法[J];電路與系統(tǒng)學(xué)報;2000年02期

9 張哲;高健;;任意長整數(shù)無誤差運(yùn)算的研究與實現(xiàn)[J];電腦編程技巧與維護(hù);2011年04期

10 陳寶平;;任意類型的分類數(shù)據(jù)的快速排序[J];電腦與信息技術(shù);2011年05期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 蘇運(yùn)霖;;并行編譯中的區(qū)域調(diào)度問題[A];廣西計算機(jī)學(xué)會2004年學(xué)術(shù)年會論文集[C];2004年

2 徐平;李愛平;繆嘉嘉;吳泉源;;大規(guī)模人貨混裝問題的一種啟發(fā)遺傳算法實現(xiàn)[A];第二十二屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2005年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 戴宏欽;球體隨機(jī)堆積及其堆積結(jié)構(gòu)的研究[D];蘇州大學(xué);2011年

2 徐東平;實時動態(tài)交互視景仿真[D];武漢理工大學(xué);2002年

3 劉曉建;大規(guī)模分布式仿真信息傳輸延遲技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2003年

4 麥永浩;數(shù)據(jù)倉庫和數(shù)據(jù)挖掘方法研究及其在公安信息建設(shè)中的應(yīng)用[D];華東理工大學(xué);2000年

5 王意潔;面向?qū)ο髷?shù)據(jù)庫的并行查詢處理與事務(wù)管理[D];國防科技大學(xué);1998年

6 南春麗;信號交叉口多目標(biāo)交通組織優(yōu)化模型及面向智能體仿真[D];長安大學(xué);2007年

7 李小林;平行機(jī)環(huán)境下批處理機(jī)調(diào)度問題研究[D];中國科學(xué)技術(shù)大學(xué);2012年

8 高勝;對稱密碼中關(guān)鍵組件的設(shè)計與分析[D];西安電子科技大學(xué);2012年

9 王星;隨機(jī)、容錯和厭惡型設(shè)施選址的算法研究[D];天津大學(xué);2012年

10 王磊;信息系統(tǒng)動態(tài)知識更新的矩陣方法研究[D];西南交通大學(xué);2013年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 劉崇亮;分布式呼叫中心監(jiān)控系統(tǒng)的設(shè)計與實現(xiàn)[D];西安電子科技大學(xué);2010年

2 桑銀邦;Deep Web集成系統(tǒng)中同類主題數(shù)據(jù)源選擇方法研究[D];重慶大學(xué);2011年

3 張江靜;一維組合裝車問題模型與算法研究[D];上海交通大學(xué);2012年

4 朱立明;高中數(shù)學(xué)“算法初步”的案例分析[D];東北師范大學(xué);2011年

5 劉君宇;防火墻包過濾規(guī)則框架的設(shè)計與實現(xiàn)[D];東北大學(xué);2010年

6 周備戰(zhàn);“651改”測控計算機(jī)系統(tǒng)設(shè)計與實現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2001年

7 別鋒鋒;油田注水系統(tǒng)設(shè)規(guī)劃優(yōu)化研究[D];大慶石油學(xué)院;2004年

8 王Ym;基于網(wǎng)絡(luò)的計算機(jī)通用考試系統(tǒng)的研制[D];長春理工大學(xué);2004年

9 倪崇嘉;數(shù)學(xué)形態(tài)學(xué)基礎(chǔ)及在圖像處理中的應(yīng)用[D];昆明理工大學(xué);2003年

10 王洪亮;齊魯石化人力資源管理及預(yù)測分析系統(tǒng)[D];北京化工大學(xué);2004年

，

本文編號：648045