Assignments are to be left in the box near the labs, McConnell
1st floor. Late assignments: -10% per day
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 aij, bi,
cj non-zero, that is infeasible.
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.