Linear programming is an optimisation technique that will enable you to find a maximum or minimum value for a problem, subject to any constraints that are relevant. In linear programming the constraints and objective function (the thing you are trying to maximise or minimise) are always modelled by linear equations.
There are two things that you need to create in order to be able to solve a linear programming question. First you should use the information given in the question to generate one or more constraint inequalities. Second you need to define the objective function, which describes the problem for which you are trying to find a maximum or minimum.
Before you can do all this you need to define your variables. The variables that you use will depend on the problem. It will be best to work through an example to demonstrate this.
Clive has decided that as a fund-raising activity he will make and sell candles. He has decided to make two types of candle, a plain one, and a scented one. Each candle requires 200g of wax and Clive has bought enough ingredients to make a total of 1.6kg of wax. His idea is to make the scented candles tall and thin, and the plain candles shorter and fatter. This means that the length of wick required for a scented candle is 200mm but only 100mm is needed for a plain candle. Clive only has 1m of wick to use. Clive has worked out from a survey that he won’t be able to sell more scented candles than double the number of plain candles plus three.
If he is going to sell the candles at £3 for a scented candle and £2 for a plain, how many of each should he make so that he raises the most money possible?
Solution
Definitions
The first thing that we must do is define our variables:
Let:
x be the number of plain candles made, y be the number of scented candles made, and I be the income from selling the candles.
Variable definitions
Constraints
Having defined the variables we can construct our constraint inequalities using the information provided in the question. These describe the conditions that will restrict the number of candles that we can make.
The first constraint relates to the mass of wax available. 200g is required for each candle, and the total available is 1.6kg. Converting to consistent units and writing as an inequality, then simplifying we get:
\begin{aligned}200x + 200y &\leq 1600 \\ x + y &\leq 8\end{aligned}First constraint inequality
The second constraint is given by the amount of wick available and required. 100mm is needed for each plain candle and 200mm is needed for each scented candle. 1m is available. As with the first constraint, we make sure the units are consistent, then write as an inequality and simplify.
The final constraint is that Clive won’t be able to sell more scented candles than double the number of plain candles plus three. Although slightly complicated this constraint can be written as follows:
y \leq 2x + 3Third constraint inequality
Trivial constraints
Most linear programming problems will have some constraints that are not explicitly described. Sometimes you will need to infer a constraint from the context; most frequently these will be trivial. Although referred to as trivial, these constraints are important to include. In this case the context means that we are only interested in positive integers:
Having constructed all of our constraint inequalities the only thing left for us to do before solving the problem is to generate an objective function. This is created from the information that tells us what we are to optimise (usually make biggest or smallest). In this case, we need to maximise income with each scented candle selling at £3 and each plain candle selling at £2. The objective function will be:
I = 2x + 3yObjective function
Solving the problem graphically
This problem can be solved graphically by constructing the graph below. Using the constraints that we have already constructed:
x + y \leq 8 \\ x + 2y \leq 10 \\ y \leq 2x + 3 \\ y \geq 0All of the constraints
Using the coordinates found at or near the vertices in the objective function, we can work out which combination of scented and plain candles will give the greatest income. Because the only solutions that make sense in the context are integer values of both x and y, it is worth checking coordinate points near the vertices, inside the feasible region.
x
y
I = 2x+ 3y
0
3
2 × 0 + 3 × 3 = £9
0.8
4.6
2 × 0.8 + 3 × 4.6 = £15.40
1
4
2 × 1 + 3 × 4 = £14
6
2
2 × 6 + 3 × 2 = £18
8
0
2 × 8 + 3 × 0 = £16
As you can see, the highest income can be achieved when 6 plain candles and 2 scented candles are sold. This will give an income of £18.
Critical path analysis allows you to determine the best way of arranging activities. The typical question to answer is “what is the minimum time required for a process?”
Performing activities one after the other as you come to them might not be the best way of organising a project. If more than one activity can be worked on at the same time you will need to decide when to start each one. Below, in table 1, are the activities needed to build a house with durations given in days. We are going to perform a critical path analysis on the process of house construction.
Task
Description
Duration
A
Excavate foundations
2
B
Pour concrete
1
C
Build walls
3
D
Construct roof sections
7
E
Put up roof sections
1
F
Tile roof
3
G
Install plumbing
4
H
Install electrics
3
I
Install windows and doors
2
J
Paint ceilings
2
K
Paint walls
3
L
Lay carpets
2
Table 1: Activities involved in building a house
The first thing that we need to do is to decide which of the activities depend on other activities:
B requires that A be complete.
C requires that B be complete.
E requires that C and D be complete.
F requires that E be complete.
G, H, and I all require that F be complete.
J and K require that G, H, and I be complete.
L requires that J and K be complete.
With this information we can draw an activity network. In an activity network the edges represent activities, such as those listed above. The nodes represent events. An event is the start and/or finish of one or more activities. The activity network for the house building example is shown in figure 1.
Figure 1: The activity network for house building.
The activity network shows that there are 12 events involved in the building of this house, and that 12 activities (plus 3 dummy activities) are required before the house is complete.
As you can see, there are a few activities that can occur concurrently. Later we will use this example to find the critical path through the operation (finding a critical path). It is the longest path and determines the minimum length of time that is necessary to complete the house.
As we saw in the introduction to critical path analysis, an activity network is a graphical representation of activities and events that are needed for a process. There are several rules that have to be obeyed when creating accurate networks.
These rules are:
An edge is used to represent an activity.
A vertex represents an event, which is the start or end of one or more activities.
Events are numbered so that the activity ends at a higher numbered event than it started.
Events are numbered so that no activity starts and ends at the same event. An activity can therefore be uniquely identified by its start and end events.
In order to avoid ambiguity between activities you must use ‘dummy’ activities. These are activities that have zero length and are inserted to ensure that precedence requirements are met. They allow two activities that ought to have the same start and end events to be distinguished.
There should only be one start event and one finish event.
The activity detail (or code) and duration are written along the edges.
The edge length has no meaning.
Using these rules you should be able to create activity networks for any process that involves more than one activity.
Once you have drawn out an activity network the next step is to work out the earliest and latest possible times for each event. This will let you find the minimum time necessary for the tasks to be completed taking activity precedence into account.
In order to make the identification of earliest and latest times easier, they are often put into a pair of boxes. The left box will be the earliest time and the right box will be the latest time. When working out the earliest times for each event you must start at the first event and assign an earliest time of 0. Work through each event in turn. Add the duration of the activity to the earliest time of the start event to get the earliest time of the end event. If there is more than one way of arriving at the end event then take the largest value for the earliest time.
Figure 1: Earliest times for the house building activity network.
Once you have gone through the entire network assigning earliest times you can begin to work out the latest times. This is done by starting at the last event and working backwards though the network. To start the process let the latest time of the last event be equal to the earliest time of that event. By subtracting the duration of an activity from the event that it ends at you will be able to find the latest time for the start event for that activity. If there is more than one way to arrive at a start event then take the smallest value for the latest time.
Figure 2: Earliest and latest times for the house building activity network.
By looking at the earliest / latest times for the last event you will know the minimum duration for the overall process.
Once you have decided on the critical path for an activity network you will need to allocate resources to each task.
Resources could take the form of equipment, people, money, or any number of other things. Most often we will use people. The question you need to ask yourself is “how many people do I need so that the project can be finished without any delay?” In answering this question you are halfway to allocating resources.
In the example we have been looking at, there are at most three things that can be happening at any one time. Do we need to use three people, or will two people be enough (have we got enough time to complete H and I before G is completed)? Looking at the activity network we can see that there will not be enough time to do this.
Figure 1: Earliest and latest times for the house building activity network.
Another way of showing the resources needed is to draw a cascade chart and then a resource histogram.
The cascade chart in figure 2 shows the critical path on the lower row and has a row for each of the other activities, starting at their earliest time and showing float at the end. This allows the viewer to see where activities can be collapsed down to be allocated to a single worker. The collapsed form, as a resource histogram, is shown in figure 3.
Figure 2: Cascade chart showing the activities in the house building example. Critical path is the lower row.
Figure 3: Resource histogram for the house building example. A total of 3 workers are needed.
This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.
Strictly Necessary Cookies
Strictly Necessary Cookie should be enabled at all times so that we can save your preferences for cookie settings.
If you disable this cookie, we will not be able to save your preferences. This means that every time you visit this website you will need to enable or disable cookies again.
