College of Business and Economics

Department of Management

Course Title: Operations Research

Course Code: Mgmt 4132

Writers:

Abdulhamid Yusuf (MBA)

Nejat Abdurezak (MBA)

March 2023
 Operations Research

Course Introduction

Hello and welcome to the course Operations Research! Operations Research (OR) is a discipline
that is focused on the application of information technology for informed decision-making. In
other words, OR represents the study of optimal resource allocation. The goal of OR is to
provide rational bases for decision making by seeking to understand and structure complex
situations, and to utilize this understanding to predict system behavior and improve system
performance. Problems solving and decision making are vital skills in all areas of management.
Operations research as discipline devoted to the solution of management problem using a
scientific approach. The problem is viewed as the focal point of analysis, and quantitative model
are the vehicles by which solutions are obtained. This course introduces several quantitative
concepts and computational tools used by managers to determine solutions to complex problems
and thereby selecting the best solution.

In general, Operations Research provides an introduction to the concepts and methods of

decision science, which involves application of mathematical modeling and analysis to
management problems. You will gain an understanding of modeling and rational approaches to
decision making and their contribution to organizational effectiveness. Analysis and
communication are emphasized by using real world applications and cases. Topics included this
course are linear programming, network models, projects scheduling, and queuing models,
applied to tactical and strategic business decisions in functional areas and interfaces among the
areas. Implementation using existing software packages of decision models to solve various
managerial problems is an integrated part of this course.

To this effect the course includes seven chapter: Introduction to Operations Research (Chapter
One), Linear Programming problem (Chapter Two), Transportation and Assignment Problem
(Chapter Three), Network Models (Chapter Four), Decision Theory (Chapter Five) and Game
Theory (Chapter Six), Queuing Analysis (Chapter Seven).

Haramaya University, Department of Management ii

 Operations Research

Course Objectives

After the end of this course, you should be able to:

✓ Develop analytical skills in structuring and analysis (scientific method) of business

decision problems which characterized the field of operation research or management
science.
✓ Develop awareness of the complementary nature of the rational and behavioral
approaches to decision making and planning and sharpen your ability to structure
problems and to perform logical analysis.
✓ Use selected software to generate computer solutions of the models.
✓ Learn, through case studies, the applications of operation research or management
science to find solutions to real life business problems including those in global
environment.
✓ Demonstrate skills in communicating the analysis and results of business decision
problems and to work as a member of a team.
✓ Use the knowledge gained from this course to continuing life-long learning in decision
technologies to aid business decision making and planning.

Haramaya University, Department of Management iii

 Operations Research

Table of Contents

Contents Page
Course Introduction ii

Table of Contents iv

Introduction to Operations Research 1

1.1. Meaning and Concepts of Operations Research 2

1.2. The History of Operations Research 4

1.3. Nature of Operations Research 6

1.4. Significance of Operations Research 6

1.5. Features of Operations Research 7

1.6. Models and Modeling in Operations Research 8

1.7. Methodology of Operations Research 12

Chapter Two 15

Linear Programming 15

Introduction 15

2.2 Application Areas of LP Model 18

2.3. Solution to Linear Programming Problems 19

2.3.1 Graphical Solution 19

2.4 Special Cases in Graphics Methods 28

2.5 Simplex Method 38

2.5 Special Cases in Simplex Method 58

Chapter Three 65

Transportation and Assignment Problem 65

3.1 Introduction 65

3.2. Methods of Finding Initial Feasible Solution 70

3.3 Optimality Tests 82

Haramaya University, Department of Management iv

 Operations Research

3.6 Assignment Problems 97

Chapter Four 117

Network Models 117

Introduction 117

4.1 General Network Concepts 118

4.2 Networking Algorithms 126

4.2.1. The Shortest-Path Problem 126

4.2.2. Minimal Spanning Tree Problem 129

4.2.3. The Maximum Flow Problem 133

4.3 Basic Difference Between PERT and CPM 140

4.4 PERT/CPM Network Components and Precedence Relationship 144

4.4.1. Types of Network Diagrams 148

[Link]. Arrow Diagram Method (ADM) 148

[Link]. Precedence Diagram Method (PDM) 149

Chapter Five 162

Decision Theory 162

Introduction 162

5.1. Overview of Decision Theory 163

5.2. Types of Decision-Making Environment 164

4.3. Decision Making Under Uncertainty 166

5.4. Decision Making Under Risk 169

5.5. Decision Making Under Certainty 172

5.6. Decision Making with Utilities 174

Chapter Six 181

Game Theory 181

Introduction 181

Haramaya University, Department of Management v

 Operations Research

6.1. Overview of Game Theory 182

6.2. Two-person Zero-Sum Game 184

6.3. Pure Strategies: Game with Saddle Point 187

6.4. The Rule of Dominance 190

6.5. Mixed Strategies: Game Without Saddle Point 194

Chapter Seven 209

Queuing Models 209

Introduction 209
7.1. Overview of Queuing Model 210

7.2. Queuing System 215

7.2.1. Input Process 215

7.2.2. Service Mechanism or Service Facility 219

7.3. Queuing System Performance Measures 222

7.4. Queuing Models 225

7.4.1 FIFO Model 226

7.4.2. Generalization of model (M /M / 1): (FCFS/ ∞/∞): (Birth – Death process) 229

7.4.3. Finite Queue Length Model: (M / M / 1): FCFS / N / ∞ 231

7.4.4. MODEL IV: (M / M / 1): FCFS / N /N (Limited Population or Source Model) 233

Haramaya University, Department of Management vi

 Operations Research

Haramaya University, Department of Management vii

 Operations Research

Chapter One

Introduction to Operations Research

Introduction
Many people still remain in the bondage of self-incurred tutelage. Tutelage is a person's inability
to make his/her own decisions. Self-incurred is this tutelage when its cause lies not in lack of
reason but in lack of resolution and courage to use it without wishing to have been told what to
do by something or somebody else.

The difficulty in life is the choice. Good decision-making brings about a better life. A bad
decision may force you to make another one. A good decision is never an accident; it is always
the result of high intention, sincere effort, intelligent direction and skillful execution; it
represents the wise choice of many alternatives. One must appreciate the difference between a
decision and an objective. A good decision is the process of optimally achieving a given
objective.

When decision-making is too complex or the interests at stake are too important, quite often we
do not know or are not sure what to decide. In many instances, we resort to informal decision
support techniques such as tossing a coin, asking an oracle, visiting an astrologer, etc. However,
formal decision support from an expert has many advantages. Business Science focuses on the
formal model-driven decision support techniques such as mathematical programs for
optimization, and decision tree analysis for risky decisions. Such techniques are now part of our
everyday life. For example, when a bank must decide whether a given client obtains credit or
not, a technique, called credit scoring, is often used.

In decision-making we may start the process of consideration. It is best to learn the decision-
making process for complex, important and critical decisions. Critical decisions are those that
cannot and must not be wrong.

The aim of this course is to make you a better decision maker by learning the decision-making
process. Decision-making is a complicated process that involves a series of steps. This
complication arises from the fact that your present goal (including wants, resources, and
abilities) dictates your choices; however, your choices will change your goals. This influential-

Haramaya University, Department of Management 1

 Operations Research

cycle keeps the decision-maker busy all the time. Selecting your goals and your criteria for
success is a dynamic process and changes over time. The goal is the foundation for decision-
making process. This is true in almost all cases dealing with personal growth or organizational
growth.

Chapter Objectives

At the end this chapter, students should be able to;

➢ Identify situations in which linear programming technique can be applied.

➢ Describe fundamental concepts and general mathematical structure of a linear

programming model.

➢ Express objective function and resource constraints in LP model in terms of decision

variables and parameters.

➢ Appreciate the limitations and assumptions of linear programming technique with a view
to interpret the solution.

➢ Describe how to solve LP using graphical and simple X method

1.1. Meaning and Concepts of Operations Research

On a daily basis a manager has to make many decisions. Some of these decisions are routine and
inconsequential, while others have drastic impacts on the operations of the firm for which he/she
works. Some of these decisions could involve large sums of money being gained or lost, or could
involve whether or not the firm accomplishes its mission and its goals.

In our increasingly complex world, the tasks of decision-makers are becoming more challenging
with each passing day. The decision-maker (i.e., the responsible manager) must respond quickly
to events that seem to take place at an ever-increasing pace. In addition, a decision-maker must
incorporate a sometimes-bewildering array of choices and consequences into his or her decision.
Routine decisions are often made quickly, perhaps unconsciously without the need for a detailed
process of consideration. However, for complex, critical or important managerial decisions it is
necessary to take time to decide systematically.

Haramaya University, Department of Management 2

 Operations Research

To make strategic decisions requires that one takes a structured approach following a formal
decision-making process. Otherwise, it will be difficult to be sure that one has considered all the
key aspects of the decision.

A basic education in OR for managers is essential. They are responsible for leading the business
system and the lives in that system. The business system is dynamic in nature and will respond as
such to disturbances internally and externally.

The OR approach to decision making includes the diagnosis of current decision-making and the
specification of changes in the decision process. Diagnosis is the identification of problems (or
opportunities for improvement) in current decision behavior; it involves determining how
decisions are currently made, specifying how decisions should be made, and understanding why
decisions are not made, as they should be. Specification of changes in decision process involves
choosing what specific improvements in decision behavior are to be achieved and thus defining
the objectives.

Nowadays, the OR approach has been providing assistance to managers in developing the
expertise and decision tools necessary to understand the decision problems, put them in
analytical terms and then solve them. The OR analysts are, e.g., "chiefs of staff for the
president", "advisors", "and R&D modelers" "systems analysts", etc. Applied Management
Science is the science of solving business problems.

Definitions
Operation Research is a tool for taking decisions which searches for the optimum results
in parity with the overall objectives and constraints of the organization.

OR is a scientific method of providing executive department with a quantitative basis of

decisions regarding the operations under their control.

OR is a scientific approach to problem solving for management.

OR is an aid for executive in making his decisions by providing him with the needed
quantitative information’s based on the scientific method of analysis.

Haramaya University, Department of Management 3

 Operations Research

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.

From the concepts and definitions 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.

1.2. The History of Operations Research

Until the middle of the 19th century, most industrial enterprises only employed a few workers.
However, as companies expanded, it became less and less feasible for one person to manage all
of the new managerial functions of the business effectively. New scientific methodologies were
developed to provide assistance to each new type of managerial function as it appeared. As more
specialized forms of management emerged, more specialized sub-functions, such as statistical
quality control, equipment maintenance, marketing research, and inventory control emerged.
Whenever a managerial function is broken down into a set of different sub-functions, a new task,
called the executive function of management, is created to integrate the diverse sub-functions
so that they efficiently serve the interests of the business as a whole. The executive function
evolved gradually with organizations themselves. However, increasing demands were made on
the manager who, in turn, sought aid outside the organization. This gave rise to management
consultants. What we call OR today is, in fact, the use of scientific tools to aid the executive.

OR originated in Great Britain during World War II to bring mathematical or quantitative

approaches to bear on military operations. Since then, it has evolved to be applicable to the
management of all aspects of a system, product, or service, and hence is often referred to as

Haramaya University, Department of Management 4

 Operations Research

Systems Science or Management Science. It has now become recognized as an important input
to decision-making in a wide variety of applications in business, industry, and government.

The term OR arose in the 1940's when research was carried out on the design and analysis of
mathematical models for military operations. Since that time the scope of OR has expanded to
include economics (known as econometrics), psychology (psychometrics), sociology (socio-
metrics), marketing (marketing research and marketing science), astrology (astronomy), and
corporate planning problems. The growing complexity of management has necessitated the
development of sophisticated mathematical techniques for planning and decision-making, and
the OR features prominently in this structured decision-making process cycle by providing a
quantitative evaluation of alternative policies, plans, and decisions. The mathematical disciplines
most widely used in OR modeling process include mathematical programming, probability and
statistics, and computer science. Some areas of OR, such as inventory control, production
control, and scheduling theory, have grown into sub-disciplines of their own right and have
become largely indispensable in the modern world.

Military organizations had gone through the same type of evolution as other businesses and
industries. This organizational evolution took place in the twenty-year gap between the end of
World War I and the beginning of World War II when the military leadership had to turn to
teams of scientists for aid. These teams of scientists were usually assigned to the executive in
charge of operations; hence their work came to be known as Operational Research in the United
Kingdom and by a variety of names in the United States: Operation Research, Decision Science,
Operational Analysis, System analysis, Success Science, and Management Science. The name
Operations Research is the most widely used.

The potential of computer and information systems as new tools for management forced the non-
technically trained executives to begin to look for help in the utilization of the computer. The
emerging search for assistance was accelerated by the outbreak of the Korean War. This
vigorous growth of OR in the military continued to provide rapid applicability to other industries
and sectors.

Haramaya University, Department of Management 5

 Operations Research

1.3. Nature of Operations Research

As its name implies, operations research involves “research on operations.” Thus, operations
research is applied to problems that concern how to conduct and coordinate the operations (i.e.,
the activities) within an organization. The nature of the organization is essentially immaterial,
and, in fact, OR has been applied extensively in such diverse areas as manufacturing,
transportation, construction, telecommunications, financial planning, health care, the military,
and public services, to name just a few. Therefore, the breadth of application is unusually wide.
The research part of the name means that operations research uses an approach that resembles
the way research is conducted in Operations Research involves creative scientific research into
the fundamental properties of operations. However, there is more to it than this. Specifically, OR
is also concerned with the practical management of the organization. Therefore, to be successful,
OR must also provide positive, understandable conclusions to the decision maker(s) when they
are needed. Still another characteristic of OR is its broad viewpoint.

OR adopts an organizational point of view. Thus, it attempts to resolve the conflicts of interest
among the components of the organization in a way that is best for the organization as a whole.
This does not imply that the study of each problem must give explicit consideration to all aspects
of the organization; rather, the objectives being sought must be consistent with those of the
overall organization.

An additional characteristic is that OR frequently attempts to find a best solution (referred to as

an optimal solution) for the problem under consideration. (We say a best instead of the best
solution because there may be multiple solutions tied as best.) Rather than simply improving the
status quo, the goal is to identify a best possible course of action. Although it must be interpreted
carefully in terms of the practical needs of management, this “search for optimality” is an
important theme in OR.

1.4. Significance of Operations Research

The operations research approach is particularly useful in balancing conflicting objectives or

goals where there are many alternative courses of action available to the decisions makers. The
optimum decision must be one that is best for the organization as a whole. It is often called the

Haramaya University, Department of Management 6

 Operations Research

global optimum. A decision that is best for one or more sections of the organization is usually
called suboptimum decision. The OR approach attempts to find global optimum by analyzing
inter-relationships among the system components involved in the problem.

Operations research attempts to resolve the conflicts of interest among various sections of the
organization and seeks the optimal solution which may not be acceptable to one department but
is in the interest of the organization as a whole.

Nowadays, OR has been providing assistance to managers in developing the expertise and tools
necessary to understand the decision problems, put them in analytical terms and then solve them.

1.5. Features of Operations Research

Interdisciplinary Approach: - Interdisciplinary teamwork is essential because while attempting

to solve a complex management problem, one person may not have the complete knowledge of
all its aspects (such as economic, social, political, psychological, engineering, etc.). Therefore,
team of individuals specialized in mathematics, statistics, economics, engineering, computer
science, psychology, etc., can be organized so that each aspect of the problem could be analyzed
by a particular specialist in that field in order to arrive at an appropriate and desirable solution of
the problem. However, there are certain problem situations which may be analyzed even by one
individual.

Methodological Approach: - Operations research is the application of scientific methods,

techniques and tools to problems involving the operations of systems so as to provide those in
control of operations with optimum solutions to the problems. The scientific method consists of
observing and defining the problem; formulating and testing the hypothesis; and analyzing the
results of the test. The data so obtained is then used to decide whether the hypothesis should be
accepted or not.

Holistic Approach: - While arriving at a decision, an operations research team examines the
relative importance of all conflicting and multiple objectives and the validity of claims of various
departments of the organization from the perspective of the whole organization.

Haramaya University, Department of Management 7

 Operations Research

Objectivistic Approach: - an operations research approach seeks to obtain an optimal solution to

the problem under analysis. For this, a measure of desirability (or effectiveness) is defined, based
on the objective (s) of the organization.

1.6. Models and Modeling in Operations Research

Operation Research model is an activity representation of the real-life situation and represents
one or more aspects of reality. Examples of operation research models are: a map, activity charts
balance sheets, PERT network, break-even equation, economic ordering quantity equation etc.
Objective of the model is to provide a means for analyzing the behavior of the system for
improving its performance.

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

reality. By its very nature a model is incomplete. A good model captures the important details of
reality without including innumerable minor details.

Both simple and complex systems can easily be studied by concentrating on some portion or key
features instead of concentrating on every detail of it. This approximation or abstraction,
maintaining only the essential elements of the system, which may be constructed in various
forms by establishing relationships among specified variables and parameters of the system, is
called a model. In general, models attempt to describe the essence of a situation or activity by
abstracting from reality so the decision-maker can study the relationship among relevant
variables in isolation.

Models do not attempt to duplicate reality in all aspects, but for models that do reveal nothing.
Effective model must be representative of those aspects of reality that are being investigated and
have a major impact on the decision situation.

A model is constructed to analyze and understand the given system for the purpose of improving
its performance. The reliability of the solution obtained from a model depends on the validity of
the model in representing the system under study. The key to model-building lies in abstracting
only the relevant variables that affect the criteria of the measures-of-performance of the given
system and expressing the relationship in a suitable form. However, a model should be as simple

Haramaya University, Department of Management 8

 Operations Research

as possible so as to give the desired result. But oversimplifying the problem can lead to a poor
decision.

A. Classification of Models Based on Structure

1. Physical Models: - are models which provide a physical appearance of the real object under
study either reduced in size or scaled up. Physical models are useful only in design of
problems because they are easy to observe, build and describe. Since these models cannot be
manipulated, they are not very useful for prediction of problems such as portfolio selection,
media selection, production scheduling, etc., and cannot be analyzed with a physical model.
Physical model can be classified in to two: -

Iconic Models: - These models are scaled version of the actual object. For example a toy of a
car is an iconic model of a real car. In other words, such models represent the system as it is
by scaling it up or down (i.e. enlarging or reducing the size). An iconic model is used to
describe the characteristics of the system rather than being explanatory. They explain all the
features of the actual object. In fact, a globe is an iconic model of the earth. These models
may be of enlarged version or reduced version.

Analogue Models: - These models represent a system by a set of properties different from
those of the original system and do not resemble it physically. In this model one set of
properties are used to represent another set of properties. Say for example, blue colour
generally represents water. Whenever we want to show water source on a map it is
represented by blue [Link] models are less specific and concrete but are easier to
manipulate and are more general than iconic models.

2. Symbolic or Mathematical Models: - use symbols (letters and numbers) and functions to
represent variables and their relationships to describe the properties of the system. In these
models the variables of a problem are represented by mathematical symbols, letters etc. To
show the relationships between variables and constraints we use mathematical symbols.
These models are used very much in operations research. Symbolic models can be classified
into two categories.

Haramaya University, Department of Management 9

 Operations Research

Verbal Models: - These models describe a situation in written or spoken language. Written
sentences, books, etc., are examples of a verbal model.
Mathematical Models: - These models involve the use of mathematical symbols, letters,
numbers and mathematical operators (+, -, ÷, x) to represent relationships among various
variables of the system to describe its properties or behavior. The solution to such models is
then obtained by applying suitable mathematical technique. Symbolic models are precise and
abstract and can be analyzed and manipulated by using laws of mathematics. The models are
more explanatory rather than descriptive.

B. Classification of Models Based on Function or Purpose

Models based on the purpose of their utility include the following types.

Descriptive models: - The descriptive model simply explains certain aspects of the problem or
situation or a system so that the user can make use for his analysis. It will not give full details
and clear picture of the problem for the sake of scientific analysis.

Predictive models: -These models indicate ‘if this occurs, then that will follow’. They relate
dependent and independent variables and permit trying out, ‘what if’ questions. These models
basing on the data collected, can predict the approximate results of the situation under question.
In other words, these models are used to predict the outcomes due to a given set of alternatives
for the problem. These models do not have an objective function as a part of the model to
evaluate decision alternatives. For example, S = a + bA + cI is a model that describes how the
sale (S) of a product changes with a change in advertising expenditure (A) and disposable
personal income (I). Here a, b and c are parameters whose values must be estimated. In these
models, however, one does not attempt to choose the best decision alternative, but can only have
an idea about each alternative available to him.

Normative (Optimization) models: - These models provide the ‘best’ or ‘optimal’ solution to
problems subject to certain limitations on the use of resources. For example, in mathematical
programming, models are formulated for optimizing the given objective function, subject to
restrictions on resources in the context of the problem under consideration and non-negativity of
variables. These models are also called prescriptive models because they prescribe what the
decision-maker ought to do.
Haramaya University, Department of Management 10
 Operations Research

C. Classification Based on Method of Solution or Quantification

Heuristic models: - These models employ some sets of rules which, though perhaps not optimal,
do facilitate solutions of problems when applied in a consistent manner.

Analytical models: - These models have a specific mathematical structure and can be solved by
known analytical or mathematical techniques. Any optimization model (which requires
maximization or minimization of an objective function) is an analytical model. All models
having mathematical structure and can be solved by mathematical methods are known as
Analytical Models.

Simulation models: - The meaning of simulation is imitation. These models also have a
mathematical structure but are not solved by applying mathematical techniques to get a solution.
Instead, a simulation model is essentially a computer-assisted experimentation on a mathematical
structure of a real-life problem in order to describe and evaluate its behaviors under certain
assumptions over a period of time.

D. Classification Based on Nature of Environment

Deterministic models

All the decision models can be classified as either deterministic or probabilistic models. In
deterministic models your good decisions bring about good outcomes. You get that which you
expect, therefore the outcome is deterministic (i.e., risk-free). However, in probabilistic decision
models, the outcome is uncertain, therefore making good decisions may not necessarily produce
good outcomes.

Probabilistic Models

Unlike deterministic models where good decisions are judged by the outcome alone, in
probabilistic models, the decision maker is concerned with both the outcome value and the
amount of risk each decision carries. When the outcome of your decision is rather certain and all
the important consequences occur within a single period, then your decision problem is classified
as a deterministic decision. However, in many instances, these types of models are encumbered
with the two most difficult factors - uncertainty and delayed effects. Both difficulties can be
overcome by probabilistic modeling, which includes the time discounting factor
Haramaya University, Department of Management 11
 Operations Research

Advantages of Models

Models in general are used as an aid for analyzing complex problems. Specifically:
• A model provides economy in representation of the realities of the system. That is,
models help the decision-maker to visualize a system.
• The problem can be viewed in its entirety, with all the components being considered
simultaneously.
• A model provides logical and systematic approach to the problem.
• Models serve as aids to transmit ideas and visualization among people in the
organization.
• It provides the analyst a base for understanding the problem and think of methods of
solving.
• A model allows us to analyze and experiment in a complex situation to a degree that
would be impossible in the actual system and its environment.
• Models saves resources like money, time etc.
• Model helps analyst to make complexities of a real environment simple.
• Models help the analyst to find newer ways of solving the problem.
• Models simplify the investigation considerably and provide a powerful and flexible tool
for predicting the future state of the process or system.

Characteristics of a Good Model:

▪ Assumptions should be simple and few.

▪ Variables should be as less as possible.
▪ It should be able to assimilate the system environmental changes without change in its
framework.
▪ It should be easy to construct

1.7. Methodology of Operations Research

The decision-making approach in Operations Research has the following steps:

1. Problem Formulation

Haramaya University, Department of Management 12

 Operations Research

One has to study the system in all aspects, if necessary, make relevant assumptions, have the
decision for which he is constructing the model in mind and formulate the model. Problem
formulation involves an analysis of the system under study, the objective of the decision-maker,
and alternative courses of action, etc., so as to understand and describe, in precise terms, the
problem that an organization faces.

2. Model Construction

Here the decision maker has to abstract the most relevant variables from the empirical situation
for the model. Identify the main variables and constraints and relate them logically to arrive at a
model. After the problem is clearly defined and understood, the next step is to collect required
data and then formulate a mathematical model. Model construction consists of hypothesizing
relationships between variables subject to and not subject to control by decision-maker.

Certain basic components required in every decision problem model are:

a. Controllable (decision) variables: - These are the issues or factors in the problem whose
values are to be determined (in the form of numerical values) by solving the model. The
possible values assigned to these variables are called decision alternatives (strategies or
courses of action).

b. Uncontrollable variables: - These are the factors whose numerical value depends upon the
external environment prevailing in the organization. The values of these variables are not
under the control of the decision-maker and are also termed as state of nature.

c. Objective function: - is the goal or objective of a management stated as intent to maximize

or minimize some important quantity such as profits and costs. It is a representation of (i) the
criterion that expresses the decision-maker’s manner of evaluating the desirability of
alternative values of the decision variables, and (ii) how that criterion is to be optimized
(minimized or maximized).

d. Constraints (or Limitations): - These are the restrictions on the values of the decision
variables. These restrictions can arise due to limited resources such as space, money,
manpower, material, etc. The constraints may be in the form equations or inequalities.

Haramaya University, Department of Management 13

 Operations Research

e. Functional relationships: - In a decision problem, the decision variables in the objective

function and in the constraints are connected by a specific functional relationship.

3. Solving the Mathematical Model

Once a mathematical model of the problem has been formulated, the next step is to solve it, that
is, to obtain numerical values of decision variables. This implies determination of specific set of
decision variables that would yield a desired level of output (Optimum level). Solving the model
requires the use of various mathematical tools and numerical procedures. In general, the
following two categories of methods are used for solving an OR model.

i. Optimization Methods: - These methods yield the best values for the decision variables
both for unconstrained and constrained problems. In constrained problems, these values
simultaneously satisfy all the constraints and provide an optimal or acceptable value for the
objective function or measure of effectiveness.

ii. Heuristic Methods or Rule of thumb method: - These methods yield values of the
variables that satisfy all the constraints, but not necessarily provide optimal solution.
However, these values provide an acceptable value for the objective function.

4. Model Validation

Validation requires determining whether the model can adequately and reliably predict the
behaviour of the real system that it seeks to represent.

5. Implementing the Solution

6. Modifying the Model

Haramaya University, Department of Management 14

 Operations Research

Chapter Two

Linear Programming

Introduction

The application of specific operations research techniques to determine the choice among several
courses of action, so as to get an optimal value of the measures of effectiveness (objective or
goal), requires to formulate (or construct) a mathematical model. Such a model helps to represent
the essence of a system that is required for decision-analysis. The term formulation refers to the
process of converting the verbal description and numerical data into mathematical expressions,
which represents the relationship among relevant decision variables (or factors), objective and
restrictions (constraints) on the use of scarce resources (such as labor, material, machine, time,
warehouse space, capital, energy, etc.) to several competing activities (such as products, services,
jobs, new equipment, projects, etc.) on the basis of a given criterion of optimality. The term
scarce resources refer to resources that are not available in infinite quantity during the planning
period. The criterion of optimality is generally either performance, return on investment, profit,
cost, utility, time, distance and the like.

Linear Programming is a mathematical process that has been developed to help management in
decision making involving the efficient allocation of scares resources to achieve a certain
objective. The term programming used to identify this technique does not refer to computer
programming but rather to a predetermined set of mathematical steps used to solve a problem.

In general, linear programming models help managers determine solutions (i.e., make decisions)
for problems that will achieve some objective in which there are restrictions, such as limited
resources or a recipe or perhaps production guidelines. For example, you could actually develop
a linear programming model to help determine a breakfast menu for yourself that would meet
dietary guidelines you may have set, such as number of calories, fat content, and vitamin level,
while minimizing the cost of the breakfast. Manufacturing companies develop linear
programming models to help decide how many units of different products they should produce to
maximize their profit (or minimize their cost), given scarce resources such as capital, labor, and
facilities.

Haramaya University, Department of Management 15

 Operations Research

Diagrammatically,

Scares To be allocated to:

Resource

Resource
constraints
Objectives Constraints

Non-negativity
Constraints

Optimization

Maximization Minimization

2.1. Component of Linear Programming

a. Objective Function: is the goal or objective of a management stated as intent to maximize

or minimize some important quantity such as profits and costs. The objective (goal) function
of each LP problem is expressed in terms of decision variables to optimize the criterion of
optimality (also called the measure of performance) such as profit, cost, revenue, distance,
etc. In its general form it is expressed as:

Optimize (Maximize or Minimize) Z= C1 X 1 + C2 X 2 + .... + Cn X n

X 1, X 2, .... X n.
Where Z is the measure of performance variable, which is the function of
C1, C2, ....Cn
Quantities are parameters that represent the contribution of a unit of the respective
X 1, X 2, .... X n.
variables to the measures of performance Z.

b. Decision variables (Activities): - are physical quantities whose optimal numerical values
indicate the solution of the problem. We need to evaluate various alternatives (courses of

Haramaya University, Department of Management 16

 Operations Research

actions) for arriving at the optimal values of objective function. The evaluation of various
alternatives is guided by the nature of objective function and availability of resources. The
X 1, X 2, .... X n.
activities (also called the decision variables) are usually denoted by . The values
of these activities represent the extent to which each of these is performed. E.g. the number
of units of a product to manufacture by using limited resources such as personnel, machinery,
money, material, etc. In an LP model all decision variables are continuous, controllable, and

non-negative. i.e.
x1  0, x2  0,.... xn0.

c. Constraints: - are limitations or restrictions imposed by the operating environment. There

are always certain limitations (or constraints) on the use of resources, e.g. labor, Machine,
Raw material, space, money, etc. that limit the degree to which an objective can be achieved.
Such constraints must be expressed as linear equalities or inequalities in terms of decision
variables. The solution of an LP model must satisfy these constraints.

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

Non-negativity constraints: are constraints that require the decision variables can’t be negative
values

Assumptions in linear programming problems

Linearity also requires that the effects of the value of each variable on the values of the
objective function and the constraints are additive. In other words, there can be no interactions
between the effects of different activities; i.e., the level of activity X1 should not affect the costs
or benefits associated with the level of activity X2.
Haramaya University, Department of Management 17
 Operations Research

