Page 1

CHAPTER ONE

Introduction to Operations Research

 Objectives:

Dear distance learner! On successful completion of this chapter, you should be able to:
 Define the term operations research
 Explain the historical development of operations research
 Understand the nature and characteristics of operations research
 Explain the significance of operations research to mangers
 Identify the operation research problem solving approach
 Understand the meaning of model and its different classifications

1.1. Introduction

Dear distance learner! 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.

Page 2
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 will obtain credit or not, a technique, called credit scoring,
is often used.

Rational decisions are often made unwillingly, perhaps unconsciously. 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. 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-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.

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.

Page 3
Making 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.

 Activity-1
 Define operation research?
_____________________________________________________________________
_____________________________________________________________________
___________________________-

1.2. Historical Development of OR

It is generally agreed that OR come into existence as a discipline during world war II
when there was a critical need to manage scarce resources. However, a particular model
and technique of OR can be traced back to much earlier times. The scientific approach to
management can be traced back to the era of Industrial Revolution and even periods
before that. But operations research, as it exists today, was born during the Second World
War when the British military management called upon a group of scientists to examine
the strategies and tactics of various military operations with the intention of efficient
allocation of scarce resources to the war effort.

The war involved strategic and tactical problems which were greatly complicated to
expect adequate solution from individuals or specialists in a single discipline. Therefore
groups of individuals who collectively were considered specialists in mathematics,
economics, statistics and probability theory, engineering, behavioral and physical science
were formed as a special units within the armed forces to deal with strategic and tactical
problems of various military operations.

Problems of this latter kind, often called systems problems, were studied rigorously for
the first time by scientists, not in industry but in the management of operations in the
1939 - 45 war.

Page 4
A number of teams of eminent scientists were employed by the British Government to
apply their expertise to management and operational problems rather than technical
problems.

One such team (the Radar Operational Research team - which gave OR its name) was
responsible for implementing the installation and operation of radar after the technical
development work was complete.

Later on another team examined the relative ineffectiveness of the Allied Forces at
destroying the German U-boats, which were sinking the food convoy ships supplying
Britain.

The OR team played an important part in reducing shipping losses and in the ultimate
defeat of the U-boats. With no precedent in the application of Science to the management
function, the scientists were still able to use their scientific approach-collecting
information and developing hypothesis in order to come up with practical plans for the
improvement of these wartime operations.

After the end of the war, the same approach was used with great success in the industrial
and commercial field, developing most rapidly in Britain and the USA, followed by
Europe and the rest of the world. This has provided the basis for the evolution of
Operational Research (OR) as a separate and independent subject of Science. It is not
based on any single academic engineering, social science, economics, statistics and
computing but is none of these.

There are three different factors behind the rapid development in the use and
development of operations research approach.

 The economic and industrial boom after World War II resulted in continuous
mechanization, automation, decentralization of operations and decisions of
management functions. This industrialization also resulted in complex managerial
problems and therefore application of operations research to managerial decision
making become popular.

Page 5
  Many operations researchers continued their research after war. A key person in
the post war development of OR was George B. Dantzing. In 1947 he developed
the concept of linear programming and its solution by a method known as
Simplex method.
 Analytic power was made available by high-speed computers. The development
of electronic digital computers, with their ability to perform arithmetic
calculations thousands or even millions of times faster than a human being can,
was a tremendous boom to OR.

 Activity-2
 State the history of Operation research?
____________________________________________________________
____________________________________________________________
_________________________
1.3. Meaning of operations research
Definition

Operations Research is defined by many authors in different ways .However, the

following definition is proposed here.

The Operational Research Society of U.K. defines OR as:

"Operational Research is the application of the methods of science to complex

problems arising in the direction and management of large systems of men,
machines, materials and money in industry, business, government and defense.
The distinctive approach is to develop a scientific model of the system,
incorporating measurements of factors, such as chance and risk, with which to
compare the outcome of alternative decisions, strategies and controls. The
purpose is to help management determine its policies and actions
scientifically."

Page 6
In the USA, where it is called Operations Research, the OR Society of America says
more briefly;

"OR is concerned with scientifically deciding how to best design and operate man-
machine systems, usually under conditions requiring the allocation of scarce
resources"

“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 constraints.”

OR is the representation of real-world systems by mathematical models together with

the use of quantitative methods (algorithms) for solving such models, with a view to
optimizing.

From the concept and definition given above, Operations Research is:

 The application of scientific methods, techniques and tools to the problem to

find an answer
 A management tool in the hands of a manager to take a decision
 A scientific approach to decision making process
 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”
 A decision-oriented research, using scientific methods, for providing
management a quantitative basis for taking decision regarding operations under
its control
 Applied decision theory. It uses scientific, mathematical and logical means to
take decisions.

Page 7
1.4. Nature and significance of operations research

As the term implies, OR involves research on military operations. The operation research
approach is particularly useful in balancing conflicting objectives where there are many
alternative courses of action available to the decision maker. In a theoretical sense, the
optimum decision (global optimum) must be one that is best for the organization as a
whole.

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.

Nature and characteristics of OR:

 Existence of a problem
 Intension to solve a problem
 Application of system concept and system analysis to the problem
 Scientific approach to the problem where research methods are used
 Formation of group consists of different specialists
 Assist management to make scientific decision
 Solution must meet the objective within the constraints

OR is concerned with providing the decision maker with decision aids (or rules) derived
from:

i. A total system orientation

ii. Scientific methods of investigation, and
iii. Models of reality, generally based on quantitative measurement and
techniques

Page 8
1.5. Feature 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).

Methodological approach

Operations research is the application of scientific methods, techniques and tools to

problems involving the operation of systems so as to provide those in control of
operations with optimum solutions to the problem.

Wholistic Approach

While arriving at a decision, an operation 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.

Objectivistic Approach

An operation research approach seeks to obtain an optimal solution to the problem under
analysis. For this a measure of desirability (effectiveness) is defined, based on the
objective(s) of the organization. A measure of desirability so defined is then used to
compare alternative courses of action with respect to their outcomes.

 Activity-3
 List and explain the feature of operations research?
______________________________________________________________________
______________________________________________________________________
__________________________

Page 9
1.6. The management science approach to problem solving
Management science encompasses a logical/systematic approach to problem solving,
which closely parallels what is known as the scientific method for attacking problems.
This approach follows a generally recognized and ordered serious of steps:
1) Observation, 2) definition of the problem, 3) model construction, 4) model solution,
5) implementation of solution results
Figure1.1. the management science process

Observation

Problem definition

Feed
Model construction
Back Management science technique

Solution

Implementation Information
1. Observation: - the first step in the management science process is the
identification of a problem that exists in the system (organization). The system
must be continuously and closely observed so that problems can be identified as
soon as they occur or are anticipated. The person who normally identifies a
problem is the manager because the managers work in places where problems
might occur.
2. Definition of problem: - once it has been determined that a problem exists, the
problem must be clearly and concisely defined. Improper definition of a problem
can easily result in no solution or an inappropriate solution.
3. Model construction:- a management science model is an abstract representation of
an existing problem situation. It can be in the form of a graph chart, but most
frequently a management science model consists of a set of mathematical
relationships.

Page 10
 4. Model solution: - once models have been constructed in management science,
they are solved using the management science techniques. A management science
solution technique usually applies to a specific type of model.
5. Implementation: - is the actual use of the model once it has been developed or the
solution to the problem the models was developed to solve. It is a critical but
often overlooked step in the process.
1.7. Models and modeling in operations research
Dear learners, here we will discuss models and modeling in operations research.
The approximation or abstraction, maintaining only the essential elements of the system,
which may be constructed with various forms by establishing relationships among
specified variables and parameters of the system, is called a model.
Models attempt to describe the essence of a solution or activity by abstracting from
reality so the decision maker can study the relationship among relevant variables in
isolation. Hence, models do not, and cannot represent every aspect of reality because of
the innumerable and changing characteristics of the real life problems to be represented.
Instead, they are limited approximation of reality.
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 situation form. A model should be as simple as possible so as to give the
desired result. There are many ways to classify models. Classification schemes can also
provide a useful frame of reference for modelers. There are five classification schemes
for models.

Self-check questions

1.
1. What is operations
Classification research?
based on structure
2. What are the main
a) Physical modelsfeatures of operations research?
3. What are basic causes for the rapid development of operations research?

Page 11
The models provide a physical appearance of the real object under study either reduced in
size or scaled up. Physical models are useful only in design problems because they are
easy to observe, build and describe.

i. Iconic models: - retain some of the physical properties and characteristics of the
system they represent. An iconic model is either in an idealized form or is a scaled
version of the system. Such models represent the system as it is by scaling it up or
down (i.e. enlarging or reducing the size).
Examples: blueprints of a home, maps, globes, photographs, drawings, a
model airplane in a wind tunnel, trains etc.

The chief merit of an iconic model is that it is concrete and specific. It resembles visually
the thing it represents and therefore, there are likely to be fewer problems in translating
any “findings” from the model into the real-life situation. However, the disadvantage of
such models is that they often do not lead themselves to manipulation for experimental
purpose.

ii. Analogue models: - represent a system by a set of properties different from those
of the original system and does not resemble it physically. After the problem is
solved, the solution is reinterpreted in terms of the original system.
Examples: organizational chart, maps in different colures may represent
water, desert and other geographical feature. These models are less specific
and concrete but are easier to manipulate and are more general than iconic
models.
b) Symbolic models

Use symbols (letters, numbers) and functions to represent variables and their
relationships to describe the properties of the system. These models are also used to
represent relationships which can be represented in a physical form.

i. Verbal models: - describe a situation in written or spoken language. Example the

perimeter (P) of a rectangle is equal to the sum total of two times the length (L) and
two times the width of the rectangle.

Page 12
ii. Mathematical models: - involve the use of mathematical symbols, letters, numbers
and mathematical operations (+, –, ÷, ×) to represent relationships among
variables of the system to describe its properties or behaviors.
Example: P = 2L + 2W

2. Classification based on function or purpose

a) Descriptive models: - simply describe some aspects of a situation, based on
observation, survey, questionnaire results or other available data of a situation and
do not predictive or recommend anything.

Example: - organizational chart plant layout diagram, block diagram

representing an algorithm or method for solving a problem etc.

b) Predictive models: - these models indicate “if these occurs then what will follow”.
They relate dependent and independent variables and permit trying out “what if
questions‟. Used to predict the outcomes due to a given set of alternatives for the
problem.
c) Normative (optimization) models: - provide the best or optimal solution to problems
subject to certain limitations on the use of resources. Are also called prescriptive
models because they provide what the decision maker out to do.

Page 13
3. Classification based on time reference
a. Static models: - static models represent a system at some specified time and do
not account for changes over time.
b. Dynamic models; - time is considered as one of the variables and allows the
impact of changes due to change in time. Thus the sequence of interrelated
decisions over a period of time is made to select the optimal course of action to
optimize the given objective.
4. Classification based on degree of certainty
a) Deterministic models

If all the parameters, constants and functional relationships are assumed to be known with
certainty when the decision is made, the model is said to be deterministic. Thus, in such
case, the outcome associated with a particular course of action is known. That is for a
specific set of input values, there is a uniquely determined output which represents the
solution of the model under considerations of certainty. The results of the models assume
single value.

b) Probabilistic (stochastic) models

Models in which at least one parameter or decision variable is a random variable are
called probabilistic (or stochastic) models. Since at least one decision variable is random,
therefore, an independent variable which is the function of dependent variable(s) will also
be random. This means consequence or payoff due to certain changes in the independent
variable cannot be predicted with certainty. However, it is possible to predict a pattern of
values of both the variables by their probability distribution.

Example: insurance against risk of fire, accidents, sickness, where the pattern of events is
studied in the form of probability distribution.

Page 14
5. Classification based on method of solution or quantification:
a. Heuristic models: These models employ some set of rules which, though
perhaps not optimal, do facilitate solution of problems when applied in a
consistent manner.
b. Analytical models: it has specific analytical structure and thus 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.
c. Simulation model: it has a mathematical structure but is not solved by
applying mathematical techniques to get a solution. Instead it is computer
assisted experimentation on a mathematical structure of a real life problem. It
is more flexible than a mathematical model and helps to represent complex
systems which otherwise can‟t be represented by mathematically.

Self-check questions

1. Briefly explain the difference between deterministic and probabilistic models?

2. Explain the nature of OR?

Page 15
 Chapter Summary

In our increasing complex world, the tasks of decision-makers are becoming more
challenging with each passing day. The decision-maker is expected to respond quickly to
events that seem to take place at an ever increasing pace.

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.

It is generally agreed that OR come into existence as a discipline during the second
world war when there was a critical need to manage scarce resources.

OR has interdisciplinary, methodological, wholistic and objectivistic approach for

problem solving.

OR is the representation of real-world systems by mathematical models together with the

use of quantitative methods (algorithms) for solving such models, with a view to
optimizing.

The operation research problem solving approach involves five major steps: observation,
definition of the problem, model construction and implementation of solution results.

The approximation or abstraction, maintaining only the essential elements of the system,
which may be constructed with various forms by establishing relationships among
specified variables and parameters of the system, is called a model.

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. There are different
classifications of models which are constructed to represent and resolve real world
business problem.

Page 16
 Exercises

1. Operations research analysts do not

a) Predict future operation c) Collect relevant data
b) Build more than one model d) Recommend decision and accept
2. Decision variables are
a) Controllable c) Parameters
b) Uncontrollable d) None of the above
3. A model is
a) An essence of reality c) An idealization
b) An approximation d) All of the above
4. A physical model is example of
a) An iconic model c) A verbal model
b) An analogue model d) A mathematical model
5. Operations research approach is
a) Multi-disciplinary
b) Scientific
c) Intuitive
d) All of the above

Page 17
 CHAPTER TWO

Linear Programming

 Learning objectives:

Dear distance learner! On successful completion of this chapter, you should be able to:

 Understand what leaner programming is and explain the component and

assumptions of Linear Programming?
 Formulate Linear Programming model and solve it by using graphic and simplex
solution techniques.
 Demonstrate special cases of graphic solution method.
 Solve maximization problem that have mixed constraint and interpret the solution.
 Solve minimization problems and interpret the solution.
 Study and demonstrate special cases of simplex solution method.
 Formulate the dual of a primal
 Read and interpret the solution to a dual problem, and relate the dual solution to
the primal solution.
 Explain the economic interpretation of dual variables and the dual solution.
 Use sensitivity analysis to evaluate change in RHS of a constraint and change in
the value of an objective function coefficient.

2.1. Introduction to Linear Programming

Dear distance learner! Linear Programming is a branch of mathematical programming

which is designed to solve optimization problems where all the constraints as well as the
objectives are expressed as linear function. It was developed by George B. Denting in
1940. Its earlier application was solely related to the activities of the second' World War.
However soon its importance was recognized and it came to occupy a prominent place in
the industry and trade.

Page 18
Linear Programming is a technique for making decisions under certainty i.e.; when
all the courses of options available to an organization are known & the objective of the
firm along with its constraints are quantified. That course of action is chosen out of all
possible alternatives which yield the optimal results. Linear Programming can also be
used as a verification and checking mechanism to ascertain the accuracy and
the reliability of the decisions which are taken solely on the basis of manager's
experience- without the aid of a mathematical model.

Some of the definitions of Linear Programming are as follows:

"Linear Programming is a method of planning and operation involved in the construction

of a model of a real-life situation having the following elements:

a) Variables which denote the available choices and

b) The related mathematical expressions which relate the variables to the controlling
conditions, reflect clearly the criteria to be employed for measuring the
benefits following out of each course of action and providing an accurate
measurement of the organization's objective. The method may be so devised' as to
ensure the selection of the best alternative out of a large number of alternative
available to the organization.

Linear Programming is the analysis of problems in which a linear function of a number of

variables is to be optimized (maximized or minimized) when whose variables are subject
to a number of constraints in the mathematical inequalities.

From the above definitions, it is clear that:

i. Linear Programming is an optimization technique, where the underlying

objective is either to maximize the profits or to minimize the Cost.
ii. It deals with the problem of allocation of finite limited resources amongst
different competing activities in the most optimal manner.
iii. It generates solutions based on the feature and characteristics of the
actual problem or situation.

Page 19
 iv. Linear Programming has been highly successful in solving the following
Types of problems :
a) Product-mix problems.
b) Investment planning problems.
c) Blending strategy formulations and
d) Marketing & Distribution management.
Even though Linear Programming has wide & diverse' applications, yet all LP problems
have the following properties in common:
 The objective is always the same (i.e.; profit Maximization or cost
minimization).
 Presence of constraints which limit the extent to which the objective can be
achieved.
 Availability of alternatives i.e.; different courses of action to choose from,
 The objectives and constraints can be expressed in the form of linear relation.
Regardless of the size or complexity, all LP problems take the same form i.e.
allocating scarce resources among various competing alternatives. Irrespective of the
manner in which one defines Linear Programming, a problem must have certain
basic characteristics before this technique can be utilized to find the optimal values.
2.2. The characteristics or the basic assumptions of linear programming
1. Decision or Activity Variables & Their Inter-Relationship. The decision or variables
refer to any activities which are in competition with other variables for limited resources.
Examples of such activity variables are: services, projects, products etc. These variables
are most often inter-related in terms of utilization of the scarce resources and need
simultaneous solutions. It is important to ensure that the relationship between these
variables be linear.
2. Finite Objective Functions. A Linear Programming problem requires a clearly defined,
unambiguous objective function which is to be optimized. It should be capable of being
expressed as a liner function of the decision variables. The single-objective
optimization is one of the most important prerequisites of linear programming. Examples
of such objectives can be: cost-minimization, sales, profits or revenue
Maximization & the idle-time minimization etc

Page 20
3. Limited Factors/Constraints. These are the different kinds of limitations on the
available resources e.g. important resources like availability of machines, number of man
hours available, production capacity and number of available markets or consumers
for finished goods are often limited even for a big organization. Hence, it is rightly said
that each and every organization function within overall constraints both internal
and external. These limiting factors must be capable of being expressed as linear
equations or in equations in terms of decision variables.
4. Presence of Different Alternatives. Different courses of action or alternatives should be
available to a decision maker, who is required to make the decision which is the most
effective or the optimal. For example, many grades of raw material may be available, the
same raw material can be purchased from different supplier, the finished goods can be
sold to various markets.
5. Non-Negativity Restrictions. Since the negative values of (any) physical quantity has
no meaning, therefore all the variables must assume non-negative values. If some of the
variables are unrestricted in sign, the non-negativity restriction can be enforced by the
help of certain mathematical tools - without altering the original information contained in
the problem.
6. Linearity Criterion. The relationship among the various decision variables must be
directly proportional. Both the objective and the constraint, must be expressed in
terms of linear equations or inequalities. For example. If one of the factor inputs
(resources like material, labor, plant capacity etc.) increases, then it should result
in a proportionate manner in the final output. These linear equations can graphically
be presented as a straight line.
7. Additively. It is assumed that the total profitability and the total amount of each
resource utilized would be exactly equal to the sum of the respective individual amounts.
Thus the function or the activities must be additive - and the interaction among
the activities of the resources does not exist.
8. Mutually Exclusive Criterion. All decision parameters and the variables are assumed to
be mutually exclusive. In other words, the occurrence of anyone variable rules out the
simultaneous occurrence of other such variables.
9. Divisibility. Variables may be assigned fractional values. i.e.; they need not

Page 21
 necessarily always be in whole number. If a fraction of a product cannot be produced, an
integer programming problem exists. Thus, the continuous values of the decision
variables and resources must be permissible in obtaining an optimal solution.
10. Certainty. It is assumed that conditions of certainty exist i.e.; all the relevant
parameters or coefficients in the Linear Programming model are ful1y and
completely known and that they don't change during the period. However, such an
assumption may not hold good at all times.
11. Finiteness. LP assumes the presence of a finite number of activities and constraints
without which it is not possible to obtain the best or the optimal solution.
Diagrammatically,

Scares To be allocated to:

Resource

Resource
constraints
Objectives Constraints

Non-negativity
Constraints

Optimization

Maximize Minimization

2.3. Advantages & Limitations of Linear Programming

Advantages of LP; The following are some of the advantages of LP approach:

1. Scientific Approach to Problem Solving. Linear Programming is the

application of scientific approach to problem solving. Hence it results in a better and true
picture of the problems-which can then be minutely analyzed and solutions ascertained.

Page 22
2. Evaluation of All Possible Alternatives. Most of the problems faced by the present
organizations are highly complicated - which cannot be solved by the traditional
approach to decision making. The technique of Linear Programming ensures that all
possible solutions are generated - out of which the optimal solution can be selected.
3. Helps in Re-Evaluation. Linear Programming can also be used in re- evaluation of a
basic plan for changing conditions. Should the conditions change while the plan is carried
out only partially, these conditions can be accurately determined with the help of Linear
Programming so as to adjust the remainder of the plan for best results.
4. Quality of Decision. Linear Programming provides practical and better quality of
decisions' that reflect very precisely the limitations of the system i.e.; the various
restrictions under which the system must operate for the solution to be optimal. If
it becomes necessary to deviate from the optimal path, Linear Programming can
quite easily evaluate the associated costs or penalty.
5. Focus on Grey-Areas. Highlighting of grey areas or bottlenecks in the production
process is the most significant merit of Linear Programming. During the periods of
bottlenecks, imbalances occur in the production department. Some of the machines
remain idle for long periods of time, while the other machines are unable to feel the
demand even at the peak performance level.
6. Flexibility. Linear Programming is an adaptive & flexible mathematical
technique and hence can be utilized in analyzing a variety of multi-dimensional problems
quite successfully.
7. Creation of Information Base. By evaluating the various possible alternatives in the
light of the prevailing constraints, Linear Programming models provide an
important database from which the allocation of precious resources can be don rationally
and judiciously.
8. Maximum optimal Utilization of Factors of Production. Linear Programming helps in
optimal utilization of various existing factors of production such as installed capacity,
labor and raw materials etc.

Page 23
 Limitations of Linear Programming
Although Linear Programming is successful and having wide applications in business and
trade for solving optimization problems, yet it has certain demerits or defects as follows:
1. Linear Relationship. Linear Programming models can be successfully applied only in
those situations where a given problem can clearly be represented in the form of
linear relationship between different decision variables. Hence it is based on the
implicit assumption that the objective as well as all the constraints or the limiting factors
can be stated in term of linear expressions - which may not always hold good in
real life situations. In practical business problems, many objective function & constraints
cannot be expressed linearly. Most of the business problems can be expressed quite easily
in the form of a quadratic equation (having a power 2) rather than in the terms of
linear equation.
2. Constant Value of objective & Constraint Equations. Before a LP technique could be
applied to a given situation, the values or the coefficients of the objective function
as well as the constraint equations must be completely known. Further, Linear
Programming assumes these values to be constant over a period of time. However, in real
life practical situations often it is not possible to determine the coefficients of objective
function and the constraints equations with absolute certainty. These variables in fact
may, lie on a probability distribution curve and hence at best, only the likely hood of their
occurrence can be predicted. Moreover, often the value's change due to external as well
as internal factors during the period of study. Due to this, the actual applicability of
LP tools may be restricted.
3. No Scope for Fractional Value Solutions. There is absolutely no certainty that the
solution to a LP problem can always be quantified as an integer quite often, Linear
Programming may give fractional-varied answers, which are rounded off to the next
integer. Hence, the solution wouldn‟t be the optimal one. For example, in finding out the
number of men and machines required to perform a particular job, a fractional Larson-
integer solution would be meaningless.
4. Degree of Complexity. Many large-scale real life practical problems can‟t be
solved by employing Linear Programming techniques even with the help of a
computer due to highly complex and Lengthy calculations. Assumptions and

Page 24
 approximations are required to be made so that the given problem can be broken down
into several smaller problems and then, solve separately.
5. Multiplicity of Goals. The long-term objectives of an organization are not confined to a
single goal. An organization, at any point of time in its operations has a multiplicity of
goals or the goals hierarchy - all of which must be attained on a priority wise basis for its
long term growth. Some of the common goals can be Profit Maximize or cost
minimization, retaining market share, maintaining leadership position and providing
quality service to the consumer. In cases where the management has conflicting,
multiple goals, Linear Programming model fails to provide an optimal solution.
The reason being that under Linear Programming techniques, there is only one goal
which can be expressed in the objective function.

2.4. Main Application Areas of Linear Programming

In the last few decades since 1960s, no other mathematical tool or technique has had such
a profound impact on the management's decision making criterion as Linear
Programming well and truly it is one of the most important decision making tools of the
last century which has transformed the way in which decisions are made and businesses
are conducted.

Some of the important application areas of Linear Programming are the following:

1. Military Applications. Paradoxically the most appropriate example of an

organization is the military and worldwide, Second World War is considered to be
one of the best managed or organized events in the history of the mankind. Linear
Programming is extensively used in military operations. Such applications include
the problem of selecting an air weapon system against the enemy so as to keep
them pinned down and at the same time minimize the amount of fuel used. Other
examples are dropping of bombs on pre-identified targets from aircraft and
military attacks against localized terrorist outfits.
2. Agriculture. Agriculture applications fall into two broad categories, farm
economics and farm management. The former deals with the agricultural

Page 25
 economy of a nation or a region, while the latter is concerned with the problems
of the individual form. Linear Programming can be gainfully utilized for
agricultural planning e:g. allocating scarce limited resources such as capital,
factors of production like labor, raw material etc. in such a way so as to maximize
the net revenue.
3. Environmental Protection. Linear programming is used to evaluate the various
possible a1temative for handling wastes and hazardous materials so as to satisfy
the stringent provisions laid down by the countries for environmental protection.
This technique also finds applications in the analysis of alternative sources of
energy paper recycling and air cleaner designs.
4. Facilities Location. Facilities location refers to the location nonpublic health care
facilities (hospitals, primary health centers) and public recreational facilities
(parks, community hal1s) and other important facilities pertaining to
infrastructure such as telecommunication booths etc. The analysis of facilities
location can easily be done with the help of Linear Programming. Apart from
these applications, LP can also be used to plan for public expenditure and drug
control.
5. Product-Mix. The product-mix of a company is the existence of various products
that the company can produce and sell. However, each product in the mix requires
finite amount of limited resources. Hence it is vital to determine accurately the
quantity of each product to be produced knowing their profit margins and the
inputs required for producing them. The primary objective is to maximize the
profits of the firm subject to the limiting factors within which it has to operate.
6. Production. A manufacturing company is quite often faced with the situation
where it can manufacture several products (in different quantities) with the use of
several different machines. The problem in such a situation is to decide which
course of action will maximize output and minimize the costs.
Another application area of Linear Programming in production is the assembly by-line
balancing, where a component or an item can be manufactured by assembling different
parts. In such situations, the objective of a Linear Programming model is to set the

Page 26
assembly process in the optimal (best possible) sequence so that the total elapsed time
could be minimized.
7. Mixing or Blending. Such problems arise when the same product can be
produced with the help of a different variety of available raw-materials each
having a fixed composition and cost. Here the objective is to determine the
minimum cost blend or mix (i.e. the cost minimizations) and the various
constraints that operate are the availability of raw materials and restrictions on
some of the product constituents.
8. Transportation & Trans-Shipment. Linear Programming models are employed
to determine the optimal distribution system i.e. the best possible channels of
distribution available to an organization for its finished product sate minimum
total cost of transportation or shipping from company's go down to the respective
markets. Sometimes the products are not transported as finished products but are
required to be manufactured at various sources. In such a situation, Linear
Programming helps in ascertaining the minimum cost of producing or
manufacturing at the source and shipping it from there.
9. Portfolio Selection. Selection of desired and specific investments out of a large
number of investment options available for the managers (in the form of financial
institutions such as banks, non-financial institutions such as mutual funds,
insurance companies and investment services etc.) it is a very difficult task, since
it requires careful evaluation of all the existing options before arriving at decision.
The objective of Linear Programming, in such cases, is to find out the
allocation/which maximizes the total expected return or minimizes the total risk
under different situations.
10. Profit Planning & Contract. Linear Programming is also quite useful in profit
planning and control. The objective is to maximize the profit margin from
investment in the plant facilities and machinery.
11. Traveling Salesmen Problem. Traveling salesmen problem refers to the problem
of a salesman to find the shortest route originating from a particular city, visiting
each of the specified cities and then returning back to the originating point of
departure. The restriction being that no city must be visited more than once during

Page 27
 a particular tour. Such types of problems can quite easily be solved with the help
of Linear Programming.
12. Media Selection/Evaluation. Media selection means the selection of the optimal
media-mix so as to maximize the effective exposure. The various constraints in
this case are: Budget limitation, different rates for different media (i.e.; print
media, electronic media like radio and T.V. etc.) and the minimum number of
repeated advertisements in the various media. The use of Linear Programming
facilities like the decision making process.
13. Staffing. Staffing or the man-power costs are substantial for a typical
organization which make its products or services very costly. Linear
Programming techniques help in allocating the optimum employees (man-power
or man-hours) to the job at hand. The overall objective is to minimize the total
man-power or overtime costs.
14. Job Analysis. Linear Programming is frequently used for evaluation of jobs in an
organization and also for matching the right job with the right worker.
15. Wages and Salary Administration. Determination of equitable salaries and
various incentives and perks becomes easier with the application of LP. LP tools
can also be utilized to provide optimal solutions in other areas of personnel
management such as training and development and recruitment etc.
2.5. Linear Programming problem Formation
Linear programming is one of the most useful techniques for effective decision making. It
is an optimization approach with an emphasis on providing the optimal solution for
resource allocation. How best to allocate the scarce organizational or national resources
among different competing and conflicting needs (or uses) forms the core of its working.
The scope for application of linear programming is very wide and it occupies a central
place in many diversified decisional problems. The effective use and application of linear
programming requires the formulation of a realistic model which represents accurately
the objectives of the decision making subject to the constraints in which it is required to
be made.
The basic steps in formulating a linear programming model are presented as follows:

Page 28
Step I Identification of the decision variables. The decision variables (parameters)
having a bearing on the decision at hand shall first be identified, and then expressed or
determined in the form of linear algebraic functions or in equations.

a. Express each constraint in words. For this first see whether the constraint is of the
form ≥ (at least, as large as), or of the form ≤ (no larger than) or = (exactly equal)
b. Then express the objective function verbally.
c. Step (a) and (b) should then allow you to verbally identify the decision variables.

Step II Identification of the constraints. All the constraints in the given problem which
restrict the operation of a firm at a given point of time must be identified in this stage.
Further these constraints should be broken down as linear functions in terms of the pre-
defined decision variables.

Step III Formulate the objective function. In the last stage, the objective which is
required to be optimized (i.e., maximized or memorized) must be dearly identified and
expressed in terms of the pre-defined decision variables.

Example 1

3F furniture Ltd. manufactures two products, tables & chair. Both the products have to
be processed through two machines Ml & M2 the total machine-hours available are: 200
hours ofM1 and 400 hours of M2 respectively. Time in hours required for producing a
chair and a table on both the machines is as follows:

Time in Hours:

Machine Table Chair

M1 7 4

M2 5 5

Profit from the Sale of table is Birr 40 and that of a chair is Birr 30.

Page 29
Required: formulate the LP Problem (LPP)?
Solution:
Step I Identification of the decision variables. Let x1 = Number of tables produced and
X2 = Number of Chairs produced
Step II List down all the constraints.
a) Total time on machine M1 cannot exceed 200 hour

(Since it takes 7 hours to produce a table & 4 hours to produce a chair on machine M1)
b) Total time on machine M2 cannot exceed 400 hour

(Since it takes 5 hours to produce both a table & a chair on machine M 2)

Step III. The objective function for maximizing the profit is given by
Maximize
(Since profit per unit from a table and a chair is Birr 40 & Birr. 30 respectively).

Presenting the problem as LPP, the given problem can now be formulated as a linear
programming model as follows:

Maximize Z
Subject to:

Further;
(Since if < 0 it means that negative quantities of products are being manufactured
which has no meaning).
Example 2
Alpha Limited produces & sells 2 different products under the brand name black &
white. The profit per unit on these products is Birr 50 & Birr 40 respectively. Both black
& white employ the same manufacturing process which has a fixed total capacity of
50,000 man-hours. As per the estimates of the marketing research department of Alpha
Limited, there is a market demand for maximum 8,000 units of Black & 10,000 units of

Page 30
white. Subject to the overall demand, the products can be sold in any possible
combination. If it takes 3 hours to produce one unit of black & 2 hours to produce one
unit of white. Formulate a linear programming model?
Solution:

Step I Identification of the decision variables. Let x1& x2 denote the number of units
produced, black & white brand respectively.

Step II: List down all the constraints.

a) Capacity or man-hours constraint:

3x1+2x2

(Since it takes 3 hours to produce 1 unit of x 1 & 2 hours to produce 1 unit of x2 & the
total available man – hours are 50,000).

b) Marketing constraints:

(Since maximum 8,000 units of x1 can be sold)

(Since maximum 10,000 units of x2 can be sold).

Step III. The objective function for maximizing the profit is given by

Maximize

Presenting the problem as LPP Now, the given problem can be written as a linear
programming model in the follows:

Maximize Z = 50x1 + 40x2

Page 31
 Subject: 3x1+2x2

Further;

(Since if x1, x2< 0, it means that negative Quantities of products are being manufactured –
which has no meaning)

Exercise

The management of ABC Chemicals is considering the optimal mix of two possible
processes. The values of input & output for both these process are given as follows:

Process Unit-input Unit-output

I1 I2 O1 O2

X 2 6 3 7

