COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/examples/stigler.mod

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 19.5 KB
Line 
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."
220stawberry      "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
316stawberry     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
396stawberry       .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;
Note: See TracBrowser for help on using the repository browser.