Certainty: -the various parameters, namely, the objective function’s coefficients, the
coefficients of the inequality/equality constraints and the constraint (resource) values are known
with certainty. The model assumes that the responses to the values of the variables are exactly
equal to the responses represented by the coefficients.

Divisibility:- the values of decision variables can be fractions. Sometimes these values only
make sense if they are integers; then we need an extension of linear programming called integer
programming.

Additivity:- the total profit in the objective function is determined by the sum of the profit
contributed by each of the products separately. Similarly, the total amount of a resource used is
equal to the sum of the resource values used by various activities.

Data:- formulating a linear program to solve a problem assumes that data are available to specify
the problem

2.2 Application Areas of LP Model

Linear programming is the most widely used technique of decision making in business and
industry and in various other fields.

i. Agricultural applications: in agricultural planning, e.g. allocation of limited resources

such as acreage, labor, and water supply, and working capital, etc.

ii. Military applications: such as selecting an air weapon against enemy, minimizing the
aviation gasoline, maximization of the tonnage of bombs dropped on a set of targets and
the problem of community defense against disaster.

iii. Production management: product mix, production planning, assembly line balancing,
blending problems, and so on.

iv. Financial management: like in portfolio selection, profit planning

v. Marketing management: like in media selection, traveling salesman problem, physical

distribution,

Haramaya University, Department of Management 18

 Operations Research

vi. Personnel management: Staffing problem, determination of equitable salaries, job

evaluation and selection.

2.3. Solution to Linear Programming Problems

The linear programming problems can be solved by

1. Graphic (Geographic) Method

2. Algebraic (Simplex) Method.

2.3.1 Graphical Solution

A Graphical solution method (for LP problems which involve only two decision variables), for
an optional as well as feasible solution to an LP problem is obtained by choosing from several
values of decision variables X1, X2, . . . Xn,- the set of values that satisfies the given set of
constraints simultaneously and also provides the optimum (maximum or minimum) value of a
given objective function. The technique used to identify optimal solution is called the graphical
solution approach or technique from an LP problem with two variables.

To use the graphic method, the following steps are needed:

• Identify the problem, i.e. the decision variables, the objective function and the
constraints.
• Draw a graph including all the constraints and identify the feasible region
• Obtain a point on the feasible region that optimizes the objective function- optimal
solution
• Interpret the results

NB. Graphical LP is a two-dimensional model.

Maximization Problem

Maximize Z with inequalities of constraints in < form

Haramaya University, Department of Management 19

 Operations Research

Example 1

Consider two models of color TV sets; Model A and B, are produced by a company to maximize
profit. The profit realized is $300 from A and $250 from set B. The limitations are

A. availability of only 40hrs of labor each day in the production department.

B. a daily availability of only 45 hrs. on machine time

C. ability to sale 12 set of model A.

Required: - How many sets of each model will be produced each day so that the total profit will
be as large as possible

Constraints Model A Model B Maximum Available hrs.

(X1) (X2)

Labor hr. 2 1 40

Machine hr. 1 3 45

Marketing hr. 1 0 12

Profit $300 $250

Solution

1. Formulation of mathematical modeling of LPP

Max Z=300X1 + 250X2

St:

2X1 +X2< 40
LPP Model
X1 +3X2< 45

X1 < 12

X1, X2 >0

Haramaya University, Department of Management 20

 Operations Research

2. Convert constraints inequalities into equalities

2X1 +X2 = 40

X1 +3X2 = 45

X1 = 12

3. Draw the graph by intercepts

2X1 +X2 = 40 ==> (0, 0) and (20, 0)

X1 +3X2= 45==> (0, 15) and (45, 0)

X1 = 12==> (12, 0)

X1, X2 = 0
2X1 +X2 = 40

X2
X1=0
40 X1=12

B
X1 +X2 = 45

15

Feasible C (12, 11)

Region X2=0
X1
D
A 12 20 45

4. Identify the feasible area of the solution which satisfies all constrains.

5. Identify the corner points in the feasible region

A (0, 0), B (0, 15), C (12, 11) and D (12, 0)

6. Identify the optimal point

7. Interpret the result

Haramaya University, Department of Management 21

 Operations Research

Corners Coordinates Max. Z = 300 X1 + 250X2

A (0, 0) $0

B (0, 15) $3750

C (12, 11) $6350

D (12, 0) $3600

Interpretation:

12 units of product A and 11 units of product B should be produced so that the total profit will be
$6350.

Example 2

A manufacturer of light weight mountain tents makes two types of tents, REGULAR tent and
SUPER tent. Each REGULAR tent requires 1 labor-hour from the cutting department and 3
labor-hours from the assembly department. Each SUPER tent requires 2 labor-hours from the
cutting department and 4 labor-hours from the assembly department. The maximum labor hours
available per week in the cutting department and the assembly department are 32 and 84
respectively. Moreover, the distributor, because of demand, will not take more than 12 SUPER
tents per week. The manufacturer sales each REGULAR tents for $160 and costs $110 per tent to
make. Whereas SUPER tent ales for $210 per tent and costs $130 per tent to make.

Required:

A. Formulate the mathematical model of the problem

B. Using the graphic method, determine how many of each tent the company should manufacture
each tent the company should manufacture each week so as to maximize its profit?

C. What is this maximum profit assuming that all the tents manufactured in each week are sold in
that week?

Haramaya University, Department of Management 22

 Operations Research

Solution

Department Regular (X1) Super (X2) Maximum labor-hours

available per week
Cutting department 1 2 32

Assembly department 3 4 84

Selling price per tent $160 $210

Cost per tent $110 $130

Profit per tent $50 $80

*The distributor will not take more than 12 SUPER tents per week. Thus, the manufacturer
should not produce more than 12 SUPER tents per week.

Let X1 =The No of REGULAR tents produced per week.

X2 =The No of SUPER tents produced per week.

X1 and X2 are called the decision variables

Max.Z = 50 X 1+80 X 2
St :
X 1+2 X 2 32 ……….Cutting department constraint

X 1+4 X 2 82 ……….Assembly department constraint

X 2  12
……….Demand constraint
LPP Model X1, X 2  0

……….Non-negativity constraints

Haramaya University, Department of Management 23

 Operations Research

Corners Coordinates Max Z=50 X1 + 800 X2

A (0, 0) $0

B (0, 12) $960

C (8, 12) $1360

D (20, 6) $1480

E (28, 0) $1400

Interpretation:

The manufacturer should produce and sale 20 REGULAR tents and 6 SUPERS tents to get a
maximum weekly profit of $1480.

Minimization Problem

Minimize Z with inequalities of constraints in > form

Example 1

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 machines vary in the amount of product
produced per hr., in the amount of labor used and in the cost of operation.

Haramaya University, Department of Management 24

 Operations Research

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

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 :
LPP Model
20 X 1+15 X 2 100
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)

Haramaya University, Department of Management 25

 Operations Research

Corners Coordinates Min Z = 25 X1 + 30X2

A (0, 20/3) 200

B (2.5, 3.33) 162.5

C (7.5, 0) 187.5

Conclusion

X1 =2.5, X2=3.33 and Min Z = 162.5

Example 2

A company owns two flour mills (A and B) which have different production capacities for
HIGH, MEDIUM and LOW grade flour. This company has entered contract supply flour to a
firm every week with 12, 8, and 24 quintals of HIGH, MEDIUM and LOW grade respectively.
It costs the Co. $1000 and $800 per day to run mill A and mill B respectively. On a day, mill A
produces 6, 2, and 4 quintals of HIGH, MEDIUM and LOW grade flour respectively.

Mill B produces 2, 2 and 12 quintals of HIGH, MEDIUM and LOW grade flour respectively.
How many days per week should each mill be operated in order to meet the contract order most
economically standardize? Solve graphically.

Solution

Minimum flour in

Mil A (X1) Mill B(X2) quintals

HIGH Capacity (in quintal) 6 2 12

MEDIUM Capacity (in quintal) 2 2 8

LOW Capacity (in quintal) 4 12 24

Cost $1000 $800

Haramaya University, Department of Management 26

 Operations Research

Mix.Z = 100X 1+800X 2

St :
6 X 1+2 X 2 12
2 X 1+2 X 2 8
4 X 1 + 12 X 2  24
X1, X 2  0

Constraint equation:

6 X 1+2 X 2= 12 (0, 6), (2, 0)

2 X 1+2 X 2= 8 (0, 4), (4, 0)
4 X 1 + 12 X 2 = 24 (0, 2), (6, 0)
X1, X 2 = 0

Corners Min Z = 1000 X1 + 800X2

(0, 6) $4800

(1, 3) $3400

(3, 1) $3800

(6, 0) $6000

Conclusion

X1 =1, X2=3 and Min Z= $3400

Haramaya University, Department of Management 27

 Operations Research

X2
X1 =0
6 6X1+2 X2=12
2X1+2 X2=8
4 FR
4X1+12 X2=24
(1, 3)
(3, 1)
X2 =0
X1
2 4 6

Note:

• In maximization problems, our point of interest is looking the furthest point from the
origin.
• In minimization problems, our point of interest is looking the point nearest to the origin.

2.4 Special Cases in Graphics Methods

1. Redundant Constraint

If a constraint when plotted on a graph doesn’t form part of the boundary making the feasible
region of the problem that constraint is said to be redundant.

Example

A firm is engaged in producing two products A and B. Each unit of product A requires 2Kg of
raw material and 4 labor hrs. for processing. Whereas each unit of product B requires 3Kg of raw
materials and 3hrs of labor. Every unit of product A requires 4 hrs. For packaging whereas B
needs 3.5hrs. Every week the firm has availability of 60Kg of raw material, 96 labor-hours and
105 hrs in the packaging department. 1 unit of product A sold yields $40 profit and 1 unit of B
sod yields $35 profit.

Required:

a. Formulate this problem as a LPP

Haramaya University, Department of Management 28

 Operations Research

b. Find the optimal solution through graphic method

Solution

Products Resource available

Resources A B per week

Raw materials (Kg) 2 3 60

Labor (hr.) 4 3 96

Packaging (hrhr.) 4 3.5 105

Profit per unit $40 $35

Let X1 =The No of units of product A produced per week

X2 =The No of units of product B produced per week

a. LPP Model

Max.Z = 40 X 1+35 X 2
St :
2 X 1+3 X 2 60
4 X 1+3 X 2 96
4 X 1 + 3.5 X 2  105
X1, X 2  0

X2

(0, 32)

Labor: 4X1 +3X2 = 96

(0, 30)
Packaging: 4X1 +3.5X2 = 105
(0, 20) C (18,8)
Raw material: 2X1 +3X2 = 60
FR
X1
A (0, 0) D (24, 0) (26, 0) (30, 0)

Haramaya University, Department of Management 29

 Operations Research

The packaging hr. is redundant.

Corners Coordinates Min Z = 40 X1 + 35X2

A (0, 0) 0

B (0, 20) 700

C (18, 8) 1000

D (24, 0) 960

X1 =18, X2=8 and Min Z = 1000

Interpretation:

The company should produce and sale 18 units of product A and 8 units of product B per week
so as to get a maximum profit of 1000.

By this production plan the entire raw material will be consumed.

2X1 +3X2 <60

2(18) +3(8) =60

60=60==> No idle or unused raw material

4X1 +3X2 <96

4(18) +3(8) <96

96=96 ==>the entire labor hour will be consumed

4X1 +3.5X2 <105

100<105==>There is to be idle or unused capacity of 5hrs in the packaging department.

Haramaya University, Department of Management 30

 Operations Research

Note:

The packaging hour’s constraint does not form part of the boundary making the feasible region.
Thus, this constraint is of no consequence and is therefore, redundant. The inclusion or exclusion
of a redundant constraint does not affect the optimal solution of the problem.

2. Multiple Optimal Solutions (Alternative Optimal Solutions)

This is a situation where by a LPP has more than one optimal solution. Multiple optimal
Solutions will be found if two corers give optimal solution, then the line segment joining these
points will be the solution. We have unlimited number of optimal solution without increasing or
decreasing the objective function.

Example

The information given below is for the products A and B.

Maximum available Machine

Department Product A Product B hours per week
Cutting 3 6 900

Assembly 1 1 200

Profit per unit $8 $16

Assume that the company has a marketing constraint on selling products B and therefore it can
sale a maximum of 125 units of this product.

Required:

a. Formulate the LPP of this problem

b. Find the optimal solution

Solution:

Let X1 = The No of units f product A produced per week

X2 = The No of units f product B produced per week

Haramaya University, Department of Management 31

 Operations Research

a. The LPP Model of the problem is:

Max.Z = 8 X 1+16 X 2
St :
3 X 1+6 X 2 900
X 1+ X 2 200
X 2  125
X1, X 2  0

X1=0
X2

(0, 200)

(0,150)
B (0, 125) C (50, 125)
D (100,100)

X2=0

X1
A (0, 0)
Corners Coordinates Max Z = 8 X1 + 16X2

A (0, 0) 0

B (0, 125) 2000

C (50, 125) 2400

D (100, 100) 2400

E (200, 100) 1600

Interpretation:

Haramaya University, Department of Management 32

 Operations Research

Both C and D are optimal solutions. Any point on the line segment CD will also lead to the same
optimal solution. Multiple optimal solutions provide more choices for management to reach their
objectives.

3. Infeasible Solution

A solution is called feasible if it satisfies all the constraints and the constraints and non-
negativity condition. However, it is sometimes possible that the constraints may be inconsistent
so that there is no feasible solution to the problem. Such a situation is called infeasibility.

Example

Max Z = 20X1+30X2
St: 2X1+X2< 40
4X1+X2< 60
X1 > 30
X1, X2 > 0

Solution

X2 X1=0
(0, 60) X1=30

(0, 40) 4X1+X2= 60

2X1+X2= 40 X2=0
X1

(15, 0) (20, 0) (30, 0)

Note:

Haramaya University, Department of Management 33

 Operations Research

• In the above graph, there is no common point in the shaded area.

• All constraints cannot be satisfied simultaneously and there is no feasible solution to the
problem.

4. Mixed Constraints

Example

ABC Gasoline Company has two refineries with different production capacities. Refinery A can
produce 4,000 gallons per day of SUPER UNLEADED GASOLINE, 2000 gallons per day of
REGULAR UNLEADED GASOLINE and 1000 gallons per day of LEADED GASOLINE. On the
other hand, refinery B can produce 1000 gallons per day of SUPER UNLEADED, 3000 gallons
per day of REGULAR UNLEADED and 4,000 gallons per day of LEADED. The company has
made a contract with an automobile manufacturer to provide 24000 gasoline of SUPER
UNLEADED, 42000 gallons of REGULAR UNLEADED and 36000 gallons of LEADED. The
automobile manufacturer wants delivery in not more than 14 days. The cost of running refinery
A is $1500 per day and refinery B is $2400 per day.

Required:

a. Formulate this problem as a LPP

b. Determine the number of days the gasoline company should operate each refinery in order
to meet the terms of the above contract most economically.
c. Which grade of gasoline would be over produced?

Solution:

Production per day (in gallons) Contract with an

Grade of gasoline A B automobile manufacturer
SUPER UNLEADED 4000 1000 24,000

REGULAR UNLEADED 2000 3000 42,000

LEADED 1000 4000 36,000

Haramaya University, Department of Management 34

 Operations Research

Running cost per day $1,500 $2,400

The automobile manufacturer wants delivery in not more than 14 days.

Let X1 =The No of days refinery A should work.

X2 =The No of days refinery B should work.

a. LPP of the problem

Min Z = 1500X1+2400X2
St: 4000X1+1000X2>24000
2000X1+3000X2>42000
1000X1+2000X2> 36000
X1 < 14
X2 < 14
X1, X2 > 0
==> To simplify the problem divide by 1000 the constraints

Min Z = 1500X1+2400X2
St: 4X1+1X2>24
2X1+3X2>42
X1+4X2 > 36
X1 < 14
X2< 14
X1, X2 > 0

Delivery time: X1=14

SUG: 4X1+X2 =24

A (2.5, 14) B (14, 14) Delivery time: X2=14

FSS

D (12, 6)

Haramaya University, Department

LG: X1+4X 2=36 of Management 35

RUG: 2X1+3X2 =42

(6, 0) (14, 0) (21, 0) (36, 0)

 Operations Research

Note: Point A, B, C, and D are solved by elimination-substitution method

Corners Coordinates Max Z = 1500X1 + 2400X2

A (2.5, 4) $37350

B (14, 14) 54600

C (14, 5.5) 34200

D (12, 6) 32400

E (3, 12) 33300

Interpretation:

The oil company should operate refinery A for 12 days and refinery B for 6 days at a minimum
operating cost of $32,400.

c. Is there any over production

SUG: 4000X1+1000X2 >24000

4000(12) +1000(6)>24000

54000 > 24000

Therefore, 30,000 gallons over production

RUG: 2000X1+3000X2>42000

2000(12) +3000(6)>42000

42000 > 42000

Therefore, there is no over production of RUG

LG: 1000X1+4000X2>36000
Haramaya University, Department of Management 36
 Operations Research

1000(12) +1000(6)>36000

36000 > 36000

Therefore, No over production of LG

5. Unbounded Solution

When the value of decision variables in LP is permitted to increase infinitely without violating
the feasibility condition, then the solution is said to be unbounded. Here, the objective function
value can also be increased infinitely. However, an unbounded feasible region may yield some
definite value of the objective function.

Example

Use the graphical method to solve the following LPP.

1. Max. Z = 3X1+4X2

St: X1-X2<-1==> -X1+X2>1 since the quantity solution is positive

-X1+X2<0

X1, X2 > 0

X2 X1-X2 =-1

X1+X2 =0

Fig: Unbounded Solution

1 Unbounded

Feasible Region

X1

Haramaya University, Department of Management 37

 Operations Research

2. Max. Z = 3X1+2X2

St:

X1-X2<1

X1+X2<3

X1, X2 > 0

X2

A(0,3) Unbounded

Feasible Region
X1-X2=1

B (2, 1)
X1+X2=3

X1

Note here that the two corners of the region are A (0,3) and B (2,1). The value of Max. Z (A) = 6
and Max. Z (B) = 8. But there exist number of points in the shaded region for which the value of
the objective function is more than 8. For example, the point (10, 12) lies in the region and the
function value at this point is 70 which is more than 8.

Remark:

An unbounded solution does not mean that there is no solution to the given LPP, but implies that
there exits an infinite number of solutions.

2.5 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 X1 and X2). In 19940’s George B. Dantzig developed an algebraic approach called
the Simplex Method which is an efficient approach to solve applied problems containing

Haramaya University, Department of Management 38

 Operations Research

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 solution each time until the optimal solution is reached at.

Note:

The simplex method starts with a corner that is in the solution space or feasible region and
moves to another corner of the solution space improving the value of the objective function each
time until optimal solution is reached at the optimal corner.

Scope of solution of LPP by simplex method

Following types of problems are solved by simplex method:

➢ Maximize Z with inequalities of constraints in “<” form.

➢ Minimize Z with inequalities of constraints in “>’’ form.

➢ Maximize Z with inequalities of constraints in “>” form.

➢ Maximize Z or Minimize Z with inequalities of constraints in “<”, “>”or “=”form.

Maximization Problems

➢ Maximize Z with inequalities of constraints in “< “form

Example 1

Solve the problem using the simplex approach

Max. Z = 300x1 +250x2

Subject to: 2x1 + x2 < 40 (Labor)

x1+3x2 < 45 (Machine)

x1 < 12 (Marketing)

x1, x2 > 0

Haramaya University, Department of Management 39

 Operations Research

Solution

Step 1፡ Formulate LPP Model

Step 2፡ Standardize the problem

i.e. Convert constraint inequality into equality form by introducing a variable called Sack
variable.

Slack Variables:

A sack variable(s) is added to the left-hand side of a < constraint to covert the constraint
inequality in to equality. The value of the slack variable shows unused resource.

A slake variable emerges when the LPP is a maximization problem.

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.

Let say that s1, s2 and s3 be unused labor, machine and marketing hours, respectively.

Max. Z=300x1 +250x2 + 0 s1 +0 s2+ 0 s3

St:

2 x1 + x2 + s1 +0 s2 + 0 s3 = 40

x1 + 3x2 +0s1 + s2 + 0 s3 = 45
Standard form
x1 + 0x2 + 0s1 + 0s2 + s3 = 12

x1, x2, s1, s2, s3 > 0

Step 3

Obtain the initial simplex tableau

To represent the data, the simplex method uses a table called the simplex table or the simplex
matrix.

Haramaya University, Department of Management 40

 Operations Research

==> In constructing the initial simplex tableau, the search for an optimal solution begins at the
origin. Indicating that nothing is produced;

Thus, first assumption, no production implies that x1 = 0 and x2 = 0

==>2 x1+x2 + s1 +0 s2+ 0 s3= 40 ==> x1+3x2 +0 s1 + s2+ 0 s3= 45

2(0) +0 + s1 +0 s2+ 0 s3= 40 0 +3(0) + 0s1 + s2+ 0 s3= 45

s1= 40 – Unused labor hrs. s2= 45 – Unused machine hrs.

==> x1+0s1 +0s2+ s3= 12

0 +0s1 +0 s2+ s3= 12

s3 = 12 – Unused Marketing hrs.

Therefore, Max. Z=300x1 +250x2 + 0 s1 +0 s2+ 0 s3

=300(0) +250(0) + 0(40) +0(45) + 0(12)

=0

Note:

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 are variables with non-zero solution values.

Or: basic variables are variables that are in the basic solution. Basic variables have 0 values in
the Cj-Zj row.

b. Non-basic variables are variables with zero solution values.

Or: non-basic variables are variables that are out of the solution.

==>n = 5 variables (x1, x2, s1, s2, and s3) and m = 3 constraints (Labor, machine and marketing
constraints), excluding non-negativity.

Haramaya University, Department of Management 41

 Operations Research

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
columns

Solution quantity
variables column
Basic or Solution

Real or decision
variable column
Profit per unit
column

column Profit per unit row

Cj 300 250 0 0 0

SV X1 X2 S1 S2 S3 Q Constraint
equation rows

0 S1 2 1 1 0 0 40 R1
Gross Profit row
0 S2 1 3 0 1 0 45 R2
Net Profit row
/Indicator row/
0 S3 1 0 0 0 1 12 R3

Zj 0 0 0 0 0 0

Cj - Zj 300 250 0 0 0

Haramaya University, Department of Management 42

 Operations Research

Step 4:

Choose the “incoming” or “entering” variables

Note:

The entering variable is the variable that has the most positive value in the Cj - Zj row also called
as indicator row. Or the entering variable is the variable that has the highest contribution to
profit per unit.

a. X1 in our case is the entering variable

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

==> In this step, we determine the variable that will leave the solution for X1 (or entering
variable)

Note:

• The row with the minimum or lowest positive (non-negative) replacement ratio shows
the variable to leave the solution.

Replacement Ratio (RR) = Solution Quantity (Q)

Corresponding values in pivot column

Note: RR > 0

• The variable leaving the solution is called leaving variable or outgoing variable.

• The row associated with the leaving variable is called key or pivot row (s3 row in our
case)

• The element that lies at the intersection of the pivot column and pivot row is called pivot
element (No 1 in our case)

Haramaya University, Department of Management 43

 Operations Research

Step 6:

Repeat step 3-5 till optimum basic feasible solution is obtained.

Or: repeat step 3-5 till no positive value occurs in the Cj - Zj row.

Note:

• Divide each element of the pivot row by the pivot element to find new values in the key
or pivot row.

• Perform row operations to make all other entries for the pivot column equal to zero.

2nd simplex tableau

Cj 300 250 0 0 0

SV X1 X2 S1 S2 S3 Q

0 S1 0 1 1 0 -2 16 R’1=R1-2R3

0 S2 0 3 0 1 -1 33 R’2=R2-R3

300 X1 1 0 0 0 1 12 R’3=R3

Zj 300 0 0 0 300 3600

Cj - Zj 0 250 0 0 -300

3rd simplex tableau

Cj 300 250 0 0 0

SV X1 X2 S1 S2 S3 Q

0 S1 0 0 1 -1/3 -5/3 5

250 X2 0 1 0 1/3 -1/3 11

300 X1 1 0 0 0 1 12

Haramaya University, Department of Management 44

 Operations Research

Zj 300 250 0 250/3 650/3 6350

Cj - Zj 0 0 0 -250/3 - 650/3

R’’1=R’1-R’2

R’’2=R2/3

R’’3=R’3

Since all the Cj - Zj < 0 optimal solution is reached at.

Therefore, X1=12, X2=11, S1=5 and Max Z=6350

Example 2

A Juice Company has available two kinds of food Juices: Orange Juice and Grape Juice. The
company produces two types of punches: Punch A and Punch B. One bottle of punch A requires
20 liters of Orange Juice and 5 liters of Grape Juice. 1 Bottle of punch B requires 10 liters of
Orange Juice and 15 liters of Grape Juice.

From each of bottle of Punch A a profit of $4 is made and from each bottle of Punch B a profit of
$3 is made. Suppose that the company has 230 liters of Orange Juice and 120 liters of Grape
Juice available

Required:

a. Formulate this problem as a LPP

b. How many bottles of Punch A and Punch B the company should produce in order to
maximize profit? (Using the simplex method)
c. What is this maximum profit?
Haramaya University, Department of Management 45
 Operations Research

Solution

Juice needed for one bottle of Juice Punch A Punch B Juice Available

Orange Juice (lt) 20 10 230

Grape Juice (lt) 5 15 120

Profit per tent $4 $3

Let X1= the No of bottles of punch A produced.

X2= the No of bottles of punch B produced.

LPP Model

Max. Z = 4X1 +3X2

St: 20X1 +10X2 < 230 Orange Constraint

5X1 +15X2 < 120 Grape Constraint

X1, X2 >0 Non-negativity constraint

Standard form

Max. Z = 4x1 +3x2 + 0 s1 +0 s2+ 0 s3

St: 20 x1+3x2 + s1 +0 s2 = 230

Standard form
5x1+15x2 +0s1 + s2+ = 120

x1, x2, s1, s2, >0

Where, s1 =Unused orange juice

s2 =Unused grape juice

Initial simplex tableau

Cj 4 3 0 0

Haramaya University, Department of Management 46

 Operations Research

SV X1 X2 S1 S2 Q

0 S1 20 10 1 0 230

0 S2 5 15 0 1 120

Zj 0 0 0 0 0

Cj - Zj 4 3 0 0

2nd simplex tableau

Cj 4 3 0 0

SV X1 X2 S1 S2 Q

4 X1 1 1/2 1/20 0 11.5

0 S2 0 25/2 -1/4 1 62.5

Zj 4 2 1/5 0 46

Cj - Zj 0 1 -1/5 0

Haramaya University, Department of Management 47

 Operations Research

Optimal simplex tableau

Cj 4 3 0 0

SV X1 X2 S1 S2 Q

4 X1 1 0 3/50 -1/25 9

0 X2 0 1 -1/50 2/25 5

Zj 4 3 0.12 0.08 51

Cj - Zj 0 0 - 0.12 -0.08

X1 = 9 bottles of punch A

X2 = 5 bottles of punch B

s1 = 0

s2 = 0

Max Z = $51

Minimization Problems

➢ Minimize Z with inequalities of constraints in “> “form

There are two methods to solve minimization LP problems:

1. Direct method/Big M-method/

➢ Using artificial variables

2. Conversion method

➢ Minimization by maximizing the dual

❖ Surplus Variable (-s):

Haramaya University, Department of Management 48

 Operations Research

➢ A variable inserted in a greater than or equal to constraint to create equality. It

represents the amount of resource usage above the minimum required usage.

➢ Surplus variable is subtracted from a > constraint in the process of converting the
constraint to standard form.

➢ Neither the slack nor the surplus is negative value. They must be positive or zero.

Example

1. 2x1+x2 < 40 ==>is a constraint inequality

x1 = 12 and x2= 11==> 2x1 + x2 + s = 40 ==>2(12) + 11 + s = 40

==> s = 5 unused resource

2. 5x1 + 3x2 < 45

x1= 12 and x2= 11==> 5x1+3x2+s = 45 ==>5 (12 )+ 3 (11) + s = 45

==> s=0 unused resource (No idle resource)

3. 5x1+2x2<20

x1= 4.5 and x2= 2==> 5x1+2x2- s = 20 ==>5(4.5)+2(2)-s = 20

==> s=6 unused resource

4. 2x1+x2 >40

x1= 0 and x2 = 0 (No production) ==> 5x1+2x2- s = 20 ==>5(4.5) + 2(2) -s = 20

==> s =-6 (This is mathematically unaccepted)

Thus, in order to avoid the mathematical contradiction, we have to add artificial variable (A)

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

Note:

Haramaya University, Department of Management 49

 Operations Research

Type of constrain To put into standard form

< Add a slack variable

= Add an artificial variable

> Subtract a surplus variable and add a slack variable

1. Big M-method

The Big-M Method (Charnes Penalty Method) is a method which is used in removing artificial
variables from the basis. In this method; we assign coefficients to artificial variables, undesirable
from the objective function point of view. If objective function Z is to be minimized, then a very
large positive price (called penalty) is assigned to each artificial variable. Similarly, if Z is to be
maximized, then a very large negative price (also called penalty) is assigned to each of these
variables.

Following are the characteristics of Big-M Method:

a. High penalty cost (or profit) is assumed as M

b. M is assigned as a coefficient to artificial variable A in the objective function Z.

c. Big-M method can be applied to minimization as well as maximization problems with the
following distinctions:

i. Minimization problems

Assign +M as coefficient of artificial variable A in the objective function Z

ii. Maximization problems:

Assign–M as coefficient of artificial variable A in the objective function Z

d. Coefficient of S (slack/surplus) takes zero values in the objective function Z

e. For minimization problem, the incoming variable corresponds to the highest negative
value of Cj-Zj.

f. Solution is optimal when there is no negative value of Cj-Zj.(For minimization case)

Haramaya University, Department of Management 50

 Operations Research

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

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

Cj 25 30 0 0 M M

SV X1 X2 S1 S2 A1 A2 Q

M A1 20 15 -1 0 1 0 100

Haramaya University, Department of Management 51

 Operations Research

M A2 2 3 0 -1 0 1 15

Zj 22M 18M -M -M M M 115 M

