CHAPTER ONE

INTRODUCTION
The subject OPERATIONS RESEARCH is a branch of mathematics - specially applied
mathematics, used to provide a scientific base for management to take timely and effective
decisions to their problems. It tries to avoid the dangers from taking decisions merely by
guessing or by using thumb rules. Management is the multidimensional and dynamic
concept. It is multidimensional, because management problems and their solutions have
consequences in several dimensions, such as human, economic social and political fields. As
the manager operates his system in an environment, which will never remain static, hence
is dynamic in nature. Hence any manager, while making decisions, considers all aspects in
addition to economic aspect, so that his solution should be useful in all aspects.

1.1 HISTORY OF OPERATIONS RESEARCH

Operations Research is a ‘war baby’. It is because, the first problem attempted to solve in a
systematic way was concerned with how to set the time fuse bomb to be dropped from an
aircraft on to a submarine. In fact the main origin of Operations Research was during the
Second World War. At the time of Second World War, the military management in England
invited a team of scientists to study the strategic and tactical problems related to air and
land defense of the country. The problem attained importance because at that time the
resources available with England was very limited and the objective was to win the war
with available meager resources. The resources such as food, medicines, ammunition,
manpower etc., were required to manage war and for the use of the population of the
country. It was necessary to decide upon the most effective utilization of the available
resources to achieve the objective. Hence, the Generals of military, invited a team of experts
in various walks of life such as scientists, doctors, mathematicians, business people,
professors, engineers etc., and the problem of resource utilization is given to them to
discuss and come out with a feasible solution. These specialists had a brain storming
session and came out with a method of solving the problem, which they coined the name
“Linear Programming”. As the name indicates, the word Operations is used to refer to the
problems of military and the word Research is use for inventing new method. As this
method of solving the problem was invented during the war period, the subject is given the
name ‘Operations Research’ and abbreviated as ‘O.R.’ After the World War there was a
scarcity of industrial material and industrial productivity reached the lowest level.
Industrial recession was there and to solve the industrial problem the method linear
programming was used to get optimal solution. In industrial world, most important
problem for which these techniques used is how to optimize the profit or how to reduce the
costs.

Prepared by: - Addisu Teferi Operations Research Handout

Page 1
1.1.1 DEFINITION OF OPERATIONS RESEARCH
Each and every definition may explain one or another characteristic of Operations
Research but none of them explain or give a complete picture of Operations research. But in
the academic interest some of the important definitions are discussed below.
 Operations Research is defined as Scientific method for providing executive
departments a quantitative basis for decisions regarding the operations under their
control. P.M. Morse and G.E. Kimball.
 Operations Research is the application of scientific methods, techniques and tools to
operation of a system with optimum solution to the problem. - Churchman, Ackoff
and Arnoff.
 Operations Research is the use of Scientific Methods to provide criteria or decisions
regarding man-machine systems involving repetitive operations.
 Operations Research is applied decision theory. It uses any scientific, mathematical
or logical means to attempt to cope with problems that confront the executive, when
he tries to achieve a thorough going rationally in dealing with his decision problem.
D.W Miller and M.K Starr. No definition is having universal approach.

But salient features of above said definitions are:

 Operations Research uses Scientific Methods for making decisions.
 It is interdisciplinary approach for solving problems and it uses the knowledge and
experience of experts in various fields.
 While analyzing the problems all aspects are considered and examined and analyzed
scientifically for finding the optimal solution for the problem on hand.
 As operations research has scientific approach, it improves the quality of answers to
the problems.
 Operations research provides scientific base for decision-making and provide scientific
substitute for judgment and intuition.

1.2 MEANING AND NECESSITY OF OPERATIONS RESEARCH MODELS

We can define an operations research model as some sort of mathematical or theoretical
description of various variables of a system representing some aspects of a problem on some
subject of interest or inquiry. The model enables to conduct a number of experiment involving
theoretical subjective manipulations to find some optimum solution to the problem on hand.

1.2.1 CLASSIFICATION OF MODELS

The models we use in operations research may broadly classify as:
i. Mathematical and Descriptive models, and
ii. Static and Dynamic Models.

Prepared by: - Addisu Teferi Operations Research Handout

Page 2
 A. Mathematical and Descriptive Models
i. Descriptive Model
A descriptive model explains or gives a description of the system giving various variables,
constraints and objective of the system or problem. In article 1.8.1 gives the statement of
the problem, which is exactly a descriptive model. The drawback of this model is as we go
on reading and proceed; it is very difficult to remember about the variables and
constraints, in case the problem or description of the system is lengthy one. It is practically
impossible to keep on reading, as the manager has to decide the course of action to be
taken timely. Hence these models, though necessary to understand the system, have limited
use as far as operations research is concerned.
ii. Mathematical Model
In article, 1.8.2 we have identified the variables and constraints and objective in the
problem statement and given them mathematical symbols x and y and a model is built in
the form of an inequality of ≤ type. Objective function is also given. This is exactly a
mathematical model, which explains the entire system in mathematical language, and
enables the operations research person to proceed towards solution.

1.2.2 TYPES OF MODELS

Models are also categorized depending on the structure, purpose, nature of environment,
behavior, by method of solution and by use of digital computers.

a. Classification by Structure
i. Iconic Models: These models are scaled version of the actual object. For
example a toy of a car is an iconic model of a real car. In fact it is a descriptive
model giving the description of various aspects of real object. As far as
operations research is concerned, is of less use.
ii. Analogue Model: In this model one set of properties are used to represent
another set of properties. Say for example, blue color generally represents
water. Many a time we represent various aspects on graph by different colors
or different lines all these are analog models. These are also not much used in
operations research.
iii. Symbolic Models or Mathematical Models: In these models the variables of a
problem is represented by mathematical symbols, letters etc. To show the
relationships between variables and constraints we use mathematical
symbols. Hence these are known as symbolic models or mathematical models.
These models are used very much in operations research.

b. Classification by utility
Depending on the use of the model or purpose of the model, the models are classified as
descriptive, predictive and prescriptive models.

Prepared by: - Addisu Teferi Operations Research Handout

Page 3
 i. Descriptive model: The descriptive model simply explains certain aspects of the
problem or situation or a system so that the user can make use for his analysis. It
will not give full details and clear picture of the problem for the sake of scientific
analysis.
ii. Predictive model: These models basing on the data collected, can predict the
approximate results of the situation under question. For example, basing on
your performance in the examination and the discussions you have with your
friends after the examination and by verification of answers of numerical
examples, you can predict your score or results. This is one type of predictive
model.
iii. Prescriptive models: We have seen that predictive models predict the
approximate results. But if the predictions of these models are successful, then it
can be used conveniently to prescribe the courses of action to be taken. In such
case we call it as Prescriptive model. Prescriptive models prescribe the courses
of action to be taken by the manager to achieve the desired goal.

c. Classification by nature of environment

Depending on the environment in which the problem exists and the decisions are made,
and depending on the conditions of variables, the models may be categorized as
deterministic models and probabilistic models.
i. Deterministic Models: In this model the operations research analyst assumes
complete certainty about the values of the variables and the available resources
and expects that they do not change during the planning horizon. All these are
deterministic models and do not contain the element of uncertainty or
probability. The problems we see in Linear Programming, assumes certainty
regarding the values of variables and constraints hence the Linear Programming
model is a Deterministic model.
ii. Probabilistic or Stochastic Models: In these models, the values of variables, the
pay offs of a certain course of action cannot be predicted accurately because of
element of probability. It takes into consideration element of risk into
consideration. The degree of certainty varies from situation to situation. A good
example of this is the sale of insurance policies by Life Insurance Companies to
its customers. Here the failure of life is highly probabilistic in nature. The models
in which the pattern of events has been compiled in the form of probability
distributions are known as Probabilistic or Stochastic Models.

d. Classification depending on the behavior of the problem variables

Depending on the behavior of the variables and constraints of the problem they may be
classified as Static Models or Dynamic models.

Prepared by: - Addisu Teferi Operations Research Handout

Page 4
 i. Static Models: This model assumes that no changes in the values of variables
given in the problem for the given planning horizon due to any change in the
environment or conditions of the system. All the values given are independent of
the time. Mostly, in static models, one decision is desirable for the given planning
period.
ii. Dynamic Models: In these models the values of given variables goes on changing
with time or change in environment or change in the conditions of the given
system. Generally, the dynamic models then exists a series of interdependent
decisions during the planning period.

e. Classification depending on the method of getting the solution

We may use different methods for getting the solution for a given model. Depending on
these methods, the models are classified as Analytical Models and Simulation Models.
i. Analytical Models: The given model will have a well-defined mathematical
structure and can be solved by the application of mathematical techniques. We
see in our discussion that the Resource allocation model, Transportation model,
Assignment model, sequencing model etc. have well defined mathematical
structure and can be solved by different mathematical techniques. For example,
Resource allocation model can be solved by Graphical method or by Simplex
method depending on the number of variables involved in the problem. All
models having mathematical structure and can be solved by mathematical
methods are known as Analytical Models.
ii. Simulation Models: The meaning of simulation is imitation. These models have
mathematical structure but cannot be solved by using mathematical techniques.
It needs certain experimental analysis to study the behavior of the system, we
use random numbers. More complex systems can be studied by simulation.
Studying the behavior of laboratory model, we can evaluate the required values
in the system. Only disadvantage of this method is that it does not have general
solution method.

Prepared by: - Addisu Teferi Operations Research Handout

Page 5
 CHAPTER II

LINEAR PROGRAMMING (LP) MODEL

Linear programming is a mathematical technique designed to aid managers in allocating
scarce resources such as labor, capital, or energy among competing activities. It reflects, in
the form of a model, the organization's attempt to achieve some objective frequently,
maximizing profit contribution, production capacity, minimizing cots, in view of limited or
constrained resources available such as capital or labor, raw material, market demand,
production process, service levels, machine time, budgets and storage capacity etc.

The linear programming technique can be said to have a linear objective function that is to
be optimized either maximized or minimized, subject to linear equality or inequality
constraints and sign restrictions on the variables. The term linear describes the
proportionate relationship of two or more variables. Thus, a given change in one variable
will always cause a resulting proportional change in another variable.

L.P is solved in a step – by – step manner called iterations. Each step of the procedure is an
attempt to improve on the solution until the "best answer" is obtained or until it is shown
that no feasible answer exists.

Properties of Linear Programming Model

Any linear programming model (problem) must have the following properties:
a. The relationship between variables and constraints must be linear.
b. The model must have an objective function.
c. The model must have structural constraints.
d. The model must have non-negativity constraint.

Formulation of LP problem
The effective use of LP in real life problems requires proper and accurate formulation of
model, which has objective function along with constraints. The steps for formulating the
L.P are:
1. Identify the unknown decision variables to be determined and assign symbols to them.
2. Identify all the restrictions or constraints in the problem and express them as linear
equations or inequalities of decision variables.
3. Identify the objective or aim and represent it also as a linear function of decision
variables.

Let xi = decision variable for ith variable.

ci = profit or cost co-efficient of ith variable.
z = function to be maximized or minimized.

Prepared by: - Addisu Teferi Operations Research Handout

Page 6
Thus for n decision variables, the objective function is to maximize or minimize
z = c1 x1 + c2 x2 + ... + cn xn
Let aij = co-efficient of the jth constraint and ith variable
bi = resource limitation for ith constraint

Thus the restrictions may be expressed in the general form

a11x1 + a12x2 + ... + a1nxn b1
a21x1 + a22x2 + ... +a2nxn b2
am1x1+ am2x2 + ...+ amnxn bm
and xi > 0 for all values of i from 1 to n

The same linear programming problem can be expressed in a more condensed form using
summation notation or matrix equation.

Maximize Z =

Subject to for all i= 1, 2…... m

and xj 0 for all j= 1, 2…... n

Maximize Z = CX, subject to AX < B

Where C is a row vector and X and B are column vectors. A is a co-efficient matrix of the
order m x n.

Example1. A firm manufactures two products A & B on which the profits earned per unit
are Birr 3 & 4 respectively. Each product is processed on two machines M1 & M2. Product A
requires one minute of processing time on M1 and two minute on M2, while product B
requires one minute in M1 and one minute on M2. Machine M1 is available for not more
than 7:30 hours and M2 is available for 10 hours, during any working day. Formulate the
mathematical LP model.

