THE GRAPHICAL METHOD
The graphical method of linear programming is used for problems involving two products.
Formulating the problem
Let us suppose that WX manufactures two products, A and B. Both products pass through two production departments, mixing and shaping. The organisation’s objective is to maximise contribution to fixed costs.
Linear programming is ‘The use of a series of linear equations to construct a mathematical model. The objective is to obtain an optimal solution to a complex operational problem, which may involve the production of a number of products in an environment in which there are many constraints’.
What are the constraints in the situation facing WX?
- Machine hours in each department
- Labour hours in each department
(iii)Sales demand for product B (iv) Selling price of product A
- and (iii)
- only
- and (iv)
- (i), (ii) and (iii)
The correct answer is A. There is no restriction on the availability of labour hours. Selling price cannot be a constraint.
The steps in the graphical method are as follows.
− Define variables.
− Establish objective function.
− Establish constraints.
− Draw a graph of the constraints.
− Establish the feasible region.
− Determine the optimal product mix.
Graphing the problem
A graphical solution is only possible when there are two variables in the problem. One variable is represented by the x axis of the graph and one by the y axis. Since non-negative values are not usually allowed, the graph shows only zero and positive values of x and y.
Finding the optimum allocation of resources
The optimal solution can be found by ‘sliding the iso-contribution (or profit) line out’.
Having found the feasible region (which includes all the possible solutions to the problem) we need to find which of these possible solutions is ‘best’ or optimal in the sense that it yields the maximum possible contribution.
THE GRAPHICAL METHOD USING SIMULTANEOUS EQUATIONS
Instead of a ‘sliding the contribution line out’ approach, simultaneous equations can be used to determine the optimal allocation of resources, as shown in the following example.
The optimal solution can also be found using simultaneous equations
Slack and surplus
Slack occurs when maximum availability of a resource is not used. Surplus occurs when more than a minimum requirement is used.
If, at the optimal solution, the resource used equals the resource available there is no spare capacity of a resource and so there is no slack.
If a resource which has a maximum availability is not binding at the optimal solution, there will be slack.
Sensitivity analysis
Once a graphical linear programming solution has been found, it should be possible to provide further information by interpreting the graph more fully to see what would happen if certain values in the scenario were to change.
- What if the contribution from one product was RWF1 lower than expected?
- What if the sales price of another product was raised by RWF2?
- What would happen if less or more of a limiting factor were available, such as material?
Sensitivity analysis with linear programming can be carried out in one of two ways.
- By considering the value of each limiting factor or binding resource constraint
- By considering sale prices (or the contribution per unit)
Limiting factor sensitivity analysis
We use the shadow price to carry out sensitivity analysis on the availability of a limiting factor.
Shadow prices
The shadow price of a resource which is a limiting factor on production is the amount by which total contribution would fall if the organisation were deprived of one unit of the resource. The shadow price also indicates the amount by which total contribution would rise if the organisation were able to obtain one extra unit of the resource, provided that the resource remains an effective constraint on production and provided also that the extra unit of resource can be obtained at its normal variable cost.
Sales price sensitivity analysis
Sales price sensitivity analysis is carried out by changing the slope of the ‘iso-contribution’ line.
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 tableau.
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 or tableaux, 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 a repetitive, step-by-step process, with each 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 matrix or tableau with 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
Formulating the problem
We have just two decision variables in this problem, but we can still use the simplex method to solve it.
Drawing up the initial tableau and testing the initial feasible solution
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 optimal solution, but it gives us a starting point from which we can develop other feasible solutions.
Simplex tableaux can be drawn in several different ways, and if you are asked to interpret a given tableau in an examination question, you may need to adapt your understanding of the tableau format in this Study Text to the format in the question. The following points apply to all tableaux, 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.
SENSITIVITY ANALYSIS
You might be asked to carry out some sensitivity analysis on a simplex tableau 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 tableau 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 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.
USING LINEAR PROGRAMMING
There are a number of assumptions and practical difficulties in the use of 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
Maximum payment for additional scarce resources. This use of shadow prices has been covered in this chapter.
Control. 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 and 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.