Y 4 8 5 9

Maximum 500 units of Input I1 and 300 units of I2 are available to ABC Chemicals in the
local market. The forecasted demand for outputs OI & O2 are at least 5,000 units & 7,000
units respectively. The respective profits from process X & Y are Birr 1,000 & Birr 2,000
per production run.

Required: formulate the above problem as a linear programming model.

Page 32
 2.6. Method for solving LPP

There are two types of finding a solution for Linear programming problems.

a) Graphic solution and

b) Simplex method

2.7. Graphical Method of solving Linear Programming Problems

2.7.1. Introduction

Dear learners, during the previous section, you have seen how to formulate a given
problem as a Linear Programming model. And you are also familiar with the method of
solving LP models by using graphics method (see module of mathematics for
management mgt221). So in this module we try to remind you some points of graphic
solution method.

The next step, after the formulation of LP model is to devise effective methods to solve
the model and ascertain the optimal solution.

Dear learners, we start with the graphical method of solving LPP and now let we move
on to simplex algorithm for solving the Linear Programming model.

The graphic solution procedure is one of the methods of solving two variable linear
programming problems.

2.7.2. Steps in graphic solution method:-

Step I Defining the problem. Formulate the problem mathematically. Express it in terms
of several mathematical constraints & an objective function. The objective function
relates to the optimization aspect, i.e. Maximization or minimization Criterion.

Step II Plot the constraints graphically. Each inequality in the constraint equation has to
be treated as an equation. An arbitrary value is assigned to one variable & the value of the
other variable is obtained by solving the equation. In the similar manner, a different

Page 33
 arbitrary value is again assigned to the variable & the corresponding value of other
variable is easily obtained. These 2 sets of values are now plotted on a graph and
connected by a straight line. The same procedure has to be repeated for all the
constraints. Hence, the total straight lines would be equal to the total no of equations,
each straight line representing one constraint equation.

Step III Locate the solution space. Solution space or the feasible region is the graphical
area which satisfies all the constraints at the same time. Such a solution point (x, y)
always occurs at the corner Points of the feasible Region the feasible region is determined
as follows:

a) For "greater than" & "greater than or equal to" constraints, the feasible region or the
solution space is the area that lays above the constraint lines.
b) For" Less Then" &" Less than or equal to" constraint, the feasible region or the
solution space is the area that lays below the constraint lines.

Step IV Selecting the graphic solution technique. Select the appropriate graphic technique
to be used for generating the solution. There are two graphic techniques to find solution;

1. Corner Point Method and

2. Iso-profit (or Iso-cost) method may be used; however, it is easier to generate
solution by using the corner point method and we use this method to find solution.
2.7.3. Corner Point Method to find Solution for Graphics Method

I. Since the solution point (x, y) always occurs at the corner point of the feasible or
solution space, identify each of the extreme points or corner points of the feasible
region by the method of simultaneous equations.
II. By putting the value of the corner point's co-ordinates [e.g. (2, 3)] into the objective
function, calculate the profit (or the cost) at each of the corner points.
III. In a Maximize problem, the optimal solution occurs at that corner point which gives
the highest profit. In a minimization problem, the optimal solution occurs at that
corner point which gives the lowest profit.

Page 34
Dear learners, let us now turn our attention to the important theorems which are used in
solving a linear programming problem.

Important Theorems in solving LPP

On the process of determining an optimum feasible solution to the linear programming

problem, the following four important theorems are used:-

Theorem I the feasible solution space constitute a convex set.

Theorem II within the feasible solution space, feasible solution correspond to the
extreme (or Corner) points of the feasible solution space.
Theorem III There is a finite number of basic feasible solutions, with the feasible
solution space.
Theorem IV The optimum feasible solution, if it exists, will occur at one, or more, of the
extreme points that are basic feasible solutions.

Note. Convex set is a polygon "Convex" implies that if any two points of the polygon are
selected arbitrarily then straight line segment joining these two points lays completely
within the polygon. The extreme points of the convex set are the basic solution to the
linear programming problem.

Important Terms

Some of the important terms commonly used in linear programming are disclosed as
follows:

a. Solution: Values of the decision variable satisfying the

constraints of a general linear programming model is known as the solution to
that linear programming model.
b. Feasible solution: Out of the total available solution a solution that also
satisfies the non-negativity restrictions of the linear programming problem is
called a feasible solution.

Page 35
 c. Basic solution: For a set of simultaneous equations in Q unknowns (P, Q) a
solution obtained by setting (P - Q) of the variables equal to zero & solving the
remaining P equation in P unknowns is known as a basic solution. The
variables which take zero values at any solution are detained as non-basic
variables & remaining are known as-basic variables, often called basic
solution.
d. Basic feasible solution: A feasible solution to a general linear programming
problem which is also basic solution is called a basic feasible solution.
e. Optimal feasible solution: Any basic feasible solution which optimizes (i.e.
maximize or minimizes) the objective function of a LP models is known as the
optimal feasible solution to that linear programming model.
f. Degenerate Solution: A basic solution to the system of equations is termed as
degenerate if one or more of the basic variables become equal to zero.

Example 1

XYZ Ltd. Co. Wishes to purchase a maximum of 3600 units of two types of product, A &
B are available in the market. Product A occupies a space of 3 cubic feet & cost Birr 9
whereas B occupies a space of 1 cubic feet & cost Birr 13 per unit. The budgetary
constraints of the company do not allow spending more than Birr 39,000. The total
availability of space in the company's god own is 6000 cubic feet. Profit margin of both
the product A & B is Birr 3 & Birr 4 respectively. Formulate the above problem as a
linear programming model and solve it by using graphical method. You are required to
ascertain the best possible combination of purchase of A & B so that the total profits are
maximized.

Solution

(a) The problem can be formulated as a linear programming model as follows:-

Let x1 = Number of units of product A &

x2 = Number of units of product B

Page 36
 Objective function,

Subject to: -

(Maximum unites constraint)

(Storage area constraint)

(Budgetary constraint)

(b) Find the solution by using graphics method

Step I Treating all the constraints as equality,

The 1st constraint is: e this in to and find the

X and Y intercept as follows.

Put

Put

Draw the graph with x1 on x-axis & x2 on y-axis as shown in the following figure.

nd
The 2 constraint is: change this in to and find X and Y
intercept.

Put

Put

Draw the graph with x1 on x-axis & x2 on y-axis as shown in the following figure.

Page 37
 rd
The 3 constraint is: e this in to
and find the X and Y intercept as follows.

Put

Put

Draw the graph with x1 on x-axis & x2 on y-axis as shown in the following figure.

Step II Determine the set of the points which satisfy the constraint:

This can easily be done by verifying whether the origin (0, 0) satisfies the constraint.
Here, hence the solution is true; all the points below the line will satisfy
the constraint.

Like it‟s in the above iteration, determine the set of points which satisfy the
constraint . At origin;

. Hence, all the points below the line will satisfy the constraint.

Like it‟s in the above iteration, determine the set of points which satisfy the constraint.
At origin;

. Hence, all the points below the line will satisfy the constraint.

The intersection of the above graphic denotes the feasible region for the given problem.

Step III Finding feasible region by plotting the graph

Always keep in mind two things: -

Page 38
 a. For ≥ constraint the feasible region will be the area, which lays above the constraint lines,
and for ≤ constraints, it will lays below the constraint lines. This would be useful in
identifying the feasible region.
b. According to a theorem on linear programming, an optimal solution to a problem (if it
exists) is found at a corner point of the solution space.

X1

6000 (Maximum unites constraint)

Number of unites of B

3600 (Storage area constraint)

B
3000 A (Budgetary constraint)
1

Feasible
region
O X1
(0, 0) C
2000 3600 3900/9

Number of unites of A

Step IV. Find the optimal solution by the corner point method.

At corner points (O, A, B, C), find the profit value from the objective function. Those
points which maximize the profit are the optimal point.

Page 39
 Corner point Coordinates Objective function Value

Optimal
solution
O (0,0) Z=0+0 0

A (0,3000) Z=0+4x3000 12,000

B (1300,2100) Z=3x1300 + 4 x2100 12,300

C (2000,0) 3 x 2000 + 0 6000

In order to get the value of point B apply simultaneous equation by taking the two
intersection lines. Solve the point.
(Storage area constraint)
(Budgetary constraint)
(∴ A+B these two lines are intersecting)
3x1 x 2 6000 …1

…2
Multiply equation (1) by -3 on both sides:
-9x1 - 3x 2 -18000 …3

…4
__ __ __
10X2 = 21,000 ∴ =2100
Put the Value of x2 in first equation:

⇒X1=1300
At point (1300, 2100)

= 12,300 which is the maximum value

Result
The optimal solution is:
No of units of product A=1300

Page 40
No of units of product B=2100
Total profit, = 12, 300 which is the maximum

Example 2:

Suppose that a machine shop has two different types of machines; machine 1 and
machine 2, which can be used to make a single product .These machine vary in the
amount of product produced per hour, in the amount of labor used and in the cost of
operation.

Assume that at least a certain amount of product must be produced and that we would
like to utilize at least the regular labor force. How much should we utilize each machine
in order to utilize total costs and still meets the requirement? The resource used, the cost
and the required hour is given in the following table.

Resource used

Machine 1 Machine 2 Minimum required hours

(X1) (X2)

Product produced/hr 20 15 100

Labor/hr 2 3 15

Operation Cost Birr25 Birr30

1. Formulation of the linear programming model

Min.Z  25 X 130 X 2
Subjectto:
20 X 115 X 2 100
LPP Model
2 X 13 X 2 15
X1, X 2  0

Page 41
 st
The 1 constraint is: change this in to and find
X and Y intercept.

Put

Put

Draw the graph with x1 on x-axis & x2 on y-axis as shown in the following figure.

The 2nd constraint is 2X1+3X2≥15 change this in to 2X1+3X2=15 and find X and Y
intercept.

Put

Put

Draw the graph with x1 on x-axis & x2 on y-axis as shown in the following figure.

Determine the set of the points which satisfy the constraint:

This can easily be done by verifying whether the origin (0, 0) satisfies the constraint.
Here,

Hence the solution is false; all the points above the line will satisfy the
constraint.

Like it‟s in the above iteration, determine the set of points which satisfy the constraint

2X1 + 3X2 ≥ 15 at origin;

. Hence, all the points above the line will satisfy the constraint.

Page 42
 Finding feasible region by plotting the graph

Always keep in mind two things: -

i. For ≥ constraint the feasible region will be the area, which lays above the constraint lines,
and for ≤ constraints, it will lays below the constraint lines. This would be useful in
identifying the feasible region.
ii. According to a theorem on linear programming, an optimal solution to a problem (if it
exists) is found at a corner point of the solution space.

X2
X1 =0
A (0, 20/3) 2X1 + 3X2 = 15

Feasible Region
5
B (2.5, 3.33)
X2 =0

X1
5 C (7.5, 0)

Feasible solution
Corner point Coordinates Objective function Value

Minimize.Z  25X 130X 2

A (0,20/3) Z=0+20/3×30 200

B (2.5, 3.33) Z=2.5×25+3.33x30 162.5

C (7.5, 0) Z=7.5x25+0 187.5

Use the same stapes to find the value of B by using the simultaneous equation as
presented previously.

Page 43
Result

The optimal solution is:

X1 =2.5, X2=3.33 and Minimum cost Z= 162.5

2.7.3. Special Cases in Graphics Methods

The following are the major special cases in graphics solution

• Alternative Optima

• Infeasible Solution

• Unbounded solution

a) Alternative Optimal solution

When the objective function is parallel to a binding constraint; (a constraint that is

satisfied in the equality sense by the optimal solution), the objective function will assume
the same optimal value at more than one solution point, for this reason they are called
alternative optima. Example 1 shows that normally there is infinity of such solutions.
The example also demonstrates the practical significance of encountering alternative
optima.

Example1

Page 44
The above Figure demonstrates how alternative optima can arise in LP model when the
objective function is parallel to a binding constraint. Any point on the line segment BC
represents an alternative optimum with the same objective value z = 10. Mathematically,
we can determine all the points (x1, x2) on the line segment BC as a nonnegative weighted
average of the points B and C. That is, given 0 α 1 and

B: x1= 0, x2=5/2

C: x1= 3, x2= 1

Then all points on the line segment BC are given by

x1=α(0) + 3 (1-α) =3 - 3α

x2=α(5/2) + 1 (1-α) =1 + 3α/2

Page 45
 Observe that when α=0, (x1, x2) = (3, 1), which is point C. When α=1, (x1,
x2) = (0, 5/2), which is point B. For values of α between 0 and 1 (x 1, x2) lays
between B and C

Example 2:

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

_____________________________________________________________________

Machine hours per week Maximum available

Department Product A Product B per week

_____________________________________________________________________

Cutting 3 6 900

Assembly 1 1 200

Profit per unit Birr 8 Birr 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 Number of units‟ f product A produced per week
X2 = The number of units f product B produced per week
a. The LPP Model of the problem is:

Page 46
 Max.Z  8 X 116 X 2
Subjectto:
3 X 16 X 2 900
X 1 X 2 200
X 2  125
X1, X 2  0

X2 X2=0

(0, 200)
X 1 X 2 200
(0,150) X2=125 Marketing equation
C (50, 125)
B (0, 125)
D (100,100)
Cutting: 3X1+6X2=900

FR X1=0

A (0, 0) X1
(200, 0) (300, 0)

Corners Coordinates Maximize 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:
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.

Page 47
 2. 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:

Maximize Z=20X1+30X2

Subject to:

2X1+X2< 40

4X1+X2< 60

X1 > 30 and X1, X2 > 0

Solution:

X2 X1=0
(0, 60) X1=30
4X1+X2= 60
(0, 40)

2X1+X2= 40
X2=0
X1
(15, 0) (20, 0) (30, 0)

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

Page 48
3. 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. Maximize Z=3X1+4X2

Subject to:

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

-X1+X2<0

X2 X1, X2 > 0
X1-X2 =-1

X1+X2 =0

1 Unbounded
Feasible region

Feasible Region
X1

2. Maximize Z=3X1+2X2

Subject to:

X1-X2<1

Page 49
 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
Maximize Z(A)=6 and Maximize Z(B)=8. But there exist number of points in the shaded
region for which the value of the objective function is more than [Link] 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.

Exercise 1:

Use graphical method to solve the following LPP.

1. Maximize Z=7/4X1+3/2X2 [Link]=X1+X2

Subject to: Subject to:

8 X1+5X2 < 320 X1+X2 < 1

4X1+5X2 < 20 -3X1+X2> 3

X1 > 15 X1, X2> 0

X2> 10

Page 50
 X1, X2 > 0

Answer: No feasible solution Answer: Unbounded solution

3. Maximize Z=3X1+2X2 4. Maximize Z=6X1-4X2

Subject to: Subject to:

X1-X2 < 1 2X1+4X2 < 4

X1+X2> 3 4X1+8X2> 16

X1, X2> 2 X1, X2 > 0

Answer: Unbounded solution Answer: Infeasible solution

Exercise2.

I. Solve the following LP problems using the graphical method.

1. Maximize Z=15X1-10X2 [Link]=2X1+X2

Subject to: Subject to:

4X1+6X2 < 360 X1+2X2 < 10

3X1+0X2< 180 X1 +X2 < 6

0X1+5X2< 280 X1 - X2 < 2

X1, X2 > 0 X1 -2X2 < 1

Answer: X1=60 , X2 =20 X1, X2 >0

and Maximize Z=1,100 Answer: X1=4, X2 =2
and Maximize Z=10

3. Maximize .Z=10X1+15X2 [Link].Z=3X1+2X2

Subject to: Subject to:

2X1+X2 < 26 5X1+X2 > 10

2X1+4X2< 56 X1 +X2 > 6

Page 51
 -X1+X2< 5 X1 + 4 X2 > 12

X1, X2 > 0 X1, X2 >0

Answer: X1=4, X2 =2 Answer:X1=1,X2=5 and

Maximize Z=230 and Minimize Z=13

II.A manufacturer produces two different models; X and Y, of the same product .The raw
materials r1 and r2 are required for production. At least 18 Kg of r1 and 12 Kg of r2 must
be used daily. Almost at most 34 hours of labor are to be utilized .2Kg of r1 are needed
for each model X and 1Kg of r1 for each model Y. For each model of X and Y, 1Kg of r2
is required. It takes 3 hours to manufacture a model X and 2 hours to manufacture a
model Y. The profit realized is $50 per unit from model X and $30 per unit from model
Y. How many units of each model should be produced to maximize the profit?

Answer: 10 units of model X, 2 units of model Y and the maximum profit is $ 560.

III.A manufacturing firm produces two machine parts P1 and P2 using milling and
grinding machines .The different machining times required for each part, the machining
times available on different machines and the profit on each machine part are as given
below:

____________________________________________________________________

Manufacturing time Maximum time

Required (min) available per week (minimum)

Machine P1 P2

________________________________________________________________________

Lathe 10 5 25,000

Milling Machine 4 10 2000

Grinding Machine 1 1.5 450

Page 52
 Profit per unit ($) $50 $100

_____________________________________________________________________

Determine the number of pieces of P1 and P2 to be manufactured per week to maximize

profit.

Answer: X1=187.5, X2 =125 and Maximize Z=21,875

2.8. Simplex Method

Dear learners, all of you have by now understand the graphical method of solving a
linear programming model and the various special cases of graphic solution of linear
programming model.

Let us see what the limitations of graphic solution are, and how can these be deal with?

Limitations of the Graphical Method

The applicability of the graphical method is very limited in scope. This is due to the fact that
it is quite simple to identity all the corner points & then tests them for optimality-in the case
of a two-variable problem. As a result, the graphical method cannot be always employed to
solve the real-life practical Linear programming models which involve more than two
decision-variables.

The above limitation of the graphical method is tackled by what is known as the simplex
method. Developed in 1940 by George B-Dantizg, it remains a widely applicable method for
solving complex LP problems. It can be applied to any LP problem which can be expressed
in terms of a Linear Objective function subject to a set of Linear Constraints. As such, no
theoretical restrictions are placed on the number of decision variables or constraints
contained in a LPP.

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

Page 53
feasible solution improving the situation 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, the solution space improving the value of the objective function each
time until optimal solution is reached at the optimal corner.

2.8.1. Standard forms of Linear Programming (LP) problems

The use of the Simplex method to solve an LP problem requires that the problem be
converted into its standard form. The standard form of the LP problem should have the
following characteristics:

i. All the constraints should be expressed as equations by adding slack or

surplus and/or artificial variables.
ii. The right hand side of each constraint should be made non-negative; if
it is not, this should be done by multiplying both side of the resulting
constraint by -1.
iii. The objective function should be of the maximization type.

The standard form of LP problem is expressed as follow;

Optimize (Maximize or Minimize) Z=

Subject to the linear constraint:

. .

. .

. .

Page 54
And

Where c= ( ) the coefficient of the objective function; x= ( )

decision variables; b= ( ) the limited resource available and s= ( )
slack variables.

In matrix notation the standard form is expressed as:

Optimize (Maximize or Minimize) Z=cx+0s

Subject to the linear constraint:

Where c= ( ) is the row vector, , , and

s= ( ) are column vector.

Hence, this method is used, which can solve LP problems with any number of variable or
constraints it is geared towards solving optimization problems which have constraints of
less than or equal to type.

And

The above matrix is the matrix of coefficient of variables in the constraints.

Remarks; three types of additional variables, namely

 Slack variable (s)

Page 55
  Surplus variable (-s), and
 Artificial variable (A)

Are added in the given LP problem to convert it in to the standard form for the following
reasons:
a. These variables allow as converting inequalities in to equalities, there by
converting the LP problem in to a form that is amenable to algebraic solution.
b. These variables permit as to make a more comprehensive economic interpretation
of a final solution.
c. Help us to get an initial feasible solution presented by the column of the identity
matrix.
The summery of the extra variable to be added in the given LP problem to convert it in to
standard form is given in the following table.

Types of Extra variable needed Coefficient of extra variables In Presence of extra variable in
constraint the objective function initial solution mix

Max Z Min Z

Less than or A slack variable is 0 0 Yes

equal to ≤ added

Greater than or A surplus variable is 0 0 No

equal to (≥) subtracted and
-M +M Yes
artificial variable is
added

Equal to (=) Only an artificial -M +M Yes

variable is added

Remark: a slack variable represents unused resource, either in the form of time on a
machine, labor hour, money, warehouse space or any number of such resources in various
business problems. Since variable yields no profit, therefore such variable are added to
the original objective function with zero coefficients.

Page 56
A surplus variable represents amount by which solution values exceed a resource. These
variables are also called negative slack variables. Surplus variables carry a zero
coefficient in the objective function.

2.8.2. The major steps and activities to solve LP model by using Simplex
method

This method utilizes the property of a LP problem of having optimal solution only at the
corner point of the feasible solution space. It systematically generates corner point
solutions & evaluates them for optimality. The method stops when an optimal solution is
found. Hence, it is an iterative (repetitive) technique.

If we get more variables & less equation, we can set extra variables equal to zero, to
obtain a system of equal variables & equal equations. Such solution is called basic
solution.

The variables having positive values in a basic feasible solution are called basic variable
while the variables which are set equal to zero, so as to define a corner point are called
non-basic variables.
Slack variables are the fictitious variables which indicate how much of a particular
resource remains unused in any solution. These variables can‟t be assigned negative
values. A zero value indicates that all the resources are fully used up in the production
process.

Column denotes the unit contribution margin.

Row is simply a statement of the projective function.

Row denotes the contribution margin lost if one unit is brought into the solution.

Hence, it represents the opportunity cost. (Opportunity cost is the cost of sacrifice i.e., the
opportunity foregone by selecting a particular course of action out of a number of
different available alternatives).

Page 57
 Row denotes the Net Potential contribution or the Net unit margin potential, per

unit.
The rules used under simplex method, for solving a linear programming problem are as
follows:-
1. Convert the LP to the following form:

Convert the given problem into Standard maximization Problem i.e. minimization
problem into a maximization one (by multiplying the objective function by -1). All
variables must be non-negative. All right hand side values must be non-negative
(multiply both sides by -1, if needed). All constraints must be in ≤ form (except the
non-negativity conditions). No strictly equality or ≥ constraints are allowed.

2. Convert all ≤ constraints to equalities by adding a different slack variable for each
one of them.
3. Construct the initial simplex tableau with all slack variables in the Basic Variables.
The last row in the table contains the coefficient of the objective function (row ).

4. Determine whether the current tableau is optimal. That is: If all the right hand side
values are non-negative (called the feasibility condition). If all elements of the last
row, that is rows are non-positive (called, the optimality condition)

If the answers to both of these two questions are yes, then stop. The current tableau
contains an optimal solution. Otherwise, go to the next step.

5. If the current BASIC VRIABLES is not optimal, determine, which non basic variable
should become a basic variable and, which basic variable should become a non basic
variable. To find the new BASIC VRIABLES with the better objective function value,
perform the following tasks:
Identify the entering variable: The entering variable is the one with the
largest positive value (In case of a tie, select the variable that corresponds

to the left most of the columns).

Page 58
 Identify the outgoing variable: The outgoing variable is the one with
smallest non-negative column ratio (to find the column ratios, divide the RHS
column by the entering variable column, wherever possible). In case of a tie
select the variable that corresponds to the upper most of the tied rows.
Generate the new tableau
a. Select the largest value of row. The column, under which this

value falls, is the pivot-column.

b. Pivot-row selection rule. Find the ratio of quantity to the corresponding
pivot-column coefficient. The pivot-row selected is the variable having
the least ratio.

Remark: Rows having negative or zero coefficients in the pivot-column are to be

neglected.
c. The coefficient, which is in both, the pivot-row & the pivot column, is
called the pivot-element or pivot-number.
d. Up-dating Pivot-row. Pivot-row, also called replaced rows, are updated as
under all elements of old-row divided by Pivot-element. Now, in the
basic activities column, write the pivot-column variable in place of the
pivot-row variable. i.e.; the pivot-row variable is to be replaced by the
pivot-column variable.
e. Up-Dating all other rows. Update all other rows by updating the formulae.

Up-dating rows. Each is obtained as the sum of the products of the

column coefficients multiplied by the corresponding coefficient in the jth column. (i.e.)
the Quantity column). It is then subtracted from row values to get

values. This pivoting is to be repeated till no positive coefficients exist in the

row, the optimal solution is known.

Page 59
 2.8.3. Simplex algorism (Maximization Case)

What is a Standard Maximization Problem?

A Standard Maximization Problem is the one that satisfies the following four conditions

1. The Objective function is to be maximized.

2. All the inequalities are of ≤ type.

3. All right hand constants are non-negative.

4. All variables are non-negative.

Dear learners, let us consider some examples to test our understanding of the solution
algorithm that has been discussed so far.

Example 1

Smart Limited manufactures two types of cement which are sold under the brand name
quick and Tuff. Each product consumes the same raw materials but in varying
proportions. The following table depicts the amount of raw materials along with thei r
respective cost.

Raw material type Price (Birr/ton) Quick Tuff

N 600 350 200

A 400 50 100

P 400 50 100

I 200 550 600

1000kg 1000kg

Page 60
Quick can be blended @ 1000 kg /hour whereas the blending rate for Tuff is 1250
kg/hour. Their respective selling prices are Birr. 1010 & Birr 845 You may assume the
variable costs to be Birr 500 per hour of plant production time. The maximum availability
of raw materials is:

Raw Material Types Max available (kg)

N 1000

A 300

P 250

I 1800

Formulate as a linear programming model and find out the optimal units of quick & tuff
to be produced so as to maximize the profits.

Solution

Step I List the objective & constraint equations.

Step II Introduce the slack variables

Step III Arrange in the form of initial table.

Step IV Find out the profit-margins from given sales price.

Step V Generate solutions.

The detailed solutions are as under:

Step I List the objective & constraint equations.

Maximize Cont-margin =

Subject to:

Page 61
 Xj ≥0 for all j

How to calculate the Profit Margin?

Late first find the time taken to manufacture 1000 kg of both types. It is required for
allocating variable production costs to finished product.

∴ 1250 kg Tuff is made in one hour.

∴ 100 kg of Tuff = 0.8 hr.

∴Variable production cost for Tuff 0.8 x 500 = Rs. 400

∴Variable production cost for Quick Rs. 500 (∴ in 1 hr. 1000 kg is made)

Particulars Revenue/sales (given) Quick (Rs.) Tuff (Rs.)

(-) variable costs: Direct Mat 1,010 845
N– 310 120
A– 20 40
P– 110 120
I– 20 40
Sub-total 360 320
Direct paid cost 500 400
Total var. cost 860 720
Contribution margin 150 125

Remarks

1. Given cost of 1000 kg of Birr 600

Given cost of 350 kg of = Birr 210 (for Quick)

Given cost of 200 kg of Birr 120 (for Tuff) etc.

Page 62
2. Contribution margin represents the profit which remains if after deducting variable costs
from sales i.e.; It covers fixed costs & net profit i.e. it fixed cost = Birr 200 X five – 100
kg of quick are sold then the net profit = 5 x 150 –200 = Rs. 550

(Fixed cost do not vary with the output)

3. All calculation has been done to obtain the contribution margin (i.e., profit)

Let x1 = thousands of kg of quick to be produced.

= thousands of kg of tuff to be produced.

Now, we have to find those values of x1 & x2 for which the contribution is maximum.
Here, the constraint is the availability of raw material. Hence, the problem is formulated
as;

Maximize Z=
Subject to:

Hence, the problem has been formulated

Step II Introduce the slack variables:

Slack Variables:

A slack 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 (linear programming problem) 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.

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

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.

Converting inequalities into equalities by using slack-variable

Maximize Cont-margin =

Subject to:

Page 64
 Note. We have dropped: as it is already contained in

Slack can‟t be larger than the constant. On right hand side (RHS) (i.e.
etc) It is to be so, and then some other variable must be negative for
equality to exist, which is not possible.
(2) Rewriting as:
Maximize Cont-margin =

Subject to:

Basic 150 125 0 0 0 (Birr.) Min ratio

Activities x1 x2 S1 S2 S3 Qty. RHS RHS/x1 Living

variable

(Pivot row)
0 S1 350 200 1 0 0 1000
)

0 S2 50 100 0 1 0 250

0 S3 550 600 0 0 1 1800

Pivot point Entering

0 0 0variable
0 0(Pivot
0
Column)

150 125 0 0 0

Page 65
Pivot Column = x1 (Largest value of )

Pivot row the lowest value in the min ratio column that is 2.875

∴ S1 is the pivot- row

Pivot element = 350, the intersection of the pivot raw and pivot column

Up-dating Pivot-row

nd
Make the pivot-row of 2 tableau:

Cj Basic Birr 150 125 0 0 0

Act. Qty.
Birr x1 x2 S1 S2 S3

150 x1 2.8571 1 0.5714 0 .0029 0 0

0 S2

0 S3

(Pivot column variable in place of Pivot row variable)

S2 row is up-dated as follows:

Page 66
 Old Row (Corresponding Pivot Updated corresponding = New S 2 raw

Element - column element x Pivot row element Element

250 - ( 50 x 2.8571) = 107.145

50 - (50 x 1) = 0

100 - (50 x 0.5714 = 71.43

0- (50 x 0.0029) = -0.145

1- (50 x 0) =1

0- (50 x 0) =0

S3 row is similarly updated:

Old Row (Corresponding Pivot Updated corresponding = New S 2 raw

Element - column element x Pivot row element element

1800 - (550 x 2.8571) = 228.595

550 - (550 x 1) = 0

600 - (550 x 0.5714) = 285.73

0- (550 x 0.0029) = -1.595

0- (550 x 0) =0

1- (550 x 0) =1

Page 67
 Complete 2nd tableau

Cj Basic Act. Birr 150 125 0 0 0

Qty.
Birr x1 x2 S1 S2 S3

150 x1 2.857 1 0.5714 0.0029 0 0

0 S2 107.145 0 71.43 -0.145 1 0

0 S3 228.595 0 285.73 1.595 0 1

- 428.55 150 85.71 0.435 0 0

- -- 0 39.29 -0.435 0 0

Now perform to get row values.

The positive value of 39.29 in ⇒ it is not the optimal solution hence, once again
pivoting is required.

Developing 3rd tableau

Now, pivot column x2 (Largest value of ), Pivot row = S3

Pivot element = 285.73

Page 68
Updating Pivot row (S3; Old row element ÷ Pivot number)

Cj Basic Birr 150 125 0 0 0

Activities Qty.
Birr x1 x2 S1 S2 S3

150 x1 2.857 1 0.5714 0.0029 0 0

0 S2 107.145 0 71.43 -0.145 1 0

Leaving
0 S3 228.595 0 285.73 1.595 0 1 variable

- 428.55 150 85.71 0.435 0 0

- -- 0 39.29 -0.435 0 0

Entering
variable
rd
Completed 3 Tableau

Cj Basic Activities Birr Qty. 150 125 0 0 0

Birr x1 x2 S1 S2 S3

150 x1 2.4 1 0 0.006 0 -0.002

0 S2 50 0 0 0.225 1 -0.25

125 X2 0.8 0 1 -0.0056 0 0.0035

- 460 150 125 0.02 0 0.1375

- -- 0 0 -0.02 0 -0.1375

Page 69
Note

Since no positive co-efficient exists in the C1 – z1 row, this is the optimal solution.

X1 = 2.4 X2 = 0.8

Page 70
 Z1= 460.

Example 2
X Ltd. Produces two products p1, p2 having profit of Rs. 4 $ Rs. 3 each p1, p2 require 4 hrs. & 2
hours of machining respectively, the total available machining time is 10 hours. P 1, p2 consume 2
units & 8/3 units of raw material respectively subject to a total of maximum 8 units. Any no. of
p2 j can be produced & sold but the no. of p1 must not be more than 6 Formulate as a (P model &
solve by the simplex method.)

Page 71
Page 72
 (Birr) Basic activities Qty. 4 3 0 0 0 Min ratio
Qty./ x1
Birr

0 S1 10 4 2 1 0 0 10/4= 2.5

0 S2 8 2 8/3 0 1 0 8/2= 4

0 S3 6 1 0 0 0 1 6/1= 6

0 0 0 0 0 0

4 3 0 0 0

Pivot Column = x1 because in the raw x1 have the highest value.

Pivot Row =S1 it have the lowest contribution (2.5)

Pivot Element = 4 the intersection of pivot raw and pivot column

Up-dating S2 row Updating row Updating raw

Qty.4

X1=4

X2=4× =2

S1=4×

S2=0

Page 73
 S3=0

Second tableau:

(Birr) Basic activities Qty. 4 3 0 0 0 Min ratio

Qty./ x1
Birr

4 x1 5/2 1 ½ -1/2 0 0 5/2÷1/2=5

0 S2 3 0
5/3 1/4 1 0 3÷5/3= 9/5

0 S3 7/2 0 -1/2 1 1 7/2÷-1/2= -7

10 4 2 -1/4 1 0

0 1 1 1 0

Pivot row = s2 the smallest value in the min ratio column (9/5). Don‟t take negative and
zero value.

Updating pivot row:

3÷5/3=9/5, 0, 1, -1/2÷5/3=-3/10, 1/5÷3=3/5, 0

Up-dating x1 row Updating row Updating raw

Qty.4 =11.6

Page 74
 3rd Tableau
(Birr) Basic activities Qty. 4 3 0 0 0

Birr

0 x1 8/5 1 0 - 2/5 -3/10

1/2

3 x2 9/5 0 1 ¼ - 3/5
3/10

4 S3 22/5 0 0 -2/5 3/10

59/5 4 3 - 7/10 3/5

1/4

0 0 1 - -3/5
7/10

There are no positive values in row, optional solution is reached.

Hence X1 = 8/5, X2 =9/5 & max. = 59/5 is the answer.

Page 75
Example 3:

Solve the problem using the simplex approach

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 (linear programming problem) 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.

Page 76
Let that, s2 and s3 be unused labor, machine and marketing hours, respectively.

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

Subject to:

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.
==> In constructing the initial simplex tableau, the search for of the optimal solution
begins at the origin. Indicating that nothing can be produced;
Thus, first assumption, No production implies that x1 =0 and x2=0

==> ==>

– Unused labor hours

==>

Page 77
 – Unused Marketing hours.

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.

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

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

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. Dear learners alternatively you may solve LP
simplex method by using the following method (you may solve the problem by using the
following table arrangement).

Page 78
 Initial simplex tableau

Slack variables

quantity column
variables column
Basic or Solution

Real or decision
variable column

columns
unit column

Solution
Profit per

Cj 300 250 0 0 0
Profit per unit

SV X1 X2 S1 S2 S3 Q Row

0 S1 2 1 1 0 0 40 R1

Constraint
0 S2 1 3 0 1 0 45 R2
equation
0 S3 1 0 0 0 1 12 rows
R3

Gross Profit row

Zj 0 0 0 0 0 0
Net Profit row
Cj - Zj 300 250 0 0 0 /Indicator row/

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

Note:

The entering variable is the variable that has the most positive value in the 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

Page 79
==> 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) or min ratio =

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 column
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)

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

Page 80
 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-2R2

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
R’’1=R’1-R’2

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

R’’2=R2/3

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

Zj 300 250 0 250/3 650/3 6350

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

Since all the optimal solution is reached at.

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

Page 81
 2.8.4. 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):
 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)==> 2x1+x2- s = 40 ==>2(0)+0-s = 20

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

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

