# Simplex Solutions of LLP

26/03/2020

The Simplex Method or Simplex Algorithm is used for calculating the optimal solution to the linear programming problem. In other words, the simplex algorithm is an iterative procedure carried systematically to determine the optimal solution from the set of feasible solutions.

Firstly, to apply the simplex method, appropriate variables are introduced in the linear programming problem, and the primary or the decision variables are equated to zero. The iterative process begins by assigning values to these defined variables. The value of decision variables is taken as zero since the evaluation in terms of the graphical approach begins with the origin. Therefore, x1 and x2 is equal to zero.

The decision maker will enter appropriate values of the variables in the problem and find out the variable value that contributes maximum to the objective function and removes those values which give undesirable results. Thus, the value of the objective function gets improved through this method. This procedure of substitution of variable value continues until any further improvement in the value of the objective function is possible.

Following two conditions need to be met before applying the simplex method:

1. The right-hand side of each constraint inequality should be non-negative. In case, any linear programming problem has a negative resource value, then it should be converted into positive value by multiplying both the sides of constraint inequality by “-1”.
2. The decision variables in the linear programming problem should be non-negative.

Thus, the simplex algorithm is efficient since it considers few feasible solutions, provided by the corner points, to determine the optimal solution to the linear programming problem.

Any linear programming problem involving two variables can be easily solved with the help of graphical method as it is easier to deal with two dimensional graph. All the feasible solutions in graphical method lies within the feasible area on the graph and we used to test the corner points of the feasible area for the optimal solution i.e. one of the corner points of the feasible area used to be the optimal solution. We used to test all the corner points by putting these value in objective function.

But if number of variables increase from two, it becomes very difficult to solve the problem by drawing its graph as the problem becomes too complex. Simplex method was developed by G.B. Dantzig, an American mathematician.

This method is mathematical treatment of the graphical method. Here also various corner points of the feasible area are tested for optimality. But it is not possible to test all the corner points since number of corner points increase manifolds as the number of equations and variables increases. Maximum number of these points to be tested could be

m + nm = m+1!/ m! n!

where m is number of and n is number of variables.

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. Let us take one example and proceed step by step.

Objective function is to maximize Z= 12x1 + 15x2 + 14x3

Subject to conditions

Step 1:

(a) Right hand side of all the constraints must be either zero or +ve. If they are -ve then they must be made +ve by multiplying both side by (-1) and sign of inequality would be reversed. In this example, R.H.S. is already +ve or zero.

(b) All the inequalities are converted into equalities by adding or subtracting slack or surplus variables. These slack or surplus variables are introduced because it is easier to deal with equalities than inequalities in mathematical treatment.

If constraint is ≤ type the slack variables are added if constraint is ≥ type then surplus variable is subtracted. Here slack variables s,, s2 and s3 are added in three in equalities (i), (ii) and (iii), we get.

And objective function becomes

Maximize Z = 12x1 + 15x2 + 14x3 + os1 + os2 + os3

Step 2:

Find initial Basic Feasible Solution:

We start with a feasible solution and then move towards optimal solution in next iterations. Initial feasible solution is preferably chosen to be the origin i.e. where the regular variables e.g. in this case xv x2, x3 assume zero values. i.e. x1 x2, x3 = 0

and we get s1 = 0, s2 = 0 and s3 = 100 from inequalities (i), (ii) and (iii)

Basic Variables are the variables which are presently in the solution e.g., Sv S2 and S3 are the basic variables in the initial solution.

Non Basic Variables are the variables which are set equal to zero and are not in the current solution e.g. x1 and x2 and x3 are the non basic variables in the initial solution.

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.

First column represents coefficients of basic variables (current solution variables) in the objective (ei) second column represent basic variables (current solution variables) and last column represents, right hand side of the constraints in standard form. I.e. after congesting all the inequalities into equalities, in any table, current values of the current solution variables (basic variables) is given by R.H.S.

In Table 1, current solution is:

S1 =0, S2 = 0, S3 = 100

Of course the non basic variables Xv X2 and X3 will also be zero