Solution
Maximize Z = 3x1 + 4x2 Objective Function
Subject to x1 + x2 450
2x1 + x2 600 Linear Structural Constraints
Where x1, x2 0 Non - Negativity Constraint

Example2.

Prepared by: - Addisu Teferi Operations Research Handout

Page 7
A firm produces three products. These products are processed on three different machines.
The time required manufacturing one unit of the three products and the daily capacity of
the three machines are given in the table.

Machine Time per unit (minutes) Machine capacity (minutes)

Product 1 Product 2 Product 3
M1 2 3 2 440
M2 4 - 3 470
M3 2 5 - 430

The profit per unit for product 1, 2 & 3 is Birr 4, 3 & 6 respectively. Formulate the
mathematical LP model that will maximize daily profit.

Solution
Max Z = 4x1 + 3x2 + 6x3
Subject to 2x1 + 3x2 + 2x3 440
4x1 + 0x2 + 3x3 470
2x1 + 5x2 + 0x3 430
Where x1, x2 & x3 0

Example3.
A person wants to decide the constituents of a diet which will fulfill his daily requirement
of proteins, fats & carbohydrates at a minimum cost. The choice is to make from different
types of foods. The yields per unit of this food are given below. Formulate LP model for the
problem.

Food types Yield per unit Cost per unit

Proteins Fats Carbohydrates (Birr)
1 3 2 6 45
2 4 2 4 40
3 8 7 7 85
4 6 5 4 65
Maximum 800 200 700
requirement

Solution
Minimize Z = 45x1 + 40x2 + 85x3 + 65x4
Subject to 3x1 + 4x2 + 8x3 + 6x4 800

Prepared by: - Addisu Teferi Operations Research Handout

Page 8
 2x1 + 2x2 + 7x3 + 5x4 200
6x1 + 4x2 + 7x3 + 4x4 700
Where x1, x2, x3 & x4 0

Graphical Method
In graphical method, the inequalities (structural constraints) are considered to be
equations. This is because; one cannot draw a graph for inequality. Only two variable
problems are considered, because we can draw straight lines in two-dimensional plane (X-
1 axis and X-2 axis). More over as we have non negativity constraint in the problem that is
all the decision variables must have positive values always the solution to the problem lies
in first quadrant of the graph. This method consists of the following steps: -
1. Formulate the mathematical model for the given problem.
2. Convert the constraints given in the form inequality to that of equality.
3. Draw the x and y axes.
4. Plot each of the constraints on the graph.
5. Identify the feasible (solution) region.

Techniques of Graphical method

- Corner (extreme) point method: this method includes the following steps.
1. Identify each of the extreme points of the feasible region.
2. Find the values of objective function at each extreme point.
3. a. The optimal solution occurs at that corner point which maximizes objective
function in case of maximization problem.
b. The optimal solution occurs at that corner point which minimizes objective
function in case of minimization problem.

Example1: solve the following LP problem by using graphical method.

Maximize Z = 5x1 + 3x2
Subject to 3x1 + 5x2 15
5x1 + 2x2 10
Where x1, x2 0

Solution
Step1. Given problem is already in mathematical form.
Step2. Convert the constraints given in the form inequality to that of equality.
Step3. Draw the X and Y axes.
Step4. Plot each of the constraints on the graph.
Step5. Consider the 1st constraint 3x1 + 5x2 15, which will be graphed as 3x1 + 5x2 = 15. To
plot the line, find any two points that satisfy the equation, and then draw a straight line
through them.

Prepared by: - Addisu Teferi Operations Research Handout

Page 9
  Now, when x1 = 0, x2 = 3 and when x2 = 0, x1 = 5.
Constraint 5x1 + 2x2 10, which will be graphed as 5x1 + 2x2 = 10, will also be plotted
 When x1 = 0, x2 = 5 and when x2 = 0, x1 = 2.

The area bounded by all these constraints called feasible region, is shown in the figure by
shaded area OABC.

The coordinates of corner point’s feasible region are:

O = (0, 0), A = (2, 0), B = (1, 2.5) and C = (0, 3).

 Compute objective function value at each corner point of the feasible region.
Corner point coordinates(x1, x2) Z= 5x1 + 3x2
O (0, 0) (5 x 0) + (3 x 0) = 0
A (2, 0) (5 x 2) + (3 x 0) = 10
B (1, 2.5) (1 x 5) + (3 x 2.5) = 12.5
C (0, 3) (5 x 0) + (3x 3) = 9
x2

(0, 5) 5

4
5x1 + 2x2 = 10
(0, 3) 3C
B (1, 2.5)
2

1 3x1 + 5x2 = 15

A x1
0 1 2 3 4 5 6 7 8 9 10
(2, 0) (5, 0)

So, Maximize Z = 12.5 and x1 = 1 & x2 = 2.5

 Minimization Case
Example 2: Minimize the following graphical problem.

Prepared by: - Addisu Teferi Operations Research Handout

Page 10
Where x1, x2 0

Solution plot each constraint on graph in the same way as explained earlier. The feasible
region is shown in the figure by the shaded area OABCDE.
x2

900

800
(0, 750)
700 3x1 + 2x2 1500

600

(0, 500) 500 x1 400

(0, 400) 400 x2 400

C (300, 300)
300
A (400, 220)
200 Area 2x1 + 3x2 1500
B (400, 180)
100
x1

0 100 200 300 400 500 600 700 800

(400, 0) (750, 0)

The coordinates of extreme points of feasible region ABC are:

A = (400, 220), B = (400, 180) and C = (300, 300)
Compute objective function value at each extreme point.

Corner point Coordinates(x1, x2) Z= 50x1 + 60x2

A (400, 220) (50 x 400) + (60 x 220) = 33,200
B (400, 180) (50 x 400) + (60 x 180) = 30,800
C (300, 300) (50 x 300) + (60 x 300) = 33,000
So, Minimize Z = 33,200 and x1 = 400 & x2 = 180

Prepared by: - Addisu Teferi Operations Research Handout

Page 11
  Mixed Constraint LP Problem
Example 3
Minimize Z = 7x1 + 3x2
x1 + 2x2 3
x1 + x2 4
x1 3/2
x2 5/2
Where x1, x2 0

Solution: Draw the graph and find the extreme points of feasible region. The feasible region
is shown in the figure by shaded area ABCD.

x2

5 x1 1.5

(0, 4) 4

3 B (1.5, 2.5)
(0, 2.5) C x2 2.5
2 Area x1+x2 4
(0, 1.5) D
1 (1.5, .8) A x1+2x2 3
x1
0 1 2 3 4 5 6
(1.5, 0) (3, 0) (4, 0)

The coordinates of extreme point of region ABCD and objective function at each extreme
point are as follows:

Corner point Coordinates(x1, x2) Z= 7x1 + 3x2

A (1.5, 0.8) (1.5 x 7) + (0.8 x 3) = 12.9
B (1.5, 2.5) (1.5 x 7) + (2.5 x 3) = 18
C (0, 2.5) (0 x 7) + (2.5 x 3) = 7.5
D (0, 1.5) (0 x 7) + (1.5 x 3) = 4.5

So, Minimize Z = 18 and x1 = 1.5 & x2 = 2.5

Prepared by: - Addisu Teferi Operations Research Handout

Page 12
  Unbounded Solution

Example 4
Maximize Z = 6x1 + x2
Subject to 2x1 + x2 3
x2 – x1 0
Where x1, x2 0

Solution x2
5

4
x2 – x1 0
(0, 3) 3 B
2x1+x2 0
2
A (1, 1)
1
(0, 0) 0 1 2 3 4 5 x1
(1.5, 0)
Here, the feasible region is unbounded, as the values of the objective function at each
extreme points A (1, 1) and B (0, 3) are 7 and 3. There exist a number of points in feasible
region for which the value of objective function more the 7.
 Alternative solution
It is also known as multiple optimal solution case. It is a solution where the linear
programming problem has more than on optimal solution.
Example 5
Maximize Z = 4x1 + 4x2
Subject to x1 + 2x2 10
6x1 + 6x2 36
Where x1, x2 0
Solution

X2
(0, 6) 6
6x1 + 6x2 = 36
(0, 5) 5 C

4 B (2, 4)

Prepared by: - Addisu Teferi Operations Research Handout

Page 13
 3

1 x1 + x2 = 10

0
1 2 3 4 5 6 7 8 9 10 X1
(0, 0) (6, 0) (10, 0)
 The coordination of extreme points of feasible region OABC is:
O = (0, 0), A = (6, 0), B = (2, 4), C = (0, 5)
Corner point coordinates(x1, x2) Z= 4x1 + 4x2
O (0, 0) (4 x 0) + (4 x 0) = 0
A (6, 0) (4 x 6) + (4 x 0) = 24
B (2, 4) (4 x 2) + (4 x 4) = 24
C (0, 5) (4 x 0) + (4x 5) = 20
 Here, we have more than one optimal solution, hence it is alternative solution.
Max Z = 24
Infeasible solution
It involves the problem where no variables satisfy all the constraints. In this type of
problems, no unique feasible solution should be achieved.
Example 6
Maximize Z = 5x1 + 3x2
Subject to 4x1 + 2x2 8
x1 3
x2 7
Where x1, x2 0
X2
10

7 x2 = 7

Prepared by: - Addisu Teferi Operations Research Handout

Page 14
 4
4x1 + 2x2 = 8
3

2 x1 = 3

0
1 2 3 4 5 6 7 8 9 10 X1
 Here, there is no common area; hence it is having infeasible solution.

Important terms
 Solutions values of decisions variable of linear programming model are called
solutions.
 Basic solutions the variables which have zero values are non basic variables and the
remaining variables which contained non-zero variables are called basic variables.
For the set of simultaneous equations in Q known (P > Q), a solution obtained by
setting (p - Q) of variables equal to zero and solving the remaining P equations in P
unknown is as basic solution.
 Feasible solution the solution which satisfies all the constraints of linear
programming problems is called a feasible solution.
 Basic feasible solution a feasible solution which is also a basic solution is known as
a basic feasible solution.
 Optimal feasible solution a basic feasible solution which optimizes the objective
function is called n optimal feasible solution.
 Degenerate solution a basic solution is said to be degenerate if one or more basic
variables become zero.
 Infeasible solution the solution which does not satisfy all the constraints of linear
programming problem is called infeasible solution.

SIMPLEX METHOD
This method was developed by G.B. Dantzing in 1947. Simplex method is the steps of
algorithm until an optimal solution is reached. It is also known as iterative method. The
various steps involved in a simplex method are as follows.

Step1. Formulate the given problem into mathematical equations.

Step2. Introduce slack/surplus variables as per need.

Prepared by: - Addisu Teferi Operations Research Handout

Page 15
  Slack variables are imaginary products; contributing zero profit accordingly they
assigned zero coefficients in objective function.

Step3. Find initial basic feasible solution and express it into matrix (table) form.
Step4. Calculate all C-Z, and if all the values are found negative or zero, it is considered to
be an optimal solution, hence stop. Else follow the next steps. Z row coefficients under any
column are obtained by adding the products of elements under that column with the
corresponding values i.e. Z= , where aij are the matrix element in the ith row
jth column.
Step5. Select the greatest positive C-Z, the corresponding column of this value is called
Pivot column. The variable is called incoming or entering variable.
Step6. To determine the leaving variable, elements under solution values (b) divided by
the corresponding elements of pivot column and the row containing the minimum non-
negative ratio is marked. This ratio is called minimum ratio. The row so marked is called
pivot row. The variable is called leaving or outgoing variable. The intersection between
pivot column and row is known as pivot element.
Step7. The corresponding variable of pivot element enters the basis, while the slack
variables will leave the basis.
Step8. Generate new solution by the following steps given below.
 For pivot row, divide all elements of the row by pivot element.
 For remaining rows, use the following formula:
New value = old value – (F.R X corresponding element of pivot row).
Here F.R means Fixed Ratio
 F.R = pivot column elements / pivot element
Step9. Repeat the steps until the optimal solution is found.
Example 1 Solve the following linear programming problems using simplex method.
Maximize
Subject to –x1 + x2 0
-x + 2x3 0
X1 + x2 + x3 100
Where x1, x2, x3 0
Solution
Step1. Since the problem is given in mathematical form we will introduce slack variables to
convert inequality constraints to equality. Now the LP problem becomes.
Maximize Z= 12x1 + 15x2 + 14x3 + 0S1 + 0S2 + 0S3
Subject to -x1 + x2+ S1 = 0
-x1 + 2x3 + S2 = 0
X1 + x2 + x3 + S3 = 100

