0 引言

【研究意义】线性比式和优化问题在运输计划,政府规划及经济投资等领域有着重要的作用^[1].考虑如下线性比式和问题:

$\left( P \right):\left\{ \begin{array}{l} minf\left( x \right) = \sum\limits_{i = 1}^p {} \frac{{c_i^ \top x + {\alpha _i}}}{{d_i^ \top x + {\gamma _i}}}\\ s.t.Ax \le b,\\ x \in {X^0} = \left\{ {x \in {\rm{ }}R_ + ^n:{l^0} \le x \le {u^0}} \right\}, \end{array} \right.$

其中A∈R^m×n,b∈R^m,c_i,d_i∈Rⁿ,α_i,γ_i∈R,d_i^┬x+γ_i>0,且γ_i≠0,i=1,2,…,p,可行域D={x∈X⁰|Ax≤b}非空. 题(P)的目标函数既非拟凸也非拟凹,在理论和计算方面具有很大的挑战性,因此对问题(P)的求解方法的研究既有理论意义又有实用价值.【前人研究进展】近年来问题(P)已引起许多研究者的关注^[1-5],目前人们针对线性比式和问题的研究大多都要求目标函数的分子分母在可行域内非负.【本研究切入点】本文考虑的问题模型仅要求d_i^┬x+γ_i>0,且γ_i≠0.【拟解决的关键问题】采用新的分支定界技术,从理论上证明了算法的收敛性,且用数值算例验证算法是可行的.

1 预备知识

为了求解问题(P),引入p个向量 y_i= $\frac{x}{{d_i^ \top x + {\gamma _i}}}$ ,i=1,2,…,p. 根据Sherman-Morrison定理可得,x= $\frac{{{\gamma _i}{y_i}}}{{1 - d_i^ \top {y_i}}}$ ,i=1,2,…,p.于是,问题(P)可转化为如下等价问题:

$\left( {\tilde P} \right)\left\{ \begin{array}{l} min\sum\limits_{i = 1}^p {} {\left( {{c_i} - \frac{{{\alpha _i}}}{{{d_i}{\gamma _i}}}} \right)^ \top }{y_i} + \frac{{{\alpha _i}}}{{{\gamma _i}}}\\ s.t.Ax \le {\rm{ }}b,\\ {y_i} = \frac{x}{{d_i^ \top x + {\gamma _i}}},i = 1,2, \ldots ,p,\\ x \in {X^0} = [{l^0},{u^0}]. \end{array} \right.$

命题1 若(x^*,y^*)是( ${\tilde P}$ )的最优解,则x^*是(P)的最优解,反之,若x^*是(P)的最优解,则(x^*,y^*) 是问题( ${\tilde P}$ ) 的最优解,其中,y^*= $\frac{{{x^*}}}{{d_i^ \top {x^*} + {\gamma _i}}}$ ,i=1,2,…,p.且问题(P)和( ${\tilde P}$ )的最优值相等.

由问题(P)和问题( ${\tilde P}$ )的定义易得命题1成立.

令X=[l,u]表示初始盒子X⁰,或者由算法产生的X⁰的子盒子.下面考虑如何在子盒子X上求解问题( ${\tilde P}$ ),为此,需要构造 ${\tilde P}$ (X)的线性松弛规划问题,其最优值能作为 ${\tilde P}$ (X)的最优值的一个下界.为了方便, 令 ${\xi _i} = {c_i} - \frac{{{\alpha _i}{d_i}}}{{{\gamma _i}}},{\tau _i} = \frac{{{\alpha _i}}}{{{\gamma _i}}}$ ,i∈I={1,2,…,p},去掉问题(X)中p个等式约束,可得其松弛问题:

$Q\left( X \right):\left\{ \begin{array}{l} ming\left( y \right) = \sum\limits_{i = 1}^p {} \xi _i^ \top {y_i} + {\tau _i}\\ s.t.(A + \frac{{bd_i^ \top }}{{{\gamma _i}}}){y_i} \le \frac{b}{{{\gamma _i}}},i \in I,\\ - (\frac{{ld_i^ \top }}{{{\gamma _i}}} + I){y_i} \le - \frac{l}{{{\gamma _i}}},i \in I,\\ (\frac{{ud_i^ \top }}{{{\gamma _i}}} + I){y_i} \le \frac{u}{{{\gamma _i}}},i \in I,\\ \frac{l}{{{s_i}}} \le {y_i} \le \frac{u}{{{t_i}}},i \in I, \end{array} \right.$

其中,s_i= $\sum\limits_{j = 1,{d_{ij}} > 0}^n {} {d_{ij}}{u_j} + \sum\limits_{j = 1,{d_{ij}} < 0}^n {} {d_{ij}}{l_j} + {\gamma _i},{\rm{ }}{t_i} = \sum\limits_{j = 1,{d_{ij}} > 0}^n {} {d_{ij}}{l_j} + \sum\limits_{j = 1,{d_{ij}} < 0}^n {} {d_{ij}}{u_j} + {\gamma _i}$ .

命题2 (i) 若x^*是问题P(X)的最优解,则问题Q(X)有最优解 ${\tilde y}$ ,且 $\sum\limits_{i = 1}^p {} \xi _i^ \top {{\tilde y}_i} + {\tau _i} \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top {x^*} + {\alpha _i}}}{{d_i^ \top {x^*} + {\gamma _i}}}$ .

(ii) 若 ${\tilde x}$ ₁=…= ${\tilde x}$ _i=…= ${\tilde x}$ _p,其中, ${{\tilde x}_i} = \frac{{{\gamma _i}{{\tilde y}_i}}}{{1 - d_i^ \top {{\tilde y}_i}}}$ ,i=1,2,…,p,则每个 ${{\tilde x}_i}$ 均是问题P(X)的最优解.

证明 (i)令y_i^*= $\frac{{{x^*}}}{{d_i^ \top {x^*} + {\gamma _i}}}$ ,i∈I,显然,y^*是问题 Q(X)的可行解.设 ${\tilde y}$ 是线性规划问题Q(X)的最优解,则g( ${\tilde y}$ )≤g(y^*)= $\sum\limits_{i = 1}^p {} \frac{{c_i^ \top {x^*} + {\alpha _i}}}{{d_i^ \top {x^*} + {\gamma _i}}}$ ,即(i)成立.

(ii)显然每个 ${\tilde x}$ _i均是问题P(X)的可行解,所以由(i),g( ${\tilde y}$ )= $\sum\limits_{i = 1}^p {} \frac{{c_i^ \top {{\tilde x}_i} + {\alpha _i}}}{{d_i^ \top {{\tilde x}_i} + {\gamma _i}}} \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top {x^*} + {\alpha _i}}}{{d_i^ \top {x^*} + {\gamma _i}}}$ ,则当 ${\tilde x}$ ₁= ${\tilde x}$ ₂…= ${\tilde x}$ _p时,每个 ${\tilde x}$ _i均是问题P(X)的最优解.

