MBA 302 Operation Research(1).pdf

Unit Contents Page No.
1OVERVIEW OF OPERATIONS RESEARCH 1-11
2LINEAR PROGRAMMING PROBLEM 12-37
3TRANSPORTATION PROBLEM (TP) 38-91
4ASSIGNMENT PROBLEM 92-108
5SIMULATION 109-125
6NETWORK ANALYSISTRANSPORTATION PROBLEM (TP) 126-141
CONTENTS

NOTES
Operations Research for
Managers
OVERVIEW OF
OPERATIONS
RESEARCH
1
UNIT - I
OVERVIEW OF OPERATIONS
RESEARCH
CHAPTER OBJECTIVES
•To familiarize the students with the history of operations research.
•To familiarize the students with the use of operations research techniques
in business domain.
CONTENTS
1.1INTRODUCTION
1.2HISTORY OF OPERATIONS RESEARCH
1.3 MEANING OF OPERATIONS RESEARCH
1.4SCOPE OF OPERATIONS RESEARCH
1.5 SIGNIFICANCE OF OPERATIONS RESEARCH
1.6 LIMITATIONS OF OPERATIONS RESEARCH
1.7 APPLICATIONS OF OPERATIONS RESEARCH IN BUSINESS
AND MANAGEMENT
1.8LATEST APPLICATIONS OF OPERATIONS RESEARCH
OVERVIEW OF THE CHAPTER
This chapter focuses on the history of the operations research. This chapter
also focuses on meaning and significance of operations research. It also includes
the scope and limitations of operations research. This chapter also elaborates the
applications of operations research in business and management. It reveals the
latest applications operations research.
KEY WORDS
History, scope, significance, applications.
1.1 INTRODUCTION
The British/Europeans refer to "operational research", the Americans to
"operations research" - but both are often shortened to just "OR" (which is the

NOTES
OVERVIEW OF
OPERATIONS
RESEARCH
2
term we will use). Another term which is used for this field is "management
science" ("MS"). The Americans sometimes combine the terms OR and MS
together and say "OR/MS" or "ORMS". Yet other terms sometimes used are
"industrial engineering"("IE"), "decision science" ("DS"), and “problem solving”.
In recent years there has been a move towards a standardization upon a single
term for the field, namely the term "OR".
The formal activities of Operations Research (OR) were initiated in England
during World War II when a team of British scientists set out to make decisions
regarding the best utilization of war material. Following the end of the war, the
ideas advanced in military operations were adapted to improve efficiency and
productivity in the civilian sector. Today, OR is a dominant decision making tool.
Operations
The activities carried out in an organization.
Research
The process of observation and testing characterized by the scientific
method. Situation, problem statement, model construction, validation,
experimentation, candidate solutions.
1.2 HISTORY OF OPERATIONS RESEARCH
Operations Research is a ‘war baby’. It is because, the first problem
attempted to solve in a systematic way was concerned with how to set the time
fuse bomb to be dropped from an aircraft on to a submarine. In fact, the main
origin of Operations Research was during the Second World War. At the time of
Second World War, the military management in England invited a team of
scientists to study the strategic and tactical problems related to air and land
defense of the country. The problem attained importance because at that time the
resources available with England was very limited and the objective was to win
the war with available meager resources. The resources such as food, medicines,
ammunition, manpower etc., were required to manage war and for the use of the
population of the country. It was necessary to decide upon the most effective
utilization of the available resources to achieve the objective. It was also
necessary to utilize the military resources cautiously. Hence, the Generals of
military, invited a team of experts in various walks of life such as scientists,
doctors, mathematicians, business people, professors, engineers etc., and the
problem of resource utilization is given to them to discuss and come out with a
feasible solution. These specialists had a brain storming session and came out
with a method of solving the problem, which they coined the name “Linear
Programming”. This method worked out well in solving the war problem. As
the name indicates, the word Operations is used to refer to the problems of
military and the word Research is use for inventing new method. As this method
Operations Research for
Managers

NOTES
Operations Research for
Managers
OVERVIEW OF
OPERATIONS
RESEARCH
3
of solving the problem was invented during the war period, the subject is given
the name ‘OPERATIONS RESEARCH’ and abbreviated as ‘O.R.’ After the
World War there was a scarcity of industrial material and industrial productivity
reached the lowest level. Industrial recession was there and to solve the industrial
problem the method linear programming was used to get optimal solution. From
then on words, lot of work done in the field and today the subject of O.R. have
numerous methods to solve different types of problems. After seeing the success
of British military, the United States military management started applying the
techniques to various activities to solve military, civil and industrial problems.
They have given various names to this discipline. Some of them are Operational
Analysis, Operations Evaluation, Operations Research, System Analysis, System
Evaluation, Systems Research, Quantitative methods, Optimization Techniques
and Management Science etc. But most widely used one is Operations Research.
In industrial world, most important problem for which these techniques used is
how to optimize the profit or how to reduce the costs. The introduction of Linear
Programming and Simplex method of solution developed by American
Mathematician George B. Dontzig in 1947 given an opening to go for new
techniques and applications through the efforts and co-operation of interested
individuals in academic field and industrial field. Today the scenario is totally
different. A large number of Operations Research consultants are available to
deal with different types of problems. In India also, we have O.R. Society of
India (1959) to help in solving various problems. Today the Operations Research
techniques are taught at High School levels. To quote some Indian industries,
which uses Operations Research for problem solving are: M/S Delhi Cloth Mills,
Indian Railways, Indian Airline, Hindustan Lever, Tata Iron and Steel Company,
Fertilizers Corporation of India and Defense Organizations. In all the above
organizations, Operations Research people act as staff to support line managers
in taking decisions. In one word we can say that Operations Research play a vital
role in every organization, especially in decision-making process.
1.3MEANING OF OPERATIONS RESEARCH
Defining OR is difficult task as its boundaries and content are not yet fixed.
It can be regarded as use of mathematical and quantitative techniques to
substantiate the decision being taken. Further, it is multidisciplinary which takes
tools from subjects like mathematics, statistics, engineering, economics,
psychology etc. and uses them to score the consequences of possible alternative
actions. Today it has become professional discipline that deals with the
application of scientific methods to decision-making.
Few other definitions of OR are as follows
“OR is concerned with scientifically deciding how to best design and
operate man-machine system usually requiring the allocation of scare resources.”
Operations Research Society, America

NOTES
OVERVIEW OF
OPERATIONS
RESEARCH
4
“OR is essentially a collection of mathematical techniques and tools which
in conjunction with system approach, are applied to solve practical decision
problems of an economic or engineering nature’’.
Daellenbach and George
“OR utilizes the planned approach (updated scientific method) and an
interdisciplinary team in order to represent complex functional relationships as
mathematical models for the purpose of providing a quantitative analysis’’.
Thieraub and Klekamp
“ORis a scientific knowledge through interdisciplinary team effort for the
purpose of determining the best utilization of limited resources.”
H.A. Taha
“OR is a scientific approach to problem solving for executive management”.
H.M. Wagner
1.4SIGNIFICANCE OF OPERATIONS RESEARCH
The significant features of operations research include the followings
(i) Decision-making
Every industrial organization faces multifaceted problems to identify
best possible solution to their problems. OR aims to help the
executives to obtain optimal solution with the use of OR techniques.
It also helps the decision maker to improve his creative and judicious
capabilities, analyze and understand the problem situation leading to
better control, better co-ordination, better systems and finally better
decisions.
(ii) Scientific Approach
OR applies scientific methods, techniques and tools for the purpose of
analysis and solution of the complex problems. In this approach there
is no place for guess work and the person bias of the decision maker.
(iii) Inter-disciplinary Team Approach
Basically the industrial problems are of complex nature and therefore
require a team effort to handle it. This team comprises of
scientist/mathematician and technocrats. Who jointly use the OR tools
to obtain an optimal solution of the problem
Operations Research for
Managers

NOTES
Operations Research for
Managers
OVERVIEW OF
OPERATIONS
RESEARCH
5
(iv) System Approach
The main aim of the system approach is to trace for each proposal all
significant and indirect effects on all sub-system on a system and to
evaluate each action in terms of effects for the system as a whole. The
interrelationship and interaction of each sub-system can be handled
with the help of mathematical/analytical models of OR to obtain
acceptable solution.
(v) Use of Computers
The models of OR need lot of computation and therefore, the use of
computers becomes necessary. With the use of computers, it is possible
to handle complex problems requiring large amount of calculations.
1.5SCOPE OF OPERATIONS RESEARCH
The scope of OR is not only confined to any specific agency like defence
services but today it iswidely used in all industrial organizations. It can be used
to find the best solution to any problem be it simple or complex. It is useful in
every field of human activities, where optimization of resources is required in
the best way. Thus, it attempts to resolve the conflicts of interest among the
components of organization in a way that is best for the organization as a whole.
The main fields where OR is extensively used are given below, however, this list
is not exhaustive but only illustrative.
(i) National Planning and Budgeting
OR is used for the preparation of Five Year Plans, annual budgets,
forecasting of income and expenditure, scheduling of major projects
of national importance, estimation of GNP, GDP, population,
employment and generation of agriculture yields etc.
(ii) Defence Services
Basically formulation of OR started from USA army, so it has wide
application in the areas such as:development of new technology,
optimization of cost and time, tender evaluation, setting and layoutsof
defence projects, assessment of “Threat analysis”, strategy of battle,
effective maintenance and replacement of equipment, inventory
control, transportation and supply depots etc.
(iii) Industrial Establishment and Private Sector Units
OR can be effectively used in plant location and setting finance
planning, product and process planning, facility planning and
construction, production planning and control, purchasing, maintenance
management and personnel management etc. to name a few.

NOTES
OVERVIEW OF
OPERATIONS
RESEARCH
6
(iv) R & D and Engineering
Research and development being the heart of technological growth,
OR has wide scope for and can be applied in technology forecasting
and evaluation, technology and project management, preparation of
tender and negotiation, value engineering, work/method study and
so on.
(v) Business Management and Competition
OR can help in taking business decisions under risk and uncertainty,
capital investment and returns, business strategy formation, optimum
advertisement outlay, optimum sales force and their distribution,
market survey and analysis and market research techniques etc.
(vi) Agriculture and Irrigation
In the area of agriculture and irrigation also OR can be useful for
project management, construction of major dams at minimum cost,
optimum allocation of supply and collection points for fertilizer/seeds
and agriculture outputs and optimum mix of fertilizers for better yield.
(vii) Education and Training
OR can be used for obtaining optimum number of schools with their
locations, optimum mix of Students/teacher student ratio, optimum
financial outlay and other relevant information in training of graduates
to meet out the national requirements.
(viii) Transportation
Transportation models of OR can be applied to real life problems to
forecast public transport requirements, optimum routing, forecasting
of income and expenses, project management for railways, railway
network distribution, etc. In the same way it can be useful in the field
of communication.
(ix) Home Management and Budgeting
OR can be effectively used for control of expenses to maximize
savings, time management, work study methods for all related works.
Investment of surplus budget, appropriate insurance of life and
properties and estimate of depreciation and optimum premium of
insurance etc.Operations Research for
Managers

NOTES
Operations Research for
Managers
OVERVIEW OF
OPERATIONS
RESEARCH
7
1.6LIMITATIONS OF OPERATIONS RESEARCH
OR has some limitations however, these are related to the problem of model
building and the time and money factors involved in application rather than its
practical utility. Some of them are as follows:
(i) Magnitude of Computation.
Operations research models try to find out optimal solution taking into
account all the factors. These factors are enormous and expressing
them in quantity and establishing relationships among these require
voluminous calculations which can be handled by computers.
(ii) Non-Quantifiable Factors
OR provides solution only when all elements related to a problem can
be quantified. All relevant variables do not lend themselves to
quantification. Factors which cannot be quantified, find no place in
OR study. Models in OR do not take into account qualitative factors
or emotional factors which may be quite important.
(iii) Distance between User and Analyst
OR being specialist’s job requires a mathematician or statistician, who
might not be aware of the business problems. Similarly, a manager
fails to understand the complex working of OR. Thus there is a gap
between the two. Management itself may offer a lot of resistance due
to conventional thinking.
(iv) Time and Money Costs
When basic data are subjected to frequent changes, incorporating them
into the OR models is a costly proposition. Moreover, a fairly good
solution at present may be more desirable than a perfect OR solution
available after sometime. The computational time increases depending
upon the size of the problem and accuracy of results desired.
(v) Implementation
Implementation of any decision is a delicate task. It must take into
account the complexities of human relations and behavior. Sometimes,
resistance is offered due to psychological factors which may not have
any bearing on the problem as well as its solution.

NOTES
OVERVIEW OF
OPERATIONS
RESEARCH
8
1.7APPLICATIONS OF OPERATIONS RESEARCH
Today, almost all fields of business and government utilizing the benefits
of Operations Research. There are voluminous of applications of Operations
Research. Although it is not feasible to cover all applications of O.R. in brief.
The following are the abbreviated set of typical operations research applications
to show how widely these techniques are used today
1.Accounting
•Assigning audit teams effectively Credit policy analysis
•Cash flow planning
•Developing standard costs
•Establishing costs for byproducts
•Planning of delinquent account strategy
2.Construction
•Project scheduling, monitoring and control
•Determination of proper work force
•Deployment of work force
•Allocation of resources to projects.
3.Facilities Planning
•Factory location and size decision
•Estimation of number of facilities required
•Hospital planning
•Quantitative Techniques for Managers
•International logistic system design
•Transportation loading and unloading
•Warehouse location decision
4.Finance
•Building cash management models
•Allocating capital among various alternatives
•Building financial planning models
•Investment analysis
•Portfolio analysis
•Dividend policy making
Operations Research for
Managers

NOTES
Operations Research for
Managers
OVERVIEW OF
OPERATIONS
RESEARCH
9
4.Manufacturing
•Inventory control
•Marketing balance projection
•Production scheduling
•Production smoothing
5.Marketing
•Advertising budget allocation
•Product introduction timing
•Selection of Product mix
•Deciding most effective packaging alternative
6.Organizational Behavior / Human Resources
•Personnel planning
•Recruitment of employees
•Skill balancing
•Training program scheduling
•Designing organizational structure more effectively
7.Purchasing
•Optimal buying
•Optimal reordering
•Materials transfer
8.Research and Development
•R & D Projects control
•R & D Budget allocation
•Planning of Product introduction
1.8LATEST APPLICATIONS OF OPERATIONS RESEARCH
Following are the latest applications of Operations Research.
1.Capital budgeting.
2.Asset allocation.
3.Portfolio selection.
4.Fraud prevention,

NOTES
OVERVIEW OF
OPERATIONS
RESEARCH
10
5.Anti-Money Laundering.
6.Benchmarking.
7.Marketing channel optimization,
8.Customer segmentation.
9.Direct marketing campaigns,
10.Predicting customer response,
11.Campaign optimization.
12.Supply Chain Planning.
13.Distribution, Routing, Scheduling,
14.Traffic flow optimization.
15.Resource allocation,
16.Staff allocation.
17.Inventory planning.
18.Retail planning,
19.Merchandize optimization.
20.Product mix and blending,
21.Industrial waste reduction.
REFERENCES
1.http://mcehassan.ac.in
2.Operations Research. Second Edition P. Rama Murthy. New Age
International (P) Ltd
3.http://www.pondiuni.edu.in/storage/dde/downloads/mbaii_qt.pdf
4.https://www.pitt.edu/~jrclass/or/or-intro.html
5.Leachman, R. C., R. F. Benson, C. Liu and D. J. Raar, "IMPReSS: An
Automated Production-Planning and Delivery-Quotation System at
Harris Corporation - Semiconductor Sector," Interfaces, 26:1, pp. 6-
37, 1996.
6.Rigby, B., L. S. Lasdon and A. D. Waren, "The Evolution of Texaco's
Blending Systems: From OMEGA to StarBlend," Interfaces, 25:5, pp.
64-83, 1995.
7.Flanders, S. W. and W. J. Davis, "Scheduling a Flexible Manufacturing
System with Tooling Constraints: An Actual Case Study," Interfaces,
25:2, pp. 42-54, 1995.
8.Subramanian, R., R. P. Scheff, Jr., J. D. Quillinan, D. S. Wiper and R.
E. Marsten, "Coldstart: Fleet Assignment at Delta Air Lines,",
Interfaces, 24:1, pp. 104-120, 1994.
Operations Research for
Managers

NOTES
Operations Research for
Managers
OVERVIEW OF
OPERATIONS
RESEARCH
11
9.Kotha, S. K., M. P. Barnum and D. A. Bowen, "KeyCorp Service
Excellence Management System," Interfaces, 26:1, pp. 54-74, 1996.
EXERCISE
1.Trace the history of Operations Research.
2. Give a brief account of history of Operations Research.
3. "Operations Research is a bunch of mathematical techniques to break
industrial problems”. Critically comment.
4. Briefly explain the significance of Operations Research.
5. Discuss the scope of Operations Research.
6. State and explain the limitations of Operations Research
*****

