CHAPTER ONE

INTRODUCTION TO OPERATIONS RESEARCH

Unit objective:
Up on the completion of this unit, the learner would be able to:
 Explain the development of OR
 Define operations research
 Describe significance of OR
 Describe the features of OR
 Explain models and their importance
 Differentiate among different categories of models
 Describe techniques in OR

1.1. History of Operations Research

It is generally agreed that operations Research came is to existence as a discipline during

World War II when there was a critical need to manage scarce resources. The term
“Operations research” was coined as a result of research on military operations during this
war. Since the war involved strategic and tactical problems which were greatly complicated,
to expect adequate solutions from individual or specialists in a single discipline was
unrealistic. Therefore, group of individuals who collectively were considered specialists in
mathematics, Economics, statistics and probability theory, engineering, behavioral, and
physical science were formed as special unit within the armed forces to deal with strategic
and tactical problems of various military operations. The objective was the most effective
utilization of most limited military resources by the use of quantitative techniques. There are
three important factors behind the rapid development in the use of operations research
approach.
(i) Pre world war
The roots of OR extended to early 1880’s. It was during 1885 when Fredric lai Taylor
emphasized the application of scientific management to methods of production that the start
took place.
Another man of early scientific management era was Henery L. Grant, most job scheduling
methods at that time where rather haphazard. However, it was the first industrial revolution
which mainly contributed towards the development of “OR”. Before this revolution, most
industries where small scale, employing only a handful of men which will be easily
controlled by a single manager.
The industrial revolution result the placement of men by machine as a source of power and
improved means of communication and transportation resulted in fast flourishing industries.
It become increasingly difficult a single men to perform all managerial functions (planning,
marketing, production, staffing, purchasing, etc.). Consequently a division of management
functions took place, managers of production, marketing, finance personnel etc began to

Page 1
appear. This industrial development brought a new problem which is inconsistent and
clashing objectives from different sectional managers. In order to solve these problem
individuals applied operations research techniques.
(ii) During WW II
The name OR come from a program under taken by Great Britain during WW II which is
called “Research in military operations”.
It is during the early course of the war that Great Britain brought together a group of
specialists from a number of areas to work on military defense of their country. The
responsibility of this operations research group was to determine the best use of the newly
invested Radar and Airpower. The name OR was apparently coined in 1940 because of the
team was carrying out research in military operations
(iii) Post WW II
Immediately after the war, the success of military teams attracted the attention of industrial
managers who are seeking solution to their problem. By 1951, OR had taken its place as
distinct science in USA and OR was introduced as a subject for academic study in American
Universities and this gives an excellent history of OR since it begins.

1.2. Nature and Significance of Operations Research

The Operations research approach is particularly useful in balancing conflicting objectives

(goals or interests), where there are many alternative courses of action available to the
decision-makers. In a theoretical sense, the optimum decision must be one that is best for the
organization as a whole.
 It provides a tool for scientific analysis and provides a solution for various business
problems
 It enables proper deployment and allocation of scarce resources
 It helps in evaluating situations involving uncertainty
 It allows quick and inexpensive examination of a large number of alternatives
 In general, it facilitates and improves the decision making process

1.3. Operation Research: Some definitions

The British/Europeans refer to "operational research", the Americans to "Operations

research" - but both are often shortened to just "OR" (which is the term we will use). Another
term which is used for this field is "management science" ("MS"). The Americans sometimes
combine the terms OR and MS together and say "OR/MS". In recent years there has been a
move towards a standardization upon a single term for the field, namely the term "OR".
Because of the wide scope of application of operations research, giving a precise definition is
difficult. However, a few definitions of OR are given below.

Operations research is a systematic application of quantitative methods, techniques and

tools to the analysis of problems involving the operation of systems.

Page 2
 Operations research is essentially a collection of mathematical techniques and tools which
in conjunction with systems approach, is applied to solve practical decision problems of
an economic or engineering nature.

Operations Research, in the most general sense, can be characterized as the application of
scientific methods, techniques and tools, to problems involving operations of a system so
as to provide those in control of the operations with optimum solutions to the problems.

Operation research seeks the determination of the optimum course of action of a decision
problem under the restriction of limited resources. It is quite often associated almost
exclusively with the use of mathematical techniques to model and analyze decision
problems.

? Dear learners, would you discuss on the above definitions and define OR in your words?
____________________________________________________________________________
_________________________________________________________________________

1.4. Features of Operations Research

From the previous discussions and various definitions of OR, important features or
characteristics can be drawn. These features of OR approach to any decision and control
problems can be summarized as:
(i) Inter-disciplinary approach
Interdisciplinary teamwork is essential because while attempting to solve a complex
management problem, one person may not have complete knowledge of all its aspects such as
economic, social, political, psychological, engineering, etc. This means we should not expect
a desirable solution to managerial problems from a single individual or discipline. Therefore,
a team of individuals specializing in mathematics, statistics, computer science, psychology,
etc, can be organized so that each aspect of the problem could be analyzed by a particular
specialists in that field.
But we shouldn’t forget that certain problem situations may be analyzed even by one
individual.

(ii) Methodological Approach

Operation research is the application of scientific methods, techniques and tools to problems
involving the operations of systems so as to provide those in control of operations with
optimum solutions to the problems.
Note: A system is defined as an arrangement of components designed to achieve a
particular objective(s) according to plan. The components may be either physical
or conceptual or both but they share a unique relationship with each other and
with the overall objective of the system.

Page 3
 (iii) Wholistic Approach or Systems Orientated
While arriving at a decision, an operation research team examines the relative importance of
all conflicting and multiple objectives and the validity of claims of various departments of the
organization from the perspective of the whole organization.
(iv)Decision Making – OR increases the effectiveness of management decisions. It is the
decision science which helps management to make better decisions. So the major
premise of OR is decision making, irrespective of the situation involved.
(v) Use of Computers: OR often requires a computer to solve the complex mathematical
model or to perform a large number of computations that are involved.

Activity
1. Operations research is an aid for the executive in making his/her decisions by providing
the needed quantitative information, based on scientific method analysis. Discuss.
2. Discuss the significance and scope of OR in modern management and Ethiopian
context?

1.5. Models and Modeling in Operations Research

Model is defined as the idealized representation of the real life situations. Models do not, and
cannot, represent every aspect of reality because of the innumerable and changing
characteristics of the real life problems to be represented. Instead, they are limited
approximation of reality. For example, to study the flow of materials through a factory, a
scaled diagram on paper showing the factory floor, position of equipment, tools, and workers
can be constructed. It would not be necessary to give such details as the color of machines,
the height of the workers, or the temperature of the building. For a model to be effective, it
must be representative of those aspects of reality that are being investigated and have a
major impact on the decision situation.

Dear learner, can you mention some of the limitations of models?

1.5.1. Classification of OR Model
________________________________________________________________________

As we discussed earlier, OR model is an abstract representation of an existing problem

situation. It can be in the form of a graph or chart, but most frequently an OR model consist
of a set of mathematical relationships. These mathematical relationships are made up of
numbers and symbols.
Why use Models?
• Real systems may be too complex
• Models may be less expensive
• Models can test options without disrupting the real system
• Modeling provides new insights into the real system
• Save time, money and reduce risk

Page 4
There are many ways to classify models:

(i) Classification based on structure

a) Physical Models: These models provide a physical appearance of the real object under
study either reduced in size or scaled up. Physical models are useful only in design
problems because they are easy to observe, build, and describe. Since these models
cannot manipulated and are not very useful for prediction, problems such as portfolio
analysis selection, media selection, production scheduling, etc cannot be analyzed by
physical models.
b) Symbolic models: These models use symbols (letters, numbers) and functions to represent
variables and their relationships to describe the properties of the system.
(ii) Classification based on function or purpose
Models based on the purpose of their utility include:
a) Descriptive models: Descriptive models simply describe some aspects of a situation,
based on observation, survey, questionnaire results or other available data of a situation
and do not recommend anything. Example: Organizational chart, plant layout diagram,
etc.
b) Predictive Models: These models indicate “If this occurs, then that follow”. They relate
dependent and independent variables and permit trying out, “what if” questions. In other
words, these models are used to predict outcomes due to a given set of alternatives for the
problem. These models do not have an objective function as a part of the model to
evaluate decision alternatives.
For example, S = a + bA +cI is a model that describes how the sales (S) of a product changes
in advertising expenditures (A) and disposal personal income (I). Here, a, b, and c are
parameters whose values must be estimated.

c) Normative (Optimization) models: These models provide the “best” or “Optimal” solution
to problems subject to certain limitations on the use of resources. These models provide
recommended courses of action. For example, in mathematical programming, models are
formulated for optimizing the given objective function, subject to restrictions on resources
in the context of the problem under consideration and non negativity of variables. These
models are also called prescriptive models, because they prescribe what the decision
maker ought to do.

(iii) Classification Based on Time Reference

a) Static Models: Static models represent a system at some specified time and do not account
for changes over time. For example, an inventory model can be developed and solved to
determine an economic order quantity for the next period assuming that the demand in
planning period would remain the same as that for today.
b) Dynamic models: In dynamic models, time is considered as one of the variables and
allows the impact of changes due to change in time. Thus, sequences of interrelated
decisions over a period of time are made to select the optimal course of action to optimize
the given objective. Dynamic programming is an example of a dynamic model.

Page 5
 (iv)Classification based on Degree of certainty

a) Deterministic Models: If all the parameters, constants and functional relationships are
assumed to be known with certainty when the decision is made, the model is said to be
deterministic. Thus, in such a case, the outcome associated with a particular course of
action is known. That is, for a specific set of input values, there is a uniquely, determined
output which represents the solution of the model under consideration of certainty. The
results of the models assume single value. Linear programming models are examples of
deterministic models.
b) Probabilistic (Stochastic) models: Models in which at least one parameter or decision
variable is a random variable are called probabilistic (or stochastic). Since at least one
decision variable is random, a dependant variable which is the function of independent
variable(s) will also be random. This means consequences or pay off due to certain
changes in the independent variable cannot be produced with certainty. However, it is
possible to predict a pattern of values of both the variables by their probability
distribution. Insurance against risk of fire, accidents, sickness, etc are examples where the
pattern of events is studied in the form of a probability distribution.

Dear learner, do you think that the above classification of models is mutually exclusive?
Support your response with evidence.
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

Page 6
 CHAPTER TWO

2. LINEAR PROGRAMMING

Unit Objectives:
Up on completion of this unit, the learner is expected to:
 Recognize problems that can be solved using LP models.
 Formulate an LP model in mathematical terms.
 Solve Linear Programming Problems (LPP) using both graphic and simplex
approach.
 Explain special cases in both graphic and simplex techniques.

INTRODUCTION
In 1947, George Danzig developed the use of algebra for determining solutions to problems
that involved the optimal allocation of scarce resources. In spite of numerous potential
applications in business, response to this new technique was low due to substantial
computational burden, which is now removed with subsequent advances in computer
technology and related software during the last three decades.

The term linear implies that all the mathematical relations used in the problem are linear or
straight-line relations, while the term programming refers to the method of determining a
particular program or plan of action, i.e., the use of algorithms that is a well defined sequence
of steps that will lead to an optimal solution. Taken as a whole, the term linear programming
refers to a family of mathematical techniques for determining the optimum allocation of
resources and obtaining a particular objective when there are alternative uses of the limited or
constrained resources.

The technique of linear programming is applicable to problems in which the total

effectiveness can be expressed as linear function of individual allocations and the limitations
on resources give rise to linear equation or inequalities of the individual allocations.

? Dear learner, can you make differences between solutions of LP models solved manually
and using computers utilizing soft wares?
_________________________________________________________________________

2.1. LINEAR PROGRAMMING MODELS

Linear programming models are mathematical representations of LP problems. Linear
programming models have certain characteristics in common. Knowledge of these
characteristics enables us to recognize problems that are amenable to a solution using LP
models, and to be able to correctly formulate an LP model. These characteristics can be
grouped as components and assumptions. The components relate to the structure of a model,
where as the assumptions reveal the conditions under which the model is valid.

Page 7
2.1.1. COMPONENTS OF LP MODELS
There are four major components of LP models including: Objective function, decision
variables, constraints and parameters.

 Objective and Objective Function

The objective in problem solving is the criterion by which all decisions are evaluated. It
provides the focus for problem solving. In linear programming models, a single,
quantifiable objective must be specified by the decision maker. Because we are dealing
with optimization, the objective will be either maximization or minimization. Hence,
every LP problem will be either maximization or a minimization problem. Once the
objective is specified, it becomes the measure of effectiveness against which alternate
solutions are judged. An LP model consists of a mathematical statement of the objective
called the objective function.

 Decision variables
They represent unknown quantities to be solved for. The decision maker can control the
value of the objective, which is achieved through choices in the levels of decision
variables. For example, how much of each product should be produced in order to obtain
the greatest profit?

 Constraints
However, the ability of a decision maker to select values of the decision variables in an
LP problem is subject to certain restrictions or limits coming from a variety of sources.
The restrictions may reflect availabilities of resources (e.g., raw materials, labor time,
etc.), legal or contractual requirements (e.g., product standards, work standards, etc.),
technological requirements (e.g., necessary compressive strength or tensile strength) or
they may reflect other limits based on forecasts, customer orders, company policies, and
so on. In LP model, the restrictions are referred to as constraints. Only solutions that
satisfy all constraints in a model are acceptable and are referred to as feasible solutions.
The optimal solution will be the one that provides the best value for the objective
function.
Generally speaking, a constraint has four elements:
A right hand side (RHS) quantity that specifies the limit for that constraint. It must
be a constant, not a variable.
An algebraic sign that indicates whether the limit is an upper bound that cannot be
exceeded, a lower bound that is the lowest acceptable amount, or an equality that
must be met exactly.
The decision variables to which the constraint applies.
The impact that one unit of each decision variable will have on the right-hand side
quantity of the constraint.
Constraints can be arranged into three groups:
System constraints – involve more than one decision variable,
Individual constraints – involve only one variable, and
Non-negativity constraints – specify that no variable will be allowed to take on a
negative value. The non-negativity constraints typically apply in an LP model,
whether they are explicitly stated or not.

Page 8
  Parameters
The objective function and the constraints consist of symbols that represent the decision
variables (e.g., X1, X2, etc.) and numerical values called parameters. The parameters are
fixed values that specify the impact that one unit of each decision variable will have on
the objective and on any constraint it pertains to as well as the numerical value of each
constraint.
The following simple example illustrates the components of LP models:

? Dear learner, can you give some of the examples of LP models which consist of
unit and system constraint and discuss the components of each constraint in the
model?
____________________________________________________________________
____________________________________________________________________
________________________________________________________

2.1.2. ASSUMPTIONS OF LP MODELS

A. Linearity (proportionality)

The linearity requirement is that each decision variable has a linear impact on the objective
function and in each constraint in which it appears. In terms of a mathematical model, a
function or equation is linear when the variables included are all to the power 1 (not squared,
cubed, square root, etc.) and no products (e.g., x 1x2) appear. On the other hand, the amount of
each resource used (supplied) and its contribution to the profit (or cost) in the objective
function must be proportional to the value of each decision variable. For example, if
production of one unit requires 5 hours of a particular resource, then making 3 units of that
product requires 15 hours ( 3x5) of that resource.
B. Divisibility (Continuity)
The divisibility requirement pertains to potential values of decision variables. It is assumed
that non-integer values are acceptable. However, if the problem concerns, for example, the
optimal number of houses to construct, 3.5 do not appear to be acceptable. Instead, that type
of problem would seem to require strictly integer solutions. In such cases, integer-

Page 9
programming methods should be used. It should be noted, however, that some obvious
integer type situations could be handled under the assumption of divisibility. For instance,
suppose 3.5 to be the optimal number of television sets to produce per hour, which is
unacceptable, but it would result in 7 sets per two hours, which would then be acceptable.

C. Certainty
This requirement involves two aspects of LP models. One aspect relates to the model
parameters, i.e., the numerical values. It is assumed that these values are known and constant.
In practice, production times and other parameters may not be truly constant. Therefore, the
model builder must make an assessment as to the degree to which the certainty requirement is
met. Large departures almost surely will have a significant effect on the model. The other
aspect is the assumption that all relevant constraints have been identified and represented in
the model.
D. Additivity
The value of the objective function and the total amount of each resource used (or supplied),
must be equal to the sum of the respective individual contributions (profit or cost) by decision
variables. For example, the total profit earned from the sale of two products A and B must be
equal to the sum of the profits earned separately from A and B. Similarly, the amount of a
resource consumed for producing A and B must be equal to the sum of resources used for A
and B respectively.

E. Non-negativity
It assumes that negative values of variables are unrealistic and, therefore, will not be
considered in any potential solutions. Only positive values and zero will be allowed and the
non-negativity assumption is inherent in LP models.

? Dear learner, can you give examples for each of the above assumptions? What will happen
if the assumptions are not met?
__________________________________________________________________________
__________________________________________________________________________
____________________________________________________________

2.2. FORMULATING LP MODELS

Just as it is to define a problem, careful formulation of the model that will be used to solve
the problem is important. Linear programming algorithms (solution techniques) are widely
used and understood and computer packages are readily available for solving LP problems.
Consequently, obtaining solutions is not the real issue, what is very important to note is
failure to check that all constraints have been accounted for and have been correctly
formulated results in ill-structuring of the model that can easily lead to poor decisions.
Steps in formulating LP models:
Identify the decision variables.
Determine the objective function.
Identify the constraints.
Determine appropriate values for parameters and determine whether an upper
limit, lower limit or equality is called for.
Use this information to build a model.
Validate the model.

Page 10
In many cases, the decision variables are obvious; in others it might require brief discussion
with the appropriate manager. However, identifying the constraints and determining
appropriate values for the parameters can require considerable time and effort. Potential
sources of information include historical records, interviews with managers and staff, and
data collection. Validating the model will involve a critical review of the output, perhaps
under a variety of inputs, in order to decide if the results are reasonable.
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 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
Maximize Z = 10x + 6y + 4z
s/t x + y + z ≤ 100 -engineering time
10x + 4 y + 6z ≤ 600 -direct labor time
2x + 2y + 5z ≤ 300 -administrative service time
Where x,y,z ≥ 0 -as the non-negativity restriction
Example 2
A company is making two products A and B. The cost of producing one unit of product A
and B is $ 60 and $ 80 respectively. As per the agreement, the company has to supply at least
200 units of product B to its regular customers. One unit of product A requires one machine
hours whereas product B has machine hours available abundantly within the company. Total
machine hours available for product A are 400 hours. One unit of each product A and B
requires one labor hour each and total of 500 labor hours are available. The company wants
to minimize the cost of production by satisfying the given requirement. Formulate the
problem as a linear programming problem.
Solution
Minimize cost =60x1 + 80x2 (production cost)
Subject to: x2≥ 200 (Agreement for supply)
x1 ≤ 400 (machine hours for product A)
x1 + x2≤500 (labor hours)
x1 , x2≥ 0 ( non –negative constraint)

Page 11
2.3. Solving LP Model
Following the formulation of a mathematical model, the next stage in the application of LP to
decision making problem is to find the solution of the model. An optimal, as well as feasible
solution to an LP problem is obtained by choosing from several values of decision variables
x1,x2…xn , the one set of values that satisfy the given set of constraints simultaneously and
also provide the optimal ( maximum or minimum) values of the given objective function. The
most common solution approaches are to solve graphically and algebraically the set of
mathematical relationships that form the model, thus determining the values of decision
variables.

2.3.1. GRAPHICAL LINEAR PROGRAMMING METHODS

Graphical linear programming is a relatively straightforward for determining the optimal
solution to certain linear programming problems involving only two decision variables.
Although graphic method is limited as a solution approach, it is very useful in the
presentation of LP, in that it gives a “picture” of how a solution is derived thus a better
understanding of the solution. More over, graphical methods provide a visual portrayal of
many important concepts.

In this method, the two decision variables are considered as ordered pairs (X 1, X2), which
represent a point in a plane, i.e, X1 is represented on X-axis and X2 on Y-axis.

Graphical method has the following advantages:

 It is simple
 It is easy to understand, and
 It saves time.
Important Definitions
Solution: The set of values of decision variables xj (j = 1,2,…, n) which satisfy the
constraints of an LP problem is said to constitute solution to that LP problem.
Feasible solution: The set of values of decision variables x j (j = 1,2,…, n) which satisfy all
the constraints and non- negativity conditions of an LP problems simultaneously is said to
constitute the Feasible solution to that LP problem.
Infeasible solution: The set of values of decision variables x j (j = 1,2,…, n) which do not
satisfy all the constraints and non- negativity conditions of an LP problems simultaneously is
said to constitute the infeasible solution to that LP problem.
Basic solution: For a set of m simultaneous equations in n variables ( n>m), a solution
obtained by setting ( n-m) variables equal to zero and solving for remaining m equations in m
variables is called a basic solution.
The (n-m) variables whose value did not appear in this solution are called non-basic
variables and the remaining m variables are called basic variables.
Basic feasible solution: A feasible solution to LP problem which is also the basic solution is
called the basic feasible solution. That is, all basic variables assume non-negative values.
Basic feasible solutions are of two types:
 Degenerate A basic feasible solution is called degenerate if value of at least one
basic variable is zero.
 Non-degenerate A basic feasible solution is called non-degenerate if value of all
m basic variables are non- zero and positive.

Page 12
Optimal Basic feasible solution: A basic feasible solution which optimizes the objective
function value of the given LP problem is called an optimal basic feasible solution.
Unbounded solution: A solution which can increase or decrease the value of objective
function of the LP problem indefinitely is called an unbounded solution.
Example One
In order to demonstrate the method, let us take a microcomputer problem in which a firm is
about to start production of two new microcomputers, X 1 and X2. Each requires limited
resources of assembly time, inspection time, and storage space. The manager wants to
determine how much of each computer to produce in order to maximize the profit generated
by selling them. Other relevant information is given below:

Type 1 Type 2
Profit per unit $60 $50
Assembly time per unit 4 hrs 10 hrs
Inspection time per unit 2 hrs 1 hrs
Storage space per unit 3 cubic feet 3 cubic feet

Availability of company resources:

Resources Amount available
Assembly time 100 hrs
Inspection time 22 hrs
Storage space 39 cubic feet
The model is then:
Maximize 60X1 + 50X2
Subject to Assembly 4 X 1 +10 X 2 < 100 hrs
Inspection 2 X 1 + 1 X 2 < 22 hrs
Storage 3 X 1 + 3 X 2 < 39 cubic feet
X1, X2 > 0

Graphical solution method involves the following steps.

Step 1. Plot each of the constraints

The step begins by plotting the non-negativity constraint, which restricts our graph only to
the first quadrant. We then can deal with the task of graphing the rest of the constraints in two
parts. For example, let us take the first constraint 4X 1 + 10X2 < 100 hrs. First we treat the
constraint as equality: 4X1 + 10X2 = 100. Then identify the easiest two points where the line
intersects each axis by alternatively equating each decision variable to zero and solving for
the other: when X1=0, X2 becomes 10 and when X2=0, X1 will be 25. We can now plot the
straight line that is boundary of the feasible region as we have got two points (0, 10) and
(25,0).

Page 13
Step 2. Identify the feasible region
The feasible region is the solution space that satisfies all the constraints simultaneously. It is
the intersection of the entire region represented by all constraints of the problem. We shade in
the feasible region depending on the inequality sign. In our example above, for all the
constraints except the non-negativity constraint, the inequality sign is ‘less than or equal to’
and it represents region of the plane below the plotted lines.

? Dear learner, can you mention some of the advantages and disadvantages of graphic
method of solving LP models?
_________________________________________________________________________
_________________________________________________________________________
_______________________________________________________________

Step 3. Locate the optimal solution.

The feasible region contains an infinite number of points that would satisfy all the constraints
of the problem. Point that will make the objective function optimum will be our optimal
solution. This point is always found among the corner points of the solution space.

2.3.1.1. The Objective Function Approach

This approach involves plotting an objective function line on the graph and then using that
line to determine where in the feasible solution space the optimal point is. We use the same
logic as plotting a constraint line except that it is not an equation until we equate it to some
right hand side quantity. Any quantity will do till we find a line that would last touch the
feasible solution space.
The optimal solution to an LP problem will always occur at a corner point because as the
objective function line is moved in the direction that will improve its value (e.g., away from

Page 14
the origin in our profit maximization problem), it will last touch one of these intersections of
constraints. Then we determine which two constraints intersect there (in our case inspection
and storage constraints) and solve the equations simultaneously to obtain the mix of the two
decision variables that gives the value of the objective function at the optimum.
Simultaneously solving inspection and storage equations, we find the quantity of type 1
microcomputer to be produced (X1) = 9 and that of type 2 (X2) = 4 giving the maximum profit
of 60(9) + 50(4) = Birr740

Note: The maximization problems the movement of the iso-lines is outward from the
origin; while for minimization the movement is inward to the origin.

2.3.1.2. The Extreme Point Approach

Corner or extreme point graphic method states that for problems that have optimal solutions,
a solution will occur at the corner point in the case of unique solution, while in the case of
multiple solutions, at least one will occur at a corner point as these multiple solutions will be
combinations of those points between two corner points. The necessary steps for this
approach is after graphing the problem, we determine the values of the decision variables at
each corner point of the feasible region either by inspection or using simultaneous equations.
We then substitute the values at each corner point into the objective function to obtain its
value at each corner point and select the one with the highest value of the objective function
(for a maximum problem) or lowest value (for a minimum problem) as the optimal solution.

Extreme Method of Solving Maximization Problems with < constraint

Maximization of objective function involves finding the point where the combination of
products results in maximum value of objective function. The constraints are connected
with < sign. The solution space lies below the slant line and is bounded by the line
segments. The origin and other points below the slant lines are in the solution space (i.e.,
feasible region).

Page 15
Using this method for our example, simultaneously solving for corner points a, b, c, and d,
we find corresponding profit values of 500, 700, 740, and 660, respectively giving us the
same solution as the above one at C. Therefore, the optimal solution is x1= 9 units and x2 = 4
units while the optimal value of objective function is 740.

Interpretation:
For a firm to maximize its profit (740), it should produce 9 units of the Model I
microcomputer and 4 units of model II.

Example 2
Minimize Z= 50X1 + 20X2
Subject to 2X1 – X2 ≤ 0-------------------- (I)
X1 + 4X2 ≥ 80------------------- (II)
0.9X1 + 0.8X2 ≥ 40-------------- (III)
Where X1, X2 ≥ 0 non- negativity condition
Solution:
The first step is skipped as LP problem is already formulated. We will follow other steps
simultaneously.
In constraint (i) 2X1 –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 passing through the origin.
Now, convert constraint (ii) in equality
X1 + 4X2 = 80
When X1 =0, X2=20
X2 =0, X1=80
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.

Page 16
For feasible area we need to examine all the there constraints equations (Note, all are > type).
In equation (i) if we move vertically upward, meaning X 1= 0 and X2 increasing, the equation
becomes negative or less than, which is not permitted. Hence feasible area should be on RHS.
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 up to infinity.
Now we have to find out different values of Z at different corner points, B,C,E by finding out
their coordinates (X1, 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
Interpretation
From the above we can see that minimum value of Z is at point B (1440), where X1=16 and
X2 =32 and hence it is the answer.

2.3.1.3 Graphical Solutions for the Special Cases of LP

i) Unboundedness
Unboundedness occurs when the decision variable increased indefinitely without violating
any of the constraints. The reason for it may be concluded to be wrong formulation of the
problem such as incorrectly maximizing instead of minimizing and/or errors in the given
problem. Checking equalities or rethinking the problem statement will resolve the problem.

Page 17
 Example:
Max Z = 10X1 + 20X2
Subject to 2X1 + 4X2 > 16
X1 + 5X2 > 15
X1, X2 > 0

Following the above listed steps of graphical solution method, we find the following graph
for the above model:

The shaded area represents the set of all feasible solutions and as can be seen from the graph,
the solution is unbounded.
ii) Redundant Constraints
In some cases, a constraint does not form a unique boundary of the feasible solution space.
Such a constraint is called a redundant constraint. A constraint is redundant if its removal
would not alter the feasible solution space. Redundancy of any constraint does not cause any
difficulty in solving an LP problems graphically. Constraints appear redundant when it may
be more binding (restrictive) than others.

iii) Infeasibility
In some cases after plotting all the constraints on the graph, feasible area (common region)
that represents all the constraint of the problem cannot be obtained. In other words,
infeasibility is a condition that arises when no value of the variables satisfy all the
constraints simultaneously. Such a problem arises due to wrong model formulation with
conflicting constraints.

Page 18
For example,
Max Z = 3X1+2X2
Subject to: 2X1 + X2 < 2
3X1 + 4X2 > 12
X1, X2 > 0

iv) Multiple optimal solutions

Recall the optimum solution is that extreme point for which the objective function has
the largest value. It is of course possible that in a given problem there may be more than
one optimal solution.
There are two conditions that should be satisfied for an alternative optimal solution to exist:
 The given objective function is parallel to a constraint that forms the boundary of
the feasible region. In other words, the slope of an objective function is the same
as that of the constraint forming the boundary of the feasible region; and
 The constraint should form a boundary on the feasible region in the direction of
optimal movement of the objective function. In other words, the constraint should
be an active constraint.

Note: The constraint is said to be an active or binding or tight, if at optimality the left
hand side equals the right hand side. In other words, an equality constraint is
always active. An inequality sign may or may not be active.
For example
Max Z = 8X1+16X2
Subject to: X1 + X2 < 200 ……. C1
3X1 + 6X2 < 900 ……. C2
X2 < 125 ……. C3
X1, X2 > 0

Page 19
In the problem above, using extreme point method and solving for values of corner points
simultaneously, the objective function assumes its maximum value of 2,400 at two corner
points B (50,125) and C (100,100). Therefore, the optimal solution is found on the line
segment connecting the two corner points. One benefit of having multiple optimal solutions
is that for other (perhaps qualitative) reasons, a manager may prefer one of them to the others,
even though each would achieve the same value of the objective function. In practical terms,
one of the two corner points is usually chosen because of ease in identifying its value

? Dear learner, can you identify other combination of decision variables that will
optimize the objective function and can you check whether the two conditions for
multiple solution is satisfied?
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________

2.3.2 THE SIMPLEX METHOD

The graphical method of solving linear programming problems is a simple way to find a
solution since the optimum solution is searched among the corner points of the solution
space. However, the graphical method is restricted to problems with two decision variables.
When the number of variables and the number of constraints increase, it becomes difficult to
visualize the solution space. As a result, the graphical method cannot be employed
successfully in such cases. In order to avoid this limitation, the simplex method, or iterative
or step by step method is efficient method for solving linear programming problems, which
was developed by George B. Datzing in 1947.

The simplex method is an algebraic procedure that starts with a feasible solution that is not
optimal and systematically moves from one feasible solution to another until an optimal
solution is found. Incase of the graphical approach, optimal solution occurs at the extreme
points where the constraints intersect. Solutions where constraints intersect are called basic
solutions, and those satisfying all of the constraints together with non-negativity constraints
are called basic feasible solutions.

Constraints are generally expressed using inequalities either in ‘less than’ or ‘greater than’ or
in mixed form. Thus, constraints are not in standard form, meaning they should be converted
into equalities. To convert the inequality constraint into equality, we introduce slack or
surplus variables. In economic terminology, slack variables represent unused capacity and

Page 20
surplus variables represent excess amount. The contribution (cost or profit) associated with
the slack and surplus variables is zero. An inequality of the ‘less than or equal to’ type is
transformed into equality by introducing a non-negative slack variable, as follows: -

Example
Non Standard form Standard form
X1+2X2 <= 6 X1+2X2+S1= 6
, where X1 and X2 are decision variables and S 1 is a slack variable, added to the smaller
side of the inequality.

On the other hand, an inequality with ‘greater than or equal to’ type is changed into equality
by subtracting surplus variable as follows: -

Example
Non Standard form Standard form
X1+2X2 <=6 X1+2X2+S1=6
, where X1 & X2 are decision variables and S1 is a slack variable, added to the smaller side
of the inequality.
As stated above, since both the slack and surplus variables are insignificant with no
contribution in the objective function, they are represented with coefficient of zero in the
objective function.

To find a unique solution, the number of variables should not exceed the number of
equations. When the number of variables is more than the number of equations, the number
of solutions is unlimited. So as to get a unique solution, we have to set at least (n-m) variables
to zero, where n is the number of variables and m is the number of equalities. Those variables
that are set to zero are called non basic variables indicating they are not in the solution. The
variables that are in solution are called basic variable.
.
To demonstrate the simplex method, we will use the microcomputer problem with the
following objective function and constraints.
The Microcomputer Problem, which was discussed in graphic approach, can be standardized
as:

Max. Z = 60X1+50X2+0S1+0S2+0S3
Subject to 4X1+10X2+S1 = 100
2X1+X2+S2 = 22
3X1+3X2+S3 = 39
, where X1 & X2 are decision variables and S1, S2 & S3 are slack variables.
Here, the number of variables (5) is greater than the number of equations (3). Therefore, the
decision variables are set to zero and we have
X1 = 0, X2 = 0, S1 = 100, S2 = 22, and S3 = 39.
This solution will serve as an initial feasible solution. An initial feasible solution is a first
solution used to generate other basic feasible solutions. The initial basic feasible solution is
obtained by setting all the decision variables to zero. As a result, the initial basic feasible

Page 21
 solution is entirely composed of the slack variables. X 1 & X2 are non basic variables since
they are not in solution. S1, S2 & S3 are basic variables since they are in solution.
A tableau is a system of displaying the basic feasible solution, the constraints of the standard
linear programming problem as well as the objective function in a tabular form. A tableau is
useful in summarizing the result of each iteration, i.e. the process of moving from one
solution/corner to another solution/corner in order to select the optimal solution.

2.3.2.1. THE SIMPLEX ALGORITHM: Maximization case

The solution steps of the simplex method can be outlined as follows:
Step1. Formulate the linear programming model of the real world problem, i.e., obtain
a mathematical representation of the problem's objective function and constraints.
Step2. Express the mathematical model of L.P. problem in the standard form by adding
slack variables in the left-hand side of the constraints and assign a zero coefficient
to these in the objective function.
Thus we can restate the problem in terms of equations:

Maximize Z = C1X1+ C2X2 + ... +CnXn + OS1 + OS2 +... +0Sm

Subject to a11X1+a12X2+... + a1nxn+s1i =b1
a2lX1+al22X2+... + a2nXn+S2 = b2
amlXl + am2 X2 +... + amNxn + Sm = bm
, where X1, X2... Xn and S1, S2 ... Sm are non-negative.

Note that the slack variables have been assigned zero coefficients in the objective function.
The reason is that these variables typically contribute nothing to the value of the objective
function.
Step 3. Design the initial feasible solution. An initial basic feasible solution is obtained by
setting
the decision variables to zero.
X1= X2 = ... = Xn = 0. Thus, we get S1 = b1, S2 = b2 ... Sm = bm.

Step 4. Set up the initial simplex tableau. For computational efficiency and simplicity, the
initial basic feasible solution, the constraints of the standard LPP as well as the
objective function can be displayed in a tabular form, called the simplex tableau as
shown below:
Initial Simplex Tableau
Cj C1 C2 ... Cn,, 0 0 ... 0 Quantity Column Ratio
(Contribution Per Unit) XB/
amn
Basic variables CB X1, X2, ... Xn S1 S2 ... Sm b(=Xj)
S1 CB1 a11 a12 ... a1n 1 0 ... 0 b1=Xb1
S2 CB2 a21 a22 ... a2n 0 1 ... 0 b2=Xb2
Sm CBm am1 am2…amn 0 0 ... 1 bm=Xbm
Zj=∑CBiXj 0 0 ... 0 0 0 ... 0 ∑CBiXj
Cj-Zj C1-Z1 C2-Z2 ... Cn-Zn

Page 22
(Net contribution per
unit)
The interpretation of the data in the above tableau is given as under. Other simplex tableau
will have similar interpretations.
In the first row labeled "C j", we write the coefficients of the variables in the objective
function. These values will remain the same in subsequent tableaus.
The second row shows the major column headings.
In the first column of the second row, under the label "Basic variables" (also called
Product mix column), the basic variables are listed.
In the second column of the second row, under the label "CB", the coefficients of the
current basic variables in the objective function are listed. Thus the coefficients of S 1,
S2... Sm, which are included in the initial feasible solution, are written in the CB
column.
The values listed under the non-basic variables (X1, X2… Xn) in the initial simplex
tableau consists of the coefficients of the decision variables in the constraint set. They
can be interpreted as physical rates of substitution.
The values listed under the basic variables (S1, S2... Sm) in the initial simplex tableau
represents the coefficients of the slack variables in the constraints set.
In the next column (also called Quantity column), we write the solution values of the
basic variables.
To find an entry in the Zj row under a column, we multiply the entries of that column
by the corresponding entries of ‘CB’ column and add the results, i.e., Z j= ∑CBiXj.
The Zj row entries will all be equal to zero in the initial simplex tableau. The other Z j
entries represent the decrease in the value of objective function that would result if
one of the variables not included in the solution were brought into the solution. The Z j
entry under the “Quantity Column" gives the current value of the objective function.
The last row labeled "Cj-Zj", called the index row or net evaluation row, is used to
determine whether or not the current solution is optimal or not. The calculation of C j-
Zj row simply involves subtracting each Zj value from the corresponding Cj value for
that column, which is written at the top of that column. We observe that C j -Zj, values
are
meaningful for the non basic variables only. This is because for a basic variable, Z j=
1x
Cj = Cj so that Cj-Zj=Cj-Cj= 0.

Note: The entries in the Cj - Zj, row represent the net contribution to the objective
function that results by introducing one unit of each of the respective column
variables. A plus value indicates that a greater contribution can be made by
bringing the variable for that column into the solution. A negative value indicates
the amount by which contribution would decrease if one unit of the variable for
that column were brought into the solution. Index row elements are also known as
the shadow prices (or accounting prices)
Step 5. We test if the current solution is optimum or not. If all the elements or entries in
the Cj- Zj row (i.e., index row) are negative or zero, then the current solution is
optimum. If there exists some positive number, the current solution can be further
improved by removing one basic variable from the basis and replacing it by some
non-basic one. So start trying to improve the current solution in line with the
following steps.

Page 23
Step 6. Further, iterate towards an optimum solution. To improve the current feasible
solution, we replace one current basic variable (called the departing variable) by a
new non-basic variable (called the entering variable).
We now determine the variable to enter into the solution mix, the entering variable.
One way of doing this is by identifying the column with the largest positive value in
the Cj - Zj row of the simplex table. The column with the largest positive entry in the
Cj - Zj row is called the key or pivot column. The non-basic variable at the top of the
key column is the entering variable that will replace a basic variable.
Next, we determine the departing variable to be replaced in the basis solution. This is
accomplished by dividing each number in the quantity column by the corresponding
number in the key column selected in identifying the entering variable. We compute
the ratio b1/a1j, b2/a2j... bm/amn. This is called replacement ratio.

Replacement Ratio (RR) = Solution Quantity (Q)

Corresponding values in pivot column

The row with the minimum ratio is the key row or pivot row. The corresponding
variable in the key row (the departing variable) will leave the basis.
We identify the key or pivot element. This is the number that lies at the intersection of
the key column and key row of a given simplex tableau.
Step7. Evaluate the new solution by constructing a second simplex tableau. After
identifying the entering and departing variable, all that remains is to find the new
basic feasible solution by constructing a new simplex tableau from the current
one.
Now we evaluate or update the new solution in the following way:
New values for the key row are computed by simply dividing every element of the
key row by the key element to obtain a unit vector (1) in the key element.
The new values of the elements in the remaining rows for the new simplex table can
be obtained by performing elementary row operations on all rows so that all elements
except the key element (1) in the key column are zero, i.e. unit vector.
New entries in the CB column and XB column are entered in the new table of the
current solution.
Compute the values of the Cj - Zj row. If all the numbers in Cj - Zj row are either
negative or zero, an optimum solution has been obtained.
Step 8. If any of the numbers in Cj - Zj row are positive, repeat the steps (6-7) again
until an optimum solution has been obtained.
Note: Rules for Ties. In choosing a key column and a key row, whenever there is a tie
between two numbers, the following rules may be followed:
The column farthest to the left may be selected if there is a tie between two numbers
in the index row.
The nearest ratio to the top may be selected whenever there is a tie between two
replacement ratios in the ratio column.

Page 24
Finding the initial Feasible Solution
As discussed above, the initial feasible solution is found by setting the decision variables to
zero.
Max Z = 60X1+50X2+0S1+0S2+0S3
Subject to 4X1+10X2+S1 = 100
2X1+ X2+S2 = 22
3X1+ 3X2+S3 = 39
X1, X2 > = 0

Initial Simplex tableau

Cj 60 50 0 0 0 Quantity
Basic V. X1 X2 S1 S2 S3
S1 0 4 10 1 0 0 100
S2 0 2 1 0 1 0 22
S3 0 3 3 0 0 1 39
Zj 0 0 0 0 0 0
Cj-Zj 60 50 0 0 0

Interpretation of the Initial Feasible Solution

To be noted first is that the values of each basic variable (variables that are in solution) is
composed of a single 1 and the rest 0’s. This is called a unit vector. Basic variables will have
a unit vector. Moreover, ‘1’ will appear in the same row that the variable appears in. The unit
vector concept will help us in developing subsequent tableaus when we want to change the
list of variables that are in solution.
The Zj row in the quantity column indicates that the value of the objective function is 0.
The values in the Cj-Zj row indicate the net contribution of the variables if one unit of each
variable is added into that solution. For example, the 60 in column X 1 indicates that bringing
one unit of X1 would increase the value of the objective function by $60. The same is true for
the X2 column, i.e. bringing one unit of X 2 would increase the value of the objective function
by $50. On the other hand, since the slack variables are at their maximum, their values in the
Cj-Zj row are all 0. According to what has been said before, we have the following rule in
order to identify an optimal solution.
A simplex solution in a maximization problem is optimal if the C j-Zj row consists of entirely
zeros and negative numbers, i.e. there are no positive values in the row.
So for our case in the initial tableau, we have two positive values under the non-basic
variables, which indicate that further improvement of the solution is possible. As a result, we
go for the optimal solution by developing the second simplex tableau

Developing the Second Simplex Tableau

In the initial feasible solution, the slack variables form entirely the basic variables and the
decision variables entirely form the non-basic variables. Since further improvement is
possible, one of the decision variables will be brought into the solution and one of the current
basic variables will be leaving the solution. ‘Which non-basic variable should be brought into
the solution and which basic variable should leave the solution?’ is a major concern here.

Page 25
In answering the first question, the non-basic variable that should enter the solution should be
the one with the highest positive value in the Cj-Zj row since bringing that non-basic variable
into the solution would make the highest contribution to the solution (objective function) and
result in the largest profit potential. As a result, the variable with the highest value in the C j-Zj
row of the initial simplex tableau is the X 1 column with a value 60. Therefore, X1 should
enter the basis or the solution mix. The X1 column is now called the pivot column. The
numbers in this column (4 2 3) indicate the amount of the basic variables needed to get one
unit of X1. For example, the number 4 indicates that 4 units of the first slack are needed to
obtain one unit of X1.
Since X1 has the highest profit potential, we need to make as much X 1 units as possible. The
amount of X1 that can be made depends on the values in the pivot column and the amount of
slack available shown under the quantity column. By dividing the values in the pivot column
by their respective values in the quantity column, we can identify the variable that is most
limiting.
The values obtained by dividing will help us in determining the variable that should leave the
solution.

Cj 60 50 0 0 0 Quantity
Basic V. X1 X2 S1 S2 S3

S1 0 4 10 1 0 0 100 100/4 = 25
S2 0 2 1 0 1 0 22 22/2 = 11
S3 0 3 3 0 0 1 39 39/3 = 13
Zj 0 0 0 0 0 0
Cj-Zj 60 50 0 0 0

Pivot Column
Pivot Row Pivot Element

In interpreting the ratios obtained by the division, I only the constraint was the first one, we
could make 25 units of X1. But there are also other constraints. Therefore, the one with the
smallest non-negative ratio is the most restrictive since it determines the amount of X 1. In this
particular case, there is only enough of the second constraint to make 11 units of X 1. In
making the 11 units of X1, the second resource (S2) will be down to zero indicating that S2
will leave out the solution mix. The row of the leaving variable is called the pivot row. The
intersection of the pivot row and the pivot column is called the pivot element. As a rule,
The leaving variable is the one with the smallest non-negative ratio.

If a zero is obtained in the results of division, none of the corresponding variable is needed to
obtain one unit of the entering variable. If a negative value is obtained in the division,
bringing the entering variable into the solution would increase the amount of the basic
variable. These values will not limit the amount of the entering variable. Therefore, there is
no need to divide the quantity column by zero or negative.
Since we have determined the leaving and the entering variables and since the initial feasible
solution can be improved further, we need to develop the second tableau in order to find the

Page 26
optimal solution. In developing the second tableau, we should compute for revised values of
the constraint equations, the Zj row and the Cj-Zj row and remember that the variables in
solution will have a unit vector, with a value of 1 in the intersection of the column and the
row of the basis, i.e. the pivot element.

To obtain a unit vector in the basis column, we perform elementary row operations resulting
in new row values by either multiplying/dividing all the elements in a row by a constant or
adding/subtracting the multiple of a row to or from another row.
In computing for the new row values from our initial simplex tableau, we first multiply the
second constraint by ½ obtaining the values as follows:
1X1+1/2X2+0S1+1/2S2+0S3 = 11, which results in making the pivot element 1.
Next, we multiply the above new row values by 4 and subtract it from the first constraint
obtaining the following results:
0X1+8X2+1S1+2S2+0S3 = 56.
Then, we multiply the new row values in the pivot row by 3 and subtract it from the third
constraint resulting as follows:
0X1+3/2X2+0S1-3/2S2+1S3 = 6.
Having these new row values, we develop the second simplex tableau as shown below.
Second Simplex Tableau
Cj 60 50 0 0 0 Quantity
Basic V. X1 X2 S1 S2 S3
S1 0 0 8 1 -2 0 56
X2 60 1 1/2 0 1/2 0 11
S3 0 0 3/2 0 -3/2 1 6
Zj 60 30 0 30 0 660
Cj-Zj 0 20 0 -30 0

Interpretation of the Second Simplex Tableau

The profit obtained at this point of solution is $660. In the Cj-Zj row, we search for the
highest positive value. If there is, it means that we can further improve this solution.
Therefore, we have a positive value in the Cj-Zj row which indicates that this is not the
optimal solution. As a result, we go for the next tableau.

Developing the Third Tableau

Here, we select the entering and the leaving variables. The entering variable is the one with
the highest Cj-Zj row value which is the X2 column. This means that bringing one unit of X 2
into the solution increases profit by $20. Therefore, the X 2 will be the entering variable
designated as the pivot column.
To determine the leaving the variable, we divide the values in the pivot column by their
corresponding row values in the quantity column. The result obtained, as shown in the table
below indicates that S3 is the leaving variable with the smallest non-negative ratio. This
means that S3 is the most limiting resource for how much units of X2 can be made.

Page 27
 Cj 60 50 0 0 0 Quantity
Basic V. X1 X2 S1 S2 S3
56/8 = 7
S1 0 0 8 1 -2 0 56
11/(1/2) = 22
X2 60 1 ½ 0 ½ 0 11
6/(3/2) = 4
S2 0 0 3/2 0 -3/2 1 6
Zj 60 30 0 30 0 660
Cj-Zj 0 20 0 -30 0

Pivot Row
Pivot Column Pivot Element
After identifying the entering and the leaving variables, we perform elementary row
operations as follows. To obtain a unit vector with 1 in the pivot element, we multiply the
pivot row by 2/3 resulting as follows:
0X1+1X2+0S1+-1S2+2/3S3 = 4
Then, multiply the above new row values by 8 and subtract it from the first constraint (row)
resulting as follows:
0X1+0X2+1S1+6S2+-16/3S3 = 24.
For row 2, first multiply the new row values in the pivot row by ½ and subtract it from the
second row resulting as follows:
1X1+0X2+0S1+1S2+-1/3S3 = 9.
And the third tableau looks like the following.
Third Simplex Tableau
Cj 60 50 0 0 0 Quantity
Basic V. X1 X2 S1 S2 S3
S1 0 0 0 1 6 -16/3 56
X1 60 1 0 0 1 -1/3 11
X2 50 0 1 0 -1 2/3 6
Zj 0 0 10 40/3 0 740
Cj-Zj 0 0 -10 -40/3 0

Interpreting the Third Tableau

All the values in the Cj-Zj row are zero and negative indicating that there can no be additional
improvement. This makes the third tableau to contain the optimal solution with the following
basic variables:
S1 = 24, X1 = 9, and X2 = 4 producing a maximum profit of $740.
This means that in order to achieve the maximum profit, the company should produce 9 units
of X1 and 4 units of X2 leaving 24 hours of unused resource of the second constraint.

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

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

b. M as a coefficient is assigned to artificial variable A in the objective function Z.
c. Big-M method can be applied to minimization as well as maximization problems with the
following distinctions:
i. Minimization problems
-Assign +M as coefficient of artificial variable A in the objective
function Z of the minimization problem.
ii. Maximization problems:
-Here –M is assigned as coefficient of artificial variable A in the
objective function Z of the maximization problem.
d. Coefficient of S (slack/surplus) takes zero values in the objective function Z
e. For minimization problem, the incoming variable corresponds to the highest negative
value of Cj-Zj.
f. The solution is optimal when there is no negative value of Cj-Zj.(For minimization LPP
case)
The various steps involved in using simplex method for minimization problems are:
Step 1. Formulate the linear programming model, and express the mathematical model of
L.P. problem in the standard form by introducing surplus and artificial variables
in the left hand side of the constraints. Assign a 0 (zero) and +M as coefficient
for surplus and artificial variables respectively in the objective function. M is
considered a very large number so as to finally drive out the artificial variables
out of basic solution.
Step 2. Next, an initial solution is set up. Just to initiate the solution procedure, the initial
basic feasible solution is obtained by assigning zero value to decision variables.
This solution is now summarized in the initial simplex table. Complete the initial
simplex table by adding two final rows Z, and C j - Zj. These two rows help us to
know whether the current solution is optimum or not.
Step 3. Now; we test for optimality of the solution. If all the entries of C j - Zj, row are
positive, then the solution is optimum. However, this situation may come after a
number of iterations. But if at least one of the C j - Zj values is less than zero, the

Page 29
 current solution can be further improved by removing one basic variable from the
basis and replacing it by some non-basic one.
Step 4. (i) Determine the variable to enter the basic solution. To do this, we identify the
column with the largest negative value in the Cj - Zj row of the table.
(ii) Next we determine the departing variable from the basic solution. If an
artificial variable goes out of solution, then we discard it totally and even this
variable may not form part of further iterations. Same procedure, as in
maximization case, is employed to determine the departing variable.

Step 5. We update the new solution now. We evaluate the entries for next simplex table in
exactly the same manner as was discussed earlier in the maximization case.

Step 6. Step (3—5) are repeated until an optimum solution is obtained.

So the following are the essential things to observe in solving for minimization problems:
The entering variable is the one with the largest negative value in the C j-Zj row while
the leaving variable is the one with the smallest non-negative ratio.
The optimal solution is obtained when the Cj-Zj row contains entirely zeros and
positive values.

Example: Assume the following minimization problem.

Min Z = 7X1+9X2
Subject to 3X1+6X2 >= 36
8X1+4X2 > = 64
X1, X2 > = 0

We introduce both surplus and artificial variables into both constraints as follows.

Min Z = 7X1+9X2+0S1+0S2+MA1+MA2
Subject to 3X1+6X2 –S1+A1 = 36
8X1+4X2-S2+A2 = 64
X1, X2 > = 0
So the subsequent tableaus for this problem are shown below. To remind in these tableaus is
in transforming from one tableau to another, we perform elementary row operations to obtain
the unit vector in the pivot column for the entering variable into the solution.
Initial Simplex Tableau
Cj 7 9 0 0 M M Quant
Basic X1 X2 S1 S2 A1 A2 ity
V.
A M 3 6 -1 0 1 0 36
1

A M 1 4 0 -1 0 1 64
2

Zj 11M 10M -M -M M M 50M

Cj-Zj 7-11M 9-10M M M 0 0

Page 30
Second Simplex Tableau
Cj 7 9 0 0 M Quantity
Basic V. X1 X2 S1 S2 A1
A1 M 0 9/2 -1 3/8 1 12
X1 7 1 ½ 0 -1/8 0 8
Zj 7 7/2+9/2M -M 3/8M-7/8 M 56+12M
Cj-Zj 0 11/2-9/2M M 7/8-3/8M 0

Third Simplex Tableau

Cj 7 9 0 0 Quantity
Basic V. X1 X2 S1 S2
X2 9 0 1 -2/9 1/12 8/3
X1 7 1 0 1/9 -1/6 20/3
Zj 7 9 -11/9 -5/12 212/3
Cj-Zj 0 0 11/9 5/12

The third tableau represents a final tableau since it is the optimal solution with entirely zeros
and non-negative values in the Cj-Zj row.
Therefore, the optimal solution is: X1 = 20/3 and X2 = 8/3 and value of objective function is
212/3.
Coefficient of extra variables Presence of
Types of
in the objective function variables in
Constrain Extra variables to be added
MaxZ the initial
t
MinZ solution mix

< Add only slack variable 0 0 Yes

> Subtract surplus variable and 0 0 No

Add artificial variable -M +M Yes
= Add artificial variable -M +M Yes

Summary

2.3.2.3. SPECIAL ISSUES

Several special situations which one many encounter during the application of simplex
method are summarized below:
Non-feasible Solution/ Infeasibility
A situation with no feasible solution may exist if the problem was formulated incorrectly.
? Dear learner, why do you think that artificial variables did not appear in the optimal
Infeasibility comes about when there is no solution that satisfies all of the problem’s
solution? What is the guarantee not to get artificial variable in the optimal solution?
constraints.

Page 31
In the simplex method, an infeasible solution is indicated by looking at the final tableau
Whenever the optimality criteria is satisfied but still there exist an artificial variable in the
basis or solution mix, this is the indication of infeasibility.
Example:
Minimization case

Cj 5 8 0 0 M

BV X1 X2 S1 S2 A2 Q

5 X1 1 1 -2 3 0 200

8 X2 0 1 1 2 0 100

M A2 0 0 0 -1 1 20
Zj 5 8 -2 31-M M 1,800+200M
Cj - Zj 0 0 2 M-31 0

Even though all Cj - Zj are positive or 0(i.e. the criterion for an optimal solution in a
minimization case), no feasible solution is possible because an artificial variable (A2)
remains in the solution mix.
Unbounded Solution
No finite solution may exist in problems that are not bounded. This means that a variable can
be infinitely large without violating a constraint. In the simplex method, the condition of
unboundedness will be discovered prior to reaching the final tableau. We will note the
problem when trying to decide which variable to remove from the solution mix.

The procedure in unbounded solution is to divide each quantity column number by the
corresponding pivot column number. The row with the smallest positive ratio is replaced. But
if the entire ratios turn out to be negative or undefined, it indicates that the problem is
unbounded.

Note: A negative ratio means that increasing that variable would increase resources. A
zero ratio means that increasing the variable would not use any resources.

Page 32
Example: Maximization case:
Cj 6 9 0 0

SV X1 X2 S1 S2 Q

9 X2 -1 1 2 0 30

0 S2 -2 0 -1 1 10
Zj -9 9 18 0 270

Cj - Z j 15 0 -18 0

Pivot Column

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

Note: When unbounded solutions occur, no outgoing variable will exist.

Degeneracy
/Tie for leaving basic variable (key row)/
If there is a tie for the smallest ratio, this is a signal that degeneracy exists. Degeneracy can
occur right in the first (initial tableau). This normally happens when the number of
constraints is less than the number of variables in the LP model. Such problems can be
overcome by trial and error method. If this is resolved by a proper selection of the key
element, degeneracy can be avoided. The main drawback to degeneracy is the increase in the
computation, which reduces the efficiency of the simplex method considerably.

Example

5 8 2 0 0 0
Cj
Q
SV X1 X2 X3 S1 S2 S3

8 X2 1/4 1 1 -2 0 0 10 RR

0 S2 4 0 1/3 -1 1 0 20
0 S3 2 0 2 2/5 0 1 10 10/1/4=40

20/4= 5 Tie for the smallest ratio

Zj 2 8 8 16 0 0 80
Indicates degeneracy.
10/2= 5
Degeneracy could lead to
Cj - Z j 3 0 -6 -16 0 0
a situation known as

Page 33
cycling, in which the simplex algorithm alternatives back and forth between the same non-
optimal solutions, i.e., it puts a new variable in, then takes it out in the next tableau, puts it
back in, and so on.
One simple way of dealing with the issue is to select either row (S2 or S3 in this case)
arbitrary. If we are unlucky and cycling does occur, we simply go back and select the other
row. How ever, the number of iterations required to arrive at the optimal solution can be
minimized by adopting the following rule:
 Divide the coefficient of slack variables in the simplex table where degeneracy is
detected by the corresponding positive numbers of the key column in the row, starting
from left to right.
 The row which contains smallest ratio comparing from left to right column wise
becomes the key row.
For the above example:
Column
Row s2 s3
s2 1 0
s3 0 1
Divide the coefficients by the corresponding element of the key column, we obtain the
following:
Column
Row s2 s3
s2 ¼= ¼ 0/4=0
s3 0/2 =0 ½=1/2
Comparing the ratios from left to right column wise until they are not equal, the minimum
ratio occurs for the second row (0). Therefore, s3 is selected to leave the basis.

Note: When there is a tie between a slack and artificial variable to leave the basis, the
preference shall be given to artificial variable to leave the basis and there is no
need to apply the procedure for resolving such cases.
Two incoming variables
/ Or Tie for entering variables/
In order to break this tie, the selection for the key column (entering variable) can be made
arbitrary. However; the number of solution can be minimized by adopting the following
rules:
1. If there is a tie between two decision variables, then the selection can be made arbitrary.
2. If there is a tie between a decision variable and a slack (or surplus) variable, then select
the decision variable to enter into basis first.

Page 34
3. If there is a tie between slack or surplus variable, then selection can be made
arbitrary.
Example:
If the equation is max Z:

Cj

SV X1 X2 S1 S3 Q

Zj
Cj - Z j 5 2 5 0

In such a case,X1 is the entering variable

Multiple Optimum Solutions

This situation occurs when there can be infinite number of solutions possible for a given
problem. This situation can be recognized in a simplex method when one of the non-basic
variables in the Cj-Zj, row have a value of zero. This is to mean in the optimal solution when
non basic variable (variable not in the basis) has a zero value in C-Z row, this is the
indication of existence of multiple solution. To obtain the other solution, we will make a non-
basic variable with a zero C-Z value to enter in to the basis and solve in the same way as the
one we did in the previous discussion.
Example:
Maximization problem

Cj 3 2 0 0

BV X1 X2 S1 S2 Q

2 X2 3/2 1 1 0 6

0 S2 1 0 1/2 1 3

Zj 3 2 2 0 12

Cj - Z j 0 0 -2 0

MaxZ=3X1+2X2
X1=0, X2=6, S2=3 and MaxZ=12 or: X1=3, X2=3/2 and MaxZ=12

The Cj - Zj value of the non-basic variable (X1) is 0. Thus, this shows the existence of
alternative optimal solution. Can you identify more alternative optimal solutions?

Page 35
 ? Dear learner, can you raise examples of your own for each of the above special issues
and show how each relate to graphic approach?
_________________________________________________________________________
_________________________________________________________________________

 Activity
1. The crumb and Custard bakery makes cakes and pies. The main ingredients are flour and
sugar. The following linear programming model has been developed for determining the
number of cakes and pies (x1 and x2 to produce each day to maximize profit.
Max Z=x1 + 5x2
Subject to:
8x1+10x2< 25(flour, lb)
2x1+4x2< 16(sugar, lb)
X1< 5(demand for cakes)
X1, x2 >0
Solve this model using graphical and simplex method and compare the answers.
2. A transistor radio Co., manufactures models A, B, and C which have profit contribution of
Birr 16, Birr 30 and Birr 50 respectively. The weekly minimum production requirements are
20 for model A, 120 for model B, and 60 for model C. Each type of radio requires a certain
amount of time for the manufacturing of component parts, assembly and packaging.
Specifically a dozen unit of model A requires 3 hrs for manufacturing of component parts, 4b
hrs for assembly and 1 hr for packaging. The corresponding figure for a dozen unit of model
B is 3.5, 5 and 1.5 and for a dozen unit of C are 5, 8, and 3 hrs. During the forth coming
week, the company has availability of 120 hrs of manufacturing, 160 hrs of assembly, and 45
hrs of packaging time.
Required:
a) Formulate the scheduling problem as LPM.
b) Solve the problem using simplex method
c) Identify basic and non basic variables at each iteration

3. A manufacturer produces two popular grades of commercial carpeting among its many other
products. In the coming production period, the company needs to decide how many rolls of
each grade should be produced in order to maximize profit. Each roll of Grade ‘X’ carpet
uses 50 units of synthetic fiber, 25 hours of production time and 20 units of foam packing.
Each roll of Grade ‘Y’ carpet uses 40 units of synthetic fiber, 28 hours of production time and
20 units of foam packing. The profit per roll of grade ‘X’ carpet is birr 200 and per roll of
grade ‘Y’ is birr 160. In the coming production period the company has 3000 units of
synthetic fiber available for use, workers have been scheduled to provide at least 1800 hours
of production time and the company has 1500 units of foam packing available for use.
Required:
a. Develop the linear programming model.
b. Find the optimal solution using graphic method

Page 36
 2.4. DUALITY
The term ‘dual’ in a general sense implies two or double. Every linear programming problem
can have two forms. The original formulation of a problem is referred to as its Primal form.
The other form is referred to as its dual LP problem or in short dual form. In general,
however, it is immaterial which of the two problems called primal or dual, since the dual of
the dual is primal.

The dual involves setting up and solving an LP problem that is almost a ‘mirror image’ of an
LP problem that has been formulated. Both in its formulation and solution, the dual is the flip
flop version of the primal.

Analysis of the dual can also enable a manager to evaluate the potential impact of a new
product, and it can be used to determine the marginal values of resources (i.e. constraints).
Relative to a product, a manager would want to know what impact adding a new product
would have on the solution quantities and the profit; relative to resources, a manager can refer
to a dual solution to determine how much profit one unit of each resource equivalent to.
Whereas the primal gives solution results in terms of the amount of profit gained from
producing products, the dual provides information on the value of the constrained resources
in achieving that profit.

? Often the manager is less concerned about profit than about the use of resource in dual. Do you agree?
_____________________________________________________________________________________

3.1.1. Formulating the Dual

The following rules which guide the formulation of the dual problem will give you the
summary of the general relationship between primal and dual LP problems.
1. If the primal’ objective is to minimize, the dual’s will be to maximize; and the vice
versa
2. The coefficient’s of the primal’s objective function become the RHS values for the
dual’s constraints.
3. The primal’s RHS values become the coefficients of the dual’s objective function.
4. The coefficients of the first “row” of the primal’s constraints become the coefficients
of the first “column” of the dual’s constraint …..
5. The ≤ constraints become ≥ and the vice versa.
Consider this Primal problem:

Minimize 40x1 + 44x2 + 48x3

Subject to: 1x1 + 2x2 + 3x3 > 20
4x1 + 4x2 + 4x3 > 30
x1, x2, x3 > 0

Page 37
The dual of this problem is:

Maximise Z = 20y1 + 30y2

Subject to:
1y1 + 4y2 < 40
2y1 + 4y2 < 44
3y1 + 4y2 < 48
y1, y2 > 0
The following table shows how the primal problem is transformed into its dual.
Primal Dual
Objective Minimize 40x1 + 44x2 + 48x3 Maximize 20y1 + 30y2
function and Subject to Subject to
right-hand 1  20 1  40
side values 2  30 2  44
3  48
Primal Dual
Constraint 1 1x1 + 2x2 + 3x3  1 1y1 + 4y2 
coefficients 2 4x1 + 4x2 + 4x3  2 2y1 + 4y2 
3 3y1 + 4y2 

We can see from the table that the original objective was to minimize, whereas the objective
of the dual is to maximize. In addition, the coefficients of the primal’s objective function
become the right-hand side values for the dual’s constraints, whereas the primal’s right-hand
side values become the coefficients of the dual’s objective function.

Note that the primal has three decision variables and two constraints; whereas the dual has
two decision variables and three constraints.

The constraint coefficients of the primal are constraint coefficients of the dual, except that the
coefficients of the first “row” of the primal become the coefficients of the first “column” of
the dual, and the coefficients of the second “row” of the primal become the coefficients of the
second “column” of the dual.

When the primal problem is a maximization problem with all < constraints, the dual is a
minimization problem with all > constraints.

3.1.2. Formulating the Dual when the Primal has Mixed Constraints
In order to transform a primal problem into its dual, it is easier if all constraints in a
maximization problem are of the < variety, and in a minimization problem, every constraint is
of the > variety.

To change the direction of a constraint, multiply both sides of the constraints by -1. For
example,
-1(2x1 + 3x2 > 18) is -2x1-3x2 < -18

Page 38
If a constraint is an equality, it must be replaced with two constraints, one with a < sign and
the other with a > sign. For instance,
4x1 + 5x2 = 20
will be replaced by
4x1 + 5x2 < 20
4x1 + 5x2 > 20
Then one of these must be multiplied by -1, depending on whether the primal is maximization
or a minimization problem.
EXAMPLE:
Formulate the dual of this LP model.

Maximize z =
1 ¿ ¿¿
50x ¿ + 80x2
Subject to:
¿ ¿¿
1
C¿
1 ¿ ¿¿
3x ¿ + 5x2 ≤ 45

C2
¿1 ¿ ¿
4x ¿ + 2x ≥16 2

C3
¿1 ¿ ¿
6x ¿ +6x2 = 30
¿1 ¿ ¿
x ¿ ,x ≥ 0 2
SOLUTION
Since the problem is a max problem, put all the constraints in to the ≤ form. Subsequently, C 2
and C3 will be first adjusted in to ≤ constraints.
- C2 will be multiplied by -1:
¿1 ¿ ¿
-1(4x ¿ + 2x2 ≥16) becomes -4x ¿ - 2x2 ≤ -16
¿1 ¿ ¿
- C3 is equality, and must be restated as two separate constraints. Thus, it becomes:
¿ ¿¿
1 1 ¿ ¿¿
6x ¿ +6x2 ≤ 30 and 6x ¿ +6x2 ≥30. Then the second of these must be multiplied by -1.
¿1 ¿ ¿
-1(6x ¿ +6x2 ≥30) becomes -6x ¿ -6x2 ≤ -30
¿1 ¿ ¿
After making the above adjustments, rewrite the LP model again.

Maximize z =
1
50x ¿ + 80x2
¿ ¿¿
Subject to:
¿ ¿¿
1
C¿
1¿ ¿¿
3x ¿ + 5x2 ≤ 45

C2
¿1 ¿ ¿
-4x ¿ - 2x ≤ -16
2

C3
¿1 ¿ ¿
6x ¿ +6x2 ≤ 30

C4
¿1 ¿ ¿
-6x ¿ -6x ≥ -302

¿1 ¿ ¿
x ¿ , x2 ≥ 0

Page 39
The dual of the above problem will be:
Minimize 45y1 - 16y2 + 30y3 – 30y4
Subject to
1¿ ¿¿
C ¿ 3y1 -4y2 + 6y3 – 6y4 ≥ 50
C2 3y1 - 2y2 + 6y3 – 6y4 ≥ 80
y1, y2, y3, y4 ≥ 0

 Activity
Convert the following in to dual and solve it using simplex approach
1. Min Z= 4x1 +x2
Subject to:
3 x1+ x2 = 3
4x1+ 3x2 > 6
x1+ 2x2 < 3
x1,x2 > 0
b. Min Z=2x1 +8x2
Subject to:
5x1+ x2 > 10
2x1+ 2x2 > 14
x1+ 4x2 > 14
x1, x2 > 0
2.5. Sensitivity Analysis
As it is indicated above, sensitivity analysis is the study of sensitivity of the optimal solution
of an LP problem due to discrete variations (changes) in its parameters. The degree of
sensitivity of the solution due to these changes can range from no change to all to a
substantial change in the optimal solution of the given LP problem.

Sensitivity analysis carries the LP analysis beyond the determination of the optimal solution
and begins with the final simplex tableau. Its purpose is to explore how changes in any of the
parameters of a problem, such as the coefficients of the constraints, coefficients of the
objective function, or the right hand side values; would affect the solution. For this, instead of
resolving the entire problem as anew problem with new parameters, we may consider the
original optimal solution as an initial solution for the purpose of knowing the ranges, both
lower and upper, within which a parameter may assume a value.

Page 40
For instance, a manager may want to consider obtaining an additional amount of scarce
resource that might be available, in which case the manager would want to know the answers
to questions such as:

a. Will an increase in the right hand side of this constraint affect the objective function?
b. If so, how much of the resource can be used?
c. Given the answer to the preceding question, what will be the revised optimal solution?

Conversely, the decision maker might be facing a situation in which the amount of scarce
resource available is less than the original amount, in which case the issues would be:
a. Will the decreased level of the resource have an impact on the value of the objective
function?
b. If yes, how much of an impact will it have, and what will be the revised optimal
solution?
The process of studying the sensitivity of the optimal solution of an LP problem is also called
post optimality analysis because it is done after an optimal solution, assuming a given set of
parameters, has been obtained for the model.

The discussion here covers only two types of changes: changes in the right hand side levels of
the constraints, and changes in the coefficients of the objective function as change in the
coefficient of constraints is beyond the coverage of this material.
To demonstrate sensitivity analysis, the microcomputer example will again be used.

Maximize 60x1 + 50x2

Subject to
Assembly time 4x1 + 10x2 ≤ 100
Inspection time 2x1 + 1x2 ≤ 22
Storage space 3x1 + 3x2 ≤ 39
X1, X2 > = 0
The most obvious way to ascertain the effect of a change in the parameter of the model is to
make the change in the original model, resolve the model, and compare the solution result
with the original solution. However, resolving a problem can be very time consuming and as
it will be demonstrated below, it is unnecessary. In most cases the effect of changes in the
model can be determined directly from the final simplex tableau.

2.5.1 A Change in the RHS of a constraint

The first step in determining how a change in the RHS (Right Hand Side) of a constraint
(e.g., the amount of scarce resource that is available for use) would influence the optimal
solution is to examine the shadow prices in the final simplex tableau. Shadow prices are the
values in the Z row in the slack columns.
The final tableau for the microcomputer is shown in the following table since sensitivity
analysis starts from final tableau.

Cj 60 50 0 0 0 Quantity
Basis 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

Page 41
 Z 60 50 0 10 40/3 740
C-Z 0 0 0 -10 -40/3

Negatives of
shadow prices
A shadow price is a marginal value; it indicates the impact that a one-unit change in the
amount of a constraint would have on the values of the objective function. As we can see
from the table, the shadow prices are $0 for s 1 (Assembly time), $10 for s2 (Inspection time),
and $40/3 for s3 (Storage space). These tell us that an increase in the amount of assembly
time would have no effect on profit; if inspection time is increased by one hour, it will
increase the profit by $10, and if storage space is increased by 1 cubic foot, profit would
increase by $40/3. The reverse also holds. If we decrease them by such respective amounts,
the decrease in profit will take the same figure.

I. Determining Feasibility ratio: How?

Feasibility Ratio (FR) = quantity ÷ respective slack variable coefficient: in the final
optimal solution tableau
≤ ≥
Allowable RHS The negative FR closest Smallest positive FR
increase to zero
Allowable RHS Smallest positive FR The negative FR closest to zero
decrease

Feasibility ratio
S1 S2 S3 Quantity Constraint 1 Constraint 2 Constraint 3
1 6 -16/3 24 24/1=24 ↓ 24/6=4 ↓ 24/(-16/3)=-4.5 ↑
0 1 -1/3 9 9/0=∞ 9/1=9 9/(-1/3)= -27
0 -1 2/3 4 4/0= ∞ ↑ 4/-1= -4 ↑ 4/ (2/3) = 6 ↓
Note: If there is no suitable negative/positive FR, then the allowable increase/decrease is ∞

ii. Determining the range of feasibility

(RHS amount - allowable decrease) up to Current RHS amount + allowable increase);
Therefore;
Constraint 1: (Assembly time): 100-24 up to 100+∞ : (76 - ∞ )
Constraint 2: (Inspection time: 22-4 up to 22+4 :(18-26)
Constraint 3: (Storage space): 39-6 up to 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.
 Similarly, Each hour increase or decrease in inspection time will increase or decrease the
current profit by $10, respectively as long as the total inspection time is between 18 and 26
hours. Out side the range of feasibility, the current shadow price ($10) will not be valid.
Page 42
 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.
 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
$10 (i.e 3×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.
Example
The manager in the microcomputer problem is contemplating a change in the level of the
storage constraint – an increase of 3 cubic feet. Determine the revised optimal solution for the
change.

Solution
First, note that an increase of 3 cubic feet is within the range. Then, the effect of an
increase of three cubic feet is computed in the following way:

Basis s3 Current solution Change Revised solution

s1 -16/3 24 3(-16/3)= -16 8

x1 -⅓ 9 3(-⅓) = -1 8
x2 ⅔ 4 3(⅔) = +2 6
Z 40/3 740 3(40/3) = +40 780

For an increase in storage space of 8 cubic feet, we take the upper limit of 4.5 cubic
feet for the computation. The resulting revised figures, then, would be s1= 0, x1=7.5,
x2=7, and Profit =800.

2.5.2. A Change in an Objective Function Coefficient

– A value of the objective function coefficient that falls within the range of
optimality will not change the optimal solution, although the optimal value of
the objective function will change
– 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 and
For both maximization and minimization problems, Range of optimality calculated as
follows:
– The values in Cj - Zj row must be divided by the corresponding row values of
the variable in question. This will result in a series of ratios.

Allowable increase: The smallest positive ratio of C-Z value and the
variable’s substitution rate.
Allowable decrease: the smallest negative ratio of C-Z value and the

variable’s substitution rate.

Page 43
  Range of optimality is calculated for only on decision variables because slack/surplus
variables and artificial variables do not have any contribution for the objective
function.
Example
Min Z = 10X1 + 3X2
Subject to:
2X1 + X2 ≥80
X1 + 4X2 ≥ 200
X1 and X2 ≥ 0

? Dear learner, would you try to determine the range over which coefficient of Xin 2

the objective function change without changing the solution mix in the same way as
above?
______________________________________________________________________

 Activity
1. AYKA Addis Textile Company obtains the following information from its production
department. The company will produce and export different clothes to various countries. The
following LPP model is found so as to maximize the total profit of the company
Maximize Z = 50X1 + 60X2
Subject to
10X1+4X2 ≤ 150 – Labor hour

Page 44
 3X1+ 4X2 ≤ 60 – Production time/week
X1 + 2X2 ≤ 44 – Capital
X1, X2 ≥ 0
With this LPP the company has the following final simplex tableau which provides optimum
profit;

50 60 0 0 0
Cj P. Mix Quantity X1 X2 S1 S2 S3
50 X1 90/7 1 0 1/7 -1/7 0
60 X2 75/14 0 1 -3/28 5/14 0
0 S3 143/7 0 0 1/14 -4/7 1
Zj 6750/7 50 60 5/7 100/7 0
Cj – Z j - 0 0 -5/7 -100/7 0

After this, the General Manager of the company obtain recent market information and
planned to introduce new changes which is vital to maximize the total profit beyond the
current level. The planned change will be increasing the level of total production time per
week of the company by 10 hours (i.e. RHS value of the second constraint).

Required
a) Find out the shadow pries from the above table.

b) Compute the upper limit, lower limit and range of feasibility by doing sensitivity analysis
whether the planned change is favorable or not?
c) Find out the Dual form of the above Primal linear programming problem.
d) Find the revised solution if AYKA Addis Textile Company wants to increase labor hour
by 2hr.

Page 45
 CHAPTER THREE
4. TRANSPORTATION AND ASSIGNMENT MODELS
Unit objectives:
Up on completion of this unit, you will be able to:
 Differentiate between linear programming and transportation and assignment models
 Explain advantages of transportation and assignment models
 Identify different techniques to find solution for both transportation and assignment
models.
 Discuss special cases in transportation and assignment models

3.1. Transportation Models

Sub section objectives
Up on completion of this section, the learner will be able to:
 Explain transportation models
 Identify application areas of transportation models
 Formulate LP model for transportation problems
 Describe methods of finding initial feasible solution
 Check for optimality of transportation model using stepping stone and MODI
techniques.
 Elucidate special cases in transportation models

Introduction
Dear learner, in the previous chapter we have been thoroughly discussed about LP models
and their applications. In this chapter we will try to see special types of LP models which are
Transportation and Assignment Models. Though it is possible to solve the two problems
using simplex method, the process would result in rather large simplex tableaus and
numerous simplex iterations. Because of the unique characteristics of each problem, however,
alternative solutions methods requiring considerably less mathematical computation than the
simplex method have been developed.

The purpose of using an LP model for transportation problems is to minimize transportation

