Contour Lines and the Direction of Improvement

Points of equal objective value form parallel lines. Everything about solving a linear program graphically follows from knowing which way to push them.

Those are two skills, not one, and only the first is drawing. The family of lines needs the slope, and the slope is identical whether you are maximising or minimising. Which way to push needs the sign, and the sign comes from the coefficient vector together with the direction of optimisation.

This matters because the second skill fails silently. A contour family drawn perfectly and pushed the wrong way produces a confident answer at the wrong corner, and nothing in the drawing looks amiss.

This unit assumes you can compute a dot product and plot a straight line.

Two programs sharing one contour family, worked to the point where the drawing stops helping.

Program A. Maximise $3x_1+2x_2$. Program B. Minimise $3x_1+2x_2$.

The contour family is identical: the lines $3x_1+2x_2=k$ for varying $k$, all with slope $-3/2$. Drawing them is the same task in both programs, and the drawing is equally correct in both.

Where they differ. Take the point $(2,2)$, objective value $10$, and move along $d=(1,1)$:

so the objective rises by $5$ per unit travelled. Program A wants that move; Program B wants $-d$. Nothing in the picture distinguishes the two, because a family of parallel lines carries no orientation.

A direction that changes nothing. Take $d=(2,-3)$:

Moving along $(2,-3)$ from any point keeps the objective at its current value. That direction is along a contour, and it is the same contour direction for both programs. Note it is perpendicular to $c=(3,2)$, which is the whole content of the geometry.

A test to run before trusting a drawing. Pick any two points in the feasible region, compute the objective at both, and confirm the one you believe is better actually scores better. On Program B, $(0,0)$ scores $0$ and $(2,2)$ scores $10$, so $(0,0)$ is the better of the two, which contradicts the habit of pushing away from the origin. The arithmetic settles it; the drawing never will.

Why this is the error that survives practice. A learner who has only maximised builds the habit "push away from the origin", and it works every time until the first minimisation. The habit is a coincidence of the problems seen, not a rule, and the drawing offers no warning when it fails.

The canonical statement gives the contour geometry and the test $c^{\mathsf{T}}d$. Its value is that one identity answers questions that look separate.

Which way to move. The objective changes by $\lambda c^{\mathsf{T}}d$, so a direction improves a maximisation exactly when . No drawing is required and the test works in any dimension, which matters because the picture stops at three.

Whether a whole edge is optimal. If $c^{\mathsf{T}}d=0$ along an edge, every point on it has the same objective value. That is the multiple-optima case, and it is detected by the same dot product rather than by inspecting the drawing for a parallel contour.

Why the gradient and the contours are both needed. The contour family says where equal-value lines run but is identical for $c$ and $-c$, so it cannot say which way improves. The vector $c$ supplies the orientation and says nothing about the values. A maximisation pushes along $c$, a minimisation against it, and the two representations are used together for that reason.

A caution about slope: $-c_1/c_2$ is undefined when $c_2=0$, where the contours are vertical. The dot product has no such special case.

A maximisation with positive coefficients. $max3x_1+2x_2$ gives $c=(3,2)$. Contours have slope $-3/2$. Push along $(3,2)$, up and to the right. Check: from $(0,0)$ to $(3,2)$ the objective goes from $0$ to $13$.

The same objective minimised. $min3x_1+2x_2$. The contours are identical lines with identical slope. Push against $(3,2)$, towards the origin. Nothing about the drawing changed; the travel direction reversed.

A negative coefficient. $max2x_1-5x_2$ gives $c=(2,-5)$. Improvement means moving right and down. A learner pushing 'away from the origin' by habit would slide up and to the right and lose $5$ per unit of $x_2$ gained.

A direction test. With $c=(2,-5)$, is $d=(1,1)$ improving for a maximisation? : no, it worsens the objective. Is $d=(5,2)$? $c^{\mathsf{T}}d=10-10=0$: neither. It runs along a contour, and the objective is unchanged.

The last case is the significant one. A direction with $c^{\mathsf{T}}d=0$ is exactly how a linear program comes to have an edge of equally good answers.

Problem. For

say which corner the contour reaches last, using the direction of improvement rather than testing every corner.

Goal. Identify the optimal corner from the geometry, then confirm.

Relevant principle. $c$ points towards increase; a minimisation travels against $c$.

Step 1: write down $c$. $c=(1,-3)$.

Step 2: find the travel direction. Minimising, so travel along $-c=(-1,3)$: left and up. Decreasing $x_1$ and increasing $x_2$ both reduce the objective, which matches the signs directly. A positive coefficient on $x_1$ means less $x_1$ is better, a negative coefficient on $x_2$ means more $x_2$ is better.

