St.

Joseph’s College of Commerce (Autonomous), Bangalore

CHAPTER -1 : INTRODUCTION TO OPERATION RESEARCH

Evaluation of Operation Research:

During the Second World War, England had very limited military resources. They felt the urgent need to
allocate the scarce resources in an efficient manner to the various military operations. So they used
Operations Research (OR) for the first time. England made OR teams. These teams included expert
mathematicians, scientists, biologists, physicists, psychologists, engineers, statisticians, etc. These OR teams
were very successful in solving England’s war problems. Their efforts were instrumental in winning the “Air
battle of Britain”, “Battle of the North Atlantic” and the “Island Campaign in the Pacific”. The success of the
team encouraged the USA, Canada and France to adopt OR to solve their war problems. Slowly industries
and businesses also started using Operations Research to solve their complex management problems.

Meaning of Operations Research:

Operations Research means to apply scientific and mathematical methods for decision making and problem
solving. Operations Research does not provide decisions. It provides quantitative data to managers. The
managers use these data for decision making. OR tries to find better solutions to different problems. Hence
it is used to solve complex management problems.

Operations research (OR) is an analytical method of problem-solving and decision-making that is useful in the
management of organizations. In operations research, problems are broken down into basic components and
then solved in defined steps by mathematical analysis.

Analytical methods used in OR include mathematical logic, simulation, network analysis, queuing theory ,
and game theory . The process can be broadly broken down into three steps.

A set of potential solutions to a problem is developed. (This set may be large.)

The alternatives derived in the first step are analyzed and reduced to a small set of solutions most likely to
prove workable.

The alternatives derived in the second step are subjected to simulated implementation and, if possible,
tested out in real-world situations. In this final step, psychology and management science often play
important roles.

Definition of Operations Research:

“Operations Research is concerned with scientifically deciding how to best design and operate man-machine
systems usually requiring the allocation of scarce resources”. – Operations Research Society – America.

“Operations Research is the art of giving bad answers to problems, to which otherwise have worse answers”.
– T.L. Saaty.

Compiled by Dr. Suganthi Pais Page

1
 St. Joseph’s College of Commerce (Autonomous), Bangalore
FEATURES OF OPERATIONS RESEARCH

1. System Orientation: OR study the situation or problem as a whole. This means that any action or
activity has some effect on the other part of the organization. Therefore to evaluate a decision, one
must identify all possible interactions and determine their impact on the organization as a whole.
2. Inter-disciplinary approach: According to this characteristic, no single person can be an expert on all
aspects of a problem under consideration. Thus OR uses inter-disciplinary approach i.e., an OR team
comprising of experts from different disciplines. Such a team when confronted with a problem, may
be in a position to suggest an approach that otherwise may not have been thought of.
3. Scientific approach: OR uses the scientific methods to solve the problems. So, it is a formalized
process of reasoning.
4. Decision making: OR increases the effectiveness of a management decisions. It is thus a decision
science which helps management to make better decisions.
5. Use of Computer: OR requires a computer to solve the complex mathematical model or to perform
large number of computations. Use of digital computer has become an integral part of the operations
research approach to decision making.
6. Objectives: OR attempts to provide the best and optimal solution to a given problem.
7. Quantitative solution: OR provides the management with a quantitative basis for decision making.
8. Human factors: OR does not take into consideration the human factors which doubtlessly play a
great role in the problems.
9. Continuing Process: OR is a continuing process. It needs to study the changing environmental
conditions and update and modify the model on a regular basis.
10. Operations economy: Whenever we have conflicts, uncertainty and complexity in any situation, OR
can help in the end to reduce costs and improve profits and effect substantial “operations economy”.

SCOPE OF OPERATIONS RESEARCH/ AREAS WHERE OPERATIONS RESEARCH COULD BE APPLIED:

In recent years of organized development, OR has entered successfully in many different areas of research. It
is useful in the following various important fields

1. In agriculture
• With the sudden increase of population and resulting shortage of food, every country is facing the
problem of
• Optimum allocation of land to a variety of crops as per the climatic conditions.
• Optimum distribution of water from numerous resources like canal for irrigation purposes.

Hence there is a requirement of determining best policies under the given restrictions. Therefore a good
quantity of work can be done in this direction.

2. In finance, Budgeting and Investment:

• In these recent times of economic crisis, it has become very essential for every government to do a
careful planning for the economic progress of the country. OR techniques can be productively applied
• To determine the profit plan for the company
Compiled by Dr. Suganthi Pais Page
2
 St. Joseph’s College of Commerce (Autonomous), Bangalore

• To maximize the per capita income with least amount of resources

• Cash flow analysis, long-range capital requirements, investment portfolios, dividend policies, etc.
• Purchasing, Procurement and Exploration:
• Determine the quantity and timing of purchase of raw materials, machinery, etc.
• Rules for buying and supplies under varying prices.
• Equipment replacement policies.
• Bidding policies, etc.

3. In production management:
• A production manager can utilize OR techniques
• To calculate the number and size of the items to be produced
• In scheduling and sequencing the production machines
• In computing the optimum product mix
• To choose, locate and design the sites for the production plans

4. In marketing:
• With the assistance of OR techniques a marketing administrator can decide upon
• Where to allocate the products for sale so that the total cost of transportation is set to be minimum
• The minimum per unit sale price
• The size of the stock to come across with the future demand
• How to choose the best advertising media with respect to cost, time etc?
• How, when and what to buy at the minimum likely cost?

5. In personnel management:
• A personnel manager can utilize OR techniques
• To appoint the highly suitable person on minimum salary
• To know the best age of retirement for the employees
• To find out the number of persons appointed in full time basis when the workload is seasonal
• Establishing equitable bonus systems.

6. In industry:

If the industry manager makes his policies simply on the basis of his past experience and a day approaches
when he gets retirement, then a serious loss is ahead of the industry. This heavy loss can be right away
compensated through appointing a young specialist of OR techniques in business management. Thus OR is
helpful for the industry director in deciding optimum distribution of several limited resources like men,
machines, material, etc to reach at the optimum decision.

7. In L.I.C:
• OR approach is also applicable to facilitate the L.I.C offices to decide

Compiled by Dr. Suganthi Pais Page

3
 St. Joseph’s College of Commerce (Autonomous), Bangalore

• What should be the premium rates for a range of policies?

• How well the profits could be allocated in the cases of with profit policies?
• Research and Development:
• Determining the areas of concentration of research and development.
• Reliability and evaluation of alternative designs.
• Control of development projects.
• Co-ordination of multiple research projects.
• Determination of time and cost requirements.

TECHNIQUES OR TOOLS OF OPERATIONS RESEARCH

1) Linear Programming: This technique is used to find a solution for optimizing a given objective. The
Objective may be maximizing profits or minimizing costs. It is also used to allocate scarce resources in
an optimum manner in problems of scheduling, product mix, etc.
2) Queuing Theory: This theory deals with the situations in which queue is formed. This theory aims at
minimizing the overall cost due to servicing and waiting.
3) Inventory Control Models: When to buy? How much to buy? How much to keep in stores? Etc., are
some of the questions purchase managers address themselves to. Inventory control aims at
optimizing inventory levels.
4) Net Work Analysis: This Model helps the managers to plan, schedule, monitor and control large
projects, such as construction of a building, making a ship or planning for a space flight. This model
helps the managers to determine the total project completion time, probability that a project will be
completed by a certain date, least cost way of shortening total project completion time, etc.
5) Replacement Problems: This theory is concerned with situations that arise when some items such as
machines, men or any other equipment require replacement due to their decreasing efficiency,
failure or break down. This theory helps to solve all replacement problems.
6) Sequencing: This model helps to sequence the processing of jobs so that the total elapsed time for all
the jobs will be the minimum. This model also helps to resolve the conflict between the objectives of
maximizing machine utilization and complying with predetermined delivery dates.
7) Integer Programming: This has been developed to overcome the drawbacks of Linear Programming.
Sometimes, when solutions given by LL are rounded off, they may lead to poor choice of solution.
Hence, Integer Programming has been developed to get the best solution of the given problem.
8) Assignment Problems: It deals with allocating the various resources or times to various activities on a
one to one basis in such a way that the time or cost involved is minimized or sale or profit is
maximized.
9) Transportation Problems: The main object of transportation problem is to schedule shipments from
sources to destinations in such a way as to minimize the total transportation cost.
10) Markov Analysis: This analysis helps to predict changes over time when information about the
behavior of a system is known. It is based on probability theory.
11) Decision Theory and Games Theory: Decision theory is concerned with decision making under the
conditions of risk and uncertainty. Games theory is concerned with decision making under conflict.
Compiled by Dr. Suganthi Pais Page
4
 St. Joseph’s College of Commerce (Autonomous), Bangalore
12) Simulation: All real life problems cannot be stated in mathematical form because of their
relationships, complexity, etc. Such problems can be tackled by simulation. Simulation allows solving
problems that are difficult or impossible to solve otherwise.
13) Dynamic Programming: When we are faced with the problem of multi faced solution which is inter-
related and almost similar in nature, then Dynamic Programming is applied. All possible results are
analyzed and the best solution is selected. Dynamic Programming problems involve manipulation of
large amount of information and require electronic computers.
14) Goal Programming: In goal programming, several objective functions are considered. Each objective
function has a fixed value known as ‘target’ and the Goal Programming models are developed to
minimize deviations from these ‘targets’. Applications include production scheduling, transportation
problems, portfolio analysis, etc.
15) Symbolic Logic: In this, the whole problem is converted into algebraic equations and propositions and
calculations are done on computers.

LIMITATIONS OF OPERATIONS RESEARCH

1. Magnitude of computation: OR tries to find out optimal solution taking into account all the factors.
This leads to complicated calculations which cannot be handled manually, but require electronic
computers which bear heavy cost.
2. Non-quantifiable factors: OR provides solution only when all the elements related to a problem can
be quantified. But there are some elements or factors which cannot be quantified such as human
relations. These qualitative or emotional factors though relevant for the solutions are kept out of OR
models.
3. Gap between Manager and Operations Researchers: OR being specialists’ job requires mathematician
or statistician who might not be aware of the business problems. Similarly, a manager fails to
understand the complex working in OR.
4. Money and Time Costs: When the basic data are subjected to frequent changes, incorporating them
into the OR models is a costly and time consuming affair.
5. Implementation: Implementation is a delicate task. There may be resistance from employees.
6. Selection of Technique: There are many techniques in OR. Choice of technique depends upon the
nature of problem, operating conditions, assumptions, objectives, etc. Thus identification and use of
an appropriate technique is difficult task.
7. Not a substitute to Management: OR does not provide decisions. It only provides quantitative data
to management for decision making. The final decision has to be taken by management within its
authority and judgment.

METHODOLOGY/ APPROACHES OF OR

Orientation: The first step in OR is to have a clear understanding of the problem and its relationship to
different operational aspects of the system, so that problem can be properly defined.

Compiled by Dr. Suganthi Pais Page

5
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Problem Definition: This is the second step in OR. It is the most important and difficult step. The objective
here is to have a clear definition of the problem in terms of its scope and the results desired.

• A clear definition has the following components:

• Statement of an unambiguous objective.
• Specification of factors that will affect the objective.
• Specification of the constraints on the causes of action.
• Proper definition will help in date correlation in the right direction.

Data Collection: Data typically comes from two sources – observation and standard i.e., primary and
secondary sources. This step involves extracting useful information from these sources.

Model Formulation: This is the fourth step in OR process. Modeling is the process of defining characteristics
of all operations. A model may be defined formally as a selective abstraction of reality which helps in the
working of original system. Models may be classified as:

• Physical Models
• Analogic Models
• Mathematical Models
• Computer Simulations Models

Solution Results: This step involves finding the solution to the model and then interpreting the solution. The
solution can be classified as:

• Feasible solution
• Infeasible solution
• Optimal solution
• Non-optimal solution
• Unique solution
• Multiple solution

Analysis and interpretation of results: This stage determines whether the model can adequately and reliably
predict the behavior of the real system. It involves testing the structural assumptions of the model. This step
gives an assurance that the future performance of the system will continue to be in the same manner as in
the past.

Implementation and Monitoring: This is certainly the most important phase because it is only after a
proposal has been implemented that the benefit accrues. When a feasible solution has been decided upon, it
has to be put into practice. Finally, it is important to ensure that any solution implemented is continuously
reviewed and updated and modified in the light of a changing environment.

MODELS IN OPERATIONS RESEARCH:

Compiled by Dr. Suganthi Pais Page

6
 St. Joseph’s College of Commerce (Autonomous), Bangalore
A Model is defined as an idealized representation or an abstraction of some real-life system, whether such
system refers to a problem, process, operation, system, object or event. The essence of operations research
lies in the construction and use of models. A model is constructed to analyse and understand the given
system for the purpose of improving its performance.

Classifications of Models:

1. On the basis of functions:

Descriptive Models: These are models which simply describe some aspects of a situation based on
observations, survey, questionnaire results, etc. They do not predict or recommend anything. Eg. Plant
layout diagrams, Flow Charts, Organisation charts, etc.

Predictive Models: These are models which indicate “if something happens what will follow”. They indicate
the relationship between dependent and independent variables and permit trying out “what if” questions.
They models can predict the outcomes due to a given set of alternatives for the problem.

Normative or Optimisation Models: These are models which provide the ‘best’ or ‘optimal’ solution to
problems subject to certain limitations on the use of resources. Eg. Mathematical model formulating an
objective function subject to certain restrictions or constraints on resources.

2. On the basis of Structure:

Physical Models: These are models which provide a physical representation of the real object under study in
a reduced size (Scaled Model). Eg. Scale models of proposed aircraft under design/prototype construction.

Physical Models can be:

Iconic Models: Icon is the depiction of an object as its image. It is a scaled version of the system it
represents. It represents the system as it is by scaling it up or down. Eg. Blue prints of buildings, houses,
photographs, drawings, etc.

Analog Models: They represent a system like an iconic model but not as the exact replica of the actual
system. They represent a system by a set of properties different from those of the original system and do not
resemble it physically. Eg. Maps, Organisation charts, graphs, frequency curves, etc.

Symbolic Models: These are models which use symbols (letters, numbers) to represent actual problems.
There are two types of symbolic Models. They are:

Verbal Models: These models describe a situation in written or spoken words or sentences. Eg. Books,
reports, etc.

Mathematical Models: These Models use mathematical operators ( +, - , x, etc) to represent relationships
among different variables of the system in order to describe the properties or behavior of the system. Eg.
EOQ Model, Cost-volume Model etc.

Compiled by Dr. Suganthi Pais Page

7
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Models based on Time Reference:

Static Models: They represent a system at some specified time and do not account for change over time. Eg.
EOQ Model.

Dynamic Models: These models consider time as one of the variables and allow the impact of changes due to
change in time. Eg. Dynamic Programming.

Models based on Degree of Certainty:

Deterministic Models: In deterministic Models, parameters are completely defined and the outcomes related
to particular courses of action are certain. Eg. Linear Programming and Break even Models.

Probabilistic Models / Stochastic Models: In these models at least one parameter is a random variable, hence
consequences or payoffs due to certain changes in the independent variable cannot be predicted with
certainty, but is able to predict a pattern of values of both variables by their probability of distribution. Eg.
Models representing insurance against risk of fire, accidents, sickness of employees, etc.

Models based on Quantification:

1. Qualitative Models: They are descriptive models. Verbal description is used to represent the
situation.
2. Quantitative Models:
• Heuristic Models: These models employ some set of rules which, though not optimal, do facilitate
problem solving when applied consistently.
• Simulation Models: These are those models which have mathematical structure but are not solved
using mathematical techniques. They use computers to solve simulation Models.

**********************

LINEAR PROGRAMMING

Linear programming is a mathematical technique. This technique is applied for choosing the best
alternative from a set of feasible alternatives. In LPP objective functions as well as restrictions or
constraints can be expressed as linear mathematical functions. This technique is designed to help
managers in planning, decision making and to allocate the resources.

Definition: According to George B. Dantzig, “Linear Programming is a programming of interdependent

activities in a linear structure”.

Basic Concepts:

1. Linearity: It implies a straight line or proportional relationship among relevant variables.

Compiled by Dr. Suganthi Pais Page

8
 St. Joseph’s College of Commerce (Autonomous), Bangalore
2. Process and its level: Process means combination of inputs to produce a particular output.
3. Criterion function/Objective function: It states the determinants of the quantity either to be
maximized or to be minimized.
4. Objective function:

Maximum / Minimum Z = C1X1 + C2X2 +…………….+ CnXn

Where C is the Contribution per unit and X is the decision variables.

Sale/Profit is to be maximized and Cost/Time is to be minimized.

5. Decision Variables: They refer to the economic or physical quantities which are competing with
one another for sharing the given limited resources. They are usually written as x1,x1,x2,………,
xn.
6. Constraints or Inequalities: These are limitations on resources which are to be allocated among
various competing activities. (>, < or =)
7. Non-negativity: The value of decision variable can either be zero or greater than zero.

Advantages of LPP:

• It is used to solve allocation of scarce resources to attain a particular objective.

• It gives possible and practicable solutions.
• It improves the quality of decisions.
• It helps in attaining the optimum use of scarce resources.

Limitations of LPP:

• Assumptions of linearity not possible in all situations.

• It does not take into account time and uncertainties.
• Parameters of the model are assumed to be constant but in real-life situations they are often
neither known nor constant.
• It deals only with a single objective.

Application of Linear Programming Methods:

