Operations research

Introduction.

1.1

Some history

There is no clear date that marks the birth of Operations (or Operational) Research (OR) such as a
book or a seminal article, but it is generally accepted that this mathematical branch originated in UK
during World War II. It started with the development of radar defense systems for the Royal Air Force,
and the rst use of the term Operations Research is attributed to a British Air Ministry ocial after the
initiation of teams to do "operational researches" on the communication system and the control room at
a British radar station ([Zandin01]).
This new approach of picking an "operational" system and conducting "research" on how to make
it run more eciently soon started to expand into other arenas of the war. In the years immediately
following the end of World War II, O.R. grew rapidly as many scientists realized that the principles
that they had applied to solve problems for the military were equally applicable to many problems in
the civilian sector. After the war, the ideas advanced in military operations were adapted to improve
eciency and productivity in the civilian sector ([Zandin01]).
OR is often concerned with determining the maximum (of prot, performance, or yield) or minimum
(of loss, risk, or cost) of some real-world objective. The problems addressed by OR range from short-term
problems such as scheduling and inventory control to long-term problems such as strategic planning and
resource allocation.
Today the OR techniques can be used in scientic decision-making, design, quantitative analysis, and
management.

1.2

Two definitions

OR is a discipline that deals with the application of advanced analytical methods to help make
better decisions. Employing techniques from other mathematical sciences, such as mathematical
modeling, statistical analysis, and mathematical optimization, OR arrives at optimal or nearoptimal solutions to complex decision-making problems (INFORMS site).
OR, application of scientific methods to the management and administration of organized military, governmental, commercial, and industrial processes (Encyclopedia Britannica).
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 eld of Operations Research (OR) has experienced a virtual explosion in the
amount of software designed to support current models of analysis and problem solving.

1.3

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.
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

1

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.

1.4

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:
1. What are the decision alternatives?
2. Under what restrictions is the decision made?
3. 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.
Dening the problem correctly is the most important (and most dicult) phase of practicing OR.

Construction of the model. The problem denition is translated into mathematical relationships
using suitable variables. If the resulted model ts 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-dened optimization algorithms.
A solution of the model is feasible if it satises all the constraints.
A solution is called optimal if, 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 techniques are linear programming designed for models with linear objective function and constraints, and integer programming (in which variables assume integer values).
Linear Programming algorithms: Simplex/ Dual Simplex.
Integer Programming algorithms: Branch and Bound (B&B) algorithm, Cutting Plane algorithm,
Interior Point algorithm.
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 ow model, the critical path method
(CPM))
The set-covering problem
The xed-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:
1 . Maximum ow.
2. Rank aggregation.
3 . Combinatorial auctions.
4. Combinatorial reverse auctions.
5. Markov decision processes (See CO-applications for a treatment of Problems1-5).

