# Simplex Solutions of LLP

26/03/2020The **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, x_{1} and x_{2} 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:**

- 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”.
- 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 + n_{m} = 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= 12x_{1} + 15x_{2} + 14x_{3}

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,, s_{2} and s_{3} are added in three in equalities (i), (ii) and (iii), we get.

And objective function becomes

Maximize Z = 12x_{1} + 15x_{2} + 14x_{3} + os_{1} + os_{2} + os_{3}

**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 x_{v} x_{2}, x_{3} assume zero values. i.e. x_{1} x_{2}, x_{3} = 0

and we get s_{1} = 0, s_{2} = 0 and s_{3} = 100 from inequalities (i), (ii) and (iii)

Basic Variables are the variables which are presently in the solution e.g., S_{v} S_{2} and S_{3} 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. x_{1} and x_{2} and x_{3} 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 (e_{i}) 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:

S_{1} =0, S_{2} = 0, S_{3} = 100

Of course the non basic variables X_{v} X_{2} and X_{3} will also be zero

Degeneracy whenever any basic variable assumes zero values, the current solution is said to be degenerate as in present problem S_{1} = 0 and S_{2} = 0 the problem can be further solved by substituting S_{1} = t and S_{2} = 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 (E_{j}) where

Ej = Σ_{ei. }A_{ij.}

Where a_{ij} 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 E_{j} 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 X_{v} X_{2} and X_{3}. 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 X_{2} 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 X_{2} 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

X_{1} = 0, X_{2} = t and X_{3} = 0 there by z = 15t

In new table s_{1} has been replaced by X_{2} 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 x_{1} has most +ve values of 27 thereby indicating that solution can be further improved by bringing x_{1} into the solution i.e. by making it basic. Therefore x_{1} 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 x_{1} = 40 tons

x_{2} = 40 tons

x_{3} = 20 tons

since t is very small, it is neglected.

**Example 1:**

Solve the following problem by simplex method

Maximize Z = 5x_{1} + 4x_{2}

Subject to 6x_{1} + 4x_{2} ≤ 24

x_{1} + 2x_{2} ≤ 6

-x_{1} + x_{2} ≤ 1

x_{2} ≤ 2

and x_{1} x_{2}≥0

**Solution:**

Add slack variables S_{1}, S_{2}, S_{3}, S_{4} in the four constraints to remove inequalities.

We get 6x_{1} + 4x_{2} + s_{1} =24

x_{1} + 2x_{2}+ s_{2} =6

-x_{1} + x_{2} + s_{3} = 1

x_{2} + s_{4} =2

Subject to x_{1}, x_{2}, s_{1}, s_{2}, s_{3} & s_{4} > 0

Objective function becomes

Maximize Z = 5x_{1} + 4x_{2} 0s_{1} + 0s_{2} + 0s_{3} + 0s_{4}

Table 1 which is formed is given below. It can be seen that X_{1} 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 X_{2} is the entering variable and S_{2} 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 x_{1} = 3, x_{2} = 3/2

Z_{max} = 5x_{3} + 4x = 3/2

= 15 + 6 = 21 Ans.

Big M- Method

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

Minimize Z = 2y_{1} + 3y_{2}

subject to constraints y_{1} + y_{2} ≥ 5

y_{1} + 2y_{2} ≥ 6

y_{1}, y_{2} ≥ 0

Converting to Standard form:

Maximize Z = -2y_{1} – 3y_{2} + Os, + 0s_{2}

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

Constraints y_{1} + y_{2} – s_{1} =6 …(i)

y, + y_{2} – s_{2} =6 …(ii)

y_{1} y_{2}, s_{1} s_{2} ≥ 0

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

Now y_{1}, y_{2} can taken as non basic variables and put equal to zero to get s_{v} s_{2} as basic variables where s_{1} = -5, s_{2} = -6.

This is infeasible solution as surplus variables s_{1} and s_{2} have get -ve values. In order to overcome this problem we add artificial variables A_{1}, and A_{2} in eqn. (i) and (ii) respectively to get

y_{1} + y_{2} –s_{1} + A_{1} =5 …(iii)

y_{1} + 2y_{2}– s_{2}+ A_{2} =6 …(iv)

Where y_{1} y_{2}, s_{1}, s_{2}, A_{1}, A_{2} ≥ 0

and objective function becomes

Maximize Z^{1} = -2y_{1} – 3y_{2} + 0s_{1} + 0s_{2} – MA_{1} – MA_{2}

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 MA_{2 }where 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. Y_{1} is the incoming variable and A_{1} is the outgoing variable. We get Table 3.

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

Y_{1} = 4, Y_{2} = 1

Minimum Value of Z = 2x_{4} + 3x_{1} = 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 X_{1} 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 A_{1,} A_{2}, A_{3}, 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, + 2Y_{2} + 3Y_{3} – Y_{4} – MA, – MA_{2} – MA_{3}

Now if we take y_{1} Y_{2}, y_{3}and y_{4} as non basic variables and put Y_{1} = Y_{2} = y_{4}= 0 then we get initial solution as A_{1} = 15, A_{2} = 20 & A_{3} = 10 and A_{1,} A_{2}, A_{3} and A_{4} 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

Y_{1} = 5/2, Y_{2} = 5/2, Y_{3} = 5/2, Y4 = 0

Also A_{1} = A_{2} = 0 and Z_{max} = 15 Ans.

[…] VIEW […]