Math 132A Assignment 1
Due: Wednesday, January 15th at midnight. Submit on Gradescope.
1. Consider the following table indicating the nutritional value of diferent food types.
|
Foods
|
Price ($) per serving
|
Calories per serving
|
Fat (g) per serving
|
Protein (g) per serving
|
Carbs (g) per serving
|
|
Raw Carrots
|
0.14
|
23
|
0.1
|
0.6
|
6
|
|
Baked Potatoes
|
0.12
|
171
|
0.2
|
3.7
|
30
|
|
Wheat Bread
|
0.2
|
65
|
0
|
2.2
|
13
|
|
Cheddar Cheese
|
0.75
|
112
|
9.3
|
7
|
0
|
|
Peanut Butter
|
0.15
|
188
|
16
|
7.7
|
2
|
You need to decide how many servings of each food to buy each day so that you minimize the total cost of buying your food while satisfying the following daily nutritional requirements:
• caolories must be at least 2000,
• fat must be at least 50g,
• protein must be at least 100g,
• carbohydrates must be at least 250g.
Write a linear program (LP) that will decide how many servings of each of the aforementioned foods we need to meet all nutritional requirements, while minimizing the total cost of the food. (you may buy fractional numbers of servings). Use an LP solver to actually find an optimal point and optimal value.
Most spreadsheet programs like Excel have an LP solver included. These days you could ask chatGPT to solve it but be careful that it ’s output makes sense! I recommend trying to learn how to do these in Matlab, Mathematica or Maple, or for heavy duty LP problems, CPLEX.
2. The director of a startup needs to decide what salaries to ofer to its employees for the fiscal year 2024. In order to keep the employees satisfied, she needs to make sure of the following.
• Tom wants at least $20, 000 or he will quit.
• Peter, Nina and Samir want each to be paid at least $5000 more than Tom.
• Gary wants his salary to be at least as high as the combined salaries of Tom and Peter.
• Linda wants to make $200 more than Gary.
• The combined salaries of Nina and Samir should be at least twice the combined salary of Tom and Peter.
• Bob’s salary is at least as high as that of Peter’s and at least as high as Samir’s.
• The combined salaries of Bob and Peter should be at least $60, 000.
• Linda should make less money than the combined salaries of Bob and Tom.
(a) Write an LP that will determine the salaries for the employees such that the above constraints are satisfied but the total salary of everyone is minimized.
(b) Write an LP that will determine the salaries for the employees such that the above constraints are satisfied but the salary of the highest paid employee is minimized. Hint: Define a new variable.
3. (A Transportation Problem). A company makes a product at factories 1, 2, . . . , p and sells it to stores 1, 2 . . . , q. Factory i produces si units per month and store j orders tj units per month. Assume that every unit made is shipped to a store, and every store receives exactly the number of units ordered. The cost of shipping one unit of the product from factory i to store j is cij dollars.
(a) Model the problem of finding the cheapest way to ship the product from the factories to the stores as an LP. To start, set xij be the number of units shipped from factory i to store j.
(b) Prove that the feasible region is nonempty if and only if
(Hint: For the hard direction, try showing there is a solution with x11 = min(s1, t1 ) . Can you find a transportation problem with fewer factories or stores such that feasible solutions of the smaller program extend to feasible solutions of the original with this value for x11 ?? )
4. Let t be a real number and consider the following LP
maximize − 2x1 + x2
subject to x1 − x2 ≤ −1
−x1 + tx2 ≤ 0
x1 , x2 ≥ 0.
(a) Let T be the values of t for which the problem has a feasible solution. Use geometry to guess T.
(b) Give an algebraic proof that the LP is feasible if and only if t ∈ T.
(c) Let S be the set of values of t for which the LP is unbounded. Use geometry to guess S.
(d) Give an algebraic proof that the LP is unbounded if and only if t ∈ S.