OR Module

UNIT ONE
1. INTRODUCTION TO OPERATIONS RESEARCH

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

It was also necessary to utilize the military resources cautiously. Hence, the Military Generals of
military, invited a team of experts that comprises scientists, doctors, mathematicians, business
people, professors, engineers etc., were presented with the problem of resource utilization that
they may discuss and come up with a feasible solution. These specialists had a brainstorming
session and arrived at a method of solving the problem, which they named as “Linear
Programming”. This method worked out well in solving the war problem. 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, 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. There was industrial recession and to solve the industrial
problem the method linear programming was used to get optimal solution.

From then on words, lot of work is done in the field and today the subject of OR has numerous
methods to solve different types of problems. After analyzing the success of British military, the
United States military management started applying the techniques to various activities to solve

1
OR Module
military, civil and industrial problems. They have given various names to this discipline. Some
of them are Operational Analysis, Operations Evaluation, Operations Research, System
Analysis, System Evaluation, Systems Research, Quantitative methods, Optimizations
Techniques and Management Science etc. But most widely used one is OPERATIONS
RESEARCH. In industrial world, most important problem for which these techniques used is
how to optimize the profit or how to reduce the costs. The introduction of Linear Programming
and Simplex method of solution developed by American Mathematician George B. Dontzig in
1947 given an opening to go for new techniques and applications through the efforts and co-
operation of interested individuals in academic field and industrial field. Today the scenario is
totally different. In one word we can say that Operations Research play a vital role in every
organization, especially in decision-making process.

1.2. Meaning of Operations Research:

? Activity
How do you define the term operation research?
_________________________________________________________________________
_________________________________________________________________________
_________________________________________________________________________

 Comments:
Operations Research is a systematic analysis of a problem through scientific methods, carried
out by appropriate specialists, working together as a team, constituted at the instance of
management for the purpose of finding an optimum and the most appropriate solution ,to meet
the given objective under a given set of constraints.

Operations
• The activities carried out in an organization/elsewhere.
Research
• The process of observation and testing characterized by the scientific method. Situation,
problem statement, model construction, validation, experimentation, candidate solutions.
• Operations Research (OR): is the application of scientific methods by inter-disciplinary
teams to problems involving the control of organized man-machine systems so as to
provide solutions which best serve the purposes of the organization as a whole (Ackoff-
Sasieni 1968)

2
OR Module
• OR is the application of a scientific approach to solving management problems in order
to help managers make better decision (Bernard W. Taylor III).
• OR is concerned with scientifically deciding how to best design and operate man-
machine system usually requiring the allocation of scare resources.” (Operations
Research Society, America)
• OR is the art of winning wars without fighting. (Clarke)
• Operations Research utilized the planned approach (updated scientific method) and an
interdisciplinary team in order to represent complex functional relationship as
mathematical models for the purpose of providing a quantitative basis for decision-
making and uncovering new problems for quantitative analysis (Thierauf and Klekamp)
From the concept and definition given above, Operations Research is:
1. The application of scientific methods, techniques and tools to the problem to find an answer
2. A management tool in the hands of a manager to take a decision
3. A scientific approach to decision making process
4. An “applied research” aims at finding a solution for an immediate problem facing a society,
industry or a business enterprise. This is not “fundamental research”
5. A decision-oriented research, using scientific methods, for providing management a
quantitative basis for taking decision regarding operations under its control
6. Applied decision theory. It uses scientific, mathematical and logical means to take decisions
The Five functions of Operations Research
A. objective: helps managers to make objective decision
B. scientific approach: helps decision makers to follow scientific approach to solve
managerial problems
C. inter disciplinary team work: it allows for team work
D. digital computers: over reliance on scientific calculators and other computing
machines
E. decision making: helps decision makers to solve managerial problems

1.3. Features of OR
An interdisciplinary team approach: the problems that OR analyst face are
heterogeneous in nature, involving the number of variables and constraints, which are
beyond the analytical ability of one person

3
OR Module
– Hence people from various disciplines are required to understand the operations
research problem.
A system (or Executive) approach: The decision made by any sub-system will have
its effect on other sub-systems. Therefore, to evaluate any decisions, one has to
identify all possible interactions and determine their impact on the organization as a
whole.
Application of Scientific Approach: OR applies scientific methods, techniques and
tools for the purpose of analysis and solution of the complex problems.
Use of Computers: The models of OR need lot of computation and therefore, the use
of computers becomes necessary.
OR offers a quantitative solution: you will get numbers as a result of running the
whole complex OR problems
Human factors: it incorporates the role of human factor in addition to the quantitative
elements it usually considers
Improvement in the quality of Decision: its scientific approach can only improve the
quality of decision but it may not be able to give perfect solution to organizational
problems. It may give bad answer to problems, otherwise, worse answers are given

1.4. MODEL AND MODELING IN OR

? Activity
What is a model?
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________

 Comments:
Model is the abstractions of a reality

Model is an abstraction of a reality. It is a simplified and often an idealized representation of real

objects/situations. Models can be classified in the following ways: Models are also categorized
depending on the structure, purpose, nature of environment, behavior, by method of
solution and by use of digital computers.

4
 OR Module
i. Classification based on structure
a. Physical (iconic) Model
Iconic models are the least abstract; they are physical models that look like the reality.
It is also called Static Model. It is given in two or three dimensions. It is a representation of the
real object as it is.
Example:
 Model of an airplane
 Photograph of a machine
 Layout drawing of a factory
 Glob
b. Analogue Models:
They are also physical models but they are more abstract than iconic models. Instead of
replicating physical appearance as iconic models do, these models substitute some physical
analogy for important aspects of the reality. These models mostly showing inter and intra
relationships between two or more parameters. It may show the relationship between an
independent variable (input) with that of a dependent variable (output). It is two dimensional
Example:
 histogram  Gantt charts
 frequency table  price-demand graph
 cause-effect diagram  world map with different colors
 flow charts  Organizational chart
c. Mathematical Models (Symbolic Models)
These are the most abstract models. They incorporate numbers and algebraic symbols to
represent important aspects of a problem often in equation form. Here a set of relations is
represented in the form of mathematical equations, using symbols to represent various
parameters.
Example:
Max Z=3000x1 +2500x2
Subject to:
2x1+x2 < 40
x1+3x2 < 45
x1 < 12

5
 OR Module

x1, x2> 0
Where:
The first line represents the objective function - A mathematical statement of the goal of an
organization, stated as intent to maximize or to minimize some important quantity such as
profits or costs.
Max Z=3000x1 +2500x2 is the objective function
 Lines three to six represent constraints-A restriction on the resources available to a
firm (stated in the form of an inequality or an equation.)

2x1+x2 < 40
x1+3x2 < 45 Are constraints
x1 < 12
x1, x2> 0 x1, x2> 0 is non-negativity constraint
 x1 and x2 are decision variables
ii. Classification by utility (Function): Depending on the use of the model or purpose of the
model, the models are classified as Descriptive, Predictive and Prescriptive models.
a. Descriptive model: The descriptive model simply explains certain aspects of the
problem or situation or a system which will not give full details and clear picture of
the problem for the sake of scientific analysis.
b. Predictive model: These models based on the data collected, can predict the
approximate results of the situation under question.
c. Prescriptive models: Prescriptive models prescribe the courses of action to be taken
by the manager to achieve the desired goal.
iii. 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.
a. 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.
b. Probabilistic or Stochastic Models:

6
 OR Module

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. Example of this is the sale of
insurance policies by Life Insurance Companies to its customers.
iv. 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.
a. 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.
a) 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.
v. 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.
Example: the Resource allocation model, Transportation model, Assignment
model, sequencing model etc. All models having mathematical structure and can
be solved by mathematical methods are known as Analytical Models.
ii. Simulation Models: Simulation is one of the most widely used quantitative
approaches to decision making.
It is a method for learning about a real system by experimenting with a model that represents
the system. The simulation model contains the mathematical expressions and logical
relationships that describe how to compute the value of the outputs given the values of the
inputs. Any simulation model has two inputs: controllable inputs and probabilistic inputs.
Only disadvantage of this method is that it does not have general solution method. These
models have mathematical structure but cannot be solved by using mathematical techniques.

7
 OR Module

UNIT TWO

2. LEANER PROGRAMMING PROBLEM MODELS (LPPM)

INTRODUCTION

In 1947, George Danzig developed the use of algebra for determining solutions to problems
that involved the optimal allocation of scarce resources.
The term linear implies that all the mathematical relations used in the problem are linear or
straight-line relations, while the term programming refers to the method of determining a
particular program or plan of action.

2.3.1 Meaning and Definition LPP

? Activity
What is a linear programming problem model?
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

 Comments:
Linear programming problem model is the mathematical form of a linear programming
problem.

 It is the mathematical representation of LP problems that has been developed to help

management in decision making, involving the efficient allocation of scares resources to
achieve an optimization objective.

8
 OR Module

Diagrammatically,

Scares Resource
To be allocated to: Objectives Optimization

Subject to Maximization Minimization

Constraints

Non-negativity Resource
Constraints constraints
2.3.2 Components of LP models

? Activity
What are the elements that form the structure of a linear programming problem model?
__________________________________________________________________________
__________________________________________________________________________
_______________________________________________________

 Comments:
The elements that form the structure of a linear programming problem model are known as
the components of a linear programming problem model. These are: objective function,
decision variables constraints and parameters.

9
OR Module

A. Objective Function: Is the goal or objective of a management, stated as intent to

maximize or to minimize some important quantity such as profits or costs.
B. Decision Variables: represents the unknown values to be solved by the decision makers.
Decision variables are the variables whose values are unknown and are searched.
C. Parameters: are fixed values that specify the impact of one unit on the objective function
and the constraint.
D. Constraints: are limitations or restrictions imposed by the problems. It includes:
 Recourse constraints: are restrictions that should be clearly identifiable and
measurable in quantitative terms, which arise from limitation of available resources.
Examples of limited resources:
 Plant capacity
 Raw materials availability
 Labor power
 Market demand, etc.
 Individual constraints: are constraints which are subject to individual decision
variables.
 Non-negativity constraints: are constraints that require the decision variables not to
take on negative values.
Generally speaking, a constraint also consists of four elements. These are:
I. A right hand side value (RHS): represents quantity that specifies the limit for that
constraint. It must be a constant, not a variable.
II. An algebraic sign: represents whether the limit is:
 An upper bound (<) that cannot be exceeded
 A lower bound (>) that is the lowest acceptable limit
 An equality (=) that must be met exactly.
III. The decision variable: to which the constraint applies.
IV. Parameters: The impact that one unit of each decision variable will have on the right
hand side quantity of the constraint.

2.3.3 Assumptions of LPP models

10
OR Module

? Activity
What are the conditions under which the LPPM is valid?
_____________________________________________________

 Comments:
The assumptions of linear programming problem models are: linearity, certainty, divisibility
and non-negativity.

The following are some important assumptions made in formulating a linear programming
model:
A. Linearity: The Objective Function and the constraints must be linear in nature in order to
deal with a Linear Programming Problems (LPP). Here the term linearity implies
proportionality and additively.
B. Certainty: It is assumed that the decision maker here is completely certain (i.e.,
deterministic conditions) regarding all aspects of the situation, i.e., availability of
resources, profit contribution of the Products, technology, courses of action and their
consequences etc.
C. Divisibility: It is assumed that the decision variables are continuous. It means that
companies manufacture products in fractional units. For example, a company
manufactures 2.5 vehicles, 3.2 barrels of oil etc.
D. Non- Negativity: indicate all variables are restricted to non-negative values (i.e., their
numerical value will be ≥ 0).i.e. negative values of variables are unrealistic or
meaningless.

2.4 FORMULATION OF LPPM

Formulating linear programming problem models involves the following steps
1. Identify the decision variables and represent them in terms of X1, X2…..
2. Determine the objective function:
 First decide whether the problem is maximization or minimization problem.

11
OR Module

 Second identify the coefficients of each decision variable.

 If the problem is a maximization problem, the profit per unit for each variable
must be determined.
 If the problem is a minimization problem the cost per unit must be determined.
 Make sure the units of measurements of all coefficients in the objective
functions must be the same.
3. Identify the constraints:
 First express each constraint in words.
 Second identify the coefficients of the decision variables in the constraints; and
the RHS values of the constraints.
 Determine the limits for the constraints i.e. see whether the constraint is of the
form (<), (>) or (=).
 Write the equation.
4. Using the above information (step 1 to 3) build the model.

NOTE THAT:
The coefficients of the variables in the Objective Function are called the profit or cost coefficients.
They express the rate at which the value of the Objective Function increases or decreases by
including in the solution one unit of each of the decision variables.

The coefficients of the constraints’ variables are called the input- output coefficients that indicate the
rate at which the given resources are depleted or utilized.

