Since first ratio is minimum, remove the first vector p, form the basis matrix. Since negative Ratio is not counted,] so the second ratio is not considered. k = 2 and Hence X 2 should be entering vector (Key column) By minimum ratio ratio Now repeat step 3 through 5 as and when needed until an optimum solution is obtained in table 5. Now construct the improved simple table as follows:įrom this table, the improved basic feasible solution is read as: Thus, the process can be fortified by simple matrix transformation as follow: Then subtract appropriate multiples of this new row from the other remaining rows, so as to obtain zero in the remaining position of the column X 1. If the number in the marked ‘□’ position is other than unity, divide all elements of that row by the ‘key element’ (the element at the intersection of minimum ratio arrow (←) and incoming vector arrow (↑) is called the key element). In order to bring B 2 in place of incoming vector X1 = unity must occupy the marked ‘□’ position and zero at all other places of X 1. Now starting table (2) is modified to table (3) In mathematical form, this rule is written as,Ĭomparing both sides of this equation, r = 2 so the vector B 2 marked with downward arrow (↓) should be removed from the basis matrix. This rule is called the Minimum Ratio Rule. The outgoing vector β r is selected corresponding to the minimum ratio of elements of X B by the corresponding positive elements of predetermined incoming vector X K. The column x 1 is marked by an upward arrow (↑). Therefore k = 1 and column vector x 1, must enter the basis matrix. The incoming vector X k is always selected corresponding to the most negative value of Δ j. In order to improve this basic feasible solution, the vector or entering the basis matrix and the vector to be removed from the basis matrix are determined by the following rules, such vectors are usually named as “incoming vector” and “outgoing vector” respectively. Hence proceed to improve this solution in step 4. (iii) If corresponding to most negative Δ j, all elements of the column X j are negative or zero (≤ 0), then the solution under test will be unboundedĪpplying this rule for testing the optimality of starting basic feasible solution, it is observed that Δ 1, and Δ 2 both are negative. (ii) If at least one Δ j is negative, the solution under test is not optimal, then proceed to improve the solution in step 4. (i) If all Δ j ≥ 0, the solution under test will be optimal. This is done by computing the “net evaluation” D j for variable x j by the formula Now, proceed to test basic feasible for optimality by the rules given below. So 5, = 4, s 2 = 2, here The complete starting feasible solution can be immediately read from table 2 as s 1 = 4, s 2, x, = 0, x 2 = 0 and the value of the objective function is zero. So x 1 = x 2 = 0 here, column x B gives the values of basic variables in the first column. It should be remembered that values of non-basic variables are always zero at each iteration. The values z j represents the amount by which the value of objective function Z would be decreased or increased if one unit of given variable is added to the new solution. Number a ij represent the rate at which resource (i- 1, 2- m) is consumed by each unit of an activity j (j = 1,2 … n). Column x B gives the current values of the corresponding variables in the basic. Column C B gives the coefficients of the current basic variables in the objective function. The second row gives major column headings for the simple table. These values represent cost or profit per unit of objective function of each of the variables. The first row in table indicates the coefficient c j of variables in objective function, which remain same in successive tables. Write down the coefficients of all the variables in given LPP in the tabular form, as shown in table below to get an initial basic Feasible solution. In this example, the inequality constraints being ‘≤’ only slack variables s 1 and s 2 are needed. The coefficients of slack or surplus variables are zero in the objective function. (iv) Next convert the inequality constraints to equation by introducing the non-negative slack or surplus variable. In this example, all the b i (height side constants) are already positive. If not, it can be changed into positive value on multiplying both side of the constraints by-1. (iii) Ensure all b i values are positive. (ii) If objective function is of minimisation type then convert it into one of maximisation by following relationship (i) Formulate the mathematical model of given LPP. The steps in simplex algorithm are as follows: