Midterm Group 1

July 8, 2022

1 Midterm Summer 2021

1.1 Instructions

•  Print out or download this file and complete the exam in the blank areas provided. You may also write your answers on a separate sheet of paper, then scan/upload the answers.

•  You are responsible for making sure your answers are legible. Use a scanner or a high-quality camera if you are completing the exam by hand (not typed).

• The exam is open book, open notes.

•  This is an individual assignment. If there is evidence of improper collaboration, all parties involved will receive a score of 0 and will be reported to the Office of Student Conduct and Community Standards.

•  You are not allowed to use Julia code in your solution. All your answers must be written in math, not code.

•  The more clearly you write your answer, the better the chance that we can grade it accurately and give it full credit.  In particular, you may write down any assumptions you make in

solving the problems.

•  This exam has 5 problems. The number of points for each problem is displayed at the end of the problem’s title. Please use your time wisely.

• Good luck! R-E-L-A-X. I am rooting for you.

Problem	Points
1	28
2	10
3	22
4	14 (+ 3 points)
5	20
Total:	94 (+3 bonus)

1.2    Problem 1: Tanks for the Food (28 points)

The Martian colonies have to produce their own storage containers for their daily provisions. The production factory makes three types of temperature-resistant tanks: water storage (W), perish- able food storage (P), and nonperishable food storage (N). Any colonist can purchase the tanks for personal use. Un-purchased tanks can be re-purposed for general use. The maximum demand this quarter for tanks of type i is estimated to be di. Tanks of type i can be sold for pi colony credits per tank.  It costs ci  to repurpose a tank of type i, but the repurposed tanks can be sold to the government for C credits per tank (independent of the original type of tank). Each tank requires a certain amount of time to produce it, ai  hours per tank for i  ∈ {W, P, N}.  Each tank requires bi  (i ∈ {W, P, N}) tons of plasteel alloy to be produced.  There are B tons of plasteel alloy and A hours available this quarter.

You are tasked with formulating a linear program to maximize the tanks production facility’s profit this quarter.

1.2.1    (a) (3 points) What are the decision variables?

1.2.2    (b) (4 points) What is the objective function?

1.2.3    (c) (8 points) What are the constraints?

1.2.4    (d) (5 points) Suppose the tank production facility wants ensure that at least 25% of the storage tanks that are produced are for nonperishable food storage.  Write a linear constraint to model this.

1.2.5    (e) (5 points) Now suppose the tank production facility wants to sell at least as many water storage tanks as perishable food storage tanks. Write a linear constraint to model this.

1.2.6 (f) (3 points) Finally, suppose each tank of type i can store up to si liters.  Write a linear constraint that models the requirement that the average tank size of all tanks repurposed this month is S liters.

1.3 Problem 2: Duality Theory (10 points)

(P)       z* = max{cTx | Ax ≤ b, x ≥ 0}

(D)       y* = min{bTy | yTA ≥ c, y ≥ 0}

Given an optimal solution x* to (P) and an optimal solution y* to (D), define the slack variables s* = b — Ax* and t* = y TA — c. Use strong duality to show that xj(*)tj(*) = 0 ∀j andyi(*)si(*) = 0 ∀i

1.4 Problem 3: Alien Puzzles (22 points)

A group of explorers set out to travel the Martian wilderness and were surprised to discover an ancient puzzle hidden in an abandoned cave.   The puzzle seemed to be describing a meeting between two alien races: the Ildirans and the Hydrogues. The puzzle was as follows:

“An impossible challenge: 3 times your Ildirans plus your Hydrogues must be 8. 2 times your Ildirans plus 5 times your Hydrogues must be 3. Your Ildirans minus your Hydrogues must be 7! How will you choose your Ildirans and your Hydrogues?”

The explorers have interpreted the puzzle to be asking them to solve the following equations:

3I + H    =   8

2I + 5H    =   3

I — H    =   7

The explorers are expert linear algebrists and know they cannot solve this problem. Instead, they will try to do the best they can with a variety of approaches, hoping one of their answers will reveal ancient alien secrets.

1.4.1    (a) (3 points) Give a mathematical argument (i.e., proof) that this system of equations has no solution. What do we call this situation?

1.4.2 (b) (5 points) Formulate a linear program that will find a solution (I, H) that will mini-

mizethe total absolute deviation (i.e., one-norm) in the three constraints.

