Term
|
Definition
| 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. |
|
|
Term
| What is Linear Programming? |
|
Definition
| 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. |
|
|
Term
| What is Network Flow Programming? |
|
Definition
| 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. |
|
|
Term
| What is Integer Programming? |
|
Definition
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. |
|
|
Term
| What is Nonlinear Programming? |
|
Definition
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. |
|
|
Term
| What is Dynamic Programming? |
|
Definition
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. |
|
|
Term
| What is Stochastic Programming? |
|
Definition
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. |
|
|
Term
| What is Combinatorial Programming? |
|
Definition
| 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. |
|
|
Term
| What are Stochastic Processes? |
|
Definition
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. |
|
|
Term
| What are Discrete Time Markov Chains? |
|
Definition
| 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. |
|
|
Term
| What are Continuous Time Markov Chains? |
|
Definition
| 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. |
|
|
Term
|
Definition
| 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. |
|
|
Term
|
Definition
| accepts data from its environment, processes data, and produces output data for decision making. E.g., an information system for processing student loans helps a service provider track loans for lending institutions; system consists of lenders, students, and government agencies. |
|
|
Term
|
Definition
| set of related components that work together to accomplish some objectives. |
|
|
Term
|
Definition
| to provide long-term memory for an information system. |
|
|
Term
Preliminary Investigation Phase: Produces a problem statement and feasibility study.
The problem statement includes the objectives, constraints, and scope of the system.
The feasibility study identifies the costs and benefits of the system. If the system is feasible,
approval is given to begin systems analysis.
• Systems Analysis Phase: Produces requirements describing processes, data, and environment
interactions. Diagramming techniques are used to document processes, data,
and environment interactions. To produce the requirements, the current system is studied
and users of the proposed system are interviewed.
• Systems Design Phase: Produces a plan to efficiently implement the requirements.
Design specifications are created for processes, data, and environment interaction. The
design specifications focus on choices to optimize resources given constraints.
• Systems Implementation Phase: Produces executable code, databases, and user documentation.
To implement the system, the design specifications are coded and tested. Before making the new system operational, a transition plan from the old system to the
new system is devised. To gain confidence and experience with the new system, an
organization may run the old system in parallel to the new system for a period of time.
• Maintenance Phase: Produces corrections, changes, and enhancements to an operating
information system. The maintenance phase commences when an information system
becomes operational. The maintenance phase is fundamentally different from other
phases because it comprises activities from all of the other phases. The maintenance phase ends when developing a new system becomes cost justified. Due to the high fixed
costs of developing new systems, the maintenance phase can last decades.
The traditional life cycle has been criticized for several reasons. First, an operating system is not produced until late in the process. By the time a system is operational, the
requirements may have already changed. Second, there is often a rush to begin implementation
so that a product is visible. In this rush, appropriate time may not be devoted to
analysis and design.A number of alternative methodologies have been proposed to alleviate these difficulties. In spiral development methodologies, the life cycle phases are performed for subsets
of a system, progressively producing a larger system until the complete system emerges.
Rapid application development methodologies delay producing design documents until
requirements are clear. Scaled-down versions of a system, known as prototypes, are used to
clarify requirements. Prototypes can be implemented rapidly using graphical development
tools for generating forms, reports, and other code. Implementing a prototype allows users
to provide meaningful feedback to developers. Often, users may not understand the
requirements unless they can experience a prototype. Thus, prototyping can reduce the risk
of developing an information system because it allows earlier and more direct feedback
about the system.
In all development methodologies, graphical models of the data, processes, and environment
interactions should be produced. The data model describes the kinds of data and relationships.
The process model describes relationships among processes. A process can provide
input data used by other processes and use the output data of other processes. The
environment interaction model describes relationships between events and processes. An
event such as the passage of time or an action from the environment can trigger a process to
start or stop.The systems analysis phase produces an initial version of these models.The systems
design phase adds more details so that the models can be efficiently implemented.
Even though models of data, processes, and environment interactions are necessary to
develop an information system, this book emphasizes data models only. |
|
Definition
|
|
