兩類分式規(guī)劃問(wèn)題的分支定界算法.pdf

1、單位代碼10476學(xué)號(hào)1501183022分類號(hào)02212IIIIIIIIIIIIIIIIIIIIf№437373河南衙蕁云大孝河南衙蕁云大孝碩士學(xué)位論文兩類分式規(guī)劃問(wèn)題的分支定界算法學(xué)科、專業(yè)：研究方向：申請(qǐng)學(xué)位類別：申請(qǐng)人：指導(dǎo)教師：數(shù)學(xué)最優(yōu)化理論、算法及其應(yīng)用理學(xué)碩士張同麗申培萍教授二。一八年五月摘要分式規(guī)劃問(wèn)題是一類非常重要的非凸優(yōu)化問(wèn)題，它廣泛應(yīng)用于交通規(guī)劃、金融投資、聚類分析、政府規(guī)劃等鄰域這類問(wèn)題的模型包含許多特殊形式，一

2、般情況下，它們存在多個(gè)局部而非全局的最優(yōu)解，增加了求解問(wèn)題的難度近年來(lái)，許多算法被提出，用于求解這類問(wèn)題的特殊模型本文針對(duì)極大化線性比式和問(wèn)題與極小化帶有二次約束的二次比式和問(wèn)題，分別提出了相應(yīng)的分支定界算首先，給出本文要研究的模型，以及該模型的應(yīng)用背景、理論意義、研究現(xiàn)狀，并簡(jiǎn)單介紹了本文的主要研究工作其次，針對(duì)一類線性比式和分式規(guī)劃問(wèn)題提出了一種分支定界算法在模型等價(jià)轉(zhuǎn)化的基礎(chǔ)上，利用雙線性函數(shù)的凸包絡(luò)和比式函數(shù)的凹包絡(luò)將等價(jià)問(wèn)題線

3、性化，然后通過(guò)求解一系列線性規(guī)劃問(wèn)題獲得原問(wèn)題的最優(yōu)解并且在理論上證明了該分支定界算法的收斂性，分析了算法的計(jì)算復(fù)雜度數(shù)值實(shí)驗(yàn)表明該算法是有效可行的最后，考慮一類帶有二次約束的二次比式和問(wèn)題先利用等價(jià)性技巧將原問(wèn)題等價(jià)轉(zhuǎn)化，然后利用矩陣分解理論將等價(jià)問(wèn)題松弛為線性規(guī)劃問(wèn)題，在求解一系列線性規(guī)劃問(wèn)題的基礎(chǔ)上得到原問(wèn)題的最優(yōu)解最后給出了算法的收斂性證明，數(shù)值實(shí)驗(yàn)表明該算法對(duì)求解二次比式和問(wèn)題有效可行關(guān)鍵詞：分式規(guī)劃，全局優(yōu)化，線性比式和，二