lemon-project-template-glpk
view deps/glpk/examples/stigler.mod @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 21:43:29 +0100 |
| parents | |
| children |
line source
1 /* STIGLER, original Stigler's 1939 diet problem */
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?
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.
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.
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:
42 Stigler's 1939 Diet
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
54 The 9 nutrients that Stigler's diet took into consideration and their
55 respective recommended daily amounts were:
57 Table of nutrients considered in Stigler's diet
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
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.
79 (From Wikipedia, the free encyclopedia.) */
81 /* Translated from GAMS by Andrew Makhorin <mao@gnu.org>.
83 For the original GAMS model stigler1939.gms see [3].
85 References:
87 1. George J. Stigler, "The Cost of Subsistence," J. Farm Econ. 27,
88 1945, pp. 303-14.
90 2. National Research Council, "Recommended Daily Allowances," Reprint
91 and Circular Series No. 115, January, 1943.
93 3. Erwin Kalvelagen, "Model building with GAMS," Chapter 2, "Building
94 linear programming models," pp. 128-34. */
96 set C;
97 /* commodities */
99 check card(C) = 77;
100 /* there must be 77 commodities */
102 set N;
103 /* nutrients */
105 param data{c in C, {"price", "weight"} union N};
106 /* nutritive values per dollar of expenditure */
108 param allowance{n in N};
109 /* recommended daily allowance for a moderately active man */
111 var x{c in C}, >= 0;
112 /* dollars of food to be purchased daily */
114 s.t. nb{n in N}: sum{c in C} data[c,n] * x[c] >= allowance[n];
115 /* nutrient balance */
117 minimize cost: sum{c in C} x[c];
118 /* total food bill */
120 solve;
122 param days := 365.25;
123 /* days in a year */
125 param commodity{c in C}, symbolic;
127 param unit{c in C}, symbolic;
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";
141 data;
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 ;
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 ;
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
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 ;
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 ;
411 end;