Case 1: Diet Problem

History
The diet problem was one of the first optimisation problems studied in the 1930s and 1940s. The problem
was motivated by the Army’s desire to minimise the cost of feeding GIs in the field while still providing a
healthy diet. One of the early researchers to study the problem was George Stigler, who made an
educated guess of an optimal solution using a heuristic method. His guess for the cost of an optimal diet
was $39.93 per year (1939 prices). In the fall of 1947, Jack Laderman of the Mathematical Tables Project of
the National Bureau of Standards used the newly developed simplex method to solve Stigler’s model. As
the first “large scale” computation in optimisation, the linear program consisted of nine equations in 77
unknowns. It took nine clerks using hand-operated desk calculators 120 man days to solve for the optimal
solution of $39.69. Stigler’s guess was off by only $0.24 per year!

Problem Statement
Given a set of foods, along with the nutrient information for each food and the cost per serving of each
food, the objective of the diet problem is to select the number of servings of each food to purchase (and
consume) to minimise the cost of the food while meeting the specified nutritional requirements. Typically,
the nutritional requirements are expressed as a minimum and a maximum allowable level for each
nutritional component. Other constraints such as a minimum and/or maximum number of servings may
be included to improve the quality of the menu.

Consider the following simple example (from The Diet Problem: A WWW-based Interactive Case Study in
Linear Programming). Suppose there are three foods available, corn, milk, and bread, and there are
restrictions on the number of calories (between 2000 and 2250) and the amount of Vitamin A (between
5000 and 50,000). The first table lists, for each food, the cost per serving, the amount of Vitamin A per
serving, and the number of calories per serving.

Food Cost per serving Vitamin A Calories

Corn $0.18 107 72
2% Milk $0.23 500 121
Wheat Bread $0.05 0 65
Suppose that the maximum number of servings is 10.
Then, the optimal solution for the problem is 1.94 servings of corn, 10 servings of milk, and 10 servings of
bread with a total cost of $3.15. The total amount of Vitamin A is 5208 and the total number of calories is
2000.
The objective of the diet problem is to select a set of foods that will satisfy daily nutritional requirements
at a minimum cost. The nutritional requirements are listed below. All the 64 food items with their
corresponding information are listed on the Diet Spreadsheet (see sheet “Table 2. Food items”). Similar to
the example above suppose that the maximum number of servings for each item is 10.

Table 1- Nutritional requirements

Name Unit Min Max

Calories cal 2000 2250
Cholesterol mg 0 300
Total_Fat g 0 65

1
 Sodium mg 0 2400
Carbohydra
tes g 0 300
Dietary_Fib
er g 25 100
Protein g 50 100
Vit_A IU 5000 50000
Vit_C IU 50 20000
Calcium mg 800 1600
Iron mg 10 30

A) Define decision variables (Notation, description)

B) Define the objective function (Equation, description)
C) Create a mathematical programming model (objective, constraints)
D) Implement your model in Excel Solver (demonstrate how you defined objective function,
variables, and constraints in Excel)
E) Provide the solution (Objective value, Optimal values of decision variables) [use a table to fit them
in one or two slides]

2
 Table 2- Food items
