分式规划和乘积规划分支定界算法的研究

《分式规划和乘积规划分支定界算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要本论文主要研究了线性分式规划问题和乘积规划问题的求解方法．全文分为三部分，主要内容如下：第一部分研究了一种新的线性分式和规划问题的分母输出空问分支定界算法．在这个算法中，以目标函数中每个分式的分母作为变量构成输出空间，对这些变量的取值范围笛卡尔乘积构成的超矩形进行剖分，在决策变量远远大于分式的个数时可以大大地降低计算量，同时用线性规划松弛技术以确定原问题最优值的下界．数值实验表明该算法的可行性及有效性．第二部分研究了线性乘积规划问题在输出空间上的一种新的分支定界算法．在这个算法中，给出可分解的松

2、弛规划阎题，以确定原问题最优值的下界；为了更有效地搜索原问题的全局最优解，建立凸二次规划问题，数值实验表明该算法的可行性及有效性．第三部分研究了一类带有乘积约束的线性乘积规划问题的分支定界缩减方法，在这个方法中，利用凸包络技术构造目标函数与约束条件中乘积函数的下界，从而通过求解一个凸规划问题来确定原问题最优值的下界；为了提高逼近程度，加快收敛速度，使用了超矩形的缩减策略．数值实验表明该算法的可行性．关键词：全局优化，线性分式和规划，线性乘积规划，分支定界算法AbstractThisthesismai

3、nlystudiesthemethodsofsolvinglinearfractionalprogrammingproblemandmultiplicativeprograrmningproblem．Thethesisisdividedintothreeparts，themaincontentsarestatedasfollows：Atfirst,册oflinearfractionalprogrammingproblemsarcresearched，anewdenominators’outcomes

4、pacebranch—and-boundalgorithmisproposed．Inthisalgorithm，thedenominatorsofthefractionsintheobjectivefunctionarcasvariablestoconstructtheoutcomespace．Thehypen'ecumgularwhichistheCartesianproductofthevariablesrangesispartitioned．Whenthenumberofthedecision

5、variablesisfargreaterthanthenumberoffractions，theamountofcomputationcallbereducedsignificantly．ThelinearprogrammingrelaxationtechniqueisusedtOdeterminethelowerboundoftheoptimalvalueoftheoriginalproblem．Numericalexperimentsarereportedtoshownthefessibili

6、哆andeffectivenessoftheproposedalgorithm．Next，alloutcomespacebranch-and-boundalgorithmisresearchedforgloballysolvingaclassoflinearmultiplicativeprogrammingproblem．Inthisalgorithm,thelowerboundisderivedbysolvingaseparablerelaxationprogrammingproblem，i．e．

7、thelowerboundingfunctionoftheobjectivefunctionformeproblem．Furthermore，inordertoefficientlysearchformcglobaloptimalsolutiontotheoriginalproblem，aconvexquadraticprogrammingproblemisconstructed．Numericalexperimentsarereportedtoshownthefeasibilityandeffec

8、tivenessoftheproposedalgorithm．Finally,abranch-and-boundreducedmethodisresearchedforgloballysolvingaclassoflinearmultiplicativeprogrammingproblemswithadditionalmultiplioativeconstraints．Inthismethod，lowerboundsofmultiplieativefunctionsi