本文關(guān)鍵詞：廣義非線性分式規(guī)劃問題的近似算法

  更多相關(guān)文章： 非凸優(yōu)化問題 非線性分式規(guī)劃問題 全局優(yōu)化 近似算法 計(jì)算復(fù)雜度

【摘要】：非凸優(yōu)化問題是一類重要的優(yōu)化問題,它能過廣泛應(yīng)用于分子生物學(xué)、環(huán)境工程、信息技術(shù)和工業(yè)制造等領(lǐng)域.一般情況下這類問題存在大量的非全局最優(yōu)解的局部最優(yōu)解,求解起來比較困難.因此,近年來引起許多工作者的關(guān)注,求解方法越來越多,但這些方法要么沒有給出其計(jì)算復(fù)雜性,要么在理論上無法保證獲得的解的質(zhì)量.本文針對一類廣義分式規(guī)劃問題的兩種特殊形式分別提出相應(yīng)的近似算法,不僅證明了這些近似算法能夠?yàn)閮?yōu)化問題獲得一個(gè)近似最優(yōu)解,而且討論了這些近似算法的計(jì)算復(fù)雜性.當(dāng)組成目標(biāo)函數(shù)的比式函數(shù)的個(gè)數(shù)固定時(shí)這些近似算是完全多項(xiàng)式近似算法.主要內(nèi)容如下：第一章,首先給出本文研究的優(yōu)化問題,其次簡要介紹該優(yōu)化問題的應(yīng)用背景、理論意義及當(dāng)前研究工作,最后介紹本文的主要工作.第二章,本章針對一類目標(biāo)函數(shù)是帶正系數(shù)的分式多項(xiàng)式函數(shù)的優(yōu)化問題提出一種近似算法.通過引入變量將原問題轉(zhuǎn)化為一個(gè)等價(jià)問題,根據(jù)該等價(jià)問題的特點(diǎn),構(gòu)造一個(gè)求解原問題的近似算法,并從理論上證明該近似算法的收斂性和分析其計(jì)算復(fù)雜性,數(shù)值算例也說明該近似算法是有效可行的.第三章,本章考慮一類具有特殊性質(zhì)的一般形式的分式規(guī)劃問題,采用類似于第二章的方法,將原問題轉(zhuǎn)化為一個(gè)等價(jià)問題.利用等價(jià)問題的特征,設(shè)計(jì)一個(gè)求其解近似最優(yōu)解的近似算法,從而獲得原問題一個(gè)近似最優(yōu)解.同時(shí),從理論上證明該算法的收斂性并給出該近似算法的計(jì)算復(fù)雜性,數(shù)值算例表明其是一個(gè)有效可行的近似算法.
【關(guān)鍵詞】：非凸優(yōu)化問題 非線性分式規(guī)劃問題 全局優(yōu)化 近似算法 計(jì)算復(fù)雜度
【學(xué)位授予單位】：河南師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O221
【目錄】：

• 摘要3-4
• ABSTRACT4-8
• 第一章 緒論8-14
• 1.1 研究模型8-9
• 1.2 相關(guān)工作9-11
• 1.3 主要內(nèi)容11-14
• 第二章 一類分式規(guī)劃問題的近似算法14-28
• 2.1 引言14
• 2.2 原問題的等價(jià)轉(zhuǎn)化14-20
• 2.3 近似算法及其計(jì)算時(shí)間復(fù)雜度20-24
• 2.3.1 近似算法20-22
• 2.3.2 近似算法的計(jì)算時(shí)間復(fù)雜性22-24
• 2.4 數(shù)值實(shí)驗(yàn)24-28
• 第三章 一類廣義分式規(guī)劃問題的近似算法28-42
• 3.1 引言28-29
• 3.2 算法的理論基礎(chǔ)29-32
• 3.3 近似算法及其復(fù)雜度分析32-37
• 3.3.1 近似算法32-35
• 3.3.2 算法的計(jì)算復(fù)雜度分析35-37
• 3.4 數(shù)值實(shí)驗(yàn)37-42
• 結(jié)論42-44
• 參考文獻(xiàn)44-48
• 致謝48-50
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄50-52

【相似文獻(xiàn)】

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

1 魏麒;蔣義偉;;一類兩階段雜交流水作業(yè)的近似算法(英文)[J];軟件學(xué)報(bào);2012年05期

2 劉振宏;組合最優(yōu)化問題的近似算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識;1983年03期

3 馬紹漢;一類限制樹問題的復(fù)雜性及其近似算法[J];山東大學(xué)學(xué)報(bào)(自然科學(xué)版);1984年01期

4 楊延齡,戚文發(fā);關(guān)于最優(yōu)備件問題的近似算法的研究[J];工程數(shù)學(xué)學(xué)報(bào);1989年01期