Page 82
  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:

Type of constraint To put into standard form

< --------------------------------------------- Add a slack variable

= ---------------------------------------------Add an artificial variable

> ---------------------- Subtract a surplus variable and add a slack variable

[Link]. Big M-method /Charnes Penalty Method/

The Big-M 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 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:

-Here –M is assigned 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 .

f. Solution is optimal when there is no negative value of .(For

minimization case)

Page 83
Example:

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 tableaus

The initial basic feasible solution is obtained by setting x 1= 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

RR (min
M A1 20 15 -1 0 1 0 100
ratio)

M A2 2 3 0 -1 0 1 15 100/20=5

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

15/2=7.5

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

X1 is entering variable because in the row X1 have the highest negative value. And

A1 is leaving or outgoing variable because the RR is lowest positive in the A1 row.

Page 84
 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

3rd Simplex Tableau

Cj 25 30 0 0

SV X1 X2 S1 S2 Q

25 X1 1 0 -1/10 1/2 5/2 R’’1=R’1-3/4 R’’2

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

R’’2=R’2/3/2
Zj 25 30 -1/2 -15/2 162.5

Cj - Z j 0 0 1/2 15/2

==>Optimal solution is reached

X1=5/2

X2=10/3 and Minimum 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:

Page 85
 2x1+4x2 < 12

2x1+ 2x2 = 10

5x1+ 2x2 > 10

x1, x2 >0

Solution
Minimize 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
6
0 S1 2 4 1 0 0 0 12 5

M A1 2 2 0 0 1 0 10
2

M 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

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

Page 86
 3rd simplex tableau

Cj 5 3 0 0 M

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

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

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

Type equation here.

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 - Z j 0 0 1 0

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

Exercise
Find the optimal solution using Simplex method

1.

2.

Page 87
2.8.5. Special Cases in Simplex Method
1. Mixed constraints
Example

Max Z=6x1 +8x2

Subject to:

x2 < 4

x1+ x2 = 9

6x1+ 2x2 >24

x1, x2 >0

 Standard form

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

Page 88
Answer: At the 4th tableau: X1 =5, X2 =4 , S3 =14 and Maximize Z=62

Note:

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 Or Tie for entering variables

In order to break this tie, the selection for the key column (entering variable) can be made
arbitrary. However; the number of solution can be minimized by adopting the following
rules:

1. If there is a tie between two decision variables, then the selection can be made
arbitrary.
2. If there is a tie between a decision variable and a slack (or surplus) variable, then
select the decision variable to enter into basis first.
3. If there is a tie between slack or surplus variable, then selection can be made
arbitrary.

3. Alternate Optimal Solutions

If a non- basic variable corresponding to which =0 the problem have multiple

optimal solution.

Let us solve a small example:

Example1

As before, we add slacks, and we solve by the Simplex method, using tableau representation.

Max Z =

Subject to:

Write it in standard form

As before, we add slacks , and , and we solve by
the simplex method, using tableau representation.

Max Z = + -

Subject to:

Page 89
The optimal solution for this LP problem is presented in the following table

6 4 0 0 0 RHS

BV

0 0 5/3 1 -2/3 0 14

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

6 1 2/3 0 1/3 0 8

6 4 0 2 0 48

0 0 0 -2 0

The optimal solution is x1=8, x2=0, s1=14, and s3= 5 and max Z=48

But the row shows a value zero corresponding to a non basic variable X 2. Thus

an alternative optimal solution can also be obtained by entering variable X 2 in to the basis
and removing S1 from the basis.

Alternative solution

6 4 0 0 0 RHS

BV

0 0 1 3/5 -2/3 0 42/5

0 0 0 1/5 1/5 1 39/5

6 1 0 -2/5 3/5 0 12/5

6 4 0 2 0 48

0 0 0 -2 0

The optimal solution is x1=12/5, x2=42/5, s1=0, and s3= 39/5 and max Z=48

Page 90
 3. Unbounded solution
In maximization LP problem, if

for a column not in the basis and all entries in this column are negative, then for
determining key row, we have to calculate minimum ration corresponding to each basic
variable have negative or zero value in the denominator.

Negative value in denominator cannot be considered, as it would indicate the entry of a

non-basic variable in the basis with a negative value (an infeasible solution will occur). A
zero value in the denominator would result a value of + . This implies that the entering
variable could be increased indefinitely with any of the current basic variables being
removed from the basis.

Example solve the following LP problem

Maximize Z=

Subject to

add slack , and , and we solve by the simplex method,

using tableau representation.

Maximize Z= +
Subject to

The initial solution to this problem is presented below

3 5 0 0 0 -M RHS Min
ratio
BV

0 1 -2 1 0 0 0 6 ___

0 1 0 0 1 0 0 10 ___

-M 0 1 0 0 -1 1 1 1

0 -M 0 0 M -M 48

3 5+M 0 0 -M 0

Page 91
Variable X2 enter in to the basis and variable A1 leaves the basis

3 5 0 0 0 -M RHS Min
ratio
BV

0 1 -2 1 0 0 0 6 ___

0 1 0 0 1 0 0 10 ___

-M 0 1 0 0 -1 1 1 1

0 -M 0 0 M -M -M

3 5+M 0 0 -M 0

Second table

3 5 0 0 0 -M RHS Min
ratio
BV

0 1 0 1 0 -2 2 6 ___

0 1 0 0 1 0 0 10 ___

5 0 1 0 0 -1 1 1 1

0 5 0 0 -5 5 5

3 0 0 0 5 -M-5

Variable s3 should inter to the basis but it may be noted that coefficient in the S3 column
ar all negative or zero. This indicates that S 3 cannot be entered in to the basis. However,
the value of S3 can be increased infinitely without removing any one of the basic variable.

Infeasible solution
In final simplex table if at least one artificial variable appear with a positive value, no
feasible solution exists, because it is not possible to remove such an artificial variable
from the basis using the simplex algorithm.

Example solving the following LPP

Max Z =

Subject to:

Page 92
By adding slack, surplus and artificial variable, the LPP becomes

Max Z = + -

Subject to:

The second table of the solution shows

6 4 0 0 -M RHS

BV

4 1 1 1 0 0 5

-M -1 0 -1 -1 1 3

4+M 4 4+M M -M 20-3M

2-M 0 -4-M -M 0

Since the the solution is optimal. But the solution not feasible for the given

problem since it has X1=0, X2=5 (recall that in the second constraint X2 ≥ 8). The fact
that artificial variable A1 =3 is in the solution also indicates that the final solution violates
the second constraint (X2 ≥ 8) by 3 unites.

2.8. Duality in linear programming- Introduction

For every LP formulation there exists another unique linear programming formulation
called the 'Dual' (the original formulation is called the 'Primal'). The - Dual formulation
can be derived from the same data from which the primal was formulated. The Dual
formulated can be solved in the same manner in which the Primal is solved since the Dual
is also a LP formulation.

The Dual can be considered as the 'inverse' of the Primal in every respect.
The columns coefficients in the Primal constrain become the row coefficients in
the Dual constraints.
The coefficients in the Primal objective function become the right hand side
constraints in the Dual constraints.
The column of constants on the right hand side of the Primal constraints becomes
the row of coefficients of the dual objective function.
The 'directions of the inequalities are reversed.
If the primal objective function is a 'Maximization' function then the dual
objective function is a 'Minimization' function and vice-versa.

Page 93
The concept of duality is very much useful to obtain additional information about the
variation in the optimal solution when certain changes are effected in the constraint
coefficient, resource availabilities and objective function coefficients. This is termed as
post optimality or sensitivity analysis.

Note:

 The dual contains economic information useful to management, and it may also be
easier to solve, in terms of less computation, than the primal problem.
 Corresponding to every LPP, there is another LPP.
 The given problem is called the primal.
 The related problem to the given problem is known as the dual.
 The dual of a dual is the primal
 If the primal has optimal solution ,the dual will have optimal solution
 If the primal has no optimal solution, the dual will not have optimal solution.
 Whether we follow the dual or primal system, the optimal solution will remain
equal.

Table

Primal-Dual Relationship

Primal Dual
Objective is minimization Objective is maximization and vice versal

> type constraints < type constraints

No of columns No of rows

No of rows No of columns

No of decision variables No of constraints

No of constraints No of decision variables

Coefficient of Object function Right hand side (RHS) value

RHS value Coefficient of Object function

Page 94
 And the relationship also presented as follow by using chart

c x

Subject to subject to

Duality Advantage

1. The dual form provides an alternative form

2. The dual reduces the computational difficulties associated with some formulation

3. The dual provides an important economic interpretation concerning the value of

scars resources used.

Dual Formation

Following are the steps adopted to convert primal problem into its dual.

Step1. For each constraint in primal problem there is an associated variable in dual
problem.

Step2. The elements of right hand side of the constraints will be taken as the co-
efficient of the objective function in the dual problem.

Step3. If the primal problem is maximization, then its dual problem will be
minimization and vice versa.

Step4. The inequalities of constraints should be interchanged from ≥ to ≤ and vice versa
and the variables in both the problems and non-negative.

Step5. The rows of primal problem are changed to columns in the dual problem. In other
words the matrix A of the primal problem will be changed to its transpose (A) for the
dual problem.

Step6. The co-efficient of the objective function will be taken the right hand side of the
constraints of the dual problem.

Page 95
 Problems and Solutions

An example will clarify the concept basis. Consider the following 'Primal' LP formulation

Example 1

Mathematical formulation the primal and the dual linear programming problems of the
given problem are

Primal problem The 'Dual' formulation for this problem

would be

Note the following:

1. The column coefficient in the Primal constraint namely (2,2) and (3,1) have become the
row co-efficient in the Dual constraints.
2. The co-efficient of the Primal objective function namely, 12 and 10 have become the
constants in the right hand side of the Dual constraints.
3. The constants of the Primal constraints, namely 18 and 14, have become the coefficient in
the Dual objective function.
4. The directions of the inequalities have been reserved. The Primal constraints have the in
equalities of ≤; while the Dual constraints have the inequalities of ≥.
5. While the Primal is a 'Maximization' problem the Dual is a 'Minimization' problem

Example: 2

Write the duals to the following problems

a. Maximize Z=5x1+6x2

Subject to:

2x1+3x2 < 3000 (Labor constraint)

5x1 + 7x2 < 1000 (Machine constraint)

x1 + x2 < 5000 (Market constraint)

Page 96
 x1, x2 > 0

Solution

Represent primal in the conventional table as follows

Dual variables x1 x2 Constraints

u1 2 3 < 3000

u2 5 7 < 1000

u3 1 1 < 500

Maximize Z 5 6

By referring the above table, dual for this can be stated as:

Note:

1. For maximizing, all constraints must be brought to “<” form

2. For minimizing, all constraints must be brought to “>” form
3. If they are not, use multiplication factor -1
4. “=” is an intersection of “>” and “< “

Example3.

A firm manufactures two products A and B on machine I and II as shown below:

_____________________________________________________________________

Machine Product Available Hours

A B

I 30 20 300

II 5 10 110

Profit/unit ($) 6 8

The total time available is 300hours and 110hours on machine I and II respectively
.Product A and B contribute $6 and $8 per unit respectively.

Page 97
i. Formulate the LPP model for the primal and determine the optimal solution using simplex
method.
ii. Formulate the LPP model for the dual and determine the optimal solution from the final
primal simplex tableau

Solution

Let X1=No of units of product A produced

X2=No of units of product B produced

The final simplex tableau is:

Cj 6 8 0 0
SV X1 X2 S1 S2 Q

6 X1 1 0 1/20 - 4
1/10
8 X2 0 1 -1/40 9
3/20
6 8 -1/10
Zj 96
6/10

0 0 -1/10 -
Cj - Zj
6/10

The optimal solution is:

X1=4 units of product A produced

X2=9 units of product B produced and Maximize Z= $96

ii. Let u1=Cost of one hour on machine I
u2=Cost of one hour on machine II

Page 98
NOTE:

The value in the Cj - Zj row under columns of the slack /surplus variables with change in
sign give directly the optimal values of the dual/primal basic variables.

Therefore,

Note: The column s1 corresponds to u1 and the column s2 corresponds to u2

u1=-$(-1/10) per hr on machine I

u2=-$(-6/10) per hr on machine II

Maximize Z=Minimize Z*=$96(Total minimum cost)

Note: The dual variables uj are also called as the shadow prices

Exercise1.

Maximize Z= 300X1+ 250X2

Subject to:

2 X1+ X2 <40

X1+ 3X2 <45

X1 <12

X1 , X2 > 0

The final primal solution is:

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

Zj 300 250 0 250/3 650/3 6350

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

Required:

I. What are the solution of the dual variables (i.e. Shadow prices) u1, u2 and u3?

Page 99
 II. What is the optimal dual cost?
Solution:

I. Note: The column s1 corresponds to u1, s2 to u2 and s3 to u3.

Therefore, u1=0, u2 =250/3 and u3=650/3

III. Minimize Z*=$6350

3.9. Sensitivity Analysis

Sensitivity Analysis is concerned with the study of „Sensitivity „of the optimal solution of
an LPP with discretion variables (changes) in parameters .The degree of sensitivity of the
solution due to those variations can range from no change at all to a substantial change in
the optimal solution of the given LPP. Thus, insensitivity analysis, we determine the
range over which the LP model parameters can change without affecting the current
optimal solution. The process of studying the sensitivity of the optimal solution of an
LPP is called post-optimal analysis.

The two sensitivity analysis approaches are:

I. Trial and error approach and

II. Analytical approach

4.1.1. Analytical approach

Five types of discrete changes in the original LP model may be investigated during the
sensitivity analysis:

A. Changes of the coefficients of the objective function (cj)

B. Changes of the RHS Quantity( bj)
C. Changes of the input-output coefficient
D. Add/delete constraints
E. The addition of a new variable to the problem

A. Changes of the coefficients of the objective function (cj)

Decision variables can be:

i. Basic (in the solution)

ii. Non-basic (out-of the solution)

Page 100
 Note:

Instead of resolving the entire problem as a new problem with new parameters, we may
take the original optimal solution table as an initial solution table for the purpose of
knowing ranges both lower and upper within which a parameter may assume value.

a. Range for the coefficients of basic decision variables

The range of optimality is the range over which a basic decision variable coefficient in
the objective function can change without changing the optimal solution mix. However,
this change will change only the optimal value of the objective function.

Example:

Max.Z=5x1 +4.5x2 +x3

Subject to:

15 x1+15.8x2 < 150

5x1+6.4x2+15x3 < 77

2.8x2+11.8x3 < 36,

The optimal tableau for this solution is:

Cj 5 4.5 1 0 0 0

SV X1 X2 X3 S1 S2 S3 Q

5 X1 1 1.053 0 0.067 0 0 10

1 X3 0 0.67 1 -0.022 0.067 0 1.8

0 S3 0 1.924 0 0.258 -0.773 1 15.12

Zj 5 5.342 1 0.311 0.067 0 51.8
Cj - Zj 0 -0.842 0 -0.311 -0.067 0

Determine the range of optimality for the coefficients of the basic-decision variables.

Solution:

Analysis of basic decision variables

The analysis will be conducted on products on X1 and X3 which are in the basic solution.
Divide each Cj - Zj row entry for variables not in the solution (for instance, by X2, S1 and
S2 values) by the associated variable aij from X1or X3 row.

I. Analysis of X1
Steps:

Page 101
 a. Take the Cj - Zj row of the optimal solution of the non-basic variables
b. Take the X1 row of the non-basic variables

c. Cj - Zj row
X1 row

X2 S1 S2 Non-basic variables

Cj - Zj row -0.842 -0.311 -0.067

X1 row 1.053 0.067 0

Cj - Zj row -0.8 -4.64 -∞

X1 row

X2 S1 S2 Non-basic variables

Cj - Zj row -0.842 -0.311 -0.067

X3 row 0.67 -0.022 0.067

Cj - Zj row
-1.26 14.13 -1
X1 row

 Upper Limit

The smallest positive number in the Cj - Zj row tells how much the profit X1 of X1 can
be increased before the solution is changed.

Upper Limit= Cj (for X1) +the smallest positive value of Cj - Zj row

=5+∞=∞ X1 row

Note: Cj (for X1) =5(Look in the OF of the LP problem)

 Lower Limit

The largest negative number closest (negative amount closest to 0)

Lower Limit= Cj (for X1 )+The largest negative value of Cj - Zj row

=5+ (-0.8)= 4.2 X1 row

Therefore, the range of optimality for the coefficient of X1 is 4.2< Cj (for X1) < ∞ (The
coefficient of X1 in the objective function can change between 4.2 and ∞ without changing
the optimal solution mix X1=10, X3=1.8 and S3=15.12)

II. Analysis of X3

 Upper Limit= Cj (for X3 )+The smallest positive value of Cj - Zj row

Page 102
 =1+ (-1) =0 X1 row

Note: Cj (for X3) =5(Look in the OF of the LP problem)

 Lower Limit= Cj (for X3 )+The largest negative value of Cj - Zj row

=1+ (-14.13) = 15.13 X1 row

Therefore, the range of optimality for the coefficient of X3 is 0 < Cj (for X3) < 15.13 (The
coefficient of X3 in the objective function can change between 0 and 15.13 without changing the
optimal solution mix X1=10, X3=1.8 and S3=15.12).However, this change will change only the
optimal value of the objective function ([Link] will change)

Exercise:

Max.Z=50x1 +120x2

Subject to:

2 x1+4x2 < 80

3x1+x2< 60

x1, x2 > 0

Determine the range of optimality for the coefficient of the basic variables.

Optimal Solution

Cj
SV X1 X2 S1 S2 Q

5 X1 1/2 1 1/4 0 20
0 S2 5/2 0 -1/4 1 40

Zj 60 120 30 0 $2,400

$-10 $0 $-30
Cj - Zj
$0

Ans: The range of optimality for X2’s profit coefficient is: $100 < Cj (for X2) < ∞

b. The range for the non-basic variables

If there is a variable Cj, not participating in the optimal basis, then, in order for the
variable to be included in the optimal solution, its coefficient in the objective function
will have to change from the existing Cj to a new level Cj(new).

Cj(new)> Zj

Page 103
 The range of insignificance is the range over which Cj rates for non-basic variables can
vary without causing a change in the optimal solution mix (variable) is called the range of
insignificance.

Example:

Max.Z=5x1 +4.5x2 +x3

Subject to:

15 x1+15.8x2 < 150

5x1+6.4x2+15x3 < 77

2.8x2+11.8x3 < 36

x1, x2 , x3 > 0

The optimal tableau for this solution is:

Cj 5 4.5 1 0 0 0

SV X1 X2 X3 S1 S2 S3 Q

5 X1 1 1.053 0 0.067 0 0 10

1 X3 0 0.67 1 -0.022 0.067 0 1.8

0 S3 0 1.924 0 0.258 -0.773 1 15.12

Zj 5 5.342 1 0.311 0.067 0 51.8

Cj - Zj 0 -0.842 0 -0.311 -0.067 0

Calculate the range of insignificance for the coefficient of non-basic variable(X2)

Solution

Cj(for X2)=4.5 and Zj( for X2) =5.342

Cj(new for X2)>5.342==> Cj(new for X2).If the profit contribution of X2 is greater than
5.342,then X2 will be included in the solution.

Thus, ∞< Cj(new for X2)< 5.342 is the range of insignificance for X2.

Cj (new for X2) can vary with in the given range without causing a change in the optimal
solution mix(X1=10, X1=0, X3=1.8, S1= S2=0 and S3=15.12).

B. Change in the Right Hand—Side Quantity (RHS)

Or

Page 104
 Change in the availability of resource (Capacity) (bj)

 Shadow prices:

==>How much should a firm be willing to pay to make additional resources

available?

Shadow prices signify the change in the optimal value of the objective function for 1 unit
increases in the value of the RHS of the constraint that represent the availability of scarce
resources.

The negative of the number of Cj - Zj row in its slack variable columns provide as with
shadow prices. Or: shadow prices are found in the Zj row of the final simplex tableau in
the slack variable columns.

 RHS ranging is the range over which shadow prices remain valid.

Example:

Max.Z=3x1+4x2

Subject to:

3 x1+5x2 < 15

2x1 + x2 < 8

x2 < 2

x1, x2 > 0

The optimal tableau is given as:

Cj 3 4 0 0 0

SV X1 X2 S1 S2 S3 Q

3 X1 1 0 -0.143 0.714 0 3.57

0 S3 0 0 -0.286 0.428 1 1.143

4 X2 0 1 0.286 -0.428 0 0.857

Cj - Zj 0 0 -0.714 -0.428 0

Required:

1. Determine the shadow price for each constraint

2. Determine the RHS ranges over which the shadow prices are valid

Page 105
 Analysis of the 1st constraint (S1)

Q S1 Q/ S1

3.57 -0.143 24.96

1.143
- -0.286 3.99

0.857
- 0.286 3.00

Lower Limit=bj-the smallest positive number in the Q/ Sj column

Upper Limit=bj-the largest negative number in the Q/ Sj column

Lower Limit=b1-the smallest positive number in the Q/ S1column

=15-3=12

Upper Limit=b1-the largest negative number in the Q/ S1 column

=15-(-3.99) =18.99

Therefore, 12< b1< 18.99 (The range of resource 1 over which the shadow price $0.714
per unit is valid).

 Analysis of the 2nd constraint (S2)

Q S2 Q/ S2
3.57 0.714 5
1.143 0.428 2.67
0.857 -0.428 -2

Lower Limit=b2-the smallest positive number in the Q/ S2 column

=8-(2.67)=5.33

Upper Limit=b2-the largest negative number in the Q/ S2 column

=8-(-2) =10

Therefore, 5.33< b1< 10 (The range of resource 2 over which the shadow price $0.428
per unit is valid).

 Analysis of the 3rd constraint (S3)

Q S3 Q/ S3

Page 106
 3.57 0 -
-
1.143 1 1.143

0.857 0 -

Lower Limit=b3-the smallest positive

number in the Q/ S3 column

=2-(1.143)= 0.857

Upper Limit=b3-the largest negative number in the Q/ S3 column

=2-(-∞) =∞

Therefore, 0.857< b3< ∞ (The range of resource 3 over which the shadow price $0 per
unit is valid).

Exercise

1. Solve the following LPP using simplex method. A firm that manufactures both lawn
mowers and snow blowers:

X1 =the number of lawn mowers

X2 =the number of snow blowers

Max.Z=30x1+80x2

Subject to:

2 x1+4x2 < 1000 Labor hours available

6x1 + 2x2 < 1,200lb of steel available

x2 < 20 snow blower engine available

x1, x2 > 0

a. What is the best product mix? What is the optimal profit?

Answer:

x1=100, x2=200 and profit =$19,000

b. What are the shadow prices? When the optimal solution has been reached, which resource
has the highest marginal value?

Answer:

The shadow price for 1 additional labor=$15

Page 107
 The shadow price for 1 additional pound of steel=0

The shadow price for 1 additional snow blowers engine made available =$20

Thus, snow blower engine have the highest marginal value at the optimal solution.

c. Over what range in each of the RHS values are these shadows valid?

Answer:

The shadow price for labor hours is valid from 800 hours to 1,066.66 hours

The shadow price for pounds of steel is valid from 1,000pounds up to an infinite number
of pounds. The shadow price for snow blower engines ranges from 180 engines up to 250
engines

d. What are the ranges over which the objective function coefficients can vary for each of the
two decision variables?

Answer:

Without changing the current solution mix, the profit coefficient for the mowers can
range from $0 to 40, while the coefficient for the blowers can range from $60 to infinity.

Chapter Summary

Linear Programming is a branch of mathematical programming which is designed to

solve optimization problems where all the constraints as well as the objectives are
expressed as linear function. It was developed by George B. Denting in 1940. Its earlier
application was solely related to the activities of the second' World War. However soon
its importance was recognized and it came to occupy a prominent place in the industry
and trade.

The basic steps in formulating a linear programming model are presented as follows:

Step I Identification of the decision variables. The decision variables (parameters)

having a bearing on the decision at hand shall first be identified, and then expressed or
determined in the form of linear algebraic functions or in equations.

Step II Identification of the constraints. All the constraints in the given problem which
restrict the operation of a firm at a given point of time must be identified in this stage.

Step III formulate the objective function. In the last stage, the objective which is
required to be optimized (i.e., maximized or memorized) must be dearly identified and
expressed in terms of the pre-defined decision variables.

Page 108
There are two types of finding a solution for Linear programming problems this are
Graphic solution and Simplex solution method.

The graphic solution procedure is one of the methods of solving two variable linear
programming problems. Steps in graphic solution method:-

Step I Defining the problem. Formulate the problem mathematically. Express it in terms
of several mathematical constraints & an objective function.

Step II Plot the constraints graphically. Each inequality in the constraint equation has to
be treated as an equation.

Step III Locate the solution space. Solution space or the feasible region is the graphical
area which satisfies all the constraints at the same time. Such a solution point (x, y)
always occurs at the corner Points of the feasible Region the feasible region is determined
as follows:

a. For "greater than" & "greater than or equal to" constraints, the feasible region or the
solution space is the area that lays above the constraint lines.
b. For" Less Then" &" Less than or equal to" constraint, the feasible region or the
solution space is the area that lays below the constraint lines.

Step IV Selecting the graphic solution technique. Select the appropriate graphic
technique to be used for generating the solution.

Some of the important terms commonly used in linear programming are:

Solution: Values of the decision variable satisfying the constraints of

a general linear programming model is known as the solution to that linear programming
model.
Feasible solution: Out of the total available solution a solution that also satisfies the non-
negativity restrictions of the linear programming problem is called a feasible solution.
Basic solution: For a set of simultaneous equations in Q unknowns (P, Q) a solution
obtained by setting (P - Q) of the variables equal to zero & solving the remaining P
equation in P unknowns is known as a basic solution. The variables which take zero
values at any solution are detained as non-basic variables & remaining are known as-
basic variables, often called basic solution.
Basic feasible solution: A feasible solution to a general linear programming problem
which is also basic solution is called a basic feasible solution.
Optimal feasible solution: Any basic feasible solution which optimizes (i.e. maximize
or minimizes) the objective function of a LP models is known as the optimal feasible
solution to that linear programming model.
Degenerate Solution: A basic solution to the system of equations is termed as
degenerate if one or more of the basic variables become equal to zero.

Page 109
The second method to find a solution for LPP is using the Simplex method. It is an
iterative or “step by step” method or repetitive algebraic approach that moves
automatically from one basic feasible solution to another basic feasible solution
improving the situation each time until the optimal solution is reached at.

The summery of the extra variable to be added in the given LP problem to convert it in to
standard form is given in the following table.

Page 110
 Chapter concept quiz

Part I: Multiple choice questions

1. Mathematical model of LPP is important because:

A. It helps in converting the verbal description and numerical idea in to mathematical
expression
B. Decision makers prefer to work with formal models
C. It captures the relevant relationship among decision factors
D. It enables the use of algebraic technique
2. Minimization of objective function in LP model means
A. Value occurs at allowable set of decisions
B. Lowest value is chosen among allowable decisions
C. Highest value is chosen among allowable decisions
D. Both A&B
3. Which of the following is not a characteristics of Linear programming model
A. Alternative course of action
B. Limited objective function
C. Limited amount of constraints
D. Work when all the information is known
E. Non negativity condition on the value of decision variables
F. All
4. Constraints in an LP model represents
A. Limitations D. All of the above
B. Requirements
C. Balancing limitations and
requirements
5. One of the following is not the distinguishing feature of an LP models
A. Relationship among all variables is linear
B. It has single objective and constraints
C. Value of decision variables is nonnegative
D. All except A
6. Each constraint in an LP model is expressed as an
A. Inequality with ≥ sign C. Equation with = sign
B. Inequality with ≤sign D. All of the above
7. LP is a?
A. Constrained optimization technique
B. Technique for economic allocation of limited resources
C. Mathematical technique
D. All
8. Which of the following is limitation of LP
A. Linear Relationship
B. Constant Value of objective & Constraint Equations.
C. No Scope for Fractional Value Solutions.

Page 111
 D. Degree of Complexity.
E. Multiplicity of Goals.
F. All
9. The role of artificial variable in the simplex table is?
A. To aid in finding an initial solution
B. To obtain optimal dual prices in the final simplex table
C. To start phases of simplex method
D. All
10. For a minimization problem, the objective function coefficient for an artificial
variable is?
A. –M C. Zero
B. +M D. None
11. A variable which does not appear in the basic variable column of simplex table
is ?
A. Never equal to zero C. Called a basic variable
B. Always equal to zero D. None

12. We must add artificial variable to write the standard form of LPP is?
A. Equality constraint C. Both A and B
B. For greater than constraint D. None
13. If a negative value appears in the RHS value then
A. The solution is optimal C. The solution is unbounded
B. The solution is infeasible D. All
14. If dual has an unbounded solution, primal has
A. No feasible solution C. feasible solution
B. unbounded solution D. None
15. the RHS constant of a constraint in a primal problem appears in the
corresponding dual as
A. a coefficient in the objective function
B. a RHS constant of constraint
C. an input- output coefficient
D. none
16. shadow price indicates how much one unit change in the resource value will
change the
A. optimality range of an objective function
B. optimal value of the objective function
C. value of basic variables in the optimal solution
D. none
17. the dual of a dual is
A. A primal C. Both A and B
B. A dual D. None
18. for any primal and its dual

Page 112
 A. optimal value of the objective function is same
