Canonical Programs and the Simplex Pivot

Section 2.1 Canonical Programs and the Simplex Pivot

In this section, we use our geometric intuition to develop an algebraic operation, a simplex pivot which will be the key operation in solving linear optimization problems. We give both a geometric and algebraic understanding of this operation.

Activity 2.1.1.

Consider 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*}

Note that we may rewrite this as a system of equalities by introducing the slack variables $t_i\text{.}$ We will refer to the $x_j$ as decision variables.

\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 + t_1 \amp = b_1\\ a_{2,1}x_1 + a_{2,2}x_2 +\cdots a_{2,m}x_m+t_2\amp = b_2\\ \vdots \amp \vdots\\ a_{n,1}x_1 + a_{n,2}x_2 +\cdots a_{n,m}x_m +t_n \amp = b_n\\ x_1, x_2, \ldots, x_m\amp \geq 0. \end{align*}

(a)

What must be true about the slack variables $t_i\text{?}$

$\displaystyle t_i\leq 0.$
$\displaystyle t_i\geq 0.$
$\displaystyle \sum_{i=1}^m t_i=0.$

(b)

What is the largest value $t_i$ could obtain?

$\displaystyle b_i.$
$\displaystyle c_i.$
$\displaystyle x_i.$
$t_i$ could be unbounded.

Observation 2.1.2.

Similarly the canonical minimization problem:

\begin{align*} \textbf{Minimize: } g(\mathbf{y}) = c_1x_1 + c_2x_2 +\cdots c_nx_n-d \amp= \left(\displaystyle\sum_{j=1}^n c_jx_j \right)-d\\ \textbf{subject to: } a_{1,1}x_1 + a_{1,2}x_2 +\cdots a_{1,n}x_n\amp \geq b_1\\ a_{2,1}x_1 + a_{2,2}x_2 +\cdots a_{2,n}x_n\amp \geq b_2\\ \vdots \amp \vdots\\ a_{m,1}x_1 + a_{m,2}x_2 +\cdots a_{m,n}x_n\amp \geq b_m\\ x_1, x_2, \ldots, x_n\amp \geq 0. \end{align*}

Where $a_{i,j}, b_i, c_j, d\in \mathbb{R}\text{,}$ may be rewritten as:

\begin{align*} \textbf{Minimize: } g(\mathbf{x}) = c_1x_1 + c_2x_2 +\cdots c_nx_n-d \amp= \left(\displaystyle\sum_{j=1}^n c_jx_j \right)-d\\ \textbf{subject to: } a_{1,1}x_1 + a_{1,2}x_2 +\cdots a_{1,n}x_n -s_1\amp = b_1\\ a_{2,1}x_1 + a_{2,2}x_2 +\cdots a_{2,n}x_n -s_2 \amp = b_2\\ \vdots \amp \vdots\\ a_{m,1}x_1 + a_{m,2}x_2 +\cdots a_{m,n}x_n -s_m \amp = b_m\\ x_1, x_2, \ldots, x_n\amp \geq 0. \end{align*}

In this case, we refer to the $s_j$ as the slack variables, and the $x_i$ as decision variables.

As usual, we focus on maximization for now.

Definition 2.1.3.

We can rewrite

\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 + t_1 \amp = b_1\\ a_{2,1}x_1 + a_{2,2}x_2 +\cdots a_{2,m}x_n+t_2\amp = b_2\\ \vdots \amp \vdots\\ a_{n,1}x_1 + a_{n,2}x_2 +\cdots a_{n,m}x_n +t_m \amp = b_n\\ x_1, x_2, \ldots, x_m\amp \geq 0 \end{align*}

\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 -b_1\amp = -t_1\\ a_{2,1}x_1 + a_{2,2}x_2 +\cdots a_{2,n}x_n-b_2\amp = -t_2\\ \vdots \amp \vdots\\ a_{n,1}x_1 + a_{n,2}x_2 +\cdots a_{n,m}x_n -b_n \amp = -t_n\\ x_1, x_2, \ldots, x_m, t_1, \ldots, t_n\amp \geq 0 \end{align*}

