Core practice ← Back to lesson

Introduction to Optimization: Core practice

10 practice problems for this lesson. Work on paper, use hints when you need them, and check the answer or the full solution when you are ready.

Difficulty: Advanced (beyond the core course) Advanced. This problem set goes beyond core Algebra I. You can skip it.

0 of 10 completed

Progress saved in this browser.

Problem 1 of 10

Problem 1 Four corners, one objective

A bounded feasible region includes its boundary and has corners $(0,2)$ , $(5,0)$ , $(7,3)$ , and $(3,6)$ . For the objective $P=2x+4y$ , find the value at each corner and state which corner gives the maximum.
1. Hint 1
  The value at a corner depends only on that corner's own coordinates.
2. Hint 2
  Work through the four corners one at a time, then compare the four results.
Answer

$P(0,2)=8$ , $P(5,0)=10$ , $P(7,3)=26$ , and $P(3,6)=30$ ; the maximum 30 is at $(3,6)$ .

Full solution

Each corner value is twice the first coordinate plus four times the second.
The four corners give
$P(0,2)=8$ $P(5,0)=10$ $P(7,3)=26$ $P(3,6)=30$

Comparing the four results, the largest is 30, at the corner $(3,6)$ .
The region is bounded and includes its boundary, so a corner does attain the maximum, and no other feasible point can beat 30.

Answer

$P(0,2)=8$ , $P(5,0)=10$ , $P(7,3)=26$ , and $P(3,6)=30$ ; the maximum 30 is at $(3,6)$ .

Key idea

On a bounded region that includes its boundary, evaluating a linear objective at every corner and comparing the values locates the maximum.
Problem 1: Mark complete
Problem 2 A liquid order

A liquid order uses $x$ liters of A at 4 dollars per liter and $y$ liters of B at 7 dollars per liter. Any real amounts are allowed. The order must contain at least 5 liters in all and at least as much A as B. Write a complete linear model for minimizing the cost, including the conditions that keep both amounts from going below zero.
1. Hint 1
  Separate the quantity being minimized from the conditions that make an order acceptable.
2. Hint 2
  Add each liquid cost for the objective and translate each quantity condition separately.
Answer

Minimize $C=4x+7y$ dollars, subject to $x+y\ge5$ , $x\ge y$ , $x\ge0$ , and $y\ge0$ .

Full solution

The total cost in dollars is
$C=4x+7y$
This is the objective to minimize.
The total-volume condition is $x+y\ge5$ , and the comparison of liquids is $x\ge y$ .

Both amounts must be zero or positive, so $x\ge0$ and $y\ge0$ are also required.
The order $(5,0)$ satisfies all four conditions, confirming that the model permits an order.

Answer

Minimize $C=4x+7y$ dollars, subject to $x+y\ge5$ , $x\ge y$ , $x\ge0$ , and $y\ge0$ .

Key idea

A complete optimization model states the objective, every quantity restriction, and the nonnegative domains.
Problem 2: Mark complete
Problem 3 Where two limits meet

Two boundary lines of a feasible region are $3x+y=19$ and $2x+3y=22$ , and the region has a vertex where these two lines cross. Find that vertex and evaluate $P=5x+y$ there.
1. Hint 1
  A vertex is the single point lying on both boundary lines at once.
2. Hint 2
  Solve the two boundary equations as a system, then substitute the solution into the objective.
Answer

The vertex is $(5,4)$ , where $P=29$ .

Full solution

The crossing point satisfies both equations together.
Solving the first for the second coordinate gives
$y=19-3x$
Substituting that into $2x+3y=22$ gives
$2x+3(19-3x)=22$ $2x+57-9x=22$ $-7x=-35$ $x=5$

Then $y=19-3(5)$ , so $y=4$ and the vertex is $(5,4)$ .
Both boundary equations check there, since $3(5)+4=19$ and
$2(5)+3(4)=22.$

Evaluating the objective at that vertex,
$P=5(5)+4$ $P=29$

Answer

The vertex is $(5,4)$ , where $P=29$ .

Key idea

