Skip to main content

Linear Optimization: A Geometric Inquiry Course

Tien Chih

Section 1.5 Problems for Chapter 1

Exercises Exercises

1.

Draw and shade appropriate regions in \(\mathbb{R}^2\) as described below, where \(x, y\geq 0\text{.}\)
(a)
A bounded polyhedral convex subset.
(b)
An unbounded polyhedral convex subset.
(c)
A bounded nonconvex subset
(d)
An unbounded nonconvex subset.
(e)
A convex subset that is not a polyhedral convex subset.
(f)
A convex subset having no extreme points.
(g)
A polyhedral convex subset having no extreme points.
(h)
A bounded polyhedral convex subset having exactly one extreme point.
(i)
An unbounded polyhedral convex subset having exactly one extreme point.
(j)
An bounded convex subset having infinitely many extreme points.
(k)
An unbounded convex subset having infinitely many extreme points.

2.

Convert each of the linear optimization problems below to canonical form as in Definition 1.2.3.
(a)
\begin{align*} \textbf{Maximize: } f(x,y) \amp = 3x-y\\ \textbf{subject to: } 15-4x\amp \geq y\\ 2x+3y\amp \leq y+12\\ x,y\amp \geq 0. \end{align*}
(b)
\begin{align*} \textbf{Minimize: } g(x,y) \amp = -4x-2y\\ \textbf{subject to: } 4x-7y\amp \leq -2\\ 5x+3y\amp \leq 21\\ x,y\amp \geq 0. \end{align*}
(c)
\begin{align*} \textbf{Maximize: } h(x,y, z) \amp = x+3y-3z\\ \textbf{subject to: } 3-4x+z\amp \geq 5y\\ 1\leq 2y+z \amp \leq 9\\ 0\leq x \amp \leq 8\\ y, z\amp \geq 0. \end{align*}
(d)
\begin{align*} \textbf{Minimize: } k(x,y,z) \amp =x-2y-z\\ \textbf{subject to: } 10x+5y+2z\amp \leq 1000\\ 2y+4z \amp \leq 800\\ x,y,z\amp \geq 0. \end{align*}
(e)
A drive-in sells homemade hot dogs and hamburgers. The hot dogs take \(3/8\) cup of flour and \(2.5\) oz of beef to make. A hamburger bun takes \(1/4\) cups of flour and \(5\) oz of beef. Suppose the drive-in has \(20\) cups of flour and \(200\) oz of beef on hand. If hot dogs sell for $4 and hamburgers for $6, how much of each should they make to maximize revenue?
(f)
A rancher has a herd to feed who requires 54, 48, and 72 units of the nutritional elements A, B, and C, respectively, per day. Feed 1 costs 10 cents a pound and contains 8, 4 and 3 units of elements A, B, C respectively. Feed 2 costs 8 cents a pound and contains 2, 4 and 6 units of elements A, B, C respectively. How much of each feed should the rancher purchase to cover the herds nutritional needs while minimizing cost?
(g)
A drug company sells three different formulations of vitamin complex and mineral complex. The first formulation consists entirely of vitamin complex and sells for $1 per unit. The second formulation consists of 3/4 of a unit of vitamin complex and 1/4 of a unit of mineral complex and sells for $2 per unit. The third formulation consists of 1/2 of a unit of each of the complexes and sells for $3 per unit. If the company has 100 units of vitamin complex and 75 units of mineral complex available, how many units of each formulation should the company produce so as to maximize sales revenue?
(h)
\begin{align*} \textbf{Maximize: } f(x,y) = \amp 5x+6y\\ \textbf{subject to: } 2x+3y\amp \geq 12\\ -3x+2y\amp \leq 14\\ x+y\amp \leq 12\\ x,y\amp \geq 0. \end{align*}

3.

For each of the following, sketch the feasible region \(\mathbf{R}\text{,}\) and find the optimal solution by identifying the extreme points of \(\mathbf{R}\) and evaluating.
(a)
\begin{align*} \textbf{Maximize: } f(x,y) = \amp 2x+y\\ \textbf{subject to: } x+4y\amp \leq 11\\ 6x+2y\amp \leq 22\\ x,y\amp \geq 0. \end{align*}
(b)
\begin{align*} \textbf{Minimize: } f(x,y) = \amp 2x+y\\ \textbf{subject to: } x+4y\amp \geq 11\\ 6x+2y\amp \geq 22\\ x,y\amp \geq 0. \end{align*}

4.

Prove that Exercise 1.5.3 (H) has infinitely many optimal solutions, two of which lie on extreme points. Identify these points on the plot of the feasible region done in Exercise 1.5.3.

5.

Prove that if \(\mathbf{x}, \mathbf{x}'\) are distinct optimal solutions of a canonical linear optimization problem, then all points on the line segment between \(\mathbf{x}, \mathbf{x}'\) are also optimal solutions of the problem.
Conclude that a canonical linear optimization problem can have 0, 1 or infinitely many optimal solutions and no other possibilities.

6.

Consider the canonical linear optimization problem
\begin{align*} \textbf{Maximize: } f(x,y,z,w) = 3x-2y+5z-w\\ \textbf{subject to: } -x+2y-3z+6w\amp \leq 12\\ x,y, z, w\amp \geq 0. \end{align*}
Find the \({5\choose 4}\) potential intersections of bounding hyperplanes, determine which are feasible, and which of those are optimal.

7.

Consider the canonical linear optimization problem
\begin{align*} \textbf{Minimize: } g(x,y,z,w) = 2x-y-3z+4w\\ \textbf{subject to: } x+2y+2z+4y\amp \geq 8\\ 4x-y\amp \geq 6\\ x,y, z, w\amp \geq 0. \end{align*}
Find the \({6\choose 4}\) potential intersections of bounding hyperplanes, determine which are feasible, and which of those are optimal. (It is recommended that you use some technological tools to solve for the resulting linear systems.)

9.

Show that
\begin{align*} \textbf{Maximize: } f(x,y) = \amp x-y\\ \textbf{subject to: } x+y\amp \geq 5\\ x-5y\amp \leq 0\\ y-2x\amp \leq 1\\ x,y\amp \geq 0. \end{align*}
is unbounded. (Hint: sketch the feasible region and consider feasible points on the line \(x=5y\text{.}\))

10.

Show that
\begin{align*} \textbf{Minimize: } g(x,y) = \amp 5x+3y\\ \textbf{subject to: } y-5x\amp \geq 1\\ x-5y\amp \geq 0\\ x,y\amp \geq 0. \end{align*}
is infeasible.

11.

For each of the following, determine whether or not the statement is TRUE or FALSE. If TRUE, provide a proof, if FALSE, provide a counterexample.
(a)
If a canonical feasible linear optimization problem is unbounded, then it’s feasible region is unbounded.
(b)
If a canonical feasible linear optimization problem has unbounded feasible region, then it is unbounded.
PrevTopNext