Abstract: Teenagers need to eat a good and balanced nutritious diet that provides calories for energy requirement and nutrients for proper growth, repair and maintenance of the body tissues and preventing diseases and infection such as anaemia, scurvy and rickets. Serving healthier meals is a major step towards achieving that objective. However, planning a nutritious and balance menu manually is complicated, inefficient and time-consuming. This study aims to develop a mathematical model for diet planning that optimizes and meets the necessary nutrient intake for student aged 13-18 as well as minimizing a budget. The data was collected from the Ministry of Education. Diet planning is a well-known optimization problem. Therefore the model was solved by using Binary Integer Linear Programming and "Delete-Shuffle Algorithm". This model can be adopted to solve other diet planning problem such as for the military, hospitals nursing home and universities.
INTRODUCTION
During 1996-1998, 791 million people in developing countries had food intake below the minimum requirements, 65% were in China, India and other parts of Asia. Due to the improper nutrient intake, many Malaysian people die annually due to diseases linked to hypertension, stroke, heart attack and renal failure. It have reported that many children in developing countries, including Malaysia are facing obesity problems that are associated with significant morbidity and mortality, including cardiovascular, respiratory, gastrointestinal, endocrine and psychosocial morbidities (Sidik and Ahmad, 2004). Planning for adequate menus faces many economic and psychological constraints. It involves simultaneous consideration of several types of constraints; the desired nutritional content, the likes and dislikes of the person that it is being planned for the amount (volume or weight) of food to be consumed and the expected form and content of different kinds of meals (Garille and Gass, 2001; Sidik and Ahmad, 2004).
The main purpose of "Diet problem" model formulated by Stigler (1945) is to study problems relating to human nutrition (Dantzig, 2002). This model, as in most operation research models have been set up on the traditional fundamental assumption that the decision maker seeks to optimize a single objective function. The problem has continued to be investigated by scientists and nutritionists (Smith, 1959; Armstrong and Sinha, 1974; Balintfy, 1975; Bassi, 1976; Foytik, 1981; McCann-Rugg et al., 1983; Silberberg, 1985; Benson and Morin, 1987; Lancaster, 1992; Sklan and Dariel, 1993; Leung et al., 1995; Gallenti, 1997; Westrich et al., 1998; Garille and Gass, 2001; Martinez-Alfaro, 2003; Cadenas et al., 2004). Therefore in this study, the main studies are to expend the current knowledge in menu planning and diet problems focusing on Malaysian recipes, minimizing the cost, fulfill the nutritional requirements and serve variety of food serve each day. Binary Integer Programming (with Matlab and the LPSolve programming language) is used to determine the most nutritious and palatable meals for Malaysian children aged 13-18 years old and likely to be used by the Ministry of Education Malaysia.
MATERIALS ANS METHODS
In Malaysian boarding schools, nutritionists from the Ministry of Education are responsible for planning menus for school children based on the cost of food items and Recommended Daily Allowance (RDA) for children aged between 13-18 years. The menu lists are given to caterers in boarding schools who provide six meals per day, breakfast (B), morning tea (M), lunch (L), evening tea (E), dinner (D) and supper (S). The menu provided is a nonselective menu where the school children do not have the choice to choose preferred foods. It is hard to plan palatable menus which simultaneously consider the nutrient intake, the cost of raw food, the variety of menu items and the preference of school children. It is time consuming and involves too many constraints and variables to manually produce an optimal palatable menu. Sometimes the combination of foods, that is produced manually, may exceed the RDA recommendation or vice versa. Planning adequate and palatable menus is important to prevent the school children from suffering any undesirable diseases. Hence, research on menu planning by developing mathematical models using operational research and decision science techniques is important in order to help caterers provide nutritious meals over extended time periods within the limited budget allocation.
Data collection: There are several types of data needed to build a menu planning model. These include the standardized price of each Malaysian menu, the nutritional contents for each menu, recommended nutritional daily allowance (RDA) for Malaysian school children aged between 13-18 years old and the government budget for caterers. Data is provided in Nutrient Composition of Malaysian Foods Handbook (1997), compiled by Tee et al. (1997) from the Malaysian Food Composition Database Programs, Institute for Medical Research. It includes suggestions for Recommended Daily Allowance (RDA) for Malaysians comprising the upper and lower bound of each nutrient needed by children aged 13-18 years old, both male and female. The information on current monthly caterers’ budget and cost per serving for each meal was collected from the nutritionists of the Ministry of Education, the boarding schools authorities through interview sessions and caterers. The budget is $3.92 USD per student per day.
Model formulation: The main aim of this research is to formulate a menu planning model that minimizes the budget provided by the government for boarding school caterers and maximizes the variety o f food intake. This model also tries to achieve the maximum nutritional requirement based on the Malaysian RDA requirements. There are 11 nutrients considered; energy, fats, carbohydrate, protein, niacin, vitamin A, vitamin B1, vitamin B2, vitamin C, calcium and iron. Furthermore, 10 types of foods will be considered; beverage, cereal flour based, rice flour based, cereal based meal, meat dishes, seafood, vegetable, fruit, wheat flour based and miscellaneous. There are 426 of foods and drinks to be considered. Based on the data, a binary integer programming model is developed and discussed. Two assumptions need to be made when conducting this study (1) The ingredients in each menu are in standardized portions and size integrally. So each variable can have the value of 0 or 1, except for Plain Water and Plain Rice and (2) The nutrients contained in each menu are assumed to be consumed as a whole and are not destroyed during the process of cooking and providing the menus.
As mentioned earlier there are 426 types of foods and drinks, therefore there will be 426 variables (xi) where i = 1, 2,…, 426. Each type of food has its own available range of selection as presented in Table 1. For example, Beverage dishes (x1 - x37). Eighteen dishes (18 variables) from 10 types of food are served per day. Therefore in a week, 126 dishes will be suitably selected from the 426 dishes that are available. For the objective function, we minimize the total cost Fin Eq. 1:
| (1) |
by selecting the dish and providing a palatable daily menu. The maximum budget provided per day by the government is MYR15.00 (MYR = Malaysian Ringgit). Therefore we try to minimize the cost. The daily constraints in Eq. 2:
| (2) |
where, LB and UB is the vector and give a different value for each nutrient. This is to ensure that the nutrients requirements are met. There are 11 constraints of nutrients with lower and upper bound values except for protein, vitamin B1 and B2 as stated in Table 2. Based on Table 1 we then specify the 10 food requirements in Eq. 3:
| (3) |
| Table 1: | Food requirement per day |
| Table 2: | Values of upper bound and lower bound of the 11 nutrients |
| LB: Lower bound, UB: Upper bound | |
so that 18 dishes will be served per day. All 426 variables are in binary values in Eq. 4:
| (4) |
Each food can only be serve once (1 chosen and 0 otherwise) in a week except for except for Plain water and Plain Rice. Each time running, the program will consider different available variables. For example, 18 variables are selected from the 426 variables that are available to be served on day 1. The variables are
x5 = x12 = x20 = x28 = x77 = x104 = x115 = x119 = x114 =
x174 = x118 5= x216 =x 238 = x269 = x319 = x390 = 1 x9 = 2
and the rest are zero. As mentioned earlier all variables are binary except for plain water and plain rice. Binary means that the lower bound value for the variable is 0 and the upper bound value is 1. Before running for day 2, each variable that are selected in day 1 will be eliminate except for plain water and plain rice. It means that all the foods that are served on day i will be deleted from the model and will not be served again on day i + 1 except for the two compulsory foods. A looping process is used for running the program for 7 days, deleting the selected variables from the existing model and reshuffle all the optimal variables into a proper serving schedule. This algorithm is called as the "Delete-Reshuffle Algorithm". The selected variables in day 1 will be rewrite as, where lower bound value is 0 and upper bound value is 0 except for plain water and plain rice. Then selected food will be arranged into proper serving schedule (Breakfast, Morning Tea, Lunch, Evening Tea, Dinner, Supper).
| Delete-Reshuffle Algorithm |
| *CFB = Cereal Flour Based, RFB = Rice Flour Based, WFB = Wheat Flour Based, MIS = Miscellaneous, BEV = Beverage, CMB = Cereal Based Meal, VEG = Vegetable, FRU = Fruit, MEAT = Meat, SEA = Seafood |
This present study involves many decision variables, constraints and parameters. The coding was programmed using Matlab with LPSolve and the optimal solution for a 7 day menu was obtained within 5 sec with a 2.26GHz pc. By eliminating the selected variables and reducing the size of variables, it will help the program run faster. The efficiency of the methods in solving this menu planning problem has been proven based on past studies (Martinez-Alfaro, 2003).
RESULTS
The results are presented in Table 3. It shows meals for 7 days to be provided by the management of the school to the children aged 13-18 years old. Based on Table 3, there are variety types of drinks and foods presented in different ways each day, which includes six types of meals from breakfast to supper. All these drinks and foods meet the daily nutritional requirement for the school children at a minimum cost. Therefore, it can be concluded that all the meals chosen are nutritious and is advisable to serve to the school children aged 13-18 years old. The value of the total cost is less than the budget provided by the government. This means the management of the school will spend less than $3.92USD per person per day. The total cost for each day getting higher and higher because the program choose the cheapest food but yet satisfy the RDA requirement to be serve first. Then it chooses slight more expensive food for the 2nd day and so on.
DISCUSSION
This research has significant contributions towards the theory of evolutionary algorithm, specifically in the zero-one. The combination of optimization methods and linear programming approach has significantly contributed to the solving of complex problems that involve many variables, constraints and conflicting objectives.
| Table 3: | Seven days menu |
A new algorithm is introduced in this study known as a "Delete-reshuffle algorithm" where it helps to eliminate selected variables and reshuffle available variables for the next day menu selection. This new algorithm has been categorically modified to suit the menu planning problem structure and has successfully improved the performance of generating feasible solutions and sensible menu lists with convincing reliability. It has been proven that the proposed approach has considerably outperformed the traditional method in terms of quality of solution and run time (Smith, 1959; Fletcher et al., 1994; Garille and Gass, 2001; Sidik and Ahmad, 2004; Asyikin and Razali, 2011). This dynamic food menu environment must be tackled by caterers in the decision making process in order to satisfy all stakeholders. Thus, the proposed menu planning prototype is flexible in managing these changes in terms of the number of menu items involved, the price of menu items, the available budget and the caterer’s cooking ability which was not taken into account by the previous studies which reported by Smith, (1959), Armstrong and Sinha (1974), Balintfy (1975), Bassi, (1976), Foytik (1981), McCann-Rugg et al. (1983), Silberberg (1985), Benson and Morin (1987), Lancaster (1992), Sklan and Dariel (1993), Fletcher et al. (1994), Leung et al. (1995), Gallenti (1997), Westrich et al. (1998), Garille and Gass (2001) and Asyikin and Razali (2011). Based on the results, the process of generating the menu can take up to more than a week within seconds. Furthermore, the food is served differently for each day, meet the RNI requirement and promoting Malaysian healthy traditional food. Compared to previous studies, the caterer can only generate 1 day menu, take long time to generate result, lack of variety of food and not promoting his/her own country traditional food (Fletcher et al., 1994; Asyikin and Razali, 2011). This study has covered all the important constraints, which make the menu planning model to be more reliable as compared to the previous menu planning models in the relevant literature. In some way, this study has extended the previous menu planning models to become more efficient and applicable to real life situation.
CONCLUSION
The researchers have produced a suitable 7 day menu plan that can be used as a guide for the management of the school. The model was solved using Matlab with LPSolve. It fulfilled all the constraints set by the researchers and gives a better solution compare to other heuristic methods such as Genetic Algorithms. This research focused on 13-18 years old school children at secondary boarding school. The nutritional requirements required for children below 12 years old and adults will be different from the one used here and it will affect the menu selection and the cost of preparing the meals. The total cost for each day is less than $3.92 USD. Therefore we can serve slightly expensive and better quality of foods for the children. An approach using post-optimality and sensitivity analysis will be developed in the future based on the changes in the coefficient value (ci). This model can be adopted to solve other diet planning problem such as for the military, hospitals nursing home and universities.