6. Interoperability and integration of processes of knowledge discovery in databases (http://thor.info.uaic.ro/ dgorea/the

7. http://www.cs.cornell.edu/ tomf/pyglpk/ex sat.html
8. Multi-agent systems.
9. Secret sharing schemes; linear time secure cryptography.

Linear Programming
2

Introduction through examples

2.1

Reddy Mikks example

Reddy Mikks Company ([Taha07]) produces both interior and exterior paints from two raw materials,

1 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
Prot 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 prot.
The correspondingly LP model, as in any OR model, has three basic components:
1. decision variables that we see to determine:

1 = tons produced daily of exterior paint;

x2 = tons produced daily of interior paint.
x

2. objective (goal) that we need to optimize (maximize or minimize).

letting z represent the total daily prot (in thousands of dollars), the objective of the company
is
maximize z = 5x1 + 4x2 .
3. constraints that the solution must satisfy:
Usage of raw material M1 by both paints = 6x1 + 4x2 tons/day and usage of raw material
both paints = 1x1 + 2x2 tons/day.
The restrictions associated to daily availabilities of

1 and M2 are:

6x1 + 4x2 6 24 (Raw material M1 );

x1 + 2x2 6 6 (Raw material M2 ).
The market restrictions are:

2 x1 6 1 (market limit);
2 6 2 (demand limit).

x
x

The non-negativity restrictions are:

1 > 0, x2 > 0.

The complete model becomes:

maximize
subject to

= 5x1 + 4x2

6x1 + 4x2
x1 + 2x2
x

1
2
x1 ; x2
x

6 24
6 6
6 1
6 2
> 0

2 by

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 feedstu
Feedstu
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% ber. Ozark
Farms wishes to determine the daily minimum cost feed mix.
The correspondingly LP model:
1. the decision variables of the model are:

1 = lb of corn in the daily mix;

x2 = lb of soybean meal in the daily mix.
x

2. the objective is expressed as:

letting

represent the cost for lb of special feed, the objective of the company is

maximize

= 0:3x1 + 0:9x2 .

3. the constraints are:

The constraint associated with the dietary requirements is:

1 + x2 > 800.

The protein dietary requirement constraint is:

0:09x1 + 0:6x2 > 0:3(x1 + x2 ).

The ber dietary requirement constraint is

0:02x1 + 0:06x1 6 0:05(x1 + x2 ).

The complete model becomes:
minimize
subject to

= 0:3x1 + 0:9x2

0:21x1
0:03x1

1 + x2
0:30x2
0:01x2

1 2

x ;x

>
6
>
>

800
0
0
0

Graphical LP solution
The graphical procedure includes two steps:
1. Determination of the feasible solution space.
2. Determination of the optimal solution from among all the feasible points in the solution space.

First step The non-negativity of the variables restricts the solution-space area to the rst quadrant
that lies above the x1 - axis and to the right to the x2 -axis.
To account for the remaining constraints, rst replace each inequality with an equation and then
graph the resulting straight line by locating two distinct points on it. Next, consider the eect of the
inequality. The line divides the (x1 ; x2 )-plane into two half-spaces, one on each side of the graphed
line. Because of the convexity of a half-space, only one of these two halves satises the inequality. To
determine the correct side, choose a point outside the line (for e.g. (0; 0) if its possible). If it satises
the inequality, then the side in which it lies this point 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 space of the problem represents the area in the rst quadrant in which all
the constraints are satised simultaneously.
Second step Because the feasible space consists of an innite 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 prot function increases (when we are maximizing z ). We can do so by assigning two 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.
x2
6x1 + 4x2 24 (1)

(5)

x1 + 2x2 6 (2)
x2 x1 1 (3)
6

x2 2 (4)
x1 0 (5)
x2 0 (6)
(1)

(3)

Feasible solution
space

(2)

(4)

B
E

A
O

(6)

x1

Figure 1:
An important characteristic of the optimum LP solution is that it is always associated with a corner
point of 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 dened by its corner
points.

4
n

Algebraic LP solution
In the simplex method the solution space is represented by m simultaneously linear equations with
non-negative variables, where m 6 n. If m = n, and the equations are consistent, the system has only

x2

increasing z

z = 5x1 + 4x2

C
B(3, 1.5)

A
x1
z

30

10

Figure 2:
x2

Feasible solution
space

(4)

x1 + x2 800 (1)
(3)

7x1 10x2 0 (2)

3x1 x2 0 (3)

800

x1 0 (4)
(2)

x2 0 (5)

A
(1)

800

(5)

x1

Figure 3:
one solution; but if m < n (which represents the majority of LPs), then the system of equations, again
if consistent, will yield an innite number of solutions.
Two requirements on the constraints of the problem are imposed to standardize and streamline the
simplex method calculations:
1. all the constraints (with the exception of the non-negativity of the variables are equations with
non-negative right-hand side;

2. all the variables are non-negative.

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.

4.1

Converting Inequalities in Equations with Non-negative Right-Hand Side

In (6) 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 dierence between the right-hand side and the left-hand side of the (6) constraint thus yields
the unused or slack amount of the resource. To convert a (6) - inequality to an equation, a non-negative
slack variable is 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 non-negative 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 non-negative.
The condition can always be satised by multiplying both sides of the resulting equation by 1, where
necessary.
x2

z = 3x1 + 9x2

z=
810
0

z=
630
0

A(470.6, 329.4)

decreasing z

x1

Figure 4:

4.2

Dealing with Unrestricted variable

We can always account for the non-negativity requirement by using for any unrestricted variable
the substitution
xi

= x+
i xi ; where

xi

+ > 0 and x > 0:

i

xi

The candidates for the optimum (i.e. corner points) are determined from the simultaneous linear
equations in a manner described in the following subsection.

4.3

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
solution and 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 benet 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.
EXAMPLE 1

maximize z = 2x1 + 3x2

subject to 2x1 + x2 6 4
x1 + 2x2
6 5
x1 ; x2
> 0

Graphical solution to this problem is in the following gure.

x2

C
2.5

Y
O

x1

Figure 5:
Algebraically, the feasible solution space of this problem is represented as

2x1 + x2 + s1
x1 + 2x2 + s2

1 2 1 2

x ;x ;s ;s

= 4
= 5
> 0

The system has m = 2 and n = 4 variables. Thus, according to the above given rule, the corner
points can be determined algebraically by setting n m = 4 2 = 2 variables equal to zero and then
solving for the remaining m = 2 variables. For example
x

1 = s1 = 0 ) x2 = 4; s2 = 3; point X (0; 4)
9

1 = s2 = 0 ) x1 = 1; x2 = 2; point B (1; 2)

In order to nd an optimum solution we have to consider all the corner points of the solution space.
The optimum solution is the feasible basic solution with the best objective value.
In this example we have C42 = 6 corner points; four of them are extreme points of the feasible solution
space (O, A, B , C , and D). The remaining two represent infeasible solutions because they do not satisfy
all the constraints (X and Y ).
To summarize the transition from the graphical to the algebraic solution, the zero n m variables are
known as nonbasic variables. The remaining m variables are called basic variables and their solution
(obtained by solving the m equations) is referred to as basic solution. The following table provides all
the basic and nonbasic solutions of the current example.
nonbasic
basic
basic
corner
objective
feasibility
variables variables solution point
value
(x1 ; x2 )
(s1 ; s2 )
(4; 5)
O
yes
0
(x1 ; s1 )
(x2 ; s2 )
(4; 3)
X
no
yes
7:5
(x1 ; s2 )
(x2 ; s1 ) (2:5; 1:5)
C
(s1 ; s2 )
(x1 ; s2 )
(1; 2)
B
yes
8
(x2 ; s1 )
(x1 ; s2 )
(2; 3)
A
yes
4
(x2 ; s2 )
(x1 ; s1 )
(5; 6)
Y
no

optimum

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 ecient manner.

References
[Hillier05] Hillier, F. S., G. J. Lieberman, Introduction to Operations Research, McGraw-Hill, 7th
edition, 2001.
[Morris94] Morris, P., Introduction to Game Theory, Springer Verlag, New York, 1994.
[Taha07] Taha, H. A., Operations Research: An Introduction, Prentice Hall International, 2007.
[Zandin01] Zandin, K., (Ed.), Maynards Industrial Engineering Handbook, McGraw-Hill Professional,
5th edition, pp. 11.27-11.44, 2001.

10