B. primal will have an optimal solution if and only if dual does not too
C. both dual and primal cannot be infeasible
D. all of the above
19. to ensure best marginal increase in the objective function value, a resource
value may be increased whose shadow p[rise is comparatively
A. Large C. Neither A nor B
B. Small D. Both A and B
20. the entering variable in the sensitivity analysis of objective function coefficient
is always
A. decision variable
B. non basic variable
C. basic variable
D. slack variable
E. none

Page 113
 21. while performing sensitivity analysis, the upper bound infinity on the value of
the RHS of the constraint means that
A. there is slack in constraint
B. the constraint is redundant
C. the shadow price for that constraint is zero
D. None
Part II: Solve the following problems
1. Maximize .Z=10X1+15X2 2. Min.Z=3X1+2X2

Subject to: Subject to:

2X1+X2 < 26 5X1+X2 > 10

2X1+4X2< 56 X1 +X2 > 6

-X1+X2< 5 X1 + 4 X2 > 12

X1, X2 > 0 X1, X2 >0

3. A manufacturer produces two different models; X and Y, of the same product .The raw
materials r1 and r2 are required for production. At least 18 Kg of r1 and 12 Kg of r2 must
be used daily. Almost at most 34 hours of labor are to be utilized .2Kg of r1 are needed
for each model X and 1Kg of r1 for each model Y. For each model of X and Y, 1Kg of r2
is required. It takes 3 hours to manufacture a model X and 2 hours to manufacture a
model Y. The profit realized is $50 per unit from model X and $30 per unit from model
Y. How many units of each model should be produced to maximize the profit?
4. A manufacturing firm produces two machine parts P1 and P2 using milling and grinding
machines .The different machining times required for each part, the machining times
available on different machines and the profit on each machine part are as given below:

____________________________________________________________________

Page 114
 Manufacturing time Maximum time

Required (min) available per week (minimum)

Machine P1 P2

________________________________________________________________________

Lathe 10 5 25,000

Milling Machine 4 10 2000

Grinding Machine 1 1.5 450

Profit per unit ($) $50 $100

_____________________________________________________________________

Determine the number of pieces of P1 and P2 to be manufactured per week to maximize

profit.

5. Consider the following 'Primal' LP formulation

Maximize 12x1 + 10x 2
Subject to 2X1 + 3X2 ≤ 18
2X1 + X2 ≤ 14
X1 X21 ≥ 0
Formula the 'Dual' for this problem

Page 115
 CHAPTER THREE

TRANSPORTATION AND ASSIGNMENT MODEL

Introduction
All linear programming can be solved by the Simplex method. However due to their
specialized structure, certain classes of linear programming problems lend themselves to
solutions by other techniques that are computationally more efficient than the simplex
methods. These types of linear problems can be represented by the so called
transportation and assignment model. Let as first describe the transformation model and
the assignment model will be discussed later in this chapter.
3.1. Transportation model
Basic transportation problem was stated by F.L. Hitchcock in 1941, and later expanded
by T.C. Koopmans and W.W. Cooper. Several extensions of transportation model and
methods have been subsequently developed. The transportation problem is a particular
case of linear programming problem.
The structure of transportation problem involves a large number of shipping routes from
several supply origins to several demand destinations. The objective is to determine the
number of units which should be shipped from an origin a destination in order to satisfy
the required quantity of goods or services at each demand destination, within the limited
quantity of goods or services available at each supply origin, at the minimum
transportation cost and/or time.

The transportation algorithm discussed in this chapter is applied to minimize the total
cost of transporting a homogeneous commodity (product) from supply origin to demand
destination. However, it can also be applied to the maximization of some total value or
utility, for example, financial resources are distributed in such a way that the profitable
return is maximized. Note that the assumption of homogeneous commodity implies no
difference in commodity characteristics among origins.

Page 116
 3.1.1. Formulation of Transportation model (table)

In order to develop a model of transportation problem, it is necessary to know the

following information:

 The sources of supply (origin) which may include production facilities,

warehouses, or supply points, characterized by available capacities.
 The destinations which may include consumption facilities, warehouses or
demand points, characterized by required levels of demand.
 Supply quantity (capacity) of each origin which is stated in rows.
 Demand quantity of each destination, which is stated in column
 Unit transportation cost (in birr) for each route.
 The total quantity available for shipment is equal to the total quantity demanded

Example1.

A company has three production facilities S1, S2, and S3 with production capacity of 7,
9, and 18 units (in 100s) per week of product respectively. These units are to be shipped
to four ware houses D1, D2, D3, and D4 with requirement of 5, 8, 7 and 14 units (in100s)
per week respectively. The transportation costs in birr per unit between factories to
warehouses are given in the table below:

Source Ware houses (demand or requirements)

(Production facilities) D1 D2 D3 D4

Ware house1 (S1) 19 30 50 10

Ware house 2 (S2) 70 30 40 60

Ware house 3 (S3) 40 8 70 20

Required: formulate the transportation table (model)

Page 117
 Solution
The First step is identifying the information needed to formulate the transportation table.
Generally, three information are needed to formulate the transportation table: demand
(also called destination or requirement), supply (also called source or capacity), and unit
transportation cost. These in formations are arranged as follows:
* Data about supplies
Source (production facilities) supply (capacity)
S1 7

S2 9

S3 18

*data about demand

warehouses demand(requirement

D1 5

D2 8

D3 7

D4 14

*data about unit transportation cost

Source Warehouses (demand or requirements)
(Production facilities) D1 D2 D3 D4

Warehouse1 (S1) 19 30 50 10

Warehouse 2 (S2) 70 30 40 60

Warehouse 3 (S3) 40 8 70 20

Page 118
 The next step is formulating the transportation table.

To formulate the table, list the demand vertically (in column) and supply horizontally (in
rows). Thus, the production facilities (sources) are listed down the left side of the table,
and their respective supply‟s quantities are listed down the right side of the table. The
destinations (warehouses) are listed across the top of the table and their respective
demands are listed across the bottom of the table. The unit shipping costs are shown in
the upper right hand corner of each sell, which represent the shipping route.

The following table arranges the information in to a transportation table.

Transportation table

To D1 D2 D3 D4 Supply

From

S1 19 30 50 10 7

S2 70 30 40 60 9

S3 40 8 70 20 18

Demand 5 8 7 14 34
34

*Remark: when the total supply equals total demand, the problem is called balanced
transportation problem, otherwise an unbalanced transportation problem. The unbalanced
transportation problem can be made balanced by adding a dummy supply (row) or a
dummy demand (column) as the need arise. We will see this in detail later in this chapter.

Page 119
 3.1.2. Finding initial feasible solution

A solution to a transportation problem consists of quantities that are assigned to the

various routes (i.e. cells in the table). These values can range from zero, which implies
that no units will be shipped over that route, to a maximum that equals the smaller of two
quantities: the row (supply) and column (demand) totals.

Remark: the quantity shipped cannot exceed the available supply in rows, and it should
not exceed the amount of demand (column total). Such solution is a feasible solution. The
starting point of the transportation method is a feasible solution. A feasible solution is
one in which assignments are made in such a way that all supply and demand
requirements are satisfied.

In this section, we shall discuss the following three different methods to obtain an initial
solution:

 North- west corner method

 Least cost method, and
 Vogel‟s approximation (or penalty) method.

The initial solution obtained by any of the three methods must satisfy the following
conditions:

 The solution must be feasible i.e. it must satisfy all the supply and
demand constraints
 The number of occupied cell should equal one less than the sum of the
number of rows(m) and the number of columns(n)in a transportation table i.e. (m +
n) – 1. For example, in the case of a table with 3 rows and 3 columns, the number
of occupied cell should be: (3 +3) – 1 = 5 in order to be able to use the
transportation algorithm.

Any solution that satisfies the above conditions is called non degenerate basic feasible
solution, otherwise, degenerate solution.

Page 120
Dear student, now let as see the above three methods of finding initial feasible solution
one by one beginning with the NWCM.

A) North-West Corner Method (NWCM) of finding initial feasible solution

The north –west corner method is a systematic approach for developing an initial basic
feasible solution. Its chief advantages are that it is simple to use and easy to understand.
Its chief drawback is that it does not take transportation cost in to account. Consequently,
such solution may require much additional effort to obtain the optimal solution.

The north-west corner method gets its name because the starting point for the allocation
process is the upper left hand (North- West) corner of transportation table.

This method can be summarized as follows:

Step1. Start with the sell at the upper left (north-west) corner of the transportation table
and allocate as many units as possible to that cell. This will be the smaller of the row
supply and the column demand. Adjust the row and column quantities to reflect the
allocation.

Step2. - If allocation made in step 1 is equal to the supply available in the first row, then
move vertically down to the cell in the second row and first column.

If allocation made in step1 is equal to the demand of the first destination (in first
column), then move horizontally to the cell in the first brow and second column and
apply step 1 again for next allocation.

Step3. Continue the procedure step by step till an allocation is made in the south east
corner cell of the transportation table.

Example2. Let as return to Example1 transportation table and see how to find the initial
feasible solution using NWCM.

Page 121
 D1 D2 D3 D4 Supply

S1 19 30 50 10 7

S2 70 30 40 60 9

S3 40 8 70 20 18

Demand 5 8 7 14 34
34

Required: consider the above table and then find the initial basic feasible solution (total
transportation cost) using NWCM.

Solution

To find the initial basic feasible solution using NWCM, track the following steps.

1. Beginning in cell (S1, D1) which is the north-west corner cell in the given
transportation table. The value for row S1 (i.e.7) and column D1 (i.e.5) are
compared. The smaller of the two, i.e. 5 is assigned as the first allocation;
otherwise it will violate the feasibility condition. This means that 5 unit of
commodities are to be transported from production facility 1 (S1) to warehouse 1
(D1). However, this allocation leaves a supply of 2 (7-5 =2) units of commodity
at S1.
2. Staying in row S1, move horizontally to cell (S1, D2) where supply is now 2 and
demand is 8. Allocate 2 units to this cell, exhausting the supply of row S1 and
leave 6 units of demand inD2 column.
3. Staying in column D2, move down to cell S2 D2, where supply is now 9 and
demand is 6. Allocate 6 units to this cell, exhausting the demand in column D2
and leaving 3 units of supply in row S2.
4. Staying in row S2, move to cell (S2, D3) and allocate 3 units to this cell,
exhausting that row‟s supply and leaving 4 units in columnD3.

Page 122
 5. Staying in column D3, move down to cell (S3, D3) and allocate 4 units to this
cell, exhausting D3 columns and leaving 14 units of supply.
6. Staying in column S3 move to cell (S3, D4) and allocate 14 units to this cell,
exhausting both the rows and columns quantities.

D1 D2 D3 D4 Supply

S1 19 30 50 10 7

5 2

S2 70 30 40 60 9

6 3

S3 40 8 70 20 18

4 14

Demand 5 8 7 14 34
34

(NB: cells with bold quantity indicates the occupied cell)

No of occupied cell= m + n – 1 = 3+4 -1 =6, so the table is not degenerate solution.
The total transportation cost of the initial solution derived by the NWCM is obtained by
multiplying the quantity in the occupied cells with the corresponding unit costs and
adding. Thus,
Total transportation cost = 19 X5 = 95

30 X 2 = 60

30 X 6 = 180

40 X 3 = 120

70 X 4 = 280

20 X 14 = 280

Page 123
 Birr 1015

In terms of minimizing total transportation cost, this solution may or may not be optimal.
We shall make that determination very shortly under „test for optimality‟ section. At this
point, our target is simply computing basic initial feasible solution (i.e. total cost =1015).

B) Least Cost Method (LCM) of finding initial feasible solution

As noted earlier, the main drawback of the north –west corner method is that it does not
consider cell (route) costs in making the allocation. Consequently, if this allocation is
optimal, that can be attributed to chance rather than the method used. To overcome this
drawback, we can use the LCM (which consider the unit transportation cost) to find the
initial feasible solution.

This approach, also called the minimum –cost method, uses lowest cell as the basis for
selecting route. Generally, this method takes in to account the minimum unit cost of
transportation for obtaining initial solution and can be summarized as follows:

Step1. Select the cell with the lowest unit cost in the entire transportation table and
allocate as much unit as possible to this cell and eliminate (line out) that row or column
in which either supply or demand is exhausted.

 If both a row and column are satisfied simultaneously, only one may be crossed
out arbitrarily
 In case the smallest unit cost cell is not unique, then select the cell where
maximum allocation can be made.

Step2. after adjusting the supply and demand for all uncrossed –out rows and columns
repeat the procedure with the next lowest unit cost among the remaining rows and
columns of the transportation table and allocate a quantity to this cell that is equal to the
lower of the available supply of the row and the demand for the column and eliminate
(cross out) that row or column in which either demand or supply is exhausted.

Page 124
Step3. Repeat the procedure until the entire available supply at various sources and
demand at various destinations is satisfied. The solution obtained need to be non-
degenerate.

Example3

Taking data of the above example, the initial solution using LCM and total transportation
cost is calculated as follows:

 The cell with lowest unit cost is 8 at cell (S3, D2). The maximum units which we
can allocate to this cell are selected from (18 and 8) whichever is smallest.
Therefore, at this cell we must allocate 8. This meets the complete demand of D2
and leaves 10 units with S3. Thus, crossed out column D2.
 In the reduced table without column D2 (note: D2 cannot be used because it has
been crossed out), the next smallest unit transportation cost is 10 in cell (S1, D4).
The maximum unit which can be allocated to this cell can be 7(i.e. compare 14
and 7 and then assign the smallest unit). This exhausts the capacity of S1 and
leaves 7 units withD4 as unsatisfied demand. Thus, eliminate S1 row.
 The next smallest cost, without considering S1, is 20 units at cell (S3, D4). The
maximum allocation in this cell could be 7 units. This satisfies the entire demand
of D4 and leaves 3 units with S3 as remaining supply. Thus line out D4.
 The next smallest unit cost cell is not unique. That is, there are two cells (S2, D3)
and (S3, D1), having the same unit transportation cost of 40 birr. Allocate 7 units
in cell (S2, D3) first because it can accommodate more units as compared to cell
(S3, D1) and allocate 3 units (only supply left with S3) in cell (S3, D1). The
remaining demand of 2 units of D1 is fulfilled from S2. Since supply and demand
at each origin in destination is exhausted, the initial solution is arrived at. The
following table summarizes the discussion.

Page 125
 D1 D2 D3 D4 Supply

S1 19 30 50 10 7

S2 70 30 40 60 9

2 7

S3 40 8 70 20 18

3 8 7

Demand 5 8 7 14 34
34

Number of occupied cell =m + n –1 = (3+4 – 1) = 6 and the solution is not degenerated.

Total transportation cost = 7 X 10 = 70

70 X 2 = 140

40 X 7 = 280

40 X 3 = 120

8X8 = 64

20 X 7 = 140

Birr 814

C) Vogel’s approximation Method (VAM) of finding initial feasible solution

Vogel‟s approximation (penalty or regret) method is a heuristic method and is preferred

to the other two methods described above. In this method each allocation is made on the
bases of the opportunity (or penalty or extra) costs that would have been incurred if
allocation in certain cells with minimum unit transportation costs were missed. In this
method allocations are made so that the penalty cost is minimized. The advantage of this

Page 126
method is that it gives an initial solution which is nearer to an optimal solution or is the
optimal solution itself. In VAM method, we look for cells having lowest cost and next
lowest cost in each row and column.

The steps in VAM are as follows:

Step1. Calculate penalties for each row /column by taking the difference between the
smallest and next smallest unit transportation cost in the same row/column and note down
their difference. 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.

Step2. Select the row or column with the largest penalty (with maximum differences) and
allocate as much unit as possible in the cell having the least cost in the selected row or
column satisfying the rim condition. If there is a tie in the value of penalties, it can be
broken by selecting the cell where maximum allocation can be made.

Step3. Adjust the supply and demand and cross out the satisfied row or column and re-
draw the reduced matrix. If a row and column are satisfied simultaneously, only one of
them is crossed out and the remaining row or column is assigned a zero supply or
demand. Any row /column with zero supply or demand should not be used in computing
future penalties and hence should be eliminated.

Step4. Repeat step 1 to 3 until the entire available supply at various sources and demand
at various destinations are satisfied.

Example4

Taking data of the above example, the initial solution using VAM and total transportation
cost is calculated as follows:

 As shown in the following table, differences (penalty costs) for each row and
column have been calculated. In the first round, the maximum penalty, 22 occur
in column D2. Thus, the cell (S3, D2) having the least transportation cost 8 is
chosen for allocation. The maximum possible allocation in this cell is 8 (compare

Page 127
 demand i.e. 8 and supply i.e.18 and assign the smallest unit) and it satisfies
demand in column D2. Adjust the supply of S3 from 18 to 10 (18-8=10) and
cross out column D2.
 Calculate the new row and column penalties except for column D2 because its
demand has been satisfied. The penalties are:

- D1=21 (i.e. the smallest 19 subtracted from the next smallest 40 units)
- D3=10 (i.e. the smallest 40 subtracted from the next smallest 50 units)
- D4=10 (i.e. the smallest 10 subtracted from the next smallest 20 units)
- S1 = 9 (i.e. the smallest 10 subtracted from the next smallest 19 units)
- S2 =20 (i.e. the smallest 40 subtracted from the next smallest 60 units)
- S3 = 20(the smallest 20 subtracted from the next smallest 40 units)

NB: Column D2 should not be considered as it is eliminated (crossed out).

 The second round allocation is made in column D1 with target penalty 21 in the
same way as in the first round as shown in cell (S1, D1) of the table.
 In the third round, the maximum penalty 50 occurs at S3. The maximum possible
allocation of 10 units is made in cell (S3, D4) having least transportation cost 20 as
shown in the table.
 The process is continued with new allocations till a complete solution is obtained.
The initial solution using VAM is in the table.

D1 D2 D3 D4 Supply Row difference

S1 19 30 50 10 7 9 9 40 40

5 2

S2 70 30 40 60 9 10 20 20 20

7 2

S3 40 8 70 20 18 12 20 50 --

Page 128
 8 10

Demand 5 8 7 14 34
34

column 21 22 10 10
difference
21 -- 10 10

-- -- 10 10

-- -- 10 50

Number of occupied cell =m + n – 1= 3 + 4 – 1 = 6 and solution is not degenerated

Total transportation cost = 19 X5 = 95

10 X 2 = 20

40 X 7 = 280

60 X 2 = 120

8X8 = 64

20 X 10 = 200

Birr 779

1.1.3. Evaluating Initial Feasible Solutions for Optimality

Once the initial solution is obtained, the next step is to check its optimality. An optimal
solution is one where there is no other set of transportation routes (allocations) that will
further reduce the total transportation cost.

The test of optimality for initial feasible solution involves a cost evaluations of
unoccupied or empty cell (i.e. routes to which no units have been allocated) to see if an
improved solution is possible. Thus, we have to evaluate each unoccupied cell in the
transportation table in terms of an opportunity of reducing total transportation cost.

Page 129
In this chapter, we shall consider two methods for cell evaluation: the stepping stone
method and the MODI method.

Mr. A. Charnes developed stepping stone methods for solving transportation problems.
Subsequent improvements led to the developments of MODI methods in 1955. Stepping
stone methods, even though now superseded by MODI method, is taken up for discussion
in this section, for better understanding the logic behind its solutions. Now let as see first
the stepping stone method and later we will see the MODI in detail.

A) Evaluation using stepping stone method

The stepping stone method involves tracing a series of closed paths in the transportation
table, using one such path for each empty cell. The name stepping stone relates to an
analogy of crossing a pond or scream by moving from stone to stone; in the case of
transportation problem the stones are the completed cell.

The steps for evaluating the optimality of initial feasible solution using stepping stone
method include the following:

Step1. Determine improvement index for each unoccupied cell.

 Trace a „closed path‟ that begins at the unoccupied cell, and moves alternately in
horizontal and vertical directions pivoting only on occupied cells and terminates
on the unoccupied cells.
 A „+‟ sign is assigned to the unoccupied cell, and succeeding corner points on the
path are alternately assigned a minus sign „–‟ and „+‟ sign.
 The plus and minus sign indicates the necessary adjustments for satisfying the
row and column requirements. See the following example.

Example 5

Now let as take the initial feasible solutions found using LCM in Example 5 and test for
optimality using the stepping stone method.

Page 130
 A B C Supply

S1 5 7 (-)9 500

(+) 500

S2 6 2 4 600

500 100

S3 (-)3 9 (+)5 800

600 200

Demand 600 500 800 1900

1900

In this example an unoccupied cells includes:

(S1, A), (S1, B), (S2, A) (S3, B),

The index for each unoccupied cell can be determined by tracing a closed path.

Unoccupied cell Closed path with alternate „+‟ and „–‟ sign

S1, A +5 – 9 + 5 – 3 = -2

S1, B +7 – 9 +4 – 2 = 0

S2, A +6 – 4 +5 – 3 = 4

S3, B +9 – 5 +4– 2 = 6

Step2. If a better solution exists, determine which cell should be occupied (entering
cell). For minimization problems, a better solution exists if there are any negative
improvement indices. An optimal solution has been found when all improvement indices

Page 131
are nonnegative (zero or positive). Once the optimal solution has been found, the
existence of one or more improvement indices at zero level indicates alternative optimal
solutions.

NB: If more than one negative index exists simultaneously, occupied (assign) to the cell
with largest negative number (i.e. largest number with minus sign). Based on the above
example, cell (S1, A) has negative indices (i.e.-2) indicating that total transportation cost
can be further reduced by 2Q (where Q is the number of units assigned to this cell).

Step3. Determine the departing cell and the number of units to assign the entering cell

The departing cell is identified by the smallest cell in a minus position on the closed path
for the entering cell. The entering cell is assigned the number of units previously given
the departing variable.

Based on the above example, the cells with minus signs are :( S1,C) & (S3 , A) with a
quantity of 500 unit and 600 units respectively.

The departing cell is the cell with the smallest quantity in a negative position.
Therefore, cell (S1, C) is the departing cell (since 500 is less than 600). Thus, the number
of unit assigned to the new entering cell (i.e.S1, A) is 500 units.

Step4. Develop the new solution, and return to step 1

The new solution can be determined by adding 500 units to the cell with + sign (i.e. cell
S1, A and S3, C) in the closed path and by deducting 500 from the cell with minus sign
(i.e. S1, C, and S3, A).

 Assigning the entering cell(S1,A) with 500units

 Adjust the supply side by subtract the 500 unit from cell (S1, C) i.e. 500-500 =0
 Adjust the demand side by adding 500 unit to cell (S3,C) i.e. 200+500 =700
 Adjust the supply side by deducting 500 unit from cell (S3, A) i.e. 600-500 =100
After these adjustments the occupied cells are:

Page 132
(S1, A), (S2, B), (S2, C), (S3, A), (S3, C). See the following table.

A B C Supply

S1 (+)5 7 (-)9 500

500

S2 6 2 4 600

500 100

S3 (-)3 9 (+)5 800

100 700

Demand 600 500 800 1900

1900

The optimum total transportation cost = 500 X5 = 2500

500 X 2 = 100
100 X 4 = 400
100 X 3 = 300
700 X5 = 3500
Birr 7700

To prove whether this figure is an optimal solution or not see the following. We stated
that total transportation cost can be reduced by 2Q where Q is the number of units
assigned to this cell. Now we identified that Q=500 units and the total transportation cost
reduction = 500X2= birr 1000

Therefore, the optimal total transportation cost = 8700-1000= birr 7700

Page 133
 B) Modified Distribution Method(MODI method)

Unlike stepping stone method, the MODI algorithm eliminates the need to trace closed
paths for each unoccupied cell. The MODI method of evaluating a transportation solution
for optimality involves the use of Index numbers that are established for the row and
columns. These are based on the unit cost of the occupied cells. The index number can be
used to obtain the cell evaluation for empty cells without the use of stepping stone-paths.
There is one index number for each column and one for each row.

The steps to evaluate unoccupied cells using MODI method are as follows:

Step1. For an initial basic feasible solution with m + n -1 occupied cells, calculate Ui for
rows(i= 1,2,3……m) and Vj for columns(j=1,2,3……n).

-Start the process by assigning a value of zero for the index number of row1.

-then complete the calculation of Ui‟s and Vj‟s for other rows and columns using the
relations: cij = Ui + Vj where cij is the transportation cost of the cell.

Step2. For unoccupied cell calculate an opportunity cost by using the relation:

dij=cij - (ui +vj) for all i and j

Step3. Examine sign of each dij

- if dij > 0 ,then current basic feasible solution is optimal

-if dij = 0, then current basic feasible solution will remain un affected but an alternative
solution exist

- If one or more dij< 0, then an improved solution can be obtained by entering

unoccupied cell (i,j) in the basis. An unoccupied cell having the largest negative value of
dij is chosen for entering in to the solution mix (new transportation schedule).

Page 134
Step4. Construct a closed path for the unoccupied cell with largest negative opportunity
cost. start the closed path with the selected unoccupied cell and mark a plus sign (+) in
this cell, trace a path along the rows (or columns) to unoccupied cell, mark the corner
with minus sign (-) and continue down the column or row to unoccupied cell and mark
the corner with plus sign and minus sign alternatively. Close the path back to the selected
unoccupied cell.

Step5. Select the smallest quantity amongst the cells marked with minus sign on the
corners of closed path. 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 sign

Step6. Obtain a new improved solution by allocating units to the unoccupied cell
according to step 5 and calculate the new total transportation cost.

Step7. Test the revised solution further for optimality. The procedure terminates when all
dij > 0 for unoccupied cell.

Remark:

 The path starts and ends at the selected unoccupied cell. It consists of successive
horizontal and vertical lines whose end points must be occupied cells, except for
the end point associated with entering unoccupied cell.
 It is immaterial whether the loop (path) is traced in a clockwise or anti-clockwise
direction. However, for a given solution only one loop can be constructed for each
unoccupied cell.
 Any two adjacent cells of the ordered set lie either in the same row or in the same
column.
 Closed loops (path) may or may not be square in shape.
 All cells that have a plus or minus sign, except the starting unoccupied cell, must
be occupied cell.
 Ever loop has an even number of cells and at least four.

Page 135
Example6

For better understanding turn back to Example 5 with the initial feasible solution found
using LCM method. The following table is the initial feasible solution found using LCM
(see Example5)

A B C Supply Ui

S1 5 7 9 500 U1=0

500

S2 6 2 4 600 U2=-5

500 100

S3 3 9 5 800 U3=-4

600 200

Demand 600 500 800 1900

1900

Vj V1=7 V2=7 V3=9

Required: Obtain an optimal solution using MODI method

Solution

To test the initial feasible solution of LCM by using MODI methods followed the
following steps.

Step1. Calculate the index for Ui (row), Vj(column) for occupied cell.

NB: the index of U1=0

Page 136
 Occupied cell cij = Ui + Vj index

S1, C 9 = U1 + V3 U1=0

9 = 0 + V3 V3=9

S2, B 2 = U2 +V2

2 = -5 + V2 V2=7

S2, C 4 = U2 +V3

4 = U2 +9 U2=-5

S3, A 3 = U3+V1

3 = -4+V1 V1=7

S3, C 5 = U3+V3

5 = U3 + 9 U3=-4

Step2 calculate the opportunity cost for unoccupied cell using the relation:

dij = Cij –Ui –Vj

Unoccupied cell dij = Cij –Ui –Vj index (dij)

S1,A 5– 0– 7 -2

S1,B 7- 0– 7 0

S2,A 6 – (-5) - 7 4

S3,B 9- (-4)- 7 6

Step3 examine the sign of each.

if dij > 0 ,then current basic feasible solution is optimal

if dij = 0 , then current basic feasible solution will remain un affected

if dij< 0, then an improved solution can be obtained by reassignment

Page 137
 if one or more dij values < 0, then improved solution can be obtained by entering
unoccupied cell (i,j) having the largest negative value.

Based on the above data, cell (S1, A) has a negative index (dij).

This indicates that, if we occupied cell (S1, A), there will be birr two reduction of
transportation cost per unit.

Thus, total reduction of cost = 2Q (where Q is number of unit assigned to this cell)

Step4. Construct a closed path for the unoccupied cell with largest negative opportunity
cost starting the closed path with the selected unoccupied cell (i.e cell S1,A).

At (S1,A), the closed path(loop) is:+(S1,A), -(S1,C),+(S3,C), -(S3,A).

See the following table.

A B C Supply Ui

S1 5 7 9 (-) 500 U1=0

(+)500

S2 6 2 4 600 U2=-5

500 100

S3 3 9 5 (+) 800 U3=-4

100 (-) 700

Demand 600 500 800 1900

1900

Vj V1=7 V2=7 V3=9

Page 138
 Step5. Select the smallest quantity amongst the cells marked with minus sign on the
corners of closed path and allocate this value to cell (S1, A). Then, add it to cell (S3, C)
and subtract it from cell (S3, A and S1, C).

Based on the above table, 500 and 600 are quantities found in cell marked with minus
sign. So, select 500 units and adjust the demand and supply as follows

- assigning the entering cell (S1, A) with 500units

- adjust the supply side by subtract the 500 unit from cell (S1, C) i.e. 500-500 =0
- adjust the demand side by adding 500 unit to cell (S3,C) i.e. 200+500 =700
- adjust the supply side by deducting 500 unit from cell (S3, A) i.e. 600-500 =100

The optimum total transportation cost can be calculated as follows:

Route unit cost quantity shipped cost

S1, A 5 500 2500

S2, B 2 500 1000

S2, 3 4 100 400

S3, A 3 100 300

S3, C 5 700 2100

Total cost 7700

Exercise

1. Based on the data given under Example 5:

a) find the initial feasible solution using NWCM and VAM method
b) test the optimality of the initial feasible solution found in a above using stepping stone
methods and MODI method

Page 139
 1.1.4. SPECIAL CASE IN TRANSPORTATION PROBLEM

In this section we will consider some special cases in solving transportation problems.
The most common special cases includes the following

1. unbalanced supply and demand

2. degeneracy
3. alternative optimal solution
4. unacceptable routes

Now let as see each in detail.

a) Unbalanced supply and demand

For a feasible solution to exist, it is necessary that the total supply must equal total
demand. Unbalanced case may be of two types: supply> demand or demand>supply.

Case1. Demand more than Supply

 If total demand exceeds total supply, a dummy row (called a dummy supply
centre) can be added to the transportation table to account for the excess demand.
The unit transportation cost for the cells in the dummy row is set equal to zero.

Example 1

Three cement factories are located at A, B, C are to be supplied with carbonates stones
from mines X, Y, and Z. any mine can supply to any factory. The only condition is to
minimize the overall transportation cost. The total requirements (demand) and capacities
(supply of mines) are indicated in the table below, along with cost of transportation in
birr per ton.

Page 140
 i. ii. iii
Mines capacity per day factory requirements per cost of transpo
In Lorries loads in tones day in lorry loads in tons rtation in birr
A B C
X 20 A 40 X 2 4 4
Y 50 B 25 Y 8 12 8
Z 30 C 85 Z 2 8 12
100 150

Required: formulate the transportation table and find the initial feasible solution using
NWCM.

Since demand and supply are not equal (i.e. demand exceeds supply) feasible solution
will not exist. This problem can be solved by a balanced situation and proceed as per
method explained earlier.

In order to balance supply and demand, create a dummy source of mine (row) having a
capacity by which supply is less than demand in the initial solution. In this case it is 50
(i.e.150-100=50). Dummy source is included in the table by adding one extra row.
Dummy source will have distribution cost =0. Then find the initial feasible solution
using NWCM. See table below.

To A B C Supply

From

X 2 4 4 20

20

Y 8 12 8 50

Page 141
 20 25 5

Z 2 8 12 30

30

Dummy 0 0 0 50

50

Demand 40 25 85 150

150

The initial feasible solution using NWCM is:

Route unit cost quantity shipped cost
X, A 2 20 40
Y, A 8 20 160
Y, B 12 25 300
Y, C 8 5 40
Z, C 12 30 360
Dummy, C 0 50 0
Total cost 900

Now proceed as above to till optimum solution is obtained using either stepping stone
method or MODI method.

Case 2 Supply more than demand

 If total supply exceeds total demand, an additional column (called dummy demand
centre) can be added to the transportation table to absorb the excess supply. The unit
transportation cost for these cells in this column is set equal to zero because these
represent product items that are not being made and not being sent.

Page 142
Example 2

In the above example given in Example1 of this section, let as have the following supply
and demand. Unit cost is assumed to be the same.

i. ii. iii

Mines capacity per day factory requirements per cost of transpo

In Lorries loads in tones day in lorry loads in tons ration in birr

A B C

X 20 A 40 X 2 4 4

Y 50 B 25 Y 8 12 8

Z 80 C 35 Z 2 8 12

150 100

Required: formulate the transportation table and find the initial feasible solution using
NWCM.

Sine total supply is greater than total demand by 50 units, add a dummy column with 0
unit cost and 50 units of demand. See the following table.

Page 143
 To A B C Dummy Supply
From

X 2 4 4 0 20

20

Y 8 12 8 0 50

20 25 5

Z 2 8 12 0 80

30 50

Demand 40 25 35 50 150
150

Route unit cost quantity shipped cost

X, A 2 20 40
Y, A 8 20 160
Y, B 12 25 300
Y, C 8 5 40
Z, C 12 30 360
Z, dummy 0 50 0
Total cost 900

Now proceed as above to till optimum solution is obtained using either stepping stone
method or MODI method.

b) Degeneracy

Degeneracy occurs when the number of occupied cell contains is less than (m+n-1). In
such cases the current solution cannot be improved because it is not possible to draw a

Page 144
closed path for every occupied cell. Also the values dual variables Ui and Vj which are
used to test the optimality ca not be computed. Thus, we need to remove the degeneracy
to improve the given solution.

The degeneracy can arise either in developing the initial solution or at some intermediate
solution.

Case1. Degeneracy at the initial solution

To resolve degeneracy at the initial solution consider the following points.

 Add an artificial solution „ ‟ (Greek letter epsilon) or  (delta) to one or more of the

unoccupied cell to get „m + n -1’ number of occupied cells. The cell with  is
considered as an occupied cell and is modified in the same manner as other occupied
cells.

 „ or  is assumed to be a very small quantity close to zero

 Generally, in a minimization transportation problem, it is better to allocate  to

unoccupied cells that have lowest transportation costs. In maximization problems it
should be allocated to a cell that has a high pay off value.
 The placement of Delta (  ) cannot be in just any unoccupied cells. It has to be
placed in either the column or the row associated with the cell which simultaneously
full filled the supply and demand constraints.
 The quantity of  is considered to be so small that if it is transferred to an occupied
cell it does not change the quantity of allocation. Hence it does not affect the total

transportation cost. Finally we can eliminate  from the table.

Example. A manufacturer wants to ship 200 loads of his products from two factories
(factiry1 and factory2) to three warehouses (warehouse A, B, and C) as shown below.

Page 145
 To A B C Supply
From

X 5 10 8 75

75 

Y 4 15 12 125

60 65

Demand 75 60 65 200
200

Required: consider the above table and find:

i. The initial feasible solution using NWCM.

ii. Test for optimality using stepping stone method.

Solution

i. Number of occupied cell is less than (m+n-1). Therefore, it is degenerate. To

overcome this problem adds  to unoccupied cell. Note that  has to be placed in
either the column or the row associated with the cell which simultaneously full filled
the supply and demand constraints. In this case cell (X, B) is the appropriate cell to
assign  . The cell with  is considered as an occupied cell and is modified in the
same manner as other occupied cells.

Therefore, the initial feasible solution using NWCM is:

(5 X 75) + (15 X 60) +(12 X 65)= birr 2055