costs, taking into account the origin supplies, the destination demands, and the transportation
costs. The transportation method is similar in certain respects to the simplex technique
because both involve an initial feasible solution that is evaluated to determine if it can be
improved. Moreover, both involve displaying initial and improved solutions in a series of
tableaus or tables. However, the transportation method requires considerably less
computational effort. In addition, it is not unusual to discover that the initial feasible solution
in a transportation problem is the optimum. Examples of transportation problems include
shipments from warehouses to retail stores, shipment from factories to warehouses,
shipments between departments within a company, and production scheduling.

Page 46
3.1.1 FORMULATING THE MODEL
A transportation problem typically involves a set of sending locations, which are referred to
as origins, and a set of receiving locations, which are referred to as destinations. In order to
develop a model of a transportation problem, it is necessary to have the following
information:
a. Supply quantity (capacity) of each origin.
b. Demand quantity of each destination.
c. Unit transportation cost for each origin-destination route.
Assumptions
The transportation algorithm requires the assumption that:
 All goods be homogeneous, so that any origin is capable of supplying any destination,
and
 Transportation costs are a direct linear function of the quantity shipped over any
route.
 Though it will be modified later in our discussion, we shall add one additional
requirement that the total quantity available is equal to the total demand.
Example
Let’s consider an example. Harley’s Sand and Gravel Pit has contracted to provide topsoil
for three residential housing developments. Topsoil can be supplied from three different
“farms” as follows:
Farm Weekly capacity (cubic yards)
A 100
B 200
C 200
Demand for the topsoil generated by the construction projects is:
Project Weekly demand(cubic yards)
1 50
2 150
3 300
The manager of the sand and gravel pit has estimated the cost per cubic yard to ship over
each of the possible routes:
Cost per cubic yard to
From Project #1 Project #2 Project #3
Farm A Birr4 Birr 2 Birr 8
Farm B 5 1 9
Farm C 7 6 3
This constitutes the information needed to solve the problem.

The next step is to arrange the information into a transportation table. This is shown in the
following table.
Transportation table for Harley’s sand and gravel
To:
From: Projec Project Project Supply
From: t #1 #2 #3
4 2 8
Farm A 100

5 1 9
Farm B 200

Page 47
 7 6 3
Farm C 200

Demand 50 150 300

Note: It is possible to write this transportation problem in the form of LPM.
Nine ( 3x3) decision variables are there and the objective function is minimization.

LPM for this problem is:

Zmin: 4x11 + 2x12 +8x13 + 5x21 + x22 + 9x23 + 7x31 + 6x32 + 3x33
Subject to:
X11 + x12 +x13 ¿ 100
X21 + x22 + x23¿ 200 Capacity/ Source constraint
X31 + x32 + x33¿ 200

X11 + x21 + x3 1¿ 50
X12 + x22 +x32¿ 150 Demand/Destination contraint
X13 + x23 + x33¿ 300

3.1.2. FINDING AND INITIAL FEASIBLE SOLUTION

The starting point of the transportation method is a feasible solution. For an assignment to be
feasible, two conditions must be fulfilled:
 A feasible solution is one in which assignments are made in such a way that all
supply and demand requirements are satisfied.
 The number of nonzero (occupied) cells should equal one less than the sum of
the number of rows and the number of columns in a transportation table. In the
case of a table with 3 rows and 3 columns, the number of occupied cells should
be 3 + 3 -1 = 5 in order to be able to use the transportation algorithm.
Sometimes, fewer occupied or completed cells appear in a solution. When that
happens, the solution is referred to as a degenerated solution; such a solution
requires modification in order to be able to determine if it is optimal. This topic
will be covered later on.
A number of different approaches can be used to find an initial feasible solution. Three of
these are described here:
The northwest-corner method.
An intuitive approach/Least cost method
Vogel’s / Penalty Method

3.1.2.1. The Northwest-Corner Method

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

The northwest corner method gets its name because the starting point for the allocation
process is the upper left-hand (Northwest) corner of the transportation table. For the Harley
problem, this would be the cell that represents the route from Farm A to Project #1. The
following set of principles guides the allocation:

Page 48
 i. Begin with the upper left-hand cell, and allocate as many units as possible to
that cell. This will be the smaller of the row supply and the column demand.
Adjust the row and column quantities to reflect the allocation.
ii. Remain in a row or column until its supply or demand is completely exhausted
or satisfied, allocating the maximum number of units to each cell in turn, until
all supply has been allocated (and all demand has been satisfied because we
assume total supply and demand are equal).
Initial Feasible Solution for Harley using Northwest-corner method
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
Farm A 50 50 100
(first) (second)
5 1 9
Farm B 100 100 200
(third) (fourth)
7 6 3
Farm C 200 200
(last)

Demand 50 150 300 500

The total cost is found by multiplying the quantities in “completed” (i.e. nonempty) cells by
the cell’s unit cost and, then, summing those amounts. Thus:

Total cost = 50(4) + 50(2) + 100(1) + 100(9) + 200(3) = $1900

As noted earlier, the main drawback of the northwest-corner method is that it does not
consider cell (route) costs in making the allocation. Consequently, if this allocation is
optimal, that can be attributed to chance rather than the method used.

3.1.2.2. The Intuitive Approach

This approach, also known as the least cost method, uses lowest cell cost as the basis for
selecting routes. The procedure is as follows:
i. Identify the cell that has the lowest unit cost. If there is a tie, select one arbitrarily.
Allocate a quantity to this cell that is equal to the lower of the available supply for
the row and the demand for the column.
ii. Cross out the cells in the row or column that has been exhausted (or both, if both
have been exhausted), and adjust the remaining row or column total accordingly.
iii. Identify the cell with the lowest cost from the remaining cells. Allocate a quantity
to this cell that is equal to the lower of the available supply of the row and the
demand for the column.
iv. Repeat steps (ii) and (iii) until all supply and demand have been exhausted.

The initial feasible solution for the Harley problem completed using the above steps is shown
below.

Page 49
Initial Feasible Solution for the Harley problem using the Intuitive approach

To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
Farm A 50 50 100

5 1 9
Farm B 150 50 200

7 6 3
Farm C 200 200

Demand 50 150 300 500

We can easily verify that this is a feasible solution by checking to see that the row and
column totals of the assigned cell quantities equal the supply and demand totals for the rows
and columns. Now let us compute the total cost of this solution and compare it to that of the
northwest corner solution.
Total cost = 50(4) + 50(8) + 150(1) + 50(9) + 200(3) = $1800

Compared to the plan generated using the Northwest-corner method, this one has a total cost
that is $100 less. This is due to the fact that the previous one did not involve the use of cost
information in allocating units.

3.1.2.3. Vogel’s Approximation Method (VAM)

The third method for determining an initial solution, Vogel’s Approximation Method (also
called VAM), is based on the concept of penalty cost or regret. If a decision maker
incorrectly chooses from several alternative courses of action, a penalty may be suffered (and
the decision maker may regret the decision that was made). In transportation problem, the
courses of action are the alternative routes and a wrong decision is allocating to a cell that
does not contain the lowest cost.

This method is preferred over the other two methods because the initial feasible solution
obtained with VAM is either optimal or very close to the optimal. With VAM the basis of
allocation is unit cost penalty i.e. that column or row which has the highest unit cost penalty
(difference between the lowest and the next highest cost) is selected first for allocation and
the subsequent allocations in cells are also done keeping in view the highest unit cost penalty.
Steps in VAM
1. Construct the cost, requirement, and availability matrix i.e. cost matrix with column
and row information.

Page 50
 2. Compute a penalty for each row and column in the transportation table. The penalty is
merely the difference between the smallest cost and the next smallest cost element
in that particular row or column.
3. Identify the row and column with the largest penalty. In this identified row (column),
choose the cell which has the smallest cost and allocate the maximum possible
quantity to this cell. Delete the row (column) in which capacity (demand) is
exhausted. When there is a tie for penalty, select one arbitrarily. After allocation,
cross that row or column and disregard it from further consideration.
4. Repeat steps 1 to 3 for the reduced table until the entire capabilities are used to fill the
requirement at different warehouses.
5. From step 4 we will get initial feasible solution. Now for initial feasible solution find
the total cost.
The solution for our problem is as follows:
To: Penalty
From: Project Project Projec Supply Hc NHC Hc- NHC
#1 #2 t #3
4 2 8
Farm A 100
8 4 4
5 1 9
Farm B 150 200
9 5 4 selected
1
7 6 3
Farm C 200
7 6 1

Deman 50 150 300

d

NHC 5 2 8
Penalt 2 4 1
HC: Highest cost
NHC: Next Highest cost

Table2 Penalty
To: Hc NHC Hc- NHC
From: Project Project Project #3 Supply
#1 #2
4 2 8
8 4 4
Farm A 100
9 5 4
5 1 9
Farm B 150 200 50
7 3 4 selected
7 6 3
Farm C 200 200
2

Demand 50 150 300 100 Penalty 2 - 1

Second allocation

Page 51
 Table 3
Third To:
From: Project Project Project #3 Supply Penalty
allocation 4 #1 #2 selected
4 2 8
Farm A 50 100 50
Penalty 1 - 1
5 1 9
Farm B 150 200 50

7 6 3
Farm C 200 200

Demand 50 150 300 100

Table 4
Since there is no penalty for the remaining cells, we allocate for these cells according to their
cost.
To:
From: Project Project Project #3 Supply
#1 #2
4 2 4 8
Farm A 50 50 100
50 Fourth allocation
5 1 50 9
Farm B 150
5 200
50
7 6 3
Farm C 200 200

Demand 50 150 300 100 50 Fifth allocation

Therefore the final allocation
will be:
To:
From: Project Project Project #3 Supply
#1 #2
4 2 4 8
Farm A 50 50 100

5 1 50 95
Farm B 150 200

7 6 3
Farm C 200 200

Demand 50 150 300 Page 52

Total cost: 1x150 + 3x200+4x50 + 8x50 + 9x50
= Birr 1800

3.1.3. Evaluating a Solution for Optimality

The test for optimality for a feasible solution involves a cost evaluation of empty cells (i.e.,
routes to which no units have been allocated) to see if an improved solution is possible. We
shall consider two methods for cell evaluation:
The Stepping-stone method
The MODI method

The stepping-stone method involves a good deal of more effort than the MODI method.
However, it provides an intuitive understanding of the evaluation process. Moreover, when a
solution is not optimal, the distribution plan must be revised by reallocating units into and out
of various cells, and only the stepping-stone method can be used for the reallocation.

3.1.3.1. The Stepping-stone method

The Stepping-stone method involves tracing a series of closed paths in the transportation
table, using one such path for each empty cell. The path represents a shift of one unit into an
empty cell, and it enables the manager or analyst to answer a “what-if” question: What
impact on total cost would there be if one unit were shifted into an unused route? The result is
a cost change per unit shifted into a cell. If the shift would result in a cost savings, the
stepping-stone path also can be used to determine the maximum number of units that can be
shifted into the empty cell, as well as modifications to other completed cells needed to
compensate for the shift into the previously unused cell.

Reconsider the initial feasible solution we found using the northwest-corner method. Only the
unoccupied cells need to be evaluated because the question at this point is not how many
units to allocate to a particular route but only if converting a cell from zero units to nonzero
(a positive integer) would decrease or increase total costs. The unoccupied cells are A-3, B-1,
C-1, and C-2. They must be evaluated one at a time, but in no particular order.

Rules for tracing Stepping-stone paths:

i. All unoccupied cells must be evaluated. Evaluate cells one at a time.
ii. Except for the cell being evaluated, only add or subtract in occupied cells. (It is
permissible to skip over unoccupied cells to find an occupied cell from which the path
can continue.)
iii. A path will consist of only horizontal and vertical moves, starting and ending with the
empty cell that is being evaluated.
iv. Alter + and – signs, beginning with a + sign in the cell being evaluated.

 Note that it is not necessary to actually alter the quantities in the various cells to reflect
the one-unit change, the + and – signs suffice.

Page 53
The general implication of the plus and minus signs is that cells with + signs mean one unit
would be added, cells with a – sign indicate one unit would be subtracted. The net impact of
such a one-unit shift can be determined by adding the cell costs with signs attached and
noting the resulting value. Thus, for cell B-1, we have a net change of +2 (i.e., 5+2-4-1)
which means that for each unit shifted into cell B-1, the total cost would increase by $2.

Computed in similar way, the evaluations of cells C-1, A-3, and C-2 result in +10, -2, and
+11 respectively. The negative value for cell A-3 indicates an improved solution is possible:
For each unit we can shift into that cell, the total cost will decrease by $2. The following table
shows how empty cell C-1 can be evaluated using the Stepping stone method.

Evaluation path for cell C-1

To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
Farm A 50 50 100
–- +
5 1 9
Farm B 100 100 200
– +
7 6 3
Farm C + – 200 200

Demand 50 150 300 500

3.1.3.2. The MODI method

The MODI (Modified Distribution) method of evaluating a transportation solution for
optimality involves the use of index numbers that are established for the rows and columns.
These are based on the unit costs of the occupied cells. The index numbers can be used to
obtain the cell evaluations for empty cells without the use of stepping-stone paths.

There is one index number for each column and one for each row. These can be conveniently
displayed along the left and upper edges of a matrix. The index numbers are determined in
such away that for any occupied cell, the sum of the row index and the column index equal
the cell’s unit transportation cost:

Row index + Column index = Cell cost

ri + kj = cij

The index numbers are determined sequentially in a manner dictated by the position of
occupied cells. The process always begins by assigning a value of zero as the index number
of row 1.
The method will be illustrated by developing index numbers for the initial feasible solution
for the Harley problem generated by the northwest-corner method. We begin assigning a
value of zero for row 1. Once a row index has been established, it will enable us to compute

Page 54
column index numbers for all occupied cells in that row. Similarly, once a column index
number has been determined, index numbers for all rows corresponding to occupied cells in
that column can be determined. The complete set of row and column index numbers is shown
in the following table.
Cell evaluations for Northwest Corner solution for the Harley Problem using the MODI
method
k1 k2 k3
+4 +2 +10
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
r1 0 Farm A 50 50 100
-2
5 1 9
r2 -1 Farm B 100 100 200

+2
7 6 3
r3 -7 Farm C 200 200

Demand 50 150 300 500

+10 +11

The cell evaluations (improvement potentials) for each of the unoccupied cells are
determined using the relationship:
Cell evaluation = Cell cost – Row index – Column index
eij = cij – ri – kj

For example, the cell evaluations for A-3 is 8 – 0 – 10 = -2. Similarly, the evaluation for B-1
is +2, for C-1, +10, and for C-2, it is +11. Note that they agree with the values we computed
earlier using the stepping-stone method.

When cell evaluations are positive or zero, an optimal solution has been found. If one or more
is negative, the cell with the largest negative should be brought into solution because that
route has the largest potential for improvement per unit. In this case, we found that cell A-3
had an evaluation of –2, which represented an improvement potential of $2 per unit. Hence,
an improved solution is possible.

3.1.3.2.1. DEVELOPING AN IMPROVED SOLUTION

Developing an improved solution to a transportation problem requires focusing on the
unoccupied cell that has the largest negative cell evaluation. Improving the solution involves
reallocating quantities in the transportation table. More specifically, we want to take
advantage of the improvement potential of cell A-3 by transferring as many units as possible
into that cell. The stepping-stone path for that cell is necessary for determining how many
units can be reallocated while retaining the balance of supply and demand for the table. The
stepping-stone path also reveals which cells must have quantity changes and both the
magnitude and direction of changes. The + signs in the path indicate units to be added, the –
signs indicate units to be subtracted. The limit on subtraction is the smallest quantity in a
negative position along the cell path. With each iteration (new solution), it is necessary to

Page 55
 evaluate the empty cells to see if further improvement is possible. This requires use of either
the MODI or the Stepping-stone method. Both will yield the same values.
After reallocating the units using the stepping stone method, the empty cells will be A-2, B-1,
C-1 and C-2. Suppose we use the MODI method for evaluation. After assigning all the row
and column indices, we find the cell evaluations to be as follows:

Cell A-2: 2 – 0 – 0 = +2
Cell B-1: 5–1–4= 0
Cell C-1: 7-(-5)- 4 = +8
Cell C-2: 6-(-5)- 0 = +11

Because none of these numbers is negative, this is an optimal solution. You may recall that
this was the same solution obtained using the intuitive method for the initial feasible solution.
At that point, it was determined that the total cost for the distribution plan was $1800.

Optimal Solution for the Harley problem

+4 0 +8
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
+2
0 Farm A 50 50 100

5 1 9
+1 Farm B 0 150 50 200

7 6 3
-5 Farm C +8 +11 200 200

Demand 50 150 300 500

? Dear learner, which of the two approaches for improvement is lengthy and
difficulty to use?
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________

3.1.4. SPECIAL ISSUES

There are a number of special issues in relation to the transportation model. They are:
i. Determining if there are alternate optimal solutions.
ii. Defining and handling degeneracy (too few occupied cells to permit evaluation of a
solution).
iii. Avoiding unacceptable or prohibited route assignments.
iv. Dealing with problems in which supply and demand are not equal.
v. Solving maximization problems.

1. Alternate Optimal Solutions

Page 56
 Sometimes, transportation problems have multiple optimal solutions. In such instances, it can
be useful for a manager to be aware of alternate solutions, because this gives the manager an
option of bringing non-quantitative considerations into the decision.

In the case of the transportation problem, the existence of an alternate solution is signaled by
an empty cell’s evaluation equal to zero. In fact, you may have noted that cell B-1 had an
evaluation equal to zero in the final solution of the Harley problem. We can find out what that
alternate solution is by reallocating the maximum number of units possible around the
stepping-stone path for that cell. After the cell evaluation of, and reallocating units to cell B-
1, we find the following table to be an alternate optimal solution.
Alternate optimal solution for the Harley problem

To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
Farm A 100 100

5 1 9
Farm B 50 150 200

7 6 3
Farm C 200 200

Demand 50 150 300 500

2. Degeneracy
A solution is degenerate if the number of occupied cells is less than the number of rows plus
the number of columns minus one. i.e., there are too few occupied cells to enable all the
empty cells to be evaluated. In the case of the stepping-stone method, this means that there
will be at least one empty cell for which an evaluation path cannot be constructed. For the
MODI method, it means that it will be impossible to determine all of the row and column
index numbers. Obviously, some modification has to be made to determine if such a
degenerate solution is optimal. The modification is to treat some of the empty cells as
occupied cells. This is accomplished by placing a delta () in one of the empty cells. The
delta represents an extremely small quantity (e.g., 0.001 unit); it is so small that supply and
demand for the row and column involved will be unaffected even without modifying other
quantities in the row or column, and so small that total cost will not change.

The purpose of the delta is to enable evaluation of the remaining empty cells. The choice of
location for the delta can be somewhat tricky: some empty cells may be unsuitable if they do
not enable evaluations of the remaining empty cells. Moreover, the delta cannot be placed in
a cell which later turns out to be in a negative position of a cell path involved in reallocation
because delta will be the “smallest quantity in a negative position” and shifting that minute
quantity around the cell path will leave the solution virtually unchanged. Consequently, a
certain amount of trial and error may be necessary before a satisfactory location can be
identified for delta.

Page 57
 The technique can be demonstrated for the degenerate alternate solution of the Harley
problem. Suppose that after some experimentation, cell A-1 has been selected for the location
of delta. The resulting index numbers generated using MODI and the improvement potential
for empty cells based on delta in cell A-1 are shown in the following table. This confirms that
the solution is optimal

Harley Alternate Solution Modified for Degeneracy

+4 0 +8
To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
+2
0 Farm A Δ 100 100

5 1 9
+1 Farm B 50 150 0 200

7 6 3
-5 Farm C +8 +11 200 200

Demand 50 150 300 500

