本文關(guān)鍵詞：集成網(wǎng)絡(luò)與裝箱的一類新型組合優(yōu)化問題　出處：《杭州電子科技大學(xué)》2016年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 裝箱 網(wǎng)絡(luò)優(yōu)化 近似算法 (漸近)最壞情況界

【摘要】：眾所周知,裝箱和網(wǎng)絡(luò)優(yōu)化都是經(jīng)典的組合優(yōu)化問題,在運(yùn)籌學(xué)領(lǐng)域里至關(guān)重要。最優(yōu)化理論的深入發(fā)展不僅豐富了這些問題本身的理論成果,而且也促使它們?cè)诮?jīng)濟(jì)管理、交通運(yùn)輸、信息與網(wǎng)絡(luò)技術(shù)等生產(chǎn)實(shí)踐中得以廣泛應(yīng)用。一般來說,對(duì)經(jīng)典組合優(yōu)化問題的研究是相互獨(dú)立的,而本文主要研究一類集成裝箱和網(wǎng)絡(luò)優(yōu)化的新型組合優(yōu)化問題。給定賦權(quán)有向網(wǎng)絡(luò)D,需要尋找D的一個(gè)具有某種特殊結(jié)構(gòu)的子網(wǎng)絡(luò),使得子網(wǎng)絡(luò)中的各條弧在按照一定規(guī)則切割成長(zhǎng)為L(zhǎng)的分段時(shí)所需的分段數(shù)盡可能小。本文給出了相關(guān)問題的近似算法和最壞情況分析。全文將分成四章進(jìn)行闡述。第一章,首先給出裝箱和網(wǎng)絡(luò)優(yōu)化問題的基本模型與定義,接著介紹計(jì)算復(fù)雜性理論以及近似算法、(漸近)最壞情況界等概念。第二章,研究了子網(wǎng)絡(luò)結(jié)構(gòu)限定為s-t有向路或者強(qiáng)連通支撐子網(wǎng)絡(luò)的問題,分別設(shè)計(jì)了漸近最壞情況界為61/36和61/18的近似算法,改進(jìn)了已有的結(jié)果。第三章集中考慮網(wǎng)絡(luò)的弧權(quán)重至少是L的特殊情形,若子網(wǎng)絡(luò)結(jié)構(gòu)限定為st有向路,設(shè)計(jì)了最壞情況界為4/3和漸近最壞情況界為95/72的兩個(gè)近似算法。若結(jié)構(gòu)限定為強(qiáng)連通支撐子網(wǎng)絡(luò),則對(duì)應(yīng)的算法界分別為8/3和95/36。第四章總結(jié)全文,并給出主要結(jié)論及可能研究方向。
【學(xué)位授予單位】：杭州電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5;O224

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 何幼林;歐福軍;魏華實(shí);徐健;張雍吉;;蟻群算法的原理及其在組合優(yōu)化中的應(yīng)用[J];黑龍江科技信息;2008年01期

2 洪大威;;從制定偵破方案說起——組合優(yōu)化一例[J];科學(xué);1986年03期

3 越民義;;組合優(yōu)化介紹[J];運(yùn)籌學(xué)雜志;1988年01期

4 王宇平,徐晨;解組合優(yōu)化的一種新方法的收斂性[J];西安電子科技大學(xué)學(xué)報(bào);1997年04期

5 彭勝志;王福勝;;高階投資組合優(yōu)化問題的研究述評(píng)[J];財(cái)會(huì)研究;2012年01期

6 陳盛雙,武華,李亮;企業(yè)管理組合優(yōu)化的數(shù)學(xué)模型及遺傳算法[J];武漢汽車工業(yè)大學(xué)學(xué)報(bào);2000年06期

7 王貞;劉三陽;孔翔宇;;投資組合優(yōu)化問題情景生成方法的比較[J];蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

8 馬玉潔;;產(chǎn)品組合優(yōu)化決策方法分析[J];財(cái)會(huì)月刊;2013年17期

9 曹家明;;一類組合優(yōu)化問題與非凸二次規(guī)劃的等價(jià)[J];西南交通大學(xué)學(xué)報(bào);1993年01期

10 汪祖柱,程家興;求解組合優(yōu)化問題的一種方法—分枝定界法[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年01期

相關(guān)會(huì)議論文 前4條

1 于曉義;吳毅;王達(dá)達(dá);楊昆;;基于負(fù)荷均衡的工作中心任務(wù)組合優(yōu)化分配研究[A];2010年云南電力技術(shù)論壇論文集（優(yōu)秀論文部分）[C];2010年

2 何洋林;葉春明;;CEPGA算法在網(wǎng)絡(luò)計(jì)劃組合優(yōu)化問題中的應(yīng)用[A];全國(guó)第十屆企業(yè)信息化與工業(yè)工程學(xué)術(shù)年會(huì)論文集[C];2006年

3 徐俊明;;網(wǎng)絡(luò)分析中幾個(gè)組合優(yōu)化問題[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

4 李彥蒼;索娟娟;;基于熵和信息素的自適應(yīng)GA及其在組合優(yōu)化中的應(yīng)用[A];Well-off Society Strategies and Systems Engineering--Proceedings of the 13th Annual Conference of System Engineering Society of China[C];2004年

相關(guān)重要報(bào)紙文章 前3條

1 程建平;發(fā)掘資源的最大價(jià)值[N];中國(guó)特產(chǎn)報(bào);2003年

2 安徽 朱寶貴;Office 2000與XP組合優(yōu)化安裝技巧[N];電子報(bào);2005年

3 薛梅;柜面勞動(dòng)組合優(yōu)化應(yīng)多管齊下[N];中國(guó)城鄉(xiāng)金融報(bào);2014年

相關(guān)博士學(xué)位論文 前6條

1 王軍強(qiáng);基于約束理論的產(chǎn)品組合優(yōu)化決策研究[D];西北工業(yè)大學(xué);2006年

2 王正元;基于狀態(tài)轉(zhuǎn)移的組合優(yōu)化方法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2004年

3 彭勝志;基于高階矩的投資組合優(yōu)化研究[D];哈爾濱工業(yè)大學(xué);2012年

4 吳t熇，

本文編號(hào)：1326009