Operations Research:
Theoretical, Computational and Implementation Issues
The first formal activities of Operations Research (OR) were initiated in England during World II, when a team of British scientists set out to make scientifically based decisions regarding the best utilization of war material. After the war, the ideas advanced in military operations were adapted to improve efficiency and productivity in the civilian sector.
The OR techniques can be used in scientific decision-making, design, quantitative analysis, and management.
Optimization = Efficiency + Savings
(to see the impact of Operations Research Table 1.1 in CO-beneficii(where Chapters 2-7 refer to Linear Programming; Ch.8 regards Transportation and assignment problems; Ch 9 concerns Network optimization models; Ch. 11 is on Integer Programming; Ch. 12 Nonlinear programming; Chapters 17 and 26 deal with Queueing theory and its applications; Ch. 18 treats Inventory theory; Ch. 20 regards Simulation;Ch. 27 refers to Forecasting).
IFORS (International Federation of Operations Research);
INFORMS (Institute for Operations Research and the Management Sciences); Interfaces
EURO XXV Computational Game Theory (only Romanian applicants)
In recent years, the field of Operations Research (OR) has experienced a virtual explosion in the amount of software designed to support current models of analysis and problem solving.
Motivation for studying Operations Research
To take advantage of the OR usefulness one must learn the standard mathematical models and OR techniques(solutions are determined by algorithms), as well as innovative methods and practical issues related to the use and development of computer implementations.
As a decision-making tool, OR is both a science and an art.
USERS
↓ ↓ ↓
OR → Decision ← Computer Science
Support tools
↓
Information Systems
Students need to know how to:
- evaluate the capabilities and limitations of the wide variety of software available;
- identify problems that the methods of OR can solve;
- structure the problems into standard mathematical models;
- apply or/and develop computational tools to solve the problems.
The aim of our OR course is to give the master student:
- a good foundation in the mathematics of OR and
- an appreciation of its potential applications.
Once the mathematical foundation has been established, the capabilities in the artistic side of OR modeling can be increased by studying published practical cases(case studies). A number of fully developed and analyzed cases that cover most of the OR models presented in this course can be provided by the instructor at request. Additional case studies are available in journals and publications. Particularly, Interfaces (published by INFORMS) is a rich source of diverse OR applications.
Phases of an OR Study (rooted in teamwork)
The principal phases for implementing OR in practice include:
- Definition of the problem. Many situations can be looked at as decision-making problems whose solution requires answering the questions:
- What are the decision alternatives?
- Under what restrictions is the decision made?
- What is an appropriate objective function for evaluating the alternatives?
The aim is to identify the principal elements of the decision problem: (1) the decision alternatives, (2) the object of the study, and (3) the limitations under which the modeled system operates.Defining the problem correctly is the most important (and most difficult) phase of practicing OR.
- Construction of the model. The problem definition is translated into mathematical relationships using suitable variables. If the resulted model fits one of the standard mathematical models, such as linear programming, we can usually reach a solution by using available algorithms. Alternatively, if the model is too complex, the OR team may opt to simplify the model and use a heuristic approach, or they may consider the use of simulation, if appropriate. In some cases, mathematical models, simulation, and heuristic models may be combined to solve the decision problem at stake. Mathematical modeling is a cornerstone of OR.
The general OR model can be organized in the general format:
Maximize/minimize Objective Function
subject to Constraints
- Model solution. This phase entails the use of well-defined optimization algorithms.
A solution of the model is feasibleif it satisfies all the constraints.
A solution is called optimalif, in addition of being feasible, it yields the best (maximum or minimum) value of the objective function. “The optimum solution” of a model is the best only for that model. The quality of the resulting solution depends on the completeness of the model in representing the real system.
An important aspect of the model solution phase is sensitivity analysis. It deals with obtaining additional information about the behavior of the optimum solution when the model undergoes some parameter changes. Sensitivity analysis is particularly needed when the parameters of the model cannot be estimated accurately; in such cases it is important to study the behavior of the optimum solution in the neighborhood of the estimated parameters.
- Validation of the model. Model validity checks whether (or not) the proposed model does what it purports to do. First, the team should check whether (or not) the solution (output data) makes sense and the results are intuitively acceptable. A common method for checking the validity of a model is to compare its output with historical output data. The model is valid if, under similar input conditions, it reasonably duplicates past performance. Generally, however, there is no assurance that future performance will continue to duplicate past behavior. If the proposed model represents a new system, since no historical data are available, we may use simulation as an independent tool for verifying the output of the mathematical model.
- Implementation of the solution. This phase involves the translation of the results into understandable operating instructions to be issued to the people who will administer the recommended system.
The most prominent OR techniquesare linear programming designed for models with linear objectivefunction and constraints, and integer programming (in which variables assume integer values).
LinearProgramming algorithms:Simplex/ Dual Simplex
Integer Programming algorithms: Branch and Bound (B&B) algorithm, Cutting Plane algorithm, Interior Point algorithm
Excel Solver, QSopt, SixPap
General applications of Linear/Integer Programming
- The transportation model and its variants
- The assignment model
- The transshipment model
- Network models
(The shortest-route problem, the maximal flow model, the critical path method (CPM))
- The set-covering problem
- The fixed-charge problem
- The traveling salesperson (TSP) problem
- Capital budgeting
- Models with “either-or” and “if-then” constraints
Problems of interest to computer scientists where linear/integer programming can be fruitful applied:
- Maximum flow
- Rank aggregation
- Combinatorial auctions
- Combinatorial reverse auctions
- Markov decision processes
(See CO-applications for a treatment of Problems1-5)
- Interoperability and integration of processes of knowledge discovery in databases(
- sat.html
- Multi-agent systems
- Secret sharing schemes; linear time secure cryptography.
Real world LP applications: urban planning, currency arbitrage, investment, production planning and inventory control, pollution control, voting on issues, water quality management, assigning students to schools, shelf space allocation, military planning, etc.
Introduction to Linear Programming through examples
A Maximization model
Example 2.1-1 (The Reddy Mikks Company; Taha (2008))Reddy Mikks produces both interior and exterior paints from two rawmaterials, M1 and M2. The following table provides the basic data of the problem:
Tons of raw material/ton of Maximum daily
Exterior paint Interior paint availability(tons)
Raw material M1 6 4 24
Raw material M2 1 2 6
Profit per ton ($1000) 5 4
A market survey indicates that the daily demand for interior paint cannot exceed that for exterior paint by more than one ton. Also, the maximum daily demand for interior paint is 2 tons. Reddy Mikks wants to determine the optimal (best) product mix of interior and exterior paints that maximizes the total daily profit.
The LP model, as in any OR model, has three basic components:
- Decision variables that we see to determine
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
- Objective (goal) that we need to optimize (maximize or minimize).
Letting z represent the total daily profit (in thousands of dollars), the objective of the company is
maximizez = 5x1 + 4x2.
- Constraints that the solution must satisfy.
Usage of raw material M1 by both paints = 6x1 + 4x2 tons/day
Usage of raw material M2 by both paints = 1x1 + 2x2 tons/day
The restrictions associated to daily availabilities of M1 and M2 are:
6x1 + 4x2 ≤ 24 (Raw material M1)
x1+ 2x2 ≤ 6 (Raw material M2).
The market restrictions are:
x2 – x1 ≤ 1 (Market limit)
x2 ≤ 2 (Demand limit).
The non-negativity restrictionsare:
x1 ≥ 0, x2 ≥ 0.
A Minimization Model
Example 2.2-2 (Diet Problem)Ozarks Farms uses at least 800 lb of special feed daily. The special feed is a mixture of corn and soybean meal with the following compositions:
lb per lb of feedstuff
------
Feedstuff Protein Fiber Cost($/lb)
Corn 0.09 0.02 0.30
Soybean meal 0.60 0.06 0.90
The dietary requirements of the special feed are at least 30% protein and at most 5% fiber. Ozark Farms wishes to determine the daily minimum cost feed mix.
The decision variables of the model are:
x1 = lb of corn in the daily mix
x2 = lb of soybean meal in the daily mix.
The objective function is expressed as
minimizez = 0.3 x1 + 0.9 x2.
The constraint associated with the dietary requirements is:
x1 + x2 ≥ 800.
The protein dietary requirement constraint is
0.09 x1 + 0.6 x2 ≥ 0.3(x1 + x2).
The fiber dietary requirement constraint is
0.02 x1 + 0.06 x2 ≤ 0.05(x1 + x2).
The complete model becomes:
minimizez = 0.3 x1 + 0.9 x2
subject to
x1 + x2 ≥ 800
0.21 x1 ─ 0.30x2 ≤ 0
0.03 x1 ─ 0.01x2 ≥ 0
x1, x2 ≥ 0.
Graphical LP solution
The graphical procedure includes two steps:
- Determination of the feasible solution space.
- Determination of the optimal solution from among all the feasible points in the solution space.
Step 1. The nonnegativity of the variables restricts the solution-space area to the first quadrant that lies above the x1- axis and to the right to the x2-axis. To account for the remaining constraints, first replace each inequality with an equation and then graph the resulting straight line by locating two distinct points on it. Next, consider the effect of the inequality. All it does is to divide the (x1, x2)-plane into two half-spaces, one on each side of the graphed line. Only one of these two halves satisfies the inequality. To determine the correct side, choose (0, 0) as a reference point (unless the line happens to pass through the origin, in which case any other point can be used). If it satisfies the inequality, then the side in which it lies is the feasible half-space, otherwise the other side is. We can use an arrow to point to the feasible half-space. The feasible solution spaceof the problem represents the area in the first quadrant in which all the constraints are satisfied simultaneously.
Figure 2.1 Feasible space of the Reddy Mikks model: ABCDEF
Step 2. Because the feasible space consists of an infinite number of points, we need a systematic procedure to identify the optimum solution. The determination of the optimal solution requires identifying the direction in which the profit function increases (when we are maximizing z). We can do so by assigning arbitrary increasing values to z, which is equivalent to graphing two lines. The optimum solution occurs at a corner which is the point in the solution space beyond which any further increase will put z outside the boundaries of the feasible solution space. The values of x1 and x2 associated with the optimum point are determined by solving the systems consisting of the equations associated with the corresponding lines. An important characteristic of the optimum LP solution is that it is always associated with a corner pointof the solution space (where two lines intersect). This is true even if the objective function happens to be parallel to a constraint-line (case in which any point on that line segment will be an alternative optimum, but the important observation here is that the line segment is totally defined by its corner points.
Figure 2.2Optimum solution of the Reddy Mikks model (point C)
Figure 2.3 Graphical solution of the diet model
Algebraic solution (The simplex method)
In the simplex method the solution space is represented by m simultaneously linear equations with n nonnegative variables, where m≤n. If m = n, and the equations are consistent, the system has only one solution; but if mn (which represents the majority of LPs), then the system of equations, again if consistent, will yield an infinite number of solutions.
Two requirements on the constraints of the problem are imposed to standardize and streamline the simplex method calculations:
- All the constraints (with the exception of the non-negativity of the variables are equations with nonnegative right-hand side.
- All the variables are nonnegative.
However, all commercial packages directly accept inequality constraints, negative right-hand side, and unrestricted variables. Any necessary preconditioning of the model is done internally in the software before the simplex method solves the problem.
Converting Inequalities in Equations with Nonnegative Right-Hand Side
In (≤) constraints, the right-hand side can be thought of as representing the limit on the availability of a resource, in which case the left-hand side would represent the usage of the limited resource by the activities (variables) of the model. The difference between the right-hand side and the left-hand side of the (≤) constraint thus yields the unused or slackamount of the resource. To convert a (≤) - inequality to an equation, a nonnegative slack variableis added to the left-hand side of the constraint.
A (≥) – constraint sets a lower limit on the activities of the LP model, so that the amount by which the left-hand side exceeds the minimum limit represents a surplus. The conversion from (≥) to (=) is achieved by subtracting a nonnegative surplus variable from the left-hand side of the inequality.
The only remaining requirement is for the right-hand side of the resulting equation to be nonnegative. The condition can always be satisfied by multiplying both sides of the resulting equation by ─ 1, where necessary.
Dealing with Unrestricted Variables
We can always account for the non-negativity requirement by using for any unrestricted variable xithe substitution
xi = xi+ ─ xi─, where xi+ ≥ 0 and xi─ ≥ 0.
The candidates for the optimum (i.e. corner points) are determined from the simultaneous linear equations in the following manner:
Algebraic Determination of Corner Points
In a set of m equations with n variables (m n), if we set n ─ m variables equal to zero and then solve the m equations for the remaining m variables, the resulting solution, if unique, is called a basic solutionand must correspond to a (feasible or infeasible) corner point of the solution space. This means that the maximum number of corner points is Cnm.
Without the benefit of the graphical solution (which is available only for two or three variables), we cannot say which (n ─ m) zero variables are associated with which corner point. But that does not prevent us from enumerating all the corner points of the solution space. Once done, the optimum solution is the feasible basic solution (corner point) that yields the best objective value.
The zero n ─ m variable are known as nonbasicvariables. The solution corresponding to basicvariables(obtained by solving the m equations) is referred to as basic solution.
Example 3.2-1 (Taha (2008), p.87-88)
Remarks. As the problem size increases (i.e. m and n become large), the procedure of enumerating all the corner points involves prohibitive computations. For example, for m = 10 and n = 20 (which is a small size in most real-life situations) it is necessary to solve 184756 sets of 10 x 10 equations. The simplex method alleviates the computational burden dramatically by investigating only a fraction of all possible basic feasible solutions (corner points) of the solution space. In essence, the simplex method utilizes an intelligent search procedure that locates the optimum corner point in an efficient manner.
Homework: Find the graphical solutions for the following LP problems:
- Maximizez = 3x1 + 9x2
subject to
x1 + 4x2 ≤ 8
x1 + 2x2 ≤ 4
x1,x2 ≥ 0.
- Maximizez = 2x1 + 4x2
subject to
x1 + 2 x2 ≤ 5
x1 + x2 ≤ 4
x1, x2 ≥ 0.
- Maximizez = 2x1 + x2
subject to
x1 ─ x2 ≤ 10
2x1 ≤ 40
x1, x2 ≥ 0.
4. Maximizez = 3x1 + 2x2
subject to
2x1 + x2 ≤ 2
3x1 + 4x2 ≥ 12
x1, x2 ≥ 0.
Computer solution with Excel Solver
In practice, where typical linear programming models may involve thousands of variables and constraints, the only feasible way to solve such models is to use the computer. There are distinct types of popular software. Excel Solver is particularly appealing to spreadsheet users (see p.69-72 (Taha, 2008)).
Other available LP software for laboratory works: QSopt, SixPap.
Other available software resources:
- OR TUTOR, Interactive OR Tutorial
- EXCEL ADD-INS: Premium Software for Education, SensIt,TreePlan, RiskSim, Crystal Ball (each of these add-ins needs to be installed in Excel before it is operational).
- MPL/CPLEX (the website for exploring MPL and its solvers, or for downloading updated student versions of MPL/CPLEX is
OptiMax 2000
- LINGO/LINDO (updated version student of LINGO and LINDO (as well as the companion spreadsheet solver What’s Best) can be downloaded from the website