(Readers familiar with linear algebra will recognize that it means that the matrix formed with the basis variable columns is transformed into reduced row echelon form.) The solution can then be simply read off from the right most solution column (as n-m of the variables are put to zero and the rest including z have coefficient 1 in one constraint each).
Since z is also a variable it's row is treated as one among the constraints comprising the linear system.
The result is that if out of the n variables, n-m variables are put to zero, and then if the constraint system can be solved then the solution will correspond to a corner point in the n-space.
Such a solution is called a basic solution (Initial Solution).
The design of the simplex method is such so that the process of choosing these two variables allows two things to happen.
Operation Research Solved Problems
Firstly, the new objective value is an improvement(or at least equals) on the current one and secondly the new solution is feasible. Consider our old chemical company problem in standard form: Maximize z = equal to zero.
The following ratios are obtained: 24/6 = 4, 6/1 = 6, 1/-1 = -1 and 2/0 = undefined.
Ignoring the negative and the undefined ratio we now proceed to select the minimum of the other two ratios which is 4, obtained from dividing 24(the value of are 0 we are considering the BFS corresponding to the origin.
The following table summarizes all the basic solutions to the problem: . This procedure of solving LP models works for any number of variables but is very difficult to employ when there are a large number of constraints and variables.
For example, for m = 10 and n = 20 it is necessary to solve sets of equations, which is clearly a staggering task.