Topic: Goal Programming

The idea of goal programming is to express our goals in a prioritized list. We identify a
target for each goal, and we state whether or not we should penalize deviations that are above
or below the target. Then, we either use dedicated software, or we solve a series of linear
programming problems, to find the solution that comes closest to meeting our goals.

To illustrate, recall an example that we spoke about in the beginning of the class, where the
Beaver Creek Pottery Company is a small crafts company that produces bowls and mugs.
Each day, they have 120 lb of clay and 40 hours of labor available. The profit and resource
requirements for each product are summarized below.

Resources Requirements
Labor Clay Profit
Product (hr/unit) (lb/unit) ($/unit)
Bowl 1 4 40
Mug 2 3 50

The LP model we developed for Beaver Creek Pottery is summarized below. Recall that
𝑥 = number of bowls and 𝑥 = number of cups.

Maximize 𝑍 = 40𝑥 + 50𝑥

subject to 𝑥 + 2𝑥 ≤ 40 (Labor)
4𝑥 + 3𝑥 ≤ 120 (Clay)
𝑥 ,𝑥 ≥ 0

This problem, like all LP problems we have studied, has certain properties.

 There is a clearly defined objective. We want to maximize profit, which we have

expressed as a linear function of our variables.
 There are a set of linear constraints that represent restrictions that must be met. These
are not soft goals or requirements; they are hard limits that must be satisfied.

In some applications, the objectives and constraints are not as clearly defined. Suppose that,
unlike the original problem statement, Beaver Creek has given us several goals that it would
like to achieve in order of priority.

1. To avoid layoffs, they would like to use no fewer than 40 hours of labor per day.
2. They would like profit to be at least $1600.
3. Due to limited storage space, they want to store no more than 120 pounds of clay.

Here is the difference between Goal #1 and the labor constraint in the LP model.

LP Constraint: We can never use over 40 hours of labor.

Goal #1: We prefer to use at least 40 hours of labor.

Here is the difference between Goal #2 and the objective function in the LP model.

LP Objective: Maximize profit.

Goal #2: We prefer at least $1600 profit (but we are not necessarily trying to make
 it as large as possible.)

In order to use goal programming, we need to allow for deviations above and below the target
value.

 We use the notation 𝑑 to represent the amount that we are over Target i.
 We use the notation 𝑑 to represent the amount that we are under Target i.
 We will always have either 𝑑 = 0, 𝑑 = 0, or both (if we hit target exactly).

For example, we can write out the first goal as follows.

𝑥 + 2𝑥 = 40 − 𝑑 + 𝑑 (Labor Goal)

If we are at the point (𝑥 , 𝑥 ) = (5,10), what would the deviations be?

𝑥 + 2𝑥 = 𝑑 = 𝑑 =

If we are at the point (𝑥 , 𝑥 ) = (10,20), what would the deviations be?

𝑥 + 2𝑥 = 𝑑 = 𝑑 =
Similarly, we could write out the other two goals as follows.

40𝑥 + 50𝑥 = 1600 − 𝑑 + 𝑑 (Profit Goal)

4𝑥 + 3𝑥 = 120 − 𝑑 + 𝑑 (Clay Goal)

How to set up our priorities:

Recall that the first priority was to use no fewer than 40 hours of labor.

𝑥 + 2𝑥 = 40 − 𝑑 + 𝑑 (Labor Goal)

In our goal program, our first priority is to minimize the hours below 40. That is,

1st Priority: Minimize

This is denoted as 𝑃 𝑑 . The subscript of P indicates which priority we are discussing (𝑃 =

first priority). After 𝑃 , we list which deviation is top priority.

Recall that the second priority was to have a profit of at least 1600.

40𝑥 + 50𝑥 = 1600 − 𝑑 + 𝑑 (Profit Goal)

Which deviation should be minimized as our second priority?

2nd Priority: Minimize

This is denoted by 𝑃 𝑑 . Our third priority was to store no more than 120 pounds of clay.

4𝑥 + 3𝑥 = 120 − 𝑑 + 𝑑 (Clay Goal)

In our goal program, which deviation would we want to penalize as our third priority?

3rd Priority: Minimize

This is denoted by 𝑃 𝑑 .

Therefore, our entire objective is to minimize 𝑃 𝑑 , 𝑃 𝑑 , 𝑃 𝑑 .

Problem 2:

We will use the following variables.

𝑥 = # Nurse Hours
𝑥 = # GP Hours
𝑥 = # Internist Hours

𝑑 = deviation above Target j

𝑑 = deviation below Target j

a. Set up the goal programming constraints for this problem, with the deviations on the
RHS.

Nurse Target:

Budget Target:

GP/Internist Target:

Internist Target:

b. Write out the complete goal programming problem, where the constraints have all
variables on the LHS.

Objective:
Subject to

(Nurse Target)

(Budget Target)

(GP/Internist Target)

(Internist Target)

(Variable Restrictions)

