Goal Programming

Introduction
 Firms often have more than one goal
Production Planning: Max Profit/Max Market Share
Location Selection: Max Sales/Min Delivery Cost
Personal Schedule: Max GPA/Max Income

 In linear and integer programming, the objective function is

measured in one dimension only
 Goal Programming (GP) is developed to supplement LP
 Typically goals set by management can be achieved only
at the expense of other goals
 Establish a hierarchy of importance so that higher-priority
goals are satisfied before lower-priority goals
Introduction
 Not always possible to satisfy every goal
 GP attempts to reach a satisfactory level of multiple
objectives (may not optimize but have to satisfice)
 Main difference is in the objective function
 GP tries to minimize the deviations between goals and
what can be achieved given the constraints (to minimize
deviational variables)
Formulation
 In GP, di+ and di- are deviation variables
 Deviation variables are the amounts a targeted goal i is
overachieved (di+ ≥ 0) or underachieved (di- ≥ 0), respectively

 Desirable vs. Undesirable Deviations:

 Max goals (≥) : the more the better, di+ desirable.
 Min goals (≤) : the less the better, di- desirable.
 Exact goals (=) : exactly equal, both di+ and di- are undesirable

 In GP, the objective is to minimize the weighted sum of

undesirable deviations (all undesirable di+ and di- → 0)
Formulation
 For each goal, at least, one of di+ and di- must be equal to
"0"
 The goals are subtracted and added with di+ and di- (acting
as the surplus an slack variables) before adding them to
the constraint set
 Goals are prioritized in some sense, and their level of
aspiration is stated
 An optimal solution is attained when all the goals are
reached as close as possible to their aspiration level, while
satisfying a set of constraints
Example 1 (1 of 7)

CP Company produces two models of computers, CP400 and CP500.

The computers use different mother boards produced in abundant supply
by the company, but use the same cases and disk drives. CP400 model
uses 2 floppy disk drives and no zip disk drive. However, CP500 model
uses 1 floppy disk drive and one zip disk drive.

The disk drives and cases are bought from vendors. There are 1000
floppy disk drives, 500 zip disk drives, and 600 cases available to CP
Company on weekly basis.
Example 1 (2 of 7)

It takes one hour to manufacture a CP400 and its profit is $200. On the
other hand, it takes one-half hours to manufacture CP500 and its profit is
$500. The company has the following four goals:

1. Produce at least 200 CP400 computers/week

2. Produce at least 500 total computers/week
3. Reach at least $250,000 on profit
4. Consume no more than 400 total man-hours each week
Example 1 (3 of 7)

 Variables:
x1: # CP400 computers produced/week
x2: # CP500 computers produced/week
di- : amount the right hand side of goal i is deficient
di+ : amount the right hand side of goal i is exceeded

 Functional Constraints

2 x1 + x2 ≤ 1000
x2 ≤ 500
x1 + x2 ≤ 600
Example 1 (4 of 7)

 Goal Constraints
1. Produce at least 200 CP400 computers/week
x1 ≥ 200 x1 + d1- - d1+ = 200

2. Produce at least 500 total computers/week

x1 + x2 ≥ 500 x1 + x2 + d2- - d2+ = 500
LP

GP
3. Reach at least $250,000 on profit
200 x1 + 500 x2 ≥ 250,000 200 x1 + 500 x2 + d3- - d3+ = 250,000

4. Consume no more than 400 total man-hours each week

x1 + 0.5 x2 ≤ 400 x1 + 0.5 x2 + d4- - d4+ = 400
Example 1 (5 of 7)

 Non-negativity x1, x2, di-, di+ ≥ 0 for all i

 Formulation
2 x1 + x2 ≤ 1000
x2 ≤ 500
x1 + x2 ≤ 600

x1 + d1- - d1+ = 200

x1 + x2 + d2- - d2+ = 500
200 x1 + 500 x2 + d3- - d3+ = 250,000
x1 + 0.5 x2 + d4- - d4+ = 400

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+, d4-, d4+ ≥ 0

 Objective Function??
Example 1 (6 of 7)

 Goals
1. Produce at least 200 CP400 computers/week (undesirable: d1-)
2. Produce at least 500 total computers/week (undesirable: d2-)
3. Reach at least $250,000 on profit (undesirable: d3-)
4. Consume no more than 400 total man-hours each week
(undesirable: d4+)
Example 1 (7 of 7)

 Formulation

Min p1 (d1-) + p2 (d2-) + p3 (d3-) + p4 (d4+)

s.t.
2 x1 + x2 ≤ 1000
x2 ≤ 500
x1 + x2 ≤ 600

x1 + d1- - d1+ = 200