Which may be recorded by the Tucker Tableau:

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

The variables at the top are called the decision variables or independent variables, the variables on the side are the slack variables, basis variables or basic variables.

The basic solution recorded by a Tucker Tableau is the solution where each decision variable has the value zero.

Observation 2.1.4.

Note that this tableau records a basic solution $x_1, x_2, \ldots, x_m=0\text{.}$ We will further explore what this means in a bit. But for now, if $x_1, x_2, \ldots, x_m =0\text{,}$ then:

\begin{align*} a_{1,1}0 + a_{1,2}0 +\cdots a_{1,m}0-b_1 \amp = -t_1\\ a_{2,1}0 + a_{2,2}0 +\cdots a_{2,m}0 -b_2\amp = -t_2\\ \vdots \amp \vdots\\ a_{n,1}0 + a_{n,2}0 +\cdots a_{n,m}0-b_n \amp = -t_n\\ c_10 + c_20 +\cdots c_m0-d \amp = f. \end{align*}

Activity 2.1.5.

Consider the region in $\mathbb{R}^2$ bound by $3x+5y\leq 8, 2x+y\leq 3$ and $x,y\geq 0\text{.}$ Let $3x+5y-8=-t_1$ and $2x+y-3=-t_2.$

$The feasible region for a canonical maximization problem.$

(a)

If $t_1=0\text{,}$ what points in $\mathbb{R}^2$ satisfy $3x+5y-8=-t_1\text{?}$

(b)

If $t_2=0\text{,}$ what points in $\mathbb{R}^2$ satisfy $2x+y-3=-t_2\text{?}$

(c)

What points in $\mathbb{R}^2$ satisfy both $t_1=0, t_2=0\text{?}$

(d)

What points in $\mathbb{R}^2$ satisfy both $t_1=8, t_2=3\text{?}$

(e)

What points in $\mathbb{R}^2$ satisfy both $t_1=8, t_2=0\text{?}$ What about $t_1=8, t_2=0\text{?}$

Activity 2.1.6.

Activity 2.1.7.

Based on Activity 2.1.6, what would be a reasonable sufficient condition for a feasible tableau to have a basic optimal solution?

Some of the $c_j\leq 0\text{.}$
All of the $c_j\leq 0\text{.}$
Some of the $c_j\geq 0\text{.}$
All of the $c_j\geq 0\text{.}$
Some of the $b_i\leq 0\text{.}$
All of the $b_i\leq 0\text{.}$
Some of the $b_i\geq 0\text{.}$
All of the $b_i\geq 0\text{.}$

Activity 2.1.8.

Consider the tableau:

$x_1$	$x_2$	$-1$
$a_{11}$	$a_{12}$	$b_1$	$=-t_1$
$a_{21}$	$a_{22}$	$b_2$	$=-t_2$
$c_1$	$c_2$	$d$	$=f$

along with the corresponding system of equations.

(a)

Solve for $x_1$ in terms of $t_1, x_2\text{.}$

(b)

In each of the other two equalities, replace $x_1$ with the expression we found above and simplify.

(c)

Record this new system in the following tableau:

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

Definition 2.1.9.

The following is the procedure for a pivot transformation:

Pick a non-zero entry $p$ in the tableau but not in the objective row or constraint column.
Transpose the decision and slack variables corresponding to the position of $p\text{.}$
Replace $p$ by $1/p\text{.}$
Replace each entry $s$ in the same row as $p$ (but not $p$) with $s/p\text{.}$
Replace each entry $r$ in the same column as $p$ (but not $p$) with $-r/p\text{.}$
Each entry $q$ not in the same row or column as $p$ but in the same column as $s$ (which is in the same row as $p$) and in the same row as $r$ (which is in the same column as $p$) is replaced with $\frac{pq-rs}{p}\text{.}$