Cj - Zj 25 -22M 30- 18M M M 0 0

RR

100/20=5

15/2=7.5

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

Cj 25 30 0 0 M

SV X1 X2 S1 S2 A2 Q

25 X1 1 3/4 -1/20 0 0 5 R’1=R1/20

M A2 0 3/2 1/10 -1 1 5 R’2=R2-2 R’

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

Cj - Zj 0 45/4-3/2M 5/4-1/10 M M 0

Cj 25 30 0 0

SV X1 X2 S1 S2 Q

Haramaya University, Department of Management 52

 Operations Research

25 X1 1 0 -1/10 1/2 5/2 3rd Simplex Tableau

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

Zj 25 30 -1/2 -15/2 162.5

Cj - Zj 0 0 1/2 15/2
R’’1=R’1-3/4 R’’2

R’’2=R’2/3/2

Cj - Zj > 0==>Optimal solution is reached

X1=5/ , X2=10/3 and Min. Z = 162.5

Note:

As long as an “A” variable is available in the solution variable column, the solution is infeasible.

Example 2

Use the penalty (Big-M) method to solve the following LPP

Min Z=5x1 +3x2

Subject to: 2x1+4x2 < 12

2x1+ 2x2 = 10

5x1+ 2x2 > 10

x1, x2 > 0

Haramaya University, Department of Management 53

 Operations Research

Solution

Min Z = 5x1 +3x2 +0s1+0s2 +MA1+MA2

Subject to: If no production

2x1+4x2+s1 = 12 ==>x1 =x2=0==>s1=0 (Solution Value in the initial simplex tableau)

2x1+2x2 +A1 =10 ==>x1 =x2=0==>A1 =15 (Solution Value in the initial simplex tableau)

5x1+2x2 –s2 +A1=10 ==>x1=x2=s2=0==>A2=10(Solution Value in the initial simplex tableau)

x1, x2 , s1, s2 ,A1 ,A2 > 0

Initial Simplex tableau

Cj 5 3 0 0 M M
RR

SV X1 X2 S1 S2 A1 A2 Q

06 S1 2 4 1 0 0 0 12

M5 A1 2 2 0 0 1 0 10

M2 A2 5 2 0 -1 0 1 10

Zj 7M 4M 0 M M M 20 M

Cj - Zj 5 -7M 3- 4M 0 -M 0 0

Haramaya University, Department of Management 54

 Operations Research

2nd simplex tableau

Cj 5 3 0 0 M

SV X1 X2 S1 S2 A1 Q

0 S1 0 16/5 1 2/5 0 8

M A1 0 6/5 0 2/5 1 6

5 X1 1 2/5 0 -1/5 0 2

Zj 5M 6/5M +2 0 2/5M -1 M 10+6 M

Cj - Zj 0 -6/5M +1 0 -2/5M+1 0

3rd simplex tableau

Cj 5 3 0 0 M

RR
SV X1 X2 S1 S2 A1 Q
20
3 X2 0 1 5/16 1/8 0 2.5

M A1 0 0 -3/8 1/4 1 3 12

5 X1 0 0 -1/8 -1/4 0 1 -

Zj 5 3 -3/8M +5/6 M/4-7/8 M 12.5+3 M

C j - Zj 0 0 3/8M -5/6 -M/4+7/8 0

Haramaya University, Department of Management 55

 Operations Research

4th Simplex tableau

Cj 5 3 0 0

SV X1 X2 S1 S2 Q

3 X2 0 1 1/2 0 1

0 S2 0 0 -3/2 1 12

5 X1 0 0 -1/2 0 4

Zj 5 3 -1 0 23

Cj - Zj 0 0 1 0

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

Example 3

Use the penalty (Big-M) method to solve the following LPP

Max Z=2x1 +x2+3x3

Subject to: 2x1+ x2 + x3 < 5
2x1+ 3x2 +4x3 = 12
x1, x2, x3 > 0

Haramaya University, Department of Management 56

 Operations Research

Solution

Initial Simplex tableau

Cj 2 1 3 0 -M

SV X1 X2 X3 S1 A1 Q
RR

0 S1 1 1 2 1 0 5

-M A1 2 3 4 0 1 12
2.5
Zj -2M -3M -4M 0 -M -12 M

Cj - Zj 2M+2 3M+1 4M+3 0 0

3
2nd simplex tableau

Cj 2 1 3 0

SV X1 X2 X3 S1 A1 Q
RR
3 X3 1/2 1/2 1 1 0 5
5
-M A1 2 3 4 0 1 12

Zj 3/2 -M +3/2 3 2M+3/2 -M -2M+15/2

2
Cj - Zj 1/22 M-1/2 0 -2M-3/2 0

Haramaya University, Department of Management 57

 Operations Research

3rd simplex tableau

Cj 2 1 3 0

SV X1 X2 X3 S1 Q
RR

3 X3 1/2 0 1 3/2 1.5

1 X2 0 1 0 -2 2 6

Zj 3/2 1 3 5/2 13/2

Cj - Zj 1/2 0 0 -5/2 Not defined

4th simplex tableau

Cj 2 1 3 0

SV X1 X2 X3 S1 Q
Cj - Zj < 0 ==> optimal
3 X1 1 0 2 3 3
solution
1 X2 0 1 0 -2 2
X1=3, X2 =2, X3=0, S1=0 and
Zj 2 1 4 4 8 Max Z=8

Cj - Zj 0 0 -1 -4

2.5 Special Cases in Simplex Method

1. Mixed Constraints

Example

Max. Z = 6x1 + 8x2

Subject to: x2 < 4

Haramaya University, Department of Management 58

 Operations Research

x1 + x2 = 9

6x1+ 2x2 >24

x1, x2 >0

Standard form

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

Initial simplex tableau

Cj 6 8 0 0 -M -M

SV X1 X2 S1 S3 A2 A3 Q

0 S1 0 1 1 0 0 0 4

-M A2 1 1 0 0 1 0 9

-M A3 6 2 0 -1 0 1 4

Zj -7M -3M 0 +M -M -M 24

Cj - Zj 7M +6 3M+8 0 -M 0 0
Ans:
At the 4th tableau: X1 = 5, X2 = 4, S3 = 14 and Max. Z = 62

Note:

Haramaya University, Department of Management 59

 Operations Research

For the initial basis, use artificial variables for constraints that have them. Otherwise, use a
constraint slack variable. Hence, surplus variables will not appear in an initial solution.

2. Two incoming variables/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:

Cj

SV X1 X2 S1 S3 Q

Zj

Cj - Zj 5 2 5 0

In such a case, X1 is the entering variable

3. Infeasibility

Haramaya University, Department of Management 60

 Operations Research

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
Cj - Zj 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

Cj 5 8 0 0 M

SV X1 X2 S1 S2 A2 Q

5 X1 1 1 -2 3 0 200

8 X2 0 1 1 2 0 100

M A2 0 0 0 -1 1 20

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

Cj - Zj 0 0 2 M-31 0

Even though all Cj - Zj are positive or 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.

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

Haramaya University, Department of Management 61

 Operations Research

The procedure in unbounded solution is to divide each quantity column number by the
corresponding pivot column number. 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

Cj 6 9 0 0
RR

SV X1 X2 S1 S2 Q

9 X2 -1 1 2 0 30 30/-1=-30

Unacceptable RRs
0 S2 -2 0 -1 1 10
10/-2=-5

Zj -9 9 18 0 270

Cj - Zj 15 0 -18 0

Pivot Column

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

• No unbounded solutions, no outgoing variable will exist.

5. 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. Problem can be overcome by trial and
error method.

Haramaya University, Department of Management 62

 Operations Research

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.

Cj 5 8 2 0 0 0

SV X1 X2 X3 S1 S2 S3 Q RR

8 X2 1/4 1 1 -2 0 0 10 10/1/4=40

0 S2 4 0 1/3 -1 1 0 20
20/4=5 Tie for the smallest ratio
0 S3 2 0 2 2/5 0 1 10 indicates degeneracy.

Zj 2 8 8 16 0 0 80 10/2=5

Cj - Zj 3 0 -6 -16 0 0

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.

6. Multiple Optimal Solutions

Multiple optimal solutions exist when non-basic variable contains zero on its Cj - Zj row.

Example:

Maximization problem

Haramaya University, Department of Management 63

 Operations Research

Cj 3 2 0 0

SV X1 X2 S1 S2 Q

2 X2 3/2 1 1 0 6

0 S2 1 0 1/2 1 3

Zj 3 2 2 0 12

Cj - Zj 0 0 -2 0

Max. Z = 3X1 + 2X2

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

The Cj - Zj value of the Non-basic variable (X1) is [Link], there is alternative optimal solution.

Haramaya University, Department of Management 64

 Operations Research

Chapter Three

Transportation and Assignment Problem

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 requirements.
The transportation model is usually applied to distribution type of problems in which supplies of
goods that are held at various locations are to be distributed to the other receiving locations. The
structure of transportation problem involves a large number of shipping routes from several
supply origins to several demand destinations.

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. Both transportation and assignment problems are members of a category of linear
programming techniques called network flow problems. Transportation problem deals with the
distribution of goods from several points of supplies (sources) to a number of points of demands
(destinations).

Consider a corporation engaged in the manufacture of products. Most of such big corporations
are of “multiple-product” and “multi-unit” organizations having production units situated at
different places. Items are produced for sales. Sales take place at different markets which are,
again located at different places. It is not feasible to co-locate production and market. Markets
are located away from the manufacturing places. Hence products are sent to factory warehouses
set up near market outlets. Cost of product consists of production cost and distribution cost.

Cost of product = production cost + distribution cost

Distribution cost consists of mainly the transportation cost of items from its production
(manufacturing) center to the warehouses. Transportation techniques are designed to minimize
the distribution costs. In order to identify products, it is necessary to workout per unit

Haramaya University, Department of Management 65

 Operations Research

distribution cost of each product. We also know the production capacity of each product in each
factory is not fixed. The holding capacity of a warehouse or potential sales in each marketing
center is again a fixed quality which cannot be exceeded.

The characteristics of transportation problem are as follows:

• A limited supply of one commodity is available at certain sources or origins.
• There is a demand for the commodity at several destinations
• The quantities of supply at each source and the demand at each destination are constant.
• The shipping or transportation costs per unit from each source to each destination are
assumed to be constant.
• No shipments are allowed between sources or between destinations. All supply and
demand quantities are given in whole number or integers.
• 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.

Uses of transportation techniques:

• Reduce distribution or transportation cost
• Improve competitiveness of product
• Assist proper location of warehouses
• Assist proper location of new factories or plants being planned.
• Close down warehouses which are found costly and uneconomical.

The objective of transportation problem is:

• To identify the optimal shipping routes-minimum cost route
• To identify the maximum amount that can be shipped over the optimum route
• To determine the total transformation cost or the profit of transportation

Information required to develop transportation model

It involves a set of sending locations which are referred to as origins and a set of receiving
locations which are referred to as destinations. The required information are:

• Supply quantity (capacity) of each origin

• Demand quantity of each destination
Haramaya University, Department of Management 66
 Operations Research

• Unit transportation cost for each route.

Assumptions of transportation problems

• All goods should be homogeneous/ Product homogeneity

• Equality between the total supply size and the total demand requirement within a specified
period of time.
• Linearity between the unit transportation cost and the total cost of transportation.

Steps to Solve Transportation problem

The solution algorithm to a transportation problem may be summarized into the following steps:

Step 1: Formulate the problem and set up in the matrix form

The formulation of the problem is similar to the linear programming. Here the objective function
is the total transportation cost and the constraints are the supply and demand available at each
source and destination respectively.

Step 2: Obtain an Initial Basic Feasible Solution

There are 3 methods to find the initial feasible solution.

1. North-West Corner Method (NWCM)
2. Least Cost Method (LCM)
3. Vogel’s Approximation Method (VAM)

The initial solution obtained by any of the three methods must satisfy the following condition:
i. The solution must be feasible
It must satisfy all the supply and demand constraints
ii. The number of positive allocations must equal to m+n-1, where m=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).

Note:
Haramaya University, Department of Management 67
 Operations Research

If the number of occupied cells < m+n-1==> degenerate solution will result in.
Step 3. Test the initial solution for optimality

Testing for optimality can be made using three approaches:

i. Stepping stone approach
ii. Modified distribution method

If the current solution is optimal, then stop. Otherwise, determine the new improved solution.
Step 4 Repeat step 3 until an optimal solution is reached

Linear programming formulation of the transportation problem

Example

Suppose 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:

Destinations (dd) =j

Origin Factory
W1 W2 W3 W4
(Supply) Capacity =i
Br.3 2 7 6
F1 5000

F2 7 5 2 3 6000

F3 2 5 4 5 2500
Requirements of the
Warehouses 6000 4000 2000 1500 13500
( Units of demand)

Using all the above information

i. Express the following transportation problem as an LPP

Haramaya University, Department of Management 68

 Operations Research

Solution

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:

Min. Z = 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 =6000 F2 supply constraint
x31 +x32 +x33+x34 = 2500 F3 supply constraint
b. Demand constraints:
x11 + x21 + x31 = 6000 W1 demand constraint
x12 + x22 + x32 = 4000 W2 demand constraint
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.

Haramaya University, Department of Management 69

 Operations Research

ii. The network representation of the transportation LPP is called Net work flow
Origin Destination centers
(Sources of Supply) (Point of demand centers)

3
F1 50000 W1 6000
2
6 7

F2 6000 5 W2 4000
2
3

W3 2000
2 5
4

F3 2500 5 W4 1500

This LPP has 12 shipping routes. The objective is to identify the minimum cost route (Least cost
route).

3.2. Methods of Finding Initial Feasible Solution

Feasible solution: - is one in which assignments are made in such a way that all supply and
demand requirements are satisfied.

The number of occupied cells should equal one less than the sum of the number of rows and the
number of columns in a transportation table.

Number of Occupied cells = m+n -1

Where, m = number of rows (origins)

n = number of columns (destinations

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:

Haramaya University, Department of Management 70

 Operations Research

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:

• 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.
• Subtract from the row supply & from the column demand the amount allocated
• If the column demand is now 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.
• Once a cell is identified as per step (3), it becomes a northwest cell. Allocate to it an
amount as per step (1)
• Repeat, the above steps (1) - (4) until all the remaining supply and demand is gone

Example:

1) Consider the following transportation problem:

To Supply
Store 1 Store 2 Store 3 Store 4
From
m
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
a. Develop an initial feasible solution using the NWCM
b. Compute the total cost for this solution.

Haramaya University, Department of Management 71

 Operations Research

Solution

a. Table: Initial feasible solution

To
Store 1 Store 2 Store 3 Store 4 Supply
From

Plant 1 19 30 50 10
7
5 2
70 30 40 60
Plant 2 9
6 3
40 8 70 20
Plant 3 18
4 14
Demand 5 8 7 14 34

Check that the solution is feasible or not:

==>m + n-1; m=3 and n=4  3+4-1= 6 cells occupied (Feasible solution)
The total transportation cost of the initial feasible solution derived by the NWCM is:

Route Unit Per unit Total

From To Shipped X 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.

Note:

Haramaya University, Department of Management 72

 Operations Research

1. Total Supply= Total demand ===> Balanced TP

2. Total Supply ≠ total demand ===> Unbalanced TP
3. Convert the unbalanced TP into a balanced TP by using dummy destination/dummy source.
* If total Supply > Total demand, then create a fictitious or artificial destination called dummy
destination

i.e.: total Supply > Total demand===> Add dummy column

• Excess demand (Supply < demand)
• Add a dummy source
• Add a dummy row

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

Example

Develop an initial feasible solution using NWCM

Table: Unbalanced transportation table

R S T Supply
A 1 2 3 100
B 4 1 5 110

Demand 80 120 60 210

260

Solution:
R S T Supply
1 2 3
A 100
80 20
4 1 5
B 110
100 10
0 0 0
Dummy 50
50
Demand 80 120 60 260
X11=80, X12=20, X22=100, X23=10, X33=50 Total cost =$270

Haramaya University, Department of Management 73

 Operations Research

B. The Least- Cost Method (LCM) or (Largest- Profit) Method

LCM is the method used a minimum cost in the allocation. It begins a solution by sequentially
assigning to the ratios or cells with the minimum cost as many units as possible. The first
allocation be made to the cell with the lowest cost (the highest profit in a maximization case).
The Least- Cost Method yields not only an initial feasible solution but also one that is close to
optimal in small problems.

Example 1

Suppose that a firm has three factories /sources of supply/ and 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:

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 and Compute the total cost
b. Develop an initial feasible solution using least-cost method & compute the total cost.

Haramaya University, Department of Management 74

 Operations Research

Solution
a. Initial feasible solution through NWCM
Factory
W1 W2 W3 W4 Capacity
3 2 7 6
F1 5000
5000
Factory 7 5 2 3
F2 6000
1000 4000 1000
2 5 4 5
F3 2500
1000 1500
Demand 6000 4000 2000 1500 13500

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

Routes Units Unit Total

From To Shipped Cost Cost
F1 W1 X 3 $ 15000
F2 W1 5000 7 7000
F2 W2 1000 5 20000
F2 W3 4000 2 2000
F3 W3 1000 4 4000
F3 W4 1000 5 7500
1500 Total transportation cost =$55,500

Haramaya University, Department of Management 75

 Operations Research

b. Initial feasible solution through LCM

Factory
W1 W2 W3 W4 Capacity
3 2 7 6
F1 5000
1000 4000
Factory
7 5 2 3
F2 6000
2500 2000 1500
2 5 4 5
F3 2500
2500
Demand 6000 4000 2000 1500 13500

Routes Units Unit Total

From To Shipped Cost Cost
F1 W1 X 3 $ 3000
F1 W2 1000 2 8000
F2 W1 4000 7 17500
F2 W3 2500 2 4000
F2 W4 2000 3 45000
F3 W1 1500 2 5000
2500 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.

Haramaya University, Department of Management 76

 Operations Research

Example 2

Develop the initial feasible solution for the following TP using the least-cost method (LCM)

Destination
D E F G Supply
Source
A 1 5 3 4 100
B 4 2 2 5 60
C 3 1 2 4 120
Demand 70 50 100 60 280

Solution

The 1st allocation should be made to the cell with the least-cost. Cells AD and CD both have the
lowest cost of $1. Cell AD is selected 1st because more units can be allocated to it (70) than to
cell CE (50). Cell CF is filled in 1st since a larger quantity (120-50-70) can be placed there.
Then, the remaining requirement of 30 for column F is allocated to cell BF & source B's supply
is reduced to 30.
The initial solution by the least -cost method
To
From D E F G Supply
A 1 5 3 4 100
70
B 4 2 2 5 60
30 30
C 3 1 2 4 120
50 70
demand 70 50 100 60 280

Haramaya University, Department of Management 77

 Operations Research

Routes Units Unit Total

From To Shipped Cost Cost
A D X 1 $ 70
B F 70 2 60
B G 30 5 150
C E 30 1 50
C F 50 2 140
70 Total transportation cost =$470

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

Example 3

Develop an initial feasible solution using LCM

R S T Supply
A 1 2 3 100
B 4 1 5 110
Demand 80 120 60

Solution

R S T Supply
A 1 2 3 100
80 10 10
B 4 1 5 110
110
Dummy 0 0 0 50
50
Demand 80 120 60

Total transportation cost=80x1+10x2+10x3+110x1+50x0=$240

Haramaya University, Department of Management 78

 Operations Research

C. Vogel's Approximation Method (VAM) Or Penalty Method

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, it 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 and demand at
various destinations are satisfied.

Haramaya University, Department of Management 79

 Operations Research

Example 1

Determine an initial basic feasible solution to the following transportation problem using VAM.

Warehouse
Row difference or Row penalty
A B C D Supply
or opportunity cost
F1 2 2 0 4
25 2 0 - - -
5 20
F2 5 9 8 3
Factory 25
15 5 5 2 2 2 2 5

F3 6 4 3 2
10
10
Demand 20 15 20 5 60 1 2 2 - -

Column difference 3 2 3 1

or Column penalty

or opportunity cost 3 2 - 1

1 5 - 1

m= 3, n=4 ==> 3+4-1 =6 Occupied cells (feasible)

5 9 - -
The transportation cost associated with this solution is:

5 - - -
Total cost= 5x2 + 20x0+15x5x9 =+95x3+10x4= $185

Example 2

A dairy firm has three plants located in different regions. The daily milk production at each plant
is as follows:

Plant 1: 6 million liters.

Plant 2: 1 million liters, &

Plant 3: 10 million liters

Each day the firm must fulfill the needs of its four distribution centers. Minimum requirement at
each center is as follows.

Haramaya University, Department of Management 80

 Operations Research

Distribution center 1: 7 million liters

" " 2: 5 " "

" " 3: 3 " "
" " 4: 2 " "

Cost of shipping one million liters form each plant to each distribution center is given in the
following table in hundreds of dollar.

Distribution Center

D1 D2 D3 D4
P1 2 3 11 7
Plant
P2 1 0 6 1
P3 5 8 15 9
Find the initial basic feasible solution by:
a. North-west corners method
b. LCM
c. VAM if the object is to minimize the total transportation cost

Solution

a. Total cost = $11, 600

b. Total cost= $11,200
c. VAM
D1 D2 D3 D4 Supply Row Penalty
P1 2 3 11 7 6 1 1 5 -
P2 1 0 6 1 1 1 - - -
P3 5 8 15 9 10 3 3 4 4
Demand 7 5 3 2
Column Penalty
7 5 3 2
1 3 5 6
3 5 4 2
3 - 4 2
5 - 15 9

Haramaya University, Department of Management 81

 Operations Research

m+n -1 +3+4-1 =6 ==>the solution is non-degenerate.

The total transportation cost=$(1x2+5x3+1x1+6x5+3x15+1x9) x100 = $ 10,200

3.3 Optimality Tests

Once an initial solution is available, the next step is to check its optimality. An optimal solution
is one in which there is no opportunity cost. That is, there is no other set of transportation routes
(allocations) that will reduce the total opportunity cost. Thus, we have to evaluate each
unoccupied cell (represents unused route) in the transportation table in terms of opportunity cost.
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 and 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. A favorable change means an increase in the value of the
objective function in maximization problems or a decrease in minimization problems.

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 stopping- 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:

Haramaya University, Department of Management 82

 Operations Research

The No of occupied routes (or squares) must always be equal 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.

2. Beginning at that 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.
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 (for minimization problems). 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.

Haramaya University, Department of Management 83

 Operations Research

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.

1. The test of optimality for a minimization (cost) problem:

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.
b. Design an improved solution - By shifting units form cell to cell

2. The test of optimality for a maximization (profit) case:

It is the reversed of minimization case. If one or more of the cell evaluators is positive, the
existing solution is not optimal. i.e.: for a maximization (profit) case, all the cell evaluators must
be negative for optimality. If any cell evaluation is positive, the solution is not optimal.

Note:

• A cell evaluator of 0 indicates the existence of another solution just as good as the current
solution. Thus, in the final solution, if cell evaluators of 0 exist, this indicates the
existence of multiple optimal solutions.

• If two or more cells have the same value, then either may be selected.

• If two or more of the "losing" cells contain the same no of units, both will become empty
simultaneously and a “degenerate" solution will result.

Haramaya University, Department of Management 84

 Operations Research

• For the minimization case; when one or more cell evaluators are negatives, the cell with
the largest negative should be brought into solution because that route has the largest
potential for improvement per unit.

• The loop starts and ends at the selected unoccupied cell. Every corner element of the
loop must be an occupied cell.

Example 1

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

Project A Project B Project C ss

F1 4 2 8 100
Farm

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

Initial feasible solution

Project A Project B Project C ss

F1 4 2 8 100
50 50
F2 5 1 9 200
100 100
F3 7 6 3 200
200
dd 50 150 300 500

m=3, n=3==> 3+3-1=5(non-degenerate solution)

Total transportation cost = $[50x4+50x2+100x1+100x9+200x3] = $1900

Haramaya University, Department of Management 85

 Operations Research

Evaluation path for the unoccupied cells

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

Project A Project B Project C SS
cell (F1, C) is
F1 4 2 8 100
50 50 - +
F2 5 1 9 200
100 + 100-
F3 7 6 3 200
200
DD 50 150 300 500

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:

Haramaya University, Department of Management 86

 Operations Research

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.

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 3 200
200
dd 50 150 300 500

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

Example 2

Consider the following TP

Destination
R S T ss
Origin

A 1 2 3 100

Haramaya University, Department of Management 87

 Operations Research

B 4 1 5 110
210
dd 80 120 60
260

a. Obtain the basic feasible solution using VAM

b. Obtain the optimal solution
c. What is the optimal shipping cost?

Solution

a. Initial feasible solution

To
R S T ss Opportunity cost
1 2 3 100
A
80 10 10 1 1 1 1
From

B 4 1 5 110
Dummy 0 1100 0 50
3 3 - -
dd 80 120 60 260
Opportunity 1 1 3 0 - - -

3 1 2

cost 1 2 3
Note: Include the dummy
1 cells
2 to select
- the opportunity cost under VAM problems.
b. Test of optimality.
Table: Test of optimality

Unoccupied cells Cell evaluators

(B,R) +4-1+2-1= +4

(B,T) +5-1+2-3= +3

(D,R) +0-1+3-0= +2

(D,S) +0-2+3-0= +1

Haramaya University, Department of Management 88

 Operations Research

Since none of the cell evaluators is negative, the above feasible solution is optimal. Thus,
accordingly the distribution is as follows:

• A Supplies 80 units to warehouse R

• B Supplies 10 units to warehouse S
• C Supplies 10 units to warehouse T
• B Supplies 110 units to warehouse S

c. The total optimal shipping cost is = $240

B. Modified Distribution Method (MODI Method)

It is another logarithm to test the transportation solution for optimality. 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. 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

Cij = Ui + Vj 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.

Where Kij is the cell evaluator or opportunity cost

3. Examine the sign of each Kij

For minimization case:

Haramaya University, Department of Management 89

 Operations Research

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

Example 1

Obtain an optimal solution to the transportation problem by MODI method given below:

Project No 1 Project No 2 Project No 3 Supply

Farm 1 4 2 8 100

Haramaya University, Department of Management 90

 Operations Research

Farm 2 5 1 9 200
Farm 3 7 6 3 200
Demand 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 No 1 Project No 2 Project No 3 Supply Ui

4 2 8 100
Farm 1 U1=0
50
5 1 9 200
Farm 2 U2=1
100 100
7 6 3 200
Farm 3 U3=-7
200
Demand 50 150 300 500
Vj V1=4 V2=2 V3=10

To determine Cij , use the occupied cells.

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

Haramaya University, Department of Management 91

 Operations Research

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

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 +V1)=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:

Project No 1 Project No 2 Project No 3 Supply

4 2 8 100
Farm 1
50 50
5 1 9 200
Farm 2
100 100
7 6 3 200
Farm 3
200
Demand 50 150 300 500

The distribution plan after reallocation of 50 units is:

Haramaya University, Department of Management 92

 Operations Research

Project No Project No Project No Supply Ui

1 2 3
4 2 8 100
Farm 1 U1=0
50 50
Cij = Ui + 5 - 1+ 9 200 Vj
Farm 2 U2=1
==>C11= + 100 100 - U1
7 6 3 200
Farm 3 U3=-5
200
Demand 50 150 300 500
Vj V1=4 V2=0 V3=8

+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

Special Cases in Transportation Problem

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

Haramaya University, Department of Management 93

 Operations Research

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

In a minimization transportation problem, allocate the smallest transportation cost to .. In a

maximization transportation problem, it should be allocated to a cell that has a high pay off
value. Insert  when it is able to create a closed loop for each occupied cell. The purpose of
epsilon/delta is to enable evaluation of the remaining empty cells. The choice of location for the
epsilon/delta can be somewhat tricky: some empty cells may be unsuitable if they do not enable
evaluations of remaining empty cells. Not all choices would be acceptable. Actually, the No of
epsilon/deltas needed will equal the difference between the No of completed cells and m+n-1.
However, you will only be exposed to the most common case in which one more completed cell
is needed. The epsilon/delta cannot be placed in a cell which later turns out to be in a negative
position of a cell path involved in reallocation because epsilon/delta will be the “smallest
quantity a negative position and shifting that minute quantity around the cell path will leave the
solution virtually unchanged. Consequently, a certain amount of trial and error may be necessary
before a satisfactory location can be identified for epsilon/delta.

Example

Solve the following transportation problem.

1 2 Supply
1 3 3 50

Haramaya University, Department of Management 94

 Operations Research

2 4 6 30
Demand 50 30 80

Solution

Using NWCM and MODI, the initial solution is:

1 2 Supply Ui

3 3
1 50 U1=0
50 
4 6
2 30 U2=3
30
Demand 50 30 80
Vj V1=3 V2=3

Cij= Ui + Vj
==>C11= U1 +V1==>3=0+ V1==> V1=3, U1=0 by convention
==>C12= U1 +V2==>3=0 +V2==> V2=3
==>C22= U2 +V2==>6= U2+3==> U2= 3
==>C33= U3 +V3==>3= U3+8 ==> U3= -5
Note: m=2 and n=2==>2+2-1=3==>Occupied cells=2< 3 (Degeneracy)

Table: Test of optimality

Unoccupied cell Cell evaluator

Kij = Cij– (Ui + Vj)
(2, 1) C21 – (U2 +V1)=4-(3+3) =-2

Haramaya University, Department of Management 95

 Operations Research

The optimal solution is:

1 2 Supply Ui
3 3
1 50 U1=0
50 30
4 6
Cij= Ui 2 30 U2=1 + Vj
30

Demand 50 30 80

Vj V1=3 V2=3

==>C11=U1+V1==>3=0+V1==>V1=3, U1=0 by convention

==>C21= U2+V1==>4= U2+3==> U2=3
==>C12= U1 +V2==>3= 0+ V2==> V2= 3

Table: Test of optimality

Unoccupied cells Cell evaluators

Kij = Cij– (Ui + Vj)
(2, 2) C22– (U2 +V2)=6-(1+3)= +2