A vertex is found by solving the pair of boundary equations that cross there, not by reading the grid.
Problem 3: Mark complete
Problem 4 A design region

For real variables, maximize $P=2x+3y$ subject to $1\le x\le5$ , $0\le y\le4$ , and $2x+y\le12$ . Sketch the region on paper, copying the blank grid in the figure, then give every vertex and evaluate $P$ at each.

A blank grid with $x$ from 0 to 6 and $y$ from 0 to 5.

Text description of this figure

A blank coordinate grid. The horizontal x axis is numbered 0, 1, 2, 3, 4, 5 and 6, and the vertical y axis is numbered 0, 1, 2, 3, 4 and 5, with the origin labeled 0. Faint grid lines run one unit apart in both directions, and each axis carries an arrowhead at its positive end. Nothing is drawn inside the grid: no points, no lines, no shading and no labels.
1. Hint 1
  Find which corners of the initial rectangle survive the slanted constraint.
2. Hint 2
  Include crossings where the slanted line cuts a rectangle edge, then compare all vertex values.
Answer

The region is the pentagon with vertices $(1,0)$ , $(5,0)$ , $(5,2)$ , $(4,4)$ , and $(1,4)$ . The values are $(1,0):2$ , $(5,0):10$ , $(5,2):16$ , $(4,4):20$ , $(1,4):14$ . Maximum 20 at $(4,4)$ .

Full solution

The rectangle runs from $x=1$ to 5 and from $y=0$ to 4.
Its corner $(5,4)$ fails $2x+y\le12$ , since $2(5)+4=14$ .
The line $2x+y=12$ cuts $x=5$ at $(5,2)$ and $y=4$ at $(4,4)$ .
The other three rectangle corners survive.

Shade the pentagon with vertices $(1,0)$ , $(5,0)$ , $(5,2)$ , $(4,4)$ , and $(1,4)$ , all edges included.
Evaluate the objective:
$P(1,0)=2$ $P(5,0)=10$ $P(5,2)=16$ $P(4,4)=20$ $P(1,4)=14$

The maximum is 20 at $(4,4)$ .
The region is nonempty and bounded with included straight edges, so a vertex attains the maximum.
At the winning point, $2x+y=12$ and $y=4$ both hold, and every other limit holds as well.

Answer

The region is the pentagon with vertices $(1,0)$ , $(5,0)$ , $(5,2)$ , $(4,4)$ , and $(1,4)$ . The values are $(1,0):2$ , $(5,0):10$ , $(5,2):16$ , $(4,4):20$ , $(1,4):14$ . Maximum 20 at $(4,4)$ .

Key idea

Clipping a rectangle can introduce new vertices that must be checked in optimization.
Problem 4: Mark complete
Problem 5 A program schedule

A program spends $x$ hours on video work and $y$ hours on text work. Any real durations are allowed. Each video hour uses 1 unit of studio capacity and each text hour uses 2 units, with at most 12 units available. Video work can receive at most 6 hours, and text work must receive at least 1 hour. Each video hour earns 4 points and each text hour earns 3 points. Write the model and find the greatest score, checking every feasible corner.
1. Hint 1
  Studio capacity, the video ceiling, and the text minimum are three separate conditions.
2. Hint 2
  Use the resulting corners to compare the score objective.
Answer

Maximize $P=4x+3y$ with $x+2y\le12$ , $x\le6$ , $y\ge1$ , $x\ge0$ . Maximum 33 points at $(6,3)$ .

Full solution

Each video hour uses 1 unit of capacity and each text hour 2, so the capacity condition is $x+2y\le12$ .
The objective is $P=4x+3y$ , and the other conditions are $x\le6$ , $y\ge1$ , and $x\ge0$ ; here $y\ge0$ follows from $y\ge1$ .

The included-boundary region has vertices $(0,1)$ , $(6,1)$ , $(6,3)$ , and $(0,6)$ .
The corner $(6,3)$ is where $x=6$ meets $x+2y=12$ , and $(0,6)$ is where $x=0$ meets that same line.

The objective values are
$P(0,1)=3$ $P(6,1)=27$ $P(6,3)=33$ $P(0,6)=18$
The bounded-region maximum is 33 points at $(6,3)$ .

