These tours lead the student through the articles of this
site while concentrating on a single major topic. Topics are
Navigation is provided by colored acorns and the Tour icon.
We have used Macromedia Flash to illustrate several concepts
on this site. To view the Flash animations, follow this tour.
You must use the Flash 4 player or later for these demonstrations.
Flash Player) Click on the link at the left to be transferred
to the download facility at Macromedia.
The branch of operations research that deals with the optimal
allocation of scarce resources among competing activities is known
as mathematical programming of which linear programming is a special
case. The word 'programming' is a synonym for planning and the
adjective 'mathematical' indicates that mathematics is the primary
mechanism by which problems are represented. For the linear program,
all functional relationships are required to be linear and decision
variables are required to be continuous rather than discrete.
Linear programming is at the center of virtually all optimization.
Many common models, such as those arising in network flows and
personnel scheduling, are special cases. On the other hand, algorithms
developed to solve nonlinear, integer and stochastic programming
models usually use an LP code as a component in the solution process.
Situations arising from the fields of transportation, water resources,
manufacturing and many others give rise to network flow models.
A flow network is a collection of nodes and arcs. Each arc passes
from one node to another and carries a commodity called flow.
A requirement is that flow be conserved at each node. The optimization
problem is to find the flow in each arc that minimizes the total
cost of the flow in the network. The tour contains articles on
modeling, finding solutions, and algorithms that solve specific
network optimization problems
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. The
integrality requirement underlies a wide variety of applications.
There are many situations, such as distributing goods from warehouses
to factories or finding the shortest path through a network,
where the flow variables are logically required to be integer
valued. There are also situations that require logical decisions
of the form yes/no, go/no go, assign/dont assign. These
decisions can be modeled with binary variables that assume values
of zero or one. The power and usefulness of these models in
representing real-world situations cannot be overstated, but
along with modeling convenience comes substantial computational
difficulty. Only relatively small problems that contain integer
variables can be solved to optimality in most cases.
Much of the world is nonlinear so it is natural to pursue optimization
of nonlinear models. Economies of scale in manufacturing, for
example, lead to decreasing costs, while biological systems
commonly exhibit exponential growth. In the design of a simple
hatch cover, the shearing stress, bending stress and degree
of defection are each polynomial functions of flange thickness
and beam height. Similar relationships abound in engineering
design, economics, and distribution systems, to name a few.
The appeal of nonlinear programming (NLP) is strong because
of the modeling richness it affords. Unfortunately, NLP solvers
have not yet achieved the same level of performance and reliability
associated with LP solvers. For all but the most structured
problems, the solution obtained from an NLP solver may not be
globally optimal. This argues for caution. Before taking any
action, the decision maker should have a full understanding
of the nonlinearities governing the system under study.
Many planning and control problems in manufacturing, telecommunications
and capital budgeting call for a sequence of decisions to be
made at fixed points in time. The initial decision is followed
by a second, the second by a third, and so on perhaps infinitely.
Because the word dynamic describes situations that occur over
time and programming is a synonym for planning, the original
definition of dynamic programming was planning over time.
Dynamic programming has been described as the most general of
the optimization approaches because conceivably it can solve
the broadest class of problems. In many instances, this promise
is unfulfilled because of the attending computational requirements.
Certain problems, however, are particularly suited to the model
structure and lend themselves to efficient computational procedures;
in cases involving discontinuous functions or discrete variables,
dynamic programming may be the only practical solution method.
In this tour, we examine models that explicitly
include some aspects of uncertainty and describe analytic techniques
for dealing with decision problems in this environment. The
tour consists primarily of PDF supplements. The first is a complete
chapter that establishes the language of probability, describes
the named discrete or continuous random variables, provides
formulas for obtaining probabilities and moments for the distributions
and introduces Monte Carlo simulation. Other supplements are
chapter length descriptions of applications of OR that include
probability models. Two important add-ins are included in the
tour, the random variables add-in and the decision analysis
-Time Markov Chains
The discrete-time Markov Chain (DTMC) is a finite-state
stochastic process in which the defining random variables are
observed at discrete points in time. A feature of the process
is that the future probabilistic behavior of the process depends
only on the present state regardless of the path by which the
present state was reached. Unlike most stochastic processes,
the DTMC has very agreeable properties allowing for easy study.
Often they are used to approximate quite complex physical systems,
even when it is clear that the actual behavior of the system
being analyzed may depend on more than just the present state,
or when the number of states is not really finite.
-Time Markov Chains
A natural extension of a discrete-time Markov
chain occurs when time is treated as a continuous parameter.
For continuous time stochastic processes, the Markovian property
is only satisfied if all activity durations are exponentially
distributed. Although this may sound somewhat restrictive, many
practical situations can be modeled as continuous-time Markov
chains and many powerful analytical results can be obtained.
A primary example is an M/M/s Queuing system in which customer
arrivals and service times follow an exponential distribution.
Because it is possible to compute the steady-state probabilities
for such systems, it is also possible to compute many performance-related
statistics such as the average wait and the average number of
customers in the queue. In addition, many critical design and
operational questions can be answered with little computational
This tour considers situations that can be modeled
as single Queuing stations or networks of queues. For the single
Queuing station having one or more servers, a variety of analytical
results are available when the arrival and service processes
are Markovian. Formulas are available to compute statistical
estimates for such measures as the average number in the queue,
the average waiting time for a customer, and the probability
that the service mechanism is busy. Some results are also available
for models that are not Markovian. When several Queuing stations
are interconnected, we have a network of queues. Many decision
situations arise in this context. For Jacksonian networks, accurate
analytical results are available. Otherwise some approximate
results estimate performance measures. An add-in is provided
to analyze both single Queuing stations and networks of queues.
Of the analytic methods that comprise operations
research, simulation stands in sharp contrast to the mathematical
programming algorithms and stochastic models. With simulation,
the analyst creates a model of a system that describes some
process involving individual entities such as persons, products
or messages. The components of the model try to reproduce, with
varying degrees of accuracy, the actual operations of the real
components of the process. Most likely the system will have
time-varying inputs and time-varying outputs that are affected
by random events. The components of the simulation are interconnected
and can often be viewed as a network with complex input-output
relationships. Moreover, the flow of entities through the system
is controlled by logic rules that derive from the operating
rules and policies associated with the process being modeled.
Because the model takes the form of a computer program, which
operates as a facsimile of its real-world counterpart, it is
much less restricted than analytical models. A skilled programmer
can duplicate with a high level of accuracy, most systems that
can be observed and rationalized. Because of this capacity for
detail, simulation has become a very popular method of analysis.
Particularly appealing is its ability to model random variables
with arbitrary probability distributions and systems that have
a variety of interacting random processes. Modern simulation
languages are very powerful tools, allowing even a beginner
to create representations of complex systems.
This tour follows a trail through a series of
computational methods that are useful for the analysis of manufacturing
systems. The computations often use the techniques of operations
research, but they are adapted to specific applications. The
topics considered are often taught in an academic programs for
Operations Management and Industrial Engineering, but are useful
in a variety of applied fields.