1.4.3    (c) (5 points) One of the explorers pipes up that she found another piece of the riddle. It states that the “maximum deviation of any of the three equations must be no more than

5.” Add linear constraints to your answer from Problem 3(b) to enforce this restriction.

1.4.4    (d) (4 points) After solving the first version of this problem, nothing happens. Growing frustrated, the explorers decide to give up on linear programming. Instead, they would like to minimize the 2-norm of the violation of the original equations in the problem statement. Modify your answer to Problem 3(b) to enforce this. Add one final constraint to your problem that must be met, even if the other constraints are not met: I + H = 15. Write down your complete (nonlinear) optimization model. What type of problem is this?

1.4.5    (e) (5 points) Write a set of linear equalities that will give you the optimal solution to Problem 3(d).

1.5    Problem 4: The Crops are Too Sensitive (14 points + 3 bonus points)

The Martian colony produces 3 major crops: corn, wheat, and potatoes. The production is limited by the number of acres of farmland available and the gallons of water available to irrigate the soil. Furthermore, corn is used for other products so it has an upper bound on how much can be sold. We can write a linear program to maximize the profit generated by these three crops as follows:

max z = p1x1+ p2x2+ p3x3

a11x1+a12x2+a13x3  ≤ b1     (acreage)

a21x1+a22x2+a23x3  ≤ b2     (water availability)

x1                                   ≤ b3      (max corn sales)

x1,       x2,       x3  ≥ 0

where xj  represents the tons of product j to produce and sell, j  =  1, 2, 3  (1=corn, 2 = wheat, 3=potatoes).

We can solve this linear program to obtain an optimal solution of (x1(*), x2(*), x3(*)) = (10,?, 0).

1.5.1    (a) (4 points) Write the dual of this linear program. Clearly indicate the relationship between your dual variables and constraints and your primal variables and constraints.

1.5.2 (b) (4 points) Suppose the dual optimal solution is (λ1(*), λ2(*), λ3(*)) =  (3, 1, 0). What is x2(*)?

Show how you determined it.

x2(*) =

1.5.3    (c) (3 points) Suppose we are able to purchase δ additional acres of farmland. How much would we be willing to pay for an additional acre? What can you say about the new

optimal objective value if we purchase all δ acres? Explain your reasoning.

zew = ≤–

1.5.4    (d) (3 points) Suppose the profit per ton of corn increases by e. What can you say about

the new optimal objective value? Explain your reasoning.

zew = ≤–

Choose one

1.5.5    (e) (Challenge: 3 bonus points) The colonists are considering adding lettuce to the farm.

Lettuce requires a14 acres and would produce p4 dollars per ton in profit. For what value U would it be profitable to produce and sell lettuce if it required less than U gallons of

water to irrigate the lettuce crop?

1.6    Problem 5: (Space)Ship-Shape (20 points)

Martian Transport, Inc., builds two types of spacecraft: shuttles (for travel across the Martian sur- face) and rockets (for transport back to Earth). The ships are made from three metals: aluminum, silica, and titanium.  The data summarizing how much of each material (in millions of tons) is required and the revenue generated for each type of spacecraft is summarized below:

Spacecraft    Profit (\$)    Aluminium    Silica    Titanium

Shuttle          ps                           a                        b            0

Rocket           pr                           c                       d            e

There are 20 million tons of aluminum, 5 million tons of silica, and 10 million tons of titanium available for spacecraft production.  To meet demand, the number of rockets made must not be more than 1 greater than the number of shuttles made.

1.6.1 (a) (5 points) Let xs be the number of shuttles to produce, and let xr be the number of rockets to produce. Formulate a linear program to maximize profit subject to the neces-

sary constraints.

1.6.2    (b) (5 points) For simplicity, assume that a, b, c, d, and e are > 0.  Which of the regions shown on this graph below (A-J) could represent the feasible region of your linear pro- gram?

1.6.3    (c) (2 points) Does this linear program have a finite optimal solution for any choice of pr

and ps?Why or why not?

1.6.4 (d) (4 points) Let a = 5, b = 1, c = 4, and d = 2. Solve this linear program for an objective function with a slope of -1. Solve this LP using the graphical method. What is the optimal solution (x, x)?

1.6.5 (e) (4 points) Given the feasible region in Problem 5(b), identify one objective function that would result in the instance having multiple optimal solutions. If this is impossible, write impossible.