3. Unacceptable Routes
In some cases, an origin-destination combination may be unacceptable. This may be due to
weather factors, equipment breakdowns, labor problems, or skill requirements that either
prohibit, or make undesirable, certain combinations (routes).

Suppose that in the Harley problem route A-3 was suddenly unavailable because of recent
flooding. In order to prevent that route from appearing in the final solution (as it originally
did), the manager could assign a unit cost to that cell that was large enough to make that route
uneconomical and, hence, prohibit its occurrence. One rule of thumb would be to assign a
cost that is 10 times the largest cost in the table (or a very big +M). Then, this revised
problem could be solved using either of the methods we have discussed earlier. Note that the
prohibited route may appear in a non-optimal solution, but it will be eliminated by the time
the optimal solution is reached.

Dear learner, would you find the optimal solution if route A-3 is not available? How do you
compare the cost with the original cost?

4. Unequal Supply and Demand

Up to this point, examples have involved cases in which supply and demand were equal. As
you might guess, there are situations in which the two are not equal. When such a situation is
encountered, it is necessary to modify the original problem so that supply and demand are
equal. This is accomplished by adding either a dummy column or a dummy row; a dummy
row

is added if supply is less than demand and a dummy column is added if demand is less than
supply. The dummy is assigned unit costs of zero for each cell, and it is given a supply (if a

Page 58
 row) or a demand (if a column) equal to the difference between supply and demand.
Quantities in dummy routes in the optimal solution are not shipped. Rather, they serve to
indicate which supplier will hold the excess supply, and how much, or which destination will
not receive its total demand, and how much it will be short.

Let’s consider an example. Suppose that Farm C in the Harley problem has experienced an
equipment breakdown, and it will be able to supply only 120 cubic yards of topsoil for a
period of time. Therefore, total supply will be 80 units less than total demand. This will
require adding a dummy origin with a supply of 80 units. The final solution is shown in the
following table. We interpret the solution indicating that Project #3 will be short by 80 units
per week until the equipment is repaired. Note, though, that this analysis has considered only
transportation costs, and that other factors, such are shortage costs or schedules of the
projects, may dictate some other course of action.

If the intuitive approach is used to obtain the initial feasible solution when a dummy is
involved, make assignments to the dummy last. Hence, begin by assigning units to the cell
with the lowest nonzero cost, then the next lowest nonzero cost, and so on. For the Harley
problem this would mean that units would be assigned first to cell B-2 because its cost of $1
is the lowest nonzero cell cost.

Solution using the Dummy Origin

To:
Project Project Project Supply
From: #1 #2 #3
4 2 8
Farm A 50 50 100

5 1 9
Farm B 150 50 200

7 6 3
Farm C 120 120

0 0 0
Dummy 80 80

Demand 50 150 300 500

? Dear learner, would you complete the above case by evaluating the assignments? What
would assignments in the dummy row or column in the optimal solution indicate?
_______________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________

5. Maximization of transportation problem

Some transportation type problems concern profits or revenues rather than costs. In such
cases, the objective is to maximize rather than to minimize. Such problems can be handled by
adding one additional step at the start: Identify the cell with the largest profit and subtract all

Page 59
 the other cell profits from that value. Then replace the cell profits with the resulting values.
These values reflect the opportunity costs that would be incurred by using routes with unit
profits that are less than the largest unit profit. Replace the original unit profits with these
opportunity cost solution. This will be identical to maximizing the total profit. For example,
suppose in the Harley problem, the cell values had been unit profits instead of unit costs. Cell
B-3 had the largest dollar value: $9. Hence, each cell’s dollar amount would be subtracted
from 9. For cell A-1, the resulting opportunity cost would have been 9-4 = 5 and so on. Cell
B-3 would have an opportunity cost of 0 making it the most desirable route.

The remainder of the steps for developing an initial feasible solution, evaluation of empty
cells, and reallocation are identical to those used for cost minimization. When the optimal
distribution plan has been identified, use the original cell values (i.e., profits) to compute the
total profit for that plan.

? Dear learner, would you complete the above case by evaluating the assignments?
Which one would you consider the original price or opportunity cost of each cell to
calculate the total profit in the optimal solution?
_____________________________________________________________________

ACTIVITY
_____________________________________________________________________

1. A transportation problem involves the following costs, supply, and demand.

To
From 1 2 3 4 Supply
1 $5 750 300 450 12
2 00 800 400
65 600 17
0
40
3 700 500 550 11
0
Demand 10 10 10 10

a. Find the initial solution using the northwest corner method, the minimum cell
cost method, and Vogel's Approximation Method. Compute total cost for each.
a. Using the VAM initial solution, find the optimal solution using the modified
distribution method (MODI).
2. Oranges are grown, picked, and then stored in warehouses in Tampa, Miami, and
Fresno. These warehouses supply oranges to markets in New York, Philadelphia,
Chicago, and Boston. The following table shows the shipping costs per truckload
($100s), supply, and demand.

To
From New York Philadelphia Chicago Boston Supply
Tampa 9 14 12 17 200
Miami 11 10 6 10 200
Fresno 12 8 15 7 200
Demand 130 170 100 150
Because of an agreement between distributors, shipments are prohibited from Miami to

Page 60
Chicago.
a. Set up the transportation tableau for this problem and determine the initial solution
using the minimum cell cost method.
b. Solve using MODI.
c. Are there multiple optimum solutions? Explain. If so, identify them.

3.2. ASSIGNMENT PROBLEMS

Section objectives:
Up on completion of this section, the learner will be able to:
 Define assignment model
 Formulate LP model for assignment problems
 Identify areas of application
 Find optimal allocation or solution to the model
 Deal with special cases of the model

? Dear learner, can you make any difference between assignment and transportation
problems?
___________________________________________________________________________
___________________________________________________________________________
There are many situations where the assignment of people or machines and so on, may be
called for. Assignment of workers to machines, clerks to various counters, salesmen to
different sales areas, service crews to different districts, are typical examples of these. The
assignment is a problem because people posses varying abilities fro performing different jobs
and, therefore, the costs of performing the jobs by different people are different. Obviously, if
all persons could do a job in the same time or at the same cost then it would not matter who
of them is assigned the job. Thus, in assignment problem, the question is how should the
assignment be made in order that the total cost involved is minimized (or the total value is
maximized when pay-offs are given in terms of, say, profits).

A typical assignment problem follows:

Example
A production supervisor is considering how he should assign the four jobs that are
performed, to four of the workers working under him. He want to assign the jobs to the
workers such that the aggregate time to perform the job in the least. Based on the
previous experience, he has the information on the time taken by the four workers in
performing these jobs, as given in below
Job
Worker A B C D
1 45 40 51 67
2 57 42 63 55
3 49 52 48 64
4 41 45 60 55

Page 61
3.2.1. THE ASSIGNMENT PROBLEM (A.P)
The Assignment Problem (A.P) is a special case of Transportation Problem (T.P) under
the condition that the number of origins is equal to the number of destinations,
i.e. m=n
Hence assignment is made on the basis of 1:1
Number of jobs equal to number of machines or persons.
Each man or machine is loaded with one and only one job.
Each man or machine is independently capable of handling any of the jobs
being presented.
Loading criteria must be clearly specified such as “ minimizing operating
time or “ maximizing profit”, or “ minimizing production cost” or
minimizing production cycle time e.t.c
The Assignment Problem (A.P.) is a special case of Transportation Problem (T.P.) in which
the number of sources and destinations are the same, and the objective is to assign the given
job (task) to most appropriate machine (person) so as to optimize the objective like
minimizing cost.
General Assignment Problem Table
.
M 1 2 3 … k … n
J
1 C11 C12 C13 … C1k … C1n
2 C21 C22 C23 … C2k … C2n
3 C31 C32 C33 … C3k … C3k
… … … … … … … …
K Ck1 Ck2 Ck3 … Ckk … Ckn
… … … … … … … …
N Cn1 Cn2 Cn3 … Cnk … Cnn

Effective Matrix
A cost Matrix in A.P. is called an “Effectiveness Matrix” when there is at
least one zero in each row and column. Following is an example of
Effectiveness Matrix.

1 2 3 4
1 0 1 3 4
2 5 0 6 0
3 7 8 0 9
4 0 4 3 8

3.2.3. HUNGARIAN ASSIGNEMNT METHOD (HAM)

A method, designed specially to handle the assignment problems in an efficient way, called
the Hungarian Assignment Method, is available, which is based on the concept of opportunity
cost. It is shown in figure 6.1 and discussed here. For a typical balanced assignment problem
involving a certain number of persons and an equal number of jobs, and with an objective
function of the minimization type, the method is applied as listed in the following steps:

Page 62
Step 1. Locate the smallest cost element in each row of the cost table. Now subtract this
smallest from each element in that row. As a result, there shall be at least one zero
in each row of this new table, called the Reduced Cost Table (Row Reduction).
Step 2. In the reduced cost table obtained, consider each column and locate the smallest
element in it. Subtract the smallest value from every other entry in the column. As
a consequence of this action, there would be at least one zero in each of the rows
and columns of the second reduced cost table (Column Reduction).
Step 3. Draw the minimum number of horizontal and vertical lines (not diagonal ones) that
are required to cover the entire ‘zero’ elements. If the number of lines drawn is
equal to n (the number of rows/columns) the solution is optimal, and proceeds to
step 6. If the number of lines drawn is smallest than n, go to step 4.
Step 4. Select the smallest uncovered (by the lines) cost element. Subtract this element from
all uncovered elements including itself and add this element to each value located
at the intersection of any lines. The cost elements through which only one line
passes remain unaltered.
Step 5. Repeat steps 3 and 4 until an optimal solution is obtained.
Step 6. Given the optimal solution, make the job assignments as indicated by the ‘zero’
elements. This done as follows:
a) Locate a row which only ‘zero’ element. Assign the job corresponding to this element
to its corresponding person. Cross out the zero’s, if any, in the column corresponding
to the element, whish is indicative of the fact that the particular job and person are no
more available.
b) Repeat (a) for each of such rows which contain only one zero. Similarly, perform the
same operation in respect of each column containing only one ‘zero’ element,
crossing out the zero(s), if any, in the row in which the element lies.
c) If there is no row or column with only a single ’zero’ element left, then select a
row/column arbitrarily and choose one of the jobs (or persons) and make the
assignment. Now cross the remaining zeros in the column and row in respect of which
the assignment is made.
d) Repeat steps (a) through (c) until all assignments are made.
e) Determine the total cost with reference to the original cost table.
Example
Solve the assignment problem given in Illustrative Example 1 for optimal solution using
HAM. The information is reproduced in the following table
Time Taken (in minutes) by 4 workers
Job
Worker A B C D
1 45 40 51 67
2 57 42 63 55
3 49 52 48 64
4 41 45 60 55

The solution to this problem is given here in a step-wise manner.

Step 1: The minimum value of each row is subtracted from all elements in the row. It is
shown in the reduced cost table, also called opportunity cost table, given as follows.
Reduced Cost Table 1

Page 63
 Job
Worker A B C D
1 5 0 11 27
2 15 0 21 13
3 1 4 0 16
4 0 4 19 14
Step 2: For each column of this table, the minimum value is subtracted from all the other
values. Obviously, the columns that contain a zero would remain unaffected by this
operation. Here only the fourth column values would change. The table below shows this.
Reduced Cost Table 2
Job
Worker A B C D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1

Step 3: Draw the minimum number of lines covering all zeros. As a general rule, we should
first cover those rows/columns which contain larger number of zeros. The above table is
reproduced in the next table and the lines are drawn.
Reduced Cost Table3
Job
Worker A B C D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1

Step 4: Since the number of lines drawn is equal to 4(=n), the optimal solution is obtained.
The assignments are made after scanning the rows and columns for unit zeros. Assignments
made are shown with squares, as shown in the following table.

Assignment of Jobs
Job
Worker A B C D
1 5 0 11 14
2 15 0 X 21 0
3 1 4 0 3
4 0 4 19 1
Assignments are made in the following order. Rows 1, 3, and 4 contain only one zero each. So assign
1-B, 3-C and 4-A. Since worker 1 has been assigned job B, only worker 2 and job E are left for
assignment. The final pattern of assignments is 1-B, 2-D, 3-C, and 4-A, involving a total time of
40+55+48+41=184 minutes. This is the optimal solution to the problem-the same as obtained by
enumeration and transportation methods.
Example
Using the following cost matrix, determine (a) optimal assignment, and (b) the cost of
assignments.
Reduced Cost Table 1

Page 64
 Job
Machinist 1 2 3 4 5
A 10 3 3 2 8
B 9 7 8 2 7
C 7 5 6 2 4
D 3 5 8 2 4
E 9 10 9 6 10

Iteration 1: Obtain row reductions.

Reduced Cost Table 1
Job
Machinist 1 2 3 4 5
A 8 1 1 0 6
B 7 5 6 0 5
C 5 3 4 0 2
D 1 3 6 0 2
E 3 4 3 0 4

Iteration 2: Obtain column reductions and draw the minimum number of lines to cover all zeros.
Reduced Cost Table2
Job
Machinist 1 2 3 4 5
A 7 0 0 0 4
B 6 4 5 0 3
C 4 2 3 0 0
D 0 2 5 0 0
E 2 3 2 0 2

Since the number of lines covering all zeros is less than the number of columns/rows, we
modify the Table 6.13. The least of the uncovered cell values is 2. This value would be
subtracted from each of the uncovered values and added to each value lying at the
intersection of lines (corresponding to cells A-4, D-4, A-5 and D-5). Accordingly, the new
table would appear as shown as follows.

Iteration 3

Job
Machinist 1 2 3 4 5
A 7 0 0 X 2 6
B 4 2 3 0 3
C 2 0 X 1 0 X 0
D 0 2 5 2 2
E 0 X 1 0 0 X 2

The optimal assignments can be made as the least number of lines covering all zeros in Table
6.14 equals 5. Considering rows and columns, the assignments can be made in the following
order:

Page 65
 i. Select the second row. Assign machinist B to job 4. Cross out zeros at cells C-4 and
E-4.
ii. Consider row 4, Assign machinist D to job 1. Cancel the zero at cell E-1.
iii. Since there is a single zero in the row, put machinist E to job 3 and cross out the zero at A-3.
iv. There being only a single left in each of the first and third rows, we assign job 2 to
machinist A and job 5 to C.
The total cost associated with the optimal machinist-job assignment pattern A-2, B-4, C-5, D-
1 and E-3 is 3+2+4+3+9 = 21

3.2.4. Special Issues

When we solve assignment problems, there are cases which are treated differently from the
usual way.

3. Unbalanced Assignment Problems

The Hungarian Method of solving an assignment problem requires that the number of
columns should be equal to the number of rows. They are equal, the problem is balanced
problem, and when not, it is called an unbalanced problem. Thus, where there are 5
workers and 4 machines, or when there are 4 workers and 6 machines, for instance, we
have unbalanced situations in which one-to-one match is not possible. In case the
machines are in excess, the excess machine(s) would remain idle and so is the case when
men are in excess- the number of excess people would get an assignment.

In such situations, dummy column(s)/row(s), whichever is smaller in number, are inserted

with zeros as the cost elements. For example, when the given cost matrix is of the
dimension 4*5, a dummy row would be included. In each column in respect of this row, a
‘zero’ would be placed. After this operation of introducing dummy columns/rows, the
problem is solved in the usual manner.
Example:
A company has 4 machines to do 3 jobs. Each job can be assigned to one and only one
machine. The cost of each job on each machine is given below. Determine the job
assignments which will minimize the total cost.
Machine
W X Y Z
A 18 24 28 32
4. Constrained/ Job
Prohibited/ B 8 13 17 18
Assignment C 10 15 19 22
Problems

It happens sometimes that a worker cannot perform a certain job or is not to be assigned a
particular job. To cope with this situation, the cost of performing that job by such person
is taken to be extremely large (which is written as M). Then the solution to the
assignment problem proceeds in the manner discussed earlier. The effect of assigning
prohibitive cost to such person-job combinations is that they do not figure in the final
solution.

Page 66
Example:
You are given the information about the cost of performing different jobs by different
persons. The job-person marking X indicates that the individual involved cannot perform
the particular job. Using this information, state (i) the optimal assignment of jobs, and (ii)
the cost of such assignment,

Job
J1 J2 J3 J4 J5
P1 27 18 X 20 21
person

P2 31 24 21 12 17
P3 20 17 20 X 16
P4 22 28 20 16 27

Solution: - Balancing the problem not assigning a high cost to the pairings P1-J3 and
P3-J4, we have the cost given in the table below.

Job
J1 J2 J3 J4 J5
P1 27 18 M 20 21
P2 31 24 21 12 17
P3 20 17 20 M 16
person

P4 22 28 20 16 27
P5 dummy 0 0 0 0 0

Now we can derive the reduced cost table as shown in table shown below. Note that the
cells with prohibited assignments continue to be shown with the cost element M, since M
is defined to be extremely large so that subtraction or addition of value does not
practically affect it. To test optimality, lines are drawn to cover all zeros. Since the
number of lines covering all zeros is less than n, we select the lowest uncovered cell,
which equals 4. With this value, we can obtain the revised reduced cost table, shown in
the final table.
Reduced Matrix

Job
J1 J2 J3 J4 J5
P1 9 0 M 2 3
P2 19 12 9 0 5
P3 4 1 44 M 0
person

P4 6 12 4 0 11
P5 0 0 0 0 0
dummy

Page 67
 Reduced Matrix
Job
J1 J2 J3 J4 J5
P1 9 0 M 2 3
P2 19 12 9 0 5
P3 4 1 4 M 0
person

P4 6 12 4 0 11
P5 0 0 0 0 0
dummy

Assignment of Job
Job
J1 J2 J3 J4 J5
P1 9 0 M 2 3
P2 15 8 9 0 1
P3 4 1 4 M 0
person

P4 2 8 0 0 X 7
P5 0 0X 0X 0 0 X
dummy

The number of lines covering zeros is equal to 5(=n), hence the optimal assignment can be
made. The assignment is: P1-J2, P2-J4, P3-J5, P4-J3, while job J1 would remain unassigned.
This assignment pattern would cost 18+12+16+20=66 in the aggregate.

5. Maximization Case in Assignment Problem

In some situations, the assignment problem may call for maximization of profit, revenue,
etc as the objective. For example, we may be faced with the problem of assignment of
salesmen in different regions in which they can display different qualities in making sales
(reflected in amounts of sales executed by them). Obviously, assignment would be made
in such a way that the total expected revenue is maximized.
For dealing with a maximization problem, we first change it into an equivalent
minimization problem. This is achieved by subtraction each of the elements of the given
pay-off matrix from a constant (value) k. Thus, we may simply put a negative sign before
each of the pay-off values (which is equivalent to subtracting each value from zero).
Usually, the largest value of all values in the given matrix is located and then each one of
the values is subtract from it (the largest value is taken so as to avoid the appearance of
negative signs). Then the problem is solved the same way as a minimization problem is.

Example:
A company plans to assign 5 salesmen to 5 districts in which it operates. Estimates of
sales revenue in thousands of birr for each salesman in different districts are given in the
following table. In your opinion, what should be the placement of the salesmen if the
objective is to maximize the expected sales revenue?

Page 68
 District
Salesman D1 D2 D3 D4 D5
S1 40 46 48 36 48
S2 48 32 36 29 44
S3 49 35 41 38 45
S4 30 46 49 44 44
S5 37 41 48 43 47

Solution: Since it is a maximization problem, we would first subtract each of the entries
in the table from the largest one, which equals 49 here. The resultant data are given in
Table below.