NOTES
LINEAR PROGRAMMING
PROBLEM
12
UNIT - II
LINEAR PROGRAMMING
PROBLEM
CHAPTER OBJECTIVES
1.To familiarize the students with the components of LPP.
2.To familiarize the students with the formulation of LPP.
3.To develop the quantitative skills of the students to make them skilled
at using graphical method of solving LPP.
CONTENTS
2.1DEFINITION
2.2 COMPONENTS OF LPP
2.3FORMULATION OF LPP
2.4 SOLUTION OF LPP: GRAPHICAL METHOD OF SOLVING LPP
2.5 APPLICATIONA AND LIMITATIONS OF LPP
INTRODUCTION
Linear programming (LP) is one of the simplest ways to perform
optimization. It helps you solve some very complex optimization problems by
making a few simplifying assumptions. As an analyst you are bound to come
across applications and problems to be solved by Linear Programming
2.1DEFINITIONS OF LPP
Linear programming is a mathematical method that is used to determine the
best possible outcome or solution from a given set of parameters or list of
requirements, which are represented in the form of linear relationships. It is most
often used in computer modeling or simulation in order to find the best solution
in allocating finite resources such as money, energy, manpower, machine
resources, time, space and many other variables. In most cases, the "best
outcome" needed from linear programming is maximum profit or lowest cost.
Because of its nature, linear programming is also called linear optimization.
Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
13
Linear programming can be defined as: “A mathematical method to allocate
scarce resources to competing activities in an optimal manner when the problem
can be expressed using a linear objective function and linear inequality
constraints.”
A linear program consists of a set of variables, a linear objective function
indicating the contribution of each variable to the desired outcome, and a set of
linear constraints describing the limits on the values of the variables. The
“answer” to a linear program is a set of values for the problem variables that
results in the best — largest or smallest — value of the objective function and
yet is consistent with all the constraints. Formulation is the process of translating
a real-world problem into a linear program. Once a problem has been formulated
as a linear program, a computer program can be used to solve the problem. In
this regard, solving a linear program is relatively easy. The hardest part about
applying linear programming is formulating the problem and interpreting the
solution.
2.2 COMPONENTS OF LPP
1.Linear Equations
All of the equations and inequalities in a linear program must, by definition,
be linear. A linear function has the following form: a0 + a1 x1 + a2 x2 + a3 x3
+. . + anxn = 0----(where 1,2,3,---n as subscript.)
In general, the a’s are called the coefficients of the equation; they are also
sometimes called parameters. The important thing to know about the coefficients
is that they are fixed values, based on the underlying nature of the problem being
solved. The x’s are called the variables of the equation; they are allowed to take
on a range of values within the limits defined by the constraints. Note that it is
not necessary to always use x’s to represent variables; any label could be used,
and more descriptive labels are often more useful.
Linear equations and inequalities are often written using summation
notation, which makes it possible to write an equation in a much more compact
form. The linear equation above, for example, can be written as follows:
Note that the letter i is an index, or counter, that starts in this case at 1 and
runs to n. There is a term in the sum for each value of the index. Just as a variable
does not have to be specified with a letter x, the index does not have to be a letter
i. Summation notation will be used a lot in the rest of this chapter and in all of
the remaining chapters. You will need to become adept at interpreting it.
2.The Decision Variables
The variables in a linear program are a set of quantities that need to be
determined in order to solve the problem; i.e., the problem is solved when the

NOTES
LINEAR PROGRAMMING
PROBLEM
14
best values of the variables have been identified. The variables are sometimes
called decision variables because the problem is to decide what value each
variable should take. Typically, the variables represent the amount of a resource
to use or the level of some activity. For example, a variable might represent the
number of acres to cut from a particular part of the forest during a given period.
Frequently, defining the variables of the problem is one of the hardest and/or
most crucial steps in formulating a problem as a linear program. Sometimes
creative variable definition can be used to dramatically reduce the size of the
problem or make an otherwise non-linear problem linear.
As mentioned earlier, a variety of symbols, with subscripts and superscripts
as needed, can be used to represent the variables of an LP. As a general rule, it
is better to use variable names that help you remember what the variable
represents in the real world. For this general introduction, the variables will be
represented — very abstractly — as x1, x2, . . ., xn . (where 1, 2,….,n as
subscript.) (Note that there are n variables in this list.)
3.The Objective Function
The objective of a linear programming problem will be to maximize or to
minimize some numerical value. This value may be the expected net present
value of a project or a forest property; or it may be the cost of a project; it could
also be the amount of wood produced, the expected number of visitor-days at a
park, the number of endangered species that will be saved, or the amount of a
particular type of habitat to be maintained.
The objective function indicates how each variable contributes to the value
to be optimized in solving the problem. The objective function takes the
following general form:
where ci = the objective function coefficient corresponding to the ith
variable, and xi = the ith decision variable.
The coefficients of the objective function indicate the contribution to the
value of the objective function of one unit of the corresponding variable. For
example, if the objective function is to maximize the present value of a project,
and xi is the ith possible activity in the project, then ci (the objective function
coefficient corresponding to xi ) gives the net present value generated by one
unit of activity i. As another example, if the problem is to minimize the cost of
achieving some goal, xi might be the amount of resource i used in achieving the
goal. In this case, ci would be the cost of using one unit of resource i.
4.The Constraints
The constraints indicate limitations on the resources, which are to be
allocated among various decision variables. These resources may be production
capacity, manpower, time, space or machinery. These must be capable of being
expressed as linear equation (i.e. =) on inequalities (i.e. > or<; type) in terms of
decision variables. Thus, constraints of a linear programming problem are linear
equalities or inequalities arising out of practical limitations.
Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
15
5.The Non-Negativity Constraints
For technical reasons beyond the scope of this book, the variables of linear
programs must always take non-negative values (i.e., they must be greater than
or equal to zero). In most cases, where, for example, the variables might
represent the levels of a set of activities or the amounts of some resource used,
this non-negativity requirement will be reasonable – even necessary. In the rare
case where you actually want to allow a variable to take on a negative value there
are certain formulation “tricks” that can be employed. These “tricks” also are
beyond the scope of this class, however, and all of the variables we will use will
only need to take on non-negative values. In any case, the non-negativity
constraints are part of all LP formulations, and you should always include them
in an LP formulation. They are written as follows:
xi ≠ 0 i = 1, 2, . . ., n
where xi = the ith decision variable.
6.Feasible Solution
Any solution to graphical method of L.P.P. which satisfies the non-
negativity restrictions of the problem is called a feasible solution to a general
L.P.P.
7.Optimum solution
Any feasible solution to graphical method of L.P.P. which optimizes
(maximizes/ minimizes) the objective function of L.P.P. is called an optimum
solution to the L.L.P.
2.3 FORMULATION OF LPP
It consists the following steps
Step 1.Identify decision variables
Step 2. Write objective function
Step 3. Formulate constraints
For the formulation of LPP consider the following example of furniture
dealer.
A furniture dealer deals in only two items–tables and chairs. He has Rs
50,000 to invest and has storage space of at most 60 pieces. A table costs Rs 2500
and a chair Rs 500. He estimates that from the sale of one table, he can make a
profit of Rs 250 and that from the sale of one chair a profit of Rs 75. He wants
to know how many tables and chairs he should buy from the available money so
as to maximize his total profit, assuming that he can sell all the items which he
buys.

NOTES
LINEAR PROGRAMMING
PROBLEM
16
In this example, we observe the following
(i) The dealer can invest his money in buying tables or chairs or
combination thereof. Further he would earn different profits by
following different investment strategies.
(ii) There are certain overriding conditions or constraints viz., his
investment is limited to a maximum of Rs 50,000 and so is his storage
space which is for a maximum of 60 pieces.
Situation 1
Suppose he decides to buy tables only and no chairs, so he can buy 50000
÷ 2500, i.e., 20 tables. His profit in this case will be Rs (250 × 20), i.e., Rs 5000.
Situation 2
Suppose he chooses to buy chairs only and no tables. With his capital of Rs
50,000, he can buy 50000 ÷ 500, i.e. 100 chairs.
But he can store only 60 pieces. Therefore, he is forced to buy only 60 chairs
which will give him a total profit of Rs (60 × 75), i.e., Rs 4500.
There are many other possibilities, for instance, he may choose to buy 10
tables and 50 chairs, as he can store only 60 pieces. Total profit in this case would
be Rs (10 × 250 + 50 × 75), i.e., Rs 6250 and so on.
We, thus, find that the dealer can invest his money in different ways and he
would earn different profits by following different investment strategies. Now
the problem is: How should he invest his money in order to get maximum profit?
To answer this question, let us try to formulate the problem mathematically
Mathematical formulation of the problem
Let x be the number of tables and y be the number of chairs that the dealer
buys. Obviously, x and y must be non-negative,
i.e., x, ≥ 0 ... (1) (Non-negative constraint)
y ≥ 0 … (2) (Non-negative constraint)
The dealer is constrained by the maximum amount he can invest (Here it
is Rs 50,000) and by the maximum number of items he can store (Here it is 60).
Stated mathematically,
2500x + 500y ≤ 50000
or 5x + y ≤ 100 ... (3) (investment constraint)
andx + y ≤ 60 ...(4)(storage constraint)
The dealer wants to invest in such a way so as to maximize his profit, say,
Z which stated as a function of x and y is given by
Z = 250x + 75y... (5) (objective function)
Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
17
Mathematically, the given problems now reduce to:
Maximize Z = 250x + 75y
subject to the constraints:
5x + y ≤ 100
x + y ≤ 60
x ≥ 0, y ≥ 0
So, we have to maximize the linear function Z subject to certain conditions
determined by a set of linear inequalities with variables as non-negative.
We have to consider the following conditions
•Objective function: Z = ax + by, where a, b are constants, which has to
be maximized or minimized is called a linear objective function.
In the above example, Z = 250x + 75y is a linear objective function.
•Decision Variables: Variables x and y are called decision variables.
•Constraints:The linear inequalities or equations or restrictions on the
variables of a linear programming problem are called constraints. The
conditions x ≥ 0, y ≥ 0 are called non-negative restrictions.
In the above example, the set of inequalities (1) to (4) are constraints.
Example 2. A firm produces three products. These products are processed
on three different machines. The time required to manufacture one unit of each
of the three products and the daily capacity of the three machines are given in
the table below:
It is required to determine the daily number of units to be manufactured for
each product. The profit per unit for product 1, 2 and 3 is Rs. 4, Rs.3 and Rs.6
respectively. It is assumed that all the amounts produced are consumed in the market.
Formulate the mathematical (L.P.) model that will maximize the daily profit.
Formulation of Linear Programming Model
Step 1:From the study of the situation find the key-decision to be made. In
the given situation key decision is to decide the extent of products 1, 2 and 3, as
the extents are permitted to vary.

