Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
CHAPTER 9:
Multi Objective Decision Making (MODM)
GOAL PROGRAMMING
Goal programming (GP) is a variation of linear
programming considering more than one objective
(goals) in the objective function.
A goal programming (GP) model is very similar to
LP models with an objective function, decision
variables and constraints.
Example 9.1:
The Beaver Creek Pottery Company produces clay
bowls and mugs. The resources used by this company
is given in the following table:
Resource Requirements
Product Clay Profit
Labor
(pounds/unit) ($/unit)
Bowl 1 4 40
Mug 2 3 50
Available
40 hours 120 kg
resources
1
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
The LP for this problem is:
Maximize Z = $40 x1 + 50 x2 (profit)
Subject to x1 + 2 x2 40 (hours of labor)
4 x1 + 3 x2 120 (pounds of clay)
x1, x2 0
Where x1 = number of bowls produced
x2 = number of mugs produced
This is a standard LP model with single objective of
maximizing profit.
However, let us suppose that instead of having one
objective, the pottery company has several
objectives that are listed here in order of
importance:
1. To avoid layoffs, the company does not want to use
fewer than 40 hours of labor per day.
2. The company would like to achieve satisfactory
profit level of RM1600 per day.
3. Because the clay must be stored in a special place
so that it does not dry out, the company prefers not
to keep more than 120 pounds on hand each day.
2
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
4. Because high overhead costs occur if the plant is
kept open past normal hours, the company would
like to minimize the amount of overtime.
All these different objectives mentioned known as
goals. All these goals can be simplified as follows
(in order of importance / priority):
1. Does not want to use fewer than 40 hours of labor
per day;
2. Would like to achieve a satisfactory profit level of
$1,600 per day;
3. Prefers not to keep more than 120 pounds of clay
on hand each day;
4. Would like to minimize the amount of overtime.
3
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Goal Programming: Goal Constraint Requirements
All goal constraints are equalities that include
deviational variables d- and d+.
A positive deviational variable (d+) is the amount by
which a goal level is exceeded.
A negative deviation variable (d-) is the amount by
which a goal level is underachieved.
At least one or both deviational variables in a goal
constraint must equal zero.
The objective function in a goal programming
model seeks to minimize the deviation from goals in
the order of the goal priorities.
4
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
First Goal:
Avoid underutilization of labor
The company does not want to use fewer than 40
hours of labor each day.
To represent the possibility of underutilizing labor,
the original constraint for labor is reformulated as
follows:
x1 + 2 x2 40 (original constraint)
x1 + 2 x2 + d1- - d1+ = 40 (reformulated constraint)
This reformulated constraint is referred as goal
constraint.
The two new variables, d1- and d1+ , are called
deviational variables. They represent the amount of
-
labor hours less than 40 ( d1 ) [labor underutilization]
+
and the amount of labor hours exceeding 40 ( d1 )
[overtime].
5
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Example:
Lets say x1 = 6 bowls and x2 = 8 mugs produced.
Substituting these values into goal constraint for
labor gives
(6) + 2 (8) + d1- - d1+ = 40
22 + d1- - d1+ = 40
Since only 22 hours of labor were used in
production, labor was underutilized by 18 hours (40
– 22 = 18).
Thus d1- = 18 hours (unused labor) and d1+ = 0
(because there is no overtime).
Now consider another situation where x1 = 10 bowls
and x2 = 20 mugs produced.
Substituting these values into goal constraint for
labor gives
(10) + 2 (20) + d1- - d1+ = 40
50 + d1- - d1+ = 40
6
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
A total of 50 hours of labor have been used for
production, or 10 hours above the goal level of 40
hours. This means there were 10 hours of overtime
(50 – 40 = 10).
Thus d1- = 0 hours (because there was no
+
underutilization) and d1 = 10 (10 hours of
overtime).
In each of the above two cases, at least one of the
deviational variables equaled zero. In the first case,
d1+ = 0 and in the second case, d1- = 0.
Fundamental characteristics of goal programming:
At least one or both deviational variables in a
goal constraint must equal zero.
Back to the labor goal:
We have formulated the labor constraint as follows:
x1 + 2 x2 + d1- - d1+ = 40
7
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Since the company wants to avoid the
underutilization of labor, the deviational variable
d1- must be minimized.
We do this by creating a new form of objective
function:
-
Minimize P1 d1
This represent priority
-
In this objective function the goal is to minimize d1
, the underutilization of labor.
The symbol P1 in the objective function designates
-
the minimization of d1 as the priority one goal.
This means that when this model is solved, the first
-
step will be to minimize the value of d1 before any
other goal is addressed.
8
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Second Goal:
Achieve a satisfactory profit level of $1,600 per day
The original LP objective function is:
Z = $40 x1 + $50 x2
Now we reformulate this objective function as a
goal constraint:
40 x1 + 50 x2 + d -2 - d +2 = 1600
The deviational variables d -2 and d +2 represent the
-
amount of profit less than $1600 ( d 2 ) and the
+
amount of profit exceeding $1600 ( d 2 ).
The company’s objective of achieving $1600 in
profit is represented in the objective function as:
- -
Minimize P1 d1 , P2 d 2
Note that only d -2 is minimized and by which the
company hopes that it can achieve at least $1600 of
profit.
9
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Third Goal:
Avoid keeping more than 120 pounds of clay on
hand.
The original constraint for clay is:
4 x1 + 3 x2 120
Now we reformulate this constraint by adding
deviational variables:
4 x1 + 3 x2 + d 3- - d 3+ = 120
Since d3- represent amount of clay less than 120
+
pounds and d 3 represent amount of clay exceeding
+
120 pounds, our objective should be minimizing d 3
(since we don’t want to keep clay more than 120
pounds).
This goal can be reflected in objective function as
- - +
Minimize P1 d1 , P2 d 2 , P3 d 3
The P3 given to this goal designates that this is the
company’s third priority goal.
10
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Fourth goal:
Minimize overtime.
This goal is also associated with labor constraint.
Recall that in the first goal, overtime is represented
by d1+ .
So the fourth goal will be minimize d1+ which
represented in the objective function as follows:
- - + +
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d1
The complete goal programming model is:
- - + +
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d1
Subject to
x1 + 2 x2 + d1- - d1+ = 40
40 x1 + 50 x2 + d -2 - d +2 = 1600
4 x1 + 3 x2 + d 3- - d 3+ = 120
x1, x2, d1- , d1+ d -2 , d +2 d 3- , d 3+ 0
The basic difference between this model and the
standard linear programming model is that the
11
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
objective function terms are not summed to equal a
total value, Z.
This is because the deviational variables in the
objective function represent different units of
measure. It would be illogical to sum hours, dollars
and pounds.
The objective function in a goal programming
model specifies only that the deviations from the
goals represented in the objective function be
minimized individually in order of their priority.
Alternative forms of goal constraints
In some cases, goal constraints can take forms other
than the one previously discussed.
For example, let say the fourth priority goal in the
above model is altered: Limit the overtime to 10
hours (instead of minimizing overtime).
12
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Recall that the goal constraint for labor is:
x1 + 2 x2 + d1- - d1+ = 40
In the above goal constraint, d1+ represent overtime.
Because the new forth priority goal is to limit
overtime to 10 hours, the following goal constraint
can be developed:
d1+ d -4 d +4 = 10
Although the above constraint looks unusual, but it
is acceptable in goal programming to have an
equation with all deviational variables.
In the above goal constraint, d -4 represents the
+
amount of overtime less than 10 hours, and d 4
represents the amount of overtime greater than 10
hours.
Since the company desires to limit overtime to 10
+
hours, so d 4 should be minimized in the objective
function.
- - + +
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d 4
13
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Now let us consider the addition of a fifth priority
goal
Assume that the company has limited warehouse
space. So it can produce no more than 30 bowls and
20 mugs daily.
The above situation will require us to add two new
constraints to the original LP model
x1 30 (bowls)
x2 20 (mugs)
If possible, the company would like to produce
these amounts of bowls and mugs.
However, since profit for mugs ($50) is greater than
the profit for bowls ($40), it is more important to
achieve the goal for mugs.
x1 + d 5- = 30 (bowls)
x2 + d -6 = 20 (mugs)
Notice that the positive deviational variables d 5+ and
d 6+ are not included in these goal constraints. This is
because the goal specifies that “no more than 30
14
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
bowls and 20 mugs can be produced” . So,
positive deviation or overproduction is not possible.
Since the company will try to produce 30 bowls and
20 mugs, the negative deviational variables d 5- and
d -6 should be minimized in the objective function.
However, since mugs have greater profit, it is more
important to achieve the goal for mugs.
This condition can be reflected in the objective
function as follows:
- - + + - -
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d 4 , 4P5 d 5 + 5P5 d 6
Because the goal for mug is more important, the
degree of importance should be in proportion to the
amount of profit.
Thus, the goal for mugs is more important than the
goal for bowls by a ratio of 5 to 4.
The coefficients 5 for P5 d -6 and 4 for P5 d 5- are
referred to as weights.
15
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
So, the minimization of d -6 is “weighted” higher
-
than the minimization of d 5 at the fifth priority level.
When this model is solved, the minimization of d -6
(mugs) will be attempted first before the
-
minimization of d 5 (bowls), even though both goals
have same priority.
Notice that these weighted goals have been summed
because they are at the same priority level.
The complete goal programming model with the
new goals for both overtime and production is as
follows:
- - + + - -
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d 4 , 4P5 d 5 + 5P5 d 6
Subject to
x1 + 2 x2 + d1- - d1+ = 40
40 x1 + 50 x2 + d -2 - d +2 = 1600
4 x1 + 3 x2 + d 3- - d 3+ = 120
d1+ d -4 d +4 = 10
x1 + d 5- = 30
x2 + d -6 = 20
x1, x2, d1- , d1+ d -2 , d +2 d 3- , d 3+ , d -4 , d +4 , d 5- , d 6- 0
16
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Graphical interpretation of Goal Programming
Since the goal programming models are linear, they
can be analyzed graphically.
The goal programming model formulated earlier
will be solved graphically in this section.
The goal programming model formulated is:
- - + +
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d1
Subject to
x1 + 2 x2 + d1- - d1+ = 40
40 x1 + 50 x2 + d -2 - d +2 = 1600
4 x1 + 3 x2 + d 3- - d 3+ = 120
x1, x2, d1- , d1+ d -2 , d +2 d 3- , d 3+ 0
To graph this model, first the deviational variables
in each goal constraint are set equal to zero.
Then we graph each equation on a set of
coordinates.
The following Figure 9.2 is a graph of the three goal
constraints for this model.
17
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Figure 9.1
Notice that in the above figure there is no feasible
solution space indicated as in regular LP model.
This is because all the three goal constraints are
equations; thus, all solution points are on the
constraint lines.
18
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
In attempting to solve this goal programming model,
we will attempt to achieve the goals in the objective
function in order of their priorities.
As a goal is achieved, the next highest-ranked goal
is then considered.
However, a higher-ranked goal that has been
achieved is never given up in order to achieve a
lower-ranked goal.
The first priority goal: Minimize d1- (avoid
underutilization of labor)
We first consider the First Priority goal of
minimizing d1- .
19
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
It is shown in Figure 9.2
Figure 9.2
The area below the goal constraint line x1 + 2x2 = 40
-
represents possible values for d1 , and the area above
+
the line represents values for d1 .
20
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
-
In order to achieve the goal of minimizing d1 , the
-
area below the constraint line corresponding to d1 is
eliminated.
This leaves the shaded area as a possible solution
area.
The second priority goal: Minimize d -2 (achieve
profit at least $1600)
Next we consider the second priority goal of
minimizing d -2 .
In the following Figure 9.3, the area below the
constraint line 40x1 + 50x2 = 1600 represents the
values for d -2 , and the area above the line represents
+
the values for d 2 .
To minimize d -2 , the area below the constraint line
-
corresponding to d 2 is eliminated.
Notice that, by eliminating the area for d -2 , we do not
-
affect the priority one goal of minimizing d1
21
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Figure 9.3
The third priority goal: Minimize d 3+ (avoid keeping
more than 120 pounds of clay)
22
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
+
Next the priority three goal of minimizing d 3 is
considered.
-
Figure 9.4 shows the areas corresponding to d 3 and
d 3+ .
Figure 9.4
+
To minimize d 3 , the area above the constraint line
4x1 + 3x2 = 120 is eliminated.
23
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
After considering the three goals, the possible
solution area left is the area between the line
segments AC and BC.
The fourth priority goal: Minimize d1+ (minimize
overtime)
To achieve this goal, the area above the constraint
line x1 + 2x2 = 40 must be eliminated.
However, if we eliminate this area, then both d -2 and
d 3- must take on values. In other words, we cannot
+
minimize d1 totally without violating the priority
one and two goals.
Therefore, we must find a solution point that
satisfies the first three goals but achieve as much of
the fourth priority goal as possible.
The fourth priority goal and solution shown in
Figure 9.5
24
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Figure 9.5
Point C in Figure 9.5 is the point that satisfies these
conditions.
Point A = (0, 32)
Point B = (0, 40)
Point C = (15, 20)
25
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Priority 4: minimize overtime: d1+ relate to
constraint 1:
- +
d -
Constraint 1: x1 + 2 x2 + 1 1 =d 40
0
+ -
At point A (0, 32): 0 + 2(32) + d - d 1 = 1 40
64 - d1+ = 40
d1+ = 24
- +
At point B (0, 40): 0 + 2(40) + d1 - d1 = 40
+
80 - d1 = 40
d1+ = 40
- +
d -
At point C (15, 20): 15 + 2(20) + 1 1 =d 40
55 - d1+ = 40
d1+ = 15 √
P1, P2 and P3 are achieved but P4 not achieve. Best
solution is at point C with x1 = 15, x2 = 20 and d1+
= 15
Notice that if we move down the goal constraint line
+
4x1 + 3x2 = 120 toward point D, d1 is further
-
minimized; however, d 2 takes on a value as we
+
d
move past point C. Thus, the minimization of 1
26
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
would be accomplished only at the expense of a
higher ranked goal.
The solution point C can be determined by
simultaneously solving the two equations that
intersect at this point.
Doing so gives us the following solution:
x1 = 15 bowls
x2 = 20 mugs
d1+ = 15 hours
- - +
d d d
Because the deviational variables 1 , 2 and 3 all
equals zero, they have been minimized and the first
three goals have been achieved.
+
Because d1 = 15 hours of overtime, the fourth
priority goal has not been achieved.
The solution to goal programming model such as
this one referred to as the most satisfactory solution
rather than optimal solution because it satisfies the
specified goals as well as possible.
27
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Goal programming solutions do not always achieve
all goals and they are not optimal, they achieve the
best or most satisfactory solution possible.
Example 9.2:
Expert Consultants has contracted to do a survey. The
firm must assign interviewers to carry out the survey.
The interviews are conducted by telephone and in
person. One person can conduct 80 telephone
interviews or 40 personal interviews in a day. An
interviewer will conduct only one type of interview on
a day. It costs RM50 per day for a telephone
interviewer and RM70 per day for a personal
interviewer. The following 3 goals which are listed in
order of their priority, have been established by the
firm to ensure a representative survey:
1. At least 3000 total interviews should be
conducted
2. the firm wants to maintain its daily budget of
RM2500
3. at least 1000 interviews should be by telephone.
Formulate a goal programming model to determine the
number of interviewers to hire to satisfy these goals
and solve the model graphically.
28
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Solution:
29
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Example 9.3:
A manufacturing company produces products 1, 2 and
3. At present the company has a daily labor capacity
of 240 hours and 400 pounds of raw material. The
products resource requirements and profit was given
in the following LP:
Maximize Z = 3 x 1 + 5 x2 + 2 x 3
Subject to 5 x1 + 2 x2 + 4 x3 240 (labor)
4 x1 + 6 x2 + 3 x3 400 (material)
x1, x2, x3 0
The company management has developed the
following set of goals, arranged in order of their
priority:
1. Management wants to avoid underutilization of
normal production capacity.
2. Management has established a satisfactory profit
level of RM500 per day.
3. Overtime is to minimized as much as possible.
4. Management wants to minimize the purchase of
additional materials to avoid handling and storage
problems.
30
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Formulate a goal programming model to determine the
number of each product to produce to best satisfy these
goals.
Solution:
31
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Computer Solution of Goal Programming
Problems: QM for Windows
In this section, we will see how goal programming
problem can be solved using “Goal Programming
Menu” in QM for windows.
Let us consider again the goal programming model
formulated in the previous section:
- - + +
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d1
Subject to
x1 + 2 x2 + d1- - d1+ = 40
40 x1 + 50 x2 + d -2 - d +2 = 1600
4 x1 + 3 x2 + d 3- - d 3+ = 120
x1, x2, d1- , d1+ d -2 , d +2 d 3- , d 3+ 0
The goal programming module in QM for Windows
can be selected by clicking at the “Module” button
at the top of the screen.
The model entered into data input screen as shown
below.
32
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
33
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
34
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Example 9.4:
Solve problem in Example 9.3 using QM for windows.
The goal programming model is:
35
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
36
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Computer Solution of Goal Programming
Problems: Excel Solver
In this section, we will see how goal programming
problem can be solved using Excel Solver.
Let us consider again the goal programming model
formulated in the previous section:
- - + +
Minimize P1 d1 , P2 d 2 , P3 d 3 , P4 d1
Subject to
x1 + 2 x2 + d1- - d1+ = 40
40 x1 + 50 x2 + d -2 - d +2 = 1600
4 x1 + 3 x2 + d 3- - d 3+ = 120
x1, x2, d1- , d1+ d -2 , d +2 d 3- , d 3+ 0
37
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
Exercise 9.1:
The Kota Setar Municipal Council has received a
federal grant of $600,000 to expand its public
recreation facilities. City council representatives have
demanded four different types of facilities –
gymnasiums, athletic fields, tennis courts and
swimming pools. In fact, the demand by various
communities in the city has been for 7 gyms, 10
athletic fields, 8 tennis courts and 12 swimming pools.
Each facility costs a certain amount, requires a certain
number of acres and is expected to be used by a certain
amount of people as follows:
Required Expected usage
Facility Cost ($)
Acres (people/week)
Gymnasium 80,000 4 1,500
Athletic field 24,000 8 3,000
Tennis court 15,000 3 500
Swimming
40,000 5 1,000
pool
38
Chapter 9: SQQP3083
------------------------------------------------------------------------------------------------------------
The Municipality has located 50 acres of land for
construction (although more land could be located if
necessary). The Municipality has established the
following goals, listed in order of their priority:
1. The Municipality wants to spend the total grant
given.
2. The Municipality wants the facilities to be used
by a total of at least 20,000 people each week.
3. The Municipality wants to avoid having to secure
more than the 50 acres of land already located.
4. The Municipality wants to meet the demands of
its communities. However, this goal should be
weighted according to the number of people
expected to use each facility.
Formulate a goal programming model for determining
how many of each type of facility should be
constructed to best achieve the Municipality’s goals.
39