Prepared by: - Addisu Teferi Operations Research Handout

Page 16
Step2. To initiate basic feasible solution, we can start by assuming that the profit earned is
Zero.
X1 = x2 = x3 = 0
S1 = 0, s2= 0, s3 = 100 and Maximize Z = 0

The above information can be expressed in the form of a simple matrix as shown below:

C (contribution/ unit) 12 15 14 0 0 0
Fixed Profit Variables Solution X1 X2 X3 S1 S2 S3 Minimum
Ratio per In values(b) ratio
(F.R) unit(CB) basic(B)
- 0 S1 0 -1 (1) 0 1 0 0 0
0 0 S2 0 -1 0 2 0 1 0
1 0 S3 100 1 1 1 0 0 1 100/1
Z 0 0 0 0 0 0
C-Z 12 15 14 0 0 0
Step3. Since all C-Z 0 or positive, the current solution is not optimal. It could be improved.
Step4. Variable x2 is chosen to enter into the basis C-Z=15, which is the largest positive
number in column 2. This column is pivot column.
Step5. S3 is the outgoing variable since it is in pivot row.
Step6.
 For pivot row, divide all elements of the row by pivot element.
 For remaining rows, use the following formula:
For row 2
0-(0X0) =0, -1-(0X1) = -1, 0-(0X1) =0, 2-(0X0) =2, 0-(0X1) =0, 1-(0X0) =1 & 0-(0x0) = 0
For row 3
100-(1X0) =100, 1-(1X-1) =2, 1-(1X1) =0, 1-(1X0) =1, 0-(1X1) =-1, 0-(1X0) =0 & 1-(1-0) =1
Improved solution 1
C 12 15 14 0 0 0 Minimum
Fixed Profit Variables Solution X1 X2 X3 S1 S2 S3 ratio
Ratio(F.R) per In values(b)
unit(CB) basic(B)
-1/2 15 X2 0 -1 1 0 1 0 0 -
-1/2 0 S2 0 -1 0 2 0 1 0 -
- 0 S3 100 (2) 0 1 -1 0 1 100/2=50
Z -15 15 0 15 0 0
C-Z 27 0 14 - 0 0
15

Prepared by: - Addisu Teferi Operations Research Handout

Page 17
Here all elements are not negative or zero, so it is not an optimal solution. Hence we will
repeat the same procedure. X1 will replace s3.
For row 1
0-(-1/2X100) =50, -1(-1/2X2) =0, 1-(1/2X0) =1, 0-(1/2X1) =1/2, 1-(1/2X-1) =1/2, 0-
(1/2X0) =0 & 0-(1/2X1) =1/2
For row 2
0-(-1/2X100) =50, -1–(-1/2X2) =0, 0-(-1/2X0) =0, 2-(-1/2X1) =5/2, 0-(-1/2x-1) =-1/2,
1-(-1/2X0) =1 & 0-(-1/2X1) =1/2
Improved solution 2
C 12 15 14 0 0 0
Fixed Profit Variables Solution X1 X2 X3 S1 S2 S3 Minimum
Ratio per In values(b) ratio
(F.R) unit(CB) basic(B)
1/5 15 X2 50 0 1 ½ ½ 0 ½ 100
- 0 S2 50 0 0 (5/2) -1/2 1 1/2 20
1/5 12 X1 50 1 0 ½ -1/2 0 ½ 100
Z 12 15 27/2 3/2 0 27/2
C-Z 0 0 1/2 -3/2 0 -
27/2

 Here all elements are not negative or zero, so it is not an optimal solution. Hence we
will repeat the same procedure. X3 will replace s2.
For row 1
50-(1/5X50) =40, 0-(1/5X0) =0, 1-(1/5X0) =1, ½-(1/5X5/2) =0, ½(1/5X-1/2) =-2/5,
0-(1/5X1) =1/5, & ½(1/5X1/2) =2/5

For row 3
50-(1/5X50) =40, 1-(1/5X0) =0, 0-(1/5X0) = 0, ½(1/5X5/2) =0, -½(1/5X-1/2) =-2/5,
0(1/5X1) =-1/5 & ½-(1/5X1/2) =2/5

Improved solution 3
C 12 15 14 0 0 0
Fixed Profit Variables Solution X1 X2 X3 S1 S2 S3 Minimum
Ratio per In values(b) ratio
(F.R) unit(CB) basic(B)
15 X2 40 0 1 0 2/5 -1/5 2/5
14 X3 20 0 0 1 -1/5 2/5 1/5
12 X1 40 1 0 0 -2/5 -1/5 2/5
Z 12 15 14 7/5 1/5 68/5

Prepared by: - Addisu Teferi Operations Research Handout

Page 18
C-Z 0 0 0 -7/5 -1/5 -
68/5

All the C-Z 0, so the optimal solution from the above solution is:
X1= 40, x2= 40 x3= 20
Max Z= 12 x 40 + 15 x 40 + 14 x 20 = 1360

Example 2
Max Z = 2x1 + 5x2
Subject to x1 + 4x2 24
3x1+ x2 21
X1 + x2 9
Where x1, x2 0

Solution
Step1. Introduce slack variables s1, s2 & s3 the problem can be expressed in the following
standard form.

Max Z = 2x1 + 5x2 + 0s1 + 0s2 + 0s3

Subject to x1 + 4x2 + s1 =24
3x1+ x2 + s2 =21
X1 + x2 + s3 =9
Where x1, x2, s1, s2, s3 0

Step2. We shall start with a basic solution which we shall get by assuming that the profit
earned is zero. Setting x1=0 & x2=0 the constraints yield the following initial basic feasible
solution & will express it into matrix form.
S1 = 24, S2 = 21, & S3 = 9 and Z = 0

C 2 5 0 0 0
Fixed Profit Variables Solution X1 X2 S1 S2 S3 Minimum
Ratio per In values(b) ratio
(F.R) unit(CB) basic(B)
- 0 S1 24 1 (4) 1 0 0 24/4=6
¼ 0 S2 21 3 1 0 1 0 21/1 = 21
¼ 0 S3 9 1 1 0 0 1 9/1 = 9
Z 0 0 0 0 0
C-Z 2 5 0 0 0

Prepared by: - Addisu Teferi Operations Research Handout

Page 19
Step3. Since all C-Z 0, the solution is not optimal and can be improved.
Step4. Select the greatest positive C-Z the corresponding column of this value is pivot
column and find minimum ratio by dividing solution value (b)/pivot column.
Step5. Find pivot row and pivot element.
Step6. X2 is the incoming variable which replaces the outgoing variable S1.
Step7. Generate a new solution.

C 2 5 0 0 0
Fixed Profit Variables Solution X1 X2 S1 S2 S3 Minimum ratio
Ratio per In values(b)
(F.R) unit(CB) basic(B)
1/3 5 X2 6 ¼ 1 ¼ 0 0 6/1/4=24
11/3 0 S2 15 11/4 0 - 1 0 15/11/4=60/11
1/4
0 S3 3 (¾) 0 - 0 1 3/3/4=4
1/4
Z 5/4 5 5/4 0 0
C-Z 3/4 0 - 0 0
5/4

Since C-Z 0 the solution is not an optimal solution and can be improved. Here ¾ is the
pivot element and s3 is the outgoing variable and x1 is the incoming variable.

C 2 5 0 0 0
Fixed Profit Variables Solution X1 X2 S1 S2 S3 Minimum
Ratio per In values(b) ratio
(F.R) unit(CB) basic(B)
5 X2 5 0 1 1/3 0 -1/3
0 S2 4 0 0 2/31 -
11/3
2 X1 4 1 0 -1/3 0 4/3
Z 2 5 1 0 1
C-Z 0 0 -1 0 -1
Since all the values are negative or zero, third feasible solution is an optimal solution.
X1=4, X2=5 & X3=0
Max Z = 2X4 + 5X5 + 4X0 = 33

Prepared by: - Addisu Teferi Operations Research Handout

Page 20
ARTIFICIAL VARIABLES TECHNIQUES
There are many LP problems where slack variable cannot provide a solution. In these
problems at least one of the constraints is of ( ) or (=) type. In such cases we introduce
another type of variable called artificial variables. These variables are fictitious and have
no physical meaning. There are two types’ artificial variables.

I. Big – M Method
The steps of big M methods are as follows:
 Add slack and artificial variables to standard form per the need of LP problem.
Assign +M for Minimization ( ) & –M Maximization ( ).
 Calculate C – Z of the last row.
 If calculated values (C – Z) are 0, the solution is optimal.
 Select pivot/key column with the most negative C – Z value.
 Follow the further steps of simplex method.
Remarks
 Slack variables are added to (the left hand sides) the constraints of ( ) type and
subtracted from the constraints of ( ) type.
 Artificial variables are added to the constraints of ( ) and (=) type. Equality (=)
constraints do not require slack variables.
 Artificial Variables once driven out can never re-enter.

Example1.
Minimize Z = 12x1 + 20x2
Subject to 6x1 + 8x2 100
7x1 + 12x2 120
Where x1, x2 0

Solution
Step1. Express the problem in standard form.
Maximize Z = 12x1 + 20x2 + 0s1 + 0s2 + MA1 + MA2
Subject to 6x1 + 8x2 – S1 + A1 = 100
7x1 + 12x2 – S2+ A2 = 120
Where x1, x2, s1, s2, A1, A2 0

 The problem has six variables and two constraints four of the variables have to be
zero to get initial basic feasible solution to the artificial system.
Setting: - x1, x2, s1, s2 = 0
We get A1= 100, A2= 120 & Z= 220

Prepared by: - Addisu Teferi Operations Research Handout

Page 21
Note: Here Z = A
Step2. Perform optimality test.
C 12 20 0 0 M M
Fixe Profi Variable Solution X1 X2 S1 S2 A1 A2 Minimum
d t per s In values ratio
Ratio unit basic (b)
(F.R) (CB) (B)
2/3 M A1 100 6 8 -1 0 1 0 100/8 = 25/2
- M A2 120 7 (12) 0 -1 0 1 120/12 =10
Z 13M 20M -M -M M M
C-Z 12- 20-20M M M 0 0
13M

Since C-Z is negative under x1, x2 initial solution is not optimal and can be improved. X2
will enter and A2 will be deleted.

C 12 20 0 0 M Minimum
(F.R) (CB) (B) (b) X1 X2 S1 S2 A1 ratio
- M A1 20 4/3 0 -1 2/3 1 20/4/3=15

7/16 20 X2 10 7/12 1 0 -1/12 0 10/7/12=

120/7
Z 35/3+4/3 20 -M - M
C-Z M 5/3+2/3
M
1/3 – 4/3 0 M 5/3-2/3M 0

Since there are negative values it is not an optimal solution and can be improved. X1 will
replace A1.

C 12 20 0 0 Minimum ratio
(F.R) (CB) (B) (b) X1 X2 S1 S2
12 X1 15 1 0 -3/4 ½
20 X2 5/4 0 1 7/16 -3/4
Z 12 20 -1/4 -9
C-Z 0 0 1/4 9

Prepared by: - Addisu Teferi Operations Research Handout

Page 22
Since all values C-Z 0 it is an optimal solution.
X1 = 15, X2 = 5/4
Max Z = 12 X 15 + 20 X 5/4 = 205

Example 2
Maximize Z = 2x1 + 3x2 = 4x3
Subject to 3x1 + x2 + 4x3 600
2x1 + 4x2 + 2x3 480
2x1 + 3x2 + 3x3 = 540
Where x1, x2, x3 0

Solution
 Standard form
Maximize Z = 2x1 + 3x2 + 4x3 + 0s1 + 0s2 – MA1 – MA2
Subject to 3x1 + x2 + 4x3 + S1 = 600
2x1 + 4x2 + 2x3 – S2 + A1 = 480
2x1 + 3x2 + 3x3 + A2 = 540
Where x1, x2, x3, S1, S2, A1, A2 0
 Setting x1, x2 & x3 = 0, the following initial solution is obtained:
S1 = 600, A1 = 480 & A2 = 540; Z = - 1020 M.

