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

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

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

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