Practice: Solving a Two-Variable Linear Program Graphically

Recognition · Interpretation

A linear program maximizes $4 x + y$ over a bounded feasible region in the first quadrant. In which direction should the contour line $4 x + y = k$ be slid to improve the objective?

1 hint available, least help first.

Hint 1: Retrieval cue

What is the relationship between the objective coefficients and the contour lines?

Direct application

In the linear program

\begin{aligned} max & 3 x_{1} + 5 x_{2} \\ subject to & x_{1} \leq 4, \\ 2 x_{2} \leq 12, \\ 3 x_{1} + 2 x_{2} \leq 18, \\ x_{1}, x_{2} \geq 0, \end{aligned}

the objective contour last touches the feasible region at the corner where $2 x_{2} = 12$ and $3 x_{1} + 2 x_{2} = 18$ are both tight. Solve those two equations and report the value of $x_{1}$ at that corner.

Your answer

Enter the value. It is checked against the answer and the precision this task asks for.

Classification

Consider the feasible region defined by

x_{1} \leq 4, 2 x_{2} \leq 12, 3 x_{1} + 2 x_{2} \leq 18, x_{1}, x_{2} \geq 0.

Select every point that is a corner of this region.

Select every option that applies

Every option that applies, and only those. The set is checked as a whole.

Direct application

Consider the linear program

\begin{aligned} max & 3 x_{1} + 5 x_{2} \\ subject to & x_{1} \leq 4, \\ 2 x_{2} \leq 12, \\ 3 x_{1} + 2 x_{2} \leq 18, \\ x_{1}, x_{2} \geq 0. \end{aligned}

The optimum lies where $2 x_{2} = 12$ and $3 x_{1} + 2 x_{2} = 18$ are both tight. Solve those two equations and report the optimal objective value.

Your answer

Enter the value. It is checked against the answer and the precision this task asks for.

Direct application · Construction

Solve the following linear program graphically.

\begin{aligned} max & 4 x + 5 y \\ subject to & x + 2 y \leq 10, \\ 3 x + y \leq 15, \\ x, y \geq 0. \end{aligned}

Identify the feasible region's corners, say which corner the objective contour last touches and why, then solve the tight constraints to give the exact optimal solution and value. State whether the optimum is unique.

Write your answer

Write your answer, then compare it with the worked solution.

3 hints available, least help first.

Hint 1: Retrieval cue

Start with the intercepts of each constraint line, then decide which side of each line is allowed.

Hint 2: Concept cue

The objective vector is $(4, 5)$ . Which corner is furthest in that direction?

Hint 3: Next step

At that corner both constraints hold with equality. Solve $x + 2 y = 10$ and $3 x + y = 15$ simultaneously.

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

The constraint lines meet the axes at $(0, 5)$ and $(10, 0)$ for $x + 2 y = 10$ , and at $(0, 15)$ and $(5, 0)$ for $3 x + y = 15$ . With the nonnegativity restrictions the feasible region has corners $(0, 0)$ , $(0, 5)$ , $(4, 3)$ and $(5, 0)$ . The objective vector $(4, 5)$ points up and to the right, so the contour is slid that way; the last corner it touches is the intersection of the two constraint lines. Solving $x + 2 y = 10$ with $3 x + y = 15$ : from the second $y = 15 - 3 x$ , so $x + 30 - 6 x = 10$ , giving $- 5 x = - 20$ , $x = 4$ and $y = 3$ . The optimal value is $4 (4) + 5 (3) = 31$ . Checking the other corners gives $0$ , $25$ and $20$ , all smaller. The optimum is unique: the contour slope $- 4 / 5$ matches neither constraint slope ( $- 1 / 2$ and $- 3$ ), so the contour meets the region at a single point.

A complete answer does each of these:

exact coordinates solved
improving direction used
optimal value reported
region identified
uniqueness stated

Error diagnosis · Explanation

A student solves

max 5 x + 4 y subject to x + 2 y \leq 11, 3 x + y \leq 15, x, y \geq 0

and writes:

"From my graph the two lines cross at about $x = 4$ , $y = 3$ , so the optimum is approximately $(4, 3)$ with value about $32$ ."

The student has identified the correct corner. Explain why the reported answer is nevertheless wrong, obtain the exact optimal solution and value, and state the general rule this illustrates.

Write your answer

Write your answer, then compare it with the worked solution.

2 hints available, least help first.

Hint 1: Retrieval cue

Which two constraints hold with equality at the corner the student identified?

Hint 2: Next step

Solve $x + 2 y = 11$ and $3 x + y = 15$ simultaneously and compare with the student's reading.

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

Identifying the crossing of $x + 2 y = 11$ and $3 x + y = 15$ as the optimal corner is correct. The error is taking coordinates from the drawing. Solving the two equations: from the second, $y = 15 - 3 x$ , so $x + 2 (15 - 3 x) = 11$ , giving $x + 30 - 6 x = 11$ , $- 5 x = - 19$ and $x = 19 / 5 = 3.8$ ; then $y = 15 - 57 / 5 = 18 / 5 = 3.6$ . The exact value is $5 (19 / 5) + 4 (18 / 5) = 19 + 72 / 5 = 167 / 5 = 33.4$ , not 32. A hand-drawn axis cannot distinguish $3.8$ from $4$ , and the resulting error in the objective is not small. The general rule is that the plot determines which corner is optimal and which constraints are tight there; the coordinates come from solving those constraint equations.

A complete answer does each of these:

region identified
exact coordinates solved
optimal value reported

Transfer · Representation translation · Evaluation

Without drawing anything, consider

max x + 2 y subject to x + 2 y \leq 14, 3 x + y \leq 21, x, y \geq 0 .

Predict from the coefficients alone whether this program has a unique optimal solution, and justify your prediction geometrically. Then confirm it by computing the objective value at each corner of the feasible region, and describe the full set of optimal solutions.

Write your answer

Write your answer, then compare it with the worked solution.

2 hints available, least help first.

Hint 1: Retrieval cue

When does a sliding contour leave the region along a whole edge rather than from a single corner?

Hint 2: Concept cue

Look at the objective coefficients and the first constraint's coefficients side by side.

Compare with the worked solution

Comparing does not record a result. Judging your own written answer cannot show that you can do this without help.

The objective $x + 2 y$ has exactly the coefficients of the first constraint $x + 2 y \leq 14$ , so the contour lines are parallel to that constraint's boundary. When the sliding contour reaches the boundary it coincides with it rather than touching at one point, so the optimum is not unique. Confirming: the corners are $(0, 0)$ , $(0, 7)$ , $(28 / 5, 21 / 5)$ and $(7, 0)$ , where $(28 / 5, 21 / 5)$ solves $x + 2 y = 14$ with $3 x + y = 21$ . The objective values are $0$ , $14$ , $28 / 5 + 42 / 5 = 14$ , and $7$ . Two distinct corners, $(0, 7)$ and $(28 / 5, 21 / 5)$ , both attain $14$ . The full optimal set is the entire edge joining them, that is every point $λ (0, 7) + (1 - λ) (28 / 5, 21 / 5)$ for $λ \in [0, 1]$ , equivalently every feasible point satisfying $x + 2 y = 14$ .

A complete answer does each of these:

improving direction used
exact coordinates solved
uniqueness stated

Practice: Solving a Two-Variable Linear Program Graphically

Recognition · Interpretation

Direct application

Classification

Direct application

Direct application · Construction

Error diagnosis · Explanation

Transfer · Representation translation · Evaluation

Session complete

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history