C 2 3 4 0 0 -M -M Minimum
(F.R) (CB) (B) (b) X1 X2 X3 S1 S2 A1 A2 ratio
1/4 0 S1 600 3 1 4 1 0 0 0 600/1 = 600
- -M A1 480 2 (4) 2 0 -1 1 0 480/4 = 120

3/4 -M A2 540 2 3 3 0 0 0 1 540/3 = 180

Z -4M -7M -5M 0 M -M -M
C–Z 2+4M 3+7M 4+5M 0 -M 0 0

Since all C-Z are 0, the current solution is not optimal. Here x2 will replace A1.

C 2 3 4 0 0 -M Minimum
(F.R) (CB) (B) (b) X1 X2 X3 S1 S2 A2 ratio
7/3 0 S1 480 5/2 0 7/2 1 1/4 0 960/7
1/3 2 X2 120 ½ 1 1/2 0 -1/4 0 240
- -M A2 180 ½ 0 (3/2) 0 3/4 1 120

Prepared by: - Addisu Teferi Operations Research Handout

Page 23
 Z 3/2 – 3 3/2 – 3M/2 0 -3/4 – -M
C–Z M/2 3M/4
1/2+M/2 0 5/2+3M/2 0 3/4 + 0
3M/4

Since there is positive C – Z values it is not an optimal solution. Now we will introduce X3
and remove A2.

C 2 3 4 0 0 Minimum
(F.R) (CB) (B) (b) X1 X2 X3 S1 S2 ratio
0 S1 60 4/3 0 0 1 -3/2
2 X2 60 1/3 1 0 0 -1/2
4 X3 120 1/3 0 1 0 1/2
Z 7/3 3 4 0 1/2
C–Z -1/3 0 0 0 -1/2

Since all C – Z 0, the solution is optimal. The values of variables are:

 X1 = 0, X2 = 60, X3 = 120
 Maximize Z = 2 x 0 + 3 x 60 + 4 x 120 = 660

II. Two Phase Method

The two phase method deals with the removal of artificial variables in the 1st phase and
work for optimal solution in the 2nd phase. If at the end of the 1st phase, there still remains
an artificial variable in the basic at a positive value, it means there no feasible solution for
the problem given. In that case, it is not necessary to work on phase – II. If as feasible
solution exists for the given problem, the value of objective function at the end of phase – I
will be zero and artificial variable will be non variable. In phase – II original objective
coefficients are introduced in the final table of phase – I and the objective function is
optimized.

Note: The new objective function in phase – I is always minimization type regardless of
whether the original problem is maximization or minimization type.

Example 1
Maximize Z = 5x1 + 3x2
Subject to 2x1 + x2 1
X1 + 4x2 6
Where x1, x2 0
Solution

Prepared by: - Addisu Teferi Operations Research Handout

Page 24
Phase I consists of the following steps.
Set up the problem in the standard form
The original objective function Z = 5x1 + 3x2 is temporarily set aside during the phase I
solution. The given constraints, after the introduction of slack and artificial variables take
the form:
2x1 + x2 + s1 = 1
X1 + 4x2 – s2 + A1= 6
Where x1, x2, s1, s2, A1 0

 The new objective function is: - Minimize w = A1,

Thus, the problem for phase I in standard form becomes.

Minimize w = 0x1 + 0x2 + 0s1 + 0s2 + A1

2x1 + x2 + s1 = 1
X1 + 4x2 –s2 + A1= 6
Where x1, x2, s1, s2, A1 0

Step2. Find an initial basic feasible solution

Substituting x1 = x2 = s2 = 0 in the constraints equations we get s1 = 1, A1 = 6 as the initial
basic feasible solution.

C 0 0 0 0 1 Minimum
(F.R) (CB) (B) (b) X1 X2 S1 S2 A1 ratio
- 0 S1 1 2 (1) 1 0 0 1/1=1
1/4 1 A1 6 1 4 0 -1 1 6/2=3/2
Z 1 4 0 -1 1
C–Z -1 -4 0 1 0

Step3. Perform optimality test

Since C – Z is negative under some columns; it is not an optimal solution.
Step4. Iterate towards an optimal solution.
X2 is the incoming variable and s1 is the outgoing variable.

C 0 0 0 0 1 Minimum
(F.R) (CB) (B) (b) X1 X2 S1 S2 A1 ratio
0 X1 1 2 1 1 0 0
1 A1 2 -7 0 -4 -1 1
Z -7 0 -4 -1 1
C–Z 7 0 4 0 0

Prepared by: - Addisu Teferi Operations Research Handout

Page 25
Since C-Z either positive or zero under all columns it is optimal solution.
However, since w = A1 = 2 > 0 and artificial variable A1 appears in the basis at a positive
level (A1 = 2), the given problem does not possess a feasible solution and the procedure
stops.

Example 2
Maximize Z = 5x1 – 4x2 + 3x3
Subject to 2x1 + x2- 6x3 = 20
6x1 + 5x2 + 10x3 76
8x1 – 3x2 + 6x3 50
Where x1, x2, x3 0

Solution
Phase I
Step1. Introduce slack and artificial variables in the constraints of the given LP problem.
Maximize Z = 5x1 – 4x2 + 3x3 we set aside the objective function.
Subject to 2x1 + x2 - 6x3 + A1 = 20
6x1 + 5x2 + 10x3 + s1 = 76
8x1 – 3x2 + 6x3 + s2 = 50
Where x1, x2, x3, s1, s2, A1 0

 The new artificial objective function is Minimize Z = A1

 The new objective function is also called dummy objective function.

Step2. Find initial feasible basic solution:

 Setting variables x1, x2, x3 =0
A1 = 20, s1 = 76, s2 = 50

C 0 0 0 0 0 1 Minimum
(F.R) (CB) (B) (b) X1 X2 X3 S1 S2 A1 ratio
¼ 1 A1 20 2 1 -6 0 0 1 20/2=10
¾ 0 S1 76 6 5 10 1 0 0 76/6=38/3
- 0 S2 50 (8) -3 6 0 1 0 50/8=25/4
Z 2 1 -6 0 0 1
C-Z -2 -1 6 0 0 0

Step3. Perform optimality test.

Since C-Z is negative under some variables it is not optimal solution. X1 will replace s2.

Prepared by: - Addisu Teferi Operations Research Handout

Page 26
C 0 0 0 0 0 1 Minimum
(F.R) (CB) (B) (b) X1 X2 X3 S1 S2 A1 ratio
- 1 A1 15/2 0 (7/4) - 0 -1/4 1 30/7
15/2
29/7 0 S1 77/2 0 29/4 11/2 1 -3/4 0 154/29
3/14 0 X1 25/4 1 -3/8 6/8 0 1/8 0 -50/3
Z 0 7/4 - 0 -1/4 1
C-Z 15/2
0 -7/4 15/2 0 1/4 0

Since C-Z is negative under some variables it is not optimal solution. X2 will replace A1.

C 0 0 0 0 0 1 Minimum
(F.R) (CB) (B) (b) X1 X2 X3 S1 S2 A1 ratio
0 X2 30/7 0 1 30/7 0 -1/7 4/7
0 S1 52/7 0 0 256/7 1 2/7 -29/7
0 X1 55/7 1 0 -6/7 0 1/14 ¾
Z 0 0 0 0 0 0
C-Z 0 0 0 0 0 1

Since all C-Z are 0 it is an optimal solution.

Phase II. Phase II finds optimal solution for the original problem. Objective function for the
initial table of phase II is the objective function of the original problem. The remaining part
of initial table for phase II is the last table for phase I with the only difference C-Z.

C 5 -4 3 0 0 Minimum
(F.R) (CB) (B) (b) X1 X2 X3 S1 S2 ratio
-4 X2 30/7 0 1 30/7 0 -1/7
0 S1 52/7 0 0 256/7 1 2/7
5 X1 55/7 1 0 -6/7 0 1/14
Z 5 -4 90/7 0 13/14
C-Z 0 0 -69/7 0 -
13/14

Since all C-Z 0, it is an optimal solution.

X1= 55/7, X2= 30/7 and X3= 0

Prepared by: - Addisu Teferi Operations Research Handout

Page 27
Maximize Z = 5 X 55/7 – 4 X 30/7 = 155/7

DUALITY IN LINEAR PROGRAMMING

For every LP problem there is a related unique LP problem involving the same data which
also describes the original problem. The given (original) problem is called the primal
problem. Its converted form is known as Dual problem. The variables of the dual problem
are known as dual variables or shadow prices of the various resources. The following the
steps of duality:
1. If the primal contains n variables and m constraints, the dual contains m variables
and m constraints.
2. The maximization problem in the primal becomes minimization problem in the
dual and vice versa.
3. The maximization problem has ( ) constraints while the minimization problem
has ( ) constraints. If we have ( ) in maximization type and ( ) in minimization
type, then it will be multiplied by (- 1).
4. Constraints of type in the primal become type in the dual and vice versa.
5. The constants of c1, c2 c3……cn in the objective function of the primal appear in the
constraint of the dual.
6. The constants of c1, c2 c3……cn in the objective function of the primal appear in the
constraint of the dual.
7. The constants of b1, b2, b3……bm in the constraints of the primal appear in the
objective function of the dual.
8. A new set of variables appear in the dual.

Example 1: construct the dual to the primal problem.

Maximize Z = 3x1 + 5x2
Subject to 2x1 + 6x2 50
3x1 + 2x2 35
5x1 – 3x2 10
x2 20
Where x1, x2 0
Solution:
Let y1, y2, y3 and y4 be the corresponding dual variables, and then the dual problem is
given by
Minimize W = 50y1 + 35y2 + 10y3 + 20y4
Subject to 2y1 + 3y2 + 5y3 3
6y1 + 2y2 – 3y3 5
Where y1, y2, y3, y4 0

Example 2: construct the dual to the primal problem.

Prepared by: - Addisu Teferi Operations Research Handout

Page 28
Minimize Z = 3x1 – 2x2 + 4x3
Subject 3x1 + 5x2 + 4x3 7
6x1 + x2 + 3x3 4
7x1 – 2x2 – x3 10
X1 – 2x2 + 5x3 3
4x1 + 7x2 – 2x3 2
Where x1, x2, x3 0
Solution:
Maximize Z = 7y1 + 4y2 – 10y3 + 3y4 + 2y5
Subject to 3y1 + 6y2 – 7y3 + y4 + 4y5 3
5y1 + y2 + 2y3 – 2y4 + 7y5 - 2
4y1 + 3y2 + y3 + 5y4 – 2y5 4
Where y1, y2, y3, y4, y5 0

Example 3:
Max Z = 4x1 + 3x2
Subject to 2x1 + x2 72
x1 + 2x2 48
Where x1, x2 0
Solution:
Minimize Z = 72y1 + 48y2
Subject to 2y1 + y2 4
y1 + 2y2 3
Where y1, y2 0
Standard Form:
Minimize Z = 72y1 + 48y2 + 0s1 + 0s2 + MA1 + MA2
Subject to 2y1 + y2 – s1 + A1 4
y1 + 2y2 – s2 + A2 3
Where y1, y2, s1, s2, A1, A2 0

C 72 48 0 0 M M Minimum ratio
(F.R) (CB) (B) (b) X1 X2 S1 S2 A1 A2
M A1 4 2 1 -1 0 1 0 4
M A2 3 1 2 0 -1 0 1 3/2
Z 3M 3M -M -M M M
C-Z 72 - 48 – M M 0 0
3M 3M
A2 will be replaced x2.

Prepared by: - Addisu Teferi Operations Research Handout

Page 29
 C 72 48 0 0 M Minimum
(F.R) (CB) (B) (b) X1 X2 S1 S2 A1 ratio
M A1 5/2 3/2 0 -1 1/2 1 5/3
48 x2 3/2 1/2 1 0 -1/2 0 3
Z 3/2M+24 48 -M 1/2M- M
C-Z 24
48–3/2M 0 M 24- 0
1/2M
A1 will be replaced by x1.
C 72 48 0 0 Minimum
(F.R) (CB) (B) (b) X1 X2 S1 S2 ratio
72 x1 5/3 1 0 - 1/3
2/3
48 x2 2/3 0 1 1/3 -2/3
Z 72 48 -32 -8
C-Z 0 0 32 8

 Since all C – Z 0, it is an optimal solution. Where: - x1= 5/3 & x2=2/3.

