Objective contour lines
Objective Contour Lines
Objective contour lines show where the objective function has the same value.
They are the key geometric tool for solving a two-variable LP graphically.
Objective Function
For two variables, a linear objective has the form:
\[f(x)=c_1x_1+c_2x_2\]where:
\[c=\begin{bmatrix}c_1\\c_2\end{bmatrix}\]is the cost vector or profit vector.
Contour Line
A contour line is obtained by fixing the objective value:
\[c_1x_1+c_2x_2=k\]Every point on that line has the same objective value $k$.
Changing $k$ gives a family of parallel lines.
Example
For:
\[f(x)=x_1+x_2\]the contour lines are:
\[x_1+x_2=k\]Examples:
\[x_1+x_2=0\] \[x_1+x_2=3\] \[x_1+x_2=5\]These are parallel lines.
The line with larger $k$ has a larger objective value.
Why They Are Parallel
All contour lines of the same linear objective have the same left-hand side:
\[c_1x_1+c_2x_2\]Only the right-hand side $k$ changes.
So their slope does not change.
If $c_2\ne 0$, then:
\[x_2=\frac{k}{c_2}-\frac{c_1}{c_2}x_1\]The slope is:
\[-\frac{c_1}{c_2}\]which does not depend on $k$.
Maximization
For maximization, slide the contour line in the direction where $k$ increases.
The optimal point is the last feasible point touched before the line leaves the feasible region.
If the last contact is one point, the optimum is unique.
If the last contact is an edge, there are multiple optima.
Minimization
For minimization, slide the contour line in the direction where $k$ decreases.
The optimal point is the last feasible point touched before leaving the feasible region in the decreasing direction.
Connection with the Cost Vector
The vector:
\[c=\begin{bmatrix}c_1\\c_2\end{bmatrix}\]is perpendicular to each contour line.
It points in the direction of increasing objective value.
Therefore:
- for maximization, move in direction $c$
- for minimization, move in direction $-c$
Example with a Feasible Region
Consider:
\[\max x_1+x_2\]subject to a feasible polygon.
Start with:
\[x_1+x_2=0\]Then imagine increasing $k$:
\[x_1+x_2=1\] \[x_1+x_2=2\] \[x_1+x_2=3\]The line slides in the direction:
\[\begin{bmatrix}1\\1\end{bmatrix}\]The best feasible point is reached at the largest $k$ that still intersects the feasible region.
Computing the Value
Once the optimal point $x^*$ is found, compute:
\[z^*=c^Tx^*\]Example:
If:
\[x^*=\left(\frac{22}{3},\frac{4}{3}\right)\]and:
\[c=\begin{bmatrix}1\\1\end{bmatrix}\]then:
\[z^*=\frac{22}{3}+\frac{4}{3}=\frac{26}{3}\]Contour Lines Are Not Constraints
The contour line is not usually part of the constraints.
It is a tool for reading objective values.
The feasible region comes from constraints.
The contour line moves across that fixed region.
Checklist
You understand objective contour lines if you can:
- write $c^Tx=k$
- draw one contour line
- explain why all contour lines are parallel
- identify the direction of increasing objective value
- slide the line to find the best feasible point
- compute the optimal value after finding the optimal point
See Also
Exam checkpoint
For graphical questions, first check whether nonnegativity is explicitly stated. Then draw half-planes, list vertices, evaluate the objective, and state finite optimum, infeasibility, multiple optima, or unboundedness.