Skip to main content

Linear Optimization: A Geometric Inquiry Course

Tien Chih

Section 3.2 Super Constrained Bounds

In this section, we consider linear optimization problems with equality bounds.

Activity 3.2.1.

Suppose we wanted to solve the linear optimization problem:
\begin{align*} \textbf{Maximize: } f(\mathbf{x})= x+y+z & \\ \textbf{subject to: } 2x+3z& \leq 2\\ 4x-y& \leq 1\\ 5y-2z& \leq 5\\ x, y, z& \geq 0 \end{align*}

(a)

Plot the feasible region, what dimension is it?
Hint.

(b)

Suppose we added in the constraint \(3x+2y-z=8\) Plot the feasible region, what dimension is it?
Hint.

(c)

Consider the inequality \(3x+2y-z\leq 8\) captured by the equality \(3x+2y-z - 8=-t_4\text{.}\) What value must \(t_4\) so that \(3x+2y-z\leq 8\) is always an equality? Call this value ?.

(d)

Note that this progam may be encoded in the tableau:
\(x\) \(y\) \(z\) \(-1\)
\(2\) \(0\) \(3\) \(2\) \(=-t_1\)
\(4\) \(-1\) \(0\) \(1\) \(=-t_2\)
\(0\) \(5\) \(-2\) \(5\) \(=-t_3\)
\(3\) \(2^*\) \(-1\) \(8\) \(=-?\)
\(1\) \(1\) \(1\) \(0\) \(=f\)
Without computing the tableau, what point does the basic solution move to if we pivot on the entry with a \(*\text{?}\) Is it feasible?

(e)

As we traverse corner points on the way to an optimal solution, would we ever leave the plane \(3x+2y-z=8\text{?}\)

(f)

After the last pivot, our tableau has the form:
\(x\) \(?\) \(z\) \(-1\)
\(a_{11}\) \(a_{12}\) \(a_{13}\) \(b_1\) \(=-t_1\)
\(a_{21}\) \(a_{22}\) \(a_{23}\) \(b_2\) \(=-t_2\)
\(a_{31}\) \(a_{32}\) \(a_{33}\) \(b_3\) \(=-t_3\)
\(a_{41}\) \(a_{42}\) \(a_{43}\) \(a_{44}\) \(=-y\)
\(c_1\) \(c_2\) \(c_3\) \(d\) \(=f\)
Ignoring the specific values of the entries of this tableau, using the value for ? computed earlier, rewrite each of the above equations in terms of \(x, z\text{.}\) What information did the ? column provide?

Observation 3.2.2.