Min Z= (72X5/3) + (48X2/3) = 152

SENSITIVITY ANALYSIS
While solving a linear programming problem for optimal solution, we assume that:
a. Technology is fixed
b. Fixed prices
c. Fixed levels of resources or requirements
d. The coefficients of variables in structural constraints (i.e. time required by a product
on a particular resource) are fixed, and
e. Profit contribution of the product will not vary during the planning period.

These assumptions, implying certainty, complete knowledge, and static conditions, permit
us to design an optimal programme. The condition in the real world however, might be
different from those that are assumed by the model. It is, therefore, desirable to determine
how sensitive the optimal solution is to different types of changes in the problem data and
parameters. The changes, which have effect on the optimal solution, are:
a. Change in objective function coefficients (aij)
b. Resource or requirement levels (bi),
c. Possible addition or deletion of products or methods of production.

The process of checking the sensitivity of the optimal solution for changes in resources and
other components of the problem, is given various names such as: Sensitivity Analysis,
Parametric Programming and Post optimality analysis or what if analysis.

Prepared by: - Addisu Teferi Operations Research Handout

Page 30
Post optimality test is an important analysis for a manager in their planning process, when
they come across certain uncertainties; say for example, shortage of resources due to
absenteeism, breakdown of machinery, power cut off etc. They may have to ask question
‘what if’, a double–edged sword.

They are designed to project the consequences of possible changes in the future, as well as
the impact of the possible errors of estimation of the past. The need for sensitivity analysis
arises due to:
i. To know the effect of and hence be prepared for, possible future changes in various
parameters and components of the problem,
ii. To know the degree of error in estimating certain parameters that could be
absorbed by the current optimal solution.
Or to put in other way, sensitivity analysis answers questions regarding what errors of
estimation could have been committed, or what possible future changes can occur, without
disturbing the optimality of the current optimal solution.

The outcome of sensitivity analysis fixes ranges i.e., upper limits and lower limits of
parameters like Cj, aij, bi etc. within which the current optimal programme will remain
optimal. Hence, we can say that the sensitivity analysis is a major guide to managerial
planning and control. Also sensitivity analysis arise the need for reworking of the entire
problem from the very beginning each time a change is investigated or incorporated. The
present optimal solution can be used to study the changes with minimum computational
effort. By adding or deleting a new column (product) or adding or deleting a new row (new
process) we can analyze the changes with respect to Cj, aij, and bi.

To summarize the Sensitivity analysis includes:

1. Coefficients (Cj) of the objective function, which include:
a. Coefficients of basic variables (Cj).
b. Confidents of non–basic variables.
2. Changes in the right hand side of the constraints (bi).
3. Changes in aij, the components of the matrix, which include:
a. Coefficients of the basic variables, aij.
b. Coefficients of non-basic variables.
4. Addition of new variables to the problem.
5. Addition of new or secondary constraint.

The above changes may results in one of the following three cases:
Case I. The optimal solution remains unchanged, that is the basic variables and their values
remain essentially unchanged.
Case II. The basic variables remain the same but their values are changed.
Case III. The basic solution changes completely.

I. Change in the Objective Coefficient

1. Non-basic Variables
Consider a change in the objective coefficient of the non-basic variable in the optimal
solution.

Prepared by: - Addisu Teferi Operations Research Handout

Page 31
Any change in the objective coefficient of the non-basic variable will affect only its index
row coefficient and not others.

Example 1:
Maximize Z = 2x1 + 2x2 + 5x3 + 4x4
1a + 3b + 4c + 3d ≤ 10
4a + 2b + 6c + 8d ≤ 25
a, b, c & d ≥ 0.

C 2 2 5 4 0 0 Minimum
(F.R) (CB) (B) (b) A b C d s1 s2 ratio
0 s1 10 1 3 (4) 3 1 0 10/4
0 s2 25 4 2 6 8 0 1 25/6
Z 0 0 0 0 0 0
C-Z 2 2 5 4 0 0

C 2 2 5 4 0 0 Minimum
(F.R) (CB) (B) (b) A b C d s1 s2 ratio
5 x3 5/2 ¼ ¾ 1 ¾ ¼ 0 10
0 s2 10 5/2 - 5/2 0 7/5 3/2 1 4
Z 5/4 15/4 5 15/4 5/4 0
C-Z ¾ -1.75 0 ¼ -5/4 0

C 2 2 5 4 0 0 Minimum
(F.R) (CB) (B) (b) a b c d s1 s2 ratio
5 x3 3/2 0 1 1 2/5 2/5 -1/10
2 x1 4 1 -1 0 7/5 -3/5 2/5
Z 2 3 5 2+14/5 2-
C-Z 6/5
0 -1 0 -4/5 -4/5 -3/10

Here ‘a’ and ‘c’ are basic variables and ‘b’ and‘d’ are non–basic variables. Consider a small
change x1 in the objective coefficient of the variable ‘b’, and then its index row (C – Z/net
evaluation row) element becomes:

(2 + x1) – (–2 + 5) = x1 –1. If variable ‘x2’ wants to be an incoming variable x1 – 1 must be

positive. Then the value of x1 should be > 1. Hence when, the value of the increment is > 1
and then the present optimal solution changes.

Prepared by: - Addisu Teferi Operations Research Handout

Page 32
Similarly for D, if x2 is the increment, then (4 + x2) – (14/5 + 10/5) = (4 + x2) – 24/5, hence
if’d’ wants to become incoming variable then the value of x2 > 4/5. To generalize, one can
easily conclude that for non-basic variables when its objective coefficient just exceeds its
index row coefficient in the optimal solution, the present solution ceases to be optimal.

2. Basic variables
Now let us consider a change in the objective coefficient of the basic variable in the optimal
solution. Here, it affects the net evaluation row coefficients of all the variables. Hence, as
soon as the C – Z/net evaluation row coefficients of basic variables become negative, it
leaves the solution, and that of non-basic variable becomes positive, it becomes an
incoming variable. In either case the present optimal solution changes.

Consider the above example. Let us say that there is a small reduction ‘x1’ in the objective
coefficient of variable ‘a’ i.e., (2– x1) then the net evaluation row coefficients of variables
are:

Variable corresponding change in net evaluation row element

a (2–x1) – 1 ( 2–x1) = 0
b 2 – {–1 (2–x1) + 5) = – (x1 + 1)
c 0
d – (4/5 + 7/5 x1)
s1 –4/5 + 3/5 x1
s2 – 3/10 + 2/5 x1
Results:
a. For any value of x1 variable 'b' cannot enter the solution.
b. As soon as x1 is > 4/7, variable’d’ enters the solution.
c. For any value of x1, S1 will not enter into solution.
d. As soon as x1 > 3/4, S2 claims eligibility to enter into solution.

A reduction in objective coefficient of variable 'a' by more than 4/7 and the present optimal
solution change. i.e., the value is 2 – 4/7 = 10/7.

When the objective coefficient of variable ‘a’ increases by a value x2, the changes are:

Variable Corresponding change

a (2 + x2) – (2 + x2) = 0
b 2 – (–1) {( 2+x2) + 5)} = –1 + x2
c 0
d –4/5 – 7/5 x2
s1 –4/5 + 3/5 x2
s2 –3/10–2/5 x2

 If x2 is ≥ 1 the variable ‘b’ claims the entry into solution and the optimal solution
changes.

Prepared by: - Addisu Teferi Operations Research Handout

Page 33
  For any value of x2 variables‘d’ and s1 are not affected.
 If x2 is > 4/3, s1 claims the entry into solution, and the optimal changes.
 Hence, as soon as objective coefficient of variable ‘a’ increases by more than 1 the
present optimal solution changes. Hence the maximum permissible value of
objective coefficient of ‘a’ is 2 + 1 = 3 for the present optimal solution to remain.
That is the range for objective coefficient of variable ‘a’ is 10/7 to 3.

II. Change in the right – hand side of the constraint

The right hand side of the constraint denotes present level of availability of resources (or
requirement in minimization problems). When this is increased or decreased, it will have
effect on the objective function and it may also change the basic variable in the optimal
solution.

Example2: A company manufactures three products: X, Y and Z by using three resources.

Each unit of product X takes three man hours and 10 hours of machine capacity and 1 cubic
meter of storage place. Similarly, one unit of product Y takes 5 man-hours and 2 machine
hours on 1cubic meter of storage place and that of each unit of products Z is 5 man-hours, 6
machine hours and 1 cubic meter of storage place. The profit contribution of products X, Y
and Z are Rs. 4/–, Rs.5/– and Rs. 6/– respectively. Formulate the linear programming
problem and conduct sensitivity analysis when

Maximize Z = 4x + 5y + 6z
3x + 5y + 5z ≤ 900
10x + 2y + 6z ≤ 1400
1x + 1y + 1z ≤ 250
x, y, & z ≥ 0

The final table of the solution is:

x= 50, y = 0, z = 150, S1 = 0, S2 = 0, S3 = 50 and Z = Rs. 1100/–

C 2 2 5 4 0 0 Minimum
(F.R) (CB) (B) (b) x y z s1 s2 s3 ratio
6 z 150 0 11/8 1 5/16 -3/32 10
4 x 50 1 -5/8 0 -3/16 5/32 0
0 s3 50 0 1/4 0 -1/8 -1/16 1
Z
C-Z 0 -23/4 0 -9/8 -1/16 0

The solution is x = 50, y = 0, z = 150, S1 = 0, S2 = 0, S3 = 50 and profit Z = Rs. 1100/–

Here man- hours are completely utilized hence S1 = 0, Machine hours are completely
utilized, hence S3 = 0 but the storage capacity is not completely utilized hence still we are
having a balance of 50 cubic meters of storage place i.e., S3 = 50.

Prepared by: - Addisu Teferi Operations Research Handout

Page 34
Value of dual variable under S1 in net evaluation row is 9/8. This is the shadow price or per
unit price of the resource. The resource is man- hours. Hence it means to say that as we go
on increasing one hour of man-hour resource, the objective function will go on increasing
by Rs. 9/8 per hour. Similarly the shadow price of machine hour is Rs. 1/16 and that of
storage space is Rs.0. Similar reasoning can be given. That is every unit increase in machine
hour resource will increase the objective function by Rs. 1/16 and that of storage space is
Rs.0/–

Now let us ask ourselves what the management wants to do:

C 2 2 5 4 0 0 Minimum
(F.R) (CB) (B) (b) x y z s1 s2 s3 ratio
6 z 150 0 11/8 1 5/16 -3/32 10
4 x 50 1 -5/8 0 -3/16 5/32 0
0 s3 50 0 1/4 0 -1/8 -1/16 1
Z
C-Z 0 -23/4 0 -9/8 -1/16 0

Question 1: If the management considers to increase man-hours by 100 hours i.e., from
900 hours to 1000 hours and machine hours by 200 hours i.e., 1400 hours to 1600 hours
will the optimal solution remain unchanged?

Now let us consider the elements in the identity matrix and discuss the answer to the above
question.

C 2 2 5 4 0 0 Minimum
(F.R) (CB) (B) (b) x y z s1 s2 s3 ratio
6 z 150 0 11/8 1 5/16 -3/32 10
4 x 50 1 -5/8 0 -3/16 5/32 0
0 s3 50 0 1/4 0 -1/8 -1/16 1
Z
C-Z 0 -23/4 0 -9/8 -1/16 0

Prepared by: - Addisu Teferi Operations Research Handout

Page 35
 CHAPTER - III
TRANSPORTATION MODEL
Transportation model was 1st introduced by F.L Hitch cook in 1941. Later on it was further
improved by T.C Koop man and George Dantzing. The objective is to transport the similar

Prepared by: - Addisu Teferi Operations Research Handout

Page 36
quantities which are initially stored at various origins (supply) to different destinations
(demand) in such a way that a total transportation cost is minimized.
Assumptions
1. Total quantity of the item available at different sources is equal to the total
requirement at different destinations.
2. It can be transported conveniently from all sources to destinations
3. The unit transportation cost of the item from all sources to destinations is certainly &
precisely known.
4. The transportation cost on a given route is directly proportional to the number of units
supplied on that route.
5. The objective is to minimize the total transportation cost for the organization as a
whole and not for individual supply and distribution centers.
General form
Suppose that there are m sources and n destinations:
Let: - ai = Quantity of product available at origin i.
bj = Quantity of products needed at destinations j.
cij = Cost of transporting one unit of product from origin i to destination j.
xij = Quantity of product transported from origin i to destination j.

