THE PRINCIPLES OF THE SIMPLEX METHOD
The simplex method is a method of solving linear programming problems with two or more decision variables.
The formulation of the problem using the simplex method is similar to that required when the graphical method is used but slack variables must be incorporated into the constraints and the objective function.
General points about the simplex method
A slack variable represents the amount of a constraint that is unused.
In any feasible solution, if a problem involves n constraints and m variables (decision plus slack), n variables will have a positive value and (m–n) variables will have a value of zero.
Feasible solutions to a problem are shown in a table.
Before introducing an example to explain the technique, we will make a few introductory points. Don’t worry if you get confused, working through the example will make things clearer.
- The simplex method involves testing one feasible solution after another, in a succession of tables, until the optimal solution is found. It can be used for problems with any number of decision variables, from two upwards.
- In addition to the decision variables, the method introduces additional variables, known as slack variables or surplus variables. There will be one slack (or surplus) variable for each constraint in the problem (excluding non-negativity constraints).
For example, if a linear programming problem has three decision variables and four constraints, there will be four slack variables. With the three decision variables, there will therefore be a total of seven variables and four constraints in the problem.
- The technique is iterative (a repetitive, step-by-step process), with each iteration (step) having the following purposes.
- To establish a feasible solution (in other words, a feasible combination of decision variable values and slack variable values) and the value of the objective function for that solution.
- To establish whether that particular solution is one that optimises the value of the objective function.
- Each feasible solution is tested by drawing up a matrixwith the following rows and columns.
- One row per constraint, plus a solution row
- One column per decision variable and per slack variable, plus a solution column
- Every variable, whether a decision variable, slack variable or surplus variable, must be ≥ 0 in any feasible solution.
- A feature of the simplex method is that if there are n constraints, there will be n variables with a value greater than 0 in any feasible solution. Thus, if there are seven variables in a problem, and four constraints, there will be four variables with a positive value in the solution, and three variables with a value equal to 0.
Formulating the problem
We have just two decision variables in this problem, but we can still use the simplex method to solve it.
| Step 1 | Define variables
Let x be the number of units of X that should be produced and sold. |
|
|
Let y be the number of units of Y that should be produced and sold. |
| Step 2
|
Establish objective function
Maximum contribution (C) = 20x + 16y subject to the constraints below. |
| Step 3 | Establish constraints
The constraints are as follows. |
| Materials 5x + 2y ≤ 3,000 Machine time 3x + 2y ≤ 2,100 | |
|
|
Labour x + 3y ≤ 1,750 Non-negativity x ≥ 0, y ≥ 0 |
| Step 4 | Introduce slack variables
Begin by turning each constraint (ignoring the non-negativity constraints now) into an equation. This is done by introducing slack variables. |
| Let a be the quantity of unused materials, b be the number of unused labour hours and c be the number of unused machine hours. |
Slack variable. ‘Amount of each resource which will be unused if a specific linear programming solution is implemented.’
Drawing up the initial table and testing the initial feasible solution
You will not be required to do this in the exam but seeing how the initial table is drawn up will give you additional insight into the technique.
We begin by testing a solution that all the decision variables have a zero value, and all the slack variables have a non-negative value.
Obviously, this is not going to be the optimum solution, but it gives us a starting point from which we can develop other feasible solutions.
Simplex tables can be drawn in several different ways, and if you are asked to interpret a given table in an examination question, you may need to adapt your understanding of the table format in this Study Text to the format in the question. The following points apply to all tables, however.
- There should be a column for each variable and also a solution column.
- It helps to add a further column on the left, to indicate the variable which is in the solution to which the corresponding value in the solution column relates.
- There is a row for each equation in the problem, and a solution row.
- The figures in each row correspond with the coefficients of the variables in each of the initial constraints. The bottom row or solution row holds the coefficients of the objective function. For example the materials constraint 5x + 2y + a = 3,000 gives us the first row, 5 (number of x’s), 2 (number of y’s), 1 (number of a’s), then zeros in the b and c columns (since these do not feature in the constraint equation) and finally 3,000 in the solution column.
- The variables in the solution are a, b and c (the unused resources).
- The value of each variable is shown in the solution column. We are testing a solution that all decision variables have a zero value, so there is no production and hence no resources are used. The total resource available is therefore unused.
- The column values for each variable in the solution are as follows.
− 1 in the variable’s own solution row
− 0 in every other row, including the solution row.
The contribution per unit obtainable from x and y is given in the solution row. These are the dual prices or shadow prices of the products X and Y. The minus signs are of no particular significance, except that in the solution given here they have the following meanings.
-
- A minus shadow price indicates that the value of the objective function can be increased by the amount of the shadow price per unit of the variable that is introduced into the solution, given no change in the current objective function or existing constraints.
- A positive shadow price indicates the amount by which the value of the objective function would be decreased per unit of the variable introduced into the solution, given no change in the current objective function or the existing constraints.
Interpreting the table and testing for improvement
We can see that the solution is testing a = 3,000, b = 1,750 and c = 2,100, contribution = 0. The co-efficients for the variables not in this solution, x and y, are the dual prices or shadow prices of these variables, given the solution being tested. A negative value to a dual price means that the objective function can be increased; therefore the solution in the table is not the optimal solution.
The shadow prices in the initial solution (table) indicate the following.
- The profit would be increased by RWF20 for every extra unit of x produced (because the shadow price of x is RWF20 per unit).
- Similarly, the profit would be increased by RWF16 for every extra unit of y produced (because its shadow price is RWF16 per unit).
Since the solution is not optimal, the contribution may be improved by introducing either x or y into the solution.
The next step
The next step is to test another feasible solution. We do this by introducing one variable into the solution, in the place of one variable that is now removed. In our example, we introduce x or y in place of a, b or c.
The simplex technique continues in this way, producing a feasible solution in each successive table, until the optimal solution is reached
Interpreting the final table
If the shadow prices on the bottom (solution) row of a table are all positive, the table shows the optimal solution.
- The solution column shows the optimal production levels and the units of unused resource.
- The figure at the bottom of the solution column/right-hand side of the solution row shows the value of the objective function.
- The figures in the solution row indicate the shadow prices of resources.
SENSITIVITY ANALYSIS
You might be asked to carry out some sensitivity analysis on a simplex matrix giving the optimal solution to a linear programming problem. This could involve the following.
- Testing how the optimal solution would change if there were either more or less of a scarce resource.
- Testing whether it would be worthwhile obtaining more of a scarce resource by paying a premium for the additional resources, for example by paying an overtime premium for extra labour hours, or by paying a supplier a higher price for extra raw materials.
The effect of having more or less of a scarce resource
Sensitivity analysis can be applied to the final matrix to determine the effect of having more or less of a scarce resource (indicated by figures in the column for the resource’s slack variable).
The optimal solution to a linear programming problem is based on the assumption that the constraints are known with certainty, and fixed in quantity. Sensitivity analysis enables us to test how the solution would alter if the quantity of a scarce resource (the size of a constraint) were to change.
USING COMPUTER PACKAGES
Spreadsheet packages can be used to solve linear programming problems.
- The slack/surplus columns provide information about the slack values of ≤ constraints and the surplus values of any ≥
- The worth column shows the positive shadow price of resources.
- The relative loss shows by how much contribution (usually) would fall if extra units of particular decision variables were produced.
USING LINEAR PROGRAMMING
There are a number of assumptions and practical difficulties in the use of linear programming.
The considerations, non-quantifiable factors and assumptions in limiting factor analysis that we looked at in Chapter 8 apply equally to linear programming.
Further assumptions
In addition, there are further assumptions if we are dealing with product mix decisions involving several limiting factors.
- The total amount available of each scarce resource is known with accuracy.
- There is no interdependence between the demand for the different products or services, so that there is a completely free choice in the product or service mix without having to consider the consequences for demand or selling prices per unit.
In spite of these assumptions, linear programming is a useful technique in practice. Some statistical studies have been carried out suggesting that linear cost functions do apply over fairly wide ranges of output, and so the assumptions underlying linear programming may be valid.
Uses of linear programming
- Budgeting. If scarce resources are ignored when a budget is prepared, the budget is unattainable and is of little use for planning and control. When there is more than one scarce resource, linear programming can be used to identify the most profitable use of resources.
- Calculation of relevant costs. The calculation of relevant costs is essential for decision making. The relevant cost of a scarce resource is calculated as acquisition cost of the resource plus opportunity cost. When more than one scarce resource exists, the opportunity cost (or shadow price) should be established using linear programming techniques.
- Selling different products. Suppose that an organisation faced with resource constraints manufactures products X and Y and linear programming has been used to determine the shadow prices of the scarce resources. If the organisation now wishes to manufacture and sell a modified version of product X (Z), requiring inputs of the scarce resources, the relevant costs of these scarce resources can be determined (see above) to ascertain whether the production of X and Y should be restricted in order to produce Z.
- Maximum payment for additional scarce resources. This use of shadow prices has been covered in this chapter.
- Opportunity costs are also important for cost control: standard costing can be improved by incorporating opportunity costs into variance calculations. For example, adverse material usage variances can be an indication of material wastage. Such variances should be valued at the standard cost of the material plus the opportunity cost of the loss of one scarce unit of material. Such an approach highlights the true cost of the inefficient use of scarce resources and encourages managers of responsibility centres to pay special attention to the control of scarce factors of production. For organisations using an optimised production technology (OPT) strategy, this approach is particularly useful because variances arising from bottleneck operations will be reported in terms of opportunity cost rather than purchase cost.
- Capital budgeting. Linear programming can be used to determine the combination of investment proposals that should be selected if investment funds are restricted in more than one period.
Practical difficulties with using linear programming
Difficulties with applying the linear programming technique in practice include the following.
It may be difficult to identify which resources are likely to be in short supply and what the amount of their availability will be.
With linear programming, the profit-maximising product mix and the shadow price of each limiting factor depend on the total estimated availability of each scarce resource. So it is not sufficient to know that labour hours and machine hours will be in short supply, it is also necessary to guess how many labour hours and machine hours will be available. Estimates of future availability will inevitably be prone to inaccuracy and any such inaccuracies will invalidate the profit-maximising product mix derived from the use of linear programming.
Management may not make product mix decisions which are profit-maximising. They may be more concerned to develop a production/sales plan which has the following features.
-
- Realistic
- Acceptable to the individual managers throughout the organisation
- Acceptable to the rest of the workforce
- Promises a ‘satisfactory’ profit and accounting return
In other words, management might look for a satisfactory product mix which achieves a satisfactory return, sales revenue and market share whilst at the same time plans operations and targets of achievement which employees can accept as realistic, not too demanding or unreasonable, and not too threatening to their job security.
If a ‘satisfactory’ output decision is adopted, the product mix or service mix recommended by the linear programming (profit-maximising) technique will inevitably be ‘watered down’, amended or ignored.
- The assumption of linearity may be totally invalid except over smaller ranges. For example, in a profit maximisation problem, it may well be found that there are substantial changes in unit variable costs arising from increasing or decreasing returns to scale.
- The linear programming model is essentially static and is therefore not really suitable for analysing in detail the effects of changes in the various parameters, for example over time.
- In some circumstances, a practical solution derived from a linear programming model may be of limited use as, for example, where the variables may only take on integer values. A solution must then be found by a combination of rounding up and trial and error.
- The shadow price of a scarce resource only applies up to a certain limit.
CHAPTER ROUNDUP
- The formulation of the problem using the simplex method is similar to that required when the graphical method is used but slack variables must be incorporated into the constraints and the objective function.
- A slack variable represents the amount of a constraint that is unused.
- In any feasible solution, if a problem involves n constraints and m variables (decision plus slack), n variables will have a positive value and (m–n) variables will have a value of zero.
- Feasible solutions to a problem are shown in a matrix table.
- If the shadow prices on the bottom (solution) row of a table are all positive, the table shows the optimal solution.
− The solution column shows the optimal production levels and the units of unused resource.
− The figure at the bottom of the solution column/right-hand side of the solution row shows the value of the objective function.
− The figures in the solution row indicate the shadow prices of resources.
- Sensitivity analysis can be applied to the final matrix to determine the effect of having more or less of a scarce resource (indicated by figures in the column for the resource’s slack variable).
- Sensitivity analysis can also be applied to test whether or not it would be worthwhile to obtain more of a scarce resource by paying a premium for additional supplies (only if the shadow price is greater than the additional cost).
- Spreadsheet packages can be used to solve linear programming problems.
− The slack/surplus columns provide information about the slack values of ≤ constraints and the surplus values of any ≥ constraints.
− The worth column shows the positive shadow price of resources.
− The relative loss shows by how much contribution (usually) would fall if extra units of particular decision variables were produced.
- There are a number of assumptions and practical difficulties in the use of linear programming.
