Chapter 11

Integer Programming
and Goal Programming

To accompany
Quantitative Analysis for Management, Tenth Edition,
by Render, Stair, and Hanna
Power Point slides created by Jeff Heyl

2008 Prentice-Hall, Inc.

2009 Prentice-Hall, Inc.

Introduction
A large number of business problems can be

solved only if variables have integer values

We will solve integer programming problems
graphically and by using the branch and bound
method
Many business problems have multiple objectives
Goal programming is an extension to LP that can
permit multiple objectives

2009 Prentice-Hall, Inc.

11 2

Integer Programming
An integer programming model is one where one

or more of the decision variables has to take on

an integer value in the final solution
There are three types of integer programming
problems
1. Pure integer programming where all variables
have integer values
2. Mixed-integer programming where some but
not all of the variables will have integer
values
3. Zero-one integer programming are special
cases in which all the decision variables must
have integer solution values of 0 or 1
2009 Prentice-Hall, Inc.

11 3

Harrison Electric Company Example of

Integer Programming
The Company produces two products popular

with home renovators, old-fashioned chandeliers

and ceiling fans
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
2009 Prentice-Hall, Inc.

11 4

Harrison Electric Company Example of

Integer Programming
Each chandelier produced nets the firm $7 and

each fan $6
Harrisons production mix decision can be
formulated using LP as follows

Maximize profit = $7X1 + $6X2

subject to
2X1 + 3X2 12 (wiring hours)
6X1 + 5X2 30 (assembly hours)
X1, X2 0 (nonnegative)
where
X1 = number of chandeliers produced
X2 = number of ceiling fans produced
2009 Prentice-Hall, Inc.

11 5

Harrison Electric Company Example of

Integer Programming
The Harrison

Electric
Problem

X2
6
5
6X1 + 5X2 30

+ = Possible Integer Solution

3
2
1

Figure 11.1

+
+

Optimal LP Solution
(X1 =3.75, X2 = 1.5,
Profit = $35.25)
2X1 + 3X2 12

X1

2009 Prentice-Hall, Inc.

11 6

Harrison Electric Company Example of

Integer Programming
The production planner Wes recognizes this is an

integer problem
His first attempt at solving it is to round the
values to X1 = 4 and X2 = 2
However, this is not feasible
Rounding X2 down to 1 gives a feasible solution,
but it may not be optimal
This could be solved using the enumeration
method
Enumeration is generally not possible for large
problems

2009 Prentice-Hall, Inc.

11 7

Harrison Electric Company Example of

Integer Programming
CHANDELIERS (X1)

CEILING FANS (X2)

PROFIT ($7X1 + $6X2)

$0

14

21

28

35

13

20

27

34

12

19

26

33

18

25

Integer

solutions

Optimal solution to
integer programming
problem

Solution if
rounding is used

Table 11.1
2009 Prentice-Hall, Inc.

11 8

Harrison Electric Company Example of

Integer Programming
The rounding solution of X1 = 4, X2 = 1

gives a profit of $34

The optimal solution of X1 = 5, X2 = 0 gives
a profit of $35
The optimal integer solution is less than
the optimal LP solution
An integer solution can never be better
than the LP solution and is usually a
lesser solution

2009 Prentice-Hall, Inc.

11 9

Branch-and-Bound Method
The most common algorithm for solving integer

programming problems is the branch-and-bound

method
It starts by first allowing non-integer solutions
If these values are integer valued, this must also
be the solution to the integer problem
If these variables are not integer valued, the
feasible region is divided by adding constraints
restricting the value of one of the variables that
was not integer valued
The divided feasible region results in
subproblems that are then solved
2009 Prentice-Hall, Inc.

11 10

Branch-and-Bound Method
Bounds on the value of the objective function are

found and used to help determine which

subproblems can be eliminated and when the
optimal solution has been found
If a solution is not optimal, a new subproblem is
selected and branching continues

2009 Prentice-Hall, Inc.

