NAME:

LOGIN:

PRECEPTS:

COS 226 Exercises on Linear Programming (3 exercises)

1. In the style of the example on page 908 in the book, give a linear-programming formulation of your maxflow problem from exercise 1 of the online maxflow exercises.







































2. (adapted from Chvatal)  Harvard Dining Services wonders how little money they can spend on food while still supplying sufficient energy (2000 kcal), protein (55g), and calcium (800mg) to meet the minimum Federal guidelines and avert a potential lawsuit. A limited selection of potential menu items along with their nutrient content and maximum tolerable quantities per day is given in the table below. 

                 Serving   Energy   Protein   Calcium   Cost per serving   Max servings
Food                Size   (kcal)       (g)      (mg)            (cents)        per day
---------------------------------------------------------------------------------------
Oatmeal              28g      110         4         2                  3              4
Chicken             100g      205        32        12                 24              3
Eggs             2 large      160        13        54                 13              2
Whole milk         237cc      160         8       285                  9              8
Cherry pie          170g      420         4        22                 20              2
Pork with beans     260g      260        14        80                 19              2
Formulate (but do not solve) a linear program to find the most economical menu.





















3.   Convert the linear program above to standard form: maximizing a linear objective function, subject to equality constraints and nonnegative variables.