Logic of how the simplex method works

(The following article does not explain the procedure of simplex, but only explains the logic of how the simplex method works for those who are already familiar with the procedure.)

Dantzig’s Simplex algorithm (or simplex method) is a popular algorithm for linear programming.

We are all familiar with solving a linear programming problem (LPP) with the help of a graph. The number of variables in the equation determines the number of dimensions in the graph. So if the equation has two variables (x,y) we plot a two dimensional graph with x & y axis.

But what if the problem has 3 or more variables? We cannot draw a 3 or 4 dimensional graph to solve it. (the 4^th dimension is in fact beyond our imagination). This is where the Simplex algorithm comes into the picture.

The simplex method is an algebraic procedure. However, its underlying concepts are geometric. The logic behind the simplex method is same as the logic with which we work out graphical solution for the LPP. In fact it eliminates some of the steps in the graphical method so that we reach at the optimum solution faster.

In order to understand the logic of the simplex method, we need to be thorough with the logic of the graphical method. 

Illustration:

LPP Ltd produces two products X and Y.

·                     Material Constraint – Each unit of X consumes 3 kgs of raw material and each unit of Y consumes 2 kgs of material. Material availability is limited to 18 kgs.

·                     Sales constraint – Maximum number units of X that can be sold is 4 and Maximum number units of Y that can be sold is 6.

·                     Profit – Each unit of X gives a profit of 3 Rs and each unit of Y gives a profit of 5 Rs.

Find out how many units of X & Y should be produced in order to maximize profits.

Solution:

Let ‘x’ & ‘y’ be the number of units of X & Y produced. The LPP would be as follows:

Maximize – Z = 3x + 5y (Profit)

Subject to:

·      3x + 2y ≤ 18 (Material constraint)

·      x ≤ 4 (Sales constraint)

·      y ≤ 6 (Sales constraint)

In the above graph, the shaded region is the feasible region. This means that every point in this shaded region satisfies all the given constraints. So we have an infinite number of possible solutions. However all cannot be optimum solutions. The optimum solution has to be one of the corner points of the feasible region.

Consider the point (1,0) in the graph. It falls within the feasible region. This means if we were to produce 1 unit of X and 0 unit of Y, it would satisfy all the constraints. But when we are not producing any units of Y (i.e. keeping y=0) we can produce up to 4 units of X. Obviously producing 4 units will get more profit than producing 1 unit. So the corner-point D(4,0) will obviously be a better option than any other point on the line ED. So D is a better option than any other point on the line OD.

Similarly if we consider the point (0,3), we can conclude that it is better to produce 6 units of Y than just 3. So the point (0,3) can never be the optimum solution. Neither can any other point on the line AO. So no point other than the Feasible Corner-Point (FCP) can ever be the optimum solution. It always has to be one of the FCPs.

Now that all the other infinite possibilities are ruled out, we are just left with 5 points. When we solve it graphically, we find the value for Z (objective function) for each of these 5 points and find out which gives the highest value. This is easy only when the number of corner points is small. In simplex method, we reach the optimum solution without having to value each and every corner-point.

Simplex Method (Graphical interpretation)

In simplex method we start off with an initial solution. This initial solution has to be one of the feasible corner points. In a maximization problem, with all constraints ‘≤’ form, we know that the origin will be an FCP. That’s the reason we always start with ‘x=0’ & ‘y=0’ while solving Simplex. We can also start with (4,3) if we want to, but to know that (4,3) is an FCP we might have to draw a graph, which will be nothing but a waste of time.

So we always start with the origin 0. Now we examine whether it’s better to move up along the Y axis or move left along the X axis. For this we check the rate of increase in the profit (objective function) for a unit increase in X & Y. Increasing X by one unit gives me a profit of only 3 Rs, but increasing Y can give me 5Rs. So it’s obviously better to increase Y.

Now that I have chosen to increase Y, the next question is – How much can I increase Y? I can increase Y only to the extent of 6 units. Because if I increase to more than that, I would be going out of the feasible region.

So I stop at the point A (0,6). Now again I look on both the sides of point A (i.e. each point has two adjacent points. In case of A it is O & B). Is it better to go towards O or towards B? We just came from O. So we just need to examine whether moving towards B (increasing the value of x) increases our profit or not. It does. So we take the route and stop at B. Again we examine the adjacent points. Now we will find that if we move towards C, our profits will reduce. So we stop there. And B would be the optimum solution., as moving towards either side will only decrease our profits.