11 11

Six Steps in Solving IP Maximization

Problems by Branch and Bound
1. Solve the original problem using LP. If the answer

satisfies the integer constraints, we are done. If

not, this value provides an initial upper bound.
2. Find any feasible solution that meets the integer
constraints for use as a lower bound. Usually,
rounding down each variable will accomplish this.
3. Branch on one variable from step 1 that does not
have an integer value. Split the problem into two
subproblems based on integer values that are
immediately above or below the noninteger value.
4. Create nodes at the top of these new branches by
solving the new problem
2009 Prentice-Hall, Inc.

11 12

Six Steps in Solving IP Maximization

Problems by Branch and Bound
5.

(a)
If a branch yields a solution to the LP
problem that is not feasible,
feasible terminate the
branch
(b) If a branch yields a solution to the LP
problem that is feasible, but not an integer
solution, go to step 6
(c)
If the branch yields a feasible integer
solution, examine the value of the objective
function. If this value equals the upper bound,
an optimal solution has been reached. If it not
equal to the upper bound, but exceeds the
lower bound, terminate this branch.
2009 Prentice-Hall, Inc.

11 13

Six Steps in Solving IP Maximization

Problems by Branch and Bound
6. Examine both branches again and set the upper

bound equal to the maximum value of the

objective function at all final nodes. If the upper
bound equals the lower bound, stop. If not, go
back to step 3.

Note: Minimization problems involved

reversing the roles of the upper and
lower bounds

2009 Prentice-Hall, Inc.

11 14

Harrison Electric Company Revisited

Recall that the Harrison Electric Companys

integer programming formulation is

Maximize profit = $7X1 + $6X2

subject to
2X1 + 3X2 12
6X1 + 5X2 30
where
X1 = number of chandeliers produced
X2 = number of ceiling fans produced
And the optimal noninteger solution is
X1 = 3.75 chandeliers,
X2 = 1.5 ceiling fans
profit = $35.25
2009 Prentice-Hall, Inc.

11 15

Harrison Electric Company Revisited

Since X1 and X2 are not integers, this solution is

not valid
The profit value of $35.25 will provide the initial
upper bound
We can round down to X1 = 3, X2 = 1, profit = $27,
which provides a feasible lower bound
The problem is now divided into two subproblems

2009 Prentice-Hall, Inc.

11 16

Harrison Electric Company Revisited

Subproblem A
Maximize profit = $7X1 + $6X2
subject to
2X1 + 3X2 12
6X1 + 5X2 30
X1
4
Subproblem B
Maximize profit = $7X1 + $6X2
subject to
2X1 + 3X2 12
6X1 + 5X2 30
X1
3
2009 Prentice-Hall, Inc.

11 17

Harrison Electric Company Revisited

If you solve both subproblems graphically

Subproblem As [X = 4, X = 1.2, profit = $35.20]

1
2
optimal solution:
Subproblem Bs [X = 3, X = 2, profit = $33.00]
1
2
optimal solution:
We have completed steps 1 to 4 of the branch and

bound method

2009 Prentice-Hall, Inc.

11 18

Harrison Electric Company Revisited

Harrison Electrics first branching:

subproblems A and B

Next Branch (C)

Subproblem A

X1

X1 = 4
X2 = 1.2
P = 35.20

Infeasible (Noninteger) Solution

Upper Bound = $35.20
Lower Bound = $33.00
Next Branch (D)

X1 = 3.75
X2 = 1.5
P = 35.25
X

Figure 11.2

Upper Bound = $35.25

Lower Bound = $27.00 (From
Rounding Down)
Subproblem B
3

X1 = 3
X2 = 2
P = 33.00
Stop This Branch
Solution Is Integer, Feasible
Provides New Lower Bound of $33.00
2009 Prentice-Hall, Inc.

11 19

Harrison Electric Company Revisited

Subproblem A has branched into two new

subproblems, C and D