[Link] test the optimality of the initial solution found above, let as use stepping stone
method.

Page 146
 To A B C Supply
From

X (-)5 (+)10 8 75

75 

Y (+)4 (-)15 12 125

60 65

Demand 75 60 65 200
200

Unoccupied cell Closed path with alternate „+‟ and „–‟ sign

X,C +8 – 12 + 15 – 10 = 1

Y, A +4 – 15 +10– 5 = -6

Since cell (Y,A) has a negative index, we must occupy this cell. This enables as to save
birr6 per unit of assignment at this cell. Therefore, total cost reduction=6Q.

See the reallocations in the following table

Page 147
 To A B C Supply
From

X 5 10 8 75

75 

Y 4 15 12 125

60 65

Demand 75 60 65 200
200

The quantities in the cell with minus sign are 75 and 60. Since the smallest is 60, assign
this units at cell (Y, A) and adjust the respective demand and supply amount.

Now, the newly occupied cells are:

(X, A) =75 unit, (Y, A) = 60 units, and (Y, C) = 65 units

Therefore, the optimum solution is:

(75X5) + (4 X 60) + (12 X65) = birr 1395

Case2. Degeneracy at some intermediate solution

To resolve degeneracy which occurs during optimality test , the quantity may be allocated
to one or more cells which have become unoccupied recently to have m+n-1 number of
occupied cells in the new solution.

Example

Goods have to be transported from sources S1, S2, and S3 to destination D1, D2, and D3.
The transportation cost per unit, capacity of the sources and requirements of the
destinations are given in the following table.

Page 148
 To D1 D2 D3 Supply
From

S1 8 5 6 120

S2 15 10 12 80

S3 3 9 10 80

Demand 150 80 50 280

280
.

Required: determine the transportation Schedule so that cost is minimized.

Solution

Using the NWCM, the non degenerate initial feasible solution is given in the following
table:

To D1 D2 D3 Supply
From

S1 8 5 6 120

120

S2 15 10 12 80

30 50

S3 3 9 10 80

30 50

Demand 150 80 50 280

280

Page 149
 Total cost= (120 X8) + (15X30) + (10X50) + (9X30) + (10X50) = birr 2680

To test the optimality of the above solution found in NWCM using MODI method,
calculate Ui, Vj and dij. As usual as shown below.

To D1 D2 D3 Supply Ui
From

S1 8 5 6 120 U1=0

120

S2 15 (+)10 12 80 U2=7

30 (-) 50

S3 (+)3 (-)9 10 80 U3=6

30 50

Demand 150 80 50 280

280

V1=8 V2=3 V3=4

Calculate the index for Ui (row), Vj(column) for occupied cell.

NB: the index of U1=0

Occupied cell cij = Ui + Vj index

S1, D1 8 = U1 + V1 U1=0

8 = 0 + V1 V1=8

S2, D1 15 = U2 +V1

15 = U2 + 8 U2=7

Page 150
 S2, D2 10 = U2 +V2

10 = 7 +V2 V2=3

S3, D2 9 = U3+V2

9 = U3+3 U3=6

S3, D3 10 = U3+V3

10 = 6+ V3 V3=4

Then calculate the opportunity cost for unoccupied cell using the relation:

dij = Cij –Ui –Vj

Unoccupied cell dij = Cij –Ui –Vj index (dij)

S1,D2 5– 0– 3 2

S1,D3 6- 0– 4 2

S2, D3 12 – 7 -4 1

S3,D1 3- 6- 8 -11

Since the unoccupied cell (S3,D1) has the largest negative opportunity cost of -11,there
fore, cell (S3, D1)is entered in to the new solution mix. The closed path for (S3.D1) is
shown in the above table. The maximum allocation to this cell is 30. However, when this
amount is allocated to (S3,D1) both cells with minus sign i.e. (S2,D1) and(S3,D2)
become unoccupied because these two have same allocation(30 units each).thus, the
number of positive allocations became less than the required number(i.e. m+n-1)

Hence this is a degenerate solution as shown below.

Page 151
 To D1 D2 D3 Supply
From

S1 8 5 6 120

120

S2 15 10 12 80

80

S3 3 9 10 80

30  50

Demand 150 80 50 280

280

To remove the degeneracy a quantity  is assigned to one of the cells that has become
occupied so that there are m+n-1 occupied cells. Assign  to either (S2, D1) OR (S3,
D2) and proceed with the usual solution procedure.

C) Alternative optimal solution

Sometimes transportation problems have multiple optimal solutions. In such instance, it

can be useful for a manager to be aware of alternative solutions because this gives the
manager an option of bringing non-quantitative considerations in to the decision. The
existence of alternative optimal solutions can be determined by an inspection of the
opportunity cost (dij) for the unoccupied cells. If an unoccupied cell in an optimal
solution has opportunity cost of zero, an alternative optimal solution can be formed with
another set of allocations without increasing the total transportation cost.

Page 152
Example

A company has received a contract to supply gravels from its three gravel pits (located in
towns W, X and Y) to three new construction projects (located in town A, B and C). The
transportation cost per unit, capacity of the sources (gravel pits) and requirements of the
destinations (construction projects) are given in the following table.

To A B C Dummy Supply
From

W 4 8 8 0 76

X 16 24 16 0 82

Y 8 16 24 0 77

Demand 72 102 41 20 235

235

(NB: Since demand is less than supply, add dummy column with a demand of 20 units.)
Required: determine the transportation Schedule so that cost is minimized.
Solution
First let as find the initial feasible solution using VAM
(Note that if the column difference and row differences are equal; select the cell in which
you can assign the maximum amount with the minimum transportation cost)

A B C Dummy Supply Row difference

W 4 8 8 0 76 4 4 0 -

76

X 16 24 16 0 82 16 8 8 8

21 41 20

Page 153
 Y 8 16 24 0 77 8 8 8 8

72 5

Demand 72 102 41 20 235

Column 4 8 8 0
difference
8 8 10

4 8 8 10

The initial feasible solution=(8X72)+(8X76)+(24X21)+(16X5)+((16x41)+(0X20)= birr

2424

Then calculate the opportunity cost (dij) as shown below.

First

A B C dummy Supply Ui

W 4 8 8 0 76 U1=0

76

X 16(+) 24 (-) 16 0 82 21 U2=16

21 41 20

Y 8 (-) 16 (+) 24 0 77 5 U3=8

72 5

Demand 72 102 26 41 20 235

Vj V1=0 V2=8 V3=0 V4=-16

calculate the index for Ui (row), Vj(column) for occupied cell.

Page 154
 NB: the index of U1=0

The initial feasible solution=(8X72)+(8X76)+(24X21)+(16X5)+((16x41)+(0X20)= birr

2424

Occupied cell cij = Ui + Vj index

W,B 8 = U1 + V2 U1=0
8 = 0 + V2 V2=8
X, B 24 = U2 +V2
24 = U2+ 8 U2=16
X, C 16 = U2 +V3
16 = 16 +V3 V3=0
X,dummy 0 = U2+V4
0 = 16 + V4 V4=-16
Y, A 8 = U3 + V1
8 = 8 +V1 V1 = 0
Y, B 16 = U3 + V2
16 = U3 + 8 U3= 8

Then, calculate the opportunity cost for unoccupied cell using the relation:

Y,dummy 0 - 8- (-16) 8 dij = Cij –Ui –Vj

Unoccupied cell dij = Cij –Ui –Vj index (dij)
W,A 4 – 0– 0 4
W,C 8 - 0– 0 8
W, dummy 0 – 0 - (-16) 16
X,A 16 - 16 - 0 0
Y,C 24 - 8- 0 16

The opportunity costs in all unoccupied cells are positive except for cell (X,A) which has
a zero opportunity cost. This means, if (X, A) is occupied, no change in the transportation
cost would occur. To determine the alternative solution, form a closed path for cell(X,A)
Page 155
as shown above. Quantity of 21 and 72 are in the cell with minus sign. So, the maximum
quantity which can be allocated to cell (X, A) is [Link] this change, the new solution is
shown in the following table.

A B C Dummy Supply Ui

W 4 8 8 0 76 U1=0

76

X 16 24 16 0 82 21 U2=16

21 41 20

Y 8 16 24 0 77 5 U3=8

51 26

Demand 72 102 26 41 20 235

Vj V1=0 V2=8 V3=0 V4=-16

Total cost=(16x21)+(8x51)+(8x76)+(16x26)+(16x41)+(0x20)= birr 2424

Since all dij values are positive or zero, this solution is optimal with a minimum total
transportation cost of birr 2424which is the same as in the previous solution.

d) Unacceptable route

In some cases, certain source-destination combinations may be unacceptable. This may

be due to road hazards (like snows, floods etc.), traffic regulations, equipment break
downs, labor problems or skill requirements and so on. In order to prevent that route from
appearing in the final solution, , the manager could assigned a unit cost to that cell that is
large enough to make that route uneconomical and hence ,prohibit its occurrence. One
rule of thumb would be to assign a cost that is 10 times the largest cost in the table. Then

Page 156
the revised problem could be solved using NWCM, LCM or VAM method for an initial
solution and either stepping stone or MODI method can be used to evaluate the initial
solution and possible reallocation. This section is left as an exercise for the reader.

3.1.4. Maximization transportation problem

In general, transportation model is used for cost minimization problems. However, some
transportation-type problems concern profits or revenues rather than costs. In this case
the objective is to maximize rather than to minimize.

The algorithm for solving maximization problem is the same as that for the minimization
problems except that it adds one additional step at the start:

 First identify the cell with the largest profit and subtract all the other cell profits
from that value. These values reflect the opportunity costs that would be incurred
by using routes with unit profits that are less than the largest unit profit.
 Then replace the original unit profits with these opportunity costs and solve in the
usual way for the minimum opportunity cost solution. This will be identical to
maximizing the total profit.
 When the optimal distribution plan has been identified, use the original cell
values (i.e. profits) to compute the total profit for that plan.

Example

A company has three manufacturing plants and three warehouses. These data along with
the unit profit are given below.

Manufacturing plant warehouse unit profit

(Sources) (Destination) D1 D2 D3
S1 =100 D1 = 50 S1 4 2 8
S2 = 200 D2 = 150 S2 5 1 9
S3 = 200 D3 = 300 S3 7 6 3

Page 157
 Required:

i. formulate this problem as the transportation problem to maximize profit

ii. find the initial feasible solution
[Link] for optimality and find the optimum solution

NB: the steps for developing an initial feasible solution, evaluation of optimality and
reallocation are identical to those used for cost minimization.
Solution
i. To formulate the transportation table of maximization, follow similar procedures as
discussed for minimization cases.

To D1 D2 D3 Supply

From

S1 4 2 8 100

S2 5 1 9 200

S3 7 6 3 200

Demand 50 150 300 500

ii. To find the initial feasible solution, first identify the largest unit profit and the subtract
all cells from that value. In this case the largest unit profit is 15.

Then subtract each cell from 15 to get the opportunity cost as shown below.

D1 D2 D3 D1 D2 D3
S1 9- 4=5 9- 2=7 9- 8 =1 S1 5 7 1
S2 9-5=4 9- 1= 8 9- 9=0 S2 4 8 0
S3 9-7 =2 9- 6 =3 9- 3=6 S3 2 3 6

Page 158
 To D1 D2 D3 Supply

From

S1 5 7 1 100

S2 4 8 0 200

S3 2 3 6 200

Demand 50 150 300 500

Find the initial feasible solution using VAM, LCM or NWCM method. Let as use
NWCM.

To D1 D2 D3 Supply

From

S1 5 7 1 100

50 50

S2 4 8 (+)0 200

100(-) 100

S3 2 (+)3 (-)6 200

200

Demand 50 150 300 500

500

Page 159
Since occupied cell=m+n-1=5, it is not degenerate.

Initial solution=(5x50)+(7x50)+(8x100)+(0x100)(6x200)= birr 2600

iii. Test for optimality and find the optimum solution.

As usual let as use the stepping stone method to test for optimality.

The index for each unoccupied cell can be determined by tracing a closed path.

Unoccupied cell Closed path with alternate „+‟ and „–‟ sign

S1, D3 +1 – 0 + 8 – 7 = 2

S1, D1 +4 – 8 +7 – 5 = -2

S3, D1 +2 – 6 +0 – 8+7-5 = 0

S3, D2 +3 – 6 +0– 8 = -11

The index for cell (S1, D1) and (S3, D2) has a negative index which indicates that further
cost reduction (in this case profit improvement) is possible. Since cell (S3, D2) has the
largest number with mines sign (-11), occupied this cell. Thus the total reduction of cost
=11Q (where Q is the amount allocated to cell (S3, D2)

For the optimum assignment see the clothed path in the above table. The quantity 200
and 100 are assigned in the cell with minus sign. Therefore, select the smallest (i.e.100)
to be assigned at cell (S3, D2). The revised allocation is shown below.

Page 160
 To D1 D2 D3 Supply

From

S1 5 7 1 100

50 50

S2 4 8 0 200

200

S3 2 3 6 200

100 100

Demand 50 150 300 500

The optimum total transportation cost can be calculated as follows:

Route unit cost quantity shipped cost

S1, D1 5 50 250
S1, D2 7 50 350
S2, D 3 9 200 0
S3, D2 3 100 300
S3, D3 6 100 600
Total cost = 1500

We stated that the total transportation cost reduction is 11Q. Since Q=100, the total cost
reduction is birr 1100.

Therefore, the optimum solution is 2600-1100= birr 1500.

Using this optimal allocation the total profit can be computed by using the original cell
values (unit profits).

Page 161
 Route unit profit quantity shipped cost
S1, D1 4 50 200
S1, D2 2 50 100
S2, D 3 9 200 1800
S3, D2 3 100 300
S3, D3 6 100 600
Total cost = birr3000

At the optimum allocation total profit = birr3000

3.2. ASSIGNMENT PROBLEM

The assignment problem is a special case of Transportation problem in which the number
of sources and destinations are the same, and the objective is to assign the given job
(tasks) to most appropriate machine (person) so as to optimize the objective function like
minimizing cost or maximizing profit.

The problem of assignment arise because available resources such as men, machine etc
have varying degree of efficiency for performing different activities. Therefore cost,
profit, or time of performing the different activities is different. Thus, the problem is:
„How the assignment is made so as to optimize the given objective‟.

Assumptions
 number of jobs is equal to 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 job being presented
 Loading criteria must be clearly stated such as “minimizing operating time”, or
“maximizing profit”, or “minimizing production costs” or “minimizing production cycle
time” etc.
 the data matrix of the assignment model is similar to transportation model except that the
supply of each resource and demand at each of the destinations is taken to be one i.e.
assignment is made on the bases of 1:1

Page 162
 3.2.1. Solution method for assignment problem

Usually the solution of assignment problem is calculated based on the principles of

reducing the given cost matrix to a matrix of opportunity costs. Opportunity cost shows
the relative penalties associated with assigning resources to an activity as opposed to
making the best (or least assignment).

The Hungarian method can be summarized in the following steps.

Step1. Develop the table from the given problem

If the numbers of rows are not equal to the number of columns and vise-versa, a dummy
row or dummy column must be added. The assignment costs for dummy cells are always
zero.

Step2. Find the opportunity cost table using row reduction and column reduction.

a) Procedures for row reduction:

- Identify the minimum value in each row

- Subtract the minimum value in each row from all the values in that row
- Use the resulting values to develop the new table

b) Procedure for column reduction

- identify the lowest cost in each column

- subtract the lowest cost value in each column from each of the values in that column
- use the resulting values to form a new table

Step3. Determine whether an optimal assignment can be made.

The technique for determining whether an optimal assignment is possible at this stage
consists of drawing straight lines (vertically and horizontally) through the opportunity
cost table in such a way as to minimize the number of lines necessary to cover all zero
entries (i.e. draw a line through a column or row which has the largest number of zeros)

Page 163
If the number of lines equals the number of either the number of rows or columns, an
optimal assignment is made. If the number of lines less than the number of rows or
column, an optimal assignment cannot be determined, and the opportunity cost table must
be revised.

Step4. Develop the new revised the opportunity cost table

If it is not possible to determine an optimal assignment in step 2, the opportunity cost

table must be modified. This can be accomplished as follows:

 From among the cells not covered by any line, chose the smallest elements. Call
this value ‘k’.
 Subtract k from every element in the cell not covered by a line
 Add k to every element in the cell covered by the two lines i.e. intersection of two
lines.
 Element in cells covered by one line remain unchanged.

Step5. You should repeat the process of finding the minimum number of covering lines.
Repeat steps 3 and 4 until number of lines equal number of rows or column.

Step 6. Make an assignment

If number of line is equal with either number of columns or rows, the optimum
assignment is possible. Here, the question is “how to assign?”

To avoid confusion in making the assignments, begin by identifying a row or column that
has only one zero, and make an assignment to that cell (box that cell). Since no other
assignments can be made in this row or column (row or column which contain the
assigned cell), we cross them off. With crossed off column and row, look for a row or
column in which there is only one zero and assigned it. Continue until all zeros are either
crossed or assigned.

Page 164
 Example 1

The district court assigns four judges (A, B, C, and D) to four court dockets (i, ii, iii, and
iv). Estimated time (in days) each court will take to clear each docket are given below.
The objective of the assignment is to minimize the total time required to complete all of
the cases on the four dockets. Based on the given data, determine the number of days
each judge would take to clear each docket.

Estimated days to clear docket

Docket

judge i ii iii iv
A 14 13 17 14
B 16 15 16 15
C 18 14 20 17
D 20 13 15 18
Solution

Step1. Develop the assignment table

 The number of rows = number of column=4. so no need of adding dummy row or column

Step2. Find the opportunity time.

Row reduction: the minimum time (day) in row A, B, C, and D are: 13, 15 14, and 13
respectively. Subtract these elements in their respective row. This shows the additional
time that would be incurred if the lowest time assignment is not made either in terms of
rows or columns. For example, judge A can handle docket ii with the lowest processing
time of 13 days. Therefore, if judge A were assigned docket i, the additional time would
be, 14-13=1 day. Similarly, if judge A were assigned docket iii and iv, the additional time
would be 4(17-13=4) and 1(14-13=1). We can perform similar calculation for the other
rows.

Page 165
 Original estimated days to clear dockets estimated days after row reduction

Docket row docket

judge i ii iii iv minimum judge i ii iii iv
A 14 13 17 14 13 A 1 0 4 1
B 16 15 16 15 15 B 1 0 1 0
C 18 14 20 17 14 C 4 0 6 3
D 20 13 15 18 13 D 7 0 2 5

Column reduction: the procedure of column reduction is similar with row reduction.

Estimated days after column reduction

Docket Docket
judge i ii iii iv judge i ii iii iv
A 1 0 4 1 A 0 0 3 1
B 1 0 1 0 B 0 0 0 0
C 4 0 6 3 C 3 0 5 3
D 7 0 2 5 D 6 0 1 5
Column
Minimum 1 0 1 0

Step3. Determine whether an optimal assignment can be made

docket

i ii iii iv

A 0 0 3 1

B 0 0 0 0

C 3 0 5 3

D 6 0 1 5

Page 166
Now compare the number of line with the number of columns or rows. Since the
minimum number of covering lines (i.e. 3) is not equals with the number of rows or
columns (i.e.4), at this stage optimum assignment is not possible.

(NB: note that there is another way of covering the first column by vertical line instead
of the line drawn through the first row. This will not change the final result. Here the
point is that, only three lines drawn would be needed.)
Step4. Develop the new revised the opportunity cost table
Since number of line is not equal with number of rows/columns, we must revise the
opportunity time. See the following:
 From among the cells not covered by any lines (i.e.3, 6, 5, 13, & 5), chose the
smallest element (i.e. 1). So k =1
 Subtract 1 from every element in the cell not covered by a line
 Add k to every element in the cell covered by the intersection of two lines i.e.
cell(A, ii)=0+1 and cell (B, ii)=0+1
 Element in cells covered by one line remain unchanged: i.e. cell (A, i) ,(A, iii),
(A,vi), (B,i) ,(B, iii) (B,iv), (C, ii), and (D, ii)
The revised opportunity cost table is shown below

docket

i ii iii vi

A 0 1 3 1

B 0 1 0 0

C 2 0 4 2

D 5 0 0 4

Step5. You should repeat the process of finding the minimum number of covering lines.
Draw the line and compare it with the number of rows or columns.
We cal also draw a line through row D instead of column iii.

Page 167
Now the number of line is 4 which are equal with the number of row or columns.
Therefore the next step is making the assignment.
Step6. Make an assignment
The procedure for identifying the assignment cell is to select the row or column in which
there is only one zero. In this example, the candidates are: row A, row C & column iv.
Thus, first assign row A of column i with a box (). Since no other assignments can be
made in row A and column i cross them with „X‟ mark. With row A and column i crossed
off, look for a row or column in which there is only one zero.
Then cell at row B column iv can be assigned, and cross row B and column iv. Next
assign cell row D column iii. Finally assign row C column ii.
docket

i ii iii vi
0
A 1 3 1
0
0
B 0 1 0
0
C 2 4 2

D 5 0 4

Step7. Find the total days needed.

The total days associated with this solution is obtained by adding original day in the
occupied cells as shown below.

Final assignments days

Judge A to docket i 14

Judge B to docket iv 15

Judge C to docket ii 14

Judge D to docket iii 15

Total estimated days 58

Page 168
 Example 2

A computer centre has three expert programmers. The centre wants three application
programs to be developed. The head of the computer centre, after studying carefully the
programs to be developed, estimate the computer time in minutes required by the expert
for the application programs as follows:

Programmers

A B C

1 120 100 80

Programs 2 80 90 110

3 110 140 120

Required: assign the programmers to the programs in such a way that the total computer
time is minimum.

Solution

Step1. Since numbers of rows are equal with number of column, dummy is not needed.

Step2. First conduct row reduction and column reduction

Estimated time row reduction

Programmers row programmers

A B C minimum

A B C

1 120 100 80 80 Programs1 40 20 0

Programs 2 80 90 110 80 2 0 10 30

3 110 140 120 110 3 0 30 10

Page 169
Second conduct column reduction
Estimated time after column reduction
Programmers‟ programmers

A B C A B C

Programs1 40 20 0 Programs 1 40 10 0

2 0 10 30 2 0 0 30

3 0 30 10 3 0 20 10

Column

Minimum 0 10 0

Step3. Determine whether an optimal assignment can be made

Programmers
A B C

Programs 1 40 10 0

2 0 0 30

3 0 20 10

At this stage optimal assignment is possible because the numbers of lines are equal with
the number of row (columns)
Step5. Make an assignment
Since there is only one zero at row 1 assign this cell.
Programmers
A B C
0
Programs 1 40 10
0
2 0 30
0

3 20 10

Page 170
Final assignments minutes

Program 1 to programmer C 80

Program 2 to programmer B 90

Program 3 to programmer A 110

Total 280

3.3. Special cases in assignment problem

1. 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 certain number of zeros. Such a situation indicates multiple
optimal solutions with the same optimal value of objective function. In such cases the
more suitable situation may be considered by the decision maker.
2. Maximization cases in assignment problem
There may arise situations when the assignment problem calls for maximization of profit,
revenue, sales etc. as the objective function. In this case, one extra step must be added to
start of the process: identify the largest value (pay off element) in the assignment table
and then subtract all the elements of the table from the largest element.
Example
A marketing manager has three sales men and three sales districts. Considering the
capabilities of the sales men and the nature of districts, the marketing manager estimates
that cell per month (in „000‟birrs) for each sales man in each district would be as follows:
Districts
1 2 3

Sales men A 14 22 30

B 20 18 40

C 11 12 50

Required: find the assignment of salesmen to districts that will result maximum sales.

Page 171
 Solution

First convert the given maximization problem in to minimization problem by subtracting

all the elements of the table from the largest element (i.e. 50).

The new cost data (which is equivalent with maximization of the original data) is given
below:

Districts
1 2 3
Sales men A 36 28 20
B 30 32 10
C 39 38 0

* First reduce the row *Table after row r deduction

Districts row district

1 2 3 minimum 1 2 3
Sales men A 36 28 20 20 sale A 16 8 0
B 30 32 10 10 men B 20 22 0
C 39 38 0 0 C 39 38 0

* Second reduce the column

Table before column deduction table after column reduction

District District
1 2 3 1 2 3
sale A 16 8 0 A 0 0 0
men B 20 22 0 B 4 14 0
C 39 38 0 C 23 30 0
Column
Minimum 16 8 0

Page 172
Then as usual, cover all zeros (from the table found after reducing the table) by lines as
shown below.

District

1 2 3

sale A 0 0 0

men B 4 14 0

C 23 30 0

Since the number of table is less than the number of rows or columns, develop a revised
opportunity table. To develop the revised table: add 4 to cell (A,3) and deduct 4 from un
covered elements i.e. cell (B,1), (B,2) (C,1) and (C, 2) and cover zeros by line.

Then the new revised table will be:

District
1 2 3 since the number of lines (3) is equal with the
Sale A0 0 4 number of column or rows (3) optimum
Men B0 10 0 assignment can be possible at this stage.
C 19 26 0

District
1 2 3 * there is only one zero in row C. Thus assign this
Sale A 0 00 4 cell and cross row C and column3.
Men 0

B 10 00 * now row B has only one zero. Assign this cell and
C 19 26 0 cross off row B and column 1.
* Finally assign row cell (A, 2)

Page 173
Optimum assignments sales (in’000’)
Salesman A to district 2 22
Salesman B to district 1 20
Salesman C to district 3 50
Total 280 Thus, total sale = 280,000 birr.

2. unbalanced assignment problem

Any assignment problem can be solved if and only if the opportunity cost matrix is a
square matrix i.e. the number of column must be equal with the number of rows. That is
why solving the assignment problem begins with checking whether the matrix is square
or ton.

If the given matrix is not a square matrix, the assignment problem is called unbalanced
problem. In such cases, a dummy row(s) or column(s) are added in the matrix (with zero
as a cost elements) to make it a square matrix. After making the given assignment matrix
a square matrix, similar procedures can be used to solve the problem. See the Example
given under next section (section 4)

3. Restriction on assignment

In certain instances, a particular matching 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 this cases, the cost of performing that particular activity by a particular
resources (say man, machine etc) is considered to be very large (written as M) so as to
prohibit the entry of this pair of resource- activity in to the final solution.

Example

In the modification of a plant lay out of a factory 4 new machines M1; M2, M3 and M4
are to be installed in a machine shop. There are 5 vacant places A, B, C, D and E

Page 174
 available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be
placed at A. The cost of locating a machine at a place (in „00‟sof birr) is as follows:
Location
A B C D E

M1
9 11 15 10 11

Machine M2 12 9 -- 10 9

M3 -- 11 14 11 7

14 8 12 7 8
M4

Required: find the optimal assignment schedule and the minimum cost.

Solution

* First balance the problem

Since the number of rows is not equal with number of column, add one dummy row to
get a square cost matrix.

* Second assign a high cost, denoted by M to the pair ( M2, C) and ( M3,A). The cost
matrix so obtained is shown below.

Location

A B C D E

M1
9 11 15 10 11

M2 12 9 M 10 9

M3 M 11 14 11 7

14 8 12 7 8
M4
0 0 0 0 0
M5

Page 175
Now apply the assignment procedures to find the optimum assignment i.e. first reduce the
row and then the column. Next draw the line to cover zeros. If all zeros are covered by a
line and the numbers of lines are equal with the number of rows or columns, assign the
cell. See the following.
Location location
A B C D E A B C D E

M1 9 11 15 10 11 M1 0 2 6 1 2

12 9 M 10 9
M2 M2 3 0 M 1 0

M 11 14 11 7 M 4 7 4 0
M3 M3
14 8 12 7 8 7 1 5 0 1
M4 M4
0 0 0 0 0 0 0 0 0 0
M5 M5

Since the number of lines (5) is equal with the number of rows or columns (5), the
optimal solution can be obtained at this stage.
Location
A B C D E
0 2 6 1 2
M1 The optimum assignment and the total mini
0
M2 3 M 1 0
mum costs are:

M3 0 optimum assignment cost (in „00‟)

M4 M 4 7 4 MachineM1 to location A 9
0
M5 MachineM2 to location B 9
0 MachineM3 to location E 7
7 1 5 1
MachineM4 to location D 7
MachineM5 to location C 0
0 0 0 0
Total cost 32 birr
Thus the total cost is 3200 birr.

Page 176
We examine all the rows starting from row „A‟ one-by-one until a row containing only a
single zero element is located (assigned). Here rows „C‟ and „D‟ have only one zero
element in the cell (C ,ii) and (D, ii). Assignment is made first at cell (C, ii) and these
cells. All zeros in the assigned columns are now crossed off as shown below

 second examine the column

We now examine each column starting from column1 (start from the first column).there
is one zero in column iii and column iv in the cell (A, iii) and (A, iv). Assignment is
made in these cells. Thus, cell

Step1. Develop the table from the given problem

If the numbers of rows are not equal to the number of columns and vise-versa, a dummy
row or dummy column must be added. The assignment costs for dummy cells are always
zero.

Step2. Find the opportunity cost table using row reduction and column reduction.

c) Procedures for row reduction:

- Identify the minimum value in each row

- Subtract the minimum value in each row from all the values in that row
- Use the resulting values to develop the new table

d) Procedure for column reduction

- identify the lowest cost in each column

- subtract the lowest cost value in each column from each of the values in that
column
- use the resulting values to form a new table

Step3. Make assignment in the opportunity cost matrix.

The procedure for making assignment is as follows:

Page 177
  Examine the rows successively until a row with exactly one unmarked zero is
obtained. Make an assignment to this single zero by making square ()
around it.
 For each zero value that becomes assigned, eliminate (strike off) all other zeros
in the same row and /or column
 Repeat these two steps for each column and also with exactly single zero value
cell that has not been assigned
 If a row and/or column has two or more unmarked zeros and one cannot be
chosen by inspection, then choose the assigned zero cell arbitrarily
 Continues these process until all zeros in rows/columns are either enclosed
(assigned) or struck off with „X‟ mark.

Step4. Optimality criteria

If the number of assigned cells is equal to the number of rows /columns, then it is an
optimal solution. The total cost associated with this solution is obtained by adding
original cost figures in the occupied cells. If a zero cell was chosen arbitrarily in step 3,
there exists an alternative optimal solution. But if no optimal solution is found, then go to
step 5.

Step5. Revising the opportunity table

Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost table
obtained from step 3 by using the following procurers:
 For each row in which no assignment was made, mark a tick ()
 Examine the marked rows. If any zero cell occurs in those rows, mark a  to the
respective columns that contain those zeros.
 Examine the marked columns. If any assigned zero occurs in those columns, tick
the respective rows that contain those assigned zeros.
 Repeat this process until no more rows or columns can be marked.
 Draw a straight line through each marked column and each unmarked row.

Page 178
If the number of lines drawn (or total assignment) is equal to the number of rows (or
rows) the current solution is the optimal solution, otherwise, go to step 6.

Step6. Develop the new revised opportunity cost table

 From among the cells not covered by any line, chose the smallest elements. Call
this value ‘k‟.
 Subtract k from every element in the cell not covered by a line
 Add k to every element in the cell covered by the two lines i.e. intersection of two
lines.
 Element in cells covered by one line remain unchanged.

Step7. Repeat steps

Repeat steps 3 to 6until an optimal solution is obtained.

Example1

The district court assigns four judges (A, B, C, and D) to four court dockets (i, ii, iii, and
iv). Estimated time (in days) each court will take to clear each docket are given below.
The objective of the assignment is to minimize the total time required to complete all of
the cases on the four dockets. Based on the given data, determine the number of days
each judge would take to clear each docket.

Estimated days to clear docket

Docket

judge i ii iii iv

A 14 13 17 14

B 16 15 16 15

C 18 14 20 17

D 20 13 15 18

Page 179
 Solution

Step1. Develop the assignment table

 The number of rows = number of column=4. so no need of adding dummy row or

column

Step2. Find the opportunity time.

Row reduction: the minimum time (day) in row A, B, C, and D are: 13, 15 14, and 13
respectively. Subtract these elements in their respective row. This shows the additional
time that would be incurred if the lowest time assignment is not made either in terms of
rows or columns. For example, judge A can handle docket ii with the lowest processing
time of 13 days. Therefore, if judge A were assigned docket i, the additional time would
be, 14-13=1 day. Similarly, if judge A were assigned docket iii and iv, the additional time
would be 4(17-13=4) and 1(14-13=1). We can perform similar calculation for the other
rows.

Original estimated days to clear dockets estimated days after row reduction

Docket row docket

judge i ii iii iv minimum judge i ii iii iv

A 14 13 17 14 13 A 1 0 4 1

B 16 15 16 15 15 B 1 0 1 0

C 18 14 20 17 14 C 4 0 6 3

D 20 13 15 18 13 D 7 0 2 5

Column reduction: the procedure of column reduction is similar with row reduction.

Page 180
 Estimated days after column reduction

Docket Docket

judge i ii iii iv judge i ii iii vi

A 1 0 4 1 A 0 0 3 1

B 1 0 1 0 B 0 0 0 0

C 4 0 6 3 C 3 0 5 3

D 7 0 2 5 D 6 0 1 5

Column

Minimum 1 0 1 0

Step3. Make an assignment in the opportunity time matrix

 first examine the row

We examine all the rows starting from row „A‟ one-by-one until a row containing only a
single zero element is located (assigned). Here rows „C‟ and „D‟ have only one zero
element in the cell (C, ii) and (D, ii). Assignment is made first at cell (C, ii) and, all zeros
in the assigned column and now must be crossed off.

 second examine the column