• Product Mix – deciding how much quantity of each product to be used to maximize or minimize
cost.
• The Diet Problem – determining the optimal combination of diet of feed mix, which will satisfy
specified nutritional requirements and minimize the total cost of purchasing the diet.
• The Portfolio Selection Problem – arises when a given amount of money is to be allocated among
several investment opportunities.
Compiled by Dr. Suganthi Pais Page
9
 St. Joseph’s College of Commerce (Autonomous), Bangalore

• Media Selection – selecting the media to maximize the audience exposure,

• Blending Problem – choosing raw materials from a number of available raw materials of various
composition and prices to make a particular product.
• Transportation Problem – to arrange for transportation of products from n sources to m
destinations to minimize cost of transportation.
• Travelling Salesman’s Problem – finding the shortest route for a salesman starting from a given
city, visiting each of the specified cities, and then returning to the original point of departure.
• Miscellaneous Problems like Farm planning, airline routine, etc.

Graphical Method of solving LPP:

Important terms:

Solution: It is a set of decision variables x1, x2,……, xn which satisfies the constraints of LPP.

Feasible Solution: It is a set of values of decision variables which satisfies all the constraints and non-
negativity of a LPP.

Non-feasible Solution/Infeasible Solution/ Infeasible Problem: In some cases, linear programming

problem has no feasible solution. It means there are no points that simultaneously satisfy all constraints
in the problem. Common region do not develop in the first quadrant.

Basic Solution: When we need to solve a system of ‘m’ equations in ‘n’ variables, where m<n, then we
need to set (n-m) variables as zero and solve for the rest of the variables. The solution obtained for the
rest of the variables is called the Basic Solution. The variables that we set to zero are called Non-basic
Variables and the other remaining variables are called Basic Variables.

For eg.

In the equation 2x + 4y = 8,

If we set x = 0, then y = 2

Here x is a Non-basic Variable and y is a Basic Variable. Y = 2 is the Basic Solution.

If we set y = 0, then x = 4

Here y is a Non-basic Variable and x is a Basic Variable. X = 4 is the Basic Solution.

Unbounded Problem: In some of the problems, feasible solution space formed by the constraints is not
confined to the first quadrant only. Constraint passes through 2nd, 3rd or 4th quadrant. In such case, the
objective function can sometimes increase indefinitely without ever reaching its maximum limit, since it
never reaches a constraint boundary. Such problems are called unbounded problems.

Compiled by Dr. Suganthi Pais Page

10
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Redundancy: A redundant constraint is simply one that does not affect the feasible solution region. In
other words, one constraint may be more binding or restrictive than another and thereby negate its
need to be considered. For e.g.

Max. Z = 3x1 + 6x2

Subject to:

X1 + x2 <=20

2x1 +x2 <= 30

X1 <= 35

Where x1, x2 >= 0

The third constraint is redundant and unnecessary.

Steps in Graphical Method:

1. Formulate the LPP.

2. Write each inequality as equality.
3. Plot each constraint line taking them as equation.
4. Identify the feasible solution region.
5. Locate the corner points of the feasible region.
6. Calculate the value of objective function on corner points. (Extreme point enumeration)
7. Choose the point where objective function has optimum solution. (Maximization
problem – highest value, Minimization – lowest value)

********************

Problems:

1. A firm is engaged in producing two products P1 and P2. Each unit of product P1 requires 2 Kg of raw
material and 4 labour hours for processing, where as each unit of product P2 requires 5 Kg of raw material
and 3 labour hours of the same type. Every week the firm has the availability of 50 Kg of raw material and
60 labour hours. One unit of product P1 sold earn profit of Rs. 20 and one unit of product P2 sold gives Rs.
30 as profit.

Formulate this problem as linear programming problem to determine as to how many units of each of the
products should be produced per week so that the firm can earn maximum profit, assume all units
produced can be sold in the market.

Compiled by Dr. Suganthi Pais Page

11
 St. Joseph’s College of Commerce (Autonomous), Bangalore
2. XYZ Advertising Agency has been asked to help a client to develop an advertising budget for the
introduction of an improved product. Advertising funds are to be spent on both television and magazine
announcements. The client has specified the following requirements:
a) No more than Rs. 2,00,000 is to be spent on television advertisement.
b) At least Rs. 1,00,000 must be spent on magazine announcements.
c) Advertisement costs Rs. 5,000 in TV and Rs. 2,000 in Magazine respectively. Total expenditure should not
exceed Rs. 5,00,000.
From prior marketing research studies, the agency has determined that 300 people are exposed to
message for each rupee spent on television and 200 people are exposed to a message for each rupee
spent on magazine. Determine the amounts to be spent on television and magazine advertisement to
maximize the total number of people exposed to the new product announcement. You are required to
formulate the LPP Model.

3. The manager of an oil refinery must decide on the optimal mix of 2 possible blending processes of which
the inputs and outputs per production run are as follows:

Process Input Output

Crude A Crude B Gasoline X Gasoline Y

1 6 3 6 9

2 5 6 5 5

The maximum availability of crude A and B are 250 units and 200 units respectively. The market
requirement shows that at least 150 units of gasoline X and 130 units of gasoline Y must be produced. The
profits per production run from process 1 and 2 are Rs. 40 and Rs. 50 respectively. Formulate the problem
for maximizing the profit.

4. Vitamins A and B are found in two different foods F1 and F2. One unit of food F1 contains 2 units of
vitamin A and 5 units of vitamin B. One unit of food F2 contains 4 units of vitamin A and 2 units of vitamin
B. One unit of food F1 and F2 cost Rs. 10 and Rs. 12.50 respectively. The minimum daily requirements
(for a person) of vitamin A and B are 40 and 50 units respectively. Assuming that anything in excess of
daily minimum requirement of vitamin A and B is not harmful, find out the optimal minimum of food F1
and F2 at the minimum cost which meets the daily minimum requirements of vitamin A and B. Formulate
this as a linear programming problem.
5. Solve the following by Graphical Method:
a) Max. Z = 2 X1 + 5 X2

Subject to:

X1 <= 4

X2 <= 3

X1 + X2 <= 8
Compiled by Dr. Suganthi Pais Page
12
 St. Joseph’s College of Commerce (Autonomous), Bangalore
X1; X2 >= 0

b) Min. Z = 40 X1 + 24 X2 Total Cost

Subject to:

20 X1 + 50 X2 >= 4,800 Material I Requirement

80 X1 + 50 X2 >= 7,200 Material II Requirement

X1, X2 >= 0 Non-negative condition.

c) Max. Z = 6 X1 + 4 X2

Subject to:

2 X1 + 4 X2 <= 4

4 X1 + 8 X2 >= 16

X1, X2 >= 0

d) Min. Z = -X1+2X2

Subject to:

-X1 + 3 X2 <= 10

X1 + X2 <= 6

X1 – X2 <= 2

X1 and X2 >= 0

e) Max. Z = 5 X1 + 2 X2

Subject to:

2 X1 + 3 X2 <= 150

3 X1 <= 150

5 X2 <= 200

X1; X2 >= 0

f) Min. Z = 4 X1 + 3 X2

Subject to:

200 X1 + 100 X2 >= 4,000

Compiled by Dr. Suganthi Pais Page

13
 St. Joseph’s College of Commerce (Autonomous), Bangalore
X1 + 2 X2 >= 50

40 X1 + 40 X2 >= 1,400

X1 and X2 >= 0

LINEAR PROGRAMMING PROBLEMS – SOLVING BY SIMPLEX METHOD

A Linear Programming Problems (LPP) is a mathematical model dealing with the use or allocation of certain scarce
resources (i.e., key factor like raw materials, labour hours, machine time, capital available, etc.) in the best
possible manner in order to maximize profit or minimizecost.

Conditions:

LPP consists of a particular class of programming problems, which meet the following conditions:

Objective: There must be a defined objective, i.e., maximization of profit/revenue/income or minimization of

cost/time.

Variables: There must be defined variables. These must be non-negative.

Constraints: There must be limitations/restrictions relating to the use of certain resources. These constraints are
denoted by inequations having ‘<=’ or ‘>=’ sign. In some cases, the conditions can be stated using ‘=’ sign also.

Various methods of solving LPP

Method Conditions for applicability

GraphicalMethod Number of variables should be two (since there are only two axes x and y on the
graph sheet). Any number of constrainst/inequalities are permitted,

but the feasible region may not be easily identified if numerous constraints are
introduced.

Trial and Error Number of variables = No. of constraints. For example, two equations in two
Method or Algebraic variables can be solved. However, as more variables and constraints are introduced,
Approach solving algebraic equations may become comparatively difficult.

Simplex Method No restrictions as to number of variables and constraints.

Slack Variables:

A variable added to the LHS of every ‘<=’ inequality is called a Slack Variable. The purpose of introducing the slack
variable is to convert the inequality constraint into an equality.