Subproblem C
Maximize profit = $7X1 + $6X2
subject to
2X1 + 3X2
6X1 + 5X2
X1
X2

12
30
4
2

Subproblem D
Maximize profit = $7X1 + $6X2
subject to
2X1 + 3X2
6X1 + 5X2
X1
X2

12
30
4
1
2009 Prentice-Hall, Inc.

11 20

Harrison Electric Company Revisited

Subproblem C has no feasible solution

because the all the constraints can not be

satisfied
We terminate this branch and do not consider
this solution
Subproblem Ds optimal solution is X1 = 4.17,
X2 = 1, profit = $35.16
This noninteger solution yields a new upper
bound of $35.16

2009 Prentice-Hall, Inc.

11 21

Harrison Electric Company Revisited

Finally we create subproblems E and F
Subproblem E
Maximize profit = $7X1 + $6X2
subject to
2X1 + 3X2
6X1 + 5X2
X1
X1
X2
Subproblem D
Maximize profit = $7X1 + $6X2
subject to
2X1 + 3X2
6X1 + 5X2
X1
X1
X2

12
30
4
4
1
12
30
4
5
1

Optimal solution to E:
X1 = 4, X2 = 1, profit = $34

Optimal solution to F:
X1 = 5, X2 = 0, profit = $35

2009 Prentice-Hall, Inc.

11 22

Harrison Electric Company Revisited

The stopping rule for the branching process is

that we continue until the new upper bound is less

than or equal to the lower bound
or no further branching is possible
The later case applies here since both branches
yielded feasible integer solutions
The optimal solution is subproblem Fs node
Computer solutions work well on small and
medium problems
For large problems the analyst may have to settle
for a near-optimal solution

2009 Prentice-Hall, Inc.

11 23

Harrison Electric Company Revisited

Harrison Electrics full branch and bound solution
Subproblem C
No
Feasible
Solution
Region

Subproblem A
X2

X1

X1 = 4
X2 = 1.2
P = 35.20

Subproblem D
X

X1 = 3.75
X2 = 1.5
P = 35.25
X

Figure 11.3

Subproblem B
3

Subproblem E

X1

X1 = 4.17
X2 = 1
P = 35.16
1

Upper Bound
= $35.25
Lower Bound
= $27.00

Feasible, Integer
Solution

Subproblem F
X

X1 = 3
X2 = 2
P = 33.00

X1 = 4
X2 = 1
P = 34.00

X1 = 5
X2 = 0
P = 35.00
Optimal
Solution
2009 Prentice-Hall, Inc.

11 24

Using Software to Solve Harrison

Integer Programming Problem
QM for Windows input screen with Harrison

Electric data

Program 11.1A
2009 Prentice-Hall, Inc.

11 25

Using Software to Solve Harrison

Integer Programming Problem
QM for Windows solution screen for Harrison

Electric data

Program 11.1B
2009 Prentice-Hall, Inc.

11 26

Using Software to Solve Harrison

Integer Programming Problem
QM for Windows iteration results screen for

Harrison Electric data

Program 11.1C

2009 Prentice-Hall, Inc.

11 27

Mixed-Integer Programming
Problem Example
There are many situations in which some of the

variables are restricted to be integers and some

are not
Bagwell Chemical Company produces two
industrial chemicals
Xyline must be produced in 50-pound bags
Hexall is sold by the pound and can be produced
in any quantity
Both xyline and hexall are composed of three
ingredients A, B, and C
Bagwell sells xyline for $85 a bag and hexall for
$1.50 per pound
2009 Prentice-Hall, Inc.

11 28

Mixed-Integer Programming
Problem Example
AMOUNT PER 50-POUND
BAG OF XYLINE (LB)

AMOUNT PER POUND

OF HEXALL (LB)

AMOUNT OF
INGREDIENTS
AVAILABLE

30

0.5

2,000 lbingredient A

18

0.4

800 lbingredient B

0.1

200 lbingredient C