So basically we always start off with the origin, examine the adjacent points as to moving along which line increases the objective function at a higher rate and move along that line till we reach an FCP. Once we reach there, we repeat the same process of examining the adjacent points, and move along that line which gives higher benefit. This process continues until we reach a point where moving further along any of the lines will reduce the objective function and this point will essentially be the optimum solution.

How to interpret the matrix:

In the following illustration, a detailed explanation of the different terms in the simplex table, their meaning and what they represent is given. How we move along from one point to another (as explained in the previous paragraph) to reach the optimum solution will be explained clearly.

Illustration:

D company produces two products X and Y. The requirements and constrains with regard to its production is given below.

Product X	Product Y
Material – 8 units Labour – 6 hrs Machine hours - 4 Contribution - 14	Material – 4 units Labour – 8 hrs Machine hours - 6 Contribution - 16

During the forthcoming accounting period the availability of labour hrs will be restricted to 2880 hrs. Material availability is limited to 3440 units. The machine has the capacity to run for  2760 hrs. The marketing manager expects the maximum sales potential for X is 420 units with respect to Product Y there is no sales Limitations.

Formulate an LPP and find the optimum number of units to be produced.

Solution:

The LPP is as follows:

Maximize C = 14x+16y subject to

8x + 4y ≤ 3440  ( Material constraint)

6x + 8y ≤ 2880  ( Labour constraint)

4x + 6y ≤ 2760 ( Machine hour constraint)

x ≤ 420 (Sales constraint)

When we convert these into equalities the equations become:

8x + 4y + S₁ = 3440 

6x + 8y + S₂ = 2880 

4x + 6y + S₃ = 2760

x + S₄ = 420

Slack variables:

S₁, S₂, S₃ and S₄ are called slack variables. Slack variables represent the unused amount of resources. Here S₁ represents unused amount of raw-materials, S₂ - unused labour hours, S₃ – unused machine hours and S₄ represents unutilized sales potential.

Suppose we consider a situation when we are producing only 1 unit of x & y each, we would be consuming 12 (i.e. 8+4) units of material. So, out of the 3440 units of material available, after the consumption of 12 units 3428 units will remain unutilized. This is the material slack. This can be found out by substituting x=1 & y=1 in the material constraint equation and solving for S₁.

Material constraint - 8x + 4y + S₁ = 3440

 = 8(1) + 4(1) + S₁ = 3440 (substituting x=1, y=1)

 = 12 + S₁ = 3440

 = S₁ = 3428

 S₁ is material slack, so it gives the unutilized amount of material for the given situation (1,1). Similarly substituting the values for a given situation in the other equations will tell us how much of those resources remain unutilized.

Contents of the table:

C_j:

The first row is the C_j row. It tells us how much profit we can get by increasing the value of the variables by 1 unit. [Refer Table 1].We have 14 written on top of x. This means 1unit of X will fetch us 14 Rs profit. Similarly, 1unit of Y will fetch us 16 Rs profit. However the slack variables can never fetch any profit, hence their values are 0 each.

Iteration Table 1:

Each table explains the situation under a given circumstance. As already explained, we always start with the origin in the simplex procedure. So the first table examines the situation at the origin (i.e. x=0 & y =0). In other words it examines the situation when we are not producing anything.

