1. 引言
本文考虑如下带有符号的线性乘积和规划问题:
其中
为
上的线性函数,
或
,
,
,
,p,m,n都是正整数,D是非空有界的凸多面体。
乘积规划问题在用于经济、交通等众多领域具有广泛的使用价值,如金融优化 [1] 、鲁棒优化 [2] 、证券投资 [3] 等。乘积规划问题的多极值性(多个局部最优解),使得求其全局最优解变得十分困难。所以,有许多学者关注于乘积规划问题的全局最优值的求解。近年来,一些求解乘积规划问题的方法相继被提出,包括外逼近方法 [4] ,割平面法 [5] ,分支定界方法 [5] [6] [7] 等。本文针对一类带有符号的线性乘积和规划问题(GLMP),采用二级松弛技术和超矩形缩减策略,提出了一种新的分支定界算法,并进行了数值分析。
本文的结构安排如下:第2节利用二级松弛技术,确定(GLMP)问题全局最优值的下界;第3节利用超矩形的剖分与缩减技术,给出分支定界算法,通过数值算例验证算法的可行性与有效性。
2. 松弛定下界方法
本节首先利用凸包络技术给出(GLMP)问题中乘积函数的一个下界函数,进一步,通过二次松弛得到原问题的线性松弛规划问题,进而给出(GLMP)问题的下界。
不失一般性,我们假定
,
;
,
。因(GLMP)问题的可行域D是非空有界集,我们可构造包含D的超矩形
,
,
,其中
,
,
.
下面确定乘积函数
的凸包络,首先求解如下线性规划问题:
,
,
和
(1)
设问题(1)的最优解分别为
,
,
,
,最优值分别为
,
,
,
(
),从而有
,
(2)
显然
,
,
,
均为(GLMP)问题的可行解,设
,其中Q表示(GLMP)问题目前可行解的集合。
令
,
。下面确定乘积函数
在
上的凸包络 [8] :
由(2)式可得:
1) 若
且
,则
展开得
2) 若
且
,则
3) 若
且
,则
4) 若
且
,则
为了表达方便,令:
,
,
即
由此,我们可以得到(GLMP)问题在超矩形
上的松弛规划问题(SLMP):
又因
所以我们可得到(GLMP)问题在超矩形
上的二级松弛规划问题(SSLP):
(SSLP)问题的最优解为(GLMP)问题的一个可行解,其最优值恰好为(GLMP)问题在超矩形
上全局最优值的一个下界,该可行解记为
,令
,其中Q表示(GLMP)问题目前所有可行解构成的集合。
进一步,我们可以得到与(GLMP)问题等价的线性规划问题(LP):
显然,(LP)问题在
上的最优值是(GLMP)问题全局最优值的一个下界,它也是(GLMP)问题在
上全局最优值的一个下界。
3. 分支定界算法
本节利用超矩形的剖分与缩减技术,给出确定(GLMP)问题全局最优值的分支定界算法,并进行数值实验。
3.1. 超矩形的剖分
不失一般性,假设第k次剖分的超矩形为
:
步骤1:
1) 选择
的最长边,即
;
2) 令
,
步骤2:将超矩形
沿着
剖分为子超矩形
,
其中
,
,
,
。
令
,
。
3.2. 超矩形的缩减
为了叙述方便,缩减后的超矩形仍记为
。对(GLMP)问题中的线性不等式约束条件
(
),利用文献 [6] [9] 中超矩形缩减技术进行缩减。
3.3. 分支定界算法
给出以下记号(假定算法迭代到第k步):
D:(GLMP)问题的可行域;Q:当前可行解的集合;
:选择剖分的超矩形;
T:剪支剩余超矩形的集合;
:(GLMP)问题全局最优值的上界;
:(GLMP)问题全局最优值的下界。
下面给出算法过程的具体描述。
步骤1:(初始化)
构造包含
的超矩形
,在超矩形
上求解问题(LP),其对应最优解和最优值分别记为
和
,
就是(GLMP)问题全局最优值的一个下界,显然
,令
,初始上界为
,并找一个当前最优解
,给定精度
,
,置k = 1。
步骤2:(终止规则)
若
或
,则终止,输出(GLMP)问题的全局最优解
、全局最优值
; 否则,转步骤3;
步骤3:(选择规则)
在
中选择
,
为
所对应的超矩形,即
;
步骤4:(剖分及缩减技术)
运用2.1中超矩形的剖分方法,将
剖分为
与
两部分,
;再应用2.2
中超矩形的缩减技术,将
和
缩减后的超矩形仍记为
,令
(
),缩减后的超矩形的指标集,记为
。
步骤5:(剪支规则)让
。
步骤6:(定界)定下界:
;
定上界:
,当前最好的可行解:
置
,转步骤2。
4. 数值实验
为了检测新算法的可行性与有效性,做以下的数值实验,算法编程在Pentium(R)4,CPU3.20 GHZ,1.00 GB内存微机上运行,精度取为
。
例1 [7]
运用本文所提出的算法得到:最优解为(5.5556; 1.7778; 2.6667),最优值为−112.7531,迭代次数为3,计算时间为1.586198。文献 [7] 的最优解为(5.5556; 1.7778; 2.6667),最优值为−112.7531,迭代次数为54。
通过以上计算所得结果显示,本文所提出的方法是有效可行的。
基金项目
陕西省自然科学基础研究项目(2017JQ3020);陕西省高校科协青年人才托举项目资助(20160234);宝鸡文理学院校级科研项目(ZK2017095; ZK2017021)。