Bagwell wants to maximize profit

We let X = number of 50-pound bags of xyline
We let Y = number of pounds of hexall
This is a mixed-integer programming problem as

Y is not required to be an integer

2009 Prentice-Hall, Inc.

11 29

Mixed-Integer Programming
Problem Example
The model is

Maximize profit = $85X + $1.50Y

subject to
30X
+ 0.5Y
30X
+ 0.5Y
30X
+ 0.5Y
X, Y

2,000
800
200
0 and X integer

2009 Prentice-Hall, Inc.

11 30

Mixed-Integer Programming
Problem Example
Using QM for Windows and Excel to solve

Bagwells IP model

Program 11.3
2009 Prentice-Hall, Inc.

11 31

Modeling With 0-1 (Binary) Variables

We can demonstrate how 0-1 variables

can be used to model several diverse

situations
Typically a 0-1 variable is assigned a value
of 0 if a certain condition is not met and a
1 if the condition is met
This is also called a binary variable

2009 Prentice-Hall, Inc.

11 32

Capital Budgeting Example

A common capital budgeting problem is selecting

from a set of possible projects when budget

limitations make it impossible to select them all
A 0-1 variable is defined for each project
Quemo Chemical Company is considering three
possible improvement projects for its plant
A new catalytic converter
A new software program for controlling operations
Expanding the storage warehouse

It can not do them all

They want to maximize net present value of

projects undertaken

2009 Prentice-Hall, Inc.

11 33

Capital Budgeting Example

Quemo Chemical Company information
PROJECT

NET PRESENT VALUE

YEAR 1

YEAR 2

Catalytic Converter

$25,000

$8,000

$7,000

Software

$18,000

$6,000

$4,000

Warehouse expansion

$32,000

$12,000

$8,000

$20,000

$16,000

Available funds

Table 11.2

The basic model is

Maximize net present value of projects

undertaken
subject to Total funds used in year 1 $20,000
Total funds used in year 2 $16,000
2009 Prentice-Hall, Inc.

11 34

Capital Budgeting Example

The decision variables are
catalytic converter project is funded
X1 = 10 if
otherwise
software project is funded
X2 = 10 if
otherwise
warehouse expansion project is funded
X3 = 10 if
otherwise

The mathematical statement of the integer

programming problem becomes

Maximize NPV = 25,000X1 + 18,000X2 + 32,000X3

subject to
8,000X1 + 6,000X2 + 12,000X3 20,000
7,000X1 + 4,000X2 + 8,000X3 16,000
X1, X2, X3 = 0 or 1
2009 Prentice-Hall, Inc.

11 35

Capital Budgeting Example

Solved with computer software, the

optimal solution is X1 = 1, X2 = 0, and X3 = 1

with an objective function value of 57,000
This means that Quemo Chemical should
fund the catalytic converter and
warehouse expansion projects only
The net present value of these
investments will be $57,000

2009 Prentice-Hall, Inc.

11 36

Limiting the Number of

Alternatives Selected
One common use of 0-1 variables involves

limiting the number of projects or items that are

selected from a group
Suppose Quemo Chemical is required to select
no more than two of the three projects regardless
of the funds available
This would require adding a constraint
X1 + X2 + X3 2
If they had to fund exactly two projects the
constraint would be
X1 + X2 + X3 = 2
2009 Prentice-Hall, Inc.

11 37

Dependent Selections
At times the selection of one project depends on

the selection of another project

Suppose Quemos catalytic converter could only
be purchased if the software was purchased
The following constrain would force this to occur
X1 X2 or X1 X2 0
If we wished for the catalytic converter and
software projects to either both be selected or
both not be selected, the constraint would be
X1 = X2 or X1 X2 = 0

2009 Prentice-Hall, Inc.

11 38

Fixed-Charge Problem Example

Often businesses are faced with decisions

involving a fixed charge that will affect the cost of