由上述命题可知,若求得问题Q(X)的最优值 g( ${\tilde y}$ ),则其可作为问题P(X)的最优值的一个下界.

2 算法及其收敛性

采用分支定界方法求解问题 ${\tilde P}$ (X),并利用问题Q(X)进行定界,而分支过程采用如下ω分割^[6].设y=(y₁,y₂,…,y_p)是问题Q(X)的最优解,则x_i= $\frac{{{\gamma _i}{y_i}}}{{1 - d_i^ \top {y_i}}}$ (i=1,2,…,p),重心ω= $\frac{1}{p}\sum\limits_{i = 1}^p {} {x_i}$ 是问题P(X)的可行解.由命题2,若x₁=…=x_p,则每个x_i是P(X)的最优解,否则,可用点ω分割盒子X=[l,u],具体过程如下:

令N={1,2,…,n},ρ_j=min{u_j-ω_j,ω_j-l_j},j∈N,q∈arg max{ρ_j|j∈N}.这样X就被分割成两个子盒子X₁=[l′,u]和X₂=[l,u′],其中,

$\begin{array}{*{20}{l}} {l' = \left( {{l_1}, \ldots ,{l_{q - 1}},{\omega _q},{l_{q{\rm{ }} + 1}}, \ldots ,{l_n}} \right),}\\ {u' = \left( {{u_1}, \ldots ,{u_{q - 1}},{\omega _q},{u_{q{\rm{ }} + 1}}, \ldots ,{u_n}} \right).} \end{array}$