That schedule spends 6 hours on video and 3 on text.
It uses $6+2(3)=12$ units of capacity, the whole allowance, and it clears the one-hour text minimum.

Answer

Maximize $P=4x+3y$ with $x+2y\le12$ , $x\le6$ , $y\ge1$ , $x\ge0$ . Maximum 33 points at $(6,3)$ .

Key idea

A resource story becomes a short comparison once each limit is an inequality and the corners are listed.
Problem 5: Mark complete
Problem 6 A strip with no ceiling

Over real variables satisfying $0\le x\le4$ and $y\ge2$ , find the maximum and minimum of each objective $P=3x-y$ and $Q=y-3x$ , if they exist. Explain how the unbounded direction affects them.
1. Hint 1
  Determine whether larger heights increase or decrease each objective.
2. Hint 2
  Use the finite coordinate limits for one extreme, then examine what happens when the second coordinate grows without bound.
Answer

P: maximum 10 at $(4,2)$ , no minimum. Q: minimum $-10$ at $(4,2)$ , no maximum.

Full solution

Since $x\le4$ and $y\ge2$ ,
$3x-y\le12-2$ $P\le10$
Equality occurs at $(4,2)$ , which is feasible.
Thus the maximum is 10.

The points $(0,2+t)$ are feasible for every $t\ge0$ and give
$P=-2-t$
This decreases without bound as $t$ grows, so there is no minimum.
The unbounded direction lowers the objective rather than raising it.

The second objective is the negative of the first:
$Q=-P$
Hence $Q\ge-10$ , with equality at $(4,2)$ .
Along the same feasible points $(0,2+t)$ ,
$Q=2+t$
This grows without bound, so Q has no maximum.
The allowed upward direction lowers P and raises Q.

Answer

P: maximum 10 at $(4,2)$ , no minimum. Q: minimum $-10$ at $(4,2)$ , no maximum.

Key idea

An unbounded direction can destroy a maximum or a minimum depending on the signs in the objective.
Problem 6: Mark complete
Problem 7 An allocation request

Maximize $P=x+y$ over $0\le x\le4$ , $0\le y\le4$ , and $x+y\le6$ . Find every maximizing point and explain how the vertices identify them.
1. Hint 1
  The last constraint is already an upper bound on the objective.
2. Hint 2
  Find the portion of its equality line that remains within the other four bounds.
Answer

Maximum 6 at every point with $x+y=6$ and $2\le x\le4$ , the segment from $(2,4)$ to $(4,2)$ .

Full solution

The region has vertices $(0,0)$ , $(4,0)$ , $(4,2)$ , $(2,4)$ , and $(0,4)$ .
Their objective values are 0, 4, 6, 6, and 4.
Thus the maximum is 6, reached at both ends of one edge.

Every point on that edge satisfies
$x+y=6$
Writing $y=6-x$ , the bounds $0\le x\le4$ and $0\le y\le4$ restrict its first coordinate to
$2\le x\le4.$
All these points give 6, and every other feasible point has $x+y<6$ .

Answer

Maximum 6 at every point with $x+y=6$ and $2\le x\le4$ , the segment from $(2,4)$ to $(4,2)$ .

Key idea

When an edge lies on the highest feasible level line, every point of that edge is optimal.
Problem 7: Mark complete
Problem 8 An additional requirement

For $0\le x\le3$ and $0\le y\le2$ , the objective is $P=2x+y$ . A new requirement $x+y\ge4$ is added. A student claims the maximum value stays the same. Decide whether the claim is correct, and justify your answer.
1. Hint 1
  Adding a requirement can only shrink the set of allowed points, never enlarge it.
2. Hint 2
  Find the original maximum, then test whether a point attaining it still satisfies the new requirement.
Answer

Yes; the maximum remains 8 at $(3,2)$ .

Full solution

The original objective is bounded by
$P\le2(3)+2$ $P\le8$
The point $(3,2)$ attains 8 and satisfies the new condition, since $3+2\ge4$ .