Activity 2.1.10.

Consider the problem: maximize $f(x,y)=5x-y$ subject to:

\begin{align*} -7x+y \amp \leq 0\\ -x+2y \amp \leq 30\\ -x-2y \amp \leq 0\\ -3x-y \amp \leq 20\\ -x,y \amp \geq 0 \end{align*}

which we may encode as:

$x_1$	$x_2$	$-1$
$-7 $	$1 $	$0$	$=-t_1$
$1 $	$2 $	$30 $	$=-t_2$
$1 $	$-2 $	$0 $	$=-t_3$
$3 $	$-1 $	$20$	$=-t_4$
$5 $	$-1 $	$0 $	$=f$

(a)

Pivot on the entry with $*$ (Keep track of the decision and slack variables.)

$x_1$	$x_2$	$-1$
$-7 $	$1 $	$0$	$=-t_1$
$1 $	$2 $	$30 $	$=-t_2$
$1^* $	$-2 $	$0 $	$=-t_3$
$3 $	$-1 $	$20$	$=-t_4$
$5 $	$-1 $	$0 $	$=f$

(b)

Pivot on the entry with $*$ (Keep track of the decision and slack variables.)

		$-1$
$? $	$? $	$?$
$? $	$? $	$? $
$? $	$? $	$? $
$? $	$?^* $	$?$
$? $	$? $	$? $	$=f$

(c)

Pivot on the entry with $*$ (Keep track of the decision and slack variables.)

		$-1$
$? $	$? $	$?$
$?^* $	$? $	$? $
$? $	$? $	$? $
$? $	$? $	$?$
$? $	$? $	$? $	$=f$

(d)

Look at your decision variables. Which two lines are we currently sitting on?

(e)

How do we know the basic solution we now have is an optimal solution?

(f)

Confirm your solution geometrically:

Remark 2.1.11.

One may observe, this pivot operation is not difficult, but rather tedious, and it is easy to make a minor error that derails this process. Doing multiple pivots in a row compounds this issue. It is like a more tedious version of row reduction and Gaussian elimination. Thus an interactive pivoter has been provided in Appendix B. Hopefully this improves everyone’s lives.

Subsection 2.1.1 A Curious Situation

Activity 2.1.12.

Suppose a company produces two types of widgets. Widget 1 sells for $200 and Widget 2 sells for $150.

Each widget takes ingredients A, B and C. Widget 1 needs 1 unit of A, 2 units of B and 2 units of C. Widget 2 needs 2 units of A, 2 units of B and 1 unit of C.

The company has 20 units of ingredient A, 30 units of B and 25 units of C.

Now, the company wants to assign values $y_A, y_B, y_C$ to the three ingredients. The values for each should be enough so that in a disaster, the potential revenue is recovered, ie:

\begin{align*} y_A +2y_B+2y_C \amp \geq 200 \\ 2y_A +2y_B+y_C \amp \geq 150 \end{align*}

Of course, the values shouldn’t be negative, so $y_A, y_B, y_C\geq 0\text{.}$

But, the higher we value the ingredients, the greater the insurance premiums will be, so we need to minimize $g(y_A, y_B, y_C)=20y_A+30y_B+25y_C\text{.}$

We can convert this into a max problem to solve, but we can also record it in the following tableau:


$y_A$	$1$	$2$	$20$
$y_B$	$2$	$2$	$30$
$y_C$	$2$	$1$	$25$
$-1$	$200$	$150$	$0$
	$=s_1$	$=s_2$	$=g$

(a)

Pivot on the entry with the $*\text{:}$


$y_A$	$1$	$2$	$20$
$y_B$	$2$	$2$	$30$
$y_C$	$2^*$	$1$	$25$
$-1$	$200$	$150$	$0$
	$=s_1$	$=s_2$	$=g$

(b)

Pivot on the entry with the $*\text{:}$