future operations
Sitka Manufacturing is planning to build at least
one new plant and three cities are being
considered in
Baytown, Texas
Lake Charles, Louisiana
Mobile, Alabama

Once the plant or plants are built, the company

want to have capacity to produce at least 38,000

units each year
2009 Prentice-Hall, Inc.

11 39

Fixed-Charge Problem Example

Fixed and variable costs for Sitka Manufacturing
SITE

ANNUAL
FIXED COST

VARIABLE COST
PER UNIT

ANNUAL
CAPACITY

Baytown, TX

$340,000

$32

21,000

Lake Charles, LA

$270,000

$33

20,000

Mobile, AL

$290,000

$30

19,000

Table 11.3

2009 Prentice-Hall, Inc.

11 40

Fixed-Charge Problem Example

We can define the decision variables as
factory is built in Baytown
X1 = 10 if
otherwise
is built in Lake Charles
X2 = 10 factory
otherwise
factory is built in Mobile
X3 = 10 if
otherwise

X4 = number of units produced at Baytown plant

X5 = number of units produced at Lake Charles plant
X6 = number of units produced at Mobile plant
2009 Prentice-Hall, Inc.

11 41

Fixed-Charge Problem Example

The integer programming formulation becomes
Minimize cost = 340,000X1 + 270,000X2 + 290,000X3
+ 32X4 + 33X5 + 30X6
subject to X4 + X5 + X6 38,000
X4
21,000X1
X5
20,000X2
X6 19,000X3
X1, X2, X3 = 0 or 1;
X4, X5, X6 0 and integer

The optimal solution is

X1 = 0, X2 = 1, X3 = 1, X4 = 0, X5 = 19,000, X6 = 19,000
Objective function value = $1,757,000
2009 Prentice-Hall, Inc.

11 42

Exercise

The CALIFORNIA MANUFACTURING COMPANY is considering

expansion by building a new factory in either Los Angeles or San
Francisco, or perhaps even in both cities.

It also is considering building at most one new warehouse, but

the choice of location is restricted to a city where a new factory is
being built.

The net present value (total profitability considering the time value
of money) of each of these alternatives is shown in the fourth
column of Table 1. The rightmost column gives the capital
required (already included in the net present value) for the
respective investments, where the total capital available is $10
million. The objective is to find the feasible combination of
alternatives that maximizes the total net present value

2009 Prentice-Hall, Inc.

11 43

Table 1

Formulate BIP model for this problem and

determine the optimal decision

2009 Prentice-Hall, Inc.

11 44

Goal Programming
Firms often have more than one goal
They may want to achieve several, sometimes

contradictory, goals
In linear and integer programming methods the
objective function is measured in one dimension
only
It is not possible for LP to have multiple goals
unless they are all measured in the same units,
and this is a highly unusual situation
An important technique that has been developed
to supplement LP is called goal programming

2009 Prentice-Hall, Inc.

11 45

Goal Programming
Typically goals set by management can be

achieved only at the expense of other goals

A hierarchy of importance needs to be established
so that higher-priority goals are satisfied before
lower-priority goals are addressed
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
2009 Prentice-Hall, Inc.

11 46

Example of Goal Programming

Harrison Electric Revisited
The LP formulation for the Harrison Electric

problem is

Maximize profit = $7X1 + $6X2

subject to
2X1 + 3X2 12 (wiring hours)
6X1 + 5X2 30 (assembly hours)
X1 , X2 0
where
X1 = number of chandeliers produced
X2 = number of ceiling fans produced

2009 Prentice-Hall, Inc.

11 47

Example of Goal Programming

Harrison Electric Revisited
Harrison 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
d1 = underachievement of the profit target
d1+ = overachievement of the profit target

2009 Prentice-Hall, Inc.

11 48

Example of Goal Programming

Harrison Electric Revisited
We can now state the Harrison Electric problem

as a single-goal programming model

Minimize under or overachievement

of profit target
subject to

= d 1 + d 1+