x1 + x2 + d2- - d2+ = 500
200 x1 + 500 x2 + d3- - d3+ = 250,000
x1 + 0.5 x2 + d4- - d4+ = 400

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+, d4-, d4+ ≥ 0
Example 2 (1 of 6)
An advertising company is considering the following three forms of
advertising.

Cost per Ad Customers

Television 3000 1000
Radio 800 500
Newspaper 250 200

The company has the following three goals:

1. Spend no more $25,000 on advertising
2. Reach at least 30,000 new potential customers
3. Run at least 10 television spots
Example 2 (2 of 6)

 Variables:
x1: # of purchased Television Ads
x2: # of purchased Radio Ads
x3: # of purchased Newspaper Ads

di- : amount the right hand side of goal i is deficient

di+ : amount the right hand side of goal i is exceeded

 Functional Constraints (N/A)

 Example 2 (3 of 6)

 Goal Constraints
1. Spend no more $25,000 on advertising
3000 x1 + 800 x2 + 250 x3 ≤ 25,000 3000 x1 + 800 x2 + 250 x3 + d1- - d1+ = 25,000

2. Reach at least 30,000 new potential customers

x1 + 500 x2 + 200 x3 ≥ 30,000 x1 + 500 x2 + 200 x3 + d2- - d2+ = 30,000

GP
LP

1000 1000

3. Run at least 10 television spots

x1 ≥ 10 x1 + d3- - d3+ = 10
Example 2 (4 of 6)

 Non-negativity x1, x2, x3, di-, di+ ≥ 0 for all i

 Formulation
3000 x1 + 800 x2 + 250 x3 + d1- - d1+ = 25,000

1000 x1 + 500 x2 + 200 x3 + d2- - d2+ = 30,000

x1 + d3- - d3+ = 10

x1, x2, x3, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

Example 2 (5 of 6)

 Objective Function? Penalties are estimated as follows:

 Each extra dollar spent on advertisement above $25,000 cost the company $1
 There is a loss of $5 to the company for each customer not being reached, below the goal of
30,000
 Each television spot below 10 is worth 100 times each dollar over budget

 Goals
1. Spend no more $25,000 on advertising (undesirable: d1+)
2. Reach at least 30,000 new potential customers (undesirable: d2-)
3. Run at least 10 television spots (undesirable: d3-)
Example 2 (6 of 6)

 Formulation

Min 1 (d1-) + 5 (d2-) + 100 (d3-)

s.t.

3000 x1 + 800 x2 + 250 x3 + d1- - d1+ = 25,000

1000 x1 + 500 x2 + 200 x3 + d2- - d2+ = 30,000

x1 + d3- - d3+ = 10

x1, x2, x3, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

Example 3 (1 of 5)

ZX Company manufactures two products, A, and B. Product A requires

five hours on machine 1 and two hours on machine 2; product B
requires two hours on machine 1 and four hours on machine 2. The
weekly capacities are 50 hours and 48 hours for machine 1 and 2,
respectively. The company has the following three goals:
Example 3 (2 of 5)
 Variables:
x1: # of Product A manufactured/week
x2: # of Product B manufactured/week
di- : amount the right hand side of goal i is deficient
di+ : amount the right hand side of goal i is exceeded

 Functional Constraints

5 x1 + 2 x2 ≤ 50
2 x1 + 4 x2 ≤ 48
 Example 3 (3 of 5)

 Goal Constraints
1. Total production of 10 units/week
x1 + x2 ≥ 10 x1 + x2 + d1- - d1+ = 10

2. Production of 8 units of Product A /week

x1 ≥ 8 x1 + d2- - d2+ = 8

GP
LP

3. Production of 13 units of Product B /week

x2 + ≥ 13 x2 + d3- - d3+ = 13
Example 3 (4 of 5)

 Non-negativity x1, x2, di-, di+ ≥ 0 for all i

 Formulation
5 x1 + 2 x2 ≤ 50
2 x1 + 4 x2 ≤ 48
x1 + x2 + d1- - d1+ = 10
x1 + d2- - d2+ =8
x2 + d3- - d3+ = 13

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

 Objective Function ??

(undesirable*: d1-)
(undesirable*: d2-)
(undesirable*: d3-)
Example 3 (5 of 5)
 Formulation

Min z = p1 (d1-) + p2 (d2-) + p3 (d3-)

s.t.
5 x1 + 2 x2 ≤ 50
2 x1 + 4 x2 ≤ 48

x1 + x2 + d1- - d1+ = 10
x1 + d2- - d2+ = 8
x2 + d3- - d3+ = 13

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+ ≥ 0

Example 4 (1 of 10)

A customer of an advertising agency has identified three primary target