The total cost= $(20x3+30x3+30x40=$270

2. Alternative Optimal Solutions

The resistance of alternative optimal solution can be determined by an inspection of the

opportunity costs, Kij 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.

3. Prohibited Transportation Routes

The situation may arise such as road hazards (snow, foods, etc.), traffic regulation etc., when it is
not possible to transport goods from certain sources to certain destinations. In this case, the
appropriate cell may either be completely crossed out or a very large per unit transportation cost
assign to it (M).

Haramaya University, Department of Management 96

 Operations Research

3.6 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. The
problem of assignment arises because available resources such as men, machines, etc. have
varying degrees of efficiency for performing different activities such as job. Therefore, cost,
profit or time of performing the different activities is different.

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

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 throughput
(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.
• 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.

Haramaya University, Department of Management 97

 Operations Research

Example

Service costs of different team assignment ($ in thousands)

Table: The assignment table
Zone
Service SS
Z1 Z2 Z3 Z1 Z2 Z3
Service
Team

20 15 31 ====> 1
S1 S1 20 15 31
S2 17 16 33 S2 17 16 33 1
S3 18 19 27 S3 18 19 27 1
DD 1 1 1

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

Min. Z = 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 =1 S2 constraint
x31 +x32 +x33 = 1 S3 supply constraint

b. Demand constraints
x11 + x21 + x31 = 1 Z1 constraint
x12 + x22 + x32 = 1 Z2 constraint
x13 + x23 +x33 = 1 Z3 constraint
xij either 0 or 1 for 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. As in the transportation problem, assignment problems
can be balanced or not. In a balanced case, the number of objects to be assigned equals the

Haramaya University, Department of Management 98

 Operations Research

number of objects to which they are assigned. Unbalanced problem can be balanced by adding a
dummy (dummies) with zero cost coefficients.

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

Hungarian Method/Food’s Technique/

The Hungarian Method (developed by Hungarian mathematician D. Konig) 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

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 2. Find the opportunity cost table

Haramaya University, Department of Management 99

 Operations Research

The transformation of the cost matrix to what is termed as a total-opportunity cost matrix. 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 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 column, now have
at least one zero value.

Step 3. Test for an optimal assignment

I.e. 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 the 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.

Haramaya University, Department of Management 100

 Operations Research

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.

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 (Estimated time in minute)

Programmers

A B C
1 120 100 80
2 80 90 110
3 110 140 120

Assign the programmers to the programs in such a way that the total computer time is 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.

Haramaya University, Department of Management 101

 Operations Research

The reduced time matrix is:

Table: After row reduction

A B C
-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).
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.

Haramaya University, Department of Management 102

 Operations Research

Step 5. Make 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
40 10 0
1

0 0 30
2

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:

Programmer Program Time (in minutes)

1 C 80
2 B 90
3 A 110
Total time=280 minutes
Example 2

A department has five employees with five jobs to be performed. The time (in hours) each man
will take to perform each job is given in the effectiveness matrix.
Haramaya University, Department of Management 103
 Operations Research

Employees
I II III IV V

A 10 5 13 15 16
B 3 9 18 13 6
Jobs

C 10 7 2 2 2
D 7 11 9 7 12

E 7 9 10 4 12

How should the jobs be allocated, one per employees, so as to minimize the total man-hours?

Solution

Table: After row reduction

I II III IV V
-5 A 5 0 8 10 11
-3 B 0 6 15 10 3
-2 C 8 5 0 0 0
-7 D 0 5 2 0 5

-4 E 3 5 6 0 8

Since the number of lines less than the number of rows/columns, an improvement is possible.

Step 4. Improve the present opportunity cost table

This is done by the following operations;

a. Select the smallest entry (element) among all uncovered elements by the lines and
subtract it from all entries in the uncovered cells.
b. Add the same smallest entry to those cells in which lines intersect (cells with two lines
them).
c. Cells with one line through them are unchanged to the improved table.

Haramaya University, Department of Management 104

 Operations Research

Table: After improvement

I II III IV V

A 7 0 8 12 11
B 0 4 13 10 1
C 10 5 0 2 0
D 0 2 0 0 2

E 3 3 4 0 6

Since the number of lines equals to the number of rows/columns, the solution is optimal.
Table: Optimal assignments

Haramaya University, Department of Management 105

 I II III IV V
Operations Research

A 7 0 8 12 11

0
B 4 13 10 1

C 10 5 0 2 0

0
D 0 2 0 2 2

E 3 3 4 0 6

The pattern of assignments among jobs and employees with respective time (in hours) is given
below:

Job Employees Time (in minutes)

A II 5
B I 3
C V 2
D III 9

E IV 4

Total time=23 Hours

Example 3

A manager has prepared the following table, which shows the costs for various combinations of
job-machine assignments:
Machine (Cost in ’000s))
A B C
1 20 15 31
Job 2 17 16 33
3 18 19 27

Haramaya University, Department of Management 106

 Operations Research

a. What is the optimal (minimum-cost) assignment for this problem?

b. What is the total cost for the optimum assignment?
Solution
Table: After row reduction Table: After column reduction

A B C A B C
-15 1 5 0 16 1 5 0 7
-16 2 1 0 17 2 1 0 8
-18 3 0 1 9 3 0 1 0

Table: After improvement

A B C
1 4 0 6
2 0 0 7
3 0 2 0

Table: Optimal Assignment machine

A B C

1 4 0 6

2 0 0 7

3
2 0
0

Haramaya University, Department of Management 107

 Operations Research

Job

Cost(in $)
1 B 15000
2 A 17000
3 C 27000
Total optimal assignment=$59000

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:

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

Haramaya University, Department of Management 108

 Operations Research

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

Given this final assignment table, identify two optimal solutions.

Machine (Estimated time in minute)

1 2 3
A 4 0 0
Job 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

Machine
1 2 3
4 0
A 0

Job B 0 3 2

1 0
C 0

Example 2

The foreman of a machine shop wants to determine a minimum cost matching for operators and
machines. The foreman has determined hourly cost for of four operators for the four machines,
as shown in the following cost table.

Haramaya University, Department of Management 109

 Operations Research

Machine (Estimated cost in $)

A B C D
1 70 80 75 64
Operator
2 55 52 58 54

3 58 56 64 68
4 62 60 67 70

Required:
a. Determine the minimum-cost assignment for this problem
b. What is the total cost for the optimal assignment?
c. Is there an alternative optimal assignment? What is it? Calculate the total cost for the
alternate optimal assignment.

Solution

Table: After row reduction Table: After column reduction

A B C D
A B C D
1 6 16 11 D0
1 4 16 5 D0
2 3 0 6 2
2 1 0 0 2
3 2 0 8 12
4 2 0 7 10 3 0 0 2 12
4 0 0 1 10

Table: Optimal Assignments

A B C D
1 4 16 5 0
0 0
2 1 2
0
3 0 2 12
a. Optimal Assignment 4 0 0 1 10 b.
Operator Machine Cost(in $)
4 A 62
3 B 56
2 C 58

Haramaya University, Department of Management 110

 Operations Research

1 D 64
Total cost =$240

c. Yes! Alternative optimal assignment

Operator Machine Cost(in $)

1 D 64
2 C 58
3 A 58
4 B 60
Total cost=$240

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

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

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
A 42 35 28 21
Salesmen

B 30 25 20 15

Haramaya University, Department of Management 111

 Operations Research

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 I II III IV
A 0 7 14 21 A 0 3 6 9
B 12 17 22 27 B 0 1 2 3
C 12 17 22 27 C 0 1 2 3
D 18 22 26 30 D 0 0 0 0

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

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 I Assignment set II

Salesman Territory Sales($) Salesman Territory Sales($)
A I 42 A I 42

Haramaya University, Department of Management 112

 Operations Research

B III 20 B II 25
C II 25 C III 20
D IV 12 D IV 12
Total =$ 99 Total = $ 99

C. Unbalanced Assignment Problem

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.

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
Dar, and Dire Dawa. 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 Bakcha there, and Br. 1,500 to
move Hirut. What is the optimal assignment of personnel to offices?

Office
Mekelle Bahir Dar 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.
C1 C2 C3 C4 (Gambela)

Haramaya University, Department of Management 113

 Operations Research

P1 800 1,100 1,200 1,000

Person 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

C1 C2 C3 C4 C1 C2 C3 C4
P1 0 300 400 200 P1 100 0 100 0
P2 0 1,100 800 300 P2 0 700 400 0
P3 0 500 1800 1000 P3 0 100 1400 700
Dummy 0 0 0 0 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 Dar
Cost = Br. (0+500+800+1,100) = Br. 2,400

D. 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 ) so as to prohibit the entry of this pair of employee-job into the
final solution. When such a restriction is present, a letter (M) is often placed in the table in the
position that would represent a paring. Analysis is performed as usual except the M is ignored
throughout the analysis. That is, M is not used in any reductions, nor is any value added to it or
subtracted from it during the course of the analysis.

Haramaya University, Department of Management 114

 Operations Research

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 cannot be placed at C and M3 cannot be placed at A. the cost of
placing of machine at place i (in $) is shown below.
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.

Table: Optimal assignment

A B C D E A B C D E
M1 9 11 15 10 11 M1 0 2 6 1 2
M2 12 9 M 10 9 M2 3 0 M 1 0
M3 M 11 14 11 7 M3 M 4 7 4 0
M4 14 8 12 7 8 M4 7 1 5 0 1
M5 0 0 0 0 0 M5

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

Machine Location Costs ($)

Haramaya University, Department of Management 115

 Operations Research

M1 A 9
M2 B 9
M3 E 7
M4 D 7
M5 (Dummy) C 0
Total = $32

Haramaya University, Department of Management 116

 Operations Research

Chapter Four

Network Models

Introduction

There are several kinds of linear-programming models that exhibit a special structure that can be
exploited in the construction of efficient algorithms for their solution. The motivation for taking
advantage of their structure usually has been the need to solve larger problems than otherwise
would be possible to solve with existing computer technology. Historically, the first of these
special structures to be analyzed was the transportation problem, which is a particular type of
network problem. The development of an efficient solution procedure for this problem resulted
in the first widespread application of linear programming to problems of industrial logistics.
More recently, the development of algorithms to efficiently solve particular large-scale systems
has become a major concern in applied mathematical programming. Network models are
possibly still the most important of the special structures in linear programming.

In this chapter, we examine major concepts related to network models and the characteristics of
projects. Additionally, major networking algorithms are to be discussed, and the differences
between Program Evaluation and Review Technique (PERT) and Critical Path Method (CPM)
are to be discussed in this chapter. Furthermore, these methods are thoroughly explained and
illustrated with examples.

Objectives of the Chapter

After studying this Chapter, students should be able to:

➢ Explain the meaning of project, network models, PERT and CPM;

➢ Describe different network algorithms;

➢ Differentiate PERT and CPM; and

➢ Implement network models in decision making

Haramaya University, Department of Management 117

 Operations Research

4.1 General Network Concepts

There are several kinds of linear-programming models that exhibit a special structure that can be
exploited in the construction of efficient algorithms for their solution. The motivation for taking
advantage of their structure usually has been the need to solve larger problems than otherwise
would be possible to solve with existing computer technology. Historically, the first of these
special structures to be analyzed was the transportation problem, which is a particular type of
network problem. The development of an efficient solution procedure for this problem resulted
in the first widespread application of linear programming to problems of industrial logistics.
More recently, the development of algorithms to efficiently solve particular large-scale systems
has become a major concern in applied mathematical programming. Network models are
possibly still the most important of the special structures in linear programming. In this chapter,
we examine the characteristics of network models, formulate some examples of these models,
and give one approach to their solution.

For a project manager as well as a project team member, familiarizing yourself with network
diagrams — also known as the project schedule network diagram are crucial. A project network
diagram is an important tool because it helps teams visualize the activities that need to be
completed over the duration of a project. It also gives crucial context like task duration,
sequence, and dependency. A network is a graphical plan consisting of a certain configuration of
arrows and nodes for showing the logical sequence of various activities to be performed to
achieve project objectives. It is the logical and sequential interconnection of project activities.
Network is a set of points and a set of lines connecting certain pairs of points. The points are
called nodes. Network is used to represent the distance, time or cost of getting from one location
to various other locations. Network analysis involves the breaking down of a project into its
constituent activities, and the presentation of these activities in diagrammatic form. Project is
temporary endeavor with unique characteristics made up of activities to achieve a set of specific
objectives. It is a series of activities designed to achieve a specific objective, and which has a
definite beginning and a definite end. It is capable of being split into a number of discrete
activities, which relate together in a logical and well-defined manner. A project is a combination
of various activities. For example, construction of a house can be considered as a project.

Haramaya University, Department of Management 118

 Operations Research

Similarly, conducting a public meeting may also be considered as a project. In the above
examples, construction of a house includes various activities such as searching for a suitable site,
arranging the finance, purchase of materials, digging the foundation, construction of
superstructure etc. Conducting a meeting includes, printing of invitation cards, distribution of
cards, arrangement of platform, chairs for audience etc.

Characteristics of a Project:

• Limited time span

• Has specific beginning and ending date
• Unique/ Non-routine
• Resource constraints
• Specific objectives/purpose

Program Evaluation and Review Technique (PERT) and Critical Path Method (CPM) are two
techniques that are widely used in planning and scheduling large projects. A project is a
combination of various activities. For example, construction of a house can be considered as a
project. Similarly, conducting a public meeting may also be considered as a project. In the above
examples, construction of a house includes various activities such as searching for a suitable site,
arranging the finance, purchase of materials, digging the foundation, construction of
superstructure etc. Conducting a meeting includes, printing of invitation cards, distribution of
cards, arrangement of platform, chairs for audience etc. In planning and scheduling the activities
of large sized projects, the two network techniques — PERT and CPM — are used conveniently
to estimate and evaluate the project completion time and control the resources to see that the
project is completed within the stipulated time and at minimum possible cost. Many managers,
who use the PERT and CPM techniques, have claimed that these techniques drastically reduce
the project completion time. But it is wrong to think that network analysis is a solution to all bad
management problems. In the present chapter, let us discuss how PERT and CPM are used to
schedule the projects.

Initially, projects were represented by milestone chart and bar chart. But they had little use in
controlling the project activities. Bar chart simply represents each activity by bars of length equal

Haramaya University, Department of Management 119

 Operations Research

to the time taken on a common time scale as shown in Figure 4.l. This chart does not show
interrelationship between activities. It is very difficult to show the progress of work in these
charts. An improvement in bar charts is milestone chart. In milestone chart, key events of
activities are identified and each activity is connected to its preceding and succeeding activities
to show the logical relationship between activities. Here each key event is represented by a node
(a circle) and arrows instead of bars represent activities, as shown in Figure 4.2. The extension of
milestone chart is PERT and CPM network methods.

Figure 4.l. Bar chart Figure 4.2. Milestone chart

The Terminology of Networks

A network consists of a set of points and a set of lines connecting certain pairs of the points. The
points are called nodes (or vertices); e.g., the network in Figure 4.3 has seven nodes designated
by the seven circles. The lines are called arcs (or links or edges or branches); e.g., the network in
Figure 4.3 has 12 arcs corresponding to the 12 roads in the road system. Arcs are labeled by
naming the nodes at either end; for example, AB is the arc between nodes A and B in Figure 4.3.

Haramaya University, Department of Management 120

 Operations Research

Figure 4.3. The road system for Seervada Park.

The arcs of a network may have a flow of some type through them, e.g., the flow of cars on the
roads of Seervada Park. Table 4.1 gives several examples of flow in typical networks. If flow
through an arc is allowed in only one direction (e.g., a one-way street), the arc is said to be a
directed arc. The direction is indicated by adding an arrowhead at the end of the line
representing the arc. When a directed arc is labeled by listing two nodes it connects, the from
node always is given before the to node; e.g., an arc that is directed from node A to node B must
be labeled as AB rather than BA. Alternatively, this arc may be labeled as A → B.

Table 4.1. Components of typical networks

Nodes Arcs Flow

Intersections Roads Vehicles
Airports Air lanes Aircraft
Switching points Wires, channels Messages
Pumping stations Pipes Fluids
Work centers Materials-handling routes Jobs

If flow through an arc is allowed in either direction (e.g., a pipeline that can be used to pump
fluid in either direction), the arc is said to be an undirected arc. To help you distinguish
between the two kinds of arcs, we shall frequently refer to undirected arcs by the suggestive
name of links.
Haramaya University, Department of Management 121
 Operations Research

Although the flow through an undirected arc is allowed to be in either direction, we do assume
that the flow will be one way in the direction of choice rather than having simultaneous flows in
opposite directions. The latter case requires the use of a pair of directed arcs in opposite
directions. However, in the process of making the decision on the flow through an undirected
arc, it is permissible to make a sequence of assignments of flows in opposite directions, but with
the understanding that the actual flow will be the net flow (the difference of the assigned flows in
the two directions). For example, if a flow of 10 has been assigned in one direction and then a
flow of 4 is assigned in the opposite direction, the actual effect is to cancel 4 units of the original
assignment by reducing the flow in the original direction from 10 to 6. Even for a directed arc,
the same technique sometimes is used as a convenient device to reduce a previously assigned
flow. In particular, you are allowed to make a fictional assignment of flow in the “wrong”
direction through a directed arc to record a reduction of that amount in the flow in the “right”
direction.

A network that has only directed arcs is called a directed network. Similarly, if all its arcs are
undirected, the network is said to be an undirected network. A network with a mixture of
directed and undirected arcs (or even all undirected arcs) can be converted to a directed network,
if desired, by replacing each undirected arc by a pair of directed arcs in opposite directions. You
then have the choice of interpreting the flows through each pair of directed arcs as being
simultaneous flows in opposite directions or providing a net flow in one direction, depending on
which fits your application.

When two nodes are not connected by an arc, a natural question is whether they are connected by
a series of arcs. A path between two nodes is a sequence of distinct arcs connecting these nodes.
For example, one of the paths connecting nodes O and T in Figure 4.3 is the sequence of arcs
OB–BD–DT (O → B → D → T), or vice versa. When some of or all the arcs in the network are
directed arcs, we then distinguish between directed paths and undirected paths. A directed path
from node i to node j is a sequence of connecting arcs whose direction (if any) is toward node j,
so that flow from node i to node j along this path is feasible. An undirected path from node i to
node j is a sequence of connecting arcs whose direction (if any) can be either toward or away
from node j. (Notice that a directed path also satisfies the definition of an undirected path, but

Haramaya University, Department of Management 122

 Operations Research

not vice versa.) Frequently, an undirected path will have some arcs directed toward node j but
others directed away (i.e., toward node i).

To illustrate these definitions, Figure 4.4 shows a typical directed network. Nodes A and B
represent two factories, nodes D and E represent two warehouses, node C represents a
distribution center, and the arcs represent shipping lanes. The sequence of arcs AB–BC–CE (A →
B → C → E) is a directed path from node A to E, since flow toward node E along this entire path
is feasible. On the other hand, BC–AC–AD (B → C → A → D) is not a directed path from node B
to node D, because the direction of arc AC is away from node D (on this path). However, B →
C → A → D is an undirected path from node B to node D, because the sequence of arcs BC–AC–
AD does connect these two nodes (even though the direction of arc AC prevents flow through
this path).

Figure 4.4. The distribution network for Distribution Unlimited Co.

As an example of the relevance of undirected paths, suppose that 2 units of flow from node A to
node C had previously been assigned to arc AC. Given this previous assignment, it now is
feasible to assign a smaller flow, say, 1 unit, to the entire undirected path B → C → A → D, even
though the direction of arc AC prevents positive flow through C → A. The reason is that this
assignment of flow in the “wrong” direction for arc AC actually just reduces the flow in the
“right” direction by 1 unit.

Haramaya University, Department of Management 123

 Operations Research

A path that begins and ends at the same node is called a cycle. In a directed network, a cycle is
either a directed or an undirected cycle, depending on whether the path involved is a directed or
an undirected path. (Since a directed path also is an undirected path, a directed cycle is an
undirected cycle, but not vice versa in general.) In Figure 4.4, for example, DE–ED is a directed
cycle. By contrast, AB–BC–AC is not a directed cycle, because the direction of arc AC opposes
the direction of arcs AB and BC. On the other hand, AB–BC–AC is an undirected cycle, because
A → B → C → A is an undirected path. In the undirected network shown in Figure 4.3, there are
many cycles, for example, OA–AB–BC–CO. However, note that the definition of path (a
sequence of distinct arcs) rules out retracing one’s steps in forming a cycle. For example, OB–
BO in Figure 4.3 does not qualify as a cycle, because OB and BO are two labels for the same arc
(link). On the other hand, DE–ED is a (directed) cycle in Figure 4.4, because DE and ED are
distinct arcs.

Two nodes are said to be connected if the network contains at least one undirected path between
them. (Note that the path does not need to be directed even if the network is directed.) A
connected network is a network where every pair of nodes is connected. Thus, the networks in
Figure 4.3 and 4.4 are both connected. However, the latter network would not be connected if
arcs AD and CE were removed.

Consider a connected network with n nodes (e.g., the n = 5 nodes in Figure 4.4) where all the
arcs have been deleted. A “tree” can then be “grown” by adding one arc (or “branch”) at a time
from the original network in a certain way. The first arc can go anywhere to connect some pair of
nodes. Thereafter, each new arc should be between a node that already is connected to other
nodes and a new node not previously connected to any other nodes. Adding an arc in this way
avoids creating a cycle and ensures that the number of connected nodes is 1 greater than the
number of arcs. Each new arc creates a larger tree, which is a connected network (for some
subset of the n nodes) that contains no undirected cycles. Once the (𝑛 − 1)𝑠𝑡 arc has been added,
the process stops because the resulting tree spans (connects) all n nodes. This tree is called a
spanning tree, i.e., a connected network for all n nodes that contains no undirected cycles. Every
spanning tree has exactly 𝑛 − 1 arcs, since this is the minimum number of arcs needed to have a
connected network and the maximum number possible without having undirected cycles.

Haramaya University, Department of Management 124

 Operations Research

Figure 4.5 uses the five nodes and some of the arcs of Figure 4.4 to illustrate this process of
growing a tree one arc (branch) at a time until a spanning tree has been obtained. There are
several alternative choices for the new arc at each stage of the process, so Figure 4.5 shows only
one of many ways to construct a spanning tree in this case. Note, however, how each new added
arc satisfies the conditions specified in the preceding paragraph. We shall discuss and illustrate
spanning trees further in the next section of this chapter.

Figure 4.5: Example of growing a tree one arc at a time for the network of Figure 4.4: (a)
The nodes without arcs; (b) a tree with one arc; (c) a tree with two arcs; (d) a tree with
three arcs; (e) a spanning tree.

Finally, we shall need a little additional terminology about flows in networks. The maximum
amount of flow (possibly infinity) that can be carried on a directed arc is referred to as the arc
capacity. For nodes, a distinction is made among those that are net generators of flow, net

Haramaya University, Department of Management 125

 Operations Research

absorbers of flow, or neither. A supply node (or source node or source) has the property that the
flow out of the node exceeds the flow into the node. The reverse case is a demand node (or sink
node or sink), where the flow into the node exceeds the flow out of the node. A transshipment
node (or intermediate node) satisfies conservation of flow, so flow in equals flow out.

4.2 Networking Algorithms

In this part of the chapter, we describe four algorithms related to networking models. We
consider (1) the shortest-route algorithm, (2) finding a minimal spanning tree of a graph, (3) the
maximal flow algorithm, and (4) the Critical Path Method (CPM) algorithm. Applications of
these algorithms include (respectively) (1) finding a shortest route between two cities in a given
network of roads, (2) constructing a network connecting given locations in such a way as to
minimize distance/cost, (3) determining the maximum flow of a fluid though a network of
connected pipelines, and (4) determining a time schedule for the activities of a construction
project. The first three methods are discussed below. The Critical Path Method (CPM) algorithm
discussed and illustrated in the next Section 4.3 and 4.4 of the chapter.

4.2.1. The Shortest-Path Problem

The shortest-route problem determines the shortest route between a source and destination in a
transportation network. In a network, this often involves determining the shortest route from one
node to each of the other nodes. Although several other versions of the shortest-path problem
exist, we shall focus on the following simple version. Consider an undirected and connected
network with two special nodes called the origin and the destination. Associated with each of the
links (undirected arcs) is a non-negative distance. The objective is to find the shortest path (the
path with the minimum total distance) from the origin to the destination.

A relatively straightforward algorithm is available for this problem. The essence of this
procedure is that it fans out from the origin, successively identifying the shortest path to each of
the nodes of the network in the ascending order of their (shortest) distances from the origin,
thereby solving the problem when the destination node is reached.

Haramaya University, Department of Management 126

 Operations Research

Algorithm for the Shortest-Path Problem

Objective of nth iteration: Find the 𝑛𝑡ℎ nearest node to the origin (to be repeated for n = 1, 2, . .
. until the nth nearest node is the destination.

Input for 𝒏𝒕𝒉 iteration: n = 1 nearest nodes to the origin (solved for at the previous iterations),
including their shortest path and distance from the origin. (These nodes,
plus the origin, will be called solved nodes; the others are unsolved
nodes.)

Candidates for nth nearest node: Each solved node that is directly connected by a link to one
or more unsolved nodes provides one candidate—the
unsolved node with the shortest connecting link. (Ties
provide additional candidates.)

Calculation of nth nearest node: For each such solved node and its candidate, add the distance
between them and the distance of the shortest path from the
origin to this solved node. The candidate with the smallest
such total distance is the nth nearest node (ties provide
additional solved nodes), and its shortest path is the one
generating this distance.

Applying This Algorithm to the Seervada Park Shortest-Path Problem

The Seervada Park management needs to find the shortest path from the park entrance (node O)
to the scenic wonder (node T) through the road system shown in Figure 4.3. Applying the above
algorithm to this problem yields the results shown in Table 4.2 (where the tie for the second
nearest node allows skipping directly to seeking the fourth nearest node next). The first column
(n) indicates the iteration count. The second column simply lists the solved nodes for beginning
the current iteration after deleting the irrelevant ones (those not connected directly to any
unsolved node). The third column then gives the candidates for the nth nearest node (the
unsolved nodes with the shortest connecting link to a solved node). The fourth column calculates
the distance of the shortest path from the origin to each of these candidates (namely, the distance

Haramaya University, Department of Management 127

 Operations Research

to the solved node plus the link distance to the candidate). The candidate with the smallest such
distance is the nth nearest node to the origin, as listed in the fifth column. The last two columns
summarize the information for this newest solved node that is needed to proceed to subsequent
iterations (namely, the distance of the shortest path from the origin to this node and the last link
on this shortest path).

Table 4.2. Applying the shortest-path algorithm to the Seervada Park problem

Now, let us relate these columns directly to the outline given for the algorithm. The input for nth
iteration is provided by the fifth and sixth columns for the preceding iterations, where the solved
nodes in the fifth column are then listed in the second column for the current iteration after
deleting those that are no longer directly connected to unsolved nodes. The candidates for nth
nearest node next are listed in the third column for the current iteration. The calculation of nth
nearest node is performed in the fourth column, and the results are recorded in the last three
columns for the current iteration. After the work shown in Table 4.2 is completed, the shortest
path from the destination to the origin can be traced back through the last column of Table 4.2 as
either T → D → E → B → A → O or T → D → B → A → O. Therefore, the two alternates for the
Haramaya University, Department of Management 128
 Operations Research

shortest path from the origin to the destination have been identified as O → A → B → E → D → T
and O → A → B → D → T, with a total distance of 13 miles on either path.

4.2.2. Minimal Spanning Tree Problem

A tree is a set of connected arcs that does not form a cycle. A spanning tree is a tree that
connects all nodes of a network. The minimal spanning tree problem seeks to determine the
minimum sum of arc lengths necessary to connect all nodes in a network. The criterion to be
minimized in the minimal spanning tree problem is not limited to distance. Other criteria include
time and cost.

The minimum spanning tree problem bears some similarities to the main version of the shortest-
path problem presented in the preceding section. In both cases, an undirected and connected
network is being considered, where the given information includes some measure of the positive
length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing
a set of links that have the shortest total length among all sets of links that satisfy a certain
property. For the shortest-path problem, this property is that the chosen links must provide a path
between the origin and the destination. For the minimum spanning tree problem, the required
property is that the chosen links must provide a path between each pair of nodes.

The minimum spanning tree problem can be summarized as follows.

1) You are given the nodes of a network but not the links. Instead, you are given the
potential links and the positive length for each if it is inserted into the network.
(Alternative measures for the length of a link include distance, cost, and time.)
2) You wish to design the network by inserting enough links to satisfy the requirement that
there be a path between every pair of nodes.
3) The objective is to satisfy this requirement in a way that minimizes the total length of the
links inserted into the network.

Algorithm for the Minimum Spanning Tree Problem

1) Select any node arbitrarily, and then connect it (i.e., add a link) to the nearest distinct
node.
Haramaya University, Department of Management 129
 Operations Research

2) Identify the unconnected node that is closest to a connected node, and then connect these
two nodes (i.e., add a link between them). Repeat this step until all nodes have been
connected.
3) Tie breaking: Ties for the nearest distinct node (step 1) or the closest unconnected node
(step 2) may be broken arbitrarily, and the algorithm must still yield an optimal solution.
However, such ties are a signal that there may be (but need not be) multiple optimal
solutions. All such optimal solutions can be identified by pursuing all ways of breaking
ties to their conclusion.
The fastest way of executing this algorithm manually is the graphical approach illustrated next.

Applying This Algorithm to the Seervada Park Minimum Spanning Tree Problem

The Seervada Park management needs to determine under which roads telephone lines should be
installed to connect all stations with a minimum total length of line. Using the data given in
Figure 4.3, we outline the step-by-step solution of this problem.

Nodes and distances for the problem are summarized below, where the thin lines now represent
potential links.

Arbitrarily select node O to start. The unconnected node closest to node O is node A. Connect
node A to node O.

Haramaya University, Department of Management 130

 Operations Research

The unconnected node closest to either node O or node A is node B (closest to A). Connect node
B to node A.

The unconnected node closest to node O, A, or B is node C (closest to B). Connect node C to
node B.

Haramaya University, Department of Management 131

 Operations Research

The unconnected node closest to node O, A, B, or C is node E (closest to B). Connect node E to
node B.

The unconnected node closest to node O, A, B, C, or E is node D (closest to E). Connect node D
to node E.