令X¹=X⁰,用上述分割方法将盒子X¹分割成X₁¹和X₂¹,在这两个子盒子上分别求解问题Q(X_r¹),r=1,2,其较小最优值所对应的盒子定义为X²,再对此盒子进行分割.该过程依次进行下去就会得到一系列子盒子X_r^k,k=1,2,…,r=1,2.

通过求解问题Q(X_r^k),可逐步改进原问题(P)的最优值的上下界,最终确定(P)的全局最优解.假定在算法的第k次迭代,E_k表示由活动节点(可能存在全局最优解的盒子)构成的集合.对每个节点 ${\hat X}$ ∈E_k,求得问题Q( ${\hat X}$ )的最优解,能得到问题(P)的对应的若干可行解,再更新(P)的最优值的上界UB_k.由于问题Q( ${\hat X}$ )的最优值LB( ${\hat X}$ )为原问题(P)最优值的下界.若LB( ${\hat X}$ )>UB_k,将节点从E_k中删除.选定一个合适的活动节点,将其分成两部分,在每个新的节点上求解问题,重复这一过程直到满足收敛条件为止.具体算法步骤如下:

步骤1 给定参数∈≥0,迭代次数k=1,活动节点E_k={X^k},上界UB_k=∞.

求解问题Q(X^k)得最优解和最优值分别为y^k和LB(X^k)=g(y^k).令

$x_i^k = \frac{{{\gamma _i}y_i^k}}{{1 - d_i^ \top y_i^k}},i = 1,2, \ldots ,p.$

若x₁^k=…=x_p^k,算法终止,x_i^k,f(x_i^k)(∀i∈I)分别是原问题(P)的最优解和最优值,否则,执行步骤2.

步骤2 令ω^k= $\frac{1}{p}\sum\limits_{i = 1}^p {} x_i^k$ , UB_k=min{UB_k,f(x₁^k),…,f(x_p^k),f(ω^k)},LB_k=LB(X^k),选定x^k使得UB_k=f(x^k).若UB_k-LB_k≤∈,算法终止,x^k与UB_k分别为原问题(P)的最优解和最优值,否则,执行步骤3.

步骤3 用ω分法将盒子X^k分成两部分X₁^k和X₂^k,令E_k=E_k \{X^k}.

步骤4 对于任意r∈{1,2},若X_r^k≠Ø,求得问题Q(X_r^k)的最优解y_r^k,令 LB(X_r^k)=g(y_r^k).

若LB(X_r^k)≤UB_k,令E_k=E_k∪X_r^k, x_{r i}^k= $\frac{{{\gamma _i}y_{ri}^k}}{{1 - d_i^ \top y_{ri}^k}}$ ,i=1,2,…,p, ω_r^k= $\frac{1}{p}\sum\limits_{i = 1}^p {} x_{ri}^k$ , UB_k=min{UB_k,f(x_{r 1}^k),…,f(x_{r p}^k),f(ω_r^k)}. 选定x^k使得UB_k=f(x^k).

步骤5 令E_k+1=E_k∪{ ${\hat X}$ ∈E_k:UB_k-LB( ${\hat X}$ )≤∈}.若E_k+1=Ø,算法终止,x^k与UB_k分别为问题(P)的最优解和最优值.否则,k=k+1,令X^k=arg $\mathop {\min }\limits_{\hat X \in {E_k}} LB\left( {\hat X} \right)$ ,返回步骤3.

由上述算法可知,在迭代过程中至少会产生一个嵌套的盒子序列,不妨仍记为{X^k},那么每个盒子的上下界及分割点ω^k 所产生的序列{l^k},{ω^k},{u^k}满足如下条件:

${l^k} \le {l^{k + 1}} \le {\omega ^{k + 1}} \le {u^{k + 1}} \le {u^k},k = 1,2, \cdots .$

(1)

其中[l1,u1]=[l0,u0],ωqkk∈{lqkk+1,uqkk+1}.

引理1 (i) 序列{l^k},{u^k}满足: $\mathop {\lim }\limits_{k \to + \infty } {l^k} = \bar l,\mathop {\lim }\limits_{k \to + \infty } {u^k} = \bar u$ ,且l¹≤l≤u≤u¹.(ii)序列{ω^k}的任意聚点均是盒子[l,u]的拐点.(iii)设{ω^k_s}是收敛于ω的一个子序列,那么 $\mathop {\lim }\limits_{s \to + \infty } $ _ix^k_s=w,i∈I.

证明 (i) 由(1)式知,对任意j∈N,序列{l_j^k},{u_j^k}单调有界,所以k趋于无穷大时它们分别收敛于l_j,u_j,且满足l_j¹≤l_j≤u_j≤u_j¹,由j的任意性可证(i).

(ii) 序列{ω^k}∈[l¹,u¹],则该序列至少存在一个聚点w,设{ω^k_s}是收敛于w的一个子列.对于无穷大的s,存在t∈N使得q^k_s=t,且ω_t^k_s∈{l_t^k_s+1,u_t^k_s+1},故

$\omega _t^{{k_s}} \to {{\bar \omega }_t} \in \left\{ {{{\bar l}_t},{{\bar u}_t}} \right\}.$

而由ρ_j及q的定义知,

min{u_t^k_s-ω_t^k_s,ω_t^k_s-l_t^k_s}≥ min{u_j^k_s-ω_j^k_s,ω_j^k_s-l_j^k_s},j∈N.

显然,s→+∞时上述不等式左边趋于0,故右边也趋于0,即ω是盒子[l,u]的拐点.(iii)由(ii)知,w_j∈{l_j,u_j},j∈N.而对任意的i∈I,x_ij^k_s∈[l_j^k_s,u_j^k_s],有

$\omega _j^{{k_s}} - l_j^{{k_s}} = \frac{1}{p}\sum\limits_{i = 1}^p {} (x_{ij}^{{k_s}} - {\rm{ }}l_j^{{k_s}}) \ge \frac{1}{p}(x_{ij}^{{k_s}} - l_j^{{k_s}}) \ge 0.$

则ω_j=l_j时, $\mathop {\lim }\limits_{s \to + \infty } $ x_ij^k_s= $\mathop {\lim }\limits_{s \to + \infty } $ l_j^k_s=ω_j.

同理,ω_j=u_j时, $\mathop {\lim }\limits_{s \to + \infty } $ x_ij^k_s= $\mathop {\lim }\limits_{s \to + \infty } $ u_j^k_s=ω_j. 所以, $\mathop {\lim }\limits_{s \to + \infty } $ x_i^k_s=,i∈I.证毕.

定理1 (i)参数∈=0,则算法有限步终止于问题(P)的最优解x^k,或者产生一个无穷序列{x^k},其任一聚点都是问题(P)的最优解.(ii)若∈>0,则算法有限步终止,并得到问题(P)的一个近似解x^k,且满足

$\begin{array}{l} U{B_k} = \sum\limits_{i = 1}^p {} \frac{{{\rm{ }}c_i^ \top {x^k} + {\alpha _i}}}{{d_i^ \top {x^k} + {\gamma _i}}} \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top x + {\alpha _i}}}{{d_i^ \top x + {\gamma _i}}} + \in ,\\ \forall x \in D. \end{array}$

证明  (i)若算法经过k次迭代终止,结论显然成立;否则,由算法可知,

$LB({X^k}) < U{B_k} \le \frac{{\sum\limits_{i = 1}^p {} c_i^ \top {\omega ^k} + {\alpha _i}}}{{d_i^ \top {\omega ^k} + {\gamma _i}}}.$

(2)

