Cost vector and direction of improvement
Cost Vector and Direction of Improvement
The cost vector tells us how the objective function changes.
In graphical linear programming, it tells us which way to slide the objective contour lines.
Objective Function
Let:
\[f(x)=c^Tx\]For two variables:
\[f(x_1,x_2)=c_1x_1+c_2x_2\]The vector:
\[c=\begin{bmatrix}c_1\\c_2\end{bmatrix}\]is called the cost vector.
In maximization problems, it is also often called the profit vector.
Gradient Interpretation
For a linear function:
\[f(x_1,x_2)=c_1x_1+c_2x_2\]the gradient is:
\[\nabla f=\begin{bmatrix}c_1\\c_2\end{bmatrix}=c\]The gradient points in the direction of fastest increase.
So $c$ points in the direction where the objective increases.
Direction of Decrease
The opposite vector:
\[-c\]points in the direction where the objective decreases.
Therefore:
| Problem | Direction of improvement |
|---|---|
| Maximization | $c$ |
| Minimization | $-c$ |
Example
For:
\[f(x)=x_1+x_2\]the cost vector is:
\[c=\begin{bmatrix}1\\1\end{bmatrix}\]For maximization, contour lines move northeast.
For minimization, contour lines move southwest.
Perpendicular to Contour Lines
A contour line has equation:
\[c^Tx=k\]The vector $c$ is perpendicular to this line.
That is why the line moves in the direction $c$ when $k$ increases.
Algebraic Check
If we move from $x$ in direction $d$, the new point is:
\[x+\theta d\]The objective becomes:
\[c^T(x+\theta d)=c^Tx+\theta c^Td\]So:
- if $c^Td>0$, the objective increases as $\theta$ increases
- if $c^Td<0$, the objective decreases as $\theta$ increases
- if $c^Td=0$, the objective stays constant along that direction
Improvement Direction and Feasibility
The cost vector tells us where the objective improves.
It does not guarantee feasibility.
We can only move within the feasible region.
The optimal point is the best point that is both:
- in an improving direction
- still feasible
Maximization Procedure
For:
\[\max c^Tx\]- draw a contour line $c^Tx=k$
- draw or imagine the vector $c$
- slide the contour line in the direction of $c$
- stop at the last contact with the feasible region
Minimization Procedure
For:
\[\min c^Tx\]- draw a contour line $c^Tx=k$
- draw or imagine the vector $-c$
- slide the contour line in the direction of $-c$
- stop at the last contact with the feasible region
Multiple Optima
If the objective contour line is parallel to an edge of the feasible region, then the final contact may be the whole edge.
Along that edge:
\[c^Tx=k^*\]for every point on the edge.
So all those points are optimal.
Unboundedness
If the feasible region extends forever in a direction $d$ and:
\[c^Td>0\]for maximization, then the problem is unbounded above.
If:
\[c^Td<0\]for minimization, then the problem is unbounded below.
Checklist
You understand the cost vector if you can:
- identify $c$ from the objective function
- draw $c$ in the plane
- explain why $c$ is the gradient of the objective
- choose the correct improvement direction for max or min
- connect $c$ with contour lines
- detect when the objective improves forever
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.