Step 3: push that way within the region. Going left drives $x_1$ to its smallest feasible value; going up drives $x_2$ as high as the constraints allow. With $x_1=0$, the binding limit is $x_1+x_2\le 6$, giving $x_2=6$. The corner is $(0,6)$.

Step 4: confirm against the other corners. They are $(0,0)$, $(4,0)$, $(4,2)$ and $(0,6)$, with objective values $0$, $4$, $-2$ and $-18$. The minimum is $-18$ at $(0,6)$, as predicted.

Check the sign convention held. Had this been a maximisation, travel would be along $c=(1,-3)$, right and down, reaching $(4,0)$ with value $4$, the largest of the four. The region never changed; only the travel direction did.

What did the work. The coefficient signs alone identified the corner before any value was computed. Enumerating the corners confirmed it; it was not the method.

Not the improving direction: the contour's own slope. The contour for $max3x_1+2x_2$ has slope $-3/2$, and $(-2,3)$ is a direction along it. Moving that way changes the objective by $c^{\mathsf{T}}d=-6+6=0$. Along the contour is precisely where nothing improves.

Not the improving direction: away from the origin. For $max2x_1-5x_2$, the direction $(1,1)$ leads away from the origin and worsens the objective, since $c^{\mathsf{T}}(1,1)=-3$. The habit works only for objectives with all-positive coefficients and fails quietly otherwise.

Not a contour: a constraint line. $x_1+2x_2\le 8$ drawn as $x_1+2x_2=8$ is a boundary of the region. It bounds what is permitted. A contour bounds nothing. It records where the objective is constant, and it extends across the whole plane, inside the region and outside it alike.

Not a reason to reverse $c$: a minimisation. For $min3x_1+2x_2$ the vector $c=(3,2)$ still points towards increase. It is not redefined as $(-3,-2)$. What changes is that you travel against it. Redefining $c$ per problem type is how sign errors enter the reduced-cost test later, where there is no picture to catch them.

Two facts about a linear objective look like one fact, and separating them is the whole of this unit.

What the drawing settles. Where the equal-value lines run. This needs only the ratio of the coefficients, and it is identical for $max3x_1+2x_2$, for $min3x_1+2x_2$, and for $max-3x_1-2x_2$. All three produce the same family of parallel lines of slope $-3/2$.

What the drawing cannot settle. Which way along them improves. Those three problems travel in three different ways: along $(3,2)$, against $(3,2)$, and against $(3,2)$ respectively. A family of parallel lines carries no orientation, so no amount of care in drawing recovers it.

Why the error survives inspection. Suppose the direction is taken backwards on the first of these. The contours are correct, the region is correct, the contour is slid neatly until it last touches, at the wrong corner. The output is a specific point and a specific value, both plausible, neither flagged by anything visible. Compare an arithmetic slip, which usually produces something that looks odd.

The habit that prevents it. Write $c$ down explicitly, state whether you are maximising or minimising, and say the travel direction in words before sliding anything: maximising, so travel along $c$, or minimising, so travel against $c$. When a direction is in doubt, test it: compute $c^{\mathsf{T}}d$ and read the sign. One multiplication settles what an hour of careful drawing cannot.

1. For $max5x_1+x_2$, give the contour slope and the travel direction. Then do the same for $min5x_1+x_2$.

2. With $c=(4,-1)$ and a maximisation, decide for each direction whether it improves, worsens, or leaves the objective unchanged: $(1,1)$, $(1,4)$, $(-1,0)$.

3. Find a nonzero direction along which $max6x_1+9x_2$ does not change, and say what it would mean for such a direction to run along an edge of the feasible region.

4. A learner says: 'It is a minimisation, so I flipped the objective to $-c$ and then pushed away from the origin.' Is the answer right? Is the reasoning? Explain what happens if they later reuse this on $min-2x_1+3x_2$.

5. Two objectives, $max2x_1+3x_2$ and $max4x_1+6x_2$, are optimised over the same region. What is the same about their contour families, what is the same about their optimal solutions, and what differs about their optimal values?

A linear objective assigns a value to every point. Equal-value points form contours: parallel straight lines sharing the coefficient vector, differing only in position.

The coefficient vector $c$ is orthogonal to every contour and points towards increase, always, irrespective of whether the problem maximises or minimises. What the direction of optimisation changes is which way you travel: along $c$ to maximise, against $c$ to minimise.

Any direction can be tested rather than judged. Moving along $d$ changes the objective by $c^{\mathsf{T}}d$, so the sign of one dot product decides whether $d$ improves, worsens, or does nothing. A direction with $c^{\mathsf{T}}d=0$ runs along a contour, and when such a direction lies along an edge of the feasible region, that edge is a set of equally optimal points.

Drawing the family and choosing the direction are separate skills with separate failure modes, and only the second fails invisibly. This same quantity returns as the reduced cost once the geometry is gone, where the sign convention is all that remains of the picture.