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

  更多相關文章： 裝箱 網絡優(yōu)化 近似算法 (漸近)最壞情況界

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關會議論文 前4條

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

2 何洋林;葉春明;;CEPGA算法在網絡計劃組合優(yōu)化問題中的應用[A];全國第十屆企業(yè)信息化與工業(yè)工程學術年會論文集[C];2006年

3 徐俊明;;網絡分析中幾個組合優(yōu)化問題[A];中國運籌學會第七屆學術交流會論文集（中卷）[C];2004年

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

相關重要報紙文章 前3條

1 程建平;發(fā)掘資源的最大價值[N];中國特產報;2003年

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

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

相關博士學位論文 前6條

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

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

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

4 吳t熇，

本文編號：1326009