Let us now try to analyze a LP model algebraically.
A solution of the standard LP model will be a solution for the original model (since the slack and surplus variables once removed would make the equations regain their old imbalance) and due to a similar reasoning a solution for the original model will also correspond to a solution for the standard model.
Now, in the next iteration according to the simplex method we should get a new BFS i.e move to a new corner point on the graph.
We can induce an increase in the value of only one variable at a time by making it an entering variable, and since becomes the leaving variable. Although any procedure of solving a linear system can be applied at this stage, usually Gauss Jordan elimination is applied.
LP models easily using the graphical method outlined in the previous section but what should we do in case of three variable problems, i.e. It is an iterative method which by repeated use gives us the solution to any n variable LP model.
when our company makes three products we have to make decisions about. A point to note is that the objective function in the original LP model and the standard model is the same.(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 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.We can't possibly examine the complete set of infinite solutions.However due to a mathematical result our work is shortened.Now what are the candidates for the optimal solution?They are the solutions of the equality constraints.This is repeated until it is clear that the current BFS can't be improved for a better objective value. It is clear that one factor is crucial to the method: which variable should replace which.The variable which is replaced is called the leaving variable and the variable which replaces it is known as the entering variable.