In this paper, a linear programming problem is investigated in which the feasible region is formed as the intersection of fuzzy relational equalities and the harmonic mean operator is considered as fuzzy composition. Theoretical properties of the feasible region are derived. It is proved that the feasible solution set is comprised of one maximum solution and a finite number of minimal solutions. Furthermore, some necessary and sufficient conditions are additionally presented to determine the feasibility of the problem. Moreover, an algorithm is presented to find the optimal solutions of the problem and finally, an example is described to illustrate the algorithm.