Linear Programming and Maximization of Contribution Margin - Simplex Method:

Learning Objective of the Article:

1. Define and explain linear programming simplex method.
2. How a profit maximization problem is solved using linear programming simplex method.

Definition and Explanation of Simplex Method:

Simplex method is considered one of the basic techniques from which many linear programming techniques are directly or indirectly derived. The simplex method is an iterative, stepwise process which approaches an optimum solution in order to reach an objective function of maximization or minimization. Matrix algebra provides the deterministic working tools from which the simplex method was developed, requiring mathematical formulation in describing the problem. An example can help us explain the simplex method in detail.

Example of Linear Programming Simplex Method:

Assume that a small machine shop manufactures two models, standard and deluxe. Each standard model requires two hours of grinding and four hours of polishing; each deluxe module requires five hours of grinding and two hours of polishing. The manufacturer has three grinders and two polishers. Therefore in 40 hours week there are 120 hours of grinding capacity and 80 hours of polishing capacity. There is a contribution margin of $3 on each standard model and $4 on each deluxe model.

Before the simplex method can be applied, the following steps must be taken:

The relationship which establish the constraints or inequalities must be set up first. Letting x and y be respectively the quantity of items of the standard model and deluxe model that are to be manufactured, the system of inequalities or the set of constraints:

2x + 5y ≤ 120
4x + 2y ≤ 80

Both x and y must be positive values or zero (x ≥ 0; y ≥ 0). Although this illustration involves only less-than-or-equal-to type constraints, equal-to and greater-than-or-equal-to type constraints can be encountered in maximization problems.

The objective function is the total contribution margin the manager can obtain from the two models. A contribution margin of $3 is expected for each standard model and $4 for each deluxe model. The objective function is CM = 3x + 4y. The problem is now completely described by mathematical notation.

The first tow steps are the same for the graphic method, the simplex method requires the use of equations, in contrast to the inequalities used by the graphic method. Therefore the set of inequalities (to-less-than-or-equal-to type constraints) must be transformed into a set of equations by introducing slack variables, s1 and s2. The use of slack variables involves the addition of an arbitrary variable to one side of the inequality, transforming it into an equality. This arbitrary variable is called a slack variable, since it takes up the slack in the inequality. The inequalities rewritten as equalities are:

2x + 5y + s1 = 120
4x + 2y + s2 = 80

The unit contribution margins of the fictitious products s1 and s2 are zero, and the objective equation becomes:

Maximize: CM = 3x + 4y + 0s1 + 0s2

At this point, the simplex method can be applied and the first matrix or tableau can be set up as shown below:
 

	MIX	0	3	4	0	0	←	Objective Row
		Quantity	x	y	s1	s2	←	Variable Row
0	s1	120	2	5	1	0	]←	Problem Rows
0	s2	80	4	2	0	1
		0	-3	-4	0	0	←	Index Row
↑	↑	↑
Objective Column	Variable Column	Quantity Column

Explanation and Calculation for the First Tableau:

The simplex method records the pertinent data in a matrix form known as the simplex tableau. The components of a tableau are described in the following paragraphs.

The Objective row is made up of the notation of the variable of the problem including slack variables.

The problem rows in the first tableau contain the coefficients of the variables in the constraints. Each constraint adds an additional problem row. Variables not included in a constraints are assigned zero coefficients in the problem rows. In subsequent tableau, new problem row values will be computed.

At each iteration, the objective column receives different entries, representing the contribution margin per unit of the variable in the solution.

At each iteration, the variable column receives different notation by replacement. These notations are the variables used to find the total contribution margin of the particular iteration. In the first matrix, a situation of no production is is considered as a starting point in the iterative solution process. For this reason, only slack variables and artificial variables are entered in the objective column, and their coefficient in the objective function are recorded in the variable column. As the iterations proceed, by replacement, appropriate values and notations will be entered in the objective and variable column.

The quantity column shows the constant values of the constraints in the first tableau; in subsequent tableaus, it shows the solution mix.

The index row carries values computed by the following steps:

1. Multiply the values of the quantity column and those columns to the right of the quantity column by the corresponding value, by rows, of the objective column.
2. Add the results of the products, by rows, of the matrix
3. Subtract the values in the objective row from the result in step 2. For this operation, the objective row is assumed to have a zero value in the quantity column. The contribution margin entered in the cell in the quantity column and the index row is zero, a condition valid only for the first tableau when a situation of no production is considered. In the subsequent matrices, it will be a positive value, denoting the total contribution margin represented by the particular matrix.

The index row for the illustration is determined as follows:
 

Step 1 and 2	Step 3
120(0) + 80(0) = 0	0 – 0 = 0
2(0) + 4(0) = 0	0 – 3 = –3
5(0) + 2(0) = 0	0 – 4 = –4
1(0) + 0(0) = 0	0 – 0 = 0
0(0) + 1(0) = 0	0 – 0 = 0

In this first tableau, the slack variables were introduced into the product mix variable column to find and initial feasible solution to the problem. It can be proven mathematically that beginning with positive slack and artificial variables assures a feasible solution. Hence, one feasible solution might have s1 take a value of 120 and s2 a value of 80. This approach satisfies the constraints but is undesirable since the resulting contribution margin is zero.

It is a rule of the simplex method that the optimum solution has not been reached if the index row carries any negative values at the completion of an iteration. Consequently, this first tableau does not carry the optimum solution since negative values appear in its index row. A second tableau or matrix must now be prepared, step by step, according to the rules of simplex method.
 

First simplex tableau		Mix	0	3	4	0	0
			Quantity	x	y	s1	s2
	0	s1	120	2	5	1	0
	0	s2	80	4	2	0	1
			0	-3	-4	0	0

Explanation and Calculation for the Second Tableau:

The construction of the second tableau is accomplished through these six steps:

1. Select the key column, the one which has the negative number with the highest absolute value in the index row, i.e., that variable whose value will most increase the contribution margin. In the first tableau, the key column is the one formed by the values: 5, 2, and -4.
2. Select the key row, the row to be replaced. The key row is the one which contains the smallest positive ratio obtained by dividing the positive number in the problem rows of the key column into the corresponding values, by rows, of the quantity column. The smallest positive ratio identifies the equation which operates as the limiting constraint. In the first tableau, the ratios are 120 / 5 = 24 and 80 / 2 = 40. Since 120 / 5 is the smaller of the two positive ratios, the key row is s1—120, 2, 5,1, and 0.
3. Select the key number, which is the value found in the crossing cell of the key column and the key row. In the example, the key number is 5.
4. Compute the main row, which is computed series of new values replacing the key row of the preceding tableau (in this case the first tableau). The main row is determined by dividing each amount in Row s1 (the row being replaced) of the preceding tableau by the key number; 120 / 5 = 24; 2 /5 = 0.4; 5 / 5 = 1; 1 / 5 = 0.2; 0 / 5 = 0. In the second tableau, these are the figures in the Row y, which replaces Row s1.
5. Compute the amounts in all other rows. In this problem new values are determined for s2 row by the following procedure:

When these steps are completed for the contribution margin maximization illustration, the second tableau appears as follows:

Second simplex tableau and second solution				Mix	0	3	4	0	0
	This row has been replaced because 24 was the smallest positive ratio computed in step 2.				Quantity	x	y	s1	s2
		→	4	y	24	0.4	1	0.2	0	←	Main row
			0	s2	32	3.2	0	-0.4	1
					96	-1.4	0	0.8	0

This second matrix does not contain the optimum solution since a negative figure, -1.4, still remains in the index row. The contribution margin arising from this model mix is $96 [4(24) + 0(32)], which is an improvement. However, the second solution indicates that some standard models and $1.40 (or 7 / 5 dollars of contribution margin) can be added for each unit of the standard model substituted in this solution.

It is interesting to reflect on the significance of - 7 / 5 or - 1.4. The original statement of the problem had promised a unit contribution margin of $3 for the standard model. Now the contribution will increase by only $1.40 per unit. The significance of the -1.4 is that it measures the net increase of the per unit contribution margin after allowing for the reduction of the deluxe model represented by y units. That is, all the grinding hours have been committed to produce 24 deluxe models (24 units × 5 hours grinding time per unit = 120 hours capacity); the standard model cannot be made without sacrificing the deluxe model. The standard model requires 2 hours of grinding time; the deluxe model requires 5 hours of grinding time. To introduce one standard model unit into the product mix, the manufacture of 2 / 5 (0.4) of one deluxe model unit must be foregone. This figure, 0.4, appears in the column headed "x" on the row representing foregone variable (deluxe) models. If more non slack variables (i.e., more than two products) were involved , the figures for these variables, appearing in column x, would have the same meaning as 0.4 has for the deluxe models.

Thus, the manufacturer loses 2 / 5 of $4, or $1.60, by making 2 / 5 less deluxe models but gains $3 from the additional standard models. A loss of $1.60 and a gain of $3 results in a net improvement of $1.40. The final answer, calculated on graphical method page, adds $14 (10 standard models × 1.4) to the $96 contribution margin that results from producing 10 standard models (10 × $3 = $30) and (20 × $4 = $80). In summary, the -1.4 in the second tableau indicates the amount of increase possible in the contribution margin if one unit of the variable heading that column (x in this case) were added to the solution; and the 0.4 value in column x represents the production of the deluxe model that must be relinquished.

The quantity column was described for the first tableau as showing the constant values of the constraints, i.e., the maximum resources available (grinding and polishing hours in the illustration) for the manufacture of standard and deluxe models. In subsequent tableaus the quantity column shows the solution mix. Additionally, for a particular iteration in subsequent tableau, the quantity column shows the constraints that are utilized in an amount different from the constraints constant value. For example, in the second tableau's quantity column, the number corresponding to the y variable denotes the number of y units in the solution mix (24), and its objective function coefficient of $4 when multiplied by 24 yields $96,  the value of the solution at this iteration. The number corresponding to the s2 variable denotes the difference in total polishing hours and those used in the second tableau solution, i.e., 80 hours of available polishing hours less polishing hours used to produce 24 units of y (24 × 2), or 80 – 48 = 32. Thus the number of unused polishing hours is 32. No unused grinding hours, the s1 variable, are indicated because 24 units of y utilized the entire quantity of available grinding time (24 × 5 = 120 hours).

While this illustration is of less-than-or-equal-to type constraints, a similar interpretation can be made for equal-to type constraints; i.e., the quantity column denotes the difference in the constant value of the constraint and the value used in the tableau's solution mix. For the greater-than-or-equal-to constraint, the quantity column denotes the amount beyond the constraint's minimum requirement that is satisfied by the particular solution mix.

These constraint utilization of satisfaction differences provide useful information, especially in the optimal solution tableau, because management may wish to make decisions to reduce these differences, e.g., by plans to utilize presently unused capacity associated with less-than-or-equal-to constraints.
 

Second simplex tableau		Mix	0	3	4	0	0
			Quantity	x	y	s1	s2
	4	y	24	0.4	1	0.2	0
	0	s2	32	3.2	0	-0.4	1
			96	-1.4	0	0.8	0

Explanation and Calculation for the Third Tableau:

The third tableau is computed by these steps:

1. Select the key column. This is the column which has the negative number with the highest absolute value in the index row. In the second tableau, the key column is formed by the values 0.4, 3.2, and -1.4.
2. Select the key row, s2, the row to be replaced by x, which is determined as follows:
   from the second tableau, for the x row, 24 / 0.4 = 60; for the s2 row, 32 / 3.2 = 10. Since 10 is the smaller positive ratio and comes from the s2 row, s2 should be replaced by x.
3. Select the key number, which is the value (3.2) located in the corresponding cell of the key column and the key row of the preceding (second) tableau.
4. Compute the main row. The new x row (old s2 row) figures are determined by dividing each amount in row s2 of the second tableau by the amount in the x column in row s2, the key number. The results are: 32 / 3.2 = 10; 3.2 / 3.2 = 1; 0 / 3.2 = 0; -0.4 / 3.2 = -0.125; 1 / 3.2 = 0.3125.
5. Compute the amounts in all other rows. The new values of the y row are:

Third tableau appears as follows:

There are no negative figures in the index row, which indicates that any further substitutions will not result in an increase in the contribution margin; the optimum solution has been obtained. The optimum strategy is to produce and sell 20 deluxe and 10 standard models for a contribution margin of $110.

 

You may also be interested in other relevant articles: Linear Programming-Maximization of Contribution Margin-Graphical Method Linear Programming-Maximization of Contribution Margin-Simplex Method Linear Programming-Minimization of Cost-Graphical Method Linear Programming-Minimization of Cost-Simplex Method Shadow Prices Dynamic Programming Linear Programming Techniques-General Observations Linear Programming Questions and Answers Linear Programming Problems, Graphical and Simplex Method

 

Dear visitor! Do you like this article? If you like, then please bookmark this page and also share with your friends. Thank you for your support.   [Report Errors and Omissions]

Back to Home Page | Linear Programming Technique