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

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

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

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