Name Unit Price Calories CholesterolTotal_Fat Sodium Carbohydrates
Dietary_Fiber
Protein Vit_A Vit_C Calcium Iron
Frozen Broccoli 10 Oz Pkg 0.16 73.8 0 0.8 68.2 13.6 8.5 8 5867.4 160.2 159 2.3
Carrots, Raw 1/2 Cup Shredded 0.07 23.7 0 0.1 19.2 5.6 1.6 0.6 15471 5.1 14.9 0.3
Celery, Raw 1 Stalk 0.04 6.4 0 0.1 34.8 1.5 0.7 0.3 53.6 2.8 16 0.2
Frozen Corn 1/2 Cup 0.18 72.2 0 0.6 2.5 17.1 2 2.5 106.6 5.2 3.3 0.3
Lettuce, Iceberg,Raw 1 Leaf 0.02 2.6 0 0 1.8 0.4 0.3 0.2 66 0.8 3.8 0.1
Peppers, Sweet, Raw 1 Pepper 0.53 20 0 0.1 1.5 4.8 1.3 0.7 467.7 66.1 6.7 0.3
Potatoes, Baked 1/2 Cup 0.06 171.5 0 0.2 15.2 39.9 3.2 3.7 0 15.6 22.7 4.3
Tofu 1/4 block 0.31 88.2 0 5.5 8.1 2.2 1.4 9.4 98.6 0.1 121.8 6.2
Roasted Chicken 1 lb chicken 0.84 277.4 129.9 10.8 125.6 0 0 42.2 77.4 0 21.9 1.8
Spaghetti W/ Sauce 1 1/2 Cup 0.78 358.2 0 12.3 1237.1 58.3 11.6 8.2 3055.2 27.9 80.2 2.3
Tomato,Red,Ripe,Raw 1 Tomato, 2-3/5 In 0.27 25.8 0 0.4 11.1 5.7 1.4 1 766.3 23.5 6.2 0.6
Apple, Raw, w/Skin 1 Fruit,3/Lb,Wo/Rf 0.24 81.4 0 0.5 0 21 3.7 0.3 73.1 7.9 9.7 0.2
Banana 1 Fruit 0.15 104.9 0 0.5 1.1 26.7 2.7 1.2 92.3 10.4 6.8 0.4
Grapes 10 Grapes 0.32 15.1 0 0.1 0.5 4.1 0.2 0.2 24 1 3.4 0.1
Kiwifruit, Raw, Fresh 1 Medium 0.49 46.4 0 0.3 3.8 11.3 2.6 0.8 133 74.5 19.8 0.3
Oranges 1 Medium, 2-5/8 Diam 0.15 61.6 0 0.2 0 15.4 3.1 1.2 268.6 69.7 52.4 0.1
Bagels 1 Oz 0.16 78 0 0.5 151.4 15.1 0.6 3 0 0 21 1
Wheat Bread 1 Sl 0.05 65 0 1 134.5 12.4 1.3 2.2 0 0 10.8 0.7
White Bread 1 Sl 0.06 65 0 1 132.5 11.8 1.1 2.3 0 0 26.2 0.8
Oatmeal Cookies 1 Cookie 0.09 81 0 3.3 68.9 12.4 0.6 1.1 2.9 0.1 6.7 0.5
Apple Pie 1 Oz 0.16 67.2 0 3.1 75.4 9.6 0.5 0.5 35.2 0.9 3.1 0.1
Chocolate Chip Cookies 1 Cookie 0.03 78.1 5.1 4.5 57.8 9.3 0 0.9 101.8 0 6.2 0.4
Butter, Regular 1 Pat 0.05 35.8 10.9 4.1 41.3 0 0 0 152.9 0 1.2 0
Cheddar Cheese 1 Oz 0.25 112.7 29.4 9.3 173.7 0.4 0 7 296.5 0 202 0.2
3.3%Fat, Whole Milk 1C 0.16 149.9 33.2 8.1 119.6 11.4 0 8 307.4 2.3 291.3 0.1
2%Lowfat Milk 1C 0.23 121.2 18.3 4.7 121.8 11.7 0 8.1 500.2 2.3 296.7 0.1
SkimMilk 1C 0.13 85.5 4.4 0.4 126.2 11.9 0 8.4 499.8 2.4 302.3 0.1
Poached Eggs Lrg Egg 0.08 74.5 211.5 5 140 0.6 0 6.2 316 0 24.5 0.7
Scrambled Eggs 1 Egg 0.11 99.6 211.2 7.3 168 1.3 0 6.7 409.2 0.1 42.6 0.7
Bologna, Turkey 1 Oz 0.15 56.4 28.1 4.3 248.9 0.3 0 3.9 0 0 23.8 0.4
Frankfurter, Beef 1 Frankfurter 0.27 141.8 27.4 12.8 461.7 0.8 0 5.4 0 10.8 9 0.6
Ham, Sliced, Extralean 1 Sl,6-1/4x4x1/16 In 0.33 37.1 13.3 1.4 405.1 0.3 0 5.5 0 7.4 2 0.2
Kielbasa, Pork 1 Sl,6x3-3/4x1/16 In 0.15 80.6 17.4 7.1 279.8 0.6 0 3.4 0 5.5 11.4 0.4
Cap'N Crunch 1 Oz 0.31 119.6 0 2.6 213.3 23 0.5 1.4 40.6 0 4.8 7.5
Cheerios 1 Oz 0.28 111 0 1.8 307.6 19.6 2 4.3 1252.2 15.1 48.6 4.5
Corn Flakes, Kellogg'S 1 Oz 0.28 110.5 0 0.1 290.5 24.5 0.7 2.3 1252.2 15.1 0.9 1.8
Raisin Bran, Kellogg'S 1.3 Oz 0.34 115.1 0 0.7 204.4 27.9 4 4 1250.2 0 12.9 16.8
Rice Krispies 1 Oz 0.32 112.2 0 0.2 340.8 24.8 0.4 1.9 1252.2 15.1 4 1.8
Special K 1 Oz 0.38 110.8 0 0.1 265.5 21.3 0.7 5.6 1252.2 15.1 8.2 4.5
Oatmeal 1C 0.82 145.1 0 2.3 2.3 25.3 4 6.1 37.4 0 18.7 1.6
Malt-O-Meal, Choc 1C 0.52 607.2 0 1.5 16.5 128.2 0 17.3 0 0 23.1 47.2
Pizza w/Pepperoni 1 Slice 0.44 181 14.2 7 267 19.9 0 10.1 281.9 1.6 64.6 0.9
Taco 1 Small Taco 0.59 369.4 56.4 20.6 802 26.7 0 20.7 855 2.2 220.6
Hamburger w/Toppings 1 Burger 0.83 275 42.8 10.2 563.9 32.7 0 13.6 126.3 2.6 51.4 2.5
Hotdog, Plain 1 Hotdog 0.31 242.1 44.1 14.5 670.3 18 0 10.4 0 0.1 23.5 2.3
Couscous 1/2 Cup 0.39 100.8 0 0.1 4.5 20.9 1.3 3.4 0 0 7.2 0.3
White Rice 1/2 Cup 0.08 102.7 0 0.2 0.8 22.3 0.3 2.1 0 0 7.9
Macaroni, cooked 1/2 Cup 0.17 98.7 0 0.5 0.7 19.8 0.9 3.3 0 0 4.9 1
Peanut Butter 2 Tbsp 0.07 188.5 0 16 155.5 6.9 2.1 7.7 0 0 13.1 0.6
Pork 4 Oz 0.81 710.8 105.1 72.2 38.4 0 0 13.8 14.7 0 59.9 0.4
Sardines in Oil 2 Sardines 0.45 49.9 34.1 2.7 121.2 0 0 5.9 53.8 0 91.7 0.7
White Tuna in Water 3 Oz 0.69 115.6 35.7 2.1 333.2 0 0 22.7 68 0 3.4 0.5
Popcorn, Air-Popped 1 Oz 0.04 108.3 0 1.2 1.1 22.1 4.3 3.4 55.6 0 2.8 0.8
Potato Chips, BBQ 1 Oz 0.22 139.2 0 9.2 212.6 15 1.2 2.2 61.5 9.6 14.2 0.5
Pretzels 1 Oz 0.12 108 0 1 486.2 22.5 0.9 2.6 0 0 10.2 1.2
Tortilla Chips 1 Oz 0.19 142 0 7.4 149.7 17.8 1.8 2 55.6 0 43.7 0.4
Chicken Noodle Soup 1 C (8 Fl Oz) 0.39 150.1 12.3 4.6 1862.2 18.7 1.5 7.9 1308.7 0 27.1 1.5
Splt Pea&HamSoup 1 C (8 Fl Oz) 0.67 184.8 7.2 4 964.8 26.8 4.1 11.1 4872 7 33.6 2.1
Veggie Beef Soup 1 C (8 Fl Oz) 0.71 158.1 10 3.8 1915.1 20.4 4 11.2 3785.1 4.8 32.6 2.2
New Eng ClamChwd 1 C (8 Fl Oz) 0.75 175.7 10 5 1864.9 21.8 1.5 10.9 20.1 4.8 82.8 2.8
Tomato Soup 1 C (8 Fl Oz) 0.39 170.7 0 3.8 1744.4 33.2 1 4.1 1393 133 27.6 3.5
New Eng ClamChwd, w/Mlk 1 C (8 Fl Oz) 0.99 163.7 22.3 6.6 992 16.6 1.5 9.5 163.7 3.5 186 1.5
CrmMshrmSoup, w/Mlk 1 C (8 Fl Oz) 0.65 203.4 19.8 13.6 1076.3 15 0.5 6.1 153.8 2.2 178.6 0.6
Bean Bacon Soup, w/Watr 1 C (8 Fl Oz) 0.67 172 2.5 5.9 951.3 22.8 8.6 7.9 888 1.5 81 2