The only remaining unconnected node is node T. It is closest to node D. Connect node T to node
D.

Haramaya University, Department of Management 132

 Operations Research

All nodes are now connected, so this solution to the problem is the desired (optimal) one. The
total length of the links is 14 miles.

Although it may appear at first glance that the choice of the initial node will affect the resulting
final solution (and its total link length) with this procedure, it really does not. We suggest you
verify this fact for the example by reapplying the algorithm, starting with nodes other than node
O.

The minimum spanning tree problem is the one problem we consider in this chapter that falls
into the broad category of network design. In this category, the objective is to design the most
appropriate network for the given application (frequently involving transportation systems)
rather than analyzing an already designed network.

4.2.3. The Maximum Flow Problem

Now recall that the third problem facing the Seervada Park management during the peak season
is to determine how to route the various tram trips from the park entrance (station O in Figure
4.3) to the scenic wonder (station T) to maximize the number of trips per day. (Each team will
return by the same route it took on the outgoing trip, so the analysis focuses on outgoing trips
only.) To avoid unduly disturbing the ecology and wildlife of the region, strict upper limits have
been imposed on the number of outgoing trips allowed per day in the outbound direction on each
individual road. For each road, the direction of travel for outgoing trips is indicated by an arrow
in Figure 4.6. The number at the base of the arrow gives the upper limit on the number of
outgoing trips allowed per day. Given the limits, one feasible solution is to send 7 trams per day,

Haramaya University, Department of Management 133

 Operations Research

with 5 using the route O → B → E → T, 1 using O → B → C → E → T, and 1 using O → B → C →

E → D → T. However, because this solution blocks the use of any routes starting with O → C
(because the E → T and E → D capacities are fully used), it is easy to find better feasible
solutions. Many combinations of routes (and the number of trips to assign to each one) need to
be considered to find the one(s) maximizing the number of trips made per day. This kind of
problem is called a maximum flow problem.

Figure 4.6. The Seervada Park maximum flow problem.

In general terms, the maximum flow problem can be described as follows.

1) All flow through a directed and connected network originates at one node, called the
source, and terminates at one other node, called the sink. (The source and sink in the
Seervada Park problem are the park entrance at node O and the scenic wonder at node T,
respectively.)
2) All the remaining nodes are transshipment nodes. (These are nodes A, B, C, D, and E in
the Seervada Park problem.)
3) Flow through an arc is allowed only in the direction indicated by the arrowhead, where
the maximum amount of flow is given by the capacity of that arc. At the source, all arcs
point away from the node. At the sink, all arcs point into the node.
4) The objective is to maximize the total amount of flow from the source to the sink. This
amount is measured in either of two equivalent ways, namely, either the amount leaving
the source or the amount entering the sink.

Haramaya University, Department of Management 134

 Operations Research

The Augmenting Path Algorithm for the Maximum Flow Problem

1) Identify an augmenting path by finding some directed path from the source to the sink in
the residual network such that every arc on this path has strictly positive residual
capacity. (If no augmenting path exists, the net flows already assigned constitute an
optimal flow pattern.)
2) Identify the residual capacity c* of this augmenting path by finding the minimum of the
residual capacities of the arcs on this path. Increase the flow in this path by c*.
3) Decrease by c* the residual capacity of each arc on this augmenting path. Increase by c*
the residual capacity of each arc in the opposite direction on this augmenting path. Return
to step 1.

When step 1 is carried out, there often will be a number of alternative augmenting paths from
which to choose. Although the algorithmic strategy for making this selection is important for the
efficiency of large-scale implementations, we shall not delve into this relatively specialized
topic. Therefore, for the following example, the selection is just made arbitrarily.

Applying This Algorithm to the Seervada Park Maximum Flow Problem

Applying this algorithm to the Seervada Park problem (see Figure 4.6 for the original network)
yields the results summarized next. Starting with the initial residual network given in Figure 4.7,
we give the new residual network after each one or two iterations, where the total amount of flow
from O to T achieved thus far is shown in boldface (next to nodes O and T).

Figure 4.7. The initial residual network for the Seervada Park maximum flow problem.

Haramaya University, Department of Management 135

 Operations Research

Iteration 1: In Figure 4.7, one of several augmenting paths is O → B → E → T, which has a

residual capacity of min {7, 5, 6} = 5. By assigning a flow of 5 to this path, the resulting residual
network is:

Iteration 2: Assign a flow of 3 to the augmenting path O → A → D → T. The resulting residual

network is:

Iteration 3: Assign a flow of 1 to the augmenting path O → A → B → D → T.

Iteration 4: Assign a flow of 2 to the augmenting path O → B → D → [Link] resulting residual

network is:

Haramaya University, Department of Management 136

 Operations Research

Iteration 5: Assign a flow of 1 to the augmenting path O → C → E → D → T.

Iteration 6: Assign a flow of 1 to the augmenting path O → C → E → T. The resulting residual

network is:

Iteration 7: Assign a flow of 1 to the augmenting path O → C → E → B → D → T. The resulting

residual network is:

There are no more augmenting paths, so the current flow pattern is optimal.
Haramaya University, Department of Management 137
 Operations Research

Figure 4.8. Optimal solution for the Seervada Park maximum flow problem.

The current flow pattern may be identified by either cumulating the flow assignments or
comparing the final residual capacities with the original arc capacities. If we use the latter
method, there is flow along an arc if the final residual capacity is less than the original capacity.

The magnitude of this flow equals the difference in these capacities. Applying this method by
comparing the residual network obtained from the last iteration with either Figure 4.6 or 4.7
yields the optimal flow pattern shown in Figure 4.8.

This example nicely illustrates the reason for replacing each directed arc i → j in the original
network by an undirected arc in the residual network and then increasing the residual capacity
for j → i by c* when a flow of c* is assigned to i → j. Without this refinement, the first six
iterations would be unchanged. However, at that point it would appear that no augmenting paths
remain (because the real unused arc capacity for E → B is zero). Therefore, the refinement
permits us to add the flow assignment of 1 for O → C → E → B → D → T in iteration 7. In effect,
this additional flow assignment cancels 1 unit of flow assigned at iteration 1 (O → B → E → T)
and replaces it by assignments of 1 unit of flow to both O → B → D → T and O → C → E → T.

Finding an Augmenting Path

The most difficult part of this algorithm when large networks are involved is finding an
augmenting path. This task may be simplified by the following systematic procedure. Begin by
determining all nodes that can be reached from the source along a single arc with strictly positive

Haramaya University, Department of Management 138

 Operations Research

residual capacity. Then, for each of these nodes that were reached, determine all new nodes
(those not yet reached) that can be reached from this node along an arc with strictly positive
residual capacity. Repeat this successively with the new nodes as they are reached. The result
will be the identification of a tree of all the nodes that can be reached from the source along a
path with strictly positive residual flow capacity. Hence, this fanning-out procedure will always
identify an augmenting path if one exists. The procedure is illustrated in Figure 4.9 for the
residual network that results from iteration 6 in the preceding example.

Figure 4.9. Procedure for finding an augmenting path for iteration 7 of the Seervada Park
maximum flow problem.

Although the procedure illustrated in Figure 4.9 is a relatively straightforward one, it would be
helpful to be able to recognize when optimality has been reached without an exhaustive search
for a nonexistent path. It is sometimes possible to recognize this event because of an important
theorem of network theory known as the max-flow min-cut theorem. A cut may be defined as
any set of directed arcs containing at least one arc from every directed path from the source to
the sink. There normally are many ways to slice through a network to form a cut to help analyze
the network. For any particular cut, the cut value is the sum of the arc capacities of the arcs (in
the specified direction) of the cut. The max-flow min-cut theorem states that, for any network
with a single source and sink, the maximum feasible flow from the source to the sink equals the
minimum cut value for all cuts of the network. Thus, if we let F denote the amount of flow from

Haramaya University, Department of Management 139

 Operations Research

the source to the sink for any feasible flow pattern, the value of any cut provides an upper bound
to F, and the smallest of the cut values is equal to the maximum value of F. Therefore, if a cut
whose value equals the value of F currently attained by the solution procedure can be found in
the original network, the current flow pattern must be optimal. Eventually, optimality has been
attained whenever there exists a cut in the residual network whose value is zero.

To illustrate, consider the network of Figure 4.7. One interesting cut through this network is
shown in Figure 4.10. Notice that the value of the cut is 3 → 4 → 1 → 6 → 14, which was found
to be the maximum value of F, so this cut is a minimum cut. Notice also that, in the residual
network resulting from iteration 7, where F = 14, the corresponding cut has a value of zero. If
this had been noticed, it would not have been necessary to search for additional augmenting
paths.

Figure 4.10. A minimum cut for the Seervada Park maximum flow problem.

4.3 Basic Difference Between PERT and CPM

Program Evaluation and Review Technique (PERT) and Critical Path Method (CPM) are
network techniques developed in 1950’s. PERT developed by Booz, Allen & Hamilton with the
U.S. Navy, for Polaris missile in 1958. CPM developed by DuPont for chemical plants in 1957.
PERT and CPM are the two most popular techniques that are widely used in planning and
scheduling large projects. There are no essential differences between PERT and CPM as both of
them share in common the determination of a critical path and are based on the network

Haramaya University, Department of Management 140

 Operations Research

representation of activities and their scheduling determines the most critical activities. Both
consider precedence relationships and interdependencies. Each uses a different estimate of
activity times. However, if the duration of activities is not known with certainty, the PERT can
be used to estimate the probability that the project will be completed by a given deadline. If the
duration of each activity is known with certainty, the CPM can be used to determine the length
of time required to complete a project.

In critical path method, the time duration of activity is deterministic in nature i.e., there will be a
single time, rather than three time estimates as in PERT networks. The network is activity
oriented. The three ways in which the CPM type of networks differ from PERT networks are:

CPM PERT
(a) Network is constructed on the basis of (a) Network is constructed basing on the events
jobs or activities (activity oriented). (event oriented)
(b) CPM does not take uncertainties (b) PERT network deals with uncertainties and
involved in the estimation of times. The hence three-time estimations are considered
time required is deterministic and hence (Optimistic Time, Most Likely Time and
only one time is considered. Pessimistic Time)
(c) CPM times are related to cost. That is (c) As there is no certainty of time, activity
can be by decreasing the activity duration cannot be reduced. Hence cost
duration direct costs increased (crashing cannot be expressed correctly. We can say
of activity duration is possible) expected cost of completion of activity
crashing of activity duration is not possible)

The academic differences between PERT network and CPM network are:

(i) PERT is event oriented and CPM is activity oriented. This is to say that while discussing
about PERT network, we say that Activity 1-2, Activity 2-3 and so on. Or event 2 occurs
after event 1 and event 5 occurs after event 3 and so on. While discussing CPM network, we
say that Activity A follows activity B and activity C follows activity B and so on. Referring
to the network shown in Figure 4.11, we can discuss as under.

Haramaya University, Department of Management 141

 Operations Research

PERT way: Event 1 is the predecessor to event 2 or event 2 is the successor to event 1.
Events 3 and 4 are successors to event 2 or event 2 is the predecessor to events 3
and 4.

CPM way: Activity 1-2 is the predecessor to Activities 2-3 and 2-4 or Activities 2-3 and 2-4
are the successors to activity 1-2.

(ii) PERT activities are probabilistic in nature. The time required to complete the PERT activity
cannot be specified correctly. Because of uncertainties in carrying out the activity, the time
cannot be specified correctly. Say, for example, if you ask a contractor how much time it
takes to construct the house, he/she may answer you that it may take 5 to 6 months. This is
because of his/her expectation of uncertainty in carrying out each one of the activities in the
construction of the house. Another example is if somebody asks you how much time you
require to reach railway station from your house, you may say that it may take 1 to 1½ hours.
This is because you may think that you may not get a transport facility in time. Or on the way
to station, you may come across certain work, which may cause delay in your journey from
house to station. Hence PERT network is used when the activity times are probabilistic.

Figure 4.11. Logical relationship in PERT and CPM.

Figure 4.12 Three Time estimates.

Haramaya University, Department of Management 142
 Operations Research

There are three-time estimates in PERT, they are:

(a) Optimistic Time: Optimistic time is represented by 𝑡𝑜 . Here the estimator thinks that
everything goes on well and he/she will not come across any sort of uncertainties and
estimates lowest time as far as possible. He/she is optimistic in his thinking.
(b) Pessimistic Time: This is represented by 𝑡𝑝 . Here estimator thinks that everything goes
wrong and expects all sorts of uncertainties and estimates highest possible time. He/she is
pessimistic in his thinking.
(c) Likely Time: This is represented by 𝑡𝐿 . This time is in between optimistic and pessimistic
times. Here the estimator expects he/she may come across some sort of uncertainties and
many a time the things will go right. So, while estimating the time for a PERT activity, the
estimator will give the three-time estimates. When these three estimates are plotted on a
graph, the probability distribution that we get is closely associated with Beta Distribution
curve. For a Beta distribution curve as shown in figure 5.4, the characteristics are:

Standard deviation:

𝑡𝑝 − 𝑡𝑜
𝜎=
6

𝑡𝑝 − 𝑡𝑜 is known as range.

Variance:

𝑡𝑝 − 𝑡𝑜 2
𝜎2 = ( )
6

𝑡𝑜 +4𝑡𝐿 +𝑡𝑝
Expected Time or Average Time: 𝑡𝐸 = 6

These equations are very important in the calculation of PERT times. Hence the
student has to remember these formulae.

Haramaya University, Department of Management 143

 Operations Research

4.4 PERT/CPM Network Components and Precedence Relationship

PERT and CPM are two techniques that are widely used in planning and scheduling the large
projects. In planning and scheduling the activities of large sized projects, the two network
techniques — PERT and CPM — are used conveniently to estimate and evaluate the project
completion time and control the resources to see that the project is completed within the
stipulated time and at minimum possible cost. Many managers, who use the PERT and CPM
techniques, have claimed that these techniques drastically reduce the project completion time.
But it is wrong to think that network analysis is a solution to all bad management problems. In
the present chapter, let us discuss how PERT and CPM are used to schedule the projects.

In PERT and CPM, the milestones are represented as events. Event or node is either starting of
an activity or ending of an activity. Activity is represented by means of an arrow, which is
resource consuming. Activity consumes resources like time, money and materials. Event will not
consume any resource, but it simply represents either starting or ending of an activity. Event can
also be represented by rectangles or triangles. When all activities and events in a project are
connected logically and sequentially, they form a network, which is the basic document in
network-based management. The basic steps for writing a network are:

(a) List out all the activities involved in a project. Say, for example, in building construction,
the activities are:
(i) Site selection,
(ii) Arrangement of Finance,
(iii) Preparation of building plan,
(iv) Approval of plan by municipal authorities,
(v) Purchase of materials,
(vi) Digging of foundation,
(vii) Filling up of foundation,
(viii) Building superstructure,
(ix) Fixing up of doorframes and window frames,
(x) Roofing,
(xi) Plastering,

Haramaya University, Department of Management 144

 Operations Research

(xii) Flooring,
(xiii) Electricity and water fittings,
(xiv) Finishing.
(b) Once the activities are listed, they are arranged in sequential manner and in logical order.
For example, foundation digging should come before foundation filling and so on.
(c) After arranging the activities in a logical sequence, their time is estimated and written
against each activity. For example: Foundation digging: 10 days, or 1½ weeks.
(d) Some of the activities do not have any logical relationship, in such cases; we can start
those activities simultaneously. For example, foundation digging and purchase of
materials do not have any logical relationship. Hence, both of them can be started
simultaneously. Suppose foundation digging takes 10 days and purchase of materials
takes 7 days, both of them can be finished in 10 days. And the successive activity, say
foundation filling, which has logical relationship with both of the above, can be started
after 10 days. Otherwise, foundation digging and purchase of materials are done one after
the other; filling of foundation should be started after 17 days.
(e) Activities are added to the network, depending upon the logical relationship to complete
the project network.

Some of the points to be remembered while drawing the network are:

(i) There must be only one beginning and one end for the network, as shown in Figure 4.13.

Haramaya University, Department of Management 145

 Operations Research

Right Wrong
Figure 4.13. Writing the Network

(ii) Event number should be written inside the circle or node (or triangle/square/rectangle
etc.). Activity name should be capital alphabetical letters and would be written above the
arrow. The time required for the activity should be written below the arrow as in Figure
4.114.

Figure 4.14. Numbering and naming the activities.

(iii)While writing network, see that activities should not cross each other. And arcs or loops
as in Figure 4.15. should not join Activities.

Wrong

Haramaya University, Department of Management 146

 Operations Research

Figure 4.15. Crossing of activities not allowed.

(iv) While writing network, looping should be avoided. This is to say that the network arrows
should move in one direction, i.e., starting from the beginning should move towards the
end, as in Figure 4.16.

Figure 4.16. Looping is not allowed.

(v) When two activities start at the same event and end at the same event, they should be
shown by means of a dummy activity as in Figure 4.17. Dummy activity is an activity,
which simply shows the logical relationship and does not consume any resource. It
should be represented by a dotted line as shown. In the figure, activities C and D start at
the event 3 and end at event 4. C and D are shown in full lines, whereas the dummy
activity is shown in dotted line.

Figure 4.17. Use of Dummy activity.

(vi) When the event is written at the tail end of an arrow, it is known as tail event. If event is
written on the head side of the arrow it is known as head event. A tail event may have any
number of arrows (activities) emerging from it. This is to say that an event may be a tail
event to any number of activities. Similarly, a head event may be a head event for any
number of activities. This is to say that many activities may conclude at one event. This is
shown in Figure 4.18.

Haramaya University, Department of Management 147

 Operations Research

Figure 4.18. Tail event and Head event.

(vii) Numbering of events: Once the network is drawn the events are to be numbered. In
PERT network, as the activities are given in terms of events, we may not experience
difficulty. Best in case of CPM network, as the activities are specified by their name, is
we have to number the events. For numbering of events, we use D.R. Fulkerson’s rule.
As per this rule:
• An initial event is an event, which has only outgoing arrows from it and no
arrow enters it. Number that event as 1.
• Delete all arrows coming from event 1. This will create at least one more
initial event. Number these initial events as 2, 3 etc.
• Delete all the outgoing arrows from the numbered element and which will
create some more initial events. Number these events as discussed above.
• Continue this until you reach the last event, which has only incoming arrows
and no outgoing arrows.

4.4.1. Types of Network Diagrams

There are two main types of network diagrams in project management: the arrow diagramming
method (ADM), also known as “activity network diagram” or “activity on arrow”; and the
precedence diagramming method (PDM), also known as “node network” or “activity on node.”

[Link]. Arrow Diagram Method (ADM)

The ADM, or activity network diagram, uses arrows to represent activities associated with the
project. It’s important to note that, due to the ADM’s limitations, it is no longer widely used in

Haramaya University, Department of Management 148

 Operations Research

project management. However, it’s still useful to understand ADMs, so that you can recognize
these diagrams if they arise in your work environment. In ADM:

• The tail of the arrow represents the start of the activity and the head represents the finish.
• The length of the arrow typically denotes the duration of the activity.
• Each arrow connects two boxes, known as “nodes.” The nodes are used to represent the
start or end of an activity in a sequence. The starting node of an activity is sometimes
called the “i-node,” with the final node of a sequence sometimes called the “j-node.”
• The only relationship between the nodes and activity that an ADM chart can represent is
“finish to start” or FS.

Occasionally, “dummy activities”—arrows that do not represent a direct relationship—need to be

included in ADM network diagrams. In the diagram below, activity C can only occur once
activities A and B are complete; in the network diagram, you’ve connected activity A to activity
C. Perhaps we’re talking about tiling a floor (activity C): It can only begin once the concrete is
poured (activity A) and the permits are obtained (activity B). Since activities A and B are not
directly related—A doesn’t lead to B, and B doesn’t lead to A—you’ll need to draw a dummy
activity between B and C to show that C is dependent on B being completed. An ADM chart also
does not have a way to encapsulate lead and lag times without introducing new nodes and
activities.

[Link]. Precedence Diagram Method (PDM)

PDM network diagrams are frequently used in project management today and are a more
efficient alternative to ADMs. In the precedence diagramming method for creating network
diagrams, each box, or node, represents an activity—with the arrows representing relationships
between the different activities. The arrows can therefore represent all four possible
relationships:

• “Finish to Start” (FS): When an activity cannot start before another activity finishes
• “Start to Start” (SS): When two activities are able to start simultaneously
• “Finish to Finish” (FF): When two tasks need to finish together

Haramaya University, Department of Management 149

 Operations Research

• “Start to Finish” (SF): This is an uncommon dependency and only used when one activity
cannot finish until another activity starts

In PDM, lead times and lag times can be written alongside the arrows. If a particular activity is
going to require 10 days to elapse until the next activity can occur, for example, you can simply
write “10 days” over the arrow representing the relationship between the connected nodes.

Now let us see how to deal with the PERT problems.

Haramaya University, Department of Management 150

 Operations Research

Example 1

A small project is composed of 7 activities whose time estimates are listed below. Activities are
being identified by their beginning (𝑖) and ending (𝑗) node numbers.

Activities Time in weeks

𝒊 𝒋 𝒕𝒐 𝒕𝑳 𝒕𝒑
1 2 1 1 7
1 3 1 4 7
1 4 2 2 8
2 5 1 1 1
3 5 2 5 14
4 6 2 5 8
5 6 3 6 15
Required:

• Draw the network

• Calculate the expected variances for each
• Find the expected project completed time
• Calculate the probability that the project will be completed at least 3 weeks than expected
• If the project due date is 18 weeks, what is the probability of not meeting the due date?

Solution

Haramaya University, Department of Management 151

 Operations Research

Activities Time in weeks 𝒕𝒐 + 𝟒𝒕𝑳 + 𝒕𝒑 𝒕𝑬 𝒕𝒑 − 𝒕𝒐 𝝈𝟐

𝒕𝑬 = 𝝈=
𝒊 𝒋 𝒕𝒐 𝒕𝑳 𝒕𝒑 𝟔 𝟔

1 2 1 1 7 2 6 1 1
1 3 1 4 7 6 6 1 1
1 4 2 2 8 3 6 1 1
2 5 1 1 1 1 0 0 0
3 5 2 5 14 6 12 2 4
4 6 2 5 8 5 6 1 1
5 6 3 6 15 7 12 2 4

Critical activities Variance

1–3 1
3-5 4
5-6 4

∑ 𝝈𝟐 9

√∑ 𝝈𝟐 = √𝟗 = 𝟑

Probability of completing the project at least 3 weeks earlier i.e., 16 in weeks

𝑡𝐿 = 16 𝑤𝑒𝑒𝑘𝑠, 𝑡𝐸 = 19 𝑤𝑒𝑒𝑘𝑠

𝑡𝐿 − 𝑡𝐸 = 16 − 19 = −3 𝑤𝑒𝑒𝑘𝑠

𝑡𝐿 − 𝑡𝐸 𝟑
𝑍= =− = −𝟏
√∑ 𝝈𝟐 𝟑

From table the probability of completing the project = 15.9% 5. if TL = 18 weeks.

𝟏𝟖−𝟏𝟗 𝟏
Probability of completing in 11 weeks is = −𝟑
𝟑

From table the probability = 38.2%

Haramaya University, Department of Management 152

 Operations Research

Probability of not meeting due date = 100 – 38.2 = 61.8%

i.e., 61.8% of the time the manager cannot complete the project by due date.

Example 2

There are seven activities in a project and the time estimates are as follows:

Time in weeks
Activities 𝒕𝒐 𝒕𝑳 𝒕𝒑
A 2 6 10
B 4 6 12
C 2 3 4
D 2 4 6
E 3 6 9
F 6 10 14
G 1 3 5
The logical of activities are:

1) Activities A and B start at the beginning of the project.

2) When A is completed, C and D start.
3) E can start when B and D are finished.
4) F can start when B, C and D are completed and is the final activity.
5) G can start when F is finished and is final activity.

Required:

(a) What is the expected time of the duration of the project?

(b) What is the probability that project will be completed in 22 weeks?

Solution

Haramaya University, Department of Management 153

 Operations Research

First, we use to establish predecessor and successor relationship and then find standard deviation
σ, variance 𝜎 2 and expected time of completing activities, 𝑡𝐸 .

Activities Predecessor Time in weeks 𝒕𝒐 + 𝟒𝒕𝑳 + 𝒕𝒑 𝒕 𝒑 − 𝒕𝒐 𝝈𝟐

𝒕𝑬 = 𝝈=
𝟔 𝟔
Event 𝒕𝒐 𝒕𝑳 𝒕𝒑

A – 2 6 10 6 8 1.77
= 1.33
6
B – 4 6 12 10 8 1.77
= 1.33
6
C A 2 3 4 3 2 0.11
= 0.33
6
D A 2 4 6 4 4 0.44
= 0.67
6
E B, D 3 6 9 5 6 1
=1
6
F B, C, D 6 10 14 10 8 1.77
= 1.33
6
G F 1 3 5 3 4 0.44
= 0.67
6

Now to write network the logical (predecessor) relationship is considered.

After writing the network, numbering of events and 𝑡𝐸 is entered on the network. Next the
project completion time is worked out. The project completion time 𝑡𝐸 = 23 weeks. This project
has two critical paths i.e. A – D – F – G and B – F – G.

Haramaya University, Department of Management 154

 Operations Research

Critical activities Variance (𝝈𝟐 )

A 1.77
D 0.44
F 1.77
G 0.44

∑ 𝝈𝟐 4.44

√∑ 𝝈𝟐 = √𝟒. 𝟒𝟒 = 𝟐. 𝟏𝟎

Critical activities Variance (𝝈𝟐 )

B 1.77

F 1.77

G 0.44

∑ 𝝈𝟐 3.98

√∑ 𝝈𝟐 = √𝟑. 𝟗𝟖 = 𝟏. 𝟗𝟗

In the problem TL is given as 22 weeks. Therefore TL – TE = 22 – 23 = –1

Therefore, probability of completing the project in 22 weeks:

–1 / 2.10 = – 0.476 OR –1 / 1.99 = 0.502

The probability of completing the project is approximately 49%.

CPM is a resource-utilization algorithm for scheduling a set of project activities. The essential
technique for using CPM is to construct a model of the project that includes a list of all tasks
required to complete the project, the dependencies between the tasks, and the estimate of time
(duration) that each activity will take to complete. With this information, you can determine the
critical path by identifying the longest stretch of dependent activities and measuring them from
start to finish. First, one has to establish the logical relationship between activities. That is
predecessor and successor relationship, which activity is to be started after a certain activity. The
essential concept behind critical path analysis is that you can’t start certain tasks until others are

155
 Operations Research

finished. These tasks must be done in a sequence, with each stage completed before the next
stage can begin. The critical path consists of the longest sequence of activities from start to finish
that must be completed to ensure the project is finished by a certain time. The critical path
analysis consists the following points.

• Earliest Start (ES) = earliest time at which an activity can start, assuming all
predecessors have been completed.
• Earliest Finish (EF) = earliest time at which an activity can be finished.
• Latest Start (LS) = latest time at which an activity can start so as to not delay the
completion time of the entire project.
• Latest Finish (LF) = latest time by which an activity has to be finished so as to not delay
the completion time of the entire project.

Forward Pass and Backward Pass

Forward Pass

Forward pass is a technique to move forward through network diagram to determining project
duration and finding the critical path or free float of the project. Under this method the following
rules to be considered.

• Begin at starting event and work forward

• Earliest Start Time Rule:
• If an activity has only one immediate predecessor, its ES equals the EF of the
predecessor.
• If an activity has multiple immediate predecessors, its ES is the maximum of all the
EF values of its predecessors.
• ES = Max (EF of all immediate predecessors).
• Earliest Finish Time Rule:
• The earliest finish time (EF) of an activity is the sum of its earliest start time (ES) and
its activity time.
• EF = ES + Activity time

156
 Operations Research

Backward Pass

Whereas backward pass represents moving backward to the end result to calculate late start or to
find if there is any slack in the activity. Under this method the following rules to be considered.

• Begin with the last event and work backwards

• Latest Finish Time Rule:
• If an activity is an immediate predecessor for just a single activity, its LF equals the
LS of the activity that immediately follows it.
• If an activity is an immediate predecessor to more than one activity, its LF is the
minimum of all LS values of all activities that immediately follow it.
• LF = Min (LS of all immediately following activities)
• Latest Start Time Rule:
• LS of an activity is the difference of its LF and activity time.
• LS = LF – Activity time

Example 1

A paper manufacturing operation has the following activities, their predecessors and processing
time.

Activity Description Immediate Predecessors Time/weeks

A Build internal components — 2
B Modify roof and floor — 3
C Construct collection stack A 2
D Pour concrete and install frame A, B 4
E Build high-temperature burner C 4
F Install pollution control system C 3
G Install air pollution device D, E 5
H Inspect and test F, G 2

Required:

157
 Operations Research

• Draw the diagram that show flows of activities

• Determine the critical path
• Compute the duration of the project
• Determine the total float time for each activity

Solution

• AON Network

• AOA Network

• Critical Path

Path Duration

158
 Operations Research

A C F H 2+2+3+2=9
A C E G H 2 + 2 + 4 + 5 + 2 = 15

A D G H 2 + 4 + 5 + 2 = 13

B D G H 3 + 4 + 5 + 2 = 14
• Duration of the project
• Critical Path = A C E G H
• Duration = 15 weeks
• Float time for each activity
On Critical
Activity ES EF LS LF LS – ES Path
A 0 2 0 2 0 Yes
B 0 3 1 4 1 No
C 2 4 2 4 0 Yes
D 3 7 4 8 1 No
E 4 8 4 8 0 Yes
F 4 7 10 13 6 No
G 8 13 8 13 0 Yes
H 13 15 13 15 0 Yes

Example 2

A company manufacturing plant and equipment for chemical processing is in the process of
quoting tender called by public sector undertaking. Help the manager to find the project
completion time to participate in the tender.

S. Mo. Activity Immediate Predecessors Time/days

1 A — 3

2 B — 4

3 C A 5

4 D A 6

5 E C 7

6 F D 8

7 G B 9

888 H E, F, G 3

159
 Operations Research

Required:

• Draw the diagram that shows flows of activities

• Determine the critical path
• Compute the duration of the project
• Determine the total float time for each activity

