OR Module All (Sublitted)
OR Module All (Sublitted)
OR Module All (Sublitted)
INTRODUCTION TO OPERATIONS
RESEARCH
Unit Objectives
After a thorough study of this unit, you will be able to:
Define operations research.
Understand the history of operations research.
Develop acquaintance with basic features and significance of operations research.
Understand models and model building.
Identify application areas of operations research
Comprehend operations research techniques
Unit Introduction
Many people still remain in the bondage of self-incurred tutelage. Tutelage is a person's
inability to make his/her own decisions. Self-incurred is this tutelage when its cause lies
not in lack of reason but in lack of resolution and courage to use it without wishing to
have been told what to do by something or somebody else. The difficulty in life is the
choice. Good decision-making brings about a better life. A bad decision may force you to
make another one. A good decision is never an accident; it is always the result of high
intention, sincere effort, intelligent direction and skillful execution; it represents the wise
choice of many alternatives. One must appreciate the difference between a decision and
an objective. A good decision is the process of optimally achieving a given objective.
When decision-making is too complex or the interests at stake are too important, quite
often we do not know or are not sure what to decide. In many instances, we resort to
informal decision support techniques such as tossing a coin, asking an oracle, visiting an
astrologer, etc. However formal decision support from an expert has many advantages.
Management Science focuses on the formal model-driven decision support techniques
such as mathematical programs for optimization, and decision tree analysis for risky
decisions. Such techniques are now part of our everyday life. In decision-making we may
start the process of consideration. It is best to learn the decision-making process for
complex, important and critical decisions.
Cognizant to the above fact, we need to be well acquainted with the fundamentals of
management science as related to its business application. This unit is dedicated to
acquaint you with overview of operations research to make you a better decision maker
by learning the decision-making process. To this end, the unit is organized in to two
sections. In the first section, you will learn about definition of operations research, history
of operations research, basic features and significance of operations research. The second
section is devoted to quantitative analysis & decision making process, models and model
building, and operations research major techniques.
1
Section One: History, Meaning, Features and
Significance of Operations Research
Section Objectives:
Up on completing this section, you will be able to:
- Know the origination of operations research.
- Define Operations Research.
- Understand the nature and basic features of Operations Research.
- Understand application areas of Operations Research
- Identify significance of Operations Research
Section Overview:
1.1 History of Operations Research
1.2 Definition of Operations Research
1.3 Basic features of Operations Research
1.4 Application areas of Operations Research
1.5 Significance of Operations Research
1.1 History of Operations Research
The Industrial Revolution of the 19th century probably did more to shape life in the
modern industrialized world than any event in history. Large factories with mass
production created a need for managing them effectively and efficiently. The field of
Decision Science (DS) also known as Management Science (MS), Operations Research
(OR) in a more general sense, started with the publication of the Principles of Scientific
Management in 1911 by Frederick W. Taylor. His approach relied on the measurement of
industrial productivity and on time /motion studies in the factories. The goal of his
scientific management was to determine the best method for performing tasks in the least
amount of time, while unfortunately using the stopwatch in an inhuman manner.
Until the middle of the 19th century, most industrial enterprises only employed a few
workers. However, as companies expanded, it became less and less feasible for one
person to manage all of the new managerial functions of the business effectively. New
scientific methodologies were developed to provide assistance to each new type of
managerial function as it appeared. As more specialized forms of management emerged,
more specialized sub-functions, such as statistical quality control, equipment
maintenance, marketing research, and inventory control emerged. Whenever a managerial
function is broken down into a set of different sub-functions, a new task, called the
executive function of management, is created to integrate the diverse sub-functions so
that they efficiently serve the interests of the business as a whole. The executive function
evolved gradually with organizations themselves. However, increasing demands were
made on the manager who, in turn, sought aid outside the organization. This gave rise to
management consultants. What we call OR/MS/DS/SS today is, in fact, the use of
scientific tools to aid the executive.
2
OR originated in Great Britain during World War II to bring mathematical or quantitative
approaches to bear on military operations. Since then, OR/MS/DS/SS has evolved to be
applicable to the management of all aspects of a system, product, or service, and hence is
often referred to as Systems Science or Management Science. It has now become
recognized as an important input to decision-making in a wide variety of applications in
business, industry, and government.
The term OR arose in the 1940's when research was carried out on the design and
analysis of mathematical models for military operations. Since that time the scope of OR
has expanded to include economics (known as econometrics), psychology
(psychometrics), sociology (socio-metrics), marketing (marketing research and marketing
science), astrology (astronomy), and corporate planning problems. The growing
complexity of management has necessitated the development of sophisticated
mathematical techniques for planning and decision-making, and the OR/MS/DS/SS
features prominently in this structured decision-making process cycle by providing a
quantitative evaluation of alternative policies, plans, and decisions. The mathematical
disciplines most widely used in OR/MS/DS/SS modeling process include mathematical
programming, probability and statistics, and computer science. Some areas of OR, such
as inventory control, production control, and scheduling theory, have grown into sub-
disciplines of their own right and have become largely indispensable in the modern
world.
Military organizations had gone through the same type of evolution as other businesses
and industries. This organizational evolution took place in the twenty-year gap between
the end of World War I and the beginning of World War II when the military leadership
had to turn to teams of scientists for aid. These teams of scientists were usually assigned
to the executive in charge of operations; hence their work came to be known as
Operational Research in the United Kingdom and by a variety of names in the United
States: Operation Research (OR), Decision Science (DS), Operational Analysis, System
Analysis (SA), Success Science (SS), and Management Science (MS). The name
Operations Research is the most widely used.
The potential of computer and information systems as new tools for management forced
the non-technically trained executives to begin to look for help in the utilization of the
computer. The emerging search for assistance was accelerated by the outbreak of the
Korean War. This vigorous growth of OR in the military continued to provide rapid
applicability to other industries and sectors.
1.2 Meaning and Definition of Operations Research
3
government, business, engineering, economics, and the natural and social sciences,
are largely characterized by the need to allocate limited resources. In these
situations, considerable insight can be obtained from scientific analysis, such as that
provided by OR/MS/DS/SS (Hiller & Lieberman, 1974).
A branch of applied mathematics wherein the application is to the decision-
making process (Gross, 1979).
Comparing definitions given by More-Kimball and Gross, the divergence is notable after
almost 40 years: in one case, OR/MS/DS/SS is defined as scientific method, while in the
other it is seen as a branch of mathematics.
In examining these definitions, it should be noted that neither the old and well-established
scientific discipline nor science itself has ever been defined in a way that is acceptable to
most practitioners.
Operations Research is defined by different scholars from different perspectives. But, the
most important comprehensive definition is given as follows.
The OR/MS/DS approach to decision making includes the diagnosis of current decision-
making and the specification of changes in the decision process. Diagnosis is the
identification of problems (or opportunities for improvement) in current decision
behavior; it involves determining how decisions are currently made, specifying how
decisions should be made, and understanding why decisions are not made, as they should
be. Specification of changes in decision process involves choosing what specific
improvements in decision behavior are to be achieved and thus defining the objectives.
Nowadays, the OR/MS/DS approach has been providing assistance to managers in
developing the expertise and decision tools necessary to understand the decision
problems, put them in analytical terms and then solve them. The OR/MS/DS analysts are,
e.g., "chiefs of staff for the president", "advisors", "and R&D modelers" "systems
4
analysts", etc. Applied Management Science is the science of solving business problems.
The major reason that MS/OR has evolved as quickly as it has is due to the evolution in
computing power. The foundation of OR/MS/DS/SS is built on the philosophy of
knowledge, science, logic, and above all creativity. Almost all decision problems have
environments with similar components as follows:
The procedure to be followed in the study of OR, generally involves the following major
phases.
1. Formulating the problem
2. Constructing a mathematical model
3. Deriving the solution from the model
4. Testing the model and its solution ( updating the model)
5. Controlling the solution
6. Implementation
1.4 Application Areas of Operations Research
There are so many application areas of operations research; to mention some of the most
widely known areas:
Forecasting Maintenance and Repair
Production Scheduling Accounting procedures
Inventory Control Packaging
Capital Budgeting Natural Resource Management
Transportation Research and Development
Plant location Health Care
Human Resource Management Quality Control
Advertising and sales research
Equipment Replacement, etc.
5
Annual saving increments for many companies
Improvement in response time of customers
Increased traffic citation revenues
Optimizing refinery revenues
Optimal overbooking discount fairs
Improving the efficiency of a production line
Helpful in establishing a long-range corporate strategy, etc.
Exercise 1-1:
Section Objectives:
Up on completing this section, you will be able to:
6
- Understand major OR techniques
- Know quantitative analysis & decision making process
- Understand what a model is.
- Identify categories of OR models
- Appraise the management science approach
Section Overview:
1.6 OR Techniques
1.7 Quantitative Analysis & Decision Making Process
1.8 Models and Model Building
2) Allocation models :
o Linear programming
o Non-linear programming
o Transportation models
o Assignment models
o Integer programming
o Goal programming
o Dynamic programming
3) Inventory models
4) Replacement models
5) Network models
6) Waiting- line models(Queuing theory)
7) Simulation
8) Sequencing models
9) Decision theory
10) Game theory
11) Markov models
12) Regression and correlation
o Decision Making: is the process of selecting a feasible course of action from a set of
alternative courses of actions so as to solve problems or capitalize on opportunities.
The decision making process is initiated by a problem. The intention of the manager,
when making a decision or selecting a course of action, is to solve that problem. In doing
7
so, the manager first makes an analysis of the alternatives. This analysis process takes
two forms— qualitative and quantitative.
Quantitative
analysis based
upon
mathematical
techniques
Figure 1.1 The Decision Making Process
(Source: Anderson, Sweeny, and Williams (2003)
The above figure shows the brief procedures in the decision making process. The steps in
the rational decision making process includes:
1. Identify and define the problem;
A problem is a necessary condition for a decision, i.e. there would be no need for
decisions if problems did not exist.
2. Determine the set of alternative solutions;
3. Determine the criteria to evaluate alternatives;
=>Identifying those characteristics that are important in making the decision.
4. Analyze the alternatives;
=>Based on the advantages and disadvantages of each alternative and using qualitative
and quantitative approaches, analysis of the identified alternatives is crucial in the
decision process.
5. Select the best alternative/make the decision;
=> Select the best alternative that suits to solve our decision problem. In selecting the
best alternative, factors such as risk, timing and limiting factors should be considered
adequately.
6. Implementing the solution;
=> Putting the decision into action. Deciding or making a selection is not an end, we
have to implement it.
7. Establishing a control, follow up and evaluation system;
=>On going actions need to be monitored.
=>Follow – up of the decision made for any adjustments and feedbacks to be
incorporated.
8
=>Evaluate the results and determine if a satisfactory solution has been obtained. This
is to assure the achievement of the goal-solving the problem.
Our emphasis is on the analyses approaches: qualitative and quantitative. In qualitative
analysis, intuition and the manager’s subjective judgment and experience are used. This
type of problem solving is more an art than a science.
o The qualitative approach is usually used when:
The problem is simple
The problem is familiar
The costs involved are not so great
Immediate decisions are needed
o The quantitative approach is used when:
The problem is complex
The problem is not familiar
The costs involved are substantial
Enough time is available to analyze the problem
Note: Both the quantitative and qualitative analyses of a problem provide important
information for the decision maker. Of course, decisions based on quantitative analysis
tend to be more objective than those based on a purely qualitative analysis. Although OR
is not entirely quantitative, its applications falls under the heading of quantitative
analysis. For this reason OR makes use of quantitative models.
To sum up, the decision making procedure as explained earlier starts with a certain
problem. The management science approach to analyze and solve the problem involves
careful definition of the problem, use of models, analysis of models (model solution), and
implementation and follow-up. (See figure 1.2)
Problem
Definition
Model
Construction
Analysis
(Model
Solution)
Implementation
& Follow-up
9
A model is a selective abstraction of reality. It is a simplified and often idealized
representation of real world problems. A good model should capture the important details
of reality without including minor details that would obscure rather than illuminate. In
this sense, a model can be taken as a selective abstraction because only those details that
are considered as important for the problem at hand are included in the model. Thus, it is
important to carefully decide which aspects of reality to include in a model.
There are certain significant advantages gained when using a model. These are:
Problems under consideration become controllable through a model
It provides a logical and systematic approach to the problem
It provides the limitations and scope of an activity
It helps in finding useful tools that eliminate duplication of methods applied to
solve problems.
It helps in finding solutions for research and improvements in a system.
It provides an economic description and explanation of either the operation, or
the systems they represent.
1. Models by Function:
These models consist of Descriptive models, Predictive models and Normative
models
A) Descriptive Models: describe and predict facts and relationships among the
various activities of the problem. These models do not have an objective function
as a part of the model to evaluate decision alternatives. In this model, it is possible
to get information as to how one or more factors change as a result of changes in
other factors.
B) Normative or Optimization Models: they are prescriptive in nature and develop
objective decision-rule for optimum solutions.
2. Models by Structure and Abstraction :
A. Iconic or Physical Models: are pictorial representations of real systems
and have the appearance of the real thing. An iconic model is said to be
scaled down or scaled up according to the dimensions of the model which
may be smaller or greater than that of the real item. It is also called Static
Model. It is given in two or three dimensions. It is a representation of the
real object. These models are easy to observe and describe but are
difficult to manipulate.
Example:
The structure of an atom
Model of an airplane
Photograph of a machine
10
Layout drawing of a factory
Glob
B. Analog Models: They are more abstract than iconic models for there is no
look alike correspondence between these models and real life items. These
models are less specific, less concrete but easier to manipulate than iconic
models. These are abstract models mostly showing inter and intra
relationships between two or more parameters. For example: It may show
the relationship between an independent variable (input) with that of a
dependent variable (output). For instance; histogram, frequency table,
cause-effect diagram, flow charts, Gantt charts, price-demand graph,
world map and others. They are two dimensional.
C. Mathematical or Symbolic Models: They are most abstract in nature.
They employ a set of mathematical symbols to represent the components
of the real system. These variables are related together by means of
mathematical equations to describe the behavior of the system. The
symbolic model is usually the easiest to manipulate experimentally and it
is the most general and abstract. Its function is more explanatory than
descriptive.
Example:
1. (x + y) 2 = x2+2xy+y2
2. Max. Z=3000x1 +2500x2
Subject to:
2x1+x2 < 40
x1+3x2 < 45
x1< 12
x1 , x2 > 0
11
A. Specific Models: when a model presents a system at some specific time it
is known as a specific model.
B. General Models: are models applicable to all situations without time
bound. Simulation and Heuristic models fall under this category.
Unit Summary
Exercise 1-2
1.
1. Distinguish between quantitative and qualitative decision making process.
2. Why are models required?
3. Describe the basic types of models.
4. Is OR an art or science? Justify with supportive reasons.
5. When is quantitative analysis required in decision making?
6. Elaborate the application of Operations Research techniques in service giving
enterprises.
12
7. Explain the management science approach to decision making.
8. Identify application areas of Operations Research in business.
9. What are the drawbacks of using quantitative analysis?
10. Briefly explain the criteria of model classification.
11. Give examples of allocation models.
12. Explain the milestones in the development of OR/MS/DS/SS.
References
13
UNIT TWO
LINEAR PROGRAMMING
Unit Introduction:
A large number of decision problems faced by a business manager
involve allocation of resources to various activities, with the objective of
increasing profits or decreasing cost. Normally, the resources are scarce
and performance of number of activities within the constraints of limited
resources is the challenge. A manager is, therefore, required to decide as
to how best to allocate resources among the various activities.
Unit Objectives:
After going through this unit you will be able to:
o Undertook the formulate of linear programming problems
o Solve linear programming (LP) problems through graphical and
simplex methods
o Understand the concept of Duality in LP models
Pre-Test Questions:
1. What are some types of problems that LP can help in
solving?
2. What characteristics must a problem have if linear
programming is to be used?
3. What is economic interpretation of dual variables?
14
Section One: Linear Programming Problem Formulation
Introduction:
Programming in American term is another name of planning. Planning of
resource is necessary because resources are scare and they are capable
of alternative uses. The word ‘Linear’ means that the relationship
handled are those represented by straight lines i.e. the relationships are
of the form Y= a+bx, and the word ‘programming’ means taking decisions
systematically. This section deals with description of LP problem, basic
assumptions and how to formulate a business problem of resource
allocation in form of LP problem.
Section Objectives
The main objective of this section is
o To understand the basic nature and expression of LP problem.
o To learn how to formulate LP problem
o To know the advantages of LP problem.
Section Overview
2.1 Description of LP problem
2.2 Requirements for application of LP
2.3 Assumptions underlying LP
2.4 Advantages of LP
2.5 Formulation of LP problems
15
Optimize Z= C1x1+C2x2+C3x3+…+Cnxn
Subject to
a11x1+a12x2+……..+ajj xj+……a1nxn(< = >) b1
a21x1+a22x2+……..+a2j xj+……a2nxn(< = >) b2
.
am1x1 + am2 x2 +……..+ amj xj +……amn xn(< = >) bm
Where,
o (< = >) means any of the three signs may be there.
o Optimize means maximize or minimize objective function
o The linear function which is to be optimized is called objective
function
o All constraints are equations except for non-negativity
restrictions which are inequalities.
o The RHS of each constraints is non-negative
o All variables are non-negative
o Inequality constraints can be changed to equations by adding or
subtracting LHS of each constraint by non-negative variable (ie
a slack variable S1 is added to LHS of constraint with the sign <
and a surplus variable S2 is subtracted on the LHS of constraint
with the sign >)
o aij and bm are known coefficients and xj is unknown variable.
16
means that the amount of each resource used and associated
contribution to profit or cost in the objective function should be optimal,
proportional to the value of each decision variable. If we increase the
production quantity, the resources requirement should also be increased
in the same proportion.
Example:
a. Eg. If the product is assumed to contributes 10 Birr
towards the profit, the total contribution would be 10x.
b. If one unit 2 hours of labour of certain type 10 units
would require 20 hours
17
2.4. ADVANTAGES OF LINEAR PROGRAMMING
Example 1
An electronic firm is undecided at the most profitable mix for its
products. The products manufactured are transistors, resistors and
carbon tubes with a profit of (per 100 units) US $ 10, $6 and $4
respectively. To produce a shipment of transistors containing 100 units
requires 1 hour of engineering, 10 hours of direct labor and 2 hours of
administrative service. To produce 100 units of resistors requires 1 hour,
4 hours and 2 hours of engineering, direct labor and administrative time
respectively. For 100 unit of carbon tubes it needs 1 hour, 6 hours and 5
18
hours of engineering, direct labor and administrative time respectively.
There are 100 hours of engineering time, 600 hours of direct labor and
300 hours of administrative time available. Formulate the corresponding
LPP.
Solution:
Let the firm produce x hundred units of transistors, y hundred units of
resistors and z hundred units of carbon tubes. Then the total profit to be
maximized from this out put will be
Z = 10x + 6y + 4z
x + y + z < 100
10x + 4 y + 6z < 600
2x + 2y + 5z < 300 with x,y,z > 0
Thus formulated LPP is
Maximize z = 10x + 6y + 4z
Solution:
19
Let us have the manufacture of x 1 and x2 units of product A and B
respectively. Then the given data indicates the relationship of decision
variables as follows:
Objective function Minimise cost =60x1 + 80x2 (production cost)
Constraints: x2> 200 (Agreement for supply)
x1 < 400 (machine hours for product A)
x1 + x2< 500 (labour hours)
x1 , x2> 0 ( non –negative constraint)
Introduction:
Section Objective
After completing this section the learners must be able to:
Prepare graphs and interpret the results of linear programming
problems.
Use simplex method to solve problems of maximization and
minimization type.
Determine the dual of any linear programming model and
understand its economic interpretations.
Section Overview
When there are only two decision variables involved, the conditions can
be placed on a graph to find the feasible region of the decision making.
The optimal solution is obtained by reaching the point on the feasible
20
region that optimizes the solution. We, then, can interpret the results
from this graph.
Solution:
Step I. Formulate LP Problem.
The information available can be put into structural matrix form as follow.
Commodities
Requirement Total
P1 P2
Machine I 4 2 60
Machine II 2 4 48
Profit $ per unit 8 6 -
21
Objective function is profit maximization and can be expressed as.
Max Z= 8x1 + 6x2
The given constraints are time and machine and can be converted into
linear relations as follow:
4x1 + 2x2 < 60 (i)
2x1 + 4x2 < 48 (ii)
Where x1, x2 > 0 non-negativity condition.
2x1 + 4x2 = 48
at x1 axes, x2 = 0 ∴ 2x1= 48 or x1 =24
at x2, axes, x1 = 0 ∴ 4x2 = 48 or x2 = 12
By these coordinates (24,12) we get line AE in graph.
Now, any point on line BD satisfies (i) constraint and any point on line
AE satisfies (ii) constraint. The constraints cannot be violated, they must
be satisfied. Any solution which satisfies all the know constraints is
called optimal solution. Since both the constraints are of the type <
hence any point on the right hand side (RHS) of BD or AE becomes
infeasible area/solution for which we are not concerned.
X2
40 -
30 - B
20 -
A
12 -
C
10 -
E
0 D
X1
10 15 20 24 30 40
22
Step III. Both the constraints are to be satisfied simultaneously,
therefore, OACD becomes the region of feasible solution. This is also
known as feasible polygon. Any point in this feasible polygon will also
give rise to optimal solution which we are in need. There are infinite
numbers of points in this feasible area to be examined. Let us take any
point in feasible region. Its movement is possible in two directions, either
towards origin or away from it. OA, AC, CD, OD are bounding lines of
feasible area and hence optimal solution must lie on any boundary line.
On line OA, point A give maximum profit, on line OD, point D gives
maximum profit.
Step IV. Evaluate the objective function Z= 8 x1 + 6x2 for all points of
feasible region i.e. O,A,C,D.
At point O profit is zero ∴ Z=O
At point A x2=12, x1=0 ∴ Z=12x6=72
At point D x1=15, x2=0 ∴ Z=15x8=120
At point C x1=12, x2=6 ∴ Z=12x8+6x6=132
(from graph)
Step V. Z is maximizing objective function, hence the point with
maximum value of Z is the optimal solution point.
Therefore at point C (Z=132) with x 1=12 and x2=6 is the optimal
point.
Solution:
The first step is skipped as LP problem is already formulated. We will
follow other steps simultaneously. In constraint (i) 2x 1 –x2 > 0 there is no
constant value, hence it must pass through the origin. First convert it
into equality.
2x1 –x2 > 0 . New give x1 any arbitrary value.
When x1 =0, x2=0
x1 =1, x2=2
x1 =2, x2=4 and so on.
We draw the line with these coordinates and get line I drawn in the graph
passing through origin.
23
We draw the line II (80, 20) as shown in graph.
Now, convert constraint (iii) in equality
0.9x1 + 0.8x2 =40
When x1 =0, x2=50
X2 =0, x1=44.4
We draw line III (44.4, 50) as shown in graph.
For feasible area we need to examine all the there constraints equations
(Note, all are > type)
In equation (ii), the feasible area should be above the line because it is
greater than the sum of x1 and x2.
Similarly in equation (iii) it is on the RHS therefore feasible area (region)
is indicated by three rows or shading and extends upto infinity.
Now we have to find out different values of Z at different corner points,
B,C,E by finding out their coordinates (x 1, x2) then putting them in
objective function Z. The point which gives the minimum value is the
answer.
At corner B x1=16,x2=32 therefore Z= 1440
At corner C x1=34.4,x2=11.4 therefore Z= 1948
At corner E x1=80,x2=0 therefore Z= 4000
From the above we can see that minimum value of Z is at point B where
x1=16 and x2 =32 and hence it is the answer.
24
2.7 Simplex Method of Solving LPM
Before using the simplex method, let us examine and understand certain
basic terms involved in the procedure.
1. Standard Form: This has already been clarified in the initial part of
this chapter. With linear relationships of objective function and
constraints, making RHS of constraints as equal produces standard
form, whereas the inequality situation is called canonical form.
2. Slack and Artificial Variables: These have also been explained under
an appropriate heading. Their physical significance have also been
clarified. These are generally designated as S 1, S2 . . . . etc. and A1, A2 etc.
respectively. Whereas the slack variables indicate spare capacity of the
constraints, artificial variables are imaginary variables added for
25
standard form.
5. Basic Feasible Solution: When a basic solution satisfies even the non-
negativity requirement is called Basic Feasible Solution. Since it has to
be within the feasible region as explained at point 4.7 (graphical method),
a basic feasible solution corresponds to a comer point of the feasible
region.
7. Variable Mix: The values of the column that contains all the variables
in the solution.
8. Basis: The set of variables which are not set to zero and figure in the
column of "Product Mix" are said to be in the 'Basis'. Other than these
figuring in the product mix column are termed as non basic variables.
10. Cj Row: It is the row containing the coefficients of all the variables
(decision variables, slack or artificial variables) in the objective function.
26
of that column is introduced in the basis.
13. Pivot -Column: The column with the largest positive number in Cj - Zj
row in a maximization problem or the smallest number in a minimization
problem is called Pivot column. This indicates the variable entering the
solution in the next iteration by replacing an appropriate variable.
14. Pivot Row: When we work out the ratio of quantities bi's and the
elements of the Pivot column, we get the last column of the simplex table.
The outgoing variable to be replaced by the entering variable (decided by
the key row) would be the one with the smallest positive value of the ratio
column.
15. Pivot Element: The element at the point of intersection of the key
column and the key row is called the Pivot element.
Objective Function
Optimise (Maximise or minimise) Z = C1 x1 + C2 x2 + . . . . . . .+ C n xn where
Cj (j = 1,2,. . . . . . . . . n) are called cost coefficients.
Constraints (linear)
Subject to,
a11 x1 + a12 x2 +...........a1n xn = b1
a21 x1 + a22 x2 +...........a2n xn = b2
. . . . . . . . . . . .. . . . . . . . . . . . .
.........................
.........................
aml x1+ am2 x2 +.........amm xn = bm.
Where bi (i = I, 2....m) are resources constraints and constants aij (i =
l,2, ...............................……….m; j = 1,2,………..n ) are called the input
output coefficients.
Also, x1, x2…………... xn > 0 (non-negative constraint)
27
The decision variables are required to be non-negative so that they
can contribute towards the optimum objective function, which is either
maximization or minimization type.
When the constraints are of the type < bi, then to convert the it into
equality we need adding some variable (not constant) this is normally
done by adding variables such as S1, S2. . . . . Sn, which are called slack
variables. In physical sense, these slack variables represent unused
resources, the slack variables contribute nothing towards the objective
function and hence their coefficients in the objective function are to be
zeros.
Standardization/Tableau Form/
Types of constraint Standard form
≤ Add a slack variable
= Add an artificial variable
≥ subtract a surplus variable and add an artificial variable
28
The artificial variables in a maximization problem will appear in the objective function
with a large negative coefficient so that they are quickly eliminated as we proceed with
the solution.
In a maximization problem with all less than or equal to constraints, we have an initial
feasible solution. With mixed constraints, we do not have initial feasible solution but only
initial solution which is not feasible.
5. Determining the leaving variable: the leaving variable is identified as the one
with the smallest non-negativity ratio for quantity divided by respective
positive pivot columnar entries. The row of the leaving variable is pivot row.
6. Make the entering variable basic and the leaving non-basic by applying
elementary row operations of matrix algebra.
29
7. Iteration for improved solution:
(a) Replace outgoing variable with the entering variable and enter
relevant coefficients in Zj column.
(b) Compute the, Pivot row with reference to the newly entered
variable by dividing the old row quantities by the key element.
(c) New values for the other rows. In the revised simplex table, all
the other rows are recalculated as follows.
New row elements= Elements in the old row - [corresponding key
column element multiplied by the corresponding new element of the
revised row at (b) above.]
Note that: if the solution is not optimal the steps will be repeated again and again until
the optimal solution is obtained!
30
In maximization case the objective function is to maximize the revenue or
profit. Heere the constraints aree of the < type. There may be cases when
constraints are of > and also = type.
Example 1
Maximise Z = 30x1 + 40x2
Subject to, 60x1 + 120x2 < 12,000
8x1 + 5x2 < 600
3x1 + 4x2 < 500
x1, x2 > 0
Solution:
We convert the inequality into equations by adding slack variables.
Above statements can thus be written as follows.
60x1 + 120x2 + S1 = 12,000
8x1 + 5x2 + S2 = 600
3x1 + 4x2 + S3 = 500 and
x1, x2, S1, S2, S3 > 0.
where S1,S2, S3 are slack variables and objective function is re-written
as: Max. Z = 30x1 + 40x2 + 0.S2 + 0.S2 + 0.S3
Now there are five variables and three equations and hence to obtain
the solution, any two variables will have to be assigned zero value.
Moreover, to get a feasible solution, all the constraints must be satisfied.
To start with, let us assign x1 = 0; x2 = 0 (Both decision variables are
assigned zero values) Hence, S1 = 12,000
S2 = 600
S3 = 500 and Z=0
This can be written as initial simplex table 1
Key Row
Key Column
Entering variable
Since Cj - Zj is maximum at + 40, i.e., profit is more for each unit for
x2 variable, we introduce x2 into the solution. It is the marked as key
31
column and x2 becomes the entering variable. Dividing Quantities (bi's)
by the corresponding key elements of each row, we obtain the ratio
(bi/aij) column such as for row S1, it is 12,000 ÷ 120 = 100.
Leaving variable
For each unit of x2, 120 units of S1, 5 units of S2 and 4 units of S3 will
have to be utilized. Minimum unutilized capacity of material is 100, it
becomes outgoing variable. (This is required to be the least positive value
of ratio, which is obtained by dividing the values in bi column by the
corresponding elements in the key column). Here Key element
corresponds to x2 and S1 and its value is 120, The least ratio being 100
corresponding to S1, it becomes the' outgoing variable, replaced by x2.
Now each of the elements of the Key row is divided by Key element to get
x2 row in the new table. Thus we get the key row as follows:
32
Key column being that for xl and key row for S2 we get the key element as
11/2 and by dividing S2 row by the Key element, we get xl row in the new
table as follows:
Other rows are correspondingly obtained as in table I.Since all the values
of Cj - Zj are either negative or zeros, it is an optimal solution. Hence, the
optimal mix would be:
Quantity of item 1 (x1) = 200/11
Quantity of item 2 (x2) = 1,000/11
Total profit = 46, 000/11
By this iterative process, we obtain optimal solution of a maximising
problem and iteration stops when values of Cj - Zj < 0. This optimality
test is carried out at every stage to reach optimal solution.
Solution:
Adding slack variables and arranging in the simplex table, we get
33
Simplex Initial Table
SIMPLEX TABLE II
.
SIMPLEX TABLE III
Now, all the values of ∆j being zero or negative, suggesting that the
solution is optimal and Z = 2,400 for x 1 = 50 and x2 = 125. S1
indicates surplus.
34
These variables, therefore, need be removed from the solution as soon
as they become non-basic.
35
problem. This method is taken up here after Big M-method.
Big M-Method
In this method, we assign the coefficients of the artificial variables, as a
very large positive penalty i.e., +M for the minimisation problem. This is,
therefore called Big M-method.
The Big M-method for solving LP problem can be adopted as follows:
Step 1 : The standard simplex table can be obtained by adding
slack and artificial variables. Slack variables are assigned zero
coefficients and artificial variables assigned +M coefficients in the
objective function.
Step 2: We obtain initial basic feasible solution by assigning
zero value to the decision and slack variables.
Example 1
36
Min. Z = 60x1+ 80x2 (Total Cost)
Subject to, 20x1 + 30x2 > 900 (Vitamin X Constraint)
40x1 + 30x2 > 1,200 (Vitamin Y Constraint)
and x1, x2 > 0
Adding slack and artificial variables, we get
SIMPLEX TABLE I
Cj 60 80 0 0 M M Quantity Ration
Zj
Variables x1 x2 S1 S2 A1 A2 bi Bi/aij
M A1 20 30 -1 0 1 0 900 45
M A2 40 30 0 -1 0 1 1,200 30
∆j 60-60m 80-60m M M 0 0
SIMPLEX TABLE II
From the table it can be seen that x 2 becomes the entering variable and
A1 the leaving variable. The modified simplex table can be written as:
SIMPLEX TABLE III
Since all the values of ∆j are non-negative, we have reached the optimal
solution of the problem.
37
Hence the optimal solution is given by
x1 = 15 and x2= 20
and Minimum Z = 2,500.
With simplex this condition can be detected by examining the C-Z row of the final
tableau. If a zero appears in the column of a non-basic variable; i.e., a variable that is not
in solution; it can be concluded that an alternative solution occurs.
3. Degeneracy:
In some cases there will be a tie for the lowest non-negative ratio for quantity divided by
substitution rate. Such an occurrence is referred to as degeneracy because it is
theoretically possible for subsequent solutions to cycle (i.e., return to the pervious
solution). It will usually suffice to simply select one variable arbitrarily and proceed with
computations. But there are ways of dealing with ties in a specific fashion.
4. Case of infeasibility:
In the simplex approach, infeasibility can be recognized by the presence of an artificial
variable with a non-zero value in a solution that appears optimal (i.e., a tableau in which
the signs of the values in row C-Z indicate optimality).
38
Shadow price: is a marginal value; it indicates the impact that a one unit
change in the value of the constraint would have on the value of the
objective function.
Shadow prices are the values in the Z-row of slack columns.
Example 1: A firm that assembles computers and computer equipment is about to start
production of two new micro computers. Each type of micro computer will require
assembly time, inspection time and storage space. The amount of each of these resources
that can be devoted to the production of the computers is limited. The manager of the
firm would like to determine the quantity of each of the microcomputers to produce in
order to maximize the profit generated by sales of these computers.
In order to develop a suitable model of the problem the manager has met with the design
and manufacturing head of the organization and obtained the following information:
Cj-Z 0 0 10 -40/3 0
Shadow prices
From the above tableau; the shadow prices are $ 0 for S 1, $10 for S2 and $40/3 for S3. This
tells us that if the amount of assembly time was increased by one hour, there would be no
effect on profit; if the inspection time was increased by one hour, the effect would be to
increase profit by $ 10, and if storage space was increased by one cubic foot, profit would
increase by $40/3. The reverse holds true. That is by using the negative shadow prices we
can determine how much a one- unit decrease in the amount of each constraint would
39
decrease profit. Hence, a one –unit decrease in inspection time would decrease profit by $
10 since its shadow price is $ 10. But a one –unit decrease in assembly time would have
no impact on profit and a one-unit decrease in storage space would decrease profit by $
40/3.
Remark: shadow prices do not tell us the extent to which the level of a scarce resource
can be changed and still have the same impact per unit.
In the above problem, the optimal solution was given by the intersection of inspection
time and storage space constraints. Thus, the shadow prices in the final simplex tableau
will remain the same so long as the same constraints give the intersection for the optimal
solution. For what range of changes in the RHS value of those constraints the current
shadow prices remain valid? This is answered by range of feasibility.
Range of Feasibility (Right hand side range)
The range of feasibility is the range over which the RHS value of a constraint can be
changed and still have the same shadow prices. To know this range, first calculate
feasibility ratio as:
≤ Constraint ≥ Constraint
Allowable RHS increase Smallest positive FR Smallest negative FR
Allowable RHS decrease Smallest negative FR Smallest positive FR
The effect of a RHS change in constraint on the objective function depends whether the
change leads to relaxation or tightening of the constraint. A
Relaxation and tightening of constraints
≤ Constraint ≥ Constraint
RHS increase Relaxation Tightening
RHS decrease Tightening Relaxation
For a less than or equal to (≤) constraint, an increase in RHS leads to relaxation
(increase) in the feasible solution area which is a favorable change. So an increase has a
positive sign attached to it. Conversely, a decrease is treated as negative.
For a greater than or equal to constraint, an increase in RHS leads to tightening of
feasible solution area and it is not a favorable change. So an increase has a negative sign
attached to it. Conversely, a decrease is treated as positive.
When a constraint is relaxed it will have a favorable effect on the objective
function. This means, if the problem is maximization, relaxation leads to a higher
objective function value. In minimization problems relaxation results in a lower
value of the objective function.
When a constraint is tightened, it results in a decrease in the value of the objective
function (in maximization) and an increase in the value of the objective function
(in minimization)
40
The impact of RHS change on the optimal solution
Basis Cj 60 50 0 0 0 Quantity
X1 X2 S1 S2 S3
S1 0 0 0 1 6 -16/3 24
X1 60 1 0 0 1 -1/3 9
X2 50 0 1 0 -1 2/3 4
Z 60 50 0 10 40/3 740
41
(Current RHS amount-allowable decrease) upto Current RHS amount + allowable
increase)
Constraint 1 (Assembly time): 100-24 upto 100+∞
:(76-∞ )
Constraint 2 (Inspection time: 22-4 upto 22+4
:(18-26)
Constraint 3 (Storage space): 39-6 upto 39+4.5
:(33-43.5)
Interpretation: Each hour decrease in assembly time will decrease the current profit
by Birr 0 (i.e no effect-indicated by shadow price) as long as the decrease is up to 24
hours. But if the assembly time decreases by more than 24 hours (or if the total available
assembly time is lower than 76 hours), the current shadow price will no longer be valid.
That is, the profit will be affected. But available assembly time can increase indefinitely
(=allowable increase is ∞ ) without affecting the current profit level.
Finally, each cubic feet increase or decrease in storage space results in an increase or
decrease, respectively, of profit by $13.33 (i.e 40/3) as long as the total storage space is
between 33 and 43.5 cubic feet.
2.) Before analyzing the effect of constraint changes on the objective function, first check
whether the change contemplated is with in the allowable increase or decrease of that
constraint. If the change is with in the allowable increase or decrease, it is possible to
analyze the change by using the current shadow prices. Otherwise, the model must be
reworked again to know the effect.
Is a 3 cubic feet increase with in (≤) the allowable increase of the storage space
constraint? Yes it is, since the allowable increase is 4.5 cubic feet.
Thus the objective function will increase by $15 (i.e 4.5×10/3)
But an 8 cubic feet increase is not with in the allowable increase. Therefore, the
model must be reworked to know the increase in the objective function. In reworking the
model change the available storage space to 39+8=47 cubic feet and keep all other parts
of the model as they are.
3) A decrease of 6 cubic feet is with in the allowable decrease of the constraint (6≤6). The
objective function value will decrease by $20 (i.e 6×10/3). But a decrease of 8 cubic feet
is not with in the allowable decrease. So the model must be reworked to know the effect
on the objective function.
Dear distance learner! The second important change we will consider is the effect of
changes in the objective function coefficients.
There are two cases:
42
Case-I: A change in the objective function coefficient of a variable which is
not currently in solution: Range of insignificance
The range over which a non-basic variable’s objective function coefficient can change
without causing that variable to enter the solution mix is called its range of
insignificance.
Example
Minimize 10X1+3X2
Subject to:
2X1+X2 80
2X1 +4X2 200
X1, X2 0
Final tableau:
Basics cj 10 3 0 0 Qty.
X1 X2 S1 S2
S2 0 6 0 -4 1 120
X2 3 2 1 -1 0 80
z 6 3 -3 0 240
cj-z 4 0 3 0
43
Case-II: Change in the objective function coefficient for a variable currently in
solution:
Range of optimality
The range over which the objective function coefficient of a variable that is in solution
(basic variable) can change without changing the optimal values of the decision variables
is called the range of optimality. Note that the objective function’s value will change.
Range of optimality is calculated for only original decision variables because
slack/surplus variables and artificial variables do not have any contribution for the
objective function.
For both maximization and minimization problems, the range of optimality is
calculated as follows:
The values in raw Cj-Z must be divided by the corresponding row values of the
variable in question. This will result in a series of ratios. The smallest positive
ratio will indicate the amount of allowable increase and the smallest negative
ratio will indicate the amount of decrease.
Example
Minimize 10X1+3X2
Subject to:
2X1+X2 80
2X1 +4X2 200
X1, X2 0
Final tableau
Basics cj 10 3 0 0 Qty.
X1 X2 S1 S2
S2 0 6 0 -4 1 120
X2 3 2 1 -1 0 80
Z 6 3 -3 0 240
cj-z 4 0 3 0
The basic variable in the last tableau is only X2. The range of
optimality for X2 is calculated as follows:
X2 row (B) 2 1 -1 0
A/B 4/2=2 ↑ 0 -3 ↓ ∞
: ↓ Allowable decrease
: (0-5)
Interpretation: The objective function coefficient of X2 can be between 0 and 5 without
changing the optimal values of the decision variables (i.e X1 =0, X2 =80). But the value
44
of the objective function will change. For instance if X2’ s coefficient is 4,
Min.Z=10×0+4×80=320.
Example 2
Minimize 20X1+12X2 +16X3
Subject to:
X1+X2 25
X2 – X3=0
X3 5
X1, X2 , X3 0
Required: Solve the above problem by simplex method and answer the following
questions.
a) What impact on the solution would a decrease of 10 units in the first constraint
have?
b) If the first constraint could be decreased by 10 units at a cost per unit of $15,
would it be worth while to do so? Explain.
c) What change in the coefficient of X3 in the objective function would cause it to
come in to solution?
d) If the cost coefficient of X1 is increased by $ 5, what impact would that have on
the quantities and on the values of the objective function in the final tableau?
Solution
Final tableau
Basics cj 10 12 16 0 0 Qty.
X1 X2 X3 S1 S3
X1 20 1 0 1 -1 0 25
X2 0 1 -1 0 0 0
12
S2 0 0 0 1 0 1 5
Z 20 12 8 -20 0 500
cj-z 0 0 8 20 0
Shadow prices
To answer (a) we should first calculate the range of feasibility of the first
constraint. Ranges of feasibility for the first and third constraint are calculated as
follows :
0 0 0 ∞↑ ∞↑
0 1 5 ∞ 5↓
45
↓ =Allowable decrease
Note that the first constraint is of ≥ type and the third constraint is of ≤ type.
Range of feasibility for first constraint: 25-25 up to 25+∞
:(0- ∞)
Range of feasibility for the third constraint: 5-5 up to 5+∞
:(0-∞)
a) A decrease of 10 units is with in the allowable decrease (i.e10 ≤ 25). The shadow
price of the constraint is -20. Therefore, if the constraint decreases (i.e relaxed) by
10 units, the cost will decrease by 20×10=$200. So the change will have a
favorable impact on the objective function.
b) Yes! As the shadow price of the constraint shows, each unit decrease in the
constraint will decrease the total cost by $20. Therefore, if we could decrease it by
paying only $15 per unit, it is worthwhile to do so. In short, any expenditure less
than $20 per unit will result in a net saving in cost.
c) X3 is a non basic variable. To come into the solution as a basic variable, its
objective function coefficient should decrease by at least 8, its cj-z value.
d) X1 is a basic variable in the final table. Thus, to know the effect of its cost
coefficient we should first calculate its range of optimality as follows:
cj-z (A) 0 0 8 20 0
X1 (B) 1 0 1 -1 0
A/B 0 ∞ 8↑ -20↓ ∞
Key: ↑= Allowable increase
↓ =Allowable decrease
Range of optimality: 20-20 upto 20+8
: (0-28)
The cost coefficient of X1 can increase upto $28 without causing any change in the
optimal value of the decision variables.
Since $5 is with in the allowable increase, it will not have any effect on the quantities
of the decision variables (i.e X1 =25, X2 =0, X3 =0). But the value of the objective
function will increase by 5×25=$75
46
1. Maximisation case can be turned into minimisation and vice versa
for ease of calculations, as for every primal, there exists a dual.
2. The optimal solution for the dual exists only where there exists an
optimal solution to its primal.
3. The dual of the dual is the primal.
4. The dual variables may assume negative values.
5. The value of the objective function of the optimal solution in both
the problems is the same.
We also need to note that if any of the in equation in the above primal
problem is of the type >, then it becomes necessary to change it as < by
multiplying it by -1 on both the sides. The inequality signs in all the
constraints should be of the same type before proceeding for its dual.
47
2.4.3. Dual when Primal Problem is in Mixed Form:
Mixed Form means that the constraints inequalities are of the type >, = <
type. For such case we need to consider theorem 2 “if the i th primal
constraint is an equality, the i th dual variable will be unrestricted in
sign.”
Example
Write a dual for a given primal.
Primal is Max. Z = 30x1+ 20x2
Subject to, 2x1,+ 3x2 < 45
4x1 + 5x2 < 85
x1, x2 > 0
48
Solution:
Taking y1, y2 as new variables for two constraints.
In Dual problem, it would be
Min. Z= 45y1 + 85y2
Subject to, 2y1 + 4y2 < 30
3y1 + 5y2 > 20
and y1, y2 > 0 .
In case, inequalities are not in the right direction, they should be
converted so. Like in a minimization problem, if the inequality is 2x 1 - x2
< 6, it should be changed to - 2x1 + x2 > -6 and problem is solved in the
normal manner. In Dual, the quantities become the objective function
and objective function gets into the constraints.
Exercise
Give the dual of the LP problem
Minimize Z= 2x1 + 3x2+ 4x3
s/t 2x1+ 3x2 + 5x3 > 2
3x1 + x2 + 7x3 = 3
x1+ 4x2 + 6x3 < 5
Where x1, x2, > 0 and x3 is unrestricted
Solution:
Since the variable x3 is unrestricted in sign, the given LP problem can be
transformed into standard primal form by substituting x 3 = x3’-x3”, where
x3’> 0, x3” > 0. Therefore standard primal problem becomes:
49
Example: Find the dual form of the following problem (“the microcomputer problem,
see page 37)
Maximize Z: 60X1 + 50X2
Subject to:
4X1+ 10X2 100
2X1 + X2 22
3X1 + 3X2 39
X1, X2, X3 0
Solution
10y1 + y2 +3y3 50
y1, y2, y3 0
Final tableau of primal solution to the micro computer problem:
Basics cj 60 50 0 0 0 Qty.
X1 x2 S1 S2 S3
s1 0 0 0 1 6 -16/3 24
X1 60 1 0 0 1 -1/3 9
X2 50 0 1 0 -1 2/3 4
z 60 50 0 10 40/3 740
y2 22 -6 1 0 -1 1 1 -1 10
Z 76 22 39 -9 -4 9 4 740
50
columns of the dual, which equate to slack equals 24 and the other two are zeros. Under
the dual’s slack columns, we can read the values of the primal decision variables. In
essence, the variables of the primal’s problem become the constraints of the dual problem
and vice versa.
The dual variables are termed as shadow prices of the constraints. These
can be named as marginal values or the opportunity costs of primal
resources. Hence, there is one dual variable for every constraint in the
primal and the change in the right hand side is proportional change in
the objective function.
Because of the same reason of one dual variable for every constraint,
the dual being non-zero, indicates full utilization of that resource. The
use of dual concept can be done in making decisions regarding change
in resources such as addition, deletion or trade-off of resources. Hence a
minimisation problem can also be solved by solving its dual as a
maximisation problem. Let us take the microcomputer problem and
illustrate the use of dual in evaluating:
a) The marginal value of resources ( constraints)
b) The potential impact of a new product
a) The marginal value of resources
In the micro computer problem considered, the variables Y 1, Y2 and Y3 are the marginal
values of scarce resources: assembly time, inspection time and storage space. The dual is
a minimization problem because the competitor wants to minimize the use of scarce
resources since the computer firm would base its charges on the amount of resources
required.
If our firm realistically considers the competitor’s offer to hire out facilities, the amount
of scarce resources that will be foregone must produce a return to the firm that is at least
equal to the foregone profit. Hence, the value of four assembly hours plus two inspection
hours plus three cubic feet of storage space that is given up when one unit of model -I is
scarified must be greater than or equal to $ 60. That is what is shown by the first
constraint of the dual. A similar interpretation is possible for the second constraint in the
dual.
The optimal dual solution always yields the same value of the objective function as the
primal optimal. In this case, it is 740. The implication is that the imputed value of the
resources that are required for the optimal solution equals the amount of profit that the
optimal solution would produce.
b)Adding a new product
For example, suppose the micro computer firm is considering a third mode that will yield
a profit of $70 per unit and this will require resources of 8 hours of assembly time, 4
hours of inspection time and 5 cubic feet of storage space per unit, what is the impact on
the current solution?
New constraint in the dual: 8y1+ 4y2+5y3 . The marginal values of resources required
for adding one units of the third model = 8(0) + 4 (10) + 5 (40/3) = $106.67. Thus, the
51
manager will not add the third model because its cost is greater than its profit
contribution ($106.67 .
UNIT SUMMARY
52
Exercise 2.2
53
1. In the microcomputer problem, what will be the effect of a 3-hour increase in
inspection time on the on the value of the objective function?
2. In the microcomputer problem, what is the effect of a 5 hour decrease in
inspection time on the objective function value?
3. Given the following LP problem and final tableaus for a simplex solution:
Max Z: 11 X1+ 10 X2 + 14 X3
Subject to:
4X2 – X3≤0
5X1+ 2X2+5X3≤72
X1≤ 13
X1 , X2 ,X3≥ 0
Basics Cj 11 10 14 0 0 0 Qty.
X1 X2 X3 S1 S2 S3
S3 0 1 0 0 0 0 1 13
Z 15 10 14 1 3 0 2/6
C-Z -4 0 0 -1 -3 0
54
2X1+ 3X2 + 4X3 72
X1 + 3X2 +4X3 18
X1 , X2, X3 0
Final tableau
Basics cj 10 6 5 0 0 0 Qty.
X1 X2 X3 S1 S2 S3
55
References
56
UNIT THREE
TRANSPORTATION AND ASSIGNMENT PROBLEMS
Unit Introduction
Dear distance learner! In this unit two related OR models-transportation and assignment-
will be discussed. They can be considered as special cases of linear programming as they
can be solved with the general LP approach. However, it will be more time consuming
and costly to do so. Consequently specialized algorithms which fit to the unique
structures of transportation and assignment problems have been developed. Thus this
chapter discusses transportation and assignment algorithms, respectively.
Unit Objectives
Dear student! This unit is aimed at enabling you to:
Understand the meaning of transportation and assignment problems
Develop a general linear programming model for transportation and assignment
problems
Solve transportation and assignment problems by using transportation and
assignment algorithms
INTRODUCTION
A scooter production company produces scooters at the units situated at various places
(called origins) and supplies them to the places where the depot (called destination) are
situated. Here the availability as well as requirements of the various depots are finite and
constitute the limited resources. This type of problem is known as distribution or
transportation problem in which the key idea is to minimize the cost or the time of
transportation. In previous lessons we have considered a number of specific linear
programming problems. Transportation problems are also linear programming problems
and can be solved by simplex method but because of practical significance the
transportation problems are of special interest and it is tedious to solve them through
simplex method. Is there any alternative method to solve such problems?
SECTION OBJECTIVES
After completion of this section you will be able to:
1. Develop linear programming model for transportation problems
2. Find initial solution for transportation problems by:
i. North-West corner rule;
ii. Least-cost (Intuitive) method; and
3. Test the initial solution for optimality by:
i. Stepping-stone method
ii. Modified distribution method
The transportation model is a special class of linear programming that deals with
shipping a commodity from sources (e.g factories) to destinations (e.g warehouses). The
objective is to determine the transportation schedule that minimizes the total
transportation cost while satisfying supply and demand limits.
SECTION OVERVIEW
57
3.1 Assumptions of transportation model
3.2 Developing LPM for transportation problems
3.3 Solving transportation problems
3.3.1 Methods of finding initial solution
3.3.1 Methods of testing the initial solution for optimality
3.4 Special cases in transportation problems
3.4.1 Unbalanced problems
3.4.2 Multiple solutions in transportation
3.4.3 Degeneracy and transportation
3.4.4 Restricted transportation routes
3.4.5 Maximization problems
Destination
58
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3* 2 5 3000
The company would like to determine how much product should be shipped from each
source to each destination in such a way that the demand of each destination is satisfied
with the available production at each source and the overall transportation cost is
minimized. Note that total demand and total supply are equal: 9500 units.
A general linear programming approach can be used to solve the above problem. Let us
see how the LP model can be developed for the problem. We will use double-subscripted
decision variables, with x11 denoting the number of units shipped from origin 1 (Mekele)
to destination 1 (Addis Ababa), x12 denoting the number of units shipped from origin
1(Mekele) to destination 2 (Gondar), and so on. In general the decision variables for a
transportation problem having m origins and n destinations are written as follows:
Since the objective of the transportation problem is to minimize the total transportation
cost, we can use the transportation cost data provided in the above table to develop the
following cost expressions:
Transportation cost for units shipped from Mekele = 3x11 + 2x12 +5x13.
Transportation cost for units shipped from Hawasa = x21 + 3x22 +4x23
Transportation cost for units shipped from Gambela=4x31 + 5x32 +6x33.
The sum of the above cost expressions provides the objective function showing the total
transportation cost for ABC Company. Accordingly, the objective function is:
Min Z= 3x11 + 2x12 +5x13 + x21 + 3x22 +4x23 + 4x31 + 5x32 + 6x33
Constraints: Transportation problems have two major categories of constraints- supply
and demand. Let us first consider supply constraints. The capacity at Mekele plant is
3000 units. Since the number of units shipped from the Mekele plant is expressed as x 11 +
x12 +x13, the supply constraint for Mekele plant is:
59
x11 + x12 +x13 = 3000 Mekele supply
Similarly, the supply constraints of the Hawasa and Gambela plants can be written as:
x21 + x22 + x23 = 4000 Hawasa supply
x31 + x32 +x33 = 2500 Gambela supply
The same approach is used to develop the demand constraints. The demand at Addis
Ababa distribution center is 4500 units. This demand is satisfied with the goods shipped
from Mekele (x11 ), Hawasa (x21 ), and Gambela (x31 ) . Therefore the demand constraint
for Addis Ababa distribution center is:
Similarly, the demand constraints of Gondar and Jijiga distribution centers are:
Combining the objective function and constraints into one model results in the following
9-variable, 6-constraint linear programming model for the ABC transportation problem:
Min Z= 3x11 + 2x12 +5x13 + x21 + 3x22 +4x23 + 4x31 + 5x32 + 6x33
Subject to:
x11 + x12 +x13 = 3000
x21 + x22 + x23 = 4000
x31 + x32 +x33 = 2500
x11 + x21 + x31 = 4500
x12 + x22 + x32 = 3500
x13 + x23 + x33 = 1500
xij ≥0, for i= 1,2,3 and j= 1,2,3
Dear learner! Once the LPM is developed as above, it can be solved with the simplex
method we discussed in the previous chapter. However, as you can imagine, solving the
above model, with out the help of a computer, will be very cumbersome and time
consuming to say the least. What is more striking is the fact that the transportation
problem we are dealing with is relatively small in comparison to most of the
transportation problems you will face in the real business world. You may be wondering
“So how can we solve a large-size transportation problem involving, say 10 warehouses
(sources) and 15 retail shops (destinations), with the simplex approach?” Well, don’t
worry about that! What is expected of you (a human decision maker) is just to develop
the linear programming model using the approach we saw above. Thanks to technology,
highly efficient computer spreadsheets, like Microsoft Excel, which are widely available
these days, can be used to solve the LPM. We will not, however, discuss them here. We
suggest that you refer to reference books attached at the end of this chapter to familiarise
yourself with the use of MS Excel in solving LPM’s. By the way a 10-source, 15-
destination transportation problem will have 150 variables and 25 constraints!
In the next section, we will discuss the transportation algorithm which will enable us to
solve ABC Company’s transportation problem more easily than the general LPM
approach.
60
3.1.2 The Transportation Algorithm
Dear student! What do you think is an algorithm?
________________________________________________________________________
________________________________________________________________________
_______________________________________________________________
Well, in simple terms an algorithm is a series of steps which, by applying the same
mathematical rules, gradually lead to the final solution of a problem. For instance, the
simplex method discussed in the previous chapter is an algorithm. The same rules of
performing the row operations, of determining the entering variable and the leaving
variable are applied to subsequent simplex tables. We start from the initial solution (first
table) and gradually progress to the optimal solution (final table) by repetitively applying
the rules to consecutive simplex tables.
The transportation algorithm is similar to the simplex algorithm in that it starts from an
initial solution, evaluates the initial solution for optimality and , if the initial solution is
not optimal, progresses to the next solution until optimality condition is satisfied.
a) Northwest-corner method
The northwest-corner method starts at the northwest-corner cell (variable x11 , Mekele-
Addis Ababa route). Follow the following steps:
Step 1. Allocate as many units as possible to the selected cell. The allocated number of
units will be equal to the lower of the row supply and column demand since we cannot
assign more than what is demanded or what can be supplied.
Accordingly, 3000 units is assigned to cell11 (Mekele-A/Ababa cell) because 3000 is the
lower of the row supply (i.e 3000 units from Mekele) and the column demand (4500 units
of the A/Ababa distribution center). Step 1 results in the following changes in the
original table.
Destination
61
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
Step 2. Adjust the associated amounts of supply and demand by subtracting the allocated
amount (i.e 3000 units). Now, after the allocation, A/Ababa’s demand will be left with
1500 units (i.e 4500-3000) and the Mekele’s supply capacity will be zero (i.e 3000-3000).
Substitute the original supply and demand amounts by crossing out and replacing with
the adjusted amounts. Thus 4500 is crossed out (cancelled) and replaced with 1500.
Similarly 3000 is crossed out, the new supply amount will be 0, thus you don’t need to
write it. The following change is made as a result of step 2:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
Step 3: If exactly one supply and demand amount remains nonzero, make the allocation
to the cell at the intersection of the remaining supply and demand and finish. Otherwise,
move to the cell to the right ( if there is supply) or below (if there is demand) and repeat
step 1 and step 2 until exactly one nonzero supply or demand remains.
In our problem, there are still 3 nonzero demand amounts (the 3 distribution centers) and
2 nonzero supply amounts (Hawasa and Gambela). Therefore, we have to make the next
allocation to the cell below cell11, that is to the nonzero demand direction. Accordingly,
the next allocation will be to cell21 (Hawasa-A/Ababa route). Again, we adjust the
supply and demand amounts. This results in the following changes:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
62
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
1500 2500
Now the A/Ababa demand is zero, and the Hawasa supply remains 2500 units.
Thnext allocation will be made to the right of cell21, that is to cell22, resulting in the
following changes:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
1500 2500 2500
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
1500 2500 2500
Finally, exactly one nonzero demand and supply amount remains (i.e the Jijiga
demand and the Gambela supply). Thus we make allocation to the cell at the
63
intersection of the remaining supply and demand amounts (cell33 ). Since both
supply and demand amounts are 1500 units, we can allocate 1500 units and finish.
The following table is the northwest-corner initial solution. The direction of the
arrows indicate the summary of the steps we followed.
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
1500 2500 2500
Initial total cost: To find the total transportation cost, multiply transportation cost per
unit and the number of units in occupied cells, and add the results of all products.
Step 1: find the cell with the smallest shipping cost and assign as many units as possible. The
number of units that can be assigned is the lower of the row supply and column demand
amounts. If there are many (more than one) cells with the same lowest cost, first assign to the
cell in which the largest number of units can be assigned, then to the cell where the next
largest number of units can be made and so on.
In our problem, the minimum transportation cost per unit is Br.1, and the cell with that cost
is cell21 (i.e Hawasa-A/Ababa route).
Step 2. As in the northwest corner method adjust the associated amounts of supply and
demand by subtracting the allocated amount (i.e 4000 units).
The above two steps result in the following changes on the transportation table:
64
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
Step 3: Then choose the cell with the lowest cost from the cells that do not lie in a zero
supply row or demand column with the minimum shipping cost and repeat step 1 and step 2.
Continue until there is only one cell that can be chosen. In other words, if exactly one supply
and demand amount remains nonzero, make the allocation to the cell at the intersection
of the remaining supply and demand and finish.
Now, since there are more than one nonzero demand and supply amounts left, we
should identify the next smallest cost. It is Br.2 (at cell12 ). 3000 units can be allocated,
resulting in the following changes after adjustment:
Destination
Origin Addis Gondar Jijiga Supply
Ababa (1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
4000
Gambela (3) 3 5 6 2500
The next smallest cost is Br.3 (at cell11 , cell22 , and cell31 ). However, we cannot
allocate to cell11 and cell22 .
Dear student! Why do you think we cannot make the allocation to those cells?
____________________________________________________________________
______________________________________________________________
Allocation cannot be made to cell11 and cell22 because the supply amounts (i.e the
Mekele and Hawasa supplies) are zero, thus there is no supply. Therefore, we have
65
to allocate to cell31. 500 units can be allocated, resulting in the following changes
after adjustment:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
4000
Gambela (3) 3 5 6 2500
500 2000
Demand 4500 3500 1500 9500
500 500
The next smallest cost is Br.4 (at cell23). However, we cannot allocate to the cell
since there is no supply.
Birr 5 is the next smallest cost. There are two candidate cells, cell13 and cell32.
However we cannot allocate to cell13 as there is no supply left. Therefore we
make the allocation to cell32 , resulting in the following changes after
adjustments:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
4000
Gambela (3) 3 5 6 2500
500 500 2000
1500
Demand 4500 3500 1500 9500
500 500
Finally, exactly one nonzero demand and supply amount remains (i.e the Jijiga
demand and the Gambela supply). Thus, 1500 units is allocated to cell33 and the
initial solution is as follows:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
66
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
4000
Gambela (3) 3 5 6 2500
500 500 1500 2000
1500
Demand 4500 3500 1500 9500
500 500
Dear distance learner! As you can note from the results of the initial solutions found
using the two methods, the initial total cost found using the least-cost method is lower
than the one found using the northwest-corner method. Thus the least-cost method
generally provides a lower cost which is a better starting solution. However, this might
not be the case in all transportation problems.
Note that in our example, the number of occupied cells =m+n-1 (i.e 5=3+3-1).
Therefore, it is possible to evaluate both the northwest-corner and stepping-stone initial
solutions.
We illustrate the two methods by taking the northwest-corner initial solution of ABC
Company’s transportation problem. The following table shows the northwest-corner
initial solution we found above.
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
67
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 3 4 4000
1500 2500
Gambela (3) 3 5 6 2500
1000 1500
Demand 4500 3500 1500 9500
The stepping-stone method gets its name from the analogy that you
need a stepping-stone to put your feet on when you cross a
swampy area. Similarly, when we evaluate each empty cell by
using this method we will use occupied cells as stepping-stones.
2. Trace a closed path (closed loop) that starts and ends in the empty cell being
evaluated. You can follow either clock-wise or anti-clock wise direction to
form the path.
3. Place alternating ‘+’s and ‘-’s on this path. Start by placing a plus (+) sign on
the empty cell being evaluated. Place plus and minus signs only on
occupied cells except the empty cell being evaluated. The ‘+’s indicate that
certain amount of goods will be added to that cell. ‘-’s indicate that certain
units will be subtracted from that occupied cell.
N.B. There must be equal number of ‘+’s and ‘-’s in every row and
column of the transportation table. This is to ensure that each row supply
and column demand amount remains intact (unaffected).
68
a product transferred to that cell. Positive cell evaluation
results are unfavorable.
5. Repeat step 1-step 4 for each empty cell in the transportation tableau. If all
cell evaluation results are positive, stop; optimality condition is
satisfied. Otherwise proceed to step 6. Optimal solution in a transportation
problem is reached when there is no any further improvement potential.
That means, the minimum-cost transportation schedule is found.
6. Reallocate to the cell with the largest improvement potential: To make the
reallocation, first identify empty cells with net negative cell evaluation
result and compare their cell evaluation value. The cell with the largest
negative net cell evaluation result is said to have the largest improvement
potential. That is, reallocation to that cell will lead to the largest reduction in
the total transportation cost.
The number of units that can be reallocated is equal to the smallest of the
number of units in the occupied cells which are on the corners of the closed
path used to evaluate the cell with the largest improvement potential. If
n=the number of units that can be reallocated, make the following changes on
cells at corners of the closed path of the current table and draw the next table:
i. Add n to cells with ‘+’ sign
ii. Subtract n from those cells with ‘-‘sign
iii. Leave other cells as they are.
Let us apply the above steps in our example and evaluate the 4 empty cells one
by one:
1) cell12 (C12 In short) : We start by placing a ‘+’ sign at C12. Since we have
one ‘+’ sign in the first row, there must be one ‘_’ sign in the same row. The
minus sign can be placed only on occupied cell in the row, cell11. The next
plus sign should be placed at c21 since c21 is the only other occupied cell
in the first row (other than c11). Finally the minus sign should be placed at
C22 to form the closed path.
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
69
Mekele (1) _ 3 + 2 5 3000
3000
Hawasa (2) + 1 _ 3 4 4000
1500 2500
Gambela (3) 3 5 6 2500
1000 1500
Demand 4500 3500 1500 9500
2 3
1 3
Note that: Except c21 all plus and minus signs are placed on occupied
cells
: There are equal number of plus and minus signs in all rows and
columns. That is: Row 1 (1 plus, 1 minus), Row 2 (1 plus, 1 minus), Row 3
(0 plus, 0 minus). Column 1 (1 plus 1 minus), Column 2 (1 plus, 1 minus),
Column 3 ( 0 plus, 0 minus)
2) Cell13:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) _ 3 2 + 5 3000
3000
Hawasa (2) + 1 _ 3 4 4000
1500 2500
Gambela (3) 3 + 5 _ 6 2500
1000 1500
Demand 4500 3500 1500 9500
5 6
5 3
1 3
70
3) Cell23 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) 1 _ 3 + 4 4000
1500 2500
Gambela (3) 3 + 5 _ 6 2500
1000 1500
Demand 4500 3500 1500 9500
4 6
5 3
4) Cell31 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 2 5 3000
3000
Hawasa (2) _ 1 + 3 4 4000
1500 2500
Gambela (3) + 3 _ 5 6 2500
1000 1500
Demand 4500 3500 1500 9500
71
Cell evaluation (c31 ) + -
3 5
3 1
To summarize, the cell evaluation results of the four empty cells- C12, C13, C23,
C31- are -3, -1, -1, and 0; respectively. This means each unit of the product
that is reallocated to the four cells will decrease the initial total cost (i.e Br.
32,000) by Br. 3, 1,1,and Br.0, respectively. Since our objective is to
minimize the total transportation cost, C12 is the most favorable one. It
has the largest improvement potential.
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele 3 2 5 3000
(1) 500 2500
Hawasa 1 3 4 4000
(2) 4000
Gambela 3 5 6 2500
(3) 1000 1500
Demand 4500 3500 1500 9500
72
But we did not yet know whether the solution we have found is optimal. The new
solution should be evaluated again. So we should evaluate each empty cell in the table-
Cell13, Cell22, Cell23, and Cell31- one by one.
1) Cell13 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) 3 _ 2 + 5 3000
500 2500
Hawasa (2) 1 3 4 4000
4000
Gambela (3) 3 + 5 _ 6 2500
1000 1500
Demand 4500 3500 1500 9500
5 2
5 6
2) Cell22 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) + 3 _ 2 5 3000
500 2500
Hawasa (2) _ 1 +3 4 4000
4000
Gambela (3) 3 5 6 2500
1000 1500
Demand 4500 3500 1500 9500
73
Cell evaluation (c22 ) + -
3 2
3 1
3) Cell23 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) + 3 _ 2 5 3000
500 2500
Hawasa (2) _ 1 3 +4 4000
4000
Gambela (3) 3 + 5 _ 6 2500
1000 1500
Demand 4500 3500 1500 9500
4 6
5 2
3 1
4) Cell31 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele (1) _ 3 + 2 5 3000
500 2500
Hawasa (2) 1 3 4 4000
4000
Gambela (3) + 3 _ 5 6 2500
1000 1500
Demand 4500 3500 1500 9500
74
Cell evaluation (c31 ) + -
3 5
2 3
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele 3 2 5 3000
(1) 3000
Hawasa 1 3 4 4000
(2) 4000
Gambela 3 5 6 2500
(3) 500 500 1500
Demand 4500 3500 1500 9500
1) Cell11:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele + 3 _ 2 5 3000
(1) 3000
Hawasa 1 3 4 4000
(2) 4000
Gambela _ 3 + 5 6 2500
(3) 500 500 1500
Demand 4500 3500 1500 9500
75
Cell evaluation (c11 ) + -
5 2
3 3
2) Cell13 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele 3 _ 2 + 5 3000
(1) 3000
Hawasa 1 3 4 4000
(2) 4000
Gambela 3 + 5 _ 6 2500
(3) 500 500 1500
Demand 4500 3500 1500 9500
5 6
5 2
3) Cell22 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele 3 2 5 3000
(1) 3000
Hawasa _ 1 + 3 4 4000
(2) 4000
Gambela + 3 _ 5 6 2500
(3) 500 500 1500
Demand 4500 3500 1500 9500
76
Cell evaluation (c11 ) + -
3 5
3 1
4) Cell23 :
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele 3 2 5 3000
(1) 3000
Hawasa _ 1 3 + 4 4000
(2) 4000
Gambela + 3 5 _ 6 2500
(3) 500 500 1500
Demand 4500 3500 1500 9500
4 6
3 1
Dear distance learner! As you can observe the optimal solution (Table III) and
the least-cost initial solution are the same. But this occurs just by chance in
our specific example. You should not assume that the least-cost initial
solution will always be the same to the final solution. Infact, the two are
different in most problems.
The MODI method requires that we define an index ui for each row of the tableau and an
index vj for each column of the tableau. Computing these row and column indices
77
requires that the cost coefficient for each occupied cell equal ui + vj . Thus, if Cij the cost
per unit from origin i to destination j, we have Cij = ui + vj for each occupied cell.
Steps in MODI method:
(i). Develop an initial feasible solution using one of the two methods- NWC or Least-cost
(ii). Setting the row index of the first row equal to zero: ul= 0. Compute successive ui
and vj values for each row and column such that ui + vj = Cij for each occupied cell.
(iii). Compute the net cell evaluation result (eij ) as cij – ui – vj for each empty cell. eij is
called net evaluation index.
(iv). Allocate as much as possible to the empty cell that has the largest improvement
potential. Allocate according to the stepping-stone path for the selected cell and develop
the next table.
(v). Repeat steps (ii) to (iv) in successive tables until all cell evaluation results (eij ) are
greater than or equal to zero; that is until there is no further improvement potential.
Let us return to the initial solution for ABC Company which we found using the
northwest-corner method and use MODI to evaluate it for further improvement potential.
The table, along with row and column indices, is repeated below for easy reference:
Step ii. Calculating row and column indices (ui and vj):
Requiring that ui + vj = Cij for all occupied cells in the initial solution leads to a system of
5 equations and 6 indices, or variables:
Mekele-A/Ababa u1 + v1 = 3
Hawasa-A/Ababa u2 + v1 = 1
Hawasa-Gondar u2 + v2 = 3
Gambela-Gondar u3 + v2 = 5
Gambela-Jijiga u3 + v3 = 6
With one more index (variable) available than equation in this system, we can freely
78
choose a value for one of the indices and then solve for others. We will always choose u1
= 0 and then solve for the values of the other indices. Setting u1 = 0, we obtain
0 + v1 = 3…v1=3
u2 + 3 = 1… u2 = -2
-2 + v2 = 3… v2 = 5
u3 + 5 = 5... u3 =0
0 + v3 = 6… v3 =6
The above row and column indices are indicated in the table.
Step iii. Calculating net evaluation index (eij )
Dear student! Before we continue further, have you observed that the net evaluation
results we found above using MODI method for each empty cell are exactly the same to
those we found using the stepping-stone method? Go back to page 17 and compare the
results. When we are evaluating one table using the stepping-stone method and MODI
method the net evaluation results will ALWAYS be the same for each empty cell evaluated.
Cell12 has the highest improvement potential. Therefore, we have to reallocate to Cell12 .
How many units should be reallocated to it? We use the stepping-stone method, only for
Cell12, to determine the number of units that can be reallocated. The path is indicated in the
above table. 2500 units (i.e the lower of 2500 and 3000) can be reallocated, resulting in the
next table after adjustments.
Exercise: Calculate row and column indices. Check your answer in the following table.
79
Hawasa 1 3 4 4000 -2
(2) 4000
Gambela + 3 _ 5 6 2500 3
(3) 1000 1500
Demand 4500 3500 1500 9500 -
Column 3 2 3 - -
indices (vj )
Origin Addis Ababa Gondar (2) Jijiga (3) Supply Row indices
(1) (ui )
Mekele (1) 3 2 5 3000 0
3000
Hawasa(2) 1 3 4 4000 1
4000
Gambela(3) 3 5 6 2500 3
500 500 1500
Demand 4500 3500 1500 9500 -
Column indices(vj) 0 2 3 - -
80
Table III. ABC Company’s NWC initial Solution -MODI Evaluation, optimum solution
If the total supply is not equal to the total demand then the problem is known as
unbalanced transportation problem. If the total supply is more than the total demand,
we introduce an additional column, called dummy column, which will indicate the
surplus supply with transportation cost zero.
81
Similarly, if the total demand is more than the total supply, an additional row, called
dummy row, which represents unsatisfied demand with transportation cost zero, is
introduced in the table.
After introducing a dummy row or column, the problem is solved just like other
‘normal’ transportation problems.
To
Warehouse Warehouse Warehouse Supply
From I II III
Plant I 7 8 10 50
Plant II 9 7 8 60
Demand 70 30 40
Required:
a.) Show that the transportation problem is unbalanced and draw a transportation tableau
for the corresponding balanced problem.
b.) Find the initial solution using northwest-corner (NWC) method and, by using MODI
method of evaluation, find the optimal solution.
Solution
Total demand ≠ Total supply. Therefore the problem is unbalanced. The problem
should be converted into a balanced one before solving it. Since demand is greater
than supply, dummy row (i.e dummy plant) should be added to the table to balance
the problem. The dummy row’s amount=140-110=30 units. The balanced
transportation table should be as follows:
Table I
To
Warehouse Warehouse Warehouse Supply
From I II III
Plant I 7 8 10 50
82
Plant II 9 7 8 60
Dummy row 0 0 0 30
Demand 70 30 40 140
Now the problem is balanced since total demand (140)=total supply (140).
Note that transportation costs in the dummy row are zero(0) because there
will not be an actual shipment of goods from the dummy row. The purpose of
the dummy row here is to balance the problem and know the demand of
which warehouse will not be partially or completely satisfied at the optimal
solution..
To
Warehouse I Warehouse II Warehouse III Supply
From
Plant I 7 50 8 10 50
9 7 8 60 40 10
Plant II
20 30 10
0
Dummy row 0 0 30
30
70 20
Demand 30 40 30 140
=Birr 820
i. Cell12
To
Warehouse I Warehouse II Warehouse III Supply
From
Plant I _ 7 50 + 8 10 50
83
+ 9 _ 7 8 60 40 10
Plant II
20 30 10
0
Dummy row 0 0 30
30
70 20
Demand 30 40 30 140
8 7
9 7
ii. Cell13
To
Warehouse I Warehouse II Warehouse III Supply
From
Plant I _ 7 50 8 + 10 50
+ 9 7 _ 8 60 40 10
Plant II
20 30 10
0
Dummy row 0 0 30
30
70 20
Demand 30 40 30 140
10 8
9 7
iii. Cell31
To
Warehouse I Warehouse II Warehouse III Supply
From
84
Plant I 7 50 8 10 50
_ 9 7 +8 60 40 10
Plant II
20 30 10
_ 0
Dummy row + 0 0 30
30
70 20
Demand 30 40 30 140
0 0
8 9
iv. Cell32
To
Warehouse I Warehouse II Warehouse III Supply
From
Plant I 7 50 8 10 50
9 _ 7 +8 60 40 10
Plant II
20 30 10
_0
Dummy row 0 + 0 30
30
70 20
Demand 30 40 30 140
0 0
8 7
Cell31 is the only cell with an improvement potential. 20 units (the lower of 20 and
30) can be reallocated, resulting in the following table after reallocation:
85
To
Warehouse I Warehouse II Warehouse III Supply
From
7
Plant I 8 10 50
50
9 7 8
Plant II 60
30 30
0 0
Dummy row 0 30
20 10
Demand 70 30 40 140
i. Cell12
To
Warehouse I Warehouse II Warehouse III Supply
From
_ 7
Plant I + 8 10 50
50
9 _ 7 + 8
Plant II 60
30 30
+ 0 _ 0
Dummy row 0 30
20 10
Demand 70 30 40 140
86
Optimal Cost=7*50+7*30+8*30+0*20+0*30
=Birr 800
8 7
8 0
0 7
ii. Cell13
To
Warehouse Warehouse Warehouse Supply
From I II III
_ 7
Plant I 8 +10 50
50
9 7 8
Plant II 60
30 30
+ 0 _ 0
Dummy row 0 30
20 10
Demand 70 30 40 140
10 0
0 7
iii. Cell21
To
Warehouse I Warehouse II Warehouse III Supply
From
7
Plant I 8 10 50
50
87
+ 9 7 _ 8
Plant II 60
30 30
_ 0 + 0
Dummy row 0 30
20 10
Demand 70 30 40 140
9 8
0 0
iv. Cell34
To
Warehouse Warehouse Warehouse Supply
From I II III
7
Plant I 8 10 50
50
9 _ 7 + 8
Plant II 60
30 30
0 _ 0
Dummy row + 0 30
20 10
Demand 70 30 40 140
0 0
8 7
88
3.4.2 Multiple Optimum Solutions
This case occurs when there are more than one (multiple) optimal solutions. This
would be indicated when at one or more unoccupied (empty) cells have zero value
for the net evaluation result in the optimum solution.
Thus a reallocation to cell having a net cost change equal to zero will have no effect
on transportation cost. This reallocation will provide another solution with same
transportation cost, but the routes employed will be different from those for the
original optimal solution. This is important because they provide management with
added flexibility in decision making.
Let us take the optimum solution table and make reallocation to Cell23 to see the
effect. The required stepping-stone path is indicated in the table below:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele 3 2 5 3000
(1) 3000
Hawasa _ 1 3 + 4 4000
(2) 4000
Gambela + 3 5 _ 6 2500
(3) 500 500 1500
Demand 4500 3500 1500 9500
As you can see from the table, 1500 units (i.e the lower of 1500 and 4000) can be
reallocated. After the reallocation, the table will look as follows:
Destination
Origin Addis Ababa Gondar Jijiga Supply
(1) (2) (3)
Mekele 3 2 5 3000
(1) 3000
Hawasa 1 3 4 4000
(2) 2500 1500
Gambela 3 5 6 2500
(3) 2000 500
Demand 4500 3500 1500 9500
89
Now, Total transportation cost= 2*3000+1*2500+4*1500+3*2000+5*500
=Br. 23,000
The total cost is after the reallocation is the same, indicating that the problem is
optimal.
Exercise: Show that reallocation to Cell22 will not result in any change in the total
transportation cost.
After placing Δ in an appropriate cell, continue the evaluation just like other
‘normal’ transportation problems. However, adding or subtracting Δ from an
occupied cell will not change the number of units in that cell. When Δ is
added to an empty cell, the empty cell becomes an occupied cell; do not
leave the empty cell as it is!
To Supply (in
Town A Town B Town C tons)
From
90
Factory I 5 4 12 500
Factory II 8 6 10 600
Required:
Find the optimum transportation schedule by using NWC method for initial solution and
MODI for evaluation purpose. Assume that unit transportation costs are in Birr per ton of
a product.
Solution
To Supply (in
Town A Town B Town C tons) Row index
From (Ui)
5
Factory I 4 200 12 500 200 0
300
91
8 6 10
Factory II 250 2
X 250
3 5
Factory III 7 400 ?
400
450 250
Demand (in tons) 300 400 1500 -
Column index 5 4 ? - -
(Vj)
The number of occupied cell is fewer than m+n-1. The number of sources (i.e m)=3; the number
of destinations (i.e n)=3. Thus, m+n-1 is 3+3-1=5. Normally the number of occupied cell should be 5.
But it is only 4 in our case, indicating that the problem is degenerate.
The degeneracy arises because in making our third allocation, 250 units in Cell22 ,
both the supply from Factory II AND the demand of Town B are exhausted
simultaneously, leading to fewer occupied cells.
To avoid the degeneracy, we should place Δ in one of the empty cells. Dear student!
Which of the empty cells do you think is/are the appropriate place(s) for Δ? Well, you
may find the right place through trial-and-error. But there is a better way than trial-and-
error:
First, try to calculate Ui’s and Vj ‘s by using the current occupied cells. Remember our
formula: Cij = ui + vj., where Cij is the cost of occupied cells. By using the three
occupied cells, we can find the following indices:
U1 (which is 0 by default),
V1 (5-0=5)
V2 (4-0=4)
U2 (6-4=2)
We cannot find U3 and V3 currently (indicated by ? in the above table). Now, Δ can be
placed in any one of the empty cells in the column/row containing the question mark (?).
Accordingly, only the empty cell marked X (see the table above) is the wrong place for Δ.
Exercise: Place Δ in any one of the 4 appropriate cells and solve the problem like any
other nondegenerate, ‘normal problem’
To Supply (in
Town A Town B Town C tons)
From
5 4
Factory I 12 500 200
300 200
92
Factory II 8 6 10 250
250
3 7 5
Factory III 400
400
450 250
Demand (in tons) 300 400 1500
Dear learner! Our discussion of transportation problems has so far been based on the
assumption that all routes from sources to destinations can be used. However in the
real world a situation such as road hazards (snow, floods, etc), traffic regulation, road
maintenance, safety problems etc may arise. In such situations it is not possible to
transport goods from certain sources to certain destinations. In this case, the
restricted cell may either be completely crossed out or a very large per unit
transportation cost (M ) is assigned to it. After placing M to the prohibited cell, ignore
that cell from further analysis.
Exercise: Take ABC Company’s transportation problem. But, now assume that it is
not possible to transport the product from Gambela to Addis Ababa directly because
the route is not operational due to road maintenance taking place.
Required: Solve the transportation problem by using least-cost method for initial
solution and stepping method for evaluation. Check your answer below:
Solution
93
Mekele (1) 3 2 5 3000
3000
Note that Addis Ababa’s demand is not fully satisfied (is short of 500 units)
because of the restriction. The 500 units are retained by the Gambela plant.
The problem is degenerate case.
Hawasa 1 3 4 4000
(2) 4000
Gambela M 5 6 2500
(3) 500 1500
Although transportation model is usually used to minimize transportation cost, it can also
be used to get a solution with an objective of maximizing the total value or returns. Since
the criterion of optimality is maximization, the converse of the rule for minimization will
94
be used. The rule is: A solution is optimal if all opportunity costs for the unoccupied cell
are zero or positive.
Once the opportunity table is developed exactly the same methods of finding the initial
solution and evaluation are carried out on the opportunity cost table.
Example: Assume that Trans Ethiopia provides transportation service to three factories-
X, Y and Z- to transport their goods to four dealers spread all over the country. The
production capacities of these factories and the demand of the four dealers are given
below. Also given in the table are the transportation fees (in Br./quintal) Trans charges for
its service.
Factory X 2 3 1 4 3000
Factory Y
5 4 3 4 2000
Factory Z
3 2 1 2 5000
Required: Develop the opportunity cost table for Trans’s problem and find the
northwest-corner initial solution.
Solution
Develop opportunity cost table by minimizing every number in the table from the largest
number (5 in our example). The NWC initial solution is also indicated in the table below.
95
Opportunity Cost table
3 2
Factory X 4 1 3000
3000
Factory Y 0 1 2000
2 1
1000 1000 1000
Factory Z 2 3 4 3
5000 4500
500 2000 2500 2500
4000 1500
Demand (in 2000 2500 10,000
quintals) 1000 500
Exercise: Use MODI method for evaluation purpose and find the minimum
opportunity-cost (i.e maximum revenue) for Trans. Check your answer below
3 2 1
Factory X 4 3000
500 2500
Factory Y 0 2000
2 1
2000
Factory Z 2 3 4 3
5000
2000 1000 2000
4000 1500
Demand(quintals) 2000 2500 10,000
Minimum opportunity cost=Br.18500. To find the maximum revenue, use the original revenue figures, not
the opportunity costs.
96
MaximumRevenue=3*500+4*2500+5*2000+3*2000+2*1000+1*2000
Birr 31,500
Exercise 3-1
1.) Consider the following raw material transportation problem. Transportation costs are
in Birr per quintal of the raw material.
97
To
Plant I Plant II Plant III Supply (in
From quintals)
3 2
Supplier A 3 25
2
Supplier B 4 3 35
3 2 6
Supplier C 20
Demand (in 30 30 20 80
quintals)
b. Solve the problem by using NWC initial solution method and MODI evaluation
method.
To Supply (in
Jimma Nekemte tons)
From
Factory I 40 65 350
Factory II 70 30 400
3.) A cement company has three plants and four warehouses. The supply and
demand (in quintal) and the corresponding transportation costs (Br. per quintal) of
a raw material are given below.
To Supply
I II III IV
From (Tons)
98
A 5 10 4 5 10
B 6 8 7 2 25
C 4 2 5 7 20
Demand (tons) 25 10 15 5
a. Solve the above problem by using northwest-corner for initial solution and MODI
for evaluation purpose.
b. Does the problem have alternate optimal solution? If so, draw the alternate optimal
solution table.
To Seattle Supply
New York Phoenix Miami
From
19 3 7 21 100
Juarez
Seoul 15 21 18 6 300
Telaviv 11 14 15 22 200
Required: Find the optimum assignment schedule by using least-cost method for initial
solution and stepping-stone method for evaluation purpose.
5.) A large manufacturing company is closing three of its existing plants and intends to
transfer some of its more skilled employees to three plants that will remain open. The
number of employees available for transfer from each closing plant is as follows:
99
1 60
2 105
3 70
Total 235
The following number of employees can be accommodated at the tree plants remaininig
open.
A 45
B 90
C 35
Total 170
Each transferable employee will increase output per day at each plant as shown in the
following table. The company wants to transfer employees so as to ensure the maximum
increase in product output.
To
A B C
From
1 5 8 6
2 10 9 12
3 7 6 8
INTRODUCTION
100
_____________________________________________________________________
_____________________________________________________________________
________
SECTION OBJECTIVES
The objective of this section is to enable you:
Understand the structure of assignment problems
Develop linear programming model for assignment problems
Solve assignment problems by the Hungarian method of assignment
Identity and solve special cases of assignment problems
SECTION OVERVIEW
3.5 Structure of Assignment Problems
3.6 General LPM Formulation of Assignment Problems
3.7 Hungarian method of assignment
3.8 Special cases in assignment problems
3.8.1 Unbalanced assignment problems
3.8.2 Multiple solutions in assignment
3.8.3 Restricted Assignment
3.8.4 Maximization Assignment problems
101
3.6 General LPM Formulation of Assignment Problems
Consider m machines to which n jobs are assigned. No machine can either sit idle or
do more than one job. Every pair of machine and assigned job has a rating. This rating
may be cost, processing time, to finish the job. There will be n2 (n-squared) such
combinations of machines and jobs assigned. Thus, the optimization problem is to find
such job- machine combinations that optimize the sum of ratings among all.
Example: Assume that a production manager wants to assign 3 jobs (m=3) to 3 machines (n=3).
Processing costs of each job in each machine is given below. For example, it costs Br.5 to process job
1 in machine 1, Br. 7 to process job 1 in machine 2…Br.16 to process job 3 in machine 3.
Required:
Solution
102
Objective function:
Minimize Z= Min Z= 5x11 + 7x12 +9x13 +14x21 + 10x22 +12x23 + 15x31 + 13x32 + 16x33
Subject to:
x11 + x12 +x13 = 1
x21 + x22 + x23 = 1
x31 + x32 +x33 = 1
x11 + x21 + x31 = 1
x12 + x22 + x32 = 1
x13 + x23 + x33 = 1
xij ≥0, for i= 1,2,3 and j= 1,2,3
Once this problem is developed the problem can be solved with simplex approach, just
like transportation problems. The optimal solution to each decision variable in the above
assignment model will be as follows:
Xij= 0, if the job i is not assigned to machine j
1, if the job i is assigned to machine j
Even if assignment problems can be solved with the general LPM approach, the solution
will be found out using a more convenient algorithm called Hungarian method which
will be illustrated with our example.
Step 1: Row Reduction: Select the smallest value in each row. Subtract this value
from each value in that row and develop a new table. The new table is called row
reduction table.
In our example the smallest numbers in Row 1,Row 2 and Row 3 are 5,10, and
13;respectively.
103
Step 2: Column Reduction: In the row reduction table, select the smallest value in each
column (0, 0, and 2, respectively in our example). Subtract this value from each value in
that column and develop a new table. The new table is called column reduction table.
Step 3: On the column reduction table, draw a minimum number of horizontal and
vertical lines through some of the rows and columns, such that all zero values are
crossed out.
3.1) If the minimum number of lines required to cover all zeros is equal to the
number of rows, stop. Optimality condition is satisfied. Make the optimal assignment
as follows:
i. First count the number of zero’s in each row. If there is a row with only one zero,
encircle that zero and cancel all other zero’s in the encircled zero’s column. If all
assignments cannot be made in this way, proceed to ii
ii. Count the number of zero’s in each column. If there is a column with only one
zero, encircle that zero and cancel all other zero’s in the encircled zero’s row.
N.B: The number of encircled zero’s must be equal to the number of rows/columns,
that is, all jobs must be assigned to all machines by assigning one job to one
machine.
104
3.2) If the minimum number of lines required covering all zeros is not equal to the
number of rows identify the smallest number from the uncovered numbers. If there are
more than one smallest numbers, just select any one of them. Let θ be the smallest
number. Make the following changes on the column reduction table and draw a new
table.
i. Add θ to those numbers at the intersection of two lines (i.e numbers covered by a
vertical and horizontal line)
ii. Subtract θ from the uncovered numbers
iii. Leave numbers that are crossed out by only one line as they are.
Step 4: Repeat Step 3 in subsequent tables until the optimality condition is satisfied.
In our example, the minimum number of lines required to cover all the zero’s in the
column reduction table is 3 which is equal to the number of rows. Therefore, optimal
assignment can be made (indicated by the bold 0’s in the column reduction table above)
as follows:
Table 0
Machines
Jobs 1 2 3 4 Row
minimum
A 1 4 6 3 1
B 9 7 10 9 7
C 4 5 11 7 4
D 8 7 8 5 5
Required: Find the optimum assignment schedule by using the Hungarian method
105
Solution
Machines
Jobs 1 2 3 4
A 0 3 5 2
B 2 0 3 2
C 0 1 7 3
D 3 2 3 0
Column 0 0 3 0
Minimum
Machines
Jobs 1 2 3 4
A 0 3 2 2
B 2 0 0 2
C 0 1 4 3
D 3 2 0 0
θ= 1
The minimum number of lines required to cover all the 4 zero’s in the column
reduction table is 3, which is less than 4 (i.e the number of rows). Thus a
feasible assignment is not possible at this moment.
Apply step 3.2 in the column reduction table. The minimum uncovered
number (θ) is 1. After applying step 3.2 the following table results
106
Table 3
Machines
Jobs 1 2 3 4
A 0 2 1 1
B 3 0xx 0 2
C 0x 0 3 2
D 4 2 0xxx 0
When the 0 in row 3 is cancelled, only 1 zero will be left in the row;
encircle the remaining zero and cancel the 0 at Cell22 (0xx).
When the 0 at Cell22 is cancelled, only 1 zero will be left in the row;
encircle the remaining zero and cancel the 0 at Cell43 (0xxx).
Note that there is only one encircled (bold) zero in each row and each column.
107
4. Maximization Assignment problems
The Hungarian method of assignment requires that the number of columns and rows in
the assignment matrix be equal. However, when the given cost matrix is not a square
matrix, the assignment problem is called an unbalanced problem. In such cases a dummy
row (s) or column (s) are added in the matrix (with zeros as the cost elements) to make it
a square matrix. After making the given cost matrix a square matrix, the Hungarian
method is used to solve the problem.
Programs
Programmer 1 2 3 4
John 4 1.5 2 3
Kumar 2 2 1 3
Required: Find the optimum assignment schedule by using the Hungarian method.
Solution.
Programs
Programmer 1 2 3 4
John 4 1.5 2 3
Kumar 2 2 1 3
108
Tut 2.5 3 1.5 1
Dummy 0 0 0 0
Programs
Programmer 1 2 3 4
Kumar 1 1 0 2
Dummy 0 0 0 0
Programs
Programmer 1 2 3 4
Kumar 1 1 0 2
Dummy 0 0 0 0
Multiple solutions arise when, at step 3 of assignment, there are more than one 0’s in
more than one row and column of the optimal assignment table. Such situation
109
indicates multiple optimal solutions with the same optimal value of objective function
(total cost, processing time, etc). In such cases the more suitable solution may be
considered by the decision-maker.
Example: Solve the following assignment problem by the Hungarian method and show
that it has multiple solutions. Check your answer below. Processing time (hours) of jobs
in machines is given.
Machines
Jobs 1 2 3
A 2 4 6
B 5 3 3
C 3 2 2
Solution
Machines
Jobs 1 2 3
A 0 2 4
B 2 0 0
C 1 0 0
Machines
Jobs 1 2 3
A 0 2 4
B 2 0 0
C 1 0 0
110
In the optimal table, there are two 0’s in two rows (Row 2 and Row 3) and two
columns (Column 2 and Column 3) at the same time, indicating that the problem
has multiple solutions. There are two possible assignments in this case.
Optimal Assignment I:
In certain instances, it may happen that a particular match or pairing may be either
undesirable or otherwise unacceptable. For example, an employee may not have the
skills necessary to perform a particular job or a machine may not be equipped to handle a
particular operation. In such cases, the cost of performing that particular activity by a
particular resource is considered to be very large (written as M or ¥ ) so as to prohibit
the entry of this pair of employee-job into the final solution.
When such a restriction is present, a letter (M) is often placed in the table in the
that contains M is ignored throughout the analysis. That is, M is not used in any
reductions, nor is any value added to it or subtracted from it during the course of
the analysis.
Departments
Alemayehu 50 45 48
Tigist M 46 50
Tiruwork 55 52 50
111
Required: Find the minimum-cost assignment schedule by using the Hungarian
method.
Solution
Step 1. Row reduction table…Table I
Departments
Alemayehu 5 0 3
Tigist M 0 4
Tiruwork 5 2 0
Departments
Alemayehu 0 0 3
Tigist M 0 4
Tiruwork 0 2 0
There may arise situations when the assignment problem calls for maximization of profit,
revenue, etc as the objective function. Such problem may be solved by converting the
given maximization problem into a minimization problem by the following procedure:
i. Find the largest number (profit, revenue, etc) in the entire table.
112
ii. Subtract each entry in the original table from the largest profit coefficient and
develop opportunity cost table.
The transformed assignment problem so obtained can be solved by using the Hungarian
method.
Example: Assume that the head of management department wants to assign 3 instructors
to 3 courses. From previous studies, the department head determines that average score of
students taking the 3 courses offered by the instructors are as given in the table below.
Required: Find the optimal assignment schedule that maximizes the average score of
students in the 3 courses
Course
Instructor 1 2 3
A 60 65 75
B 80 70 67
C 67 82 73
ii. Subtract each entry in the original table from the largest score (from 82) and
develop “ opportunity cost” table.
Course
Instructor 1 2 3
A 22 17 7
B 2 12 15
C 15 0 9
Course
Instructor 1 2 3
113
A 15 10 0
B 0 10 13
C 15 0 9
Column reduction table
Course
Instructor 1 2 3
A 15 10 0
B 0 10 13
C 15 0 9
A minimum of 3 lines are required to cover all zero’s, indicating that optimal
assignment can be made.
UNIT SUMMARY
Dear distance learner! In this unit we have seen two related OR model-the transportation
and assignment problems- which have interesting applications in business. Both problems
can be approached with the general LPM. However, we usually use specialized
algorithms for each one.
The transportation algorithm involves the following procedures:
1. To set up the transportation table.
2. Examine whether total supply equals total demand. If not, introduce a dummy
row/column having all its cost elements as zero and Supply/Demand as the (+ive)
difference of supply and demand.
3. To find an initial basic feasible solution by using northwest-corner or least-cost
method. An initial solution for a TP with m sources and n destinations must include
m+n–1 occupied cells. If the number of occupied cells at any transportation table is fewer
than m+n-1, the problem is a case of degeneracy. Degeneracy is solved by filling one or
114
more empty cells (until the occupied cells=m+n-1) with an artificial variable (like Δ) and
proceeding with the solution process like any other “normal” problem.
4. To obtain an optimal solution by making successive improvements to initial basic
feasible solution until no further decrease in the transportation cost is possible. An
optimal solution is one where there is no other set of transportation routes that will
further reduce the total transportation cost. Thus, we have to evaluate each unoccupied
cell in the transportation table in terms of an opportunity of reducing total transportation
cost. An unoccupied cell with the largest negative net evaluation value (cost) is selected
to include in the new set of transportation routes (allocations). This value indicates the
per unit cost reduction that can be achieved by raising the shipment allocation in the
unoccupied cell from its present level of zero. We can use the stepping-stone or MODI
method for evaluation. They differ in their approaches, but will give exactly the same
results and use the same testing strategy.
115
6. Repeat step 5 until the number of lines required is equal to the number of rows.
References
1.W. J. Stevenson (1991); Introduction to Management Science, Richard D. Irwin Inc., USA
2. Anderson, Sweeney, and Williams (1997), An Introduction to Management Science:
Quantitative Approaches to Decision Making (8th ed.), West Publishing. Co, USA.
3. Jeffrey D. Camm and James R. Evans (1996) Management Science: Modeling, Analysis
and Interpretation, South Western College Publishing, USA
4. Taha, Hamdy A. (2002), Operations Research:An Introduction (7 th edition), Pearson
Education,Inc. India
5. Eppen, Gould and Shmidt (1988), Quantitative Concepts for Management:Decision
Making Without Algorithms(3rd edition), Prentice Hall, USA
6. J K Sharma (2003): Operations Research, Theory and Application, Second Edition.
116
Exercise 3-2
1.) A marketing manager in XYZ Company wants to assign 4 salespersons to 4
regions. The table below summarizes the expected monthly sales revenue (in 1000’s
of Br.) that can be generated by each sales person in each region.
Required: Find the assignment schedule that maximizes expected sales revenue.
What is the expected total revenue?
Regions
Sales 1 2 3 4
Person
Alemu 50 40 35 42
Bedada 35 30 29 27
Chaltu 28 40 25 38
Ahmed 26 35 30 34
2.)A contractor pays his subcontractors a fixed fee plus mileage for work performed.
On a given day the contractor is faced with three electrical jobs associated with
117
various projects. Given below are the distances (in miles) between the
subcontractors and the projects.
Projects
Subcontractors W X Y
Westside 50 36 36
Federated 20 30 18
Goliath 35 32 20
Universal 25 25 14
3.) Determine the optimal assignment schedule for the following problem. Costs of
assignment (Br.) are given.
Machines
Operators 1 2 3 4
A 30 45 35 49
B 44 43 47 48
C 30 45 35 49
D 50 35 40 47
4.) A computer center has three programmers. The center wants three application
programs to be developed. Programmer 2 cannot be assigned to develop Program B. The
head of the computer center, after studying carefully the programs to be developed,
estimates the computer time in minutes required by the experts for the application
programs as follows. Assign the programmers to the programs in such a way that the total
computer time is minimum.
118
Programs
ProgrammersA B C
1 120 100 80
2 80 - 110
5.) Nyala Steel Industries has four jobs to be completed. Each machine must be assigned
to complete one job. The time required to setup each machine for completing each job is
shown in the table below. Determine the assignment schedule that minimizes the total
setup time needed to complete the four jobs.
Time (Hours)
Machine 1 14 5 8 7
Machine 2 2 12 6 5
Machine 3 7 8 3 9
Machine 4 2 4 6 10
UNIT SIX
GAME THEORY
UNIT OBJECTIVES
After a thorough study of this unit, you will be able to:
Define strategy
Understand the nature of game theory
Develop acquaintance with types of games
Define saddle point
Explain pure strategies
Comprehend mixed strategies
119
understand dominance property
UNIT INTRODUCTION
Decision makers are often faced with situations of conflict and competition which
involve two or more rational opponents. Their results are not solely dependent on their
own decisions but are influenced by what the rival does. War between nations, sports
competitions, market rivalry and competition, negotiations between trade unions and the
management and so on are typical of such situations. The aim of each participant in such
conflicts would be to ascertain what each one can expect to gain in view of the opposing
interests. The theory of games provides an insight in to such problems.
Cognizant to the above fact, we need to be well acquainted with the fundamentals of
game theory in making winning decisions in case of conflicting situations in the business
environment. This unit is devoted to explain game theory to make you a better decision
maker by being watchdog of competitions. To this end, the unit is organized in to two
sections. In the first section, you will learn about assumptions, definitions and
classifications of games; pure strategies and saddle points. The second section is devoted
to mixed strategies & the rule of dominance.
Competition is the watch word of modern of life. We say that a competitive solution
exists if two or more individuals make decision in a situation that involves conflicting
interest in which the outcome is controlled by the decision of all the concerned parties. A
competitive solution is called a game. The term game represents a conflict between two
or more parties. A situation is called a game when it possesses the following properties:
I. The number of competitors is finite.
II. There is a conflict in interests between the participants.
III. Each of the participants has a finite set of possible courses of action.
120
IV. The rules governing these choices are specified and known to all players, a play of
the game results when each of the players chooses a single course of action from the
courses available to him/her.
V. The outcome of the game is affected by the choices made by all the players.
VI. The outcome for all specific set of choices by all of the players is known in advance
and numerically defined.
The outcome of a play consists of a particular set of courses of action undertaken by the
competitors. Each outcome determines a set of payments (Positive, Negative or Zero) one
to each competitor.
Game theory, therefore, is theory that examines the choices of optimal strategies in
conflict situations, where it is concerned with general analysis of strategic interactions.
Economists call game theory as psychologists’ call the theory of social situations, which
is an accurate description of what game theory is about. Most researches in game theory
focuses on how groups of people interact. There are two main branches of game theory:
i.e. Co-operative and non co-operative game theory. Cooperation is more likely to occur
in repeated or many move games, which are more realistic in the real world. In such
games (repeated games) the best strategy is that of to do to your opponent what he/she
has done to you. This is begun by cooperating and continuing to cooperate as long as
your opponent cooperates. If a given firm betrays you after some time he/she agreed to
cooperate, the next time the other opponent waits to betray back. So that for any optimal
cooperation to be applied there must be a hope that cooperation will induce further
cooperation in the future. Among other conditions, it must be assumed that the game is
repeated indefinitely, or at a least a very large and uncertain number of times. If the game
is played for a finite number of times, each firm has an incentive to cooperate in the final
period because it cannot be harmed by retaliation. Each firm knows thus and will not
cooperate on the next- to- the last move. In an effort to gain a competitive advantage by
being the first to start cheating, the entire situation will be unravel (there will be no
confusion) and cheating begins from the first move.
The following conditions should be met other than infinite number of games for an
optimal cooperative game type to be applied. These are:
Stable set of players for the cooperative behavior to develop.
A small number of players to keep track of what each are doing.
Each firm can quickly detect and is willing and able to quickly retaliate for
cheating by other firms.
Demand and cost conditions are relatively stable.
Under conflicting situations, the theory of game generally concerned with the denial
analysis of strategic interactions where we apply it to the study of economic behavior in
different market situations like oligopolistic markets.
Non- Cooperative game theory deals largely with how intelligent enough individuals
interact with one another in an effort to achieve their own goals. Most of the time,
competitive rival industrial, manufacturing as well as service rendering firms compete
one another and try to choose their optimal strategies in non- cooperative styles and select
their optimal strategies given the strategies chosen by the competitive firms.
The term strategy is defined as a complete set of plan of actions specifying precisely
what the player will do under every possible future contingency that might occur during
121
the play of the game. That is, strategy of a player is the decision rule he/she uses for
making a choice from his/her list of courses of actions. Strategy can be classified as:
1. Pure strategy
2. Mixed strategy
A strategy is called pure if one knows in advance of the play that it is certain to be
adopted irrespective of the strategy the other player might choose. The optimal strategy
mixture for each player may be determined by assigning to each strategy, its probability
of being selected. These strategies so determined are called mixed strategy because they
are probabilistic combination of available choices of strategy. Mixed strategy is denoted
by the set S=(x1, x2 ….xn); where xj is probability of choosing the course j such that xj
> 0, for j=1, 2…..n and x1 + x2+…… + xn = 1.
It is evident that pure strategy is a special case of mixed strategy. In the case where all but
one xj is zero, a player may be able to choose only n pure strategy but he has an infinite
number of mixed strategies to choose from.
Player B
1 2 3 …….j………...n
a11 a12 a13…. .a1j….. …..a1n
Player A a21 a22 a23 …..a2j ……....a2n A’s payoff matrix
122
Player B
1 2 3 j n
1 -a11 - a12 a13……-a1j……..-a1
Player A 2 -a21 -a22 -a23…...-a2j… …...-a2
: : : : : ;
i -ai1 -ai2 -ai3……-ai .......-ain
Games are classified according to the number of players involved, the sum of the gains
and losses, and the number of strategies employed in the game.
1. Two – person games and n-person games: In two person games, the players may
have many possible choices open to them for each play of the game, but the
number of players remains only two. Hence it is called a two person game. In case
of more than two persons, the game is generally called n-person game.
2. Zero Sum Game: A zero sum game is one in which the sum of the payment to all
the competitors is zero for every possible outcome of the game is in a game if the
sum of the points won equals the sum of the points lost.
3. Two person zero sum game: A game with two players, where the gain of one
player equals the loss to the other is known as a two person zero sum game. It is
also called a rectangular game because their payoff matrix is in the rectangular
form. The characteristics of this game are :
i) Only two players participate in the game.
ii) Each player has a finite number of strategies to use.
iii) Each specific strategy results in a payoff.
iv) Total payoff to the two players at the end of each play is zero.
This principle is used for the selection of optimal strategies by two players. Consider two
players A and B; A is a player who wishes to maximize his Minimum gain in the strategy
to minimize his losses. Since A would like to maximize his minimum gain, we obtain for
player A, the value called Maximin value and the corresponding strategy is called the
Maximin strategy.
123
On the other hand, since player B wishes to minimize his losses, a value called the
minimax value which is the minimum of the maximum losses is found. The
corresponding strategy is called the minimax strategy. When these two are equal
(Maximin value = Minimax value), the corresponding strategies are called optimal
strategy and the game is said to have saddle point. The value of the game is given by the
saddle point.
The selection of Maximin and Minimax strategies by A and B is based upon the so called
Maximin-Minimax principle which guarantees the best of the worst results.
Saddle point: a saddle point is a position in the payoff matrix where the maximum of row
minima coincides with the minimum of column maxima. The payoff at the saddle point is
called the value of the game.
We shall denote the Maximin value by ұ, the minimax value of the game by ŷ and the
value of the game by Y.
Example 6.1: Solve the game whose pay off matrix is given by:
Player B
Player A
Solution: Player B
Row minima
Player A
Column maxima 1 5 1
124
Maxi (minimum) = Max (1, -4, -1) = 1
Mini (maximum) = Min (1, 5, 1) = 1
That is, Maximin value ұ = 1= Minimax value ŷ
Therefore; Saddle point exists. The value of the game is the saddle point which is 1. The
optimal strategy is the position of the saddle point and is given by (A1, B1).
Example 6.2:
Determine which of the following two people zero sum games are strictly determinable
and fair. Given; the optimum strategy for each player in the case of strictly determinable
games.
Player B
(a) Player B (b) B1 B2
B1 B2 A1 1 1
A1 -5 2 Player A
Player A
A2 -7 -4 A2 4 -3
Solution:
a)
Player B
B1 B2 Row minima
Player A A1 -5 2 -5
A2 -7 -4 -7
Column maxima -5 2
Since ұ = ŷ = -5, the game is strictly determinable, there exist a saddle point= -5. Hence
the value of the game is -5. The optimal strategy is the position of the saddle point given
by (A1, B1).
Player B
b) B1 B2 Row minimum
A1 1 1 1
Player A
A2 4 -3 -3
Column maximum 4 1
125
Exercise 6-1
1. Determine which of the following two people zero sum games are strictly determinable
and fair. Give the optimum strategies for each player in the case of strictly determinable
games.
a) b)
Player B Player B
Player A 5 0 Player A 0 2
0 2 -1 4
6 4 -6
Determine the best strategies for players A and B and also the value of the game for them.
Is this game (i) fair, (ii) strictly determinable?
3. Define a game.
4. Explain a saddle point.
5. What is meant by Minimax and Maximin?
6. What is a pure strategy?
126
6.4 Mixed Strategies: Games without Saddle
Points
A game without saddle point can be solved by various solutions methods.
Example 1. Consider a 2x2 two person zero sum game without any saddle point having
the payoff matrix for player A;
B1 B2
A1 a11 a12
A2 a21 a22
The optimal mixed strategies;
SA= A1 A2 and SB =
B1 B2
P1 P2
q1 q2
Where p1 = a22 - a21 ; p1+ p2=1 → p2 = 1- p1
(a11 + a22) - (a12 + a21)
Example 6.4:
Solve the following game and determine the value of the game.
B
4 -4
A
-4 4
127
Solution: It is clear that the payoff matrix does not possess any saddle point. The players
will use mixed strategies. The optimum mixed strategy for the players are :
SA= A1 A2 , P1 + P2 = 1 and SB =
B1 B2 , q1 + q2 = 1
P1 P2
q1 q2
p2 = 1 – p1 = 1 – ½ = ½
q2 = 1- q1 = 1- ½ = ½
Therefore; the optimum strategy is SA = (½, ½); SB = ( ½ , ½ )
The value of the game is y = a22 a11 - a12a21 = (4x4) – ( -4 x (-4) ) = 0
(a11 + a22) - (a12 + a21) (4 + 4) – (-4+ (-4))
Example 6.5:
In a game of matching coins with two players suppose A wins one unit of value when
there are two heads, wins nothing when there are two tails and losses ½ unit of value
when there are one head and one tail. Determine the payoff matrix, the best strategies for
each player and the value of game to A.
Solution:
The payoff matrix for the player A is given by:
Player B
H T
H 1 -1/2
Player A
T -1/2 0
A2 a21 a22
SA= A1 A2 and SB =
B1 B2
P1 P2
128
q1 q2
= 0 – (- ½ )
1+ 0 – (- ½ – ½ )
= ½ /2 = ¼
q2 = 1 – q1 = 1 – ¼ = ¾
Example 6
Player B
3 -2 4
Player A -1 4 2
2 2 6
129
Solution:
In the given payoff matrix, the entire elements in the third column are greater than or
equal to the corresponding elements in the first column. Therefore, column 3 is
dominated by first column. Delete column 3. The reduced payoff matrix is given by:
Player B
3 -2
Player A -1 4
2 2
Since no row (or column) dominates another row (or column). The 3 x 2 game could now
be solved in simplest ways.
Unit Summary
The theory of games deals with decision making under conditions of competition or
conflict. The players have the same objective but conflicting interests. In the world of
business, striving for greater market share by the different competitors is a typical game
situation. Games are classifies according to the number of players and according to
whether the gains of one player are equal to the losses of the other or not. The simplest
130
form of game is the two-person zero sum game , implying that there are only two
participants who may be individuals , groups or organizations, and that the gains of one
are the losses of the other.
An optimal strategy guarantees a player the best payoff regardless of the strategies
adopted by the opponent. Two-person zero sum games have pure strategies for the
players if a saddle point exists, that is a single optimal strategy for both the players.
Where no saddle point exists, players have to use mixed strategies. A strategy is said to
dominate another if the payoffs it yields are higher than the payoffs of the other strategy
no matter what strategy the opponent adopts. Dominated strategies can be eliminated
from the game.
Game theory has limited practical use at present because of the assumptions made. These
are not totally realistic. Situations are not as simplistic. When there are more than two
players, some of them may negotiate or collaborate against another player. Such
situations are complex and cannot be dealt with the game theory in its present form.
Exercise 6-2
131
3. For a game with the following payoff matrix, determine the optimal strategy and
the value of the game.
B
6 -3
A
-3 0
Player B
1 7 2
Player A 6 2 7
5 1 6
References
132
3. M.P. Gupta R.B. Khanna (2004), Quantitative Techniques for Decision
Making New Delhi.
4. Anderson, Sweeney, and Williams (2003), An Introduction to
Management Science: Quantitative Approaches to Decision Making, 5th
ed. west publishing. Co.
5. Gupta Pram Kumar (2007), Operations Research, S. Chard and Company
LTD. New Delhi, India.
6. Jeffrey D. Camm and James R. Evans; Management Science: Modeling,
Analysis and Interpretation, South Western College Publishing.
7. Harvey M. Wagner; Principles of Operations Research, Prentice Hall
International Inc.
8. Kant Swamp, P.K. Gupta and Man Mohan; Operations Research;
McGraw Hill International.
133