An equality constraint can be written as:
\begin{equation*} a_{i1}x_1+a_{i2}x_2+\cdots+a_{im}x_m-b_i = 0 \end{equation*}
and thus recorded in a tableau as:
\(x_1\) \(x_2\) \(\cdots\) \(x_{j-1}\) \(x_j\) \(x_{j+1}\) \(\cdots\) \(x_m\) \(-1\)
\(a_{11}\) \(a_{12}\) \(\cdots\) \(a_{1(j-1)}\) \(a_{1j}\) \(a_{1(j+1)}\) \(\cdots\) \(a_{1m}\) \(b_1\) \(=-t_1\)
\(a_{21}\) \(a_{22}\) \(\cdots\) \(a_{2(j-1)}\) \(a_{2j}\) \(a_{2(j+1)}\) \(\cdots\) \(a_{2m}\) \(b_2\) \(=-t_2\)
\(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(a_{i1}\) \(a_{i2}\) \(\cdots\) \(a_{i(j-1)}\) \(a_{ij}\) \(a_{i(j+1)}\) \(\cdots\) \(a_{im}\) \(b_i\) \(=-0\)
\(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(a_{n1}\) \(a_{n2}\) \(\cdots\) \(a_{n(j-1)}\) \(a_{nj}\) \(a_{n(j+1)}\) \(\cdots\) \(a_{nm}\) \(b_n\) \(=-t_n\)
\(c_1\) \(c_2\) \(\cdots\) \(c_{j-1}\) \(c_j\) \(c_{j+1}\) \(\cdots\) \(c_m\) \(d\)
If we pivot on the \(a_{ij}^*\) entry, we obtain:
\(x_1\) \(x_2\) \(\cdots\) \(x_{j-1}\) \(0\) \(x_{j+1}\) \(\cdots\) \(x_m\) \(-1\)
\(a_{11}\) \(a_{12}\) \(\cdots\) \(a_{1(j-1)}\) \(a_{1j}\) \(a_{1(j+1)}\) \(\cdots\) \(a_{1m}\) \(b_1\) \(=-t_1\)
\(a_{21}\) \(a_{22}\) \(\cdots\) \(a_{2(j-1)}\) \(a_{2j}\) \(a_{2(j+1)}\) \(\cdots\) \(a_{2m}\) \(b_2\) \(=-t_2\)
\(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(a_{i1}\) \(a_{i2}\) \(\cdots\) \(a_{i(j-1)}\) \(a_{ij}\) \(a_{i(j+1)}\) \(\cdots\) \(a_{im}\) \(b_i\) \(=-x_j\)
\(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(a_{n1}\) \(a_{n2}\) \(\cdots\) \(a_{n(j-1)}\) \(a_{nj}\) \(a_{n(j+1)}\) \(\cdots\) \(a_{nm}\) \(b_n\) \(=-t_n\)
\(c_1\) \(c_2\) \(\cdots\) \(c_{j-1}\) \(c_j\) \(c_{j+1}\) \(\cdots\) \(c_m\) \(d\)
Then depending on your perspective, we can either delete the 0 column because it does not contribute information algebraically, or because it is redundant geometrically, and we restrict ourselves to a \(m-1\) dimensional solution space. Either way, removing this column gives us:
\(x_1\) \(x_2\) \(\cdots\) \(x_{j-1}\) \(x_{j+1}\) \(\cdots\) \(x_m\) \(-1\)
\(a_{11}\) \(a_{12}\) \(\cdots\) \(a_{1(j-1)}\) \(a_{1(j+1)}\) \(\cdots\) \(a_{1m}\) \(b_1\) \(=-t_1\)
\(a_{21}\) \(a_{22}\) \(\cdots\) \(a_{2(j-1)}\) \(a_{2(j+1)}\) \(\cdots\) \(a_{2m}\) \(b_2\) \(=-t_2\)
\(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(a_{i1}\) \(a_{i2}\) \(\cdots\) \(a_{i(j-1)}\) \(a_{i(j+1)}\) \(\cdots\) \(a_{im}\) \(b_i\) \(=-x_j\)
\(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\) \(\vdots\)
\(a_{n1}\) \(a_{n2}\) \(\cdots\) \(a_{n(j-1)}\) \(a_{n(j+1)}\) \(\cdots\) \(a_{nm}\) \(b_n\) \(=-t_n\)
\(c_1\) \(c_2\) \(\cdots\) \(c_{j-1}\) \(c_{j+1}\) \(\cdots\) \(c_m\) \(d\)

Activity 3.2.3.

Solve the linear optimization problem:
\begin{align*} \textbf{Maximize: } f(\mathbf{x})= x+4y+2z & \\ \textbf{subject to: } x+2y+3z& \leq 6\\ 4x-7y& = 28\\ x, y, z& \geq 0. \end{align*}

Activity 3.2.4.

Consider the linear optimization problem:
\begin{align*} \textbf{Maximize: } f(\mathbf{x})= 2x+y-2z & \\ \textbf{subject to: } x+y+z& \leq 1\\ y+4z& = 2\\ x, y, z& \geq 0. \end{align*}

(a)

Record this problem in a tableau with an equality constraint.
\(x\) \(y\) \(z\) \(-1\)
\(a_{11}\) \(a_{12}\) \(a_{13}\) \(b_1\) \(=-t_1\)
\(a_{21}\) \(a_{22}\) \(a_{23}\) \(b_2\) \(=-0\)
\(c_1\) \(c_2\) \(c_3\) \(d\)

(b)

Pivot on the entry with \(*\text{.}\)
\(x\) \(y\) \(z\) \(-1\)
\(a_{11}\) \(a_{12}\) \(a_{13}\) \(b_1\) \(=-t_1\)
\(a_{21}\) \(a_{22}^*\) \(a_{23}\) \(b_2\) \(=-0\)
\(c_1\) \(c_2\) \(c_3\) \(d\)

(c)

We obtained a tableau of the form:
\(x\) \(0\) \(z\) \(-1\)
\(a_{11}\) \(a_{12}\) \(a_{13}\) \(b_1\) \(=-t_1\)
\(a_{21}\) \(a_{22}\) \(a_{23}\) \(b_2\) \(=-y\)
\(c_1\) \(c_2\) \(c_3\) \(d\)
Rewrite the 3 rows as linear equalities, and verify that the 0 column contributes nothing.

(d)

Delete the 0 column and solve the remaining system.

Activity 3.2.5.

Solve the linear optimization problem:
\begin{align*} \textbf{Maximize: } f(\mathbf{x})= x+4y+2z & \\ \textbf{subject to: } x+2y+3z& \leq 6\\ 4x-7y& \leq 28\\ x, y, z& \geq 0. \end{align*}
Hint.

Activity 3.2.6.

Solve the linear optimization problem:
\begin{align*} \textbf{Maximize: } f(\mathbf{x})= x+2y+z & \\ \textbf{subject to: } x+y+z& = 6\\ x+y& \leq 1\\ x, z& \geq 0. \end{align*}
Hint.
PrevTopNext