NOTES
LINEAR PROGRAMMING
PROBLEM
18
Step 2: Assume symbols for variable quantities noticed in step 1. Let the
extents (amounts) of products 1, 2 and 3 manufactured daily be x1, x2 and x3
units respectively.
Step 3: Express the feasible alternatives mathematically in terms of
variable. Feasible alternatives are those which are physically, economically and
financially possible. In the given situation feasible alternatives are sets of values
of x1, x2 and x3 units respectively.
Where, X1, X2 and X3 ≥ 0.
since negative production has no meaning and is not feasible.
Step 4: Mention the objective function quantitatively and express it as a
linear function of variables. In the present situation, objective is to maximize the
profit.
i.e., Maximize Z = 4X1+ 3X2 + 6X3
Step 5: Put into words the influencing factors or constraints. These occur
generally because of constraints on availability (resources) or requirements
(demands). Express these constraints also as linear equations/inequalities in terms
of variables. Here, constraints are on the machine capacities and can be
mathematically expressed as,
Maximize Z = 4X1+ 3X2 + 6X3
Subject to the constraints:
2X1+ 3X2 + 2X3 ≤ 440
4X1+ 0X2 + 3X3 ≤ 470
2X1+ 5X2 + 0X3 ≤ 430
Example 3: A factory manufactures two products Table (A) and Chairs (B).
For manufacturing one unit of A, 15 machine hours and 25 labour hours are
required. For manufacturing product B, 25 machine hours and 15 labour hours
are required. In a month, 300 machine hours and 240 labour hours are available.
Profit per unit for A is Rs. 50 and for B is Rs. 40. Formulate as LPP to maximize
the profit.Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
19
Solution: Formulation of LPP
1. The objective is to maximize the total profit by selling units of
Table(X) and Chair(Y) which are produced under the given production
machine and labour constraints.
2.Decision Variables
Let X1 be the total units of table to be manufactured.
and X2 be the total units of chair to be manufactured.
3.Objective function: Total Profit (Z = 50X1 + 40X2) must be maximized.
Thus,
Maximize P= 50X1 + 40X2 is the objective function.
4.Constraints
(i) Machine Constraints: Total hours available for machine (i.e. 15X1+
25X2 must be less than or equal to the time available i.e. 300 hours. Thus,
15X1+ 25X2 ≤ 300
(ii) Labour Constraints: Total hours available for labour (i.e. 25X1+
15X2must be less than or equal to the time available i.e. 240 hours. Thus,
25X1+ 15X2 ≤ 240
Thus the LPP format is,
Maximize Z = 50X1+ 40X2
Subject to the constraints:
15X1+ 25X2 ≤ 300
25X1+ 15X2 ≤ 240
x ≥ 0, y ≥ 0
2.4 SOLUTION OF LPP: GRAPHICAL SOLUTION OF LPP
The steps involved in Graphical method of solving a LPP
Step 1. Formulate the linear programming problem.
Step 2. Graph the feasible region and ﬁnd the corner points. The coordinates
of the corner points can be obtained by either inspection or by solving the two
equations of the lines intersecting at that point.
Step 3. Make a table listing the value of the objective function at each corner
point.
Step 4. Determine the optimal solution from the table in step 3.

NOTES
LINEAR PROGRAMMING
PROBLEM
20
If the problem is of maximization (minimization) type, the solution
corresponding to the largest (smallest) value of the objective function is the
optimal solution of the LPP.
Graphical Solution for the problem of Maximization
Example 1
Maximize Z = 250x + 75y
subject to the constraints:
5x + y ≤ 100
x + y ≤ 60
x ≥ 0, y ≥ 0
We will now solve this problem graphically. Let us graph the constraints
stated as linear inequalities: 5x + y ≤ 100 ... (1)
x + y ≤ 60 ... (2)
x ≥ 0 ... (3)
y ≥ 0 ... (4)
Step I: Convert the given inequalities into equalities:
5x + y = 100 ...(1)
x + y = 60 ...(2)
x = 0 ... (3)
y = 0 ... (4)
Step II:To find the coordinates of each line equation.
Consider
5x + y = 100 ...(1)
Let us consider y = 0
5x = 100
x = 100 / 5
x = 20
Now, let us consider x = 0
y = 100
Therefore, the coordinates of the line 5x + y = 100 are (20, 100)
Consider
x + y = 60 ...(2)
Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
21
Let us consider y = 0
x = 60
Now, let us consider x = 0
y = 60
Therefore, the coordinates of the line 5x + y = 100 are (60, 60)
Step III: To plot a graph.
Step IV: To find the common feasible region.
The graph of this system (shaded region) consists of the points common to
all half planes determined by the inequalities. Each point in this region represents
a feasible choice open to the dealer for investing in tables and chairs. The region,
therefore, is called the feasible region for the problem. Every point of this region
is called a feasible solution to the problem. Thus, we have, Feasible region The
common region determined by all the constraints including non-negative
constraints x, y ≥ 0 of a linear programming problem is called the feasible region
(or solution region) for the problem. In above figure the region OAED (shaded)
is the feasible region for the problem. The region other than feasible region is
called an infeasible region.
Feasible solutions point within and on the boundary of the feasible region
represent feasible solutions of the constraints. In the fig, every point within and
on the boundary of the feasible region OAED represents feasible solution to the
problem. For example, the point (10, 50) is a feasible solution of the problem
and so are the points(0, 60), (20, 0) etc.

NOTES
LINEAR PROGRAMMING
PROBLEM
22
Any point outside the feasible region is called an infeasible solution. For
example, the point (60, 0) and the point (0, 100) are infeasible solutions ofthe
problem.
Therefore, the common feasible region is OAED
Step V:Optimum solution
Any point in the feasible region that gives the optimal value (maximum or
minimum) of the objective function is called an optimal solution. Now, we see
that every point in the feasible region OAED satisfies all the constraints as given
in (1) to (4), and since there are infinitely many points, it is not evident how we
should go about finding a point that gives a maximum value of the objective
function Z = 250x + 75y. To handle this situation, we use the following theorems
which are fundamental in solving linear programming problems.
Hence the optimal solution is,
Maximize Z = 6250
X1 = 10
X2 = 50
The maximum profit to the dealer i.e. Rs 6250 results from the investment
strategy (10, 50), i.e. buying 10 tables and 50 chairs.
Theorem 1: Let R be the feasible region (convex polygon) for a linear
programming problem and let Z = ax + by be the objective function. When Z has
an optimal value (maximum or minimum), where the variables x and y are subject
to constraints described by linear inequalities, this optimal value must occur at a
corner point* (vertex) of the feasible region.
Theorem 2: Let R be the feasible region for a linear programming problem,
and let Z = ax + by be the objective function. If R is bounded**, then the
objective function Z has both a maximum and a minimum value on R and each
of these occurs at a corner point (vertex) of R.
Remark: If R is unbounded, then a maximum or a minimum value of the
objective function may not exist. However, if it exists, it must occur at a corner
point of R. (By Theorem 1). In the above example, the corner points (vertices)
of the bounded (feasible) region are: O, A, B and C and it is easy to find their
coordinates as (0, 0), (20, 0), (10, 50) and (0, 60) respectively. Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
23
Example 2
Maximize Z = 100x + 250y
subject to the constraints:
5x + 10y ≤ 2500
2x + 10y ≤ 1000
x + 2y ≤ 4000
x ≥ 0, y ≥ 0
We will now solve this problem graphically. Let us graph the constraints
stated as linear inequalities:
5x + 10y ≤ 2500 ... (1)
2x + 10y ≤ 1000 ...(2)
x + 2y ≤ 4000 ...(3)
x, y ≥ 0 ... (4)
Step I: Convert the given inequalities into equalities:
5x + 10y = 2500 ... (1)
2x + 10y =1000 ...(2)
x + 2y = 4000 ...(3)
x, y = 0 ... (4)
Step II: To find the coordinates of each line equation.
Consider
5x + 10y = 2500...(1)
Let us consider y = 0
5x = 2500
x = 2500 / 5
x = 500
Now, let us consider x = 0
10y = 2500
y = 2500 / 10
y = 250
Therefore, the coordinates of the line 5x + 10y = 2500 are (500, 250)
Consider
2x + 10y =1000 ...(2)

NOTES
LINEAR PROGRAMMING
PROBLEM
24
Let us consider y = 0
2x = 1000
x = 1000 / 2
x = 500
Now, let us consider x = 0
10y = 1000
y = 1000 / 10
y = 100
Therefore, the coordinates of the line 2x + 10y =1000 are (500, 100)
Consider
x + 2y = 4000 ... (3)
Let us consider y = 0
x = 4000
Now, let us consider x = 0
2y = 4000
y = 4000 / 2
y = 2000
Therefore, the coordinates of the line x + 2y = 4000 are (4000, 2000)
Step III: To plot a graph.Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
25
Step IV: To find the common feasible region.
The common feasible region is OACD
Step V: Optimum solution
Here are multiple solutions but the coordinates of the line are same.
Max Z = Rs 5000
x = 500
y = 100
Example 3
Maximize Z = 30x + 50y
subject to the constraints:
2x + 10y ≤ 500
4x + 5y ≤ 200
3x + y ≤ 300
x ≥ 0, y ≥ 0
We will now solve this problem graphically. Let us graph the constraints
stated as linear inequalities:
2x + 10y ≤ 500 ... (1)
4x + 5y ≤ 200 ...(2)
3x + y ≤ 300 ...(3)
x, y ≥ 0 ... (4)
Step I:Convert the given inequalities into equalities:
2x + 10y = 500 ... (1)
4x + 5y =200 ...(2)
3x + y = 300 ...(3)
x, y ≥ 0 ... (4)

NOTES
LINEAR PROGRAMMING
PROBLEM
26
Step II: To find the coordinates of each line equation.
Consider
2x + 10y = 500 ...... (1)
Let us consider y = 0
2x = 500
x = 500 / 2
x = 250
Now, let us consider x = 0
10y = 500
y = 500 / 10
y = 50
Therefore, the coordinates of the line 2x + 10y = 500are (250, 50)
Consider
4x + 5y =200 ...(2)
Let us consider y = 0
4x = 200
x = 200 / 4
x = 50
Now, let us consider x = 0
5y = 200
y = 200 / 5
y = 20
Therefore, the coordinates of the line 4x + 5y =200 are (50, 20)
Consider
3x + y = 300 ... (3)
Let us consider y = 0
3x = 300
x = 300 / 3
x = 100
Now, let us consider x = 0
y = 300
Therefore, the coordinates of the line 3x + y = 300 are (100, 300)Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
27
Step III: To plot a graph.
Step IV: To find the common feasible region.
The common feasible region is OCD
Step V:Optimum solution
Here are multiple solutions but the coordinates of the line are same.
Max Z = Rs. 1500
x = 50
y = 0
Examples on minimization
Example 4
Minimize Z = 40x + 20y
subject to the constraints:
2x + 5y ≥ 500
10x + 4y ≥200
x + y ≥300
x ≥ 0, y ≥ 0

NOTES
LINEAR PROGRAMMING
PROBLEM
28
Step I: Convert the given inequalities into equalities:
2x + 5y = 500 ... (1)
10x + 4y =200 ...(2)
x + y = 300 ...(3)
x, y ≥ 0 ... (4)
Step II: To find the coordinates of each line equation.
Consider
2x + 5y = 500 ...... (1)
Let us consider y = 0
2x = 500
x = 500 / 2
x = 250
Now, let us consider x = 0
5y = 500
y = 500 / 5
y = 100
Therefore, the coordinates of the line 2x + 5y = 500are (250, 100)
Consider
10x + 4y =200 ...(2)
Let us consider y = 0
10x = 200
x = 200 / 10
x = 20
Now, let us consider x = 0
4y = 200
y = 200 / 4
y = 50
Therefore, the coordinates of the line 10x + 4y =200 are (20, 50)
Consider
x + y = 300 ... (3)
Let us consider y = 0
x = 300Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
29
Now, let us consider x = 0
y = 300
Therefore, the coordinates of the line x + y = 300 are (300, 300)
Step III:To plot a graph
Step IV: To find the common feasible region
The common feasible region is EF
Step V: Feasible solution:
In above table the minimum cost is Rs 9000. The objective function is to
minimize the total cost.
Hence,
Minimum Z = 9000
X = 300
Y = 0
Example 5
Minimize Z = 4x + 2y
Subject to : x + 2y ≥ 200
3x + y ≥ 300
4x + 3y ≥ 600
x ≥ 0 , y ≥ 0

NOTES
LINEAR PROGRAMMING
PROBLEM
30
Step I: Convert the given inequalities into equalities:
x + 2y = 200 ... (1)
3x + y =300...(2)
4x + 3y = 600 ...(3)
x, y ≥ 0 ... (4)
Step II:To find the coordinates of each line equation.
Consider
x + 2y = 200 ...... (1)
Let us consider y = 0
x = 200
Now, let us consider x = 0
2y = 200
y = 200 / 2
y = 100
Therefore, the coordinates of the line 2x + 5y = 500are (200, 100)
Consider
3x + y =300 ...(2)
Let us consider y = 0
3x = 300
x = 300 / 3
x = 100
Now, let us consider x = 0
y = 300
Therefore, the coordinates of the line 3x + y =300 are (100, 300)
Consider
4x + 3y = 600 ... (3)
Let us consider y = 0
4x = 600
x = 600 / 4
x = 150
Now, let us consider x = 0
3y = 600Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
31
y = 600 / 3
y = 200
Therefore, the coordinates of the line 4x + 3y = 600 are (150, 200)
Step III: To plot a graph
Step IV: To find the common feasible region
The common feasible region is DA
Step V: Feasible solution:
In above table the minimum cost is Rs 600. The objective function is to
minimize the total cost.
Hence,
Minimum Z = 600
X = 0
Y = 300

NOTES
LINEAR PROGRAMMING
PROBLEM
32
2.6APPLICATIONA AND LIMITATIONS OF LPP
APPLICATIONS OF LPP
1.Food and Agriculture
Farmers apply linear programming techniques to their work. By
determining what crops they should grow, the quantity of it and how
to use it efficiently, farmers can increase their revenue.
In nutrition, linear programming provides a powerful tool to aid in
planning for dietary needs. In order to provide healthy, low-cost food
baskets for needy families, nutritionists can use linear programming.
Constraints may include dietary guidelines, nutrient guidance, cultural
acceptability or some combination thereof. Mathematical modeling
provides assistance to calculate the foods needed to provide nutrition
at low cost, in order to prevent no communicable disease. Unprocessed
food data and prices are needed for such calculations, all while
respecting the cultural aspects of the food types. The objective function
is the total cost of the food basket. Linear programming also allows
time variations for the frequency of making such food baskets.
2.Applications in Engineering
Engineers also use linear programming to help solve design and
manufacturing problems. For example, in airfoil meshes, engineers
seek aerodynamic shape optimization. This allows for the reduction
of the drag coefficient of the airfoil. Constraints may include lift
coefficient, relative maximum thickness, nose radius and trailing edge
angle. Shape optimization seeks to make a shock-free airfoil with a
feasible shape. Linear programming therefore provides engineers with
an essential tool in shape optimization.
3.Transportation Optimization
Transportation systems rely upon linear programming for cost and time
efficiency. Bus and train routes must factor in scheduling, travel time
and passengers. Airlines use linear programming to optimize their
profits according to different seat prices and customer demand.
Airlines also use linear programming for pilot scheduling and routes.
Optimization via linear programming increases airlines' efficiency and
decreases expenses.
4.Efficient Manufacturing
Manufacturing requires transforming raw materials into products that
maximize company revenue. Each step of the manufacturing process
Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
33
must work efficiently to reach that goal. For example, raw materials
must past through various machines for set amounts of time in an
assembly line. To maximize profit, a company can use a linear
expression of how much raw material to use. Constraints include the
time spent on each machine. Any machines creating bottlenecks must
be addressed. The amount of products made may be affected, in order
to maximize profit based on the raw materials and the time needed.
5.Energy Industry
Modern energy grid systems incorporate not only traditional electrical
systems, but also renewables such as wind and solar photovoltaics. In
order to optimize the electric load requirements, generators,
transmission and distribution lines, and storage must be taken into
account. At the same time, costs must remain sustainable for profits.
Linear programming provides a method to optimize the electric power
system design. It allows for matching the electric load in the shortest
total distance between generation of the electricity and its demand over
time. Linear programming can be used to optimize load-matching or
to optimize cost, providing a valuable tool to the energy industry.
LIMITATIONS OF LPP
1.Linearity of relations
A primary requirement of linear programming is that the objective
function and every constraint must be linear. However, in real life
situations, several business and industrial problems are nonlinear in
nature.
2.Single objective
Linear programming takes into account a single objective only, i.e.,
profit maximization or cost minimization. However, in today's
dynamic business environment, there is no single universal objective
for all organizations.
3.Certainty
Linear Programming assumes that the values of co-efficient of decision
variables are known with certainty. Due to this restrictive assumption,
linear programming cannot be applied to a wide variety of problems
where values of the coefficients are probabilistic
4.Constant parameters
Parameters appearing in LP are assumed to be constant, but in practical
situations it is not so.

NOTES
LINEAR PROGRAMMING
PROBLEM
34
5.Divisibility
In linear programming, the decision variables are allowed to take non-
negative integer as well as fractional values. However, we quite often
face situations where the planning models contain integer valued
variables. For instance, trucks in a fleet, generators in a powerhouse,
pieces of equipment, investment alternatives and there are myriad of
other examples. Rounding off the solution to the nearest integer will
not yield an optimal solution. In such cases, linear programming
techniques cannot be used.
EXERCISE
Use the graphical method to solve each of the following LP problems.
1.A wheat and barley farmer has 168 hectare of ploughed land, and a
capital of Rs.2000. It costs E14 to sow one-hectare wheat and Rs.10
to sow one hectare of barley. Suppose that his proﬁt is E80 per hectare
of wheat and Rs.55 per hectare of barley. Find the optimal number of
hectares of wheat and barley that must be ploughed in order to
maximize proﬁt? What is the maximum proﬁt?
2. An company manufactures two electrical products: air conditioners
and large fans. The assembly process for each is similar in that both
require a certain amount of wiring and drilling. Each air conditioner
takes 3 hours of wiring and 2 hours of drilling. Each fan must go
through 2 hours of wiring and 1 hour of drilling. During the next
production period, 240 hours of wiring time are available and up to
140 hours of drilling time may be used. Each air conditioner sold yields
a proﬁt of Rs.25. Each fan assembled may be sold for a proﬁt of Rs.15.
Formulate and solve this linear programming mix situation to ﬁnd the
best combination of air conditioners and fans that yields the highest
proﬁt.
3. A manufacturer of lightweight mountain tents makes a standard model
and an expedition model for national distribution. Each standard tent
requires 1 labour hour from the cutting department and 3 labour hours
from the assembly department. Each expedition tent requires 2 labour
hours from the cutting department and 4 labour hours from the
assembly department. The maximum labour hours available per day
in the cutting department and the assembly department are 32 and 84
respectively. If the company makes a proﬁt ofRs. 50 on each standard
tent andRs. 80 on each expedition tent, use the graphical method to
determine how many tents of each type should be manufactured each
day to maximize the total daily proﬁt?
4. A manufacturing plant makes two types of inﬂatable boats, a two-
person boat and a four-person boat. Each two-person boat requires 0.9
labour hours from the cutting department and 0.8 labour hours from
Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
35
the assembly department. Each four-person boat requires 1.8 labour
hours from the cutting department and 1.2 labour hours from the
assembly department. The maximum labour hours available per month
in the cutting department and the assembly department are 864 and
672 respectively. The company makes a proﬁt of Rs.25 on each two-
person boat andRs. 40 on each four-person boat. Use the graphical
method to ﬁnd the maximum proﬁt.
5.Harsh Engineering produces chairs and tables. Each table takes four
hours of labour from the carpentry department and two hours of labour
from the ﬁnishing department. Each chair requires three hours of
carpentry and one hour of ﬁnishing. During the current week, 240
hours of carpentry time are available and 100 hours of ﬁnishing time.
Each table produced gives a proﬁt of Rs.70 and each chair a proﬁt of
Rs.50. How many chairs and tables should be made in order to
maximize proﬁt?
6. A company manufactures two products X and Y. Each product has to
be processed in three departments: welding, assembly and painting.
Each unit of X spends 2 hours in the welding department, 3 hours in
assembly and 1 hour in painting. The corresponding times for a unit
of Y are 3,2 and 1 respectively. The man-hours available in a month
are 1500 for the welding department, 1500 in assembly and 550 in
painting. The contribution to proﬁts and ﬁxed overheads areRs. 100
for product X and Rs.120 for product Y. Formulate the appropriate
linear programming problem and solve it graphically to obtain the
optimal solution for the maximum contribution.
7. Suppose a manufacturer of printed circuits has a stock of 200 resistors,
120 transistors and 150 capacitors and is required to produce two types
of circuits. Type A requires 20 resistors, 10 transistors and 10
capacitors. Type B requires 10 resistors, 20 transistors and 30
capacitors. If the proﬁt on type A circuits isRs. 5 and that on type B
circuits isRs. 12, how many of each circuit should be produced in order
to maximize proﬁt?
8. A small company builds two types of garden chairs. Type A requires
2 hours of machine time and 5 hours of craftsman time. Type B
requires 3 hours of machine time and 5 hours of craftsman time. Each
day there are 30 hours of machine time available and 60 hours of
craftsman time. The proﬁt on each type A chair isRs. 60 and on each
type B chair isRs. 84. Formulate the appropriate linear programming
problem and solve it graphically to obtain the optimal solution that
maximizes proﬁt.
9. Sheetal sales produces two gift packages of fruit. Package A contains
20 peaches, 15 apples and 10 pears. Package B contains 10 peaches,
30 apples and 12 pears.Sheetal sales has 40 000 peaches, 60 000 apples

NOTES
LINEAR PROGRAMMING
PROBLEM
36
and 27 000 pears available for packaging. The proﬁt on package A
isRs. 2.00 and the proﬁt on B is Rs.2.50. Assuming that all fruit
packaged can be sold, what number of packages of types A and B
should be prepared to maximize the proﬁt?
10. A factory manufactures two products, each requiring the use of three
machines. The ﬁrst machine can be used at most 70 hours; the second
machine at most 40 hours; and the third machine at most 90 hours.
The ﬁrst product requires 2 hours on Machine 1, 1 hour on Machine
2, and 1 hour on Machine 3; the second product requires 1 hour each
on machines 1and 2 and 3 hours on Machine 3. If the proﬁt inRs. 40
per unit for the ﬁrst product andRs. 60 per unit for the second product,
how many units of each product should be manufactured to maximize
proﬁt?
Minimization problems
1. A house wife wishes to mix together two kinds of food, I and II, in such
a way that the mixture contains at least 10 units of vitamin A, 12 units of vitamin
B and 8 units of vitamin C. The vitamin contents of one kg of food is given
below;
Vitamin A Vitamin B Vitamin C Food I 1 2 3 Food II 2 2 1
One Kg of food I costs E6 and one Kg of food II costs E10. Formulate the
above problem as a linear programming problem and ﬁnd the least cost of the
mixture which will produce the diet.
1.A chicken farmer can buy a special food mix A at 20c per Kg and
special food mix B at 40c per Kg. Each Kg of mix A contains 3000
units of nutrient N1 and 1000 units of nutrient N2; each Kg of mix B
contains 4000 units of nutrient N1 and 4000 units of nutrient N2. If
the minimum daily requirements for the chickens collectively are
36000 units of nutrient N1 and 20000 units of nutrient N2, how many
pounds of each food mix should be used each day to minimize daily
food costs while meeting (or exceeding) the minimum daily nutrient
requirements? What is the minimum daily cost?
2.A farmer can buy two types of plant food, mix A and mix B. Each
cubic metre of mix A contains 20 kg of phosphoric acid, 30 kg of
nitrogen, and 5 kg of potash. Each cubic metre of mix B contains 10
kg of phosphoric acid, 30 kg of nitrogen and 10 kg of potash. The
minimum monthly requirements are 460 kg of phosphoric acid, 960
kg of nitrogen, and 220 kg of potash. If mix A costs Rs.30 per cubic
metre and mix B costs Rs.35 per cubic metre, how many cubic metres
of each mix should the farmer blend to meet the minimum monthly
requirements at a minimal cost? What is the cost?
3. A city council voted to conduct a study on inner-city community
problems. A nearby university was contacted to provide sociologists
Operations Research for
Managers

NOTES
Operations Research for
Managers
LINEAR PROGRAMMING
PROBLEM
37
and research assistants. Allocation of time and costs per week are given
in the table. How many sociologists and how many research assistants
should be hired to minimize the cost and meet the weekly labour-hour
requirements? What is the weekly cost?
Labour hours minimum labourresearch hours needed sociologist
assistant per week fieldwork 10 30 180 research centre 30 10 140 costs
per week Rs. 500 300
4. A laboratory technician in a medical research centre is asked to
formulate a diet from two commercially packaged foods, food A and
food B, for a group of animals. Each kg of food A contains 8 units of
fat, 16 units of carbohydrates, and 2 units of protein. Each Kg of food
B contains 4 units of fat, 32 units of carbohydrate and 8 units of
protein. The minimum daily requirements are 176 units of fat, 1024
units of carbohydrate, and 384 units of protein. Iffood A costs 5Rs per
Kg and food B costs 5Rs per Kg, how many kilograms of each food
should be used to meet the minimum daily requirements at the least
cost? What is the cost of this amount?
5. A can of cat food, guaranteed by the manufacturer to contain at least
10 units of protein, 20 units of mineral matter, and 6 units of fat,
consists of a mixture of four dierent ingredients. Ingredient A contains
10 units of protein, 2 units of mineral matter, and 1 2 unit of fat per
100g. Ingredient B contains 1 unit of protein, 40 units of mineral
matter, and 3 units of fat per 100g. Ingredient C contains 1 unit of
protein, 1 unit of mineral matter, and 6 units of fat per 100g. Ingredient
D contains 5 units of protein, 10 units of mineral matter, and 3 units
of fat per 100g. The cost of each ingredient is 3Rs, 2Rs, 1Rs, and 4Rs
per 100g, respectively. How many grams of each should be used to
minimize the cost of the cat food, while still meeting the guaranteed
composition?
REFERENCES
1.ncert.nic.in
2.http://mcehassan.ac.in
3.Operations Research. Second Edition P. Rama Murthy. New Age
International (P) Ltd
4.https://sciencing.com

NOTES
TRANSPORTATION
PROBLEM (TP)
38
UNIT - III
TRANSPORTATION
PROBLEM (TP)
CHAPTER OBJECTIVES
1.To equip students with fundamentals of Transportation Problem.
2.To acquaint the students with initial basic feasible solution of
Transportation Problem.
3.To enable the students to understand optimal solution of Transportation
Problem.
CHAPTER CONTENTS
a)Introduction and Formulation of TP.
b)Initial Basic Feasible Solution (North West Corner Rule)
c)Matrix Minimum Method
d)Vogel’s Approximation Method - VAM)
e)Checking for Optimality, Moving towards optimality, finding optimal
solution
f)Special cases- TP for maximization
g)Uunbalanced TP, restricted TP, Multiple /Optimal Solutions, Business
Applications
OVERVIEW OF THE CHAPTER
This chapter deals with In detail study of Transportation Problem and its
various concepts. It includes Meaning of terms initial basic feasible solution,
optimal solution etc. Special cases in Transportation Problem are also discussed
in this topic.
KEY WORDS
Transportation Problem, initial basic feasible solution, optimal solution.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
39
3.1 INTRODUCTION
The transportation problem is a special type of linear programming problem,
where the objective is to minimize the cost of distributing a product from a
number of sources to a number of destinations.
3.2 TRANSPORTATION PROBLEM - BUSINESS APPLICATIONS
Because of the special structure of the Transportation Problem the Simplex
Method of solving is unsuitable for the Transportation Problem. The model
assumes that the distributing cost on a given rout is directly proportional to the
number of units distributed on that route. Generally, the transportation model can
be extended to areas other than the direct transportation of a commodity,
including among others, inventory control, employment scheduling, and
personnel assignment.
Suppose a manufacturing company owns three factories (sources) and
distribute his products to five different retail agencies (destinations). The
following table shows the capacities of the three factories, the quantity of
products required by the various retail agencies and the cost of shipping one unit
of the product from each of the three factories to each of the five retail agencies.
Usually the above table is referred as Transportation Table, which provides
the basic information regarding the transportation problem. The quantities inside
the table are known as transportation cost per unit of product. The capacity of
the factories 1, 2, 3 is 50, 100 and 150 respectively. The requirement of the retail
agency 1, 2, 3, 4, 5 is 100,60,50,50, and 40 respectively.In this case, the
transportation cost of one unit from factory 1 to retail agency 1 is 1,from factory
1 to retail agency 2 is 9,from factory 1 to retail agency 3 is 13, and so on.
A transportation problem can be formulated as linear programming problem
using variables with two subscripts.

