赵营峰,尹景本

（河南科技学院,河南新乡453003）

一类线性多乘积规划的分支定界算法

赵营峰,尹景本

（河南科技学院,河南新乡453003）

针对广泛应用于金融及经济等实际问题中的一类线性多乘积规划问题,提出一种分段线性化全局优化算法.首先将问题转化为等价问题,然后利用分段线性化技术得到问题目标函数和约束函数的线性下界,构造出等价问题的松弛线性规划,并从理论上证明了算法的收敛性.数值试验表明算法是有效可行的.

多乘积规划；分支定界；松弛线性规划

多乘积规划广泛应用于产品计划、任务管理、化学工程设计、交通运输和商业等很多领域[1-4].本文针对一类特殊的线性多乘积规划问题提出了一种新的分枝定界算法,该算法在理论上具有重要意义,很多数学规划是其特殊情形或者可以转化为多乘积规划[5-9].针对多乘积规划问题,首先利用恒等变形,建立了原问题的等价问题,然后对等价问题进行松弛得到松弛线性规划,通过对松弛线性规划的可行域的细分以及一系列线性规划的求解,不断更新上下界,并从理论上证明了算法收敛到原问题的全局最优解.

1 松弛线性规划

考虑如下线性多乘积规划问题

根据x2i在区间[li,ui]上的几何性质可知

且

因而令

可得到问题（P）在Sk上的松弛线性规划

2 分支定界算法

下面给出分支定界算法,通过求解一系列松弛线性规RLP（Sk）,逐步改进原问题（P）的最优值的上界和下界,最终确定（P）的全……