Degeneracy whenever any basic variable assumes zero values, the current solution is said to be degenerate as in present problem S1 = 0 and S2 = 0 the problem can be further solved by substituting S1 = t and S2 = t where t is very small +ve number.

Step 3:

Optimality Test.

Optimality test can be performed to find whether current solution is optimal or not. For this first write last row in the form of (Ej) where

Ej = Σei. Aij.

Where aij represents coefficients in the body identity matrix for ith row & jth column, i.e., represents first column of the table. In the last row, write the value of (Cj – Ej) where c; represents the values of first row and Ej represents the values of last row. (Cj – Ej) represents the advantage of bringing any non basic variable to the current solution i.e. by making it basic.

In the Table 2, values of Cj – Ej are 12, 15 and 14 for Xv X2 and X3. 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. In present case X2 is the potential variable to come into the solution for next iteration. If all the values in (Cj – Ej) row are negative then it means that optimal solution has been reached.

Step 4:

Iterate towards Optimal solution:

Maximum the value of Cj – Ej gives Key coloumn as marked in the Table

Therefore X2 is the entering variable i.e. it would become basic and would enter the solution. Out of the existing non basic variable, and one has to go out and become non basic. To find which variable is to be driven out, me divide the coefficients in RHS column by the corresponding coefficients in the key column to get Ratio Column. Now look for the least positive value in the Ratio Column and that would give the key row. In present problem we have three values i.e. t, µ and 100 and out of these, t is the least +ve. Therefore Row corresponding to t in Ratio column would be the key row. And S., would be the leaving variable. Element at the intersection of key row and key coloumn is the key element.

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. 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

X1 = 0, X2 = t and X3 = 0 there by z = 15t

In new table s1 has been replaced by X2 in the basic variables and correspondingly ei coloumn has also been changed.

Step 5:

On looking at Cj -Ej values in Table 3, we find that x1 has most +ve values of 27 thereby indicating that solution can be further improved by bringing x1 into the solution i.e. by making it basic. Therefore x1 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. Then by adding suitable multiples of that row in another rows we get table 6.

It can be seen from table 6 that still solution is not optimal as Cj-Ej has still are +ve values is 1/2 this gives is key coloumn and corresponding key row is found, key element is made as given in Table 7

Now by suitable row operations we make other elements in key coloumn is zero as shown in Table 8.

It can be seen that since all the values in Cj-Ej row are either -ve or zero optimal solution has been reached.

Final solution is    x1 = 40 tons

x2 = 40 tons

x3 = 20 tons

since t is very small, it is neglected.

Example 1:

Solve the following problem by simplex method

Maximize    Z = 5x1 + 4x2

Subject to    6x1 + 4x2 ≤ 24

x1 + 2x2 ≤ 6

-x1 + x2 ≤ 1

x2 ≤ 2

and x1 x2≥0

Solution:

Add slack variables S1, S2, S3, S4 in the four constraints to remove inequalities.

We get    6x1 + 4x2 + s1 =24

x1 + 2x2+ s2 =6

-x1 + x2 + s3 = 1

x2 + s4 =2

Subject to x1, x2, s1, s2, s3 & s4 > 0

Objective function becomes

Maximize Z = 5x1 + 4x2 0s1 + 0s2 + 0s3 + 0s4

Table 1 which is formed is given below. It can be seen that X1 is the entering variable and S, is the leaving variable. Key element in Table 1 is made unity and all other element in that coloumn are made zero.

It can be from Table 2 that X2 is the entering variable and S2 is the leaving variable.

It can be seen from Table 5 that all the values of Cj-Ej row are either -ve or zero. Therefore optimal solution has been obtained.

Solution is x1 = 3, x2 = 3/2

Zmax = 5x3 + 4x = 3/2

= 15 + 6 = 21 Ans.

Big M- Method

Let us take following problem to illustrate the Big M- Method.

Minimize Z = 2y1 + 3y2

subject to constraints y1 + y2 ≥ 5

y1 + 2y2 ≥ 6

y1, y2 ≥ 0