因为序列{UB_k}单调递减且有下界,故存在极限 $\overline {UB} $ ,且{UB_k}的任意子列{UB_ks}收敛于 $\overline {UB} $ . 令ω是{ω^k}的任意聚点,{ω^k_s}是{ω^k}的收敛于ω的子列,则由引理1中的(iii)可知,s→+∞时,

$\begin{array}{l} LB\left( {{X^{{k_s}}}} \right) = g\left( {{y^{{k_s}}}} \right){\rm{ }} = \sum\limits_{i = 1}^p {} {\rm{ }}\frac{{c_i^ \top x_i^{{k_s}} + {\alpha _i}}}{{d_i^ \top x_i^{{k_s}} + {\gamma _i}}} \to \\ \sum\limits_{i = 1}^p {} \frac{{{\rm{ }}c_i^ \top + {\alpha _i}}}{{d_i^ \top \bar \omega + {\gamma _i}}}. \end{array}$

又因为 $\sum\limits_{i = 1}^p {} \frac{{c_i^ \top {\omega ^{{k_s}}} + {\alpha _i}}}{{d_i^ \top {\omega ^{{k_s}}} + {\gamma _i}}} \to \sum\limits_{i = 1}^p {} \frac{{c_i^ \top \bar \omega + {\alpha _i}}}{{d_i^ \top \bar \omega + {\gamma _i}}}$ (s→+∞), 由(2)式可知UB_ks→ $\sum\limits_{i = 1}^p {} \frac{{c_i^ \top \bar \omega + {\alpha _i}}}{{d_i^ \top \bar \omega + {\gamma _i}}}$ (s→+∞), 则 $\sum\limits_{i = 1}^p {} \frac{{c_i^ \top \bar \omega + {\alpha _i}}}{{d_i^ \top \bar \omega + {\gamma _i}}} = \overline {UB} $ . 所以LB(X^k_s), $\frac{{c_i^ \top {\omega ^{{k_s}}} + {\alpha _i}}}{{d_i^ \top {\omega ^{{k_s}}} + {\gamma _i}}}$ 收敛到 $\overline {UB} $ . 假设存在x′∈D满足

$\sum\limits_{i = 1}^p {} \frac{{c_i^ \top x' + {\alpha _i}}}{{d_i^ \top x' + {\gamma _i}}} < \overline {UB} $

(3)

对于任意s,在第k_s次迭代可行解x′属于某个盒子 ${\hat X}$ ∈E_ks,而由X^k_s的选取可知

$LB\left( {{X^{{k_s}}}} \right) \le LB\left( {\hat X} \right) \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top x' + {\alpha _i}}}{{d_i^ \top x' + {\gamma _i}}},$

则有

$\overline {UB} \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top x' + {\alpha _i}}}{{d_i^ \top x' + {\gamma _i}}}$

这与(3)式矛盾,故假设不成立.即有

$\overline {UB} \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top x + {\alpha _i}}}{{d_i^ \top x + {\gamma _i}}},\forall x \in D.$

因为D是紧集,故序列{x^k}的任意聚点x∈D.设{x^k_t}是收敛于x的子列,则

$\mathop {\lim }\limits_{s \to + \infty } U{B_{{k_t}}} = \mathop {\lim }\limits_{s \to + \infty } \sum\limits_{i = 1}^p {} \frac{{{\rm{ }}c_i^ \top {x^{{k_t}}} + {\alpha _i}}}{{d_i^ \top {x^{{k_t}}} + {\gamma _i}}} \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top \bar x + {\alpha _i}}}{{d_i^ \top \bar x + {\gamma _i}}},$

即

$\overline {UB} = \sum\limits_{i = 1}^p {} \frac{{c_i^ \top \bar x + {\alpha _i}}}{{d_i^ \top \bar x + {\gamma _i}}}$

那么对∀x∈D,有

$\sum\limits_{i = 1}^p {} \frac{{c_i^ \top \bar x + {\alpha _i}}}{{d_i^ \top \bar x + {\gamma _i}}} \le \sum\limits_{i = 1}^p {} \frac{{c_i^ \top x + {\alpha _i}}}{{d_i^ \top x + {\gamma _i}}}.$

所以,x是(P)的最优解.

