This LPs you construct in this assignment should be your own work!

1. The purpose of this question is for you to find a low cost diet for yourself meeting various minimum requirements using linear programming. Choose about 10 foods or snacks that you like and record the price and nutrition information from the labels. Formulate a linear program that finds a diet of minimum cost using these foods and satisfying the minimum requirements of vitamins and minerals given below. Put a bound on the calory intake also (recommended at 1900 for women and 2700 for men, but choose your own). Also put an upper bound (and lower bound if you like) on the amount of each food you are willing to eat.

(a) Write out the primal and dual problems.

(b) Use lp_solve to find the solution, and give both the primal and dual solutions.

(c) Verify optimality by hand (see section 2.1 and 2.2 of class notes). Can you find any interpretation of the dual variables?

vitamin A vitamin D vitamin E vitamin C calcium iron protein |
RE mcg mg mg mg mg g |
1000 5 10 60 800 14 55 |

2. (a) Construct a linear program with at least 3 variables and 3 constraints, and all data a

Give a proof of infeasiblity as described in Section 2.3. Verify infeasibility using lp_solve.

(b) Write down the dual of your problem. Use lp_solve to see if it is infeasible or unbounded. Give a proof of the result as described in Section 2.3 or 2.4 respectively.