Once the reduced costs for each variable have been calculated and the entering variable chosen, it is necessary to calculate what is known as the search direction. The search direction is a vector of values which indicates how the basic variables will change to keep the solution feasible as the entering variable takes on a value other than 0.
Let B be the submatrix of A that corresponds to the basic variables and N the remainder of the matrix. Let xB be the vector of basic variables and xN be the vector of non-basic variables (xN= 0). We can write the constraints as follows:
BxB + NxN = b
Since we will leave all non-basic variables (except the entering variable) at 0, let us simplify the above equation. Let Aj be the column of A that corresponds to the entering variable xj. We can write:
BxB + Ajxj = b
If we solve for xB as a function of xj, we can see how xB will change as xj enters the basis and takes on positive values.
xB = B-1 b - (B-1 Aj) xj
The value, B-1 b, is the current value of xB, and we can define the search direction, yB, to be B-1 Aj.
As the value of xj is increased by 1 unit, xB will change by -yB.
Continue to the next step to see how we use the value of the current basis and the search direction to determine the step length using the minimum-ratio test.