Skip to main content

Linear Optimization: A Geometric Inquiry Course

Tien Chih

Section 3.4 Problems for Chapter 3

The simplex pivoter may be found here:
Hint.

Exercises Exercises

1.

Solve each of the noncanonical linear optimization problems below. If a linear optimization problem has infinitely many optimal solutions, find all optimal solutions.
(a)
\begin{align*} \textbf{Maximize: } f(x,y,z) & = x-2y-z\\ \textbf{subject to: } x+y& \leq 1\\ x+y+z& \geq 2\\ y-2z & \geq 0. \end{align*}
(b)
\begin{align*} \textbf{Maximize: } g(x,y,z) & = 4x+2y+z\\ \textbf{subject to: } x+y+z& \leq 5\\ 4x-y-z& \leq 5\\ 2y+z & \leq 4. \end{align*}
(c)
\begin{align*} \textbf{Maximize: } f(x,y,z) & = 4x+2y+z\\ \textbf{subject to: } x+z& \leq 5\\ 4x-y-z& \leq 5\\ 2y+z & \leq 4. \end{align*}
(d)
\begin{align*} \textbf{Maximize: } k(x,y,z) & = x+2y+z\\ \textbf{subject to: } 2x-y+z& = 3\\ x+2y& \leq 4\\ -2x+5y+3z & \leq 4\\ x, y, z & \geq 0. \end{align*}
(e)
\begin{align*} \textbf{Minimize: } h(x,y,z) & = x+y+z\\ \textbf{subject to: } x-y& \geq 1\\ 2x+z& \leq 10\\ y+z & = 4\\ x, y, z & \geq 0. \end{align*}
(f)
\begin{align*} \textbf{Minimize: } f(x,y,z) & = 3x+y+2z\\ \textbf{subject to: } x+2y+3z& \geq 24\\ 2x+4y+3z& = 36\\ y, z & \geq 0. \end{align*}
(g)
\begin{align*} \textbf{Maximize: } \ell(x,y,z) & = x+y+z\\ \textbf{subject to: } x+y+z& \leq 3\\ x+y& \leq 1\\ y+2z& =2\\ x, y & \geq 0. \end{align*}
(h)
\begin{align*} \textbf{Maximize: } f(x,y,z) & = 3x-2y+3z\\ \textbf{subject to: } x-y+2z& =6\\ x+2z& =8\\ y+2z& \geq 2\\ y, z & \geq 0. \end{align*}
(i)
\begin{align*} \textbf{Minimize: } \alpha(x,y,z) & = -5x+y-2z\\ \textbf{subject to: } 2x+z& =0\\ x-y& \geq 1\\ 3x-y+z& \leq 3. \end{align*}
(j)
\begin{align*} \textbf{Maximize: } g(x,y,z) & = x+y+z\\ \textbf{subject to: } x-y-z& \leq 2.\\ y-z& \geq 1 \end{align*}
(k)
\begin{align*} \textbf{Maximize: } f(x,y) & = x+y\\ \textbf{subject to: } 2x+y& =5\\ x-y& =-2\\ x+2y& =8\\ x, y & \geq 0. \end{align*}

2.

Label each of the following statements TRUE or FALSE. If the statement is FALSE, provide a counterexample.
(a)
A noncanonical linear optimization problem with more unconstrained independent variables than constraints has unbounded objective function. (As in Exercise 3.4.1 (J))
(b)
A noncanonical linear optimization problem with more equations of constraint than independent variables is infeasible. (As in Exercise 3.4.1 (K))

3.

Sketch the constraint set for each noncanonical linear optimization problem below. On the basis of this constraint set, formulate a conjecture as to whether or not the solution of the given problem is the same as the solution of the associated canonical linear optimization problem where all independent variables are constrained to be nonnegative. Verify your conjecture by solving both linear optimization problems.
(a)
\begin{align*} \textbf{Maximize: } f(x,y) & = x+y\\ \textbf{subject to: } 2x+y& \leq 11\\ x-y& \geq -2. \end{align*}
(b)
\begin{align*} \textbf{Minimize: } g(x,y) & = 2x+y\\ \textbf{subject to: } 3x+2y& \geq 5\\ 2x-y& \geq 1. \end{align*}
(c)
\begin{align*} \textbf{Maximize: } f(x,y) & = 5x+y\\ \textbf{subject to: } x-y& \leq 8\\ 2x+y& \leq 7. \end{align*}
(d)
\begin{align*} \textbf{Minimize: } g(x,y) & = x+2y\\ \textbf{subject to: } x+3y& \geq 5\\ 2x+y& \geq 0. \end{align*}

4.

The following problem has infinitely many solutions. Sketch the feasible region, find the optimal solutions and sketch the solution set.
\begin{align*} \textbf{Maximize: } f(x,y,z) & = 2x+y-2z\\ \textbf{subject to: } x+y+z& \leq 1\\ y+4z& =2\\ x, y, z& \geq0. \end{align*}

5.

Another method method for transforming a linear optimization problem with unconstrained independent variables into canonical form is to replace every unconstrained independent variable by the difference of two independent variables constrained to be nonnegative. This produces an equivalent canonical linear optimization problem which is solved by using the simplex algorithm.
For example:
\begin{align*} \textbf{Maximize: } f(x,y) & = 4x+y\\ \textbf{subject to: } x+y& \leq 2\\ x-2y& \leq 5\\ x& \geq0 \end{align*}
may be restated as the following canonical optimization problem:
\begin{align*} \textbf{Maximize: } f(x,y^+, y^-) & = 4x+y^+-y^-\\ \textbf{subject to: } x+y^+-y^-& \leq 2\\ x-2y^+ + 2y^-& \leq 5\\ x, y^+, y^-& \geq0 \end{align*}
where we let \(y=y^+ - y^-\text{.}\)
(a)
Solve the second canonical optimization problem above.
(b)
Solve the original optimization problem.
(c)
How do the solutions compare?

6.

Another method method for transforming a linear optimization problem with equations of constraint into canonical form is to replace every equation of constraint by two inequality constraints. This produces an equivalent canonical linear optimization problem which is solved by using the simplex algorithm.
For example:
\begin{align*} \textbf{Maximize: } f(x,y, z) & = x+y+z\\ \textbf{subject to: } x+2z& \leq 7\\ -x+2y-z& \leq 3\\ x+y& =7\\ x, y, z& \geq0 \end{align*}
may be restated as the following canonical optimization problem:
\begin{align*} \textbf{Maximize: } f(x,y, z) & = x+y+z\\ \textbf{subject to: } x+2z& \leq 7\\ -x+2y-z& \leq 3\\ x+y& \leq 7\\ x+y& \geq 7\\ x, y, z& \geq0. \end{align*}
(a)
Solve the second canonical optimization problem above.
(b)
Solve the original optimization problem.
(c)
How do the solutions compare?

7.

Use the methods presented in Exercise 3.4.5 and Exercise 3.4.6 to solve:
\begin{align*} \textbf{Maximize: } f(x,y, z) & = 2x+y-2z\\ \textbf{subject to: } 2x+y& \leq 3\\ x+2y-z& \leq 5\\ x+y+z& =0\\ x, y& \geq0. \end{align*}
PrevTopNext