(In the second column, we can find only the values S₁, S₂, S₃ and S₄. X & Y are missing. This means that x & y are zero.

Iteration Table 1:

  

Solution:

The values in the ‘Solution’ column (3440, 2880 …) are the values of the variables in the second column (S₁, S₂, S₃ and S₄). So we have to read the table as S₁=3440, S₂ = 2880, etc. This is nothing but the slack when we are producing nothing. (Remember the given situation for the first table is (0,0). (If we are not producing anything, the entire 3440 units of materials remain unutilized. That’s why S₁= 3440)

Columns x, y, S₁, S₂, S₃ and S₄:

The values under these columns tell us the impact of the respective variables on the values in the solution column (keeping other variables constant). In other words it tells how many units of each of the resources will be consumed by each of the products.

Under Column x – Row S₁­, we have the number 8. This means – if we increase the value of x by 1, the value of S₁ will come down by 8. (Each unit of X consumes 8 units of raw materials. So if we produce one unit of X, our material slack reduces by 8).

In the same row under Column y, we have the number 4. This means each unit of y will decrease the value of S₁ by 4.

Similarly, Column y – Row S₃ says 6. This means each unit of y will reduce the value of S₃ (machine hours slack) by 6 units from the current value of 2760.

Column S₃ – Row S₄ says 0. This is because S₃ does not have any impact on the value of S₄.

(In the first table we are assuming x & y as zero. Hence we need to see only the columns under x & y. The remaining columns will be zeros and ones. So we can ignore them.)

Column C_B

It indicates how much profit each variable in the second column earns. S₁, S₂, S₃ and S₄ do not fetch any profit. Hence they are all zeros.

Row Z_j:

This indicates how much profit is lost if we increase the values of x, y, S₁, S₂, S₃ and S₄. As of now we do not lose any profit with the increase of these variables. Hence they are all zeros.

Row C_j- Z_j:

This gives the effective increase in profits when we increase the values of the variables by 1.

C_j tells us how much additional profit we can get. Z_j tell us how much we lose. So C_j – Z_j gives the net increase/decrease.

Each unit of x gives 14 profit (C_j ) and what we lose is 0(Z_j). Therefore the net effect is an increase in the profit by 14. But if we produce y we can get an additional profit of 16. So obviously we would choose to produce Y instead of X.

(Graphically this can be interpreted as – we choose to move along the Y axis instead of the X axis, as the rate of change is higher while moving towards A)

This is the reason why we choose the highest positive value among the C_j- Z_j values and mark them.

Ratio:

Now that we choose to produce Y, the question is - how many units of y can we produce?

Each of the constraints is a limiting factor that restricts the production of the units. So we check, with the remaining units of each of the resources, how many units of y we can produce. We have 3440 units of materials. Each unit of y takes 4 units. So we can produce 3440/4=860units.

Labour – we have 2880 hrs left. Each unit of y takes 8. So we can produce 2880/8=360units.

So we divide the solution column (which tells how much units are left) with the y column (which tells how many units are consumed) to know the ratio (i.e. how many units can be produced).

The material constraint allows us to produce 860units. But the labour constraints restricts us to just 360units. So the defining constraint would be the one with the lowest ratio. That is the reason why we choose the minimum positive ratio.

The sales constraint does not restrict the production of Y. Hence the ratio is ∞. So ratio indicates the maximum units that can be produced keeping in mind the particular constraint. The least ratio indicates the maximum qty that can be produced.

(Graphical interpretation – the ratio indicates the maximum distance we can go along the chosen line yet stay within the feasible region. It indicates that we cannot go beyond the point A)

For all further calculations, the labour constraint is what matters the most, as it has been completely used up. The other resources however are still available in plenty. Hence we circle that row and take that as the point of reference for the next table.

Iteration Table 2:

Now we have decided to produce 360units of Y. The second table examines the situation when x=0 & y=360. Since all available units of labour is used up, the labour slack (S₂) is zero. So in this table, in the second column, Y replaces S₂.

Iteration Table 2:

Solution:

When 360 units of Y are produced, it consumes 360*4=1440 units of material. So out of 3440 only 2000 (i.e. 3440-1440) will be left. So the material slack for the given situation is 2000. Hence the table reads S₁ = 2000. Similarly S3=600 & S4=420.

Columns x, y, S₁, S₂, S₃ and S₄:

The intersection in the first table is at 8. We divide the whole row by 8 and this forms the second row in the second table. This row is called the main row.

If we have to increase the value of any other variable, say you want to produce some units of x, you can do it only if you forego the production of some units of Y. And how many units of Y need to be foregone depends on the units of labour consumed by X & Y, as labour is completely exhausted.

1 unit of X requires 6 units of labour. One units of Y requires 8 units. So X consumes 3/4^th the labour that Y consumes. So, to produce 1units of X we need to forego the production of 3/4^th unit of Y. We can say that 1 unit of X is equivalent of  ¾ unit of Y. This is what is given in the main row.

The main row gives the equivalent value of all other variables in terms of 1 unit of Y. 

Main row: If we increase the value of X by 1, Y will come down by ¾. If we increase the value of S2 by 1, the value of Y will come down by 1/8.

Row S₁: If we increase the value of X by 1, S₁ will come down by 5^#. If we increase the value of S2 by 1, the value of S₁ will go up by 1/2^##. (Positive values indicate consumption/decrease in value. Negative values indicate increase in value)

Note:

^# - To produce one unit of X, we will have to forego the production of 3/4^th unit of Y. When we forego this, we will get back 3 units (3/4^th of 4) of material. But to produce one unit of x we consume 8 units. Thus the net effect is an additional consumption of 8-3=5 units in the materials.

^##Similarly if we were to increase the value of S₂ by 1, we need to decrease Y by 1/8^th. When we do this we get 4*1/8=1/2 units of material back. But increasing S2 does not consume any material. So the net effect is an increase in the materials by ½ units which is indicated by -1/2 in the table.

Row S₃: The values in the row S₃ are the net effect on the solution values, after considering the decreasing in the value of Y, which is now required to increase any other variable.

Column C_B

It indicates how much profit each variable in the second column earns. S₁, S₃ and S₄ do not fetch any profit. Hence they are all zeros. But Y fetches a profit of Rs. 16.

 Row Z_j:

This indicates how much profit is lost if we increase the values of x, y, S₁, S₂, S₃ and S₄.

If we increase X, we will be foregoing 3/4^th unit of Y. Along with this we will also be foregoing the profit from 3/4^th unit of Y. That is ¾*16=12. So 12 is the opportunity cost of producing one unit of X. (Opportunity cost - The profit/opportunity foregone while making another choice)

Increasing one unit of Y is possible only if we decrease another unit of Y. So we will lose 16. (Column X & S₂ only needs to be considered. Others can be ignored). Increasing one unit of S₂ will lead to loss of profit to the extent of 1/8*16=2.

Row C_j- Z_j:

Each unit of x gives 14 profit (C_j ) and what we lose(opportunity cost) is 12(Z_j). Therefore the net effect is an increase in the profit by 2. Each unit of S₂ gives 0profit (C_j ) and what we lose is 2(Z_j). Therefore the net effect is a decrease in the profit by 2. So we choose the value with the highest positive integer - X.

(On producing Y you get 16, at the same time on foregoing you lose 16. So the net effect is 0.)

Ratio:

Now again the question is - how many units of  X can we produce?

We check how many units of  X we can produce before one of the resources run out. We have 2000 units of materials. Each unit of X will consume an additional 5 units. So we can produce 2000/5=400units.

The sales constraint allows us to produce 420 units. But the labour material constraint restricts us to just 400 units. So now the defining constraint would be the material constraint (negative values to be ignore)

(Graphical interpretation – the ratio indicates that we wil have to stop at the point B)

For the next table the material constraint is what matters, as it will be completely used up. The other resources, (excluding labour) are now available. Hence we circle that row and take that as the point of reference.

Final Matrix (Table 3):

Now we are producing 400 units of X and 60 units of Y (to produce X we had to decrease the production of Y). This table examines the situation when x=400 & y=60. Since all available units of material are used up, the material slack (S₁) is zero. So, in this table in the first column, X replaces S₁. We do not find S₁ & S₂ in the second row, indicating that they have been completely utilized.

In every table two variables will take be assigned zero as the value. These are called non-basic variables as they do not appear in the basic solution. So the variables that appear in the basic solution (second column) are the ones that are not completely utilized.

Iteration Table 3:

  

Solution:

When 400 units of X and 60units of Y are produced 800 units of machine hours and 20 units of sales potential still remains unutilized. 6560 is the profit that can be made in the current decision.

Columns x, y, S₁, S₂, S₃ and S₄:

The interpretation is the same as the other table. Here we need to consider only S₁ and S₂, the rest will be just zeros and ones. Column S₁ indicates, to increase the value of S₁ by 1 unit (i.e. release 1 unit form production), we will have to forego the production of  X by 1/5 unit. And this will result in increase the production of Y by 1/7^th unit and also S₄ to increase by 1/5^th unit.

Similarly we can infer that we were to release one unit of labour (yet keep the materials at zero), we wil have to decrease the production of Y by 1/5^th unit and increase the production of X by 1/10^th unit. This will result in the increase of S₄ by 4/5^th unit.

 Row Z_j:

If we increase S₁ or S₂ we will lose profits. It is anyway quite obvious that we will lose profits if we try to increase slack.

Row C_j- Z_j:

This row has only negative values and zeros. The negative values indicate that increasing those variables will decrease the profit. Nothing can be done to increase profits further, thus indicating that we have reached the optimum solution.

(Moving to either point A or C from the current point B will only decrease the value of Z. so we decide to stay there)

So the optimum solution is to produce 400 units of x and 60 units of Y.