Effect on Minimizer of Tightening Constraints

Question

The Statement of the Problem:

Consider the minimization problem $f(x,y)=14x+20y$ under the constraints $x+2y \ge 4 $, $7x+6y \ge 20$, and $x,y \ge 0$. Don't use the simplex method!

(i) Draw the picture of the constraint set; solve the minimization problem graphically by showing the minimum exists and calculating $f$ at extreme points.

(ii) How does the optimizer location change if we replace the first constraint by $x+2y \ge 4+\epsilon $? How does it change if we replace the second constraint by $7x+6y \ge 20+\epsilon$? What are the shadow values for each of these constraints?

Where I Am:

I did part (i) which was quite simple. I found the following extrema:

$$(4,0);(0,\frac{10}{3});(2,1)$$

with the function attaining a minimum of $48$ at $(2,1)$.

However, I don't really understand part (ii) of the problem. Obviously, the constraints are "tightened" by adding $\epsilon$, because the feasible set gets smaller. That doesn't seem to be "all there is" to this problem. Furthermore, I'm not sure how I'm supposed to find the shadow values. Normally, I just read them off the bottom of the simplex tableau, but we're specifically told NOT to use the simplex method, so I'm not sure what to do. Any help here would be appreciated.

Answer 1

You can investigate the solution of the dual problem:

The dual problem is:

$\texttt{max} \ 4u+20v$

$u+7v\leq 14$

$2u+6v \leq 20$

$u,v \geq 0$

The optimal solution $(u^*, v^*)$ can be found graphically as well.

Interpretation:

If the first constraint would be replaced by $x+2y\geq 4+ \epsilon $, then the optimal soulition would be $z^*_{new}=z^*+u^*\cdot \epsilon=48+u^*\cdot \epsilon$.

If the second constraint would be replaced by $7x+6y\geq 20+ \epsilon $, then the optimal soulition would be $z^*_{new}=z^*+v^*\cdot \epsilon=48+v^*\cdot \epsilon$.

Answer 2

The important thing to note is that at your solution, the active constraints are $x+2y\geq 4$, $7x+6y\geq 20$. In other words, at the solution, $$x+2y=4, ~~ 7x+6y=20, ~~ x>0, ~~y>0.$$ For sufficiently small changes in the constraints, the first two constraints will remain the active set. Thus for any sufficiently small $\epsilon$s, you will be able to determine the optimal solution simply by solving a system of two linear equations: $$\begin{bmatrix} x^* \\ y^* \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 7 & 6 \end{bmatrix}^{-1} \begin{bmatrix} 4 + \epsilon_1 \\ 20 + \epsilon_2 \end{bmatrix}, \quad f(x,y) = \begin{bmatrix} 14 & 20 \end{bmatrix} \begin{bmatrix} 1 & 2 \\ 7 & 6 \end{bmatrix}^{-1} \begin{bmatrix} 4 + \epsilon_1 \\ 20 + \epsilon_2 \end{bmatrix} $$

This information allows us to answer the question without appealing to duality or the simplex method.

1. In the case $x+2y\geq 4+\epsilon_1$, the change in location and objective is $$\begin{bmatrix} \Delta x \\ \Delta y \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 7 & 6 \end{bmatrix}^{-1} \begin{bmatrix} \epsilon_1 \\ 0 \end{bmatrix} = \begin{bmatrix} -3/4 \\ 7/8 \end{bmatrix}\epsilon_1, \quad \Delta f = \begin{bmatrix} 14 & 20 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \end{bmatrix} = 7\epsilon_1. $$
2. In the case $7x+6y\geq 20+\epsilon_2$, we have $$\begin{bmatrix} \Delta x \\ \Delta y \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 7 & 6 \end{bmatrix}^{-1} \begin{bmatrix} 0 \\ \epsilon_2 \end{bmatrix} = \begin{bmatrix} 1/4 \\ -1/8 \end{bmatrix}\epsilon_2, \quad \Delta f = \begin{bmatrix} 14 & 20 \end{bmatrix} \begin{bmatrix} \Delta x \\ \Delta y \end{bmatrix} = \epsilon_2. $$

The shadow values are $7$ and $1$ respectively.