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