$7X1 + $6X2 + d1 d1+ = $30

2X1 + 3X2
12
6X1 + 5X2
30
X1, X2, d1, d1+ 0

(profit goal constraint)

(wiring hours)
(assembly hours)

2009 Prentice-Hall, Inc.

11 49

Extension to Equally Important

Multiple Goals
Now Harrisons 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

2009 Prentice-Hall, Inc.

11 50

Extension to Equally Important

Multiple Goals
The deviational variables are

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

2009 Prentice-Hall, Inc.

11 51

Extension to Equally Important

Multiple Goals
Because management is unconcerned about d1+,

d2+, d3, and d4+ these may be omitted from the

objective function
The new objective function and constraints are

Minimize total deviation = d1 + d2 + d3+ + d4

subject to 7X1 + 6X2 + d1
2X1 + 3X2 + d2
6X1 + 5X2 + d3
X2 + d4

d 1+
d 2+
d 3+
d 4+

= 30
= 12
= 30
=7

(profit constraint)
(wiring hours)
(assembly hours)
(ceiling fan constraint)

All Xi, di variables 0

2009 Prentice-Hall, Inc.

11 52

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 managements eyes
Higher-order goals are satisfied before lowerorder goals
Priorities (Pis)
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

2009 Prentice-Hall, Inc.

11 53

Ranking Goals with Priority Levels

Harrison Electric has set the following priorities

for their four goals

GOAL

PRIORITY

Reach a profit as much above $30 as possible

P1

Fully use wiring department hours available

P2

Avoid assembly department overtime

P3

Produce at least seven ceiling fans

P4

2009 Prentice-Hall, Inc.

11 54

Ranking Goals with Priority Levels

This effectively means that each goal is infinitely

more important than the next lower goal

With the ranking of goals considered, the new
objective function is

Minimize total deviation = P1d1 + P2d2 + P3d3+ + P4d4

The constraints remain identical to the previous

ones

2009 Prentice-Hall, Inc.

11 55

Solving Goal Programming Problems

Graphically
We can analyze goal programming

problems graphically
We must be aware of three characteristics
of goal programming 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
2009 Prentice-Hall, Inc.

11 56

Solving Goal Programming Problems

Graphically
Recall the Harrison Electric goal programming

model

Minimize total deviation = P1d1 + P2d2 + P3d3+ + P4d4

subject to 7X1 + 6X2 + d1 d1+ = 30 (profit )
2X1 + 3X2 + d2 d2+ = 12 (wiring )
6X1 + 5X2 + d3 d3+ = 30 (assembly )
X2 + d4 d4+ = 7 (ceiling fans)
All Xi, di variables 0 (nonnegativity)
where
X1 = number of chandeliers produced
X2 = number of ceiling fans produced
2009 Prentice-Hall, Inc.

11 57

Solving Goal Programming Problems

Graphically
To solve this we graph one constraint at a time

starting with the constraint with the highestpriority deviational variables

In this case we start with the profit constraint as
it has the variable d1 with a priority of P1
Note that in graphing this constraint the
deviational variables are ignored
To minimize d1 the feasible area is the shaded
region

2009 Prentice-Hall, Inc.

11 58

Solving Goal Programming Problems

Graphically
Analysis of

the first goal

X2
7

Minimize Z = P1d1

6
5
4
3
d1+

2
1
0
Figure 11.4

d 1

7X1 + 6X2 = 30

X1

2009 Prentice-Hall, Inc.

11 59

Solving Goal Programming Problems

Graphically
The next graph is of the second priority goal of

minimizing d2
The region below the constraint line 2X1 + 3X2 =
12 represents the values for d2 while the region
above the line stands for d2+
To avoid underutilizing wiring department hours
the area below the line is eliminated
This goal must be attained within the feasible
region already defined by satisfying the first goal

2009 Prentice-Hall, Inc.

11 60

Solving Goal Programming Problems

Graphically
Analysis of

first and
second goals

X2
7

