OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.
A full list of the topics available in OR-Notes can be found here.
We follow the same structure as given in the lecture notes - namely:
Essentially we are interested in the amount (in thousand kg) produced (mixed) at each of the three plants and in the amount shipped out of a production plant for packing. Hence let
xi = amount (thousand kg) produced (mixed) at plant i (i=1,2,3)
in the next month
yij = amount (thousand kg) shipped in the next month from plant
i (i=1,2,3) to plant j (j=1,2,3) for packing before being shipped back
to plant i for distribution to the customers.
Note that xi >= 0 (i=1,2,3) and yij >= 0 (i=1,2,3 and j=1,2,3). We interpret yii (i=1,2,3) as the amount "shipped" (at zero cost) within plant i for packing at plant i after production at plant i.
We illustrate the problem diagrammatically below. Note here that often in problems involving "flow" of material a diagram is useful in clarifying the situation.
x1 <= 60
x2 <= 80
x3 <= 40
y11 + y21 + y31 <= 70
y12 + y22 + y32 <= 50
y13 + y23 + y33 <= 50
y21 + y31 <= 5
y12 + y32 <= 10
y13 + y23 <= 15
x1 = y11 + y12 + y13
x2 = y21 + y22 + y23
x3 = y31 + y32 + y33
These constraints could be regarded as examples of implicit constraints in that they are effectively implicit from the definition of the variables. Alternatively they can be regarded as constraints that logically we need to relate the amount produced to the amount shipped.
The question explicitly states "minimise costs". Cost has four components:
100x1 + 120x2 + 150x3
60(y11 + y21 + y31) +30(y12 + y22 + y32) +40(y13 + y23 + y33)
20y12 + 23y13 + 25y21 + 24y23 + 30y31 + 27y32
300(x1 + x2 + x3)
Defining C= 100x1 + 120x2 + 150x3 + 60(y11 + y21 + y31) + 30(y12 + y22 + y32) + 40(y13 + y23 + y33) + 20y12 + 23y13 + 25y21 + 24y23 + 30y31 + 27y32 + 300(x1 + x2 + x3) to be the total cost we have that our objective is
minimise C
However it is clear that to minimise cost (in this problem) we would simply not produce anything at all, i.e. setting all variables equal to zero satisfies the constraints and minimises cost. This is plainly not what was meant by the question. Hence we need to revise our objective.
Rereading the question it is clear that our objective is really two-fold, namely to maximise the total amount produced (given we are told that we can sell all that we can make) whilst at the same time minimising the cost of producing that maximum amount (i.e. arrange the production of the maximum amount in such a way so as to minimise total cost).
Multiple objective problems (such as this one) are often difficult to transform into a single objective problem (which is all we can cope with in LP). For this particular problem there are two possible approaches:
If we adopt the first approach we have that the total revenue is
P(x1 + x2 + x3)
(note P is a known constant, not a variable) so that the objective now is
maximise P(x1 + x2 + x3) - C
Note here that this question was set so as to be deliberately confusing as to the objective. Many real-life problems also have no clear-cut objective.
Now to solve this LP using the package we need to assign a value to P large enough to ensure that it is profitable to produce at all the plants (e.g. P=1000). We also need to rearrange the constraints so that their right-hand sides are constants. If we do this we find from the package that the solution is x1=60, x2=70 and x3=35, with the values of the y variables being given by y11=60, y21=5, y22=50, y23=15 and y33=35 (all other y variables being zero).
If we adopt the second approach the first LP would be maximise production (x1+x2+x3) subject to the constraints given above, leading to a maximum production of K (say) - where here we would find numerically if we solved this LP that K=165. Note here that it is much better to solve the problem of determining the maximum possible production via LP Examining the data and using our brains to see what we think is the maximum possible production is not an adequate approach. For this particular example I have deliberately set the numbers in such a way that it is not necessarily obvious what the maximum production is - e.g. if you had looked at the numbers given in the question what would you have said the maximum production was?
The second LP would be minimise cost subject to the constraints given above and (x1+x2+x3)=K. Hence we end up with the maximum possible production achieved in a minimum cost way. (Note here that this approach is related to a logical question we might ask, namely "what is the maximum possible production achievable given this system?") Note too here that this approach would enable us to explore the variation in (minimum) cost as we change the production level K, e.g. down from its maximum level of 165. After all we may suspect that the plant capacities quoted are such that we would encounter problems if we were to run the system at full capacity. Hence we may, as a management decision, be interested in running the system at less than capacity (i.e. in choosing a value of K less than 165).