Using relay stations (RSs) has been known as a promising technology to improve the system performance of a traditional cellular network. This paper aims to investigate the uplink performance of a relay-assisted cellular network with optimal system parameters. Two performance measures, average power consumption of mobile stations and uplink system spectral efficiency, are optimized by jointly considering the system parameters of RSs' locations, reuse patterns, path selections and resource allocation. A genetic algorithm along with a method of MAI (multiple access interference) estimation is proposed to solve the optimization problem. Numerical results show that significant improvement on system performance can be achieved from both power consumption and system spectral efficiency aspects if RSs are deployed and used in the optimal way.