Problem 3:
A small furnishing company manufactures tables and chairs. Each chair requires 4 man-hours
of labour while each table requires 5 man-hours of labour. If only 80 man-hours are available
each week and the owner of the company would neither hire additional labour nor utilize
overtime. Formulate the goal programming problem. Both the table and chair fetch a profit of
Rs. 100 each. The owner has a target to earn a profit of Rs. 2000 per week. Also he would
like to supply 10 chairs, if possible, per week to a sister concern.
Solve the following GP by modified simplex method
Problem 3:

Solution:
We will use the following variables.

𝑥 =#
𝑥 =#

𝑑 = deviation above Target j

𝑑 = deviation below Target j

Set up the goal programming constraints for this problem, with the deviations on the LHS.

(Objective)

(Profit goal)

(assembly constraint)

(Finishing constraint)

Standard Form:
 Initial Table

Cj 0 0 0 0 1 0

CB B XB X1 X2 S1 S2 𝑑 𝑑 ER

1 𝑑 2100 120 90 0 0 1 -1

0 S1 90 6 3 1 0 0 0

0 S2 72 3 6 0 1 0 0

Zj 120 90 0 0 1 -1

Cj - Zj -120 -90 0 0 0 1

1st Improved Table

1 𝑑 300 0 30 -20 0 1 -1

0 X1 15 1 1/2 1/6 0 0 0

0 S2 27 0 9/2 -1/2 1 0 0

Zj 0 30 -20 0 1 -1

Cj - Zj 0 -30 20 0 0 1

2nd Improved Table

1 𝑑 120 0 0 -50/3 -20/3 1 -1

0 X1 12 1 0 2/9 -1/9 0 0

0 X2 6 0 1 -1/9 2/9 0 0

Zj 0 0 -50/3 -20/3 1 -1

Cj - Zj 0 0 50/3 20/3 0 1
Optimal Solution:
𝑑 = 120 means that the target profit of Rs. 2100/- is underachieved by Rs. 120/-
i.e. profit actually earned by manufacturing x1=12(Radios), x2=6(transistors) is Rs. 2100 –
Rs. 120 = 1980/- (=120*12+90*6)

Set up the goal programming constraints for this problem, with the deviations on the LHS.

(Objective)

(Profit goal)

(radio goal)

(assembly constraint)

(Finishing constraint)

Standard Form:
 Initial Table

Cj 0 0 0 0 1 0 1 0

CB B XB X1 X2 S1 S2 𝑑 𝑑 𝑑 𝑑

1 𝑑 1500 120 90 0 0 1 -1 0 0

1 𝑑 10 1 0 0 0 0 0 1 -1

0 S1 90 6 3 1 0 0 0 0 0

0 S2 72 3 6 0 1 0 0 0 0

Zj 121 90 0 0 1 -1 1 -1

Cj -Zj -121 -90 0 0 0 1 0 1

1st Improved Table

1 𝑑 300 0 90 0 0 1 -1 -120 120

0 X1 10 1 0 0 0 0 0 1 -1

0 S1 30 0 3 1 0 0 0 -6 6

0 S2 42 0 6 0 1 0 0 -3 3

Zj 0 90 0 0 1 -1 -120 120

Cj -Zj 0 -90 0 0 0 1 121 -120

2nd Improved Table

0 𝑑 5/2 0 ¾ 0 0 1/120 -1/120 -1 1

0 X1 25/2 1 ¾ 0 0 1/120 -1/120 0 0

0 S1 15 0 -3/2 1 0 -1/20 1/20 0 0

 0 S2 69/2 0 15/4 0 1 -1/40 1/40 0 0

Zj 0 0 0 0 0 0 0 0

Cj -Zj 0 0 0 0 1 0 1 0

Optimal Solution: 𝑑 = 0, 𝑑 = 0,

Goal of 10 radios is achieved and in fact we have better solution [as (x1=)25/2-10 = 5/2, i.e.
𝑑 = 5/2 overachievement of radios].
Profit goal of Rs. 1500/- is achieved exactly as 𝑑 = 0, 𝑑 = 0.

Set up the goal programming constraints for this problem, with the deviations on the LHS.

(Objective)

(Profit goal)

(radio goal)

(transistor goal)

(assembly constraint)

(Finishing constraint)
Standard Form:

Initial Table

Cj 0 0 0 0 P2 0 P1 0 P3 0

CB B XB X1 X2 S1 S2 𝑑 𝑑 𝑑 𝑑 𝑑 𝑑 ER

P2 𝑑 1950 120 90 0 0 1 -1 0 0 0 0

P1 𝑑 13 1 0 0 0 0 0 1 -1 0 0

P3 𝑑 5 0 1 0 0 0 0 0 0 1 -1

0 S1 90 6 3 2 0 0 0 0 0 0 0

0 S2 72 3 6 0 1 0 0 0 0 0 0

Zj 0 1 0 0 0 0 0 0 1 -1

P3 Cj - Zj 0 -1 0 0 0 0 0 0 0 1

Zj 120 90 0 0 1 -1 0 0 0 0

P2 Cj - Zj -120 -90 0 0 0 1 0 0 0 0

Zj 1 0 0 0 0 0 1 -1 0 0

P1 Cj - Zj -1 0 0 0 0 0 0 1 0 0
1st Improved Table

2nd Improved Table

3rd Improved Table