The Problem
A builder is planning to construct new buildings at four
local sites designated 1, 2, 3 and 4. At each site there
are three possible building designs labeled A, B and C.
There is also the option of not using a site. The problem
is to select the building locations and accompanying designs.
Preliminary studies have determined the required investment
and net annual income for each of the 12 options. These
are shown in the table below, with A1, for example, denoting
design A at site 1. The company has an investment budget
of $100M. The goal is to maximize total annual income
without exceeding the investment budget. As the OR analyst,
you are given the job of finding the optimum plan.
Option
|
A1
|
A2
|
A3
|
A4
|
B1
|
B2
|
B3
|
B4
|
C1
|
C2
|
C3
|
C4
|
Net income ($M)
|
6
|
7
|
9
|
11
|
12
|
15
|
5
|
8
|
12
|
16
|
19
|
20
|
Investment ($M)
|
13
|
20
|
24
|
30
|
39
|
45
|
12
|
20
|
30
|
44
|
48
|
55
|
This example introduces one of the major differences
between linear and integer programming; the indivisibility
of decisions. It is an obvious requirement here that only
whole buildings may be built and only whole designs may
be selected.
Linear/Integer Programming Model
To begin creating a model, variables must be defined
to represent each decision. In many cases models can be
more succinctly stated using algebraic expressions with
subscripted variables. In this section, we use variable
names like A1, A2,
C3, and C4 to represent the
decisions. This makes it easier to present the model in
a browser readable format. The notation is also similar
to that used for the computer model. We will write several
models in this section, but the simplest is:
Objective: Max. z = 6*A1 + 7*A2 + 9*A3 ...
+ 19*C3 + 20*C4
subject to:
Budget: 13*A1 + 20*A2 + 24*A3 ... + 48*C3
+ 55*C4 100
Simple Bounds and Integrality
0
A1
1, 0
A2
1, ... , 0
C4
1 and integer
We use * to indicate multiplication and
... to indicate a continuation in a similar fashion.
Note that since the variables are restricted
between 0 and 1 and required to be integer, there are
actually only two feasible values, 0 and 1 for each variable.
A design/location combination either adds its contributions
to the net income and budget (=1) or does not (=0). The
simple phrase "and integer" specifies that all
the variables must be integer Thus the model describes
the problem of selecting the set of design/location combinations
that maximize net income, while not exceeding the budget
constraint.
The model has the linear form required for
linear programming, but it is not a linear programming
model because the variables are not allowed to assume
all values within a continuum. Often the phrase Integer
Programming is used for the linear model with some
or all the variables required to be integer, leaving out
the term linear. Although one can express models that
are integer and nonlinear, these are generally much more
difficult to solve. For a nonlinear-integer model we use
the phrase nonlinear-integer program. We only consider
(linear) integer programming models in this section.
|