Example 1:
A firm that assembles computers and computer equipment is about to start production two
new microcomputers. Each type of microcomputers will require assembly time, inspection
time and storage space. The amount of each of these resources that can be devoted to the
production of these microcomputers is limited. The manager of the firm would like to
determine the quantity of each microcomputer to produce in order to maximize the profit
generated by sales of these microcomputers.
Additional information

12
OR Module

In order to develop a suitable model of the problem, the manager has met with design and
manufacturing personnel. As a result of these meetings the manager has obtained the
following information.

TYPE ONE TYPE TWO

Profit per unit Birr 60 Birr 50

Assembly time per unit 4 hours 10 hours

Inspection time per unit 2 hours 1 hour

Storage space per unit 3 cubic feet 3 cubic feet

The manager also has acquired information on the availability of company resources. These
weekly resources are:

RESOURCE AMOUNTS AVAILABLE

Assembly time 100 hours

Inspection time 22 hours

Storage space 39 hours

The manager also met with the firms marketing manager and learned that demand for the
microcomputers was such that whatever combination of these two types of microcomputers is
produced, all of the outputs can be sold.
Required: Formulate the LPPM of the problem.
Solution
Step 1: identify the decision variable
 the quantity/ amount/ units of each microcomputer (microcomputer type 1 and
microcomputer type 2) to be produced

Letx1represents quantity of microcomputer type 1 to be produced

x2represents quantity of microcomputer type 2 to be produced

Step 2: Identify the objective function

13
OR Module

The problem is maximization problem, as indicated in the problem (5th line of the
problem)
To write the equation both the objective function and the constraints summarize the given
information in tabular form accordingly

RESOURCE TYPE TYPE TWO AVAILABILITY

ONE

Assembly time per unit 4 hours 10 hours 10 hours

Inspection time per unit 2 hours 1 hour 1 hour

Storage space per unit 3 cubic feet 3 cubic feet 3 cubic feet

Profit per unit Birr 60 Birr 50

 Max Z = 60x1 + 50 x2

Step 3: identify each constraints and write the equation

 Assembly time 4x1 + 10x2<100

 Inspection time 2x1 + x2< 22

 Storage space 3x1+ 3x2<39

 Non negativity constraint x1& x2> 0

Step 4: write the summarized form of the model

In summary, the mathematical model of the microcomputer
problem is:
Max Z+ 60x1 + 50x2
Subject to
4x1 + 10x2< 100
2x1 + x2< 22
3x1+ 3x2< 39
x1 & x2> 0

Example 2:

14
OR Module

A firm is engaged in breeding pigs. The pigs are feed on various products grown on the farm.
In view of the need to ensure certain nutrient constituents (call them vitamins, minerals and
proteins) it is necessary to buy two additional products say A and B. One unit of product A
contains 36 units of vitamins, 3 units of minerals and 20 units of proteins. One units of
product B contains 6 units of vitamins, 12 units of minerals and 10 units of proteins. The
minimum requirement of vitamins, minerals and proteins is 108units, 36units and 100 units
respectively. Product A costs birr 20 per unit and product B costs birr 40 per unit
Required: formulate the LPPM of the problem
Step 1: identify the decision variables
Product A and B to be purchased to prepare the food for pigs
Let x1 represent product A to be purchased
X2 represent products B to be purchased

Step 2: identify the objective function

The problem is a minimization problem, so the equation;
 Min Z = 20x1 + 40 x2

When we put the information in a tabular form

NUTRIENT
CONSTITUENTS PRODUCT A PRODUCT B REQUIREMENT
Vitamins 36 units 6 units 108 units

Minerals 3 units 12 units 36 units

Proteins 20 units 10 units 100 units

Cost per unit Birr 20 Birr 40

Step 3: identify each constraints and write the equation

 Vitamins 36x1 + 6x2> 108

 Minerals 3x1 +12 x2> 36

 Proteins 20x1+ 10x2>100

15
OR Module

 Non negativity constraint x1& x2> 0

Step 4: write the summarized form of the model

In summary, the mathematical model of the problem is:

Min Z=60x1 + 50x2
Subject to
36x1 + 6x2> 100
3x1 +12 x2> 22
20x1+ 10x2>39
x1 & x2> 0

2.5 APPROACHES TO SOLVE LPPM

There are two methods used to solve LP problems
1. Graphical methods

2. Simplex methods

1. Graphical methods: used to find solutions for LPP when the decision variables of the
problem are not greater than two.

Graphical LP is a two-dimensional model

To apply this method, we should follow the following steps.

A. Draw a graph including all the constraints

B. Identify the feasible region

C. Identify the corner points and its coordinates

D. Evaluate the objective function at each corner point and Obtain a point on
the feasible region that optimizes the objective function-Optimal solution

E. Interpret the results

Examples 1: Consider the microcomputer problem and solve it using graphical approach.
Step one: Graph each constraint: To draw the graph first change the inequality to equality
i.e. replace the <and> sign into = sign.
Max Z=60x1 + 50x2

16
OR Module

Subject to
36x1 + 6x2> 100 36x1 + 6x2= 100
3x1 +12 x2> 22 3x1 +12 x2= 22
20x1+ 10x2>39 20x1+ 10x2 =39
x1 & x2> 0

Then find the x and y intercepts (in our case x1 and x2 respectively) - points where each
constraint intersects the axis. To do so, set x1 =0 to find values for x2 and set x2= 0 to find
values for x1.
For the first constraint:
4x1 + 10x2 = 100 4x1 + 10x2 = 100
4(0) + 10 x2 = 100 4x1 + 10(0) = 100
10x2= 100 4x1= 100
X2= 10 x1 = 25
The x1 and x2 intercepts are (0, 10) (25, 0). Similarly calculate for the second and third
constraints.
For the second constraint the intercepts are (0, 22) (11, 10)
For the third constraint the intercepts are (0, 13) (13, 0)
Graph the constraints using the intercepts calculated above. The graph is:

17
OR Module

As indicated in the graph, the corner points of the feasible region (the corner points of the
shaded region) are A, B, C, D and E. The next task is to find the coordinates of these corner
points, some are determined by observation and some are through simultaneous equation.
Then we test each corner points to find the points that results the optimal solution. These
activities are indicated in the following table.

Evaluating the corner points

Point Coordinates How determined Value of the objective function

X1 X2 Max Z=60x1 + 50x2

A 0 0 Inspection 60(0) + 50(0) = 0

B 11 0 Inspection 60(11) + 50(0) =660

C 9 4 Simultaneous 60(9) + 50(4) =740

equation

D 5 8 Simultaneous 60(5) + 50(8) =700

equation

E 0 10 Inspection 60(0) + 50(10)=500

Since the maximum value (because the objective function of the problem is maximization) is
740. The solution is
X1= 9, X2= 4 and The Maximum Profit is Birr 740.
When we interpret the result, the company should produce 9 units of microcomputer type
one and 4 units of microcomputer type two to get a maximum profit of Birr 740.
Example 2
Suppose that a machine shop has two different types of machines; machine 1 and machine 2,
which can be used to make a single product. These machine vary in the amount of product
produced per hr., in the amount of labor used and in the cost of operation.
Assume that at least a certain amount of product must be produced and that we would like to
utilize at least the regular labor force. How much should we utilize each machine in order to
utilize total costs and still meets the requirement?
Solution

18
 OR Module

Resource used
Machine 1 (X1) Machine (X2) Minimum required hours
___________________________________________________________________________
_____________
Product produced/hr 20 15 100
Labor/hr 2 3 15______
Operation Cost $25
$30____________________________________
Min.Z  25 X 130 X 2
St :
20 X 115 X 2 100 LPP Model

2 X 13 X 2 15
X1, X 2  0
Constraint equation:
20X1 +15X2=100 ==> (0, 20/3) and (5, 0)
2X1+3X2=15 ==> (0, 5) and (7.5, 0)
X1 X2> 0

X2
X1 =0
A (0, 20/3)

Feasible Region

B (2.5, 3.33)
X2 =0

X1
5 C (7.5, 0)

19
OR Module

Corners Coordinates MinZ=25 X1 + 30X2

A (0, 20/3) 200
B (2.5, 3.33) 162.5
C (7.5, 0) 187.5
_______________________________________________________________
X1 =2.5 X2=3.33 and MinZ= 162.5
2. Simplex method
The graphical method to solving LPPs provides fundamental concepts for fully understanding
the LP process. However, the graphical method can handle problems involving only two
decision variables (say X1and X2).

In 19940’s George [Link] developed an algebraic approach called the Simplex Method
which is an efficient approach to solve applied problems containing numerous constraints;
and involving many variables that cannot be solved by the graphical method.
The simplex method is an ITERATIVE or “step by step” method or repetitive algebraic
approach that moves automatically from one basic feasible solution to another basic feasible
solution improving the situation each time until the optimal solution is reached at.

MAXIMIZATION PROBLEM
i. Maximization having all the constraints in “<” form
Example: Consider the microcomputer problem which is solved with graphical method so
that you can compare and contrast the two approaches.
Max Z+ 60x1 + 50x2
Subject to
4x1 + 10x2< 100
2x1 + x2< 22
3x1+ 3x2< 39
x1 & x2> 0
To solve the problem using the simplex approach, follow the following steps.
Step 1

20
OR Module

Formulate LPP Model: in our example it is already done.

Step 2
Standardize the problem
I.e. convert each constraint into a standard form by introducing a variable called Sack
variable, surplus variable and artificial variable
Slack Variables(S): A sack variable/sis /are added to the left hand side of a < constraint to
covert the constraint into its standard form. The value of the slack variable shows unused
resource.
Surplus variables(S): A surplus variable/sis/are added to the left hand side of a >constraints
to convert the constraint into its standard form. The value of the surplus variable shows the
excess resources used.
Artificial variables (A): somewhat analogous to slack variables in that they are added to
equality and a > constraints in the same way that slack variables are added to a<constraints.
However artificial variables have no physical interpretation, they merely serve as a device to
enable us to use the simplex process.
Since the above problem constraints have all a <algebraic sign, we use slack variables for
standardizing the problem.

A slack variable is always added for a < constraint to convert the constraint to a standard form.

Slack variables represent unused resource or idle capacity. Thus, they don’t produce any
product and their contribution to profit is zero.

Slack variables are added to the objective function with zero coefficients.
Max Z+ 60x1 + 50x2+0s1+0s2+0s3
Subject to
4x1 + 10x2+s1=100
2x1 + x2+s2= 22
3x1+ 3x2 +s3=39
x1 , x2 ,s1,s2,&s3> 0

21
 OR Module

NOTE THAT;
To standardize, start from the constraint and finally move to the objective function.
When you add the slack variables it should be according to the existence of the constraints (how it
is written in the model). I.e. add S1 to the first constraint, s2 to the second constraints etc.

Step 3
Obtain the initial simplex tableau
To make ready the data for analysis, the simplex method uses a table called the simplex
tableau or the simplex matrix.
In constructing the initial simplex tableau, the search for the optimal solution begins at the
origin. Indicating that nothing can be produced;
Thus, based on this assumption, no Microcomputer Type One and Microcomputer Type
Two is produced, which implies that x1 =0 and x2=0

==>4x1+10x2+ s1 +0 s2+ 0 s3= 100 ==> 2x1+x2+0s1 + s2+ 0s3= 22

2(0) +10(0) + s1 +0 s2+ 0 s3= 100 2(0) +0+0s1 + s2+ 0 s3= 22
s1= 100 – Unused assembly time. s2= 22 – Unused inspection time.
==> 3x1+ 3x2+0s1 +0s2+ s3= 39
3(0) +3(0) +0s1 +0 s2+ s3= 39
s3= 39 – Unused storage space.
Therefore, Max Z=60x1 +50x2 + 0 s1 +0 s2+ 0 s3
=60(0) +50(0) + 0(100) +0(22) + 0(39)
=0
NOTE THAT;
In general, whenever there are n variables and m constraints (excluding the non-negativity),
where m is less than n (m<n), n-m variables must be set equal to zero before the solution can be
solved algebraically.
a. Basic variables
a. are variables with non-zero solution values
b. are variables that are in the basic solution

22
OR Module

c. have 0 values in the C-Z row

b. Non-basic variables
a. are variables with zero solution values
b. are variables that are out of the solution
From the above example n=5 variables (x1, x2, s1, s2, and s3) and m=3 constraints (assembly,
inspection and storage space constraints), excluding non-negativity.
Therefore, n-m=5-3=2 variables (x1 and x2) are set equal to zero in the 1st simplex tableau.
These are non-basic variables. 3 Variables (s1, s2, and s3) are basic variables (in the 1st simplex
tableau) because they have non-zero solution values.
Step 3
Construct the initial simplex tableau

Initial simplex tableau

Slack variables
variables column
Real or decision

columns

Solution quantity
Profit per unit
Basic or DV
column

column

column
Profit per unit row

