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 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.