|
|
|
|
Most operations
research studies involve the construction of a mathematical
model. The model is a collection of logical and mathematical
relationships that represents aspects of the situation under
study. Models describe important relationships between variables,
include an objective function with which alternative solutions
are evaluated, and constraints that restrict solutions to feasible
values.
Although the analyst would hope to study the broad
implications of the problem using a systems approach, a model
cannot include every aspect of a situation. A model is always
an abstraction that is of necessity simpler than the real situation.
Elements that are irrelevant or unimportant to the problem are
to be ignored, hopefully leaving sufficient detail so that the
solution obtained with the model has value with regard to the
original problem.
Models must be both tractable, capable of being
solved, and valid, representative of the original situation.
These dual goals are often contradictory and are not always
attainable. It is generally true that the most powerful solution
methods can be applied to the simplest, or most abstract, model.
We provide in this section, a description of
the various types of models used by operations research analysts.
The division is based on the mathematical form of the model.
All the models described here are solved with Excel add-ins
described in the Computation section
of this site. In some cases,
the methods used to solve a model are described in the Methods section.
Student exercises for creating models are in the Problems section.
Additional models related to problems arising in Operations
Management
and Industrial
Engineering
are in the OM/IE section. |
|
|
Operations research (OR) is a discipline explicitly devoted to
aiding decision makers. This section reviews the terminology of
OR, a process for addressing practical decision problems and the
relation between Excel models and OR. |
|
|
A typical mathematical program consists of a single objective
function, representing either a profit to be maximized or a cost
to be minimized, and a set of constraints that circumscribe the
decision variables. In the case of a linear program (LP) the objective
function and constraints are all linear functions of the decision
variables. At first glance these restrictions would seem to limit
the scope of the LP model, but this is hardly the case. Because
of its simplicity, software has been developed that is capable
of solving problems containing millions of variables and tens
of thousands of constraints. Countless real-world applications
have been successfully modeled and solved using linear programming
techniques. |
|
|
The term network flow program describes a type of model that is
a special case of the more general linear program. The class of
network flow programs includes such problems as the transportation
problem, the assignment problem, the shortest path problem, the
maximum flow problem, the pure minimum cost flow problem, and
the generalized minimum cost flow problem. It is an important
class because many aspects of actual situations are readily recognized
as networks and the representation of the model is much more compact
than the general linear program. When a situation can be entirely
modeled as a network, very efficient algorithms exist for the
solution of the optimization problem, many times more efficient
than linear programming in the utilization of computer time and
space resources. |
|
|
Integer programming is concerned with optimization problems in
which some of the variables are required to take on discrete values.
Rather than allow a variable to assume all real values in a given
range, only predetermined discrete values within the range are
permitted. In most cases, these values are the integers, giving
rise to the name of this class of models.
Models with integer variables are very useful. Situations that
cannot be modeled by linear programming are easily handled by
integer programming. Primary among these involve binary decisions
such as yes-no, build-no build or invest-not invest. Although
one can model a binary decision in linear programming with a
variable that ranges between 0 and 1, there is nothing that
keeps the solution from obtaining a fractional value such as
0.5, hardly acceptable to a decision maker. Integer programming
requires such a variable to be either 0 or 1, but not in-between.
Unfortunately integer programming models of practical size
are often very difficult or impossible to solve. Linear programming
methods can solve problems orders of magnitude larger than integer
programming methods. Still, many interesting problems are solvable,
and the growing power of computers makes this an active area
of interest in Operations Research. |
|
|
When expressions defining the objective function or constraints
of an optimization model are not linear, one has a nonlinear programming
model. Again, the class of situations appropriate for nonlinear
programming is much larger than the class for linear programming.
Indeed it can be argued that all linear expressions are really
approximations for nonlinear ones.
Since nonlinear functions can assume such a wide variety of
functional forms, there are many different classes of nonlinear
programming models. The specific form has much to do with how
easily the problem is solve, but in general a nonlinear programming
model is much more difficult to solve than a similarly sized
linear programming model. |
|
|
Dynamic programming (DP) models are represented in a different
way than other mathematical programming models. Rather than an
objective function and constraints, a DP model describes a process
in terms of states, decisions, transitions and returns. The process
begins in some initial state where a decision is made. The decision
causes a transition to a new state. Based on the starting state,
ending state and decision a return is realized. The process continues
through a sequence of states until finally a final state is reached.
The problem is to find the sequence that maximizes the total return.
The models considered here are for discrete decision problems.
Although traditional integer programming problems can be solved
with DP, the models and methods are most appropriate for situations
that are not easily modeled using the constructs of mathematical
programming. Objectives with very general functional forms may
be handled and a global optimal solution is always obtained.
The price of this generality is computational effort. Solutions
to practical problems are often stymied by the "curse of
dimensionally" where the number of states grows exponentially
with the number of dimensions of the problem. |
|
|
The mathematical programming models, such as linear programming,
network flow programming and integer programming generally
neglect the effects of uncertainty and assume that the results
of decisions are predictable and deterministic. This
abstraction of reality allows large and complex decision problems
to be modeled and solved using powerful computational methods.
Stochastic programming explicitly recognizes uncertainty by
using random variables for some aspects of the problem. With
probability distributions assigned to the random variables,
an expression can be written for the expected value of the
objective to be optimized. Then a variety of computational
methods can be used to maximize or minimize the expected value.
This page provides a brief introduction to the modeling process. |
|
|
The most general type of optimization problem and one that is
applicable to most spreadsheet models is the combinatorial optimization
problem. Many spreadsheet models contain variables and compute
measures of effectiveness. The spreadsheet user often changes
the variables in an unstructured way to look for the solution
that obtains the greatest or least of the measure. In the words
of OR, the analyst is searching for the solution that optimizes
an objective function, the measure of effectiveness. Combinatorial
optimization provides tools for automating the search for good
solutions and can be of great value for spreadsheet applications. |
|
|
In
many practical situations the attributes of a system randomly
change over time. Examples include the number of customers in
a checkout line, congestion on a highway, the number of items
in a warehouse, and the price of a financial security, to name
a few. When aspects of
the process are governed by probability theory, we have a stochastic
process.
The model is described in part by enumerating the states in
which the system can be found.
The state is like a snapshot of the system at a point
in time that describes the attributes of the system. The example
for this section is an Automated Teller Machine (ATM) system
and the state is the number of customers at or waiting for the
machine. Time is the linear measure through which the system
moves. Events occur that change the state of the system. For
the ATM example the events are arrivals and departures.
In this section we describe the basic ideas associated with
modeling a stochastic process that are useful for both Discrete
and
Continuous Time Markov Chains. |
|
|
Say
a system is observed at regular intervals such as every day or
every week. Then the stochastic process can be described by a
matrix which gives the probabilities of moving to each state from
every other state in one time interval. Assuming this matrix is
unchanging with time, the process is called a Discrete Time Markov
Chain (DTMC). Computational techniques are available to compute
a variety of system measures that can be used to analyze and evaluate
a DTMC model. This section illustrates how to construct a model
of this type and the measures that are available. |
|
|
Here we consider a continuous time stochastic process in which
the duration of all state changing activities are exponentially
distributed. Time is a continuous parameter. The process satisfies
the Markovian property and is called a Continuous Time Markov
Chain (CTMC). The process is entirely described by a matrix showing
the rate of transition from each state to every other state. The
rates are the parameters of the associated exponential distributions.
The analytical results are very similar to those of a DTMC. The
ATM example is continued with illustrations of the elements of
the model and the statistical measures that can be obtained from
it. |
|
|
When a situation is affected by random variables it is often difficult
to obtain closed form equations that can be used for evaluation.
Simulation is a very general technique for estimating statistical
measures of complex systems. A system is modeled as if the random
variables were known. Then values for the variables are drawn
randomly from their known probability distributions. Each replication
gives one observation of the system response. By simulating a
system in this fashion for many replications and recording the
responses, one can compute statistics concerning the results.
The statistics are used for evaluation and design. |
|
|
|
|