We now examine each column starting from column1 (start from the first column and
then to the next). In this example, there is one zero in column iii and column iv in the cell
(A, iii) and (A, iv). Assignment is made in these columns (first column iii as per their
order and then the next column). Then, all zeros in the assigned cells column and row
must be crossed off. See the following.

Page 181
Estimated days after column reduction

Docket
i ii iii vi
A 0 0 3 1
B 0 0 0 0
C 3 0 5 3
D 6 0 1 5

Chapter Summery

The transportation problem is a particular case of linear programming problem. The

structure of transportation problem involves a large number of shipping routes from
several supply origins to several demand destinations.

In order to find initial solution of a transportation methods the following methods used:

 North- west corner method

 Least cost method, and
 Vogel‟s approximation (or penalty) method.

The north –west corner method is a systematic approach for developing an initial basic
feasible solution. Its chief advantages are that it is simple to use and easy to understand.

List cost approach, also called the minimum –cost method, uses lowest cell as the basis
for selecting route.

Vogel‟s approximation (penalty or regret) method is a heuristic method and is preferred

to the other two methods described above.

The assignment problem is a special case of Transportation problem in which the number
of sources and destinations are the same, and the objective is to assign the given job
(tasks) to most appropriate machine (person) so as to optimize the objective function like
minimizing cost or maximizing profit.

Page 182
 Solution of assignment problem is calculated based on the principles of reducing the
given cost matrix to a matrix of opportunity costs. Opportunity cost shows the relative
penalties associated with assigning resources to an activity as opposed to making the best
(or least assignment).

Review exercise

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

Factory
W1 W2 W3 W4 Capacity

F1 3 2 7 6 5000

F2 7 5 2 3 6000

F3 2 5 4 5 2500

Demand 6000 4000 2000 1500 13500

Required:

a. Develop an initial feasible solution using NWCM & Compute the total cost

b. Develop an initial feasible solution using least-cost method & compute the total cost.
[

2. Three garment plants are available for monthly education of four styles of men's shirts. The
capacities of the three plants are 45,000, 93,000 and 60,000 shirts. The number of shirts required
in style "a" through "d" is 28,000, 65,000, 35,000 & 70,000, respectively. The profits, in $ per
shirt, at each plant for each style are shown below.

Page 183
 Table: The garment plants' profit.

STYLE a b c D
PLANT
1 8 12 -2 6

2 13 4 3 10

3 0 7 11 8

How many shirts of each type to produce in each plant so that profit is maximized?

3. A car rental company has one car at each of five depots a, b, c, d and e. A customer in
each of the five towns A, B, C, D and E requires a car. The distance in (in kilometers)
between the depots and towns where the customers are, is given in the following distance
matrix:

Depots

a B c d e

A 160 130 175 190 200

B 135 120 130 160 175

Towns

C 140 110 155 170 185

D 50 50 90 80 110

E 55 35 70 80 105

How should the cars be assigned to the customers so as to minimize the distance traveled?

Page 184
 CHAPTER FOUR

Decision theory

Learning objectives:

After completing this chapter, you should be able to:

Outline the characteristics of a decision theory to decision making

 Describe and give example of decision making under the three conditions
(certainty, risk and complete uncertainty)
 Construct and understand the pay off table
 Make conclusion by using maximin, maximax, minimax regret, inseaficent reason
and expected value criteria.
 Find out the expected value of perfect information

4.1. Introduction

Making appropriate decision is the most vital aspects in management. Infect certain
authors have defined management as decision making. Decision making is an action.
Every action has a reaction. Some decision initiates a set of activities; some put an end a
certain activities. Some decision can be withdrawn without any consequential actions and
losses, but majority of the decisions are not. Therefore, the success or failure of an
individual or organization experiences, depends to large extent on the ability of making
appropriate decisions

Making an appropriate decision requires an enumeration of feasible and viable

alternatives (courses of actions or strategies), the projection of consequence associated
with different alternatives, and a measure of effectiveness (or an objectives) by which the
most preferred alternative is identified.

Page 185
 Decision theory provides an analytical and systematic approach to the study of decision
making. Decision models useful in helping decision makers make the best possible
decisions are classified according to the degree of certainty. The scale of certainty can
range from complete certainty to complete uncertainty. The region which falls between
these two extreme points corresponds to the decision making under risk (probabilistic
problems).

Irrespective of the types of decision model, there are certain essential terms which are
common in decision making. Let as defines theses terms:

 Decision alternatives: these are act, action, option, or strategies available for decision
maker before any decision is made. Decision alternatives are under the control and
known to decision maker.
 State of nature: a possible future condition (consequence or event) resulting from the
choices of a decision alternatives depends up on certain factors beyond the control of
decision maker. These factors are depends on the environment. Decision maker can
at the most attach subjective probability of occurrence of such events.
 Payoff: a numerical value resulting from each possible combination of alternatives
and state of nature is payoff. The payoff might be profits, revenues costs, or other
measures of values. The payoff values are always conditional values because of
unknown state of nature.
 Degree of certainty. There can be different degree of certainty. One extreme is
complete certainty and the other is complete uncertainty. The latter exists when the
likely hood of the various state of are unknown. Between theses two extremes is risk,
a term that implies that probabilities are known for the state of nature. We will see
these in detail in the next section.

A tabular arrangement of these conditional outcome (payoff) values is known as payoff

matrix (or decision table or payoff table). Rows represent the state of nature and columns
represent decision alternatives to be considered.

Page 186
 4.2. Steps in decision making theory

The decision making process involves the following steps:

Step1. Identify and define the problem

Step2. List all possible future events (state of nature) which are beyond the control of
the decision maker

Step3. Identify all courses of actions (alternatives) which are under the control of the
decision maker

Step4. Express the payoff resulting from each pair of course of action and state of nature.
Normally payoffs are expressed in a monetary value.

Step5. Apply appropriate decision theory model to select the best courses of action.

4.3. The payoff table

A tabular arrangement conditional outcome (payoff) values is known as payoff matrix (or
decision table or payoff table). It includes a list of the alternatives, the possible state of
nature, and the payoff associated with each of the alternatives-statue of nature
combinations. Conventionally, rows represent the state of nature and columns represent
decision alternatives to be considered. Please not that pay off can be profits, revenues
costs, or other measures of values.

Example 1

A firm manufactures three types of products (A, B, C). The fixed cost and the variable
cost of producing each product are given below.

Page 187
 Fixed cost variable cost

Product A 25000 12

Product B 35,000 9

Product C 53,000 7

The likely demand (units) of the products is given below.

Poor demand 3000

Moderate demand 7000

High demand 11,000

The sales price of each type of product is birr 25.

Required: prepare the payoff table.

Solution

In this case the payoff is expressed in profit. So first calculate the profit for each
alternative. There are three products and three demands. Therefore, there are 9(3x3=9)
pairings or pay off cells.

Let D1, D2, and D3 be poor, moderate, and high demand respectively, then payoff is
given by:

Payoff= sales revenue-cost.

The calculation for payoff (in „000‟s) for each pair of alternative demand (course of
action) and the types of product (state of nature) are shown below:

Page 188
Thus, the pay off values in the payoff table (in „000‟s) is shown below.

Product type demand (alternative courses of action)

(State of nature) D1 D2 D3

Product A 14 66 118

Product B 13 77 141

Product C 1 73 145

4.4. Decision making environment

Knowledge of the likely hood of each of the state of nature can play an important role in
selecting a course of action. Generally there are three decision making environments:
certainty, uncertainty and risk.

Page 189
 4.4.1. Decision under certainty

Decision under certainty is the case where the decision maker has a perfect knowledge
(information) about the state of nature. This situation does not need any techniques or
managerial tool for the manager to take his decision. In this case, the decision maker will
simply select an alternative that yields the largest return (payoff) for the known future
(state of nature). However, in practice, decision under certainty is very rare. So this
situation is not of our interest and we left it for the reader.

4.4.2. Decision making under uncertainty

This is a situation in which decision maker has neither previous knowledge of the
outcomes of his decisions, nor is in a position to attribute a probability of occurrence of
such outcomes. Still various options are opened to you to make decision in the absence of
perfect knowledge which depends on a variety of criteria. In this section we will
introduce you only four approaches for decision making under uncertainty.

a) maximaxi or minimini (criteria of optimism)

In this section, the decision maker ensures that he should not miss the opportunity to
achieve the largest possible profit (maxmaxi) or lowest possible cost (minimini). Thus, he
selects the alternatives that represent the maximum of the maxima (or minimum of the
minima) payoffs (outcomes).
The working method is summarized as follows:
 Locate the maximum (or minimum) payoff values corresponding to each alternative.
Then,
 Select an alternative with best anticipated payoff value(maximum for profit and
minimum for cost)
Example 2
To illustrate the maximaxi criteria, let as refer the example given under Example1.
Required: based on Example1, which strategy (decision alternative) should the
manufacturing company adopt?

Page 190
 Solution

In order to determine the strategy (alternative action) first determine the maximum value
for each column. Then, the column with the largest value is considered as the best
strategy.

Product type demand (alternative courses of action)

(State of nature) D1 D2 D3

Product A 14 66 118

Product B 13 77 141

Product C 1 73 145

Column maximum 14 77 145

Maximaxi

The maximum of column maxima is 145. Hence the manufacturing company should
adopt alternative D3 (sale in the high demand).

b) Maximin or minimaxi(criteria of pessimism).

In this criterion, the decision makers ensures that he would earn no less or (pay no more)
tan some specified amount. Thus he selects the alternative that represents the maximum
of the minima (in case of profit) and the minimum of the maximum (in case of loss). The
application is simple. First select the minimum from each column and select the largest
values from the minimum column rows.

Page 191
Example3

Product type demand (alternative courses of action)

(State of nature) D1 D2 D3

Product A 14 66 118

Product B 13 77 141

Product C 1 73 145

Column minimum 1 66 118

maxmin

c) Laplace criteria (equally likely or insufficient reason)

Since the probabilities of state of nature are not known, it is assumed that all state of
nature will occur with equal probability, i.e. each state of nature is assigned an equal
probability.

The working method is summarized as follows:

 compute the expected(average) value payoff for each alternative by adding all the
pay offs and dividing by the number of possible states of nature
 Select the best expected payoff value (maximum for profit or minimum for cost).
a) minimax regret
This criteria also called opportunity loss decision criteria or savage criterion because
decision makers feels regret after adopting a wrong course of action (alternative)
resulting an opportunity loss of payoff. Thus, the decision maker always intends to
minimize this regret. The work method is as follows:
 from the given pay off matrix, develop an opportunity loss(or regret)matrix as
follows:
i. Find the best payoff corresponding to each state of nature, and
ii. Subtract all other entries (payoff values) in that row from this value.
 For each course of action(alternative) identify the worst (maximum regret value)

Page 192
 Select the course of action with the smallest anticipated opportunity loss value. For
better understanding of the concept let as see the following Example
Example
Given the following payoff tables, determine which alternatives would be chosen using
each of these decision criteria.
i. maximaxi, ii)maximin iii) minimax regret iv) laplace criterion
State of alternative

nature a b c d

1 12 17 22 14

2 18 10 16 14

3 15 14 10 14

Solution
i. The maximaxi approach to select the best alternative using maximaxi approach; first
select the maximum values from each column. Then, the best strategy is the
minimum column row with the highest values. See the following computation.
Strategy

State of (alternative)

nature a b c d

1 12 17 22 14

2 18 10 16 14

3 15 14 10 14

Column 18 17 22 14----maximum column row

Maximum

mximaxi

Page 193
The maximum value from the maximum column row is 22. Thus select strategy C

ii. maximin approach.

To select the best alternative using maximini approach, first select the minimum values
from each column. Then, the best strategy is the column with the highest values. See the
following computation.

Strategy

State of (alternative)
nature a b c d
1 12 17 22 14
2 18 10 16 14
3 15 14 10 14
Column 12 10 10 14----maximin column row

minimum

Mximin

The maximum value from the maximum column row is 14. Thus select strategy d.

iii. minimax regret

In order to the maximin regret decision, we must first obtain the opportunity loss or regret
table. To get this table, first identify the best payoff in each row (i.e. 22, 18, and 15 for
row 1, 2, and 3 respectively). Then subtract every payoff in each row from the best pay
off rows. See the following.

Page 194
 State of (alternative) Strategy

nature a b c d

1 (22-12=10) (22-17=5) (22-22=0) (22- 14=8)

2 (18-18=0) (18-10=8) (18-16=2) (18-14=4)

3 (15-15=0) (15-14=1) (15-10=5) (15-14)=1)

Thus, the regret (opportunity loss) table is:

Strategy

State of (alternative)

nature a b c d

1 10 5 0 8

2 0 8 2 4

3 0 1 5 1

Worst regret (Column 10 8 5 8

Maximum)

Minimum regret

The minimum value from the worst regret row is 4. Thus select strategy C.

iv. Laplace criterion

To select the best alternative using Laplace approach, first we must determine the average
payoff for each alternative. Then select the minimum values from each column. Then, the
best strategy is the column with the highest values. To illustrate the laplace criterion
application, let as refer the above Example once again.

Page 195
 Strategy

State of (alternative)

nature a b c d

1 12 17 22 14

2 18 10 16 14

3 15 14 10 14

Average payoff (12+18+15)/3 (17+10+14)/3 (22+16+10)/3 (14+14+14)/3

= 15 =13.67 =16 =14

Best payoff

Since the largest payoff is obtained from alternative C, select this strategy.

b) Hurwicz (criterion of realism)

4.4.3. Decision making under risk

In this case also the decision maker has to make decision when outcomes are not certain.
However, unlike the previous case, he has sufficient information to assign probability
values to the likely occurrence of each of the states. Knowing the probability distribution
of the state of nature, the best decision is to select that course of action (decision
alternatives) which has the largest expected payoff value.

The most widely used criterion for evaluating various courses of action (alternatives)
under risk includes: expected monetary value (EMV), expected opportunity loss (EOL),
expected value of perfect information (EVPI).

Now let us see each with Examples

Page 196
i. expected monetary value

Expected monetary value is the sum of the payoffs for each course of action multiplied
by the probabilities associated with each state of nature.

Steps for calculating EMV

 Construct a payoff matrix listing all possible courses of action and state of nature.
Enter the conditional payoff values associated with each possible combination of
courses of action and state of nature along with the probabilities of the occurrences
of each state of nature.
 Calculate the EMV for each course of action by multiplying the conditional payoffs
by the associated probabilities and add these weighted values for each course of
action.
 Select the course of action that yields the optimal values.

Example

Mr. Abebe quite often flies from Adis Ababa to Debrezeyt. He can use the air port bus
but it costs him birr 25 and there is a 0.8 chance that he will miss the bus. He can also
stay in hotel but it costs him birr 270 with a 0.96cahnces of being on time for the flight.
Still he can use Taxi which costs him birr 350 with a 0.99 chance of being on time for
flight. If Mr. A bebe catches the plane, he will conclude a business transaction which will
produce a profit of birr 10,000 otherwise, he will lose it.

Required: using EMV method, which mode of transportation should [Link] use?

Solution

Computations of EMV for the three courses of action are shown below.

Page 197
State of nature courses of action

Bus

Cost probability expected value

Catch the flight 10,000-25=9975 1-0.8=0.92 9975X 0.92=9177

Miss the flight -25 0.8 -25X0.8= -2

EMV 9177 -2 = birr 9175

State of nature courses of action

Stay in hotel

Cost probability expected value

Catch the flight 10,000-270=9730 0.96 9730X 0.96=9341

Miss the flight -270 1-0.96=0.04 -270X0.04= -11

EMV 9341 -11 = birr 9330

State of nature courses of action

Taxi

Cost probability expected value

Catch the flight 10,000-350=9650 0.99 9650X 0.99=9553.50

Miss the flight -350 1-0.99=0.01 -350X0.01= -3.50

EMV 9553 -3.50 = birr 9550

Page 198
Thus, comparing the EMV of the three courses of action, the alternative with the highest
EMV is the third alternative i.e. using Taxi. So Mr. Abebe must use taxi to maximize his
expected monetary value.

i. Expected opportunity loss (EOL)

An alternative approach to maximize EMV is to minimize the EOL. This approach is

nearly identical to the EMV approach except that a table of opportunity loses used rather
than a table off payoffs. Hence the opportunity loses for each alternative are weighted by
the probabilities of their respective state of nature to compute the EOL. The alternative
with the smallest EOL is selected as the best choice.

Example

A company manufactures goods for a market in which the technology of the product is
changed very rapidly. The R&D department has produced a new product which appears
to have potential for commercial exploitation. A further birr 60,000 is required for
development testing. The company has 100 customers and each customer might purchase
at the most one unit of the product. Market research suggest that a selling price of birr
6000 for each unit with total variable costs and selling estimates are birr 2000 for each
unit.

From the previous experience, it has been possible to drive a probability distribution
relating to the proportion of customers who will buy the product as follows:

Proportion of customers 0.04 0.08 0.12 0.16 0.20

Probability 0.10 0.10 0.20 0.40 0.20

Required: given the above data,

a) show the expected opportunity loss value using the opportunity loss table
b) state whether or not the company should develop the product

Page 199
 Solution

Given: selling price= birr 6000, variable cost = birr 2000,

Number of unit sold=100p, cost of testing 60,000

a) Let „p‟ be the proportion of customers who purchase the product,

S1 be develop the new product alternative

S2 be do not develop the new product

N state of nature, then

First determine the conditional profit payoff as follows

The conditional profit is= (contribution to profit X number of unit sold) -development
test

= (6000-2000) X (100p) - 60000

=400000p- 60,000

The conditional profit values (payoffs) for each pair of state of nature (proportion of
customers who will by the product) and alternative (to develop or not to develop the new
product) is shown in the following table.

Page 200
 State of nature conditional profit =400000p-60,000

(Proportion of customers, p) courses of action

S1 S2

(Develop) (Do not develop)

0.04 -44,000 0
0.08 -28000 0
0.12 -12000 0
0.16 4000 0
0.20 20,000 0

State of nature

(Proportion of customers, p)

Conditional profit opportunity loss

State of nature prob. S1 S2 S1 S2

0.04 0.1 -44,000 0 44,000 0

0.08 0.1 -28000 0 28000 0
0.12 0.2 -12000 0 12000 0
0.16 0.4 4000 0 0 4000
0.20 0.2 20000 0 0 20,000

c) Using the given estimate of probabilities of associated with each state of nature, the
expected opportunity loss (EOL) for each alternative is given below:

*EOL of developing the product (S1) is:

0.1(44000) +0.1(28000) + 0.2(12000) +0.4(0) +0.2(0) = birr 9600

Page 201
*EOL of do not develop the product (S2) is:

0.1(0) +0.1(0) +0.2(0) +0.4(4000) +0.2(20,000) =birr5600.

Since the company wants to minimize the expected opportunity loss, it should select
courses of action S2 (do not develop the product) with minimum EOL.

i) Expected value of perfect information(EVPI)

In decision making under risk each state of nature is associated with the probability of its
occurrence. However, if the decision maker can acquire perfect(complete and
accurate)information, about the occurrence of various state of nature , then he will be able
to select a course of action that yields the desired payoff for whatever state of nature that
actual occurs.

EVPI represents the maximum amount of money the decision maker has to pay to get
information about the occurrence of various state of nature before a decision has to be
made.

Example

A company needs to increase its production beyond its existing capacity. It has narrowed
the alternatives to two approaches to increase the production capacity: expansion, at a
cost of birr 8 million or modernization at a cost of birr5 million. Both approaches would
require the same amount of time for implementation. Management believe that over the
required payback period, demand will either be high or moderate. Since high demand is
considered to be somewhat less likely than moderate demand, the probability of high
demand has been set at 0.35. If the demand is high, expansion would gross an estimated
additional birr 12 million but modernization only an additional birr 6 million, due to
lower maximum production capability. On the other hand, if the demand is moderate, the
comparable figure would be birr 7 million for expansion and birr 5 million for
modernization.

Page 202
 Required: given the above data:

a) calculate conditional profit

b) If the company wishes to maximize EMV, should it modernize or expand?
c) Calculate EVPI
d) Construct the conditional opportunity loss table and also calculate EOL.

Solution

Given: - state of nature: high demand (N1) and moderate demand (N2)

-alternative action (courses of action): expand (S1) and modernize (S2)

a) The calculation for conditional profit values are shown below:

NB: since the probability that the demand is high estimated at 0.35, the probability of
moderate demand must be (1-0.35) = 0.6

State of nature conditional profit (in „000000‟s

(Demand) expand (S1) modernize (S2)

High demand (N1) 12-8=4 6-5=1

Moderate demand (N2) 7-8=-1 5-5=0

b) The calculation of EMV for each courses of action S1 and S2 is given below:

EMV (S1) = 0.35(4) +0.65(-1) =0.75million

EMV (S2) = 0.35(1) +0.65(0) =0.35milliuon

Page 203
 To maximize EMV, the company must choose courses of action S1 (expand). Thus, the
EMV=0.75million

c) To calculate EVPI, we shall first calculate expected payoff with perfect information
(EPPI). To calculate EPPI, we chose optimal courses of action for each state of nature ,
multiply its conditional profit by the given probability to get weighted profit, and then
sum these weights as shown below:

State of nature optimal conditional

(Demand) probability course of action profit weighted profit

High demand 0.35 S1 4 4X.35=1.40

Moderate DD 0.65 S2 0 0X.65=0

EPPI =1.40

The optimal EMV is 0.75million corresponding to the courses of action S1. Then,

EVPI = EPPI –EMV (S1)

= 1.40-0.75

= birr 0.65 million

d) The opportunity loss values are shown below:

Page 204
 State of nature conditional profit conditional loss

(Demand) probability S1 S2 S1 S2

High demand 0.35 4 1 0 3

Moderate DD 0.65 -1 0 1 0

EOL(S1)=0.35(0)+0.65(1)= 0.65 million

EOL(S2) = 0.35(3)+0.65(0)=1.05 million

Since decision makers seek to minimize the EOL, he must select alternativeS1.

Decision threes
In the discussion of decision problems until now our concern has been with the single
stage a problem where in the decision maker has to select the best course of section on
the basis of whatever information is achievable at appoint of time. We shall now consider
the decision situations that involve multiple stages. Also called the sequential decision
problems, they are characterized by a sequence of decisions in which following each
decision, a chance event occurs which in turn affects the next decision.
In analyzing multiple stage decision situations we have to evaluate the decision procedure
in a backward manner by evaluating the best course of action at the later stages to decide
the best action at the earlier stages. For this purpose the decision tree or the decision flow
diagram as it is sometimes called is a very effective device.
A decision tree is a graphic representation of the sequence of action event combination
available the decision maker. It depicts in a systematic manner all possible sequences of
decisions and consequences. Each such sequence is shown by a distinct path through h
the tree. A decision tree enables the decision maker to see the various element of this
problem in proper perspective e and in a systematic manner. It may be mentioned that the
criterion on the basis of which the decision are made in the decision tree approach is

Page 205
 generally the expectation principle. Thus we may choose the alternative that maximizes
the expected profit, or the alternative that minimizes the expected cost… and so on.
Example1.
1. An oil company has recently acquired rights in a certain area to conduct surveys and test
drillings to lead to lifting oil if it is found in commercially exploitive quantities. The area
is considered to have good potential for finding oil in commercial quantities. At the
outset the company has the choice to conduct further geological tests or to Cary out a
drilling program immediately. On the known conditions, the company estimates that
there is a 70:30 chance of future tests showing a success.
Whether a tests show the possibility of ultimate success or not or even if no test are
undertaken at all, the company could still pursue its drilling program or alternatively
consider selling its rights to drill in the area. Therefore, However, if it carries out the
drilling program, the likely hood of final success or failure is considered depends on the
forgoing stages. Thus;
 If successful tests have been carried out the expectation of success in drilling is
given as 80:20.
 If the test indicates failure, then the expectation of success in drilling is given as
20:80.
 If no tests have been carried out at all the expectation of success in drilling is given
as 55:45.
Costs and revenues have been estimated for all possible outcomes and the net present
value of each is as follows:
Outcomes Net present value (birr million)
Success
With prior list 100
Without prior list 120
Failure
With prior list -50
Without prior list -40

Page 206
 Sale of exploitation right:

Prior test show success

Prior test show failure

Without prior test

A. Draw up a decision (probability) tree diagram to represent the above information: and
B. Evaluate the tree in order to advice the management of the company on its best course of
action.

65
-40 -50
Failure (0.45)
Sell l Failure (0.2)

120 2 100
Success (0.55)
Drill
Success (0.8)
l
Drill Positive (0.7)
l
Test
3 l 100
Failure (0.2)
Sell l Negative (0.3) Drill
1 l
Index 45 Success (0.8)
Sell
l -50

Decision nods
15
Chance nods

As you observe that the tree has several branches which originate from squares or from
circles. A squire represents a decision node or decision fork at which the decision maker
has to take a decision, while a circle represents a chance node or chance fork at which
events (i.e. the state of nature) are branched out.

Page 207
The method of solution: as mentioned earlier the decisions have to be evaluated in a
backward manner by evaluating the best course at the later stages so as to decide on the
best course of actions on the early stage. Thus, the solution to the problem is obtained by
working backwards, from right to left, through the tree.

Evaluation of decision node 1

Alternatives Out come Probability Conditional value Expected value

Success 0.2 100 20

1. Drill Failure 0.8 (-50) (40)

Total (20)

2. Sell 1.0 15 15

The expected value of the drilling option is a loss of Birr 20 million while if the site is
sold, we can get birr 15 million. On the basis of the criterion of maximization of the
expected profit, our decision would be to sell the site.

Evaluation of decision node 2

Alternatives Out come Probability Conditional value Expected value

Success 0.8 100 80

1. Drill Failure 0.2 (-50) (10)

Total 70

2. Sell 1.0 65 15

Page 208
The two alternative course of action, selling and drilling have expected value equal to 65
million and birr 70 million, respectively. Obviously, therefore, provided that a positive
result is indicated by the test, the best course would be to go in for oil drilling.

Now at this stage we have two conditional decisions, sell the site if negative is obtained
on the test and drill in case the test indicates a positive. At each node the branch at which
we have not to move. Next, we move to the decision node where a decision has to be
taken whether to drill at the outset.

Evaluation of decision node

Alternatives Out come Probability Conditional value Expected value

Success 0.55 120 66

1. Drill Failure 0.45 (40) (18)

Total 48

Positive 0.7 70 49

2. Test Negative 0.3 15 4.5

Total 53.5

3. Sell 1.0 45 45

The expected value of the alternative of carrying out a test is birr 53.5 million, which is
the highest of the three. Therefore, it is better to test before carried out. If it proves
negative, the right should be sold to give a return of birr 15 million. To proceed with
relining, if that happens, would expectedly lead to a loss. However, if the test proves
positive the drilling should be under taken.

Page 209
 Chapter Summary

Knowledge of the likely hood of each of the state of nature can play an important role in
selecting a course of action. There are three decision making environments: certainty,
uncertainty and risk.

Decision under certainty is the case where the decision maker has a perfect knowledge
(information) about the state of nature

Decision making under uncertainty is a situation in which decision maker has neither
previous knowledge of the outcomes of his decisions nor is in a position to attribute a
probability of occurrence of such outcomes.

The most widely used criterion for evaluating various courses of action (alternatives)
under risk includes: expected monetary value (EMV), expected opportunity loss (EOL),
expected value of perfect information (EVPI),

Expected monetary value is the sum of the payoffs for each course of action multiplied
by the probabilities associated with each state of nature.

Expected value of perfect information (EVPI) represents the maximum amount of money
the decision maker has to pay to get information about the occurrence of various state of
nature before a decision has to be made.

A decision tree is a graphic representation of the sequence of action event combination

available the decision maker. It depicts in a systematic manner all possible sequences of
decisions and consequences.

Page 210
 Review question

Choose the best answer

1. A type of decision making environment is

a. Certainty c. Risk
b. Uncertainty d. All

2. The concept of utility is used to

a. Measure the utility of money c. Both A and B

b. Take in to account a version of d. None
risk
3. Which of the following criteria is not applicable to decision making under risk

a. Maximize expected return

b. Maximize return
c. Minimize expected regret
d. Knowledge of likely hood occurrence of each state of nature

4. Which of the following criteria is not used for decision making under uncertainty

a. Maximin
b. Maximax
c. Minimax
d. Minimize expected loss

Page 211
5. The expected value of perfect information (EVPI) is

a. Equal to expected regret of the optimal decision under risk

b. The utility of additional information
c. Maximum expected opportunity loss
d. None

Solve the following problem

6. An investor is given the following investment alternatives and percentage rate of

return.

State of nature (market condition)

Low (%) Medium (%) High (%)

Regular sharing 2 5 8

Risky sharing -5 7 15

Property -10 10 20

Over the past 300 days, 150 days have been medium market conditions and 60 days have
had high market increases.

On the basis of these data, state the optimal investment strategy for the investor.
According to the f given information the probabilities of low medium and high market
conditions would be 90/300 0r 0.30, 150/300 or 0.50 and 60/300 or 0.20, respectively.

a. Calculate the expected payoffs for each of the alternatives

b. Calculate the expected return
c. In which alternative the investor invest hiss money?

Answer b, regular share 0.047, b. risky shares 0.050 and property 0.060. c. since the
expected of 6% highest for property, the investor should invest in this alternative.

Page 212
 CHAPTER FIVE

NETWORK MODEL

Learning objectives

After going through this chapter, you should be able to:

 Define network, project management and network diagram

 State and explain the characteristics and phases of project management
 Describe the major difference between PERT and CPM
 Explain the major conventions of network and steps to draw the network diagram
 Demonstrate project time cost trade-off

5.1. Introduction
Network model is a technique used for planning, and scheduling large projects in the
field of construction, maintenance, fabrication, purchasing computer system, distribution,
transportation, facility allocation, and many others. There are several reasons for the wide
range of applications. First many problems that can be formulated as LP models can also
be visualized with the context of networks. Second network models of problems are
often easier to formulate than alternative LP models of the same problem. Third the
pictorial representation of network models makes them relatively easy to understand,
particularly by the nontechnical decision makers. Finally the advances in network
optimization procedure have resulted in some amazing results in solving network model.

Network diagram is a practical representation of the various events and activities.

Network modeling: Techniques that enable complex projects to be scheduled, taking into
account the precedence of each activity.

The different systems satisfying the definition of network in the physical world

Physical situation Nodes Branches Flow

Highway systems Intersections Roads Vehicles

Communication systems Switching points Wires Messages

Fluid supply systems Pumping stations Pipes Fluid

Production systems Work centers Handling routs Jobs

Project Management Decision points Activities Time

Airway systems Air port Air lines Aircraft

Page 213
 PROJECTS

Definition: A project is a set of proposals for the investment of resources in to a clearly

identified set of actions that are expected to produce future benefits that exceeds costs.

A project is a combination of interrelated activities all of which must be executed in a

certain order for its completion.

Examples of a project:

 New business establishment

 Expansion of existing business
 Launching new product
 Cost reduction project
 Total Quality of Management (TQM), etc
Characteristics of a project:

1. The duration of a project lasts long

2. A project is complex in nature involving many interrelated activities and
participants
3. Delay in completion time may be very costly
4. Project activities are sequential
Phases of project management:

Project management consists of three phases;

1. project planning phase

In order to visualize the sequencing or preceding requirements of the activities in a
project, it is helpful to draw a network diagram. For this the following steps are adopted:

i. Identify various activities (tasks or work elements) to be performed in the project, that is,
develop a breakdown structure (WBS).
ii. Determine requirement of resources such as man, material, machines, money, e.t.c. for
carrying out activities listed above.
iii. Assign responsibility for each work package. The work package corresponds to the
smallest work effort defined in a project and from the set of elements which are the base
for planning, scheduling and controlling the project
iv. Allocate resources to work package.
v. Estimate cost and time at various level of project completion.
vi. Develop work performance criteria
vii. Establish control channels for project personnel.
2. Project scheduling phase
Once all packages have been identified and given unique names or identification,
scheduling of the project, i.e. when each of the activities required to be performed, is
taken up. The various steps are listed below:

Page 214
 i. Identify all people who will be responsible for each task.
ii. Estimate the expected duration of each activity, taking in to consideration the resource
required for their execution in most economic manner.
iii. Specify the interrelationship (i.e. precedence relationship) among various activities.
iv. Develop a network diagram showing the sequential interrelationship between various
activities.
v. Based on the time estimate, calculate the total project duration, identify critical path;
calculate floats; carry out resource smoothing (leveling) exercise for critical (or scarce)
resources taking in to account resource constraints if any.
3. project control phase
It refers to evaluating actual progress (status) against the plan. If significant difference are
observed then the scheduling and resource allocation decision are changed to update and
revise the uncompleted part of the project.

There are two basic planning and control technique that utilize network to complete
predetermined Project or schedule. These are Program Evaluation and Review Technique
(PERT) and Critical Path Method.

PERT is an acronym for "Program Evaluation and Review Technique". This was created
as a means to plan and accelerate the development of the Polaris Ballistic Missile. In
USA the defense department developed a nuclear missile to be launched from beneath the
ocean's surface by a mobile submarine, which would be an effective deterrent against
aggression by an enemy. This paved way to plan how to design, develop and plan the
different stages in the production of a missile and how quickly this task could be
completed. A planning and scheduling technique named PERT gave the answer to these
questions.