NOTES
TRANSPORTATION
PROBLEM (TP)
40
Let
x11=Amount to be transported from factory 1 to retail agency 1
x12= Amount to be transported from factory 1 to retail agency 2
……..
……..
……..
……..
x35= Amount to be transported from factory 3 to retail agency 5.
Let the transportation cost per unit be represented by C11, C12, …..C35
that is C11=1, C12=9, and so on.
Let the capacities of the three factories be represented by a1=50, a2=100,
a3=150.
Let the requirement of the retail agencies are b1=100, b2=60, b3=50, b4=50,
and b5=40. Thus, the problem can be formulated as
Minimize
C11x11+C12x12+……………+C35x35
Subject to:
Thus, the problem has 8 constraints and 15 variables. So, it is not possible
to solve such a problem using simplex method. This is the reason for the need of
special computational procedure to solve transportation problem.Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
41
3.3 MATHEMATICAL FORMULATION OF
TRANSPORTATION PROBLEM
Mathematically a transportation problem is nothing but a special linear
programming problem in which the objective function is to minimize the cost of
transportation subjected to the demand and supply constraints.
The transportation problem applies to situations where a single commodity
is to be transported from various sources of supply (origins) to various demands
(destinations). Let there be m sources of supply s
1, s2, .…..............sm having ai (
i = 1,2,......m) units of supplies respectively to be transported among n
destinations d
1, d2………d nwith b j( j = 1,2…..n) units of requirements
respectively.
Let cij be the cost for shipping one unit of the commodity from source i, to
destination j for each route. If xij represents the units shipped per route from
source i, to destination j, then the problem is to determine the transportation
schedule which minimizes the total transportation cost of satisfying supply and
demand conditions.
The transportation problem can be stated mathematically as a linear
programming problem as below:
3.4 TRANSPORTATION ALGORITHM
The steps of the transportation algorithm are exact parallels of the simplex
algorithm, they are:

NOTES
TRANSPORTATION
PROBLEM (TP)
42
Step 1: Determine a starting basic feasible solution, using any one of the
following three methods
1.North West Corner Method
2.Least Cost Method
3.Vogel Approximation Method
Step 2: Determine the optimal solution using the following method:
MODI (Modified Distribution Method) or UV Method.
3.5 INITIAL BASIC FEASIBLE SOLUTION OF A
TRANSPORTATION PROBLEM
The computation of an initial feasible solution is illustrated in this section
with the help of the example1.1 discussed in the previous section. The problem
in the example 1.1 has 8 constraints and 15 variables we can eliminate one of
the constraints since a
1+ a2+ a3= b1+ b2+ b3+ b4+b5. Thus now the problem
contains 7 constraints and 15 variables.
Note that any initial (basic) feasible solution has at most 7 non-zero X
ij.
Generally, any basic feasible solution with m sources (such as factories) and n
destination (such as retail agency) has at most m + n -1 non-zero X
ij.
The special structure of the transportation problem allows securing a non
artificial basic feasible solution using one the following three methods.
1. North West Corner Method
2. Least Cost Method
3. Vogel Approximation Method
The difference among these three methods is the quality of the initial basic
feasible solution they produce, in the sense that a better that a better initial
solution yields a smaller objective value. Generally the Vogel Approximation
Method produces the best initial basic feasible solution, and the North West
Corner Method produces the worst, but the North West Corner Method involves
least computations.
3.5.1 North West Corner Method
The method starts at the North West (upper left) corner cell of the tableau
(variable x11).
Step -1: Allocate as much as possible to the selected cell, and adjust the
associated amounts of capacity (supply) and requirement (demand) by subtracting
the allocated amount.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
43
Step -2: Cross out the row (column) with zero supply or demand to indicate
that no further assignments can be made in that row (column). If both the row
and column becomes zero simultaneously, cross out one of them only, and leave
a zero supply or demand in the uncrossed out row (column).
Step -3:If exactly one row (column) is left uncrossed out, then stop.
Otherwise, move to the cell to the right if a column has just been crossed or the
one below if a row has been crossed out. Go to step -1.
The concept of North-West Corner can be well understood through a
transportation problem given below:
In the table, three sources A, B and C with the production capacity of 50
units, 40 units, 60 units of product respectively is given. Every day the demand
of three retailers D, E, F is to be furnished with at least 20 units, 95 units and 35
units of product respectively. The transportation costs are also given in the matrix.
The prerequisite condition for solving the transportation problem is that
demand should be equal to the supply. In case the demand is more than supply,
then dummy origin is added to the table. The supply of dummy origin will be
equal to the difference between the total supply and total demand. The cost
associated with the dummy origin will be zero.
Similarly, in case the supply is more than the demand, then dummy source
is created whose demand will be equivalent to the difference between supply and
demand. Again the cost associated with the dummy source will be zero.

NOTES
TRANSPORTATION
PROBLEM (TP)
44
Once the demand and supply are equal, the following procedure is followed:
1.Select the north-west or extreme left corner of the matrix, assign as
many units as possible to cell AD, within the supply and demand
constraints. Such as 20 units are assigned to the first cell, that satisfies
the demand of destination D while the supply is in surplus.
2.Now move horizontally and assign 30 units to the cell AE. Since 30
units are available with the source A, the supply gets fully saturated.
3.Now move vertically in the matrix and assign 40 units to Cell BE. The
supply of source B also gets fully saturated.
4.Again move vertically, and assign 25 units to cell CE, the demand of
destination E is fulfilled.
5.Move horizontally in the matrix and assign 35 units to cell CF, both
the demand and supply of origin and destination gets saturated. Now
the total cost can be computed.
The Total cost can be computed by multiplying the units assigned to each
cell with the concerned transportation cost. Therefore,
Total Cost = 20*5+ 30*8+ 40*6+ 25*9+ 35*6 = Rs 1015
Unbalanced supply and demand
If the total supply is not equal to the total demand then the problem is called
unbalanced transportation problem.
Solution
1. If the total supply is more than the total demand, then we add a new
column, with transportation cost 0
2. If the total demand is more than the total supply, then we add a new
row, with transportation cost 0
Example
Find Solution using North-West Corner method
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
45
Solution
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
Here Total Demand = 215 is less than Total Supply = 235. So We add a
dummy demand constraint with 0 unit cost and with allocation 20.
Now, the modified table is
The rim values for S1=76 and D1=72 are compared.
The smaller of the two i.e. min(76,72) = 72 is assigned to S1 D1
This meets the complete demand of D1 and leaves 76 - 72 = 4 units with S1
Table-1

NOTES
TRANSPORTATION
PROBLEM (TP)
46
The rim values for S1=4 and D2=102 are compared.
The smaller of the two i.e. min(4,102) = 4 is assigned to S1 D2
This exhausts the capacity of S1 and leaves 102 - 4 = 98 units with D2
Table-2
The rim values for S2=82 and D2=98 are compared.
The smaller of the two i.e. min(82,98) = 82 is assigned to S2 D2
This exhausts the capacity of S2 and leaves 98 - 82 = 16 units with D2
Table-3
The rim values for S3=77 and D2=16 are compared.
The smaller of the two i.e. min(77,16) = 16 is assigned to S3 D2
This meets the complete demand of D2 and leaves 77 - 16 = 61 units with S3
Table-4
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
47
The rim values for S3=61 and D3=41 are compared.
The smaller of the two i.e. min(61,41) = 41 is assigned to S3 D3
This meets the complete demand of D3 and leaves 61 - 41 = 20 units with S3
Table-5
The rim values for S3=20 and Dummy=20 are compared.
The smaller of the two i.e. min(20,20) = 20 is assigned to S3 Dummy
Table-6
Initial feasible solution is
The minimum total transportation cost =4×72+8×4+24×82+
16×16+24×41+0×20=3528
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
∴This solution is non-degenerate

NOTES
TRANSPORTATION
PROBLEM (TP)
48
3.5.2 Least Cost Method (Matrix Minimum Method)
Definition
The Least Cost Method is another method used to obtain the initial feasible
solution for the transportation problem. Here, the allocation begins with the cell
which has the minimum cost. The lower cost cells are chosen over the higher-
cost cell with the objective to have the least cost of transportation.
The Least Cost Method is considered to produce more optimal results than
the North-west Corner because it considers the shipping cost while making the
allocation, whereas the North-West corner method only considers the availability
and supply requirement and allocation begin with the extreme left corner,
irrespective of the shipping cost.
Let’s understand the concept of Least Cost method through a problem
given below:
In the given matrix, the supply of each source A, B, C is given Viz. 50units,
40 units, and 60 units respectively. The weekly demand for three retailers D, E,
F i.e. 20 units, 95 units and 35 units is given respectively. The shipping cost is
given for all the routes.
The minimum transportation cost can be obtained by following the
steps given below:
1. The minimum cost in the matrix is Rs 3, but there is a tie in the cell
BF, and CD, now the question arises in which cell we shall allocate.
Generally, the cost where maximum quantity can be assigned should
be chosen to obtain the better initial solution. Therefore, 35 units shall
be assigned to the cell BF. With this, the demand for retailer F gets
fulfilled, and only 5 units are left with the source B.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
49
2. Again the minimum cost in the matrix is Rs 3. Therefore, 20 units shall
be assigned to the cell CD. With this, the demand of retailer D gets
fulfilled. Only 40 units are left with the source C.
3. The next minimum cost is Rs 4, but however, the demand for F is
completed, we will move to the next minimum cost which is 5. Again,
the demand of D is completed. The next minimum cost is 6, and there
is a tie between three cells. But however, no units can be assigned to
the cells BD and CF as the demand for both the retailers D and F are
saturated. So, we shall assign 5 units to Cell BE. With this, the supply
of source B gets saturated.
4. The next minimum cost is 8, assign 50 units to the cell AE. The supply
of source A gets saturated.
5. The next minimum cost is Rs 9; we shall assign 40 units to the cell
CE. With his both the demand and supply of all the sources and origins
gets saturated.
The total cost can be calculated by multiplying the assigned quantity with
the concerned cost of the cell. Therefore,
Total Cost = 50*8 + 5*6 + 35*3 +20*3 +40*9 = Rs 955.
Note: The supply and demand should be equal and in case supply are more,
the dummy source is added in the table with demand being equal to the difference
between supply and demand, and the cost remains zero. Similarly, in case the
demand is more than supply, then dummy destination or origin is added to the
table with the supply equal to the difference in quantity demanded and supplied
and the cost being zero.
Find Solution of Transportation Problem using Least Cost method
Solution
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 4

NOTES
TRANSPORTATION
PROBLEM (TP)
50
Problem Table is
The smallest transportation cost is 8 in cell S3D2
The allocation to this cell is min(18,8) = 8.
This satisfies the entire demand of D2 and leaves 18 - 8 = 10 units with S3
Table-1
The smallest transportation cost is 10 in cell S1D4
The allocation to this cell is min(7,14) = 7.
This exhausts the capacity of S1 and leaves 14 - 7 = 7 units with D4
Table-2
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
51
The allocation to this cell is min(10,7) = 7.
This satisfies the entire demand of D4 and leaves 10 - 7 = 3 units with S3
Table-3
The smallest transportation cost is 40 in cell S2D3
The allocation to this cell is min(9,7) = 7.
This satisfies the entire demand of D3 and leaves 9 - 7 = 2 units with S2
Table-4
The smallest transportation cost is 40 in cell S3D1
The allocation to this cell is min(3,5) = 3.
This exhausts the capacity of S3 and leaves 5 - 3 = 2 units with D1
Table-5

NOTES
TRANSPORTATION
PROBLEM (TP)
52
The smallest transportation cost is 70 in cell S2D1
The allocation to this cell is min(2,2) = 2.
Table-6
Initial feasible solution is
The minimum total transportation cost =10×7+70×2+40×7+40×
3+8×8+20×7=814
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
∴This solution is non-degenerate
3.5.3 Vogel’s Approximation Method
Definition: The Vogel’s Approximation Method or VAM is an iterative
procedure calculated to find out the initial feasible solution of the transportation
problem. Like Least cost Method, here also the shipping cost is taken into
consideration, but in a relative sense.The concept of Vogel’s Approximation
Method can be well understood through an illustration given below:
1.First of all the difference between two least cost cells are calculated
for each row and column, which can be seen in the iteration given for
each row and column. Then the largest difference is selected, which is
4 in this case. So, allocate 20 units to cell BD, since the minimum cost
is to be chosen for the allocation. Now, only 20 units are left with the
source B.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
53
2.Column D is deleted, again the difference between the least cost cells
is calculated for each row and column, as seen in the iteration below.
The largest difference value comes to be 3, so allocate 35 units to cell
AF and 15 units to the cell AE. With this, the Supply and demand of
source A and origin F gets saturated, so delete both the row A and
Column F.
3. Now, single column E is left, since no difference can be found out, so
allocate 60 units to the cell CE and 20 units to cell BE, as only 20 units
are left with source B. Hence the demand and supply are completely
met.

NOTES
TRANSPORTATION
PROBLEM (TP)
54
Now the total cost can be computed, by multiplying the units assigned to
each cell with the cost concerned. Therefore,
Total Cost = 20*3 + 35*1 + 15*4 + 60*4 + 20*8 = Rs 555
Note: Vogel’s Approximation Method is also called as Penalty Method
because the difference costs chosen are nothing but the penalties of not choosing
the least cost routes.
Ex. Find Solution using Vogel's Approximation method
Solution
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
Here Total Demand = 215 is less than Total Supply = 235. So We add a
dummy demand constraint with 0 unit cost and with allocation 20.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
55
Now, The modified table is
Table-1
The maximum penalty, 16, occurs in row S2.
The minimum cij in this row is c24 = 0.
The maximum allocation in this cell is min(82,20) = 20.
It satisfy demand of Dummy and adjust the supply of S2 from 82 to 62 (82
- 20 = 62).
Table-2

NOTES
TRANSPORTATION
PROBLEM (TP)
56
The maximum penalty, 8, occurs in row S3.
The minimum cij in this row is c31 = 8.
The maximum allocation in this cell is min(77,72) = 72.
It satisfy demand of D1 and adjust the supply of S3 from 77 to 5 (77 - 72 = 5).
Table-3
The maximum penalty, 8, occurs in row S2.
The minimum cij in this row is c23 = 16.
The maximum allocation in this cell is min(62,41) = 41.
It satisfy demand of D3 and adjust the supply of S2 from 62 to 21 (62 - 41 = 21).
Table-4
The maximum penalty, 24, occurs in row S2.
The minimum cij in this row is c22 = 24.
The maximum allocation in this cell is min(21,102) = 21.
It satisfy supply of S2 and adjust the demand of D2 from 102 to 81 (102 - 21 = 81).
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
57
Table-5
The maximum penalty, 16, occurs in row S3.
The minimum cij in this row is c32 = 16.
The maximum allocation in this cell is min(5,81) = 5.
It satisfy supply of S3 and adjust the demand of D2 from 81 to 76 (81 - 5 = 76).
Table-6
The maximum penalty, 8, occurs in row S1.
The minimum cij in this row is c12 = 8.
The maximum allocation in this cell is min(76,76) = 76.
It satisfy supply of S1 and demand of D2.

NOTES
TRANSPORTATION
PROBLEM (TP)
58
Initial feasible solution is
The minimum total transportation cost =8×76+24×21+16×41+0×20+
8×72+16×5=2424
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
∴This solution is non-degenerate
Modified Distribution Method
Definition: The Modified Distribution Method or MODI is an efficient
method of checking the optimality of the initial feasible solution.
MODI Method Steps
Step-1: Find an initial basic feasible solution using any one of the three
methods NWCM, LCM or VAM.
Step-2: Find ui and vj for rows and columns. To start:
a. assign 0 to ui or vj where maximum number of allocation in a
row or column respectively.
b. Calculate other ui's and vj's using cij=ui+vj, for all occupied cells.
Step-3: For all unoccupied cells, calculate dij=cij-(ui+vj),
Step-4: Check the sign of dij
a. If dij>0, then current basic feasible solution is optimal and stop
this procedure.
b. If dij=0 then alternative soluion exists, with different set
allocation and same transportation cost. Now stop this procedure.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
59
b. If dij<0, then the given solution is not an optimal solution and
further improvement in the solution is possible.
Step-5: Select the unoccupied cell with the largest negative value of dij,
and included in the next solution.
Step-6: Draw a closed path (or loop) from the unoccupied cell (selected
in the previous step). The right angle turn in this path is allowed only at occupied
cells and at the original unoccupied cell. Mark (+) and (-) sign alternatively at
each corner, starting from the original unoccupied cell.
Step-7:
1. Select the minimum value from cells marked with (-) sign of the
closed path.
2. Assign this value to selected unoccupied cell (So unoccupied cell
becomes occupied cell).
3. Add this value to the other occupied cells marked with (+) sign.
4. Subtract this value to the other occupied cells marked with (-)
sign.
Step-8: Repeat Step-2 to step-7 until optimal solution is obtained. This
procedure stops when all dij≥0 for unoccupied cells.
Terms in Transportation Problem
Feasible Solution
A solution that satisfies the row and column sum restrictions and also the
non-negativity restrictions is a feasible solution.
Basic Feasible Solution
A feasible solution of (m X n) transportation problem is said to be basic
feasible solution, when the total number of allocations is equal to (m + n – 1).
Optimal Solution
A feasible solution is said to be optimal solution when the total
transportation cost will be the minimum cost.
Occupied Cell: Occupied cell is a cell in Transportation Matrix where there
is an allocation.
Unoccupied Cell: Unoccupied cell is a cell in Transportation Matrix where
there is no allocation.
Example :Find the initial basic solution for the transportation problem and
hence solve it.

