Sensitivity Analysis

Section 4.1 Sensitivity Analysis

In this section, we begin the exploration of what duality means. We assign natural meanings to dual variables and the dual problem. One perspective to keep in mind this section is the role of bounds and objective function in the primal problem, and how they change here.

Exploration 4.1.1.

The witch Agnesi

The name Agnesi was chosen by my Spring 2024 class who knew her from her eponymous curve.

is brewing a healing elixir and a poison. A pint of healing elixir takes 3 newt eyes and one frog, whereas a pint of poison takes 1 each of newt eyes and frogs. She currently has 34 newt eyes and 14 frogs.

Supposing that the healing elixir sells for three gold pieces, and the poison sells for two. Agnesi wishes to maximize her revenue. Let us suppose that since these are liquids, she is happy making fractional amounts of elixirs and potions.

(a)

Before proceeding to solve the problem, make an estimate: how much do you think each newt eye and frog is worth to her? Why do you think so?

(b)

We now return to the initially posed maximization problem. Sketch the feasible region for this problem, and use whatever method you feel like to find the optimal solution.

(c)

Agnesi is frustrated by her production levels and income. She is going to recruit some local children to gather more materials for her. Without explicitly computing anything, looking at her situation, what would result in greater profits for her, more newt eyes or frogs?

(d)

Recompute this linear optimization problem with 35 newt eyes and 14 frogs, then with 34 newt eyes and 15 frogs. Which provides the greater increase in revenue? Is this consistent with what you thought earlier?

(e)

If the need for healing elixir increases and they now sell for 5 gold, would that change our answers above?

Activity 4.1.2.

In both Exploration 4.1.1 and Activity 2.1.12 we essentially explore the idea of assigning values somehow to the bounds of a maximization problem.

Suppose you have a production problem, and you wish to acquire new materials to increase production. You then assign a value to each potential new material, according to which would benifit you the most. Which of the following should be reasonable things to expect from these values?

The value of each material is non-negative.
The total value of the materials should be as big as possible, to maximize costs associated with their value.
The total value of the materials should be as small as possible, to minimize costs associated with their value.
The total value of these materials should reflect the value of selling products made with those materials.
If a material is not to be used, it has zero value.

Activity 4.1.3.

From Exploration 4.1.1, letting $x_1$ denote the number of healing elixirs, and $x_2$ denote the amount of poison created. Then, we get that the feasible region satisfies the inequalities:

\begin{align*} 3x_1+x_2 \amp\leq 34 \\ x_1+x_2 \amp\leq 14 \\ -x_1 \amp\leq 0 \\ -x_2 \amp\leq 0 \end{align*}

which is bounded by hyperplanes:

\begin{align*} 3x_1+x_2 \amp = 34 \\ x_1+x_2 \amp = 14 \\ -x_1 \amp = 0 \\ -x_2 \amp = 0 \end{align*}

with normal vectors

\begin{equation*} \begin{bmatrix}3\\1 \end{bmatrix}, \begin{bmatrix}1\\1 \end{bmatrix}, \begin{bmatrix}-1\\0 \end{bmatrix}, \begin{bmatrix}0\\-1 \end{bmatrix} \end{equation*}

which may be depicted:

$The feasible region for the witch production problem, and depicted normal vectors.$

(a)

Starting at the basic solution, perform pivots as follows:

$x_1$	$x_2$	$-1$
$3^*$	$1$	$34$	$=-t_1$
$1$	$1$	$14$	$=-t_2$
$3$	$2$	$0$	$=f$

$t_1$	$x_2$	$-1$
$?$	$?$	$?$	$=-x_1$
$?$	$?^*$	$?$	$=-t_2$
$?$	$?$	$?$	$=f$

$t_1$	$t_2$	$-1$
$?^*$	$?$	$?$	$=-x_1$
$?$	$?$	$?$	$=-x_2$
$?$	$?$	$?$	$=f$

$x_1$	$t_2$	$-1$
$?$	$?$	$?$	$=-t_1$
$?$	$?$	$?$	$=-x_2$
$?$	$?$	$?$	$=f$

For each tableau, confirm the solution is feasible.

(b)

For each tableau above, if we decrease each decision variable from $0$ to $-1\text{,}$ how does that change the value of the objective function? What does decreasing a decision variable from $0$ to $-1$ mean geometrically? What does it mean in terms of the normal vectors of the associated intersecting hyperplanes?

(c)

Consider that $(0,14)$ is on the intersection of $-x=0, x+y=14$ which are hyperplanes with normal vectors $\begin{bmatrix} -1 \\ 0 \end{bmatrix}$ and $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ respectively. Note that $3x+2y=28$ passes through $(0,14)$ with normal vector $\begin{bmatrix} 3 \\ 2 \end{bmatrix}\text{.}$

Drag sliders for $y_1, y_2$ so that

\begin{equation*} \begin{bmatrix} 3 \\ 2 \end{bmatrix} = y_1\begin{bmatrix} -1 \\ 0 \end{bmatrix}+y_2 \begin{bmatrix} 1 \\ 1 \end{bmatrix}. \end{equation*}

(d)

For each extreme point, express $\begin{bmatrix}3 \\ 2\end{bmatrix} $ as a linear combination of the normal vectors of the corresponding hyperplanes. Then, for each tableau computed above, look at their basic solutions. What point corresponds to each basic solution, and how are these coefficients reflected in each tableau?

(e)

For each extreme point in the feasible region, consider the bounding planes who intersect at that point. If you traverse in the direction of the normal vectors from the extreme point, does the objective function increase or decrease? How does this connect to the coefficients we just found?

(f)

