QBUS6820 – Prescriptive Analytics
Week 10
• Goal Programming
Introduction
• Most of the optimisation problems considered to this
point have had a single objective.
• Often, more than one objective/goal can be identified for
a given problem.
- Maximise Return or Minimise Risk
- Maximise Profit or Minimise Pollution
• These objectives often conflict with one another.
• This lecture looks at how we deal with such problems.
Goal Programming (GP)
• Most LP problems have hard constraints that cannot be
violated.
- There are 1,566 labor hours available.
- There is a budget of $850,000 available for projects.
• In some cases, hard constraints are too restrictive.
- You have a maximum price in mind when buying a car (this is
your “goal” or target price).
- If you can’t buy the car for this price, there’s a reasonable
chance that you’ll try to find a way to increase your budget.
• We use soft constraints to represent such goals or targets we’d
like to achieve.
Goal Programming Example
• Imagine a client wants to expand a conference center at a
hotel
• The types of conference rooms being considered are:
Size (sq ft) Unit Cost
Small 400 $18,000
Medium 750 $33,000
Large 1,050 $45,150
• They would like to add 5 small, 10 medium, and 15 large
conference rooms.
• They also want the total expansion to be 25,000 square
feet and to limit the cost to $1,000,000.
Defining the Decision Variables
X1 = number of small rooms to add
X2 = number of medium rooms to add
X3 = number of large rooms to add
• Goal 1: The expansion should include approximately 5
small conference rooms.
• Goal 2: The expansion should include approximately 10
medium conference rooms.
• Goal 3: The expansion should include approximately 15
large conference rooms.
• Goal 4: The expansion should consist of approximately
25,000 square feet.
• Goal 5: The expansion should cost approximately
$1,000,000.
Defining the Goals
• We will introduce a set of decision variables called
deviational variables:
• Represent positive and negative deviations from each goal.
One will always take on a value of zero in the solution.
• We require 2 deviational variables for each goal because
we need all the deviational variables to be non-negative.
• Here the index i refers to the relevant goal constraint, not
the decision variables.
Introducing Deviational Variables
ui = the amount we underachieve goal ioi = the amount we overachieve goal i
Small Rooms
Medium Rooms
Large Rooms
Where:
1 + ! − ! = 5
2 + # − # = 10
3 + $ − $ = 15
% , % ≥ 0
Defining the Goal Constraints
Total Expansion
Total Cost (in $1,000s)
Where:
4001 + 7502 + 1,0503 + & − & = 25,000
181 + 332 + 45.153 + ' − ' = 1,000
% , % ≥ 0
Defining the Goal Constraints
There are numerous objective functions we could
formulate for a GP problem.
Should we minimise the sum of the deviations?
Problem:
•The deviations measure different things, so
what does this objective represent?
F% % + %
Defining the GP Objective Functions
Minimise the sum of percentage deviations
where ti represents the target value of goal i
Problem:
Suppose the first goal is underachieved by 1 small room
and the fifth goal is overachieved by $20,000.
• We underachieve goal 1 by 1/5=20%
• We overachieve goal 5 by 20,000/1,000,000 = 2%
• Does this imply being $200,000 over budget is just
as undesirable as having one less small room?
F% 1% % + %
Defining the GP Objective Functions
Weights can be used in the previous objectives to
allow the decision maker to indicate:
• desirable vs. undesirable deviations
• the relative importance of various goals
Minimise the weighted sum of deviations
Minimise the weighted sum of % deviations
F% % % + % %
F% 1% % % + % %
Defining the GP Objective Functions
Assume:
• It is undesirable to underachieve any of the first three
room goals
• It is undesirable to overachieve or underachieve the
25,000 sq ft expansion goal
• It is undesirable to overachieve the $1,000,000 total
cost goal
If you’re unsure about the weights, to start you can
assume all the weights equal 1.
Defining the Objective
(! ' ! + (# !) # + ($ !' $ + (% #',)))& + +% #',)))& + +& !,))),)))'
• GP involves making trade-offs among the goals until
the most satisfying solution is found.
• GP objective function values should not be
compared because the weights are changed in each
iteration. Compare the solutions!
• An arbitrarily large weight will effectively change a
soft constraint to a hard constraint.
• Hard constraints can be placed on deviational
variables.
Comments about Goal Programming
The original formulation was:
Maximise Z = 40x1 + 50x2
Subject to:
1x1 + 2x2 £ 40 hours of labor
4x1 + 3x2 £ 120 pounds of clay
x1, x2 ³ 0
Where: x1 = number of bowls produced
x2 = number of mugs produced
GP Example – Pottery Company
Adding objectives (goals) in order of importance, the
company…
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 minimise the amount of overtime.

GP Example – Pottery Company
• All goal constraints are equalities that include deviational
variables.
• The objective function seeks to minimise the deviation
from the respective goals in the order of the goal
priorities.
GP Example – Pottery Company
Labor goal:
x1 + 2x2 + u1 - o1 = 40 (hours/day)
Profit goal:
40x1 + 50x2 + u2 - o2 = 1,600 ($/day)
Material goal:
4x1 + 3x2 + u3 - o3 = 120 (lbs of clay/day)
Goal Programming – Model Formulation
1. Labor goals constraint (priority 1 – no less than 40 hours
labor; priority 4 - minimum overtime):
Minimise w1u1 + v1o1
2. Add profit goal constraint (priority 2 - achieve profit of
$1,600)
Minimise w1u1 + w2u2 + v1o1
3. Add material goal constraint (priority 3 - avoid keeping more
than 120 pounds of clay on hand):
Minimise w1u1+ w2u2 + v3o3 + v1o1
Goal Programming – Model Formulation
Complete GP Model:
Minimise w1u1+ w2u2 + v3o3 + v1o1
Subject to:
x1 + 2x2 + u1 - o1 = 40 (labor)
40x1 + 50x2 + u2 - o2 = 1,600 (profit)
4x1 + 3x2 + u3 - o3 = 120 (clay)
xi, ui, oi ³ 0 for all i
with w1 > w2 > v3 > v1
Goal Programming – Model Formulation
• Goal programming solutions do not always achieve all goals
nor are they optimal.
• They achieve the best solution possible given goal priorities.
Goal Programming - Result Interpretation
The MiniMax Objective
Can be used to minimise the maximum deviation from any goal.
Mathematically we’re looking to do this: min maxi {vioi/ti , wiui/ti}
How do we implement this in GP?
Objective Function: Min α
Constraints:
vioi/ti ≤ α
wiui/ti ≤ α
+ other relevant constraints
The MiniMax Objective
For the hotel expansion example how would you recast the goal
program using minimax percentage deviations?
Objective Function: Min α
Constraints:
Those on slides 8 and 9 +
all weighted percentage deviations <= α, i.e.
vioi/ti <= α
wiui/ti <= α
For i = 1,…,5
where wi and vi > 0
Summary of Goal Programming
1. Identify the decision variables in the problem.
2. Identify any hard constraints in the problem and
formulate them in the usual way.
3. State the goals of the problem along with their target
values.
4. Create constraints using the decision variables that
would achieve the goals exactly.
5. Transform the above constraints into goal constraints
by including deviational variables.
6. Determine which deviational variables represent
undesirable deviations from the goals.
7. Formulate an objective that penalises the undesirable
deviations.
8. Identify appropriate weights for the objective.
9. Solve the problem.
10. Inspect the solution to the problem. If the solution
is unacceptable, return to step 8 and revise the
weights as needed.
Summary of Goal Programming
End of lecture
Questions?