Solution

• AOA Network

• Critical path

Path Duration
A C E H 3 + 5 + 7 + 3 = 18
A D F H 3 + 6 + 8 + 3 = 20

B G H 4 + 9 + 3 = 16

The critical path: A - D - F - H

• Duration of the project is 20 days

• Float time for each activity

On Critical
Activity ES EF LS LF LS – ES Path
A 0 3 0 3 0 Yes
B 0 4 4 8 4 No

160
 Operations Research

C 3 8 5 10 2 No
D 3 9 3 9 0 Yes
E 8 15 10 17 2 No
F 9 17 9 17 0 Yes
G 4 13 8 17 4 No
H 17 20 17 20 0 Yes

161
 Operations Research

Chapter Five

Decision Theory

Introduction

In the previous chapters of the course Operations Research, we focused mainly on decision
making when the consequences of alternative decisions are known with a reasonable degree of
certainty. This decision-making environment enabled formulating helpful mathematical models
(linear programming etc.) with objective functions that specify the estimated consequences of
any combination of decisions. Although these consequences usually cannot be predicted with
complete certainty, they could at least be estimated with enough accuracy to justify using such
models (along with sensitivity analysis, etc.). However, decisions often must be made in
environments that are much more fraught with uncertainty.

Consequently, in this chapter, we deal with decision making models under uncertainty, under the
condition of risk, with certainty and with utilities. A decision problem, where a decision-maker is
aware of various possible states of nature but has insufficient information to assign any
probabilities of occurrence to them, is termed as decision-making under uncertainty. A decision
under uncertainty is when there are many unknowns and no possibility of knowing what could
occur in the future to alter the outcome of a decision. In case of decision-making under
uncertainty the probabilities of occurrence of various states of nature are not known. When these
probabilities are known or can be estimated, the choice of an optimal action, based on these
probabilities, is termed as decision making under risk. A condition of certainty exists when the
decision-maker knows with reasonable certainty what the alternatives are, what conditions are
associated with each alternative, and the outcome of each alternative. Under conditions of
certainty, accurate, measurable, and reliable information on which to base decisions is available.
Utility theory is a branch of decision analysis that is concerned with building models to explain
and guide choice behavior under uncertainty in situations in which “long run” expected values
are too simplistic.

162
 Operations Research

Objectives of the Chapter

After studying this Chapter, students should be able to:

➢ Explain main issues related to decision theory;

➢ Discuss the decision-making environment;

➢ Make decisions in conditions of uncertainty, risk, certainty, and with utilities.

5.1. Overview of Decision Theory

The success or failure that an individual or organization experiences depends to a large extent on
the ability to make appropriate decisions. Making a decision requires an enumeration of feasible
and viable alternatives (courses of action or strategies), the projection of consequences
associated with different alternatives, and a measure of effectiveness (or an objective) by which
the most preferred alternative is identified. Decision is the conclusion of a process designed to
weigh the relative merits of a set of available alternatives so that the most preferred course of
action can be selected for implementation. Decision making is a managerial process of
identifying, developing, analyzing alternative courses of action and selecting the most feasible
one to solve a problem. Decision-making involves all that is necessary to identify the most
preferred choice to satisfy the desired goal or objective. Hence decision-making process must
involve a set of goals or objectives, a system of priorities, methods of enumerating the alternative
courses of feasible and viable courses and a system of identifying the most favorable alternative.
One must remember that the decisions are sequential in nature. It means to say that once we
select an alternative, immediately another question arises. For example, if you take a decision to
purchase a particular material, the next question is how much. The next question is at what price.
The next question is from whom… Like that there is no end.

In management theory we study that the essence of management is to make decisions that
commit resources in the pursuit of organizational objectives. Resources are limited and wants
and needs of human beings are unlimited and diversified and each wants to satisfy his needs in
an atmosphere, where resources are limited. Here the decision theory helps to take a certain

163
 Operations Research

decision to have most satisfactory way of satisfying their needs. Decisions are made to achieve
these goals and objectives.

When a group of people is working together in an organization, due to individual behavior and
mentality, there exists a conflict between two individuals. Not only that in an organization, each
department has its own objective, which is subordinate to organizational goal, and in fulfilling
departmental goals, there exists a conflict between the departments. Hence, any decision maker
has to take all these factors into consideration, while dealing with a decision process, so that the
effect of conflicts between departments or between subordinate goals is kept at minimum in the
interest of achieving the overall objective of the organization. Decision making related theories
important in this regard.

Decision theory is an analytical and systematic approach to the study of decision-making in

which data on the occurrence of various outcomes (or consequences) can be evaluated to allow
the decision-maker to identify a suitable alternative (or course of action). Decision theory deals
with methods for determining the optimal course of action when a number of alternatives are
available and their consequences cannot be forecast with certainty. The degree of certainty is
assigned to decision models that aid decision-makers in making the best decisions possible. The
scale of certainty can range from complete certainty to complete uncertainty. The region that
falls between these two extreme points corresponds to decision-making under risk (probabilistic
problems).

5.2. Types of Decision-Making Environment

The decision theory has assumed an important position, because of contribution of such diverse
disciplines as philosophy, economics, psychology, sociology, statistics, political science and
operations research to the area decision theory. In decision-making process, we recognize two
phases: (1) How to formulate goals and objectives, enumerate environmental constraints, identify
alternative strategies and project relevant payoffs. (2) Concentration on the question of how to
choose the optimal strategy when we are given a set of objectives, strategies, payoffs. We
concentrate more on the second aspect in our discussion.

164
 Operations Research

In general, decisions are classified as strategic decision, which is related to the organization's
outside environment, administrative decisions dealing with structuring resources and operational
decisions dealing with day-to-day problems. Depending on the nature of the problem there are
programmed decisions, to solve repetitive and well-structured problems, and non-programmed
decisions, designed to solve non-routine, novel, ill structured problems. Depending on the scope,
complexity and the number of people employed decision can be divided as individual and
managerial decisions. Depending on the sphere of interest, as political, economic, or scientific
etc. decision can be divided as static decision requiring only one decision for the planning
horizon and dynamic decision requiring a series of decisions for the planning horizon.

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 payoff 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
conditions of certainty (DMUC) and decision-making under conditions of uncertainty (DMUU)
at the two extreme points on a scale. The region that falls between these extreme points
corresponds to the concept of probabilistic models and is referred to as "decision-making under
risk" (DMUR). Hence, we can say that most of the decision-making problems fall into the
category of decision-making under risk, and the assumed degree of certainty is only one aspect
of a decision problem.

A decision problem is characterized by decision alternatives, states of nature and resulting

payoffs. Alternatives are course of actions or strategies that may be chosen by the decision
maker. State of nature is occurrence or a situation over which the decision maker has little or no
control. States of nature should be defined so that they are mutually exclusive and collectively
exhaustive. The consequence resulting from a specific combination of a decision alternative and
a state of nature is a payoff. A table showing payoffs for all combinations of decision
alternatives and states of nature is a payoff table. Payoffs can be expressed in terms of profit,
cost, time, distance or any other appropriate quantifiable measure.

Steps in Decision Theory Approach

165
 Operations Research

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) Choose the criterion that results in the largest payoff.

4.3. Decision Making Under Uncertainty

Decision-making under uncertainty (DMUU) entails the selection of a course of action when we
do not know with certainty the results that each alternative action will yield. This type of
decision problems can be solved by statistical techniques along with good judgment and
experience. In order to select the best alternative under DMUU there are three approaches such
as Maximax, Maximin and equally likely.

• Maximax
• Find the alternative that maximizes the maximum outcome for every alternative.
• Pick the outcome with the maximum number.
• Highest possible gain.
• Maximin
• Find the alternative that maximizes the minimum outcome for every alternative.
• Pick the outcome with the minimum number.
• Least possible loss.
• Equally likely
• Find the alternative with the highest average outcome.
• Pick the outcome with the maximum number.
• Assumes each state of nature is equally likely to occur.

Example 1

Consider the following problem with: 3 decision alternatives and 2 states of nature with the
following payoff table representing profits (in Birr):

166
 Operations Research

Alternative State of Nature

Favorable Market Unfavorable Market
Construct large plant 200,000 -180,000
Construct small plant 100,000 -20,000
Do nothing 0 0
Required: Select the best alternative under

• Maximax
• Maximin
• Equally likely

Solution

State of Nature
Alternative Favorable Unfavorable Maximum Minimum Average
Market Market in Raw in Raw in Raw
Construct large plant 200,000 -180,000 200,000 -180,000 10,000
Construct small plant 100,000 -20,000 100,000 -20,000 40,000
Do nothing 0 0 0 0 0
• Maximax choice is to construct a large plant
• Maximin choice is to do nothing
• Equally likely choice is to construct a small plant

Example 2

Consider the following problem with: 4 decision alternatives in relation to stations with different
size and 3 states of nature with the following payoff table representing profits (in Birr):

State of Nature
Station Good Market Fair Market Poor Market
Small 50,000 20,000 -10,000
Medium 80,000 30,000 -20,000
Large 100,000 30,000 -40,000

167
 Operations Research

Very large 300,000 25,000 -160,000

Required: Select the best alternative under

• Maximax
• Maximin
• Equally likely
• Plot the graph
Solution

State of Nature Maximum Minimum Average

Station Good Market Fair Market Poor Market in Raw in Raw in Raw
Small 50,000 20,000 -10,000 50,000 -10,000 20,000
Medium 80,000 30,000 -20,000 80,000 -20,000 30,000
Large 100,000 30,000 -40,000 100,000 -40,000 30,000
Very large 300,000 25,000 -160,000 300,000 -160,000 55,000
• Maximax choice is large station
• Maximin choice is small station
• Equally likely choice is large station
• The graph:

168
 Operations Research

5.4. Decision Making Under Risk

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: (1) availability of more than one strategy,
(2) the existence of more than one states of nature, (3) the relevant outcomes, (4) the probability
distribution of outcomes associated with each strategy, (5) each possible state of nature has an
assumed probability, (6) states of nature are mutually exclusive, and (7) probabilities must sum
to 1. The optimal strategy in decision making under risk is identified by the strategy with highest
expected utility (or highest expected monetary value (EMV)).

169
 Operations Research

EMV = (Payoff of the 1st state of nature) x (Probability of 1st state of nature)

+ (Payoff of the 2nd state of nature) x (Probability of 2nd state of nature)

+…+ (Payoff of the last state of nature) x (Probability of last state of nature)

Example 1

Consider the following problem with: 3 decision alternatives and 2 states of nature with the
following payoff table representing profits (in Birr) as well as probabilities of states of nature:

Alternative State of Nature

Favorable Market Unfavorable Market
Construct large plant (𝐴1 ) 200,000 -180,000
Construct small plant (𝐴2 ) 100,000 -20,000
Do nothing (𝐴3 ) 0 0
Probabilities 0.5 0.5

Required: Compute EMV and identify the highest EMV

Solution

EMV (𝐴1 ) = (200,000) (0.5) + (180,000) (0.5) = Br. 10,000

EMV (𝐴2 ) = (100,000) (0.5) + (20,000) (0.5) = Br. 40,000

EMV (𝐴3 ) = (0) (0.5) + (0) (0.5) = Br. 0

The highest EMV: EMV (𝐴2 ) = Br. 40,000

Example 2

Consider the following problem with 5 decision alternatives related to results of each book
stocked and sold (Br.) and 5 states of nature related to their demand. Thus, the payoff table is:

170
 Operations Research

Stock Demand
70 75 80 85 90
70 2100 2100 2100 2100 2100
75 1870 2250 2250 2250 2250
80 1640 2020 2400 2400 2400
85 1410 1790 2170 2550 2550
90 1180 1560 1940 2320 2700
Probabilities 0.15 0.30 0.30 0.20 0.05

Required: Compute EMV and identify the highest EMV

Solution

EMV (70) = (2100) (0.15) + (2100) (0.3) + (2100) (0.3) + (2100) (0.2) + (2100) (0.05)

= Br. 2,100

EMV (75) = (1870) (0.15) + (2250) (0.3) + (2250) (0.3) + (2250) (0.2) + (2250) (0.05)

= Br. 2,193

EMV (80) = (1640) (0.15) + (2020) (0.3) + (2400) (0.3) + (2400) (0.2) + (2400) (0.05)

= Br. 2,172

EMV (85) = (1410) (0.15) + (1790) (0.3) + (2170) (0.3) + (2550) (0.2) + (2550) (0.05)

= Br. 2,037

EMV (90) = (1180) (0.15) + (1560) (0.3) + (1940) (0.3) + (2320) (0.2) + (2700) (0.05)

= Br. 1,829

The highest EMV: EMV (75) = Br. 2,193

171
 Operations Research

5.5. Decision Making Under Certainty

Decision-making under conditions of certainty assumes that all relevant information required to
make a decision is certain in nature and well known. It uses a deterministic model with complete
knowledge, stability, and no ambiguity. To make a decision, the manager will have to be quite
aware of the strategies available and their payoffs, and each strategy will have a unique payoff,
resulting in certainty. The decision-making may be based on single objective or on multiple
objectives.

The decision-maker knows with reasonable certainty what the alternatives are, what conditions
are associated with each alternative, and the outcome of each alternative. Under conditions of
certainty, accurate, measurable, and reliable information on which to base decisions is available.
It tries to answer the question, "Is the cost of perfect information worth it?" It determines the
expected value of perfect information (EVPI). EVPI is the difference between the payoff under
certainty and the payoff under risk.

EVPI = Expected value under certainty - Maximum EMV

Expected value under certainty = (Best outcome for 1st state of nature) x (Probability of 1st
state of nature)

+ (Best outcome for 2nd state of nature) x (Probability of 2nd

state of nature)

+…+ (Best outcome for last state of nature) x (Probability

of last state of nature)

Example 1

Consider the following problem with: 3 decision alternatives and 2 states of nature with the
following payoff table representing profits (in Birr) as well as probabilities of states of nature:

Alternative State of Nature

Favorable Market Unfavorable Market

172
 Operations Research

Construct large plant 200,000 -180,000

Construct small plant 100,000 -20,000
Do nothing 0 0
Probabilities 0.5 0.5
Required:

• Compute Expected value under certainty

• Compute EVPI

Solution

Expected value under certainty = 200,000 × 0.5 + 0 × 0.5

= 𝐵𝑟. 100,000

EVPI = Expected value under certainty – Maximum of EMV

= 100,000 − 40,000

= 𝐵𝑟. 60,000

Therefore, the most the company should pay for perfect information is Br. 60,000.

Example 2

Consider the following problem with 5 decision alternatives related to results of each book
stocked and sold (Br.) and 5 states of nature related to their demand. Thus, the payoff table is:

Stock Demand
70 75 80 85 90
70 2100 2100 2100 2100 2100
75 1870 2250 2250 2250 2250
80 1640 2020 2400 2400 2400
85 1410 1790 2170 2550 2550

173
 Operations Research

90 1180 1560 1940 2320 2700

Probabilities 0.15 0.30 0.30 0.20 0.05
Required:

• Compute Expected value under certainty

Compute EVPI

Solution

Expected value under certainty

= 2,100 × 0.15 + 2,250 × 0.3 + 2,400 × 0.3 + 2,550 × 0.2 + 2,700 × 0.05

= 𝐵𝑟. 2,355

EVPI = Expected value under certainty – Maximum of EMV

= 2,355 − 2,193

= 𝐵𝑟. 162

Therefore, the most the company should pay for perfect information is Br. 162.

5.6. Decision Making with Utilities

People do not always just look at the highest expected monetary return to make decisions; they
often evaluate the risk. Utility combines monetary return with people’s attitude toward risk.
Utility function is a mathematical function that transforms monetary values into utility values
Utility assessment may assign the worst payoff a utility of 0 and the best payoff a utility of 1. A
standard gamble is used to determine utility values: When DM is indifferent between two
alternatives, the utility values of them are equal.

Utility theory is an approach for assessing risk attitudes quantitatively. An individual’s utility
function reflects their preference toward risk. The risk premium is the payoff amount that an
individual is willing to forgo to avoid risk. The break-even probability is the point at which an

174
 Operations Research

individual is indifferent between a guaranteed payoff and taking a gamble for a higher payoff.
The certainty equivalent is the amount an individual feels is equivalent to the payoff from an
uncertain gamble.

Example 1

Suppose in a personal investment you have Br. 10,000 to invest short-term. You are considering
3 options: bank deposit paying 4% return, bond fund with uncertain return and stock fund with
uncertain return. The payoff matrix which shows these alternatives and related states of nature
are provided below.

Alternative State of Nature

Rates Rise Rates Stable Rates Fall
Bank deposit 400 400 400
Bond fund -500 840 1,000
Stock fund -900 600 1,700
Solution
• Sort the payoff amounts from highest to lowest.
• Assign a utility to the highest payoff of U(X) = 1.
• Assign a utility to the lowest payoff of U(X) = 0.

Payoff, X Utility, U(X)

1,700 1.0
1,000 -
840 -
600 -
400 -
-500 -
-900 0.0
• U(1,700) = 1
• U(1000) = the probability you would give up a certain 1,000 to possibly win 1,700
payoff.

175
 Operations Research

• U(-900) = 0
• After deciding U(1,000) = 0.90, continue choosing U(X) preferences for the remaining
four payoffs.
Payoff, X Utility, U(X)
1,700 1.00
1,000 0.90
840 0.85
600 0.80
400 0.75
-500 0.35
-900 0.0
• Probability tree

176
 Operations Research

• We can find the Breakeven (BE) probability for each payoff by solving

Expected payoff = 1700p − 900(1−p)

Risk Premium = Payoff - Expected payoff

p = (Payoff + 900)/2600

Payoff, X Utility, U(X) Expected payoff Risk Premium BE probability

1,700 1.00 - - -
1,000 0.90 1,440 440 0.73
840 0.85 1,310 470 0.67
600 0.80 1,180 580 0.58
400 0.75 1,050 650 0.50
-500 0.35 10 510 0.15
-900 0.0 - - -
Expected payoff
• Expected payoff (1,000) = (1700 × 0.90) − (900 × 0.10) = 1,440
• Expected payoff (840) = (1700 × 0.85) − (900 × 0.15) = 1,310
• Expected payoff (600) = (1700 × 0.80) − (900 × 0.20) = 1,110
• Expected payoff (400) = (1700 × 0.75) − (900 × 0.25) = 1,050
• Expected payoff (-500) = (1700 × 0.35) − (900 × 0.65) = 10
177
 Operations Research

BE probability

(1000+900)
• BE probability (1,000) = = 0.73
2600
(840+900)
• BE probability (840) = = 0.67
2600
(600+900)
• BE probability (600) = = 0.58
2600
(400+900)
• BE probability (400) = = 0.50
2600
(−500+900)
• BE probability (-500) = = 0.15
2600

Risk Averse Utility Function

Risk Aversion: Risk premiums > 0 U(X) > Risk neutral Concave downward

Risk Taking Utility Function

Risk Taker: Risk premiums < 0 U(X) < Break-even Probability Concave upward utility function

178
 Operations Research

Payoff, X Utility, U(X) Expected payoff Risk Premium BE probability

1,700 1.00 - - -
1,000 0.60 660 340 0.73
840 0.55 530 310 0.67
600 0.45 270 330 0.58
400 0.40 140 260 0.50
-500 0.10 640 140 0.15
-900 0.0 - - -

Expected Values of The Risk Averse Utilities

Alternative State of Nature

Rates Rise Rates Stable Rates Fall Average Utility
Bank deposit 0.75 0.75 0.75 0.75
Bond fund 0.35 0.85 0.90 0.70
Stock fund 0.00 0.80 1.00 0.60

Expected Values of The Payoffs for Each Decision

Alternative State of Nature

Rates Rise Rates Stable Rates Fall Average Payoff
Bank deposit 400 400 400 400
Bond fund -500 840 1,000 447
Stock fund -900 600 1,700 467

Expected Values of The Risk Taker Utilities

Alternative State of Nature

Rates Rise Rates Stable Rates Fall Average Utility
Bank deposit 0.40 0.40 0.40 0.40
Bond fund 0.10 0.55 0.6 0 0.42
Stock fund 0.00 0.45 1.00 0.60

179
 Operations Research

Expected Values of The Payoffs for Each Decision

Alternative State of Nature

Rates Rise Rates Stable Rates Fall Average Payoff
Bank deposit 400 400 400 400
Bond fund -500 840 1,000 447
Stock fund -900 600 1,700 467

180
 Operations Research

Chapter Six

Game Theory

Introduction

Game theory generally refers to the study of mathematical models that describe the behavior of
logical decision-makers. Generally, a game refers to a situation involving a set of players who
each have a set of possible choices, in which the outcome for any individual player depends
partially on the choices made by other players. It is widely used in many fields such as
economics, political science, politics, and computer science, and can be used to model many
real-world scenarios. In business, game theory is beneficial for modelling competing behaviours
between economic agents. Businesses often have several strategic choices that affect their ability
to realize economic gain. For example, businesses may face dilemmas such as whether to retire
existing products or develop new ones or employ new marketing strategies. Businesses can often
choose their opponent as well. Some focus on external forces and compete against other market
participants. Others set internal goals and strive to be better than previous versions of itself.
Whether external or internal, companies are always competing for resources, attempting to hire
the best candidates away from their rivals, and gather the attention of customers away from
competing goods.

In this chapter of the course, Operations Research, we will discuss these issues with illustrations.
To this end, we will discuss the main concepts in relation to game theory: the two-person zero-
sum game, the game with saddle points, the game without saddle points, and the rule of
dominance.

Objectives of the Chapter

After studying this Chapter, students should be able to:

➢ Explain the main concepts in relation to game theory;

➢ Make decisions through the two-person zero-sum game;

181
 Operations Research

➢ Make decisions in consideration with the game with saddle points;

➢ Make decisions in consideration with the game without saddle points;

➢ Make decisions through the rule of dominance.

6.1. Overview of Game Theory

In previous chapters like Linear Programming etc., we have seen the problems related to
individual industrial concern and problems are solved to find out the decision variables which
satisfy the objective of the industrial unit. But there are certain problems where two or more
industrial units are involved in decision making under conflict situation. This means that
decision-making is done to maximize the benefits and minimize the losses. The decision-making
much depends on the decision made or decision variables chosen by the opponent business
organization. Such situations are known as game theory or competitive strategies. Competitive
strategies are a type of business games. When we hear the word game, we get to our mind like
pleasure giving games like Football, Badminton, Chess, etc. In these games we have two parties
or groups playing the game with definite well-defined rules and regulations. The outcome of the
game determines the winning of a group. In our discussion in Theory of Games, we are not
concerned with pleasure giving games but we are concerned with business games. What is a
business game?

Every business manager is interested in capturing the larger share in the market. To do this they
have to use different strategies (course of actions) to motivate the consumers to prefer their
product. For example, you might have seen in newspapers certain company is advertising for its
product by giving a number of (say 10) eyes and names of 10 cine stars and identify the eyes of
the stars and match the name with the eyes. After doing this, the reader has to write why he/she
likes the product of the company. For right entry they get a prize. This way they motivate the
readers to prefer the product of the company. When the opponent company sees this, they also
use similar strategy to motivate the potential market to prefer the product of their company. Like
this the companies advertise in series and measure the growth in their market share. This type of
game is known as business game. Managers competing for share of the market, army chief

182
 Operations Research

planning or execution of war, union leaders and management involved in collective bargaining
uses different strategies to fulfill their objective or to win over the opponent. All these are known
as business games or competitive situation. In business, competitive situations arise in
advertising and marketing campaigns by competing business firms.

Hence, Game theory is a theoretical framework for conceiving social situations among
competing players. In some respects, game theory is the science of strategy, or at least the
optimal decision-making of independent and competing actors in a strategic setting. Game theory
is a body of knowledge that deals with making decisions when two or more intelligent and
rational opponents are involved under conditions of conflict or competition. The competitors in
the game are called players.

The beginning of theory of games goes back to 20th century. But John Von Neumann and
Morgenstern have mathematically dealt the theory and published a well-known paper “theory of
Games and Economic Behavior” in 1944. The mathematical approach of Von Neumann utilizes
the Two-person Zero-Sum Game Minimax principle, which involves the fundamental idea of
minimization of the maximum losses. Many of the competitive problems can be handled by the
game theory but not all the competitive problems can be analyzed with the game theory. The
following terminologies are commonly used in Game theory.

Game: Any set of circumstances that has a result dependent on the actions of two or more
decision-makers (players).

Player: Each participant (interested party) of a game is called a player.

Strategy: The strategy of a player is the predetermined rule by which a player decides his course
of action from the list of courses of action during the game. A strategy may be of two types:

• Pure strategy - It is a decision, in advance of all plays, always to choose a particular

course of action.
• Mixed strategy - It is a decision, in advance of all plays, to choose a course of action
for each play in accordance with some particular probability distribution.

183
 Operations Research

Optimal strategy: Course of action which maximizes the profit of a player or minimizes his/her
loss is called an optimal strategy.

Payoff: The outcome of playing a game is called payoff.

Payoff matrix: When the players select their particular strategies, the payoffs (gains or losses)
can be represented in the form of a matrix called the payoff matrix.

Saddle point: A saddle point is an element of the payoff matrix, which is both the smallest
element in its row and the largest element in its column. Furthermore, the saddle point is also
regarded as an equilibrium point in the theory of games.

Value of the game: Refers to the expected outcome per play when players follow their optimal
strategy.

6.2. Two-person Zero-Sum Game

A game with only two players is called a two-person zero-sum game if the losses of one player
are equivalent to the gains of the other so that the sum of their net gains is zero. This game also
known as rectangular game.

In a two-person game, suppose that player A has m activities and player B has n activities. Then,
a payoff matrix can be formed by adopting the following rules:

• Row designations for each matrix are activities available to the player A.
• Column designations for each matrix are activities available to the player B.
• Cell entry 𝑣𝑖𝑗 is the payment to the player A in A’s payoff matrix when A chooses the
activity 𝑖 and B chooses the activity 𝑗.
• For a zero-sum game, the cell entry in player B’s payoff matrix will be negative
corresponding to the cell entry 𝑣𝑖𝑗 in player A’s payoff matrix so that the sum of payoff
matrices for the players A and B is ultimately zero, see Tables 6.1 and 6.2.

184
 Operations Research

Player B

1 2 … n
Player A 1 𝑣11 𝑣12 … 𝑣1𝑛
2 𝑣21 𝑣22 … 𝑣1𝑛
. . . . .
m 𝑣𝑚1 𝑣𝑚2 … 𝑣1𝑛

Table 6.1: Player A’s payoff matrix

Payer B
1 2 … N
1 −𝑣11 −𝑣12 … −𝑣1𝑛
Player A 2 −𝑣21 −𝑣22 … −𝑣1𝑛
. . . . .
M −𝑣𝑚1 −𝑣𝑚2 … −𝑣1𝑛

Table 6.2: Player B’s payoff matrix

Consider a two-person coin tossing game. Each player tosses an unbiased coin simultaneously.
Each player selects either a head (H) or a tail (T). If the outcomes match (i.e., (H, H) or (T, T))
then A wins Br. 4 from B; otherwise, B wins Br. 3 from A. Player A’s payoff matrix is given in
Table 6.3. This game is a two-person zero-sum game, since the winning of one player is taken as
losses for the other. Each player has his choice from amongst two pure strategies H and T.

Player B
H T
Player A H 4 -3
T -3 4
Table 6.3. Player A’s payoff matrix

So far we discussed two types of Two-person, Zero-sum games. In one of the most preferred
position for each player is achieved by adopting a single strategy. Hence this game is known as
pure strategy game. The second type requires the adoption by both players of a mixture or a
combination of different strategies as opposed to a single strategy. Therefore, this is termed as
mixed strategy game.

185
 Operations Research

In pure strategy game one knows, in advance of all plays that he/she will always choose only one
particular course of action. Thus, pure strategy is a decision rule always to select the same course
of action. Every course of action is pure strategy.

A mixed strategy is that in which a player decides, in advance to choose one of this course of
action in accordance with some fixed probability distribution. This in case of mixed strategy we
associate probability to each course of action (each pure strategy). The pure strategies, which are
used in mixed strategy game with non-zero probabilities, are termed as supporting strategies.
Mathematically, a mixed strategy to any player is an ordered set of ‘m’ non-negative real
numbers, which add to a sum unity (‘m’ is the number of pure strategies available to a player).

It is said above that in pure strategy game a player selects same strategy always, hence the
opponent will know in advance the choice. But the superiority of mixed strategy game over pure
strategy games is that the player is always kept guessing about the opponent’s choice as
innumerable combination of pure strategies one can adopt.

The purpose of the game theory is to determine the best strategies for each player on the basis of
maximin and minimax criterion of optimality. In this criterion a player lists his/her worst
possible outcomes and then he/she chooses that strategy which corresponds to the best of those
worst outcomes. The value of the game is the maxim guaranteed gain to player. The value is
denoted by ‘v’. The game whose value v = 0 is known as zero sum game or fair game. Solving
the game means to find the best strategies for both the players and find the value of the game.

The game theory does not insist on how a game should he played, but only tells the procedure
and principles by which the action should be selected. Hence, the game theory is a decision
theory useful in competitive situations. The fundamental theorem assures that there exists a
solution and the value of a rectangular game in terms of mixed strategies.

Characteristics or Properties of a Game

To classify the games, we must know the properties of the game. They are:
• Number of persons or groups who are involved in playing the game
• Number of strategies or courses of action each player or group have (they may be finite
or infinite).
186
 Operations Research

• Type of course of action or strategy.

• How much information about the past activities of other player is available to the players.
It may be complete or partly or may be no information available.
• The payoff may be such that the gains of some players may or may not be the direct
losses of other players.
• The players are independent in decision-making and they make the decision rationally.

6.3. Pure Strategies: Game with Saddle Point

In a zero-sum game, the pure strategies of two players constitute a saddle point if the
corresponding entry of the payoff matrix is simultaneously a maximum of row minima and a
minimum of column maxima. This decision-making is referred to as the minimax-maximin
principle to obtain the best possible selection of a strategy for the players.

