Dinkelbach复杂度分析.pdf
需积分: 0 119 浏览量
2024-01-22
20:53:43
上传
评论
收藏 126KB PDF 举报
An Analysis of Dinkelbach's Algorithm
for
0-1 Fractional Programming Problems
Tomomi MATSUI * Yasufumi SARUWATARI
y
Maiko SHIGENO
z
(METR92-14, December 1992 )
* Department of Mathematical Engineering and Information Physics
Faculty of Engineering, UniversityofTokyo
Bunkyo-ku, Tokyo 113, Japan
y
Department of So cial Sciences
The National Defense Academy
Hashirimizu, Yokosuka, Kanagawa 239, Japan
z
Department of Management Science
Science UniversityofTokyo
Kagurazaka, Shinjuku-ku, Tokyo 162, Japan
Abstract:
The 0-1 fractional programming problem minimizes the fractional ob-
jective function (
c
1
x
1
+
c
2
x
2
+
111
+
c
n
x
n
)
=
(
d
1
x
1
+
d
2
x
2
+
111
+
d
n
x
n
)=
cx
=
dx
un-
der the condition that
x
=(
x
1
;
111
;x
n
)
2
f
0
;
1
g
n
;
where is the set of
feasible solutions. For a fractional programming problem, Dinkelbach developed an
algorithm which obtains an optimal solution of the given problem by solving a se-
quence of subproblems Q(
), in which the linear ob jective function
cx
0
dx
is
minimized under the same condition
x
2
:
In this pap er, we show that Dinkel-
bach's algorithm solves at most O(log(
nM
)) subproblems in the worst case, where
M
= max
f
max
i
=1
;
2
;
111
;n
j
c
i
j
;
max
i
=1
;
2
;
111
;n
j
d
i
j
;
1
g
:
1
资源评论
