|
1 /* STIGLER, original Stigler's 1939 diet problem */ |
|
2 |
|
3 /* The Stigler Diet is an optimization problem named for George Stigler, |
|
4 a 1982 Nobel Laureate in economics, who posed the following problem: |
|
5 For a moderately active man weighing 154 pounds, how much of each of |
|
6 77 foods should be eaten on a daily basis so that the man's intake of |
|
7 nine nutrients will be at least equal to the recommended dietary |
|
8 allowances (RDSs) suggested by the National Research Council in 1943, |
|
9 with the cost of the diet being minimal? |
|
10 |
|
11 The nutrient RDAs required to be met in Stigler's experiment were |
|
12 calories, protein, calcium, iron, vitamin A, thiamine, riboflavin, |
|
13 niacin, and ascorbic acid. The result was an annual budget allocated |
|
14 to foods such as evaporated milk, cabbage, dried navy beans, and beef |
|
15 liver at a cost of approximately $0.11 a day in 1939 U.S. dollars. |
|
16 |
|
17 While the name "Stigler Diet" was applied after the experiment by |
|
18 outsiders, according to Stigler, "No one recommends these diets for |
|
19 anyone, let alone everyone." The Stigler diet has been much ridiculed |
|
20 for its lack of variety and palatability, however his methodology has |
|
21 received praise and is considered to be some of the earliest work in |
|
22 linear programming. |
|
23 |
|
24 The Stigler diet question is a linear programming problem. Lacking |
|
25 any sophisticated method of solving such a problem, Stigler was |
|
26 forced to utilize heuristic methods in order to find a solution. The |
|
27 diet question originally asked in which quantities a 154 pound male |
|
28 would have to consume 77 different foods in order to fulfill the |
|
29 recommended intake of 9 different nutrients while keeping expense at |
|
30 a minimum. Through "trial and error, mathematical insight and |
|
31 agility," Stigler was able to eliminate 62 of the foods from the |
|
32 original 77 (these foods were removed based because they lacked |
|
33 nutrients in comparison to the remaining 15). From the reduced list, |
|
34 Stigler calculated the required amounts of each of the remaining 15 |
|
35 foods to arrive at a cost-minimizing solution to his question. |
|
36 According to Stigler's calculations, the annual cost of his solution |
|
37 was $39.93 in 1939 dollars. When corrected for inflation using the |
|
38 consumer price index, the cost of the diet in 2005 dollars is |
|
39 $561.43. The specific combination of foods and quantities is as |
|
40 follows: |
|
41 |
|
42 Stigler's 1939 Diet |
|
43 |
|
44 Food Annual Quantities Annual Cost |
|
45 ---------------- ----------------- ----------- |
|
46 Wheat Flour 370 lb. $13.33 |
|
47 Evaporated Milk 57 cans 3.84 |
|
48 Cabbage 111 lb. 4.11 |
|
49 Spinach 23 lb. 1.85 |
|
50 Dried Navy Beans 285 lb. 16.80 |
|
51 ---------------------------------------------- |
|
52 Total Annual Cost $39.93 |
|
53 |
|
54 The 9 nutrients that Stigler's diet took into consideration and their |
|
55 respective recommended daily amounts were: |
|
56 |
|
57 Table of nutrients considered in Stigler's diet |
|
58 |
|
59 Nutrient Daily Recommended Intake |
|
60 ------------------------- ------------------------ |
|
61 Calories 3,000 Calories |
|
62 Protein 70 grams |
|
63 Calcium .8 grams |
|
64 Iron 12 milligrams |
|
65 Vitamin A 5,000 IU |
|
66 Thiamine (Vitamin B1) 1.8 milligrams |
|
67 Riboflavin (Vitamin B2) 2.7 milligrams |
|
68 Niacin 18 milligrams |
|
69 Ascorbic Acid (Vitamin C) 75 milligrams |
|
70 |
|
71 Seven years after Stigler made his initial estimates, the development |
|
72 of George Dantzig's Simplex algorithm made it possible to solve the |
|
73 problem without relying on heuristic methods. The exact value was |
|
74 determined to be $39.69 (using the original 1939 data). Dantzig's |
|
75 algorithm describes a method of traversing the vertices of a polytope |
|
76 of N+1 dimensions in order to find the optimal solution to a specific |
|
77 situation. |
|
78 |
|
79 (From Wikipedia, the free encyclopedia.) */ |
|
80 |
|
81 /* Translated from GAMS by Andrew Makhorin <mao@gnu.org>. |
|
82 |
|
83 For the original GAMS model stigler1939.gms see [3]. |
|
84 |
|
85 References: |
|
86 |
|
87 1. George J. Stigler, "The Cost of Subsistence," J. Farm Econ. 27, |
|
88 1945, pp. 303-14. |
|
89 |
|
90 2. National Research Council, "Recommended Daily Allowances," Reprint |
|
91 and Circular Series No. 115, January, 1943. |
|
92 |
|
93 3. Erwin Kalvelagen, "Model building with GAMS," Chapter 2, "Building |
|
94 linear programming models," pp. 128-34. */ |
|
95 |
|
96 set C; |
|
97 /* commodities */ |
|
98 |
|
99 check card(C) = 77; |
|
100 /* there must be 77 commodities */ |
|
101 |
|
102 set N; |
|
103 /* nutrients */ |
|
104 |
|
105 param data{c in C, {"price", "weight"} union N}; |
|
106 /* nutritive values per dollar of expenditure */ |
|
107 |
|
108 param allowance{n in N}; |
|
109 /* recommended daily allowance for a moderately active man */ |
|
110 |
|
111 var x{c in C}, >= 0; |
|
112 /* dollars of food to be purchased daily */ |
|
113 |
|
114 s.t. nb{n in N}: sum{c in C} data[c,n] * x[c] >= allowance[n]; |
|
115 /* nutrient balance */ |
|
116 |
|
117 minimize cost: sum{c in C} x[c]; |
|
118 /* total food bill */ |
|
119 |
|
120 solve; |
|
121 |
|
122 param days := 365.25; |
|
123 /* days in a year */ |
|
124 |
|
125 param commodity{c in C}, symbolic; |
|
126 |
|
127 param unit{c in C}, symbolic; |
|
128 |
|
129 printf "\n"; |
|
130 printf "MINIMUM COST ANNUAL DIET\n"; |
|
131 printf "\n"; |
|
132 printf " Commodity Unit Quantity Cost \n"; |
|
133 printf "------------------------- ---------- ---------- ----------\n"; |
|
134 printf{c in C: x[c] != 0} "%-25s %10s %10.2f $%7.2f\n", commodity[c], |
|
135 unit[c], 100 * days * x[c] / data[c,"price"], days * x[c]; |
|
136 printf " -----------------\n"; |
|
137 printf " Total: $%7.2f\n", |
|
138 days * sum{c in C} x[c]; |
|
139 printf "\n"; |
|
140 |
|
141 data; |
|
142 |
|
143 param : C : commodity unit := |
|
144 flour "Wheat Flour (Enriched)" "10 lb." |
|
145 macaroni "Macaroni" "1 lb." |
|
146 cereal "Wheat Cereal (Enriched)" "28 oz." |
|
147 cornflakes "Corn Flakes" "8 oz." |
|
148 cornmeal "Corn Meal" "1 lb." |
|
149 grits "Hominy Grits" "24 oz." |
|
150 rice "Rice" "1 lb." |
|
151 oats "Rolled Oats" "1 lb." |
|
152 whitebread "White Bread (Enriched)" "1 lb." |
|
153 wheatbread "Whole Wheat Bread" "1 lb." |
|
154 ryebread "Rye Bread" "1 lb." |
|
155 poundcake "Pound Cake" "1 lb." |
|
156 crackers "Soda Crackers" "1 lb." |
|
157 milk "Milk" "1 qt." |
|
158 evapmild "Evaporated Milk (can)" "14.5 oz." |
|
159 butter "Butter" "1 lb." |
|
160 margarine "Oleomargarine" "1 lb." |
|
161 eggs "Eggs" "1 doz." |
|
162 cheese "Cheese (Cheddar)" "1 lb." |
|
163 cream "Cream" "1/2 pt." |
|
164 peanutbutter "Peanut Butter" "1 lb." |
|
165 mayonnaise "Mayonnaise" "1/2 pt." |
|
166 crisco "Crisco" "1 lb." |
|
167 lard "Lard" "1 lb." |
|
168 sirloinsteak "Sirloin Steak" "1 lb." |
|
169 roundsteak "Round Steak" "1 lb." |
|
170 ribroast "Rib Roast" "1 lb." |
|
171 chuckroast "Chuck Roast" "1 lb." |
|
172 plate "Plate" "1 lb." |
|
173 liver "Liver (Beef)" "1 lb." |
|
174 lambleg "Leg of Lamb" "1 lb." |
|
175 lambchops "Lamb Chops (Rib)" "1 lb." |
|
176 porkchops "Pork Chops" "1 lb." |
|
177 porkroast "Pork Loin Roast" "1 lb." |
|
178 bacon "Bacon" "1 lb." |
|
179 ham "Ham - smoked" "1 lb." |
|
180 saltpork "Salt Pork" "1 lb." |
|
181 chicken "Roasting Chicken" "1 lb." |
|
182 veal "Veal Cutlets" "1 lb." |
|
183 salmon "Salmon, Pink (can)" "16 oz." |
|
184 apples "Apples" "1 lb." |
|
185 bananas "Bananas" "1 lb." |
|
186 lemons "Lemons" "1 doz." |
|
187 oranges "Oranges" "1 doz." |
|
188 greenbeans "Green Beans" "1 lb." |
|
189 cabbage "Cabbage" "1 lb." |
|
190 carrots "Carrots" "1 bunch" |
|
191 celery "Celery" "1 stalk" |
|
192 lettuce "Lettuce" "1 head" |
|
193 onions "Onions" "1 lb." |
|
194 potatoes "Potatoes" "15 lb." |
|
195 spinach "Spinach" "1 lb." |
|
196 sweetpotato "Sweet Potatoes" "1 lb." |
|
197 peaches "Peaches (can)" "No. 2 1/2" |
|
198 pears "Pears (can)" "No. 2 1/2" |
|
199 pineapple "Pineapple (can)" "No. 2 1/2" |
|
200 asparagus "Asparagus (can)" "No. 2" |
|
201 cannedgrbn "Grean Beans (can)" "No. 2" |
|
202 porkbeans "Pork and Beans (can)" "16 oz." |
|
203 corn "Corn (can)" "No. 2" |
|
204 peas "Peas (can)" "No. 2" |
|
205 tomatoes "Tomatoes (can)" "No. 2" |
|
206 tomatosoup "Tomato Soup (can)" "10 1/2 oz." |
|
207 driedpeach "Peaches, Dried" "1 lb." |
|
208 prunes "Prunes, Dried" "1 lb." |
|
209 raisins "Raisins, Dried" "15 oz." |
|
210 driedpeas "Peas, Dried" "1 lb." |
|
211 limabeans "Lima Beans, Dried" "1 lb." |
|
212 navybeans "Navy Beans, Dried" "1 lb." |
|
213 coffee "Coffee" "1 lb." |
|
214 tea "Tea" "1/4 lb." |
|
215 cocoa "Cocoa" "8 oz." |
|
216 chocolate "Chocolate" "8 oz." |
|
217 sugar "Sugar" "10 lb." |
|
218 cornsirup "Corn Sirup" "24 oz." |
|
219 molasses "Molasses" "18 oz." |
|
220 stawberry "Strawberry Preserve" "1 lb." |
|
221 ; |
|
222 |
|
223 set N := |
|
224 calories /* Calories, unit = 1000 */ |
|
225 protein /* Protein, unit = grams */ |
|
226 calcium /* Calcium, unit = grams */ |
|
227 iron /* Iron, unit = milligrams */ |
|
228 vitaminA /* Vitamin A, unit = 1000 International Units */ |
|
229 thiamine /* Thiamine, Vit. B1, unit = milligrams */ |
|
230 riboflavin /* Riboflavin, Vit. B2, unit = milligrams */ |
|
231 niacin /* Niacin (Nicotinic Acid), unit = milligrams */ |
|
232 ascorbicAcid /* Ascorbic Acid, Vit. C, unit = milligrams */ |
|
233 ; |
|
234 |
|
235 param data |
|
236 : price weight calories protein calcium iron := |
|
237 # aug. 15 edible |
|
238 # 1939 per $1 |
|
239 # (cents) (grams) (1000) (grams) (grams) (mg.) |
|
240 flour 36.0 12600 44.7 1411 2.0 365 |
|
241 macaroni 14.1 3217 11.6 418 .7 54 |
|
242 cereal 24.2 3280 11.8 377 14.4 175 |
|
243 cornflakes 7.1 3194 11.4 252 .1 56 |
|
244 cornmeal 4.6 9861 36.0 897 1.7 99 |
|
245 grits 8.5 8005 28.6 680 .8 80 |
|
246 rice 7.5 6048 21.2 460 .6 41 |
|
247 oats 7.1 6389 25.3 907 5.1 341 |
|
248 whitebread 7.9 5742 15.6 488 2.5 115 |
|
249 wheatbread 9.1 4985 12.2 484 2.7 125 |
|
250 ryebread 9.2 4930 12.4 439 1.1 82 |
|
251 poundcake 24.8 1829 8.0 130 .4 31 |
|
252 crackers 15.1 3004 12.5 288 .5 50 |
|
253 milk 11.0 8867 6.1 310 10.5 18 |
|
254 evapmild 6.7 6035 8.4 422 15.1 9 |
|
255 butter 20.8 1473 10.8 9 .2 3 |
|
256 margarine 16.1 2817 20.6 17 .6 6 |
|
257 eggs 32.6 1857 2.9 238 1.0 52 |
|
258 cheese 24.2 1874 7.4 448 16.4 19 |
|
259 cream 14.1 1689 3.5 49 1.7 3 |
|
260 peanutbutter 17.9 2534 15.7 661 1.0 48 |
|
261 mayonnaise 16.7 1198 8.6 18 .2 8 |
|
262 crisco 20.3 2234 20.1 0 .0 0 |
|
263 lard 9.8 4628 41.7 0 .0 0 |
|
264 sirloinsteak 39.6 1145 2.9 166 .1 34 |
|
265 roundsteak 36.4 1246 2.2 214 .1 32 |
|
266 ribroast 29.2 1553 3.4 213 .1 33 |
|
267 chuckroast 22.6 2007 3.6 309 .2 46 |
|
268 plate 14.6 3107 8.5 404 .2 62 |
|
269 liver 26.8 1692 2.2 333 .2 139 |
|
270 lambleg 27.6 1643 3.1 245 .1 20 |
|
271 lambchops 36.6 1239 3.3 140 .1 15 |
|
272 porkchops 30.7 1477 3.5 196 .2 80 |
|
273 porkroast 24.2 1874 4.4 249 .3 37 |
|
274 bacon 25.6 1772 10.4 152 .2 23 |
|
275 ham 27.4 1655 6.7 212 .2 31 |
|
276 saltpork 16.0 2835 18.8 164 .1 26 |
|
277 chicken 30.3 1497 1.8 184 .1 30 |
|
278 veal 42.3 1072 1.7 156 .1 24 |
|
279 salmon 13.0 3489 5.8 705 6.8 45 |
|
280 apples 4.4 9072 5.8 27 .5 36 |
|
281 bananas 6.1 4982 4.9 60 .4 30 |
|
282 lemons 26.0 2380 1.0 21 .5 14 |
|
283 oranges 30.9 4439 2.2 40 1.1 18 |
|
284 greenbeans 7.1 5750 2.4 138 3.7 80 |
|
285 cabbage 3.7 8949 2.6 125 4.0 36 |
|
286 carrots 4.7 6080 2.7 73 2.8 43 |
|
287 celery 7.3 3915 .9 51 3.0 23 |
|
288 lettuce 8.2 2247 .4 27 1.1 22 |
|
289 onions 3.6 11844 5.8 166 3.8 59 |
|
290 potatoes 34.0 16810 14.3 336 1.8 118 |
|
291 spinach 8.1 4592 1.1 106 .0 138 |
|
292 sweetpotato 5.1 7649 9.6 138 2.7 54 |
|
293 peaches 16.8 4894 3.7 20 .4 10 |
|
294 pears 20.4 4030 3.0 8 .3 8 |
|
295 pineapple 21.3 3993 2.4 16 .4 8 |
|
296 asparagus 27.7 1945 .4 33 .3 12 |
|
297 cannedgrbn 10.0 5386 1.0 54 2.0 65 |
|
298 porkbeans 7.1 6389 7.5 364 4.0 134 |
|
299 corn 10.4 5452 5.2 136 .2 16 |
|
300 peas 13.8 4109 2.3 136 .6 45 |
|
301 tomatoes 8.6 6263 1.3 63 .7 38 |
|
302 tomatosoup 7.6 3917 1.6 71 .6 43 |
|
303 driedpeach 15.7 2889 8.5 87 1.7 173 |
|
304 prunes 9.0 4284 12.8 99 2.5 154 |
|
305 raisins 9.4 4524 13.5 104 2.5 136 |
|
306 driedpeas 7.9 5742 20.0 1367 4.2 345 |
|
307 limabeans 8.9 5097 17.4 1055 3.7 459 |
|
308 navybeans 5.9 7688 26.9 1691 11.4 792 |
|
309 coffee 22.4 2025 .0 0 .0 0 |
|
310 tea 17.4 652 .0 0 .0 0 |
|
311 cocoa 8.6 2637 8.7 237 3.0 72 |
|
312 chocolate 16.2 1400 8.0 77 1.3 39 |
|
313 sugar 51.7 8773 34.9 0 .0 0 |
|
314 cornsirup 13.7 4996 14.7 0 .5 74 |
|
315 molasses 13.6 3752 9.0 0 10.3 244 |
|
316 stawberry 20.5 2213 6.4 11 .4 7 |
|
317 |
|
318 : vitaminA thiamine riboflavin niacin ascorbicAcid := |
|
319 # (1000 IU) (mg.) (mg.) (mg.) (mg.) |
|
320 flour .0 55.4 33.3 441 0 |
|
321 macaroni .0 3.2 1.9 68 0 |
|
322 cereal .0 14.4 8.8 114 0 |
|
323 cornflakes .0 13.5 2.3 68 0 |
|
324 cornmeal 30.9 17.4 7.9 106 0 |
|
325 grits .0 10.6 1.6 110 0 |
|
326 rice .0 2.0 4.8 60 0 |
|
327 oats .0 37.1 8.9 64 0 |
|
328 whitebread .0 13.8 8.5 126 0 |
|
329 wheatbread .0 13.9 6.4 160 0 |
|
330 ryebread .0 9.9 3.0 66 0 |
|
331 poundcake 18.9 2.8 3.0 17 0 |
|
332 crackers .0 .0 .0 0 0 |
|
333 milk 16.8 4.0 16.0 7 177 |
|
334 evapmild 26.0 3.0 23.5 11 60 |
|
335 butter 44.2 .0 .2 2 0 |
|
336 margarine 55.8 .2 .0 0 0 |
|
337 eggs 18.6 2.8 6.5 1 0 |
|
338 cheese 28.1 .8 10.3 4 0 |
|
339 cream 16.9 .6 2.5 0 17 |
|
340 peanutbutter .0 9.6 8.1 471 0 |
|
341 mayonnaise 2.7 .4 .5 0 0 |
|
342 crisco .0 .0 .0 0 0 |
|
343 lard .2 .0 .5 5 0 |
|
344 sirloinsteak .2 2.1 2.9 69 0 |
|
345 roundsteak .4 2.5 2.4 87 0 |
|
346 ribroast .0 .0 2.0 0 0 |
|
347 chuckroast .4 1.0 4.0 120 0 |
|
348 plate .0 .9 .0 0 0 |
|
349 liver 169.2 6.4 50.8 316 525 |
|
350 lambleg .0 2.8 3.0 86 0 |
|
351 lambchops .0 1.7 2.7 54 0 |
|
352 porkchops .0 17.4 2.7 60 0 |
|
353 porkroast .0 18.2 3.6 79 0 |
|
354 bacon .0 1.8 1.8 71 0 |
|
355 ham .0 9.9 3.3 50 0 |
|
356 saltpork .0 1.4 1.8 0 0 |
|
357 chicken .1 .9 1.8 68 46 |
|
358 veal .0 1.4 2.4 57 0 |
|
359 salmon 3.5 1.0 4.9 209 0 |
|
360 apples 7.3 3.6 2.7 5 544 |
|
361 bananas 17.4 2.5 3.5 28 498 |
|
362 lemons .0 .5 .0 4 952 |
|
363 oranges 11.1 3.6 1.3 10 1993 |
|
364 greenbeans 69.0 4.3 5.8 37 862 |
|
365 cabbage 7.2 9.0 4.5 26 5369 |
|
366 carrots 188.5 6.1 4.3 89 608 |
|
367 celery .9 1.4 1.4 9 313 |
|
368 lettuce 112.4 1.8 3.4 11 449 |
|
369 onions 16.6 4.7 5.9 21 1184 |
|
370 potatoes 6.7 29.4 7.1 198 2522 |
|
371 spinach 918.4 5.7 13.8 33 2755 |
|
372 sweetpotato 290.7 8.4 5.4 83 1912 |
|
373 peaches 21.5 .5 1.0 31 196 |
|
374 pears .8 .8 .8 5 81 |
|
375 pineapple 2.0 2.8 .8 7 399 |
|
376 asparagus 16.3 1.4 2.1 17 272 |
|
377 cannedgrbn 53.9 1.6 4.3 32 431 |
|
378 porkbeans 3.5 8.3 7.7 56 0 |
|
379 corn 12.0 1.6 2.7 42 218 |
|
380 peas 34.9 4.9 2.5 37 370 |
|
381 tomatoes 53.2 3.4 2.5 36 1253 |
|
382 tomatosoup 57.9 3.5 2.4 67 862 |
|
383 driedpeach 86.8 1.2 4.3 55 57 |
|
384 prunes 85.7 3.9 4.3 65 257 |
|
385 raisins 4.5 6.3 1.4 24 136 |
|
386 driedpeas 2.9 28.7 18.4 162 0 |
|
387 limabeans 5.1 26.9 38.2 93 0 |
|
388 navybeans .0 38.4 24.6 217 0 |
|
389 coffee .0 4.0 5.1 50 0 |
|
390 tea .0 .0 2.3 42 0 |
|
391 cocoa .0 2.0 11.9 40 0 |
|
392 chocolate .0 .9 3.4 14 0 |
|
393 sugar .0 .0 .0 0 0 |
|
394 cornsirup .0 .0 .0 5 0 |
|
395 molasses .0 1.9 7.5 146 0 |
|
396 stawberry .2 .2 .4 3 0 |
|
397 ; |
|
398 |
|
399 param allowance := |
|
400 calories 3 |
|
401 protein 70 |
|
402 calcium .8 |
|
403 iron 12 |
|
404 vitaminA 5 |
|
405 thiamine 1.8 |
|
406 riboflavin 2.7 |
|
407 niacin 18 |
|
408 ascorbicAcid 75 |
|
409 ; |
|
410 |
|
411 end; |