Opportunity Loss Matrix

District
Salesman D1 D2 D3 D4 D5
S1 9 3 1 13 1
S2 1 17 13 20 5
S3 0 14 8 11 4
S4 19 3 0 5 5
S5 12 8 1 6 2
Now, we will proceed as usual.

 Activity
1. A computer centre has got four Expert Programmers. Centre needs four application
programmers to be developed. The head of department, estimate the computer required by the
respective experts to develop the application programs as follows.

Program Expert A B C D
1 120 90 80 90
2 100 90 70 70
3 140 160 120 150
4 90 90 80 90

Required: Assign experts for each program application that will minimize the cost and
assignment.

2. A university department head has five instructors to be assigned to four different

courses. All of the instructors have taught the courses in the past and have been
evaluated by the students. The rating for each instructor for each course is given in the
following table (a perfect score is 100).

Page 69
 Course
Instructor A B C D
1 80 75 90 85
2 95 90 90 97
3 85 95 88 91
4 93 91 80 84
5 91 92 93 88

The department head wants to know the optimal assignment of instructors to courses
that will maximize the overall average evaluation. The instructor who is not assigned to
teach a course will be assigned to grade exams. Solve this problem using the assignment
method.

Page 70
 UNIT FOUR
4. DECISION THEORY/ANALYSIS
Unit objective:
After completing this unit, the learner should be able to:
 Describe the basic characteristics of decision theory problems
 Differentiate between decision analysis under certainty and uncertainty.
 Describe the different approaches (criteria) to decision making under complete
uncertainty.
1. Maximamax
2. Maximix
3. Minimax regret
4. Hurwicz
 Use decision tree as decision making tools.

? Dear learner, from your previous courses, can you define decision making? What
steps are involved in it? Can you mention conditions in which decision at different
levels are made?
______________________________________________________________________
______________________________________________________________________

Dear learner, in the previous units dealing with LP, models were formulated and solved in
order to aid the manager in making decision. The solutions to the models were represented by
values for the decision variables. However, these LP models are formulated under the
assumption that certainty existed. In actual practice, however, many decision making
situations occur under conditions of uncertainty. For example, the demand for a product may
be not 100 units next week, but 50 or 200 units, depending on the market (which is
uncertain).

4.1. Characteristics of Decision Theory

Decision theory problems are characterized by the following:
1. List of alternatives: are a set of mutually exclusive and collectively exhaustive
decisions that are available to the decision maker (some times, not always, one of
these alternatives will be to “do nothing”.)
2. States of nature: - the set of possible future conditions, or events, beyond the control
of the decision maker, that will be the primary determinants of the eventual
consequence of the decision. The states of nature, like the list of alternatives, must be
mutually exclusive and collectively exhaustive.
3. Payoffs: - the payoffs might be profits, revenues, costs, or other measures of value.
Usually the measures are financial. Usually payoffs are estimated values. The more
accurate these estimates, the more useful they will be for decision making purposes
and the more likely, it is that the decision maker will choose an appropriate
alternative. The number of payoffs depends on the number of alternative/state of
nature combination.

Page 71
 4. Degree of certainty: - the approach often used by a decision maker depends on the
degree of certainty that exists. There can be different degrees of certainty. One
extreme is complete certainty and the other is complete uncertainty. The later exists
when the likelihood of the various states of nature are unknown. Between these two
extremes is risk (probabilities are unknown for the states of nature). Knowledge of the
likelihood of each of the states of nature can play an important role in selecting a
course of active.
5. Decision criteria: - the decision maker’s attitudes toward the decision as well as the
degree of certainty that surrounds a decision. Example; maximize the expected
payoffs.

4.2. THE PAYOFF TABLE

A payoff table is a device a decision maker can use to summarize and organize
information relevant to a particular decision. It includes a list of alternatives, the possible
future states of nature, and the payoffs associated with each of the alternative/state of
nature combinations. If probabilities for the states of nature are available, these can also
be listed. The general format of the table is illustrated below:

States of nature
S1 S2 S3
A1 V11 V12 V13
Alternatives A2 V21 V22 V23
A3 V31 V32 V33

Ai = the ith alternative

Sj = the jth states of nature
Vij = the value or payoff that will be realized if alternative i is chosen and event j occurs.
Decision situations can be categorized in to three classes: Situation of certainty,
Situations where probabilities cannot be assigned to future occurrences and Situations
where probabilities can be assigned to future occurrences. In this chapter we will discuss
each of these classes of decision situations separately.

4.3. DECISION MAKING UNDER CERTAINTY

The simplest of all circumstances occurs when decision making takes place in an
environment of complete certainty. When a decision is made under conditions of
complete certainty, the attention of the decision maker is focused on the column in the
payoff table that corresponds to the state of nature that will occur. The decision maker
then selects the alternative that would yield the best payoff, given that state of nature.

EXAMPLE

The following payoff table provides data about profits of the various states of
nature/alternative combination.
S1 S2 S3
A1 4 16 12
A2 5 6 10
-1 4 15

Page 72
 A3

4.4. DECISION MAKING UNDER COMPLETE UNCERTAINTY (With out

probabilities)

Under complete uncertainty, the decision maker either is unable to estimate the
probabilities for the occurrence of the different state of nature, or else he or she lacks
confidence in available estimates of probabilities, and for that reason, probabilities are not
included in the analysis.
A decision making situation includes several components- the decision themselves and
the actual event that may occur future, known as state of nature. At the time the decision
is made, the decision maker is uncertain which state of nature will occur in the future, and
has no control over them.

Decisions made under these circumstances are at the opposite end of the spectrum from
the certainty case just mentioned. Once the decision has been organized in to a payoff
table, several criteria are available making the actual decision. There are several
approaches (criteria) to decision making under complete uncertainty. Some of these
discussed in this section include: maximax, maximin,minimax regret, Hurwicz, and equal
likelihood.

4.4.1. MAXIMAX

With the maximax criterion, the decision maker selects the decision that will result in the
maximum of the maximum payoffs.( In fact this is how this criterion derives its name-
maximum of maximum). That maximax is very optimistic. The decision maker assumes
that the most favorable state of nature for each decision alternative will occur. For
example, the investor would optimistically assume that good economic conditions will
prevail in the future. The best payoff for each alternative is identified, and the alternative
with the maximum of these is the designated decision.
For the previous problem:
S1 S2 S3 Row Maximum
A1 4 16 12 16*maximum
A2 5 6 10 10
A3 -1 4 15 15

Note: If the pay off table consists of costs instead of profits, the opposite selection would
be indicated: The minimum of minimum costs. For the subsequent decision
criteria we encounter, the same logic in the case of costs can be used.

? Dear learner, how would the decision in the above example change if the
values in the table stand for costs instead of profit?
_________________________________________________
_________________________________________________

Page 73
 4.4.2. Maximum Criteria

This approach is the opposite of the previous one, i.e. it is pessimistic. This strategy is a
conservative one; it consists of identifying the worst (minimum) payoff for each
alternative, and, then, selecting the alternative that has the best (maximum) of the worst
payoffs. In effect, the decision maker is setting a floor on the potential payoff by selecting
maximum of the minimum; the actual payoff can not be less than this amount. It involves
selecting best of the worst.

For the previous problem:

S1 S2 S3 Row minimum
A1 4 16 12 4
A2 5 6 10 5*maximum
A3 -1 4 15 -1

Note: If it were cost, the conservative approach would be to select the maximum cost
for each decision and select the minimum of these costs.

? Dear learner, how would the decision in the above example change if the
values in the table stand for costs instead of profit?
________________________________________________
________________________________________________

4.4.3. MINIMAX REGRET

Both the maximax and maximin strategies can be criticized because they focus only on a
single, extreme payoff and exclude the other payoffs. Thus, the maximax strategy ignores
the possibility that an alternative with a slightly smaller payoff might offer a better overall
choice. For example, consider this payoff table:
S1 S2 S3 Row Max.
A1 -5 16 -10 16*max
A2 15 15 15 15
A3 15 15 15 15
A similar example could be constructed to demonstrate comparable weaknesses of the
maximin criterion, which is also due to the failure to consider all payoffs.
An approach that does take all payoffs in to consideration is Minimax regret. In order to
use this approach, it is necessary to develop an opportunity loss table. The opportunity
loss reflects the difference between each payoff and the best possible payoff in a column
(i.e., given a state of nature). Hence, opportunity loss amounts are found by identifying
the best payoff in a column and, then, subtracting each of the other values in the column
from that payoff. Therefore, this decision avoids the greatest regret by selecting the
decision alternative that minimizes the maximum regret.

Page 74
 EXAMPLE:
S1 S2 S3
A1 4 16 12
A2 5 6 10
A3 -1 4 15

Opportunity loss table:

S1 S2 S3
A1 5-4=1 16-16=0 15-12=3
A2 5-5=0 16-6=10 15-10=5
A3 5-(-1)=6 16-4=12 15-15=0

The values in an opportunity loss table can be viewed as potential “regrets” that might be
suffered as the result of choosing various alternatives. A decision maker could select an
alternative in such a way as to minimize the maximum possible regret. This requires
identifying the maximum opportunity loss in each row and, then, choosing the alternative
that would yield the best (minimum) of those regrets.
S1 S2 S3 Max. Loss
A1 5-4=1 16-16=0 15-12=3 3*minimum
A2 5-5=0 16-6=10 15-10=5 10
A3 5-(-1)=6 16-4=12 15-15=0 12

Decision: A1 will be chosen.

? Dear learner, how would the decision in the above example change if the
values in the table stand for costs instead of profit?
_______________________________________________
_______________________________________________

Although this approach makes use of more information than either Maximin or Maximax,
it still ignores some information, and, therefore, can lead to a poor decision.
EXAMPLE:
Opportunity loss table
S1 S2 S3 S4 Max. Loss
A1 0 0 0 2 24
A2 4
A3 15 15 15 0 15*minimum
15 15 15 0 15*minimum

4.4.4. PRINCIPLE OF INSUFFICIENT REASON/ Equal likelihood/ Laplace

The Minimax regret criterion’s weakness is the inability to factor row differences. Hence,
sometimes the minimax regret strategy will lead to a poor decision because it ignores certain
information.
The principle of insufficient reason offers a method that incorporates more of the
information. It treats the states of nature as if each were equally likely, and it focuses on the
average payoff for each row, selecting the alternative that has the highest row average.

Page 75
 EXAMPLE
S1 S2 S3 S4 S5 Row Average
A1 28 28 2 28 4 23.2*maximum
A2 8
A3 5 5 5 5 2 9.6
8
5 5 5 5 2 9.6
8

Decision: A1 is selected
The basis for the criterion of insufficient reason is that under complete uncertainty, the
decision maker should not focus on either high or low payoffs, but should treat all payoffs
(actually, all states of nature), as if they were equally likely. Averaging row payoffs
accomplishes this.

? Dear learner, how would the decision in the above example change if the values in the
table stand for costs instead of profit?
__________________________________________________________________________
4.4.5. The Hurwitz Criterion
The Hurwitz criterion strikes a compromise between the maximax and maximin criterion.
The principle underlying this decision criterion is that the decision maker is neither totally
optimistic, nor totally pessimistic. With Hurwitz criterion, the decision payoffs are weighted
by a coefficient of optimism, a measure of a decision maker’s optimism. The coefficient of
optimism, which is defined as, is between zero and one (0< <1). If  = 1, then the decision
maker is said to be completely optimistic, if = 0, then the decision maker is completely
pessimistic. Given this definition, if  is coefficient of optimism, 1- is coefficient of
pessimism.

The Hurwitz criterion requires that for each alternative, the maximum payoff is multiplied by
 and the minimum payoff be multiplied by 1-.
Example: If  = 0.4 for the above example,

A1 = (0.4x16) + (0.6x4)
= 8.8
A2 = (0.4x10) + (0.6x5)
=7
A3 = (0.4x15) – (0.6x1)
= 5.4
Decision: A1 is selected

A limitation of Hurwicz criterion is the fact that  must be determined by the decision maker.
Regardless of how the decision maker determines, it is still a completely a subjective
measure of the decision maker’s degree of optimism. Therefore, Hurwicz criterion is a
completely subjective decision making criterion.

? Dear learner, can you mention conditions under which Hurwicz criterion criteria can be
considered as maximin or minimax criterion
_________________________________________________________________________
Page 76
_________________________________________________________________________
_________________________________________________________________________
__
4.5. DECISION MAKING UNDER RISK (WITH PROBABILITIES)
Dear learner, the decision making criteria just presented were based on the assumption that
no information regarding the likelihood of the states of the nature was available. Thus, no
probabilities of occurrence were assigned to the states of nature, except in the case of the
equal likely hood criterion.

It is often possible for the decision maker to know enough about the future state of nature to
assign probabilities to their occurrences. The term risk is often used in conjunction with
partial uncertainty, presence of probabilities for the occurrence of various states of nature.
The probabilities may be subjective estimates from managers or from experts in a particular
field, or they may reflect historical frequencies. If they are reasonably correct, they provide
the decision maker with additional information that can dramatically improve the decision
making process.
Given that probabilities can be assigned, several decision criteria are available to aid the
decision maker. Some of these are discussed below.

4.5.1. EXPECTED MONETARY VALUE (EMV)

The EMV approach provides the decision maker with a value which represents an average
payoff for each alternative. The best alternative is, then, the one that has the highest EMV.
The average or expected payoff of each alternative is a weighted average:
K
EMVi = Σ Pj.Vij
i=1
Where:
EMVi = the EMV for the ith alternative
Pi = the probability of the ith state of nature
Vij = the estimated payoff for alternative i under state of nature j.
Note: the sum of the probabilities for all states of nature must be 1.

EXAMPLE:

Probability 0.20 0.50 0.30

S1 S2 S3 Expected payoff
A1 4 16 12 12.40*maximum
A2 5 6 10 7
A3 -1 4 15 6.30
Decision: A1 will be chosen.
Note that it does not necessarily follow that the decision maker will receive a payoff
equal to the expected monetary value of a chosen alternative. Similarly, the expected
payoffs for either of the other alternatives do not equal any payoffs in those rows. What,
then, is the interpretation of the expected payoff? Simply a long-run average amount; the

Page 77
 approximate average amount one could reasonably anticipate for a large number of
identical situations.

4.5.2. Expected Opportunity Loss (EOL)

The table of opportunity loss is used rather than a table of payoffs. Hence, the opportunity
losses for each alternative are weighted by the probabilities of their respective state of
nature to compute a long run average opportunity loss, and the alternative with the
smallest expected loss is selected as the best choice.
EOL (A1) = 0.20(1) + 0.50(0) + 0.30(3) = 1.10 *minimum
EOL (A2) = 0.20(0) + 0.50(10) + 0.30(5) = 6.50
EOL (A3) = 0.20(6) + 0.50(12) + 0.30(0) = 7.20

Note: The EOL approach resulted in the same alternative as the EMV approach
(Maximizing the payoffs is equivalent to minimizing the opportunity losses).

4.5.3. Expected Value of Perfect Information (EVPI)

It can some times be useful for a decision maker to determine the potential benefit of
knowing for certain which state of nature is going to prevail. The EVPI is the measure of the
difference between the certain payoffs that could be realized under a condition involving risk.
If the decision maker knows that S1 will occur, A2 would be chosen with a payoff of $5.
Similarly for S2 $16 (for A1) and for S3, $15 (with A3) would be chosen.
Hence, the expected payoff under certainty (EPC) would be:
EPC = 0.20(5) + 0.50(16) + 0.30(15) = 13.50
The difference between this figure and the expected payoff under risk (i.e., the EMV) is the
expected value of perfect information. Thus:
EVPI = EPC – EMV
= 13.50 – 12.40 = 1.10
Note: The EVPI is exactly equal to the EOL. The EOL indicates the expected
opportunity loss due to imperfect information, which is another way of saying the expected
payoff that could be achieved by having perfect information.
Note: The expected value approach is particularly useful for decision making when a
number of similar decisions must be made; it is a long-run approach. For one-shot decisions,
especially major ones, other methods (perhaps, maximax or maximin) may be preferable. In
addition, non monetary factors, although not included in a payoff table, may be of
considerable importance. Unfortunately, there is no convenient way to include them in an
expected value analysis.

??? Dear learner, can you make differences between decision making situations under
uncertainty and risk?
___________________________________________________________________________
___________________________________________________________________________

Page 78
4.6. DECISION TREES
Decision trees some times are used by decision makers to obtain a visual portrayal of
decision alternatives and their possible consequences. The term gets its name from the tree-
like appearance of the diagram.
Decision tree format:

Decision tree, like probably tree is composed of squares, circles, and lines:
 The squares indicate decision points
 Circles represent chance events( circles and squares are called nodes)
o The lines (branches) emanating from squares represent alternatives.
o The lines from circles represent states of nature
 The tree is read from right to left.
It should be noted that although decision trees represent an alternative approach to payoff
tables, they are not commonly used for problems that involve a single decision. Rather, their
greatest benefit lies in portraying sequential decisions (i.e., a series of chronological
decisions). In the case of a single decision, constructing a decision tree can be cumbersome
and time consuming.
Example
Pay off table for Real Estate investment
State of Nature
Good economic Good economic
Decision conditions conditions
(Purchase) 0.6 0.4

Apartment building 50,000 30,000

Office building 100,000 -40,000
Warehouse 30,000 10,000

The decision tree for the above example will be:

$30,000
Good economic conditions (0.6 $50,000

Apartment building 2
Poor economic conditions (0.4)

Purchase
Good economic conditions (0.60 $100,000

Office building
1 3
Poor economic -$40,000
Conditions (0.4)

Warehouse Good economic conditions (0.60

4 Page 79 $30,000

Poor economic conditions (0.0.4)

$10,000
The circles ( ) and squares (  ) in the above figure are referred to as nodes. The
squares are decision nodes, and the branches emanating from a decision node reflect the
alternative decisions possible at that point. For example, in the above figure, node 1
signifies a decision to purchase an apartment building. Office building, or ware house.
The circles are probability nodes, and the branches emanating from them indicate the
state of nature that can occur: good economic conditions or poor economic conditions.
The decision tree represents the sequence of events in a decision situation. First, one of
the three decision choices is selected at node 1. Depending on the branch selected, the
decision maker arrives at probability node 2, 3, or 4, where one of the states of nature
will prevail, resulting in one of six possible payoffs.
Determining the best decision using a decision tree involves computing the expected
value at each probability node. This is accomplished by starting with the final outcomes
(payoffs) and working backward through the decision tree toward node 1. First, the
expected value of the payoffs is computed at each probability node.
EV(node 2) = .60($ 50,000) + .40($ 30,000) = $42,000
EV(node 3) = .60($100,000) + .40($-40,000) = $44,000
EV(node 4) = .60($ 30,000) + .40($ 10,000) = $22,000
These values are now shown as the expected payoffs from each of the three branches
emanating from node 1 in figure below. Each of these three expected values at nodes 2,
3, and 4 is the outcome of a possible decision that can occur at node 1. Moving toward
node 1, we select the branch that comes from the probability node with the highest
expected payoff. In figure below, the branch corresponding to the highest payoff,
$44,000 is from node 1 to node 3. This branch represents the decision to purchase the
office building. The decision to purchase the office building, with an expected payoff of
$44,000, is the same result we achieved earlier using the expected value criterion. In
fact, when only one decision is to be made (i.e., there is not a series of decisions), the
decision tree will always yield the same decision and expected payoff as the expected
value criterion. As a result, in these decision situations the decision tree is not very use-
ful. However, when a sequence or series of decisions is required, the decision tree can
be very useful.

Good economic
$42,000
Conditions (0.6)

$50,000
2
Apartment
building
Poor economic
Conditions(0.4) $30,000
$44,000
Good economic
Office building 3 Conditions (0.6)
1 $100,000
Purchase
Poor economic
Conditions -$40,000

Good economic
$22,000
Warehouse Conditions (0.6)
$30,000
4
Page 80
 Poor economic
Conditions (0.4) $10,000

Activity
1. The owner of the Burger Doodle Restaurant is considering two ways to expand operations:
opening a drive-up window or serving breakfast. The increase in profits resulting from these
proposed expansions depends on whether a competitor opens a franchise down the street. The
possible Profits from each expansion in operations given both future competitive situations
are shown in the following payoff table.
Competitor
Decision open Not Open
Drive-up window $-6,000 $20,000
Breakfast 4,000 8,000
Select the best decision using the following decision criteria.
a) Maximax
b) Maximin
c) Equally likely
d) Minimax regret
2. Consider the following payoff table for three alternatives, A,B, and C, under two future
states of the economy, good and bad.
Economic Conditions
Investment Good Bad
A $ 70,000 $ 25,000
B 120,000 -60,000
C 40, 000 40,000
Determine the decision using the following decision criteria.
a) Maximax
b) Maximin
c) Minimax regret
d) Hurwicz (α = 0.3)
e) Equal likelihood
3. An investor is considering investing in stock, real estate, or bonds under uncertain
economic conditions. The payoff table of returns for the investor’s decision situation is
shown below
Economic Conditions
Investment Good Stable Poor
Stocks $ 5,000 $ 7,000 $ 3,000
Real estate -2,000 10,000 6,000
Bonds 4,000 4,000 4,000
Determine the best investment using the following decision criteria.
a) Equal likelihood
b) Maximin

