Skip to main content

Linear Optimization: A Geometric Inquiry Course

Tien Chih

Section 3.1 Unconstrained Variables

Recall that canonical problems have non-negative variables and inequality bounds. In this section, we consider linear optimization problems with potentially negative variables.

Activity 3.1.1.

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

(a)

What are some differences between this linear optimization problem and previous examples of optimization problems?

(b)

We can record the problem with the following tableau, we denote the variables which can be negative by circling them:
\(\ec{x}\) \(\ec{y}\) \(-1\)
\(4\) \(5 \) \(23\) \(=-t_1\)
\(2 \) \(1\) \(7 \) \(=-t_2\)
\(1\) \(-1 \) \(5 \) \(=-t_3\)
\(3 \) \(2 \) \(0\) \(=f\)
What point currently represents the basic solution?

(c)

Suppose we pivot on the entry with the \(*\text{.}\) What point has the basic solution moved to? (You do not need to fill in the tableau.)
\(\ec{x}\) \(\ec{y}\) \(-1\)
\(4\) \(5 \) \(23\) \(=-t_1\)
\(2^* \) \(1\) \(7 \) \(=-t_2\)
\(1\) \(-1 \) \(5 \) \(=-t_3\)
\(3 \) \(2 \) \(0\) \(=f\)

(d)

Suppose we pivot on the entry with the \(*\text{.}\) What point has the basic solution moved to?
\(t_2\) \(\ec{y}\) \(-1\)
\(?\) \(? \) \(?\) \(=-t_1\)
\(? \) \(?\) \(? \) \(=-\ec{x}\)
\(?\) \(?^* \) \(? \) \(=-t_3\)
\(? \) \(? \) \(?\) \(=f\)

(e)

Consider the plot of the feasible region. What did our two pivots do?

(f)

Which of the following do you believe is true?
  1. Following the rules of pivoting through the Simplex Algorithm, we should be able to return to the origin.
  2. It is possible to perform pivots that don’t neccesarily follow the rules of the Simplex Algorithm, to return to the origin, and this is sensible as we are just traversing corner points.
  3. It is technically possible to perform pivots that don’t neccesarily follow the rules of the Simplex Algorithm and this is not sensible.

(g)

List all the hyperplanes that bound the feasible region.

Definition 3.1.2.

In a linear optimization problem, a variable which can be potentially negative is called an unconstrained variable.

Activity 3.1.3.

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

(a)

We can record the problem as follows:
\(x \) \(y \) \(-1\)
\(2\) \(3 \) \(26\) \(=-t_1\)
\(-2\) \(-10 \) \(2 \) \(=-t_2\)
\(5 \) \(4 \) \(0\) \(=f\)
Out of \(x, y, t_1, t_2\text{,}\) which are non-negative?

(b)

Perform a pivot on the given entry:
\(\ec{x} \) \(\ec{y} \) \(-1\)
\(2^*\) \(3 \) \(26\) \(=-t_1\)
\(-2\) \(-10 \) \(2 \) \(=-t_2\)
\(5 \) \(4 \) \(0\) \(=f\)

(c)

Consider the resulting tableau:
\(t_2 \) \(\ec{y} \) \(-1\)
\(?\) \(? \) \(?\) \(=-\ec{x}\)
\(?\) \(? \) \(? \) \(=-t_2\)
\(? \) \(? \) \(?\) \(=f\)
What point in \(\mathbb{R}^2\) represents the basic solution of this tableau? Why is this point not an optimal solution?

(d)

Consider the row with the \(\ec{x}\text{,}\) and recall that \(\ec{x}\) is allowed to be negative. Consider only this row and the non-negativity constraints of \(t_i\text{.}\) Which of the following is \(t_1\) allowed to be?
  1. \(t_1=0\text{.}\)
  2. \(t_1=10\text{.}\)
  3. \(t_1=100\text{.}\)
For each choice of \(t_1\) that is valid, with \(y=0\text{,}\) what would \(x\) be?

(e)

Which of the following bits of information does this row communicate to us? (There could be more than one.)
  1. There is a lower bound for \(t_1\) which is greater than 0.
  2. There is an upper bound for \(t_1\text{.}\)
  3. There is a lower bound for \(t_2\) which is greater than 0.
  4. There is an upper bound for \(t_2\text{.}\)
  5. There is a lower bound for \(x\) which is greater than 0.
  6. There is an upper bound for \(x\text{.}\)
  7. There is a lower bound for \(y\) which is greater than 0.
  8. There is an upper bound for \(y\text{.}\)
  9. That \(x = 13 -\frac{1}{2}t_1-\frac{3}{2}y\text{.}\)
  10. That \(t_2 = 28 -t_1+7y\text{.}\)

(f)

After recording this piece of information, we may as well delete this row, since we have what we need from it:
\(t_1 \) \(\ec{y} \) \(-1\)
\(?\) \(?^* \) \(? \) \(=-t_2\)
\(? \) \(? \) \(?\) \(=f\)
Pivot on the entry with the \(*\text{.}\)

(g)

Why does the resulting tableau encode a basic solution which is not infeasible?

(h)

Which of the following bits of information does the \(\ec{y}\) row communicate to us? (There could be more than one.)
  1. There is a lower bound for \(t_1\) which is greater than 0.
  2. There is an upper bound for \(t_1\text{.}\)
  3. There is a lower bound for \(t_2\) which is greater than 0.
  4. There is an upper bound for \(t_2\text{.}\)
  5. There is a lower bound for \(y\) which is greater than 0.
  6. There is an upper bound for \(y\text{.}\)
  7. That \(y = -\frac{1}{7}t_1+\frac{1}{7}t_2-4\text{.}\)

(i)

After recording this piece of information, we may as well delete this row, since we have what we need from it:
\(t_1 \) \(t_2 \) \(-1\)
\(?\) \(? \) \(? \) \(=-f\)
Why is the basic solution encoded by this tableau optimal?

(j)

What are \(t_1, t_2, x, y, f\text{?}\)

(k)

Consider the plot of the feasible region. If we started at the origin, what did we do in each step?

Observation 3.1.4.

With unconstrained variables, we proceed as follows.
  1. Remove all unconstrained slack variables and delete the corresponding rows.
  2. If there are no unconstrained decision variables: STOP.
  3. Pivot an unconstrained decision variable with a slack variable.
  4. GOTO 1
What is left should be a maximization tableau with no unconstrained variable. One should take a moment to ponder: It may well be that the resulting tableau is infeasible. Why is this either not possible, or possible but ok?

Activity 3.1.5.

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