Slack Variable is an idle or unused resource represented by a constraint.

Compiled by Dr. Suganthi Pais Page

14
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Since it represents an unused resource, a slack variable has to be positive (i.e. non- negative).

Contribution or Profit per unit of slack variable is zero, since profits are not made on unused resources. Hence the
co-efficient of a slack variable in the objective function is always zero.

The co-efficient of a slack variable in the constraint will be 1. It is taken as the basic variable in the Initial Simplex
Table.

Surplus Variables:

A variable subtracted from the LHS of every ‘>=’ inequality is called as a Surplus Variable. The purpose of
introducing the Surplus Variable is to convert the inequality constrain into an equality.

Surplus variable is the excess amount of resources utilized over and above the given level.

Since it represents a resource (excess utilized), a surplus variable has to be positive (i.e., non-negative).

Contribution or profit per unit of a surplus variable is zero, since profits are not made on excess utilization of
resources. Hence the co-efficient of a surplus variable in the Objective Function is always ‘zero’.

The co-efficient of a surplus variable in the constraint will be ‘negative one’ (-1). It cannot be taken as the basic
variable in the Initial Simplex Table, since it does notform a unit matrix.

Artificial Variables:

The Surplus Variable in every ‘>=’ constraint cannot provide an Initial Feasible Solution since the co-efficient do
not form a unit matrix. To form a unit matrix and have an initial basic solution, an Artificial Variable is deliberately
added to every ‘>=’ and ‘=’ constraint of an LPP.

An Artificial Variable is a fictitious variable, and cannot have any physical or economic meaning. It is intentionally
introduced to form a initial solution for further iteractions.

Since none of the Basic Variables in the LPP can have a negative value, an Artificial Variable provides the Initial
Basic Solution and avoids the possibility of getting negative values for basic variables.

The co-efficient of the artificial variable in the Objective Function will be:

a) +M in case of Minimization Objective, where M represents a huge penalty/cost which should be avoided,
and

b) -M in the case of Maximization Objective, where such cost should be avoided inorder to maximize profit.

An Artificial Variable once eliminated during the replacement decision, will not re-entersubsequent interactions.

If the Optimal Table contains the Artificial Variable also, it is a LPP with no feasiblesolution.

Compiled by Dr. Suganthi Pais Page

15
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Distinguish between Slack, Surplus and Artificial Variables in LPP

Particulars Slack Variables Surplus Variables Artificial Variables

1. Meaning Idle or unusedresources Excess amount of No physical or economic

resources utilized. meaning. Itis fictitious.

2. When used? ‘<=’ inequality ‘>=’ inequality ‘>=’ or ‘=’ constraints.

3. Co-efficient in +1 -1 +1

the constraint.

4. Co-efficient in the 0 0 +M for minimization and -

Objective Function M for mazimisation.

5. Use as Initial Used as starting point Cannot be used since Initially used but later
(Initial Simplex Table) eliminated.
Programvariable unit matrix conditionis not
satisfied.

6. Presence in Helps to interpret idle - Indicates ‘No feasible

Optimal Table and key resources. solution’.

Interpretation of the existence of Slack Variables in the Optimal Table of a maximization LPP

Nature of Nature of Nature of Interpretation/Remarks

slack NER Resource

Non- program NER < Key resource This means that for every reduction in the RHS of that
variable 0 constraint, the profit will be reduced by the NER. Thus,
the value of NER represents the contribution loss per unit
(i.e., of RHS of that constraint/key resource.
negative)
Note: This contribution loss is also called the

shadow price or Marginal value of that resource.

ProgramVariable NER = 0 Idle resource This means that the resource has no contribution loss,
and is hence not fully utilized. The extent of slackness /
idleness / unused resources is equal to the ‘quality
column’ of the concerned program

slack variable.

Compiled by Dr. Suganthi Pais Page

16
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Duality

Every LPP, whether of maximization or minimization is associated with another mirror image problem based on
the same data. The original problem is called the primal problem and the other is called the dual problem.

For example, in the problem of producing 2 products where each consume 2 types of resources,the primal pattern
could be to determine what quantity of each product will maximize the overall profit subject to the constraints on
resource availability.

The Dual Problem would then be to determine cost of quantity of the 2 types of resources being consumed so as
to obtain an overall minimum cost.

It is the interesting feature of the simplex method that we can use it to solve either the original problem called the
primal or the Dual. Whichever problem we start to solve, it will also give thesolution to the other problem. It is to
be noted that sometimes it is computationally easier to solve the dual than the primal.

Procedure for conversion from Primal to Dual

Step Procedure

1 Write the Primal LPP with its constraints. Ensure that all constraints are in tune with the

objective. For example, if Objective = Maximization, all constraints should have ‘<=’ sign.

Note: If all constraints are not in tune with the objective, multiply that constraint by -1 and
change in inequality sign.

2 Write the Primal in a matrix form with co-efficients of the variables and RHS of the

constraints. Also state the co-efficients of the variables in the Objective Function.

3 Transpose the matrix stated in step 2 above (i.e., convert rows into columns and vice-versa)

4 Write the revised LPP from the transposed matrix. The objective of the revised LPP will

be the reverse of the primal. The revised LPP is called the Dual.

Steps in solving LPP using the Simplex method

● Step 1: Verify whether at least 1 constraint is in line with the objective function. That is if the
objective is more. Then at least 1 constraint should be less than equal to and if the object is min.
Then at least one constraint should be greater or equal.
● Step 2: introduce appropriate variables to convert inequalities to equalities and redraft the
objective function.
● Step 3: Preparation of the initial & simplex data table.

Compiled by Dr. Suganthi Pais Page

17
 St. Joseph’s College of Commerce (Autonomous), Bangalore
⇒ Notes to prepare IST

1. Fill up the program variable that is, slack variables.

2. Fill up the profit column that is, the coefficient of program variables from the objective function.
3. Fill up variable columns that are on the right side of the values of the constraints.
4. Fill up variable columns, that is the coefficient of each variable from the respective constraint.
5. Check whether the coefficient relating program variable consists of a unit matrix, but need not be
adjacent - each other.
6. Write Z row, that is the coefficient of each variable from the objective function.
7. Write C row, that is the total profit into the coefficient of each variable.
8. Compute NER (net evaluation row) (z-c)
⇒ Note: for program variables, NER should always be equal to 0.

9. Select the maximum positive NER for the max objective. And if the minimum objective takes the
minimal / lowest value. This is called the key column.
10. Compute replacement ratio, that is Quantity / key column element.
11. Select the minimum non-negative replacement ratio, and this is called the key row.
⇒ Note: If replacement ratio = 0, it shall be selected as the key row. Because of a tie between the
replacement ratio, arbitrary selection shall be made.

12. Identify pivot element (P. E). It is the junction of the Key row and key column.
13. Compute fixed ratio, that is key column element / PE.
⇒ Note: Fixed ratio is not applicable for key rows.

14. Replacement decision in = key column variable, out = key row variable.

● Step 4: Compute/prepare 2nd, 3rd and so on simplex tables.

1. Fill up the program variable (variable as per the previous replacement decision and maintain the
same order in the table.
2. Fill up the profit column, that uses the coefficient of the program variable from the objective
function.
3. Fill up the previous table’s key row with the transform action rule.
⇒ Transformation rule = previous table key row element / PE

4. Fill up the non-key row by the transformation rule.

⇒ Transformation rule = previous table corresponding row element - (key row * fixed ratio)

5. Make sure that coefficients relating to program variables constitute a unit matrix, but need not be
adjacent to each other.
6. Z row remains the same as per the previous table.
7. Compute C row.
Same as step 3 (i.e. from 8th to 13 points).

Compiled by Dr. Suganthi Pais Page

18
 St. Joseph’s College of Commerce (Autonomous), Bangalore
PROBLEMS

1. You are required to introduce appropriate variables and restate the problem to set the simplex table for
the following:

a) Max. Z = 8x1 + 4x2 – 3x3 + 10x4

Subject to:

2x1 – x2 + x3 + 2x4 >= 40

3x1 – x3 + x4 <= 90

2x1 + x2 + x4 = 60

Where x1 , x2 , x3 and x4 >=0

b) Min. Z = 16 x1 + 16 x2

Subject to:

2 x1 + 4 x2 >= 3

3 x1 + 2 x2 >= 4

5 x1 + 3 x2 = 10

10 x1 – x2 <= 5

Where x1 and x2 >=0

2. Solve by Simplex Method the models given below:

a) Max. Z = 22 x1 + 18 x2

Subject to:

x1 + x2 <= 20

360 x1 + 240 x2 <= 5760

Where x1 and x2 >=0

b) Min. Z = 60 x1 + 80 x2

Subject to:

x2 >= 200

x1 <= 400

Compiled by Dr. Suganthi Pais Page

19
 St. Joseph’s College of Commerce (Autonomous), Bangalore