NOTES
TRANSPORTATION
PROBLEM (TP)
60
Transportation Problem
Solution: Vogel’s Approximation Method (VAM) is preferred to find initial
feasible solution.
The advantage of this method is that it gives an initial solution which is
nearer to an optimal solution or the optimal solution itself.
Step 1: The given transportation problem is a balanced one as the sum of
supply equals to sum of demand.
Step 2: The initial basic solution is found by applying the Vogel’s
Approximation method and the result is shown in the following table.
Initial Basic Solution Found by Applying VAM
Step 3:Calculate the Total Transportation Cost.
Initial Transportation cost = (2 × 250) + (3 × 200) + (5 × 250) + (4 × 150)
+ (3 × 50) + (1 × 300)
= 500 + 600 + 1250 + 600 + 150 + 300
= Rs. 3,400
Step 4:Check for degeneracy. For this, verify the condition,
Number of allocations, N= m + n – 1
6 = 3 + 4 – 1
6 = 6
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
61
Since the condition is satisfied, degeneracy does not exist.
Step 5:Test for optimality using modified distribution method. Compute
the values of U i and vj for rows and columns respectively by applying the
formula for occupied cells.cij+ui+vj = 0 Then, the opportunity cost for each
unoccupied cell is calculated using the formula C ij = cij + ui + vj and denoted
at the left hand bottom corner of each unoccupied cell. The computed valued of
uj and vi and are shown in the table below.
Calculation of the Opportunity Cost
Calculate the values of ui and v j, using the formula for occupied cells.
Assume any one of u
iand v jvalue as zero (U3 is taken as 0)

NOTES
TRANSPORTATION
PROBLEM (TP)
62
Since all the opportunity cost, C ij values are positive the solution is
optimum.
Total transportation cost = (2 × 25) + (3 × 200) + (5 × 250) + (4 × 150) +
(3 × 50)+ (1 × 300)
= 50 + 600 +1250 + 600 + 150 + 300
= Rs 2,950/-
Sreps to draw Closed Loop
1. A closed loop consists of horizontal and vertical lines starting from
and ending on an unoccupied cell.
2. All the vertex or the corner points should be occupied cells except the
starting vertex.
3. For any given Transportation Problem we can form only one loop for
an unoccupied cell.
Showing Closed Loop
Conditions for forming a loop
(i) The start and end points of a loop must be the same.
(ii) The lines connecting the cells must be horizontal and vertical.
(iii) The turns must be taken at occupied cells only.
(iv) Take a shortest path possible (for easy calculations).
Remarks on forming a loop
(i) Every loop has an even number of cells and at least four cells
(ii) Each row or column should have only one ‘+’ and ‘–’ sign.
(iii) Closed loop may or may not be square in shape. It can also be a
rectangle or a stepped shape.
(iv) It doesn’t matter whether the loop is traced in a clockwise or
anticlockwise direction.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
63
Ex. The concept of MODI can be further comprehended through an
illustration given below:
1.Initial basic feasible solution is given below
2.Now, calculate the values of ui and vj by using the equation

NOTES
TRANSPORTATION
PROBLEM (TP)
64
Next step is to calculate the opportunity cost of the unoccupied cells (AF,
BD, BF, CD) by using the following formula:
4. Choose the largest positive opportunity cost, which is 7 and draw a
closed path, as shown in the matrix below. Start from the unoccupied
cell and assign “+” or “–“sign alternatively. Therefore, The most
favored cell is BD, assign as many units as possible.
5. The matrix below shows the maximum allocation to the cell BD, and
that number of units are added to the cell with a positive sign and
subtracted from the cell with a negative sign.
6. Again, repeat the steps from 1 to 4 i.e. find out the opportunity costs
for each unoccupied cell and assign the maximum possible units to the
cell having the largest opportunity cost. This process will go on until
the optimum solution is reached.Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
65
The Modified distribution method is an improvement over the stepping
stone method since; it can be applied more efficiently when a large number of
sources and destinations are involved, which becomes quite difficult or tedious
in case of stepping stone method.
Modified distribution method reduces the number of steps involved in the
evaluation of empty cells, thereby minimizes the complexity and gives a
straightforward computational scheme through which the opportunity cost of
each empty cell can be determined.
3.6 SPECIAL CASES IN TRANSPORTATION PROBLEM
1. Unbalanced transportation problem.
When the total supply of all the sources is not equal to the total demand of
all destinations, the problem is an unbalanced transportation problem.
Total supply ≠ Total demand
Ex.Find Solution to following Transportation Problem using Vogel's
Approximation method.
Solution
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3

NOTES
TRANSPORTATION
PROBLEM (TP)
66
Problem Table is
Here Total Demand = 215 is less than Total Supply = 235. So we add a
dummy demand constraint with 0 unit cost and with allocation 20.
Now, The modified table is
Table-1
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
67
he maximum penalty, 16, occurs in row S2.
The minimum cij in this row is c24 = 0.
The maximum allocation in this cell is min(82,20) = 20.
It satisfy demand of Dummy and adjust the supply of S2 from 82 to 62 (82
- 20 = 62).
Table-2
The maximum penalty, 8, occurs in row S3.
The minimum cij in this row is c31 = 8.
The maximum allocation in this cell is min(77,72) = 72.
It satisfy demand of D1 and adjust the supply of S3 from 77 to 5 (77 - 72 = 5).
Table-3
The maximum penalty, 8, occurs in row S2.
The minimum cij in this row is c23 = 16.
The maximum allocation in this cell is min(62,41) = 41.
It satisfy demand of D3 and adjust the supply of S2 from 62 to 21 (62 - 41 = 21).

NOTES
TRANSPORTATION
PROBLEM (TP)
68
Table-4
The maximum penalty, 24, occurs in row S2.
The minimum cij in this row is c22 = 24.
The maximum allocation in this cell is min(21,102) = 21.
It satisfy supply of S2 and adjust the demand of D2 from 102 to 81 (102 -
21 = 81).
Table-5
The maximum penalty, 16, occurs in row S3.
The minimum cij in this row is c32 = 16.
The maximum allocation in this cell is min(5,81) = 5.
It satisfy supply of S3 and adjust the demand of D2 from 81 to 76 (81 - 5 = 76).
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
69
Table-6
The maximum penalty, 8, occurs in row S1.
The minimum cij in this row is c12 = 8.
The maximum allocation in this cell is min(76,76) = 76.
It satisfy supply of S1 and demand of D2.
Initial feasible solution is
The minimum total transportation cost =8×76+24×21+16×
41+0×20+8×72+16×5=2424
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
∴This solution is non-degenerate

NOTES
TRANSPORTATION
PROBLEM (TP)
70
Demand Less than Supply
In real-life, supply and demand requirements will rarely be equal. This is
because of variation in production from the supplier end, and variations in
forecast from the customer end. Supply variations may be because of shortage
of raw materials, labour problems, Transportation Model improper planning and
scheduling. Demand variations may be because of change in customer
preference, change in prices and introduction of new products by competitors.
These unbalanced problems can be easily solved by introducing dummy
sources and dummy destinations. If the total supply is greater than the total
demand, a dummy destination (dummy column) with demand equal to the supply
surplus is added. If the total demand is greater than the total supply, a dummy
source (dummy row) with supply equal to the demand surplus is added. The unit
transportation cost for the dummy column and dummy row are assigned zero
values, because no shipment is actually made in case of a dummy source and
dummy destination.
Example :Check whether the given transportation problem shown in Table
is a balanced one. If not, convert the unbalanced problem into a balanced
transportation problem.
Transportation Model with Supply Exceeding Demand
Solution: For the given problem, the total supply is not equal to the total
demand.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
71
The given problem is an unbalanced transportation problem. To convert the
unbalanced transportation problem into a balanced problem, add a dummy
destination (dummy column). i.e., the demand of the dummy destination is equal
to,
Thus, a dummy destination is added to the table, with a demand of 100 units.
The modified table is shown in Table which has been converted into a balanced
transportation table. The unit costs of transportation of dummy destinations are
assigned as zero.
Dummy Destination Added
Similarly,
Demand Greater than Supply
Example :Convert the transportation problem shown in Table into a
balanced problem.
Demand Exceeding Supply
Solution: The given problem is,

NOTES
TRANSPORTATION
PROBLEM (TP)
72
The given problem is an unbalanced one. To convert it into a balanced
transportation problem, include a dummy source (dummy row) as shown in Table
Balanced TP Model
Ex.: A particular product is manufactured in factories A, B, C, and D; and
is sold at Centres 1, 2 and 3. The cost in Rs. of product per unit and capacity in
kgms per unit time of each plant is given below:
The sales price in Rs. Per unit and the demand in kgms per unit time
are as follows:
Find the optimal sales distribution.
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
73
Solution: The given problem is a transportation problem. The profit matrix
for various factories and sales counters is calculated below:
Since this is an unbalanced transportation problem (demand >capacity), let
us introduce a dummy factory with profit as Rs. 0 per until for various sales
Centres and capacity equal to sixty units. The resulting matrix would be as below:
The above profit matrix can be converted into a loss matrix by subtracting
all its elements from the highest payoff of the matrix i.e. 5. The loss matrix so
obtained is given below.

NOTES
TRANSPORTATION
PROBLEM (TP)
74
The initial solution is obtained by applying Vogel’s approximation method.
The solution obtained by VAM is as given below
The initial solution is tested for optimality. The total number of independent
allocations is 6 which is one less than (m +n –1) allocations. Let us introduce a
small quantity e in the least cost independent cell (A, 3). We also introduce ui,
vj, i = (1,2,3,4,5); j = (1,2,3) such that Äij =Cij – (ui +vj) for allocation cells.Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
75
We assume v2 = 0 and remaining vi’s, vj’s and Äij are calculated as below:
Since all Äij > 0 for the non allocated cells, hence the solution given by
above matrix is optimal. The optimal solution for the given problem is given
below:
2. Degeneracy in Transportation Problem:
In a standard transportation problem with m sources of supply and n demand
destinations, the test of optimality of any feasible solution requires allocations
in m + n – 1 independent cells. If the number of allocations is short of the required
number, then the solution is said to be degenerate.If number of allocations, N =
m + n – 1, then degeneracy does not exist and if number of allocations, N less
than m + n – 1, then degeneracy will exist.
Resolving degeneracy
In order to resolve degeneracy, the conventional method is to allocate an
infinitesimally small amount e to one of the independent cells i.e., allocate a
small positive quantity e to one or more unoccupied cell that have lowest

NOTES
TRANSPORTATION
PROBLEM (TP)
76
transportation costs, so as to make m + n – 1 allocations (i.e., to satisfy the
condition N = m + n – 1).
In other words, the allocation of e should avoid a closed loop and should
not have a path. Once this is done, the test of optimality is applied and, if
necessary, the solution is improved in the normal was until optimality is reached.
The following table shows independent allocations.
Independent Allocations
The following Tables show non-independent allocations.
Non-Independent Allocations
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
77
Example :Find the initial basic feasible solution for the transportation
problem given in Table.
Transportation Problem
Solution :The initial basic feasible solution using VAM is shown in table
below.
Check for degeneracy,
The number of allocations, N must be equal to m + n – 1.
i.e., N = m+n – 1
5 = 3+3 – 1
since 4 ≠5, therefore degeneracy exists.
To overcome degeneracy, the condition N = m + n – 1 is satisfied by
allocating a very small quantity, close to zero in an occupied independent cell.
(i.e., it should not form a closed loop) or the cell having the lowest transportation
cost. This quantity is denoted by e.
This quantity would not affect the total cost as well as the supply and
demand values.

NOTES
TRANSPORTATION
PROBLEM (TP)
78
Resolving Degeneracy in Transportation Problem
Table shows the resolved degenerate table.
Resolved Degenerate Table
Total transportation cost = (50 × 1)+ (90 × 3) + (200 × 2) + (50 × 2) + (250 × e)
= 50 + 270 + 400 + 100 + 250 e
= 820 + 250 e = Rs. 820 since e is 0
Example : Obtain an optimal solution for the transportation problem by
MODI method given in Table.
Transportation Problem
Solution
Step1: The initial basic feasible solution is found using Vogel’s
Approximation Method as shown in Table.
Non Degenerate basic feasible Solution in Transportation Problem
Total transportation cost = (19 × 5) + (10 × 2) + (40 × 7) + (60 × 2) + (8 ×
8) +(20 × 10)
= 95 + 20 + 280 + 120 + 64 + 200
= Rs. 779.00
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
79
Step 2: To check for degeneracy, verify the number of allocations, N = m+n – 1.
In this problem, number of allocation is 6 which is equal m+n – 1.
∴N = m + n – 1
6 = 3 + 4 – 1
6 = 6 therefore degeneracy does not exist.
Step 3: Test for optimality using MODI method. In Table, the values of Ui
and Vj are calculated by applying the formula Ci
j+ Ui+ Vj= 0 for occupied cells.
Transportation Problem Modi method degeneracy
Optimality Test Using MODI Method
Find the values of the dual variables U iand V jfor occupied cells.
Initially assume U
i= 0,
In Table the cell (2,2) has the most negative opportunity cost. This negative
cost has to be converted to a positive cost without altering the supply and demand
value.

NOTES
TRANSPORTATION
PROBLEM (TP)
80
Step 4: Construct a closed loop . Introduce a quantity + q in the most
negative cell (S2, D2 ) and a put – q in cell (S3, D2 ) in order to balance the
column D2. Now, take a right angle turn and locate an occupied cell in column
D4. The occupied cell is (S3, D4) and put a + q in that cell. Now, put a – q in cell
(S2, D4 ) to balance the column D4. Join all the cells to have a complete closed
path. The closed path is shown in Figure.
Closed Path
Now, identify the – q values, which are 2 and 8. Take the minimum value,
2 which is the allocating value. This value is then added to cells (S2, D2 ) and
(S3, D4 ) which have ‘+’signs and subtract from cells (S2, D4 ) and (S3, D2 )
which have ‘–’ signs. The process is shown in Figure.
Closed Path
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
81
The table after reallocation is shown in Table below.
After Reallocation
Now, again check for degeneracy. Here allocation number is 6.
Verify whether number of allocations,
N = m + n – 1
6 = 3 + 4 – 1
6 = 6
therefore degeneracy does not exits.
Again find the values of U
i, Vjand ci jfor the Table 6.39 shown earlier.
For occupied cells, Ci
j+ Ui+ Vj= 0

NOTES
TRANSPORTATION
PROBLEM (TP)
82
The values of the opportunity cost cij are positive. Hence the optimality is
reached.
The final allocations are shown in Table.
Final Allocation
V1 = – 19 V2 = 2 V3 = – 8 V4 = – 10
Total transportation cost = (19 × 5) + (10 × 2) + (30 × 2) + (40 × 7) + (8 ×
6) + (20 × 12)
= 95 + 20 + 60 + 280 + 48 + 240
= Rs. 743
Restircted Transportation Problem
Sometimes there may be situations, where it is not possible to use certain
routes in a transportation problem. For example, road construction, bad road
conditions, strike, unexpected floods, local traffic rules, etc. Such restrictions (or
prohibitions) can be handled in the transportation problem by assigning a very
high cost (say M or [infinity]) to the prohibited routes to ensure that routes will
not be included in the optimal solution and then the problem is solved in the usual
manner.
Ex. Solve the following transportation problem
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
83
Note: It is not possible to transport any quantity from factory 2 to godown
5. State whether the solution derived by you is unique.
Solution
The initial solution is found by VAM below
The above initial solution is tested for optimality. Since there are only 8
allocations and we require 9(m+n-1 =9) allocations, we put a small quantity in
the least cost independent cell (2, 6) and apply the optimality test. Let u3 = 0 and
then we calculate remaining ui and vj
Now we calculateij = cij – (ui +vj) for non basic cells which are given
in the table below:

NOTES
TRANSPORTATION
PROBLEM (TP)
84
Since all ij are positive, the initial solution found by VAM is an optimal
solution. The final allocations are given below:
Multiple Solutions to TP
It is possible for a transportation problem to have multiple optimal solutions.
This happens when one or more of the improvement indices zero in the optimal
solution. This means that it is possible to design alternative shipping routes with
the same total shipping cost The alternate optimal solution can be found by
shipping the most to this unused square using a stepping-stone path. In the real
world, alternate optimal solutions provide management with greater flexibility
in selecting and using resources
Example
Find Solution using Vogel's Approximation method, also find optimal
solution using modi method,
Solution
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
85
Problem Table is
Here Total Demand = 215 is less than Total Supply = 235. So We add a
dummy demand constraint with 0 unit cost and with allocation 20.
Now, The modified table is
Table-1
The maximum penalty, 16, occurs in row S2.
The minimum cij in this row is c24 = 0.
The maximum allocation in this cell is min(82,20) = 20.
It satisfy demand of Dummy and adjust the supply of S2 from 82 to 62 (82
- 20 = 62).

NOTES
TRANSPORTATION
PROBLEM (TP)
86
Table-2
The maximum penalty, 8, occurs in row S3.
The minimum cij in this row is c31 = 8.
The maximum allocation in this cell is min(77,72) = 72.
It satisfy demand of D1 and adjust the supply of S3 from 77 to 5 (77 - 72 = 5).
Table-3
The maximum penalty, 8, occurs in row S2.
The minimum cij in this row is c23 = 16.
The maximum allocation in this cell is min(62,41) = 41.
It satisfy demand of D3 and adjust the supply of S2 from 62 to 21 (62 - 41
= 21).
Table-4
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
87
The maximum penalty, 24, occurs in row S2.
The minimum cij in this row is c22 = 24.
The maximum allocation in this cell is min(21,102) = 21.
It satisfy supply of S2 and adjust the demand of D2 from 102 to 81 (102 -
21 = 81).
Table-5
The maximum penalty, 16, occurs in row S3.
The minimum cij in this row is c32 = 16.
The maximum allocation in this cell is min(5,81) = 5.
It satisfy supply of S3 and adjust the demand of D2 from 81 to 76 (81 - 5 = 76).
Table-6
The maximum penalty, 8, occurs in row S1.
The minimum cij in this row is c12 = 8.
The maximum allocation in this cell is min(76,76) = 76.
It satisfy supply of S1 and demand of D2.

