1. (adapted from Chvatal) PU Dining Services wonders how little money they can spend on food while still supplying sufficient energy (200 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.
2. Convert the linear program above to standard form: a maximization
problem with equality constraints and nonnegative variables.