# A New Linearizing Method for Sum of Linear Ratios Problem with Coefficients

Authors: Hongwei Jiao; Yongqiang Chen
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A new linearizing method is presented for globally solving sum
of linear ratios problem with coefficients. By using the linearizing method, linear relaxation
programming (LRP) of the sum of linear ratios problem with coefficients is established,
which can provide the reliable lower bound of the optimal value of the initial problem. Thus,
a branch and bound algorithm for solving the sum of linear ratios problem with coefficients
is put forward. By successively partitioning the linear relaxation of the feasible region and
solving a series of the LRP, the proposed algorithm is convergent to the global optimal
solution of the initial problem. Compared with the known methods, numerical experimental
results show that the proposed method has the higher computational efficiency in finding the
global optimum of the sum of linear ratios problem with coefficients.


---

## Body

## 1. Introduction

In this paper, we consider the following sum of linear ratios problem with coefficients:(1)
(
SLRC
)
:
{
min
⁡
H
(
x
)
=
∑
j
=
1
p
H
j
(
x
)
=
∑
j
=
1
p
δ
j
t
j
(
x
)
s
j
(
x
)
s
.
t
.
x
∈
D
=
{
x
∈
R
n
∣
A
x
≤
b
,
x
≥
0
}
,
where t
j
(
x
) and s
j
(
x
) are all linear functions, δ
j are all arbitrary real coefficients, j
=
1
,
…
,
p, A
∈
R
m
×
n, b
∈
R
m, and D is a nonempty compact set. Here, symbols δ
j in the problem (SLRC) can be considered the weight of each linear ratio, since δ
j are all arbitrary real numbers; thus the sum of linear ratios with coefficients δ
j can be called the weighted sum and difference of linear ratios. Therefore, the problem (SLRC) considered in this paper popularizes the mathematical model of sum of linear ratios problem investigated in many literatures.The sum of linear ratios problem with coefficients (SLRC) has attracted the interest of researchers and practitioners for many years. In part, this is because the problem (SLRC) and its special case have broad applications in many practical problems, for example, profit rates and pricing decisions problem [1], cluster analysis problem [2], bond portfolio optimization problem [3], and so forth. Another reason for the strong interest in the problem (SLRC) is that from a research point of view the problem (SLRC) poses many important theoretical and computational difficulties. This is mainly because the problem (SLRC) is a global optimization problem; that is, it shows multiple local optimal solutions which are not global optimal solutions.During the past 20 years, many algorithms have been presented for globally solving special cases of the problem (SLRC), which are only developed for solving the sum of linear ratios problem with the assumption that all coefficientsδ
j
=
+
1, j
=
1
,
…
,
p. For example, when feasible region D is a polyhedral set and p
=
2, Konno et al. [4] proposed a parametric simplex method for sum of linear ratios problem without coefficients. When all numerators t
j
(
x
)
≥
0 and all denominators s
j
(
x
)
≥
0, Wang et al. [5] proposed a linear relaxation method for the sum of linear ratios problem without coefficients. When the numerators t
j
(
x
)
≥
0 and the denominators s
j
(
x
)
≠
0, Wang and Shen [6] and Ji et al. [7] presented two different branch and bound algorithms for globally solving the sum of linear ratios problem; Shen and Wang [8] first proposed a global optimization algorithm for the sum of linear ratios problem with coefficients, which is investigated in this paper. Recently, by using the linear characteristics of convex envelope and concave envelope of double variables product function, Gao and Jin [9] proposed an effective branch and bound algorithm for solving sum of linear ratios problem; by using subgradient and convex envelope, Pei and Zhu [10] presented a global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region, which can be used to globally solve the sum of linear ratios problem. However, to our knowledge, although there exist many algorithms to solve special cases of the problem (SLRC), due to its intrinsic difficulty, less theoretical research and algorithm design have been still expanded to globally solving the sum of linear ratios problem with coefficients (SLRC).The purpose of this paper is to develop a new linearizing method for globally solving the sum of linear ratios problem with coefficients (SLRC). The proposed new linearizing method uses more information of the objective function of the problem (SLRC); by using the method, the linear relaxation programming (LRP) of the problem (SLRC) is established, which can provide a tighter lower bound of the global optimal value of the problem (SLRC) than the previous linearizing method in branch and bound algorithm and which can be used to reduce rapidly the growth of branching tree in the branch and bound algorithm for solving the problem (SLRC); therefore it can improve the computational efficiency of the algorithm. By successively subdividing feasible region of the problem (SLRC) and solving a series of the LRP, the proposed algorithm is convergent to the global optimum of the problem (SLRC). Finally, compared with the known methods, numerical experimental results imply that the proposed new linearizing method can be used to globally solve the problem (SLRC) with the higher computational efficiency.The remainder sections of this paper are organized as follows. In Section2, a new linearizing method is proposed; by utilizing the method, the linear relaxation programming (LRP) of the problem (SLRC) is established. In Section 3, a branch and bound algorithm for globally solving the problem (SLRC) is presented. Several test examples in the recent literatures and their numerical results obtained are listed in Section 4. At last, some concluding remarks are described in Section 5.


## 2. New Linearizing Method

To globally solve the problem (SLRC), by solving2
n simple linear programming problems, we obtain easily the initial partitioned rectangle
(2)
X
0
=
{
x
∣
min
⁡
x
∈
D
⁡
x
i
=
x
_
i
≤
x
i
≤
x
¯
i
=
max
⁡
x
∈
D
⁡
x
i
,
i
=
1
,
…
,
n
}
.By the characteristic of fractional functiont
j
(
x
)
/
s
j
(
x
), j
=
1
,
…
,
p, we have the denominator s
j
(
x
)
≠
0; that is, s
j
(
x
)
>
0 or s
j
(
x
)
<
0. If s
j
(
x
)
<
0, by letting t
j
(
x
)
/
s
j
(
x
)
=
-
t
j
(
x
)
/
-
s
j
(
x
), we have -
s
j
(
x
)
>
0. Thus, we can always assume that all denominators s
j
(
x
)
>
0. If t
j
(
x
) is an arbitrary function, then there always exists an enough large positive number σ
j such that t
j
(
x
)
+
σ
j
s
j
(
x
)
>
0; thus we can assume t
j
(
x
)
>
0. Therefore, we can always suppose that t
j
(
x
)
>
0 and s
j
(
x
)
>
0, for all j
=
1
,
…
,
p.The important structure in the establishment of a branch and bound procedure to globally solve the problem (SLRC) is the calculation of lower bounds for this problem and for its subproblems. A lower bound of the global optimal value of the problem (SLRC) and its subproblems can be computed by solving a sequence of linear relaxation programming problems. The proposed new linearizing method for establishing linear relaxation programming of the problem (SLRC) is to underestimate or overestimate each functionH
j
(
x
)
=
t
j
(
x
)
/
s
j
(
x
) with linear functions L
j
(
x
) or U
j
(
x
), j
=
1,2
,
…
,
p. By the former assumption, let
(3)
H
j
(
x
)
=
exp
⁡
⁡
{
ln
⁡
⁡
(
t
j
(
x
)
)
-
ln
⁡
⁡
(
s
j
(
x
)
)
}
.Firstly, for all x
∈
X
⊆
X
0, for each j
∈
{
1
,
…
,
p
}, let
(4)
t
j
l
=
min
⁡
x
∈
X
⁡
t
j
(
x
)
,
t
j
u
=
max
⁡
x
∈
X
⁡
t
j
(
x
)
,
k
j
1
=
ln
⁡
⁡
(
t
j
u
)
-
ln
⁡
⁡
(
t
j
l
)
t
j
u
-
t
j
l
,
s
j
l
=
min
⁡
x
∈
X
⁡
s
j
(
x
)
,
s
j
u
=
max
⁡
x
∈
X
⁡
s
j
(
x
)
,
k
j
2
=
ln
⁡
⁡
(
s
j
u
)
-
ln
⁡
⁡
(
s
j
l
)
s
j
u
-
s
j
l
.LetL
(
ln
⁡
⁡
(
Z
)
) and U
(
ln
⁡
⁡
(
Z
)
) be the linear underestimating function and the linear overestimating function of the ln
⁡
⁡
(
Z
) over the interval [
Z
l
,
Z
u
]. By the linear characteristic of the concave function ln
⁡
⁡
(
Z
), we can get the following inequalities:
(5)
L
(
ln
⁡
⁡
(
Z
)
)
=
k
(
Z
-
Z
l
)
+
ln
⁡
⁡
Z
l
≤
ln
⁡
⁡
(
Z
)
≤
k
Z
-
1
-
ln
⁡
⁡
k
=
U
(
ln
⁡
⁡
(
Z
)
)
,
where
(6)
k
=
ln
⁡
⁡
Z
u
-
ln
⁡
⁡
Z
l
Z
u
-
Z
l
.By the above inequality (5), it follows that
(7)
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
t
j
l
≤
ln
⁡
(
t
j
(
x
)
)
≤
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
k
j
1
,
k
j
2
[
s
j
(
x
)
-
s
j
l
]
+
ln
⁡
⁡
s
j
l
≤
ln
⁡
⁡
(
s
j
(
x
)
)
≤
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
.By the above inequalities (7), for each j
∈
{
1
,
…
,
p
}, then we can establish the underestimating function H
j
l
(
x
) and the overestimating function H
j
u
(
x
) of the function H
j
(
x
) as follows:
(8)
H
j
l
(
x
)
=
exp
⁡
⁡
{
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
}
,
H
j
u
(
x
)
=
exp
⁡
⁡
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
}
.
It is obvious that we have
(9)
H
j
l
(
x
)
≤
H
j
(
x
)
≤
H
j
u
(
x
)
,
for
∀
x
∈
X
⊆
X
0
.Secondly, for all x
∈
X
⊆
X
0, we let
(10)
Z
j
=
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
,
Z
j
u
=
max
⁡
x
∈
X
⁡
{
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
}
,
Z
j
l
=
min
⁡
x
∈
X
⁡
{
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
}
,
A
j
1
=
exp
⁡
⁡
(
Z
j
u
)
-
exp
⁡
⁡
(
Z
j
l
)
Z
j
u
-
Z
j
l
,
Y
j
=
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
,
Y
j
u
=
max
⁡
x
∈
X
⁡
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
}
,
Y
j
l
=
min
⁡
x
∈
X
⁡
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
}
,
A
j
2
=
exp
⁡
⁡
(
Y
j
u
)
-
exp
⁡
⁡
(
Y
j
l
)
Y
j
u
-
Y
j
l
.By the characteristic of the convex function, we can derive its linear underestimating functionL
(
exp
⁡
⁡
(
Z
j
)
) of exp
⁡
⁡
(
Z
j
) over the interval [
Z
j
l
,
Z
j
u
] as follows:
(11)
L
j
(
exp
⁡
⁡
(
Z
j
)
)
=
A
j
1
(
1
+
Z
j
-
ln
⁡
⁡
A
j
1
)
,
such that
(12)
L
j
(
exp
⁡
⁡
(
Z
j
)
)
≤
exp
⁡
⁡
(
Z
j
)
.Based on the above discussion, for eachj
∈
{
1
,
…
,
p
}, by (11)-(12), then finally we can derive the linear underestimating function L
j
(
x
) of H
j
l
(
x
), which underestimates the value of the function H
j
l
(
x
) as follows:
(13)
L
j
(
x
)
=
A
j
1
{
1
+
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
-
ln
⁡
⁡
A
j
1
}
,
such that
(14)
L
j
(
x
)
≤
H
j
l
(
x
)
,
for
∀
x
∈
X
⊆
X
0
.Similarly, for each convex functionexp
⁡
⁡
(
Y
j
) over the interval [
Y
j
l
,
Y
j
u
], we can derive its linear overestimating function U
(
exp
⁡
⁡
(
Y
j
)
) as follows:
(15)
U
j
(
exp
⁡
⁡
(
Y
j
)
)
=
A
j
2
(
Y
j
-
Y
j
l
)
+
exp
⁡
⁡
(
Y
j
l
)
,
such that
(16)
U
j
(
exp
⁡
⁡
(
Y
j
)
)
≥
exp
⁡
⁡
(
Y
j
)
.According to the above discussion, for eachj
∈
{
1
,
…
,
p
}, by (15)-(16), then finally we derive the linear overestimating function U
j
(
x
) of H
j
u
(
x
), which overestimates the optimal value of the function H
j
u
(
x
) as follows:
(17)
U
j
(
x
)
=
A
j
2
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
-
Y
j
l
}
+
exp
⁡
⁡
(
Y
j
l
)
,
such that
(18)
U
j
(
x
)
≥
H
j
u
(
x
)
,
for
∀
x
∈
X
⊆
X
0
.By (9), (14), and (18), we get
(19)
L
j
(
x
)
≤
H
j
l
(
x
)
≤
H
j
(
x
)
≤
H
j
u
(
x
)
≤
U
j
(
x
)
,
for
∀
x
∈
X
⊆
X
0
.Let(20)
H
L
(
x
)
=
∑
j
=
1
,
δ
j
>
0
p
δ
j
L
j
(
x
)
+
∑
j
=
1
,
δ
j
<
0
p
δ
j
U
j
(
x
)
.
Then, by (19), we have
(21)
H
L
(
x
)
=
∑
j
=
1
,
δ
j
>
0
p
δ
j
L
j
(
x
)
+
∑
j
=
1
,
δ
j
<
0
p
δ
j
U
j
(
x
)
≤
∑
j
=
1
p
δ
j
H
j
(
x
)
≤
H
(
x
)
.According to the above linearizing method, for∀
X
⊆
X
0, we can construct the linear relaxation programming (LRP) of the problem (SLRC) over X as follows:
(22)
(
LRP
)
:
{
min
⁡
H
L
(
x
)
s
.
t
.
A
x
≤
b
,
x
≥
0
,
x
∈
X
.According to the construction method of the linear relaxation programming (LRP), for∀
X
⊆
X
0, the problem (
LRP
) provides a valid lower bound for the global optimal value of the problem (
SLRC
).The following theorem ensures that the linear functionH
L
(
x
) will approximate infinitely the corresponding function H
(
x
) as ∥
x
¯
-
x
_
∥
→
0.Theorem 1.
For allx
∈
X
=
[
x
_
,
x
¯
]
⊆
X
0, then one can follow that the error Δ
=
H
(
x
)
-
H
L
(
x
)
→
0 as ∥
x
¯
-
x
_
∥
→
0.Proof.
Let(23)
Δ
j
1
=
t
j
(
x
)
s
j
(
x
)
-
L
j
(
x
)
,
Δ
j
2
=
U
j
(
x
)
-
t
j
(
x
)
s
j
(
x
)
.
Then, we have
(24)
Δ
=
H
(
x
)
-
H
L
(
x
)
=
(
∑
j
=
1
p
δ
j
t
j
(
x
)
s
j
(
x
)
‍
)
-
(
∑
j
=
1
,
δ
j
>
0
p
δ
j
L
j
(
x
)
‍
+
∑
j
=
1
,
δ
j
<
0
p
δ
j
U
j
(
x
)
‍
)
=
∑
j
=
1
,
δ
j
>
0
p
δ
j
(
t
j
(
x
)
s
j
(
x
)
-
L
j
(
x
)
)
‍
-
∑
j
=
1
,
δ
j
<
0
p
δ
j
(
U
j
(
x
)
-
t
j
(
x
)
s
j
(
x
)
)
=
∑
j
=
1
,
δ
j
>
0
p
δ
j
Δ
j
1
‍
-
∑
j
=
1
,
δ
j
<
0
p
δ
j
Δ
j
2
‍
.
Firstly, in the following, we will prove that Δ
j
1
→
0 as ∥
x
¯
-
x
_
∥
→
0. Since
(25)
Δ
j
1
=
[
H
j
(
x
)
-
H
j
l
(
x
)
]
+
[
H
j
l
(
x
)
-
L
j
(
x
)
]
=
Δ
j
1
1
+
Δ
j
2
1
,
then we only need to prove that Δ
j
1
1
→
0 and Δ
j
2
1
→
0 as ∥
x
¯
-
x
_
∥
→
0.
Let(26)
f
j
(
x
)
=
ln
⁡
(
t
j
(
x
)
)
-
ln
⁡
(
s
j
(
x
)
)
,
g
j
(
x
)
=
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
,
h
j
(
x
)
=
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
.
Then, we have(27)
Δ
j
1
1
=
exp
⁡
⁡
{
ln
⁡
⁡
(
t
j
(
x
)
)
-
ln
⁡
⁡
(
s
j
(
x
)
)
}
-
exp
⁡
⁡
{
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
}
=
exp
⁡
⁡
(
f
j
(
x
)
)
-
exp
⁡
⁡
(
h
j
(
x
)
)
≤
∥
f
j
(
x
)
-
h
j
(
x
)
∥
sup
⁡
ξ
j
∈
L
(
f
j
(
x
)
,
h
j
(
x
)
)
⁡
exp
⁡
⁡
(
ξ
j
)
,
where
(28)
L
(
f
j
(
x
)
,
h
j
(
x
)
)
=
α
f
j
(
x
)
+
(
1
-
α
)
h
j
(
x
)
with
α
∈
[
0,1
]
.
Let(29)
f
j
(
x
)
-
h
j
(
x
)
=
{
ln
⁡
⁡
(
t
j
(
x
)
)
-
ln
⁡
⁡
(
s
j
(
x
)
)
}
-
{
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
}
=
{
ln
⁡
⁡
(
t
j
(
x
)
)
-
[
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
]
}
+
{
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
-
ln
⁡
⁡
(
s
j
(
x
)
)
}
=
Δ
j
1.1
1
+
Δ
j
1.2
1
.
SinceΔ
j
1.1
1
=
ln
⁡
⁡
(
t
j
(
x
)
)
-
[
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
t
j
l
] is a concave function about t
j
(
x
), we know that Δ
j
1.1
1 can attain the maximum Δ
j
1.1
1
.
max
⁡ at the point t
j
(
x
)
=
1
/
k
j
1. Let u
j
=
t
j
u
/
t
j
l; then through computing, we can derive
(30)
Δ
j
1.1
1
.
max
⁡
=
ln
⁡
⁡
u
j
u
j
-
1
-
1
-
ln
⁡
⁡
ln
⁡
⁡
u
j
u
j
-
1
.
Since u
j
→
1 as ∥
x
¯
-
x
_
∥
→
0, then we have Δ
j
1.1
1
.
max
⁡
→
0 as ∥
x
¯
-
x
_
∥
→
0.
SinceΔ
j
1.2
1
=
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
-
ln
⁡
⁡
(
s
j
(
x
)
) is a convex function about s
j
(
x
), it can attain the maximum Δ
j
1.2
1
.
max
⁡ at the points s
j
u or s
j
l. Let v
j
=
s
j
u
/
s
j
l; then through computing, we can derive
(31)
Δ
j
1.2
1
.
max
⁡
=
ln
⁡
⁡
v
j
v
j
-
1
-
1
-
ln
⁡
⁡
ln
⁡
⁡
v
j
v
j
-
1
.
Since v
j
→
1 as ∥
x
¯
-
x
_
∥
→
0, then we have Δ
j
1.2
1
.
max
⁡
→
0 as ∥
x
¯
-
x
_
∥
→
0.
Therefore, we have(32)
∥
f
j
(
x
)
-
h
j
(
x
)
∥
=
∥
Δ
j
1.1
1
+
Δ
j
1.2
1
∥
≤
∥
Δ
j
1.1
1
∥
+
∥
Δ
j
1.2
1
∥
.
By the above proof, we have(33)
∥
f
j
(
x
)
-
h
j
(
x
)
∥
⟶
0
,
as
∥
x
¯
-
x
_
∥
⟶
0
.
Since exp
⁡
⁡
(
ξ
j
) is a continuous and bounded function about variable x and by the above (27) and (33), we have
(34)
Δ
j
1
1
⟶
0
,
as
∥
x
¯
-
x
_
∥
⟶
0
.
Next, we consider the differenceΔ
j
2
1, and it follows that
(35)
Δ
j
2
1
=
H
j
l
(
x
)
-
L
j
(
x
)
=
exp
⁡
⁡
{
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
(
t
j
l
)
-
[
k
j
2
s
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
2
]
}
-
A
j
1
{
1
+
k
j
1
[
t
j
(
x
)
-
t
j
l
]
+
ln
⁡
⁡
(
t
j
l
)
-
[
k
j
2
(
s
j
(
x
)
)
-
1
-
ln
⁡
⁡
k
j
2
]
-
ln
⁡
⁡
A
j
1
}
=
exp
⁡
(
Z
j
)
-
A
j
1
{
1
+
Z
j
-
ln
⁡
A
j
1
}
.
Since Δ
j
2
1 is a convex function about Z
j, for any Z
j
∈
[
Z
j
l
,
Z
j
u
] defined in the former, then it follows that Δ
j
2
1 can obtain the maximum Δ
j
2
1
.
max
⁡ at the points Z
j
l or Z
j
u. Let
(36)
R
j
=
exp
⁡
⁡
(
Z
j
u
-
Z
j
l
)
-
1
Z
j
u
-
Z
j
l
.
Then, through computing, we can follow that
(37)
Δ
j
2
1
.
max
⁡
=
Δ
j
2
1
(
Z
j
l
)
=
Δ
j
2
1
(
Z
j
u
)
=
exp
⁡
⁡
(
Z
j
l
)
(
1
-
R
j
+
R
j
ln
⁡
⁡
R
j
)
.
Since R
j
→
1 as |
Z
j
u
-
Z
j
l
|
→
0 and |
Z
j
u
-
Z
j
l
|
→
0 as ∥
x
¯
-
x
_
∥
→
0, it is obvious that Δ
j
2
1
.
max
⁡
→
0 as ∥
x
¯
-
x
_
∥
→
0. Therefore, we have Δ
j
2
1
→
0 as ∥
x
¯
-
x
_
∥
→
0.
Secondly, we will prove that Δ
j
2
→
0 as ∥
x
¯
-
x
_
∥
→
0. Since
(38)
Δ
j
2
=
[
U
j
(
x
)
-
H
j
u
(
x
)
]
+
[
H
j
u
(
x
)
-
H
j
(
x
)
]
=
Δ
j
1
2
+
Δ
j
2
2
,
then we only need to prove that Δ
j
1
2
→
0 and Δ
j
2
2
→
0 as ∥
x
¯
-
x
_
∥
→
0. Thus,
(39)
Δ
j
1
2
=
U
j
(
x
)
-
H
j
u
(
x
)
=
A
j
2
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
-
Y
j
l
}
+
exp
⁡
⁡
(
Y
j
l
)
-
exp
⁡
⁡
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
}
=
A
j
2
(
Y
j
-
Y
j
l
)
+
exp
⁡
⁡
(
Y
j
l
)
-
exp
⁡
⁡
(
Y
j
)
.
Since Δ
j
1
2 is a concave function about Y
j, for any Y
j
∈
[
Y
j
l
,
Y
j
u
] defined in the former, then it follows that Δ
j
1
2 can obtain the maximum Δ
j
1
2
.
max
⁡ at the points ln
⁡
(
A
j
2
). Let
(40)
W
j
=
exp
⁡
⁡
(
Y
j
u
-
Y
j
l
)
-
1
Y
j
u
-
Y
j
l
.
Then, through computing, we can get
(41)
Δ
j
1
2
.
max
⁡
=
exp
⁡
⁡
(
Y
j
l
)
(
1
-
W
j
+
W
j
ln
⁡
W
j
)
.
Since W
j
→
1 as |
Y
j
u
-
Y
j
l
|
→
0 and |
Y
j
u
-
Y
j
l
|
→
0 as ∥
x
¯
-
x
_
∥
→
0, it is obvious that Δ
j
1
2
.
max
⁡
→
0 as ∥
x
¯
-
x
_
∥
→
0. Therefore, we have Δ
j
1
2
→
0 as ∥
x
¯
-
x
_
∥
→
0.
Thus,(42)
Δ
j
2
2
=
H
j
u
(
x
)
-
H
j
(
x
)
=
exp
⁡
⁡
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
}
-
exp
⁡
⁡
{
ln
⁡
⁡
(
t
j
(
x
)
)
-
ln
⁡
⁡
(
s
j
(
x
)
)
}
=
exp
⁡
⁡
(
g
j
(
x
)
)
-
exp
⁡
⁡
(
f
j
(
x
)
)
≤
∥
g
j
(
x
)
-
f
j
(
x
)
∥
sup
⁡
η
j
∈
L
(
g
j
(
x
)
,
f
j
(
x
)
)
exp
⁡
(
η
j
)
,
where
(43)
L
(
g
j
(
x
)
,
f
j
(
x
)
)
=
β
g
j
(
x
)
+
(
1
-
β
)
f
j
(
x
)
with
β
∈
[
0,1
]
.
Let(44)
g
j
(
x
)
-
f
j
(
x
)
=
{
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
-
k
j
2
[
s
j
(
x
)
-
s
j
l
]
-
ln
⁡
⁡
s
j
l
}
-
{
ln
⁡
⁡
(
t
j
(
x
)
)
-
ln
⁡
⁡
(
s
j
(
x
)
)
}
=
{
[
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
k
j
1
]
-
ln
⁡
(
t
j
(
x
)
)
}
+
{
ln
⁡
⁡
(
s
j
(
x
)
)
-
[
k
j
2
[
s
j
(
x
)
-
s
j
l
]
+
ln
⁡
⁡
s
j
l
]
}
=
Δ
j
2.1
2
+
Δ
j
2.2
2
.
SinceΔ
j
2.1
2
=
[
k
j
1
t
j
(
x
)
-
1
-
ln
⁡
⁡
k
j
1
]
-
ln
⁡
⁡
(
t
j
(
x
)
) is a convex function about t
j
(
x
), it can attain the maximum Δ
j
2.1
2
.
max
⁡ at the points t
j
u or t
j
l. Then, through computing, we derive
(45)
Δ
j
1.1
2
.
max
⁡
=
ln
⁡
⁡
u
j
u
j
-
1
-
1
-
ln
⁡
⁡
ln
⁡
⁡
u
j
u
j
-
1
.
Since u
j
→
1 as ∥
x
¯
-
x
_
∥
→
0, then we have Δ
j
2.1
2
.
max
⁡
→
0 as ∥
x
¯
-
x
_
∥
→
0.
SinceΔ
j
2.2
2
=
ln
⁡
⁡
(
s
j
(
x
)
)
-
[
k
j
2
[
s
j
(
x
)
-
s
j
l
]
+
ln
⁡
s
j
l
] is a concave function about s
j
(
x
), we can get the fact that Δ
j
2.2
2 can attain the maximum Δ
j
2.2
2
.
max
⁡ at the point s
j
(
x
)
=
1
/
k
j
2. Then, through computing, we derive
(46)
Δ
j
2.2
2
.
max
⁡
=
ln
⁡
⁡
v
j
v
j
-
1
-
1
-
ln
⁡
⁡
ln
⁡
⁡
v
j
v
j
-
1
.
Since v
j
→
1 as ∥
x
¯
-
x
_
∥
→
0, then we have Δ
j
2.2
2
.
max
⁡
→
0 as ∥
x
¯
-
x
_
∥
→
0.
Therefore, we have(47)
∥
g
j
(
x
)
-
f
j
(
x
)
∥
=
∥
Δ
j
2.1
2
+
Δ
j
2.2
2
∥
≤
∥
Δ
j
2.1
2
∥
+
∥
Δ
j
2.2
2
∥
.
By the above proof, we have
(48)
∥
g
j
(
x
)
-
f
j
(
x
)
∥
⟶
0
,
as
∥
x
¯
-
x
_
∥
⟶
0
.
Sinceexp
⁡
⁡
(
η
j
) is a continuous and bounded function about variable x and by (42) and (48), we have
(49)
Δ
j
2
2
⟶
0
,
as
∥
x
¯
-
x
_
∥
⟶
0
.
By the above proof, we can follow that(50)
Δ
j
2
=
[
U
j
(
x
)
-
H
j
u
(
x
)
]
+
[
H
j
u
(
x
)
-
H
j
(
x
)
]
=
Δ
j
1
2
+
Δ
j
2
2
,
⟶
0
as
∥
x
¯
-
x
_
∥
⟶
0
.
Therefore,(51)
Δ
=
H
(
x
)
-
H
L
(
x
)
=
∑
j
=
1
,
δ
j
>
0
p
δ
j
Δ
j
1
-
∑
j
=
1
,
δ
j
<
0
p
δ
j
Δ
j
2
⟶
0
as
∥
x
¯
-
x
_
∥
⟶
0
.
By the above discussion, it is obvious that the conclusion is followed.


