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 96set C; 97/* commodities */ 98 99check card(C) = 77; 100/* there must be 77 commodities */ 101 102set N; 103/* nutrients */ 104 105param data{c in C, {"price", "weight"} union N}; 106/* nutritive values per dollar of expenditure */ 107 108param allowance{n in N}; 109/* recommended daily allowance for a moderately active man */ 110 111var x{c in C}, >= 0; 112/* dollars of food to be purchased daily */ 113 114s.t. nb{n in N}: sum{c in C} data[c,n] * x[c] >= allowance[n]; 115/* nutrient balance */ 116 117minimize cost: sum{c in C} x[c]; 118/* total food bill */ 119 120solve; 121 122param days := 365.25; 123/* days in a year */ 124 125param commodity{c in C}, symbolic; 126 127param unit{c in C}, symbolic; 128 129printf "\n"; 130printf "MINIMUM COST ANNUAL DIET\n"; 131printf "\n"; 132printf " Commodity Unit Quantity Cost \n"; 133printf "------------------------- ---------- ---------- ----------\n"; 134printf{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]; 136printf " -----------------\n"; 137printf " Total: $%7.2f\n", 138 days * sum{c in C} x[c]; 139printf "\n"; 140 141data; 142 143param : C : commodity unit := 144flour "Wheat Flour (Enriched)" "10 lb." 145macaroni "Macaroni" "1 lb." 146cereal "Wheat Cereal (Enriched)" "28 oz." 147cornflakes "Corn Flakes" "8 oz." 148cornmeal "Corn Meal" "1 lb." 149grits "Hominy Grits" "24 oz." 150rice "Rice" "1 lb." 151oats "Rolled Oats" "1 lb." 152whitebread "White Bread (Enriched)" "1 lb." 153wheatbread "Whole Wheat Bread" "1 lb." 154ryebread "Rye Bread" "1 lb." 155poundcake "Pound Cake" "1 lb." 156crackers "Soda Crackers" "1 lb." 157milk "Milk" "1 qt." 158evapmild "Evaporated Milk (can)" "14.5 oz." 159butter "Butter" "1 lb." 160margarine "Oleomargarine" "1 lb." 161eggs "Eggs" "1 doz." 162cheese "Cheese (Cheddar)" "1 lb." 163cream "Cream" "1/2 pt." 164peanutbutter "Peanut Butter" "1 lb." 165mayonnaise "Mayonnaise" "1/2 pt." 166crisco "Crisco" "1 lb." 167lard "Lard" "1 lb." 168sirloinsteak "Sirloin Steak" "1 lb." 169roundsteak "Round Steak" "1 lb." 170ribroast "Rib Roast" "1 lb." 171chuckroast "Chuck Roast" "1 lb." 172plate "Plate" "1 lb." 173liver "Liver (Beef)" "1 lb." 174lambleg "Leg of Lamb" "1 lb." 175lambchops "Lamb Chops (Rib)" "1 lb." 176porkchops "Pork Chops" "1 lb." 177porkroast "Pork Loin Roast" "1 lb." 178bacon "Bacon" "1 lb." 179ham "Ham - smoked" "1 lb." 180saltpork "Salt Pork" "1 lb." 181chicken "Roasting Chicken" "1 lb." 182veal "Veal Cutlets" "1 lb." 183salmon "Salmon, Pink (can)" "16 oz." 184apples "Apples" "1 lb." 185bananas "Bananas" "1 lb." 186lemons "Lemons" "1 doz." 187oranges "Oranges" "1 doz." 188greenbeans "Green Beans" "1 lb." 189cabbage "Cabbage" "1 lb." 190carrots "Carrots" "1 bunch" 191celery "Celery" "1 stalk" 192lettuce "Lettuce" "1 head" 193onions "Onions" "1 lb." 194potatoes "Potatoes" "15 lb." 195spinach "Spinach" "1 lb." 196sweetpotato "Sweet Potatoes" "1 lb." 197peaches "Peaches (can)" "No. 2 1/2" 198pears "Pears (can)" "No. 2 1/2" 199pineapple "Pineapple (can)" "No. 2 1/2" 200asparagus "Asparagus (can)" "No. 2" 201cannedgrbn "Grean Beans (can)" "No. 2" 202porkbeans "Pork and Beans (can)" "16 oz." 203corn "Corn (can)" "No. 2" 204peas "Peas (can)" "No. 2" 205tomatoes "Tomatoes (can)" "No. 2" 206tomatosoup "Tomato Soup (can)" "10 1/2 oz." 207driedpeach "Peaches, Dried" "1 lb." 208prunes "Prunes, Dried" "1 lb." 209raisins "Raisins, Dried" "15 oz." 210driedpeas "Peas, Dried" "1 lb." 211limabeans "Lima Beans, Dried" "1 lb." 212navybeans "Navy Beans, Dried" "1 lb." 213coffee "Coffee" "1 lb." 214tea "Tea" "1/4 lb." 215cocoa "Cocoa" "8 oz." 216chocolate "Chocolate" "8 oz." 217sugar "Sugar" "10 lb." 218cornsirup "Corn Sirup" "24 oz." 219molasses "Molasses" "18 oz." 220strawberry "Strawberry Preserve" "1 lb." 221; 222 223set N := 224calories /* Calories, unit = 1000 */ 225protein /* Protein, unit = grams */ 226calcium /* Calcium, unit = grams */ 227iron /* Iron, unit = milligrams */ 228vitaminA /* Vitamin A, unit = 1000 International Units */ 229thiamine /* Thiamine, Vit. B1, unit = milligrams */ 230riboflavin /* Riboflavin, Vit. B2, unit = milligrams */ 231niacin /* Niacin (Nicotinic Acid), unit = milligrams */ 232ascorbicAcid /* Ascorbic Acid, Vit. C, unit = milligrams */ 233; 234 235param data 236: price weight calories protein calcium iron := 237# aug. 15 edible 238# 1939 per $1 239# (cents) (grams) (1000) (grams) (grams) (mg.) 240flour 36.0 12600 44.7 1411 2.0 365 241macaroni 14.1 3217 11.6 418 .7 54 242cereal 24.2 3280 11.8 377 14.4 175 243cornflakes 7.1 3194 11.4 252 .1 56 244cornmeal 4.6 9861 36.0 897 1.7 99 245grits 8.5 8005 28.6 680 .8 80 246rice 7.5 6048 21.2 460 .6 41 247oats 7.1 6389 25.3 907 5.1 341 248whitebread 7.9 5742 15.6 488 2.5 115 249wheatbread 9.1 4985 12.2 484 2.7 125 250ryebread 9.2 4930 12.4 439 1.1 82 251poundcake 24.8 1829 8.0 130 .4 31 252crackers 15.1 3004 12.5 288 .5 50 253milk 11.0 8867 6.1 310 10.5 18 254evapmild 6.7 6035 8.4 422 15.1 9 255butter 20.8 1473 10.8 9 .2 3 256margarine 16.1 2817 20.6 17 .6 6 257eggs 32.6 1857 2.9 238 1.0 52 258cheese 24.2 1874 7.4 448 16.4 19 259cream 14.1 1689 3.5 49 1.7 3 260peanutbutter 17.9 2534 15.7 661 1.0 48 261mayonnaise 16.7 1198 8.6 18 .2 8 262crisco 20.3 2234 20.1 0 .0 0 263lard 9.8 4628 41.7 0 .0 0 264sirloinsteak 39.6 1145 2.9 166 .1 34 265roundsteak 36.4 1246 2.2 214 .1 32 266ribroast 29.2 1553 3.4 213 .1 33 267chuckroast 22.6 2007 3.6 309 .2 46 268plate 14.6 3107 8.5 404 .2 62 269liver 26.8 1692 2.2 333 .2 139 270lambleg 27.6 1643 3.1 245 .1 20 271lambchops 36.6 1239 3.3 140 .1 15 272porkchops 30.7 1477 3.5 196 .2 80 273porkroast 24.2 1874 4.4 249 .3 37 274bacon 25.6 1772 10.4 152 .2 23 275ham 27.4 1655 6.7 212 .2 31 276saltpork 16.0 2835 18.8 164 .1 26 277chicken 30.3 1497 1.8 184 .1 30 278veal 42.3 1072 1.7 156 .1 24 279salmon 13.0 3489 5.8 705 6.8 45 280apples 4.4 9072 5.8 27 .5 36 281bananas 6.1 4982 4.9 60 .4 30 282lemons 26.0 2380 1.0 21 .5 14 283oranges 30.9 4439 2.2 40 1.1 18 284greenbeans 7.1 5750 2.4 138 3.7 80 285cabbage 3.7 8949 2.6 125 4.0 36 286carrots 4.7 6080 2.7 73 2.8 43 287celery 7.3 3915 .9 51 3.0 23 288lettuce 8.2 2247 .4 27 1.1 22 289onions 3.6 11844 5.8 166 3.8 59 290potatoes 34.0 16810 14.3 336 1.8 118 291spinach 8.1 4592 1.1 106 .0 138 292sweetpotato 5.1 7649 9.6 138 2.7 54 293peaches 16.8 4894 3.7 20 .4 10 294pears 20.4 4030 3.0 8 .3 8 295pineapple 21.3 3993 2.4 16 .4 8 296asparagus 27.7 1945 .4 33 .3 12 297cannedgrbn 10.0 5386 1.0 54 2.0 65 298porkbeans 7.1 6389 7.5 364 4.0 134 299corn 10.4 5452 5.2 136 .2 16 300peas 13.8 4109 2.3 136 .6 45 301tomatoes 8.6 6263 1.3 63 .7 38 302tomatosoup 7.6 3917 1.6 71 .6 43 303driedpeach 15.7 2889 8.5 87 1.7 173 304prunes 9.0 4284 12.8 99 2.5 154 305raisins 9.4 4524 13.5 104 2.5 136 306driedpeas 7.9 5742 20.0 1367 4.2 345 307limabeans 8.9 5097 17.4 1055 3.7 459 308navybeans 5.9 7688 26.9 1691 11.4 792 309coffee 22.4 2025 .0 0 .0 0 310tea 17.4 652 .0 0 .0 0 311cocoa 8.6 2637 8.7 237 3.0 72 312chocolate 16.2 1400 8.0 77 1.3 39 313sugar 51.7 8773 34.9 0 .0 0 314cornsirup 13.7 4996 14.7 0 .5 74 315molasses 13.6 3752 9.0 0 10.3 244 316strawberry 20.5 2213 6.4 11 .4 7 317 318: vitaminA thiamine riboflavin niacin ascorbicAcid := 319# (1000 IU) (mg.) (mg.) (mg.) (mg.) 320flour .0 55.4 33.3 441 0 321macaroni .0 3.2 1.9 68 0 322cereal .0 14.4 8.8 114 0 323cornflakes .0 13.5 2.3 68 0 324cornmeal 30.9 17.4 7.9 106 0 325grits .0 10.6 1.6 110 0 326rice .0 2.0 4.8 60 0 327oats .0 37.1 8.9 64 0 328whitebread .0 13.8 8.5 126 0 329wheatbread .0 13.9 6.4 160 0 330ryebread .0 9.9 3.0 66 0 331poundcake 18.9 2.8 3.0 17 0 332crackers .0 .0 .0 0 0 333milk 16.8 4.0 16.0 7 177 334evapmild 26.0 3.0 23.5 11 60 335butter 44.2 .0 .2 2 0 336margarine 55.8 .2 .0 0 0 337eggs 18.6 2.8 6.5 1 0 338cheese 28.1 .8 10.3 4 0 339cream 16.9 .6 2.5 0 17 340peanutbutter .0 9.6 8.1 471 0 341mayonnaise 2.7 .4 .5 0 0 342crisco .0 .0 .0 0 0 343lard .2 .0 .5 5 0 344sirloinsteak .2 2.1 2.9 69 0 345roundsteak .4 2.5 2.4 87 0 346ribroast .0 .0 2.0 0 0 347chuckroast .4 1.0 4.0 120 0 348plate .0 .9 .0 0 0 349liver 169.2 6.4 50.8 316 525 350lambleg .0 2.8 3.0 86 0 351lambchops .0 1.7 2.7 54 0 352porkchops .0 17.4 2.7 60 0 353porkroast .0 18.2 3.6 79 0 354bacon .0 1.8 1.8 71 0 355ham .0 9.9 3.3 50 0 356saltpork .0 1.4 1.8 0 0 357chicken .1 .9 1.8 68 46 358veal .0 1.4 2.4 57 0 359salmon 3.5 1.0 4.9 209 0 360apples 7.3 3.6 2.7 5 544 361bananas 17.4 2.5 3.5 28 498 362lemons .0 .5 .0 4 952 363oranges 11.1 3.6 1.3 10 1993 364greenbeans 69.0 4.3 5.8 37 862 365cabbage 7.2 9.0 4.5 26 5369 366carrots 188.5 6.1 4.3 89 608 367celery .9 1.4 1.4 9 313 368lettuce 112.4 1.8 3.4 11 449 369onions 16.6 4.7 5.9 21 1184 370potatoes 6.7 29.4 7.1 198 2522 371spinach 918.4 5.7 13.8 33 2755 372sweetpotato 290.7 8.4 5.4 83 1912 373peaches 21.5 .5 1.0 31 196 374pears .8 .8 .8 5 81 375pineapple 2.0 2.8 .8 7 399 376asparagus 16.3 1.4 2.1 17 272 377cannedgrbn 53.9 1.6 4.3 32 431 378porkbeans 3.5 8.3 7.7 56 0 379corn 12.0 1.6 2.7 42 218 380peas 34.9 4.9 2.5 37 370 381tomatoes 53.2 3.4 2.5 36 1253 382tomatosoup 57.9 3.5 2.4 67 862 383driedpeach 86.8 1.2 4.3 55 57 384prunes 85.7 3.9 4.3 65 257 385raisins 4.5 6.3 1.4 24 136 386driedpeas 2.9 28.7 18.4 162 0 387limabeans 5.1 26.9 38.2 93 0 388navybeans .0 38.4 24.6 217 0 389coffee .0 4.0 5.1 50 0 390tea .0 .0 2.3 42 0 391cocoa .0 2.0 11.9 40 0 392chocolate .0 .9 3.4 14 0 393sugar .0 .0 .0 0 0 394cornsirup .0 .0 .0 5 0 395molasses .0 1.9 7.5 146 0 396strawberry .2 .2 .4 3 0 397; 398 399param allowance := 400calories 3 401protein 70 402calcium .8 403iron 12 404vitaminA 5 405thiamine 1.8 406riboflavin 2.7 407niacin 18 408ascorbicAcid 75 409; 410 411end; 412