(ii) 由(i)可知, $\mathop {\lim }\limits_{s \to + \infty } $ UB_ks= $\mathop {\lim }\limits_{s \to + \infty } $ LB(X^k_s),根据极限的定义知,一定存在,不妨设k=k_s,满足

$U{B_k} - LB({X^k}) \le \in ,$

所以,对任意x∈D,有

$U{B_k} - \sum\limits_{i = 1}^p {} \frac{{c_i^ \top x + {\alpha _i}}}{{d_i^ \top x + {\gamma _i}}} \le U{B_k} - LB\left( {{X^k}} \right) \le \in $

即有UB_k≤ $\sum\limits_{i = 1}^p {} \frac{{c_i^ \top x + {\alpha _i}}}{{d_i^ \top x + {\gamma _i}}} + \in $ ,∀x∈D.证毕.

3 数值实验

为验证算法的可行性,在AMD A8 CPU(主频 1.9 GHz)4 GB 内存的微机上用Matlab(2012b)进行数值计算.

例1^[2]

$\begin{array}{l} \begin{array}{*{20}{l}} {max\frac{{{a_1}\left( x \right)}}{{{b_1}\left( x \right)}} + \frac{{{a_2}\left( x \right)}}{{{b_2}\left( x \right)}} + \frac{{{a_3}\left( x \right)}}{{{b_3}\left( x \right)}} + \frac{{{a_4}\left( x \right)}}{{{b_4}\left( x \right)}}}\\ {s.t.2{x_1} + {x_2} + 5{x_3} \le 10,} \end{array}\\ {x_1} + 6{x_2} + 3{x_3} \le 10,\\ 5{x_1} + 9{x_2} + 2{x_3} \le 10,\\ 9{x_1} + 7{x_2} + 3{x_3} \le 10,\\ {x_1},{x_2},{x_3} \ge 0. \end{array}$

其中,a₁(x)=4x₁+3x₂+3x₃+50,a₂(x)=3x₁+4x₂+50,a₃(x)=x₁+2x₂+5x₃+50,a₄(x)=x₁+2x₂+4x₃+50, b₁(x)=3x₂+3x₃+50,b₂(x)=4x₁+4x₂+5x₃+50,b₃(x)=x₁+5x₂+5x₃+50,b₄(x)=5x₂+4x₃+50.

取∈=1e-9,得计算结果:运行时间0.8120 s,最优值为4.0907,最优解为(1.1111,0.0000,0.0000),迭代次数为29.

例2^[1]

$\begin{array}{*{20}{l}} {max\frac{{{a_1}\left( x \right)}}{{{b_1}\left( x \right)}} - \frac{{{a_2}\left( x \right)}}{{{b_2}\left( x \right)}} - \frac{{{a_3}\left( x \right)}}{{{b_3}\left( x \right)}} - \frac{{{a_4}\left( x \right)}}{{{b_4}\left( x \right)}}}\\ \begin{array}{l} s.t.6{x_1} + 3{x_2} + 3{x_3} \le 10,\\ 10{x_1} + 3{x_2} + 8{x_3} \le 10,\\ {x_1},{x_2},{x_3} \ge 0. \end{array} \end{array}$

其中,a₁(x)=3x₁+4x₂+50,a₂(x)=3x₁+5x₂+3x₃+50,a₃(x)=x₁+2x₂+4x₃+50,a₄(x)=4x₁+3x₂+3x₃+50, b₁(x)=3x₁+5x₂+4x₃+50,b₂(x)=5x₁+5x₂+4x₃+50,b₃(x)=5x₂+4x₃+50,b₄(x)=3x₂+3x₃+50.

取∈=1e-6,得计算:运行时间0.8580 s,最优值为-1.9,最优解为(0.0000,3.3333,0.0000),迭代次数为32.

数据结果表明,本文算法是可行的.

4 结论

本文提出一种新的分支定界算法求解线性比式和问题(P),先把问题(P)转换成等价问题,再利线性松弛技术建立( ${\tilde P}$ )的线性松弛规划，最后证明了算法的收剑性，并用数值算例验证其有效性.