alpar@1: /* STIGLER, original Stigler's 1939 diet problem */ alpar@1: alpar@1: /* The Stigler Diet is an optimization problem named for George Stigler, alpar@1: a 1982 Nobel Laureate in economics, who posed the following problem: alpar@1: For a moderately active man weighing 154 pounds, how much of each of alpar@1: 77 foods should be eaten on a daily basis so that the man's intake of alpar@1: nine nutrients will be at least equal to the recommended dietary alpar@1: allowances (RDSs) suggested by the National Research Council in 1943, alpar@1: with the cost of the diet being minimal? alpar@1: alpar@1: The nutrient RDAs required to be met in Stigler's experiment were alpar@1: calories, protein, calcium, iron, vitamin A, thiamine, riboflavin, alpar@1: niacin, and ascorbic acid. The result was an annual budget allocated alpar@1: to foods such as evaporated milk, cabbage, dried navy beans, and beef alpar@1: liver at a cost of approximately $0.11 a day in 1939 U.S. dollars. alpar@1: alpar@1: While the name "Stigler Diet" was applied after the experiment by alpar@1: outsiders, according to Stigler, "No one recommends these diets for alpar@1: anyone, let alone everyone." The Stigler diet has been much ridiculed alpar@1: for its lack of variety and palatability, however his methodology has alpar@1: received praise and is considered to be some of the earliest work in alpar@1: linear programming. alpar@1: alpar@1: The Stigler diet question is a linear programming problem. Lacking alpar@1: any sophisticated method of solving such a problem, Stigler was alpar@1: forced to utilize heuristic methods in order to find a solution. The alpar@1: diet question originally asked in which quantities a 154 pound male alpar@1: would have to consume 77 different foods in order to fulfill the alpar@1: recommended intake of 9 different nutrients while keeping expense at alpar@1: a minimum. Through "trial and error, mathematical insight and alpar@1: agility," Stigler was able to eliminate 62 of the foods from the alpar@1: original 77 (these foods were removed based because they lacked alpar@1: nutrients in comparison to the remaining 15). From the reduced list, alpar@1: Stigler calculated the required amounts of each of the remaining 15 alpar@1: foods to arrive at a cost-minimizing solution to his question. alpar@1: According to Stigler's calculations, the annual cost of his solution alpar@1: was $39.93 in 1939 dollars. When corrected for inflation using the alpar@1: consumer price index, the cost of the diet in 2005 dollars is alpar@1: $561.43. The specific combination of foods and quantities is as alpar@1: follows: alpar@1: alpar@1: Stigler's 1939 Diet alpar@1: alpar@1: Food Annual Quantities Annual Cost alpar@1: ---------------- ----------------- ----------- alpar@1: Wheat Flour 370 lb. $13.33 alpar@1: Evaporated Milk 57 cans 3.84 alpar@1: Cabbage 111 lb. 4.11 alpar@1: Spinach 23 lb. 1.85 alpar@1: Dried Navy Beans 285 lb. 16.80 alpar@1: ---------------------------------------------- alpar@1: Total Annual Cost $39.93 alpar@1: alpar@1: The 9 nutrients that Stigler's diet took into consideration and their alpar@1: respective recommended daily amounts were: alpar@1: alpar@1: Table of nutrients considered in Stigler's diet alpar@1: alpar@1: Nutrient Daily Recommended Intake alpar@1: ------------------------- ------------------------ alpar@1: Calories 3,000 Calories alpar@1: Protein 70 grams alpar@1: Calcium .8 grams alpar@1: Iron 12 milligrams alpar@1: Vitamin A 5,000 IU alpar@1: Thiamine (Vitamin B1) 1.8 milligrams alpar@1: Riboflavin (Vitamin B2) 2.7 milligrams alpar@1: Niacin 18 milligrams alpar@1: Ascorbic Acid (Vitamin C) 75 milligrams alpar@1: alpar@1: Seven years after Stigler made his initial estimates, the development alpar@1: of George Dantzig's Simplex algorithm made it possible to solve the alpar@1: problem without relying on heuristic methods. The exact value was alpar@1: determined to be $39.69 (using the original 1939 data). Dantzig's alpar@1: algorithm describes a method of traversing the vertices of a polytope alpar@1: of N+1 dimensions in order to find the optimal solution to a specific alpar@1: situation. alpar@1: alpar@1: (From Wikipedia, the free encyclopedia.) */ alpar@1: alpar@1: /* Translated from GAMS by Andrew Makhorin . alpar@1: alpar@1: For the original GAMS model stigler1939.gms see [3]. alpar@1: alpar@1: References: alpar@1: alpar@1: 1. George J. Stigler, "The Cost of Subsistence," J. Farm Econ. 27, alpar@1: 1945, pp. 303-14. alpar@1: alpar@1: 2. National Research Council, "Recommended Daily Allowances," Reprint alpar@1: and Circular Series No. 115, January, 1943. alpar@1: alpar@1: 3. Erwin Kalvelagen, "Model building with GAMS," Chapter 2, "Building alpar@1: linear programming models," pp. 128-34. */ alpar@1: alpar@1: set C; alpar@1: /* commodities */ alpar@1: alpar@1: check card(C) = 77; alpar@1: /* there must be 77 commodities */ alpar@1: alpar@1: set N; alpar@1: /* nutrients */ alpar@1: alpar@1: param data{c in C, {"price", "weight"} union N}; alpar@1: /* nutritive values per dollar of expenditure */ alpar@1: alpar@1: param allowance{n in N}; alpar@1: /* recommended daily allowance for a moderately active man */ alpar@1: alpar@1: var x{c in C}, >= 0; alpar@1: /* dollars of food to be purchased daily */ alpar@1: alpar@1: s.t. nb{n in N}: sum{c in C} data[c,n] * x[c] >= allowance[n]; alpar@1: /* nutrient balance */ alpar@1: alpar@1: minimize cost: sum{c in C} x[c]; alpar@1: /* total food bill */ alpar@1: alpar@1: solve; alpar@1: alpar@1: param days := 365.25; alpar@1: /* days in a year */ alpar@1: alpar@1: param commodity{c in C}, symbolic; alpar@1: alpar@1: param unit{c in C}, symbolic; alpar@1: alpar@1: printf "\n"; alpar@1: printf "MINIMUM COST ANNUAL DIET\n"; alpar@1: printf "\n"; alpar@1: printf " Commodity Unit Quantity Cost \n"; alpar@1: printf "------------------------- ---------- ---------- ----------\n"; alpar@1: printf{c in C: x[c] != 0} "%-25s %10s %10.2f $%7.2f\n", commodity[c], alpar@1: unit[c], 100 * days * x[c] / data[c,"price"], days * x[c]; alpar@1: printf " -----------------\n"; alpar@1: printf " Total: $%7.2f\n", alpar@1: days * sum{c in C} x[c]; alpar@1: printf "\n"; alpar@1: alpar@1: data; alpar@1: alpar@1: param : C : commodity unit := alpar@1: flour "Wheat Flour (Enriched)" "10 lb." alpar@1: macaroni "Macaroni" "1 lb." alpar@1: cereal "Wheat Cereal (Enriched)" "28 oz." alpar@1: cornflakes "Corn Flakes" "8 oz." alpar@1: cornmeal "Corn Meal" "1 lb." alpar@1: grits "Hominy Grits" "24 oz." alpar@1: rice "Rice" "1 lb." alpar@1: oats "Rolled Oats" "1 lb." alpar@1: whitebread "White Bread (Enriched)" "1 lb." alpar@1: wheatbread "Whole Wheat Bread" "1 lb." alpar@1: ryebread "Rye Bread" "1 lb." alpar@1: poundcake "Pound Cake" "1 lb." alpar@1: crackers "Soda Crackers" "1 lb." alpar@1: milk "Milk" "1 qt." alpar@1: evapmild "Evaporated Milk (can)" "14.5 oz." alpar@1: butter "Butter" "1 lb." alpar@1: margarine "Oleomargarine" "1 lb." alpar@1: eggs "Eggs" "1 doz." alpar@1: cheese "Cheese (Cheddar)" "1 lb." alpar@1: cream "Cream" "1/2 pt." alpar@1: peanutbutter "Peanut Butter" "1 lb." alpar@1: mayonnaise "Mayonnaise" "1/2 pt." alpar@1: crisco "Crisco" "1 lb." alpar@1: lard "Lard" "1 lb." alpar@1: sirloinsteak "Sirloin Steak" "1 lb." alpar@1: roundsteak "Round Steak" "1 lb." alpar@1: ribroast "Rib Roast" "1 lb." alpar@1: chuckroast "Chuck Roast" "1 lb." alpar@1: plate "Plate" "1 lb." alpar@1: liver "Liver (Beef)" "1 lb." alpar@1: lambleg "Leg of Lamb" "1 lb." alpar@1: lambchops "Lamb Chops (Rib)" "1 lb." alpar@1: porkchops "Pork Chops" "1 lb." alpar@1: porkroast "Pork Loin Roast" "1 lb." alpar@1: bacon "Bacon" "1 lb." alpar@1: ham "Ham - smoked" "1 lb." alpar@1: saltpork "Salt Pork" "1 lb." alpar@1: chicken "Roasting Chicken" "1 lb." alpar@1: veal "Veal Cutlets" "1 lb." alpar@1: salmon "Salmon, Pink (can)" "16 oz." alpar@1: apples "Apples" "1 lb." alpar@1: bananas "Bananas" "1 lb." alpar@1: lemons "Lemons" "1 doz." alpar@1: oranges "Oranges" "1 doz." alpar@1: greenbeans "Green Beans" "1 lb." alpar@1: cabbage "Cabbage" "1 lb." alpar@1: carrots "Carrots" "1 bunch" alpar@1: celery "Celery" "1 stalk" alpar@1: lettuce "Lettuce" "1 head" alpar@1: onions "Onions" "1 lb." alpar@1: potatoes "Potatoes" "15 lb." alpar@1: spinach "Spinach" "1 lb." alpar@1: sweetpotato "Sweet Potatoes" "1 lb." alpar@1: peaches "Peaches (can)" "No. 2 1/2" alpar@1: pears "Pears (can)" "No. 2 1/2" alpar@1: pineapple "Pineapple (can)" "No. 2 1/2" alpar@1: asparagus "Asparagus (can)" "No. 2" alpar@1: cannedgrbn "Grean Beans (can)" "No. 2" alpar@1: porkbeans "Pork and Beans (can)" "16 oz." alpar@1: corn "Corn (can)" "No. 2" alpar@1: peas "Peas (can)" "No. 2" alpar@1: tomatoes "Tomatoes (can)" "No. 2" alpar@1: tomatosoup "Tomato Soup (can)" "10 1/2 oz." alpar@1: driedpeach "Peaches, Dried" "1 lb." alpar@1: prunes "Prunes, Dried" "1 lb." alpar@1: raisins "Raisins, Dried" "15 oz." alpar@1: driedpeas "Peas, Dried" "1 lb." alpar@1: limabeans "Lima Beans, Dried" "1 lb." alpar@1: navybeans "Navy Beans, Dried" "1 lb." alpar@1: coffee "Coffee" "1 lb." alpar@1: tea "Tea" "1/4 lb." alpar@1: cocoa "Cocoa" "8 oz." alpar@1: chocolate "Chocolate" "8 oz." alpar@1: sugar "Sugar" "10 lb." alpar@1: cornsirup "Corn Sirup" "24 oz." alpar@1: molasses "Molasses" "18 oz." alpar@1: stawberry "Strawberry Preserve" "1 lb." alpar@1: ; alpar@1: alpar@1: set N := alpar@1: calories /* Calories, unit = 1000 */ alpar@1: protein /* Protein, unit = grams */ alpar@1: calcium /* Calcium, unit = grams */ alpar@1: iron /* Iron, unit = milligrams */ alpar@1: vitaminA /* Vitamin A, unit = 1000 International Units */ alpar@1: thiamine /* Thiamine, Vit. B1, unit = milligrams */ alpar@1: riboflavin /* Riboflavin, Vit. B2, unit = milligrams */ alpar@1: niacin /* Niacin (Nicotinic Acid), unit = milligrams */ alpar@1: ascorbicAcid /* Ascorbic Acid, Vit. C, unit = milligrams */ alpar@1: ; alpar@1: alpar@1: param data alpar@1: : price weight calories protein calcium iron := alpar@1: # aug. 15 edible alpar@1: # 1939 per $1 alpar@1: # (cents) (grams) (1000) (grams) (grams) (mg.) alpar@1: flour 36.0 12600 44.7 1411 2.0 365 alpar@1: macaroni 14.1 3217 11.6 418 .7 54 alpar@1: cereal 24.2 3280 11.8 377 14.4 175 alpar@1: cornflakes 7.1 3194 11.4 252 .1 56 alpar@1: cornmeal 4.6 9861 36.0 897 1.7 99 alpar@1: grits 8.5 8005 28.6 680 .8 80 alpar@1: rice 7.5 6048 21.2 460 .6 41 alpar@1: oats 7.1 6389 25.3 907 5.1 341 alpar@1: whitebread 7.9 5742 15.6 488 2.5 115 alpar@1: wheatbread 9.1 4985 12.2 484 2.7 125 alpar@1: ryebread 9.2 4930 12.4 439 1.1 82 alpar@1: poundcake 24.8 1829 8.0 130 .4 31 alpar@1: crackers 15.1 3004 12.5 288 .5 50 alpar@1: milk 11.0 8867 6.1 310 10.5 18 alpar@1: evapmild 6.7 6035 8.4 422 15.1 9 alpar@1: butter 20.8 1473 10.8 9 .2 3 alpar@1: margarine 16.1 2817 20.6 17 .6 6 alpar@1: eggs 32.6 1857 2.9 238 1.0 52 alpar@1: cheese 24.2 1874 7.4 448 16.4 19 alpar@1: cream 14.1 1689 3.5 49 1.7 3 alpar@1: peanutbutter 17.9 2534 15.7 661 1.0 48 alpar@1: mayonnaise 16.7 1198 8.6 18 .2 8 alpar@1: crisco 20.3 2234 20.1 0 .0 0 alpar@1: lard 9.8 4628 41.7 0 .0 0 alpar@1: sirloinsteak 39.6 1145 2.9 166 .1 34 alpar@1: roundsteak 36.4 1246 2.2 214 .1 32 alpar@1: ribroast 29.2 1553 3.4 213 .1 33 alpar@1: chuckroast 22.6 2007 3.6 309 .2 46 alpar@1: plate 14.6 3107 8.5 404 .2 62 alpar@1: liver 26.8 1692 2.2 333 .2 139 alpar@1: lambleg 27.6 1643 3.1 245 .1 20 alpar@1: lambchops 36.6 1239 3.3 140 .1 15 alpar@1: porkchops 30.7 1477 3.5 196 .2 80 alpar@1: porkroast 24.2 1874 4.4 249 .3 37 alpar@1: bacon 25.6 1772 10.4 152 .2 23 alpar@1: ham 27.4 1655 6.7 212 .2 31 alpar@1: saltpork 16.0 2835 18.8 164 .1 26 alpar@1: chicken 30.3 1497 1.8 184 .1 30 alpar@1: veal 42.3 1072 1.7 156 .1 24 alpar@1: salmon 13.0 3489 5.8 705 6.8 45 alpar@1: apples 4.4 9072 5.8 27 .5 36 alpar@1: bananas 6.1 4982 4.9 60 .4 30 alpar@1: lemons 26.0 2380 1.0 21 .5 14 alpar@1: oranges 30.9 4439 2.2 40 1.1 18 alpar@1: greenbeans 7.1 5750 2.4 138 3.7 80 alpar@1: cabbage 3.7 8949 2.6 125 4.0 36 alpar@1: carrots 4.7 6080 2.7 73 2.8 43 alpar@1: celery 7.3 3915 .9 51 3.0 23 alpar@1: lettuce 8.2 2247 .4 27 1.1 22 alpar@1: onions 3.6 11844 5.8 166 3.8 59 alpar@1: potatoes 34.0 16810 14.3 336 1.8 118 alpar@1: spinach 8.1 4592 1.1 106 .0 138 alpar@1: sweetpotato 5.1 7649 9.6 138 2.7 54 alpar@1: peaches 16.8 4894 3.7 20 .4 10 alpar@1: pears 20.4 4030 3.0 8 .3 8 alpar@1: pineapple 21.3 3993 2.4 16 .4 8 alpar@1: asparagus 27.7 1945 .4 33 .3 12 alpar@1: cannedgrbn 10.0 5386 1.0 54 2.0 65 alpar@1: porkbeans 7.1 6389 7.5 364 4.0 134 alpar@1: corn 10.4 5452 5.2 136 .2 16 alpar@1: peas 13.8 4109 2.3 136 .6 45 alpar@1: tomatoes 8.6 6263 1.3 63 .7 38 alpar@1: tomatosoup 7.6 3917 1.6 71 .6 43 alpar@1: driedpeach 15.7 2889 8.5 87 1.7 173 alpar@1: prunes 9.0 4284 12.8 99 2.5 154 alpar@1: raisins 9.4 4524 13.5 104 2.5 136 alpar@1: driedpeas 7.9 5742 20.0 1367 4.2 345 alpar@1: limabeans 8.9 5097 17.4 1055 3.7 459 alpar@1: navybeans 5.9 7688 26.9 1691 11.4 792 alpar@1: coffee 22.4 2025 .0 0 .0 0 alpar@1: tea 17.4 652 .0 0 .0 0 alpar@1: cocoa 8.6 2637 8.7 237 3.0 72 alpar@1: chocolate 16.2 1400 8.0 77 1.3 39 alpar@1: sugar 51.7 8773 34.9 0 .0 0 alpar@1: cornsirup 13.7 4996 14.7 0 .5 74 alpar@1: molasses 13.6 3752 9.0 0 10.3 244 alpar@1: stawberry 20.5 2213 6.4 11 .4 7 alpar@1: alpar@1: : vitaminA thiamine riboflavin niacin ascorbicAcid := alpar@1: # (1000 IU) (mg.) (mg.) (mg.) (mg.) alpar@1: flour .0 55.4 33.3 441 0 alpar@1: macaroni .0 3.2 1.9 68 0 alpar@1: cereal .0 14.4 8.8 114 0 alpar@1: cornflakes .0 13.5 2.3 68 0 alpar@1: cornmeal 30.9 17.4 7.9 106 0 alpar@1: grits .0 10.6 1.6 110 0 alpar@1: rice .0 2.0 4.8 60 0 alpar@1: oats .0 37.1 8.9 64 0 alpar@1: whitebread .0 13.8 8.5 126 0 alpar@1: wheatbread .0 13.9 6.4 160 0 alpar@1: ryebread .0 9.9 3.0 66 0 alpar@1: poundcake 18.9 2.8 3.0 17 0 alpar@1: crackers .0 .0 .0 0 0 alpar@1: milk 16.8 4.0 16.0 7 177 alpar@1: evapmild 26.0 3.0 23.5 11 60 alpar@1: butter 44.2 .0 .2 2 0 alpar@1: margarine 55.8 .2 .0 0 0 alpar@1: eggs 18.6 2.8 6.5 1 0 alpar@1: cheese 28.1 .8 10.3 4 0 alpar@1: cream 16.9 .6 2.5 0 17 alpar@1: peanutbutter .0 9.6 8.1 471 0 alpar@1: mayonnaise 2.7 .4 .5 0 0 alpar@1: crisco .0 .0 .0 0 0 alpar@1: lard .2 .0 .5 5 0 alpar@1: sirloinsteak .2 2.1 2.9 69 0 alpar@1: roundsteak .4 2.5 2.4 87 0 alpar@1: ribroast .0 .0 2.0 0 0 alpar@1: chuckroast .4 1.0 4.0 120 0 alpar@1: plate .0 .9 .0 0 0 alpar@1: liver 169.2 6.4 50.8 316 525 alpar@1: lambleg .0 2.8 3.0 86 0 alpar@1: lambchops .0 1.7 2.7 54 0 alpar@1: porkchops .0 17.4 2.7 60 0 alpar@1: porkroast .0 18.2 3.6 79 0 alpar@1: bacon .0 1.8 1.8 71 0 alpar@1: ham .0 9.9 3.3 50 0 alpar@1: saltpork .0 1.4 1.8 0 0 alpar@1: chicken .1 .9 1.8 68 46 alpar@1: veal .0 1.4 2.4 57 0 alpar@1: salmon 3.5 1.0 4.9 209 0 alpar@1: apples 7.3 3.6 2.7 5 544 alpar@1: bananas 17.4 2.5 3.5 28 498 alpar@1: lemons .0 .5 .0 4 952 alpar@1: oranges 11.1 3.6 1.3 10 1993 alpar@1: greenbeans 69.0 4.3 5.8 37 862 alpar@1: cabbage 7.2 9.0 4.5 26 5369 alpar@1: carrots 188.5 6.1 4.3 89 608 alpar@1: celery .9 1.4 1.4 9 313 alpar@1: lettuce 112.4 1.8 3.4 11 449 alpar@1: onions 16.6 4.7 5.9 21 1184 alpar@1: potatoes 6.7 29.4 7.1 198 2522 alpar@1: spinach 918.4 5.7 13.8 33 2755 alpar@1: sweetpotato 290.7 8.4 5.4 83 1912 alpar@1: peaches 21.5 .5 1.0 31 196 alpar@1: pears .8 .8 .8 5 81 alpar@1: pineapple 2.0 2.8 .8 7 399 alpar@1: asparagus 16.3 1.4 2.1 17 272 alpar@1: cannedgrbn 53.9 1.6 4.3 32 431 alpar@1: porkbeans 3.5 8.3 7.7 56 0 alpar@1: corn 12.0 1.6 2.7 42 218 alpar@1: peas 34.9 4.9 2.5 37 370 alpar@1: tomatoes 53.2 3.4 2.5 36 1253 alpar@1: tomatosoup 57.9 3.5 2.4 67 862 alpar@1: driedpeach 86.8 1.2 4.3 55 57 alpar@1: prunes 85.7 3.9 4.3 65 257 alpar@1: raisins 4.5 6.3 1.4 24 136 alpar@1: driedpeas 2.9 28.7 18.4 162 0 alpar@1: limabeans 5.1 26.9 38.2 93 0 alpar@1: navybeans .0 38.4 24.6 217 0 alpar@1: coffee .0 4.0 5.1 50 0 alpar@1: tea .0 .0 2.3 42 0 alpar@1: cocoa .0 2.0 11.9 40 0 alpar@1: chocolate .0 .9 3.4 14 0 alpar@1: sugar .0 .0 .0 0 0 alpar@1: cornsirup .0 .0 .0 5 0 alpar@1: molasses .0 1.9 7.5 146 0 alpar@1: stawberry .2 .2 .4 3 0 alpar@1: ; alpar@1: alpar@1: param allowance := alpar@1: calories 3 alpar@1: protein 70 alpar@1: calcium .8 alpar@1: iron 12 alpar@1: vitaminA 5 alpar@1: thiamine 1.8 alpar@1: riboflavin 2.7 alpar@1: niacin 18 alpar@1: ascorbicAcid 75 alpar@1: ; alpar@1: alpar@1: end;