A mobile network operator cloud (MNOC), solely or with the help of public clouds, provides the computational resources in the form of virtual machines on physical machines (PMs) to handle heavy tasks, which are offloaded by the subscribers. Definitely, cost is a constant source of worry for an MNOC. In fact, although a large number of used PMs of the MNOC and public clouds decreases the penalty cost of request rejection, other associated costs, such as infrastructure, power consumption, cooling, and virtual machine instances of public clouds, are imposed on the MNOC. Therefore, to minimize the overall cost, finding the optimal number of required PMs in all participant clouds, including the MNOC and public clouds, is recognized as an important issue. To deal with this issue, in the present paper, using analytical performance model of a MNOC, a capacity planning framework is proposed. Specifically, this framework solves a cost optimization problem using a simulated annealing algorithm. Numerical results demonstrate the ability of the proposed framework to identify the optimal solution within an acceptable duration of the time.