In any new venture, uncertainties are bound to creep in. PERT incorporated these
uncertainties into a model, which provides a reasonable answer to these uncertainties.
There are certain statistical aspects scheduling large projects consisting of numerous
activities whose completion times are uncertain and are independent of one another.
PERT is an event-oriented technique. By 'event' we mean reaching a certain stage of
completion of the project.

Another technique, Critical Path Method, abbreviated as CPM, has emerged

simultaneously. It is also a network technique but it is concerned with obtaining the
trade-off, between cost and completion date for large projects. In any project consisting
of several activities each activity can be completed in a normal duration with normal cost.
If we employ more persons or skilled people or given overtime to the workers, the
activity could be completed in a reduced duration known as crash duration. But this
involves an increased cost in the form of additional resources. With CPM the amount
needed to complete the various activities is assumed to be known with certainty. So, the
direct costs for the activities increase and hence the cost of the project also increases. By
reducing the activity duration of some or all possible completed ahead of the schedule.

Page 215
 This will naturally reduce the overhead cost for the entire project. On one hand the direct
expenses increase, if we shorten the activity duration, but, the indirect expenses for the
project are reduced. We have to strike a balance or an optimum time schedule, or at least
cost schedule is to be obtained. This is the purpose of the Critical Path Method. Thus
CPM is not concerned with uncertain job times as in PERT. PERT is useful in research
and developmental projects, whereas CPM is mostly used in construction projects, or in
situations already handled, so that the details like the normal completion time, crash
duration and cost of crashing are already known.

The following are the suggested applications when PERT or CPM is found useful.

The construction of a building or of a highway.

Planning and launching a new product.
Scheduling maintenance for a project.
The manufacture and assembly of a large machine tool.
To conduct a music or drama festival.
Preparation of budget for a company.

5.2. Basic Difference between PERT and CPM

PERT

1. It assumes a probability distribution for the duration of each activity. Thus completion
time estimates for all of the activities are needed
2. To perform PERT analysis on a project, the emphasis is given on the completion of a task
rather than the activities required to perform to reach a particular event or task. Thus, it is
also called event-oriented technique.
3. It is used for one time project involving activities of none-repetitive nature (i.e. activities
which may never have been performed before) in which time estimates are uncertain,
such as redesigning an assembly line or installing a new information system
4. It helps in identifying critical areas in a project so that necessary adjustment can be made
to meet the schedule completion date of the project.
CPM

1. This technique was developed in connection with a construction and maintenance project
in which duration of each activity was known with certainty.
2. It is suitable for establishing a trade-off for optimum balancing between schedule time
and cost of the project.
3. It is used for completion of project involving activities of repetitive nature.
5.3. Network Conventions
1. The project can be sub-divided into a set of predictable independent activities each of
which has a clear beginning and ending.
2. Each activity can be sequenced as to its predecessors or successors.
3. The network is not cyclical

Page 216
 i.e: Each activity is executed once and only once during the life of the project.

4. Activity times may be estimated either as a single point estimate (CPM) or as a 3- point
estimate (PERT)
 CPM- Critical Path Method
 PERT- Program Evaluation and Review Technique
5. The duration of the activities is independent of each other.
Basic terms

 Network: it is the graphic representation of logically and sequentially connected arrows

and nods representing activities and events of a project. Networks are also called arrow
diagram.
 Events: Events of the network represent protect milestone, such as the start or the
completion of an activity (task) or activities, and occur at a particular instant of time at
which some specific part of the project has been or is to be achieved. Event An event is a
point in time that marks the beginning or ending of activity. Events are commonly
represented by circles (nodes) in the network diagram.
The events can be further classified into the following two categories (types):

i. Merge event
An event which represents the joint completion of more than one activity is known as
merge event.

Event

Fig: merge event

ii. Burst event

An event which represents the initiation (beginning) of more than one activity is known
as burst event.
Event

Fig: Burst event

Events in the network diagram are identified by numbers. Each event should be identified
by a number higher than that allotted to its immediately preceding event to indicate
progress of work. The numbering of events in the network diagram must start from left
(start of the project) to right (completion of the project) and top to the bottom. Care
should be taken that there is no duplication in the numbering.

 Activities: Activity is a time-consuming job or task that is a key subpart of the total
project. Activities of the net work represent project operations or tasks to be conducted.
As such each activity except dummy consumes time and resources and incurs costs. An
arrow is commonly used to represent an activity with its head indicating the direction of
progress in the project.

Page 217
 Activities are identified by the numbers of their starting (tail or initial) event and ending
(head or terminals) event. An arrow ( ) extended between two events; the tail event i
represents the start of the activity and the head event j, represents the completion of the
activity.
Activity

Starting Event Completion Event

Fig: Activity -Node relationship in network diagram

Activities can be further classified into the following three categories:

i. Predecessor activity: Predecessor activity is an activity which must be completed

before one or more other activities start.
ii. Successor activity: Successor activity is an activity which started immediately
after one or more of other activities are completed.
iii. Dummy activity
Dummying activity is an activity which does not consume either any resource or time.

A dummy activity in the network is added only to represent the given precedence
relationships among activities of the project and is needed when

a) Two or more parallel activities in a project have same head and tail events, or

b) Two or more activities have some (but not all) of their immediate predecessor
activities in common.

A dummy activity is depicted by dotted line in the network diagram.

A B C

Activity 1 Activity 2 4
Activity

D Dummy Activity
 B is the predecessor of C and D
Activity 3

 B is the successor of A;C and D for B

Network model use the following two type of network to show precedence requirements
of the activities in the project.
Activity-on-Node (AON) Network in this type of precedence network each node (or
circle) represent a specific task while the arcs represent the ordering between tasks. AON
network diagrams place the activities when the nodes and the arrows are used to indicate
sequencing requirement. Generally, these diagrams have no particular starting and ending
nods for the whole project. The lack of dummy activities in this diagram always makes
them easier to draw and to interpret.
Activity-on-Arrow (AOR) network: in this type of precedence network at the each end
of the activity arrow is a node (or circle). This node represents points in time or instance,

Page 218
 when an activity is starting or ending. The arrow itself represents the passage of time
required for that activity to be performed.
These diagrams have a single beginning node from which all activities with no
predecessor may start. The diagram then works its way from left to right, ends with a
single ending node, where all activities with no followers come together. Three important
advantage of using AOA are:
a. Many computer programs are based on AOA network
b. AOA diagram can be superimposed on a time scale with the arrows drawn, the correct
length to indicate the time requirement.
c. AOA diagram give a better sense of the flow of time throughout the project.
The following diagram illustrates AON and AOA.

AOA network AON network

1. Activity A A
A

A B
2. B must follow A A B
B
A
C
3 C must follow B
A&B A C
C

A
B D
4 C must follow A, A C
and D must follow
A&B
B D

5.4. Rules of Network Construction

Following are some of the rules which have to be followed while constructing a network:
1. In network diagram, arrows represent activities and circles the events. The length of an
arrow is of no significance.
2. Each activity should be represented by one arrow and must start and end in a circle
called event. The tail of an activity represents the start and head the completion of work.
3. The event numbered 1 denotes start of the project and is called initial event. All activities
emerging (or taking off) from event 1 should not be preceded by any other activity or
activities. Event carrying the highest number denotes the completion events. A network
should have only one initial event and only one terminal event.

Page 219
 4. The general rule of numbering the event is that the number at an activity’s head should
always be larger than that at its tail. That is, events should be numbered such that for
each activity (i, j), i< j.
5. An activity must be uniquely identified by its starting and completion event which implies
that
a. An event number should not get repeated or duplicated
b. Two activities should not be identified by the same completion event
c. Activities must be represented either by their symbols or by the
corresponding ordered pair of starting-completion events.
6. The logical sequence ( or interrelationship ) between activities must follow the following
rules :
a. An event cannot occur until all the incoming activities into it have been
completed.
b. An activity cannot start unless all the preceding activities, on which it depends,
have been completed.
c. Though a dummy activity does not consume ether any resource or time, even then
it has to follow the rules 6(a) and 6(b).
6. Errors and Dummies In Network
i. Looping and Dangling
Looping (cycling) and dangling are considered as faults in a network. Therefore, these
must be avoided.
1. Looping
A case of endless loop in a network which is also known as looping is shown in figure
below, where activities A, B, and C from a cycle.
4

3
C
1
Looping
B

Fig: Looping in network diagram

In this case it is difficult to number three events associated with activity A, B, and C so as to
satisfy rule 6 of constructing the network.
2. Dangling
A case of disconnect activity before the completion of all activities which is also known as
dangling.

1 A 2 B 4
≈

C Dangling

Fig: Dangling in network diagram

Page 220
 In this case, activity C does not give any result as per the rules of the network. The
dangling may be avoided by adopting rule 5 of constructing the network.

i. Dummy or Redundant Activity.

The following is the one of the cases in which the use of dummy activity may help in
drawing the network correctly as per the various rules

When two or more parallel activities in a project have the same head and tail events:

i.e: two events are connected with more than one arrow.

In figure a, activities B and C have a common predecessor activity A. At the same time,
they have activity D as a common successor. To get the correct network a dummy
activity for the ending event of B to show that D may not start before both B and C are
completed is shown in figure b). A dummy which is used in such a case to establish
relationship proper logical relationships is also known as logic dummy activity.

B
A 2
1 B 3 D
A D B Dummy
1 2 C Dummy A C D
1 3
2

C
C

Fig: a) Parallel Activities Fig: b) Dummy Activity

Example
1. An assembly is to be made from two parts X and Y. Both parts must be turned on a
lathe and Y need not be polished. The sequence of activities together with their
predecessors is given below:
Activity Description Predecessor Activity

A Open work order _

B Get material for X A

C Get material for Y A

D Turn X on Lathe B

E Turn Y on Lathe B, C

F Polish Y E

G Assemble X and Y D, F

H Pack G

Draw a network diagram for the project.

Page 221
 Solution

The network diagram for the project is show below:

3 D
B
1 A 2
Dummy
6 G 7 H 8
C
F
4 E 5

Fig: Network Diagram

2. Listed in the table are the activities and sequencing necessary for a maintenance job on
the heat exchangers in a refinery.

_______________________________________________________________________

Activity Description Predecessor Activity

A Dismantle pipe connections -

B Dismantle header, closure, and floating front A

C Remove tube bundle B

D Clean bolts B

E Clean header and floating head front B

F Clean tube bundle C

G Clean shell C

H Replace tube bundle F, G

I Prepare shell pressure test D, E, H

J Prepare tube pressure test and reassemble I

Required:

Draw a network diagram for the project

Page 222
 Solution

5
F D2
C 4
A 2 B 3 G 6
1 H J
D 8 I 9 10
E
D1
7

Fig: Network Diagram

3. The following table gives the activities in a construction project:

Activity Immediate Predecessor

A -

B -

C -

D A

E C

F A

G D, B, E

Required: Draw an arrow diagram for the project

Solution:

4 5
1

Fig. Net work diagram

Page 223
Example A project has the following activities. The relationships among the activities
are given below. Construct the network.

A is the first operation.

B and C can be performed parallel and are immediate successors to A.

D, E and F follow B.

G follows E.

H follows D, but it cannot start till E is complete.

I and J succeed G.

F and J precede K.

H and I precede L.

M succeeds L and K.

The last operation N succeeds M and C.

H
D
L
I
E
G J K M
B F N
A
C

6.5. Critical path Analysis

The objective of critical path analysis is to estimated the total project duration & to assign
starting & finishing times to all activities involved in the project. This helps in checking
actual progress against the scheduled duration of the project.

The duration of individual activities may be uniquely determined (in case of CPM) or
may involve the three time estimates (in case of PERT) out of which the expected
duration of an activity is computing. Having done this, the following factors should be
known to prepare project scheduling.

i. Total completion time of the project

ii. Earliest & latest start time of each activity
iii. Float for each activity
i.e. the amount of time by which the completion of an activity can be delayed without
delaying the total project completion time.

iv. Critical activities & critical path.

Page 224
 Consider the following notation for the purpose of calculating various times of event &
activities.

A. =Earliest occurrence time of an event, i. It is the earliest time at which an event

can occur without affecting the total project time.
B. =Latest occurrence time of event i. It is the latest time at which an event can
occur without affecting the total project time
C. =Earliest start time for activity (i, j). It is the time at which the activity can start

without affecting the total project time

D. =Latest start time for activity (i, j). It is the latest possible time by which an

activity must start without affecting the total project time

E. =Earliest finish time for activity (i, j ). It is the earliest possible time at which an

activity can finis without affecting the total project time.

F. =Latest finish time for activity (i, j). It is the latest time by which an activity

must get completed without delaying the project completion.

G. Duration of activity ( i, j ).

Expected time estimate

In a network diagram, there should only be one initial event & one final event, while
other events are numbered consecutively with integers 1, 2… n such that , for any
two event i&j connected by an activity which starts at i & finish at j

For calculating the above mentioned times, there are two methods; namely;

1) Forward pass method &

2) Backward pass method
2. Forward Pass Method (For Earliest Event Time)
In this methods calculation begin from the initial event 1, proceed through the network
visiting event in an increasing order of event number & end to the final event, say N. At
each event we calculate earliest occurrence event time (E) & earliest start & finish time
for each activity that begins at that event. When calculations end at the final event N, its
earliest occurrence time gives the earliest possible completion time of the entire project.

The method may be summarized as follows:

1) Set the earliest occurrence time of initial event 1 to zero, i.e.

2) Calculate earliest start time for each activity that begins at event i(=1) This is equal to
earliest occurrence time of event, i (tail event). That is , for all activities (i, j

) starting at event i.

Page 225
 3) Calculate the earliest finish time of each activity that begins at event i. This equal to the
earliest start time of the activity plus the duration of the activity. That is,
for all activities ( i j ) beginning at event

4) Proceed to the next event, say j; j > j

5) Calculate the earliest occurrence time for the event j. This is the maximum of the earliest
finish times of all activities ending into that event, i.e.
for all immediate predecessor activities.

6) If j = N (final event ), then earliest finish time for the project, i.e. the earliest occurrence
time for the final event is given by

= , for all terminal activities.

= max { -1+ } & stop the method.

3. Backward Pass Method (For Latest Allowable Event Time)

In this method calculations begin from final event N, proceed through the network visiting
events in the decreasing order of event number & end at the initial event 1. At each event,
we calculate the latest occurrence event time (L) for the corresponding event, latest finish
& start time for each activity that is terminating at the event, such that the earliest finish
time for the project remains the same. The method may be summarized as follows.

1. Set the latest occurrence of last event N equal to its earliest occurrence tome ( known from
forward pass method), that is

2. Calculate latest finish time of each activity which ends at event j. This is equal to latest
occurrence time of final event N. That is,
= , for all activities (i, j) ending at even j.

3. Calculate the latest start times of all activities ending at j. I t is obtained by subtracting the
duration of the activity from the latest finish time of the activity, That is,
= –, for each activity (i, j) ending at Event j,

4. Proceed backward to the event in the sequence that decreases j by 1.

5. Calculate the latest occurrence time of event i (i<j). This is the minimum of the latest start
times of all activities starting from that event. That is,

6. If j = 1 (initial event), then the latest finish time for project, i.e. latest occurrence time for
the initial event is given by.
For all immediate successor activities

& stop the method

Page 226
 6.5.1. Float (or slack) of an Activity and Event
The float (slack) or free time is the length of time to watch a non critical activity and/or an event
can be delayed the total project completion time. The float of an activity is the amount of time by
which it is possible to delay its completion time without affecting the total project completion
time.
1. Event Float
The float (also sometimes called „slack‟) of an event is the difference between its latest time (Li)
and its earliest time ( ).That is

It is a measure of how much later than expected a particular event could occur without delaying
the completion of the entire project.

2. Activity Float

It is the float (or slack) in the activity time estimates.

Types of activity floats:

a. Total Float
It is the difference between the time available to perform the activity (measured from the
earliest start time to the latest finish time) and the expected completion time of the activity. That
is, for activity (i, j), the total float is given by

b. Free Float

For calculating the total float, only a particular activity was considered with respect to its tail and
head event times or by considering latest start and finish time of an activity with respect to its
earliest start and finish time. However, it may be needed to know that how much an activity‟s
scheduling time can be increased or decreased without changing its immediate successor
activities.

The time by which the completion of an activity can be delayed beyond its earliest finish time
without affecting the earliest start time of a succeeding activity is called free float.

Page 227
Independent float: it is the amount of acceptable daily in the completion of an activity so that it
neither affects its predecessor nor the successor activities. Thus, independent float is the amount
of time available when presiding activities take place at their latest permissible time and all the
following activities can still take place at their earliest possible times.
Independent float

The negative value of independent float is considered zero.

Remarks:
1. Since latest event time is always greater than or equal to the earliest event time (i.e
Ei (TFij )> (FF〗 ij).

This implies the value of free float may range from zero to total float and can never exceed total
float value.
2. The calculation of various floats can help the decision-maker in identifying the
underutilized resources, flexibility in the total schedule and possibilities of
redeployment of resources.
3. Once the float of an activity is disturbed, float of all other activities of the project is changed
and should be recalculated.
4. If total float value is
a. Negative (i.e L-E<0),
-resources are not adequate and activity may not finish in time
-Induce extra resources or certain activities (also called critical activities) need crashing to
reduce negative float value.
b. Zero (i.e L-E=0)
-Resources are just sufficient to complete the activity. Any delay in activity execution will
necessarily increase the project cost.
c. Positive (i.e L-E>0)
-Resources are surplus
-Surplus resources can be deployed elsewhere or execution of the activity can be delayed.
Critical Path
Path: A path is unbroken chain of activities that connects form the start node to the end node
(terminal node).
Certain activities in a network diagram of a project are called critical activities because delay in
their execution will cause further delay in the project completion time. Thus, all activities having
zero total float value are identified as critical activities.
The critical path is the continuous chain of critical activities in a network diagram. It is the
longest path starting from first to the last event & is shown by the thick line or double lines in
the network diagram most of the time.
The length of the critical path is the sum of the individual times of the critical activities living on
it & defines the minimum time required to complete the project.
The critical path on a network diagram can be identified as:
i. For all activities (i, j) lying on the critical path the E –values & L-values for tail &
head events are equal That is,

Page 228
 ii. On critical path
Finding the critical path is important for directing decision-makers attention & effort to critical
activities where improvement will pay the largest dividend.
Example
1. An established company has decided to add a new product to its line. It will buy the
product form manufacturing concern, package is & sell it to a number of distributes
selected on a geographical basis. Market research has identified the volume expected &
the size of sales force required. The steps

Activity Description Time (Week)

A Organize sales office 6
B Hire Salesman 4
C Train salesman 7
D Select advertising agency 2
E Plan advertising campaign 4
F Conduct 10
G Design package 2
H Setup packaging facilities 10
I Package initial Stocks 6
J Order Stock from manufacture 13
K Select distributors 9
L Sell to distributors 3
M Ship stocks 5

Required:
a) Draw the an arrow diagram
b) Indicate the critical path; the critical activities & the total project time
c) For each non-critical activity, find the total float
Solution: (a). the arrow diagram for the given project along with E-values and L-values
is shown in the following diagram.

E4=13
4 I (6)
L4=14
J (13)
H (10)
M (5)
G (2) 9 10
1 3

A (6) 6 E9=20
E1=0 E3=2 E10=25
K (9) L9=20
L1=0 L3=4 E6=17 L10=25
C (7) F (10)
2 5 L6=17
B (4) E5=10
E2=6
L5=10 8
D (2)
L2=6 7 E (4)
E8=12
Forward pass method E7=8
L8=15
L7=11
Page 229
 Determine the earliest start time E i and latest finish Lj for each event by processing as
follows.

E1=0 E2= E1+t1, 2=0+6

E3= E1+t1, 3=0+2=2 E4=Max {E1+t14; E3+t3,4 } i=1, 3

E5= E2+t2, 5=6+4=10

E6=Max {Ei + ti, 6} =Max {E2+t2, 6; E5+t5, 6} Max {0+13, 2+10}=13

E8= E7+t7, 8=8+4=12

Max {6+9; 10+7}=17 E10=Max{Ei+ti, 10]

E7= E2+t2,7=6+2=8 i=8,9

E9=Max {Ei+ti, 9} =Max {E4+t4, 9;E6+t6, 9} =Max {E8+t8, 10; E9+t9, 10}

=Max {12+10; 20+5}=25

=Max {13+6; 17+3} =20

Backward pass method

L10=E10=25 L9=L10 – t9,10=25-5=20

L8=L10 – t8,10=25-10=15 L7=L8 – t7,8=15-4=11

L6- t6,9=20-3=17 L5=L6 – t5,6=17-7=10

L4=L9-t4,9=20-6=14 L3=L4 – t3,4=14-10=4

L2=min {Lj- t2,j} L2=min {Lj- t1,j}

J=5, 6, 7 j=2, 3, 4

=min {L5, - t2, 5; L6, t2, 6;L7-t2, 7} =min{L2,- t1, 2; L3, t1, 3;L4-t1, 4}

=min {10-4; 17-9; 11-2} =6 =min {6- 6, 5; 4-2,; 14-13}=0

B. The vertical path in the network diagram above has been shown by thick lines by joining
all those events where two values Ei& Lj are equal. The critical path of the project is: 1-
2-5-6-9-10 the critical activities are A, B, C, L&M. the total project time is 25 weeks
C. For each non-critical activity, the total float is:

Page 230
 Earliest time Last time Float

Activity Duration Start Finish Start Finish Total Free

(i,j) (tii) (Ei) (Ei+tij) (Lj-tij) (Lj) [(Lj-tij)Ej] (Ej-Ei)-tji

1-3 2 0 2 2 4 2 0

1-4 13 0 13 1 14 1 0

2-6 9 6 15 8 17 2 2

2-7 2 6 8 9 11 3 0

3-4 10 2 12 4 14 2 1

4-9 6 13 19 14 20 1 1

7-8 4 8 13 11 15 3 0

8-10 10 12 22 15 25 3 3

Remark:

 What does the critical path really mean?

- The critical path shows the shortest time in which a project can be completed. Even
though the critical path is the longest path, it represents the shortest time it takes to
complete a project.
- There can be more than one critical path on a project. Project managers should closely
monitor performance of activities on the critical path to avoid late project completion. If
there is more than one critical path, project managers must keep their eyes on all of them

Example2. The following table gives the activities of a construction project and
duration.

Activity 1-2 1-3 2-3 2-4 3-4 4-5

Duration (days) 20 25 10 12 6 10

(i) Draw the network for the project.

(ii) Find the critical path.

(iii) Find the total, free and independent floats of each activity.

Page 231
 Solution: The first step is to draw the network and fix early start and early finish
schedule and then late start-late finish schedule.

E1=0 20 2 12 E1=24
E1=36
L1=36
L1=20 E1=20
4 L1=46 5
1 15 10
6
L1=30
25
E1=5 3 E1=30
L1=30 L1=36

Activity Total Slack Slack Independent Slack

1-2 0 0 0

1-3 5 5 5

2-3 0 0 0

2-4 4 4 4

3-4 0 0 0

4-5 0 0 0

To find the critical path, connect activities with 0 total slack and we get 1-2-3-4-5 as the
critical path.

Check with alternate paths.

1-2-4-5 = 42

1-2-3-4-5 = 46* (critical path)1-3-4-5 = 41

6.6. PERT Networks

Program Evaluation and Review Technique (PERT) - is a network analysis technique
used to estimate project duration when there is a high degree of uncertainty about the
individual activity duration estimates. PERT applies the critical path method to a
weighted average duration estimate.

If the duration of activities in a project is uncertain than activity scheduling calculations

are done by using the expected value of the durations. However, such expected duration
estimated may not be given an accurate answer. Thus, rather than estimating directly the
expected completion time of an activity, three values are considered in PERT.

The three time estimates are:

Page 232
1. Optimistic time (to or a): This is the shortest possible time to perform an activity,
assuming that everything goes well.
2. Pessimistic time (tp or b): This is the maximum (longest) time that is required to perform
an activity, under extremely bad conditions. However, such conditions do not include
acts of God like earthquakes, flood, etc.
3. Most likely time (tm or m): This is the most realistic time to complete the activity.
Statistically, it is the modal values of duration of the activity i.e. consider the time
estimate under the normal situation.
The β distribution is not necessarily systematic; the degree of skewness depends on the
location of and. Thus the range specified by the optimistic time (t0) and pessimistic
time (tp) estimates is assumed to enclose every possible estimates of the duration of the
activity. The most likely time (tm) estimate may not coincide with the midpoint (〖to+
tp)/2 and may occur to its left or its right as shown in the following figure.
Probability

Fig an example of a β distribution

Activity duration

In beta distribution the midpoint ( )/2 is assumed to weight half as much as the most

likely point (). Thus the expected or mean (te) or μ) value of the captivity duration can be
approximated as the arithmetic mean of (to+ tp)/2 and 2tm. That is

Expected activity time (te) = ((to+ tp)/2+2tm)/3 = ((to+ 4tm)+tp)/6

Estimating the variance is apparently based on an analogy to the normal distribution

where 99% of the area under normal curve is within ± 3σ from the mean or fall within the
range approximately 6 standard deviation in length, therefore to, tp or range
enclose about 6 standard deviation of a symmetric distribution, thus, if σ denotes standard
deviation, then

Variance of activity time,

Standard deviation, σ =

Estimation of project completion time

Page 233
 As we are expecting variability in the activity duration, the total project may not be
completed exactly in time. Thus, it is necessary to calculate the probability of actually
meeting the schedule time to the project as well as activities.

The probability distribution of time for completing an event can be approximated by the
normal distribution due to central limit theorem. Thus, the probability of completing the
project by schedule time () is given by

Prob(Z= te/σe )

Where = expected completion time of the project

Z= number so standard deviations the scheduled time or target date lies away
from the mean or expected date.

In order to find out the probability of completing the project in some given time, we shall
consider only the expected length of the critical path and its variance. The expected time
of the project can be calculated by adding the expected time of each activity lying on the
critical path can be known by adding variance of critical activity.

Example1.

1. A project is represented by a network shown below & has the following data

Task: A B C D E F G H I

Optimistic time 5 18 26 16 15 6 7 7 3

Pessimistic time: 10 22 40 20 25 12 12 9 5

Most Likely time: 8 20 33 18 20 9 10 8 4

Determine the following

a. Expected task time & their variance
b. The earliest & latest expected times to reach each event
c. The critical path

F
I
3 6 7
B
E H

A D
1 2 5
G

C
4

Page 234
 d. The probability of an event occurring at the expected completion date if the original
scheduled time of completing the project is 41.5 weeks.
e. The duration of the project that will have 95% chance of being completed.
Solution (a) using the following formula, the expected activity time (te) or μ) and
variance (σ^2) is given in the following table.

= ((to+ 4tm)+tp)/6 and σ^2=[1/6(tp- to)]^2

Activity to tp tm te= ((to+ 4tm)+tp)/6 σ^2=[1/6(tp- to)]^2

1-2 5 10 8 7.8 0.694

1-3 18 22 20 20.0 0.444

1-4 26 40 33 33.0 5.444

2-5 16 20 18 18.0 0.444

2-6 15 25 20 20.0 2.778

3-6 6 12 9 9.0 1.000

4-7 7 12 10 9.8 0.694

5-7 7 9 8 8.0 0.111

6-7 3 5 4 4.0 0.111

(b) The earliest and latest estimated time presented in the following graph.
E6=29
E3=20
L6=38.8
L3=29.8
F (9) E7=42.8
I (4)
3 6 7
E5=25.8 L7=42.8
E (20) H (8)
B (20)
E2=7.8 L5=34.8
A (7.8) D (18)
1 2 5
L2=16.8
G (9.8)
E1=0

L1=0 C (33)
4
E4=33

L4=33
(c). the critical path is shown by thick line in the above figure where E values and L
values are the same. The critical path is 1-4-7 and the critical completion time for the
project is 42.8 week.

Page 235
(d) the last event 7 will occur only after 42.8 weeks. For this, we require only the duration of
critical activity. This will help us in calculating the standard of the duration of the last event.

Expected length of critical path= 33+9.8=42.8

Variance of critical path length = 5.429+0.694=6.123

It is given that Ts=41.5, Te=42.8 and . Therefore probability of meeting the

scheduled time is given by Prob =prob (Z≤-0.5) =0.3 from normal distribution table

Thus, the probability that the project can be completed in less than or equal to 41.5 weeks is
0.30. In other words, the probability that the project well gate delayed beyond 41.5 weeks is 70%

(e) Given that Prob(Z≤ ts- te/σe )=0.95

But Z0.95=1.46, from normal distribution table. Thus

1.64= ( (Ts-42.8)/2.47)or Ts weeks.

6.7. Project Time-Cos t Trade-Off

The project completion time can be reduced by reducing (crashing) the normal completion time
or critical activities. The reduction in normal time of completion will increase the total budget of
the project. However, the decision maker always looks trade-off between total cost of project and
total time required to complete it.

Project crashing

Crashing is employed to reduce the project can be estimated by computing the relative
completion time by spending extra change in cost (cost slope) per unit change
resource (cost). However, as shown in the in time.
figure beyond point A, cost increases more
Remark: crashing an activity means
quickly when time is reduced. Similarly,
performing it in the shortest technically
beyond point B, the time increases while the
possible time by allocating to it necessary
cost decrease. Since for technical reasons
resources.
time may not be reduced indefinitely,
therefore, we call this limit as crash point.
There is also a cost efficient duration called
Time cost trade-off procedure
normal point. Thus extending the activity
duration beyond normal point may increase The method of establishing Time cost trade-
costs. off procedure for the completion of a project
can be summarized as follows:
For simplicity the relationship between
normal time and cost as well as crash time Step1 determine the normal project
and cost for an activity is assumed to be completion time and associated critical path
linear instead of being concave and/or for the following two cases.
discrete. Thus the crash cost per unit of time

Page 236
 a) When all critical activities are
completed with their normal time. This
provides the starting point for crashing
analysis.
b) When all critical activities are crashed.
This provides the stopping point for
crashing analysis.
Step2. Identify critical activity and compute
the cost slope for each of these by using the
relationship

Cost slope=(crash cost-normal cost)/(crash Step3. For reducing total project completion
time-normal time) time, identify and crash an activity time on
the critical path with lower cost slope value
The values of cost slop for critical activities
to the point where
indicate the direct extra cost required to
execute an activity per unit of time. a) Another path in the network become
critical, or
b) The activity has been crash to its
lowest time.
Step4. If the critical path under crashing is
still critical, return to step three. However, if
due to crashing of an activity time in step 3,
other path(s) in the network also become
critical, then identify and crash the
activities(s) on the critical path (s) with the
Crash point

minimum joint cost slope.

Steps 5 terminate the procedure when each

Normal point

Crash cost A critical activity has been crashed to its

(maximum cost)
lowest possible time. Determine total project
Direct cost

cost (indirect cost plus direct cost)

Normal cost
B corresponding to different project durations.
(minimum cost)

Crash time Normal time

Example1. (maximum
The following
time)table gives data
(Regular on normal time, and cost and crash time and cost for a
time)
project
Activity time

Page 237
 Activities Normal Crash

Time (weeks) Cost (Birr) Time Cost (Birr)

(weeks)

1-2 3 300 2 400

2-3 3 30 3 30

2-4 7 420 5 580

2-5 9 720 7 810

3-5 5 250 4 300

4-5 0 0 0 0

5-6 6 320 4 410

6-7 4 400 3 470

6-8 13 780 10 900

7-8 10 1000 9 1200

a) Draw the network and identify the critical path with a double line.
b) What are the normal project duration and associated cost?
c) Find out the total float associated with each activity.
d) Crash the relevant activities systematically and determine the optimal project completion
time and cost.
Solution (a) the network for normal activity times indicates a project completion time of 32
weeks with the critical path: 1- 2- 5- 6 – 7 -8, as shown in the following figure.
E4=10
E7=22
L4=12
L7=22
4 E5=12 E6=18 7
0
7 L5=12 L6=18 4
3 9 6 10
1 2 5 6
E1=0 E2=3
3 13
5
L1=0 L2=3
8
3
E3=6 E8=32

L3=7 L8=32

(b). normal project duration is 32 weeks and the associated cost is as follow:

Total cost=Direct normal cost+Indirect cost for 32 week

Page 238
(c). Calculation for total float associated with each activity are shown in the following
table.
Activities Total float

1-2

2-3

2-4

2-5

3-5

4-5

5-6

6-7

6-8

7-8

Page 239
(d). for critical activities, crash cost slope is given.

E4=10
E7=21
L4=11
4 L7=21
E6=17 7
0
7 E5=11
L6=17 4
3 8 L5=11 6 10
1
E2=3
2
× 5 6

E1=0 3 13
5
L2=3
L1=0 E8=31 8
3 E3=6

L3=6 L8=31

The minimum value of crash cost per week is for activity 2-5 and 5-6. Hence, crash activity 2-5
by 2days from 9 weeks to 7 weeks. But the time should be reduced by 1 week only otherwise
another path 1-2-3-4-6-7-8 becomes a parallel path. Net work as shown in the above figure is
developed when it is observed that the new project time is 31 weeks and the critical paths are 1-
2-5-6-7-8 and 1-2-3-5-6-7-8. The following table shows the crash cost per week (in birr)

Critical activities Crash cost per week (Birr)

1-2

2-5

5-6

6-7

7-8

With crashing of activity 2-5 the new total cost involved can be calculated as follows;

Page 240
 r h

Dear learners now with respect to the new network given, the new possibilities for crashing in
the critical paths are listed in the following table.