C 60 50 0 0 0

BV X1 X2 S1 S2 Q
S3
Constraint
S1 0 4 10 1 0 0 100 R1 equation rows

S2 0 2 1 0 10 22 R2
Gross Profit row
S3 0 3 3 0 0 39 R3
1 Net Profit row
/Indicator row/
Z 0 0 0 0 0
C-Z 0

60 50 0 0

23
 OR Module

Step 4: Choose the “incoming” or “entering” variables

Note: The entering variable is the variable that has the most (the largest) positive value in the
C – Z row (indicator row).
Note:
The entering variable is the variable that has the highest contribution to profit per unit.
X1 in our case is the entering variable. (Because the maximum number in the c-z row is 60).
The column associated with the entering variable is called key or pivot column X1 column in our case.

Step 5: Choose the “leaving “or “outgoing “variable and the “pivot element”
In this step, we determine the variable that will leave the solution for X1.
To identify the leaving variable, we should calculate the ratio first and then we should select
the minimum non negative ratio.

Note:
The leaving variable is the variable that has the smallest replacement ratio.
S2 in our case is the leaving variable. (Because the smallest replacement ratio is 11
The row associated with the entering variable is called key or pivot row S2row in our case.

The pivot element is the intersection point between the pivot row and pivot column; No 2 in
the above example
Replacement Ratio (RR) = Solution Quantité (Q)
Corresponding values in pivot column
In our case
100 / 4 =25

22/2= 11 is the minimum

39 /3 =13

It is interesting to note that the three ratios (25, 11, 13) corresponding to the intersections of
the constraints with the x1(look the graphical solution). Note that the smallest of the ratios
represents the extreme point of the feasible solution space; the other points lie beyond the
feasible solution space. Hence by selecting the smallest ratio, the simplex procedure stays
within the feasible solution space. It sometimes happens that some of the substation rates for

24
OR Module

the variable we want to bring into solution are zero or negative. We don’t need to divide the
quantity values by a negative or a zero substitution rates.

? Activity
Briefly describe the following points:
1. Leaving variable
2. Entering variable
3. Pivot element

 
Comment:
The entering variable is the variable that has the highest contribution to profit per unit
 X1 in our case is the entering variable. (Because the maximum number in the c-z row is 60)
 The variable leaving the solution is called leaving variable or outgoing variable.
Step 6:The
Perform row operations:
row associated perform
with the leaving algebraic
variable is called operations
key or pivot on
rowthe PIVOTinCOLUMN
(s2 column our case) to
 The
convert theelement that lies at
pivot element the 1intersection
into of the pivotpivot
and the remaining column and pivot
column row is called
numbers pivot
into 0. element
Obtain the(No 2in
ourvalues
new row case) through the following two operations:

 Multiply (divide) all of the elements in a row by a constant

 Add or subtract the multiple of the row to or from another row
After identifying the entering, leaving and pivot element construct the second tableau by
replacing the S2 by X1 in the basic solution.
2nd tableau

C 60 50 0 0 0

SV X1 X2 S1S2 S3 Q RR

S1 0 0 8 1 -2 0 56 56/8=7 R’1=R1+ (-4R’2)

X1 60 1 1/2 0 1/2 0 11 11/1/2=22 R’2=R2/2

S3 0 0 3/2 0 -3/2 1 6 6/3/2=4 R’3=R3+ (-3R’2)

Z 60 30 0 30 0 660
C-Z 0 20 0 -30 0

Note the following to see how it is calculated

25
OR Module

Since the minimum replacement ratio (RR) is associated with the 2nd row we should start the
operation on the second row i.e. we should change the pivot element into 1. To do so we
should divide the whole elements of the 2nd row by the pivot element of the first tableau.
Look
2 1 0 1 0 22 when we divide it by 2 we get 1 ½ 0 ½ 0 11 so this will be
the new row values of the second tableau.
Then calculate the new values of the first row and the third row of the second tableau. You
can begin in ether row one or row three.
Let’s start with the first row
Bring the first row values of the initial tableau
4 10 1 0 0 100
The take the second row values of the 2nd tableau
1 ½ 0 ½ 0 11
Then in order to change 4 into 0, ask yourself what algebraic operation should be done. Very
simple, multiply the whole elements of the second tableau’s value by -4.
You get
-4 -20 -2 0 -44, then add this value to the first row value of initial tableau.
Look the summary
4 10 1 0 0 100 4 10 1 0 0 100 4 10 1 0 0 100
1 ½ 0 ½ 0 11 -4( 1 ½ 0 ½ 0 11) + -4 -2 0 -2 0 -44
0 8 1 -2 0 56
will be the new values of the first row of the second tableau. To put it in a simple formula
R’1=R1 + (-4R’2)
Similarly calculate for row three of the second tableau
3 3 0 0 1 39 3 3 0 0 1 39 3 3 0 0 1 39
1 ½ 0 ½ 0 11 -3( 1 ½ 0 ½ 0 11) + -3 -3/2 0 -3/2 0 -33
0 3/2 0 -3/2 1
6will be the new values of the 3rd row value of the second tableau. To put it in a simple
formula again it will be:
R’3=R3 + (-3R’2)

Note:
 Divide each element of the pivot row by the pivot element to find new values in the key or pivot row.
26
 Perform row operations to make all other entries for the pivot column equal to zero.
OR Module

Then calculate the Z row values i.e. these are found by multiplying the values in each column
by the corresponding coefficients in the C column and adding them.

BV C X1 x2 s1 s2 s3 Q

S1 0 0(0 ) =0 0 (8 )=0 0 (1)=0 0(-2 ) =0 0(56)=0

0(0)=0
X1 60 60(11)=66
60(1 )=6060 (1/2) =30 60( 0 )=0 60(1/2)=30 60 0
S3 0 (0)=0
0(6)= 0
0(0 )= 0 0(3/2) =0 0( 0 )=0 0(-3/2)=0
0( 1)=0

Z 60 30 0 30 660
0

Then finally calculate C – Z row. It is simple follow the formula.

Step 7: Repeat step 4-6 till optimum basic feasible solution is obtained. I.e. repeat these steps
till no positive value occurs in the C – Z row.

A simplex solution in a maximization problem is optimal when the C-Z row consists entirely
zeros and negative No (when there are no positive values in the C-Z row.

3rd simplex tableau

BV C 60 50 0 0 0 Q

X1 X2 S1 S2 S3

S1 0 0 0 1 6 - 24

27
OR Module

16/3

X1 60 1 0 0 1 - 9
1/3 R’’1=R’1+ (-8R’3)
X2 50 0 1 0 -1 2/3 4 R’’2=R’2+ (-1/2R’3)
R’’3=R’3/3/2
Z 60 50 0 10 740
C-Z 40/3

0 0 0 -10
- 40/3 Since the
entire C –Z< 0
indicating that no additional potential for improvement exists. I.e. Optimal solution is
reached at.
Therefore, the optimal solution isX1=9, X2=4, S1=24and Max Z=740
Interpretation of the Results:
The last step is interpreting the result: in order to achieve the maximum weekly profit of birr
740, the company should produce 9 units of microcomputer type one and 4 units of
microcomputer type two. This will leave no slack in either inspection (s2=0) or storage space
(s3 =0). However, there will be 24 hours of assembly time that is unused.
Maximization with Mixed Constraints:
In the previous section, you have learned how to solve a maximization problem with all
<constraints. Here you will learn how to solve a maximization problem with mixed
constraints (<> =). For the most, part the technique is identical to that illustrated in the
previous section. What is new is the introduction of the –M coefficients in the objective
functions and the use of artificial variables.
Example1:
Max Z=6x1 +8x2
Subject to:
x2 < 4
x1+ x2 = 9
6x1+ 2x2 >24
x1, x2> 0

28
OR Module

Standard form
To standardize the model what we have learned in the previous example is not enough. Here
the model consists <, >&= sign constraints which demands their unique standardization
approach. For < constraint you know it already we add a slack variable. For the remaining
two consider the following two variables.
1. Surplus variables (S): refers to the excess utilization of resources
 A variable inserted in a greater than constraint to create equality. It represents
the amount of resource usage above the minimum required level.
 Surplus variable is subtracted from a > constraint in the process of converting
the constraint to standard form.
Neither the slack nor the surplus should be negative value in the initial tableau. They must
have a positive value. Look the following
1. 5x1+3x2+ S1 < 45
x1= 0 and x2= 0==>s1 = 45
==>s1=45unused resource (all resources are idle)
2. 2x1+x2 >40
x1= 0 and x2= 0(No production) ==>5x1+2x2- s1= 20
==>s1=-6(This is mathematically unaccepted)
To avoid these problem another variable is inserted which is known as an Artificial variable
(A)
Artificial variable: is a variable that has no meaning in a physical sense but acts as a tool to
create an initial feasible LP solution. It helps to make the model logical and meaningful.
It is added to constraints having = and > algebraic sign.
Has a coefficient of [-M] in the objective function for maximization type problem? It
represents an artificial very large negative value.
Consider the above example
2x1+x2 >40
x1= 0 and x2= 0(No production) ==>5x1+2x2- s1= 20
s1=-6(This is mathematically unacceptable, because it violates the non-negativity
assumptions of LPPM)

29
OR Module

 5x1+2x2- s1= 20
 5x1+2x2- s1 + A1= 20
 So when we set x1,x2 and s1 = 0
 The basic solution in the initial solution will be A1= 20 which is mathematically
correct.
Let’s consider another example having = sign
5x1 +9x2=30
To determine the values of the basic variables for the initial tableau, we set x1& x2=0
5x1 +9x2=30 ==> 5(0) +9(0) =30
==> 0=30 which is mathematically wrong. To avoid this problem, we add an artificial
variable to standardize constraints with = sign.
5x1 +9x2=30 ==> 5x1 +9x2+ s1=30 ==> 5(0) +9(0 +s1) =30
==>S1=30 which is logical.
Note:
For the initial basis, use artificial variables for constraints that have >and = sign. For a
<constraint use a slack variable. Hence, surplus variables will not appear in an initial
solution.
Now based on the above logic when we standardize the above problem
Max Z=6x1 +8x2 + 0 s1 +0 s2+ 0 s3-M A2- M A3
St:
x2+ s1 =4
x1+ x2+ A2 =9 Standard form
6x1+2x2 - s3 + A3 =24
All Variables > 0

30
OR Module

Initial simplex tableau

B C 8 0 0 -M
-M Since

X1 X2 S1 S3 A2 Q RR 7m+ 6

A3 is the
largest,
S1 0 0 1 1 0 0 4 4/0=und.
x1 will
0
be the
A2 -M 1 1 0 0 1 9 9
enterin
0
g
A3 - 6 2 0 -1 0 24 4 variabl
M 1 e for
Z -7M -3M 0 +M -M -33M the
C-Z -M next

7M +6 3M+8 0 -M 0 tableau.

0 Since
an
artificial value (A3) leaves the solution it will removed from the next table, so A3 column will
not exist in the 2nd tableau

2nd tableau

B C 6 8 0 0 -M

X1 X2 S1 S3 Q RR
A2

S1 0 0 1 1 0 0 4 4

A2 -M 0 2/3 0 1/6 1 5 27/2

A3 6 1 1/3 0 -1/6 0 4 12

31
OR Module

Z 6 2-3/3M 0 -1-1/6M -M 24-5M

C-Z 3rd
0 6+2/3M 0 1+1/6M 0
table
au

BV 6 8 0 0 -M
C X1 X2S1 S3 A2 Q RR

X2 8 0 1 1 0 0 4 und

A2 -M 0 0 2/3 1/6 1 7/3 14

A3 6 1 0 1/3 -1/6 0 8/3 Neg.

Z 68 6+2/3m -1-1/6M M 48-7/3M

C-Z 00 -6-2/3m 1+1/6M 0

Final tableau

BV C 6 8 0 Q
0

X1 X2S1 S3

X2 8 0 1 1 4
0

S3 0 0 0 -4 14
1

A3 6 1 0 -1 5
0

Z 68 2 0 62
C-Z 00 2 0

Since the C - Z< 0==>optimal solution

X1=3, X2 =2, X3=0, S1=0 and Max Z= 8

32
OR Module

Minimization Problems
For most part, manual solution of minimization problems using simplex are handled in the
same fashion as maximization problems with mixed constraints. The two exceptions are:
 The M coefficients in the objective function are given positive signs instead of
negative signs
 The selection of the variable to enter the solution is based on the largest negative value
(the negative number far from 0) in the C-Z row of a tableau.
 Solution is optimal when there is no negative value of C-Z.

Note:
TYPE OF CONSTRAINT TO PUT INTO STANDARD FORM
< ----------------------------------------Add a slack variable
= -----------------------------------------Add an artificial variable
> ---------------------- Subtract a surplus variable and add an artificial variable

Example:
1. Minimize Z=25x1 +30x2
Subject to:
20x1+15x2 > 100
2x1+ 3x2 > 15
X1& x2> 0
Solution
Step 1
Standardize the problem:
Minimize Z=25x1 +30x2 +0s1+0s2 +MA1+MA2
Subject to:
20x1+15x2- s1+A1 = 100
2x1+ 3x2 –s2+A2 = 15
x1, x2, s1, s2, A1, A2 > 0
Step 2
Initial simplex tableau:
The initial basic feasible solution is obtained by setting x1= x2= s1= s2=0

33
OR Module

No production, x1= x2= s1=0==>20(0) +15(0) - 0+A1 = 100 ==> A1 = 100

x1= x2= s2=0==>0(0)+3(0) - 0+A2 =15==> A2 = 15
Initial simplex tableau

B C 25 30 0 0 M Q
M RR
X1 X2 S1 S2 A1
100/20=5
A2
15/2=7.5
A1 M 20 15 -1 0 1 100
0

A2 M 2 3 0 -1 0 15
1

Z 22M 18M -MM M M 115 M

C-Z 25 -22M 30- 18MMM 0 0

Note:
Once an artificial variable has left the basis, it has served its purpose and can therefore be
removed from the simplex tableau. An artificial variable is never considered for re-entry into
the basis.
2nd Simplex Tableau

B C 25 30 0 0 Q
M

X1 X2 S1 S2
A2

X1 25 1 ¾ -1/20 0 5
0

A2 M 0 3/2 1/10 -1 1 5

Z 25 75/4+3/2M -5/4+1/10M M 125+5 M

34
OR Module

C-Z M

0 45/4-3/2M 5/4-1/10 MM 0
R’1=R1/20

R’2=R2-2 R’

3rd Simplex Tableau

B C 25 30 0 0 Q

X1 X2 S1 S2

X1 25 1 0 -1/10 1/2 5/2

X2 30 0 1 1/15 -2/3 10/3

Z 25 30 -1/2 - 162.5
C-Z 15/2

0 0 1/2
15/2

C - Z> 0==>Optimal solution is reached

X1=5/2
X2=10/3 and Min Z=162.5

35
OR Module

X1=4, X 2=1, S1=0, S2=12 and MinZ=23

Note:
To get an initial feasible solution
Types of constraint Presence of variables in the initial solution mix
1. < (Slack) Yes
2. > *(Surplus) No
*(Artificial) Yes
3. = (Artificial) Yes

? Activity
What are the special cases in simplex methods? Please try in the given space.
_________________________________________________________________________
_________________________________________________________________________
_________________________________________________________________________
___________________________________

 Comment:
The special cases are: Tie, Infeasibility, Unbounded solution, Degeneracy, Multiple optimal
solutions

2.7 SPECIAL CASES IN SIMPLEX METHOD

I. Two incoming variables / or Tie for entering variables/

In order to break this tie, the selection for the key column (entering variable) can be made
arbitrary. However; the number of solution can be minimized by adopting the following rules:
1. If there is a tie between two decision variables, then the selection can be made arbitrary.
2. If there is a tie between a decision variable and a slack (or surplus) variable, then select
the decision variable to enter into basis first.
3. If there is a tie between slack or surplus variable, then selection can be made arbitrary.
Example:
If the equation is max Z:

36
OR Module

B Q
C X1 X2 S1 S3

Z
C- Z 5 5 2 0

In such a case, X1 is the entering variable

II. Infeasibility
A situation with no feasible solution may exist if the problem was formulated improperly.
Infeasibility comes about when there is no solution that satisfies all of the problem’s
constraints.
In the simplex method, an infeasible solution is indicated by looking at the final tableau .In it,
all C – Z row entries will be the proper sign to imply optimality, but an artificial variable (A)
will still be in the solution mix.
Example:
Minimization case

B C 5 8 0 0 Q
M

X1 X2 S1 S2
A2

X1 5 1 1 -2 3 200
0

X2 8 0 1 1 2 100
0

A2 M 0 0 0 -1 20
1

Z 5 8 -2 31-M 1,800+200M

37
OR Module

C-Z M

0 0 2 M-31
0

Even though all C - Z are positive and 0(i.e. the criterion for an optimal solution in a
minimization case), no feasible solution is possible because an artificial variable (A2)
remains in the solution mix.
III. Unbounded Solutions
No finite solution may exist in problems that are not bounded. This means that a variable can
be infinitely large without violating a constraint.

In the simplex method, the condition of unbounded ness will be discovered prior to reaching
the final tableau. We will note the problem when trying to decide which variable to remove
from the solution mix.

The procedure in simplex solution is to divide each quantity column number by the
corresponding pivot column number to identify the leaving variable. The row with the
smallest positive ratio is replaced. But if the entire ratios turn out to be negative or undefined,
it indicates that the problem is unbounded.
Example:
Maximization case

B C 5 9 0 Q
0

X1 X2 S1
S2

X2 5 -1 1 2 30
0

S2 0 -2 0 -1 10

38
OR Module

Z -9 9 18 270
C-Z 0 RR

15 0 -18 30/-1=-30
UnacceptableRRs
0
10/-2=-5

The solution in the above case is not optimal because not all C- Z entries are 0 or negative, as
required in a maximization problem. The next variable to enter the solution should be X1. To
determine which variable will leave the solution, we examine the ratios of the quantity
column numbers to their corresponding numbers in the X1or pivot column. Since both pivot
column numbers are negative, an unbounded solution is indicated.

IV. Degeneracy/Tie for leaving basic variable (key row)/

If there is a tie for the smallest ratio, this is a signal that degeneracy exists. Degeneracy can
occur right in the first (initial tableau). This normally happens when the number of constraints
is less than the number of variables in the objective function.

39
OR Module

B 5 8 2 0 0 Q
C 0
RR
X1 X2 X3 S1 S2
10/1/4=40
S3
20/4=5Tie for the smallest
X2 8 1/4 1 1 -2 0 10 ratio indicates deg.
10/2=5
0

S2 0 4 0 1/3 -1 1 20
0

S3 0 2 0 2 2/5 0 10
1

Z 2 8 8 16 0 80
C-Z 0

3 0 -6 -16 0
0
Problem can be overcome by trial and error method.
Degeneracy could lead to a situation known as cycling,
in which the simplex algorithm alternatives back and forth between the same non-optimal
solutions, i.e., it puts a new variable in, then takes it out in the next tableau, puts it back in,
and so on.
One simple way of dealing with the issue is to select either row (S2 or S3 in this case)
arbitrary. If we are unlucky and cycling does occur, we simply go back and select the other
row.
Remark
When there is a tie between a slack and artificial variable to leave the basis, the preference
shall be given to artificial variable to leave the basis and there is no need to apply the
procedure for resolving such cases.

V. Multiple Optimal Solutions

Multiple optimal solutions exist when non-basic variable contains zero on its C – Z row.

40
OR Module

Example:
Maximization problem

B C 3 2 0 Q
0

X1 X2 S1
S2

X2 2 3/2 1 1 0 6

S2 0 1 0 1/2 1 3

Z 3 2 2 12
C-Z 0 Max Z=3X1+2X2

0 0 -2 X1=0, X2=6, S2=3 and Max Z=12

0 or: X1=3, X2=3/2 and Max Z=12

The C –Z value of the Non-basic variable (X1) is 0. Thus, there is alternative optimal solution.

41
OR Module

UNIT THREE

3. TRANSPORTATION AND ASSIGNMENT MODELS

3.1. INTRODUCTION

One important application of linear programming has been in the area of the physical
distribution (transportation) of resources, from one place to another, to meet a specific set of
requirement.
This chapter describes two special –purpose algorithms: the transportation model and the
assignment model. Model formulation and manual solution are covered for each of these
classes of problems.

?
3.2. TRANSPORTATION PROBLEMS
Activity
What is the purpose of transportation problem model?
________________________________

 Comment:
Transportation problem deals with the distribution of goods from several points of supplies
(sources) to a number of points of demands (destinations) with a minimum cost of
transportation

Transportation problem deals with the distribution of goods from several points of supplies
(sources) to a number of points of demands (destinations).
Objective of the model: is to identify a distribution plan that would minimize the cost of
transporting the goods from the supply areas to the demand areas taking into account supply
capacities and demand requirements as well as transportation costs.
Application areas: we can use transportation model for various types of problems. For
example:
 Shipments from factories to warehouses
 Shipments between departments within a company
 To compare location alternative
 Production scheduling etc.
Necessary conditions for the model:

42
OR Module

A transportation problem typically involves a set of sending locations which are referred to as
origins (supply areas) and a set of receiving locations which are referred to as destinations
(demand areas). In order to develop a model of a transportation problem it is necessary to
have the following information:
1. Supply quantity (capacity) of each origin
2. Demand quantity of each destination
3. Unit transportation cost for each origin- destination route
Assumptions:
1. All goods be homogeneous
2. Transportation costs are a direct linear function of the quantity shipped over any route
3. The total quantity available for shipment is equal to the total quantity demanded
The characteristics of transportation problem are as follows:
1. A limited supply of one commodity is available at certain sources or origins.
2. There is a demand for the commodity at several destinations
3. The quantities of supply at each source and the demand at each destination are constant.
4. The shipping or transportation costs per unit from each source to each destination are
assumed to be constant.
5. No shipments are allowed between sources or between destinations. All supply and demand
quantities are given in whole number or integers.
6. The problem is to determine how many units shipped from each source to each destination
so that all demands are satisfied at the minimum total shipping costs.
Example:
Let’s consider that a firm has three factories /sources of supply/ & four warehouses/point of
demand/. The firm's production capacity at the three factories, the demand for the four
distribution centers located at various regions & the cost of shipping each unit from the
factories to the warehouses through each route is given as follows:

43
OR Module

Factories Weekly capacity

F1 5000
F2 6000
F3 2500

Warehouse Demand
W1 6000
W2 4000
W3 2000
W4 1500

Cost per unit to

FromW1 W2 W3 W4

F1 3 2 7 6
F2 7 5 2 3
F3 2 5 4 5
Solution
The solution algorithm to a transportation problem is summarized into the following steps:
Step 1:
Formulate the transportation table: set up a transportation table with M- rows representing
the number of supply areas and N- columns representing the number of demand areas.
The formulation of the problem is similar to the linear programming. Here the objective
function is to minimize the total transportation cost and the constraints are the supply and
demand available at each source and destination respectively. The origins are listed down the
left side of the table, and the respective supply quantities are listed down the right side of the
table.
Step 2: Obtain an initial basic feasible solution:
For this there are 3 methods to find the initial feasible solution.
I. North-West Corner Method (NWCM)

44
OR Module

II. Least Cost Method (LCM)

III. Vogel’s Approximation Method (VAM)
The initial solution obtained by any of the above three methods must satisfy the following
condition:
The solution must be feasible: i.e. it must satisfy all the supply and demand constraints
The number of positive allocations must equal to m+n-1, where=the number of rows (or
origins or supply centers) and n= the number of columns (or destination centers or demand
centers)
Example:
M=3 origins and N=4 destinations ==>M+N-1=3+4 -1=6 (i.e. the transportation model should
have 6 occupied cells). If the number of occupied cells < m+n-1==>degenerate solution
you will see it in special issue of a transportation problem.
Step 3:
Test the initial solution for optimality: If the current solution is optimal, then stop.
Otherwise, determine the new improved solution.
For this there two methods to find the optimal solution
1. Stepping stone methods
2. Modified distribution method(MODI)
Step 4:
Repeat step 3 until an optimal solution is reached
Now based on the above logic lets solve the problem.
3.3.1 TRNSPORTATION TABLE
Summarize all the given information in the tabular form as follows.

45
OR Module

Destinations (dd) =j

Origin W1 W2 W3 W4 Factory
(Supply) Capacity
=i

F1 3 2 7 6 5000

F2 6000
7 5 2 3
F3 2 5 4 5 2500

Requirements of 6000 4000 2000 1500 13500

the
Warehouses
( Units of
demand)

Note that we can solve the problem using LPPM, because transportation problem is a special
type of LPPM. So we can change the above problem into LPPM as follows:
Let xij =The amount of commodity to be transported form source i (i =1,2,3 ) to destination j(
j= 1,2,3,4).
Then the objective function of the problem (minimization of the total transportation cost) can
be formulated as:
MinZ = 3x11 +2x12 + 7x13 +6 x14 +7x21 +5x22 +2x23 + 3x24 +2x31+5x32 +4x33+5x34
Subject to the constraints
a. Supply constraints:
x11 +x12 +x13 +x 14 =5000 F1 supply constraint
x21 + x22 + x23 +x24 =6000F2 supply constraint
x31 +x32 +x33+x34 = 2500F3supply constraint
b. demand constraints:
x11 + x21 + x31 = 6000 W1 demand constraint
x12 + x22 + x32 = 4000 W2demand constraint

46
OR Module

x13 + x23 +x33 = 2000 W3 demand constraint

x14 +x24 + x34 = 1500 W4 demand constraint
xij > 0 for all i& j
In the above LPP, there are m x n = 3x4 =12 decision variables & m + n = 3+4 =7 constraints.
Thus, if this problem is solved by the simplex method, then it may take considerable
computational time.
To conceptualize the problem easily let’s represent of the problem using a Net work flow
diagram
The objective is to identify the minimum cost route (Least cost route). From these routes
which rout results the minimum total transportation cost. Using Try and error is very tiresome
and inefficient. But by using the transportation problem models you can identify the routes
easily.
METHODS OF FINDING INITIAL FEASIBLE SOLUTION
There are several methods available to obtain an initial feasible solution. Here we shall
discuss only three different methods to obtain the initial feasible solution:
A. North- West Corner Method (NWCM)
This method does not take into account the cost of transportation on any route of
transportation.
The NWCM gets its name because the starting point for the allocation process is the Upper
Left-hand (Northwest) corner of the transportation table. Therefore, allocate to the Northwest
corner as many units as possible.
Northwest corner rule:
The following set of principles guides the allocation:
1. Begin with the upper left hand cell (Left, upper most in the table), & allocate as many
units as possible to that cell. This will be the smaller amount of either the row supply or
the column demand. Adjust the row & column quantities to reflect the allocation.
2. Subtract from the row supply & from the column demand the amount allocated
3. If the column demand is zero, move to the cell next to the right, if the row supply is zero,
move down to the cell in the next row.
If both are zero, move first to the next cell on the right then down one cell.

47
 OR Module

4. Once a cell is identified as per step (3), it becomes a northwest cell. Allocate to it an amount
as per step (1)
5. Repeat, the above steps (1) - (4) until all the remaining supply and demand is gone.

Example:

T Store 1 Store Store Store 4 Supply

F 2 3

Plant 1 19 30 50 10 7

Plant 2 70 30 40 60 9
Plant 3 40 8 70 20 18

Demand 5 8 7 14 34

1) Consider the following transportation problem:

Required:
a. Develop an initial feasible solution using the NWCM
b. Compute the total cost for this solution.

? Activity
Using the above rules try to find the transportation schedule using NWCM in a piece of paper and
check your answer, before you read the solution.

Solution

48
OR Module

a. Table: Initial feasible solution

To Store 1 Store 2 Store 3 Store 4 Supply

Check that the solution

From
is feasible or no
Plant 1 19 30 50 10 7
t:
5 2
==>m + n-1; m=3 and
Plant 2 70 30 40 60 9
n=4  3+4-1= 6 cells
6 3
Plant 3 40 8 70 20 18 occupied (Feasible
4 14 solution)
Demand 5 8 7 14 34
The total transportation
cost of the initial feasible solution derived by the NWCM is:

Route Unit Per unit Total

FromTo Shipped cost ( $) = Cost ( $)

Plant 1 Store 1 5 19 95
plant 1 Store 2 2 30 60
Plant 2 Store 3 6 30 180
Plant 2 Store 4 3 40 120
Plant 3 Store 4 4 70 280
Plant 3 Store 4 14 20 280

Total Cost= $ 1015

Note: NWCM does not consider the cost factor for allocation.
Example 2
1. Determine an initial basic feasible solution to the following transportation problem using
NWCM and Compute the total cost for this solution
Destination

49
OR Module

A B C Supply

S1 2 7 14 5

S2 3 3 1 8

S3 5 4 7 7

S4 1 6 2 14

Demand 7 9 18 34

Answer: X11=5, X21=2, X22=6, X32=3, X33=4, X43=4, and Total cost =$10

B. The Least- Cost Method (LCM)

LCM: is the method that uses a minimum cost in the allocation.

It begins a solution by sequentially assigning to the cells with the minimum cost as many
units as possible. The first allocation is made to the cell with the lowest cost.
The Least- Cost Method yields not only an initial feasible solution but also one that is close to
optimal in small problems.

? Activity
What is the difference between NWCM and LCM?
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________


Example
Comment:
NWCM: we don’t use cost for allocation it uses direction (North West as base for allocation)
LCM: uses minimum transportation as base for allocation

[Link] that a firm has three factories / sources of supply /& four warehouses/point of
demand/. The firm's production capacity at the three factories, the demand for the four
destination centers located at various regions & the cost of shipping each unit from the
factories to the warehouses through each route is given as follows:

50
 OR Module

Destinations

W1 W2 W3 W4 Factory
Capacity
F1 3 2 7 6 5000

F2 7 5 2 3 6000

F3 2 5 4 5 2500

Demand 6000 4000 2000 1500 13500

Required:
a. Develop an initial feasible solution using NWCM & Compute the total cost
b. Develop an initial feasible solution using least-cost method & compute the total cost.
Solution:
a. Initial feasible solution using NWCM

W1 W2 W3 W4 Factory
Capacity

F1 3 2 7 6 5000
Factory 5000

F2 7 5 2 3 6000
1000 4000 1000
F3 2 5 4 5 2500
1000 1500

Demand 6000 4000 2000 1500 13500

m= 3, n =4 ==> 3+4 -1 =6 occupied cells (Feasible)

Initial feasible solution using LCM

W1 W2 W3 W4 Factory
Capacity

F1 3 2 7 6 5000

51
OR Module

F2 7 5 2 3 6000

F3 2 5 4 5 2500
2500

Demand 6000 4000 2000 1500 13500

Routes Units Unit Total

FromTo Shipped X Cost =Cost
F1 W1 1000 3 $ 3000
F1 4000 2 8000
W2 2500 7 17500
F2 W1 2000 2 4000
F2 W3 1500 3 45000
F2 2500 2 5000
W4
F3W1

Total transportation cost =$42,000

m= 3, n=4 ==> 3+4-1 =6 occupied calls (Feasible)

Least- Cost method is better than the NWCM because it considers cost factories.

? Activity
Solve problems that are solved by NWCM using LCM & vise-versa. What differences
you observe between NWCM and LCM. Which method is preferable? Why?
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
_______________________________________________________________________

 Comment:
[Link] total Approximation
Vogel's cost of transportation is the
Method minimum
(VAM) in LCMMethod
or Penalty as compared to NWCM. LCM is
preferable because it minimizes the steps to reach the optimal solution.

52
OR Module

VAM is preferred to the other two methods described above. In this method each allocation is
made on the basis of the opportunity (or penalty or extra) cost that would have incurred if
allocation in certain cells with minimum unit transportation cost were missed.

In this method allocation are made so that the penalty cost is minimized. The advantage of
this method is that it gives an initial solution which is nearer to an optimal solution or is the
optimal solution itself.
VAM determines the penalty for not using the minimum cost routes, where the objective is
to avoid large penalties so that the penalty from not using the routes is minimized.

The steps in VAM are as follows:

1. Calculate penalties for each row (column) by taking the smallest & the next smallest unit
transportation cost in the same row (column). This difference indicates the penalty or extra
cost which has to be paid if one fails to allocate to the cell with the minimum unit
transportation cost
2. Select the row or column with the largest penalty & allocate as much unit as possible in the
cell having the least cost in the selected row or column satisfying the conditions. If there is
a tie in the values of penalties, then t can be broken by selecting the cell where maximum
allocation can be made.
3. Adjust the supply & demand & cross out the satisfied row or column. If a row or column is
satisfied simultaneously, only one of them is crossed out & the remaining row (column) is
assigned a zero supply (demand). Any row or column with zero supply or demand should
not be used in computing future penalties.
4. Repeat step 1 to 3 until the entire available supply at various sources & demand at various
destinations are satisfied.

Example:
1. Determine an initial basic feasible solution to the following transportation
problem using VAM.
Warehouse

53
 OR Module

A B C D Supply

Factory F1 2 2 0 4 25 Row difference or Row penalty

or opportunity cost
5 20
2 0 - - -
F2 5 9 8 3 25
2 2 2 2 5
15 5 5

F3 6 4 3 2 10 1 2 2 - -

10

Demand 20 15 20 5 60

Column difference 3 2 3 1
or Column penalty
or opportunity cost 3 2 - 1

1 5 - 1

5 9 - -
m= 3, n=4 ==> 3+4-1
5
=6
-
Occupied
-
cells
-
(feasible)
The transportation cost associated with this solution is:
Total cost= 5x2 + 20x0+15x5x9 =+95x3+10x4= $185

? Activity
What is the base for allocation in VAM?
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
_______________________________________________________________________

 Comment:
VAM uses penalty cost as a base for allocation

OPTIMALITY TESTS

54
OR Module

The purpose of the optimality test is to see if the proposed solution just generated can be
improved or not. The solution to be checked for optimality must be non-degenerate i.e. The no
of occupied cells must be >m+n-1.

The Procedure for testing optimality is analogous to that of the simplex method. A distinction
is made between basic variables, those associated with occupied cells & non-basic variables,
those associated with the empty cells.

For each empty cell, the effect of changing it to an occupied cell is examined. If any of these
changes are favorable, the solution is not optimal & a new solution must be designed.
Optimum solution to a TP can be obtained by following two methods. These methods are
much simpler compared to simplex method of an LPP.
A. Stepping stone Method
B. Modified Distribution method (MODI Method)
A. Stepping-stone method
The Stepping-stone method is an iterative technique for moving from an initial feasible
solution to an optimal solution in transportation problems.

For the stepping- stone method to be applied to a transportation problem, one rule about the
no of shipping routes being used must be observed. The rule is:

“The No of occupied routes (or squares) must always be equal or greater than to one less
than the sum of the no of rows plus the no of columns."i.e. Occupied shipping routes
(squares) >No of rows + No of columns - Non degenerate solution.
Rules for drawing each closed loop:
1. Select an unused square (cell) to be evaluates.
[Link] at this cell, trace a closed loop going clockwise draw an arrow to an occupied
cell in the same row (or column).
3. Move vertically or horizontally (but never diagonally) to another occupied cell “stepping
–over” unoccupied or occupied cells (if necessary) without changing them. Follow the
same procedure to other occupied cells until returning to the original empty cell.

55
OR Module

4. Begin with a plus (+) sign at the unused cell, place alternative (-) signs and plus signs on
each corner square of the closed path just traced. I.e. At each turn of the loop (the loop
may cross over itself at times), plus and minus signs are alternately placed in the cells,
starting with a +sign in an empty cell.
5. There must be exactly one cell with a + sign and exactly one cell with a - sign in any row
or column in which the loop turns.
6. An even no of at least four cells must participate in a loop and the occupied cells can be
visited once and only once.
7. Repeat steps 1 to 4 until an improvement index has been calculated for all unused squares
(cells). If all indices computed are greater than or equal to zero, an optimal solution has
been reached. If not, it is possible to improve the current solution and decrease total
shipping costs.
Note:
In a non-degenerate problem, there is only one possible way of drawing the loop for each
empty cell.
How to find the value of a cell evaluator?
The value of a cell evaluator is the sum of the per unit shipping costs in the gaining cells less
the sum of the per unit shipping costs in the losing cells of the closed loop. This evaluation
process must be extended to all unoccupied cells.
If one or more of the cell evaluators is negative, the existing solution is not optimal. i.e.: For
minimization (cost) problems, all the cell evaluators must be positive for optimality.
 Analysis of test:
Check all the empty cells and select for improvement the one with the largest improvement
potential.
 If the solution is not optimal, the next step in the transportation method is to find a
better solution. The operations in this step are:
a. Identify the “incoming" cell (the empty cell to be occupied) -In a minimization case, the
incoming cell is located by identifying the most negative cell evaluator .

56
OR Module

Project Project Project ss

A B C

F1 4 2 8 100

F2 5 1 9 200

F3 7 6 3 200
Farm

b. Design an improved solution, by

dd 50 150 300 500 shifting units form cell to cell

Example:
1. Use NWCM to find initial feasible solution and test the solution for optimality.

Project Project Project ss

A B C

F1 4 2 8 100
50 50
Project Project Project ss
F2 5 1 9 200
100 100

F3 7 6 3 200
200

dd 50 150 300 500

57
OR Module

A B C
m=3, n=3==> 3+3-1=5(Non-degenerate
F1 4 2 8 100
solution)
50 50 - +
Total transportation cost =
F2 5 1 9 200 $[50x4+50x2+100x1+100x9+200x3] =
100 + 100- $1900
F3 7 6 3 200
200 Evaluation path for the unoccupied cells
Dd 50 150 300 500
Table: Test of optimality

Unoccupied cells Cell evaluators

(F2 ,A) +5-4+2-1=+2

(F1 ,C) +8-9+1-2=-2

(F3 ,A) +7-4+2-1+9-3=+10

(F3 ,B) +6-1+9-3=+11

The negative value for cell (F1, C) indicates an improved solution is possible. For each unit
we can shift into that cell, the total cost will decrease by $2. The next question is how many
units can be reallocated into that cell while retaining the balance of supply and demand for
that table?

The Stepping- stone path for cell(F1, C) is:

The + Signs in the path indicate units to be added, the - signs indicate units to be subtracted.
The limit on subtraction is the smallest quantity in a negative position along the cell path.
There are two quantities in negative positions, 50 and 100. Because 50 is the smaller
quantity, that amount will be shifted in the following manner: Subtract 50 units from each
cell on the path with a - sign and add 50 units to the quantity of each cell with a + sign in it.

With each iteration (new solution), it is necessary to evaluate the empty cells to see if further
improvements is possible.

58
OR Module

The distribution plan after reallocation of 50 units is:

A B C ss

F1 4 2 8 100

F2 50
5 1 50
9 200
150 50
F3 7 6 200
3
dd 50 150 300 500
200

Table: Test of optimality

Unoccupied cells Cell evaluators

(F1 ,B) +2 -8+9-1 =+2

(F2 ,A) +5 -4+8-9 =0

(F3 ,A) +7-4+8-3 =+8

(F3 ,A) +6-1+9-3= +11

Because none of these no is negative, this is an optimal solution. Therefore, the total cost for
the distribution plan is:
The total transportation cost = $ (50x4 +50x8 150x1+50x9 +200x3) = $1,800

B. Modified Distribution Method (MODI Method)

It is another algorithm for finding the optimal solution to a transportation problem.
The MODI method allows us to compute improvement indices quickly for each unused cell
without drawing all of the closed paths. Because of this, it can often provide considerable
time savings over the stepping-stone method for solving transportation problems.

59
OR Module

MODI provides a new means of finding the unused route with the largest negative
improvement index. Once the largest index is identified, we are required to trace only one
closed path. Just as with the stepping-stone approach, this path helps to determine the
maximum No of units that can be shipped via the best unused route.
Steps in the MODI Method
The steps to evaluate unoccupied calls are as follows:
1. For an initial basic feasible solution, calculate Ui and Vj ;for rows and columns
and set

𝐂𝐢𝐣 = 𝐔𝐢 + 𝐕𝐣 for all occupied calls (i ,j)

i.e.: Cell cost= Raw Index+ Column Index

2. For unoccupied cells, calculate opportunity cost by using the relation:

Kij = Cij– Ui- Vj; for all j and j.

I.e. cell cost –row index- column index

3. Examine the sign of each Kij :

i. If Kij> 0, then current basic feasible solution is optimal.
ii. If Kij= 0, then the current basic feasible solution will remain be unaffected
but an alternative solution exists.
iii. If one or more Kij< 0, then an improved solution be obtained entering
unoccupied cell (i, j), in the basis. An unoccupied cell having the largest
negative value of Kij is chosen for entering into the solution mix (new
transportation schedule)
4. Solve the problem as you did using the stepping-stone method.
i.e. construct a closed path (or loop) for the unoccupied cell with largest negative
opportunity cost. Start the close path with the selected unoccupied cell and mark a
plus sign (+) and in this cell, trace a path along the rows (or columns) to an
occupied cell, mark the corner with minus sign (-) and continue down the column
(or row) to an occupied cell and mark the corner with plus sign (+) and minus sign
(-) alternatively. Close the path back to the selected unoccupied call.

60
 OR Module

Locate the smallest quantity allocated to a cell marked with a minus sign. Allocate
this value to the selected unoccupied cell and add it to other occupied cells marked
with plus signs and subtract it from the occupied cells marked with minus signs.

5. Obtain a new improved solution by allocating units to the unoccupied call and
calculate the new transportation cost.

6. Test the revised solution for optimality.

Note:
 Any initial feasible solution will do: NWCM, VAM Solution, or any arbitrary
assignment.
 The stepping- stone method is efficient for small sized transportation problems. For
larger problems, however, the MODI method is recommended.

? Activity
What differences observe between stepping stone and MODI METHOD?
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________


Example:
Comment:
Stepping stone uses closed path to evaluate empty cells
MODI uses row index and column index values to evaluate the empty cells

61
 OR Module

[Link] an optimal solution to the transportation problem by MODI method given below:

Project Proje Proje Supp

N o
Farm 4 1 ct
2 ct
8 ly
100
1 No 2 No 3

Farm 5 1 9 200
2

Farm 7 6 3 200
DD
3 50 150 300 500

Solution
Note:
Both the MODI and the stepping - stone method will yields the same values.
Remark:
Conventionally, we begin by assigning a value of zero as the index for row 1 (U1=0). Once
row index has been established, it will enable us to compute column index numbers for all
occupied cells in that row. Similarly, once a column index number has been determined, index
numbers for all rows corresponding to occupied cells in that column can be determined.

Consider the initial feasible solution of the given example by NWCM as shown below:
Initial solution, NWCM

Project Proje Proje Supp Ui

No 1 ct ct ly
No 2 No 3
Farm 1 4 2 8 100 U1=0
50
50

Farm 2 5 1 9 200 U2=1

100 100

62
 OR Module

Farm 3 7 6 3 200 U3=-

200 7

Demand 150 300 500

50

Vj V1=4 V2=2 V3=1

0

To determine Cij,use the occupied cells.

For instance, C11=4, C12=2, C22=1, C23=9, and C33=3

Cij= Ui + Vj
==>C11= U1 +V1==>4=0+ V1==>V1=4, U1=0 by convention
==>C12= U1 +V2==>2=0 +V2==>V1=2
==>C22= U2 +V2==>1= U2+ 0==>U2=-1
==>C23= U2 +V3==>9= -1+V3==>V3=10
==>C33= U3 +V3==>3= U3+10 ==>U3= -7

63
OR Module

Note :
Cij≠ Ui + Vj (For unoccupied cells)
For instance,from the above information, C32 ≠ U3 + V2==>6≠-7+2
Table: Test of optimality

Unoccupied cells Cell evaluators

Kij = Cij– Ui- Vj

(1,3) C13 –U1 -V3=8-0-10= -2

(2,1) C21 –U2 -1=5+1-4=+2
(3,1) C31–U3 -V1=7+7-4=10
(3,2) C32–U3 -V2=6+7-2=+11

In this case, we found that cell (1, 3) had an evaluation of -2, which represented an
improvement potential of and $ 2 per unit. Hence, an improved solution is possible.
The stepping-stone path for call (1, 3) is:

Projec Projec Project Supply

t t No 3
Farm 4 2 8 100
No 1 No 2
1 50 50

Farm 5 1 9 200
2 100 100

Farm 7 6 3 200
3 200
Dema 150 300 500
nd 50

64
OR Module

The distribution plan after reallocation of 50 units is:

Proj Proje Proje Suppl Ui

Far ect
4 ct
2 ct
8 y
100 U1=0
N o No50 No 3
m1 50 1 2

Far 5 1- 9 + 200 U2=1

m2 + 100 100 -

Far 7 6 3 200 U3=-5

m3 200
Dem 150 300 500
and 50

Vj V1=4 V2=0 V3=

8

Cij= Ui + Vj
==>C11= U1 +V1==>4=0+ V1==>V1=4, U1=0 by convention
==>C13= U1 +V3==>8=0 +V3==>V3=8
==>C23= U2 +V3==>1= U2+ 0==>U2=1
==>C22= U2 +V2==>1= 1+V2==>V2= 0
==>C33= U3 +V3==>3= U3+8 ==>U3= -5
Table: Test of optimality

Unoccupied cells Cell evaluators

Kij = Cij– Ui- Vj

(1,2) C12–U1 -V2=2-0-0= 2

(2,1) C21 –U2 -V1=5-1-4=0
(3,1) C31–U3 -V1=7+5-4=8
(3,2) C32–U3 -V2=6+5-0=+11

Because none of the cell evaluators is negative, this is an optimal solution.

Thus, the total cost for the distribution plan =$1800

65
OR Module

SPECIAL CASES
I. Degeneracy
A condition that occurs when the No of occupied cells in any solutions less than the No of
rows plus the No of columns minus 1 in a transportation table

I.e. No of occupied calls < m+n -1 .....................Degeneracy

If the No of occupied cells = m+n-1, then the solution is non- degenerate.

The degeneracy in the transportation problems may occur at two stages:

1. when obtaining an initial solution
2. During improvement (or at any stage while moving towards optimal solution.
To resolve degeneracy, we processed by allocating a very small quantity close to zero to one
or more unoccupied cell so as to get m+n-1= number of occupied cells. This amount is
denoted by a Greek letter  (epsilon) or (delta). This quantity would not affect the total cost
as well as supply and demand values.
 = Almost zero
II. Alternative Optimal solutions
The existence of alternative optimal solution can be determined by an inspection of the
opportunity costs, 𝑲𝒊𝒋 for the unoccupied cells. If an unoccupied cell in an optimal solution
has opportunity cost of zero, then an alternative optimal solution can be formed with another
set of allocations without increasing the total transportation cost.

III. Prohibited Transportation Routes.

The situation may arise such as road hazards (snow, floods, etc.), traffic regulation, equipment
break down, labor problem etc., when it is not possible to transport goods from certain
sources to certain destinations.
IV. Unequal Demand and Supply

* If total Supply > Total demand, then create a fictitious or artificial destination called dummy
destination i.e.: total Supply > Total demand===>Add dummy column
* But if excess demand (Supply < demand) exists add a dummy source (add a dummy row)

66
OR Module

Note: the cost of “shipments” to the dummy is usually set at zero ==> No real cost

V. Maximization Problem
If you are faced with transportation type problem concerned with profit (revenue). First
change the problem to a minimization type. The steps are:
 Select the largest unit profit from the total cells
 Subtract each cell value from the largest
 Do the same procedure as usual?

ASSIGNMENT PROBLEMS
The Assignment Problem(AP) refers to the class of LPPs that involves determining the most
efficient assignment of people to projects, salespeople to territories, contracts to bidders,
jobs to machines, and so on.
The objective is to assign a number of resources to an equal number of activities so as to
minimize total costs or total time or maximize total profit of allocation.

Assumptions:
The AP is a special case of TP under the condition that the number of origins is equal to the
number of destinations. Viz. m=n. Hence assignment is made on the basis of 1:1relationship.
Following are the assumptions:
 Number of jobs is equal to the number of machines or persons
 Each man or machine is loaded with one and only one job.
 Each man or machine is independently capable of handling any of the jobs being
presented.
 Loading criteria must be clearly specified such as “minimizing operating time” or
“maximizing profit”, or “minimizing production cost” or “minimizing throughout
(production cycle) time” etc.

Remark:
 The AP is considered as a special TP in which the supply at each source and the demand at
each destination are always one unit.

67
 OR Module

 Since the supply and demand are always equal to one unit in each row and column, there is
no need to write them in the assignment table.

Example:
Service costs of different team assignment ($ in thousands

Table: The assignment table

Z Z1 Z2 Z3
Se
====>
20 15 31 Zone
S1 Z1 Z2 Z3
S2 17 16 33 Seri SS

S3 18 19 27 S1 20 15 31 1

S2 17 16 33 1

S3 18 19 27 1

DD 1 1 1

The above problem can be presented as a LPP as follows:

MinZ = 20x11 +15x12 + 31x13 +17x21 +16x22 +33x23 +18x31+19x32 +27x33
Subject to the constraints
a. Supply constraints:
x11 +x12 +x13 =1 S1 constraint
x21 + x22 + x23 =1S2 constraint
x31 +x32 +x33 = 1S3 supply constraint
b. Demand constraints
x11 + x21 + x31 = 1 Z1 contraint
x12 + x22 + x32 = 1Z2 contraint
x13 + x23 +x33 = 1Z3 contraint
xij either 0 or 1for all i , j
Since all xij can be either 0 or 1, there will be one assignment in each supply constraint and
one assignment in each demand constraint.

68
OR Module

? Activity
What differences observe between transportation problem and assignment problem?
_________________________________________________________________________
_________________________________________________________________________
______________________________________________________________________

 Comment:
TP- transporting products from supply area to consumption area with a minimum
transportation cost
AP -assigning in a one to one relationships jobs to men, machine to jobs etc.

Methods of solving assignment problems

An assignment problem can be solved by the following methods:
1. Enumeration method
2. Simplex method
3. Transportation method
4. Hungarian method
1. Hungarian Method/Flood’s Technique/
The Hungarian Method (developed by Hungarian mathematician [Link]) of assignment
provides us with efficient method of finding the optimal solution without having to make a
direct comparison of every solution. It works on the principle of reducing the given cost
matrix (the principle of matrix reduction) to a matrix of opportunity costs, which means that
by subtracting and adding appropriate numbers in the cost table or matrix ,we can reduce the
problem to a matrix of opportunity costs.

Opportunity costs show the relative penalties associated with assigning resource to an activity
as opposed to making the best or least-cost assignment. If we can reduce the cost matrix to the
extent of having at least one zero in each row and column, then it will be possible to make
optimal assignments.
Steps in solving assignment problems:
Step.1. Develop the cost table from the given problem

69
OR Module

If the number of rows does not equal the number of columns and vice versa, then a dummy
row or dummy column must be added. The assignment costs for dummy cells are always zero.
Step [Link] the opportunity cost table
It involves two operations:
a. Perform row operation
i.e. Locate the smallest element in each row of the given cost table and then
subtract that from each element of that row.
b. Perform column operation
i.e. In the reduced matrix obtained from 2(a) ,locate the smallest element in
each column and then subtract that from each element of that column. Notice
that each row and each column now have at least one zero value.

Step 3. Test for an optimal assignment

Test the table resulting from step 2 to see whether an optimal assignment can be made. The
procedure is:
a. Draw the minimum number of Horizontal and /or Vertical lines necessary to cover
all zeros costs. Draw the lines by trial and error but always try to cover two or
more zeros with one line.
b. Count the number of lines
If the number of lines equals either the number of rows or columns in the table, an
optimal assignment can be made. If the number of lines is less than the number of
rows or columns, an improvement is possible (we proceed to step 4).
Step 4. Improve the present opportunity cost table (matrix)
This is done by the following operations:
a. Find the smallest entry in the uncovered cells (cells with no lines through them) and
subtract it from all entries in the uncovered cells.
b. Add the same smallest entry to those cells in which the lines intersect (cells with two lines
them)
c. Cells with one line through them are transferred (i.e. unchanged to the improved table).
In those problems where the first improvement does not yield an optimal solution, we keep on
improving the solution by repeating step 4 until an optimal solution is achieved.

70
 OR Module

Step 5: Make an optimal assignment

An optimal assignment should be made to cells with a zero entry, maintaining the one-to-one
requirement
If more than one optimal solution exists, a trial-and –error approach can be used to find all
possible combination assignments in the zero cells.
Note that multiple optimal solutions are possible.
Example:
1. A computer center has three programmers. The center wants three application programs to
be developed. The head of the computer center, after studying carefully the programs to
be developed, estimate the computer time in minutes required by the experts for the
application programs as follows:

Programs
1 120 100 80
(Estimated
Programmerstime in
2 minute)
80 90 110
A
3 110 140 120
B C

Assign the programmers to the programs in such a way that the total computer time is the
minimum.

Solution:
Steps 1 and 2:
a. Perform row reduction

The minimum time element in row 1, 2, and 3 is 80, 80 and 110 respectively. Subtract those
elements from all elements in their respective row. The reduced time matrix is:Table: After
row reduction

A B
C
Row minimum
71
 OR Module

-80 1 40 20 0

-80 2 0 10 30

-110 3 0 30 10

b. Column reduction
Since column B has no one ‘0’, perform also column reduction. The minimum time element
in columns A, B and C is 0, 10 and 0 respectively. Subtract these elements from all elements
in their respective column to get the reduced time matrix.

Table: After column reduction

A
B C

1 40 10 0

2 0 0 30

3 0 20 10

Step 3: Test for an optimal assignment

a. Draw the minimum number of horizontal and /or vertical lines necessary to cover all zero
times (costs).

72
OR Module

Table: Test of optimal assignment

A
B C

1 40 10 0

2 0 0 30

3 0 20 10

b. Count the number of lines

If the number of lines is equal to the number of rows/columns, the optimal solution is
obtained. Thus proceed directly to step 5.
Step [Link] an optimal assignment
An optimal assignment should be made to cells with a zero entry, maintaining the one-to-one
requirement.

Table: optimal assignment

A
B C

1 40 10 0
2 0 0 30

3 0
20 10

Note:
In optimal assignment, start with row/column having one zero and cancel the alternative
zeros(x)

The pattern of assignment among programmers and programs with their respective time (in
minute) is given below:

73
OR Module

Programmer Program Time (in minutes)

1 C 80

2 B 90

3 A 110

Total time=280 minutes C

ross Check Formula

Optimal solution = summation of row minimum + summation of columin minimum + revised
reduction
i.e., considering the above problem:
280=270 +10+0
280=280
SPECIAL CASES IN THE ASSIGNMENT PROBLEMS
Certain situations can arise in which the model deviates slightly from that previously
described. Among those situations are the following:
I. Multiple Optimal Solutions

While making an assignment in the reduced assignment matrix, it is possible to have two or
more ways to strike off a number of zeros. Such situation indicates multiple optimal solutions
with the same optimal value of objective function. In such cases the more suitable solution
may be considered by the decision-maker.

In multiple optimal solutions, no unique 0 will exist at some point, resulting in more than one
choice for assignment and hence, more than one optimal solution. It should be noted that all
optimal solutions will yield the same value of the objective function.
Example:1
1. Given this final assignment table, identify two optimal solutions.

74
OR Module

Job Machine (Estimated time in

minute)

A 4 1 0 0 2
3
B 0 3 2

C 1 0 0

Solution
The first assignment must be B-1, because B-1 is the only 0 that appears in a single row or
column. Having made that assignment, there are two choices for the remaining two rows, and
two choices for the remaining two columns. This results in two possible solutions, as shown:

Job Machine (Estimated time in

minute) Job Machine (Estimated time in
A 4 1
0 minute)
2 3 A 41 2
0 0
B 3 2 3
0 0
B 3 2
0
C 1
0 0
C 1
0 0

Alternative optimal assignment

II. Maximization case in assignment problems

There may arise situations when the assignment problem calls for maximization of profit,
revenue, etc. as the objective function. Such problem may be solved by converting the given
maximization problem into a minimization problem by the following procedure:

i. Find the largest profit coefficient in the entire.

75
OR Module

ii. Subtract each entry in the original table from the largest profit coefficient.
The transformed assignment problem so obtained can be solved by using the
Hungarian method.

Example
1.A company has four territories open, and four salesmen available for an assignment. The
territories are not equally rich in their sales potential. Based on the past performance, the
following table shows the annual sales (in $) that can be generated by each salesman in each
territory. Find the optimal assignment and the maximum expected total sales.

Territory

I II III IV
Salesmen

A 42 35 28 21

B 30 25 20 15

C 30 25 20 15

D 24 20 16 12

Solution:
Convert maximization problem into minimization problem by subtracting all elements from
the highest element (i.e. 42)
Thus, the equivalent cost table is:

I II III IV

A 0 7 14 21 I II III IV

B 12 17 22 27 A 0 3 6 9

C 12 17 22 27 B 0 1 2 3

D 18 22 26 30 C 0 1 2 3

D 0 0 0 0

Thus, after improvement of the table, the optimal assignment is:

76
OR Module

I II III IV

A 0 2 4 7

B 0 0 0 1

C 0 0 0 1

D 2 1 0 0

The pattern of two alternative optimal assignments among territories and salesmen with
respective sale is given below:

Assignment set II
Assignment set I

Salesman Territory Sales($) Salesman Territory Sales($)

A I 42 A I 42

B III 20 B II 25

C II 25 C III 20

D IV 12 D IV 12

Total= $ 99 Total= $ 99

III. Unbalanced Assignment Problem (unequal number of

The Hungarian method of assignment requires that the number of columns and rows in the
assignment matrix be equal. However, when the given cost matrix is not a square matrix, the
assignment problem is called an unbalanced problem.
In such cases a dummy row(s) or column(s) are added in the matrix (with zeros as the cost
elements) to make it a square matrix. After making the given cost matrix a square matrix, the
Hungarian method may be used to solve the problem.

77
OR Module

Example
MEGA printing press, a publisher headquartered in Addis Ababa, wants to assign three
recently hired college graduates, Marta, Bakcha and Hirut to regional sales districts in
Mekelle, Bahir Dare, and DireDawa. But the firm also has an opening in Gambela and
would send one of the three there if it were more economical than a move to Mekelle, Bahir
Dar and Dire Dawa. It will cost Br. 1,000 to relocate Marta to Gambela, Br. 800 to relocate
Baklcha there, and Br. 1,500 to move Hirut. What is the optimal assignment of personnel to
offices?

Office Mekelle Bahir Dare Dire Dawa

Hire

Marta Br.800 Br 1,100 Br 1,200

Bekcha Br. 500 Br 1,600 Br 1,300

Hirut Br. 500 Br 1,000 Br 2,300

Solution
To balance the problem, we add a dummy row (person) with a zero relocation cost to each
city.

City C1 C2 C3 C4(Gambela)
Person

P1 800 1,100 1,200 1,000

P2 500 1,600 1,300 800

P3 500 1,000 2,300 1,500

Dummy 0 0 0 0

Table: after row reduction Table: Optimal Assignment

78
 OR Module

C1 C2 C3 C4

P1 0 300 400 200 C1 C2 C3 C4

P2 0 1,100 800 300 P1 100 0 100 0
P3 0 500 1800 1000 P2 0 700 400 0
Dummy 0 0 0 0 P3 0 100 1400 700

Dummy 400 0 0 100

Thus, an optimal assignment can be made at zero cells (squares).

Person City

Dummy(No person) Dire Dawa

Hirut Mekelle

Bekcha Gambela

Marta Bahir Dare

Cost =Br. (0+500+800+1,100)=Br.2,400

IV. Restrictions on Assignments

In certain instances, it may happen that a particular match or pairing may be either
undesirable or otherwise unacceptable. For example, an employee may not have the skills
necessary to perform a particular job or a machine may not be equipped to handle a particular
operation. In such cases, the cost of performing that particular activity by a particular resource
is considered to be very large (written as M or  )
Example
1. In the modification of a plant layout of a factory four new machines M1, M2, M3 and M4
are to be installed in a machine shop. There are five vacant places A, B, C, D and E
available. Because of limited space, machine M2 can not be placed at C and M3 cannot be
placed at A. the cost of placing of machine at place i (in $) is shown below.

79
OR Module

Location

A B C D E

M1 9 11 15 10 11
Machine M2 12 9 - 10 9

M3 - 11 14 11 7

M4 14 8 12 7 8

Find the optimal assignment schedule.

Solution:

As the cost matrix is not balanced, add one dummy row (machine) with a zero cost
element in that row. Also assign a high cost, denoted by M, to the pair (M2, C) and (M3,
A).

Apply the Hungarian method to solve the problem

A B C D E

M1 9 11 15 10 11

M2 12 9 M 10 9

M3 M 11 14 11 7

M4 14 8 12 7 8

M5 0 0 0 0 0

The total minimum cost ($) and optimal assignments made are as follows:

Machine Location Costs ($)

80
OR Module

M1 A 9

M2 B 9

M3 E 7

M4 D 7

M5 (Dummy) C 0
Total = $32

81
OR Module

UNIT FOUR

4. DECISION THEORY

4.2 INTRODUCTION

Decision theory represents a generalized approach to decision making which often serves as
the bases for a wide range of managerial decision making.
The decision model includes a list of courses of action that are available & the possible
consequences of each course of action.

The decisions are classified according to the degree of certainty as deterministic models,
where the manager assumes complete certainty and each strategy results in a unique payoff,
and Probabilistic models, where each strategy leads to more than one payoffs and the
manager attaches a probability measure to these payoffs. The scale of assumed certainty can
range from complete certainty to complete uncertainty hence one can think of decision
making under certainty (DMUC) and decision making under uncertainty (DMUU) on
the two extreme points on a scale. The region that falls between these extreme points
corresponds to the concept of probabilistic models, and referred as decision-making under
risk (DMUR). Hence we can say that most of the decision making problems fall in the
category of decision making under risk and the assumed degree of certainty is only one aspect
of a decision problem.

In this chapter you will learn decision theories concerned with decision under certainty,
decision under risk and decision under uncertainty.
4.2 DECISION THEORY
Decision theory deals with decision making under conditions of risk and uncertainty. For our
purpose, we shall consider all types of decision models including deterministic models to be
under the domain of decision theory. In management literature, we have several quantitative
decision models that help managers identify optimal or best courses of action.
Before we go to decision theory, let us just discuss the issues, such as
(i) What is a decision?

82
 OR Module

(ii) Why must decisions be made?

(iii)What is involved in the process of decision-making?
(iv) What are some of the ways of classifying decisions? This will help us to have clear
concept of decision models.

WHAT IS A DECISION

? Activity
What is decision making?

 Comment:
Decision making is the process of selecting the best choices from the available
alternatives.

A decision is the conclusion of a process designed to weigh the relative utilities or merits
of a set of available alternatives so that the most preferred course of action can be selected
for implementation.
Decision-making involves all that is necessary to identify the most preferred choice to
satisfy the desired goal or objective.
STEPS IN DECISION THEORY APPROACH

? Activity
What are the steps to make to make decisions? Please try your answer in the
given space.
________________________________________________________________
_______________________________________________________________

 Comment
The common steps in decision making are list of possible alternatives, list of
future events; construct pay of tables, assessment of degree of certainty and
making a choice

83
OR Module

Though the steps to make the decision differ from problem to problem, the general steps in
decision theory include the following
1. List the viable alternatives (strategies) that can be considered in the decision.
2. List all future events that can occur. These future events (not in the control of decision
maker) are called as states of nature.
3. Construct a payoff table for each possible combination of alternative course of action and
state of nature.
4. An assessment of the degree of certainty of possible future events
5. Choose the criterion that result in the largest payoff.
List of alternatives:
The list of alternatives must be a set of mutually exclusive and collectively exhaustive
decisions that are available to the decision maker.
For example, suppose that a real estate developer plan to develop a building. After careful
analysis, the developer lists the following acceptable alternatives.
Residential
Hospital
Hotel
State of nature:
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 consequence of the
decision. Suppose in the case of the real estate developer, the main factor that that will
influence the profitability is the state of the economic development that will be achieved in
the future. Suppose that the developer views the possibilities as:
Low economic growth
Medium economic growth
High economic growth

Payoffs:
In order for a decision maker to be able to rationally approach a decision problem, it is
necessary to have some idea of the payoffs that would be associated with each decision

84
OR Module

alternative and the various states of nature. The payoffs might be profits, revenue, costs, or
other measure of value. They may be weekly, monthly, or annual amounts.

Pay off table:

The payoff table is a device a decision maker can use to summarize and organize information
relevant to particular decision. It includes a list of alternatives, the possible future state of
nature and payoffs associated with each of the alternative / state of nature combinations.

Now let’s assume the real estate developer, set up the following payoff

Low economic Medium economic High economic

Growth Growth Growth

4 16 12
Residential
5 6 10
Hospital
Hotel -1 4 15

The pay of table for the real state developer’s decision is shown in the above table. The three
alternatives under considerations are listed down the left side of the table and the three
possible states of nature are listed across the top of the table. The pay offs that are associated
with each alternative /state of nature combinations are shown in the body of the table.
Suppose that the values represent profits in million birr. Hence if the residential is chosen and
if the economic growth is low the developer realize a profit of birr 4,000,000. Similarly, if
hotel is selected and if the economic growth is low, the developer will lose birr 1,000,000,
similarly there are nine payoffs. But the question is which alternative is the best for the
decision maker? To answer the question, it is a must to determine the degree of certainty i.e.
is it certainty, risk or uncertainty.

DECISION MAKING ENVIRONMENT

Base on the availability of information during the decision making, there are three decision
making environment. These are:

85
OR Module

A. Decision making under certainty

B. Decision making under risk
C. Decision making under uncertainty
A. DECISION MAKING UNDER CERTAINTY (DMUC)
Decision making under certainty assumes that all relevant information required to make
decision is certain and well known. It uses a deterministic model, with complete knowledge,
stability and no ambiguity.
If the developer knows that the economic growth is low, he/she select hospital as the best
alternatives because it results a profit of birr 5,000,000 and the like.

B. DECISION MAKING UNDER UNCERTANITY (DMUU)

Decision making under uncertainty is formulated exactly in the same way as decision making
under risk, the only difference is that no probability to each strategy is attached. In decision
making under uncertainty, remember that no probabilities are attached to set of the states of
nature. While solving the problem of decision making under uncertainty, we have two
approaches, the first one is pessimistic approach and the second one is optimistic approach.

C. DECISION MAKING UNDER RISK (DMUR)

Decision-making under risk (DMUR) describes a situation in which each strategy results in
more than one outcome or payoffs and the manager attaches a probability measure to these
payoffs. This model covers the case when the manager projects two or more outcomes
for each strategy and he or she knows, or is willing to assume, the relevant probability
distribution of the outcomes.

The following assumptions are to be made:

Availability of more than one strategy,
The existence of more than one states of nature,
The relevant outcomes and
The probability distribution of outcomes associated with each strategy.
The optimal strategy in decision making under risk is identified by the strategy with highest
expected utility (or highest expected value).

86
OR Module

4.3 DECICISIN CRITERIA

The process of selecting one alternative from a list of alternatives is governed by a decision
criterion, which embodies the decision maker’s attitudes towards the decision.
4.3.1 Decision Criterion under Certainty
The simplest of all circumstances occurs when decision making takes place in an environment
of complete certainty. For example, in the case of real state problem, an unexpected early
announcement concerning the economic development indicate low economic growth could
reduce the problem to a situation of certainty since the developer focus on the first column of
the pay of table.
4.3.2 Decision Criterion under Uncertainty
Decisions made under these circumstances are at the opposite end of the spectrum from the
certainty case. We shall consider four approaches to decision making under complete
uncertainty. They are:
1 . Maxi-max: (optimistic view) under this method the best payoff for each alternative
is identified and the alternative with the maximum of these is the designated decision.
(identifying the best from the best alternatives) it is the optimistic view because the decision
maker assume the best things will occur. (the maxi- max will be converted to mini-min
principle under cost scenario)
For the real state problem, the maxi-max solution is shown below.

Low economic Medium economic High economic

Growth Growth Growth Row max
4 16 12 16 max
Residential
5 6 10
Hospital 10
Hotel -1 4 15
15

Therefore, the developer will select Residential as the best alternative, since it provides the
highest pay off i.e. 16,000,000.

87
OR Module

2. Maxi-min: (pessimistic view) it is the conservative strategy; it consists of identifying the

worst (minimum) payoff for each alternative and then selecting the alternative that has the
best (maximum) of the worst pay off. Many people view the maxi-min criterion as pessimistic
because they believe the decision maker must assume the worst will occur. (the maxi- max
will be converted to mini-min principle under cost scenario)
For the real state problem, the maxi-max solution is shown below.

Low economic Medium economic High economic

Growth Growth Growth Row mini

4 16 12 4
Residential
5 6 10 5 max
Hospital
Hotel -1 4 15 -1

Therefore, the developer will select Hospital as the best alternative, since it provides the
highest pay off from the worst alternatives i.e. 5,000,000.
2. Mini-max regret: both the maxi-max and maxi-min strategies can be criticized because
they focus only on a single extreme payoff and exclude the other payoffs. This approach
does take all payoffs in to account. In order to use this approach, it is necessary to develop
an opportunity loss table. The opportunity loss reflects the difference between each payoff
and the best possible payoff in a given state of nature. For the real state problem, the
maxi-max solution is shown below
Low economic Medium economic High economic
Growth Growth Growth

4 16 12
Residential
5 6 10
Hospital
Hotel -1 4 15

Column
Max 5 16 15

88
OR Module

The opportunity loss table is calculated as follows

5-4 16-16 15-12

5-5 16-6 15-10

5-(-1) 16-4 15-15

The result of the opportunity loss calculation

Maximum loss (regret)

3 Mini
1 0 3

0 10 5 10

6 12 0 12

Therefore, the developer will select Residential as the best alternative; since it provides the
minimum loss pay off from the worst alternatives (highest loss) i.e. 3,000,000.
3. The principle of insufficient reason: it offers a method that incorporates more of the
information. It treats the states of nature as if each were equally likely and it focuses
on the average payoff for each row selecting the one that has the highest row average.
we calculate the payoffs by assuming all the states of natures have equal chance of
existence i.e. 1/3 since the number of state of natures are three in our case.

Alternatives State of nature as if all are equally likely

LEG MEG LEG
RES (4*1/3)+(16*1/3)+(12*1/3)=32/3=10.6
HOT (5*1/3)+(6*1/3)+(10*1/3)=21/3=7
HOS (-1*1/3)+(4*1/3)+(15*1/3)=18/3=6

Therefore, the developer will select Residential as the best alternative; since it provides the
maximum pay off from the available alternatives i.e. 10.6 million.

89
OR Module

? Activity:
What are the different approaches for making decisions under uncertainty?
_____________________________________________________________________
_____________________________________________________________________
_____________________________________________________________________
___________________________________________________________________

 Comment:
Maxi-max, max-min, mini-max regret and the principle of insufficient reason

4.3.3 Decision Criterion under Risk

The essential difference between decision making under complete uncertainty and decision
making under Risk (partial uncertainty) is the presence of probabilities for the occurrence of
the various states of nature in partial uncertainty. The probabilities may be subjective
estimates from managers or from experts in a particular field or they may reflect historical
frequencies. If they are reasonably correct they provide a decision maker with additional
information that can dramatically improve the decision making process.

Note that
The sum of the probabilities for all states of nature must be 1.

The Expected monetary value (EMV): This approach provides the decision maker with a
value which represents an average pay off for each alternative the best alternative is , then, the
one that has the highest expected pay offs . Thus the expected monetary value is:
EMVi = PjVij
Where:
EMVi= the expected monetary value for the i th alternative
Pj = the probability of the j th state of nature
Vij =the estimated payoff for alternative i under state of nature j
For example, considering the real stare developer problem, assuming the manager estimates
the state of nature as LEG 20%, MEG 50% & HEG 30%. We ca compute the expected
monetary value for the real state developer’s alternatives as follows

90
OR Module

EMVR= .2(4) +.5(16) + 3(12) =12.40

EMVHT= .2(5) +.5(6) + 3(10) =7.00
EMVHS= .2(-1) +.5(4) + 3(15) =6.30
Because the residential alternatives have the largest expected monetary value, it would be
selected using this criterion
The Expected opportunity loss (EOL): This approach provides an alternative method for
incorporating probabilities into the decision making. The approach is nearly identical to the
EMV approach except that a table of opportunity loses is used rather than a table of loss.
Hence the opportunity loses for each alternative are weighted by the probabilities of their
respective states of nature to compute a long run average opportunity loss and the alternative
with the smallest expected loss is selected as the best choice. For real state problem, the
expected opportunity loss can be calculated as follows (use previously calculated opportunity
loss table)
EOLR=.2(1) +.5(0) + 3(3) =1.10
EOLHT = .2(0) +.5(10) + 3(5) =6.5
EOLHT = .2(6) +.5(112) + 3(0) =7.2
Because the residential alternatives have the minimum expected opportunity loss, it would be
selected. note that the EOL approach resulted in the same alternative as the EMV approach.
This is more than coincidence; the two methods will always result in the same choice because
they are equivalent ways of combining the values maximizing the pay offs is equivalent to
minimizing the opportunity loss.
Expected value of perfect information: it can sometimes be useful for a decision maker to
determine the potential benefit of knowing for certain which state of nature is going to
prevail. For instance, a decision maker might have the option of delaying a decision until it is
evident which state of nature is going to materialize. The obvious benefit of waiting would be
to move the decision maker into the realm of certainty, thereby allowing the decision maker to
obtain the maximum possible payoff.

The expected value of perfect information (EVPI) is a measure of the difference between the
certain payoff that could be realized under a condition of certainty and the expected under
conditions involving risk.

91
 OR Module

Consider the payoff that the real estate developer could expect under certainty. If the
developer knew that the economic growth is low, the hospital alterative would be choose with
a payoff of 5, 000,000. If the developer knew a medium economic growth would exist, the
residential alternative would be chosen for a payoff of 16,000,000 and if the developer knew
that a high economic growth would happen, hotel would be chosen for a payoff of
15,000,000.
Hence if it were possible to remove the uncertainty surrounding the states of nature, the
decision maker could capitalize on that knowledge. Obviously before investing time or money
in eliminating the probabilities, it will be impossible for the decision maker to say which
states of nature will turn out to be the one that will occur. However, what can be said is that
the probability that perfect information will indicate that LEG will happen t is 20%, that the
probability that perfect information will indicate a MEG will happen is 50% and the
probability of perfect information indicating a HEG will happen is 30%. Thus, these
probabilities which are the original state of nature probabilities can be used to weight the
payoffs, one of which will occur under certainty. This is called the expected pay off under
certainty (EPC), and is computed in the following way for the real state problem.
EPC =.2(5) +.5(16) + 3(15) =13.50
The difference between this figure and the expected payoff under risk (i.e. the EMV) is the
expected value of perfect information. Thus,
EVPI= EPC- EMV
For the real state problem, with EPC 13.5- and EMV = 12.4 we find EVPI= 13.5-12.4= 1.1
The EVPI represents an upper bound on the amount of money the real estate developer would
be justified in spending to obtain perfect information. Thus the real estate developer would be
justified in spending up to 1100,000 to find out for certain which h state of nature will prevail
Note that: The EVPI is exactly equal to the previously computed EOL. In fact, these two
quantities will always be equal. The EOL indicates the expected opportunity loss due to
imperfect information which is another way of saying the expected payoff that could be
achieved by having perfect information. Hence there are two equivalent ways to determine the
expected value of perfect information:
o Subtract the EMV from the EPC or
o Compute the EOL For cost scenario
EVPI=EMV-EPC

92