Page 81
 c) Maximax
d) Hurwicz ( α = 0.3)
e) Minimax regret
UNIT FIVE
5. NETWORK MODELS
Unit objectives
After completing this unit, the learner should be able to:
 Define network
 Understand the general network concept
 Explain the meaning and importance of network models
 Describe the characteristics of network models
 Point out the basic difference between PERT and CPM
 Explain PERT/CPM network components, and precedence relationship
 Describe critical path analysis
 Understand the concept and methods of project crashing

5.1. Basic Components of Network Diagram

i) Network
It is the graphic representation of logically and sequentially connected arrows and nodes
representing activities and events of a project. Networks are also called arrow diagram.
ii) Activity
An activity represents some action and is a time consuming effort necessary to complete a
particular part of the overall project. Thus each and every activity has a point where it ends.
It is represented in the network by an arrow.
A

Here A is called an activity.

The straight lines connecting the circles represent a task that takes time or resources; these
lines are called activities. The arrow heads show the direction of the activity.
The beginning and end points of an activity are called events or nodes. Event is a point in the
line and does not consume any resource. A numbered circle represents it. The head event has
always a number higher than the tail event.
Activity

Tail Head
Merge and burst events

Page 82
It is not necessary an event to be the ending event of the only one activity but can be the
ending event of two or more activities. Such event is defined as a Merge event.

Merge event

If the event happened to be the beginning event of two or more activities, it is defined as a
Burst event.
Burst event

iii) Preceding, succeeding and concurrent activities

Activities, which must be accomplished before a given event can occur, are termed as
preceding activities. Activities, which cannot be accomplished until any event has occurred,
are termed as succeeding activities. Activities that can be accomplished concurrently are
known as concurrent activities.
This classification is relative, which means that one activity can be proceeding to a certain
event, and the same activity can be succeeding to some other event or it may be a concurrent
activity with one or more activities.
iv) Dummy Activity
Certain activities, which neither consume time nor resources but are used simply to represent
a connection or a link between the events, are known as dummies. It is shown in the network
by a dotted (broken) line.
The purpose of introducing dummy activity is:
 To maintain uniqueness in the numbering system as every activity may have
distinct set of events by which the activity can be identified.
 To maintain a proper logic in the network.
D
A Dummy
B

v) Numbering the Events

Page 83
After the network is drawn in a logical sequence, every event is assigned a number. The
number sequence must be in such a way that it should reflect the flow of the network. In
event numbering, the following rules should be observed:
i. Event numbers should be unique.
ii. Event numbering should be carried out a sequential basis from left to right.
iii. The initial event, which has all outgoing arrows with no incoming arrow, is numbered 0 or 1.
iv. The head of an arrow should always bear a number higher than the one assigned at the
tail of the arrow.
v. Gaps should be left in the sequence of event numbering to accommodate subsequent
inclusion of activities, if necessary.
vi) Path
Sequence of activities that leads from the starting node to the finishing node
vii) Critical path
i. The longest path; determines expected project duration
ii. A path from the start node to then finish node that consists entirely of critical
nodes is a critical path
iii. The length of the critical path is minimum time required for project completion
(viii) Critical activities
 Activities on the critical path
 A critical activity is an activity that cannot be delayed without delaying the
completion of the project
 A delay of X days on a critical activity will increase the length of the project by X
days
 Critical activity should be monitored carefully to avoid delays
 A critical activity has a total float of zero or slack
(ix) Slack
Allowable slippage for path; the difference the length of path and the length of critical path

5.2. Rules for drawing a network

 A complete network should have only one point of entry -the start event, and one point of exit
-the finish event.
 Every activity must have one preceding event -the tail, and one following event - each activity
has one head.
 Several activities may use the same tail event, and the same head event, but no two activities
may share the same head and tail events.
 Time flows from left to right.
 An activity must be completed in order to reach the end-event.
 Dummy activities should only be introduced if absolutely necessary.

5.3. Convention for Drawing Networks

Page 84
 In addition to the rules described above, certain conventions are followed for the sake of
clarity and uniformity. There are two slightly different conventions for constructing the net
work diagrams. Under one convention, the arrows are used to designate activities, where as
under the other convention, the nodes are used to designate activities. These conventions are
referred to as activity- on-arrow (A-O-A) and activity – on- node (A-O-N) respectively. In
order to avoid confusion, the discussion here focuses primarily on activity- on- arrow
convention. When we use this convention:

 Networks proceed from left to right -the start event is at the left hand side of the
diagram and the end event at the right hand side
 Networks are not drawn to scale.
 Arrows representing activities should have their head to the right of their tail unless it
is impossible to draw the network in that way.
 Events or nodes should be numbered so that an activity always moves from a lower
numbered event to a higher one. This convention is relatively easy to accomplish in a
simple network but in a complex network it may be necessary to number in tens to
allow for extra activities to be added without the need for a complete renumbering of
the whole diagram
 Lines that cross should be avoided if possible
 The start event may be represented as a line instead of a circle, particularly when
several activities may begin at the start point.

5.4. Characteristics of Projects

 Cost involved
 A long time horizon
 Large number of activities
The main objectives of project network are:
 Minimization of total time
 Minimization of total cost
 Minimization of time for a given cost
 Minimization of cost for a given total time
 Minimization of idle resources
 Minimization of production delays, interruptions and conflicts

5.5. Critical path method (CPM) and Program evaluation and review
technique (PERT)
 Graphically displays project activities
 Estimates how long the project will take
 Indicates most critical activities
 Show where delays will not affect project
 How long any activity can be delayed without lengthening the project
Page 85
• PERT and CPM have been used to plan, schedule, and control a wide variety of projects:
– R&D of new products and processes
– Construction of buildings and highways
– Maintenance of large and complex equipment
Design and installation of new systems
• If the duration of each activity is known with certainty, the critical path method (CPM) can
be used to determine the length of time required to complete a project.
• If the duration of activities is not known with certainty, the program evaluation and review
technique (PERT) can be used to estimate the probability that the project will be completed
by a given deadline
• Today’s project management software packages have combined the best features of both
approaches.
• PERT/CPM is used to plan the scheduling of individual activities that make up a project
• Projects may have as many as several or thousand activities
• A complicating factor in carrying out the activities is that some activities depend on the
completion of other activities before they can be started.
• Project managers rely on PERT/CPM to help them answer questions such as:
 What is the total time to complete the project?
 What are the scheduled start and finish dates for each specific activity?
 Which activities are critical and must be completed exactly as scheduled to keep the
project on schedule?
 How long can noncritical activities be delayed before they cause an increase in the
project completion time?

Project Network – Activity on Arrow

Order 4
Locate 2furniture
facilities Remodel Furniture
1 setup
5 6
Move
Interview Hire and in
train
3

Example 1
A project to manufacture a product is composed of the following activities: draw project
network & critical path & its activities.

Page 86
 Solution

Example 2
Computation of earliest start and latest start times for the activities in the net work model for
2 simple data collection project.
Sequence Activity
1-2 Design questionnaire
2-3 Prepare questionnaire
3-4 Prepare Time Table
3-5 Select interviewers
3-6 Select target respondents
4-5 Arrange facilities
4-6 Notify the respondents
5-6 Train the interviewers
6-7 Undertake the interview
7-8 Organize the collected data

Required:
a) Draw the network diagram

Page 87
 b) Determine the critical path
c) How much slack time is available in the path containing notifying the respondents

Solution Time
a. 1-2 -3-5-6-7-8 36 days
b. 1-2-3-4-5-6-7-8 38 days
c. 1-2-3-4-6-7-8 32 days
d. 1-2-3-6-7-8 31 days

The length of any path can be determined by summing the expected times of the activities on
that path. The path with the longest time is of particular interest because it determines the
projects completion time. If there are any delays along the longest path, here will be
corresponding delays in project completion time. So to shorten the project completion time
one must focus on the longest path. This longest path is so called the critical path and its
activities are referred to as critical activities.
Thus, one the above example, the critical path corresponds to path B with a time requirement
of 38 days.
A path slack is the difference between the length of a given path and the length of the critical
path. Thus, the slack corresponding to path C is;
Slack = Time for critical path - Time for = 38 - 32 = 6 days
Thus, slacks for the paths can be:
Path Slack
A 38-36 2
B 38-38 0
C 38-32 6
D 38-31 7

In conclusion, the expected length of the project is 44 days.

Page 88
With regard to identification of the earliest start, earliest finish, latest start and latest finish
times, observing the following diagram is instrumental.
Example 3

6 wee
8 wee ks 4
ks 2
1
1 1 we 3 wee
ek s ks
4 wee
ks
5 1M
9 wee woeveek
3 ks in 6
Required
Given the above information, determine each of the following
1. The length of each path
2. The critical path
3. The expected length of the project
4. The amount of slack time for each path

Path Length Slack

(weeks)
1-2-4-5-6 18 2
1-2-5-6 20 (critical path) 0
1-3-5-6 14 6

5.5.1. Critical Path Analysis

5.5.1.1. Forward pass method

• Earliest Start Time (ES): earliest time an activity can start

– ES = maximum EF of immediate predecessors
• Earliest finish time (EF): earliest time an activity can finish earliest start time plus
activity time. EF= ES + t.

5.5.1.2. Backward Pass method

 Latest Start Time (LS): Latest time an activity can start without delaying critical path
time
LS = LF - t
 Latest finish time (LF): latest time an activity can be completed without delaying
critical path time. LF = minimum LS of immediate predecessors
Note: for nodes with multiple entering arrows: ES for activities leaving such nodes
equals the largest EF of entering arrows. For nodes with multiple leaving arrows; LF

Page 89
 for arrows entering that node equals to the smallest LS of leaving arrows. EF and LF
of the last activity in the path are the same.

• Determine the float for each activity

– Compute the activity’s float/slack
Float = LS - ES = LF - EF
– Float is the maximum amount of time that this activity can be delay in its
completion before it becomes a critical activity, i.e., delays completion of the
project
• Find the critical path is that the sequence of activities and events where there is no
“slack” i.e.. Zero slack
– Longest path through a network
• Find the project duration is minimum project completion time

Example

Activity Immediate
Completion
predecessors Time
(week)
A - 5
B - 6
C A 4
D A 3
E A 1
F E 4
G D,F 14
H B,C 12
I G,H 2
Total …… 51
This information indicates that the total time required to complete activities is 51
weeks. However, we can see from the network that several of the activities can be
conducted simultaneously (A and B, for example)
Required:
1. What is the total time to complete the project?
2. What are the scheduled start and completion times for each activity?
ES, EF, LS, LF for each activity.

Page 90
 1. What activities are critical and must be completed as scheduled in order to keep the
project on time? Critical path activities
2. How long can non-critical activities be delayed before they cause a delay in the
project’s completion time. Slack time available for all activities is given.
Solution

Earliest start time rule:

The earliest start time for an activity leaving a particular node is equal to the largest
of the earliest finish times for all activities entering the node.

Latest finish time rule:

The latest finish time for an activity entering a particular node is equal to the smallest
of the latest start times for all activities leaving the node.
Activity Earliest Latest Earliest Latest Slack Critical path
start (ES) start (LS) finish (EF) finish (LF) (LS-
ES)

A 0 0 5 5 0 Yes

B 0 6 6 12 6

C 5 8 9 12 3

D 5 7 8 10 2

E 5 5 6 6 0 Yes

F 6 6 10 10 0 Yes

G 10 10 24 24 0 Yes

H 9 12 21 24 3

I 24 24 26 26 0 Yes

Page 91
 5.5.2. Program evaluation and review technique (PERT) method analysis
• PERT is based on the assumption that an activity’s duration follows a probability distribution
instead of being a single value
• Three time estimates are required to compute the parameters of an activity’s duration
distribution:
– pessimistic time (tp ) - the time the activity would take if things did not go well
– most likely time (tm ) - the consensus best estimate of the activity’s duration
– optimistic time (to ) - the time the activity would take if things did go well
Expected Time

teto=+ 4tm +tp

6
te = expected time
to = optimistic time
tm = most likely time
tp = pessimistic time
Variance

Page 92
  2 (t
=p
–
t o)2
36
2 = variance
to = optimistic time
tp = pessimistic time
Example
Immed. Optimistic Most Likely Pessimistic
Activity Predec. Time (Hr.) Time (Hr.) Time (Hr.)
A -- 4 6 8
B -- 1 4.5 5
C A 3 3 3
D A 4 5 6
E A 0.5 1 1.5
F B,C 3 4 5
G B,C 1 1.5 5
H E,F 5 6 7
I E,F 2 5 8
J D,H 2.5 2.75 4.5
K G,I 3 5 7
Required:
1) draw the network diagram
2) Find the critical path
3) Determine the expected length and variance of the project
4) Determine the slack for each of the activities

Page 93
 Activity Expected Time Variance
A 6 4/9
B 4 4/9
C 3 0
D 5 1/9
E 1 1/36
F 4 1/9
G 2 4/9
H 6 1/9
I 5 1
J 3 1/9
K 5 4/9

5.6. Project crashing

Crashing -is accelerating project of those critical activities that have the lowest ratio of
incremental cost to incremental time saved
Crash time -is the minimum time in which activity can be completed in case additional
remoras are inducted.
Crash cost -is the total cost of completing an activity in crash time.

The objective of project crash cost analysis is to reduce the total projected completion time
(to avoid late penalties, to take advantage of monetary incentives for timely completion of a

Page 94
project, or to free resources for we on other the projects), while minimizing the cost of
crashing.
Project completion time can be shortened only by crashing critical activities, which follows
that not all project activities should be crashed. However, when activities are crashed, the
critical path may change, requiring further crashing of previously non-critical activates in
order to further reduce the project completion time. In a nutshell, crashing means adding
extra resources, and managers are usually interested in speeding up project at the least
additional cost.
In order to make a rational decision about which activities (if any) to crash and the extent of
crashing desirable, a manager needs the following information:
1. Regular time and crash time estimates for each activity (normal)
2. Regular (normal) cost and crash cost estimates for “
3. A list of activates that are on the critical path
 Note: Activities on critical path are potential candidates for crashing between
shortening non critical activities would not have an impact on total project
duration and activities are crashed according to crashing costs. Crash those
activities with the lowest cost first. Moreover, crashing should continue as
long as the cost to crash is less than the benefit received from crashing. These
benefits might take the form of incentive payments for early completion of the
project as part of a government contract, or they might reflect savings in the
indirect project costs, or both

Procedures
1. Identify the critical path and critical activities
2. Calculate the cost slope for each activities
3. Start crashing the critical activity with the lowest crashing cost (lowest cost slope)
4. Stop crashing, if not possible beyond that
Cost slope = crashing cost – Normal cost
Normal time – Crashing Time
Example
The following table gives data on normal time and cost and crash time and cost for a project.

Required:
1. Draw a network diagram

Page 95
 2. Find the critical path and critical activity
3. Calculate the cost slope of the project
4. What would be a total cost of the project and total crashing cost of a project if the
project manager wants to finish three days sooner than the original critical path.
1) Network diagram

2) Possible paths
Path 1:- 1-2-5-6-7
6+3+4+3 = 16 days
Path 2:- 1-2-4-6-7 - critical activities
6+5+8+3 =22 days - critical path
Path 3:- 1-3-4-6-7
4+6+8+3 = 21 days
3) Cost slope for each activities
Activity CC – NC Cost/ day Max. Reduction
NT - CT
1-2 100-60 20 2
2
1-3 200-50 75 2
2
2-4 150-50 50 2
2
2-5 65-45 10 2
2
3-4 200-90 55 2
2
4-6 300-80 55 4
4
5-6 100-40 30 2
2
6-7 80-45 35 1
1

4) Calculating total cost of the project

Critical path 2 Critical activity Cost/ day

1-2 20 = 20*2 = 40

Page 96
 2-4 50
4-6 55
6-7 35 = 35*1 = 35
Critical path 3 1-3 75
3-4 55 = 55*2 = 110
4-6 55
6-7 35

Total crashing cost = 40 +35 + 110= 185

Total normal cost = 60 + 50 + 50 + 45 + 90 + 80 + 40 + 45 = 460
Total cost of the project = 645

Activity
1. Given the following information:

Activity Description Immediate

predecessor Time
Select office site - 3
A
B Create organizational and financial plan - 5
C Determine personnel requirement B 3
D Design facility A and C 5
E Construct interior material D 6
F Select personnel to move C 3
G Hire new employees F 2
H Move records, key personnel F 1
I Make financial arrangements with B 4
institution & selected sight
J Train new personnel H,E,G 2

Required:
a) Develop the network diagram
b) Critical path and Critical activities
c) Duration of the project
d) Slack time of activities
2. Given the following information
Activity Estimates (months)
a m b
1--->2 4 8 12

Page 97
 1--->3 6 10 15
1--->4 2 10 14
2--->5 3 6 9
2--->6 1 4 13
3--->5 3 6 18
4--->5 0 0 0
4--->7 2 8 12
5--->8 9 15 22
5--->7 5 12 21
7--->8 5 6 12
6--->9 7 20 25
8--->9 3 8 20

Determine the following:

a. Draw the network diagram
b. Expected activity times and variance
c. Find the critical path and critical activities
d. Earliest event times
e. Latest event times
f. Activity slack
3. The following table gives data on normal time and cost and crash time and cost for a project
Normal Crash
Activity Time ( in days) Cost (Birr) Time ( in days) Cost (Birr)
1-2 4 100 2 150
1-3 3 80 1 180
2-4 4 45 3 80
2-5 6 100 4 300
3-4 4 30 3 110
4-5 6 260 4 300
5-6 4 30 3 60
Required:
i. Draw a network diagram
ii. Find the critical path and critical activity.
iii. Calculate the cost slope for each project activities.
iv. What would be the total crashing cost and total cost of the project, if the
project manager wants to finish three days sooner than the original critical
path.

Page 98