GP TwoMines
GP TwoMines
GP TwoMines
Goal programming
Introduction
Multicriteria decision making refers to situations where we have more than
one objective (or goal) and these objectives conflict and we must somehow reach a
decision taking them all into account. This contrasts with, for example, decision trees
or linear programming, where we have a single objective – either optimise expected
monetary value for decision trees or optimise a single linear objective in the case of
linear programming. Here we consider goal programming, one technique used for
multicriteria decision making.
Production (tons/day)
Mine Cost per day High Medium Low
X 180 6 3 4
Y 160 1 1 6
How many days per week should each mine be operated to fulfil the smelting
plant contract ?
1
To crush, triturar.
2
To smelt, fundir para extrair metal.
Goal programming [:7] 2
MINIMIZE
1,714286 2,857143
180 160 765,7143
x y C+ C- H+ M+ L+
6 1 13,14286 >= 12
3 1 8 >= 8
4 6 24 >= 24
1 1,714286 <= 5
1 2,857143 <= 5
Figure 1
• do not produce excess ore — which actually relates to the three grades of ore for
which the respective goals are the amount that we need: 12, 8 and 24 tonnes,
respectively.
Let C+ (≥ 0) represent the amount by which we deviate upward from our cost
goal and C– (≥ 0) represent the amount by which we deviate downward from our cost
goal. Then we have an equation linking these new variables to our old variables:
180 x + 160 y = 800 + C+ – C–
This constraint, which must be an equality, says that whatever we decide in terms of
production on mines X and Y (x and y, respectively) the cost of that (180 x + 160 y)
must equal the goal (800) adjusted by the deviation variables C+ and C–, the plus in
front of C in this equation indicating an upward movement (deviation) from the goal
and the minus in front of C in this equation indicating a downward movement
(deviation) from the goal.
There are two comments to make here:
• it is standard notational practice in GP to use a plus superscript to indicate upward
deviation from the goal and a negative superscript to indicate downward deviation
from the goal.
• one subtle point here is that the way we have written our equation including C+ – C–
opens the possibility that when we come to numerically solve the problem we get
an answer like C+ =100 and C– =120, so both an upward and a downward
deviation with the overall deviation being C+ – C– = 100 – 120 = –20; a
downward deviation of 20.
We can now deal with our objective relating to production of excess ore.
Letting H+, M+ and L+ (all ≥ 0) be the upward deviation for high, medium and low-
grade, respectively, and H–, M– and L– (all ≥ 0) be the downward deviation for high,
medium and low-grade, respectively, we have the three equality equations:
6 x + 1 y = 12 + H+ – H–
3 x + 1 y = 8 + M+ – M–
4 x + 6 y = 24 + L+ – L–
One point to note here is that the above equations leave open the possibility
that the company might decide not to supply all the ore for some particular grade (i.e.,
we have a downward deviation from the goal level where here the goal level relates to
the amount that we are contracted to supply). If the company wishes to exclude this
possibility, then we simply set H– = M– = L– = 0 (eliminate these variables from the
problem).
Hence for our Two Mines problem where we wish to reconcile our conflicting
objectives we have the equations (p 5):
180 x + 160 y = 800 + C+ – C–
6 x + 1 y = 12 + H+ – H–
3 x + 1 y = 8 + M+ – M–
4 x + 6 y = 24 + L+ – L–
x≤5
y≤5
(nonnegative variables)
These equations are, given our variables, equations that must be satisfied.
Goal programming [:7] 4
Weighted approach
(pp 5–10)
Priority approach
(p 11) For the priority approach, we will again assume that we always wish to
supply the amount of ore we are contracted to supply, so that H– = M– = L– = 0 (i.e.,
these variables can be eliminated from the problem). This leaves variables C+, C–,
H+, M+ and L+.
As mentioned above, in the priority approach we need to decide priority levels
for the goals (priority level 1 for the most important goal, then priority level 2 for the
second most important goal, etc.) and first satisfy priority one goals, then priority two
goals, etc., so that a sequence of related problems are solved.
Here, for the purposes of illustrating the approach, we shall assume that
management consider that their priority levels are:
• priority level 1 – as little excess high-grade ore as possible
• priority level 2 – cost
• priority level 3 – as little excess combined medium-grade and low-
grade ore as possible
Hence the first problem that we solve (a linear program) is (p 11):
Minimize H+
subject to 180 x + 160 y = 800 + C+ – C
6x +1y = 12 + H+
3x +1y = 8 + M+
4x +6y = 24 + L+
x ≤5
y ≤5
(nonnegative variables)
3
Sequential goal programming, programação sequencial por objectivos.
4
Preemptive goal programming, programação preemptiva por objectivos (por objectivos prioritários).
Goal programming [:7] 5
Solving the linear program represented in the above model we get (Excel
p 12a&b):
First goal
MINIMIZE
1,333333 4 0 0 0 0 5,333333
1 0
x y C+ C- H+ M+ L+
6 1 -1 12 = 12
3 1 -1 8 = 8
4 6 -1 24 = 24
1 1,333333 <= 5
1 4 <= 5
Figure 2
This indicates that we can achieve zero excess high-grade ore, H+ (a zero value
corresponding to a zero upward deviation variable for high-grade ore), but at the price
of an upward deviation from our cost goal of 80 and an upward deviation from our
low-grade ore goal, L+, of 5.333.
We can now move to our second priority level. This was cost so we have the
new linear program (p 13):
Minimize C+ – C–
subject to 180 x + 160 y = 800 + C+ – C–
6x +1y = 12 + H+
3x +1y = 8 + M+
4x +6y = 24 + L+
x ≤5
y ≤5
H+ =0
(nonnegative variables)
where we are trying to minimise deviation from our cost goal but where the upward
deviation variable H+ for high-grade ore is now constrained to be zero (the value it
had in our solution calculated above at the first priority level).
Note that the objective function here is minimise C+ – C–, where the positive
sign before C+ indicates that we dislike upward deviations from our cost goal but the
minus sign before C– indicates that we like downward deviations from our cost goal.
Had we wished to just minimise deviation from our cost goal our objective
would have been minimise C+ + C–.
You will see: (Excel p 14a & b)
Goal programming [:7] 6
Second goal
MINIMIZE
1,333333 4 80 0 0 0 5,333333
1 -1 80
x y C+ C- H+ M+ L+
180 160 -1 1 800 = 800
6 1 -1 12 = 12
3 1 -1 8 = 8
4 6 -1 24 = 24
1 1,333333 <= 5
1 4 <= 5
1 0 = 0
Figure 3
which is actually the solution we had before, i.e.: our previous solution that we
obtained when we minimised upward deviation for high-grade ore also happened to
minimise our cost goal.
We can now consider the third priority level which was: as little excess
combined medium-grade and low-grade ore as possible. This implies that we
minimise the combined deviation for medium and low-grade ore. The linear program
for this problem is (p 15):
Minimize M+ + L+
subject to 180 x + 160 y = 800 + C+ – C–
6x +1y = 12 + H+
3x +1y = 8 + M+
4x +6y = 24 + L+
x ≤5
y ≤5
+
H =0
C+ – C– = 80
(nonnegative variables)
where we have added a constraint specifying that the objective at the second priority
level (C+ – C–) must retain the minimum value (80) we calculated above.
Third goal
MINIMIZE
1,333333 4 80 0 0 1,11E-16 5,333333
1 1 5,333333
x y C+ C- H+ M+ L+
180 160 -1 1 800 = 800
6 1 -1 12 = 12
3 1 -1 8 = 8
4 6 -1 24 = 24
1 1,333333 <= 5
1 4 <= 5
1 0 = 0
1 -1 80 = 80
Figure 4