Math 171A: Linear Programming
Instructor: Philip E. Gill© 2021 (Not to be Reposted)
Winter Quarter 2021
Homework Assignment #1
Due Friday January 15, 2021
I know that you are all aware of the importance of doing the homework assignments. This
is the best way to keep up with the class and do well in the midterm and final examinations.
Unfortunately, the graders will not have the time to grade every exercise. Instead, they will
grade two or three exercises (including at least one Matlab exercise) and give a fixed score
for every other exercise attempted.
The starred exercises require the use of Matlab. Remember that it is necessary to do all
the Matlab assignments to obtain credit for the class.
Exercise 1.1. In the JuiceCo mixture problem considered in class, x represents gallons of
cranapple, y gallons of appleberry.
(a) How many gallons of each juice mixture are represented by each corner point? Evaluate
the profit formula 3x+ 4y at each corner point of the feasible region.
(b) Which corner point represents the maximum profit for each of the following profit
formulas:
(i) profit = 3x+ 4y (the definition used in class);
(ii) profit = 2x+ 5y;
(iii) profit = 5x+ 3y.
Exercise 1.2. Convert the JuiceCo problem into “all-inequality form” min cTx, subject to
Ax ≥ b and define the quantities A, b, and c.
Exercise 1.3. Consider the following constraints in two variables: (1) x1 − 2x2 ≤ −1; (2)
x1 − x2 ≥ −3; (3) 12 ≤ x2 ≤ 4; (4) 2x1 − 2x2 ≤ 6; (5) x1 + x2 ≤ 6; (6) x1 ≥ 0; and (7)
x2 ≥ 0.
(a) Define the matrix A and vector b that express these constraints in the form Ax ≥ b.
(b) Draw the feasible region defined by the 8 constraints. Outline the feasible region on
your graph and label each of the corner points.
(c) Draw the level curve along which the linear function −2x1 − x2 is equal to −8.
(d) Draw the level curve along which the linear function −x1 − x2 is equal to −6.
Exercise 1.4. Suppose that your diet consists of a selection of the following items from a
well-known fast food restaurant (we give each food a nickname to assist in referring to it):
QP: Quarter Pounder FR: Fries, small
MD: McLean Deluxe SM: Sausage McMuffin
BM: Big Mac 1M: 1% Lowfat Milk
FF: Filet-O-Fish OJ: Orange Juice
MC: McGrilled Chicken
2 Mathematics 171A
You are interested in providing your diet with appropriate amounts of the following seven
“nutrients”:
Prot: Protein Iron: Iron
VitA: Vitamin A Cals: Calories
VitC: Vitamin C Carb: Carbohydrates
Calc: Calcium
Using the internet you have found how much of each nutrient is in one serving of each food,
and the total of each nutrient that you require. You also found the price per serving of each
food. The relevant costs, requirements, and nutritional values are:
QP MD BM FF MC FR SM 1M OJ Req’d
Cost 1.84 2.19 1.84 1.44 2.29 0.77 1.29 0.60 0.72
Prot 28 24 25 14 31 3 15 9 1 55
VitA 15 15 6 2 8 0 4 10 2 100
VitC 6 10 2 0 15 15 0 4 120 100
Calc 30 20 25 15 15 0 20 30 2 100
Iron 20 20 20 10 8 2 15 0 2 100
Cals 510 370 500 370 400 220 345 110 80 2000
Carb 34 35 42 38 42 26 27 12 20 350
Formulate a linear program with a solution that defines the least expensive combination of
the foods providing a day’s nutritional requirements. Write the problem in the form min
cTx, subject to Ax ≥ b.
Exercise 1.5.∗ You have formulated the diet problem above as a linear program of the
form min cTx subject to Ax ≥ b.
(a) In class we defined a “corner point” as a feasible point that lies at the intersection of n
hyperplanes. Give an upper limit on the number of corner points for the diet problem.
(Don’t just guess a number, give an estimate based on the row and column dimensions
of the constraint matrix.)
(b) Find three corner points and compute the value of the objective function at each one.
Exercise 1.6. Consider the inequality constraint aTx ≤ b where a 6= 0. Show that the
constraint normal points “into” the infeasible half-space.