Linear Programming and Maximization of Contribution Margin  Simplex
Method:
Learning Objective of
the Article:
 Define and explain linear programming simplex method.
 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 lessthanorequalto
type constraints, equalto and greaterthanorequalto 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
(tolessthanorequalto 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:
 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.
 Add the results of the products, by rows,
of the matrix
 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:
 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.
 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.
 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.
 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.
 Compute the amounts in all other rows.
In this problem new values are determined for s2 row by the following
procedure:

Old s2
row (First Tableau) 
– 
Old s2
row and y (the key) column 
× 
y row
(second tableau) 
= 
Values
of new s2 row 

80 
– 
2 
× 
24 
= 
32 

4 
– 
2 
× 
0.4 
= 
3.2 

2 
– 
2 
× 
1 
= 
0 

0 
– 
2 
× 
0.2 
= 
– 0.4 

1 
– 
2 
× 
0 
= 
1 

These computations
accomplish (1) the substitution of as much of the deluxe model as is
consistent with constraints and (2) the removal of as much s1 and s2
as in necessary to provide for the insertion of y (deluxe mode)
units into the solution. The $4 contribution margin of the deluxe
model is placed in the objective column of the y row. 
6. 
Finally compute the
index row:

Step 1 and 2 
Step 3 

24(4) + 32(0) = 96 
96  0 = 96 

0.4(4) + 3.2(0) = 1.6 
1.6  3 1.4 

1(4) + 0(0) = 4 
4  4 = 0 

0.2(4) + 0.4(0) = 0.8 
0.8  0 = 0.8 

0(4) + 1(0) = 0 
0  0 = 0 

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 lessthanorequalto type constraints, a similar interpretation can be made for equalto
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 greaterthanorequalto 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 lessthanorequalto 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:
 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.
 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.
 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.
 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.
 Compute the amounts in all other rows. The
new values of the y row are:

Old y Row (Second Tableau) 
– 
Old y Row and X (The Key) Column 
× 
X Row (Third Tableau) 
= 
Values of New y Row 

24 
– 
0.4 
× 
10 
= 
20 

0.4 
– 
0.4 
× 
1 
= 
0 

1 
– 
0.4 
× 
0 
= 
1 

0.2 
– 
0.4 
× 
0.125 
= 
0.25 

0 
– 
0.4 
× 
0.3125 
= 
0.125 
6. 
Compute the index row:
Step
1 and 2 
Step
3 
20 (4)
+ 10 (3) = 110 
110  0
= 110 
0 (4) +
1 (3) = 3 
3  3 =
0 
1 (4) +
0 (3) 
4  4 =
0 
0.25
(4) + 0.125 (3) = 0.625 
0.625 
0 = 0.625 
0.125
(4) + 0.3125 (3) = 0.4375 
0.4375
 0 = 0.4375 

Third tableau appears as follows:
Third
simplex tableau and optimal solution 

Mix 
0 
3 
4 
0 
0 
Quantity 
x 
y 
s1 
s2 
4 
y 
20 
0 
1 
0.250 
0.1250 
3 
x 
10 
1 
0 
0.125 
0.3125 


110 
0 
0 
0.625 
0.4375 
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. 