## 3. Algorithm and Its Convergence

In this section, based on the former new linearizing method, we present an effective branch and bound algorithm for globally solving the sum of linear ratios problem with coefficients (SLRC). The critical construction in ensuring that the proposed branch and bound algorithm is convergent to the global optimum of the problem (SLRC) is the selection of a reasonable branching rule. In this paper, we use a standard branching rule which is called bisection. The selected branching rule is described as follows.Assume that the hyperrectangleX
k
=
[
x
_
k
,
x
¯
k
]
⊆
X
0 is a node subproblem identified, select ρ
∈
argmax
{
x
¯
i
k
-
x
_
i
k
:
i
=
1
,
…
,
n
}, and subdivide X
k by partitioning the maximum edge of the interval [
x
_
ρ
k
,
x
¯
ρ
k
] into the two subintervals [
x
_
ρ
k
,
(
x
_
ρ
k
+
x
¯
ρ
k
)
/
2
] and [
(
x
_
ρ
k
+
x
¯
ρ
k
)
/
2
,
x
¯
ρ
k
].Assume thatL
B
(
X
k
) is the optimal value of the LRP(X
k) and x
k
=
x
(
X
k
) is the corresponding optimal solution of the LRP(X
k). The steps of the proposed algorithm are as follows.Step 1.
Set the initial convergence toleranceɛ
>
0, the initial number of iteration k
:
=
0, and the set of initial active node Ξ
0
=
X
0. Let the initial upper bound U
B
0
=
+
∞ and the initial feasible point set Θ
:
=
∅.
CalculateL
B
0
:
=
L
B
(
X
0
) and x
0
=
x
(
X
0
) by solving the LRP over X
0; if x
0 is feasible to the problem (SLRC), update the feasible point set Θ and the upper bound U
B
0, if necessary. If U
B
0
-
L
B
0
≤
ɛ, then the algorithm stops with x
0 being the global optimal solution of the problem (SLRC); otherwise, continue the following Step 2.Step 2.
Subdivide hyperrectangleX
k into two new sub-hyper-rectangles by utilizing the proposed branching rule and denote the set of new partitioned subrectangles as X
¯
k.Step 3.
For everyX
∈
X
¯
k, calculate L
B
(
X
) and x
(
X
) by solving the LRP over X. If L
B
(
X
)
>
U
B
k, then let X
¯
k
:
=
X
¯
k
∖
X; if x
(
X
) is feasible to the problem (SLRC), then update feasible point set Θ, the upper bound U
B
k, and the best known feasible point x
k, if necessary, and let Ξ
k
=
(
Ξ
k
∖
X
)
∪
X
¯
k and update the lower bound L
B
k
=
inf
⁡
X
∈
Ξ
k
L
B
(
X
).Step 4.
LetΞ
k
+
1
=
Ξ
k
∖
{
X
:
U
B
k
-
L
B
(
X
)
≤
ɛ
,
X
∈
Ξ
k
}. If Ξ
k
+
1
=
∅, then the algorithm stops with U
B
k being the global ϵ-optimal value for the problem (SLRC) and x
k being a global optimization solution for the problem (SLRC). Otherwise, let k
:
=
k
+
1, select subrectangle X
k satisfying X
k
=
arg
min
⁡
X
∈
Ξ
k
L
B
(
X
), and return to Step 2.Theorem 2.
The above proposed algorithm either stops finitely with the global optimal solution for the problem (SLRC) or generates an infinite sequence of iterations{
x
k
}, the limitation point of which will be the global optimal solution for the problem (SLRC).Proof.
If the proposed algorithm stops finitely at iterationk, then, when the algorithm stops, we obtain U
B
k
=
v
*
=
L
B
k, where v
* is the global optimal value of the problem (SLRC). Thus, by the structure of the proposed algorithm, we know that x
k must be a global optimal solution for the problem (SLRC).
If the proposed algorithm generates an infinite sequence of partitioned subrectangles{
X
k
}, then, by exhaustiveness of the branching method, we know that the sequence {
X
k
} must shrink to a singleton. By the design of the proposed algorithm we can follow that the sequence {
U
B
k
} is nonincreasing, and the sequence {
L
B
k
} is nondecreasing; thus, the sequence {
U
B
k
-
L
B
k
} is nonincreasing. In conclusion, we can get the fact that the bounding operation is consistent and that the selection operation is bound improving; thus, by Theorem IV.3. in [11], we can follow easily that the sequence {
U
B
k
-
L
B
k
} must converge to zero. Since L
B
k
≤
v
*
≤
U
B
k, this shows that lim
⁡
k
→
∞
U
B
k
=
v
*. Since U
B
k
=
H
(
x
k
), any cluster point x
* of the sequence {
x
k
} is a feasible point for the problem (SLRC) with the objective function value H
(
x
*
). Therefore, the conclusion is followed.