In a pay-off matrix, the minimum value in each row represents the minimum gain for player A.
Player A will select the strategy that gives him the maximum gain among the row minimum
values. The selection of strategy by player A is based on maximin principle. Similarly, the same
pay-off is a loss for player B. The maximum value in each column represents the maximum loss
for Player B. Player B will select the strategy that gives him the minimum loss among the
column maximum values. The selection of strategy by player B is based on minimax principle. If
the maximin value is equal to minimax value, the game has a saddle point (i.e., equilibrium
point). Thus, the strategy selected by player A and player B are optimal.

Maxi(i) min(j) aij = mini(j) max(i) aij is called a game with saddle point. This makes us to
understand that the players in the game always use pure strategies. The element at the
intersection of their pure strategies is known as saddle point. The element at the saddle point is
the value of the game. As the players uses the pure optimal strategies, the game is known as
strictly determined game. A point to remember is that the saddle point is the smallest
element in the row and the greatest element in the column. Not all the rectangular games
will have saddle point, but if the game has the saddle point, then the pure strategies
corresponding to the saddle point are the best strategies and the number at the point of
intersection of pure strategies is the value of the game. Once the game has the saddle point
the game is solved. The rules for finding the saddle point are:

187
 Operations Research

• Select the minimums of each row and encircle them.

• Select the maximums of each column and square them.
• A point where both circle and square appears in the matrix at the same point is the
saddle point.

Another name given to saddle point is equilibrium point of the game and the
corresponding strategies form the equilibrium pair of strategies.

Example 1

Solve the game whose payoff matrix is given below:

Player B
I II III
I -2 15 -2
Player A II -5 -6 -4
III -5 20 -8

Table 6.4: A’s payoff matrix

Solution

We use the maximin (minimax) principle to determine the optimal strategy. The game has two saddle points
at positions (1, 1) and (1, 3).
Player B

I II III Row minimum

I -2 15 -2 -2 (Maximin)
II -5 -6 -4 -6
Player A III -5 20 -8 -8
Column maximum -2 20 -2

↑ Minimax ↑ Minimax

(i) The best strategy for player A is I.

(ii) The best strategy for player B is either I or III.

188
 Operations Research

(iii) The value of the game is −2 for player A and +2 for player B.

Example 2

Solve the game given below:

Player B
I II III
Player A I 1 9 2
II 8 5 4
Table 6.6. Player A’s payoff matrix

Solution

Player B
I II III Minimum
Player A I 1 9 2 1
II 8 5 4 4
Maximum 8 9 4

In the matrix given, row minimums and column maximums are indicted. The element of A’s
second strategy and B’s third strategy i.e., a (3, 2) is both row minimum and column maximum.
Hence 4 is the saddle point and pure strategy for A is second strategy and pure strategy for B is
third strategy. Hence answer is:

A (0.1), B (0, 0, 1) and the value of the game is v = +4. This means A will gain 4 units of money
B will lose 4 units of money and the sum of outcomes is zero.

Example 3

Solve the game whose pay of matrix is:

Player B
I II III
I -3 -2 6
Player A II 2 0 4
III 5 -2 -4

189
 Operations Research

Table 6.7: A’s payoff matrix

Solution

Player B
I II III Minimum
I -3 -2 6 -3
Player A II 2 0 4 0
III 5 -2 -4 -4
Maximum 5 0 6

Element at A(II) and B(II) is both column maximum and row minimum. Hence, the element 0 is
the saddle point. The answer is: A (0, 1, 0) and B (0, 1, 0) and the value v = 0.

6.4. The Rule of Dominance

The principle of dominance in Game Theory (also known as dominant strategy or

dominance method) states that if one strategy of a player dominates over the other strategy in
all conditions, then the later strategy can be ignored. A strategy dominates over the other only if
it is preferable over other in all conditions. The concept of dominance is especially useful for the
evaluation of two-person zero-sum games where a saddle point does not exist.

In case there is no saddle point the given game matrix (m × n) may be reduced to m × 2 or 2 × n
or 2 × 2 matrix, which will help us to proceed further to solve the game. The ultimate way is we
have to reduce the given matrix to 2 × 2 to solve mathematically.

Dominant Strategy Rules (Dominance Principle)

The general rules of dominance can be formulated as below:

• If all the elements of a column (say 𝑖 𝑡ℎ column) are greater than or equal to the
corresponding elements of any other column (say 𝑗 𝑡ℎ column), then the 𝑖 𝑡ℎ column is
dominated by the 𝑗 𝑡ℎ column and can be deleted from the matrix.

190
 Operations Research

• If all the elements of a row (say 𝑖 𝑡ℎ row) are less than or equal to the corresponding
elements of any other row (say 𝑗 𝑡ℎ row), then the 𝑖 𝑡ℎ row is dominated by the 𝑗 𝑡ℎ row
and can be deleted from the matrix.
• A pure strategy of a player may also be dominated if it is inferior to some convex
combinations of two or more pure strategies, as a particular case, inferior to the averages
of two or more pure strategies.

Note: At every reduction of the matrix, check for the existence of saddle point. If saddle point
found, the game is solved. Otherwise continue to reduce the matrix by method of dominance.

Consider the matrix given below:

Player B
I II
Player A I -2 -4
II 1 2

Let A play his first strategy, then he loses 2 units of money and loses 4 units of money when B
plays his second strategy. But when A plays his second strategy, he gains 1 unit of money for B’s
first strategy and gains 2 units of money, for B’s second strategy. Hence, A's second strategy
(pure strategy) is superior to A's first strategy or A's second strategy dominates A's first strategy
or A's first strategy is dominated by A's second strategy. We can closely examine and find that
elements of A's second strategy are greater than the elements of first strategy. Hence, we can
formulate general rule of dominance for rows. When the elements of 𝑟 𝑡ℎ row are greater than or
equals to elements of 𝑠 𝑡ℎ row, then 𝑟 𝑡ℎ row dominates 𝑠 𝑡ℎ row or 𝑠 𝑡ℎ row is dominated by 𝑟 𝑡ℎ
row.

Example 1

To discuss the principle of dominance, let us consider the matrix given below:

191
 Operations Research

Player B
I II III IV
Player A I 2 -4 -3 4
II 4 -3 -4 2

Solution

Player B
I II III IV Minimum
I 2 -4 -3 4 -4
Player A
II 4 -3 -4 2 -4
Maximum 4 -3 -3 4

The row minimums and column maximums show that the problem is not having saddle point.
Hence, we have to use method of dominance to reduce the size of the matrix.

(i) Consider the first and second strategies of B. If B plays the first strategy, he/she loses 2
units of money when A plays first strategy and 4 units of money when A plays second
strategy. Similarly, let us consider B’s second strategy, B gains 4 units of money when
A plays his/her first strategy and gains 3 units of money when A plays second strategy.
Irrespective of A’s choice, B will gain money. Hence for B his second strategy is
superior to his first strategy. In other words, B's second strategy dominates B's first
strategy. Or B’ first strategy is dominated by B's second strategy. Hence, we can
remove the first strategy of B from the game. The reduced matrix is:
Player B
II III IV
Player A I -4 -3 4
II -3 -4 2
(ii) Consider B’s III and IV strategy. When B plays IV strategy, he/she loses 4 units of
money when A plays his/her first strategy and 2 units of money when A plays his
second strategy. Whereas, when B plays his III strategy, he/she gains 3 units of money
and 4 units of money, when A plays his I and II strategy respectively. Hence B’s IV

192
 Operations Research

strategy (pure strategy) is dominating the third strategy. Hence, we can remove the
same from the game. The reduced matrix is:
Player B
II III
Player A I -4 -3
II -3 -4

In the above example, if we keenly observe, we see that the elements of second column
are smaller or less than the elements of column 4, similarly elements of III column also
smaller or less than the elements of column I and IV. Hence, we can write the
dominance rule for columns as When elements of a column, say 𝒊𝒕𝒉 are less than or
equals to the corresponding elements of 𝒋𝒕𝒉 column, then 𝒋𝒕𝒉 column is dominated
by 𝒊𝒕𝒉 column or 𝒊𝒕𝒉 column dominates 𝒋𝒕𝒉 column.

Example 2

The payoff matrix for player A is given in the table below to illustrate the principle of
dominance.

Player B
I II III IV
I 3 5 4 2
Player A
II 5 6 2 4
III 2 1 4 0
IV 3 3 5 2
Required: Use the principle of dominance to solve this problem.

Solution

Player B
I II III IV Minimum
I 3 5 4 2 2
II 5 6 2 4 2
Player A

193
 Operations Research

III 2 1 4 0 0
IV 3 3 5 2 2
Maximum 5 6 5 4

There is no saddle point in this game.

Using Dominance Property in Game Theory

If a column is greater than another column (compare corresponding elements), then delete that
column. Here, I and II column are greater than the IV column. So, player B has no incentive in
using his/her I and II course of action.

Player B
III IV
I 4 2
Player A II 2 4
III 4 0
IV 5 2

If a row is smaller than another row (compare corresponding elements), then delete that row.
Here, I and III row are smaller than IV row. So, player A has no incentive in using his I and III
course of action.

Player B
III IV
Player A II 2 4
IV 5 2

6.5. Mixed Strategies: Game Without Saddle Point

In rectangular games, when we have saddle point, the best strategies were the pure strategies.
Now let us consider the games, which do not have saddle points. In such cases, the best strategies
are the mixed strategies. While dealing with mixed strategies, we have to determine the

194
 Operations Research

probabilities with which each action should be selected.

If maximin value is not equal to minimax value, then the game is said to have no saddle point. In such a
case, both the players must determine an optimal mixture of strategies to find an equilibrium point. The optimal
strategy mixture for each player may be determined by assigning to each strategy its probability of being
chosen. The strategies so determined are called mixed strategies.

Points to be remembered in mixed strategy games are:

(a) If one of the players adheres to his optimal mixed strategy and the other player deviates
from his optimal strategy, then the deviating player can only decrease his yield and cannot
increase in any case (at most may be equal).

(b) If one of the players adheres to is optimal strategy, then the value of the game does not alter
if the opponent uses his supporting strategies only either singly or in any combination.

(c) If we add (or subtract) a fixed number say 1, to (from) each elements of the payoff matrix,
then the optimal strategies remain unchanged while the value of the game increases (or
decreases) by 1.

Let us consider a 2 × 2 game and get the formulae for finding the probabilities with which each
strategy to be selected and the value of the game.

Player B
𝑦1 𝑦2
I II
Player A 𝑥1 I 𝑎11 𝑎12
𝑥2 II 𝑎21 𝑎22

Let 𝑥1 and 𝑥2 be the probability with which A plays his first and second strategies respectively.
Similarly, B plays his first and second strategies with probability of 𝑦1 and 𝑦2 respectively.
Now:

x1 + x2 = 1, and y1 + y2 = 1.

195
 Operations Research

Let us work out expected gains of A and B when they play the game with probabilities of x1, x2
and y1 and y2.

A’s expected gains when:

• B plays his first strategy = a11 x1 + a21 x2

• When B plays his second strategy = a12 x1 + a22 x2

Similarly, B's gains when:

• A plays his first strategy = a11 y1 + a12 y2

• When A plays his second strategy = a21 y1 + a22 y2

Now let us assume that the v is the value of the game. As A is the maximin player, he wants to see
that his gains are ≥ v. As B is the minimax player, he wants to see that his gains must be always
≤v.

Therefore, we have:

a11 x1 + a21 x2 ≥ v

a12 x1 + a22 x2 ≥ v and

a11 y1 + a12 y2 ≤ v

a21 y1 + a22 y2 ≤ v

To find the value of x1, x2 and 𝑦1 , 𝑦2 we have to solve the above given inequalities. For
convenience, let us consider them to be equations to find the values of x1, x2 and 𝑦1 , 𝑦2 .
Therefore, we have:

a11 x1 + a21 x2 = v

a12 x1 + a22 x2 = v and

196
 Operations Research

a11 y1 + a12 y2 = v

a21 y1 + a22 y2 = v

Always we work out a solution of a 2 × 2 game by considering the above inequalities as strict
equalities. Now we can write above as:

a11 x1 + a21 x2 = v = a12 x1 + a22 x2

Or this can be written as:

x1 (a 11 – a 12) = x2 (a 22 – a 21) or

𝑥1 𝑎22 − 𝑎21
=
𝑥2 𝑎11 − 𝑎12

Similarly, we can write:

𝑦1 𝑎22 − 𝑎12
=
𝑦2 𝑎11 − 𝑎12

By simplifying, we get:

(𝑎22 − 𝑎21 )
𝑥1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

Or:

𝑥1 = 1 − 𝑥2

(𝑎11 − 𝑎12 )
𝑥2 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

Or:

𝑥2 = 1 − 𝑥1

(𝑎22 − 𝑎12 )
𝑦1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

197
 Operations Research

Or:

𝑦1 = 1 − 𝑦2

(𝑎11 − 𝑎21 )
𝑦2 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

Or:

𝑦2 = 1 − 𝑦1

The value of the game is:

(𝑎11 𝑎22 − 𝑎12 𝑎21 )

𝑣=
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

When the game does not have saddle point, the two largest elements of its payoff matrix must
constitute one of the diagonals.

Example 1

Now, let us consider the 2 × 2 matrix we got by reducing the given matrix in the Example 1 of
Section 6.4 and get the answer by applying the formula.

The reduced matrix is:

Player B
II III

Player A I -4 -3
II -3 -4

Solution
Player B
II III Row Minimum
I -4 -3 -4
Player A
II -3 -4 -4

198
 Operations Research

Column Maximum -3 -3

(𝑎22 − 𝑎21 )
𝑥1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

(−4 − (−3))
=
(−4 + (−4)) − (−3 + (−3))

(−4 + 3)
=
(−4 − 4) − (−3 − 3)

−1
=
(−8) − (−6)

−1
=
−2

1
= = 0.5
2

𝑥2 = 1 − 𝑥1

𝑥2 = 1 − 0.5

= 0.5

(𝑎22 − 𝑎12 )
𝑦1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

(−4 − (−3))
=
(−4 + (−4)) − (−3 + (−3))

(−4 + 3)
=
(−4 − 4) − (−3 − 3)

−1
=
(−8) − (−6)

199
 Operations Research

−1
=
−2

1
= = 0.5
2

𝑦2 = 1 − 𝑦1

𝑦2 = 1 − 0.5

= 0.5

The value of the game is:

(𝑎11 𝑎22 − 𝑎12 𝑎21 )

𝑣=
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

((−4 × −4) − (−3 × −3))

=
(−4 + (−4)) − (−3 + (−3))

12 − 9
=
(−8) − (−6)

3 3
= =−
−2 2

Example 2

Solve the game whose payoff matrix is:

Player B
I II III
I 1 7 2
Player A
II 6 2 7
III 5 1 6

200
 Operations Research

Solution
Player B
I II III Row Minimum
I 1 7 2 1
Player A II 6 2 7 2
III 5 1 6 1
Column Maximum 6 7 7

No saddle point.

Hence reduce the matrix by method of dominance. B’s third strategy gives him 2,7,6 units of
money when A plays his I, II, and III strategies. When we compare this with the B's first
strategy, it clearly shows that the payoffs of first strategy are superior or better to that of third
strategy. Hence B’s third strategy is dominated by the B’s first strategy. Hence, we remove the
third of B strategy from the game.

The reduced matrix is:

Player B

I II Row Minimum

Player A I 1 7 1
II 6 2 2
III 5 1 1
Column Maximum 6 7
No Saddle point.

Reduce the matrix by method of dominance. Consider A’s II strategy. The payoffs are 6 and 2
units of money when B plays his I and II strategies. When we compare this with A’s III strategy,
which fetches only 5 and 1 units of money, which is inferior to payoffs of II strategy. Hence, we
can remove A's third strategy form the game.

The reduced matrix is:

201
 Operations Research

Player B
I II Row Minimum
I 1 7 1
Player A II 6 2 2
Column Maximum 6 7

No saddle point. Hence apply the formula:

(𝑎22 − 𝑎21 )
𝑥1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

(2 − 6)
=
(1 + 2) − (7 + 6)

−4
=
(3) − (13)

−4
=
−10

2
= = 0.4
5

𝑥2 = 1 − 𝑥1

2
𝑥2 = 1 −
5

3
= = 0.6
5

(𝑎22 − 𝑎12 )
𝑦1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

(2 − (7))
=
(1 + 2) − (7 + 6)

−5
=
(3) − (13)

202
 Operations Research

−5
=
−10

1
= = 0.5
2

𝑦2 = 1 − 𝑦1

= 1 − 0.5

= 0.5

The value of the game is:

(𝑎11 𝑎22 − 𝑎12 𝑎21 )

𝑣=
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

((1 × 2) − (7 × 6))
=
(1 + 2) − (7 + 6)

2 − 42
=
(3) − (13)

−40
= =4
−10

Solution to the game is: A (2/5, 3/5, 0) and B (½, ½, 0) and value of the game is v = 4 i.e. A
allays win 4 units of money.

Example 3

Use the concept of dominance to solve the game whose payoff matrix is:
Player B
I II III IV
I 3 2 4 0
Player A II 3 4 2 4
III 4 2 4 0

203
 Operations Research

IV 0 4 0 8

Solution
Player B
I II III IV Row Minimum
I 3 2 4 0 0
II 3 4 2 4 2
Player A
III 4 2 4 0 0
IV 0 4 0 8 0
Column Maximum 4 4 4 8

No saddle point. Let us reduce the matrix by method of dominance.

Compare A’s I strategy and III strategy, we find that third strategy is superior to first strategy
as the elements of III row are greater than or equal to that of elements of first row. Hence, A’s III
strategy dominates A’s I strategy. Hence A's first strategy can be removed from the game.

The reduced matrix is:

Player B
I II III IV Row Minimum
II 3 4 2 4 2

Player A III 4 2 4 0 0
IV 0 4 0 8 0
Column Maximum 4 4 4 8

No saddle point, try to reduce the matrix by dominance method.

Compare B’s first strategy and III strategy. As the elements of III strategy are less than or equal
to that of first strategy, the III strategy dominates the first strategy. Hence, B’s first strategy is
removed from the game.

The reduced matrix is:

204
 Operations Research

Player B
II III IV Row Minimum
II 4 2 4 2

Player A III 2 4 0 0
IV 4 0 8 0
Column Maximum 4 4 8

No saddle point and there is no dominance among pure strategies.

Hence let us take the averages of two or more pure strategies and compare with other strategies,
to know whether there is dominance or not. Let take B’s III and IV strategy and take the average
and compare with elements of first strategy.

Average of elements of B’s III and IV strategy are: (2 + 4 = 6/2 = 3), (4 + 0 = 4 /2 = 2) and (0 + 8
= 8/2 = 4).

Hence the reduced matrix is:

Player B
II Avr. III & IV Row Minimum
II 4 3 3

Player A III 2 2 2
IV 4 4 4
Column Maximum 4 4

Note: Do not consider saddle point.

As all the elements of B’s second strategy are greater than or equal to that of averages of III and
IV strategies, B’s second strategy is inferior to that of III and IV strategies.

Hence the matrix is:

205
 Operations Research

Player B
III IV Row Minimum
II 2 4 2

Player A III 4 0 0
IV 0 8 0
Column Maximum 4 8

No saddle point.

Hence, let us try the dominance by comparing the averages of two A’s strategies with elements
of other strategy. Averages of A’s III and IV pure strategies is: (4 + 0 = 4 / 2 = 2) and (0 + 8 = 8 /
2 = 4).

The matrix is:

Player B
III IV
Player A II 2 4
Avr. III & IV 2 4

As the elements of A’s II strategy are inferior to averages of III and IV strategy, II strategy is
removed from the matrix.

The reduced matrix is:

Player B
III IV Row Minimum

Player A III 4 0 0
IV 0 8 0
Column Maximum 4 8

No saddle point. By applying the formulae:

(𝑎22 − 𝑎21 )
𝑥1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

206
 Operations Research

(8 − 0)
=
(4 + 8) − (0 + 0)

8
=
(12) − (0)

8
=
12

2
= = 0.67
3

𝑥2 = 1 − 𝑥1

2
𝑥2 = 1 −
3

1
= = 0.33
3

(𝑎22 − 𝑎12 )
𝑦1 =
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

(8 − 0)
=
(4 + 8) − (0 + 0)

8
=
(12) − (0)

8
=
12

2
= = 0.67
3

𝑦2 = 1 − 𝑦1

2
=1−
3

207
 Operations Research

1
= = 0.33
3

The value of the game is:

(𝑎11 𝑎22 − 𝑎12 𝑎21 )

𝑣=
(𝑎11 + 𝑎22 ) − (𝑎12 + 𝑎21 )

((4 × 8) − (0 × 0))
=
(4 + 8) − (0 + 0)

32 − 0
=
(12) − (0)

32
=
12

8
= = 2.67
3

Hence the solution is A (0, 0, 2/3, 1/3), B (0, 0, 2/3, 1/3) and v = 8/3 A will always win 8/3 units
of money.

208
 Operations Research

Chapter Seven

Queuing Models

Introduction

Queues are part of everyday life. We all wait in queues to buy a movie ticket, to make bank
deposit, pay for groceries, mail a package, obtain food in a cafeteria, to have ride in an
amusement park and have become adjustment to wait but still get annoyed by unusually long
waits. The Queuing models are very helpful for determining how to operate a queuing system in
the most effective way if too much service capacity to operate the system involves excessive
costs. The models enable finding an appropriate balance between the cost of service and the
amount of waiting.

Main concepts of waiting line theory or queuing model, description of queuing system,
components of queuing system, various ways in which the customer called to serve, measures of
queue performance, and queuing model approaches.

Objectives of the Chapter

After studying this Chapter, students should be able to:

➢ Explain the main concepts in relation to waiting line theory or queuing model;

➢ Describe queuing system;

➢ Identify components of queuing system;

➢ Recognize various ways in which the customer called to serve;

➢ Explain major queuing model methods.

209
 Operations Research

7.1. Overview of Queuing Model

Before going to waiting line theory or queuing theory, one has to understand two things in
clear. They are service and customer or element. Here, customer or element represents a
person or machine or any other thing, which is in need of some service from servicing point.
Service represents any type of attention to the customer to satisfy his/her need. For example,

• Person going to hospital to get medical advice from the doctor is an element or a
customer,
• A person going to railway station or a bus station to purchase a ticket for the journey is a
customer or an element,
• A person at ticket counter of a cinema hall is an element or a customer,
• A person at a grocery shop to purchase consumables is an element or a customer,
• A bank pass book tendered to a bank clerk for withdrawal of money is an element or a
customer,
• A machine breaks down and waiting for the attention of a maintenance crew is an
element or a customer.
• Vehicles waiting at traffic signal are elements or customers,
• A train waiting at outer signal for green signal is an element or a customer

Like this we can give thousands of examples.

In the above cases, the service means,

• Doctor is a service facility and medical care is a service,

• Ticket counter is a service facility and issue of ticket is service.
• Ticket counter is a service facility and issue of ticket is service.
• Shop owner is a service facility and issue of items is service.
• Bank clerk is a service facility and passing the cheque is service.
• Maintenance crew is service facility and repairing the machine is service.
• Traffic signals are service facility and control of traffic is service.
• Signal post is a service facility and green signaling is service.

210
 Operations Research

Above, we have seen elements or customer and service facility and service. We can see here that
all the customer or elements (hereafter called as customer only) will arrive and waits to avail the
service at service station. When the service station has no desired capacity to serve them all at a
time the customer has to wait for their chance resulting the formulation of a waiting line of
customers which is generally known as a queue. In general, we can say that a flow of customers
from infinite or finite population towards the service facility forms a queue or waiting line on
account of lack of capability to serve them all at a time. The above discussion clarifies that the
term customer we mean to the arriving unit that requires some service to be performed at the
service station. Queues or waiting lines stand for a number of customers waiting to be serviced.
Queue does not include the customer being serviced. The process or system that performs the
services to the customer is termed as service channel or service facility. Thus, from the above we
see that waiting lines or not only the lines formed by human beings but also the other things like
railway coaches, vehicles, material etc.

A. K. Erlang, a Danish telephone engineer, did original work on queuing theory. Erlang started
his work in 1905 in an attempt to determine the effects of fluctuating service demand (arrivals)
on the utilization of automatic dialing equipment. It has been only since the end of World War II
that work on waiting line models has been extended to other kinds of problems. In today’s
scenario a wide variety of seemingly diverse problems situations are recognized as being
described by the general waiting line model. In any queuing system, we have an input that
arrives at some facility for service or processing and the time between the arrivals of individual
inputs at the service facility is commonly random in nature. Similarly, the time for service or
processing is commonly a random variable.

Table 7.1 shows waiting line model elements for some commonly known situations. Servers may
be in parallel or in service. When it is parallel, the arriving customers may form a single queue as
in the case of post offices, ticket windows in railway station and bus station or a cinema theatre
etc. shown in figure 7.1. If the serves are in series, then number of queues is formed in front of
service facilities, for example we can take repair of break down machines. This is illustrated in
figure number 7.2.

211
 Operations Research

Figure 7.1. Four basic structures of waiting line situations.

Table 7.1. Waiting line model elements for some commonly known situations

212
 Operations Research

In figure number 7.2 arrows between service centers indicates possible routes for jobs processed

in the shop. In this particular system, we see that the service center moves to the customer rather
than the customer coming to service center for service. So, it may be understood here that there
is no rule that always the customers has to move to service centers to get the service. Depending
on the situation, the service center may also move to the customer to provide service. In this
system, the departure from one-service center may become input to the other service center.

In our everyday activity, we see that there is a flow of customer to avail some service from
service facility. The rate of flow depends on the nature of service and the serving capacity of the
station. In many situations, there is a congestion of items arriving from service because an item
cannot be serviced immediately on arrival and each new arrival has to wait for some time before
it is attended. This situation occurs where the total number of customers requiring service
exceeds the number of facilities. So, we can define a queue as “A group of customers/items
waiting at some place to receive attention / service including those receiving the service.”

In this situation, if queue length exceeds a limit, the customer gets frustrated and leave the queue
to get the service at some other service station. In this case the organization looses the customer
goodwill. Similarly, some service facility waits for arrival of customers when the total capacity
of system is more than the number of customers requiring service. In this case service facility
remains idle for a considerable time causing a burden of exchequer.

So, in absence of a perfect balance between the service facility and the customers, waiting is
required either by the customer or by the service facility. The imbalance between the customer
and
service facility, known as congestion, cannot be eliminated completely but efforts/techniques can
be evolved and applied to reduce the magnitude of congestion or waiting time of a new arrival in
the system or the service station. The method of reducing congestion by the expansion of
servicing counter may result in an increase in idle time of the service station and may become
uneconomical for the organization. Thus, both the situation namely of unreasonable long queue
or expansion of servicing counters are uneconomical to individual or managers of the system.

213
 Operations Research

Figure 7.2. Complex queue for a maintenance shop.

As discussed above, if the length of the queue is longer, the waiting time of the customer will
increase causing dissatisfaction of customer and to avoid the longer waiting time of customer, if
the management increases the service facilities, then many a time we see that the service
facilities will remain idle causing burden on the organization. To avoid this situation, the theory
of waiting line will help us to reduce the waiting time of the customer and suggest the
organization to install optimal number of service facilities, so that the customer will be happy
and the organization can run the business economically.

The arrival pattern of the customer and the service time of the facility depend on many factors
and they are not under the control of the management. Both cannot be estimated or assessed in
advance and moreover their arrival pattern and service time are random in nature. The waiting
line phenomenon is the direct result of randomness in the operation of service facility and
random arrival pattern of the customer. The customer arrival time cannot be known in advance to
schedule the service time and the time required to serve each customer depends on the magnitude
of the service required by the customer. For example, let us consider two customers who come to
the ticket counter to purchase the counter. One-person tenders exact amount and purchase one
ticket and leaves the queue. Another person purchases 10 tickets and gives a Rs. 500/- currency
note. For him after giving the ticket, the counter clerk has to give the remaining amount back.
So, the time required for both customers will vary. The randomness of arrival pattern and service
time makes the waiting line theory more complicated and needs careful study. The theory tries to
strike a balance between the costs associated with waiting and costs of preventing waiting and
help us to determine the optimal number of service facilities required and optimal arrival rate of
the customers of the system.

214
 Operations Research

7.2. Queuing System

Wait time is affected by the design of the waiting line system. A waiting line system (or
queuing system) is defined by two elements: the population source of its customers and the
process or service system itself. One thing we have think of is that when we speak of queue, we
have to deal with two elements, i.e., arrivals and service facility. We conclude with descriptions
of managerial decisions related to waiting line system design and performance. Entire queuing
system can be completely described by:

• The input (Arrival pattern)

• The service mechanism or service pattern,
• The queue discipline and
• Customer behavior.

Components of the queuing system are arrivals, the element waiting in the queue, the unit being
served, the service facility and the unit leaving the queue after service. This is shown in figure
7.3.

Figure 7.3. Components of queuing system

7.2.1. Input Process

The input describes the way in which the customers arrive and join the system. In general,
customer arrival will be in random fashion, which cannot be predicted, because the customer is

215
 Operations Research

an independent individual and the service organization has no control over the customer. The
characteristics of arrival are shown in figure 7.4.

Figure 7.4. Characteristics of Arrivals or input.

Input to the queuing system refers to the pattern of arrival of customers at the service facility. We
can see at ticket counters or near petrol bunks or any such service facility that the customer
arrives randomly individually or in batches. The input process is described by the following
characteristics (as shown in the figure 7.4) nature of arrivals, capacity of the system and behavior
of the customers.

Size of arrivals: The size of arrivals to the service system is greatly depends on the nature of
size of the population, which may be infinite or finite. The arrival pattern can be more clearly
described in terms of probabilities and consequently the probability distribution for inter- arrival
times i.e. the time between two successive arrivals or the distribution of number of customers
arriving in unit time must be defined. In our discussion in this chapter, it is dealt with those
queuing system in which customers arrive in Poisson or Completely random fashion. In fact
there are many more arrival patterns available but for simplicity, only Poisson arrivals are
considered.

216
 Operations Research