5 杜林古;;帶風(fēng)向投遞員問題的一個(gè)多項(xiàng)式1—近似算法[J];山東紡織工學(xué)院學(xué)報(bào);1992年01期

6 蘇純潔;帶服務(wù)器的三臺平行機(jī)排序問題的復(fù)雜性和近似算法[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2003年03期

7 劉光聰;朱大銘;姜海濤;;有向基因組反轉(zhuǎn)和轉(zhuǎn)位排序最小權(quán)重問題的1.5k近似算法[J];小型微型計(jì)算機(jī)系統(tǒng);2010年07期

8 何勇;帶核集分劃問題的一個(gè)線性(1/7)-近似算法[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);1997年04期

9 季敏,何勇;帶核集分劃問題的一個(gè)改進(jìn)近似算法[J];系統(tǒng)工程理論與實(shí)踐;2003年12期

10 何曉瓊;陳沖;李榮珩;;工廠地址集中的k-種產(chǎn)品選址問題的近似算法[J];計(jì)算機(jī)工程與應(yīng)用;2010年08期

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

1 劉聲田;朱大銘;;基因序列翻轉(zhuǎn)排序的一種近似算法[A];山東省計(jì)算機(jī)學(xué)會2005年信息技術(shù)與信息化研討會論文集（一）[C];2005年

2 梅生偉;洪奕光;秦化淑;翁紹鵬;;非線性H_∞控制的粘性解及其近似算法[A];1996年中國控制會議論文集[C];1996年

3 田世俊;李建;朱洪;;多需求目標(biāo)的UFL問題及其近似算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

4 梁國宏;郭云霞;鄭明發(fā);;最大化下模函數(shù)的近似算法及其性能保證[A];第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學(xué)者大會論文集[C];2012年

5 保利勇;趙東風(fēng);丁洪偉;;雙服務(wù)器異步控制策略輪詢系統(tǒng)性能的近似算法分析[A];2009年中國高校通信類院系學(xué)術(shù)研討會論文集[C];2009年

6 任建峰;張玉忠;孫國;;一種新的柔性車間排序問題[A];中國企業(yè)運(yùn)籌學(xué)學(xué)術(shù)交流大會論文集[C];2005年

7 李灝;張春路;丁國良;;對多層墻體反應(yīng)系數(shù)的一種近似算法的討論[A];上海市制冷學(xué)會一九九七年學(xué)術(shù)年會論文集[C];1997年

8 李灝;張春路;丁國良;;對多層墻體反應(yīng)系數(shù)的一種近似算法的討論[A];全國暖通空調(diào)制冷1998年學(xué)術(shù)年會論文集（2）[C];1998年

9 周露;吳瑤華;黃文虎;聞新;;一種推廣卡爾曼濾波的近似算法[A];1995中國控制與決策學(xué)術(shù)年會論文集[C];1995年

中國重要報(bào)紙全文數(shù)據(jù)庫 前1條

1 PALADIN;近似算法[N];電腦報(bào);2003年

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

1 楊朝霞;超圖嵌入圈問題的近似算法[D];山東大學(xué);2010年

2 潘銳;設(shè)施選址與K-中間點(diǎn)問題的復(fù)雜性與近似算法[D];山東大學(xué);2007年

3 陳仕平;若干組合優(yōu)化問題的近似算法設(shè)計(jì)與分析[D];浙江大學(xué);2002年

4 柳楠;基因組片段填充問題的算法研究[D];山東大學(xué);2013年

5 姜海濤;基因組比較算法研究[D];山東大學(xué);2011年

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

1 陳崇琛;多色點(diǎn)集直線劃分的復(fù)雜性及其近似算法[D];復(fù)旦大學(xué);2014年

2 王敏;基于圖特征的介度中心近似算法研究[D];曲阜師范大學(xué);2015年

3 張亞平;最小賦權(quán)連通k-子圖覆蓋問題的近似算法[D];新疆大學(xué);2015年

4 張永俊;廣義非線性分式規(guī)劃問題的近似算法[D];河南師范大學(xué);2015年

5 李彥杰;連通控制吸收集的近似算法[D];新疆大學(xué);2013年

6 張峰;漫射光化通量的二流四流混合近似算法求解[D];中國氣象科學(xué)研究院;2010年

7 劉海;非光滑問題的三次近似算法[D];北京工業(yè)大學(xué);2014年

8 張諸俊;異構(gòu)車輛路徑問題近似算法的研究[D];華東師范大學(xué);2014年

9 趙倩;公共鄰接距離基因組片段填充問題研究[D];山東大學(xué);2013年

10 王錦;集裝箱調(diào)度問題的平行機(jī)排序算法研究[D];復(fù)旦大學(xué);2010年

，

本文編號：791825