## 4. Numerical Examples

To verify the reliability and effectiveness of the proposed new linearizing method, several test examples that appeared in the recent literatures are implemented on an Intel(R) Core(TM)2 Duo CPU (1.58 GHZ) microcomputer. The proposed algorithm using the new linearizing method is coded in C++ and every linear relaxation programming problem is solved by simplex method. These test examples and their numerical results are described as follows.Example 1 (see [9]).
We have the following:(52)
min
⁡
37
x
1
+
73
x
2
+
13
13
x
1
+
13
x
2
+
13
+
63
x
1
-
18
x
2
+
39
13
x
1
+
26
x
2
+
13
s
.
t
.
x
x
5
x
1
-
3
x
2
=
3
,
s
.
t
.
x
x
1.5
≤
x
1
≤
3
.
Withϵ
=
1
0
-
4, using the method proposed in this paper, the optimal solution is (
x
1
,
x
2
)
=
(
1.500000000,1.500000000
), the global ϵ-optimal value is 4.912587413, the number of algorithm iterations is 29, the maximal number of algorithm active nodes necessary is 9, and the computational time is 0.12715 seconds.
Using the method in [9], with ϵ
=
1
0
-
4, the optimal solution is (
x
1
,
x
2
)
=
(
1.5000,1.5000
), the global ϵ-optimal value is 4.9125, the number of algorithm iterations is 113, and the computational time is 201.626020 seconds.Example 2 (see [6]).
We have the following:(53)
max
⁡
37
x
1
+
73
x
2
+
13
13
x
1
+
13
x
2
+
13
+
63
x
1
-
18
x
2
+
39
13
x
1
+
26
x
2
+
13
s
.
t
.
x
x
5
x
1
-
3
x
2
=
3
,
s
.
t
.
x
x
1.5
≤
x
1
≤
3
.
Withϵ
=
1
0
-
4, using the method proposed in this paper, the optimal solution is (
x
1
,
x
2
)
=
(
3.000000000,4.000000000
), the global ϵ-optimal value is 5.000000000, the number of algorithm iterations is 59, the maximal number of algorithm active nodes necessary is 19, and the computational time is 0.25843 seconds.
But, using the method in [6], with ϵ
=
1
0
-
4, the optimal solution is (
x
1
,
x
2
)
=
(
3,4
), the global ϵ-optimal value is 5, the number of algorithm iterations is 32, the maximal number of algorithm active nodes necessary is 32, and the computational time is 1.089285 seconds.Example 3 (see [10]).
We have the following:(54)
max
⁡
3
x
1
+
5
x
2
+
3
x
3
+
50
3
x
1
+
4
x
2
+
5
x
3
+
50
+
3
x
1
+
5
x
2
+
50
3
x
1
+
5
x
2
+
3
x
3
+
50
max
⁡
+
4
x
1
+
2
x
2
+
4
x
3
+
50
5
x
1
+
4
x
2
+
3
x
3
+
50
s
.
t
.
x
x
6
x
1
+
3
x
2
+
3
x
3
≤
10
,
s
.
t
.
x
x
10
x
1
+
3
x
2
+
8
x
3
≤
10
,
s
.
t
.
x
x
x
1
,
x
2
,
x
3
≥
0
.
Withϵ
=
1
0
-
5, using the proposed method in this paper, the optimal solution is (
x
1
,
x
2
,
x
3
)
=
(
0.000000000,0.000000000,0.000000000
), the global ϵ-optimal value is 3.000000000, the number of algorithm iterations is 37, the maximal number of algorithm active nodes necessary is 10, and the computational time is 0.109402 seconds.Using the method in [10], with ϵ
=
1
0
-
5, the optimal solution is (
x
1
,
x
2
,
x
3
)
=
(
0.0013,1.6725,0.0000
), the global ϵ-optimal value is 3.0009, the number of algorithm iterations is 1033, the maximal number of algorithm active nodes necessary is 200, and the computational time is 99.3570 seconds.Example 4 (see [10]).
We have the following:(55)
max
⁡
4
x
1
+
3
x
2
+
3
x
3
+
50
3
x
2
+
3
x
3
+
50
+
3
x
1
+
4
x
2
+
50
4
x
1
+
4
x
2
+
5
x
3
+
50
max
⁡
+
x
1
+
2
x
2
+
5
x
3
+
50
x
1
+
5
x
2
+
5
x
3
+
50
max
⁡
+
x
1
+
2
x
2
+
4
x
3
+
50
5
x
2
+
4
x
3
+
50
s
.
t
.
x
x
2
x
1
+
x
2
+
5
x
3
≤
10
,
s
.
t
.
x
x
x
1
+
6
x
2
+
3
x
3
≤
10
,
s
.
t
.
x
x
5
x
1
+
9
x
2
+
2
x
3
≤
10
,
s
.
t
.
x
x
9
x
1
+
7
x
2
+
3
x
3
≤
10
,
s
.
t
.
x
x
x
1
,
x
2
,
x
3
≥
0
.
Withϵ
=
1
0
-
5, using the proposed method in this paper, the optimal solution is (
x
1
,
x
2
,
x
3
)
=
(
1.111111111,0.000000000,0.000000000
), the global ϵ-optimal value is 4.090702948, the number of algorithm iterations is 21, the maximal number of algorithm active nodes necessary is 3, and the computational time is 0.0831093 seconds.
Using the method in [10], with ϵ
=
1
0
-
5, the optimal solution is (
x
1
,
x
2
,
x
3
)
=
(
0.0013,0.0000,0.0000
), the global ϵ-optimal value is 4.0001, the number of algorithm iterations is 1640, the maximal number of algorithm active nodes necessary is 233, and the computational time is 120.6355 seconds.
By substituting verification, we know that the global optimal solutions of Examples3 and 4 obtained using our algorithm are feasible and correct and the global optimal values of Examples 3 and 4 obtained using our algorithm are correct. From the above comparison, we know that the optimal solutions and optimal values for Examples 3 and 4 using our method are much better than those in the literature [10]; that is, using our algorithm, we can obtain the more accurate global optimal solution.
From numerical results for Examples1–4, the proposed new linearizing method can be used to globally solve the problem (SLRC) with the higher computational efficiency.