x1 + x2 = 500

Where x1 and x2 >=0

c) Max. Z = 25 x1 + 20 x2

Subject to:

16 x1 + 12 x2 <= 100

8 x1 + 16 x2 <= 80

Where x1 and x2 >=0

3. Obtain the Dual of the following:

Type 1 – All constraints are ‘<=’ type

Max. Z = 5 x1 + 3 x2Subject to:

x1 + x2 <= 2

5 x1 + 2 x2 <= 10

3 x1 + 8 x2 <= 12

Where x1 and x2 >=0

Types 2 – One or more constraints is/are ‘>=’ type

Max. Z = 3 x1 + 4 x2Subject to:

2 x1 + 3 x2 <= 16

5 x1 + 2 x2 >= 20

Where x1 and x2 >=0

Type 3 – All constraints have ‘>=’ sign

Max. Z = 3 x1 + 4 x2Subject to:

x1 + x2 >= 4

-x1 + 3 x2 >= -4

Where x1 and x2 >=0

Type 4 – One or more constraints with ‘=’ sign

Max. Z = 5 x1 + 10 x2Subject to:

Compiled by Dr. Suganthi Pais Page

20
 St. Joseph’s College of Commerce (Autonomous), Bangalore
2 x1 - 3 x2 <= 7

x1 + 2 x2 = 4

Where x1 and x2 >=0

Type 5 – When some variables are unrestricted in singh)

Max. Z = 3 x1 + 5 x2 + 7 x3

Subject to:

x1 + x2 + 3 x3 <= 10

4 x1 - x2 + 2 x3 >= 15

7 x1 – 2 x2 – x3 <= 10

Where x1 and x2 >=0 and x3 is unrestricted variable

*************************

Compiled by Dr. Suganthi Pais Page

21
 St. Joseph’s College of Commerce (Autonomous), Bangalore
TRANSPORTATION

Transportation applications relate to a LPP where goods are to be transported from ‘m’
production locations (factories) to ‘n’ sales locations (warehouses).

The objectives are:

a) To meet the differing availabilities and requirements of these locations and

b) To minimize the total transportation costs.

The transportation application can be solved in three stages:

a) Preliminary check
b) Initial Basic Feasible Solution (IBFS) and
c) Optimality Test

Stage 1: Preliminary Check: This involves the following:

a) Verify the Objective = Minimization.

If objective is not Maximization, then the matrix should be converted into Opportunity
Matrix by subtracting each number from the highest number in the matrix.
b) Verify the nature of data = Balanced data.
The data is said to be balanced if total availability = total requirement.
In case of unbalanced data, a dummy column or row should be introduced with zero
transportation costs.

Stage 2: IBFS can be determined using any of the following methods:

a) Northwest Corner Rule

b) Least Cost Cell Method and
c) Vogel’s Approximation Method (VAM)

Stage 3: Optimality Test: It consists of the following steps:-

a) Computation of margin numbers, ‘U’ and ‘V’ for all rows and columns such that U + V =
Cost allocated cells.
b) Computations of U + V for unallocated cells.
c) Computation of Cost minus (U+V) for unallocated cells, i.e., step 1 minus step 2 above.

Compiled by Dr. Suganthi Pais Page

22
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Northwest Corner Rule:

The Northwest Corner Rule Method is a method for computing a basic feasible solution of a
transportation problem, where the basic variables are selected from the north-west corner (i.e.,
top left corner) of the transportation tableau.

Procedure:

Step Description
1 Ensure availability = requirement, by inserting dummy row or column, if required.
2 • Go to top left hand corner cell of the matrix
• Compare availability and requirement, and allocate whichever is less, to that cell.
• Cancel the row or column where availability or requirement (i.e., quantity)
condition is satisfied.
3 • Go to top left corner cell of the resultant matrix (after cancellation of row or
column in step 2)
• Repeat step 2 procedure till all the row availability and column requirements are
satisfied.
Areas of application: Northwest Corner Rule may be used in Transportation Applications: -

• Within the compus of an organization as cost differences are not significant.

• Obligations where cost is not the criteria for decision-making.

Advantages of Northwest Corner Rule:

a) Very simple and reliable method.

b) Easy to compute, understand and interpret.
c) It does not require any calculation of opportunity costs or penalties.
d) It can be used as a starting point for other methods that improve the solution.

Dis-advantages of Northwest Corner Rule:

a) Ignores the relative cost of different routes while making the first assignment.
b) It does not guarantee an optimal solution.

Least Cost Cell Method or Matrix Minimum Method:

The Least Cost Cell Method is another method used to obtain the initial feasible solution for a
transportation problem, where the basic variables are selected from the cell which has the
minimum cost in the transportation tableau.

Compiled by Dr. Suganthi Pais Page

23
 St. Joseph’s College of Commerce (Autonomous), Bangalore
Procedure:

Step Description
1 Ensure availability = requirement, by inserting dummy row or column, if required.
2 • Identify the cell with the lowest cost. In case of a tie, arbitrary selection may be
made.
• Compare availability and requirement, and allocate whichever is less, to that cell.
• Cancel the row or column where availability or requirement condition is satisfied.
3 • Identify the next lowest cost cell in the matrix.
• Repeat step 2 procedure till all the row availability and column requirements are
satisfied.

Advantages of Least Cost Cell Method:

a) It is simple and easy to apply.

b) It tends to give a better initial solution than the Northwest Corner Rule Method.
c) It can reduce the number of iterations required to reach the optimal solution.

Dis-advantages of Least Cost Cell Method:

a) It does not guarantee an optimal solution.

b) It may leave some cells unallocated or degenerate.

Vogel’s Approximation Method (VAM):

The Vogel's Approximation Method or VAM is an iterative procedure used to find out the initial
feasible solution of the transportation problem, where the basic variables are selected based
on the difference between the two lowest costs in each row and column.

Procedure:

Step Description
1 • Compute cost differences for each row and column.
• Cost difference is the difference between the least cost and the next least cost in
that row or column.
• In case of tie in least cost, cost difference = 0
2 • Ascertain the maximum of cost differences, and select that row or column for
allocation.
3 • Choose the least cost cell in the selected row or column for allocation.
4 • Compare availability and requirement for that cell, and allocate whichever is less,
to that cell.
• Cancel the row or column where availability or requirement condition is satisfied.

Compiled by Dr. Suganthi Pais. Page 3

 St. Joseph’s College of Commerce (Autonomous), Bangalore

5 • Compute cost differences for the resultant matrix and repeat the above
procedure till all row availability and column requirements are satisfied.

Advantages of Vogel’s Approximation Method:

a) It is simple and easy to apply.

b) It tends to give a better initial solution than the Northwest Corner Rule Method and the
Least Cost Cell Method.
c) It can reduce the number of iterations required to reach the optimal solution.

Dis-advantages of Vogel’s Approximation Method:

a) It does not guarantee an optimal solution.

b) It may leave some cells unallocated or degenerate.

Optimality Test under Modi’s Method:

It involves the following steps:

1. Table 1 : U + V for allocated cells:

a) Select the row or column with maximum number of allocations.
b) For the row or column, U (or) V is requal to zero. (U for rows and V for columns).
c) The other set of numbers U (or) V are computed in such a way that U + V = cost of
allocated cells.

Note: U + V table can be completed only if the IBFS is non-degenerate. IBFS is said to be
degenerate if number of allocations < (no. of rows + no. of columns – 1), i.e., (m + n – 1).
In case of degeneracy, a dummy allocation denoted by ‘e’ (a number very close to zero,
i.e., ‘e’ = 0.000…….01) is made in the least cost independent unallocated cell.

2. Table 2 : U + V for unallocated cells:

a) Draw a matrix for the given rows and columns.
b) Block out the allocated cells.
c) Compute U + V (i.e, total of margin numbers) for all unallocated cells.

3. Table 3: Net Evaluation Table (NET) = Decision Table

a) Draw a matrix for the given rows and columns.
b) Block out the allocated cells.
c) Compute cost differences for all unallocated cells. Cost difference = Number in table
1 minus number in table 2.

Compiled by Dr. Suganthi Pais Page 4

 St. Joseph’s College of Commerce (Autonomous), Bangalore
Decision/ Interpretation:

NET Entries Nature of solution

If all numbers are positive (i.e. > 0) IBFS is optimal and unique.
If all numbers are non-negative (i.e. >= 0) and IBFS is optimal but not unique. As many
one or more of the cells contains zero. zeroes, that many alternate solution(s) exist.
Total no. of solutions = No. of zeroes + 1
If any one number is negative Solution is not optimal. Re-allocation should
be made to determine Alternative Basic
Feasible Solution (ABFS).
Note: ABFS is tested for optimality by adopting the same procedure.

Loop Diagram in transportation or determining the ABFS:

