In this paper, we propose a multi-objective formulation for solving the menu planning problem, in a Brazilian school context. Considering the school category, the student age group, and the school duration time, we propose a formulation of the problem in which the total cost and the nutritional error according to the Brazilian reference are simultaneously minimized. The menus must also meet some qualitative requirements, such as variety and harmony of preparations. We propose a NSGA-II for solving the problem. As a comparison, we use a weighted-sum approach for transforming the multi-objective problem into a mono-objective one and solve it using a generic Genetic Algorithm. Using as test scenario full-time preschool students (4-5 years old), 5-day menus are obtained by both methodologies. The menus are qualitatively and quantitatively assessed applying the Quality Index of Nutritional Food Safety Coordination (IQ COSAN, acronym in Portuguese) and compared to a 5-day menu for a Brazilian school. Results show the methodology is very promising and the obtained menus are adequate.