Then, the transportation model would be in the form as follows: -

Maximize

Subject to where i=1, 2, 3 ………., m,

Where j=1, 2, 3 ……… …, n,

Where
The two sets of constraints will be consistent i.e. the system will be in balance if:-

 Transportation problem will be a feasible solution only if the above restriction is

satisfied. Thus, is necessary as well as a sufficient condition?
 A solution becomes feasible when total number of allocations is such that:
Total Allocations = m + n – 1

Destinations
1 2 3 4 5 Supply
source

origin

1 c11 c12 c13 c1j c1n a1

x11 x12 x13 x1j x1n
or

Prepared by: - Addisu Teferi Operations Research Handout

Page 37
 2 c21 c22 c23 c2j c2n a2
x21 x22 x23 x2j x2n
3 c31 c32 c33 c3j c3n a3
x31 x32 x33 x2j x3n
I ci1 ci2 ci3 Cij cin Ai
xi1 xi2 xi3 xij xin
M cm1 cm2 cm31 Cmj cmn Am
xm1 xm2 xm3 xmj xmn
Demand b1 b2 b3 Bj bn

Algorithm for transportation method

Transportation problem can be solved in the following steps: -
1. Define objective function.
2. Set up transportation table.
3. Develop initial feasible solution by any of the following three methods: -
a. North West Corner Method (NWCM).
b. Least Cost Method (LCM).
c. Vogel’s Approximation Method (VAM).
4. Test optimality of the initial basic feasible solution.
5. Update the solution accordingly and repeat step 3. Until optimal solution is reached.

A. North West Corner Method (NWCM)

The following steps are used in NWCM: -
1. Select the upper left hand corner cell of the given transportation table and allocate as
much as possible in such a way that either the capacity of the first row is exhausted or
the first column of demand is satisfied i.e. x11=min (a1,b1).
2. (a) If b1 > a1, move vertically down to second row and make the second allocation x21
= min (a1, b2 – x11).
(b) If b1 < a1, move horizontally right to the second column and make the second
allocation x12 = min (a1, x11 – b2).
(c) If b1 = a1, one can choose any one of the following: -
X12 = min (a1 – a1, b1) = 0
X21 = min (a2, b1 – b1) = 0
3. Repeat step 1 & 2 while moving down towards the lower right corner of the table.

Example1.
Destination
1 2 3 4 Supply
O
r
i

Prepared by: - Addisu Teferi Operations Research Handout

Page 38
 1 2 3 11 7 6
2 1 0 6 1 1
3 5 8 15 9 10
gin

Demand 7 5 3 2
Solution
1. The upper left corner is cell c11, where demand is 7 and supply is 6. So allocate 6 in cell
c11. Demand is not met.
2. Now move vertically to cell c21, here demand is 7 – 6 = 1 and supply is 1. So allocate 1
to cell 21.
3. Move to cell c32, where demand is 5 and supply is 10. So allocate 5 to cell c32.
4. Move horizontally to cell c33, where demand is 3 and supply is 10 – 5 = 5. So allocate 3
to cell c33.
5. Move horizontally to cell c34, where demand is 3 and supply is 10 – 5 – 3 = 2. So
allocate 2 to cell c34.
Destination
1 2 3 4 Supply
1 2 3 11 7 6
2 1 0 6 1 1
Origin

3 5 8 15 9 10
Demand 7 5 3 2
Total cost = 2 x 6 + 1 x 1 + 8 x 5 + 15 x 3 + 9 x 2 = 116
Example2.
Destination
D E F G Supply
A 11 13 17 14 250
B 16 18 14 10 300
Origin

C 21 24 13 10 400
Demand 200 225 275 250
Solution
1. The upper left cell is c11, where the demand is 200 and supply is 250. So
allocate 200 in c11. Here demand could meet supply.
2. Now move horizontally to the next cell c12. Here demand is 225 and supply is
250 – 200 = 50, so allocate 50 to cell c12.
3. Move vertically to the next cell c22. Here demand is 225 – 50 = 175 and supply
is 300. So allocate 175 to cell c22.
4. Move horizontally to the next cell c23. Here demand is 275 and supply is 300 –
175 = 125. So allocate 125 to cell c23.
5. Move vertically to the next cell c33. Here demand is 275 – 125 = 150 and supply
is 400. So allocate 150 to cell c33.

Prepared by: - Addisu Teferi Operations Research Handout

Page 39
 6. Move horizontally to the next cell c34. Here demand is 250 and supply is 400 –
150 = 250. So allocate 250 to cell c34.
Destination
D E F G Supply
A 11 (200) 13 (50) 17 14 250
B 16 18 (175) 14 (125) 10 300
Origin

C 21 24 13 (150) 10 (250) 400

Demand 200 225 275 250
Total cost = (200 x 11) + (50 x 13) + (175 x 18) + (125 x 14) + (150 x 13) + (250 x 10) =
12,200

B. Least cost method (LCM)

In this method we look for the minimum cost element of the entire matrix. Here locate cell
having the minimum cost element and allocate maximum quantity permissible.

Example1
Distribution centers
1 2 3 4 Supply
1 2 3 11 7 6
2 1 0 6 1 1
3 5 8 15 9 10
Plant

Demand 7 5 3 2

Solution
 Here, the lowest cost cell is (2, 2) maximum feasible allocation in this cell is (1). This
meets the supply position of plant 2. Therefore row is crossed out, indicating that no
allocations are to be made in cells (2, 1), (2, 3) and (2, 4). The next lowest cost cell is (1,
1) maximum allocation (6) is made here and row 1 is crossed out. Next lowest cell in
row 3 is (3, 1) and allocation of (1) is made. Likewise, allocation of (4), (2) and (3) are
made in cells (3, 2), (3, 4) and (3, 3) respectively.
Distribution centers
1 2 3 4 Supply
1 2 (6) 3 11 7 6
2 1 0 (1) 6 1 1
3 5 (1) 8 (4) 15 (3) 9 (2) 10
Plant

Demand 7 5 3 2

Total cost = (2 x 6) + (0 x 1) + (5 x 1) + (8 x 4) + (9 x 2) + (15 x 3) = 112

Prepared by: - Addisu Teferi Operations Research Handout

Page 40
Example 2
A B C Demand
I 1 2 3 50
II 3 2 1 80
III 4 5 6 75
IV 3 1 2 95
Supply 120 80 100

Solution
 On the examination we find there are 3 cells having minimum cost 1 Birr. These are
cell (1, 1,), (2, and 3) and (4, 1). Allocate maximum quantities to these cells as
shown.

A B C Demand
I 1 (50) 2 3 50
II 3 2 1 (80) 80
III 4 (70) 5 6 (5) 75
IV 3 1 (80) 2 (15) 95
Supply 120 80 100

Total cost = 50 x 1 + 80 x 1 + 70 x 4 + 5 x 6 + 80 x 1 + 15 x 2 = 550

C. Vogel’s Approximation Method (VAM) or penalty method

It is preferred to the methods described above.
Example - 1
Distribution centers
1 2 3 4 Supply
1 2 3 11 7 6
2 1 0 6 1 1
3 5 8 15 9 10
Plant

Demand 7 5 3 2

Solution: - the following steps to be followed.

1. Enter the difference between the smallest and second smallest element in each column
below the corresponding column and the difference between the smallest and second
smallest element in each row to the right of the row.
2. Determine the row or column which has the largest difference. If tie occurs, choose any
one of them randomly. Allocate as much as possible with in the restrictions to the
lowest cost cell in the row or column selected.

Prepared by: - Addisu Teferi Operations Research Handout

Page 41
 3. Cross out the row or column completely satisfied by the allocation just made.
4. Repeat the above steps.
Distribution centers
1 2 3 4 Supply Row penalty
1 2 (1) 3 (5) 11 7 6 115 XX
2 1 0 6 1(1) 1 1XXXX
3 5 (6) 8 15 (3) 9 (1) 10 33464
Demand 7 5 3 2
Column 1 3 5 6
penalty 3 5 4 2
3 X 4 2
4 X 15 9
Plant

4 X X 9

Total cost = (2 x 1) + (3 x 5) + (1 x 1) + (5 x 6) + (15 x 3) + (9 x 1) = 102

Example 2
A B C Demand
I 1 2 3 50
II 5 2 4 80
III 4 5 6 75
IV 3 1 2 95
Supply 120 80 100

Solution
 Here row 4 has the maximum difference. Hence select 4th row and allocate maximum
quantity in cell (4, 2) which is having minimum cost – 1. Maximum permissible
quantity is 80.
A B C Demand Row penalty
I 1 (50) 2 3 50 1 2 XX
II 5 2 4 (80) 80 2111
III 4 (70) 5 6 (5) 75 122 2
IV 3 1 (80) 2 (15) 95 3 111
Supply 120 80 100
Column 2 3 1
penalty 2 X 1
1 X 2
X X 2

Total cost = 50 x 1 + 80 x 4 +70 x 4 + 5 x 6 + 80 x 1 + 15 x 2 = 630

Prepared by: - Addisu Teferi Operations Research Handout

Page 42
 The Modified Distribution (MODI) Method or the U – V Method
In this method, cell evaluation of all the unoccupied cells are evaluated simultaneously and
only one closed loop (path) for the most negative cells is traced. The steps for MODI
method as follows: -
1. Find initial solution by using any of the three methods.
2. Count the number of occupied cells, if they are less than (m + n - 1), there is
degeneracy.
3. Solve the equation ui + vj = cij for each occupied cell in table, starting initially by
letting vj = 0 and solve progressively.
4. Calculate zij = cij – (ui + vj) for each unoccupied cell positions and write them in lower
left corner of that cell.
5. Identify the negative sign values and its corresponding cells among the values
calculated in step 4.
6. Let the selected unoccupied cell in step 5 is cxy, allocate an unknown quantity here (0).
Identify a closed loop that starts and ends at cell cxy while connecting some occupied
cells. Add and subtract interchangeably, (0) to and from the cells in the closed loop.
7. Assign the maximum value to 0 in such a way that the value of any one of the basic cell
(occupied) becomes zero while other remains positive or zero.
8. Go to step 3 and repeat the procedure until the optimal solution is found.

Example1
Destination
D1 D2 D3 D4 Supply
S1 21 32 52 12 7
Origin

S2 72 32 42 62 9
S3 42 10 72 22 18
Demand 5 8 7 14

Solution: by applying VAM method for initial solution, we will get the following initial
solution.
1. Find initial basic feasible solution by VAM.
D1 D2 D3 D4 Supply Ui
S1 21 32 52 12 7 U1 = 12
(5) (2)
S2 72 32 42 62 9 U2 = 62
(7) (2) -
S3 42 10 72 22 18 U3 = 22

Prepared by: - Addisu Teferi Operations Research Handout

Page 43
 - (8) (10) +
Demand 5 8 7 14
Vj V1 = 9 V2 = -12 V3 = 20 V4 = 0

2. In this initial solution, we have total of 6 allocations, which are equal to (m + n - 1),
hence it is not a degeneracy problem. Therefore, we can obtain its optimal solution.
The cost is birr 8,47,000
3. To calculate the values of ui and vj for each allocated cell, we take v4 = 0 randomly to
simplify the calculations.
Cij = ui + vj
Now c34 = u3 + v4 = 22,
u3 = 22 + 0 = 22
c24 = u2 + v4 = 62
u2 = 62 +v4 = 62
c14 = u1 + v4 = 12
u1= 12 + v4 = 12
By using the values of u1, u2 & u3 we can find the values of v1, v2 & v3.
c11 = u1 + v1 c23 = u2 + v3 c32 = u3 + v2
21 = 12 + v1 42 = 62 + v3 10 = 22 + v2
v1= 9 v2 = -20 v2 = -12

4. We will calculate the opportunity cost for each non allocated cell.
Zij = cij – (ui + vi)
z12 = c12 – (u1 + v2) = 32 – (12 - 12) = 32
z13 = c13 – (u1 + v3) = 52 – (12 - 20) = 60
z21 = c21 – (u2 + v1) = 72 – (62 + 9) = 1
z22 = c22 – (u2 + v2) = 32 – (62 - 12) = -18
z31 = c31 – (u3 + v1) = 42 – (22 + 9) = 11
z33 = c33 – (u3 + v3) = 72 – (22 - 20) = 70

