Initial Examples

Section 1.2 Initial Examples

Here we begin with some initial examples motivating the sort of problems we will study. We define the central problems around which the course will revolve.

Activity 1.2.1.

A sculptor and a painter work together to produce pieces of art, vases and figurines. The vases takes the sculptor 1 hour to make and the painter 2 hours to paint. The figurine takes the sculptor two hours to make and the painter 1 hour to paint. The sculptor has 35 hours a week to work and the painter has 40 hours a week to work.

Let $x_1$ denote the number of vases produced and $x_2$ denote the number of figurines produced.

(a)

Write an in terms of $x_1, x_2$ that represent the constraints on the time of the sculptor.

(b)

Write an in terms of $x_1, x_2$ that represent the constraints on the time of the painter.

(c)

What other inequalities involving $x_1, x_2$ would be sensible to impose?

(d)

Treating $x_1$ as $x$ and $x_2$ as $y\text{,}$ sketch the region on the cartesian plane satisfying all the above inequalities. We will refer to this as the feasible region.

(e)

Pick some points within this feasible region, what do they represent in terms of vases and figurines? How much revenue is generated? What causes the revenue to increase or decrease?

(f)

Suppose the vases sold for $100 and the figurines sold for $120. Without reading ahead, what would or could you do to solve this problem? What kind of things would you need to consider?

For those of you who had Calculus and especially Multivariable Calculus, what ideas from those course might you employ? What are some limitations of these ideas?

(g)

If there was a surge in demand for vases, and they started selling for $1000, how would that change your approach and the solution?

Activity 1.2.2.

Suppose Carlos planning on shopping for a meal. Mini bell peppers are $1.00 (simplified) a pound, Chicken is $1.25 a pound and Spaghetti with sauce is $0.80 a cup.

A pound of Bell Peppers has 500 units of vitamin A, 30 calories and 10 units of calcium. A pound of Chicken has 75 units of vitamin A, 280 calories and 22 units of calcium. A cup of Spaghetti with sauce has 2000 units of Vitamin A, 240 Calories and 52 units of Calcium.

Carlos needs a minimum of 640 calories, 1650 units of Vitamin A and 500 units of Calcium.

(a)

Let $x_1$ denote pounds of bell pepper, $x_2$ denote pounds of chicken and $x_3$ denote cups of spaghetti with sauce. Find three inequalities in terms of the $x_i$ for how much of each food Carlos should eat to meet his minimum dietary requirements.

(b)

How might we solve this problem? How is it different from Activity 1.2.1?

(c)

This seems like a wildly oversimplistic dietary problem, because it is. How might we complicate it for more realism?

Definition 1.2.3.

The Canonical Maximazation Linear Optimization Problem is the problem:

\begin{align*} \textbf{Maximize: } f(\mathbf{x}) = c_1x_1 + c_2x_2 +\cdots c_nx_n-d \amp= \left(\displaystyle\sum_{i=1}^n c_ix_i \right)-d\\ \textbf{subject to: } a_{1,1}x_1 + a_{1,2}x_2 +\cdots a_{1,n}x_n\amp \leq b_1\\ a_{2,1}x_1 + a_{2,2}x_2 +\cdots a_{2,n}x_n\amp \leq b_2\\ \vdots \amp \vdots\\ a_{m,1}x_1 + a_{m,2}x_2 +\cdots a_{m,n}x_n\amp \leq b_m\\ x_1, x_2, \ldots, x_n\amp \geq 0 \end{align*}

where $a_{i,j}, b_j, c_i, d\in \mathbb{R}\text{.}$

The Canonical Minimization Linear Optimization Problem is the problem:

\begin{align*} \textbf{Minimize: } g(\mathbf{x}) = c_1x_1 + c_2x_2 +\cdots c_nx_n-d \amp= \left(\displaystyle\sum_{i=1}^n c_ix_i \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_j, c_i, d\in \mathbb{R}\text{.}$

Note 1.2.4.

The term canonical in this context refers to the fact that for both of the above problems, the $x_i$ are non-negative, and each bound is an inequality.

(In Chapter 3, we discuss noncanonical linear optimization problems, where these conditions may fail.)

Definition 1.2.5.

$f,g$ above are called objective functions. Any point $\mathbf{x} = (cx_1, x_2, \ldots, x_n)$ satisfying either of the above set of inequalities are called feasible solutions. Any feasible solution $\mathbf{x}$ which maximizes (minimizes) the objective function is called an optimal solution.

Activity 1.2.6.

(a)

Given the canonical minimization problem:

\begin{align*} \textbf{Minimize: }g(x_1, x_2) = 5x_1-3x_2\amp \\ \amp \\ \textbf{subject to: } 4x_1 + x_2 \amp \geq 10\\ 3x_1 + 12x_2 \amp \geq 12\\ x_1, x_2, \amp \geq 0. \end{align*}

How might we convert this to a canonical maximization problem?

(b)

How might we in general convert a minimization problem to a maximization problem?

Prev Top Next