First column represents coefficients of basic variables (current solution variables) in the objective (e) second column represent basic variables (current solution variables) and last column represents, right hand side of the constraints in standard form. after congesting all the inequalities into equalities, in any table, current values of the current solution variables (basic variables) is given by R. (Cj – Ej) represents the advantage of bringing any non basic variable to the current solution i.e. In the Table 2, values of Cj – Ej are 12, 15 and 14 for X.
If any of the values of Cj – Ej is ve then it means that most positive values represents the variable which is brought into current solution would increase the objective function to maximum extent. it would become basic and would enter the solution.
Now look for the least positive value in the Ratio Column and that would give the key row. Now all the elements in the key coloumn except the key element is to be made zero and key element is to be made unity.
This is done with the help of row operations as done is the matrices.
The above information can be expressed in the Table 1 In the table, first row represents coefficients of objective function, second row represents different variables (first regular variables then slack/surplus variables).
Third fourth & fifth row represents coefficients of variables in all the constraints. In Table 1, current solution is: S represents the values of last row.An extreme point or vertex of this polytope is known as basic feasible solution (BFS).It can be shown that for a linear program in standard form, if the objective function has a maximum value on the feasible region, then it has this value on (at least) one of the extreme points.Infinite Number of Solutions: A Linear Programming Problem is said to have infinite number of solutions if during any iteration, in Cj-Ej row, we have all the values either zero or -ve. But since one of the regular variables has zero value in Cj-Ej row, it can be concluded that there exists an alternative optimal solution. It can be seen that optimal solution has been reached since all values in Cj-Ej row are zero or -ve But X is non basic variable and it has zero value in Cj-Ej row, it indicates that X, can be brought into solution, however it will not increase the value of objective function and alternative optimal exists. Maximize Z = Y, 2Y are basic variables (variables in current solution)to start with. AS Cj- Ej is positive, the current solution is not optimal and hence better solution exists.Iterate towards an optimal solution Performing iterations to get an optimal solution as shown in Table below Since Cj-Ej is either zero or negative under all columns, the optimal basic feasible solution has been obtained.one of the corner points of the feasible area used to be the optimal solution. This method is mathematical treatment of the graphical method. These slack or surplus variables are introduced because it is easier to deal with equalities than inequalities in mathematical treatment.We used to test all the corner points by putting these value in objective function. Here also various corner points of the feasible area are tested for optimality. In simplex method therefore the number of corner points to be tested is reduced considerably by using a very effective algorithm which leads us to optimal solution corner point in only a few iterations. (a) Right hand side of all the constraints must be either zero or ve. If constraint is ≤ type the slack variables are added if constraint is ≥ type then surplus variable is subtracted.Here key element is already unity and other element in key coloumn are made zero by adding -1 times first row in its third row & get next table.Therefore second feasible solution becomes X coloumn is key column, also find key row as explained earlier and complete Table 5.Key element in Table 5 comes out to be 2 and it is made unity and all other elements in the key coloumn are made zero with the help of row operations and finally we get Table 6.First key element is made unity by dividing that row by 2.