5. Since not all the values are positive or zero, the current solution is not optimal. The
value of z22 = - 18 in cell (s2, D2) is indicating that total cost can be reduced in the
multiple of 18 by shifting the allocation of this cell.
6. A closed loop drawn along s2 to an occupied cell (s3, D2). Mark a (+) sign cell (s2, D2)
and (-) sign on (s3, D2). Take a right angle turn and find an allocated cell in column
D4. An allocated cell (s3, D4) exists at row 3 and marks (+) signs on this cell, while
continuing the process like this. Complete the closed loop.
7. Select the smallest allocation, which will determine the maximum number of units that
can be shifted along the closed loop. We will select cell (s2, D4) as it has the smallest
allocation. Now, this value will be added to cell (s2, D2) and (s3, D4) which have (+)

Prepared by: - Addisu Teferi Operations Research Handout

Page 44
 signs, the same value will be subtracted from cells (s2, D4) and (s3, D2) which have (-)
signs.
8. The revised table will be as follows: -

D1 D2 D3 D4 Supply Ui
S1 21 32 52 12 7 U1 = 0
(5) (2)
S2 72 32 42 62 9 U2 = 32
(2) (7)
S3 42 10 72 22 18 U3 = 10
(6) (12)
Demand 5 8 7 14
Vj V1 = 21 V2 = 0 V3 = 10 V4 = 12

Total cost = 8, 11,000

 Calculation for allocated cells
Step3. Let u1 = 0
c11 = u1 + v1 = 21 c23 = u2 + v3 = 42
= 0 + v1 = 32 + v3
v1 = 21 v3 = 10

c14 = u1 + v4 = 12 c32 = u3 + v2 = 10
= 0 + v4 = 10 + v2
V4 = 12 v2 = 0

c22 = u2 + v2 = 32 c34 = u3 + v4 = 22
= u2 + 0 = u3 + 12
u2 = 32 u3 = 10

Step4 calculate opportunity cost for each non allocated cell.

z12 = c12 – (u1 + v2) z24 = c24 – (u2 + v4)
= 32 – (0 + 0) = 62 – (32 + 12)
= 32 = 18
z13 = c13 – (u1 + v3) z31 = c31 – (u3 + v1)
= 52 – (0 + 10) = 42 – (10 + 21)
= 42 = 11
z21 = c21 – (u2 + v1) z33 = c33 - (u3 + v3)
= 72 – (32 + 21) = 72 – (10 + 10)

Prepared by: - Addisu Teferi Operations Research Handout

Page 45
 = 19 = 52
Step5. Since all the values are positive it is an optimal solution.

CHAPTER - IV
ASSIGNMENT MODEL
The Assignment Problem (AP) is a special case of transportation problem under the
condition is that the number of origins is equal to number of destinations. The objective is
to assign the given job (task) to most appropriate machine (person) so as to optimize the
objective function like minimizing cost. The unit available and the unit demanded should be
equal and there should be exactly one occupied cell in each row and column of the table.
Here, m = n
Hence assignment is made on the basis of 1:1.

Prepared by: - Addisu Teferi Operations Research Handout

Page 46
Assumptions
 Number of jobs is equal to number of machines or persons.
 Each man or machine is loaded with one and only one job.
 Loading criteria must be clearly specified such as minimizing operating time or
maximizing production or minimizing production cost etc.

HUNGARIAN METHOD
The Hungarian method was created by Mr. D. Koning of Hungary. He stated a theorem for
the method of modifying the rows and columns of matrix until there is at least one zero
component in each row and column, so that a complete assignment corresponding to the zero
can be made, which result in optimal solution. The Hungarian method of minimization case
consists of the following steps: -
1. Prepare a square matrix; this step will not be required for n x n assignment. For m x n
problems a dummy column or row is added as case may be to make the matrix square.

Man
Task E F G H
A 20 28 19 13
B 15 30 16 28
C 40 21 20 17
D 21 28 26 12

2. Reduce the matrix by subtracting the smallest element of each row from every element
of the corresponding row.
Man
Task E F G H
A 7 15 6 0
B 0 15 1 13
C 23 4 3 0
D 9 16 14 0
3. Examine if there is at least on zero in each column. If not, subtract the smallest
element of the columns.
Man
Task E F G H
A 7 11 5 0
B 0 11 0 13
C 23 0 2 0
D 9 12 13 0

Prepared by: - Addisu Teferi Operations Research Handout

Page 47
 4. Optimality test.
a. Examine the rows until a row with a single zero is found. Highlights this zero (0)
and cross (x) all other in its column. Continue this process for all the rows.
b. Examine columns successfully until a column with exactly one single zero is found.
Make assignment to this zero (0) and cross (x) all others in its row.

Man
Task E F G H
A 7 11 5 (0)
B (0) 11 0 13
C 23 (0) 2 0
D 9 12 13 0

Here, column 3 does not have any assignment, so will move into the next step.

5. Find the minimum number of lines crossing all zeros.

a. Mark (√) the rows that don’t have assignment.

b. Mark (√) the columns (not already marked) that have zeros in the marked
rows.
c. Mark (√) the rows (not already marked) that have assignments in marked
columns.
d. Repeat b & c till no more rows or columns can be marked.
e. Draw straight lines through all unmarked rows and marked columns.

Man
Task E F G H √ (b)
A 7 11 5 (0) √ (c)
B (0) 11 0 13
C 23 (0) 2 0
D 9 12 13 0 √ (a)

6. Generate new matrix as follows: -

 Select the smallest element of matrix not covered by any of the lines and subtract
this element from all uncovered element and add this element to elements laying at
the intersection of any two lines.
Man
Task E F G H
A 2 6 0 0

Prepared by: - Addisu Teferi Operations Research Handout

Page 48
 B 0 11 0 18
C 23 0 2 5
D 4 7 8 0

7. Repeat step 4 on reduced matrix.

Man
Task E F G H
A 2 6 (0) 0
B (0) 11 0 18
C 23 (0) 2 5
D 4 7 8 (0)

Now since each row and column has one and only one assignment an optimal solution is
reached. The optimum assignment is: -
A G, B E, C F and B H

 The minimum total schedule for this assignment is 19 + 15 + 21 + 12 = 67 man hours.

Maximization problem
In some special type of assignment problem, it is possible to find out a situation where the
objective function is to maximize instead of minimize. To deal with such kind of problems,
one has to convert the maximization into minimization problem. This could be achieved by
subtracting all the elements from the highest element of the matrix.

Example
Districts
Salesman 1 2 3 4
A 18 12 16 13
B 16 13 17 17
C 17 17 15 14
D 15 14 16 17

Solution
Step1. Convert maximization into minimization.

Districts
Salesman 1 2 3 4
A 0 6 2 5
B 2 5 1 1

Prepared by: - Addisu Teferi Operations Research Handout

Page 49
 C 1 1 3 4
D 3 4 2 1

Step2. Prepare square matrix.

Step3. Reduce matrix.

Districts
Salesman 1 2 3 4
A 0 6 2 5
B 2 5 0 0
C 0 0 3 4
D 3 4 2 0

Step4. Make assignments.

Districts
Salesman 1 2 3 4
A (0) 6 2 5
B 2 5 (0) 0
C 0 (0) 3 4
D 3 4 2 (0)

Then, the assignments will be: A 1, B 3, C 2 and D 4. Hence, the maximum sales per
day = 18 + 17 + 17 + 17 = 69

Non square matrix or unbalanced problem

In some special cases of assignment, it is possible to find out a matrix which is not a square.
It is called a non square or unbalanced problem, in which number rows not equal to
number of columns. To solve such kind of problems, firstly, we have to make the
unbalanced matrix a square matrix by adding suitable dummy row or column. After making
the dummy row or column, traditional Hungarian method can be applied to solve the
assignment problem.

Example
A B C D
1 9 14 19 15
2 7 17 20 19
3 9 18 21 18

Prepared by: - Addisu Teferi Operations Research Handout

Page 50
4 10 12 18 19
5 10 15 21 16

Solution The given cost matrix is not balanced, so we will add a dummy column with zero
cost in that column. The cost matrix after adding a dummy column will be as follows: -

A B C D E
1 9 14 19 15 0
2 7 17 20 19 0
3 9 18 21 18 0
4 10 12 18 19 0
5 10 15 21 16 0

Apply the Hungarian method to solve this modified matrix.

 This is left as an exercise.

CHAPTER - V
NETWORK MODELS AND PROJECT MANAGEMENT

Project is any undertaking that has definite, final objectives representing specified values to
be used in the satisfaction of some need or desire. In other words, Project is a set of
activities which are related to each other and are to be completed to signal the end of the
given project. Project management is different from manufacturing, sales and marketing
and yet, it involves every one of them. Setting up a factory is a project, building a bridge or
developing technology for new telephone network. This involves the activities like
scheduling, sequencing and forecasting. This also calls for managerial functions like
planning, organizing, directing and staffing.

Prepared by: - Addisu Teferi Operations Research Handout

Page 51
Project management is the art of directing and coordinating the human and material
resources throughout the like of a project by using management techniques to achieve pre-
determined objectives of scope, cost, time, and quality and participants satisfaction.

Network Techniques
Network is a technique in which a project is broken down into various activities which are
arranged in logical sequence in the form of a network. This approach assists managers to
visualize a project as a number of tasks which can be easily defined in terms of its duration,
cost, starting time and finishing time. There are two important techniques: -
 Critical Path Method (CPM).
 Programme Evaluation and Review Technique (PERT).

Important terms
 Events: - the beginning and end points of an activity are events or nodes.
 Activity: - any task or piece of work which consumes money, time and man power.
 Predecessor activity: - an activity which should be completed before any activity
could start.
 Successor activity: - an activity which starts immediately after any activity is
completed.
 Path: - a broken chain of activities arrows connecting the initial event to some other
event.
 Dummy activity: - an activity which only determines the dependency of one activity
on the other, but does not consume any time and resources.
 Loop: - when an activity goes back to the starting event.

Construction of network Diagram

Example: - Draw a network for the following project.
 A is the start event and K is the end event.
 A precedes event B.
 J is the successor event to F.
 C and D are successor events to B.
 D is the preceding event to G.
 E and F occur after event C.
 C restraints the occurrence of G and G precedes H.
 H precedes J and K succeeds J
 F restraints the occurrence of H.

5
E

Prepared by: - Addisu Teferi Operations Research Handout

Page 52
 1 2 3 6 9 10
A B C F J K

4 7 8
D D G H

Critical Path Method (CPM)

It uses activity oriented network which consists of a number of well recognized jobs, tasks
or activities. Each activity is represented by arrow and the activities are joined together by
events. CPM is generally used for simple, repetitive types of projects for which activity
times and costs are certainly and precisely known.

The critical path of a network gives the shortest time in which the whole project can be
completed. It is the chain of activities with the longest time duration. These activities are
called critical activities. They are critical in the sense that delay in any of them result in
the delay of the completion of the project. The critical path analysis consists of the
following steps:-

1. Calculate the time schedule for each activity: It involves the determination of the
time by which an activity must begin and the time before which it must be
completed. The time schedule data for each activity include the calculation of the
earliest start, the earliest finish, the latest start times and the float.
2. Calculate the time schedule for the completion of the entire project: It involves
the calculation of project completion time.
3. Identify the critical activity and find the critical path: Critical activities are the
ones which must be started and completed on the schedule or else the project may
get delayed. The path containing these activities is the critical path and is the longest
path in terms of duration.

Example: - Draw a network diagram and solve the problem by using CPM.
Activity: 1-2, 1-3, 2-3, 2-5, 3-4, 3-6, 4-5, 4-6, 5-6 and 6-7
Duration: 15 15 3 5 8 12 1 14 3 and 14
E=18 E=40 E=54
L=18 L=40 L=54
12 14 6 7
3
E=26
E=0 15 8 L=26 14 3
L=0 3
4
1
1 2
Prepared by: - Addisu Teferi Operations Research Handout
Page 53
 15 5
E=15 E=27 5
L=15 L=37