$y_A$	$?$	$?$	$?$
$y_B$	$?$	$?^*$	$?$
$s_1$	$?$	$?$	$?$
-1	$?$	$?$	$0$
	$=y_C$	$=s_2$	$=g$

(c)

Compare this basic solution and tableau to the final solution in Activity 2.1.6. What do you notice?

Hint.

Prev Top Next

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

\(x_1\)	\(x_2\)	\(-1\)
\(?\)	\(?\)	\(?\)	\(=-t_A\)
\(?\)	\(?\)	\(?\)	\(=-t_B\)
\(?\)	\(?\)	\(?\)	\(=-t_C\)
\(?\)	\(?\)	\(?\)	\(=f\)

\(t_C\)	\(x_2\)	\(-1\)
\(?\)	\(?\)	\(?\)	\(=-t_A\)
\(?\)	\(?\)	\(?\)	\(=-t_B\)
\(?\)	\(?\)	\(?\)	\(=-x_1\)
\(?\)	\(?\)	\(?\)	\(=f\)

\(t_C\)	\(t_B\)	\(-1\)
\(?\)	\(?\)	\(?\)	\(=-t_A\)
\(?\)	\(?\)	\(?\)	\(=-x_2\)
\(?\)	\(?\)	\(?\)	\(=-x_1\)
\(?\)	\(?\)	\(?\)	\(=f\)

\(x_1\)	\(x_2\)	\(-1\)
\(a_{11}\)	\(a_{12}\)	\(b_1\)	\(=-t_1\)
\(a_{21}\)	\(a_{22}\)	\(b_2\)	\(=-t_2\)
\(c_1\)	\(c_2\)	\(d\)	\(=f\)

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

\(\)	\(\)	\(-1\)
\(? \)	\(? \)	\(?\)	\(\)
\(? \)	\(? \)	\(? \)	\(\)
\(? \)	\(? \)	\(? \)	\(\)
\(? \)	\(?^* \)	\(?\)	\(\)
\(? \)	\(? \)	\(? \)	\(=f\)


\(y_A\)	\(1\)	\(2\)	\(20\)
\(y_B\)	\(2\)	\(2\)	\(30\)
\(y_C\)	\(2\)	\(1\)	\(25\)
\(-1\)	\(200\)	\(150\)	\(0\)
	\(=s_1\)	\(=s_2\)	\(=g\)

\(x_1\)	\(x_2\)	\(-1\)
\(-7 \)	\(1 \)	\(0\)	\(=-t_1\)
\(1 \)	\(2 \)	\(30 \)	\(=-t_2\)
\(1 \)	\(-2 \)	\(0 \)	\(=-t_3\)
\(3 \)	\(-1 \)	\(20\)	\(=-t_4\)
\(5 \)	\(-1 \)	\(0 \)	\(=f\)

\(x_1\)	\(x_2\)	\(-1\)
\(-7 \)	\(1 \)	\(0\)	\(=-t_1\)
\(1 \)	\(2 \)	\(30 \)	\(=-t_2\)
\(1^* \)	\(-2 \)	\(0 \)	\(=-t_3\)
\(3 \)	\(-1 \)	\(20\)	\(=-t_4\)
\(5 \)	\(-1 \)	\(0 \)	\(=f\)

Section 2.1 Canonical Programs and the Simplex Pivot

Activity 2.1.1.

(a)

(b)

Observation 2.1.2.

Definition 2.1.3.

Observation 2.1.4.

Activity 2.1.5.

(a)

(b)

(c)

(d)

(e)

Activity 2.1.6.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Activity 2.1.7.

Activity 2.1.8.

(a)

(b)

(c)

Definition 2.1.9.

Activity 2.1.10.

(a)

(b)

(c)

(d)

(e)

(f)

Remark 2.1.11.

Subsection 2.1.1 A Curious Situation

Activity 2.1.12.

(a)

(b)

(c)