NOTES
TRANSPORTATION
PROBLEM (TP)
88
Initial feasible solution is
The minimum total transportation cost =8×76+24×21+16×41+
0×20+8×72+16×5=2424
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
∴This solution is non-degenerate
Optimality test using modi method...
Allocation Table is
Iteration-1 of optimality test
1. Find ui and vj for all occupied cells(i,j), where cij=ui+vj
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
89
Since all dij≥0.
So final optimal solution is arrived.
The minimum total transportation cost =8×76+24×21+16×41
+0×20+8×72+16×5=2424
Alternate solution is available with unoccupied cell S2D1:d21 = [0], but
with the same optimal value.

NOTES
TRANSPORTATION
PROBLEM (TP)
90
QUESTIONS
1.Find the optimum Transportation schedule using VAM method and
minimum total cost of Transportation.
2.Solve the transportation problem using VAM.
3.Solve the following transportation problem:
4. A Company has 3 production facilities S1, S2 and S3 with production
capacity of 7, 9 and 18 units (in 100's) per week of a product,
respectively. These units are tobe shipped to 4 warehouses D1, D2, D3
and D4 with requirement of 5,6,7 and 14 units (in 100's) per week,
respectively. The transportation costs (in rupees) per unit between
factories to warehouses are given in the table below.
Find initial basic feasible solution for given problem by using
(a) North-West corner method
(b) Least cost method
Operations Research for
Managers

NOTES
Operations Research for
Managers
TRANSPORTATION
PROBLEM (TP)
91
(c) Vogel's approximation method
(d) obtain an optimal solution by MODI method
if the object is to minimize the total transportation cost.
5. A company has factories at F1, F2 and F3 which supply to warehouses
at W1, W2 and W3. Weekly factory capacities are 200, 160 and 90
units, respectively. Weekly warehouse requiremnet are 180, 120 and
150 units, respectively. Unit shipping costs (in rupess) are as follows:
Determine the optimal distribution for this company to minimize total
shipping cost.
6. Find an initial basic feasible solution for given transportation problem
by using
(a) North-West corner method
(b) Least cost method
(c) Vogel's approximation method
*****

NOTES
ASSIGNMENT
PROBLEM
92
UNIT - IV
ASSIGNMENT PROBLEM
CHAPTER OBJECTIVES
1. To know the Assignment Problem Concept.
2. To understand Hungarian Method.
3.To Know Business applications of Assignment Problem.
CHAPTER CONTENTS
a) Meaning
b) Definition and applications of Assignment Problem
c) Hungarian Method
d) Assignment Problem for Maximization
e) Minimization. unbalanced AP, restricted AP
f) Multiple /Optimal Solutions
g) Business Applications
OVERVIEW OF THE CHAPTER
This chapter throws light on Assignment Problem. Hungarian Method for
solving Assignment Problem is also discussed in this chapter. Special cases in
Assignment Problem are also discussed along with business applications of
Assignment Problem.
KEY WORDS
Assignment Problem, Hungarian Method, Special Cases
INTRODUCTION
The assignment problem is a particular class of transportation linear
programming problems with the supplies and demands equal to integers (often
1). Since all supplies, demands, and bounds on variables are integers, the
assignment problem relies on an interesting property of transportation problems
that the optimal solution will be entirely integers.
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
93
Definition
Suppose there are n jobs to be performed and n persons are available for
doing these jobs. Assume that each person can do each job at a term, though with
varying degree of efficiency, let cij be the cost if the i-th person is assigned to
the j-th job. The problem is to find an assignment (which job should be assigned
to which person one on-one basis) So that the total cost of performing all jobs is
minimum, problem of this kind are known as assignment problem.
Structure of assignment problem
Assignment problem is a special type of transportation problem in which
1.Number of supply and demand nodes are equal.
2.Supply from every supply node is one.
3.Every demand node has a demand of one.
4.Solution is required to be all integers.
The goal of a general assignment problem is to find an optimal assignment
of machines (laborers) to jobs without assigning an agent more than once and
ensuring that all jobs are completed. The objective might be to minimize the total
time to complete a set of jobs, or to maximize skill ratings, maximize the total
satisfaction of the group or to minimize the cost of the assignments. This is
subjected to the following requirements:
1.Each machine is assigned not more than one job.
2.Each job is assigned to exactly one machine.
The structure of assignment problem of assigning operators to jobs is shown
in Table.
Structure of Assignment Problem
Let n be the number of jobs and number of operators.
tij be the processing time of job i taken by operator j.
Assignment problem- Business Applications
A few applications of mathematical model of assignment problem are:
i.Assignment of employees to machines.

NOTES
ASSIGNMENT
PROBLEM
94
ii.Assignment of operators to jobs.
iii.Effectiveness of teachers and subjects.
iv.Allocation of machines for optimum utilization of space.
v.Salesmen to different sales areas.
vi.Clerks to various counters.
In all the cases, the objective is to minimize the total time and cost or
otherwise maximize the sales and returns.
Hungarian method
An assignment problem can be easily solved by applying Hungarian method
which consists of two phases. In the first phase, row reductions and column
reductions are carried out. In the second phase, the solution is optimized on
iterative basis.
Phase 1
Step 1: Consider the given matrix.
Step 2: In a given problem, if the number of rows is not equal to the number
of columns and vice versa, then add a dummy row or a dummy column. The
assignment costs for dummy cells are always assigned as zero.
Step 3: Reduce the matrix by selecting the smallest element in each row
and subtract with other elements in that row.
Phase 2
Step 4: Reduce the new matrix column-wise using the same method as
given in step 2.
Step 5:Draw minimum number of lines to cover all zeros.
Step 6:If Number of lines drawn = order of matrix, then optimally is
reached, so proceed to step 7: If optimally is not reached, then go to step 6.
Step8:Select the smallest element of the whole matrix, which is not covered
by lines. Subtract this smallest element with all other remaining elements that
are not covered by lines and add the element at the intersection of lines. Leave
the elements covered by single line as it is. Now go to step 4.
Step 7:Take any row or column which has a single zero and assign by
squaring it. Strike off the remaining zeros, if any, in that row and column (X).
Repeat the process until all the assignments have been made.
Step 8:Write down the assignment results and find the minimum cost/time.
Note: While assigning, if there is no single zero exists in the row or column,
choose any one zero and assign it. Strike off the remaining zeros in that column
or row, and repeat the same for other assignments also. If there is no single zero
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
95
allocation, it means multiple numbers of solutions exist. But the cost will remain
the same for different sets of allocations.
Example 1
Consider three jobs to be assigned to three machines. The cost for each
combination is shown in the table below. Determine the minimal job – machine
combinations.
Table 1
Solution
Step 1
Create zero elements in the cost matrix (zero assignment) by subtracting
the smallest element in each row (column) from the corresponding row (column).
After this exercise, the resulting cost matrix is obtained by subtracting 5 from
row 1, 10 from row 2 and 13 from row 3.
Table 2

NOTES
ASSIGNMENT
PROBLEM
96
Step 2
Repeating the same with columns, the final cost matrix is
Table 3
The italicized zero elements represent a feasible solution. Thus the optimal
assignment is (1,1), (2,3) and (3,2). The total cost is equal to 60 (5 +12+13).
In the above example, it was possible to obtain the feasible assignment. But
in more complicated problems, additional rules are required which are explained
in the next example.
Example 2
Consider four jobs to be assigned to four machines. The cost for each
combination is shown in the table below. Determine the minimal job – machine
combinations.
Table 4
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
97
Solution
Step 1:Create zero elements in the cost matrix by subtracting the smallest
element in each row from the corresponding row.
Table 5
Step 2:Repeating the same with columns, the final cost matrix is
Table 6
Rows 1 and 3 have only one zero element. Both of these are in column 1,
which means that both jobs 1 and 3 should be assigned to machine 1. As one
machine can be assigned with only one job, a feasible assignment to the zero
elements is not possible as in the previous example.
Step 3: Draw a minimum number of lines through some of the rows and
columns so that all the zeros are crossed out.

NOTES
ASSIGNMENT
PROBLEM
98
Table 7
Step 4: Select the smallest uncrossed element (which is 1 here). Subtract it
from every uncrossed element and also add it to every element at the intersection
of the two lines. This will give the following table.
Table 8
This gives a feasible assignment (1,1), (2,3), (3,2) and (4,4) with a total cost
of 1+10+5+5 = 21.If the optimal solution had not been obtained in the last step,
then the procedure of drawing lines has to be repeated until a feasible solution is
achieved.
Unbalanced Maximization Assignment problem
Whenever the cost matrix of an assignment problem is not a square matrix,
that is, whenever the number of sources is not equal to the number of destinations,
the assignment problem is called an unbalanced assignment problem. In such
problems, dummy rows (or columns) are added in the matrix so as to complete
it to form a square matrix. The dummy rows or columns will contain all costs
elements as zeroes. The Hungarian method may be used to solve the problem.
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
99
Example : A company has five machines that are used for four jobs. Each
job can be assigned to one and only one machine. The cost of each job on each
machine is given in the following Table.
Assignment Problem
Solution: Convert the 4 × 5 matrix into a square matrix by adding a dummy
row D5.
Dummy Row D5 Added
Row-wise Reduction of the Matrix

NOTES
ASSIGNMENT
PROBLEM
100
Column-wise reduction is not necessary since all columns contain a single
zero. Now, draw minimum number of lines to cover all the zeros, as shown in
Table.
All Zeros in the Matrix Covered
Number of lines drawn ≠ Order of matrix. Hence not optimal.
Select the least uncovered element, i.e., 1, subtract it from other uncovered
elements, add to the elements at intersection of lines and leave the elements that
are covered with single line unchanged as shown in Table.
Subtracted or Added to Elements
Number of lines drawn ≠ Order of matrix. Hence not optimal.
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
101
Again Added or Subtracted 1 from Elements
Number of lines drawn = Order of matrix. Hence optimality is reached.
Now assign the jobs to machines, as shown in Table.
Assigning Jobs to Machines

NOTES
ASSIGNMENT
PROBLEM
102
Restricted Route Assignment Problem
It is sometimes possible that a particular person is incapable of doing certain
work or a specific job cannot be performed on a particular machine. The solution
of the assignment problem should take into account these restrictions so that the
restricted (infeasible) assignment can be avoided. This can be achieved by
assigning a very high cost (say ∞ or M)to the cells where assignments are
prohibited, thereby restricting the entry of this pair of job-machine or resource-
activity into the final solution.
Example : In a plant layout, four different machines M1, M2, M3 and M4
are to be erected in a machine shop. There are five vacant areas A, B, C, D and
E. Because of limited space, Machine M2 cannot be erected at area C and
Machine M4 cannot be erected at area A. The cost of erection of machines is
given in the Table.
Assignment Problem
Find the optimal assignment plan.
Solution: As the given matrix is not balanced, add a dummy row D5 with
zero cost values. Assign a high cost H for (M2, C) and (M4, A). While selecting
the lowest cost element neglect the high cost assigned H, as shown in Table below.
Dummy Row D5 Added
Row-wise reduction of the matrix is shown in Table.
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
103
Matrix Reduced Row-wise
Note: Column-wise reduction is not necessary, as each column has at least
one single zero. Now, draw minimum number of lines to cover all the zeros, see
Table.
Lines Drawn to Cover all Zeros
Number of lines drawn ≠ Order of matrix. Hence not Optimal. Select the
smallest uncovered element, in this case 1. Subtract 1 from all other uncovered
element and add 1 with the elements at the intersection. The element covered by
single line remains unchanged. These changes are shown in Table. Now try to
draw minimum number of lines to cover all the zeros.
Added or Subtracted 1 from Elements

NOTES
ASSIGNMENT
PROBLEM
104
Now number of lines drawn = Order of matrix, hence optimality is reached.
Optimal assignment of machines to areas are shown in Table.
Optimal Assignment
Hence, the optimal solution is
Example : A marketing manager has five salesmen and sales districts.
Considering the capabilities of the salesmen and the nature of districts, the
marketing manager estimates that sales per month (in hundred rupees) for each
salesman in each district would be as follows. Find the assignment of salesmen
to districts that will result in maximum sales.
Maximization Problem
Maximization assignment problem is transformed into minimization
problem by
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
105
Solution: The given maximization problem is converted into minimization
problem by subtracting from the highest sales value (i.e., 41) with all elements
of the given table.
Conversion to Minimization Problem
Reduce the matrix row-wise
Matrix Reduced Row-wise
Reduce the matrix column-wise and draw minimum number of lines to
cover all the zeros in the matrix, as shown in Table.
Matrix Reduced Column-wise and Zeros Covered

NOTES
ASSIGNMENT
PROBLEM
106
Number of lines drawn ≠ Order of matrix. Hence not optimal.
Select the least uncovered element, i.e., 4 and subtract it from other
uncovered elements, add it to the elements at intersection of line and leave the
elements that are covered with single line unchanged, Table.
Added & Subtracted the least Uncovered Element
Now, number of lines drawn = Order of matrix, hence optimality is reached.
There are two alternative assignments due to presence of zero elements in cells
(4, C), (4, D), (5, C) and (5, D).
Two Alternative Assignments
Therefore,
Operations Research for
Managers

NOTES
Operations Research for
Managers
ASSIGNMENT
PROBLEM
107
Multiple Solutions
While making assignment in the reduced assignment matrix, it is possible
to have two or more ways to strike off certain number of zeroes. Such a situation
indicates multiple solutions with the same optimal value of the objective function.
If the problem has only one solution then the solution is said to be Unique
solution.
Business Applications of Assignment Problem
The business applications of Assignment Problem can be described with
the help of following examples.
•The problem instance has a number of agents and a number of tasks. Any
agent can be assigned to perform any task, incurring some cost that may
vary depending on the agent-task assignment. It is required to perform
all tasks by assigning exactly one agent to each task and exactly one task
to each agent in such a way that the total cost of the assignment is
minimized. If the numbers of agents and tasks are equal, and the total
cost of the assignment for all tasks is equal to the sum of the costs for
each agent (or the sum of the costs for each task, which is the same thing
in this case), then the problem is called the linear assignment problem.
Commonly, when speaking of the assignment problem without any
additional qualification, then the linear assignment problem is meant.
•Suppose that a taxi firm has three taxis (the agents) available, and three
customers (the tasks) wishing to be picked up as soon as possible. The
firm prides itself on speedy pickups, so for each taxi the "cost" of picking
up a particular customer will depend on the time taken for the taxi to
reach the pickup point. The solution to the assignment problem will be
whichever combination of taxis and customers results in the least total
cost. However, the assignment problem can be made rather more flexible
than it first appears. In the above example, suppose that there are four
taxis available, but still only three customers. Then a fourth dummy task
can be invented, perhaps called "sitting still doing nothing", with a cost
of 0 for the taxi assigned to it. The assignment problem can then be solved
in the usual way and still give the best solution to the problem. Similar
adjustments can be done in order to allow more tasks than agents, tasks
to which multiple agents must be assigned (for instance, a group of more
customers than will fit in one taxi), or maximizing profit rather than
minimizing cost.
QUESTIONS
Q.1 What is Assignment Problem?
Q.2 Explain Formulation of Assignment Problem.

NOTES
ASSIGNMENT
PROBLEM
108
Q.3 Discuss the following with respect to Assignment Problem
a) Hungarian Method
b)Assignment problem for Maximization
Q.4 Discuss Businss Applications of Assignment Problem.
Q.5 The Funny Toys Company has four men available for work on four
separate jobs. Only one man can work on any one job. The cost of
assigning each man to each job is given in the following table. Assign
men to jobs in such a way that the total cost of assignment is minimum.
Q.6 Four jobs (J1, J2, J3, and J4) need to be executed by four workers (W1,
W2, W3, and W4), one job per worker. The matrix below shows the
cost of assigning a certain worker to a certain job. Assign the jobs so
as to minimize the total cost of the assignment.
*****Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 109
UNI - V
SIMULATION
CHAPTER OBJECTIVES
1. To know the concept of Simulation.
2. To understand advantages of Simulation.
3. To know the Monte Carlo Simulation Technique
CHAPTER CONTENTS
a) Introduction to Simulation
b) Monte Carlo technique
c) business applications and limitations.
OVERVIEW OF THE CHAPTER
This chapter is about understanding the concept of Simulation.Monte Carlo
Simulation Technique is explained in this chapter. After careful study of this
chapter, students will be able to know advantages of Simulation.
KEY WORDS
Simulation, Monte Carlo Technique
INTRODUCTION
5.1 SIMULATION MEANING
A simulation is an approximate imitation of the operation of a process or
system; the act of simulating first requires a model is developed. This model is
a well-defined description of the simulated subject, and represents its key
characteristics, such as its behaviour, functions and abstract or physical
properties. The model represents the system itself, whereas the simulation
represents its operation over time.
Simulation is used in many contexts, such as simulation of technology for
performance optimization, safety engineering, testing, training, education, and
video games. Often, computer experiments are used to study simulation models.
Simulation is also used with scientific modelling of natural systems or human