## 5. Some Extensions

The new linearizing method used for solving the problem (SLRC) can be extended to seek a global optimal solution of the sum of linear ratios problem with coefficients whose domain is not linear. Some extensions are given as follows.When domainD is convex set, by solving 2
n simple convex programming problems, we obtain easily the initial rectangle X
0. For any X
∈
X
0, utilize the presented linearizing method to construct linear underestimating function of the sum of linear fractional function, so that we can establish a convex relaxation programming problem of the problem (SLRC) over X. Use the algorithm proposed in Section 3, at each iteration, and solve convex relaxation programming subproblems rather than linear relaxation programming subproblems; we can globally solve the problem (SLRC) over convex set.When constraint functions of the problem (SLRC) are also sum of linear fractional functions with coefficients, whose mathematical modeling can be reformulated as follows:(56)
(
SLRC
1
)
:
{
min
⁡
H
0
(
x
)
=
∑
q
=
1
T
0
‍
δ
0
q
t
0
q
(
x
)
s
0
q
(
x
)
s
.
t
.
H
σ
(
x
)
=
∑
q
=
1
T
σ
‍
δ
σ
q
t
σ
q
(
x
)
s
σ
q
(
x
)
≤
B
σ
,
x
x
x
x
x
x
x
x
x
σ
=
1,2
,
…
,
M
,
x
∈
D
=
{
x
∈
R
n
∣
A
x
≤
b
,
x
≥
0
}
,
where t
σ
q
(
x
) and s
σ
q
(
x
) are all linear affine functions, δ
σ
q are all arbitrary real coefficients, σ
=
1,2
,
…
,
M, A
∈
R
m
×
n, b
∈
R
m, B
∈
R
M, and D is a nonempty compact set.Using the linearizing method proposed in Section2 to construct the linear underestimating function H
σ
L
(
x
) of each function H
σ
(
x
), σ
=
1,2
,
…
,
M, we can establish the linear relaxation programming (LRP1) of the problem (SLRC1) over X as follows:
(57)
(
LRP
1
)
:
{
min
⁡
H
0
L
(
x
)
s
.
t
.
H
σ
L
(
x
)
≤
B
σ
,
σ
=
1,2
,
…
,
M
,
A
x
≤
b
,
x
≥
0
,
x
∈
X
⊆
X
0
.Using the same algorithm step in Section3, at each iteration, and solving linear relaxation programming subproblem (LRP1), we can globally solve the sum of linear ratios problem (SLRC1) with sum of linear ratios constraints. To verify the feasibility of the proposed new linearizing method, two test examples are implemented on a microcomputer; test examples and their computational results are given as follows.Example 5.
We have the following:(58)
min
⁡
x
1.6
×
∑
i
=
1
N
x
i
+
1
∑
i
=
1
N
x
i
+
2
+
2.3
×
∑
i
=
1
N
x
i
+
2
∑
i
=
1
N
x
i
+
3
-
3.1
s
.
t
.
x
x
×
∑
i
=
1
N
x
i
+
5
∑
i
=
1
N
x
i
+
4
-
4.2
×
∑
i
=
1
N
x
i
+
6
∑
i
=
1
N
x
i
+
5
s
.
t
.
x
x
x
∑
j
=
2
5
∑
i
=
1
N
x
i
+
j
∑
i
=
1
N
x
i
+
j
+
1
≤
3.61
,
s
.
t
.
x
x
∑
j
=
3
6
∑
i
=
1
N
x
i
+
j
∑
i
=
1
N
x
i
+
j
+
1
≤
3.76
,
s
.
t
.
x
x
∑
j
=
4
7
∑
i
=
1
N
x
i
+
j
∑
i
=
1
N
x
i
+
j
+
1
≤
3.83
,
s
.
t
.
x
x
∑
j
=
5
8
∑
i
=
1
N
x
i
+
j
∑
i
=
1
N
x
i
+
j
+
1
≤
3.86
,
s
.
t
.
x
x
1.0
≤
x
i
≤
3.0
,
i
=
1,2
,
…
,
N
,
where N
=
4.Withϵ
=
1
0
-
8, using the proposed method in this paper, the global optimal solution is (
x
1
,
x
2
,
x
3
,
x
4
)
=
(
1.000000000,1.000000000,1.000000000,1.000000000
), the global ϵ-optimal value is −4.849404762, the number of algorithm iterations is 181, and the maximal number of algorithm active nodes necessary is 64.Example 6.
We have the following:(59)
min
⁡
xx
2
x
1
+
x
2
-
x
3
+
x
4
+
1
x
1
+
2
x
2
-
x
3
+
x
4
+
2
s
.
t
.
x
x
+
x
1
+
2
x
2
-
x
3
+
x
4
+
2
2
x
1
+
2
x
2
+
x
3
+
x
4
+
3
s
.
t
.
x
x
-
x
1
+
x
2
+
3
x
3
+
x
4
+
5
x
1
+
2
x
2
+
3
x
3
+
x
4
+
4
s
.
t
.
x
x
-
1.5
x
1
-
x
2
+
1.5
x
3
+
x
4
+
6
1.4
x
1
-
x
2
+
2.5
x
3
+
1.6
x
4
+
5
s
.
t
.
xx
2
x
1
-
x
2
+
3
x
3
+
x
4
+
2
x
1
+
3
x
2
+
x
3
+
3
x
4
+
3
s
.
t
.
x
x
+
2
x
1
+
x
2
+
4
x
3
+
x
4
+
3
x
1
+
4
x
2
-
x
3
+
5
x
4
+
4
s
.
t
.
x
x
-
x
1
+
2
x
2
+
x
3
+
3
x
4
+
4
1.5
x
1
+
x
2
+
3.5
x
3
+
x
4
+
5
s
.
t
.
x
x
+
x
1
+
2
x
2
+
x
3
+
x
4
+
5
2
x
1
-
x
2
+
1.3
x
3
+
x
4
+
6
≤
1.55
,
s
.
t
.
x
x
x
1
+
2
x
2
+
2
x
3
-
x
4
+
3
2
x
1
-
x
2
+
2
x
3
+
x
4
+
4
s
.
t
.
x
x
+
3
x
1
+
x
2
+
4
x
3
+
x
4
+
4
x
1
+
4
x
2
-
x
3
+
5
x
4
+
5
s
.
t
.
x
x
+
1.4
x
1
-
x
2
+
1.5
x
3
+
x
4
+
5
1.5
x
1
+
x
2
+
1.7
x
3
+
2
x
4
+
6
s
.
t
.
x
x
-
2
x
1
-
x
2
+
2
x
3
+
2
x
4
+
7
x
1
+
3
x
2
+
4
x
3
+
3
x
4
+
6
≤
3
.
15
,
s
.
t
.
x
x
2
x
1
-
x
2
+
2
x
3
+
2
x
4
+
4
3
x
1
+
2
x
2
+
x
3
+
4
x
4
+
5
s
.
t
.
x
x
-
x
1
-
x
2
+
2
x
3
+
3
x
4
+
5
x
1
+
x
2
+
3
x
3
+
4
x
4
+
6
s
.
t
.
x
x
+
x
1
+
x
2
+
x
3
+
x
4
+
6
2
x
1
+
2
x
2
+
4
x
3
+
3
x
4
+
7
s
.
t
.
x
x
+
x
1
+
x
2
+
2
x
3
+
x
4
+
7.6
x
1
+
2
x
2
+
x
3
+
x
4
+
8.5
≤
3.85
,
s
.
t
.
x
x
x
1
-
3
x
2
+
x
3
+
2
x
4
+
5
x
1
-
2
x
2
+
2
x
3
+
3
x
4
+
6
s
.
t
.
x
x
+
2.1
x
1
-
x
2
+
x
3
+
x
4
+
6
x
1
+
2
x
2
+
2
x
3
+
x
4
+
7
s
.
t
.
x
x
+
x
1
+
2
x
2
+
2
x
3
+
3
x
4
+
7
x
1
+
2
x
2
+
3
x
3
+
3
x
4
+
8
s
.
t
.
x
x
+
1.5
x
1
-
x
2
+
x
3
+
x
4
+
8
1.6
x
1
+
x
2
-
x
3
+
2
x
4
+
9
≤
3.88
,
s
.
t
.
x
x
1.0
≤
x
1
,
x
2
,
x
3
,
x
4
≤
3.0
.
Withϵ
=
1
0
-
8, using the proposed method in this paper, the global optimal solution is (
x
1
,
x
2
,
x
3
,
x
4
)
=
(
1.000000000,1.000000000,3.000000000,1.000000000
), the global ϵ-optimal value is −0.888192268, the number of algorithm iterations is 98, and the maximal number of algorithm active nodes necessary is 18.
From numerical results for Examples5–6, the proposed new linearizing method can be extended to globally solve the problem (SLRC) with the weighted sum of linear fractional functions constraints.
It should also be noted that our approach could be extended to solve more general generalized linear fractional programming problems; this will constitute a subject for future research.


## 6. Concluding Remarks

In this paper, by utilizing the linear approximation of exponential and logarithmic functions, a new linearizing method is presented. Combining the linearizing method within the branch and bound scheme, a branch and bound algorithm is constructed for solving the problem (SLRC). By subsequently partitioning linear relaxation of the feasible region and solving a series of linear programming problems, the proposed algorithm is convergent to a global optimal solution of the problem (SLRC). Compared with the known methods, numerical experimental results show that the proposed new linearizing method can be used to globally solve the problem (SLRC) with the higher computational efficiency.



---

*Source: 490297-2014-03-26.xml*