The critical path method may provide results by the following two types of calculations: -
A. Forward pass method
The Earliest Start Time (E) for an activity represents the time at which an activity
can begin at the earliest. Example, Earliest start time of activity 1-2 and 1-3 is zero
(0) or the earliest occurrence time of event 1 is zero (0). Earliest start time of
activities 2-3 and 2-5 or the earliest occurrence time of event 2 is obtained by adding
0 + 15 = 15.
 Here if, more than one activity coverage’s on its E’s via all paths would be computed
and the highest value chosen and put around the event.
B. Backward pass method
The Latest Finish Time (L) this calculated by proceeding progressively from the end
event to the start event. The Latest finish time for the last event is assumed to be
equal to its E.
 Here, if more than one activity originates from an event, compute L’s via all the paths
and chose the smallest value and put it around the event.

 Earliest Finish Time (T ) and the Latest Start Time (T ) for an activity are
computed.
T = E + tij
T = L – tij
Here, tij = time duration of activity.
F = L - T or F = T -E
Here, F = Total Float.

 Critical path is the path containing activities with zero (0) Float. For the
problem at hand it is 1 – 2 – 3 – 4 – 6 – 7 shown by double arrows are critical
path. The project duration is 54 weeks. Non critical activities have positive
Float. Delay in any critical activity will delay the project.

Prepared by: - Addisu Teferi Operations Research Handout

Page 54
 Activity Duration Start Time Finish Time Total
(i-j) (D) Earliest Latest Earliest Latest Float (F)
(E) (T ) (T ) (L) F=L-T
(L – tij) (E + tij) or
F=T - E
1–2 15 0 0 15 15 0
1–3 15 0 3 15 18 3
2–3 3 15 15 18 18 0
2–5 5 15 32 20 37 17
3–4 8 18 18 26 26 0
3–6 12 18 28 30 40 10
4–5 1 26 36 27 37 10
4–6 14 26 26 40 40 0
5–6 3 27 37 30 40 10
6–7 14 40 40 54 54 0

CHAPTER SIX
Decision Theory
Decision theory is a systematic procedure to identify the best possible decision among the
various available alternatives. Decision theory enables the decision maker to take the best
suitable decision by providing him the facilities to evaluate and examine the decisions as

Prepared by: - Addisu Teferi Operations Research Handout

Page 55
per the degree of certainty. This degree of certainty ranges from completely certain to
completely uncertain which also involves the mid range that has risk factor.

Characteristics of Decision Theory

a. List of Alternatives: the decision alternatives are the set of all possible courses of
action available for the decision maker. For e.g. for a company, there may be the
following three options:
 Expand the present plant.
 Construct a new plant
 Subcontract production for extra demand.
b. State of Nature: refers to a set of possible future conditions or events, beyond the
control of the decision maker that will be the primary determinants of the eventual
consequences of the decision. E.g.
 High demand.
 Moderate demand.
 Low demand.
 No demand.
c. Degree of Certainty: this shows that how much certain the decision is in present
condition whether it includes risk or uncertainty. If yes, then up to what extent.
d. Pay Off: in order for a decision maker to be able to rationally approach a decision
problem, it is necessary to have some idea of the payoff that would be associated
with each decision alternatives and various state of nature. The payoff might be
profit, revenues, costs or other measures of values. Usually the measures are
financial.
e. Decision Criterion: the decision maker will choose the criterion which result in
largest payoff. The criterion may be economic, quantitative or qualitative (e.g.
market share, profit etc).
f. Payoff Table: the decision maker constructs a payoff table for each possible
combination of alternative course of action and state of nature. The general format
of a payoff table is illustrated as follows:

State of Nature
Alternatives s1 s2 s3
a1 v11 v12 v13
a2 v21 v22 v23
a3 v31 v32 v33

Prepared by: - Addisu Teferi Operations Research Handout

Page 56
 ai = the ith alternatives.
sj = the jth state of nature.
vij = the payoff that will be realized if alternative i is chosen and event j occurs.
 The possible payoff for the manufacturing company’s expansion decision.

State of Nature (product demand)

Alternatives High Moderate Low Nil
Expand 50,000 25,000 -25,000 -45,000
Construct 70,000 30,000 -40,000 -80,000
Subcontract 30,000 15,000 -1,000 -10,000

Decision making under conditions of certainty

Here, only one state of nature exists, the decision maker simply pick up the best payoff in
that one column and chooses the associated alternatives. For e.g. if the company knew that
the demand would be high, it would chose the alternative “construct” to get the highest
payoff Birr 70,000, if it knew that the demand would be low, it would chose alternatives
“subcontract” to keep the losses lowest Birr 1,000.

Decision making under conditions of uncertainty

Here, the decision maker has knowledge about the state of nature that happens but lacks
the knowledge about the probabilities of their occurrence. Situations like launching a new
product fall under this category. The insufficient data lead to a more complex decision
model and perhaps a less satisfactory solution. However, one uses scientific methods to
exploit the available data to the fullest extent.

Under conditions of uncertainty, a few decision criterions are available which could be of
help to the decision maker these are:

The Maximax (Optimism) Criterion

This criterion provides the decision maker with optimistic criterion. He finds the maximum
possible payoff for each possible alternative and then chooses the alternative with the
maximum payoff within this group. The maximum payoff is Birr 70,000 corresponding to
the alternative “construct”.

State of Nature (product demand)

Alternatives High Moderate Low Nil Maximum of the
row
Expand 50,000 25,000 -25,000 -45,000 50,000

Prepared by: - Addisu Teferi Operations Research Handout

Page 57
 Construct 70,000 30,000 -40,000 -80,000 70,0000 Maximax
Subcontract 30,000 15,000 -1,000 -10,000 30,000

When dealing with costs, the minimum of each alternative is considered and then the
alternative which minimizes the above minimum cost is selected. This is called Minimin
criterion.

The Maximin (Pessimism) Criterion

This criterion provides the decision maker with pessimistic criterion. To use this criterion,
the decision maker maximizes his minimum possible payoff. He finds the minimum
possible payoff for each alternative and chooses the alternative with maximum payoff
within this group. The Maximini payoff to the company is Birr – 10,000 corresponding to
the alternative “Subcontract”.

State of Nature (product demand)

Alternatives High Moderate Low Nil Maximum of the row
Expand 50,000 25,000 -25,000 -45,000 - 45,000
Construct 70,000 30,000 -40,000 -80,000 - 80,000
Subcontract 30,000 15,000 -1,000 -10,000 - 10,000 Maximin

Thus, this criterion identifies the worst outcome of each alternative and then selects the
best of those worst outcomes.

When dealing with costs, the maximum cost associated with each alternative is considered
and the alternative that minimizes the above maximum cost is selected. This called
Minimax Criterion.

The Minimax (Regret) criterion

Both the Maximax and Maximin strategies can be criticized because they focus only on a
single extreme payoff and exclude the other payoff. Thus, the Maximax strategy ignores the
possibility that an alternative with a slightly smaller payoff might offer a better overall
choice. One approach that does take all payoffs into account is Minimax (Regret) approach.
Here, it is necessary to develop what is called an opportunity loss table. The opportunity
loss table shows values what the decision maker would loss for selecting other decision
alternative. The opportunity loss table reflects the difference between each payoff and the
best possible payoff in a column (i.e. given the state of nature). Hence opportunity loss
amounts are found by identifying the best payoff in the column and then subtracting each
of the other values in the column from that payoff. For the manufacturing company
problem, the conversion of the original payoff into an opportunity loss table is shown in the
table below:

Prepared by: - Addisu Teferi Operations Research Handout

Page 58
 State of Nature (product demand)
Alternatives High Moderate Low Nil Maximum of the
row
Expand 20,000 5,000 24,000 35,000 35,000 Minimax
Construct 0 0 39,000 70,000 70,000
Subcontract 40,000 15,000 0 0 40,000

This table shows, the decision maker first identify the maximum opportunity loss in each
row and then choose the alternative that would yield the best (minimum) of those regrets.

The principle of Insufficient Reason Decision Approach

This approach treats the state of nature as if each were equally likely and it focuses on the
average payoff for each row, selecting the alternative that has the highest row average. The
following table with three decision alternatives and five state of nature. The Insufficient
reasoning approach derives average payoff values for the three alternatives as 23.2, 9.6 and
9.6 respectively. The best alternative is row A1 = 23.2, Maximum.

State of Nature (product demand)

Alternatives S1 S2 S3 S4 S5 Row Average
A1 28 28 28 28 4 23.2
A2 5 5 5 5 28 9.6
A3 5 5 5 5 28 9.6

Decision Making under Conditions of Risk

Most of decisions may have to be made under conditions of risk. Here, more than one state
of nature exists and the decision maker has sufficient information to assign probabilities to
each of these states. These probabilities could be obtained from the past records or simply
the subjective judgment of the decision maker. There are two common used approaches:

The Expected Monetary values (EMV) Approach

The EMV approach provides the decision maker with a value which best represents an
average payoff for each alternative. The best alternative is then, one that has the highest
EMV. The average or highest expected payoff of probabilities is used to weight the
respective payoff. Thus, the EMV is:

EMV =

EMVi = the expected monetary value for the ith alternative.

Pj = the probability of the jth state of nature.
Vij = the estimated payoff for alternative i under the state of nature j.

Prepared by: - Addisu Teferi Operations Research Handout

Page 59
E.g. A real estate developer has the following probabilities:
 For No Shopping Center being built at 0.2.
 The probability of a Medium Size Shopping Center at 0.5.
 The probability of a Large Size Shopping Center at 0.3.

State of Nature (product demand)

Alternatives No center Medium Large center
center
Residential 4 16 12
Commercial-I 5 6 10
Commercial-II -1 4 15

We can compute the expected payoff for the real estate developer alternative. The EMV of
the Residential alternative is:
EMVR = (4x0.2) + (16x0.5) + (12x0.3) = 12.40
EMVC-I = (5x0.2) + (6x0.5) + (10x0.3) = 7.00
EMVC-II = (-1x0.2) + (4x0.5) + (15x0.3) = 6.30
 Since the residential alternative has the largest EMV, it would be selecting using this
criterion.

The Expected Opportunity Loss (EOL) Criterion

EOL represents the amount by which maximum possible payoff/profit will be reduced
under various possible stock options. The course action that minimizes these losses is the
optimal decision alternative. For the real estate problem the EOL can be calculated as
follows:
State of Nature (product demand)
Alternatives No center Medium Large center
center
Residential 1 0 3
Commercial-I 0 10 5
Commercial-II 6 12 0

EOLR = (1x0.2) + (0x0.5) + (3x0.3) = 1.10 Minimum

EOLC-I = (0x0.2) + (10x0.5) + (5x0.3) = 6.50
EOLC-II = (6x0.2) + (12x0.5) + (0x0.3) = 7.20

Note: the EOL approach resulted in the same alternative as EMV approach. The two
methods always result in the same choice.

Prepared by: - Addisu Teferi Operations Research Handout

Page 60
Expected Profit with Perfect Information (EPPI) Method
This is another variation of EMV, when all uncertainties are removed. Let us consider that
the retailer in our e.g. could secure a firm and recurring order every day.

State of Nature (product demand)

Alternatives No center Medium Large center
center
Residential 16
Commercial-I 5
Commercial-II 15

EPPI = (5x0.2) + (16x0.5) + (15x0.3) = 13.5

Expected Value of Perfect Information (EVPI)

 The EVPI is a measure d/ce b/n the certain payoff (EPPI) that could be realized
under a condition of certainty and the expected payoff (EMV) under a condition
involving risk.
EVPI = EPPI – EMV
 The d/ce b/n the figures is Birr 13.50 – 12.40 = 1.10, the amount by which he can
increase EMV by seeking perfect information. Thus is may be concluded the EVPI
equal to the minimum EOL.

 Consider once again the payoff the real estate investor could expect under certainty.
If the investor knew that No. center would be built, commercial – I. proposal would
be chosen and in which case a payoff Birr 5 could be realized; if the investor knew a
Medium size shopping center would built, the residential would be chosen for best
payoff Birr 16 and if the investor knew that large center would be built, commercial
– II proposal would be chosen for a payoff of Birr 15. Such are what we all decision
strategies that the investor is starting out which alternative to pick provided that a
certain state of nature is known to occur. However, what can be said is that the
probability that perfect information will indicate a Medium center w

Prepared by: - Addisu Teferi Operations Research Handout

Page 61