Critical activities Crash cost per week (Birr)

1-2 100

2-5 × (Crashed)

5-6 0 (no crashing is needed)

6-7 50

7-8 45

1-2 70

2-5 200

The minimum value of crashed cost slope is for activity 5-6. Hence, crashing it by 2 weeks from
6 weeks to 4 weeks. The new network diagram is presented as follow. E7=19
E4=10
4 E6=15 L7=19
7
L4=11 0
7 E5=11 L6=15 4
3 8 L5=11 4 10
1
E2=3
2
× 5 × 6

E1=0 3 13
5
L2=3 E8=29
E3=6 8
L1=0
3
L3=6 L8=29

Page 241
As you see in the above figure the critical paths are not changed because activity 5-6 is common
for the two critical paths. But with crashing of activity 5-6 by 2 weeks, the new cost involved is:

With respect to the new network depicted above the new possibility for crashing in the critical
paths are listed below.

Critical activities Crash cost per week (Birr)

1-2 100

2-3 0 (no crashing is needed)

2-5 × (Crashed)

5-6 × (Crashed)

6-7 70

7-8 200

The further crashing of 6-7 activity time from 4 weeks to 3 weeks will results in increased direct
cost than the gain due to reduction in project time. Consequently, here we must stop further
crashing. The optimal project duration is 29 weeks with associated cost of birr 5,805 as shown in
the table below.

Page 242
 Project Crashing Direct cost (Birr) Indirect cost Total cost

duration Activity Normal Crashing Total (Birr) (Birr)

(weeks) And Weeks

32 -- 4,220 -- 4,220 32×50=1,600 5,820

31 2-5(1) 4,220 1×45=45 4,265 31×50=1,550 5,815

29 5-6(2) 4,220 45+45×2=135 4,355 29×5=1,450 5,805

28 6-7(1) 4,220 135+1×70=205 4,425 28×50=1,400 5,825

Summery

Network model is a technique used for planning, and scheduling large projects in the field of
construction, maintenance, fabrication, purchasing computer system, distribution, transportation,
facility allocation, and many others.

A project is a set of proposals for the investment of resources in to a clearly identified set of
actions that are expected to produce future benefits that exceeds costs.

There are two basic planning and control technique that utilize network to complete
predetermined Project or schedule. These are Program Evaluation and Review Technique
(PERT) and Critical Path Method.

Critical path analysis helps to estimate the total project duration & to assign starting & finishing
times to all activities involved in the project. This helps in checking actual progress against the
scheduled duration of the project.

List cost approach, also called the minimum –cost method, uses lowest cell as the basis for
selecting route.

Vogel‟s approximation (penalty or regret) method is a heuristic method and is preferred to the
other two methods described above.

Page 243
The assignment problem is a special case of Transportation problem in which the number of
sources and destinations are the same, and the objective is to assign the given job (tasks) to most
appropriate machine (person)so as to optimize the objective function like minimizing cost or
maximizing profit.

Solution of assignment problem is calculated based on the principles of reducing the given cost
matrix to a matrix of opportunity costs. Opportunity cost shows the relative penalties associated
with assigning resources to an activity as opposed to making the best (or least assignment).

Page 244
 Review Exercise

Choose the best answer

1. The objective of network analysis is to

a. Minimize total project duration
b. Minimize total project cost
c. Minimize production delays, interruption and conflicts
d. All of the above
2. In time cost tradeoff analysis
a. Cost decrease linearly as time increases
b. Cost at normal time is zero
c. Cost increases linearly as time increases
d. None
3. In PERT network each activity time assume a Beta distribution because
a. It is uni-modal distribution that provides information regarding the uncertainty of
time estimates of activities.
b. It has got finite non negative error
c. It need not be symmetrical about model value
d. All
4. The activity which can be delayed without affecting the execution of the immediate
succeeding activity is determined by
a. Total float
b. Free float
c. Independent float
d. A and B
e. None
5. Generally pert technique deals with the project of
a. Reiterative nature
b. Non Reiterative nature

Page 245
c. Deterministic nature
d. None
Part II Solve the following question

6. Listed in the table are the activities & sequencing necessary for the completion of a
recruitment procedure for management trainees (MT) in a firm.

Activity Predecessor Activity

A -

B A

C A

D C

E B

F C

G D, E

H G

I H

J F

K I, J

L K

M L

N M, N.

Draw a network diagram for the project Answer:

Page 246
7. The owner of a chain of fast food restaurants is considering a new computer system for
accounting and inventory control. A computer company sent the following information
about the computer system installation.

Activity Expected time (days)

Description Predecessors Optimistic Most Pessimistic

likely

A Select the computer - 4 6 8

model

B Design input output A 5 7 15

system

C Deign monitoring system A 4 8 12

D Assemble computer hard B 15 20 25

ware

E Develop the main B 10 18 26

programs

F Develop input-output C 8 9 16
routines

G Create database E 4 8 12

H Install the system D,F 1 2 3

I Test and implement G,H 6 7 8

Required:
A. Construct an arrow diagram for this problem
B. Determine the critical path and compute the expected completion time
C. Determine the probability of completing the project in 55 days

Page 247
 Chapter Six

Queuing Theory

Objectives:

On successful completion of this chapter, you should be able to:

 Define the term queuing theory

 Understand the essential features of queuing system
 Explain the queuing discipline

6.1. Introduction

The queuing theory also called the waiting line theory, owes its development to A K Erlang‟s
effort to analyze telephone traffic congestion with a view to satisfying the randomly arising
demand for the services of the Copenhagen automatic telephone system, in year 1909. The
theory is applicable to situations where the “customers” arrive at some service stations for some
service, wait (occasionally not): and then leave the system after getting the service.
Queuing Theory is a collection of mathematical models of various queuing systems. It is used
extensively to analyze production and service processes exhibiting random variability in market
demand (arrival times) and service times.
Queues or waiting lines arise when the demand for a service facility exceeds the capacity of that
facility, that is, the customers do not get service immediately upon request but must wait, or the
service facilities stand idle and wait for customers.
Some customers wait when the total number of customers requiring service exceeds the number
of service facilities, some service facilities stand idle when the total number of service facilities
exceeds the number of customers requiring service.
A common situation occurring in everybody life is that of queuing or waiting in a line.
Registration for school term, red light at a traffic signal, thicket at a movie theater, checkout
counter at a supermarket, buy signal when making a phone call, teller window at a bank, line or
table at a dining hall or restaurant, and so on are examples waiting lines.
Queuing theory can be applied to a wide variety of operational situations where imperfect
matching between the customers and the service facilities is caused by one‟s inability to predict

Page 248
accurately the arrival and service time of customers. In particular, it can be used to determine the
level of service (either the service rate or the number of service facilities) that balances the
following two conflicting costs:

a) Cost of offering the service

b) Cost incurred due to delay in offering service

An increase in the existing service facilities would reduce the customer‟s waiting time.
Conversely, decreasing the level of service should result in long queue(s). This means an
increase (decrease) in the level of service increases (decreases) the cost of operating service
facilities but decreases (increases) the cost of waiting time.

Figure1.1. Illustrates both types of costs as a function of level of service. The optimum service
level is one that minimizes the sum of the two costs.

Cost of operation
Total expected cost

Optimum service level

Cost of operating the service

facility per unit time

Level of service

Fig.6.1. Queuing costs vs. level of service

Of the two types of costs mentioned above, the cost of waiting is difficult to estimate. However,
it is measured in terms of loss of sales or goodwill when the customer is a human being who has
no sympathy with the service. But, if the customer is a machine waiting for repair, then cost of
waiting is measured in terms of the cost of lost production.

The waiting line is developed because the service to a customer may not be rendered
immediately as the customer reaches to the service facility. Thus lack of adequate service facility
would cause waiting lines of customers to be formed. The only way that the service demand can

Page 249
be met with ease is to increase the service capacity (raising the efficiency of the existing capacity
if possible) to a higher level. A manager has to decide an appropriate level of service which is
neither to low nor too high.

6.2. Essential Features of queuing system

The essential features or characteristics of queuing system are:

1. Input source
2. Queuing process
3. Queue discipline
4. Service process(or mechanism)

Customers requiring service are generated at different times by an input source, commonly
known as population. The rate (constant or random) at which customers arrive at the service
facility is determined by the arrival process. The customer‟s entry into the service system
depends upon the queue conditions. If at the time of customer‟s arrival, the server is idle, then
the customer is served immediately. Otherwise the customer is asked to join the queues, which
can have several configurations.

Input source of queue

Service system

Input service Queuing process Service process

Balk Renege Jockey

An input source is characterized by

 Size of the calling population

 Pattern of arrivals at the system
 Behavior of the arrivals

Page 250
An input source need not be homogeneous population but may consist of several sub-
populations.

Size of calling population: the size of calling population whether it is homogeneous or consists
of several sub-populations is considered either to be finite. When the number of potential arrivals
is dependent on the number of customers already in the system (those being served plus those in
queue), the calling population is limited or finite. Alternatively, if a new customer‟s arrival is
independent of the number of customers already in the system, the calling population is
considered unlimited or infinite.

Behavior of arrivals: if a customer, on arriving at the service system stays in the system until
served, no matter how much he has to wait for the service is called a patient customer. Whereas
the customer, who waits for a certain time in the queue and leaves the service system without
getting service due to certain reasons such as a long queue in front of him is called an impatient
customer.

Pattern of arrivals: the arrival process (or pattern) to the service system is classified into two
categories: static and dynamic. These two are further classified based on the nature of arrival rate
and the control which can be exercised on the arrival process.

In static arrival process, the control depends on the nature of arrival rate (random or constant).
Random arrivals are either at a constant rate or varying with time. Thus to analyze the queuing
system, it is necessary to attempt to describe the probability distribution of arrivals. From such
distributions we obtain average time between successive arrivals, also called inter-arrival time
(time between two consecutive arrivals), and the average arrival rate (i.e. number of customers
arriving per unit of time at the service system).

The dynamic arrival process is controlled by both service facility and customers. The service
facility adjusts its capacity to match changes in the demand intensity, by either varying the
staffing levels at different timings of service, varying service charges (such as telephone call
charges at different hours of the day or week) at different timings, or allowing entry with
appointments.

Page 251
The variation in the demand intensity also affects the customer‟s behavior. They either balk or
renege from the service system when confronted with a long slow moving waiting line.

The arrival time distribution can be approximated by one of the following probability
distributions;

a) Poisson distribution
b) Exponential distribution
c) Erlang distribution

Frequently in queuing problems, the number of arrivals per unit of time can be estimated by a
probability distribution known as the Poisson distribution, as it adequately supports many real
world situations.

The Poisson distribution is a discrete probability distribution of the number of customers (events)
arriving in some time interval. The Poisson probability mass function is

, n=0,
P (×=n/Pn= λt) =

Now, if we are interested in the inter arrival time probability distribution, then the time interval
from 0 to t, the probability of no arrival is given by

Let us define the random variable T as the time between successive arrivals. Since a customer
can arrive at any time, T must be a continuous random variable. The probability of no arrival in
the time interval from 0 to t will be equal to the probability that T exceeds t, so we have

The probability that there is an arrival in the time interval from 0 to t is given by

Page 252
 This probability is also called the cumulative probability distribution function, F (t) of T. Also
the distribution of the random variable T is referred to as the exponential distribution. Its
probability density function (pdf) is

In many practical situations, the inter-arrival time is approximated by an exponential distribution

(sometimes called the negative exponential distribution).

F(t)
f (t)

t
0 1 2 3 4

Fig 6.2. _ Exponential probability distribution function fig---Exponential cumulative probability

density function
The mean of exponential distribution is the expected or average time between arrivals E (T).
Thus with arrivals per unit time,

Hence from the above discussion we may conclude that the Poisson distribution of arrivals with
arrival rate is equal to the negative exponential distribution of inter-arrival times with mean

inter arrival times .

The probability density function of exponential distribution can also be used to compute the
probability that the next customer arrives within time, T of the previous arrival. This means that
if a customer has already arrived at the service system, then probability of arriving for the next
customer can be determined by using this equation.
Example if =1.2 and t= 1.5 so
F (1.5) = P (T≤1.5) =1-(x=0/pn=1.8)

= 1-0.165-0.835

Page 253
Also, if customers arrive at the service system at an average rate of 24 customers per hour, and a
customer has already arrived, then probability of another customer arriving in the next 5 minutes
(i.e. t=1/12 hr) is

Further if =24 customers per hour, t= 1/12 hour and , the probability of n
customers arriving within the next 10 minutes is:

Queuing process

The queuing process refers to the number of queues, and their respective lengths. The number of
queues depends upon the layout of the service system. Thus there may be single or multiple
queues. Certain service systems adopt “take a number” policy to avoid a formal queue to form;
the length (or size) of the queue depends upon the operational situation such as physical space,
legal restrictions, and attitude of the customers.

In certain cases, a service system is unable to accommodate more than the required number of
customers at a time. No further customers are allowed to enter until space becomes available to
accommodate new customers. Such type of situations are referred to us finite (or limited) source
queue. On the other hand, if the service system is able to accommodate any number of customers
at a time, then it is referred to as infinite (or unlimited) source queue.

In many other situations, when arriving customers experience long queue(s) in front of a service
facility, they often do not enter the service system even though additional waiting space is
available. The queue length in such cases depends upon the attitude of the customers. In some
finite source queue systems, the maximum permissible queue is of zero length.

A multiple queue system at a service system can also be finite or infinite. But this has certain
advantages such as:

Page 254
 I. The service provided to the customers can be differentiated by adopting different
service rules called queuing discipline
II. Division of manpower is possible
III. Customers has the option of joining any queue and can also switch to the end of
any other queues
IV. Balking behavior of the customers can be controlled

Queue discipline

In the queue structure, the important thing to know is the queue discipline. The queue discipline
is the order or manner in which customers from the queue are selected for service.

There are a number of ways in which customers in the queue are served. Some of these are:

a) Static queue disciplines: are based on the individual customer's status in the queue. Few
of such disciplines are:
i. If the customers are served in the order of their arrival, then this is known as the first-
come, first-served (FCFS) service discipline. Prepaid taxi queue at airports where a taxi
is engaged on a first-come, first-served basis is an example of this discipline.
ii. Last-come-first-served (LCFS) sometimes, the customers are serviced in the reverse
order of their entry so that the ones who join the last are served first. For example,
assume that letters to be typed, or order forms to be processed accumulate in a pile, each
new addition being put on the top of them. The typist or the clerk might process these
letters or orders by taking each new task from the top of the pile. Thus, a just arriving
task would be the next to be serviced provided that no fresh task arrives before it is
picked up. Similarly, the people who join an elevator last are the first ones to leave it.
b) Dynamic queue disciplines are based on the individual customer attributes in the queue.
Few of such disciplines are:
i. Service in Random Order (SIRO) -- Under this rule customers are selected for service
at random, irrespective of their arrivals in the service system. In this every customer in
the queue is equally likely to be selected. The time of arrival of the customers is,
therefore, of no relevance in such a case.

Page 255
 ii. Priority Service-- Under this rule customers are grouped in priority classes on the basis
of some attributes such as service time or urgency or according to some identifiable
characteristic, and FCFS rule is used within each class to provide service. Treatment of
VIPs in preference to other patients in a hospital is an example of priority service.
iii. Pri-emptive priority- under this rule, the highest priority customer is allowed to enter
into the service immediately after entering into the system even if a customer with lower
priority is already in service. That is lower priority customer‟s service is interpreted (pre-
empted) to start service for a special customer. This interrupted service resumed again
after the highest priority customer is served or according to the pre-emptive rules.
iv. Non-pre-emptive priority- in this case highest priority customer goes ahead in the
queue, but service is started immediately on completion of the current service.

For the queuing models that we shall consider, the assumption would be that the
customers are serviced on the first-come-first-served basis.

Service process (mechanism)

The service process is concerned with the manner in which customers are serviced and
leave the service system. It is characterized by

 The arrangement (or capacity) of the service system

 The distribution of the service lines
 Server‟s behavior
 Management policies

Page 256
Arrangement of service facilities the capacity of the service mechanism is measured in
terms of customers that can be served simultaneously and/or effectively. The service
facilities (or servers), commonly known as service channels may be series or in parallel
or mixed (partly in series and partly in parallel).

The series arrangement consists of a sequence of a number of service facilities such that a
customer must go through one facility after another in a particular sequence before the
whole service is completed. Each service facility may however, work independently of
the others, having its own rules of service.

Service Facility
Customers
Served

Customers

a) Single queue, single server

Service Facilities

Customers
Served

Customers

b) Single queue

In the parallel arrangement the incoming customer may join the queue of his choice in
front of service facilities or may be served by any service facilities.

Page 257
 Service facility
Served customers

Customers

Served customers
Arrangement of service facilities in parallel
Service facilities

Customer

Served

Customers

Mixed Arrangement of Service Facilities

Distribution of service time-the time taken by the server from the commencement of
service to the completion of service for a customer is known as the service time.

If μ is the average service rate, then the expected number of customers served during time
interval t will be μt. Thus, if we consider zero time at the start of service, the probability
that services is not completed by time t is given by

If the random variable T represents the service time, then the probability of service
completion within time t is given by

Page 258
 6.3. Probability distribution in queuing system

It is assumed that customers joining a queuing system arrive in random manner and
follow a Poisson distribution or equivalently the inter-arrival times follow exponential
distribution.

In most of the cases, service times are also assumed to be exponentially distributed. It
implies that the probability of service completion in any short-time period is constant and
independent of the length of time that the service has been in progress. The basic reason
for assuming exponential service is that it helps in formulating simple mathematical
models which ultimately help in analyzing a number of aspects of queuing problems.

The number of arrivals and departures (those served) during an interval of time in a
queuing system is controlled by the following assumptions (also called axioms).

a. The probability of an event (arrival or departure) occurring during the time interval (t,
t+Δt) depends on the length of time interval Δt. That is, probability of the event does not
depend either on number of events that occur up to time t or the specific value of t,
meaning that the events that occur in non- overlapping time are statistically independent.
b. The probability of more than one event occurring during the time interval (t, t+ Δt) is
negligible. It is denoted by 0(Δt).
c. At most one event (arrival or departure) can occur during a small time interval Δt. the
probability of an arrival during the time interval ( t, t + Δt) is given by

Where λ is a constant and independent of the total number of arrivals up to time t; Δt is a

small time interval and 0(Δt) represents the quantity that becomes negligible when
compared to Δt as Δt→0, i.e.

Page 259
Distribution of arrivals (pure birth process)

The arrival process assumes that the customers arrive at the queuing at the queuing
system and never leave it. Such a process is called pure birth process. The aim is to
derive an expression for the probability P n (t) of n arrivals during time interval (t, t+ Δt).
The terms commonly used in the development of various queuing models are the
following:

Δt = a time interval so small that the probability of more than one customer‟s arrival is
negligible, i.e. during any given small interval of time Δt only one customer can arrive.

λΔt = probability that a customer will arrive in the system during time Δt.

1- λΔt = probability that no customer will arrive in the system during time Δt.

If the arrivals are completely random, then the probability distribution of a number of
arrivals in a fixed time interval follows Poisson distribution.

Distribution of inter-arrival times (exponential process)

If the number of arrivals, n, in time t follows the Poisson distribution, then

Is an associated random variable defined as the inter-arrival T follows the exponential

distribution and vice vera.

Markovian property of inter- arrival times

The Markovian property of inter arrival times states that the probability that a customer
currently in service is completed at some time t is independent of how long he has
already been in service. That is

T ≥ to} Prob. = {T ≥ t1 T ≥ to} = prob. {0 ≤ T ≤ t1 -to}

Where T is the time between successive arrivals

Page 260
Distribution of departures (pure death process)

The departure process assumes that no customer joins the system while service is
continued for those who are already in the system. Let, at time t =0 (starting time) there
be N ≥ 1 customers in the system. Since service is being provided at the rate of μ.
Therefore, customers leave the system at the rate μ after being serviced. Such a process is
called pure death process

Basic axioms

i. Probability of the departure during time Δ t is μ Δ t.

ii. Probability of more than one departure between time t and

t + Δ t is negligible.

iii. The number o f departures in non- overlapping intervals are statistically

independent.

The following terms are used in the development of various queuing models.

μ Δ t = probability that a customer in-services at time t will complete service during time
Δ t.

1 - μ Δ t = probability that the customer in-service at time t will not complete service
during time Δ t.

The probability density function s (t) of service time is given by

This shows that service times follows negative exponential distribution with mean 1 / μ
2
.
and variance 1 / μ

Distribution of service times

The service time of short duration have the highest probability of occurrence. As the
service time increases, the probability of occurrence tails off exponentially towards zero
probability.

Page 261
 The area under the negative exponential distribution curve is determined as:

It is also described as:

Where F(T) is the area under the curve to the left of T. Thus

is the area under the curve to the right of T.

6.4. Single Server Queuing Models

Model I {M/M1): ( Exponential service-unlimited Queue

The derivation of this model is based on certain assumptions about the queuing system:

I. Exponential distribution of inter-arrival time or Poisson distribution of arrivals

II. Single waiting line with no restriction on length of queue (i.e infinite capacity) and no
balking or reneging
III. Queue discipline is “first-come, first served”
IV. Single server with exponential distribution of service time

The following events (possibilities) may occur during a small interval of time, Δt just
before time t. it is assumed that the system is in state n (number of customers) at time t.

1) The system is in state n (number of customers) and no arrival and no departure, leaving
the total to n customer.
2) The system is in state n+1 (number of customers) and no arrival and one departure,
reducing the total to n customers.
3) The system is in state n-1(number of customers) and one arrival and no departure,
bringing the total to n customers.

Page 262
 We will begin with determining probability, of n customers in the system at time t and
value of its various operating characteristics is summarized as follows:

Figure XX illustrates the process of determining by considering each possible number

of customers either waiting or receiving service at each state which may be entered by the
arrival of new customer or left by the completion of the leading customer‟s service.

0 1 2 n- n n
1- =1
-1

Step 1 obtain system of differential difference equation

If is the probability of a customers at time t in the system, then the probability that
the system will contain n customers at time ( ) can be expressed as the sum of the
joint probabilities of the three mutually exclusive and collectively exhaustive cases as
mentioned above. That is

For

)= -prob. (no arrival in )

+ . Prob. (no arrival in )

+ . Prob. (no arrival in )

. Prob. (no arrival in )

. Prob. (one arrival in )

Terms involving ( ) 2 since

is very small, therefore terms involving ( ) 2 can be neglected. Subtracting from
both sides and dividing by , we got

Page 263
Taking limit on both sides as then above equation reduces to

(1)

Similarly, if there is no customer in the system at time (t when there will be no

service completion during . Thus for n=0 and t 0, we have only two probabilities
instead of three. The resulting equation is

Taking limit on both sides as , we get

(2)

Step 2 obtaining the system of steady state equations

In the steady-state, is independent of time t, and the rate of change can be

considered to be zero. That is

And

Consequently, equations (1) and (2) may be written as:

(3)

(4)

Thus these equations constitute the system of steady-state difference equations. The
solution of these equations can be obtained either by (i) iterative method, (ii) generating
functions method, or (iii) linear operator method. Here we shall be using the iterative
method to find the values of P1, P2 ….in terms of P0, and

Page 264
Step 3 Solve the system of difference equations

From equation 4 we get

Putting n=1 in equation (3), we get

Or

In general, by using the inductive principle, we get

= probability of being in state n(i.e. n customers in the system)

To obtain the value of , we make use of the fact that (sum of all possibilities)

Or

The denominator of this expression is an infinite geometric series, whose sum is:

And hence

Page 265
And

Probability that an arriving customer has to wait= 1-

This expression gives the required probability distribution for exactly n customers in the
queuing system. Hence denotes the probability of the system being empty (no
customer).

Step 4 obtain probability density function of waiting time excluding service time
distribution

The waiting time distribution of each customer in the steady-state is same, and it is a
continuous random variable except that there is a non-zero probability that the delay will
be zero probability that the delay will be zero, i.e. waiting time is zero. Let w be the time
required by the server to serve all the customers present in the system at a particular time
in the steady state. Let be the probability distribution function of w, i.e.
,0

If an arriving customer find customers already in the system, then in order for a
customer to get service at time between 0 and t, all the customers must have been
serviced by time t. let …………… denote service of n customers, respectively.
Thus

The distribution function of waiting time w for a customer who has to wait is given by

Page 266
Since the service time for each customer is independent and identically distributed,
therefore its probability function density is where the mean service

rate is. Thus

Thus the expression for may be written as

This shows that the waiting time distribution is discontinuous at t=0 and continuous in
the range thus expression for (t) may also be written as

dt

Step 5 calculate busy period distribution

Page 267
 For the busy period distribution, let the random variable w denote the total time (waiting
and service) that a customer spends in the system. Then the probability density function
for the distribution is given by

Now

Which is required distribution of busy period

Remark if is viewed as a measurement of demand for service, and as the capacity of the
service facility, then represents the „excess capacity‟ of the system to fill the demand.

Performance measure for Model I

1. a) Expected number of customers in the system (customers in the line plus the customer
being served)

0r

Page 268
 b) Expected number of customers waiting in the queue (i.e. queue length)

2. a) expected waiting time for a customer in the queue

Integrating by parts

Or

b) Expected waiting time for a customer in the system (waiting and service)

0r

3. probability that the number of customers in the system is greater than or equal to k

4. the variance (fluctuation) of queue length

Page 269
5. probability that the queue is non-empty

6. probability of k or more customers in the system

Or

7. expected length of non-empty queue

8. probability of an arrival during the service time when system contains r customers

dt

Page 270
 Example

A television repairman finds that the time spent on his jobs has an exponential
distribution with a mean of 30 minutes. If he repairs sets in the order in which they come
in, and if the arrival of sets follows a Poisson distribution approximately with an average
rate of 10 per 8-hour day, what is the repairman‟s expected idle time each day? How
many jobs are headed of the average set just brought in?

Solution
From the data of the problem, we have
10/8= 5/4 sets per hour; and = (1/30)60=2 sets per hour
a) Expected idle time of repairman each day

Number of hours for which the repairman remains busy in an 8 hour day (traffic
intensity) is given by

Hence the idle time for a repairman in an 8-hours day will be: (8-5) =3 hours

b) Expected (or average) number of TV sets in the system

Example 2

Arrivals at telephone booth are considered to be Poisson with an average time of 10 minutes
between one arrival and the next. The length of phone call is assumed to be distributed
exponentially with mean three minutes.

a) What is the probability that a person arriving at the booth will have to wait?
b) The telephone department will install a second booth when convinced that an arrival
would expect waiting for at least 3 minutes for a phone call. By how much should the
flow of arrivals increase in order to justify a second booth?

Page 271
c) What is the average length of queue that forms from time to time?
d) What is the probability that it will take him more than 10 minutes altogether to wait for
the phone and complete his call?

Solution

From the data of the problem we have

1/10= 0.10 person per minute and =1/3=0.33 person per minute

a) Probability that a person has to wait at the booth

b) The installation of second booth will be justified only if the arrival rate is more than the
waiting time. Let be the increased arrival rate. Then expected waiting time in the queue
will be

Where given) and (say) for the second booth

Hence, the increase in the arrival rate is 0.60-0.10=0.06 arrivals per minute

c) Average length of non-empty queues

d) Probability of waiting for 10 minutes or more is given by

This shows that 3 percent of the arrivals on average will have to wait for 10 minutes or
more before they can use the phone.

Model II

Page 272
This model is identical to the model I with a difference only in queue discipline. Since
the derivation of is independent of any specific queue discipline, therefore in this
model also we have

Consequently, other results will also remain unchanged in any queuing system as long as
remain unchanged.

Model III exponential service, Finite (or limited) Queue

The model is different from model I in respect of the capacity of the system. Suppose that
no more than N customers can be accommodated at any time in the system due to certain
reasons. Thus any customer arriving when the system is already contains N customers
dies not enter the system and is lost.

The difference equations derived in model I will also be same for this model as long
as . The systems of steady-state difference equations for this model are:

Assumptions of this model are same as that of Model I except that the length of the queue
is limited. Moreover, in this case the service rate does not have to exceed arrival rate
( ) in order to obtain steady state conditions.

Using the usual procedure from first two difference equations the probability of a
customer in the system for n= 0, 1. 2 ….N are obtained as follows.

Now in order to obtain the value of use the fact that

Page 273
 And consequently,

The steady-state solution in this case exists even for this is due to the limited
capacity of the system which controls the arrivals by the queue length ( ) not by
the relative rates of arrivals and departure, if

, which is same as in model I.

Performance Measure for Model III

1. Expected number of customers in the system

2. Expected Queue length or expected number of customers waiting in the system

Page 274
3. Expected waiting time of a customer in the system (waiting + service)

4. Expected waiting time of a customer in the queue

5. Fraction of potential customers lost (=fraction of time system is full)

Effective arrival rate,

Effective traffic intensity,

Example

Consider a single server queuing system with Poisson input, exponential service times.
Suppose the mean arrival rate is 3 calling units per hour, the expected service time is 0.25
hour and the maximum permissible calling units in the system is two. Derive the steady-
state probability distribution of the distribution of the number of calling units in the
system, and then calculate the expected number in the system.

Solution

From the data of the problem, we have

3 units per hour; per hour, and N=2

Then traffic intensity,

The steady-state probability distribution of the number of n customers (calling units) in

the system is

Page 275
The expected number of calling units in the system is given by

Chapter summary

The queuing theory also called the waiting line theory, owes its development to A K
Erlang‟s effort to analyze telephone traffic congestion with a view to satisfying the
randomly arising demand for the services of the Copenhagen automatic telephone system,
in year 1909.

Queuing Theory is a collection of mathematical models of various queuing systems. It is

used extensively to analyze production and service processes exhibiting random
variability in market demand (arrival times) and service times.

It is assumed that customers joining a queuing system arrive in random manner and
follow a Poisson distribution or equivalently the inter-arrival times follow exponential
distribution.

Page 276
Page 277
 Review Question

Solve the following problem

1. A company distributes its products by trucks loaded at its only loading station. Both,
company‟s trucks and constructer‟s trucks, are used for this purpose. It was found out that
on average every five minutes, one truck arrived and the average loading time was 3
minutes. 50% of the trucks belong to the constructer. Find out
a. The probability that a truck has to Wait
b. The waiting time of truck that waits and
c. The expected waiting time of constructer truck per day, assuming a 24 shift

2. Customers arrive at a one window drive according to a poison distribution with mean of 10
minutes and service time per customer is Solve exponential with mean of 6 minutes. The
space in front of the window can accommodate only 3 vehicles including the serviced
one. Other vehicles have to wait outside this space. Calculate
a. probably that an arriving customer can drive directly to the space in front of the window
b. Probability that an arriving customer will have to wait outside the directed space.
c. how long an arriving customer is expected to wait before gating the service
3. A branch of Dashen Bank has only one typist. Since the typing work varies in length
(number of pages to the typed) the typing rate is randomly distributed approximating a
poison distribution with mean service rate of 8 letters per hour. The letter arrives at a rate
of 5 per hour during the entire 8 hour work day. If the type writer is values at birr 1.50
per hour, determine
a. Equipment utilization
b. Average system time
c. The percent time that an arriving letter has to wait
d. Average cost due to waiting on the part of type writer, i.e. it remaining idle.

Page 278
 Answer for Review exercises
Chapter one
1. A, 2. A, 3. D, 4. A, 5. A
Chapter Two
1. A 7. D 13. B
2. D 8. F 14. A
3. F 9. A 15. A
4. D 10. B 16. B
5. B 11. B 17. A
6. D 12. C 18. D
Part II
1. Answer: X1=4, X2 =2 2. Answer:X1=1,X2=5
and Maximize Z=230 and Minimize Z=13
3. Answer: 10 units of model X, 2 units of model Y and the maximum profit is $
560.
4. Answer: X1=187.5, X2 =125 and Maximize Z=21,875
5. Minimize 18Y1 + 14Y2
Subject to 2Y1 + 2Y2 ≥ 12
3Y1 + Y2 ≥ 10
Y1 >= 0, Y2 ≥ 0

Chapter three

Initial feasible solution

W1 W2 W3 W4 Factory Capacity

F1 3 2 7 6 5000

Factory 5000

F2 7 5 2 3 6000

F3 1000 2 4000 5 1000 4 5 2500

1000 1500

Demand 6000 4000 2000 1500 13500

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

Routes Units Unit Total

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

b.

Routes Units Unit Total

From To Shipped Cost =Cost

X
F1 W1 3 $ 3000
1000
F1 W2 2 8000
4000
F2 W1 7 17500
2500
F2 W3 2 4000
2000 m= 3,
F2 W4 3 45000
n=4
1500
F3 W1 2 5000 ==>
2500 3+4-1
Total transportation cost =$42,000
=6
occup
ied
calls (Feasible)

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

2. Total profit= $2,119,000

Page 280
3.

A e

B c

C b

D d

Minimum distance = 570 km

Chapter 4
1. D 3. B 5. A
2. C 4. D
6. Answer b, regular share 0.047, b. risky shares 0.050 and property 0.060. c.
since the expected of 6% highest for property, the investor should invest in
this alternative.

Chapter five

1. A 3. A 5. D
2. A 4. B
Chapter six

1. A. 0.6, b. 7.5 minutes c. 10.8 hours

2. a. 98/125 or 0.784, b. 0.216. c. 3/20 hour or 9 minutes.
3. a. 5/8 b, 20 minutes c. 62.5% d. birr 4.50

Page 281