Goal Programming
Nico R. Penaredondo
MSICT
Goal Programming
▪ May be used to solve linear programs with multiple
objectives, with each objective viewed as a “goal”.
▪ The goals themselves are subtracted and added to
the constraint set with di+ and di– acting as the
surplus and slack variables
▪ A hierarchy of importance needs to be established
so that higher-priority goals are satisfied before
lower-priority goals are addressed
Goal Programming
▪ It is not always possible to satisfy every goal so
goal programming attempts to reach a
satisfactory level of multiple objectives
▪ The main difference is in the objective function
where goal programming tries to minimize the
deviations between goals and what we can
actually achieve within the given constraints
Goal Programming and Linear Programming
Differences
Differences between GP and LP
Goal Programming Linear Programming
Multiple Goals One Goal
Deviation Variables are Maximizing Profit /
minimized Minimizing Costs
Once the GP is formulated, we can solved it as the same as LP
minimization problem
Example Problem
Spade Hardware
▪The company produces two products popular with home
renovators, old-fashioned chandeliers and ceiling fans
▪Each chandelier produced nets the firm $7 and each fan $6
▪Both the chandeliers and fans require a two-step production
process involving wiring and assembly
▪It takes about 2 hours to wire each chandelier and 3 hours
to wire a ceiling fan
▪Final assembly of the chandeliers and fans requires 6 and 5
hours respectively
▪The production capability is such that only 12 hours of
wiring time and 30 hours of assembly time are available
LP Formulation
[Maximize Profit]
Z = 7x1 + 6x2
[Subject To]
2x1 + 3x2 <= 12 (Wiring Hours)
6x1 + 5x2 <= 30 (Assembly Hours)
x1,x2 >= 0
[Let]
x1 = # of chandeliers produced
x2 = # of ceiling fans produced
Spade Hardware
▪ Spade Hardware is moving to a new location and feels
that maximizing profit is not a realistic objective
▪ Management sets a profit level of $30 that would be
satisfactory during this period
▪ The goal programming problem is to find the production
mix that achieves this goal as closely as possible given
the production time constraints
▪ We need to define two deviational variables
di– = underachievement of the profit target
di+ = overachievement of the profit target
List of Goals
Space’s management wants to achieve several goals of
equal in priority
Goal 1: To produce a profit of $30 if possible during
the production period
Goal 2: To fully utilize the available wiring
department hours
Goal 3: To avoid overtime in the assembly
department
Goal 4: To meet a contract requirement to produce
at least seven ceiling fans
Deviation Variables
d1– = underachievement of the profit target
d1+ = overachievement of the profit target
d2– = idle time in the wiring department (underutilization)
d2+ = overtime in the wiring department (overutilization)
d3– = idle time in the assembly department (underutilization)
d3+ = overtime in the assembly department (overutilization)
d4– = underachievement of the ceiling fan goal
d4+ = overachievement of the ceiling fan goal
Because management is unconcerned about d1+, d2+, d3–, and d4+
these may be omitted from the objective function
GP Model
[Minimize Total Deviation]
d1– + d2– + d3+ + d4–
[Subject To]
7x1 + 6x2 + d1– – d1+ = 30 (Profit Constraint)
2x1 + 3x2 + d2– – d2+ = 12 (Wiring Hours)
6x1 + 5x2 + d3– – d3+ = 30 (Assembly Hours)
x2 + d4– – d4+ = 7 (Ceiling Fan Constraint)
All xi,di variables >= 0
Ranking Goals with Priority Levels
▪In most goal programming problems, one goal will be more
important than another, which will in turn be more important
than a third
▪Goals can be ranked with respect to their importance in
management’s eyes
▪Higher-order goals are satisfied before lower-order goals
▪Priorities (Pi’s) are assigned to each deviational variable
with the ranking so that P1 is the most important goal, P2 the
next most important, P3 the third, and so on
Ranking Goals with Priority Levels
Goal Priority
Reach a profit as much above $30 as possible P1
Fully use wiring department hours available
P2
Avoid assembly department overtime
P3
Purchase at least seven ceiling fans
P4
Minimize total deviation = P1d1– + P2d2– + P3d3+ + P4d4–
3 Characteristics of GP Problems
1. Goal programming models are all minimization
problems
2. There is no single objective, but multiple goals to be
attained
3. The deviation from the high-priority goal must be
minimized to the greatest extent possible before the
next-highest-priority goal is considered
Recalling GP Model
[Minimize Total Deviation]
P1d1– + P2d2– + P3d3+ + P4d4–
[Subject To]
7x1 + 6x2 + d 1– – d1+ = 30 (Profit Constraint)
2x1 + 3x2 + d 2– – d2+ = 12 (Wiring Hours)
6x1 + 5x2 + d 3– – d3+ = 30 (Assembly Hours)
x2 + d 4– – d4+ = 7 (Ceiling Fan Constraint)
All xi,di variables >= 0
Solving GP Problems
Graphically
First Goal Analysis
X2
7– Minimize Z = P1d1–
6–
5–
4–
3–
2–
1– d1– 7X1 + 6X2 = 30
0– | | | | | |
1 2 3 4 5 6 X1
First Goal and Second Goal Analysis
X2
7– Minimize Z = P1d1– + P2d2–
6–
5–
4–
3–
2X1 + 3X2 = 12
2–
d2+
1–
7X1 + 6X2 = 30 d2–
0– | | | | | |
1 2 3 4 5 6 X1
All four priority goals analysis
X2
d4+
7– X2 = 7
d4–
6 –A Minimize Z = P1d1– + P2d2– + P3d3– + P4d4–
d3+
5 –D
d3–
4–
d1+
3–
d2+ 6X1 + 5X2 = 30
C
2–
B
2X1 + 3X2 = 12
1–
7X1 + 6X2 = 30
0– | | | | | |
1 2 3 4 5 6
X1
Solving GP Problems Graphically
▪ The optimal solution must satisfy the first three goals and come as
close as possible to satisfying the fourth goal
▪ This would be point A on the graph with coordinates of X1 = 0 and
X2 = 6
▪ Substituting into the constraints we find
d1– = $0 d1+ = $6
d2– = 0 hours d2+ = 6 hours
d3– = 0 hours d3+ = 0 hours
d4– = 1 ceiling fan d4+ = 0 ceiling fans
A profit of $36 was achieved
exceeding the goal
Thanks!
Goal Programming
Nico Penaredondo
MSICT