NOTES
SIMULATION
110
systems to gain insight into their functioning, as in economics. Simulation can
be used to show the eventual real effects of alternative conditions and courses of
action. Simulation is also used when the real system cannot be engaged, because
it may not be accessible, or it may be dangerous or unacceptable to engage, or it
is being designed but not yet built, or it may simply not exist.
Simulation models may be either deterministic or stochastic (meaning
probabilistic). In a deterministic simulation, all of the events and relationships
among the variables are governed entirely by a combination of known, but
possibly complicated, rules . The advantage of simulation is that you can still
answer the question even if the model is too complicated to solve analytically.
In a stochastic simulation, ‘‘random variables’’ are included in the model
to represent the influence of factors that are unpredictable, unknown, or beyond
the scope of the model we use in the simulation..
In many applications, such as a model of the tellers in a bank, it makes sense
to incorporate random variables into the model. In the case of a bank, we might
wish to assume that there is a stream of anonymous customers coming in the
door at unpredictable times, rather than explicitly modeling the behavior of each
of their actual customers to determine when they plan to go to the bank. It is
worth noting here that it is well known in statistics that when we combine the
actions of a large population of more-or-less independently operating entities
(customers, etc.) the resulting behavior appears to have been randomly produced,
and that the patterns of activity followed by the individual entities within that
population are unimportant. For example, all of the telephone systems designed
in the last 60 years are based on the (quite justified) assumption that the number
of calls made in fixed length time intervals obeys the Poisson distribution. Thus
the generation and use of random variables is an important topic in simulation.
5.2 STATIC VERSUS DYNAMIC SIMULATION MODELS
Another dimension along which simulation models can be classified is that
of time. If the model is used to simulate the operation of a system over a period
of time, it is dynamic. The baseball example above uses dynamic simulation. On
the other hand, if no time is involved in a model, it is static. Many gambling
situations (e.g., dice, roulette) can be simulated to determine the odds of winning
or losing. Since only the number of bets made, rather than the duration of
gambling, matters, static simulation models are appropriate for them
5.3 MONTE CARLO SIMULATION
Monte Carlo Simulation refers to the type of simulation in which a static,
approximate, and stochastic model is used for a deterministic system.Let us now
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 111
look at an example of Monte Carlo simulation. Consider estimating the value of
p by finding the approximate area of a circle with a unit radius. The first quadrant
of the circle is enclosed by a unit square.If pairs of uniformly distributed pseudo-
random values for the x and y coordinates in [0, 1] are generated, the probability
of the corresponding points falling in the quarter circle is simply the ratio of the
area of the quarter circle to that of the unit square.
The above program is an example of Monte Carlo integration, by which
definite integral of arbitrary but finite functions can be estimated. Consider the
following integral:
Such an integral can be partitioned into segments above or below the
horizontal axis. Without loss of generality, let us assume f (x)³0, a £ x £ b. We
can then bound the curve with a rectangle with borders of x = a, x = b, y = 0, and
y = y max, where y max is the maximum value of f (x) in the interval [a, b]. By
generating random points uniformly distributed over this rectangular area, and
deciding whether they fall above or below the curve f (x), we can estimate the
integral.
5.4 DYNAMIC SIMULATION
In the remainder of chapter, dynamic stochastic simulation models will be
emphasized. A dynamic simulation program that is written in a general purpose
programming language (such as Turing) must:
i)Keep track of simulated time,
ii)Schedule events at ‘‘simulated’’ times in the future, and
iii)Cause appropriate changes in state to occur when ‘‘simulated’’ time
reaches the time at which one or more events take place.
The structure of a simulation program may be either time-driven or event-
driven, depending on the nature of the basic loop of the program. In time-driven
models, each time through the basic loop, simulated time is advanced by some
‘‘small’’ (in relation to the rates of change of the variables in the program) fixed
amount, and then each possible event type is checked to see which, if any, events
have occurred at that point in simulated time. In event-driven models, events of
various types are scheduled at future points in simulated time. The basic program
loop determines when the next scheduled event should occur, as the minimum
of the scheduled times of each possible event. Simulated time is then advanced
to exactly that event time, and the corresponding event handling routine is
executed to reflect the change of state that occurs as a result of that event.

NOTES
SIMULATION
112
5.5 CONSTRUCTING A SIMULATION MODEL
1.Identification of Components
First task is to identify those system components that should be
included in the model. This choice depends not only on the real system,
but also on the aspects of its behavior that we intend to investigate.
The only complete model of a system is the system itself. Any other
model includes assumptions or simplifications. Some components of
a system may be left out of the system model if their absence is not
expected to alter the aspects of behavior that we wish to observe.
Assume that the bank automation problem specification includes the
following information:
i)the times between successive arrivals of customers, expressed as
a probability distribution,
ii)the distribution of the number of liters of gasoline needed by
customers,
iii)the distribution of how long service at the pump takes as a
function of the number of litres needed,
iv)the probability that an arriving customer will balk as a function
of the number of cars already waiting at the service station and
the number of liters of gasoline he needs,
v)the profit per liter of gasoline sold, and
vi)the cost per day of running a pump (including an attendant’s
salary, etc.).
2.Entities
Customers, resources, service facilities, materials, service personnel,
etc., are entities. Each type of entity has a set of relevant attributes. In
our service station example, the entities are cars, with the attributes
arrival time and ‘number of liters needed, and pumps, with the attribute
time to the completion of service to the current customer.
3.Events
Events are occurrences that alter the system state. Here the events are
the arrival of a customer at the station, the start-of-service to a
customer at a pump, and the completion-of- service to a customer at a
pump. The first arrival event must be scheduled in the initialization
routine; the remaining arrivals are handled by letting each invocation
of the arrival routine schedule the next arrival event. The scheduling
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 113
of a start-of-service event takes place either in the arrival routine, if
there are no other cars waiting and a pump is available, or in the
completion-of service routine, otherwise. Each time the start-of-service
routine is invoked, the completion-of-service at that pump is
scheduled.
Besides the types of events identified in the real system, there are two
other pseudo-events that should be included in every simulation
program. End-of-simulation halts the simulation after a certain amount
of simulated time has elapsed, and initiates the final output of the
statistics and measurements gathered in the run. End-of simulation
should be scheduled during the initialization of an event-driven
simulation; for time-driven simulations, it is determined by the upper
bound of the basic program loop. A progress-report event allows a
summary of statistics and measurements to be printed after specified
intervals of simulated time have elapsed. These progress-report
summaries can be used to check the validity of the program during its
development, and also to show whether or not the system is settling
down to some sort of equilibrium (i.e., stable) behavior.
4.Groupings
Similar entities are often grouped in meaningful ways. Sometimes an
ordering of the entities within a group is relevant. In the service station
example, the groupings are available pumps (that are not currently
serving any auto), busy pumps (ordered by the service completion time
for the customer in service), and autos awaiting service (ordered by
time of arrival). In a Turing program, such groupings can be
represented as linked lists of records, as long as a suitable link field is
included in the records for that entity type.
5.Relationships
Pairs of non-similar entities may be related. For example, a busy pump
is related to the auto that is being served. Relationships can be
indicated by including in the record for one of the entities in a pair a
link to the other entity. In some cases, it may be desirable for each of
the entities in the pair to have a link to the other entity. For example,
the relationship between a busy pump and the auto being served can
be represented by a link from the pump record to the corresponding
auto record.
6.Stochastic Simulation
In a stochastic simulation, certain attributes of entities or events must
be chosen at random from some probability distribution. In the service
station example, these include the customer inter arrival times (i.e.,
the times between successive arrivals), the number of liters needed,

NOTES
SIMULATION
114
the service time (based on the number of liters needed), and whether
the customer decides to balk (based on the length of the waiting queue
and the number of liters needed).
7.Strategies
Typically, a simulation experiment consists of comparing several
alternative approaches to running the system to find out which one(s)
maximize some measure of system performance. In the case of the
service station, the strategies consist of keeping different numbers of
pumps in service.
8.Measurements
The activity of the system will be reflected in measurements associated
with entities, events, groups, or relationships. Such measurements are
used in specifying the performance of the system. If the measurement
is associated with an entity, it should be recorded in a field contained
within the record for that entity. For measurements associated with
events, groupings or relationships, additional variables or records must
be declared to record the measured quantities.
5.6 ADVANTAGES AND DISADVANTAGES OF SIMULATION
Competition in the computer industry has led to technological
breakthroughs that are allowing hardware companies to continually produce
better products. It seems that every week another company announces its latest
release, each with more options, memory, graphics capability, and power.
What is unique about new developments in the computer industry is that
they often act as a springboard for other related industries to follow. One industry
in particular is the simulation software industry. As computer hardware becomes
more powerful, more accurate, faster, and easier to use, simulation software
does too.
The number of businesses using simulation is rapidly increasing. Many
managers are realizing the benefits of utilizing simulation for more than just the
one-time remodeling of a facility. Rather, due to advances in software, managers
are incorporating simulation in their daily perations on an increasingly regular
basis.
Advantages
For most companies, the benefits of using simulation go beyond just
providing a look into the future and are included in the following:
Choose Correctly.Simulation lets you test every aspect of a proposed
change or addition without committing resources to their acquisition. This is
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 115
critical, because once the hard decisions have been made, the bricks have been
laid, or the material-handling systems have been installed, changes and
corrections can be extremely expensive. Simulation allows to test the designs
without committing resources to acquisition.
Time Compression and Expansion. By compressing or expanding time
simulation allows to speed up or slow down phenomena so that you can
thoroughly investigate them. One can examine an entire shift in a matter of
minutes if one desire, or can spend two hours examining all the events that
occurred during one minute of simulated activity.
Explore Possibilities. One of the greatest advantages of using simulation
software is that once developed a valid simulation model, one can explore new
policies, operating procedures, or methods without the expense and disruption
of experimenting with the real system. Modifications are incorporated in the
model, and you observe the effects of those changes on the computer rather than
the real system.
Diagnose Problems. The modern factory floor or service organization is
very complex. So complex that it is impossible to consider all the interactions
taking place in one given moment. Simulation allows to better understand the
interactions among the variables that make up such complex systems. Diagnosing
problems and gaining insight into the importance of these variables increases
understanding of their important effects on the performance of the overall system.
The last three claims can be made for virtually all modeling activities,
queuing, linear programming, etc. However, with simulation the models can
become very complex and, thus, have a higher fidelity, i.e., they are valid
representations of reality.
Identify Constraints. Production bottlenecks give manufacturers
headaches. It is easy to forget that bottlenecks are an effect rather than a cause.
However, by using simulation to perform bottleneck analysis, you can discover
the cause of the delays in work-in-process, information, materials, or other
processes.
Develop Understanding. Many people operate with the philosophy that
talking loudly, using computerized layouts, and writing complex reports
convinces others that a manufacturing or service system design is valid. In many
cases these designs are based on someone's thoughts about the way the system
operates rather than on analysis. Simulation studies aid in providing
understanding about how a system really operates rather than indicating an
individual's predictions about how a system will operate.
Visualize the Plan. Taking designs beyond CAD drawings by using the
animation features offered by many simulation packages allows you to see your
facility or organization actually running. Depending on the software used, one
may be able to view your operations from various angles and levels of
magnification, even 3-D. This allows to detect design flaws that appear credible
when seen just on paper on in a 2-D CAD drawing.

NOTES
SIMULATION
116
Build Consensus. Using simulation to present design changes creates an
objective opinion. One can avoid having inferences made when it is approved or
disapproved of designs because one can simply select the designs and
modifications that provided the most desirable results, whether it be increasing
production or reducing the waiting time for service. In addition, it is much easier
to accept reliable simulation results, which have been modeled, tested, validated,
and visually represented, instead of one person's opinion of the results that will
occur from a proposed design.
Prepare for Change. Answering all of the "what-if" questions is useful for
both designing new systems and redesigning existing systems. Interacting with
all those involved in a project during the problem- formulation stage gives an
idea of the scenarios that are of interest. Then one can construct the model so
that it answers questions pertaining to those scenarios.
Wise Investment. The typical cost of a simulation study is substantially
less than 1% of the total amount being expended for the implementation of a
design or redesign. Since the cost of a change or modification to a system after
installation is so great, simulation is a wise investment.
Train the Team. Simulation models can provide excellent training when
designed for that purpose. Used in this manner, the team provides decision inputs
to the simulation model as it progresses. The team, and individual members of
the team, can learn by their mistakes, and learn to operate better. This is much
less expensive and less disruptive than on-the-job learning.
Specify Requirements. Simulation can be used to specify requirements for
a system design. For example, the specifications for a particular type of machine
in a complex system to achieve a desired goal may be unknown. By simulating
different capabilities for the machine, the requirements can be established.
B. Disadvantages
The disadvantages of simulation include the following
Model Building Requires Special Training. It is an art that is learned over
time and through experience. Furthermore, if two models of the same system are
constructed by two competent individuals, they may have similarities, but it is
highly unlikely that they will be the same.
Simulation Results May Be Difficult to Interpret. Since most simulation
outputs are essentially random variables (they are usually based on random
inputs), it may be hard to determine whether an observation is a result of system
interrelationships or randomness.
Simulation Modeling and Analysis Can Be Time Consuming and
Expensive.
Skimping on resources for modeling and analysis may result in a simulation
model and/or analysis that is not sufficient for the task.
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 117
Simulation May Be Used Inappropriately. Simulation is used in some cases
when an analytical solution is possible, or even preferable. This is particularly
true in the simulation of some waiting lines where closed-form queueing models
are available, at least for long-run evaluation.
Pseudo-Random Number Generation
Probability is used to express our confidence in the outcome of some
random event as a real number between 0 and 1. An outcome that is impossible
has probability 0; one that is inevitable has probability 1. Sometimes, the
probability of an outcome is calculated by recording the outcome for a very large
number of occurrences of that random event (the more the better), and then taking
the ratio of the number of events in which the given outcome occurred to the
total number of events.
It is also possible to determine the probability of an event in a non-
experimental way, by listing all possible non-overlapping outcomes for the
experiment and then using some insight to assign a probability to each outcome.
For example, we can show that the probability of getting ‘‘heads’’ twice during
three coin tosses should be 3/8 from the following argument. First, we list all
eight possible outcomes for the experiment (TTT, TTH, THT, THH, HTT, HTH,
HHT, HHH). Next, we assign equal probability to each outcome (i.e., 1/8),
because a ‘‘fair’’ coin should come up heads half the time, and the outcome of
one coin toss should have no influence on another. (In general, when we have no
other information to go on, each possible outcome for an experiment is assigned
the same probability.) And finally, we observe that the desired event (namely two
H’s) includes three of these outcomes, so that its probability should be the sum
of the probabilities for those outcomes, namely 3/8.
A random variable is a variable, say X, whose value, x, depends on the
outcome of some random event. For example, we can define a random variable
that takes on the value of 1 whenever ‘‘heads’’ occurs and 0 otherwise.
5.7 GENERATING UNIFORM PSEUDO-RANDOM NUMBERS
Since the result of executing any computer program is in general both
predictable and repeatable the idea that a computer can be used to generate a
sequence of random numbers seems to be a contradiction. There is no
contradiction, however, because the sequence of numbers that is actually
generated by a computer is entirely predictable once the algorithm is known.
Such algorithmically generated sequences are called pseudo-random sequences
because they appear to be random in the sense that a good pseudo-random
number sequence can pass most statistical tests designed to check that their
distribution is the same as the intended distribution. On the other hand, to call
them random numbers is no worse than it is to label floating point numbers as

NOTES
SIMULATION
118
real numbers in a programming language.It is worth noting that the availability
of pseudo-random (rather than truly random) numbers is actually an advantage
in the design of simulation experiments, because it means that random numbers
are reproducible.
In general, most pseudo-random number generators produce uniform
values. (This does not lead to a loss of generality because, as we shall see in the
next section, uniform values can be transformed into other distributions.)
5.8 PROGRESS IN A SIMULATION STUDY
1.Problem formulation
Every simulation study begins with a statement of the problem. If the
statement is provided by those that have the problem (client), the
simulation analyst must take extreme care to insure that the problem
is clearly understood. If a problem statement is prepared by the
simulation analyst, it is important that the client understand and agree
with the formulation. It is suggested that a set of assumptions be
prepared by the simulation analyst and agreed to by the client. Even
with all of these precautions, it is possible that the problem will need
to be reformulated as the simulation study progresses.
2.Setting of objectives and overall project plan
Another way to state this step is prepare a proposal. This step should
be accomplished regardless of location of the analyst and client, viz.,
as an external or internal consultant.
The objectives indicate the questions that are to be answered by the
simulation study. The project plan should include a statement of the
various scenarios that will be investigated. The plans for the study
should be indicated in terms of time that will be required, personnel
that will be used, hardware and software requirements if the client
wants to run the model and conduct the analysis, stages in the
investigation, output at each stage, cost of the study and billing
procedures, if any.
3.Model conceptualization
The real-world system under investigation is abstracted by a
conceptual model, a series of mathematical and logical relationships
concerning the components and the structure of the system. It is
recommended that modeling begin simply and that the model grow
until a model of appropriate complexity has been developed. For
example, consider the model of a manufacturing and material handling
system. The basic model with the arrivals, queues and servers is
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 119
constructed. Then, add the failures and shift schedules. Next, add the
material-handling capabilities. Finally, add the special features.
Constructing an unduly complex model will add to the cost of the study
and the time for its completion without increasing the quality of the
output. Maintaining client involvement will enhance the quality of the
resulting model and increase the client's confidence in its use.
4.Data collection
Shortly after the proposal is accepted a schedule of data requirements
should be submitted to the client. In the best of circumstances, the
client has been collecting the kind of data needed in the format
required, and can submit these data to the simulation analyst in
electronic format. Oftentimes, the client indicates that the required data
are indeed available. However, when the data are delivered they are
found to be quite different than anticipated.
5.Model translation
The conceptual model constructed in Step 3 is coded into a computer
recognizable form, an operational model.
6.Verification
Verification concerns the operational model. Is it performing properly.
Even with small textbook sized models, it is quite possible that they
have verification difficulties. It is highly advisable that verification
take place as a continuing process. It is ill advised for the simulation
analyst to wait until the entire model is complete to begin the
verification process. Also, use of an interactive run controller, or
debugger, is highly encouraged as an aid to the verification process.
7.Validation
Validation is the determination that the conceptual model is an accurate
representation of the real system.
8.Experimental design
For each scenario that is to be simulated, decisions need to be made
concerning the length of the simulation run, the number of runs (also
called replications), and the manner of initialization, as required.
9.Production runs and analysis
Production runs, and their subsequent analysis, are used to estimate
measures of performance for the scenarios that are being simulated.
10.More runs
Based on the analysis of runs that have been completed, the simulation
analyst determines if additional runs are needed and if any additional
scenarios need to be simulated.

