stigler.mod

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* 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 <[e-mail]>.

   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."