audiences they are trying to reach. The advertising agency has been
allocated a budget of $600,000 and has the following three goals to
satisfy.
1. Ads should be seen by at least 40 million High-Income Men (HIM)
2. Ads should be seen by at least 60 million Low-Income People (LIP)
3. Ads should be seen by at least 35 million High-Income Women (HIW)

Agency recognizes that advertising during football games and soap

opera will reach the target audiences as shown next.
HIM LIP HIW Cost

Football Ad (/min) 7 million 10 million 5 million $ 100,000

Soap Opera (/min) 3 million 5 million 4 million $ 60,000

Example 4 (2 of 10)

 Variables:
x1 : # minutes of Football Ad
x2 : # minutes of Soap Opera Ad
di- : amount the right hand side of goal i is deficient
di+ : amount the right hand side of goal i is exceeded

 Functional Constraints

100 x1 + 60 x2 ≤ 600
 Example 4 (3 of 10)

 Goal Constraints
1. Ads should be seen by at least 40 million HIM

7 x1 + 3 x2 ≥ 40 7 x1 + 3 x2 + d1- - d1+ = 40

2. Ads should be seen by at least 60 million LIP

10 x1 + 5 x2 ≥ 60 10 x1 + 5 x2 + d2- - d2+ = 60

GP
LP

3. Ads should be seen by at least 35 million HIW

5 x1 + 4 x2 ≥ 35 5 x1 + 4 x2 + d3- - d3+ = 35
Example 4 (4 of 10)

 Non-negativity x1, x2, di-, di+ ≥ 0 for all i

 Formulation
100 x1 + 60 x2 ≤ 600
7 x1 + 3 x2 + d1- - d1+ = 40

10 x1 + 5 x2 + d2- - d2+ = 60
5 x1 + 4 x2 + d3- - d3+ = 35

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

 Objective Function ??
Example 4 (5 of 10)

 Objective Function?
Suppose each shortfall of 1 Million viewers from the goal translates to the following costs

HIM LIP HIW

Cost (short of 1 Million viewers) $ 200,000 $ 100,000 $ 50,000

 Goals
1. Ads should be seen by at least 40 million HIM (undesirable: d1-)
2. Ads should be seen by at least 60 million LIP (undesirable: d2-)
3. Ads should be seen by at least 35 million HIW (undesirable: d3-)
Example 4 (6 of 10)

 Formulation
Min z = 200 d1- + 100 d2- + 50 d3-
s.t.
100 x1 + 60 x2 ≤ 600
7 x1 + 3 x2 + d1- - d1+ = 40

10 x1 + 5 x2 + d2- - d2+ = 60
5 x1 + 4 x2 + d3- - d3+ = 35

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

Example 4 (7 of 10)

In this example, the goals could be weighted by relative importance using

given cost penalties
HIM LIP HIW

Cost (short of 1 Million viewers) $ 200,000 $ 100,000 $ 50,000

In many cases, the “weighting” of a goal is not easily determined; however, the
goals can be ranked from most important to least important. In this case, the
most important goal pre-empts all the other goals. Once the most important goal
is met, the second important goal is addressed, and etc..
Example 4 (8 of 10)

Suppose in the advertising example, HIM goal must be met first, followed
by LIP, and then HIW.
Min z = d1-
s.t.
100 x1 + 60 x2 ≤ 600
7 x1 + 3 x2 + d1- - d1+ = 40

10 x1 + 5 x2 + d2- - d2+ = 60
5 x1 + 4 x2 + d3- - d3+ = 35

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

Solution: z = 0 = d1- So HIM goal is met

Example 4 (9 of 10)

Since the HIM goal is met, now make goal HIM a fixed constraint while
trying to satisfy LIP
Min z = d2-
s.t.
100 x1 + 60 x2 ≤ 600
7 x1 + 3 x2 + d1- - d1+ = 40

10 x1 + 5 x2 + d2- - d2+ = 60
5 x1 + 4 x2 + d3- - d3+ = 35
d1- = 0

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

Solution: z = 0 = d2- So LIP goal is met

Example 4 (10 of 10)

Since both HIM and LIP goals are met, make them both fixed constraints
while trying to satisfy HIW
Min z = d3-
s.t.
100 x1 + 60 x2 ≤ 600
7 x1 + 3 x2 + d1- - d1+ = 40

10 x1 + 5 x2 + d2- - d2+ = 60
5 x1 + 4 x2 + d3- - d3+ = 35
d1- = 0
d2- = 0

x1, x2, d1-, d1+, d2-, d2+, d3-, d3+≥ 0

GP Models
 There are two types:
I. Non-preemptive GP - no goal is pre-determined to dominate any
other goal
II. Preemptive GP - level 1 goal dominates level 2 goal, and etc..