For which extreme points are the normal vector of the objective plane a linear combination of the normal vectors of intersecting hyperplanes using only positive coefficients? Is there anything special about those extreme points? Is there anything noteworthy about the corresponding tableau?

Activity 4.1.4.

Consider the tableau:

$x_1$	$x_2$	$\cdots$	$x_m$	$-1$
$a_{11}$	$a_{12}$	$\cdots$	$a_{1m}$	$b_1$	$=-x_{m+1}$
$a_{21}$	$a_{22}$	$\cdots$	$a_{2m}$	$b_2$	$=-x_{m+2}$
$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$	$\vdots$
$a_{n1}$	$a_{n2}$	$\cdots$	$a_{nm}$	$b_n$	$=-x_{m+n}$
$c_1$	$c_2$	$\cdots$	$c_m$	$d$

Suppose that for $j\in \{1,2,\ldots,m\}$ each plane $-x_j=0$ has corresponding normal vector $\mathbf{v}_j\text{.}$

(a)

Prove that the normal vector for $f$ is $\sum_{j=1}^m (-c_j)\mathbf{v}_j\text{.}$

(b)

Is there anything special about a tableau where $f$ is a non-negative linear combination of normal vectors?

(c)

Suppose that this tableau corresponds to an optimal solution. If we decrease any $x_j$ from $0$ to $-1\text{,}$ how does $f$ change? What does this decrease correspond to geometrically?

Definition 4.1.5.

Recall the canonical maximization problem:

\begin{align*} \textbf{Maximize: } f(\mathbf{x}) = c_1x_1 + c_2x_2 +\cdots c_mx_m-d \amp= \left(\displaystyle\sum_{j=1}^m c_jx_j \right)-d\\ \textbf{subject to: } a_{1,1}x_1 + a_{1,2}x_2 +\cdots a_{1,m}x_m\amp \leq b_1\\ a_{2,1}x_1 + a_{2,2}x_2 +\cdots a_{2,m}x_m\amp \leq b_2\\ \vdots \amp \vdots\\ a_{n,1}x_1 + a_{n,2}x_2 +\cdots a_{n,m}x_m\amp \leq b_n\\ x_1, x_2, \ldots, x_m\amp \geq 0. \end{align*}

The dual minimization problem is aritculated as follows:

\begin{align*} \textbf{Minimize: } g(\mathbf{y}) = y_1b_1 + y_2b_2 +\cdots y_nb_n-d \amp= \left(\displaystyle\sum_{i=1}^n y_ib_i \right)-d\\ \textbf{subject to: } a_{1,1}y_1 + a_{2,1}y_2 +\cdots a_{n,1}y_n\amp \geq c_1\\ a_{1,2}y_1 + a_{2,2}y_2 +\cdots a_{n,2}y_n\amp \geq c_2\\ \vdots \amp \vdots\\ a_{1,m}y_1 + a_{n,2}x_2 +\cdots a_{n,m}x_m\amp \geq c_m\\ y_1, y_2, \ldots, y_n\amp \geq 0. \end{align*}

We refer to the $y_i$ as dual variables.

Activity 4.1.6.

Recall Agnesi’s business Exploration 4.1.1, and the coefficient computations done in Activity 4.1.3.

(a)

Following Definition 4.1.5, write out the dual problem to the maximization problem described in Exploration 4.1.1.

(b)

Which of the following best represent the dual variables $y_1, y_2$ in this context?

The quantity of newt eyes and frogs.
The value of newt eyes and frogs.
The quantity of healing elixirs and poisons.
The value of healing elixirs and poisons.

(c)

For each inequality in our dual problem, articulate what those inequalities represent in this context.

(d)

Describe the dual objective function in this context.

Activity 4.1.7.

Describe three primal maximization problems with some “real world” context, these do not have to be “realistic”, they can be fantastical like Agnesi’s problem here. Then, describe the dual problem to each and say what the dual variables mean in each case.

Prev Top Next

\(x_1\)	\(x_2\)	\(-1\)
\(3^*\)	\(1\)	\(34\)	\(=-t_1\)
\(1\)	\(1\)	\(14\)	\(=-t_2\)
\(3\)	\(2\)	\(0\)	\(=f\)

\(t_1\)	\(x_2\)	\(-1\)
\(?\)	\(?\)	\(?\)	\(=-x_1\)
\(?\)	\(?^*\)	\(?\)	\(=-t_2\)
\(?\)	\(?\)	\(?\)	\(=f\)

\(t_1\)	\(t_2\)	\(-1\)
\(?^*\)	\(?\)	\(?\)	\(=-x_1\)
\(?\)	\(?\)	\(?\)	\(=-x_2\)
\(?\)	\(?\)	\(?\)	\(=f\)

\(x_1\)	\(t_2\)	\(-1\)
\(?\)	\(?\)	\(?\)	\(=-t_1\)
\(?\)	\(?\)	\(?\)	\(=-x_2\)
\(?\)	\(?\)	\(?\)	\(=f\)

\(x_1\)	\(x_2\)	\(\cdots\)	\(x_m\)	\(-1\)
\(a_{11}\)	\(a_{12}\)	\(\cdots\)	\(a_{1m}\)	\(b_1\)	\(=-x_{m+1}\)
\(a_{21}\)	\(a_{22}\)	\(\cdots\)	\(a_{2m}\)	\(b_2\)	\(=-x_{m+2}\)
\(\vdots\)	\(\vdots\)	\(\ddots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(a_{n1}\)	\(a_{n2}\)	\(\cdots\)	\(a_{nm}\)	\(b_n\)	\(=-x_{m+n}\)
\(c_1\)	\(c_2\)	\(\cdots\)	\(c_m\)	\(d\)