Converting to Standard form:

Maximize Z = -2y1 – 3y2 + Os, + 0s2

i.e. Minimization problem is converted to maximization problem by multiplying R.H.S. of objective function by -1.

Constraints y1 + y2 – s1 =6 …(i)

y, + y2 – s2 =6 …(ii)

y1 y2, s1 s2 ≥ 0

Here surplus variables s1, s2 and subtracted from the constraints (i) and (ii) respectively.

Now y1, y2 can taken as non basic variables and put equal to zero to get sv s2 as basic variables where s1 = -5, s2 = -6.

This is infeasible solution as surplus variables s1 and s2 have get -ve values. In order to overcome this problem we add artificial variables A1, and A2 in eqn. (i) and (ii) respectively to get

y1 + y2 –s1 + A1 =5 …(iii)

y1 + 2y2– s2+ A2 =6 …(iv)

Where y1 y2, s1, s2, A1, A2 ≥ 0

and objective function becomes

Maximize Z1 = -2y1 – 3y2 + 0s1 + 0s2 – MA1 – MA2

It can be observed that we have deliberately applied very heavy penalties to artificial variables in the objective function in the form of -MA1 and MAwhere M is a very large +ve number. Purpose for it is that the artificial variables initially appear in the starting basic solution.

Because artificial variables decrease the objective function to very large extent be case of penalties, simplex algorithm drives the artificial variables out of the solution in the initial iterations and therefore the artificial variables which we introduced to solve the problem further don’t appear in the final solution. Artificial variables are only a computational device. They keep the starting equations in balance and provide a mathematical trick for getting a starting solution.

Initial Table becomes

Since Cj-Ej is +ve under some columns, solution given by Table 1 is not optimal. It can be seen that out of -2 + 2M and -3 + 3M, -3 + 3M is most +ve as M is a very large +ve number. Key element is found as shown in table 1 and it is made unity and all other elements in this column are made zero. We get Table 2.

From Table 2, it can be seen that optimal solution is still not reached and better solution exists. Y1 is the incoming variable and A1 is the outgoing variable. We get Table 3.

It can be seen from Table 3 that optimal solution has reached and solution is

Y1 = 4, Y2 = 1

Minimum Value of Z = 2x4 + 3x1 = 11 units Ans.

Unbounded Solution:

A Linear Programming Problem is said to have unbounded solution when in the ratio column, we get all entries either -ve or zero and there is no +ve entry. This indicates that the value of incoming variable selected from key coloumn can be as large as we like without violating the feasible condition and the problem is said to have unbounded solution.

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. It shows that optimal value has reached. 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.

Example of this type of table is given below.

It can be seen that optimal solution has been reached since all values in Cj-Ej row are zero or -ve But X1 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.

Case of No. Feasible Solution:

In some L.P.P. it can be seen that while solving problem with artificial variables, Cj-Ej row shows that optimal solution is reached whereas we still have artificial variable in the current solution having some +vp value. In such situations, it can be concluded that problem does not have any feasible solution at all.

Example 2:

Solution:

In order to solve the problem, artificial variables will have to be added in L.H.S. so as to get the initial basic feasible solution. Let us introduce artificial variables A1, A2, A3, the above constraints can be written as.

Now if these artificial variables appear in final solution by having some +ve values then the equality of equation either (i), (ii) or (iii) gets disturbed. Therefore we want that artificial variables should not appear in final solution and therefore we apply large penalty in the objective function, which can be written as.

Maximize Z = Y, + 2Y2 + 3Y3 – Y4 – MA, – MA2 – MA3

Now if we take y1 Y2, y3and y4 as non basic variables and put Y1 = Y2 = y4= 0 then we get initial solution as A1 = 15, A2 = 20 & A3 = 10 and A1, A2, A3 and A4 are basic variables (variables in current solution)to start with. The above information can be put in Table 1.

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. Optimal values are

Y1 = 5/2, Y2 = 5/2, Y3 = 5/2, Y4 = 0

Also A1 = A2 = 0 and Zmax = 15 Ans.