Linear Programming and Maximization of Contribution Margin – Simplex Method
Linear Programming and Maximization of Contribution Margin – Simplex Method:Learning Objective of the Article:
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 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 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:
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:
The index row for the illustration is determined as follows:
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.
Explanation and Calculation for the Second Tableau:The construction of the second tableau is accomplished through these six steps:
When these steps are completed for the contribution margin maximization illustration, the second tableau appears as follows:
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.
Explanation and Calculation for the Third Tableau:The third tableau is computed by these steps:
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 articles from “linear programming technique” chapter


Not able to see the full simplex tableau