ProblemSet 3 -- Dual linear programs

1. Consider the primal linear program

Maximize \[11x + 5y\] subject to \[\begin{bmatrix} 1 & 1 \\ 10 & 4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \le \begin{bmatrix} 7 \\ 40 \end{bmatrix} \quad \text{and} \quad \begin{bmatrix} x \\ y \end{bmatrix} \ge \mathbf{0}\]

1. Write the dual linear program.

2. Find the optimal solution to both the primal and the dual linear programs. You may do this using python’s linprog, or by plotting the feasible sets. Confirm that both the strong duality theorem and complementary slackness are satisfied. What are the dual prices of each of the constraints?

3. Does the dual price provide an accurate prediction of the increase in the primal objective function when the right-hand side of the first constraint is increased from 7 to 8? From 7 to 9? From 7 to 11?

2. Consider the linear program

   maximize \(\quad y + z\)

   subject to \(\quad \mathbf{x} = \begin{bmatrix} x \\ y \\ z \end{bmatrix} \ge 0\)

   and \(A \mathbf{x} \le \mathbf{b}\)

   where \(A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & -1 \end{bmatrix}\) and \(\mathbf{b} = \begin{bmatrix} 10 \\ 1 \end{bmatrix}\).

   1. What is the value of the objective function at points of the form

      \[\mathbf{p}(c,t) = \begin{bmatrix} c \\ 0 \\ 0 \end{bmatrix} + t\begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} c\\t\\t \end{bmatrix} \quad c,t \in \mathbb{R}?\]

   2. Under what conditions on \(c,t\) is the point \(\mathbf{p}(c,t)\) in the feasible region of the linear program?

   3. Does the linear program have an optimal solution?

   4. What is the dual linear program? Does the dual linear program have any feasible points? Does it have an optimal solution?

3. An author of a dystopian novel wants to write a scene in which a characters plans and builds a doomsday shelter under his home.

   In the novel, the character will store food supplies in a large underground storage container, which has 50 liters of storage in which he will store dried beans and rice.

   It seems at least somewhat realistic to expect that a liter of beans provides nutrition for approx. 9 days, while a liter of rice provides nutrition for approx. 5 day.

   Each liter of beans costs $12.0 and each liter of rice costs $5.00.

   The character will spend $60.

   1. Write the primal and dual linear programs.

      In each case, indicate the variables, the objective, and the constraints.

   2. Find solutions to both the primal and dual linear programs. Confirm that both the strong duality theorem and complementary slackness hold.

   3. Indicate and explain the dual prices for each of the primal constraints.

   4. Suppose the author had instead envisioned a storage container holding an additional c liters of food. Does the dual price for this modified constraint provide an accurate prediction for the increase in the primal objective function (i.e. for the number of days of nutrition provided?)