Minimize Z = P1d1 + P2d2

6
5

d1+

4
3
2

2X1 + 3X2 = 12

1
d2+

0
Figure 11.5

7X1 + 6X2 = 30

d2

X1

2009 Prentice-Hall, Inc.

11 61

Solving Goal Programming Problems

Graphically
The third goal is to avoid overtime in the

assembly department
We want d3+ to be as close to zero as possible
This goal can be obtained
Any point inside the feasible region bounded by
the first three constraints will meet the three
most critical goals
The fourth constraint seeks to minimize d4
To do this requires eliminating the area below
the constraint line X2 = 7 which is not possible
given the previous, higher priority, constraints

2009 Prentice-Hall, Inc.

11 62

Solving Goal Programming Problems

Graphically
Analysis of

all four
priority goals

X2
d 4+

7
6 A

Minimize Z = P1d1 + P2d2 + P3d3 + P4d4

d3+

5
D
4

X2 = 7

d 4

d3

d1+

d2+

6X1 + 5X2 = 30
B

0
Figure 11.6

2X1 + 3X2 = 12

7X1 + 6X2 = 30
|

X1

2009 Prentice-Hall, Inc.

11 63

Solving Goal Programming 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

2009 Prentice-Hall, Inc.

11 64

Modified Simplex Method for

Goal Programming
The modified simplex method can be used to

solve problems with more than two real variables

Recall the Harrison Electric model
Minimize = P1d1 + P2d2 + P3d3+ + P4d4
subject to 7X1 + 6X2 + d1 d1+ = 30
2X1 + 3X2 + d2 d2+ = 12
6X1 + 5X2 + d3 d3+ = 30
X2 + d4 d4+ = 7
All Xi, di variables 0

2009 Prentice-Hall, Inc.

11 65

Modified Simplex Method for

Goal Programming
Initial goal programming tableau
Cj

P1

P2

P4

P3

SOLUTION
MIX

X1

X2

d1

d2

d3

d4

d1+

d2+

d3+

d4+

QUANTITY

P1

d1

30

P2

d2

12

d3

30

P4

d4

Zj

P4

P3

P2

12

P1

30

P4

P3

P2

P1

Cj Zj

6 column
0
Pivot

Table 11.5
2009 Prentice-Hall, Inc.

11 66

Modified Simplex Method for

Goal Programming
There are four features of the modified simplex

tableau that differ from earlier simplex tableaus

1. The variables in the problem are listed at the top,
with the decision variables (X1 and X2) first, then
the negative deviational variables and, finally, the
positive deviational variables. The priority level
of each variable is assigned on the very top row.
2. The negative deviational variables for each
constraint provide the initial basic solution. This
is analogous to the use of slack variables in the
earlier simplex tableaus. The priority level of
each variable in the current solution mix is
entered in the Cj column.
2009 Prentice-Hall, Inc.

11 67

Modified Simplex Method for

Goal Programming
3. There is a separate Xj and Cj Zj row for each of

the Pi priorities because different units of

measurement are used for each goal. The bottom
row of the tableau contains the highest ranked
(P1) goal, the next row has the P2 goal, and so
forth. The rows are computed exactly as in the
regular simplex method, but they are done for
each priority level.

2009 Prentice-Hall, Inc.

11 68

Modified Simplex Method for

Goal Programming
4. In selecting the variable to enter the solution

mix, we start with the highest-priority row, P1,

and select the most negative Cj Zj value in it. If
there was no negative number for P1, we would
move on to priority P2s Cj Zj row and select the
largest negative number there. A negative Cj Zj
that has a positive number in the P row
underneath it, however, is ignored. This means
that deviations from a more important goal (one
in a lower row) would be increased if that
variable were brought into the solution.

2009 Prentice-Hall, Inc.

11 69

Modified Simplex Method for

Goal Programming
We move towards the optimal solution just as

with the regular minimization simplex method