1) Identify the worst negative in table 3. If there is a tie, choose the least cost cell. (call this
as ‘origin’)
2) Draw a loop with the following principles:
i) Loop should commence from and end in the selected worst negative cell, i.e., the
origin.
ii) It should have only allocated cells as its other corners. (But the loop can cross
over allocated/unallocated cells).
iii) Only horizontal and vertical lines (not diagonal) can be used.
iv) Loop should result in an even-sided figure.
3) Put positive (+) sign and negative (-) sign to the corners of the loop alternatively, with
origin as +ve corner.
4) Re-allocation is done as under:
i) Identify the allocations to the negative corners of the loop (i.e., corners marked
with (-) sign).
ii) Select the minimum quantity out of the above allocations. Let this quantity be
called Selected Quantity.
iii) Add this Selected Quantity to (+) corners and subtract this Selected Quantity
from (-) corners. Other allocated and unallocated calls will remain unaffected.
5) This ABFS is tested for optimality using the procedure outlined in the earlier question.
In case negatives still arise in table 3 of ABFS, the re-allocation procedure should be
continued further.

How do you treat the following in Transportation Problem?

Total availability is not • It is called unbalanced transportation problem.

equal to total • Introduce a dummy row or column to balance availability
requirement. and requirement.

Compiled by Dr. Suganthi Pais. Page 5

 St. Joseph’s College of Commerce (Autonomous), Bangalore

• All entries (costs) of the dummy row or column should be

zeroes.
Maximization objective • Select the highest element of profit in the matrix.
• Subtract each element from the maximum element.
• Take the resultant Opportunity Cost Matrix with
Minimization Objective, for the IBFS allocation procedure.
Degeneracy • Optimality test can be done only if number of allocations
= (m + n – 1) i.e., no. of rows + no. of columns -1.
• If number of allocations < m + n – 1, all Us and Vs cannot
be computed. This situation is called Degeneracy.
• If IBFS is degenerate, introduce a dummy allocation (e), a
small number very close to zero, in the least cost
independent unallocated cell.
Existence of zeroes in • Zero in the NET (Table 3) indicates the availability of
the NET alternative solutions (provided all other numbers are
positive)
• The alternative optimal solutions can be determined by
drawing a loop commencing from such cell having zero as
Net Evaluation.
• Re-allocation will be based on the loop drawing
procedure.
Prohibited Routes • Sometimes some routes may not be available due to
reasons like bad road conditions, strike, etc.
• Such prohibited routes are identified with a high cost
represented by ‘M’, a very large cost close to infinity.
• Due to assignment of very large cost, such routes would
automatically be eliminated in the final solution.

Transshipment Model:

A transshipment model is a type of transportation model in which items are shipped from
different sources to different destinations. However, unlike a regular transportation model,
the items can also pass through some intermediate points before reaching their final
destinations. These intermediate points are called transshipment points and they can
reduce the total cost of shipment. The objective of the transshipment problem is to find the
optimal shipping pattern that minimizes the total cost while satisfying the supply and
demand constraints.

The following diagram represents transshipment model with sources and destinations
acting as transient nodes.

Compiled by Dr. Suganthi Pais. Page 6

 St. Joseph’s College of Commerce (Autonomous), Bangalore

Every source is a source as well as destination and every destination is a destination as well as a
source in Transshipment Model.

PROBLEMS

1. Obtain an IBFS to the transportation problem by using Northwest Corner Rule.

Factory Distribution Centre Availability
D1 D2 D3 D4
F1 8 12 44 28 13
F2 4 0 24 4 3
F3 20 32 60 36 30
Requirement 21 15 9 6

2. Obtain an IBFS for the following transportation problem by using Least Cost Cell
Method.
Origin Distribution Centre Availability
D1 D2 D3 D4 D5
S1 5 7 10 8 4 60
S2 7 9 6 3 5 20
S3 10 11 12 9 6 20
S4 4 6 10 7 13 50
Requirement 30 40 20 30 30

3. Use Vogel’s Approximation Method to obtain an IBFS for the transportation problem.
Origin Distribution Centre Availability
D E F G
A 11 13 17 14 250
B 16 18 14 10 300
C 21 24 13 10 400
Demand 200 225 275 250

Compiled by Dr. Suganthi Pais. Page 7

 St. Joseph’s College of Commerce (Autonomous), Bangalore

4. Obtain and IBFS to the transportation problem by Vogel’s Approximation Method.

Origin Distribution Centre Availability

D1 D2 D3 D4
O1 8 7 4 2 8
O2 2 3 1 9 12
O3 10 7 8 3 11
Demand 7 8 10 6

5. Obtain and IBFS to the transportation problem to maximize profit by:

a) NWCR
b) LCC Method
c) VAM

Origin Distribution Centre Availability

D1 D2 D3 D4
O1 40 25 22 33 100
O2 44 35 30 30 30
O3 33 38 28 30 70
Demand 90 20 60 40

6. A Company has 3 plants located at A, B and C. The production of these plants is

absorbed by 4 distribution centers located at X, Y, W and Z. The transportation costper
unit has been shown in shall cells in the following table.
Factories Distribution Centre Availability
X Y W Z
A 6 9 13 7 6000
B 6 10 11 5 6000
C 4 7 14 8 6000
Demand 4000 4000 4500 5000
Find the optimal solution of the transportation problem by applying VAM.

7. The information on the available supply to each warehouse requirement of each market
and the unit transportation cost from each warehouse to each market is givenbelow:
Warehouse Market Availability
M1 M2 M3 M4

Compiled by Dr. Suganthi Pais. Page 8

 St. Joseph’s College of Commerce (Autonomous), Bangalore
A 5 2 4 3 22
B 4 8 1 6 15
C 4 6 7 5 8
Demand 7 12 17 9
The shipping clerk has worked out the following schedule from his experience.
Units 12 1 9 15 7 1
From warehouse A A A B C C
To market M2 M3 M4 M3 M1 M3
You are required to:
a) Check and see if the clerk has the optimal schedule.
b) Find the optimal schedule and minimum total shipping cost.

Compiled by Dr. Suganthi Pais Page 3

 St. Joseph’s College of Commerce (Autonomous), Bangalore
ASSIGNMENT PROBLEMS

Assignment problems in LPP are a special type of linear programming problems where the objective is to
minimize the cost or time of completing a number of jobs by a number of persons. Assignment should
be on a one-to-one basis (i.e., two jobs cannot be assigned to the same person, and two persons cannot
be assigned the same job).

Features of Assignment Problems:

1. Objective: The objective is either to maximize Profit/ Revenue/Sales or to Minimize Cost/Time.
2. Nature of data: ‘m’ jobs/products are to be assigned to ‘n’ persons/facilities. It is not always
necessary that m=n. If they are equal, data is said to be balanced, otherwise, data is said to be
unbalanced.
3. Conditions: Assignment should be on a one-to-one basis (i.e., two jobs cannot be assigned to
the same person, and two persons cannot be assigned the same job).

Procedure for determining the Optimal Solution under Hungarian Algorithm Method
Step Description
1 Verify objective = Minimization.
In case objective = Maximization, convert the same into an Opportunity Loss Matrix, by
subtracting each number from the highest number in the matrix.
2 Verify nature of data = Balanced.
Data is said to be balance when number of rows is equal to the number of columns.
In case data is unbalanced, add a dummy row or column as required, with all elements being
zero.
3 Perform Row Operations. Subtract the smallest number in each row from all element of that
row.
4 Perform Column Operations. In the resultant matrix from step 3, subtract the smallest number
in each column from all the elements of that column.
5 Draw the minimum number of horizontal and vertical lines to cover all zeroes in the matrix.
Optimal Assignment is possible only if No. of lines drawn = Order of the matrix.
6 In case, number of lines < order of the matrix, increase the number of zeroes as under:
a) Select the smallest number not covered by the lines. (Call this as Least Open Element,
i.e., LOE)
b) Rewrite the matrix, with the following adjustments:-
i) Open Elements, i.e., not covered by any line: Previous Element minus LOE.
ii) Covered Elements, i.e., covered by one line only: No Change.
iii) Junction Elements, i.e., covered by intersection of two lines: Previous element
plus LOE.
Repeat step 5 for such revised matrix till number of lines drawn = Order of the matrix.
7 Optimal Assignment is made in the following manner:
a) Go row-wise, identify a row with only one zero.
b) Select this zero as an assignment by drawing a box around it.
c) Cancel all zeroes in that column since the same job cannot be assigned to a different
facility.
d) Continue this procedure with columns and complete the assignment.

Compiled by Dr. Suganthi Pais Page 1

 St. Joseph’s College of Commerce (Autonomous), Bangalore

In case of multiple optimal solution or ties up to the last stage, arbitrary assignment can be
made.

Treatment in special cases:

Situation Treatment
Maximization a) Identify the highest element in the given maximization matrix.
Objective b) Subtract each element in the matrix from the highest element. This is called
the Opportunity Loss Matrix. Continue the assignment procedure in this
matrix.
Note: The Opportunity Loss Matrix should not have any negative elements.
Unbalanced Insert a dummy row or column, with all entries equal to zero.
Matrix Note: Insert dummy after converting into Opportunity Loss Matrix, if required.
Prohibited a) Where a particular job cannot be assigned to a particular individual, it is called
Assignment prohibited assignment (Restrictive Condition).
b) Such routes/cells are given a high cost ‘M’, where M = infinity cost.
Condition a) Where a particular job should be assigned only to a particular individual, it is
Assignment or called as Facilitative Condition.
Facilitative b) Delete that row and column and reduce the matrix and continue the
Condition procedure.

PROBLEMS

1. Four operators A, B, C and D are available to a manager who has to get four jobs J1, J2, J3 and J4
done by assigning one job to each operator. The time needed by different operators for different
jobs are given in the matrix below (in minutes):
Operator / Jobs J1 J2 J3 J4
A 12 10 10 8
B 14 12 15 11
C 6 10 16 4
D 8 10 9 7
a) How should the manager assign the job so that the total time needed for all jobs is minimum?
b) If job J1 is to be assigned only to Operator A, what should be the assignment and how much
additional total time will be required?

2. A BPO Co. is taking bid for 4 routes in the city to ply pick up and drop cabs. 4 companies have made
bids as detailed below:
R1 R2 R3 R4
C1 4000 5000 - -
C2 - 4000 - 4000
C3 3000 - 2000 -
C4 - - 4000 5000
Each bidder can be assigned one route. Determine the minimum cost that the BPO should incur.

Compiled by Dr. Suganthi Pais Page 2

 St. Joseph’s College of Commerce (Autonomous), Bangalore
3. A Toy Co. has 4 men available for work on 4 separate jobs. Only one man can work on anyone job.
The cost of assigning each man to each job is given in the following table. The objective is to assign
men to jobs in such as way that the total cost assignment is minimum. You are required to
determine the minimum cost.
Person J1 J2 J3 J4
A 20 25 22 28
B 15 18 23 17
C 19 17 21 24
D 25 23 24 24

4. At the end of a cycle of a cycle of schedules, a trucking firm has a surplus of one vehicle in each of
the cities 1, 2, 3, 4 and 5 and a deficit of one vehicle in each of the city’s A, B, C, D, E and F. the costs
(in rupees) of transportation and handling between the cities with a surplus and cities with a deficit
are shown in the following table.
A B C D E F
1 134 116 167 233 194 97
2 114 195 260 166 175 130
3 129 117 48 94 66 101
4 71 156 92 143 114 136
5 77 134 125 83 142 118
Find the assignment of surplus vehicles to deficit cities that will result in total minimum cost. Which
city will not receive a vehicle?

5. Three different salesmen – X, Y and Z are to be assigned to three different regions – A, B and C, so
that the company’s revenue is maximized. The following matrix gives the sales revenue.

X Y Z
A 10 60 30
B 20 30 15
C 60 40 10
You’re required to use the assignment technique to maximize revenue.

6. A company has 4 zones open and 4 marketing managers available for assignment. The zones are not
equal in sales potentials. It is estimated that a typical marketing manager operating in each zone
would bring in the following annual sales.
Zones East West North South
Sales (Rs. In lakhs) 2.40 1.92 1.44 1.20
The 4 marketing managers are also different in ability. It is estimated that working under the same
conditions, their yearly sales would be proportionately as under:
Manager M N O P
Proportion 8 7 5 4
Required:
If the criteria is maximum expected total sales, find the optimal assignment and the maximum sales.

Compiled by Dr. Suganthi Pais Page 3

 St. Joseph’s College of Commerce (Autonomous), Bangalore

NETWORK ANALYSIS

Project: A project is a set of activities or jobs that are performed in a certain sequence determined
logically to accomplish a given objective.

Conditions:

i) These activities or jobs are to be completed within a specified time and within a specified
cost.
ii) It should also meet the performance standards.

Examples: Construction of a building, new product launch, etc.

Characteristic features common for all projects:

a) Objective: Each project has certain performance standards, i.e., an objective or a set of objectives to
be accomplished.
b) Sequence of activities: Every project consists of a set of activities and events, which are linked
together in a logical manner. There may be concurrent activities and sequential activities in a project.
c) Large scale: Projects are generally very large and complex. It involves:
i) Resources like materials, machinery, tools, etc.
ii) The efforts of a large number of persons like workers, supervisors and experts. The resources
and efforts have to be properly co-ordinated and matched.
d) Time: Every activity in the project involves time. Also, each project has a completion date, i.e., a
deadline. In case of any delay in the completion of the project, extra costs (penalties) may have to be
incurred.
e) Cost: Every activity in the project consumes resources and has a specific cost. Some costs are related
to time, e.g., overheads per day, hire charges for machinery per day, etc., while other costs may relate
to the resources used for that activity, e.g., materials consumed in construction contract, etc.
f) Uncertainty: Time estimates and cost estimates of a project are not very certain. Even where a
company deals in projects of the same kind, e.g., a civil construction company, every new project is of
a one-time nature and has a degree of uncertainty associated with it.

Network or Arrow Diagrams:

A network is a graphical representation of a project, depicting the flow as well as the sequence of well-
defined activities and events, and their inter-relationships.

Project Schedule:

When results of time estimates and computations are added to a network, it is called a Project Schedule.

Compiled by Dr. Suganthi Pais. Page 1

 St. Joseph’s College of Commerce (Autonomous), Bangalore

Fundamental terms used in Network Diagram:

Activity/Task/Job:

a) An activity is any portion of a project/network, which consumes time or resources and has a definite
beginning and ending, e.g., laying of foundation in a construction contract.
b) Activity may involve labour, paper work, contractual negotiations, machinery operations, etc.
c) Activities are graphically represented by arrows and denoted by alphabet A, B, C , D, etc.
d) The tail of the arrow portraying an activity represents the starting point of the activity and its head
(arrow pointer side) represents its completion.

Events/ Nodes/Connectors:

a) The beginning and ending points of an activity or a group of activities are called events.
b) Event is the results of the previous activity, and provides the starting point for the next activity.
c) Some examples of events are – foundation completed, materials purchased, etc.
d) An event is represented graphically by a numbered circle.

Tail Events or Preceding Events:

All activities in a network must commence from some event called Tail Events. Since the arrow diagram
is always drawn from left to right, the LHS Node/Event is called the Tain Event

Head Events or Succeeding Events:

All activities in a network must have terminal points called the Head Event. The Node/Circle to which
the arrow points to, i.e., the RHS Node/Event is called the Head Event.

Note: In a Network, symbol ‘i’ is used to represent Tail Event (or Preceding Event) and ‘j’ for the Head
Event (or Succeeding Event) of an activity. An Activity is denoted by (i-j)

Merge Event:

If an Event represents the joint completion of more than one activity, it is called a Merge Event. In other
words, if two or more arrows/activities point to one Event, such Head Event is called Merge Event.

Burst Event:

If an Event represents the joint initiation of more than one activity, it is called a Burst Event. In other
words, if two or more arrows/activities commence from one Event, such Tail Event is called Burst Event.

Conventions used in Drawing Network Diagram

a) Activities are represented by arrows. They are designated by alphabet like A, B, C, D, E, etc.
b) Events are represented by numbered circles called nodes. They are designated by numbers, i.e., 1,
2, 3, …

Compiled by Dr. Suganthi Pais. Page 2

 St. Joseph’s College of Commerce (Autonomous), Bangalore

c) Time flows from left to right. Hence the activities can be indicated from left to right by way of straight
horizontal lines, vertical lines or diagonal lines also. (In fact, every flow other than right to left is
permitted).
d) Every subsequent event should be depicted preferably to the right hand side of the preceding event.
This will facilitate scheduling computations for each event.
e) Each event/node should be numbered without any ambiguity. The numbers should be assigned to
events in such a way that the number assigned to the Head Event of an activity is greater than the
number assigned to the Tail Event of that activity.
f) Each activity should be bound by two events, i.e., a Tail Event and a Head Event. No Event/Activity
should hand or dangle loosely in the Network. Also, no two activities should have the same Head and
same Tail Event.
g) Arrows that cross each other should be avoided to the extent possible. Where crossing of arrows is
unavoidable, bringing may be used.

Common errors committed in drawing Network Diagrams.

a) Looping: Generally, the arrow points from left to right, since time flows in that direction. If this
convention is not followed, the result is illogical looping.
b) Dangling: This represents a situation when an event is not continued further, i.e., it hangs abruptly in
the middle of a the network without being connected to completion stage. Such activities undertaken
with no results should be avoided. This can be overcome by following these rules:
1) All events, except the first and the last, must have at least one activity entering and one activity
leaving them.
2) All activities must start and finish with an event.
c) Duplication: Activities that have the same head event and the same tail event are called duplicate
activities. Duplication can be corrected by the instruction of a Dummy Activity.

