In this work, we consider combinatorial multi-agent optimization problems, i.e., problems presenting a combinatorial set of solutions, and each solution is evaluated through a vector. An element of the vector corresponds to the utility that an individual agent receives from the solution. Given potential conflicts, it is improbable that a single feasible solution will be optimal for all agents. Consequently, a relevant objective is to identify solutions that are fair to all agents. There are several approaches to defining fairness in the context of optimization problems, and here we focus on Lorenz-optimal solutions. However, in some cases, in addition to the search for a fair solution, an economic criterion comes into play, i.e., we also seek to find a least-cost solution. Since the optimal solution for the cost function is not necessarily fair (i.e., Lorenz-optimal in our case), our aim is to generate a Lorenz-optimal solution with minimum cost. We propose a new exact method to solve this problem, and apply it to the multi-agent assignment problem and to the multi-agent knapsack problem. Results show that the new method is much more efficient than a method based on a complete enumeration of Lorenz-optimal solutions.