We find the pivot row by dividing the quantity
values by their corresponding pivot column (X1)
values and picking the one with the smallest
positive ratio
In this case, d1 leaves the basis and is replaced
by X1
We continue this process until an optimal
solution is reached

2009 Prentice-Hall, Inc.

11 70

Modified Simplex Method for

Goal Programming
Second goal programming tableau
Cj

P1

P2

P4

P3

SOLUTION
MIX

X1

X2

d1

d2

d3

d4

d1+

d2+

d3+

d4+

QUANTITY

X1

6/7

1/7

1/7

30/7

P2

d2

9/7

2/7

2/7

24/7

d3

1/7

6/7

6/7

30/7

P4

d4

Zj

P4

P3

P2

9/7

2/7

2/7

24/7

P1

P4

P3

P2

9/7

2/7

2/7

P1

Cj Zj

1 column
0
Pivot

Table 11.6
2009 Prentice-Hall, Inc.

11 71

Modified Simplex Method for

Goal Programming
Final solution to Harrison Electric's goal program
Cj

P1

P2

P4

P3

SOLUTION
MIX

X1

X2

d1

d2

d3

d4

d1+

d2+

d3+

d4+

QUANTITY

d2+

8/5

3/5

3/5

X2

6/5

1/5

1/5

d1+

1/5

6/5

6/5

P4

d4

6/5

1/5

1/5

Zj

P4

6/5

1/5

1/5

P3

P2

P1

P4

6/5

1/5

1/5

P3

P2

P1

Cj Zj

Table 11.7
2009 Prentice-Hall, Inc.

11 72

Modified Simplex Method for

Goal Programming
In the final solution the first three goals have

been fully achieved with no negative entries in

their Cj Zj rows
A negative value appears in the d3+ column in the
priority 4 row indicating this goal has not been
fully attained
But the positive number in the d3+ at the P3
priority level (shaded cell) tells us that if we try
to force d3+ into the solution mix, it will be at the
expense of the P3 goal which has already been
satisfied

2009 Prentice-Hall, Inc.

11 73

Modified Simplex Method for

Goal Programming
The final solution is

X1 = 0 chandeliers produced
X2 = 6 ceiling fans produced
d1+ = $6 over the profit goal
d2+ = 6 wiring hours over the minimum set
d4 = 1 fewer fan than desired

2009 Prentice-Hall, Inc.

11 74

Goal Programming with

Weighted Goals
Normally priority levels in goal programming

assume that each level is infinitely more

important than the level below it
Sometimes this may not be desirable
A goal may be only two or three times more
important than another
Instead of placing these goals on different levels,
we place them on the same level but with different
weights
The coefficients of the deviation variables in the
objective function include both the priority level
and the weight
2009 Prentice-Hall, Inc.

11 75

Goal Programming with

Weighted Goals
Suppose Harrison decides to add another goal of

producing at least two chandeliers

The goal of producing seven ceiling fans is
considered twice as important as this goal
The goal of two chandeliers is assigned a weight
of 1 and the goal of seven ceiling fans is
assigned a weight of 2 and both of these will be
priority level 4
The new constraint and objective function are
X1 + d5 d5+ = 2 (chandeliers)
Minimize = P1d1 + P2d2 + P3d3+ + P4(2d4) + P4d5

2009 Prentice-Hall, Inc.

11 76

Using QM for Windows to Solve

Harrisons Problem
Harrison Electrics goal programming analysis

using QM for Windows

This table refers to the formulation as presented
in Table 11.5

Program 11.6A

2009 Prentice-Hall, Inc.

11 77

Using QM for Windows to Solve

Harrisons Problem
Final tableau for Harrison Electric using QM for

Windows

Program 11.6B

2009 Prentice-Hall, Inc.

11 78

Using QM for Windows to Solve

Harrisons Problem
Summary solution screen for Harrison Electrics

goal programming problem using QM for Windows

Program 11.6C
2009 Prentice-Hall, Inc.

11 79