NOTES
SIMULATION
120
11.Documentation and reporting
Documentation is necessary for numerous reasons. If the simulation
model is going to be used again by the same or different analysts, it
may be necessary to understand how the simulation model operates.
This will enable confidence in the simulation model so that the client
can make decisions based on the analysis. Also, if the model is to be
modified, this can be greatly facilitated by adequate documentation.
The result of all the analysis should be reported clearly and concisely.
This will enable the client to review the final formulation, the
alternatives that were addressed, the criterion by which the alternative
systems were compared, the results of the experiments, and analyst
recommendations, if any.
12.Implementation
The simulation analyst acts as a reporter rather than an advocate. The
report prepared in step 11 stands on its merits, and is just additional
information that the client uses to make a decision. If the client has
been involved throughout the study period, and the simulation analyst
has followed all of the steps rigorously, then the likelihood of a
successful implementation is increased.
Example
Akshay Bakery maintains sufficient stock of cake. The daily demand is
given below:
Using the following sequence of random numbers, simulate the demand for
the next 12 days. If the proprietor of the bakery decides to make 40 cakes
everyday, calculate the stock position at the end of the 12th day. Also calculate
the daily average demand for the cakes.
Random Numbers: 36,29,84,57,19,79,46,67,08,81,87,94
Solution
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 121
Following is theschedule of simulated demand for the first 12 days.
Total Demand = 480
Average Daily Demand = 480/12 = 40 Cakes per day
Example :A dealer sells a particular model of washing machine for which
the probability distribution of daily demand is as given in Table.
Probability Distribution of Daily Demand
Simulation Problems using Random numbers
The simulation problems using random numbers are given below
Find the average demand of washing machines per day.
Solution: Assign sets of two digit random numbers to demand levels as
shown in Table.
Random Numbers Assigned to Demand
Ten random numbers that have been selected from random number tables
are 68, 47, 92, 76, 86, 46, 16, 28, 35, 54. To find the demand for ten days see the
Table below.

NOTES
SIMULATION
122
Table 5.1: Ten Random Numbers Selected
Average demand =28/10 =2.8 washing machines per day. The expected
demand /day can be computed as,
Expected demand per day
where, pi = probability and xi = demand
= (0.05 × 0) + (0.25 × 1) + (0.20 × 2) + (0.25 × 3) + (0.1 × 4) + (0.15 × 5)
= 2.55 washing machines.
The average demand of 2.8 washing machines using ten-day simulation
differs significantly when compared to the expected daily demand. If the
simulation is repeated number of times, the answer would get closer to the
expected daily demand.
Example :A farmer has 10 acres of agricultural land and is cultivating
tomatoes on the entire land. Due to fluctuation in water availability, the yield per
acre differs. The probability distribution yields are given below:
a. The farmer is interested to know the yield for the next 12 months if
the same water availability exists. Simulate the average yield using the
following random numbers 50, 28, 68, 36, 90, 62, 27, 50, 18, 36, 61
and 21, given in table.
Simulation Problem
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 123
b. Due to fluctuating market price, the price per kg of tomatoes varies
from Rs. 5.00 to Rs. 10.00 per kg. The probability of price variations
is given in the Table below. Simulate the price for next 12 months to
determine the revenue per acre. Also find the average revenue per acre.
Use the following random numbers 53, 74, 05, 71, 06, 49, 11, 13, 62,
69, 85 and 69.
Simulation Problem
Solution
Table for Random Number Interval for Yield
Table for Random Number Interval for Price
Simulation for 12 months period
Average revenue per acre = 21330 / 12
= Rs. 1777.50
Example : J.M. Bakers has to supply only 200 pizzas every day to their
outlet situated in city bazaar. The production of pizzas varies due to the
availability of raw materials and labor for which the probability distribution of
production by observation made is as follows:

NOTES
SIMULATION
124
Simulation Problem
Simulate and find the average number of pizzas produced more than the
requirement and the average number of shortage of pizzas supplied to the outlet.
Solution: Assign two digit random numbers to the demand levels as shown
in table
Random Numbers Assigned to the Demand Levels
Selecting 15 random numbers from random numbers table and simulate the
production per day as shown in table below.
Simulation of Production Per Day
The average number of pizzas produced more than requirement
= 12/15
= 0.8 per day
Operations Research for
Managers

NOTES
Operations Research for
Managers
SIMULATION 125
The average number of shortage of pizzas supplied
= 4/15
= 0.26 per day
QUESTIONS
Q.1 What is Simulation? Explain advantages of Simulation.
Q.2 Discuss Monte Carlo Simulation Technique.
Q3Explain Simulation Modelling.
4. Explain Monte Carlo Simulation Technique pointing out its uses in
Operations Research.
5. An ice-cream parlor's record of previous month’s sale of a particular
variety of ice cream as follows:
Simulation of Demand Problem
Simulate the demand for first 10 days of the month
*****

NOTES
NETWORK ANALYSIS126
UNIT - VI
NETWORK ANALYSIS
CHAPTER OBJECTIVES
1. To equip students with fundamentals of Network Analysis
2. To acquaint the students with PERT and CPM Techniques.
3. To enable the students to determine Critical Path.
CHAPTER CONTENTS
a) PERT and CPM techniques
b) Introduction to Networks
c) key terms in Network Analysis
d) Network models − PERT/CPM network components and precedence
relationships.
e) Critical Path Method (CPM), Program Evaluation and Review
Technique (PERT).
f) Determination of PERT times
g) Determining the critical path − determining the floats and slacks.
OVERVIEW OF THE CHAPTER
This chapter deals with understanding Network Analysis. It focuses on
PERT and CPM Techniques. Key terms in Network Analysis and determination
of Critical Path is discussed in this chapter.
KEY WORDS
Network Analysis, PERT, CPM, Critical Path
INTRODUCTION TO NETWORKS
One of the most challenging jobs that any manager can take on is the
management of a large-scale project that requires coordinating numerous
activities throughout the organi-zation. A myriad of details must be considered
in planning how to coordinate all these activities, in developing a realistic
schedule, and then in monitoring the progress of the project.
Fortunately, two closely related operations research techniques, PERT
(program evaluation and review technique) and CPM (critical path method), are
available to assist the project manager in carrying out these responsibilities. These
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
127
techniques make heavy use of networks (as introduced in the preceding chapter)
to help plan and display the coordination of all the activities. They also normally
use a software package to deal with all the data needed to develop schedule
information and then to monitor the progress of the project.
PERT and CPM have been used for a variety of projects, including the
following types:
1. Construction of a new plant
2. Research and development of a new product
3. NASA space exploration projects
4. Movie productions
5. Building a ship
6. Government-sponsored projects for developing a new weapons system
7. Relocation of a major facility
8. Maintenance of a nuclear reactor
9. Installation of a management information system
10. Conducting an advertising campaign
A project is defined by a set of activities. Each activity is defined by its
duration (time to complete the activity) and its predecessors (activities that must
be completed before the activity can start). CPM (Critical Path Method) is used
to assist the project manager in scheduling the activities (i.e., when should each
activity start). It assumes that activity durations are known with certainty.
PERT (Program Evaluation and Review Technique) is used to assist in
project scheduling similar to CPM. However, PERT assumes that activity
durations are random variables (i.e., probabilistic)
The first step in CPM/PERT is to construct a project network. In the project
network each activity is represented by an arc connected by two nodes. The first
node represents the start of the activity and the second node represents the end
of it.
Activity
The network should reflect activities precedence relations.
Unfortunately, PERT/CPM techniques were credited for the early
completion of the submarine-launched Polaris nuclear missile.

NOTES
NETWORK ANALYSIS128
6.1 FULKERSON'S RULE OF NUMBERING EVENTS
An event represents the accomplishment of task. In a network diagram,
beginning and ending of an activity are represented as events.
Step1: Number the start or initial event as 1.
Step2: From event 1, strike off all outgoing activities. This would have
made one or more events as initial events (event which do not have incoming
activities).
Number that event as 2.
Step3:Repeat step 2 for event 2, event 3 and till the end event. The end
event must have the highest number.
Example :Draw a network for a house construction project. The sequence
of activities with their predecessors is given in the following table, below.
Sequence of Activities for House Construction Project
Solution
Network diagram representing house construction project.
The network diagram in the above figure shows the procedure relationship
between the activities. Activity A (preparation of house plan), has a start event 1
as well as an ending event 2. Activity B (Construction of house) begins at event
2 and ends at event 3.
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
129
The activity B cannot start until activity A has been completed. Activities
C and D cannot begin until activity B has been completed, but they can be
performed simultaneously. Similarly, activities E and F can start only after
completion of activities C and D respectively. Both activities E and F finish at
the end of event 6.
Example : Consider the project given in the following table and construct
a network diagram.
Sequence of Activities for Building Construction Project
Solution: The activities C and D have a common predecessor A. The
network representation shown in Figure Network representing the Error violates
the rule that no two activities canbegin and end at the same events. It appears as
if activity B is a predecessor of activity C, which is not the case. To construct the
network in a logical order, it is necessary to introduce a dummy activity as shown
in Figure.
Network representing the Error
Correct representation of Network using Dummy Activity

NOTES
NETWORK ANALYSIS130
Example : Construct a network for a project whose activities and their
predecessor relationship are given in Table.
Activity Sequence for a Project
Solution: The network diagram for the given problem is shown in Figure
with activities A, B and C starting simultaneously.
Network Diagram
Example :Draw a network diagram for a project given in Table.
Project Activity Sequence
Solution: An activity network diagram describing the project is shown in
figure below:
Network Diagram
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
131
6.2 CRITICAL PATH
The critical path for any network is the longest path through the entire
network. Since all activities must be completed to complete the entire project,
the length of the critical path is also the shortest time allowable for completion
of the project. Thus if the project is to be completed in that shortest time, all
activities on the critical path must be started as soon as possible.
These activities are called critical activities. If the project has to be
completed ahead of the schedule, then the time required for at least one of the
critical activity must be reduced. Further, any delay in completing the critical
activities will increase the project duration.
The activity, which does not lie on the critical path, is called non-critical
activity. These non-critical activities may have some slack time. The slack is the
amount of time by which the start of an activity may be delayed without affecting
the overall completion time of the project. But a critical activity has no slack. To
reduce the overall project time, it would require more resources (at extra cost) to
reduce the time taken by the critical activities to complete.
6.3 SCHEDULING OF ACTIVITIES: EARLIEST TIME
AND LATEST TIME
Before the critical path in a network is determined, it is necessary to find
the earliest and latest time of each event to know the earliest expected time (TE)
at which the activities originating from the event can be started and to know the
latest allowable time (TL) at which activities terminating at the event can be
completed.
Forward Pass Computations (to calculate Earliest, Time TE)
Procedure
Step 1:Begin from the start event and move towards the end event.
Step 2: Put TE = 0 for the start event.
Step 3:Go to the next event (i.e node 2) if there is an incoming activity for
event 2, add calculate TE of previous event (i.e event 1) and activity time.
Note:If there are more than one incoming activities, calculate TE for all
incoming activities and take the maximum value. This value is the TE for event 2.
Step 4: Repeat the same procedure from step 3 till the end event.

NOTES
NETWORK ANALYSIS132
Backward Pass Computations (to calculate Latest Time T Network Model L)
Procedure
Step 1: Begin from end event and move towards the start event. Assume
that the direction of arrows is reversed.
Step 2:Latest Time TL for the last event is the earliest time. TE of the last
event.
Step 3: Go to the next event, if there is an incoming activity, subtract the
value of TL of previous event from the activity duration time. The arrived value
is TL for that event. If there are more than one incoming activities, take the
minimum TE value.
Step 4:Repeat the same procedure from step 2 till the start event.
Head event slack and Tail event slack
The head event slack of an activity in a network is the slack at the head.The
tail event slack of an activity in a network is the slack at the tail.
As discussed earlier, the non – critical activities have some slack or float.
The float of an activity is the amount of time available by which it is possible to
delay its completion time without extending the overall project completion time.
For an activity i = j, let
t
ij= duration of activity
TE = earliest expected time
T
L= latest allowable time
ES
ij= earliest start time of the activity
EF
ij= earliest finish time of the activity
LS
ij= latest start time of the activity
LF
ij= latest finish time of the activity
A) Total Float TFij: The total float of an activity is the difference between
the latest start
time and the earliest start time of that activity.
TF
ij= LS ij– ES ij....................(1)
or
TF
ij= (T L – TE) – t ij....................(2)
B) Free Float FFij: The time by which the completion of an activity can be
delayed from its earliest finish time without affecting the earliest start time of
the succeeding activity is called free float.
FF
ij= (E j– Ei) – tij....................(3)
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
133
FFij= Total float – Head event slack
C) Independent Float IFij: The amount of time by which the start of an
activity can be delayed without affecting the earliest start time of any immediately
following activities, assuming that the preceding activity has finished at its latest
finish time.
IF
ij= (E j– Li) – tij....................(4)
IF
ij= Free float – Tail event slack
Where tail event slack = L
i – Ei
The negative value of independent float is considered to be zero.
Critical Path: After determining the earliest and the latest scheduled times
for various activities, the minimum time required to complete the project is
calculated. In a network, among various paths, the longest path which determines
the total time duration of the project is called the critical path. The following
conditions must be satisfied in locating the critical path of a network.
An activity is said to be critical only if both the conditions are satisfied.
1. T
L– TE= 0
2. T
Lj– tij– TE j= 0
Example : A project schedule has the following characteristics as shown
in the table
Project Schedule
i. Construct PERT network.
ii. Compute TE and TL for each activity.
iii. Find the critical path.
Solution
(i) From the data given in the problem, the activity network is constructed
as shown in the following figure.

NOTES
NETWORK ANALYSIS134
Activity Network Diagram
(ii) To determine the critical path, compute the earliest, time T Network
Model E and latest time TL for each of the activity of the project. The
calculations of TE and TL are as follows:
To calculate TEfor all activities,
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
135
Various Activities and their Floats
(iii) From the table, we observe that the activities 1 – 3, 3 – 5, 5 – 7,7 – 8
and 8 – 10 are critical activities as their floats are zero.
Critical Path of the Project
The critical path is 1-3-5-7-8-10 (shown in double line in the above figure)
with the project duration of 22 days.

NOTES
NETWORK ANALYSIS136
6.4 PROGRAMME REVIEW TECHNIQUES
The Programme review techniques are
In the critical path method, the time estimates are assumed to be known
with certainty. In certain projects like research and development, new product
introductions, it is difficult to estimate the time of various activities. Hence PERT
is used in such projects with a probabilistic method using three time estimates
for an activity, rather than a single estimate, as shown in Figure.
PERT Using Probabilistic Method with 3 Time Estimates
Optimistic time tO
It is the shortest time taken to complete the activity. It means that if
everything goes well then there is more chance of completing the activity within
this time.
Most likely time tm
It is the normal time taken to complete an activity, if the activity were
frequently repeated under the same conditions.
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
137
Pessimistic time tp
It is the longest time that an activity would take to complete. It is the worst
time estimate that an activity would take if unexpected problems are faced.
Taking all these time estimates into consideration, the expected time of an
activity is arrived at.
The average or mean (ta) value of the activity duration is given by,
T
a= t0+4tm+tp/6 .....................(5)
The variance of the activity time is calculated using the formula,
T
a= t0+4tm+tp/6 ...................(6)
Probability for Project Duration
The probability of completing the project within the scheduled time (Ts) or
contracted time may be obtained by using the standard normal deviate where Te
is the expected time of project completion.
...............(7)
Probability of completing the project within the scheduled time is,
P (T≤ Ts) = P ( Z≤ Z0 ) (from normal tables) .................(8)
Example : An R & D project has a list of tasks to be performed whose time
estimates are given in the table, as follows.
Time expected for each activity is calculated using the formula (5):
T
a= t0+4tm+tp/6
= 4+4(6)+8/6 = 36/6 = 6 days for activity A
Similarly, the expected time is calculated for all the activities. The variance
of activity time is calculated using the formula (6).
Similarly, variances of all the activities are calculated. Construct a network
diagram and calculate the time earliest, TE and time Latest TL for all the
activities.

NOTES
NETWORK ANALYSIS138
Network Diagram
Time Estimates for R & D Project
a.Draw the project network.
b.Find the critical path.
c.Find the probability that the project is completed in 19 days. If the
probability is less that 20%, find the probability of completing it in 24
days.
Solution
Calculate the time average ta and variances of each activity as shown in the
following table.
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
139
Te & s2 Calculated
From the network diagram Figure, the critical path is identified as 1-4, 4-6,
6-7, with project duration of 22 days. The probability of completing the project
within 19 days is given by,
Thus, the probability of completing the R & D project in 19 days is 9.01%.
Since the probability of completing the project in 19 days is less than 20%, we
find the probability of completing it in 24 days.

NOTES
NETWORK ANALYSIS140
QUESTIONS
Q.1 What do you mean by Network? Explain Network Analysis concept
with suitable examples.
Q.2 What is CPM?
Q.3 Explain PERT Technique.
Q.4 Differentiate between PERT and CPM
Q.5. An assembly is to be made from two parts X and Y. Both parts must
be turned on a lathe Y must be polished where as X need not be
polished. The sequence of acitivities, together with their predecessors,
is given below
Draw a network diagram of activities for the project.
6) The following details are available regarding a project:
Determine the critical path, the critical activities and the project completion time.
Operations Research for
Managers

NOTES
Operations Research for
Managers
NETWORK ANALYSIS
141
7) Two experts A and B examined an activity and arrived at the following
time estimates.
Determine which expert is more certain about his estimates of time:
BIBLIOGRAPHY
1. Operations Research- Aditham B. Rao, Jaico Publishing House, 1st
edition
2. Operations Research- S.D.Sharma, Kedar Nath Ram Nath & Co.
Publishers, Meerut, 10th edition
3. Frederick S. Hillier & Gerald J. Lieberman, Introduction to Operations
Research, McGraw-Hill: Boston MA; 10th Edition, 2014
4. Taha, Hamdy A., "Operations Research: An Introduction", Pearson,
10th Edition, 2016
5. Robert J. Thierauf & Richard A. Grosse, "Decision Making Through
Operations Research", John Wiley & Sons, INC, 1970
6. Harvey M. Wagner, Principles of Operations Research, Englewood
Cliffs, Prentice-Hall
7. International Journal of Operations Research and Information Systems
(IJORIS)
8. https://staff.aub.edu.lb
9. https://www.math.upatras.gr
10. https://nptel.ac.in
11. https://hithaldia.in
12. https://businessjargons.com
13. https://www.wisdomjobs.com
14. https://www.coursehero.com
*****

MBA 302 Operation Research(1).pdf

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

MBA 302 Operation Research(1).pdf

About This Presentation

Slide Content

Slide 1

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78