The new feasible region is contained in the old one, so it cannot produce an objective value above 8.
Since the old maximizing point survives, 8 remains the maximum despite removal of other corners.

Answer

Yes; the maximum remains 8 at $(3,2)$ .

Key idea

A maximum survives an added constraint when an old maximizing point remains feasible.
Problem 8: Mark complete
Problem 9 A ceiling claim

Maximize $P=4x+5y$ over $x\ge0$ , $y\ge0$ , $y\le5$ , $x+4y\le21$ , and $4x+y\le24$ . A student says that because raising $y$ raises $P$ , a maximizing point must have $y$ at its ceiling, so $y=5$ there. For each of the three upper limits $y\le5$ , $x+4y\le21$ , and $4x+y\le24$ , state whether it is fully used at the maximizing point, and say whether the student's claim is correct.
1. Hint 1
  Deciding which limits are fully used means finding the maximizing point itself, so locate that point first.
2. Hint 2
  List all vertices and compare the objective values before checking which limits are tight.
Answer

Maximum 40 at $(5,4)$ , where $x+4y\le21$ and $4x+y\le24$ are fully used but $y\le5$ is not; the claim is incorrect.

Full solution

The five vertices are $(0,0)$ , $(6,0)$ , $(5,4)$ , $(1,5)$ , and $(0,5)$ .
The corner $(5,4)$ is where the two slanted boundaries cross.
Multiplying $4x+y=24$ by 4 gives
$16x+4y=96$
and subtracting $x+4y=21$ from that leaves
$15x=75$
so $x=5$ , and $y=24-4(5)$ gives $y=4$ .

The objective values at the five vertices are
$P(0,0)=0$ $P(6,0)=24$ $P(5,4)=40$ $P(1,5)=29$ $P(0,5)=25$

The maximum is 40 at $(5,4)$ .
There $x+4y=21$ and $4x+y=24$ , so those two upper limits are fully used, but $y=4<5$ , so the height limit is not.
The student's claim therefore fails.
Raising $y$ by itself would raise $P$ , but from $(5,4)$ the limit $x+4y\le21$ forces $x$ down by four for each unit $y$ rises, so $P$ drops by 11 per unit instead.

Answer

Maximum 40 at $(5,4)$ , where $x+4y\le21$ and $4x+y\le24$ are fully used but $y\le5$ is not; the claim is incorrect.

Key idea

An optimal point may leave some upper limits unused.
Problem 9: Mark complete
Problem 10 An objective report

A bounded feasible polygon includes its boundary and has corners $A(0,0)$ , $B(4,0)$ , $C(2,4)$ , and $D(0,3)$ . A report for the linear objective $P=ax+by$ correctly records 12 at B and 16 at C. It also claims 17 at the interior point $M(1,2)$ . Can all three values be correct? Give the correct value at M and the actual maximum over the polygon, explaining why no unlisted point can give a larger value.
1. Hint 1
  The two verified records determine the objective coefficients.
2. Hint 2
  Evaluate the corrected objective at M and at every corner.
3. Hint 3
  Relate the largest corner value to the last objective level line that still touches the polygon.
Answer

No; $P(M)=8$ . The maximum is 16 at $C(2,4)$ .

Full solution

The record at B gives
$4a=12$
so $a=3$ .
The record at C then gives
$6+4b=16$
so $b=5/2$ .
The objective is therefore
$P=3x+\frac52y$

At M,
$P(1,2)=3+5$ $P(1,2)=8$
Thus the reported value 17 is inconsistent with the two verified records.

The four corner values are
$P(A)=0$ $P(B)=12$ $P(C)=16$ $P(D)=\frac{15}{2}$
The greatest is 16 at C.
For a bounded feasible polygon with its boundary included, the highest objective level line that still meets the region touches a vertex or an edge whose endpoints are vertices.
Thus an unlisted point cannot exceed every corner value.
Only C attains the largest corner value, so it is the unique maximizing point.

Answer

No; $P(M)=8$ . The maximum is 16 at $C(2,4)$ .

Key idea

Verified objective values can expose an inconsistent interior report, while the corner principle certifies the corrected maximum.
Problem 10: Mark complete

← Back to lesson