Inter-arrival time: The period between the arrival of individual customers may be constant or
may be scattered in some distribution fashion. Most queuing models assume that some inter-
arrival time distraction applies for all customers throughout the period of study. It is true that in
most situations that service time is a random variable with the same distribution for all arrivals,
but cases occur where there are clearly two or more classes of customers such as a machine
waiting for repair with a different service time distribution. Service time may be constant or
random variable. In this chapter mostly distribution of service time, which are important, are
considered and they are Negative exponential distribution and Erlang or Gamma distribution.
The most convenient way is to designate some random variables corresponding to the time
between arrivals. In general, the arrivals follow Poisson distribution when the total number of
arrivals during any given time interval of the number of arrivals that have already occurred prior to
the beginning of time interval. Figures 7.5 and 7.6 shows the Poisson distribution and negative
exponential distribution curves.

Figure 7.5. Poisson Distribution

217
 Operations Research

Figure 7.6. Negative Exponential Distribution

Capacity of the service system: In queuing context, the capacity refers to the space available for
the arrivals to wait before taken to service. The space available may be limited or unlimited.
When the space is limited, length of waiting line crosses a certain limit; no further units or
arrivals are permitted to enter the system till some waiting space becomes vacant. This type of
system is known as system with finite capacity and it has its effect on the arrival pattern of the
system, for example a doctor giving tokens for some customers to arrive at certain time and the
present system of allowing the devotees for darshan at Tirupathi by using the token belt system.

Customer behavior: The length of the queue or the waiting time of a customer or the idle time
of the service facility mostly depends on the behavior of the customer. Here, the behavior refers
to the impatience of a customer during the stay in the line. Customer behavior can be classified
as:

• Balking: This behavior signifies that the customer does not like to join the queue seeing
the long length of it. This behavior may affect in losing a customer by the organization.
Always a lengthy queue indicates insufficient service facility and customer may not turn
out next time. For example, a customer who wants to go by train to his/her destination

218
 Operations Research

goes to railway station and after seeing the long queue in front of the ticket counter,
may not like to join the queue and seek other type of transport to reach his destination.
• Reneging: In this case the customer joins the queue and after waiting for certain time
loses his/her patience and leaves the queue. This behavior of the customer may also
cause loss of customer to the organization.
• Collusion: In this case several customers may collaborate and only one of them may
stand in the queue. One customer represents a group of customers. Here, the queue
length may be small but service time for an individual will be more. This may break the
patience of the other customers in the waiting line and situation may lead to any type of
worst episode.
• Jockeying: If there are number of waiting lines depending on the number of service
stations, for example Petrol bunks, Cinema theaters, etc. A customer in one of the
queues after seeing the other queue length, which is shorter, with a hope of getting the
service, may leave the present queue and join the shorter queue. Perhaps the situation
may be that other queue which is shorter may be having a greater number of
Collaborated customers. In such case, the probability of getting service to the customer
who has changed the queue may be very less. Because of this character of the customer,
the queue lengths may go on changing from time to time.

7.2.2. Service Mechanism or Service Facility

Service facilities are arranged to serve the arriving customer or a customer in the waiting line is
known as service mechanism. The time required to serve the customer cannot be estimated until
we know the need of the customer. Many a time it is statistical variable and cannot be
determined by any means such as number of customers served in a given time or time required to
serve the customer, until a customer is served completely. Service facility design and service
discipline and the channels of service as shown in figure 7.7 may generally determine the service
mechanism.

219
 Operations Research

Figure 7.7 Service Mechanisms.

Service facility design: Arriving customers may be asked to form a single line (single queue) or
multi line (multi queue) depending on the service need. When they stand in single line, it is
known as single channel facility. When they stand in multi lines it is known as multi-channel
facility.

• Single channel queues: If the organization has provided single facility to serve the
customers, only one unit can be served at a time, hence arriving customers form a queue
near the facility. The next element is drawn into service only when the service of the
previous customer is over. Here also depending on the type of service the system is
divided into Single phase and Multi phase service facility. In Single channel Single Phase
queue, the customer enters the service zone and the facility will provide the service
needed. Once the service is over the customer leaves the system. For example, petrol
bunks, the vehicle enters the petrol station. If there is only one petrol pump is there, it
joins the queue near the pump and when the term comes, get the fuel filled and soon after
leaves the queue. Or let us say there is a single ticket counter, where the arrivals will
form a queue and one by one purchases the ticket and leaves the queue. In single channel
multi-phase service design, the service needed by the customer is provided in different
stages, say for example, at petrol station, the customer will first get the tank filled with
fuel, then goes to pollution check point get the exhaust gas checked for carbon dioxide
content and then goes to Air compressor and get the air check and leaves the petrol

220
 Operations Research

station. Here, each service facility is known as a phase. Hence the system is known as
multi-phase system. Another good example is a patient enters the queue near the doctor’s
room, get examined by doctor and take prescription goes to compounder takes medicine
and then goes to nurse have the injection and leaves the hospital. Here doctor,
compounder and nurse all are facilities and serve the customer one by one. This is shown
in figure 7.1.

• Multi-Channel queues: When the input rates increase, and the demand for the service
increases, the management will provide additional service facilities to reduce the rush of
customers or waiting time of customers. In such cases, different queues will be formed in
front of different service facilities. If the service is provided to customers at one
particular service center, then it is known as Multi channel Single-phase system. In case
service is provided to customer in different stages or phases, which are in parallel, then it
is known as multi-channel multi-phase queuing system. This is shown in figure 9.1.

Queue discipline or Service discipline: When customers are standing in a queue, they are
called to serve depending on the nature of the customer. The order in which they are called is
known as Service discipline. There are various ways in which the customer called to serve. They
are:
• First In First Out (FIFO) or First Come First Served (FCFS): We are quite aware
that when we are in a queue, we wish that the element which comes should be served
first, so that every element has a fair chance of getting service. Moreover, it is understood
that it gives a good morale and discipline in the queue. When the condition of FIFO is
violated, there arises the trouble and the management is answerable for the situation.
• Last In First Out (LIFO) or Last Come First Served (LCFS): In this system, the
element arrived last will have a chance of getting service first. In general, this does not
happen in a system where human beings are involved. But this is quite common in
Inventory system. Let us assume a bin containing some inventory. The present stock is
being consumed and suppose the material ordered will arrive that is loaded into the bin.
Now the old material is at the bottom of the stock where as fresh arrived material at the
top. While consuming the top material (which is arrived late) is being consumed. This is

221
 Operations Research

what we call Last Come First Served). This can also be written as First In Last Out
(FILO).
• Service In Random Order (SIRO): In this case the items are called for service in a
random order. The element might have come first or last does not bother; the servicing
facility calls the element in random order without considering the order of arrival. This
may happen in some religious organizations but generally it does not followed in an
industrial / business system. In religious organizations, when devotees are waiting for the
darshan of the god man /god woman, the devotees are picked up in random order for
blessings. Sometimes we see that in government offices, the representations or
applications for various favors are picked up randomly for processing. It is also seen to
allocate an item whose demand is high and supply is low, also seen in the allocation of
shares to the applicants to the company.
• Service By Priority: Priority disciplines are those where any arrival is chosen for service
ahead of some other customers already in queue. In the case of Pre-emptive priority, the
preference to any arriving unit is so high that the unit is already in service is removed /
displaced to take it into service. A non- pre-emptive rule of priority is one where an
arrival with low priority is given preference for service than a high priority item. As an
example, we can quote that in a doctor shop, when the doctor is treating a patient with
stomach pain, suddenly a patient with heart stroke enters the doctors’ shop, the doctor
asks the patient with stomach pain to wait for some time and give attention to heart
patient. This is the rule of priority.

7.3. Queuing System Performance Measures

It’s easy to jump straight to possible or seemingly obvious measures of queue performance, but
that’s a mistake. We want to first understand the specific results that matter to us, and to our
queue-based process, before we give any thought to measures of queue performance.

We most certainly do not want to fall into the trap of measuring the first five queue-related key
performance indicators (KPIs) we find in an internet search. That’s because the results that
define the performance of our queue-based process will depend on our unique context, which
includes:

222
 Operations Research

• the current performance of our queue-based process

• what our customers value most from that process
• higher-level goals, such as strategic goals or the organisation’s mission, that the process
also impacts on
• other goals that need to be traded off against queue performance, like the quality of the
service that the queue is feeding into
• feasibility of gathering the data we’d need from the systems and procedures we use for
managing the queue-based process

So, keeping in mind the context of our queue, the results that we might possibly want could be
like the following:

• waiting times within the queue are tolerable to customers

• no customers have to wait longer than the promised longest wait time (this may vary
depending on customer priority)
• server time is as quick as possible
• the queue doesn’t get too long or full, or completely backed up
• the servers’ capacity is not wasted (they are not idle for too much of their working time –
like cancelled appointments or oversupply of servers, their utilisation is high)

No doubt there are more possible results that define queue performance, and that’s why it’s
worth taking the time to craft your own goals or result statements to define your queue
performance priorities.

With clear results, we can set meaningful measures of queue performance. The brilliant thing
about defining your results for queue performance is that it makes finding the right measures
much easier. Now, the temptation will be to jump straight to the data you have, or can easily get,
and base your measures on that.

But it’s a mistake to focus only on the data you have. How will you get the data you need unless
you are honest about the information (that is, the measures) that you need? And I cannot tell you
how many times I have seen people discover new ways to get data for measures they first
thought would be impossible to implement.

223
 Operations Research

So, we forget about data until we clearly defined the measures of queue performance that will be
the most useful to us. And using a technique like this PuMP Measure Design template, we can
design potential measures of queue performance for each of the results (from above) that matter
to us.

The following are just a sample of possible measures (with suggested names and descriptions),
for a healthcare clinic. Patients join a virtual queue – basically a booking system – waiting for
appointments to become available. Potential measures, for results like those listed above, might
include:

• Queue Length: Average number of patients currently waiting for an appointment

• Queue Fluctuation: Variance of the number of patients in the booking system
• Waiting Time: Average number of days that patients wait until they get their appointment
• Waiting Time Variation: Variance of the number of days that patients wait until they get
their appointment
• Waiting Time Promise: Percentage of patients that wait longer than 5 business days until
they get their appointment
• Appointment Time: Average minutes that actual patient appointments take
• Doctor Downtime: Percentage of working hours that specialists are not seeing or treating
patients

Only after the measures are clearly articulated should we then evaluate their feasibility to
implement. And now we can have a more motivated and informed discussion about the data
needed for these measures of queue performance.

There are various measures that one can use to assess the quality of a queuing system. These are:

• Average time that each customer or object spends in the queue

• Average queue length
• Average time in the system
• Average number of customers in the system
• Probability the service facility will be idle
• Utilization factor for the system

224
 Operations Research

• Probability of a specified number of customers in the system

7.4. Queuing Models

Most elementary queuing models assume that the inputs (arrivals) and outputs (departures)
follow a birth and death process. Any queuing model is characterized by situations where both
arrivals and departures take place simultaneously. Depending upon the nature of inputs and
service faculties, there can be a number of queuing models as shown below:

• Probabilistic queuing model: Both arrival and service rates are some unknown random
variables.
• Deterministic queuing model: Both arrival and service rates are known and fixed.
• Mixed queuing model: Either of the arrival and service rates is unknown random
variable and other known and fixed.

Earlier we saw how to designate a queue. Arrival pattern / Service pattern / Number of channels /
(Capacity / Order of servicing). (A /B/ S / (d / f).

In general, M is used to denote Poisson distribution (Markovian) of arrivals and departures.

• D is used to constant or Deterministic distribution.

• 𝐸𝑘 is used to represent Erlangian probability distribution.
• G is used to show some general probability distribution.

In general, queuing models are used to explain the descriptive behavior of a queuing system.
These quantify the effect of decision variables on the expected waiting times and waiting lengths
as well as generate waiting cost and service cost information. The various systems can be
evaluated through these aspects and the system, which offers the minimum total cost is selected.

Procedure for Solution

(a) List the alternative queuing system

(b) Evaluate the system in terms of various times, length and costs.
(c) Select the best queuing system.

225
 Operations Research

7.4.1 FIFO Model

FIFO Model also known as Poisson Arrival, Poisson output, Number of channels, Infinite
capacity, M/M/1/ (∞/FIFO) model of queue model.

Formulae used:
1. Average number of arrivals per unit of time = 𝜆
2. Average number of units served per unit of time = µ
𝜆
3. Traffic intensity or utility ratio = 𝑝 = µ, the condition is: (µ > 𝜆)

4. Probability that the system is empty = 𝑝0 = (1 − 𝑝)

5. Probability that there are ‘n’ units in the system = 𝑝𝑛 = 𝑝𝑛 𝑝0
𝑝 𝜆 𝜆
6. Average number of units in the system = 𝐸(𝑛) = (1−p) 𝑜𝑟 = (µ−𝜆) = 𝐿𝑞 + µ

𝑝2 𝜆2
7. Average number of units in the waiting line = 𝐸𝐿 = (1−p) = µ(µ−𝜆)

8. Average waiting length (mean time in the system) = 𝐸(𝐿 / 𝐿 > 0)

1 1
= =
(µ − 𝜆) (1 − p)
1 𝐿
= 𝐸(𝑤) + =
µ 𝜆
9. Average length of waiting line with the condition that it is always greater than zero =
𝑝
𝑉(𝑛) =
(1 − p)2
𝜆
=
(µ − 𝜆)2
𝐿𝑞 𝜆
= =
𝜆 µ(µ − 𝜆)
10. Average time an arrival spends in the system
1
𝐸(𝑣) =
µ(1 − p)
1
= = 𝐸(𝑤 / 𝑤 > 0)
µ(µ − 𝜆)
11. 𝑃(𝑤 > 0) = System is busy = 𝑝
12. Idle time = (1 − 𝑝)

226
 Operations Research

13. Probability distribution of waiting time = 𝑃(𝑤)𝑑𝑤 = µp(1 − p)e−µw(1−p)

14. Probability that a consumer has to wait on arrival = 𝑃(𝑤 > 0) = 𝑝
15. Probability that a new arrival stays in the system = 𝑃(𝑣)𝑑𝑣 = µ(1 − p)e−µv(1−p) 𝑑𝑣

Example 1

A T.V. Repairman finds that the time spent on his jobs have an exponential distribution with
mean of 30 minutes. If he repairs sets in the order in which they come in, and if the arrival of sets
is approximately Poisson with an average rate of 10 per 8-hour day, what is repairman’s
expected idle time each day? How many jobs are ahead of the average set just brought in?

Solution

This problem is Poisson arrival/Negative exponential service / single channel /infinite capacity/
FIFO type problem.

Data: λ = 10 sets per 8 hours per day = 10 / 8 = 5/4 sets per hour.

Given 1/µ = 30 minutes, hence µ = (1/30) × 60 = 2 sets per hour.

Hence, Utility ratio:

5
𝜆 4 5
𝑝 = = = = 0.625
µ 2 8

This means out of 8 hours 5 hours the system is busy i.e., repairman is busy.

5 3
Probability that there is no queue = The system is idle = (1 − 𝑝) = 8 = 8. That is out of 8 hours

the repairman will be idle for 3 hours.

𝜆
Number of sets ahead of the set just entered = Average number of sets in system = (µ−𝜆) =
𝑝 0.625 5
(1−p)
= 1−0.625 = 3 ahead of jobs just came in.

227
 Operations Research

Example 2

The arrivals at a telephone booth are considered to be following Poisson law of distribution with
an average time of 10 minutes between one arrival and the next. Length of the phone call is
assumed to be distributed exponentially with a mean of 3 minutes.

(a) What is the probability that a person arriving at the booth will have to wait?
(b) What is the average length of queue that forms from time to time?
(c) The telephone department will install a second booth when convinced that an arrival
would expect to wait at least three minutes for the phone. By how much must the flow of
arrivals be increased in order to justify a second booth?

Solution

1 1
Data: Time interval between two arrivals = 10 𝑚𝑖𝑛. = 𝜆, Length of phone call= 3 𝑚𝑖𝑛. = µ
1 1 λ 0.1
Hence, λ = 10 = 0.1 𝑝𝑒𝑟 𝑚𝑖𝑛., and µ = 3 = 0.33 𝑝𝑒𝑟 𝑚𝑖𝑛., and p = µ = 0.33 = 0.3.

(a) Any person who is coming to booth has to wait when there is somebody in the queue.
He/she need not wait when there is nobody in the queue i.e., the queue is empty. Hence
the probability of that an arrival does not wait = 𝑝0 = (1 − 𝑝)

Hence, the probability that an arrival has to wait = 1 −The probability that an arrival
does not wait= (1 − 𝑝0 ) = 1 − (1 − 𝑝) = 𝑝 = 0.3. That means 30% of the time the
fresh arrival has to wait. That means that 70% of the time the system is idle.
(b) Average length of non- empty queue from time to time = (Average length of the waiting
1 L
line with the condition that it is always greater than zero = (1−p) 𝑖. 𝑒 𝐸 (L > 0) =
1
(1−0.3)
= 1.43 𝑝𝑒𝑟𝑠𝑜𝑛𝑠.

(c) The installation of the second booth is justified if the waiting time is greater than or equal
to three. If the new arrival rate is λ′, then for µ = 0.33 we can work out the length of the
λ′
waiting line. In this case 𝑝 = .
µ

228
 Operations Research

λ′
Length of the waiting line for λ′ and µ = 0.33 = E(w) = ( µ (µ − λ′ )) ≥ 3E or λ′ =

3µ2 3×0.332
(3µ2 − 3pµλ′ ) or λ′ = (1+3µ) = 1+3×0.33 𝑖. 𝑒. λ′ ≥ 0.16. That is the arrival rate must be at

least 0.16 persons per minute or one arrival in every 6 minutes. This can be written as 10
arrivals per hour to justify the second booth.

7.4.2. Generalization of model (M /M / 1): (FCFS/ ∞/∞): (Birth – Death process)

In waiting line system each arrival can be considered to be a birth i.e., if the system is in the state
𝐸𝑛 , i.e., there are n units in the system and there is an arrival then the state of the system changes
to the state 𝐸𝑛+1 . Similarly, when there is a departure from the system the state of the system
becomes 𝐸𝑛−1 . Hence, whole system is thus viewed as a birth and death process. When λ is the
arrival rate of the system, will never be fixed and dependent on the queue length ‘n’, then it will
mean that some person interested in joining the queue may not join due to long queue. Similarly,
if µ is also dependent on the queue length it may affect the service rate. Hence in this case both λ
and µ cannot be taken to be fixed. Three cases may occur, which are described below.

In this model, arrival rate and service rate i.e., λ and µ do not remain constant during the queuing
phenomenon and vary to λ1 , λ2 ,… λ𝑛 and µ1 , µ2 ,… µ𝑛 respectively. Then:
𝜆𝑜
𝑝1 = ( ) 𝑝0
µ1
𝜆𝑜 𝜆1
𝑝2 = ( )( )𝑝
µ1 µ2 0
……………………………..
……………….……………
𝜆𝑜 𝜆1 𝜆𝑛−2 𝜆𝑛−1
𝑝𝑛 = ( ) ( ) … ( )( ) 𝑝0
µ1 µ2 µ𝑛−1 µ𝑛

But there are some special cases when:

1. 𝜆𝑛 = 𝜆 and µ𝑛 = µ, then
𝜆 𝜆 2 𝜆
𝑝0 = 1 − ( ) , 𝑝𝑛 = ( ) × (1 − ( ))
µ µ µ

229
 Operations Research

𝜆
2. When 𝜆𝑛 = 𝑛+1, µ𝑛 = µ

𝑝0 = 𝑒 −𝑝
𝑝𝑛 𝜆
𝑝𝑛 = ( 𝑛! ) × 𝑒 −𝑝 , where 𝑝 = (µ )
𝑝𝑛
3. When 𝜆𝑛 = 𝜆 and µ𝑛 = 𝑛 × µ, then 𝑝0 = 𝑒 −𝑝 𝑎𝑛𝑑 𝑝𝑛 = ( 𝑛! ) × 𝑒 −𝑝 .

Example

A transport company has a single unloading berth with vehicles arriving in a Poisson fashion at
an average rate of three per day. The unloading time distribution for a vehicle with ‘n’ unloading
workers is found to be exponentially with an average unloading time (1/2) xn days. The company
has a large labor supply without regular working hours, and to avoid long waiting lines, the
company has a policy of using as many unloading groups of workers in a vehicle as there are
vehicles waiting in line or being unloaded. Under these conditions find (a) What will be the
average number of unloading group of workers working at any time? (b) What is the probability
that more than 4 groups of workers are needed?

Solution

Let us assume that there are ‘n’ vehicles waiting in line at any time. Now service rate is
dependent on waiting length hence nµ = 2n vehicles per day (when there are ‘n’ groups of
workers in the system).

Now λ = 3 vehicles per day and µ = 2 vehicles per day. (With one unloading labor group)

𝑝𝑛
Hence, 𝑝𝑛 = ( 𝑛! ) × 𝑒 −𝑝 , where 𝑛 ≥ 0

Therefore, expected number of group of workers working any specified instant is

𝐸(𝑛) = ∑ 𝑛 × 𝑝𝑛
𝑛=0

∑ 𝑛 × (𝑝𝑛 𝑒 −𝑝 )
=
𝑛!

230
 Operations Research

∞
−𝑝
(𝑝𝑛−1 )
=𝑝×𝑒 ×∑
(𝑛 − 1)
𝑛=0

𝜆
=( )
µ

= 1.5 labour group

The probability that the vehicle entering in service will require more than four groups of workers

∞ ∞
𝑝𝑛
∑ 𝑝𝑛 = ∑ ( ) × 𝑒 −𝑝 = 0.019.
𝑛!
𝑛=0 𝑛=0

7.4.3. Finite Queue Length Model: (M / M / 1): FCFS / N / ∞

This model differs from the above model in the sense that the maximum number of customers in
the system is limited to N. Therefore, the equations of above model is valid for this model as
long as n < N and arrivals will not exceed N under any circumstances. The various equations of
the model is:

1−𝑝 𝜆 𝜆
1. 𝑝0 = (1−𝑝𝑁+1) where 𝑝 = (µ) and (µ ) > 1 is allowed.
(1−𝑝)×𝑝𝑛
2. 𝑝𝑛 = ( ) for all 𝑛 = 0, 1, 2, … 𝑁
1−𝑝𝑁+1

3. Average queue length:

𝑝[1 − (1 + 𝑛)𝑝𝑁 + 𝑁𝑝𝑁+1 ]
𝐸(𝑛) =
(1 − 𝑝)(1 − 𝑝𝑁+1 )
𝑛 𝑁
(1 − 𝑝)
= × ∑ 𝑛𝑝𝑛 = 𝑝0 ∑ 𝑛𝑝𝑛
(1 − 𝑝𝑁+1 )
𝑛=0 𝑛=0

4. The average length of the waiting line:

[(1 − 𝑁𝑝𝑁+1 ) + (𝑁 − 1)𝑝𝑁 )]𝑝2
𝐸(𝐿) =
(1 − 𝑝)(1 − 𝑝𝑁+1 )
5. Waiting time in the system:
𝐸(𝑛)
𝐸(𝑣) = 𝑤ℎ𝑒𝑟𝑒 λ′ = 𝜆(1 − 𝑝𝑁 )
λ′

231
 Operations Research

6. Waiting time in the queue:

𝐸(𝐿) 𝐸(𝑛) 1
𝐸(𝑤) = = ′ /( )
λ′ λ µ

Example 1

In a railway marshalling yard, good train arrives at the rate of 30 trains per day. Assume that the
inter arrival time follows an exponential distribution and the service time is also to be assumed as
exponential with a mean of 36 minutes.

Required: Calculate:

(a) The probability that the yard is empty

(b) The average length assuming that the line capacity of the yard is 9 trains.

Solution

30 1 1
Data: 𝜆 = 60×24 = 48 trains per minute. And µ = 36 trains per minute.

𝜆 36
Therefore 𝑝 = µ = 48 = 0.75
1−𝑝
(a) The probability that the queue is empty is given by = 𝑝0 = (1−𝑝𝑁+1) , 𝑤ℎ𝑒𝑟𝑒 𝑁 = 9

1 − 0.75
𝑝0 = ( )
1 − (0.75)9+1
0.25
= = 0.28
0.90
This means 28 % of the time the line is empty.

(b) Average queue length:

𝑝[1 − (1 + 𝑛)𝑝𝑁 + 𝑁𝑝𝑁+1 ]
𝐸(𝑛) =
(1 − 𝑝)(1 − 𝑝𝑁+1 )

𝑛
(1 − 𝑝)
= × ∑ 𝑛𝑝𝑛
(1 − 𝑝𝑁+1 )
𝑛=0

232
 Operations Research

9
1 − 0.75
=( ) × ∑ 𝑛(0.75)𝑛
1 − (0.75)10
𝑛=0

= 0.28 × 9.58 = 3 𝑡𝑟𝑎𝑖𝑛𝑒𝑠.

Example 2

A barbershop has space to accommodate only 10 customers. He/She can serve only one person at
a time. If a customer comes to his/her shop and finds it is full, he/she goes to the next shop.
Customers randomly arrive at an average rate λ = 10 per hour and the barber service time is
1
negative exponential with an average of µ =5 minute. Find 𝑝0 and 𝑝𝑛 .

Solution

10 1 𝜆 5
Data: 𝑁 = 10, 𝜆 = 60, µ = 5. Hence, 𝑝 = µ = 6

1−𝑝
𝑝0 = ( )
1 − 𝑝11

5
(1 − 6)
=( )
5 11
1 − (6)

0.1667
= = 0.1926
0.8655

(1 − 𝑝) × 𝑝𝑛
𝑝𝑛 = ( )
1 − 𝑝𝑁+1

5 𝑛
= (0.1926) × ( ) 𝑤ℎ𝑒𝑟𝑒, 𝑛 = 0, 1, 2, 3 … 10.
6

7.4.4. MODEL IV: (M / M / 1): FCFS / N /N (Limited Population or Source Model)

In this model, we assume that customers are generated by limited pool of potential customers
i.e., finite population. The total customer’s population is M and n represents the number of

233
 Operations Research

customers already in the system (waiting line), any arrival must come from M - n number that is
not yet in the system. The formulae for this model are:

𝑀
𝑀! 𝜆 𝑛
𝑝0 = 1/ ∑ [ ]×( )
(𝑀 − 𝑛)! µ
𝑛=0

𝑀! 𝜆 𝑛
𝑝𝑛 = [ ] × ( ) × 𝑝0
(𝑀 − 𝑛)! µ

𝑀
𝑀! 𝜆 𝑛 𝑀! 𝜆 𝑛
𝑝0 = {[ ] × ( ) } / {∑ [ ]×( ) }
(𝑀 − 𝑛)! µ (𝑀 − 𝑛)! µ
𝑛=0

𝑀
µ
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐𝑢𝑠𝑡𝑜𝑚𝑒𝑟𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑠𝑦𝑠𝑡𝑒𝑚 = 𝐸(𝑛) = ∑ 𝑛𝑝𝑛 = 𝑀 − ( ) (1 − 𝑝0 )
𝜆
𝑛=0

µ+𝜆
𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐𝑢𝑠𝑡𝑜𝑚𝑒𝑟𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑞𝑢𝑒𝑢𝑒 = 𝐸(𝑙) = 𝑀 − ( ) (1 − 𝑝0 )
𝜆

Example

A mechanic repairs 4 machines. The mean time between service requirements is 5 hours for each
machine and forms an exponential distribution. The mean repair time is 1 hour and also follows
the same distribution pattern. Machine down time costs Br. 25 per hour and the mechanic costs
Br. 55 per day. Find:

(a) Expected number of operating machines,

(b) The expected down time cost per day,
(c) Would it be economical to engage two mechanics, each repairing only two machines?

Solution

Data: Finite population, λ = Arrival rate = (1/5) = 0.2, µ = Service rate = µ = (1/1) = 1

Probability of the empty system:

234
 Operations Research

𝑀
𝑀! 𝜆 𝑛
𝑝0 = 1/ ∑ [ ]×( )
(𝑀 − 𝑛)! µ
𝑛=0

4
4! 0.2 𝑛
= 1/ ∑ [ ]×( )
(4 − 𝑛)! 1
𝑛=0

1
= + (4 × 0.2) + (4 × 3 × 0.22 ) + (4 × 3 × 2 × 0.23 ) + (4 × 3 × 2 × 1 × 0.24 ) = 0.4
1

i.e., 40 percent of the time the system is empty and 60 percent of the time the system is busy.

(a) Expected number of operating machines:

µ
𝐸(𝑛) = 𝑀 − ( ) (1 − 𝑝0 )
𝜆
1
= 4 − ( ) × (1 − 0.4)
0.2
= 4 − 5 × 0.6
=4−3=1
(b) The expected down time cost per day:
Expected down time cost per day of 8 hours = 8 × (expected number of breakdown
machine
× Br. 25 per hour)
= 8 × 1 × 25 = 𝐵𝑟. 200/𝑑𝑎𝑦
(c) Would it be economical to engage two mechanics, each repairing only two machines?
When there are two mechanics each serving two machines, M = 2

𝑀
𝑀! 𝜆 𝑛
𝑝0 = 1/ ∑ [ ]×( )
(𝑀 − 𝑛)! µ
𝑛=0

2
2! 0.2 𝑛
= 1/ ∑ [ ]×( )
(2 − 𝑛)! 1
𝑛=0

1
= + (2 × 0.2) + (2 × 1 × 0.22 )
1

235
 Operations Research

1
= = 0.68
1.48

i.e., 68 percent of the time the system is idle. It is assumed that each mechanic with his two
machines constitutes a separate system with no interplay. Expected number of machines in the
system:

µ
𝐸(𝑛) = 𝑀 − ( ) (1 − 𝑝0 )
𝜆
1
= 2 − ( ) × (1 − 0.68) = 0.4
0.2
Therefore, expected down time per day:

= 8 × 0.4 × Number of mechanics or machine in system

= 8 × 0.4 × 2 = 6.4 ℎ𝑜𝑢𝑟𝑠 𝑝𝑒𝑟 𝑑𝑎𝑦

Hence, total cost involved:

= 8 × 2 × 6.4 × 𝐵𝑟. 25

= (110 + 160) = 𝐵𝑟. 270 𝑝𝑒𝑟 𝑑𝑎𝑦

But total cost with one mechanic is br. (55 + 200) = Br. 255 per day, which is cheaper compared
to the above. Hence use of two mechanics is not advisable.

236