Operations Research, Operational Research, or Simply OR, Is The Use of Mathematical Models
Operations Research, Operational Research, or Simply OR, Is The Use of Mathematical Models
Operations Research, Operational Research, or Simply OR, Is The Use of Mathematical Models
INTRODUCTION
Operations research, operational research, or simply OR, is the use of mathematical models,
statistics and algorithms to aid in decision-making. It is most often used to analyze complex real-
world systems, typically with the goal of improving or optimizing performance. It is one form of
applied mathematics.
The terms operations research and management science are often used synonymously. When
a distinction is drawn, management science generally implies a closer relationship to the problems
of business management.
Operations research also closely relates to industrial engineering. Industrial engineering takes more
of an engineering point of view, and industrial engineers typically consider OR techniques to be a
major part of their toolset.
Some of the primary tools used by operations researchers are statistics, optimization, stochastics,
queueing theory, game theory, graph theory, and simulation. Because of the computational nature
of these fields OR also has ties to computer science, and operations researchers regularly use
custom-written or off-the-shelf software.
Operations research is distinguished by its ability to look at and improve an entire system,
rather than concentrating only on specific elements (though this is often done as well). An
operations researcher faced with a new problem is expected to determine which techniques are
most appropriate given the nature of the system, the goals for improvement, and constraints on
time and computing power. For this and other reasons, the human element of OR is vital. Like any
tools, OR techniques cannot solve problems by themselves.
Areas of application
A few examples of applications in which operations research is currently used include the following:
designing the layout of a factory for efficient flow of materials
constructing a telecommunications network at low cost while still guaranteeing quality
service if particular connections become very busy or get damaged
determining the routes of school buses so that as few buses are needed as possible
designing the layout of a computer chip to reduce manufacturing time (therefore
reducing cost)
managing the flow of raw materials and products in a supply chain based on uncertain
demand for the finished products
Introduction
Define OR
OR is the application of scientific methods, techniques and tools to problems involving the
operations of a system so as to provide those in control of the system with optimum solutions to
the problems.
Characteristics of OR
1. its system orientation
2. the use of interdisciplinary teams
3. application of scientific method
4. uncovering of new problems
5. improvement in the quality of decisions
6. use of computer
7. quantitative solutions
8. human factors
Phases of OR
1) formulating the problem
in formulating a problem for OR study, we mist be made of the four major components.
i) The environment
ii) The decision maker
iii) The objectives
iv) Alternative course of action and constraints
2) Construction a Model
After formulating the problem, the next step is to construct mode. The mathematical model
consists of equation which describe the problem.
the equation represent
i) Effectiveness function or objective functions
ii) Constraints or restrictions
The objective function and constraints are functions of two types of variable, controllable
variable and uncontrollable variable.
A medium-size linear programming model with 50 decision variable and 25 constraints will have
over 1300 data elements which must be defined.
3) Deriving solution from the model
an optimum solution from a model consists of two types of procedure: analytic and numerical.
Analytic procedures make use of two types the various branches of mathematics such as
calculus or matrix algebra. Numerical procedure consists of trying various values of controllable
variable in the mode, comparing the results obtained and selecting that set of values of these
variables which gives the best solution.
4) Testing the model
a model is never a perfect representation of reality. But if properly formulated and correctly
manipulated, it may be useful predicting the effect of changes in control variable on the over all
system.
5) Establishing controls over solution
a solution derived from a model remains a solution only so long as the uncontrolled variable
retain their values and the relationship between the variable does not change.
6) Implementation
OR is not merely to produce report to improve the system performance, the result of the
research must implemented.
additional changes or modification to be made on the part of OR group because many time
solutions which look feasible on paper may conflict with the capabilities and ideas of persons.
Limitations of OR
1) Mathematical models with are essence of OR do not take into account qualitative factors or
emotional factors.
2) Mathematical models are applicable to only specific categories of problems
3) Being a new field, there is a resistance from the employees the new proposals.
4) Management, may offer a lot of resistance due to conventional thinking.
5) OR is meant for men not that men are meant for it.
Difficulties of OR
1) The problem formulation phase
2) Data collection
3) Operations analyst is based on his observation in the past
4) Observations can never be more than a sample of the whole
5) Good solution to the problem at right time may be much more useful than perfect solutions.
Linear Programming
Requirements for LP
1. There must be a well defined objective function which is to be either maximized or minimized
and which can expressed as a linear function of decision variable.
2. There must be constraints on the amount of extent of be capable of being expressed as linear
equalities in terms of variable.
3. There must be alternative course of action.
4. The decision variable should be inter-related and non-negative.
5. The resource must be limited.
n
that is, z c j x j c , that is, the optimal values are just independent of any constant c.
j 1
It is required to determine the daily number of units to be manufactured for each product. The
profit per unit for product 1,2 and 3 is Rs. 4, Rs. 3 and Rs. 6 respectively. It is assumed that all the
amounts produced are consumed in the market.
Solution:
The objective is to maximize the total number of potential customers.
That is, maximize Z = (2x1 + 6x2 + 1.5x3 + x4) * 105
Constraints are
On the advertising budget 30,000x1 + 20,000x2 + 15,000x3 + 10,000x4 4,50,000
On number of female 1,50,000x1 + 4,00,000x2 + 70,000x3 + 50,000 x4 10,00,000
On expense on magazine 15,000x3 + 10,000x4 1,50,000
On no. of units on magazines x3 3, x4 2
On no. of unit on television 5 x2 10, 5 x2 10
Example 3 :
A company has two grades of inspectors, 1 and 2 to undertake quality control inspection. At least
1,500 pieces must be inspected in an 8 hour day. Grade 1 inspector can check 20 pieces in an hour
with an accuracy of 96%. Grade 2 inspector checks 14 pieces an hour with an accuracy of 92%.
The daily wages of grade 1 inspector are Rs. 5 per hour while those of grade inspector are Rs. 4
per hour, any error made by an inspector costs Rs. 3 to the company. If there are, in all, 10 grade
1 inspectors and 15 grade 2 inspectors in the company, find the optimal assignment of inspectors
that minimize the daily inspection cost.
Solution
Let x1, x2 be the inspector of grade 1 and 2.
Grade 1: 5 + 3 * 0.04 * 20
Grade 2: 4 + 3 * 0.08 * 14
Z = 8*(7.4x1 + 7.36x2)
X1 10, x2 15
20 * 8 x1 + 14* 8 x2 1500
Example 4:
An oil company produces two grades of gasoline P and Q which it sells at Rs. 3 and Rs.4 per litre.
The refiner can buy four different crude with the following constituents an costs:
Crude Constituents Price/litre
A B C
1 0.75 0.15 0.10 Rs. 2.00
2 0.20 0.30 0.50 Rs. 2.25
3 0.70 0.10 0.20 Rs. 2.50
4 0.40 0.60 0.50 Rs. 2.75
The Rs. 3 grade must have at least 55 percent of A and not more than 40% percent of C. The Rs. 4
grade must not have more than 25 percent of C. Determine how the crude should be used so as to
maximize profit.
Solution:
Example 5:
A person wants to decide the constituents of a diet which will fulfill his daily requirements of
proteins, fats and carbohydrates at the minimum cost. The choice is to be made from four different
types of foods. The yields per unit of these foods are given below
Yield per unit Cost per
Food type Proteins Fats Carbohydrates
unit
1 3 2 6 45
2 4 2 4 40
3 8 7 7 85
4 6 5 4 65
Minimum 800 200 700
requirement
Formulate linear programming model for the problem.
Solution:
The objective is to minimize the cost
That is , Z = Rs.(45x1+40x2+85x3+65x4)
The constraints are on the fulfillment of the daily requirements of the constituents.
For proteins, 3x1 + 4x2+8x3+6x4 800
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 9
Operations Research
Information about the location of the plants and their probability of being attacked by a medium
bomber and a heavy bomber is given below:
Probability of destruction by
Distance from base
Plant A heavy A medium
(km)
bomber bomber
A Heavy 2 40
B Medium 2.5 30
How many of each type of bombers should be dispatched, and how should they be allocated among
the four targets in order to maximize the probability of success?
Solution:
Let xij is number of bomber sent.
The objective is to maximize the probability of success in destroying at least one plant and this is
equivalent to minimizing the probability of not destroying any plant. Let Q denote this probability:
then, Q = (1 – 0.1) xA1 . (1 – 0.2) xA2 . (1 – 0.15) xA3. (1 – 0.25) xA4 .
(1 – 0.08) xB1 . (1 – 0.16) xB2 . (1 – 0.12) xB3 . (1 – 0.20) xB4
here the objective function is non-linear but it can be reduced to the linear form.
Take log on both side, moreover, minimizing log Q is equivalent to maximizing –log Q or
maximizing log 1/Q
log 1/Q = -(xA1 log 0.9 + xA2 log 0.8 + xA3 log 0.85 + xA4 log 0.75 +
xB1 log 0.92 + xB2 log 0.84 + xB3 log 0.88 + xB4 log 0.80)
therefore, the objective is to maximize
Example 7:
A paper mill produces rolls of paper used cash register. Each roll of paper is 100m in length and
can be produced in widths of 2,4,6 and 10 cm. The company’s production process results in rolls
that are 24cm in width. Thus the company must cut its 24 cm roll to the desired width. It has six
basic cutting alternative as follows:
Cutting Width of rolls(cm)
Wastage(cm)
alternatives 2 4 6 10
1 6 3 - - -
2 - 3 2 - -
3 1 1 1 1 2
4 - - 2 1 2
5 - 4 1 - 2
6 4 2 1 - 2
The constraints are on the market demand for each type of roll width:
for roll width of 2 cm, 6x1 + x3 + 4x6 2,000
for roll width of 4 cm, 3x1 + 3x2 + x3 + 4x5 3,600
for roll width of 6 cm, 2x2 + x3 + 2x4 + x5 + x6 1,600
for roll width of 10 cm, x3 + x4 500
1. The collection of all feasible solutions to an LP problem constitutes a convex set whose
extreme points correspond to the basic feasible solutions.
2. There are a finite number of basic feasible solutions within the feasible solution space.
3. If the convex set of the feasible solutions of the system Ax=b, x≥0, is a convex polyhedron,
then at least one of the extreme points gives an optimal solution.
4. If the optimal solution occurs at more than one extreme point, then the value of the
objective function will be the same for all convex combinations of these extreme points.
Step1: State the given problem in the mathematical form as illustrated in the previous chapter.
Step2: Graph the constraints, by temporarily ignoring the inequality sign and decide about the
area of feasible solutions according to the inequality sign of the constraints. Indicate the
area of feasible solutions by a shaded area, which forms a convex polyhedron.
Step3: Determine the coordinates of the extreme points of the feasible solution space.
Step4: Evaluate the value of the objective function at each extreme point.
Step5: Determine the extreme point to obtain the optimum (best) value of the objective function.
• Multiple solutions.
• Infeasible solutions.
Example 1.
Use the graphical method to solve the following LP problem
Maximize Z= 15x1+10x2
Notes:
Simplex Method
Cj 3 5 4 0 0 0
Cb Basic Solution X1 X2 X3 S1 S2 S3 Ratio
Variables
0 S1 8 2 3 0 1 0 0 8/3
0 S2 10 0 2 5 0 1 0 10/2
0 S3 15 3 2 4 0 0 1 15/2
Zj 0 0 0 0 0 0
Cj-Zj 3 5 4 0 0 0
5 X2 8/3 2/3 1 0 1/3 0 0 --
0 S2 14/3 -4/3 0 5 -2/3 1 0 14/15
0 S3 24/3 5/3 0 4 -2/3 0 1 29/12
Zj 10/3 5 0 5/3 0 0
Cj-Zj -1/3 0 4 -5/3 0 0
All Zj –Cj < 0 for non-basic variable. Therefore the optimal solution is reached.
X1=89/41, X2=50/41, X3=62/41
Z = 3*89/41+5*50/41+4*62/41 = 765/41
Example 2:(unbounded)
Max Z=4x1+x2+3x3+5x4
Subject to
4x1-6x2-5x3-4x4 -20
-3x1-2x2+4x3+x4 10
-8x1-3x2+3x3+2x4 20
x1, x2, x3, x4 0.
Solution:
Since the RHS of the first constraints is negative , first it will be made positive by multiplying by
–1, -4x1+6x2+5x3+4x4 20
Introducing non-negative slack variable s1, s2 & s3 to convert inequality constraint to equality then
the LP problem becomes.
Max Z=4x1+x2+3x3+5x4+0s1+0s2+0s3
Subject to
-4x1+6x2+5x3+4x4+0s1=20
-3x1-2x1+4x3+x4+s3=10
-8x1-3x2+3x3+2x4+s4=20
x1,x2,x3,x4,s1,s2,s3 0
Cj 4 1 3 5 0 0 0
Cb Variables Solution X1 X2 X3 X4 S1 S2 S3 Ratio
0 S1 20 -4 6 5 4 1 0 0 5
0 S2 10 -3 -2 4 1 0 1 0 10
0 S3 20 -8 -3 3 2 0 0 1 10
Zj 0 0 0 0 0 0 0
CJ-Zj 4 1 3 5 0 0 0
5 X4 5 -1 3/2 5/4 1 ¼ 0 0 -ve
0 S2 5 -2 -7/2 11/4 0 -1/4 1 0 -ve
0 S3 10 -6 -6 ½ 0 -1/2 0 1 -ve
Zj -5 15/2 25/4 5 5/4 0 0
Cj-Zj 9 -13/2 -13/4 0 -5/4 0 0
Since all the ratio is negative, the value of incoming non-basic variable x1 can be made as large as
we like without violating condition. Therefore, the problem has an unbounded solution.
Max Z=4x1+10x2
Subject to
2x1+x2 10,
2x1+5x2 20,
2x1+3x2 18. x1, x2 0.
Solution:
Introduce the non-negative slack variables to convert inequality constraint to equality, then the LP
problem becomes,
Max Z=4x1+10x2+0s1+0s2+0s3
Subject to
2x1+x2+s1=10,
2x1+5x2+s2=20,
2x1+3x2+s3=18. x1, x2, s1, s2, s3 0.
Cj 4 10 0 0 0
Cb Variables Soln X1 X2 S1 S2 S3 Ratio
0 S1 10 2 1 1 0 0 10
0 S2 20 2 5 0 1 0 4
0 S3 18 2 3 0 0 1 6
Zj 0 0 0 0 0
Cj-Zj 4 10 0 0 0
0 S1 6 8/5 0 1 -1/5 0 15/4
10 X2 4 2/5 1 0 1/5 0 10
0 S3 6 4/5 0 0 -3/5 1 15/2
Zj 4 10 0 2 0 *x1=0
Cj-Zj 0 0 0 -2 0 X2=4,Z=40
4 X1 15/4 1 0 5/8 -1/8 0
10 X2 5/2 0 1 -1/4 ¼ 0
0 S3 3 0 0 -1/2 -1/2 1
Zj 4 10 0 0 0
Cj-Zj 0 0 0 0 0
*All Cj-Zj is either 0 or negative, it gives the optimal basic feasible solution.
But one of non-basic variable (x1) is 0. it indicates the existence of an alternative optimal basic
feasible solution.
If 2 basic feasible optimal solution are known, an infinite number of non-basic feasible optimal
solution can be derived by taking any weighted average of these 2 solutions.
Variables 1 2 General solution
X1 0 15/4 X1=0 +15/4 (1-)
X2 4 5/2 X2=4 +5/2 (1-)
Minimization Case
In certain situations it is difficult to obtain an initial basic feasible solution
(a) When the constraints are of the form
E (aj.xj) bj. Xj 0.
But some RHS constraints are negative. Then in this case after adding the non-negative
slack variables Si the initial solution so obtained will be si=bi. It violates the non-negative
condition of slack variable.
(b) When the constraints are of the form ‘’
E (aj.xj) bj Xj 0.
In this case to convert the inequalities into equation, we are adding surplus variables, then
we get the initial solution is
-si=bi
si=-bi which violates the non-negative condition of the variables.
To solve these type of problems we are adding artificial variable. Thus the new solution to the
given LP problem does not constitute a solution to the original system of equations because the 2
system of equation are not equivalent.
Thus to get back to the original problem artificial variable must be driven to 0 in the optimal
solution.
There are 2 methods to eliminate these variables
1) Two Phase method
2) Big M method or Penalties.
Solution:
Introduce slack, surplus & artificial variable to convert inequality into equality then the LP problem
becomes
Max Z =3x1-x2+0s1+0s2+0s3+0A1,
Subject to
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 21
Operations Research
2x1+x2-s1+A1=2
x1+3x2+s2=3
x2+s3=4 x1,x2,x3,s1,s2,s3,A1 0
Cj 3 -1 0 0 0 -M
Cb Variables Soln X1 X2 S1 S2 S3 A1 Ratio
1 A1 2 2 1 -1 0 0 1 1
0 S2 3 1 3 0 1 0 0 3
0 S3 4 0 1 0 0 1 0 -
Zj -2M -M M 0 0 -M
Cj-Zj 3+2M -1+M -M 0 0 0
3 X1 1 1 ½ -1/2 0 0 ½ -
0 S2 2 0 5/2 ½ 1 0 -1/2 2
0 S3 4 0 1 0 0 1 0 -
Zj 3 3/2 -3/2 0 0 3/2
Cj-Zj 0 -5/2 3/2 0 -
3 X1 3 1 3 0 1 0 0
0 S1 4 0 5 1 2 0 -1
0 S3 4 0 1 0 0 1 0
Zj 3 9 0 3 0 0
Cj-Zj 0 -10 0 -3 0 4
Since the value of Cj-Zj is either negative or 0 under all columns the optimal solution has been
obtained.
Therefore x1=3 & x2=0, Z=3x1-x2 =3*3 =9
Cj -3M/2 -2M -M 0 M -M
Cj-Zj -1+3M/2 -2+2M -1+M 0 -M 0
-2 X2 2 2 1 1 2 0 0
-M A1 4 -5/2 0 -1 -4 -1 1
Cj -4+5m/2 -2 -2+M -4+4M M -M
Cj-Zj 3-5M/2 0 1-M 4-4M -M 0
Since Cj - Zj is either negative or zero & the variable column contains artificial variable A 1 is not at
Zero level.
In this method there is a possibility of many cases
1. Column variable contains no artificial variable. In this case continue the iteration till an
optimum solution is obtained.
2. Column variable contains at least one artificial variable AT Zero level & all Cj-Zj is either
negative or Zero. In this case the current basic feasible solution is optimum through
degenerate.
3. Column Variable contains at least one artificial variable not at Zero level. Also Cj - Zj<=0. In
this case the current basic feasible solution is not optimal since the objective function will
contain unknown quantity M, Such a solution is called pseudo-optimum solution.
Use the optimum basic feasible solution of Phase I as a starting solution fir the original LPP.
Using simplex method make iteration till an optimum basic feasible solution for it is obtained.
Note:
The new objective function is always of minimization type regardless of whether the given
original LPP is of max or min type.
Example 6:
Max Z=3x1+2x2+2x3,
Subject to
5x1+7x2+4x3 7
-4x1+7x2+5x3 -2
3x1+4x2-6x3 29/7
Solution:
Phase I
Step 1:
Since for the second constraint b2=-2, multiply both sides by –1 transform it to
4x1-7x2-5x3 2
Step 2:
Introduce slack variables
5x1+7x2+4x3+s1=7
4x1-7x2-5x3+s2=2
3x1+4x3-6x3+s3=29/7
Step 3:
Putting x1=x2=x3=0, we get s1=7,s2=2,s3=-29/7as initial basic feasible solution.
However it is not the feasible solution as s1 is negative.
Therefore introduce artificial variable A1 from the above Constraints can be
written as
5x1+7x2+4x3+s1=7
4x1-7x2-5x3+s2=2
3x1+4x2-6x3-s3+A1=29/7
Cj 3 4 -6 0 0 -1 1
Cj-Zj -3 -4 6 0 0 1 0
0 X2 1 5/7 1 4/7 1/7 0 0 0 7/5
0 S2 9 9 0 -1 1 1 0 0 1
1 A1 1/7 1/7 0 -58/7 -4/7 0 -1 1 1
Cj 1/7 0 -58/7 -4/7 0 -1 1
Cj-Zj -1/7 0 58/7 4/7 0 1 0
0 X2 2/7 0 1 294/7 3 0 5 -5
0 S2 0 0 0 521 37 1 63 -63
0 X1 1 1 0 -58 -4 0 -7 7
Cj 0 0 0 0 0 0 0
Cj-Zj 0 0 0 0 0 0 1
Since all Cj - Zj 0 the objective function is 0 & no artificial variable appears in column variable the
table yields the basic feasible solution to the original problem.
Phase II
The original objective function is
Max Z=3x1+2x2+2x3+0.s1+0.s2+0.s 3
Cj 0 0 0 0 0 0
CB Var Soln X1 X2 X3 S1 S2 S3 Ratio
0 X2 2/7 0 1 42 3 0 5 1/147
0 S2 0 0 0 521 37 1 63 0
3 X3 1 1 0 -58 -4 0 -7 -
Cj 3 2 -90 -6 0 -11
Cj-Zj 0 0 92 6 0 11
2 X2 2/7 0 1 0 59/521 -42/521 -41/521
2 X3 0 0 0 1 37/521 1/521 63/521
3 X1 1 1 0 0 62/521 58/521 7/521
Cj 3 2 2 278/521 92/521 65/521
Cj-Zj 0 0 0 -278/521 -92/521 -65/521
x1=1,x2=2/7,x3=0
z=25/7
Example 7:
(Unconstrained variables)
Min Z=2x1+3x2
Subject to
x1-2x2 0
-2x1+3x2 -6
x1,x2 unrestricted.
Solution:
The RHS of 2nd constraint id –ve so multiply both sides by –1 we get
2x1-3x2 6
Cj 2 -2 3 -3 0 0
CB Var Soln Y1 Y2 Y3 Y4 S1 S2 Ratio
0 S1 0 1 -1 -2 2 1 0 0
0 S2 6 2 -2 -3 3 0 1 2
Cj 0 0 0 0 0 0
Cj-Zj 2 -2 3 -3 0 0
-3 Y4 0 ½ -1/2 -1 1 ½ 0 -
0 S2 6 ½ -1/2 0 0 -3/2 1 -
Cj -3/2 3/2 3 -3 3/2 0
Cj-Zj 3/2 -7/2 0 0 -3/2 0
All the ratios are –ve that the value of the incoming non-basic variable y2 can be made as large
as possible without violating the constraint. This problem has unbounded solution & the iteration
stops here.
Note:
If the minimum ratio is equal to for 2 or more rows, arbitrary selection of 1 of these variables may
result in 1 or more variable becoming 0 in the next iteration & the problem is said to degenerate.
These difficulties maybe overcome by applying the following simple procedure called perturbation
method.
1. Divide each element in the tied rows by the positive co-efficient of the key column in that
row
2. Compare the resulting ratios, column-by-column 1st in the identity & then in the body from
left to right.
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 26
Operations Research
3. The row which first contains the smallest algebraic ratio contains the outgoing variable.
Recall the production planning problem concerned with four variants of the same product which we
formulated before as an LP. To remind you of it we repeat below the problem and our formulation of it.
A company manufactures four variants of the same product and in the final part of the manufacturing
process there are assembly, polishing and packing operations. For each variant the time required for
these operations is shown below (in minutes) as is the profit per unit sold.
Constraints
The operation time limits depend upon the situation being considered. In the first situation, where the
maximum time that can be spent on each operation is specified, we simply have:
In the second situation, where the only limitation is on the total time spent on all operations, we simply
have:
Objective
A summary of the input to the computer package for the first situation considered in the question
(maximum time that can be spent on each operation specified) is shown below.
We can see that the optimal solution to the LP has value 58000 (£) and that Tass=82000, Tpol=50000,
Tpac=60000, X1=0, X2=16000, X3=6000 and X4=0.
This then is the LP solution - but it turns out that the simplex algorithm (as a by-product of solving the
LP) gives some useful information. This information relates to:
We deal with each of these in turn, and note here that the analysis presented below ONLY applies for a
single change, if two or more things change then we effectively need to resolve the LP.
suppose we vary the coefficient of X2 in the objective function. How will the LP optimal
solution change?
Currently X1=0, X2=16000, X3=6000 and X4=0. The Allowable Min/Max c(i) columns above tell us that,
provided the coefficient of X2 in the objective function lies between 2.3571 and 4.50, the values of the
variables in the optimal LP solution will remain unchanged. Note though that the actual optimal solution
value will change.
In terms of the original problem we are effectively saying that the decision to produce 16000 of variant 2
and 6000 of variant 3 remains optimal even if the profit per unit on variant 2 is not actually 2.5 (but lies
in the range 2.3571 to 4.50).
In terms of the underlying simplex algorithm this arises because the current simplex basic solution
(vertex of the feasible region) remains optimal provided the coefficient of X2 in the objective function
lies between 2.3571 and 4.50.
for the variables, the Reduced Cost column gives us, for each variable which is currently
zero (X1 and X4), an estimate of how much the objective function will change if we make
that variable non-zero.
Variable X1 X4
Opportunity Cost 1.5 0.2
New value (= or >=) X1=A X4=B
or X1>=A X4>=B
Estimated objective function change 1.5A 0.2B
The objective function will always get worse (go down if we have a maximisation problem, go up if we
have a minimisation problem) by at least this estimate. The larger A or B are the more inaccurate this
estimate is of the exact change that would occur if we were to resolve the LP with the corresponding
constraint for the new value of X1 or X4 added.
Hence if exactly 100 of variant one were to be produced what would be your estimate of the new
objective function value?
Note here that the value in the Reduced Cost column for a variable is often called the "opportunity cost"
for the variable.
Note here than an alternative (and equally valid) interpretation of the reduced cost is the amount
by which the objective function coefficient for a variable needs to change before that variable will
become non-zero.
Hence for variable X1 the objective function needs to change by 1.5 (increase since we are maximising)
before that variable becomes non-zero. In other words, referring back to our original situation, the profit
per unit on variant 1 would need to need to increase by 1.5 before it would be profitable to produce any
of variant 1. Similarly the profit per unit on variant 4 would need to increase by 0.2 before it would be
profitable to produce any of variant 4.
for each constraint the column headed Shadow Price tells us exactly how much the objective
function will change if we change the right-hand side of the corresponding constraint within
the limits given in the Allowable Min/Max RHS column.
For example for the polish constraint, provided the right-hand side of that constraint remains between
40000 and 90000 the objective function change will be exactly 0.80[change in right-hand side from
50000].
The direction of the change in the objective function (up or down) depends upon the direction of the
change in the right-hand side of the constraint and the nature of the objective (maximise or minimise).
constraint more (less) restrictive after change in right-hand side implies objective function
worse (better)
if objective is maximise (minimise) then worse means down (up), better means up (down)
Hence
if you had an extra 100 hours to which operation would you assign it?
if you had to take 50 hours away from polishing or packing which one would you choose?
what would the new objective function value be in these two cases?
The value in the column headed Shadow Price for a constraint is often called the "marginal value" or
"dual value" for that constraint.
Note that, as would seem logical, if the constraint is loose the shadow price is zero (as if the constraint is
loose a small change in the right-hand side cannot alter the optimal solution).
Comments
Different LP packages have different formats for input/output but the same information as
discussed above is still obtained.
You may have found the above confusing. Essentially the interpretation of LP output is
something that comes with practice.
Much of the information obtainable (as discussed above) as a by-product of the solution of
the LP problem can be useful to management in estimating the effect of changes (e.g.
changes in costs, production capacities, etc) without going to the hassle/expense of
resolving the LP.
This sensitivity information gives us a measure of how robust the solution is i.e. how
sensitive it is to changes in input data.
Note here that, as mentioned above, the analysis given above relating to:
is only valid for a single change. If two (or more) changes are made the situation becomes more
complex and it becomes advisable to resolve the LP.
maximise
3x1 + 7x2 + 4x3 + 9x4
subject to
x1 + 4x2 + 5x3 + 8x4 <= 9 (1)
x1 + 2x2 + 6x3 + 4x4 <= 7 (2)
xi >= 0 i=1,2,3,4
decrease to 22.0 - 9.45 = 12.55. Note that the value calculated here is only an estimate of
the change in the objective function value. The actual change may be different from the
estimate (but will always be >= this estimate).
Note that we can, if we wish, explicitly enter the four constraints xi>=0 i=1,2,3,4. Although this is
unnecessary (since the package automatically assumes that each variable is >=0) it is not incorrect.
However, it may alter some of the solution figures - in particular the Reduced Cost figures may be
different. This illustrates that such figures are not necessarily uniquely defined at the linear
programming optimal solution.
Transportation Model
Find the optimal solution for the following given TP model.
Distribution center (to)
Plants (From)
1 2 3 4 Supply
2 3 11 7 6
1 0 6 1 1
5 8 15 9 10
Requirements 7 5 3 2
Note:
If the supply & demand are equal then it is called balanced otherwise unbalanced.
Non-Degenerate:
A basic feasible solution to a (m x n) transportation problem that contains exactly (m+n-1)
allocation in independent position.
Degenerate:
A basic feasible solution that contains less than m+n-1 non-negative allocations
Find Basic Feasible Solution
1) North West Corner Rule
Start in the northwest corner
If D1<S1, then set x1 equal to D1 & proceed horizontally.
If D1=S1, then set x1 equal to D1 & proceed diagonally.
If D1>S1, then set x1 equal to S1 & proceed vertically.
2 3 11 7
6
6 0
1 0 6 1
Session Feb06-Jun06 1 Dept of Electronics Staff:NLJ 33
5 8 15 9
5 3 2
Operations Research
1 0
10 5 3 2
7 5 3 2
6 0 0 0
1
it can be easily seen that the proposed solution is a feasible solution since all the supply &
requirement constraints are fully satisfied. In this method, allocations have been made without any
consideration of cost of transformation associated with them.
Hence the solution obtained may not be feasible or the best solution.
The transport cost associate with this solution is :
Z=Rs (2*6+1*1+8*5+15*3+9*2) * 100
=Rs (12+1+40+45+18) * 100
=Rs 11600
2) Row Minima Method
This method consists in allocating as much as possible in the lowest cost cell of the 1st row so that
either the capacity of the 1st plant is exhausted or the requirement at the jth distribution center is
satisfied or both
Three cases arises:
If the capacity of the 1st plant is completely exhausted, cross off the 1st row & proceed to the 2nd
row.
If the requirement of the jth distribution center is satisfied, cross off the jth column & reconsider
the 1st row with the remaining capacity.
If the capacity of the 1st plant as well as the requirement at jth distribution center are
completely satisfied, make a 0 allocation in the 2nd lowest cost cell of the 1st row. Cross of the
row as well as the jth column & move down to the 2nd row.
2 3 11 7
6 0 6
1 0 6 1
1 0 1
5 8 15 9
1 4 3 2
10 9 5 3 0
7 5 3 2
1 0 0 0
0
Z=100 * (6*2+0*1+5*1+8*4+15*3+9*2)
=100 * (12+0+5+32+45+18) =100 * 112 =11200
3) Column Minima Method
2 3 11 7
6
6 0
1 0 6 1
1
5 8 15 9 1 0
5 3 2
10 5 3 2 0
7 5 3 2
6 0 0 0
1
0
Z= 2*6+1*1+5*0+5*8+15+18
= 12+1+40+45+18
= 116
2 3 11 7
6 6 0
1 0 6 1
1
5 8 15 9
1 0
1 4 3 2
10 9 5 2 0
7 5 3 2
1 4 0 0
0 0
Z= 12+0+5+32+45+18
= 112
2 3 11 7
6 1 0 [1] [1] [5] *
1 5
1 0 6 1
1 1 0 [1] * * *
5 8 15 9
6 3 1 10 7 8 0 [3] [3] [4] [4]
7 5 3 2
6 0 0 1
0 0
[1] [3] [5] [6]
[3] [5] [4] [2]
[3] * [4] [2]
[5] [8] [4] [9]
z = 2 + 15 + 1 + 30 + 45 + 9
= 102
Perform Optimality Test
An optimality test can, of course, be performed only on that feasible solution in which:
(a) Number of allocations is m+n-1
(b) These m+n-1 allocations should be in independent positions.
A simple rule for allocations to be in independent positions is that it is impossible to travel from any
allocation, back to itself by a series of horizontal & vertical jumps from one occupied cell to
another, without a direct reversal of route.
Now test procedure for optimality involves the examination of each vacant cell to find whether or
not making an allocation in it reduces the total transportation cost.
The 2 methods usually used are:
(1) Stepping-Stone method
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 36
Operations Research
2 +1 3 -1 11 7
1 5
1 -1 0 +1 6 1
1
5 8 15 9
6 3 1
Step 2: Enter a set of number Vj across the top of the matrix and a set of number Ui
across the left side so that their sums equal to the costs entered in Step 1.
Thus,
u1+v1=2 u3+v1=5
u1+v2=3 u3+v3=15
u2+v4=1 0 1 10 4 u3+v4=9
2 12 6
Let v1=0
-3 -3 -2 7
u1=2 ; u2=-3 ; 5 6 u1=2 ; v2=1 ; v3=10 ; v4=4
-1 1
4 2 -1
2
V1=0 v2=0 v3=0 v4=0
u1=2 2 3
u2=3 1
u3=5 5 15 9
Step 4: Subtract the cell values of the matrix of Step 3 from original cost matrix.
11-12 7-6
1+3 0+2 6-7
8-6
step5: If any of the cell evaluations are negative the basic feasible solution is not optimal.
1 5 +
-
1
6 3
+ -
Check mark ( )the empty cell for which the cell evaluation is negative. This cell is chosen in
substep1 & is called identified cell.
Substep3: Trace a path in this matrix consisting of a series of alternately horizontal & vertical
lines. The path begins & terminates in the identified cell. All corners of the path lie in the cells for
which allocations have been made. The path may skip over any number of occupied or vacant cells.
Substep4: Mark the identified cells as positive and each occupied cell at the corners of the path
alternatively negative & positive & so on.
Note :In order to maintain feasibility locate the occupied cell with minus sign that has the smallest
allocation
Substep5: Make a new allocation in the identified cell.
1-1=0 5 1
1
7 2 1
2 3 11 7
5 1
1 0 6 1
1
5 8 15 5
7 2 1
u1+v2=3 u3+v1=5
u1+v3=11 u3+v3=15
u2+v4=1 u3+v4=9
Let v1=0
u1=1 ; u2=-3 ; u3=5 ; v2=2 ; v3=10 ; v4=4
v1 v2 v3 v4
u1 3 11
u2 1
u3 5 15 9
2-1 7-5 1 2
1+3 0+1 6-7 4 1 -1
8-7 -1
Step5: Since one cell is negative, 2nd
feasible solution is not optimal.
Iterate towards an optimal solution
Substep1: Identify the cell with most negative entry. It is the cell (2,3).
Substep2: Write down the feasible solution.
5 1
+ 1 -
7 2 - 1 +
Z=(5*3+1*11+1*6+1*15+2*9+7*5)
=100
Assignment Problem
Step 1: Prepare a square matrix: Since the solution involves a square matrix, this step is not
necessary.
SUBSTEP 2: Next examine columns for single unmarked zeroes and mark them suitably.
SUBSTEP 3: In the present example, after following substeps 1 and 2 we find that their repetition
is unnecessary and also row 3 and column 3 are without any assignments. Hence we proceed as
follows to find the minimum number of lines crossing all zeroes.
SUBSTEP 4: Mark the rows for which assignment has not been made. In our problem it is the third
row.
SUBSTEP 5: Mark columns (not already marked) which have zeroes in marked rows. Thus column 1
is marked.
SUBSTEP 6: Mark rows(not already marked) which have assignmentsin marked columns. Thus row
1 is marked.
SUBSTEP 7: Repeat steps 5 and 6 until no more marking is possible. In the present case this
repetition is not necessary.
Cost = 61
The condition for TSP is that no city is visited twice before the tour of all the cities is completed.
A B A C B DC DE E A B C D E
A 0 2 5 7 1
B 6 0 3 8 2
C 8 7 0 4 7
A 唴 1D 12 4 4 66 00 5 A 唴 1 3 6 0
_ E 1 3 2 8 0
_
As going from A->A,B->B etc is not allowed, assign a large penalty to these cells in the cost matrix
B 4 A 唴
B C1 D 6E 0 B A 4B C 唴 D 0E 6 0
A
唴 _1 4 6 0 A
唴 1 3_ 6 0
B 4 1 6 0
C _
4
唴
3 0 3
B 4
_ 唴 0 6 0
_ 唴 C 4 3
唴 0 3
D 8 0 2
唴 1 _
C E 4 0 32 1唴 7 0 3 D
C8 40 13 唴唴1 0 3
唴 E 0 2 0 7
__ _ _唴
_ _
A B C_ D E
_
D 8 A 0 唴 21 唴
3 61 D 8 0 1 唴 1
B _
4 唴
_0 6 0
0 _
C 4 _
3 唴 0 3
D 8 _
1 唴 1
E 0 E 2 0 1 2 0 70 _
唴 唴 E
7 0 2 0 7 唴
Session Feb06-Jun06
_ _
Dept of Electronics Staff:NLJ 49
_
Operations Research
Which gives optimal for assignment problem but not for TSP because the path A->E, E-A, B->C-
>D->B does not satisfy the additional constraint of TSP
The next minimum element is 1, so we shall try to bring element 1 into the solution. We have three
cases.
Case 1:
Make assignment in cell (A,B) instead of (A,E).
A B C D E
A ∞ 1 3 6 0
B 4 ∞ 0 6 0
C 4 3 ∞ 0 3
D 8 0 1 ∞ 1
E 0 2 0 7 ∞
Case 2:
A B C D E
A ∞ 1 3 6 0
B 4 ∞ 0 6 0
C 4 3 ∞ 0 3
D 8 0 1 ∞ 1
E 0 2 0 7 ∞
Since second row does not have any assignment. We can choose minimum cost in that
row and if any assignment is there in that column, shift to next minimum cell.
A B C D E
A ∞ 1 3 6 0
B 4 ∞ 0 6 0
C 4 3 ∞ 0 3
D 8 0 1 ∞ 1
E 0 2 0 7 ∞
Case 3:
A B C D E
A ∞ 1 3 6 0
B 4 ∞ 0 6 0
C 4 3 ∞ 0 3
D 8 0 1 ∞ 1
E 0 2 0 7 ∞
Activity – It is a physically identifiable part of a project which consumes time and resources.
Event – the beginning and end points of an activity are called events or nodes. Event is a point in
time and does not consume any resources. It is generally represented by a numbered circle.
Example:
Activity
i j
Event Event
Path – An unbroken chain of activity arrows connecting the initial event to some other event is
called a path.
Network - It is the graphical representation of logically and sequentially connected arrows and
nodes representing activities and events of a project.
Network construction – Firstly the project is split into activities. While constructing the network , in
order to ensure that the activities follow a logical sequence. The following questions are checked.
Example
An assembly is to be made from two parts X and Y. both parts must be turned on a lathe and Y
must be polished, X need not be polished. The sequences of activity together with their
predecessors are given below.
6 7 8
1 2
4 5
Consider the following notations for calculating various times of events and activities.
Ei = Earliest occurrence time of event i
Li = Latest occurrence time of event i
ESij = Earliest start time for activity (i,j)
LSij = Latest start time for activity (i,j)
EFij = Earliest finish time for activity (i,j)
LFij = Latest finish time for activity (i,j)
Tij = duration of activity (I,j)
Total float
The difference between the maximum time available to perform the activity and activity duration
time.
Free float
The difference between the earliest start time for the successor activity and earliest completion
time for activity under consideration.
Independent float
The difference between the predecessor event occurring at its latest possible time and the
successor event at its earliest possible time.
1. Consider the Network shown below. The three time estimates for activities are along the arrow.
Determine the critical path. What is the probability that the project will be completed in 20 days?
4
3-4-11
0.5-1-7.5 6-7-8
2-2-8 0-0-0 4-6-8
1 2 5 6
1-1.5-11 1-2.5-7
1-2-3
3
Te=6,tl=6
4 5
2
tl=3 7
te=0 te=3 6 te=19
3 6 tl=19
5
1 2 3 Tl=13
Tl=0 3 te=13
2
3
Te=6
Tl=6
V=[(tp-to)/6]2
=2.08
z=Ts-Te/
Z=0.48
From Std Dev. Probability = 68.44%
Te=10,tl=12
te=22,tl=22 7
4
1 2 5 6
8
3
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 54
Operations Research
Te=6,tl=7 te=32
tl=32
e4=10 7
l4=11
4
3 7 0 6 4 10
1 2 5 6
e1=0 e2=3 9 e5=11 e6=17
l1=0 l2=3 l5=11 l6=17 13
3 5
8
3
e3=6
e8=31,l8=31
l3=6 new total cost = Rs 5815
e4=10 e7=19
l4=11 l7=19
7
4 10
8
E3=6,l3=6 3 e8=29
L8=29
New total cost = Rs 5805
-----------------------------------------------------------------------------------------------------------
Resource leveling
Activity Normal time Man power required
0-1 2 4
1-2 3 3
1-3 4 3
2-4 2 5
3-5 4 3
3-6 3 4
4-7 6 3
5-7 6 6
6-8 5 2
7-9 4 2
8-9 4 9
5
6 8
3
4
3 4 5
4 6
2 3 2 6 4
0 1 2 4 7 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4 4 6 6 6 8 12 10 10 8 11 11 11 8 15 15 11 11 2 2
4 4 6 6 6 8 8 10 10 10 9 11 11 8 8 8 11 11 11 11
Thus the man power is reduced to 11 people.
Economic order quantity (EOQ) for finding the optimum order quantity in order to balance costs to
balance costs of holding too much stock against that of ordering in small quantities too frequently.
Optimum Quantity,
Q0=Rt0=Sqrt(2C3R/C1)
Example:
A particular item has a demand of 9000 units/year. The of one procurement is Rs.100 and the
holding cost per unit is Rs.2.240 per year. The replacement is instantaneous & no shortages are
allowed. Determine,
(i) Economic lot size,
(ii) Number of orders per year,
(iii) Time between orders,
(iv) The total cost per year if the cost of one unit is Re1
Solution
R=9,000 units/year
C3= Rs. 100 /procurement,
C1= Rs 2.40 /unit/year
Model: 2 (a) (Demand Rate Uniform, Production Rate, Infinite, shortages Allowed)
This model is just the extension of model 1(a) allowing shortage .
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 57
Operations Research
Example
Solve the previous problem in addition to the data given that the problem the cost of shortage is
also given as Rs.5 per unit per year.
Solution
R=9000
C3 = Rs 100 /procurement
C1 = Rs 2.40 /uit/procurement
C2 = Rs 5 /unit/year
(i) From Equation q0=Sqrt((C1+ C2)/ C2) * Sqrt(2C3R/ C1)=Sqrt((2.40+5)/5) *
Sqrt((2*100*9000)/2.4) =1053 units/run
(ii) C0(Im,q) = 9000*1+Sqrt(C2(C2+ C1))*Sqrt(2C1C3R) = 10710 /year
(iii)Number of orders/year
N0=9000/1053 = 8.55
(iv)Time between orders,
t0=1/N0 =1/8.55 =0.117 year
Example
The demand for a commodity is 100 units per day. Every time an order is placed, a fixed cost Rs.
400 is incurred. Holding cost is Rs 0.08 per unit per day. If the lead time is 13 days, determine the
economic lot size & the reorder point
Solution
Q0=Sqrt(2C3R/ C3)=Sqrt(2*4*100/0.08) = 1000 units.
Length of the cycle t0 = 1000/100 =10 days.
As the lead time is 13 days & the cycle length is 10 days, recording should occur when the leve of
inventory is sufficient to satisfy the demand for 13-10 = 3 days
Reorder point =100*3 = 300 units.
It may be noted that the ‘effective’ lead time is taken equal to 3 days rather than 13 days. It is
because the lead time is longer than t0.
Model1(b) (Demand Rate Non-uniform, production Rate Infinite)
In this method all assumptions are same as in model 1(a) with the exception that instead of
uniform demand rate R, we are given some total amount D, to be satisfied during some long time
period T. Thus, demand rates are different in different production runs
Optimal Lot size q0 = Sqrt(2C3(D/T)/C1)
And minimum total cost, C0(q) = Sqrt(2C1C3(D/T))
Here, it can be noted that the uniform demand rate R in model 1(a) is replaced by average demand
rate D/T.
Example
A manufacturing company purchases 9000 parts of a machine for its actual requirements, ordering
one month’s requirement at a time. Each part costs Rs.20. the ordering cost per order is Rs.15 and
the are 15% of the average inventory per year. You have been asked to suggest a more
economical purchasing policy for the company. What advice would you offer & how much would it
save the company per year?
Solution
D=9000
C3=15
C0=15
C1=15% of the investment in inventories
=20 of 0.15 = Rs.30 per year
Optimal Size=Sqrt(2C3(D/T)/C1)=300 units.
Total Cost=Sqrt(2C1C3(D/T))=Rs900
2C 3 RK
Optimum Lot Size q0 .
c1 K 1 R
KR
Optimum average cost 2C1C 2 R.
K
q0 K 2C 3
Time interval, t 0 .
R K R C1 R
K R
max. inventory Imo .q 0
K
Example:
A company has a demand of 12,000 units/year for an item and it can produce 2,000 such items per
month. The cost of one setup is Rs. 400 and the holding cost/unit/month is Re. 0.15. find the
optimum lot size and the total cost per year, assuming the cost of 1 unit as Rs. 4. also, find the
maximum inventory, manufacturing time and total time.
Solution:
R = 12,000 units/year
K = 2,000 * 12 = 24,000 units/ear
C3 = Rs. 400
C1 = Rs. 0.15 * 12 = Rs. 1.80/unit/year
1 C1C 2
The minimum average cost per unit time is given by Co(Im) . .Rt
2 C1 C 2
Example
A commodity is to be supplied at a constant rate of 25 units per day. A penalty cost is being
changed at a the rate of Rs. 10 per unit per day late for missing the scheduled delivery date. The
cost of carrying the commodity in inventory is Rs 16 per unit per month. The production process is
such that each month(30 days) a batch of items is started and are available for delivery and time
after the end of the month. Find the optimal level of inventory at the beginning of each month.
Solution:
From the data of the problem in usual notations, we have
R = 25 units/day
C1 = Rs 16/30 = 0.53 per unit per day
C2 = Rs 10 per unit per day
T = 30 days
10
The optimal inventory level is given by = 25 30 712units
0.53 10
Model 2(c) Demand Rate uniform, production Rate finite, shortage allowed
This model has the same assumptions as in model 2(a) except that production rate is finite.
Example
Find the results of example 12.5 –2 if in addition to the date given in that problem the cost of
shortages is also given as Rs. 5 per unit per year.
Solution
R = 9,000 units/year
C3 = Rs. 100 / procurement,
C1 = Rs. 2.40 / unit/year
C2 = Rs. 5/ unit/year
Notes:
Game Theory
Many practical problems require decision making in a competitive situation. Where there are
two or more opposite parties with conflicting interests and where the action of one depends upon
the one taken by the opponent.
b. Dominance- Method.
Player B
B1 B2 B3 B4
A1 1 7 3 4
A2 5 6 4 5
A3 7 2 0 3
Solution:
Player B
B1 B2 B3 B4
A1 1\/ 7+ 3 4
A2 5 6 4\/+ 5+
A3 7+ 2 0\/ 3
The optimal Strategy for player A is A2 and player B is B3 and the value of the game is 4
2. Dominance principle Method:
Player B
B1 B2 B3 B4
A1 1 7 3 4
A2 5 6 4 5
A3 7 2 0 3
Steps:
1. Row Comparison Inferiors.
2. Column comparison Superior.
1. The elements of the second column are superior to corresponding elements of 3 rd column
so delete II column.
The revised matrix is:
Sol: Player B
B1 B3 B4
A1 1 3 4
A2 5 4 5
A3 7 0 3
2. The elements of I row are inferior to corresponding elements of II rows So Delete I row
(A1)
The revised matrix is:
Sol: Player B
B1 B3 B4
A2 5 4 5
A3 7 0 3
4. A3 is inferior to A2 – Delete A3
The revised matrix is :
Sol: Player B
B3 B4
A2 4 5
4. B4 is superior is to B3 Delete B4
The revised matrix is :
Sol: Player B
B3
A2 4
Player B
I II III IV
I 3 2 4 0
II 3 4 2 4
III 4 2 4 0
IV 0 4 0 8
Solution:
1. Min- Max Method:
Player B
I II III IV
I 3 2 4+ 0\/
II 3 4+ 2\/ 4
III 4+ 2 4+ 0\/
IV 0\/ 4+ 0\/ 8+
The Given Game does not posses the saddle point.
2. Dominance Method:
Player B
I II III IV
I 3 2 4 0
II 3 4 2 4
III 4 2 4 0
IV 0 4 0 8
1. The Elements of A1 row are inferior to the corresponding elements of AIII row So Delete A1
The revised matrix is
Player B
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 63
Operations Research
I II III IV
II 3 4 2 4
III 4 2 4 0
IV 0 4 0 8
B1 is superior to BIII So delete BI
The revised matrix is
Player B
II III IV
II 4 2 4
III 2 4 0
IV 4 0 8
3 2 4
The average of AIII & AIV rows i.e 2+4, 4+0, 0+8 are inferior to the corresponding
elements of AII So delete row
The revised matrix is
Player B
II III IV
II 4 2 4
Solution :
From the Above matrix:
A1 is inferior to A3 so delete A1
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 64
Operations Research
B1 is superior to B2 so delete B1
B2 B3 B4
A2 4 2 4
A3 2 4 0
A4 4 0 8
B3 B4
A34 0
A4 0 8
B3 B4
A3 a11 a12
A4 a21 a22
Let the players A chooses his strategies A3, A4 with probabilities P1 & P2. Such that P1+P2=1.
Similarly player B chooses his strategies B3+B4 with probabilities q1 &q2, such that q1+q2=1.
Formula
P1= a22-a21
a11+a22-(a12+a21)
q1= a22-a12
a11+a22-(a12+a21)
P1= a22-a21
a11+a22-(a12+a21)
= 8-0
4+8-(0+0)
= 8
12
=0.67
P1+P2=1 We know the value of P1=067 so when we substitute we get P2=1-067 P2=0.33
q1= a22-a12
a11+a22-(a12+a21)
= 8-0
4+8-(0+0)
= 8
12
=067
=4 x 8 – 0 x 0
4+8-(0+0)
=32
12
=8
3
=2.67
Value =2.67
B1 B2 B3 B4 B5 B6
A1 1 3 -1 4 2 -5
A2 -3 5 6 1 2 0
Solution:
B1 B2 B3 B4 B5 B6
A1 1 3 -1 4 2 -5
A2 -3 5 6 1 2 0
All Superior columns are deleted by comparison to corresponding elements revised matrix.
B1 B6
A1 1 -5
A2 -3 0
P1= a22-a21
a11+a22-(a12+a21)
q1= a22-a12
a11+a22-(a12+a21)
P1= a22-a21
a11+a22-(a12+a21)
= 0-(-3)
(1+0)-(-5+-3)
=3
9
0.33 , p2= 1-p1 p2=1-0.38=067
q1= a22-a12
a11+a22-(a12+a21)
= 0-(-5)
9
=5
9
=(1 x 0) – ( -5 x -3)
(1 + 0)-(-5+-3)
=0-+15
1-(-8)
=1.67
A1 A2 B1 B2
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 P 4
3 3 3 3
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 67
Operations Research
2 2 2 2
1 1 1 1
-1 -1 -1 -1
-2 -2 -2 -2
-3 -3 -3 -3
p -4 -4 -4
-4 -5 -5 -5
-5 -6 -6 -6
-6 -7 -7 -7
-7
Replacement Model
Replacement problem:
1. Replacement of capital equipment that becomes worse with time, e.g. machines tools,
buses in a transport organization, planes, etc
2. Group replacement of items which fail completely, e.g. light bulbs, radio tubes, etc.
3. Problems of mortality and staffing.
4. Miscellaneous problems.
1. The cost of machine is Rs 6100 and its scrap value is only Rs 100. The maintenance costs
are found from experience to be:
Year 1 2 3 4 5 6 7 8
Mtn- 100 250 400 600 900 1250 1600 2000
Cost
Solution:
First, find an average cost per year during the life of the machine as follows.
These computations may be summarized in the following
Replace at Maintenance Total Difference Total cost Average
the end of cost an maintenance b/w Price cost
the year (n) cost and Resale
price
(n) Rn ∑ (c-s) [p(n)] P(n)/n
1 100 100 6000 6100 6100
2 250 350 6000 6350 3175
3 400 750 6000 6750 2250
4 600 1350 6000 7350 1837.50
5 900 2250 6000 8250 1650
6 1250 3500 6000 9500 1583.33
7 1600 4100 6000 11100 1585.71
Here it is observed that the maintenance cost in the 7th year becomes greater than the average
cost for 6 years. Hence the machine should be replaced at the end of 6th year.
2. Machine owner finds from his past records that the costs per year of maintaining a machine
whose purchase price is Rs 6000 are as given below:
Year 1 2 3 4 5 6 7 8
Mtn 1000 1200 1400 1800 2300 2800 3400 4000
Cost
Resale 3000 1500 750 375 200 200 200 200
price
At what age is a replacement due?
Solution: As in example 1, the machine should be replace at the end of the fifth year, because
the maintenance cost in the 6th year becomes greater than the average cost for 5 years.
Here the average cost per year during the life of the machine.
Replace at Maintenance Total Difference Total cost Average
the end of cost maintenance b/w price cost
year (n) cost and resale
price
(n)` Rn ∑Rn (c-sn) P(n) P(n)/n
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 69
Operations Research
A should be replaced by
2. A computer contains 10,000 resistors. When any resistor fails, it is replaced. The cost
of replacing a resistor individually is Re.1 only. If all the resistors are replaced at the
same time, the cost per resistor would be reduced to 35 paise. The percentage of
surviving resistors say S(t) at the end of month t and P(t) the probability of failure
during the month t are:
T 0 1 2 3 4 5 6
S(t) 100 97 90 70 30 15 0
P(t) - 0.03 0.07 0.20 0.40 0.15 0.15
What is the optimal replacement plan?
No=10,000
N1=300
N2=709
N3=2042
N4=4171
N5=2030
N6=2590
Expected life = 4.02 months
Avg Failures = 2488 resistors
End of month TC ATC
1 3,800 380,00
2 4,509 2254.50
3 6,551 2183.66
4 10,722 2680.5
5 12,752 2550.40
6 15,442 2557.00
3. Machine A costs Rs.45,000 and the operating costs are estimated at Rs.1000 for the
first year increasing by Rs.10,000 per year in the second and subsequent years. Machine
B costs Rs.50,000 and operating costs are Rs.2,000 for the first year, increasing by
Rs.4,000 in the second and subsequent years. If we now have a machine of type A,
should we replace it with B? If so when? Assume that both machines have no resale value
and future costs are not discounted.
Queuing theory
Queuing theory deals with problems which involve queuing (or waiting). Typical examples might be:
As we know queues are a common every-day experience. Queues form because resources are limited. In
fact it makes economic sense to have queues. For example how many supermarket tills you would need
to avoid queuing? How many buses or trains would be needed if queues were to be avoided/eliminated?
In designing queueing systems we need to aim for a balance between service to customers (short queues
implying many servers) and economic considerations (not too many servers).
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 71
Operations Research
In essence all queuing systems can be broken down into individual sub-systems consisting of entities
queuing for some activity (as shown below).
Typically we can talk of this individual sub-system as dealing with customers queuing for service. To
analyse this sub-system we need information relating to:
arrival process:
o how customers arrive e.g. singly or in groups (batch or bulk arrivals)
o how the arrivals are distributed in time (e.g. what is the probability distribution of
time between successive arrivals (the interarrival time distribution))
o whether there is a finite population of customers or (effectively) an infinite number
The simplest arrival process is one where we have completely regular arrivals (i.e. the
same constant time interval between successive arrivals). A Poisson stream of arrivals
corresponds to arrivals at random. In a Poisson stream successive customers arrive after
intervals which independently are exponentially distributed. The Poisson stream is
important as it is a convenient mathematical model of many real life queuing systems and
is described by a single parameter - the average arrival rate. Other important arrival
processes are scheduled arrivals; batch arrivals; and time dependent arrival rates (i.e. the
arrival rate varies according to the time of day).
service mechanism:
o a description of the resources needed for service to begin
o how long the service will take (the service time distribution)
o the number of servers available
o whether the servers are in series (each server has a separate queue) or in parallel
(one queue for all servers)
o whether preemption is allowed (a server can stop processing a customer to deal with
another "emergency" customer)
Assuming that the service times for customers are independent and do not depend upon
the arrival process is common. Another common assumption about service times is that
they are exponentially distributed.
queue characteristics:
o how, from the set of customers waiting for service, do we choose the one to be
served next (e.g. FIFO (first-in first-out) - also known as FCFS (first-come first
served); LIFO (last-in first-out); randomly) (this is often called the queue discipline)
o do we have:
balking (customers deciding not to join the queue if it is too long)
reneging (customers leave the queue if they have waited too long for service)
jockeying (customers switch between queues if they think they will get served
faster by so doing)
a queue of finite capacity or (effectively) of infinite capacity
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 72
Operations Research
Changing the queue discipline (the rule by which we select the next customer to be
served) can often reduce congestion. Often the queue discipline "choose the customer
with the lowest service time" results in the smallest value for the time (on average) a
customer spends queuing.
Note here that integral to queuing situations is the idea of uncertainty in, for example, interarrival times
and service times. This means that probability and statistics are needed to analyse queuing situations.
In terms of the analysis of queuing situations the types of questions in which we are interested are
typically concerned with measures of system performance and might include:
How long does a customer expect to wait in the queue before they are served, and how long
will they have to wait before the service is complete?
What is the probability of a customer having to wait longer than a given time interval before
they are served?
What is the average length of the queue?
What is the probability that the queue will exceed a certain length?
What is the expected utilisation of the server and the expected time period during which he
will be fully occupied (remember servers cost us money so we need to keep them busy). In
fact if we can assign costs to factors such as customer waiting time and server idle time
then we can investigate how to design a system at minimum total cost.
These are questions that need to be answered so that management can evaluate alternatives in an attempt
to control/improve the situation. Some of the problems that are often investigated in practice are:
In order to get answers to the above questions there are two basic approaches:
The reason for there being two approaches (instead of just one) is that analytic methods are only
available for relatively simple queuing systems. Complex queuing systems are almost always analysed
using simulation (more technically known as discrete-event simulation).
The simple queueing systems that can be tackled via queueing theory essentially:
consist of just a single queue; linked systems where customers pass from one queue to
another cannot be tackled via queueing theory
have distributions for the arrival and service processes that are well defined (e.g. standard
statistical distributions such as Poisson or Normal); systems where these distributions are
derived from observed data, or are time dependent, are difficult to analyse via queueing
theory
The first queueing theory problem was considered by Erlang in 1908 who looked at how large a
telephone exchange needed to be in order to keep to a reasonable value the number of telephone calls
not connected because the exchange was busy (lost calls). Within ten years he had developed a
(complex) formula to solve the problem.
lamda to be the mean (or average) number of arrivals per time period, i.e. the mean arrival
rate
µ to be the mean (or average) number of customers served per time period, i.e. the mean
service rate
If D and E are not specified then it is assumed that they are infinite.
For example the M/M/1 queueing system, the simplest queueing system, has a Poisson arrival
distribution, an exponential service time distribution and a single channel (one server).
Note here that in using this notation it is always assumed that there is just a single queue (waiting line)
and customers move from this single queue to the servers.
Suppose we have a single server in a shop and customers arrive in the shop with a Poisson arrival
distribution at a mean rate of lamda=0.5 customers per minute, i.e. on average one customer appears
every 1/lamda = 1/0.5 = 2 minutes. This implies that the interarrival times have an exponential
distribution with an average interarrival time of 2 minutes. The server has an exponential service time
distribution with a mean service rate of 4 customers per minute, i.e. the service rate µ=4 customers per
minute. As we have a Poisson arrival rate/exponential service time/single server we have a M/M/1 queue
in terms of the standard notation.
We can analyse this queueing situation using the package. The input is shown below:
The first line of the output says that the results are from a formula. For this very simple queueing system
there are exact formulae that give the statistics above under the assumption that the system has reached a
steady state - that is that the system has been running long enough so as to settle down into some
kind of equilibrium position.
Naturally real-life systems hardly ever reach a steady state. Simply put life is not like that. However
despite this simple queueing formulae can give us some insight into how a system might behave very
quickly. The package took a fraction of a second to produce the output seen above.
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 75
Operations Research
One factor that is of note is traffic intensity = (arrival rate)/(departure rate) where arrival rate = number
of arrivals per unit time and departure rate = number of departures per unit time. Traffic intensity is a
measure of the congestion of the system. If it is near to zero there is very little queuing and in general as
the traffic intensity increases (to near 1 or even greater than 1) the amount of queuing increases. For the
system we have considered above the arrival rate is 0.5 and the departure rate is 4 so the traffic intensity
is 0.5/4 = 0.125
The simple answer is that we can analyse this using the package. For the first situation one server
working twice as fast corresponds to a service rate µ=8 customers per minute. The output for this
situation is shown below.
For two servers working at the original rate the output is as below. Note here that this situation is a
M/M/2 queueing system. Note too that the package assumes that these two servers are fed from a single
queue (rather than each having their own individual queue).
Of the figures in the outputs above some are identical. Extracting key figures which are different we
have:
It can be seen that with one server working twice as fast customers spend less time in the system on
average, but have to wait longer for service and also have a higher probability of having to wait for
service.
Below we have extended the example we had before where now we have multiplied the customer arrival
rate by a factor of six (i.e. customers arrive 6 times as fast as before). We have also entered a queue
capacity (waiting space) of 2 - i.e. if all servers are occupied and 2 customers are waiting when a new
customer appears then they go away - this is known as balking.
We have also added cost information relating to the server and customers:
Note, as the above output indicates, that this is an M/M/1/3 system since we have 1 server and the
maximum number of customers that can be in the system (either being served or waiting) is 3 (one being
served, two waiting).
The key here is that as we have entered cost data we have a figure for the total cost of operating this
system, 3.0114 per minute (in the steady state).
Suppose now we were to have two servers instead of one - would the cost be less or more? The simple
answer is that the package can tell us, as below. Note that this is an M/M/2/4 queueing system as we
Session Feb06-Jun06 Dept of Electronics Staff:NLJ 78
Operations Research
have two servers and a total number of customers in the system of 4 (2 being served, 2 waiting in the
queue for service). Note too that the package assumes that these two servers are fed from a single queue
(rather than each having their own individual queue).
So we can see that there is a considerable cost saving per minute in having two servers instead of one.
In fact the package can automatically perform an analysis for us of how total cost varies with the number
of servers. This can be seen below.
General queueing
The screen below shows the possible input parameters to the package in the case of a general queueing
model (i.e. not a M/M/r system).
Here we have a number of possible choices for the service time distribution and the interarrival time
distribution. In fact the package recognises some 15 different distributions! Other items mentioned
above are:
service pressure coefficient - indicates how servers speed up service when the system is
busy, i.e. when all servers are busy the service rate is increased. If this coefficient is s and
we have r servers each with service rate µ then the service rate changes from µ to (n/r) sµ
when there are n customers in the system and n>=r.
arrival discourage coefficient - indicates how customer arrivals are discouraged when the
system is busy, i.e. when all servers are busy the arrival rate is decreased. If this coefficient
is s and we have r servers with the arrival rate being lamda then the arrival rate changes
from lamda to (r/(n+1))slamda when there are n customers in the system and n>=r.
batch (bulk) size distribution - customers can arrive together (in batches, also known as in
bulk) and this indicates the distribution of size of such batches.
As an indication of the analysis that can be done an example problem is shown below:
This screen indicates that no formulae exist to evaluate the situation we have set up. We can try to
evaluate this situation using an approximation formula, or by Monte Carlo Simulation. If we choose to
adopt the approximation approach we get:
The difficulty is that these approximation results are plainly nonsense (i.e. not a good approximation).
For example the average number of customers in the queue is -2.9813, the probability that all servers are
idle is -320%, etc. Whilst for this particular case it is obvious that approximation (or perhaps the
package) is not working, for other problems it may not be readily apparent that approximation does not
work.
If we adopt the Monte Carlo Simulation approach then we have the screen below.
What will happen here is that the computer will construct a model of the system we have specified and
internally generate customer arrivals, service times, etc and collect statistics on how the system
performs. As specified above it will do this for 1000 time units (hours in this case). The phrase "Monte
Carlo" derives from the well-known gambling city on the Mediterranean in Monaco. Just as in roulette
we get random numbers produced by a roulette wheel when it is spun, so in Monte Carlo simulation we
make use of random numbers generated by a computer.
These results seem much more reasonable than the results obtained the approximation.
However one factor to take into consideration is the simulation time we specified - here 1000 hours. In
order to collect more accurate information on the behaviour of the system we might wish to simulate for
longer. The results for simulating both 10 and 100 times as long are shown below.
Clearly the longer we simulate, the more confidence we may have in the statistics/probabilities obtained.
As before we can investigate how the system might behave with more servers. Simulating for 1000
hours (to reduce the overall elapsed time required) and looking at just the total system cost per hour
(item 22 in the above outputs) we have the following:
Hence here the number of servers associated with the minimum total system cost is 9