Math 132A Assignment 1
1. Consider the following table indicating the nutritional value of diferent food types.
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 an 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.
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. The CRUD chemical plant produces, as part of its production process, the noxious compound chemical X. Chemical X is highly toxic and needs to be disposed of properly. Fortunately, CRUD is linked by a pipe system to the FRESHAIR recycling plant that can safely reprocess chemical X. On any given day, the CRUD plant produces the following amount of chemical X.
Because of environmental regulations, at no point in time is the CRUD plant allowed to keep more than 1000ℓ of chemical X on site, and no amount of chemical X can be kept overnight.
At the top of every hour, an arbitrary amount of chemical X can be sent to FRESHAIR. The cost of recycling chemical X varies throughout the day according the following table.
Write an LP that will decide how much of chemical X to send from CRUD to FRESHAIR at the top of each hour so that you minimize the total cost but meet all environmental constraints.
4. (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 one direction, set x11 = min(s1 , t1 ) . Can you find a transportation problem with fewer factories and/or stores such that feasible solutions of the smaller program extend to feasible solutions of the original? )
5. Let t be a real number and consider the following LP
(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 oft 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.