一类线性分式规划问题的全局优化方法.pdfVIP

第27卷第2期 纺织高校基础科学学报 V01．27，No．2 201 TEXTILE 4年6月 BASICSCIENCESJOURNALOF UNIVERSITIESJun．，2014 文章编号：1006—8341(2014)02—0216—06 一类线性分式规划问题的全局优化方法 陈艳霞1，高岳林1’2，马文路2 (1．宁夏大学数学计算机学院，宁夏银川750021；2．北方民族大学信息与系统科学研究所，宁夏银川750021) 摘要：针对一类线性分式规划问题，给出一个新的分支定界算法．算法的主要特点是在建立原问 题等价的松弛线性规划问题时，利用对数函数和指数函数的单调性和凹凸性，提出了一个新的二 级松弛规划来确定最优值的下界，这可以用于改善算法的收敛速度．通过对松弛线性规划问题可 行域的细分以及一系列松弛线性规划问题的求解过程，从理论上证明了此算法能收敛到初始问 题的全局最优解．并通过数值算例证明了算法的有效性． 关键词：线性分式规划；分支定界方法；线性松弛技术；全局优化 中图分类号：O211．1 文献标识码：A 0 引 言 考虑如下线性分式和规划问题(P) (P)min弛)-善端， l。．t．z∈x． z ER““，b∈R”， 0，V EX，7／』，dJ∈R“，aj，bj∈R，歹一1，2，…，力，X={X∈R”{舡≤b)是多胞形，A 一般地P≥2． 全局优化是最优化理论中最重要的一个分支，全局优化研究的是目标函数在某个区域上全局最优点 的特征和计算方法．从20世纪70～80年代开始，国内就有一些学者从事全局优化的研究，他们提出的填 充函数、水平集上积分等全局优化算法在国际上也有一定的影响． 分式规划是非线性优化中的一个重要分支，数十年来吸引了许多研究者的关注．原因在于：第一，此 类问题广泛用于经济、交通等领域，具有很强的实用性；第二，这类问题的分子和分母均为线性仿射函 数，所以问题(P)可能存在多个局部最优解，使得问题求解比较困难．目前，针对线性分式规划的求解已 提出许多算法[1≈]． 问题(P)是一类特殊的非线性优化问题，在许多领域中有着广泛的应用，如运输方案、经济效益问题、 金融投资问题等，因此十多年来受到了许多学者的关注．由于问题(P)是多极值的，甚至拥有许多局部最 优解，所以求全局最优解很难．求解一般分式规划问题的思想是将分式规划转化为非分式规划形式的非线 收稿日期：2013—03一i1 基金项目：国家自然科学基金资助项目 通讯作者：高岳林(1963一)，男，陕西省榆林市人，宁夏大学教授，博士生导师，研究方向为最优化理论与方法，智能计算 与智能信息处理，金融数学与金融工程．E-mail：gaoyuelin@263．net 第2期 一类线性分式规划问题的全局优化方法 217 性规划来求解．当P一2时，Konnon3构造了一个类似的参数单纯形算法，该算法可用来求解大规模的优 化问题；当P一3时，KonnoE豇推广了参数单纯形算法，构造出一种有效的启发式算法；当P≥4时，文献 [6]给出求解一个带系数的线性比式和问题时，通过使用一个等价转化和线性松弛化技术，将初始非凸规 划问题缩减到一系列的线性规划问题从而达到求解的目的． 本文首先通过使用等价变换技术得出初始问题(P)的一个等价问题(Q)，接着用二级线性松弛技术[9] 给出了等价问题(Q)的线性松弛规划问题．然后给出矩形的剖分过程．描述分支定界算法并给出算法的收 敛性证明．最后通过数值实验说明所提出的算法是有效的． 1 二级线性松弛 在求解问题(P)时，首先求解下面2n个线性规划问题 』洲n：ri’ 和『ma弛’ 1 s．t．Ax≤b．’1 s．t．Ax≤b． 可得