一类多乘积规划问题的单纯形分支定界方法.pdfVIP

第28卷第1期 黑龙江大学自然科学学报 V01．28No．1 JOURNALOFNATURALSCIENCEOF UNIVERSITY 2011年2月 HEILONGJIANG February，2011 一类多乘积规划问题的单纯形分支定界方法 魏飞， 高岳林， 刘俊梅 (北方民族大学信息与系统科学研究所，银川750021) 摘要：利用对数函数的性质将一类多乘积规划问题等价地转化为一个凹最小问题。针对这 个问题的凹和特殊结构，利用单纯形上凹函数凸包络的线性性质，给出线性规划松弛问题以确定原 问题最优值的下界，由此提出一类多乘积规划问题的单纯形分支定界算法，并且给出收敛性证明。 数值例子表明所提出的算法是可行的和有效的。 关键词：全局优化；凹乘积规划；分支定界方法；凸包络 中图分类号：0211．1文献标志码：A 0 引 言 考虑下面的非线性多乘积全局优化问题： F0(戈)， rmin (P){s．t．FI(z)≤巩，k=1，2，…，m． 【 髫∈s． 其中 靠 凡(石)=兀凡(z)，k=o，1，…，m。 的可行域。 乘积规划问题广泛应用于金融优化‘1|、证券投资‘引、VLISI芯片设计‘引、多目标决策问题‘引、最优储存与 布局‘5l、数据挖掘与模式识别‘6 3等众多实际问题中。由于问题(P)通常有多个局部最优解，使得求其全局最 优解变得十分困难。而且问题(P)是NP难的。近年来，针对乘积规划问题已有很多求解算法，可分为以下 几类：原始对偶单纯形方法‘引、外逼近方法‘81、分解方法‘91、分支定界方法‘10一圳、割平面方法‘11,21]、启发式算 法‘121、基于参数的方法‘131、极点枚举法‘“1、像空间分析方法‘15 3等。本文针对一类多乘积的规划问题(P)， 提出了一种求解的单纯形分支定界算法，给出了收敛性的证明，进行了数值分析。 1 等价问题及其线性规划松弛 在分支定界算法中，定下界是核心工作之一，本节给出问题(P)的一个定下界技术。 化为： ，mmGo(戈)， (户)j。．t．G^(石)一ln0^，k=1，2，…，m。 【 茗∈S． 收稿日期：2010—04—06 基金项目：国家自然科学基金资助项目 作者简介：魏飞(1987一)，女，硕士研究生，主要研究方向：最优化理论方法及应用 通讯作者：高岳林(1963一)，男，教授，博士。E—mail：gaoyuelin@263．net ·卯· 黑龙江 大学 自 然科学 学报 第28卷 其中 n G。(菇)=∑ln％(z)，k=o，1，…，m。 妨记为菇’，则问题(P)的最优值就是R(戈’)。下面只需考虑问题(户)。 界。为了对问题(户)进行线性规划松弛，首先给出关于凹函数凸包的两个引理‘19】。 引理I．1设口。，秽：，…，％是多胞形P的顶点。凹函数以菇)在P上的凸包络F(x)可以表示成 fF(茗)2哑n荟a以Vi) { 。 。 【s．t． ∑Ogiq=龙，∑0[f=1，0ci≥o，i=1，2，…，k。 其中