Note: A Dummy Activity is a hypothetical activity, which consumes no resources and time. It is
represented by dotted line in the Network Diagram. For a dummy activity, time consumed = nil,
resources used = nil and cost incurred = nil.

Critical Path:

It is the longest path in a Network Diagram. It is the minimum time required to complete the project.
This path does not provide flexibility in scheduling and transferring resources.

Concept of Floats used in Network Analysis

Non-critical activities have some flexibility, i.e., they can be delayed for some time without affecting the
project duration. This flexibility is called as slack for events and float for activity.

Slack time for an event:

a) Head Event Slack: It is the difference between the latest and earliest time at the Head Event of
an activity.

Compiled by Dr. Suganthi Pais. Page 3

 St. Joseph’s College of Commerce (Autonomous), Bangalore

b) Tail Event Slack: It is the difference between the latest and earliest time at the Tail Event of an
activity.

Total Float:

• Total float of an activity is equal to the difference between the earliest or latest start or finish
time for an activity.
• Activity float = (LST – EST) or (LFT – EFT).
• It indicates the amount of time by which an activity can be delayed without causing any delay in
the project duration.
• It refers to the free time associated with an activity which can be used before, during or after
the performance of this activity.

Note: For all Critical Path Activities, Total Float = Zero. This is because these activities cannot be
delayed.

Free Float:

• It is the portion of the total float within which an activity can be manipulated without affecting
the float of the succeeding activities.
• Free Float = Total Float – Head Event Slack.
• It indicates the value by which an activity in question can be delayed beyond the earliest starting
point without affecting the earliest start and the total float of the activities following it.
• It is always either equal to or less than the total float of an activity. If a negative value is
obtained, then the free float is taken to be zero.

Independent Float:

• It is the portion of the total float, within which an activity can be delayed for start without
affecting the float of the preceding activities.
• Independent float = Free float – Tail Event Slack
• It is always either equal to or less than the Free Float of an activity. If a negative value is
obtained, the Independent Float is taken to be Zero.

CRITICAL PATH METHOD (CPM)

CPM stands for Critical Path Method. It is a network analysis approach that helps to plan and control the
most logical and economic sequence of operations for accomplishing a project. CPM is based on the
estimation of the standard time needed for execution of an activity. CPM manages both the time and cost
of the project.

CPM works by determining the longest path along all the critical activities in a project, which is the
minimum duration of the project. CPM also helps to separate the critical from non-critical activities, which
can help to optimize the use of resources and avoid delays. CPM is a deterministic approach, that assigns
only one time estimate for each activity, based on historical data or expert judgment.

Compiled by Dr. Suganthi Pais. Page 4

 St. Joseph’s College of Commerce (Autonomous), Bangalore

CPM is an activity-oriented technique that focuses on the tasks and work activities more than the events
and milestones. CPM is mainly used for simple, routine and predictable projects, such as civil engineering,
construction, or manufacturing projects.

PERT (PROGRAM EVALUATION AND REVIEW TECHNIQUE)

PERT stands for Program Evaluation and Review Technique. It is an event-oriented technique. It is a
probabilistic model, i.e., it takes into account uncertainties involved in estimation of time of a job or an
activity.

Distinguish between CPM and PERT

Basis of distinction CPM PERT

Full form It stands for Critical Path Method. It stands for Program Evaluation and
Review Technique
Event/Activity It is activity-oriented. Results of various It is Event-oriented.
calculations are considered in terms of
activities.
Uncertainty It is deterministic model. It does not It is a probabilistic model. It uses 3
consider uncertainties involved in estimates of activity time to, tm and tp,
project completion. keeping time uncertainty in view.
Emphasis It places dual emphasis on time and It is primarily concerned with time.
cost.
Nature of projects It is used for projects of repetitive It is generally used for new projects
nature, where one has prior experience where time required for various
of handling similar projects. activities are not pre-determined.

TIME ESTIMATES USED IN PERT:

Three kinds of time estimates are used in PERT taking uncertainty into account. They are:

• Optimistic Time Estimate: This is the estimate of the shortest possible time in which an activity
can be completed under ideal and perfect conditions. No provision is made for delays or setbacks.
It is denoted by to.
• Pessimistic Time Estimate: This is the maximum possible time which an activity could take to
complete the job. This represents all abnormal and inefficient situations, i.e., estimated time if
everything went wrong. It is denoted by tp.
• Most likely Time Estimate: This is the time estimate of an activity which lies between the
optimistic and the pessimistic time estimates. It assumes normal conditions and expected
setbacks. It is denoted by tm.

Characteristics associated with the time estimates in PERT:

The time estimates in PERT are governed by the following formulae / relationships:

Compiled by Dr. Suganthi Pais. Page 5

 St. Joseph’s College of Commerce (Autonomous), Bangalore

• Expected Time: Average time taken for the job can be determined as under:
𝑡𝑜+4 𝑡𝑚+𝑡𝑝
te =
6
• Range: It is the difference between the maximum and minimum time, i.e.,
Range = tp - to
• Standard Deviation: It is equal to one-sixth of the range, i.e.,
1 𝑡𝑝−𝑡𝑜
SD = (tp – to) or 𝑆𝐷 =
6 6

• Variance: It is square of the standard deviation, i.e.,

𝑡𝑝−𝑡𝑜
Variance = SD2 or ( )2
6
• Probability: Due to uncertainty in time estimates, the probability or chance that the project will
be completed within the Expected Duration / Critical Path Duration is only 50%. Probability of
completing the project within a shorter duration than the Critical Path will be less than 50%, and
the probability of completing the project at a date later than the Critical Path will be higher than
50%.

PROBABILITY ANALYSIS IN ACHIEVING COMPLETION DATE

1. A project as a whole, consisting of several activities, will have a normal distribution. Hence, the
probability of completing the project in time (i.e., Critical Path Duration) is equal to Mean Value
Te which is 50%.
2. Using Normal Distribution Assumption, the probability of completing the project by a particular
date can be computed, using the following procedure:
Step Procedure
𝑡𝑜+4 𝑡𝑚+𝑡𝑝
1 Compute the Expected Time te = for each activity.
6
2 Draw the Network Diagram and update te for each activity.
3 Identify the Critical Path and compute Tcp, i.e., Duration of the Critical Path.
4 Compute Variance of all the activities on the Critical Path.
5 Compute the Total Variances of all Critical Path activities, (say V) and compute, Standard
Deviation. SD = √𝑉
𝑡𝑝−𝑡𝑐𝑝
6 Find Standard Normal Variate (Z) = , where Tr = Duration in which the project is
𝑆𝐷
required to be completed, Tcp = Duration of the Critical Path and SD = Standard Deviation
of the Critical Path.
7 Obtain the value of Standard Normal Variate from the Normal Tables. Call this as NT (Z)
8 Compute Probability of completing the project within the required duration = 0.5
± 𝑁𝑇 (𝑍).
Note: Where required time > Critical Path Duration, probability will be greater than 50% and
vice-versa.

PROBLEMS

1. Draw a Network Diagram from the following.

Activity A B C D E F G
Predecessor - - A A B C D,E

Compiled by Dr. Suganthi Pais. Page 6

 St. Joseph’s College of Commerce (Autonomous), Bangalore

2. Draw a Network Diagram from the following.

Activity A B C D E F
Predecessor - A A B C D,E

3. Activities in respect of maintenance of a project is as follows:

Activity 1-2 1-3 1-4 2-5 3-6 3-7 4-7 5-8 6-8 7-9 8-9
Duration 2 2 1 4 5 8 3 1 4 5 3
in months
Draw a Network Diagram and find the Critical Path and the duration of the project. Determine the
total float, free float and independent float.

4. A product comprised of 10 activities whose normal time and cost is given as follows:
Activity 1-2 2-3 2-4 2-5 3-5 4-5 5-6 6-7 6-8 7-8
Duration 3 3 7 9 5 0 6 4 13 10
in months
Required:
a) Draw the Network Diagram.
b) Identify the Critical Path.
c) Determine total float, free float and independent float.
d) What is the project duration and the associated cost, if indirect cost is Rs. 9 per day?

5. A project consists of 7 activities and the time estimates of the activities are furnished as under:
Activity (i-j) 1-2 1-3 1-4 2-5 3-5 4-6 5-6
to 4 3 4 5 8 4 2
tm 10 6 7 5 11 10 5
tp 16 9 16 5 32 16 8
Required:
a) Draw the Project Network.
b) Identify the different path on the Network and its durations.
c) Identify the Critical Path and Expected Project Duration.
d) What is the probability that the project will be completed in 5 days earlier than the critical path
duration.
e) What project duration will provide 95% confidence level of completion (Z0.95 = 1.65)?

**************

Compiled by Dr. Suganthi Pais. Page 7