Simplex Solutions of LLP

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, x₁ and x₂ 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.

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.

Subject to conditions

Step 1:

(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₂ and s₃ are added in three in equalities (i), (ii) and (iii), we get.

Maximize Z = 12x₁ + 15x₂ + 14x₃ + os₁ + os₂ + os₃

Step 2:

Find initial Basic Feasible Solution:

and we get s₁ = 0, s₂ = 0 and s₃ = 100 from inequalities (i), (ii) and (iii)

Basic Variables are the variables which are presently in the solution e.g., S_v S₂ and S₃ 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₁ and x₂ and x₃ 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₁ =0, S₂ = 0, S₃ = 100

Of course the non basic variables X_v X₂ and X₃ 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₁ = 0 and S₂ = 0 the problem can be further solved by substituting S₁ = t and S₂ = t where t is very small +ve number.

Step 3:

Optimality Test.

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₂ and 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. In present case X₂ 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₂ 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₁ = 0, X₂ = t and X₃ = 0 there by z = 15t

In new table s₁ has been replaced by X₂ 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₁ has most +ve values of 27 thereby indicating that solution can be further improved by bringing x₁ into the solution i.e. by making it basic. Therefore 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. 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₁ = 40 tons

x₂ = 40 tons

x₃ = 20 tons

since t is very small, it is neglected.

Example 1:

Solve the following problem by simplex method

Maximize    Z = 5x₁ + 4x₂

Subject to    6x₁ + 4x₂ ≤ 24

x₁ + 2x₂ ≤ 6

-x₁ + x₂ ≤ 1

x₂ ≤ 2

and x₁ x₂≥0

Solution:

Add slack variables S₁, S₂, S₃, S₄ in the four constraints to remove inequalities.

We get    6x₁ + 4x₂ + s₁ =24

x₁ + 2x₂+ s₂ =6

-x₁ + x₂ + s₃ = 1

x₂ + s₄ =2

Subject to x₁, x₂, s₁, s₂, s₃ & s₄ > 0

Objective function becomes

Maximize Z = 5x₁ + 4x₂ 0s₁ + 0s₂ + 0s₃ + 0s₄

Table 1 which is formed is given below. It can be seen that X₁ 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₂ is the entering variable and S₂ 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₁ = 3, x₂ = 3/2

Z_max = 5x₃ + 4x = 3/2

= 15 + 6 = 21 Ans.

Big M- Method

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

Minimize Z = 2y₁ + 3y₂

subject to constraints y₁ + y₂ ≥ 5

y₁ + 2y₂ ≥ 6

y₁, y₂ ≥ 0

Converting to Standard form:

Maximize Z = -2y₁ – 3y₂ + Os, + 0s₂

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

Constraints y₁ + y₂ – s₁ =6 …(i)

y, + y₂ – s₂ =6 …(ii)

y₁ y₂, s₁ s₂ ≥ 0

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

Now y₁, y₂ can taken as non basic variables and put equal to zero to get s_v s₂ as basic variables where s₁ = -5, s₂ = -6.

This is infeasible solution as surplus variables s₁ and s₂ have get -ve values. In order to overcome this problem we add artificial variables A₁, and A₂ in eqn. (i) and (ii) respectively to get

y₁ + y₂ –s₁ + A₁ =5 …(iii)

y₁ + 2y₂– s₂+ A₂ =6 …(iv)

Where y₁ y₂, s₁, s₂, A₁, A₂ ≥ 0

and objective function becomes

Maximize Z¹ = -2y₁ – 3y₂ + 0s₁ + 0s₂ – MA₁ – MA₂

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₂ 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₁ is the incoming variable and A₁ is the outgoing variable. We get Table 3.

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

Y₁ = 4, Y₂ = 1

Minimum Value of Z = 2x₄ + 3x₁ = 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₁ 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₂, A₃, 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₂ + 3Y₃ – Y₄ – MA, – MA₂ – MA₃

Now if we take y₁ Y₂, y₃and y₄ as non basic variables and put Y₁ = Y₂ = y₄= 0 then we get initial solution as A₁ = 15, A₂ = 20 & A₃ = 10 and A_1, A₂, A₃ and A₄ 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₁ = 5/2, Y₂ = 5/2, Y₃ = 5/2, Y4 = 0

Also A₁ = A₂ = 0 and Z_max = 15 Ans.