|
|
 |
Ch. 2 Linear ProgrammingModels |
|
| Additional Exercises |
Equivalent Linear Programs
There are a number of problems that do not at first appear
to be candidates for linear programming but, in fact, have
an equivalent or approximate representation that fits the
LP framework. In these instances, the solution to the equivalent
problem gives the solution to the original problem. Among
the subjects considered in this supplement are: nonlinear
objective functions, maximizing the minimum, goal programming,
fractional programming, and the complementarity problem.
The supplement includes exercises. |
Chemical Processing
We consider a somewhat larger problem than those used in
Chapter 2 as a medium for the discussion of the modeling
process. The example is especially informative in that it
incorporates a number of features found in many real-world
applications. |
|
|
|
|
Ch. 3 Linear ProgrammingMethods |
|
Additional Exercises |
|
|
Ch. 4 Sensitivity Analysis, Duality and Interior Point
Methods |
|
Additional Exercises
|
|
|
Ch. 6 Network Flow Programming Methods |
|
Relation of Pure Minimum Cost Flow Model to Linear
Programming
Network flow programming is really a special case of linear
programming. This supplement describes the relationship
between the two models, their primal and dual variables
and solution algorithms. |
Primal Simplex Algorithm for the Pure Minimal Cost
Flow Problem
Based on the primal and dual variables described in Chapter
6, we provide an algorithm to solve the minimum cost flow
problem for pure network problems. Exercises are included. |
Generalized Network Flow Programming
This chapter long supplement adapts the bounded variable
primal simplex method to the generalized minimum cost flow
problem. Exercises are included. |
|
|
|
Ch. 8 Integer Programming Methods |
|
Additional Branch and Bound Algorithms
Two additional sections and associated exercises comprise
this supplement. One provides an example branch and bound applied
to the 0-1 mixed integer programming problem. The second describes
Balas' implicit enumeration procedure. |
|
|
Ch. 9 Nonlinear Programming Models |
|
Additional Exercises
|
|
|
Ch. 10 Nonlinear Programming Methods |
|
Algorithms for Constrained Optimization
In this additional section, we present several procedures
for solving the nonlinear programming problem. The first is the
now classical penalty approach developed by Fiacco and McCormick
[1968] and is perhaps the simplest to implement. The second is
Zoutendijk's feasible direction method. Other primal approaches
discussed in the literature include the gradient projection method
and the generalized reduced gradient method that is a simplex-like
algorithm. |
|
|
Ch. 18 Simulation |
|
Statistics from Simulations
Three appendices to the Simulation chapter are provided by
this supplement: Statistical Inference and Estimation of Population
Parameters, Chi-Square Goodness-of-Fit Test, and Kolmogorov-Smirnov
Goodness-of-Fit Test |
|
|
Ch. 19 Dynamic Programming Models |
|
Dynamic Programming Models
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.
This supplement is a complete chapter with exercises. |
|
|
Ch. 20 Dynamic Programming Methods |
|
Dynamic Programming Methods
Although all dynamic programming (DP) problems have a similar
structure, the computational procedures used to find solutions
are often quite different. Unlike linear and integer programming
where standard conventions are used to describe parameters and
coefficients, there is no common data structure that unifies all
DPs. Models are problem specific, and for the most part, are represented
by recursive formulas rather than algebraic expressions. This
supplement is a complete chapter with exercises. The chapter describes
the principal compuational procedures used to solve dynamic programming
models. |
|
|
Ch. 21 Probability Models |
|
Probability Models
Here we present the language of probability that is used to model
situations whose outcomes cannot be predicted with certainty.
In important instances, reasonable assumptions allow single random
variables to be described using one of the named discrete or continuous
random variables. The chapter summarizes the formulas for obtaining
probabilities and moments for these distributions. When combinations
of several random variables affect the system output, the method
of simulation is often used to learn about a system. Here we provide
an introduction to the subject. |
|
|
Ch. 22 Time Series and Forecasting |
|
Time Series and Forecasting
A time series is a sequence of observations of a periodic random
variable. Examples are: the monthly demand for a product, the
annual freshman enrollment in a department of the university and
the daily flows in a river. Time series are important for operations
research because they are often the drivers of operations research
decision models. Time series analysis provides tools for selecting
a model that describes the time series and using the model to
forecast future events. Modeling the time series is a statistical
problem because observed data is used in computational procedures
to estimate the parameters of a supposed model. |
|
|
Ch. 23 Decision Analysis |
|
Decision Analysis
Consider a situation requiring a series of decisions. The problem
is complicated however in that the results of some of the decisions
are not deterministic. Rather, the results are governed by known
probability distributions. Decision analysis provides a model
for handling processes involving an ordered series of decisions
interrupted by random events. Many practical situations can be
modeled in this way. Solution procedures find the optimum decisions
that maximize the expected net benefit. |
|
|
Ch. 24 Game Theory |
|
Game Theory
The decision problems we often face are associated with another
individual who may be an opponent. We must make decisions knowing
that the result will be governed in part by the actions of another.
The part of operations research that deals with this kind of situation
is called game theory. Although clearly applicable to games as
the name implies, it is appropriate for the wide variety of contexts
in which one must make a decision whose result will be impacted
by the actions of one or more individuals. |
|
|
Ch. 25 Inventory Theory |
|
Inventory Theory
Because of practical and economic importance of industrial inventories,
the subject of inventory control is a major consideration in many
situations. Questions must be constantly answered as to when and
how much raw material should be ordered, when a production order
should be released to the plant, what level of safety stock should
be maintained at a retail outlet, or how in-process inventory
is to be maintained in a production process. These questions are
amenable to quantitative analysis through the subject of inventory
theory. |
|
|
Ch. 26 Reliability |
|
Reliability
The name reliability is given to the field of study that attempts
to assign numbers to the propensity of systems to fail. In a more
restrictive sense, the term "reliability" is defined
to be the probability that a system performs its mission successfully.
Since mission is often specified in terms of time, reliability
is often defined as the probability that a system will operate
satisfactorily for a given time. Thus reliability may be a function
of time. We use probability models to compute the reliability
of a complex system. |
|
|
Ch. 27 Stochastic Optimization |
|
Stochastic Optimization
Operations research has been particularly successful in two areas
of decision analysis: (i) optimization of problems involving many
variables when the outcome of the decisions can be predicted with
certainty, and (ii) the analysis of situations involving a few
variables when the outcome of the decisions cannot be predicted
with certainty. In this chapter, we combine optimization and uncertainty
and consider two decision models that explicitly incorporate the
probability distributions of random variables. Both are solved
with linear programming (LP). Although we will see that rather
simple situations lead to large LP models, the general availability
of efficient LP algorithms may make the solution of such problems
practical. |
| |
|
|
