Operations Research

CHAPTER ONE

INTRODUCTION TO OPERATIONS RESEARCH

Introduction

The first formal activities of Operations Research (OR) were initiated in England during World
War II, when a team of British scientists set out to make scientifically based decisions regarding
the best utilization of war material. After the war, the ideas advanced in military operations were
adapted to improve efficiency and productivity in the civilian sector.

This chapter will familiarize you the basic terminologies in operations research/management
science. The evolution of operations research and its basic characteristics will also be discussed.
The chapter also presents the OR modeling framework and relates it with the general problem
solving process. Here it will be shown that the OR/MS modeling framework supports each stage
of the problem solving process: problem formulation, identification and evaluation of
alternatives, and selection of the best alternative. The chapter concludes with a brief discussion
on a variety of OR models and their applications.

Learning Outcomes

At the end of this section, you should be able to;

 Know the History of Operations Research

 Understand the nature and significance of operations research

 Recognize the features of Operations Research

 Be aware of model and modeling in Operations Research

1.1 Defining Operations Research

Define Operations Research on your own words.

________________________________________________________________________
________________________________________________________________________

1 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

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" or "ORMS". Yet other terms sometimes used are
"industrial engineering" ("IE"), "decision science" ("DS"), and “problem solving”. In recent
years there has been a move towards a standardization upon a single term for the field, namely
the term "OR". OR has been defined in various ways and it is perhaps too early to define it in
some authoritative way. However given below are a few opinions about the definition of OR
which have been changed along-with the development of the subject.

In 1946 Morse & Kimbel has defined as; "OR is a scientific method of providing executive
departments with a quantitative basis for decision regarding the operations under their control."

In 1948 Blackett defined as; "OR is a scientific method of providing executives with any
analytical and objective basis for decisions" Another definition is due to Morse who defined in
1948 as; "The term OR, has here-to fore been used to connote various attempts to study
operations of war by scientific methods. From a more general point of view, OR can be
considered to be an attempt to study those operations of modern society which involved
organizations of men or men and machines". Later on in 1957, Churchmen Ackoff and Arnoff
defined; "OR is the application of scientific methods, techniques and tools to problems involving
the operations of systems so as to provide those in control of the operations with optimum
solutions to the problem".

In 1958 Saaty defined OR as; "The art of giving bad answer to problems to which, otherwise,
worse answers are given". The Operational Research Society of U.K. defines OR as:
"Operational Research is the application of the methods of science to complex problems arising
in the direction and management of large systems of men, machines, materials and money in
industry, business, government and defense. The distinctive approach is to develop a scientific
model of the system, incorporating measurements of factors, such as chance and risk, with which
to compare the outcome of alternative decisions, strategies and controls. The purpose is to help
management determine its policies and actions scientifically." In the USA, where it is called
Operations Research, the OR Society of America says more briefly; "OR is concerned with

2 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

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

An even briefer definition might be "Science applied to management", but however, it might be
defined, there is no doubt that OR provides the numerate scientist - of whatever discipline-with
an opportunity to apply the skills of science in the field of Management. To sum up Operations
Research (OR) is the application of quantitative methods to decision making. It formulates
problems incisively and assesses the possible consequence of alternative course of action, so that
informed and effective decisions can be taken.

1.2 The History of Operations Research

Since the advent of the industrial revolution, the world has seen a remarkable growth in the size
and complexity of organizations. The artisans‟ small shops of an earlier era have evolved into the
billion-dollar corporations of today. An integral part of this revolutionary change has been a
tremendous increase in the division of labor and segmentation of management responsibilities in
these organizations. The results have been spectacular. However, along with its blessings, this
increasing specialization has created new problems, problems that are still occurring in many
organizations. One problem is a tendency for the many components of an organization to grow
into relatively autonomous empires with their own goals and value systems, thereby losing sight
of how their activities and objectives mesh with those of the overall organization. What is best
for one component frequently is detrimental to another, so the components may end up working
at cross purposes. A related problem is that as the complexity and specialization in an
organization increase, it becomes more and more difficult to allocate the available resources to
the various activities in a way that is most effective for the organization as a whole. These kinds
of problems and the need to find a better way to solve them provided the environment for
the emergence of operations research (commonly referred to as OR).

The roots of OR can be traced back many decades, when early attempts were made to use a
scientific approach in the management of organizations. However, the beginning of the activity
called operations research has generally been attributed to the military services early in World
War II. Because of the war effort, there was an urgent need to allocate scarce resources to the
various military operations and to the activities within each operation in an effective manner.

3 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Therefore, the British and then the U.S. military management called upon a large number of
scientists to apply a scientific approach to dealing with this and other strategic and tactical
problems. In effect, they were asked to do research on (military) operations. These teams of
scientists were the first OR teams. By developing effective methods of using the new tool of
radar, these teams were instrumental in winning the Air Battle of Britain. Through their research
on how to better manage convoy and antisubmarine operations, they also played a major role in
winning the Battle of the North Atlantic. Similar efforts assisted the Island Campaign in the
Pacific.

When the war ended, the success of OR in the war effort spurred interest in applying OR outside
the military as well. As the industrial boom following the war was running its course, the
problems caused by the increasing complexity and specialization in organizations were again
coming to the forefront. It was becoming apparent to a growing number of people, including
business consultants who had served on or with the OR teams during the war, that these were
basically the same problems that had been faced by the military but in a different context. By the
early 1950s, these individuals had introduced the use of OR to a variety of organizations in
business, industry, and government. The rapid spread of OR soon followed. At least two other
factors that played a key role in the rapid growth of OR during this period can be identified. One
was the substantial progress that was made early in improving the techniques of OR. After the
war, many of the scientists who had participated on OR teams or who had heard about this work
were motivated to pursue research relevant to the field; important advancements in the state of
the art resulted. A prime example is the simplex method for solving linear programming
problems, developed by George Dantzig in 1947. Many of the standard tools of OR, such as
linear programming, dynamic programming, queueing theory, and inventory theory, were
relatively well developed before the end of the 1950s.

A second factor that gave great impetus to the growth of the field was the onslaught of the
computer revolution. A large amount of computation is usually required to deal most effectively
with the complex problems typically considered by OR. Doing this by hand would often be out
of the question. Therefore, the development of electronic digital computers, with their ability to
perform arithmetic calculations thousands or even millions of times faster than a human being

4 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

can, was a tremendous boon to OR. A further boost came in the 1980s with the development of
increasingly powerful personal computers accompanied by good software packages for doing
OR. This brought the use of OR within the easy reach of much larger numbers of people. Today,
literally millions of individuals have ready access to OR software. Consequently, a whole range
of computers from mainframes to laptops now are being routinely used to solve OR problems.

1.3 The Nature and Significance of Operations Research

1.3.1 The Nature of Operations Research

As its name implies, operations research involves “research on operations.” Thus, operations
research is applied to problems that concern how to conduct and coordinate the operations (i.e.,
the activities) within an organization. The nature of the organization is essentially immaterial,
and, in fact, OR has been applied extensively in such diverse areas as manufacturing,
transportation, construction, telecommunications, financial planning, health care, the military,
and public services, to name just a few. Therefore, the breadth of application is unusually wide.

The research part of the name means that operations research uses an approach that resembles
the way research is conducted in established scientific fields. To a considerable extent, the
scientific method is used to investigate the problem of concern. (In fact, the term management
science sometimes is used as a synonym for operations research.) In particular, the process
begins by carefully observing and formulating the problem, including gathering all relevant data.
The next step is to construct a scientific (typically mathematical) model that attempts to abstract
the essence of the real problem. It is then hypothesized that this model is a sufficiently precise
representation of the essential features of the situation that the conclusions (solutions) obtained
from the model are also valid for the real problem. Next, suitable experiments are conducted to
test this hypothesis, modify it as needed, and eventually verify some form of the hypothesis.
(This step is frequently referred to as model validation.) Thus, in a certain sense, operations
research involves creative scientific research into the fundamental properties of operations.
However, there is more to it than this. Specifically, OR is also concerned with the practical
management of the organization. Therefore, to be successful, OR must also provide positive,
understandable conclusions to the decision maker(s) when they are needed.

5 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Still another characteristic of OR is its broad viewpoint. As implied in the preceding section, OR
adopts an organizational point of view. Thus, it attempts to resolve the conflicts of interest
among the components of the organization in a way that is best for the organization as a whole.
This does not imply that the study of each problem must give explicit consideration to all aspects
of the organization; rather, the objectives being sought must be consistent with those of the
overall organization. An additional characteristic is that OR frequently attempts to find a best
solution (referred to as an optimal solution) for the problem under consideration. (We say a best
instead of the best solution because there may be multiple solutions tied as best.) Rather than
simply improving the status quo, the goal is to identify a best possible course of action. Although
it must be interpreted carefully in terms of the practical needs of management, this “search for
optimality” is an important theme in OR.

All these characteristics lead quite naturally to still another one. It is evident that no single
individual should be expected to be an expert on all the many aspects of OR work or the
problems typically considered; this would require a group of individuals having diverse
backgrounds and skills. Therefore, when a full-fledged OR studies of a new problem is
undertaken, it is usually necessary to use a team approach. Such an OR team typically needs to
include individuals who collectively are highly trained in mathematics, statistics and probability
theory, economics, business administration, computer science, engineering and the physical
sciences, the behavioral sciences, and the special techniques of OR. The team also needs to have
the necessary experience and variety of skills to give appropriate consideration to the many
ramifications of the problem throughout the organization.

1.3.2 The Significance of Operations Research

Operations research has had an impressive impact on improving the efficiency of numerous
organizations around the world. In the process, OR has made a significant contribution to
increasing the productivity of the economies of various countries. In its recent years of organized
development, OR has entered successfully many different areas of research for military
government and industry in many countries of the world. The basic problem in most of the
developing countries in Asia and Africa is to remove poverty and improve the standard of living
of a common man as quickly as possible. So there is a great scope for economists, statisticians,

6 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

administrators, politicians and the technicians working in a team to solve this problem by an OR
approach. The possible application sectors are as under:

1) Macro Economic Planning: OR can be employed for Macro-Economic Planning of the

country:

o OR can also be used in Simulation Modeling of the Economy of the country.

o Investment Planning: OR can be employed in the Investment Planning of the country

where investment plans for the next five or ten years are prepared. Mixed Integer
Programming and Linear Programming techniques can be used.

o Choice of Projects: OR can help the people in the planning in choosing the optimal
project. This sort of choice would need Integer Programming and Quadratic Assignment
techniques.

2) Sectoral Planning: OR can also be employed in a particular sector of the Economy, e.g. in
agriculture, in finance, in industry, in marketing, in production, in management etc.

 Scheduling all operations within a sector can be done by using OR e.g. production
scheduling + Distribution planning + marketing + Personnel management + maintenance
+ ...............

 Schedule of some operations within a sector can be done by employing OR e.g. Inventory
planning in agriculture or distribution of fertilizer etc.

3) Micro Economic Planning: This sort of activity involve for example: Planning the operations
of a Company. Improving the layout of a workshop in a company. Finding size of a hospital in
an area etc. There is a great potential for utilizing OR in this area of planning in our country.

1.4 Features of Operations Research

The main characteristics or features of operations research (OR) are:-

1. Creating a Model: OR first makes a model. A model is a logical representation of a
problem. It shows the relationships between the different variables in the problem. It
is just like a mathematical formula. For e.g. Assets - Liabilities = Capital +
Accumulated Reserves.

7 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

2. Shows Important Variables: OR shows the variables which are important for
solving the problem. Many of the variables are uncontrollable.
3. Symbolizes the Model: The OR model, its variables and goals are converted into
mathematical symbols. These symbols can be easily identified, and they can be used
for calculation.
4. Achieving the Goal: The main goal of OR is to select the best solution for solving
the problem.
5. Quantifying the Model: All variables in the OR model are quantified. That is, they
are converted into numbers. This is because only quantified data can be put into the
model to get results.
6. Using Mathematical Devices: Data is supplemented with mathematical devices to
narrow down the margin of error.
7. Use of Computer: The main focus is on decision-making and problem solving. For
this purpose computers are widely used.
8. Interdisciplinary: OR is interdisciplinary, because it uses techniques from
economics, mathematics, chemistry, physics, etc.
9. Highest Efficiency: The main aim of OR is to make decisions and solve problems.
This results in the highest possible efficiency.
1.5 OR Approach to Problem Solving

OR encompasses a logical systematic approach to problem solving. This approach to problem

solving follows a generally recognized ordered set or steps: (1) observation, (2) definition of the
problems, (3) model construction, (4) model solution, and (5) implementation of solution results.

Observation The first step in a problem solving exercises in OR is the identification of a

problem that exist in the system. This requires that the system be continuously and closely
observed so that problems can be identified as soon as they occur.

Definition of the Problem Once it has determined that a problem exists, it must be clearly and
concisely defined. The problem definition includes the limits of the problems and the degree to
which it pervades other organs of the system. A requirement of problem definition is that the

8 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

goals (or objective) must be clearly defined which helps to focus attention on what the problem
is.

Model Construction An OR model is an abstract representation of an existing problem

situation. It can be in the form of a graph or chart, but mostly, an OR model consists of a set of
mathematical relationship. In OR terminology, these are called objective function and
constraints.

Model Solution Once models are constructed, they are solved using the OR techniques,
presented in the next section. Actually it is difficult to separate model construction and solution
in most cases, since OR technique usually applies to a specific type of model. Thus, the model
type and solution method are both part of the OR technique.

Implementation of Results The results of an OR technique are information which helps in

making a decision. The beauty of OR process lies in obtaining, the results which are implement
able or we call it a feasible whole exercise will go waste.

1.6 Model and Modeling in Operations Research

Operations research (often referred to as management science) is simply a scientific

approach to decision making that seeks to best design and operate a system, usually under
conditions requiring the allocation of scarce resources. By a system, we mean an organization of
interdependent components that work together to accomplish the goal of the system. For
example, Ford Motor Company is a system whose goal consists of maximizing the profit that can
be earned by producing quality vehicles. The term operations research was coined during World
War II when British military leaders asked scientists and engineers to analyze several military
problems such as the deployment of radar and the management of convoy, bombing,
antisubmarine, and mining operations.

The scientific approach to decision making usually involves the use of one or more
mathematical models. A mathematical model is a mathematical representation of an actual
situation that may be used to make better decisions or simply to understand the actual situation
better. The following example should clarify many of the key terms used to describe
mathematical models.

9 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Prescriptive or Optimization Models

Most of the models discussed in this book will be prescriptive or optimization models. A
prescriptive model “prescribes” behavior for an organization that will enable it to best meet its
goal(s). The components of a prescriptive model include:
 Objective function(s)
 Decision variables
 Constraints
In short, an optimization model seeks to find values of the decision variables that optimize
(maximize or minimize) an objective function among the set of all values for the decision
variables that satisfy the given constraints.
Static and Dynamic Models

A static model is one in which the decision variables do not involve sequences of decisions over
multiple periods. A dynamic model is a model in which the decision variables do involve
sequences of decisions over multiple periods. Basically, in a static model we solve a “one-shot”
problem whose solutions prescribe optimal values of decision variables at all points in time.

Linear and Nonlinear Models

Suppose that whenever decision variables appear in the objective function and in the constraints
of an optimization model, the decision variables are always multiplied by constants and added
together. Such a model is a linear model. If an optimization model is not linear, then it is a
nonlinear model. Linear mathematical programming technique consist of first, identifying
problem as being solvable by linear programming; second formulation of unturned problem and
then finding the solution by using established mathematical techniques. It derives its name from
the fact that the functional relationship in the mathematical model are linear and the solution
techniques consists of a predetermined mathematical steps i.e. program.

Integer and Noninteger Models

10 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

If one or more decision variables must be integer, then we say that an optimization model is an
integer model. If all the decision variables are free to assume fractional values, then the
optimization model is a noninteger model. Clearly, volume, temperature, pressure, and
percentage composition of our inputs may all assume fractional values.

Deterministic and Stochastic Models

Suppose that for any value of the decision variables, the value of the objective function and
whether or not the constraints are satisfied is known with certainty. We then have a
deterministic model. If this is not the case, then we have a stochastic model.

1.6.1 The Seven-Step Model-Building Process

When operations research is used to solve an organization‟s problem, the following seven step
model-building procedure should be followed:

Step 1: Formulate the Problem The operations researcher first defines the organization‟s
problem. Defining the problem includes specifying the organization‟s objectives and the parts of
the organization that must be studied before the problem can be solved.

Step 2: Observe the System Next, the operations researcher collects data to estimate the value
of parameters that affect the organization‟s problem. These estimates are used to develop (in step
3) and evaluate (in step 4) a mathematical model of the organization‟s problem.

Step 3: Formulate a Mathematical Model of the Problem In this step, the operations
researcher develops a mathematical model of the problem.

Step 4: Verify the Model and Use the Model for Prediction The operations researcher now
tries to determine if the mathematical model developed in step 3 is an accurate representation of
reality. For example, to validate our model, we might check and see if (1) accurately represents
yield for values of the decision variables that were not used to estimate (1). Even if a model is
valid for the current situation, we must be aware of blindly applying it.

Step 5: Select a Suitable Alternative Given a model and a set of alternatives, the operations
researcher now chooses the alternative that best meets the organization‟s objectives. (There may
be more than one!)

11 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Step 6: Present the Results and Conclusion of the Study to the Organization In this step, the
operations researcher presents the model and recommendation from step 5 to the decision-
making individual or group. In some situations, one might present several alternatives and let the
organization choose the one that best meets its needs. After presenting the results of the
operations research study, the analyst may find that the organization does not approve of the
recommendation. This may result from incorrect definition of the organization‟s problems or
from failure to involve the decision maker from the start of the project. In this case, the
operations researcher should return to step 1, 2, or 3.

Step 7: Implement and Evaluate Recommendations If the organization has accepted the
study, then the analyst aids in implementing the recommendations. The system must be
constantly monitored (and updated dynamically as the environment changes) to ensure that the
recommendations enable the organization to meet its objectives.
Self-Assessment Questions (SAQ1)
1. Write short notes on the legacy of operations research
2. Discuss the Seven-step modeling process.
3. Military advancement has a direct effect on economic development. Elucidate.
©©©©©©©©©

CHAPTER TWO

LINEAR PROGRAMMING

Introduction

The development of linear programming has been ranked among the most important scientific
advances of the mid-20th century, and we must agree with this assessment. Its impact since just
1950 has been extraordinary. Today it is a standard tool that has saved many thousands or
millions of dollars for most companies or businesses of even moderate size in the various
industrialized countries of the world; and its use in other sectors of society has been spreading
rapidly. A major proportion of all scientific computation on computers is devoted to the use of
linear programming. Dozens of textbooks have been written about linear programming, and
published articles describing important applications now number in the hundreds.

12 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Learning Outcomes

At the end of this section, you should be able to;

 Understand the nature and application of linear programming

 Understand and formulate linear programming problems
 Solve the linear programming problems using graphical methods
 Solve the linear programming problems using the simplex method
 Critically appreciate what optimal solution and duality mean
 Know how to analyze the impact of change in the RHS of a constraint on the optimal
solution
 Know how to analyze the impact of change in the coefficient of an objective function on
the optimal solution
 Understand the concept of duality and formulate dual LP models
2.1 Defining Linear Programming

Linear programming is a mathematical technique designed to aid managers in allocating scarce

resources (such as labor, capital, or energy) among competing activities. It reflects, in the form
of a model, the organization's attempt to achieve some objective (frequently, maximizing profit
contribution, maximizing rate of return, minimizing cots) in view of limited or constrained
resources (available capital or labor, service levels, available machine time, budgets).
The linear programming technique can be said to have a linear objective function that is to be
optimized (either maximized or minimized) subject to linear equality or inequality constraints
and sign restrictions on the variables. The term linear describes the proportionate relationship of
two or more variables. Thus, a given change in one variable will always cause a resulting
proportional change in another variable.

2.2 Application Areas of Linear Programming

Some areas in which linear programming have been applied will be helpful in setting the climate
for learning about this important technique.

13 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

o A company produces agricultural fertilizers. It is interested in minimizing costs while

meeting certain specified levels of nitrogen, phosphate, and potash by blending together a
number of raw materials.
o An investor wants to maximize his or her rate of return by investing in stocks and bonds.
The investor can set specific conditions that have to be met including availability of
capital.
o A company wants the best possible advertising exposure among a number of national
magazines, and radio and television commercials within its available capital
requirements.
o An oil refinery blends several raw gasoline and additives to meet a car manufacturer's
specifications while still maximizing its profits.
o A city wants to maximize the daytime use of recreational properties being proposed for
purchase with a limited capital available. This technique, called linear programming
(L.P), is solved in a step-by-step manner called iterations. Each step of the procedure is
an attempt to improve on the solution until the "best answer" is obtained or until it is
shown that no feasible answer exists.
Briefly, the most common type of application involves the general problem of allocating limited
resources among competing activities in a best possible (i.e., optimal) way. More precisely, this
problem involves selecting the level of certain activities that compete for scarce resources that
are necessary to perform those activities. The choice of activity levels then dictates how much of
each resource will be consumed by each activity. The variety of situations to which this
description applies is diverse, indeed, ranging from the allocation of production facilities to
products to the allocation of national resources to domestic needs, from portfolio selection to the
selection of shipping patterns, from agricultural planning to the design of radiation therapy, and
so on. However, the one common ingredient in each of these situations is the necessity for
allocating resources to activities by choosing the levels of those activities.
2.3 Structure of Linear Programming Model

Linear programming uses a mathematical model to describe the problem of concern. The
adjective linear means that all the mathematical functions in this model are required to be linear
functions. The word programming does not refer here to computer programming; rather, it is

14 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

essentially a synonym for planning. Thus, linear programming involves the planning of activities
to obtain an optimal result, i.e., a result that reaches the specified goal best (according to the
mathematical model) among all feasible alternatives. Although allocating resources to activities
is the most common type of application, linear programming has numerous other important
applications as well. In fact, any problem whose mathematical model fits the very general format
for the linear programming model is a linear programming problem.

2.3.1 Formulation of the Linear Programming Problem

To formulate a real-life problem as a linear program is an art in itself. To aid you in this task, it is
helpful to isolate the essential elements of the problem as a means of asking what the clients
wants and what information can be gained from the data that has been provided.

The first step in formulating a problem is to set forth the objective called the objective function.
A second element of a problem is that there are certain constraints on the company's ability to
maximize the total contribution. These constraints are:

(1) Quantity of raw materials available,

(2) The level of demand for the products, and
(3) The equipment productive capacity.
A further element that must be considered in the problem is the time period being used. The
duration may be either long term or short term. Although time is an important element, it is one
that has flexibility so that the time horizon may be changed as long as the restrictions are
compatible with the periods under consideration.

The last element is that every product has a likelihood of being made. These products are the
dependent or decision variables. Of course, the likelihood of a variable's being in the answer may
change with the price or contribution values (usually profit and the nature of the restraints. Yet,
at this point there is nothing to indicate that differing chances of occurrence exists for the
possibility of making each of the products.

The first stage of solving linear programming problems is to set forth the problem in a
mathematical form by defining the variables and the resulting constraints. Generally, the
relationship is fairly simple using only elementary algebraic notation. The relationships can be

15 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

seen by first identifying the decision variables. To aid in using algebraic notation, the decision
variables can be represented by symbols such as X, Y, Z. Next, we must build the objective
function. If the goal is to maximize profit, we identify our objective function as Maximize total
profit or Minimize total loss (cost). Then we write problem constraints. These steps are
illustrated by taking an example.

Illustration 1: Product Mix

The Regal China Company produces two products daily plates and mugs. The company has
limited amounts of two resources used in the production of these products clay and labor. Given
these limited resources, the company desires to know how many plates to produce each day, in
order to maximize profit. The two products have the following resource requirements for
production and profit per item produced (i.e., the model parameters).

Product Labor (hours/unit) Clay (lbs./unit) Profit (Rs./unit)

Plate 1 4 4
Mug 2 3 5

There are 40 hours of labor and 120 pounds of clay available each day for production.

Required: Formulate this problem as a linear programming model by defining each component
of the model separately and then combining the components into a single model.

Decision Variables: The decision confronting management in this problem is how many plates
and mugs to produce. As such, there are two decision variables that represent the number of
plates and mugs to be produced on a daily basis. The quantities to be produced can be
represented symbolically as,

X1 = the number of plates to produce

X2 = the number of mugs to produce

The Objective Function: The objective of the company is to maximize total profit. The
company's profit is the sum of the individual profits gained from each plate and mug. As such,
profits from plates is determine by multiplying the unit profit for each plate, Rs. 4, by the number

16 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

of plates produced, X1. Likewise, profit derived from mugs is the unit profit of a mug, Rs. 5,
multiplied by the number of mugs produced, X2. Thus, total profit, Z, can be expressed
mathematically as

Maximize Z = 4X1 + 5X2

where
Z = total profit per day

Rs 4X1 = profit from plates

Rs 5X2 = profit from mugs

By placing the term Maximize in front of the profit function, the relationship expresses the
objective of the firm to Maximize total profit.

Model Constraints

This problem has two resources used for production, which are limited, labor and clay.
Production of plates and mugs require both labor and clay. For each plate produce, one hour of
labor is required. Therefore, the labor used for the production of plates is 1X1 hours. Similarly,
each mug requires two hours of labor; the labor used for the production of mugs is 2X2 hours.
Thus, the labor used by the company is the sum of the individual amounts of labor used for each
product.
1X1 + 2X2

However, the amount of labor represented "1X1 + 2X2" is limited to 40 hrs per day, thus, the
complete labor constraint is

1X1 + 2X2 < 40 hours

The "less than or equal to ( < )" inequality is employed instead of an equality ( = ) because the
forty hours of labor is a maximum limitation that can be used, but not an amount that must be
used, but not an amount that must be used. This allows the company more flexibility in that it is
not restricted to use the 40 hours exactly, but whatever amount necessary to Maximize profit up
to and including forty hours. This means that the possibility of "idle or excess capacity" (i.e., the
amount under forty hours not used) exists.

17 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

The constraint for pottery clay is formulated in the same way as the labor constraint. Since each
plate requires four pounds of clay, the amount of clay used daily for the production of plates is
4X1 pounds, and since each mug requires three pounds of clay, the amount of clay used for mugs
daily is 3X2. Given that amount of clay available for production each day is 120 pounds, the
material constraint can be formulated as

4X1 + 3X2 < 120 pounds

A final restriction is that the number of plates and mugs produced be either zero or a positive
value, since it would be impossible to produce negative items. These restrictions are referred to
as nonnegative constraints and are expressed mathematically as

X1 > 0, X2 > 0

The complete linear programming model for this problem can now be summarized as

Maximize Z = Rs. 4X1 + 5X2

Subject to 1X1 + 2X2 < 40

4X1 + 3X2 < 120

X1, X2 > 0

The solution of this model will result in numerical values for X1 and X2, which will maximize
total profit, Z. As one possible solution, consider X1 = 5 plates and X2 = 10 mugs. First we will
substitute this hypothetical solution into each of the constraints in order to make sure that the
solution does not require more resources than the constraints show are available.

1(5) + 2(10) < 40 25 < 40

4(5) + 3(10) < 120 50 < 120
and
4(5) + 3(10) < 120 50 < 120
Thus, neither one of the constraints is violated by this hypothetical solution. As such, we say the
solution is feasible (i.e., it is possible). Substituting these solution values in the objective
function gives Z = 4(5) + 5(10) = Rs. 70. However, the maximum profit.

18 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Now consider a solution of X1 = 10 plates and X2 = 20 mugs, This would result in a profit of
Z = Rs. 4(10) + 5 (20) = 40 + 100 = Rs. 140

While this is certainly a better solution in terms of profit, it is also infeasible (i.e., not possible)
because it violates the resource constraint or labor:

1(10) + 2(20) < 40 50 < 40

Thus, the solution to this problem must both Maximize profit and not violate the constraints. The
actual solution to this model which achieves this objective is X1 = 24 plates and X2 = 8 mugs,
with a corresponding profit of Rs. 136.

Exercises: Ingredients Mixing

Fauji Foundation produces a cereal SUNFLOWER, which they advertise as meeting the
minimum daily requirements for vitamins A and D. The mixing department of the company uses
three main ingredients in making the cereal-wheat, oats, and rice, all three of which contain
amounts of vitamin A and D. Given that each box of cereal must contain minimum amounts of
vitamin A and D, the company has instructed the mixing department determine how many
ounces of each ingredient should go into each box of cereal in order to minimize total cost. This
problem differs from the previous one in that its objective is to minimize cost, rather than
Maximize profit. Each ingredient has the following vitamin contribution and requirement per
box.

Vitamin Wheat (mg./oz.) Oats (mg./oz) Rice (mg./oz.) Milligrams Required/Box

A 10 20 08 100
D 07 14 12 70

The cost of one ounce of wheat is Rs. 0.4, the cost of an ounce of oats is Rs. 0.6, and the cost of
one ounce of rice is Rs. 0.2.

Required: Formulate this problem as a linear programming model by defining each component
of the model separately and then combining the components into a single model.

2.4 Methods of Solving Linear Programming Problems

19 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

There are two approaches to solving linear programming models. The first one is the Graphical
approach and the second is the simplex approach.

2.4.1 Graphical Approach

This is a simple and straightforward approach for determining the optimal solution to certain
linear programming problems. This is done by plotting the constraints and determining the
solution space (which is equivalent to the feasible solution) and pointing out the optimal solution
from the feasible region which is found in one of the corner points. The graphical approach is
only applicable to problems that involve two decision variables. This is because we can‟t plot an
equation having more than two variables in a two- dimensional coordinate plane.

There are about three basic steps in finding the optimal solution using the graphical approach:

1. Plotting each of the constraints

2. Determining the region or area that contains all of the points that satisfy the entire set of
constraints (the solution space)
3. Determining the optimal solution
In a nutshell, if the linear programming problem involves only two decision variables, graphical
method of solution is quite adequate. Even when three decision variables are involved, a
graphical solution can be resorted to. But this involves three dimensional representations.
Therefore we can conveniently restrict the graphical method to problems involving two decision
variables.
Illustration: Solve the following linear programming model using graphical approach:

Maximize Z = 10x1 + 16x2 (profit)

Subject to
8x1 + 20x2  120
25x1 + 20x2  200
X1, X2  0
Now we can solve the above model following the above mentioned steps.

Plotting the constraints

20 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Plotting the constraint functions starts by plotting the non-negativity constraints. This is the same
as taking only one quadrant of the coordinate plane (where both X and Y have positive values).

X2

Area of
feasibility

Non-negativity
constraints

X1

The other two constraints can be plotted usually by determining the vertical and horizontal
intercepts of them and then by connecting the two points to draw (plot) the straight line
representing the constraint function. The first constraint is plotted by connecting two points (0, 6)
and (15, 0) which are the vertical and horizontal intercepts respectively. And the second
constraint is plotted by connecting points (0, 10) and (8, 0) again the vertical and horizontal
intercepts. Look at the following figure.

21 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

X2

10

25x1 + 20x2  200

8x1 + 20x2  120

Solution space

15 X1
8

As can be seen from the above figure (shaded region), the solution space is the region that
represents all points that satisfy all the constraints (these points are called feasible solutions to
the model).

The last step is the determination of the optimal solution. The optimal solution is represented by
a point which is in the solution space. There are infinitely many points in the solution space from
which we are going to determine the point(s) representing the optimal solution to the problem.
There are different approaches to determine the optimal point. We shall discuss two approaches,
one involves graphing the objective function (objective function approach) and the other
involves examining the points at the edges of the feasible solution space (corner point approach).

Objective function approach: This approach is done by plotting the objective function like we
did in the case of constraint functions. But the objective function is not an equation like the
constraint functions. Therefore, we have to make it first an equation by assigning any number
arbitrarily to the right side. In our example the objective function 10x1 + 16x2 is not an equation
because it does not include an equality sign. We make it by simply setting it equal to any
quantity. Suppose we decide to set the objective function equal to 40. That is, 10x1 + 16x2 =
22 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

40, we can now plot the function by just following the same procedure we used to plot constraint
functions. Connecting two points (4, 0) and (0, 2.5) which are the horizontal and vertical
intercepts respectively. Look at the following figure.

10

25x1 + 20x2  200

6
B
C
8x1 + 20x2  120
L2
2.5
L1
L3
A D
4 8
15

Then we can identify the optimal point by plotting parallel lines with the objective function.
Look at l1, l2, and l3 above. These parallel lines are drawn to pass through the corner points of
the solution space. If we take l1 it passes through point (0, 6), our intention here is to check if the
point is the optimal point. This point is not the optimal point because there are points above the
line which are in the solution space and can still maximize the objective function. The same is
true for l2. But look at l3, there is no point which is above the line and in the solution space, the
line passes only through one point which is in the solution space. This indicates that this point is
the optimal solution.

To determine the optimal solution to the model we will just determine the coordinate values of
the point we have identified to be the optimal. This could be done by finding out the intersection
80 70
point of the two constraint functions. The intersection is when X1 = 17 and X2 = 17 . This

23 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

means the optimal solution to the model. The optimal profit is approximately 113. Computed by
substituting the optimal solution to the objective function

80 70
10x1 + 16x2  10( 17 ) + 16( 17 ) = 112.94

The extreme point approach: this approach is less efficient as compared with the previous one
(plotting the objective function). However, it better reflects the nature of non-graphical
approaches to solve linear programming models. This approach states that the optimal solution to
the model will occur at an extreme or corner points of the feasible region. Thus, we only
consider corner points in searching for an optimal solution. This is done by determining the value
of the objective function at each extreme point. For the example above, the corner point
approach is summarized by the following table.

Points (Coordinates) Value of the objective function

A (0, 0) 10(0) + 16(0) = 0
B (0, 6) 10(0) + 16(6) = 96
80 70 80 70
C ( 17 , 17 ) 10( 17 ) + 16( 17 ) = 113
D (8, 0) 10(8) + 16(0) = 80

Since our objective is maximization, we will take the point which gives us the largest value of
the objective function. That is point C.

Interpretation: By producing 80/17 units of X1 and 70/17 units of X2, the company can
generate a maximum profit of 113 birr.

Illustration 2: Solve the following minimization problem using the graphical technique.

Minimize Z = 3X1 + 2X2

Subject to

5X1 + 4X2 > 20

2X1 + 8X2 > 16

X1, X2 > 0

24 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

X2

X1

Points (Coordinates) Value of the objective function

A (8, 0) 3(8) + 2(0) = 24
B (3, 1.25) 3(3) + 2(1.25) = 11.5
C (0, 5) 3(0) + 2(5) = 10

Interpretation: At a minimum cost of birr 10 the company can produce 5 units of X2 only.

Self Exercises

1. The Apex Television Company has to decide on the number of 27- and 20-inch sets to be
produced at one of its factories. Market research indicates that at most 40 of the 27-inch sets
and 10 of the 20-inch sets can be sold per month. The maximum number of work-hours
available is 500 per month. A 27-inch set requires 20 work-hours and a 20-inch set requires
10 work-hours. Each 27-inch set sold produces a profit of $120 and each 20-inch
set produces a profit of $80. A wholesaler has agreed to purchase all the television sets
produced if the numbers do not exceed the maxima indicated by the market research.
A) Formulate a linear programming model for this problem.

B) Use the graphical method to solve this model.

25 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

2. The World-Light Company produces two light fixtures (products 1 and 2) that require both
metal frame parts and electrical components. Management wants to determine how many
units of each product to produce so as to maximize profit. For each unit of product 1, 1 unit
of frame parts and 2 units of electrical components are required. For each unit of product 2,
3 units of frame parts and 2 units of electrical components are required. The company has
200 units of frame parts and 300 units of electrical components. Each unit of product 1
gives a profit of $1, and each unit of product 2, up to 60 units, gives a profit of $2. Any
excess over 60 units of product 2 brings no profit, so such an excess has been ruled out.

A) Formulate a linear programming model for this problem.

B) Use the graphical method to solve this model. What is the resulting total profit?

3. The Primo Insurance Company is introducing two new product lines: special risk insurance
and mortgages. The expected profit is $5 per unit on special risk insurance and $2 per unit
on mortgages. Management wishes to establish sales quotas for the new product lines to
maximize total expected profit. The work requirements are as follows:

Work-Hours Per Unit

Department Special Risk Mortgage Work Hours Available
Underwriting 3 2 2400
Administration 0 1 800
Claims 2 0 1200

A) Formulate a linear programming model for this problem.

B) Use the graphical method to solve this model.
C) Verify the exact value of your optimal solution from part (b) by solving algebraically for the
simultaneous solution of the relevant two equations
2.4.2 Special Cases in the Graphic Approach
In solving LP models graphically, you may find some unusual situations that may arise because
of many reasons. Some of these are:

o No feasible solutions
o Unbounded problems

26 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

o Redundant constraints
o Multiple optimum solutions
No feasible solutions: This happens when there is no point in the solution space satisfying all
the constraints. In this case the constraints may be contradictory or there may be inconsistencies
among the constraints. Thus the feasible solution space is empty and the problem has no feasible
graphical approach and then by the simplex method.

Example (no feasible solution)

Maximize Z = 3X1 – 4X2

Subject to

2X1 + X2 < 12

X1 + 2X2 > 12

X1, X2 > 0

Area of feasibility for

constraint 2

2
1
Area of feasibility
for constraint 2

Unbounded problems: This is the case when we can increase the value of the objective function
without limit. This case happens if the objective is maximizing while all the constraints are
greater than constraints.

27 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

X2
An unbounded solution space

A feasible solution space for

a maximization problem

X1

Redundant Constraints: When a constraint does not form a boundary to the feasible solution
region, this constraint is a redundant constraint. Its absence (removal) does not make change to
the feasible solution space.

Redundant Constraint

Second
constraint

First
constraint

Multiple Optimal Solutions: Linear programming problems sometimes may have multiple
optimal solutions, where different combination of values of the decision variable can yield the

28 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

same optimal value for the objective function. This will happen when any of the constraint
functions is parallel to the objective function. The entire portion of this line (parallel to the
objective function) which makes the boundary of the feasible solution space will touch the
objective function. All points in this segment will yield the same optimal value to the objective
function (i.e. Points on the segment are solutions to the problem). The following graphs indicate
the above cases.

Multiple Optimal Solutions

Optimal line
segment

Objective function

2.5 The Simplex Method

The graphical approach is useful in solving linear programming models having only two
variables. When the model has more than two variables, the appropriate approach is the Simplex
procedure.

Basic Properties

The simplex method is based on the following fundamental properties:

Property 1: The collection of feasible solutions constitutes a convex set.

Property 2: If a feasible solution exists, a basic feasible solution exists where the basic feasible
solution corresponds to the extreme points (corner points) of the set of feasible solutions.
Property 3: There exist only a finite number of basic feasible solutions.

29 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Property 4: If the objective function possesses a finite maximum or minimum, then at least one
optimal solution is a basic feasible solution.
These properties can be easily verified for their plausibility with reference to the graphical
representation. The reason for these properties can be attributed to the complete linearity of the
linear programming model. We shall clarify the hypothesis of properties 2 and 4. The linear
programming problem need not necessarily have any feasible solution. This will be so when the
constraints have inconsistencies or contradictions.

2.5.1 The Simplex Procedure

The simplex approach is an algebraic technique to solve LP problems. It begins with a feasible
solution which is not optimal, and the solution is improved through continuous algebraic
manipulations (iterations) until the optimal solution is determined. The simplex procedure is a
general purpose approach that can be used in any LP model regardless of the number of decision
variables. This procedure is discussed in different conditions: Maximization problems having
only  constraints, Minimizations and Maximizations with mixed constraints (having some
constraints that are not  type).

In our previous discussion (graphical approach), we learned that to identify the optimal solution
we have to first identify the feasible solution space. This will help us to know where to
concentrate our attention in the process of finding the optimal solution. Even from the feasible
solution space the corner points (extreme points) along the boundaries of the feasible solution
space are the only solutions that are worthwhile to examine because, optimal solution is one of
these points. The simplex method has a very similar approach that enables us to do just the same!
Like we identified the feasible solution space first in the graphical approach, here also we
identify the initial feasible solution first. Then this solution will be tested for optimality using a
certain approach, if not optimal, another feasible solution (called basic feasible solution) will be
developed. This procedure will continue until the optimal solution is identified. This will be
achieved through the help of a table called the simplex tableau.

Case 1: Maximization Problems with all < constraints

1) Initial simplex tableau

30 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Write the LP model in a standard form: This is writing each constraint in a way that all the
variables are on the left side of the constraint function and the non-negative constant in the
constraint is on the right side. Then add (introduce) a slack variable to the left side of the
constraint, to make it an equality.

Slack variables are variables we introduce to the left side of  constraints which represent the
amount of unused scarce resources or capacity. A slack variable is denoted by letter „S‟ with a
subscript number to indicate the constraint to which the variable is introduced. For example S1
indicates the value of a slack variable in the first constraint.

Illustration: Given the following LP problem,

Maximize Z = 10x1+6x2+7x3
Subject to
4x1+8x2+5x3  860 ………….Material
2x1+3x2+1x3  400 ………….Labor
x1, x2, x 3 0………….Non-negativity
The standard form will be:
Maximize Z = 10x1+6x2+7x3 +0S1 +0 S2
Subject to
Material 4x1+8x2+5x3 + S1 = 860
Labor 2x1+3x2+1x3 + S2 = 400
x1, x2, x 3, S1, S2  0
Do you see the coefficients of variables in the objective function of the standard form? Slack
variables are assigned coefficients of zero because they have no any real contribution to the
objective.
(1) Develop the initial Simplex tableau
(a) List the variables across the top of the table and write the objective function coefficient
just above it.
(b) Provide one row for each constraint in the body of the tableau. List each slack variable
in the basis column, one per row.
(c) Enter the objective function coefficient of 0 in the C column for each slack variable.

31 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

(d) Compute values for row Z

(e) Compute values for row C – Z
By using the following notations for a general reference purpose,
cj = Coefficient of variable j in the objective function
aij = Coefficient of variable j in constraint i
bi = Right hand side value of constraint i
We can have the following general format for a linear programming model:

Maximize Z = c1x1 + c2x2 + c3x3 +… + cmxn +0S1 + 0S2 + 0S3 +…+ 0Sn
Subject to
a11x1 + a12x2 + a13x3 + … + a1mxn + S1 = b1
a21x1 + a22x2 + a23x3 + … + a2mxn + S2 = b2
a31x1 + a32x2 + a33x3 + … + a3mxn + S3 = b3
am1x1 + am2x2 + am3x3 + … + amnxn + Sn = bn
x1, x2, x3 … xn, S1, S2, S3… Sn  0
The initial simplex tableau for the above general format looks like:

C1 C2 C3 … 0 0 0 0 … 0 RHS
Basis X1 X2 X3 … Xn S1 S2 S3 … Sn values
S1 0 a11 a12 a13 … a1m 1 b1
S2 0 a21 a22 a23 … a2m 1 b2
S3 0 a31 a32 a33 … a3m 1 … b3
Sn 0 am1 am2 am3 … amn 1 bn
Z Optimal
C-Z Level

The standard form for the model is as developed above. Therefore we can just go to the
representation of the standard form using the simplex tableau. Before developing the initial
simplex tableau, we have to be able to understand the meaning of each bits and pieces of
information depicted in it. Before coming to this discussion it is worth saying something about
the relationship between the number of variables in a standard form linear programming model
and the number of constraint functions. If you look at the number of variables, we do have a total

32 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

of three decision variables, and two slack variables. This indicates that the number of constraints
is less than the number of variables. The number of slack variables is equal to the number of
constraints.

The simplex tableau in the simplex procedure is equivalent to the solution space and the
checking process is done for each corner points. The corner points represent the intersection of
two constraints. (i.e. the coordinate value for decision variables at the intersection point). The
variables in the basis of a simplex tableau are like variables at the intersection point. The value
for these variables at this point is found from the RHS column of the tableau. All constraints
must also be represented in the simplex tableau if the simplex procedure is to yield a solution
that takes all the constraints into account.

Having this in mind, in a maximization problem to get the optimal corner point using the
graphical approach obviously we don‟t test the origin where the value of the decision variables is
zero. But the simplex procedure starts checking from this point, where the value of all the
decision variables is zero. If we start from the origin by assuming a value of zero for all the
decision variables, and if all the constraints are to be represented in the tableau; how can we
develop the initial simplex tableau?

The initial simplex tableau represents all the constraints in the model without violating the
assumption of starting from the origin through the help of other variable(s). These variables are
slack variables. Look at the basis in following simplex tableau.

Initial tableau

C 10 6 7 0 0 RHS
Basis X1 X2 X3 S1 S2 Values
S1 0 4 8 5 1 0 860
S2 0 2 3 1 0 1 400
Z 0 0 0 0 0 0
C-Z 10 6 7 0 0
The meaning of the above simplex tableau is that the solution to the model is S1 = 860, S1 =
400, and all the decision variables are equal to zero. And the level of the objective function at
this point is 0.

33 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Then our next task is to check if the solution so determined is the optimal solution to the model.
This will be proved by looking at the net evaluation row (C-Z) row in the tableau. The rule is
check if there is any positive value in this row. If there is one, the solution is not an optimal
solution to the model. That is the level of the objective function can be improved by searching
for other combination(s) of variables. This demands the development of subsequent simplex
tableau(s). In our example, there are three positive numbers. This indicates that the initial
simplex tableau doesn‟t give us the optimal solution to the model.

2) Subsequent tableaus

(1) Identify the variable that has the largest positive value in row C-Z (the net evaluation
row). This is the next variable to come into the solution mix (basis). The largest positive
value in the above example is 10. The column containing this largest positive value is
called the pivot column; and the variable in the pivot column is the incoming variable to
bring about the improvement in the level of the objective function.

(2) Using the constraint coefficients in the entering variable‟s column (called substitution
rates), divide each one into the corresponding quantity column value. However, do not
divide by a 0 or a negative value. The smallest non negative ratio indicates which
variable will leave the solution mix.

This resulting values (ratios) so computed indicates the quantity or units of the incoming variable
that we can get by replacing it with another variable which was previously basic. In our example,
the column containing the entering variable (pivot column) as indicated below contains the
substitution rates that indicate the amount of slack variable to be given up so as to increase the
incoming variable just by one unit. That is in order to increase x1 by one unit; we need to give up
2 units of S1 and 4 units of S2. And to know the total number of x1 that we can get by giving up
any of the basic variables is determined by dividing the RHS values with corresponding
860 400
substitution rates. In our example, we will take two ratios: 4 and 2 which is 215 and 200.
This means if we give up S1 and bring x1 into the basis we will have an additional 215 units of
x1 whereas additional 200 units of x1 by giving up S2.

34 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Our objective is maximization; per unit contribution of x1 to our objective is 10. This shows that
we have to have as much x1 as possible. Therefore, the largest ratio is the largest contribution to
profit; and the least ratio means least contribution to profit. That is why the variable with the
least positive ratio is the leaving variable. S2 is therefore the leaving variable.

Pivot
column
C 10 6 7 0 0 RHS
Basis X1 X2 X3 S1 S2 values
S1 0 4 8 5 1 0 860 860 4 = 215

S2 0 2 3 1 0 1 400 400 2 = 200

Leaving
Z 0 0 0 0 0 0 variable

C-Z 10 6 7 0 0

Entering
variable Pivot element

(3) Compute replacement values for the leaving variable: Divide each element in the
pivot row by the pivot element. These resulting values will be the values in the
same row (major row) of the new tableau. This row will also contain the new
variable (entered the solution mix) together with its objective function coefficient
next to it in column C. Look at the following tableau.

C 10 6 7 0 0 RHS
Basis X1 X2 X3 S1 S2 Values
S1
X1 10 1 3/2 1/2 0 1/2 200
Z
C-Z

(4) Compute values for each of the other constraint equations: This will be done in
such a way that all the entries in the pivot column of the previous tableau will be
converted from top to down with zero except the one which is the pivot element
35 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

by the application of elementary row operations. Every other entry in the heart of
the former tableau will also be converted as a result of the row operations to make
the entries for the new tableau.

C 10 6 7 0 0 RHS
Basis X1 X2 X3 S1 S2 Values
S1 0
X1 10 1 3/2 1/2 0 1/2 200
Z
C-Z

The entries in the pivot column are now converted into zero except the pivot element. By the
way, would you go back to the initial simplex tableau and see what is common to all the columns
containing basic variables?

As you might have successfully realized, these columns are unit columns (having entries of all
zeros and only a single one at the intersection point of the column and the row containing that
same variable). For example look the column containing S1 one of the basis, it has a one in the
first row where it is in; and a zero in the other row. To develop our new tableau in the same
fashion, we will identify appropriate row operations that can yield the desired outcome.

Elementary row operations may be:

(a) Multiplying (dividing) all of the elements in a row by a constant.

(b) Adding or subtracting the multiple of a row to or from another row.

The desired value in the other entry for the pivot column is zero. But this value was 4 in the
previous tableau. So we have to search for the row operation that helped to convert 4 into 0. This
can be achieved by multiplying the second row of the new tableau by -4 and adding it to the
entries in the first row of the former tableau. This way, entries in the second tableau are
constructed.

36 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

2nd Simplex tableau

C 10 6 7 0 0 RHS
Basis X1 X2 X3 S1 S2 values
S1 0 0 2 3 1 -2 60 -4R2 +R1
X1 10 1 3/2 1/2 0 1/2 200
Z 10 15 5 0 10 2000 = Profit
C-Z 0 -9 2 0 -10

(5) Compute values for row Z: For each column take the sum of the products of the row
coefficients (constraint coefficients) and coefficients of basic variables (row values
in column C). For example the first entry is determined as: 0(0) + 1(10) = 10

(6) Compute values for row C – Z (the net evaluation row): For each column, subtract
the value in row Z from the objective function coefficient values in row C at the top
of the tableau. For example the first entry is determined as: 10 – 10 = 0

(7) Test the solution for optimality by looking if there is any negative value in the C – Z
row. If there is a positive value, the solution is not optimal and hence we have to
develop other tableau. This is done by repeating step B. This process will continue
until you get an optimal solution (all the entries in the last row are converted into
zeros or negatives but no positives).

The pivot column is the one with the largest positive value in the net evaluation row. The only
positive value in the row is 2. The column containing this value is therefore the pivot column as
indicated below.

C 10 6 7 0 0 RHS
Basis X1 X2 X3 S1 S2 values
S1 0 0 2 3 1 -2 60
X1 10 1 3/2 ½ 0 1/2 200
Z 10 15 5 0 10 2000
C-Z 0 -9 2 0 -10

This will lead us to the development of the fourth tableau. The major row in the fourth tableau is
the first row (the pivot row in the third tableau). Then by dividing every element in the pivot row

37 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

by the pivot element, we develop the major row of the new tableau. The remaining entries are
determined through the help of elementary row operations as usual. Look at the following
tableau:

4th Tableau

C 10 6 7 0 0 RHS
Basis X1 X2 X3 S1 S2 values
X3 7 0 2/3 1 1/3 -2/3 20
X1 10 1 7/6 0 -1/6 5/6 190 -1/2(R1) + R2
Z 10 70/6 7 4/9 11/3 2040 = Optimal profit
C-Z 0 -5.67 0 -4/9 -11/3

The fourth tableau is the optimal tableau because there is no any positive value in the net
evaluation row. This indicates that the optimal level of profit is achieved when: x1 = 20, x2 = 0,
x3 =190, S1 = 0, S2 =0 and S3 = 0. The maximum profit is 2,040.

Case 2: Maximization with Mixed Constraints

As we have discussed earlier, the simplex technique requires that the LP model should be in its
standard form first. To put an LP model with all constraints having  in standard form, we
added a slack variable to the left sides of the constraint functions. But constraints with  and =
signs will be handled differently. Our attention in this section is to solve LP models with all the
=,  , and  signs. This is what is meant by mixed constraints.

In the case of equality constraints slacks are not applicable. These constraints require an exact
(precise) amount. But to use the simplex technique in solving a maximization problem we
assume to start from the origin by making the values of decision variables zero (excluding them
from the basis of the initial simplex tableau). In the simplex procedure we need to represent each
constraint function through the help of a variable. This implies that having a variable that will
serve this end in the simplex tableau is a must. Therefore, we will introduce a variable to the
equality constraint called an artificial variable. Artificial variables have no economic
interpretations, they merely serve as a device to enable us use the simplex procedure. Because of
this fact, after serving their purpose, artificial variables should leave the simplex process
(solution mix) as quickly as possible. The optimal solution should never contain an artificial
38 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

variable with non-zero value (artificial variable should not appear in the basis of the final
simplex tableau).

Example: Let us assume we do have the following constraint in an LP model under

consideration

2x1 + 10x2 = 30,

Its standard form will be: 2x1 + 1x2 + A1 = 30

A1 does mean an artificial variable in the first constraint of an LP model.

What will happen if our constraint is with  sign? In a  constraint, the restriction is to meet a
specific lower limit. The constraint is never allowed to have a value which is less than the
minimum amount designated by the constraint. But it can have a value which exceeds the
minimum designated amount. This excess amount is referred to as Surplus. This surplus amount
is subtracted from the left side of the constraint function to put it in standard form.

Example: 4x1 + 11x2  60 will be look like:

4x1 + 11x2 – S1 = 60, where S1 = the surplus amount for the first constraint.

By subtracting the surplus, the constraint becomes equality. Therefore, to allow for the initial
solution that will be less than that amount, an artificial variable must be added. Thus the above
constraint will be put in its standard form as:

4x1 + 11x2 – S1 + A1 = 60

Our next vital issue is how to express these surplus and artificial variables in the objective
function. Surplus variables are expressed in exactly the same way as slack variables. They are
assigned coefficients of zero.

Assigning coefficients for artificial variables depends on whether the problem is a maximization
or minimization problem. Moreover, we don‟t want the artificial variables to appear in the final
solution because they are not real variables.

In a maximization problem, we assign a large negative number denoted by M to facilitate the

solution. Which means, the contribution of the variables will be negative (reduction) to the level
of the objective function for a maximization problem (opposing the objective of the model). The
39 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

simplex procedure does exclude a basic variable that has least contribution to the objective
function and brings another variable (previously non basic) with the most desirable contribution
to the basis. This being the procedure, assigning large negative number to be the coefficient of
the artificial variable in the objective function for a maximization problem will facilitate the
exclusion of the artificial variable from the basis.

For example

Maximize 2x1 + 3x2 + 0S1 + 0S2 - MA2 indicates that the first constraint in the model is a
 constraint and the second is a  constraint.

In a minimization problem, we assign a large positive number to be the coefficient of the

artificial variable. This will have the same effect on the variable under consideration. Here also
the large positive number is denoted by M.

Illustration:
Maximize Z= 6x1 + 8x2
Subject to
x2  4
x1 + x2 = 9
x1 + 2x2  24
x1, x2  0
As usual, the simplex procedure starts solving LP models first by putting them into their standard
form. The standard form to the above problem is:

Maximize Z = 6x1 + 8x2 + 0S1 + 0S3 – MA2 – MA3

Subject to
x2 + S1 = 4
x1 + x2 + A2 = 9
6x1 + 2x2 – S3 + A3 = 24
x1, x2, S1, S3, A1, A3  0
Then we will develop the initial simplex tableau.

40 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

The initial simplex tableau

C 6 8 0 0 -M -M RHS
Basis X1 X2 S1 S3 A2 A3 values
S1 0 0 1 1 0 0 0 4
A2 -M 1 1 0 0 1 0 9
A3 -M 6 2 0 -1 0 1 24
Z -7M -3M 0 M -M -M -33M
C-Z 6 + 7M 8 + 3M 0 -M 0 0
The next step is testing the initial simplex tableau for optimality.

Remember that the test is done by checking whether there is a positive number in the net
evaluation row, and taking the largest one if there are more than one positive numbers in that
row. So, what is the largest positive number?

The variable M is just a very large number, therefore when we try to identify the largest positive
number, what we do is just to take the positive M with the largest coefficient regardless of the
constant number added with it. In the above tableau, we do have two positive numbers, 6 + 7M
and 8 + 3M. From these two, the first one is the larger even though 8 is greater than 6. This is
because M is very large as compared with the difference between 8 and 6. This indicates that the
next variable to enter the solution mix is X1.

The leaving variable is determined in the same way as we did in our previous discussions. The
one with the least positive ratio will be the leaving variable.

C 6 8 0 0 -M -M RHS
Basis X1 X2 S1 S3 A2 A3 values
S1 0 0 1 1 0 0 0 4
A2 -M 1 1 0 0 1 0 9
A3 -M 6 2 0 -1 0 1 24
Z -7M -3M 0 M -M -M -33M Leaving
variable
C-Z 6 + 7M 8 + 3M 0 -M 0 0

Entering variable

41 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Don‟t forget to exclude the third artificial variable from the simplex tableau when you develop
the second tableau. The second tableau will look like:

Second Tableau

C 6 8 0 0 -M RHS
Basis X1 X2 S1 S3 A2 values
S1 0 0 1 1 0 0 4
A2 -M 0 23 0 16 1 5
X1 6 1 13 0 -1 6 0 4
Z 6 2 - 2 3M 0 -1 - 1 6 M -M 24 – 5 M
C-Z 0 6 + 2 3M 0 1+ 0
1 6M
The largest positive number in the net evaluation row is 6 + 2 3 M. This shows that the next
variable to enter the basis is X2. And the leaving variable is S1. Therefore, we develop the next
tableau by taking the above facts into consideration.

Third Tableau

C 6 8 0 0 -M RHS
Basis X1 X2 S1 S3 A2 values
X2 8 0 1 1 0 0 4
A2 -M 0 0 - 3
2 16 1 73
X1 6 1 0 -1 3 -1 6 0 83
Z 6 8 6 + 2 3M -1 - M 6 -M 48 - 7 3 M
C-Z 0 0 -6 - 2 3 M 1+ M 6 0

Still we do have a positive number in the net evaluation row. Therefore, we have to search for a
better solution. We need to determine the next variable to enter the solution mix and the one
which must leave the basis. Look at the following table.

C 6 8 0 0 -M RHS
Basis X1 X2 S1 S3 A2 values
X2 8 0 1 1 0 0 4
A2 -M 0 0 -2 3 16 1 73
X1 6 1 0 -1 3 -1 6 0 83
Z 6 8 6 + 2 3M -1 - M 6 -M 48 - 7 3 M

42 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

C-Z 0 0 -6 - 2 3 M 1 + M 6 0
The next tableau will be developed by excluding A2 from the basis and bringing S3 to the basis.

Fourth Tableau

C 6 8 0 0 RHS
Basis X1 X2 S1 S3 values
X2 8 0 1 1 0 4
S3 0 0 0 -4 1 14
X1 6 1 0 -1 0 5
Z 6 8 2 0 62
C-Z 0 0 -2 0
Look at the above tableau. There is no positive number in the C-Z row. Therefore, the fourth
tableau is the final tableau.

Case 3: Simplex Minimization

The simplex procedure to solving minimization problems is almost the same as the procedure for
maximization with mixed constraints except the following differences:

 The M coefficients in the objective function are given positive signs instead of
negative signs.

 The selection of the variable to enter the solution is based on the largest negative
value in the C – Z row.

Note also that minimization problems always require at least one artificial variable.

What do the M variables and the values in the C – Z row indicate? If you know the answer to this
question, you will also know the reason behind the above differences between maximization and
minimization problems.

M, the coefficient of artificial variables when we indicate them in the objective function, has
same meaning as other coefficients of variables in the objective function. It indicates the extent
of the artificial variable‟s per unit contribution to the level of the objective function.

43 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

The values in the net evaluation row indicate the extent of possible increase to the level of the
objective function as a result of bringing an additional unit of the variable in that column to the
solution mix.

Therefore, in a minimization problem, a large positive coefficient to a variable in the objective

function means a large undesirable impact towards achieving the objective of the model
(minimizing). And a large negative number in the net evaluation row means large desirable
contribution to the level of the objective function.

The first one, creating an adverse impact towards achieving the objective seams paradox. The
reason is to exclude the artificial variable (a variable with no real meaning) from the basis and
the tableau as a whole as quickly as possible. Assigning a large positive coefficient is the
appropriate measure since we are solving the model using the simplex procedure. If you consider
the simplex procedure each iteration in the procedure is about excluding a variable with least
contribution to the achievement of the objective, and replacing it with another variable which is
the most desirable contributor of those which previously were not in the basis. Therefore,
assigning a large positive number to be the coefficient of an artificial variable will force the
variable to be the first to leave the solution mix.

Selecting the largest negative number from the net evaluation row is a straight forward action in
a minimization problem. Large negative number in this row means large deduction to the level of
the objective function. This will facilitate the achievement of the objective of the model
(minimization).

To sum up; in minimization problems, while the variable with the largest negative value in the
net evaluation row enters the next tableau, the variable with the least positive ratio will leave the
solution mix like the maximization case.

Example: Solve the following linear programming model using the simplex method.
Minimize 6X1 + 9X2
Subject to
10X1 + 4X2 > 400
X2 > 14
X1, X2 > 0
44 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

Standard form
Minimize 6x1 + 9x2 + 0S1 + 0S2 MA1 + MA2
Subject to
10x1 + 4x2 - S1 + A1 = 400
X2 – S2 + A2 = 14
X1, X2 > 0
Initial tableau
C 6 9 0 0 M M RHS
Basis X1 X2 S1 S2 A2 A3 values
A2 M 10 4 -1 0 1 0 400
A3 M 0 1 0 -1 0 1 14
Z 10M 5M -M -M M M 414M
C-Z 6 -10M 9 - 5M M M 0 0
Because 6 -10M is the largest negative C-Z value, X1 will be the entering variable in the second
simplex tableau. When we divide the RHS with the X1 column (400/10 = 40 and 14/o =
undefined), the smallest positive ratio is 40. As a result, A2 will be the leaving variable. That
means in the second simplex tableau, A2 will be out of the basic solution and in place of A2, X1
will come to the solution.

Second tableau

C 6 9 0 0 M RHS
Basis X1 X2 S1 S2 A3 values
X1 6 1 2/5 - 0 0 40
1/10
A3 M 0 1 0 -1 1 14
Z 6 12/5+M -3/5 -M M 240+14M
C-Z 0 33/5 - M 3/5 M 0
The second tableau is not the optimal tableau because there is a negative number in the net
evaluation row (C-Z row). This indicates that we can get a better solution by bringing the
variable having this negative value (X2 in this case) to the basis. Therefore, the 3rd tableau is
developed by taking this concept into consideration. Look at the following tableau. Because
33/5-M is the largest negative, X2 will be the entering variable and A3 will be the leaving
variable (since 14/1 = 14 is the smallest positive ratio).

45 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Third tableau

C 6 9 0 0 RHS
Basis X1 X2 S1 S2 Values
X1 6 1 0 - 2/5 34.4
1/10
X2 9 0 1 0 -1 14
Z 6 9 -3/5 -6.6 332.4
C-Z 0 0 3/5 6.6

Since there is no any negative value in the net evaluation row, the 3rd tableau is the optimal
tableau. Therefore, the optimal solution to the above linear programming model is: X1 = 34.4
and X2 = 14. The level of the objective function (minimum cost) is 332.4. There is no surplus
variable in the final tableau. This means, the solution to S1 and S2 is zero.

2.6 Some Complication and their Resolution

The followings are some complication and their resolution (special issues) in the simplex
method:

2.6.1 Unrestricted Variables

Thus far we have made the restrictions for the decision variables to be non-negative in most of
the practical or real life problems. But there may be situations in which this is not always the
case. However, the simplex method assumes non-negative variables. But if the problem involves
variables with unrestricting in sign (the variables can take positive or negative or zero value), the
problem can be converted into an equivalent one involving only nonnegative variables.

A variable unrestricted in sign can always be expressed as the difference of two non-negative
variables. If x is the variable unrestricted in sign, the same can be replaced with two other
variables say m and n which are nonnegative ( > 0 ). Thus we have x = m – n and since m and n
are non-negative, the value of x will be positive if m n, negative if m n and zero if m = n. Thus
the values of m and n, which are non-negative, will decide the fate of the variable x. Since the
simplex method examines the basic feasible solutions (extreme points), it will always have at
least one of these two no-negative variables set equal to zero.

46 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

To illustrate we consider the following example.

Example
Maximize Z = 2x + 5y
Subject to
x<4
y<3
x+y<6
y>0
2.6.2 Tie for Leaving and Entering Variables

Dear student, think about what will you do to develop the next simplex tableau after recognizing
that a tableau is not optimal. Normally you will identify the leaving and entering variables and
make the appropriate replacement. In some cases however, when you are determining the leaving
variable, there may be a tie for the lowest positive ratio. Such a case is known to be the case of
degeneracy. If you try to generate the next tableau by just taking any one variable with the least
ratio, you encounter no problem in the procedure but there will be no improvement in the
solution (level of the objective function); it will rather be the same as the previous solutions.

2.6.3 Unboundedness and Multiple optimal solutions

A) Unboundedness

When the problem was not correctly formulated, constraints don‟t properly bind the solution, or
a minimization problem incorrectly stated as a maximization problem; unboundedness can be the
case. This condition can easily be identified in the simplex procedure. When we try to determine
the leaving variable in the construction of a new tableau, we have said that we identify the least
positive ratio of values in the RHS column and values in the pivot column. But in this special
case all the ratios will be either negative or zero. Therefore we can‟t identify the leaving variable.

Example: Solve the following linear programming model using the simplex procedure.
Maximize Z = 2x1 + 3x2
Subject to

47 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

-x1 + x2  1
-1/2x1 + x2  3
x1, x2  0
The simplex tableau after some iteration is:
C 2 3 7 0 RHS
Basis X1 S1 S1 S2 values
X2 3 0 1 -1 2 5
X1 2 1 0 -2 2 4
Z 2 3 -7 10 23
C-Z 0 0 7 -10
Even though there is a positive value in the net evaluation row indicating that the solution is not
optimal (can be improved by bringing the variable in the pivot column into the solution mix), we
can‟t determine the variable to be replaced because there is no positive ratio in the pivot column.
This special condition is referred to as unboundedness.

B) Multiple optimal solutions

This is the condition when same maximum value of the objective function might be possible
with a number of different combinations of values of the decision variables. It occurs when the
objective function is parallel to any of the binding constraint function. Two functions are said to
be parallel if the ratio of coefficients of variables is the same. When using the simplex approach,
we can recognize alternate optima if the C-Z row contains a zero value for one or more of the
non-basic variables in the final simplex tableau.

Self Exercises

1. A manufacturer has two products P1 and P2 both of which are produced in two steps by
machines M1 and M2. The process times per hundred for the products on the machines are:-
Products M1 M2 Contribution (per 100 units)
P1 4 5 10 Birr
P2 5 2 5 Birr
Available Hours 100 80

48 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Required: The manufacturer is in a market upswing and can sell as much as he can produce of
both products. Formulate the mathematical model and determine optimum product mix using
simplex method.

2. A manager produces three items A, B and C. He has the possibility of applying two strategies:
produce all the three items or any two of them. Products A and C pass through shops I and II,
whereas B is further processed in shop III. Each shop has limited available hours. Hours
available in shops I, II and III are 162 hours, 189 hours and 5 hours respectively. Profit per
unit from A, B and C is Birr 27, Birr 29 and Birr 25 respectively. The following table gives
the processing time of different items in different shops.

Items
Shops A B C
I 27 12 12
II 27 15 25
III 0 3 0

Required: Formulate the above problem as LPM and find the optimum production of A, B and C
so as to maximize profit.
2.7 Duality in Linear Programming Problems

Assume that there are two companies (Company X and Company Y) and also assume that
company X sells its products to company Y. The objective of company X is profit maximization
and that of Company Y is cost minimization. That means if you formulate the LPM of company
X, on the other side you have formulated the LPM of company Y and vice versa. This is the
concept of duality.
Linear programming problems have two forms. The original formulation of a problem is known
as its Primal form. The other form formulated from the primal is the dual form. The dual is the
“mirror image” of the primal. The solution to the primal contains the solution to the dual and
vice versa. Therefore, solving either of the two is enough to determine the solutions.

Analysis of the dual can help the decision maker assess the potential impact of a new product by
determining the marginal value of resources. This is generally known to be the economic

49 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

interpretation of the dual. This is discussed later in this section. But first let‟s have a look at the
technical aspects of the dual-its formulation.

Formulating the Dual

The dual for a primal problem of maximization with all  constraints, is a minimization problem
with all  constraints The constraint coefficients of the primal are constraint coefficients of the
dual except that the coefficients of first “row” of the primal become the coefficients of the firs
“column” of the dual, and the coefficients of the second “row” of the primal become the
coefficients of the second “column” of the dual; and so on.

The following procedures can be followed to formulate the dual:

 Change maximizations into minimization and minimizations in to maximization.

 Coefficients of the objective function in the primal will be RHS in the dual and RHS
values in the primal will be coefficients of the objective function in the dual.

 ≤ Constraints in the primal will be changed to ≥ in the dual and vice versa.

Example: Formulate the dual of the following problem

Minimize 5x1 + 7x2 +9x3

Subject to
20x1 + 10x2 +30x3  300
40x1 + 5x2 +10x3  200
X1, x2, x3  0
The objective function for the dual is

Maximize 300y1 + 200y2

We usually use y‟s as variables to the dual. The reason is to differentiate it from variables of the primal.

The constraints of the dual are developed in the following way:

20y1 +40y2  5
10y1 + 5y2  7
30y1 + 10y2  9
Y1, y2  0
50 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

Dear students, please notice the following facts from the above dual constraints:

 The number of primal decision variables is the same as the number of dual constraints.

(i.e. there are three decision variables in the primal and three constraints in the dual)

 The RHS values of the dual constraints are equal to the objective function coefficients of
the primal taken in order.

(The RHS values in the dual; that is 5, 7, and 9 are the coefficients of decision variables
in the primal objective function)

 The coefficients of the primal constraints are also the coefficients of the dual constraints
but in a different pattern.

Example: Formulate the dual of the following linear programming model

Maximize Z = 60x1 + 50x2

Subject to
4x1 + 10x2  100
2x1 + x2  22
3x1 + 3x2  39
x1, x2  0
The dual to the above LP model is:

Minimize Z = 100y1 +22y2 +39y3

Subject to

4y1 +2y2 + 3y3  60

10y1 + y2 +3y3  50

y1, y2, y3  0

Solution Values of the Dual

As it was discussed earlier, the dual is the mirror image of the primal. As a result, if we solve the
primal LPM using the simplex method, we can find the solution values of the dual without

51 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

solving it or if we solve the dual LPM, we can find the solution values of the primal without
solving.

Primal Dual
X1 C-Z value of S1
X2 C-Z value of S2
S1 C-Z value of Y1
S2 C-Z value of Y2
C-Z value of S1 Y1
C-Z value of S2 Y2
C-Z value of X1 S1
C-Z value of X2 S2
Zmax Zmin

Consider the final simplex tableau for the above primal LP model

Final tableau of the Primal

C 60 50 0 0 0 RHS
Basis X1 X2 S1 S2 S3 values
S1 0 0 0 1 6 -16/3 24
x1 60 1 0 0 1 -1/3 9
x2 50 0 1 0 -1 2/3 4
Z 60 50 0 10 40/3 740
C-Z 0 0 0 -10 -40/3

Primal Solutions

X1 = 9, X2 = 4, S1 = 24, S2 = 0, S3 = 0 and profit = 740 birr

Dual solutions

Y1 = 0, Y2 = 10, Y3 = 40/3, S1 = 0, S2 = 0 and cost = 740 birr

52 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Final tableau of the dual

C 100 22 39 0 0 RHS
Basis y1 y2 y3 S1 S2 values
y3 39 16/3 0 1 1/3 -2/3 40/3
y2 22 -6 1 0 -1 1 10
Z 76 22 39 -9 -4 740
C-Z 24 0 0 9 4
Primal shadow prices

Primal solution quantities

Primal Solutions

X1 = 9, X2 = 4, S1 = 24, S2 = 0, S3 = 0 and profit = 740 birr

Dual Solutions

Y1 = 0, Y2 = 10, Y3 = 40/3, S1 = 0, S2 = 0 and cost = 740 birr

The following can be summarized about the solutions of the dual and the primal as can be seen
from the above tableaus:

1. If the primal problem has an optimum solution, the dual will also have an optimum
solution and vice versa. The optimum solution of the dual and the primal are the same

2. Given the final tableau of the dual, the optimal solutions for decision variables of the
primal are given by the C – Z row values of slack variables in the dual

3. Given the final solution of the primal, the solution for the decision variables of the dual
are determined to be the Z row values of slack variables (shadow prices) of the primal;
and the solution for slack variables of the dual are given by the C – Z row values of
decision variables of the primal

This indicates the technical importance of formulating the dual. That is to say, if you encounter
problems in solving the primal problem, you can solve the dual and vice versa. Generally, we
can reduce our computing time by developing the two models and solving the easier.

53 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Beyond the above importance (technical), the dual has an economic interpretation. The following
paragraph is about the economic interpretation of the dual.

2.8 Sensitivity Analysis

Sensitivity analysis also known as post optimality analysis is concerned about the study of
possible changes to a linear programming model and the associated impacts to the solutions to
the model and to the level of the objective function. Such a kind of analysis is done after the
determination of the optimum solution to the model. That is why we refer it as “post optimality
analysis.” It is also called “sensitivity analysis” because we are observing the sensitivity of the
model to possible changes.

When we were developing the LP models, we assumed that we know all the parameter values for
certain (Certainty assumption). However, in reality, the parameter values are just educated
guesses. Therefore, the optimum solutions computed under this assumption may not be optimal
depending on how sensitive that solution is to alternate values of parameters. That is why the
decision maker needs to perform sensitivity analysis before implementing the solution.

Changes to a model might happen due to changes in any of the parameters (coefficients of the
objective function, to the coefficients of the constraint functions, or to the RHS values of the
constraints). In our discussion in this section, the possible changes to the model will be seen
being classified into two categories. The first one is a change to the coefficients of the objective
function, and the second is a change to the RHS values of the constraints. But we will not discuss
the change to the coefficients of constraints.

Changes can also be resulted due to changes in the product lines especially when introducing a
new product. To deal with these kinds of changes, we use a technique called “duality.” Duality is
another way of formulating (representing) linear programming models. We shall analyze the
above changes by using the final simplex tableau (optimal solution) as a starting point.

2.8.1. A Change in the RHS of a Constraint

Our analysis will be made by looking at the impact one unit change in the right hand side (RHS)
of a constraint would have on the value of the objective function. If we know this, we will be

54 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

able to determine the total impact of change in the RHS of a constraint to the level of the
objective function. But this kind of analysis has some other associated questions:

 How can we determine the impact of a per unit change in the RHS value of a constraint?

 To what extent can the RHS values of a constraint increase or decrease without affecting
the current optimal solution?

As indicated in the beginning, our analysis is based on the optimal solution of a linear
programming problem. Therefore, all our discussions right now are based on final simplex
tableaus. The following simplex tableau is a final tableau for an LP model representing an LP
problem presented below for simplicity purpose.

Example 1: The following is an LP model representing the problem for a certain company and
its final tableau is also given below.

Maximize 60X1 + 50X2

Subject to

4X1 + 10X2  100 Assembly time constraint

2X1 + X2  22 Inspection time constraint

3X1 + 3X2  39 Storage space constraint

X1, X2  0

C 60 50 0 0 0 RHS
Basis X1 X2 S1 S2 S3 values
S1 0 0 0 1 6 -16/3 24
x1 60 1 0 0 1 -1/3 9
x2 50 0 1 0 -1 2/3 4
Z 60 50 0 10 40/3 740
C-Z 0 0 0 -10 -40/3
Remember that when changing an LPM with all constraints ≤ into standard form, we add S1 to
the first constraint, S2 to the second constraint, and S3 to the second constraint. Hence, in our
case, S1, S2 and S3 will represent assembly time, inspection time and storage space,
respectively.

55 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Now let‟s go back to the above two questions. To get an answer to the first question (determining
the per unit impact of a change in the RHS value of constraints to the objective function), look at
the slack column values. For instance, if we increase S2 (inspection time) by 1 hour, what will
happen to the basic variables? The answer is that S1 will increase by 6 units, X1 will increase by
1 unit and X2 will decrease by 1 unit. The Z row values of the above tableau are called “shadow
prices.” That is 0, 10 and 40/3. They indicate the impact that one unit change in the constraint
would have in the value of the objective function. To be specific, if the value of the second
constraint in the above problem increases just by one unit (i.e. inspection time rose from 22 hrs
to 23 hrs), profit will be increased by 10. This value (10) also shows the amount by which the
value of the objective function will be decreased due to a unit decrease in the level of the
constraint. If the value of the third constraint (storage space) increases by one unit, the level of
the objective function will also be increased by 40/3. But a unit increase or decrease in the first
constraint has no effect to the level of the objective function.

However, knowing the impact of a unit change is not sufficient; because, we cannot make
changes to the values of the constraints without limit. For example, we have said that the unit
increase in inspection time will result in an increase to the level of the objective function by 10.
This means, if we increase inspection time by 2 units, the level of the objective function will be
increased by 20. But, we cannot increase time (a precious resource) unlimitedly. And also we
cannot decrease it without limit, because we need time to produce our product. Therefore, we
should be informed that we can have a change to the RHS value of constraints only within a
certain range. This indicates that, our effort to analyze the impact of changes to the RHS values
of constraints should also include knowing the range within which the possible change to the
RHS values of constraints can happen and still have the same shadow price. This range is called
the “range of feasibility” or “the RHS range.” This leads us to the second question we raised at
the beginning of our discussion.

The range of feasibility is the range over which the RHS value of a constraint can decrease or
increase without affecting the current optimal solution.

We can determine the upper and lower limits of the range of feasibility from the final simplex
tableau. To do so, take the ratios of the entries in the RHS column to the corresponding entries in

56 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

each slack column. This will give you the amount by which the level of the constraint function
can be increased or decreased. This is summarized as follows:

For maximization problems,

 Allowable decrease: The smallest positive ratio

 Allowable increase: The smallest negative ratio/the negative ratio close to zero

For minimization problems,

 Allowable decrease: The smallest negative ratio/the negative ratio close to zero

 Allowable increase: The smallest positive ratio

This means, for maximization problems, we add the smallest negative ration to the original RHS
value to determine the upper limit of the range of feasibility and we subtract the smallest positive
ratio from the original RHS value to determine the lower limit of the range of feasibility and the
reverse will be true for minimization problems. Look at the following table.

Slack variables
S1 S2 S3 RHS/S1 RHS/S2 RHS/S3
24
1 6 -16/3 24/1=24 24/6 =4 16 / 3 = -4.5
9
0 1 -1/3 9/0 = Undefined 9/1 = 9 1 / 3 = -27
4
0 -1 2/3 4/0 = Undefined 4/-1 = -4 2/3 =6
Allowable decrease 24 4 6
Allowable increase No –ve ratio -4 -4.5
Original Amount 100 22 39
Upper Limit None 22 + 4 =26 39 + 4.5 = 43.5
Lower Limit 100-24=76 22 – 4 = 18 39 – 6 = 33
The range of feasibility for each of the constraints is:

Assembly time (S1), from 76 hrs to no upper limit or 76 ≤ S1 ≤ ∞

Inspection time (S2), from 18 hrs to 26 hrs or 18 ≤ S2 ≤ 26

Storage space (S3), from 33 cubic feet to 43.5 cubic feet or 33 ≤ S3 ≤ 43.5

To give more meaning to the above ranges, without affecting the current optimal solution, S1 can
decrease up to 76 or can increase without any limit, S2 can decrease up to 18 or can increase up
to 26 and S3 can decrease up to 33 or can increase up to 43.5.
57 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

For example, let us assume that inspection time (S2) is increased by 3 hours. The impact is
calculated as:

Basis S2 Current Solution Change Revised solution

S1 6 24 +3 (6) = +18 42
X1 1 9 +3(1) = +3 12
X2 -1 4 +3(-1) = -3 1
Z 10 740 +3(10) = 30 770

Self-Exercise

Find the revised solution values assuming that storage space (S3 is decreased to 34 units
meaning that S3 is decreased by 5 units)

Self-Assessment Questions (SAQ2)

1. Consider the following LP model and solve it using the simplex method

Minimize Z = 40X1 + 50X2

Subject to

2x1 + 3X2 ≥ 12

X1 + X2 ≥ 30

2X1 + X2 ≥ 20

X1, X2 ≥ 0

2. Solve the following linear programming model using the simplex procedure.

Minimize Z = 50x1 + 60x2

Subject to

X1 + X2 ≥ 1000

X1 ≥ 300

X2 ≥150

X1, X2 ≥ 0

58 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

3. A stereo equipment manufacturer can produce two models A and B of 40 and 80 watts total
music power each. Each model passes through three different manufacturing divisions 1, 2 and 3
where model A takes 4, 2.5 and 4.5 hrs each and model B takes 2, 1 and 1.5 hrs each. The three
divisions have a maximum of 1600, 1200 and 1600 hours every month respectively. Model A
gives a contribution of Rs. 400 each and B gives Rs. 100 each. Assuming abundant product
demand, find out the optimum product mix and the maximum contribution through simplex
method.

4. Clearly articulate the difference between the graphical approach and the simplex method for solving
LPP.
5. Determine the range of optimality for the variables in the following final simplex tableau of a
maximization linear programming problem.
C 60 50 0 0 0 RHS
Basis X1 X2 S1 S2 S3 values
S1 0 0 0 1 6 -16/3 24
x1 60 1 0 0 1 -1/3 9
x2 50 0 1 0 -1 2/3 4
Z 60 50 0 10 40/3 740
C-Z 0 0 0 -10 -40/3

6. Given this problem and its final tableau:

Minimize 10x1 + 3x2
Subject to
2x1 + 1x2 ≥ 80
2x1 + 4 x2  200
x1, x2  0
C 10 3 0 0 RHS
Basis X1 X2 S1 S2 values
S2 0 6 0 -4 1 120
x2 3 2 1 -1 0 80
Z 6 3 -3 0 240

59 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

C-Z 4 0 3 0

a. Determine the range of feasibility for each of the constraints.

b. Determine the range of optimality for the decision variables.
c. When do you think that x1 will be part of the basic solution? Determine the range of
insignificance of this variable.

60 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

CHAPTER THREE

TRANSPORTATION AND ASSIGNMENT

Introduction

Many practical problems in operations research can be broadly formulated as linear

programming problems, for which the simplex this is a general method and cannot be used for
specific types of problems like, transportation models, and transshipment models and the
assignment models. These models are also basically allocation models. We can adopt the
simplex technique to solve them, but easier algorithms have been developed for solution of such
problems. The following sections deal with the transportation problems and their streamlined
procedures for solution.

Chapter 3 emphasized the wide applicability of linear programming. We continue to broaden our
horizons in this chapter by discussing two particularly important (and related) types of linear
programming problems. One type, called the transportation problem, received this name because
many of its applications involve determining how to optimally transport goods. However, some
of its important applications (e.g., production scheduling) actually have nothing to do with
transportation. The second type, called the assignment problem, involves such applications as
assigning people to tasks. Although its applications appear to be quite different from those for
the transportation problem, we shall see that the assignment problem can be viewed as a special
type of transportation problem.

Learning Outcomes

After studying this chapter, you should be able to

 Understand the basic concepts of transportation and assignment problems

 Solve transportation problems at a maximum profit or minimum cost level

 Handle special cases of a transportation problem

 Solve assignment problems optimally

61 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

 Handle special cases of an assignment problem

3.1 Transportation Problem

The transportation problem arises in the distribution of material between different locations. The
problem is to determine the minimum cost of shipping material from a set of sources to a set of
destinations, given constraints on the supply at each source and the demand at each destination.

Let
m = number of sources
n = number of destinations
si = number of units of supply at source i (i = 1, 2, ...., m)
dj = number of units of demand at destination j ( j = 1, 2, ...., n)
cij = cost per unit of shipping from source i to destination j
xij = number of units to be shipped from source i to destination j
The shipments from each source to each destination are displayed in the following table:

Destination
1 2 … n Supply
1 x11 x12 … x1n s1
2 x21 X22 … X2n s2
Source . . . . . .
. . . . . .
. . . . . .
m xm1 xm2 … xmn sm
Demand d1 D2 … Dn

The decision variables xij in this table must be chosen so that the row totals are equal to the
supply quantities si and the column totals are equal to the demand quantities dj. This ensures that
the total number of units shipped from each source matches the supply at that source, and the
total number of units shipped to each destination matches the demand at that destination.
The objective is to find the values of the mn variables xij (i = 1, 2, …, m; j = 1, 2, …, n) to
minimize the total shipping cost, C.

In general, a transportation problem is specified by the following information:

62 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

o A set of m supply points from which a good is shipped. Supply point i can supply at most
si units.
o A set of n demand points to which the good is shipped. Demand point j must receive at
least dj units of the shipped good.
o Each unit produced at supply point i and shipped to demand point j incurs a variable cost
of cij.
There are three sets of constraints: The demand constraints, the supply constraints and the
non-negativity constraints. If total supply equals total demand then the problem is said to be a
balanced transportation problem.

Properties of the Transportation Problem

i) The requirements assumption:
 Each source has a fixed supply of units, where this entire supply must be distributed to the
destinations. Similarly, each destination has a fixed demand for units, where this entire
demand must be received from the sources.
 This assumption that there is no scope in the amounts to be sent or received.
ii) The feasible solutions property:
 A transportation problem will have feasible solutions if and only if: ∑SSi = ∑DDj
 The current basic variables (occupied cells) are equal to: m + n – 1. Where m is the number
of columns and n is the number of rows. Or the no. of BVs = the no. of lines (vertical and or
horizontal lines)
iii) The cost assumption:
 The cost of distributing units from any particular source to any particular destination is
directly proportional to the number of units distributed.
 This cost = unit cost of distribution x the number of units distributed
iv) Integer solutions property:
 For transportation problem where every si and dj has an integer value, all the basic variables
(allocations) in every basic feasible solution (including an optimal one) also have integer
values.

63 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Steps of Solving the Transportation Problem

There are three common steps of solving the transportation problem given below:

Step One: Initialization: Build an IBFS

 Construct an initial basic feasible solution by using any of the three techniques - North
West Corner Method (NWCM), Least Cost Method (LCM) and Vogel‟s Approximation
Method (VAM).

 The three methods differ in the quality of the IBFS they produce (a better solution yields
a smallest objective value). In general, though not always, the VAM yields the best IBFS,
the NWCM yields the worst and the LCM yields between the two.

3.1.1 Methods of Finding the Initial Solution

An initial basic feasible solution to a transportation problem can be found by any one of the three
following methods:
 Northwest corner rule (NWC)
 Least cost method (LCM)
 Vogel's approximation method (VAM)
Illustration 1: A firm owns facilities at six places. It has manufacturing plants at places A, B
and C with daily production of 50, 40 & 60 units, respectively. At point D, E and F, it has three
warehouses with daily demands of 20, 95 and 35 units, respectively. Per unit shipping costs are
given in the following table. If the firm wants to minimize its total transportation cost, how it
should route its products?
Warehouses
Plant D E F
A 6 4 1
B 3 8 7
C 4 4 2

Required:
1. Obtain an initial feasible solution using any Northwest corner method (NWCM) and least
cost method (LCM).

64 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

2. Check whether it is optimal or not using the stepping stone or the MODI method. If not
optimal revise the solution until it is optimal
A) North West Corner Rule

o STEP 1: Start with the cell in the upper left hand corner (North West Corner).

o STEP 2: Allocate the maximum feasible amount.

o STEP 3: Move one cell to the right if there is any remaining supply. Otherwise, move
one cell down. If both are impossible, stop or go to step (2).

Initial feasible solution

a) North-West corner method (NWCM)

From D E F Supply
To
A 20 30 50
6 4 1
B 40 40
3 8 7
C 25 35 60
4 4 2
Demand 20 95 35 150

TC = 6x20 + 4x30 + 8x40 + 4x25 + 2x35

TC = 730 birr

B) Least Cost Method

o STEP 1: Determine the least cost among all the rows of the transportation table.

o STEP 2: Identify the row and allocate the maximum feasible quantity in the cell
corresponding to the least cost in the row. Then eliminate that row (column) when an
allocation is made.

o STEP 3: Repeat steps 1 and 2 for the reduced transportation table until all the available
quantities are distributed to the required places. If the minimum cost is not unique, the tie
can be broken arbitrarily.

65 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Initial feasible solution

b) Least cost method (LCM)
From D E F Supply
To
A 15 35 50
6 4 1
B 20 20 40
3 8 7

C 60 60
4 4 2
Demand 20 95 35 150

TC = 4x15 + 1x35 + 3x20 + 8x20 + 4x60

TC = 555 birr

C) Vogel's Approximation Method (VAM)

This method is based on the 'difference' associated with each row and column in the matrix
giving unit cost of transportation cij. This 'difference' is defined as the arithmetic difference
between the smallest and next to the smallest element in that row or column. This difference in a
row or column indicates the minimum unit penalty incurred in failing to make an allocation to
the smallest cost cell in that row or column. This difference also provides a measure of proper
priorities for making allocations to the respective rows and column. In other words, if we take a
row, we have to allocate to the cell having the least cost and if we fail to do so, extra
cost will be incurred for a wrong choice, which is called penalty. The minimum penalty is given
by this difference. So, the procedure repeatedly makes the maximum feasible allocation in the
smallest cost cell of the remaining row or column, with the largest penalty. Once an allocation is
fully made in a row or column, the particular row or column is eliminated. Hence and allocation
already made cannot be changed. Then we have a reduced matrix. Repeat the same procedure of
finding penalty of all rows and columns in the reduced matrix, choosing the highest penalty in a
row or column and allotting as much as possible in the least cost cell in that row or column. Thus
we eliminate another fully allocated row or column, resulting in further reducing the size of the

66 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

matrix. We repeat till all supply and demand are exhausted. A summary of the steps involved in
Vogel's Approximation Method is given below:

o STEP 1: Represent the transportation problem in the standard tabular form.

o STEP 2: Select the smallest element in each row and the next to the smallest element in
that row. Find the difference. This is the penalty written on the right hand side of each
row. Repeat the same for each column. The penalty is written below each column.

o STEP 3: Select the row or column with largest penalty. If there is a tie, the same can be
broken arbitrarily.

o STEP 4: Allocate the maximum feasible amount to the smallest cost cell in that row or
column.

o STEP 5: Allocate zero elsewhere in the row or column where the supply or demand is
exhausted.

o STEP 6: Remove all fully allocated rows or columns from further consideration. Then
proceed with the remaining reduced matrix till no rows or columns remain.

Illustration 2: The Hardrock Concrete Company has plants in three locations and is
currently working on three major construction projects, each located at a different site.
The shipping cost per truckload of concrete, daily plant capacities, and daily project
requirements are provided in the accompanying table.
From Construction Projects

To Project D Project D Project F Capacity

Plant A 5 4 3 100

Plant B 8 4 3 300

Plant C 9 7 5 300

Demand 300 200 200 700

1. Obtain an initial feasible solution using Vogel‟s Approximation Method (VAM).

67 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Solution: The six steps involved in determining an initial VAM solution are illustrated as
follows:
VAM Step 1: For each row and column of the transportation table, find the difference between
the two lowest unit shipping costs. These numbers represent the difference between the
distribution cost on the best route in the row or column and the second best route in the row or
column. (This is the opportunity cost of not using the best route.) Step 1 has been done in Table
1.1. The numbers at the heads of the columns and to the right of the rows represent these
differences. For example, in row E the three transportation costs are $8, $4, and $3. The two
lowest costs are $4 and $3; their difference is $1.
VAM Step 2: Identify the row or column with the greatest opportunity cost, or difference. In the
case of Table 1.2, the row or column selected is column A, with a difference of 3.
Table 1.1: Transportation Table VAM Row and Column Differences Shown

From Construction Projects

To Project D Project D Project F Capacity Row Penalty

Plant A 100 5 4 3 100 1

Plant B 8 4 3 300 1
Plant C 9 7 5 300 2
Demand 300 200 200 700
Column Penalty 3 0 0

VAM Step 3: Assign as many units as possible to the lowest cost square in the row or column
selected. Step 3 has been done in Table 1.2. Under Column A, the lowest-cost route is D–A
(with a cost of $5), and 100 units have been assigned to that square. No more were placed
in the square because doing so would exceed D‟s availability.
Table 1.2: VAM Assignment with D‟s Requirements Satisfied
From Construction Projects
To Capacity Row Penalty
Project D Project D Project F

Plant A 100 5 X 4 X 3 100 1 X

68 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Plant B 8 200 4 3 300 11

Plant C 9 7 5 300 2 2
Demand 300 200 200 700
Column Penalty 3 0 0
1 3 2

VAM Step 4: Eliminate any row or column that has just been completely satisfied by the
assignment just made. This can be done by placing Xs in each appropriate square. Step 4 has
been done in Table 1.2 D row. No future assignments will be made to the D–B or D–C routes.
VAM Step 5: Recompute the cost differences for the transportation table, omitting rows or
columns crossed out in the preceding step. This is also shown in Table 4.2. A‟s, B‟s, and C‟s
differences each change. D‟s row is eliminated, and E‟s and F‟s differences remain the same as
in Table 1.1.
VAM Step 6: Return to step 2 and repeat the steps until an initial feasible solution has been
obtained. In our case, column B now has the greatest difference, which is 3. We assign 200 units
to the lowest-cost square in column B that has not been crossed out. This is seen to be E–B. Since
B‟s requirements have now been met, we place an X in the F–B square to eliminate it.
Differences are once again recomputed. This process is summarized in Table 1.3. The greatest
difference is now in row E. Hence, we shall assign as many units as possible to the lowest-cost
square in row E, that is, E–C with a cost of $3. The maximum assignment of 100 units depletes
the remaining availability at E. The square E–A may therefore be crossed out. This is illustrated
in Table 1.3. The final two allocations, at F–A and F–C, may be made by inspecting supply
restrictions (in the rows) and demand requirements (in the columns). We see that an assignment
of 200 units to F–A and 100 units to F–C completes the table (see Table 4.3). The cost of this
VAM assignment is = (100 units × $5) + (200 units × $4) + (100 units × $3) + (200 units × $9) +
(100 units × $5) = $3,900. Even though VAM takes many more calculations to find an initial
solution than does the northwest corner rule, it almost always produces a much better initial
solution. Hence VAM tends to minimize the total number of computations needed to reach an
optimal solution.

69 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Table 1.3: Final Assignments to Balance Column and Row Requirements

From Construction Projects
To Project D Project D Project F Capacity Row Penalty

Plant A 100 5 X 4 X 3 100 1 XXXXX

Plant B 8 200 4 100 3 300 115XXX
Plant C 200 9 7 100 5 300 2 2222X
Demand 300 200 200 700
3 0 0
1 3 2
Column Penalty 1 X 2
1 X 2
1 X X
X X X

For the transportation problem discussed in Illustration 1 determine the initial solution
using the Vogel‟s Approximation Method (VAM).
3.1.2 Test for Optimality
There are two options to test the optimality of transportation problem: the stepping stone method
and the Modified Distribution Method (MODI). Let‟s discuss them one by one.

A) The Stepping Stone Method (SSM)

It refers to crossing a stream by moving from stone to stone. The stones are the completed
(occupied) cells or the basic variables. The following are the basic steps of testing the optimality
of the initial basic feasible solutions (IBFS) IBFS using the stepping stone method (SSM):

Step I: Evaluate unoccupied cells or empty cells (non-basic variables)

If every unoccupied (empty) cell has a net cost greater or equal to zero (using kij= cij -
ui – vj. If cij - ui - vj ≥ 0 for every (i, j) such that xij is nonbasic), the current solution is
optimal (stop the iteration).

70 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

If not, select the unoccupied cells having the largest negative value (in terms of
absolute value). And then go to the step II.

Step II: Determine the occupied cell or the basic variables.

 Select the occupied cells having the smallest positive value.

 Add the values of the leaving basic variable to the allocation for each receipt cell
and subtract this value from the allocation for donor cell.

 Return to step I until all unoccupied cell values are ≥ 0.

 The following are the rules:

 Construct a closed loop that starts and ends at an empty cell. The loop is constructed
from horizontal and vertical segments (no diagonal line is allowed).

 Except for the entering variable cell (the empty cell currently you evaluated) each
corner of the closed loop must coincide with a basic variable (an occupied cell).

 Add (+) sign and subtract (-) sign beginning with a plus sign in unoccupied cell.

B) The Modified Distribution Method (MODI)

The MODI (modified distribution) method allows us to compute improvement indices quickly
for each unused square without drawing all of the closed paths. Because of this, it can often
provide considerable time savings over other methods for solving transportation problems.
MODI provides a new means of finding the unused route with the largest negative improvement
index. Once the largest index is identified, we are required to trace only one closed path. This
path helps determine the maximum number of units that can be shipped via the best unused
route. The next are the basic steps of testing the optimality of the IBFS using the MODI:

Step I: Find out the occupied cell or the basic variables.

By assigning row one (U1) =0 to get the row and column index using: cij= ui + vi for each (i, j)
such that xij is basic.

Step II: Evaluate unoccupied cells or empty cells (non-basic variables)

71 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

 Compute the cost change kij for each empty cell (current non basic cells) using kij= cij – (ui +
vj).

 If cij - ui - vj ≥ 0 for every (i, j) such that xij is nonbasic, then the current solution is optimal,
so stop.

 Otherwise, go to iterations (that is the SSM).

Step Three: Iterations

 If negative marginal cost values are obtained for one or more cells when we with either of
the two techniques, our conclusion is that the CBFS is not optimal.

 To find a new feasible solution that improves on the previous BF solution, we will
reallocate from the current basic variables to the cell that has the highest absolute value
net cost margin.

 The iteration stage of the transportation algorithm can be summarized as follows.

o Step I: Determine the entering non- basic variable: Select the non basic variable kij
having the largest (in absolute terms) negative value of kij=cij –ui-vj.

o Step II: Determine the leaving basic variable: Identify the chain reaction required to
retain feasibility when the entering basic variable is increased. From the donor cells,
select the basic variable having the smallest value.

o Step III: Allocate as much as possible to the empty cell that will result in the greatest
net decrease in cost.

o Step IV: Determine the new BF solution: Add the value of the leaving basic variable
to the allocation for each recipient cell and subtract this value from the allocation for
each donor cell.

o Repeat the above steps until all kij values are positive or zero (until an optimal
solution is obtained)

Illustration: A Company has three production facilities: S1, S2 and S3 with a production
capacity of 7000, 9000 and 18,000 units per week of a product respectively. These units are to be

72 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

shipped to four warehouses: D1, D2, D3 and D4 with a requirement of 5000, 8000, 7000 and14,
000 per week respectively. The transportation costs in Birr per unit between factories to
warehouses are given in the following table.

Table: Transportation cost per quintal data

From To SS amount

Warehouses

Factory D1 D2 D3 D4

S1 19 30 50 10 7,000

S2 70 30 40 60 9,000

S3 40 8 70 20 18,000

DD amount 5,000 8,000 7,000 14,000 34,000

Required:

1) Find an initial basic feasible solution for the problem using:

a) The northwest corner method? 19x5+30x2+30x6+40x3+70x4+20x14 = 1,015,000 Birr.

b) The least cost method? 70x2+40x3+8x8+40x7+10x7+20x7 = 814,000 Birr.

c) The Vogel‟s approximation method? 19x5+8x8+10x2+60x2+20x10+40x7 = 779,000 Birr.

2) Determine the optimal solution for the problem obtained by VAM using:

a) The stepping stone method? 19x5+10x2+30x2+8x6+40x7+20x12 = 743,000 Birr. Or (779,000) –

(18 ×2,000) = 743,000 Birr

Unoccupied cells or empty cells (non-basic variables)

i) S1D2= + (30,20) and - (10,8) =+32

ii) S1D3= +60

iii) S2D1= +1

iv) S2D2= -18

v) S3D1=+11
73 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])
 Operations Research

vi) S3D3=+70

b) The MODI method? 743,000 Birr.

Occupied cell or the basic variables: Using Cij = Ui + Vj

i) S1D1=19 S1+ D1 or U1+ V1=19 = 0 + V1 =19

ii) S1D4=10

iii) S2D3=40

iv) S2D4=60

v) S3D2=8

vi) S3D4=20

Ui Vj
U1= 0 V1= 19
U2= 50 V2= -2
U3= 10 V3= -10
V4= 10
Unoccupied cells or empty cells (non-basic variables) Using Kij = Cij – (Ui + Vj)

i) S1D2= 30. Thus, 30 -(0-2) =+32

ii) S1D3=+60

iii) S2D1=+1

iv) S2D2=-18

v) S3D1=+11

vi) S3D3=+70

74 Dereje T., Statistics Dep't (derejetesfaye11@@[Link])

 Operations Research

Finding an optimal solution

A|) Stepping stone method
 Consider the initial feasible solution obtained by using NWCM
From D E F Supply
To
A 20 30
6 4 1 50
B 40 40
3 8 7
C 4 25 35 60
4 2
Demand 20 95 35 150
Evaluate the opportunity cost of each empty cell.
Empty cell Closed loop Net cost change
AF AF-CF-CE-AE +1-2+4-4 = -1
BF BF-CF-CE-BE +7-2+4-8 =+1
BD BD-AD-AE-BE +3-6+4-8=-7
CD CD-AD-AE-CE +4-6+4-4 =-2

If we take cell BD, cost can decrease by birr 7per unit

Improved solution

From D E F Supply
To
A 50 50
6 4 1
B 20 20 40
3 8 7
C 25 35 60
4 4 2
Demand 20 95 35 150

TC = 4x50 + 3x20 + 8x20 + 4x25 + 2x35

TC = 590 birr

75
 Operations Research

2nd evaluation

Empty cell closed 100P Net cost change

AD AD – AE –BE – BD +6-4+8-3 = +7
AF AF-CF-CE-BE +1-2+4-4 = -1
BE BF-CF-CE-BE +7-2+4-8 =+1
CD CD-BD-BE-CE +4-3+8-4 = +5
Take cell AF and improve the solution
Improved solution
D E F Supply
A 15 35 50
6 4 1
B 20 20 40
3 8 7
C 4 60 4 60
2
Demand 20 95 35 150
TC = 4x15 + 1x35 + 3x20 + 8x20 + 4x60
TC = 555 birr this is final solution.
Cheek
AD = +6-4+8-3 = +7
BF = +7-8+4-1 =+2
CD = +4-3+8-4 =+5
CF=+2-4+4-1 =+1
This is optimal solution
b) The modified distribution method (MODI)

Initial solution

C1= 6 C2=4 C3=2

D E F Supply
r1=0 A 20 30 50
6 4 1
r2=4 B 40 40
3 8 7
r3=0 C 25 35 60
4 4 2
Demand 20 95 35 150

76
 Operations Research

Evaluation
Cost of unoccupied cell – row index – column index
AF = 1 – 0 – 2 = - 1
BD = 3 – 4 – 6 = - 7
BF = 7 – 4 – 2 = + 1
CD = 4 – 0 – 6 = - 2
Select cell BD since it reduces cost to a larger extent (by birr 7 per unit)
ri + ci = Cost of occupied cell
r1 =0 (always)
r1 + c1 = 6 r3 + c2 = 4
D + c1 = 6 r3 + 4 = 4
C1 = 6 r3 = 0
C2 = 4
r2 + c2 = 8 r3 + c3 = 2
r2 + 4 = 8 0 + c3 = 2
r2 = 4 c3 = 2
Improved solution

D E F Supply
A 50 50
6 4 1
B 20 20 40
3 8 7 TC = 590 birr
C 25 35 60
4 4 2
Demand 20 95 35 150
Select cell AF
Improved solution
D E F Supply
A 15 35 50
6 4 1
B 20 20 40
3 8 7 TC = 555 birr
C 60 60 Optimal
4 4 2
Demand 20 95 35 150

77
 Operations Research

Evaluation

R1 = 0 Evaluation
C2 = 4 AD = 6-0-4 = + 2
R2 = 4 AF = 1- 0 – 4 = -1
C1 = -1 BF = 7 – 4 – 2 = +1
R3 = 0 CD = 4-0-(-1) = +5

3.1.3 Variation in Transportation Problem

[Link] Unbalanced demand and supply

The transportation problems we discussed earlier were having the same aggregate demand and
supply. However situations may arise when the two are unequal. When the aggregate supply
exceeds the aggregate demand, the excess supply is assumed to go to inventory and costs nothing
for shipping. A column of dummy is added and transportation cost is zero. When the aggregate
demand exceeds the aggregate supply, demand for some of the destinations will not be satisfied
and no transportation cost is incurred. As a result, a dummy row is added with zero
transportation cost.

Example: Given the following transportation problem, determine the best transportation schedule

D1 D2 D3 Supply
Q1 1 3 4 200
Q2 2 6 8 500
Q3 2 5 7 300
Demand 200 100 400

After we add dummy row or dummy column, we will use the same procedure for finding an initial
feasible solution or for evaluating it for optimality.
Lest cost method (LCM)
D1 D2 D3 D4 (dummy) Supply
Q1 200 0 200
1 3 4
Q2 200 500
2 6 8 0 300
Q3 100 200 300
2 5 7 0
Demand 200 100 400 300 1000
TC = 200x1 + 8x200 + 0x300 + 5x100 + 7x200
= 3700 birr

78
 Operations Research

Use the same procedure for checking for optimality

[Link] Degeneracy
We have seen that a basic feasible solution of a transportation problem must have an
number of occupied cells where, m represents the number of rows and n represents the number
of columns. A solution is degenerate if the number of occupied cells is less than . If it
is degenerate, it is impossible to evaluate using both the stepping stone and MODI method.
Example: Solve the following transportation problem
NWCM
1 2 3 4 Supply
A 20 7 40 8 6 60
3 TC = 970 birr
B 10 50 40 10 100
4 2 5
C 40 40
2 5 6 1
Demand 20 50 50 80 200
Is the solution degenerate? No b/c 3+4 - 1 = 6 = 6
Revise the solution using MODI method.

r1 = 0 k3 = 6 A3 = 8 – 0 – 6 = 2
k1 = 7 k4 = 11 A4 = 6 – 0 – 11 = -5
k2 = 3 r3 = -10 B1 = 4 – (-1) – 7 = - 2
r2 = -1 C1 = 2 – (-10) – 7 = 5
C2 = 5 – (-10) – 3 = 12
C3 = 6 – (-10) – 6 = 10
Improved solution

1 2 3 4 Supply
A 20 7 +4 - 8 40 60
3 6

B + 50 - 50 100
4 2 5 10
C 40 40 40
2 5 1 1
Demand 20 50 50 80 200

79
 Operations Research

TC = 770 birr it degenerate because only 5 cells are occupied from. Assume that ∆ is a very
small positive number which close to zero that does not have any impact on demand and supply.
Add ∆ to any one of the empty cells and consider it as occupied.
MODI method

r1 = 0 r3 = -1 A3 = 8 – 0 – 6 = 2
k1 = 7 k3 = 6 B1 = 4 – (-1) – 7 = -2
k2 = 3 r3 = -5 B4 = 10 – (-1) – 6 = 5
r4 = 6 C1 = 2 – (-5) – 7 = 0
C2 = 5 – (-5) – 3 = 7
C3 = 6 – (-5) – 6 = 5
1 2 3 4 Supply
X 20 8 40 60
7 3 6
Y 20 30 50 100 TC = 730 birr
4 2 5 10 It is optimal
Z 5 40 40
2 6 1
Demand 20 50 50 80 200

[Link] Alternate Optimal Solutions

When we evaluate a solution for optimality, in order to be optimal all evaluations must give a
positive result. However, if we find a zero evaluation result, we can conclude that there is an
alternate optimal solution.
Example: A company has three plants and four warehouses. The supply and demand in units and
the corresponding transportation costs are given. Also the final solution is given below.
1 2 3 4 Supply
A 10 10
5 10 4 5
B 20 2 20 TC = 235 birr
6 8 7
C 5 10 5 5 25
4 2 5 7
Demand 25 10 15 5 55
Required: Does the problem have an alternate optimal solution? Identify.

80
 Operations Research

Let‟s evaluate it with MODI method

r1 = 0 A1 = 5 – 0 – 3 = 2
k3 = 4 A2 = 4 – 0 – 1 = 3
r3 = 1 A4 = 5 – 0 – (-1) = 6
k2 = 1 B2 = 8 – 3 – 1 = 4
r2 = 3 B3 = 7 – 3 - 4 = 0 *
k4 = -1 C4 = 7 – 1 – (-1) = 7
Since there is no negative evaluation result, we can conclude that this is an optimal
solution. But the net evaluation result of cell B3 is 0 which indicates the existence of an
optimal solution. Let‟s improve the solution by using cell B3.
Improved solution
1 2 3 4 Supply
A 5 10 10
10 4 5 TC = 235 birr
B 15 5 5 25 It gives the same total cost
6 8 7 2
C 10 10 20
4 2 5 7
Demand 25 10 15 5 25
[Link] Prohibited Transport Routes
Sometimes some transportation routes may not be available. This could be due to a variety of
reasons like unfavorable weather conditions, strike on a particular route, road construction, etc.
To handle such routes, we assign a very large cost represented by M to each of such prohibited
routes and make them out of consideration.
Example: Find a solution for the following transportation problem
A B C Supply

X 4 10 6 100

Y 8 16 6 300

Z 14 18 10 300

Demand 200 300 200 700

Because of road construction the Y-C route is now closed. Solve the problem.
81
 Operations Research

LCM
A B C Supply
X 100 100
4 10 6 TC = 6400 birr
Y 100 200 300 Make M out of consideration
8 16 M and use the same procedure
Z 100 200 300
14 18 10
Demand 200
300 200 700

3.2 The Assignment Problem

A special type of problem called the assignment problem is also an allocation problem. Here we
have n jobs to perform with n persons and the problem is how to distribute the jobs to the
different persons involved. Depending on the intrinsic capacity or merit or potential of the
individual, he will be able to accomplish the task in different times. Then the objective function
in assigning the different jobs to different persons is to find the optimal assignment that will
minimize the total time taken to finish all the jobs by the individuals. For example, we have four
different building activities say, construction of a hotel, a theatre, a hospital and a multistoried
building and there are four contractors competing for these jobs. Each contractor has to be
assigned only one job. The allocation should aim to minimize the total time taken to complete
the construction of all four activities after assigning only one job to one individual. In fact there
are (4!) permutations possible for allocating 4 jobs to 4 contractors. We have 24 possible ways
and it is tiresome to list all the possible ways and find the best one. If we have more jobs to be
allocated, it is even difficult to list out the different permutations of allocations, then what to
speak of choosing the best combinations!

Assumptions of the Assignment Problem

The number of assignees and the number of tasks are the same. (This number is denoted by n).
Each assignee is to be assigned to exactly one task and each task is to be performed by exactly
one assignee. There is a cost (cij) associated with assignee (i) performing task (j) and the
objective is to determine how all n assignments should be made to minimize the total cost. In

82
 Operations Research

fact, the assignment problem is just a special type of transportation problem where the sources
now are assignees and the destinations now are tasks and where the number of sources (m) =
number of destinations (n).

3.2.1 Solution Method for Assignment Problem

An efficient specialized algorithm to solve the assignment problem is a method known as the
Hungarian method (Hungarian- somebody who comes from Hungary/ official language of
Hungary). This method involves the following steps:

Step One: Develop an opportunity cost table (Initial solution)

a) Row reduction: For each row in the assignment cost table, subtract from all the elements
in a row the smallest value element in the row.

b) Column reduction: In the new table (row reduction table), subtract from all the elements
in a column the smallest value element in the column.

Step Two: Optimality test

 In the completed opportunity cost table, seek a solution in which the total cost (total time)
has a null value, that is, an assignment in which all of the elements of the solution are
zeros.

 To this end, cross out all zeros, using the minimum number of horizontal and/or vertical
lines.

 To do this,

First consider the row, or one of the rows, containing the fewest zeros.

Draw a box around one of the zeros in this line and then cross out the other zeros
in the same line and column as the one that is encased (box is drawn around this
zero).

From among the remaining rows seek the one with the fewest zeros and repeat the
same procedure, continuing until you can no longer encase any zeros.

83
 Operations Research

The number of encased elements is the minimum number of lines required to

cover all the zeros.

If the minimum number of lines (or the number of selected/boxed zeros) is found
to be the same as the number of rows or columns, an optimal assignment can be
made; otherwise, go to step 3.

Step Three: Iteration

a) Identify the smallest number from uncovered elements.

b) Subtract the minimum uncrossed value from all other uncrossed values.

c)Add the same value to every element at the intersection of two lines.

d) Leave the element that crosses only one line (either vertical or horizontal line).

 Repeat this step until an optimal solution is obtained

Example 1: The Bahir Dar City administration wants to employ (use/utilize) four of the town‟s
cobblestone road construction cooperatives to pave (cover) three roads with cobblestones in the
town. The administration is determined that all the four cooperatives should get work to do. The
administration has told the managers of the three cooperatives to submit secret bids for each of
the four roads. The bids submitted by the four cooperatives are shown in the table below.

Table: Bids submitted by Cooperatives („00000)

Bidders Roads

A B C D
I 8 7 8 9
II 9 6 7 10
III 10 8 7 12
IV 11 10 9 7
The town‟s administration wants to assign each cooperative (bidders) to one of the roads in a
cost minimizing way. Which cooperative should be assigned to which road?

Solution: The optimal assignment of bidders to roads and the costs associated are shown in the
table below.

84
 Operations Research

Bidder Road Cost Row Column

(‘00000) reduction reduction
I A 8 r1=7 C1 = 1
II B 6 r2= 6 C2 = 0
III C 7 r3= 7 C3 = 0
III D 7 r4= 7 C4 = 0

OR
Total cost 28 Total no. of row & column
reduction = 28
Example 2: XYZ Company is to undertake market studies for its three clients. The company has
to do the task of assigning project leaders to each of the three market studies. The Company‟s
management realizes that the time required by each of the three project leaders assigned to each
study is different due to the experience and ability of the project leader. The estimated project
completion times are summarized by the table below.

Table: Estimated project completion times

Project leader Client

1 2 3
Taye 10 15 9
Chanie 9 18 5
Kebede 6 14 3
The company would like to assign project leaders so that the total number of days required to
complete all the projects is minimized. If a project is to be assigned to one and only one client,
what assignments should be made?

Solution: Taye- 2, Chanie- 3 & Kebede- 1 and then 15 + 5 + 6 = 26 days are the optimal number
of days that are required to complete the study for the three clients.

OR: [Row reduction (r1 =9, r2= 5 & r3=3) + column reduction (c1= 1, c2= 6, c3= 0) + (2)]=
26 days

Example 3: A production supervisor is considering how he should assign the five jobs that are to
be performed to the five workers under him such that the aggregate time in days to complete all
the jobs is the least. Based on previous experience, he has the information on the time taken by
the five workers as given below.

85
 Operations Research

Job

Worker A B C D E Min no.

1 10 3 3 2 8 2
2 9 7 8 2 7 2
3 7 5 6 2 4 2
4 3 5 8 2 4 2
5 9 10 9 6 10 6
Step 1: row reduction

A B C D E
1 8 1 1 0 6
2 7 5 6 0 5
3 5 3 4 0 2
4 1 3 6 0 2
5 3 4 3 0 4
min 1 1 1 0 2
Step 2: Column reduction

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

Step 3: Minimum number of covering lines

A B C D E

1 7 0 0 0 4

2 6 4 5 0 3

3 4 2 3 0 0

4 0 2 5 0 0

5 2 3 2 0 2

86
 Operations Research

Number of covering lines < number of rows/ columns which indicate that the solution is not
optimal.

- The smallest uncovered value is 2

- Subtract 2 from all uncovered values and add it to the intersection of any two lines.
A B C D E

1 7 0 0 2 6

2 4 2 3 0 3

3 2 0 1 0 0

4 0 2 5 2 2

5 0 1 0 0 2

No of lines = no of rows /columns = 5  optimal

Assignment

A B C D E
1 7 0 0 2 6
2 4 2 3 00 3
3 2 0 1 0 0
4 2 5 2 2
5 0 0 1 0 2
0

The assignment will be

Worker Job Time

1 B 3
2 D 2
3 E 4
4 A 3
5 C 9
Minimum time = 21 days

87
 Operations Research

3.2.2 Special Cases in Assignment Problem

Unbalanced Assignment Problems

The Hungarian assignment method requires that the number of rows should be equal to the
number of columns. But sometimes unbalanced problems may exist. If the number of
rows is more than the number of columns, dummy column will be added with costs of zero and
when the number of columns is more than the number of rows, a dummy row will be added with
costs of zero.
Prohibited Assignment Problems
It happens sometimes that a worker cannot perform a certain job because of any reason. To
handle such problems, the cost of performing that job by such person is taken to be extremely
large which will be written as M.
Example: You are given the following information about the cost of performing different jobs
by different persons. Also you are given that person 1 cannot be assigned to job 3 and person 3
cannot be assigned to job 4.
Job
J1 J2 J3 J4 J5
P1 27 18 16 20 21
Person P2 31 24 21 12 17
P3 20 17 20 21 16
P4 22 28 20 16 27
Because this is the case of unbalanced and a prohibited assignment problem, we have to first
balance and handle the prohibited assignment as follows.
J1 J2 J3 J4 J5 row minimum
P1 27 18 M 20 21 18
P2 31 24 21 12 17 12
P3 20 17 20 M 16 16
P4 22 28 20 16 27 16
Dummy 0 0 0 0 0 0

Row reduction
A B C D E
P1 9 0 M 2 3
P2 19 12 9 0 5
P3 4 1 4 M 0
P4 6 12 4 0 11
dummy 0 0 0 0 0
Column Minimum 0 0 0 0 0

88
 Operations Research

Column reduction
A B C D E
P1 9 0 M 2 3
P2 19 12 9 0 5
P3 4 1 4 M 0
P4 6 12 4 0 11
dummy 0 0 0 0 0

This is not optimal because the number of covering lines is less than the number of rows and
columns.
Smallest uncovered number = 4
J1 J2 J3 J4 J5

P1 9 0 M 6 3

P2 15 8 5 0 1

P3 4 1 4 M 0

P4 2 8 0 0 7

dummy 0 0 0 4 0

No. of lines = 5  optimal

Assignment

A B C D E

1 9 M 6 3
0
2 15 8 5 00 1

3 4 1 4 M 0
4 2 8 0 0 7

5 0 0 0 4 0

P1 J2 = 18
89
 Operations Research

P2 J4 = 12

P3 J5 = 16

P4 J3 = 20

Min cost = 66

J1 will remain unassigned

Multiple optimal solutions

Sometimes we may find a tie in assigning as there may be no row or column which has only one
zero. If this happens, we can conclude that there are multiple/alternate optimal solutions and we
can take any of the zeros and assign.

Example: Solve the following assignment problem and obtain the minimum cost at which all
the jobs can be performed.

1 2 3 4 5

A 25 18 32 20 21

B 34 24 21 12 17

C 20 17 20 32 16

D 20 28 20 16 27

The optimal solution is

1 2 3 4 5

A 7 14 6 3
0
B 18 9 5 00 1

C 4 1 4 20 0
D 0 8 0 0 7

dummy 0 0 4 0
0
Alternative 1 Alternative 2
A2 = 18
B904 = 12
C5 = 16
D1 = 20
E3 =0
Total = 66
 Operations Research

A  2 = 18
Maximization problems B  4 = 12
C  5 = 16
D  3 = 20
As you have seen earlier, the objective of an assignment problem is minimization in most of the
E  1 = 0 instead of minimization if unit profits
cases. But sometimes the objective may be maximization
Total = 66
are given.
Example: A company plans to assign 5 salesmen to 5 districts in w/c it operates. Estimates of
sales revenue in birr for each salesman in d/t districts are given as follows. Determine the
optimum assignment which maximizes the total sales revenue.
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

As we have done in the case of transportation problems, we will identify the largest unit
profit (49 in this case) and subtract all unit profits from the largest one so that it will be
changed to opportunity cost table.
Opportunity loss matrix
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 47
After this we will follows the same procedure for assignment.

Solution: Maximum sale = 231

91
 Operations Research

Self-Assessment Questions (SAQ3)

1. A manufacturer has distribution centres at X, Y and Z. These centres have availability of 40, 20
and 40 units of the product, His retail outlets at A, B, C, D and E require 25, 10, 20, 30 and 15
units respectively. The transport cost per unit between each centre and each outlet is given
below.

To To E
From A B C D E
X 55 30 40 50 50
Y 35 30 100 45 60
Z 40 60 95 35 30

a. Develop an initial feasible solution using the northwest corner method; compute the total
cost for these solutions.
b. Evaluate the solution using the stepping stone method. Is the solution optimal? Explain
c. Repeat the evaluation using MODI and compare your cell evaluations to those obtained
using the stepping stone method.
d. Obtain an improved solution and evaluate it using MODI. Is it optimal?
e. What is the total cost for your optimal solution?
2. The Microsoft enterprise manufactures the central processing unit (CPU) for a line of personal
computers. The CPUs are manufactured in Philadelphia, Columbus, and New York, and shipped to
warehouses in Kansas, Milano, Denver, Seattle and Washington DC for further distribution. The
transportation table below shows the number of CPUs available at each plant and the number of
CPUs required by each warehouse. The shipment costs are also shown below.

Warehouse

Kansas Milano Denver Seattle Washington SS

Philadelphia 10 20 5 9 10 9000
Columbus 2 10 8 30 6 4000
New York 1 20 7 10 4 8000
DD 3000 5000 4000 6000 3000 21000
a. Determine the amount that should be shipped from each plant to each warehouse in order to
minimize the total shipping cost.
92
 Operations Research

b. The pits burgh ware house has just increased its order by 1000 units and Microsoft has
authorized the Columbus plant to increase productivity by 1000 units, Do you expect this
development to lead to an increase or a decrease in total shipping costs? Solve for the new
optimal solution.

3. A firm produces four products. There are four operators who are capable of producing any of
these four products. The firm records 8 hours a day and allows 30 minutes for lunch. The
processing time in minutes and the profit for each of the products are given below.

Products
A B C D
1 15 9 10 6
Operators
2 10 6 9 6
3 25 15 15 9
4 15 9 10 10
Profit/unit 8 6 5 4
Find the optimal assignment of products to operators

93
 Operations Research

©©©©©©©©©
CHAPTER FOUR

DECISION THEORY

Introduction

Decision theory deals with methods for determining the optimal course of action when a number
of alternatives are available and their consequences cannot be forecast with certainty. It is
difficult to imagine a situation which does not involve such decision problems, but we shall
restrict ourselves primarily to problems occurring in business, with consequences that can be
described in dollars of profit or revenue, cost or loss. For these problems, it may be reasonable to
consider as the best alternative that which results in the highest profit or revenue, or lowest cost
or loss, on the average, in the long run. This criterion of optimality is not without shortcomings,
but it should serve as a useful guide to action in repetitive situations where the consequences are
not critical.

Learning Outcomes

After studying this chapter, you will be able to:

o Define the terms state of nature, event, decision alternative, and payoff.

o Organize information in a payoff table or a decision tree.

o Find the expected payoff of a decision alternative.

o Compute opportunity loss and expected opportunity loss.

o Assess the expected value of information

4.1 Decision Theory

Decision theory represents a generalized approach to decision making which often serves as the
basis for a wide range of managerial decision making for selecting the best alternative among
possible options.

94
 Operations Research

4.2 Features of Decision Theory

Decision theory problems are characterized by the following

1. Lists of alternatives: are a set of mutually exclusive and collectively exhaustive decisions
that are available to the decision maker.
2. States of nature – a set of possible future conditions, or events beyond the control of a
decision maker, that will be the primary determinants of the decision
3. Payoffs – are profits, revenues, costs, or other measure of value that are associated with each
alternative and the various states of nature.
4. Degree of certainty – the approach used by a decision maker often depends on the degree of
certainty that exists.
5. Decision criterion – the process of selecting one alternative from a list of alternatives is
governed by a decision criterion, which embodies the decision maker‟s attitudes toward the
decision as well as the degree of certainty. For instance, some decision makers are more
optimistic, whereas others are pessimistic. Some want to maximize gains, where as others
want to protect large losses.

Example

S1 S2 S3
S = State of nature
A = alternatives
a1 V11 V12 V13
V = values /payoffs
a2 V21 V22 V23

a3 V31 V32 V33

4.3 Types of Decision-making Environment

4.2.1 Decision-making under Certainty
In this case, 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. Then select the best payoff in that state of
nature.

Example: If you are given the following payoff table for three products and three states of
nature.
95
 Operations Research

Product type States of nature

D1 D2 D3
A 14 66 118
Alternatives B 13 77 141
C 1 73 145
If we are certain that
D1 will occur – select A (14)
D2 will occur – select B (77)
D3 will occur – select C (145)
4.2.2 Decision-making under Risk

In this situation the decision maker is supposed to have evidential information, knowledge, and
experience of judgment to enable him to assign probability values to the states of nature.

1. Expected monetary values (EMV): Is the sum of possible payoffs of the alternatives, each
weighted by the probability of that payoff occurring.
2. Expected opportunity loss (EOL) : Is an alternative approach to maximize expected
monetary value (EMV)
3. Expected value of perfect information (EVPI)

Example: Management is faced with the problem of choosing one of three products for
manufacturing. The potential demand for each product may turn out to be good, moderate on
poor. The probabilities for each of the states of nature are estimated as follows.

Product Demand
Good Moderate Poor
X 0.7 0.2 0.1
Y 0.5 0.3 0.2
Z 0.4 0.5 0.1
The estimated profit or loss under the three states may be taken as

Product Demand
Good Moderate Poor
X 3 2 1
Y 6 3 2
Z 7 1 -1.5

96
 Operations Research

EMV Approach

Find the expected monetary value for each alternative and select the best product.

Emv(x) = 3x0.7 + 2x0.2 + 1x0.1 = $2.6

Emv(y) = 6x0.5 + 3x0.3 + 2x0.2 = $4.3

Emv(z) = 4x0.4 + 1x0.5 – 1.5x0.1 = $1.85

 Select product y.

EOL Approach

Find the expected opportunity loss for each alternative. Let‟s change the given payoff matrix into
opportunity cost by subtracting all values from the largest value in that column.

Demand
Product Good Moderate Poor
X 3 1 1
Y 0 0 0
Z 2 2 3.5
EOL(x) = 3 x 0.7+1 x 0.2 + 1 x 0.1 = 2.4
EOL(y) = 0 x 0.7+0 x 0.2 + 1 x 0.1 = 0.1
EOL (z) = 2 x 0.7+2 x 0.2 + 3.5 x 0.1 = 2.15
 Select Y
Expected Value of Perfect Information (EVPI)

The value of perfect information is the difference between a payoff under perfect information
and expected payoff without perfect information.

Example: Find the expected value of perfect information for the following problem

S1 S2 S3
D1 4 16 12
D2 5 6 10
D3 -1 4 15
P(s) 0.2 0.5 0.3
EVPI = EPC-EMV

97
 Operations Research

EPC = expected pay off under certainty

EXP EPC = 5 x 0.2+16 x 0.5 + 1 x 15 = 0.3 = 13.5
EMV (01) = 4 x 0.2+16 x 0.5 + 12 x 0.3 = 12.4
EMV (02) = 5 x 0.2+6 x 0.5 + 10 x 0.3 = 7
EMV (03) = -1 x 0.2+ 4 x 0.5 + 15 x 0.3 = 6.3
D1 – Selected
EVPI = EPC - EMV
= 13.5 – 12.4 = 1.1
4.2.3 Decision-making under Uncertainty

There are four approaches to decision making under complete uncertainty: maximin, maximax,
minmax regret & principle of insufficient reason (average approach).

1. Maximin: Is a conservative strategy; it involves identifying the worst (minimum) payoff for
each alternative and then selecting the best (maximum) of worst payoffs.

D1 D2 D3
A 14 66 118
B 13 77 141
C 1 73 145
2. Maximax approach: Select the best payoff for each alternative and select the alternative
with the maximum of maximums.

3. Minimax regret: First develop an opportunity loss table that shows the difference b/n each
payoff and the best possible payoff in a given state of nature.
4. Principle of insufficient reason (Laplace): 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.

Example: ABC Company is faced with four decision alternatives relating to investments in a
capital expansion program. Since these investments are made in future, the company forecasts
different conditions or states of nature as follows.

98
 Operations Research

States of nature (demand)

Strong moderate week

D1 D2 D3
Investment A1 17 15 8
Alternatives A2 18 16 9
A3 21 14 9
A4 19 12 10
If the company has no information regarding the probability of the occurrence of the three states
of nature, give the recommended decisions in
1. Maximax 2. Maximin 3. Min max regret 4. Insufficient reason.
Maximax
Alternative Maximum
A1 17
A2 18
A3 21 Since the maximax is 21, select A2
A4 19
Maximin
Alternative Minimum
A1 8
A2 9
A3 9 Since the maximin is 10, select A4
A4 10
Minimax regret
First let us change the given payoff table into opportunity cost table by subtracting all unit profits
from the largest one in each state of nature. For the first column, subtract all elements from 21,
for the second column, from 16 and for the third column, from 10.

D1 D2 D3 Maximum
Investment A1 4 1 2 4
Alternatives A2 3 0 1 3
A3 0 2 1 2
A4 2 4 0 4
Select A3 since it 2 is the minimax value.

99
 Operations Research

4.3 Decision-making with Utilities

Utility theory is based on this assumption of rationality and describes all decision outcomes
(financial and otherwise) in terms of the utility (or value) placed on them by individuals. Within
this framework, decisions can be understood in terms of rationally ordered levels of utility
attached to different outcomes.

Self-Assessment Questions (SAQs 4)

1. A certain piece of equipment has to be purchased for a construction project at a remote location.
This equipment contains an expensive part which is subject to random failure. Spares of this part
can be purchased at the same time the equipment is purchased. Their unit cost is $1500 and they
have no scrap value. If the part fails on the job and no spare is available, the part will have to be
manufactured on a special order basis. If this is required, the total cost including down time of
the equipment, is estimated at $9,000 for each unit. Based on previous experience with similar
parts, the following probability estimates of the number of failures expected over the duration of
the project are given below.

Failure: 0 1 2

Probability: 0.8 0.15 0.05

Required

a) Determine the EMV and optimal number of spares to purchase

b) Based on opportunity losses, determine the optimal course of action and optimal value of
EOL
c) Determine expected value of perfect information EVPI

Hint Solution States of nature

0 1 2
(0.8) (0.15) (0.05)
Alternatives 0 0 9000 18,000
1 1500 1500 10,500
2 3000 3,000 3,000
2. A company needs to increase its production beyond its existing capacity. It has narrowed the
alternatives to two approaches to increase the production capacity: expansion at a cost of $ 8

100
 Operations Research

million or modernization at a cost of $ 5 million. Both approaches would require the same
amount of time for implementation. Management believes that over the required payback period,
demand will either be high or moderate. Since moderate demand is considered to be some what
less risky than moderate demand, the probability of high demand has been set at high 0.35. If the
demand is high, expansion would yield and additional revenue of $ 12 million but modernization
only additional $6 million, due to lower maximum production capacity. On the other hand, if the
demand is moderate, the comparable figures would be $7 million for expansion and $5 million
for modernization.

Required

a) Calculate the conditional profit in relation to various action and outcome combinations.
b) If the company wishes to maximize its EMV, should it modernize or expand?
c) Calculate the EVPI
d) Construct the conditional opportunity loss table and also calculate EOL

CHAPTER FIVE

NETWORK MODELS

Introduction

Networks arise in numerous settings and in a variety of guises. Transportation, electrical, and
communication networks pervade our daily lives. Network representations also are widely used
for problems in such diverse areas as production, distribution, project planning, facilities
location, resource management, and financial planning to name just a few examples. In fact, a
network representation provides such a powerful visual and conceptual aid for portraying the
relationships between the components of systems that it is used in virtually every field of
scientific, social, and economic endeavor. One of the most exciting developments in operations
research (OR) in recent years has been the unusually rapid advance in both the methodology and
application of network optimization models. A number of algorithmic breakthroughs have had a
major impact, as have ideas from computer science concerning data structures and efficient data
manipulation. Consequently, algorithms and software now are available and are being used to

101
 Operations Research

solve huge problems on a routine basis that would have been completely intractable two or three
decades ago. Many network optimization models actually are special types of linear
programming problems.

Learning Outcomes
After studying this chapter, you will be able to
 Know how to represent different things in a network
 Find shortest route and distance through a network
 Find the minimal spanning tree on a network
 Determine the maximal flow capacity of a network

5.1 General Network Concepts

Networks are important tools of management science. Not only can networks are used to model a
wide variety of problems, they can also be solved more easily than other models of the same
problem, and they present models in a visual format.

5.2 Networking Algorithms

The minimum spanning tree problem can be solved in a very straightforward way because it
happens to be one of the few OR problems were being greedy at each stage of the solution
procedure still leads to an overall optimal solution at the end! Thus, beginning with any node, the
first stage involves choosing the shortest possible link to another node, without worrying about
the effect of this choice on subsequent decisions. The second stage involves identifying the
unconnected node that is closest to either of these connected nodes and then adding the
corresponding link to the network. This process is repeated, per the following summary, until all
the nodes have been connected.

Algorithm for the Minimum Spanning Tree Problem

1. Select any node arbitrarily, and then connect it (i.e., add a link) to the nearest distinct node.

102
 Operations Research

2. Identify the unconnected node that is closest to a connected node, and then connect these two
nodes (i.e., add a link between them). Repeat this step until all nodes have been connected.

3. Tie breaking: Ties for the nearest distinct node (step 1) or the closest unconnected node (step
2) may be broken arbitrarily, and the algorithm must still yield an optimal solution. However,
such ties are a signal that there may be (but need not be) multiple optimal solutions. All such
optimal solutions can be identified by pursuing all ways of breaking ties to their conclusion.

5.3 Basic Differences Between PERT and CPM

Project management can be understood as a systematic way of planning, scheduling, executing,

monitoring, controlling the different aspects of the project, so as to attain the goal made at the
time of project formulation. PERT and CPM are the two network based project management
techniques, which exhibit the flow and sequence of the activities and events. Program (Project)
Management and Review Technique (PERT) is appropriate for the projects where time needed
to complete different activities are not known. On the other hand, Critical Path Method or CPM
is apt for the projects which are recurring in nature. The two scheduling methods, uses common
approach for designing the network and for ascertain its critical path. They are used in the
successful completion of a project and hence used in conjunction with each other. Nevertheless,
the truth is that CPM is different from PERT in a way that the former concentrates on time while
the latter stresses on time-cost trade-off.

5.4 PERT/CPM Network Components and Precedence Relationship

PERT the acronyms of Program Evaluation and Review Technique are an activity-on-the-arrow
notation developed in the 50s to plan the Polaris weapon system in the USA. PERT allows
assigning optimistic, pessimistic and most likely estimates for the span times of each activity.
You can then compute the probability to determine the likelihood that overall project duration
will fall within specified limits.
Definition of Basic Terms
 Critical path: A sequence of activities that take the longest time to complete. It is the
length of the critical path(s) defines how long your project will take to complete.

103
 Operations Research

 Noncritical path: A sequence of activities that you can delay and still finish the project in
the shortest time possible.
 Slack time: the maximum amount of time that you can delay an activity and still finish
your project in the shortest time possible.
5.5 Critical Path Analysis

Critical path analysis ("CPA") is a widely-used project management tool that uses network
analysis to help project managers to handle complex and time-sensitive operations. Many larger
businesses get involved in projects that are complex and involve significant investment and risk.
As the complexity and risk increases it becomes even more necessary to identify the
relationships between the activities involved and to work out the most efficient way of
completing the project. The essential technique for using CPA is to construct a model of the
project that includes a list of all activities required to complete the project, the time (duration)
that each activity will take to completion, and the dependencies between the activities. Using this
information, CPA calculates the longest path of planned activities to the end of the project and
the earliest and latest that each activity can start and finish without making the project longer

This process determines which activities are "critical" (i.e., on the longest path) and which have
"total float" (i.e. can be delayed without making the project longer). In project management, a
critical path is the sequence of project activities which add up to the longest overall duration.
The critical path determines the shortest time possible to complete the project. Any delay of an
activity on the critical path directly impacts the planned project completion date (i.e. there is no
float on the critical path).

104
 Operations Research

Illustration: Consider the following series of activities in a business planning to launch a new
product:

Laid out in the correct sequence of activities, the network diagram would look like this before we
calculate the EST and LFT for each activity:

The next step is to calculate the EST for each activity.

For example: The EST for task B is 2 months – the time taken to conduct market research (task
A). To calculate the EST for task C, we add the 2 months for task A to the 4 months for
designing the product concept (task B) = 6 months

The remaining ESTs can then be added to the network diagram:

105
 Operations Research

The LFTs show the latest time an activity must be completed by to avoid a delay to the project.
LFTs are calculated by looking right to left on the network diagram. So:

Evaluating CPA

The main advantages and disadvantages of a business using CPA can be summarised as follows:

Advantages of CPA

 Most importantly – helps reduce the risk and costs of complex projects
 Encourages careful assessment of the requirements of each activity in a project
 Help spot which activities have some slack ("float") and could therefore transfer some
resources = better allocation of resources
 A decision-making tool and a planning tool – all in one!
 Provides managers with a useful overview of a complex project
 Links well with other aspects of business planning, including cash flow forecasting and
budgeting

Disadvantages of CPA

 Reliability of CPA largely based on accurate estimates and assumptions made

 CPA does not guarantee the success of a project – that still needs to be managed properly

106
 Operations Research

 Resources may not actually be as flexible as management hope when they come to
address the network float
 Too many activities may the network diagram too complicated. Activities might
themselves have to be broken down into mini-projects

CPM Calculations

There are two approaches to managing projects: CPM and PERT. Basically similar, they reflect
the original projects for which they were developed. CPM was developed by DuPont, to
standardize the time needed to set up new production facilities. All the facilities were essentially
the same and they knew exactly what they were doing, so the only goal for CPM was to get the
project done on time by spending whatever money was needed to correct problems as they
occurred. PERT was developed by the Navy, for the Polaris nuclear submarine project. No one
had ever built a nuclear sub, so the goal for PERT was to provide probability estimates for each
activity and for the completion time of the project as a whole. Being a government project,
money was not an issue. These differences are reflected in the math you will see.

First, let‟s look at CPM. Since DuPont knew exactly what to do (having done it before) they
knew how long each part of the project should take and how much each part should cost.
DuPont called these two numbers the “Normal Time” and the “Normal Cost.” For our example,
the activity times we used before will be the normal times and the normal costs are shown below:

Activity Predecessors Normal Time Normal Cost

A - 5 2000
B - 6 4000
C A 4 3000
D A 7 6000
E B,C 5 3500
F D 8 5000
G D,E 3 1500
DuPont also knew that, for building a plant, most activities could be done faster (up to a point), if
they were willing to spend more money. The fastest each activity can be completed and the cost
to reach that speed are called the “Crash Time” and “Crash Cost.” An important note: crash time

107
 Operations Research

and crash cost is extreme values - you do not have to go as fast as possible or spend all the
money. So, the full data you need for a CPM problem is:

Normal Normal Crash Crash

Activity Predecessors Time Cost Time Cost

A -- 5 2000 4 2750

B -- 6 4000 3 5500

C A 4 3000 3 4200

D A 7 6000 2 9000

E B, C 5 3500 3 4900

F D 8 5000 6 9000

G D, E 3 1500 1 2300

The network for this problem, with the normal times shown under the arrows in the center, is on
the next page. It shows the project will be done in 20 weeks, and the path A-D-F is the
CRITICAL PATH, which I am sure you remember is the set of activities with no slack (slack =
LS - ES). Slack, of course, is the time you can waste between when you could start an activity
and when you must start it if you want to be done in 20 weeks. Unfortunately, when you go to
your boss with the happy news, that the project will be done in 20 weeks, your boss tells you that
the project has to be done in 15 weeks. You say that speeding up the project will cost more
money. Your boss wants to know how much the project is costing now. You quickly add up the
normal costs and tell her $25,000. She wants to know what the cost will be to get the project
done in 15 weeks. That is what we have to calculate.

108
 Operations Research

2 5 D 12 4
5 12
5 7 12
A 5 12
8 5 1712 F
5 8 20
0 20
1 0 4 C 6
0 17
6 20
B G
12 9 1712
6 6 14 3
12 3 9 E 14 5 17
12 5 17

The first step is to remember that the critical path is the longest path through the network. Try it
and see. The other paths you can trace through the network, and the total of their activity times,
is shown next:

Path Time

A-D-F 20

A-C-E-G 17

A-D-Dummy-G 15

B-E-G 14

Now, if we want to spend money to speed the project, we want to spend the money where it will
do the most good, and we want to spend as little money as possible. Consider activity G. If we
were to spend money to speed up activity G by one week, then the last three paths would all be
done one week faster. Unfortunately, the longest path through the network, A-D-F, wasn‟t
affected, and still takes 20 weeks to complete. This means we wasted the money, because the
project will still take 20 weeks to complete. So, if we want to avoid wasting our money, we
should only look at the critical path as a place to spend money. The process of spending money
to speed up an activity is called “crashing” the network. So, we find the critical path and crash
one or more activities on it until we get to our 15 week completion time. You still want to spend
as little money as possible, and you have to be careful because the critical path can shift as you
crash the network. To watch out for this, you do not automatically jump some activity from its

109
 Operations Research

normal activity time to its crash activity time. Instead, you perform a little calculation which will
tell you two things: which of the critical activities is the least expensive for crashing, and what
the cost will be to crash each activity 1 week. This calculation is called the “Crash Cost Per
Period” and is calculated by finding the increase in cost (Crash Cost - Normal Cost) and dividing
by the decrease in time (Normal Time - Crash Time), as is shown next:

Normal Normal Crash Crash Crash Cost

Activity Predecessors Time Cost Time Cost Calculation Per Period

A -- 5 2000 4 2750 (2750-2000)/(5-4) = 750/1 =750*

B -- 6 4000 3 5500 (5500-4000)/(6-3) = 1500/3 =500

C A 4 3000 3 4200 (4200-3000)/(4-3) = 1200/1 =1200

D A 7 6000 2 9000 (9000-6000)/(7-2) = 3000/5 = 600*

E B, C 5 3500 3 4900 (4900-3500)/(5-3) = 1400/2 = 700

F D 8 5000 6 9000 (9000-5000)/(8-6) = 4000/2 = 2000*

G D, E 3 1500 1 2300 (2300-1500)/(3-1) = 800/2 = 400

The asterisk (*) next to the critical activities make them easier to find. Now, crashing one
critical activity is just as good as crashing another critical activity, so we should look at the
critical path, A-D-F, and find the activity that will cost us the least on a per-week basis. This is
activity D, with a CC/P of $600. Notice that activities B and G cost less per period, but those
activities are no good to us because they are not critical activities. Since activity D is the critical
path activity that costs the least, we will reduce its activity time by one week, from 7 to 6,
spending $600 to do so, and look at how the network changes for this simple change in the data:

2 5 D 11 4
5 11
5 6 11
A 5 11
7 5 1611 F
5 8 19
0 19
1 0 4 C 6
0 17
5 19
B G
11 9 1611
6 6 14 3
11 3 9 E 14 5 16
11 5 16

110
 Operations Research

The first change is that D is now done in 11 weeks instead of 12 (compare the earlier network to
this new one) which means F can start earlier and therefore finish earlier, in 19 weeks. This
changes the LF and LS calculations for most of the network (see why we do this on computer?),
resulting in the numbers shown above. The important points are that the project can be done 1
week earlier AND the non-critical activities now have one week‟s less slack. This last point is
very important. If you keep on losing slack every time you crash an activity, eventually every
activity will have zero slack, and will be critical. That can be a problem. For now, though, the
critical path is still A-D-F and you can continue crashing the network. You would like to crash D
again, because it is still the cheapest way to speed up the critical path. First, though, you have to
check to see if you CAN crash D again. The fastest you can get D done is 2 weeks, shown as the
crash time in your data. You reduced D from 7 weeks to 6 weeks, so you can continue to go
further. If you ever get D down to 2 weeks, you will have to look at some other activity for
further crashing. Right now, though, we will spend another $600 to crash D again, from 6 weeks
to 5 weeks. Now the network, with the appropriate changes, looks like:

2 5 D 10 4
5 10
5 5 10
A 5 10
6 5 1610 F
5 8 18
0 18
1 0 4 C 6
0 17
4 18
B G
10 9 1610
6 6 14 3
10 3 9 E 14 5 15
10 5 15

Once again, D is done faster, so F can start sooner and the whole project is completed 1 week
earlier (the completion time is now 18 weeks). This changes most of the calculations again, and
again reduces the slack for the non-critical activities. The critical path, though, is still the same,
and since D can be reduced all the way down to an activity time of 2, we can repeat this whole
procedure and crash D at least one more time, from 5 to 4, spending $600 again to get:

111
 Operations Research

2 5 D 9 4
5 9
5 4 9
A 5 9
5 5 14 9 F
5 8 17
0 17
1 0 4 C 6
0 17
3 17
B G
9 9 14 9
6 6 14 3
9 3 9 E 14 5 14
9 5 14

Now we have something interesting. Our completion time is down to 17 weeks, almost to our
goal of 15 weeks, but crashing will now get more difficult. Having crashed D three times,
reducing D‟s activity time from 7 weeks to 4 weeks and spending $1,800, activities C, E, and G
now have no more slack (their ES and LS are the same). What this means is that there are two
critical paths through the network. Since a critical path runs all the way from the first node to the
last, one critical path is still A-D-F, and the new critical path is A-C-E-G. One activity, such as
A, can be on more than one critical path. This is a problem because now we have to speed up
both critical paths if we want to speed up the whole project, and speeding up two critical paths
will cost us more money. On the original critical path, D is still the least expensive activity to
crash, and we can crash D two more weeks. On the new critical path (A-C-E-G), activity G is
the cheapest activity to crash, at a cost of $400 per week. Crashing both of them, though, will
cost us $1000 per week, which is pretty expensive. However, there is a better way. Activity A
lies on both paths. If we crash activity A, we will speed up both paths at the same time, and A
only costs us $750 per week. To see this, reduce A from 5 weeks to 4 weeks on the network and
re-calculate all the ES, EF, LF, and LS. You get:

2 4 D 8 4
4 8
4 4 8
A 4 8
4 4 13 8 F
4 8 16
0 16
1 0 4 C 6
0 16
2 16
B G
8 8 13 8
6 6 13 3
8 3 8 E 13 5 13
8 5 13

112
 Operations Research

You have now spent a total of $2550 ($1800 on D and $750 on A) to reduce the completion time
to 16 weeks, and you are almost at your goal. You still have two critical paths, for that matter
there is only one activity that is not critical, activity B (unless you count the Dummy, which is
OK), and B is down to 2 weeks of slack. You only need to speed up the project by one more
week. You would like to use activity A again, but you can‟t. The fastest A can be done is 4
weeks, and you are already at that limit. You should check for any other common activities
between the critical paths, but there are none (A-D-F and A-C-E-G only have one activity in
common), so you have to go back to looking at individual activities on the separate paths, which
means more expense. Activity D is still the least expensive activity to crash on critical path A-
D-F, and can be crashed another week, so that is half of the solution. For the other critical path,
A-C-E-G, activity G, at $400, is the least expensive, so you will have to crash both of them at the
same time to reduce the project to a 15 week completion time. This gives you:

2 4 D 7 4
4 7
4 3 7
A 4 7
4 4 13 7 F
4 8 15
0 15
1 0 4 C 6
0 15
2 15
B G
8 8 13 7
6 6 13 2
8 3 8 E 13 5 13
8 5 13

If you like, go through the network only crashing D or only crashing G, and you will see that the
project completion time does not decrease; all you do is create slack on the critical path you
crashed. Having crashed both, the project is done in 15 weeks and you can go back to your boss
and tell her that the additional cost will be $3,550. for a total project cost of $28,550 (the sum of
the normal costs was $25,000 and the total crash costs were $3,550). It useful to present this
same information in another way. Set up a table showing your boss what you did at each step
and what you gained. Such a table might look like:

113
 Operations Research

Critical Path Activity Crashed Completion Time Additional Cost Total Cost
A-D-F 20 weeks $25,000
A-D-F D 19 weeks $600 $25,600
A-D-F D 18 weeks $600 $26,200
A-D-F D 17 weeks $600 $26,800
A-D-F & A-C-E-G A 16 weeks $750 $27,550
A-D-F & A-C-E-G D and G 15 weeks $1,000 $28,550
A-D-F & A-C-E-G D and G 14 weeks $1,000 $29,550
A-D-F & A-C-E-G E and F 13 weeks $2700 $32,250
A-D-F & A-C-E-G E and F 12 weeks $2700 $34,950

The advantage of a table like this one is that your boss can see for herself the tradeoff between
dollars and time. If you go to your boss and simply say that it will cost $28,550 to get done in 15
weeks, all your boss can do is take your recommendation or reject it. If you present this table,
your boss might decide that the final $1,000 is simply too much, and a 16 week deadline is
acceptable. Possible, the project budget is limited to $27,000, so with this table your boss knows
the project can be done in 17 weeks and can stay within budget. Since we have chosen the least
expensive crash at each step, your boss can make her decisions with confidence.

5.5.1 Forward Pass Method

Before applying the critical path method, we need to know the activities we plan to carry out for
this project and what there dependencies are. In other words, we should already have a network
diagram that looks like this example:

114
 Operations Research

This is a small project with four activities in it. We have estimated that activities A and B will
both take two days, activity C with take three and the final activity, D, will take five. The
structure of the diagram shows that activity A has to finish before either activity B or activity C
can begin and both activities B and C need to complete before we can get onto activity D.

Now, in order to identify the critical path – i.e. the longest path through the network, or the one
with zero float – we need to complete a forward ad a backward pass. In the following diagram,
the forward pass has been completed using the official approach.

This technique implies that the first day of the project is day 1. So, if day 1 is Monday, we will
spend Monday and Tuesday carrying out activity A. We expect to finish by close of business
Tuesday (day 2). So the Early Start for activity A is Monday (day 1) and the Early Finish is
Tuesday (day 2). Now we can get on with activities B and C. They will both start on Wednesday
(day 3). Activity B will occupy us during Wednesday and Thursday, finishing on Thursday (day
4). Similarly, we plan to work on activity C on Wednesday, Thursday and Friday (day 5). The
6th working day of the project is likely to be Monday, so that is when we will start activity D.
Because activity D depends on both activities B and C, we must wait until they are both
complete. Five days‟ work is involved in activity D, which will take us up to Friday (day 10).

While the Early Starts and Finishes clearly indicate the days we are starting and finishing,
calculating these values requires a bit of thinking. The recommended approach is to add the
estimated duration to the activity‟s Early Start Date to get the Early Start for the successor
activity (or activities). Then we have to subtract 1 from this figure to arrive at the activity‟s Early
Finish. In the heat of the PMP© exam, the adding and subtracting operations can become
confused and it is easy to make a mistake.

115
 Operations Research

Our technique is to start at day 0! Then the forward pass involves adding the estimated duration
to the Early Start to yield both the Early Finish and the Early Start of the subsequent activity.

You will see that the Early Finish dates are the same as for the official version, but the Early
Starts are all one less. This makes sense, because our project starts on day 0 instead of on day 1.
Of course, converting a 0-based forward pass to a 1-based one simply involves adding 1 day to
every Early Start value.

5.5.2 Backward Pass Method

Make a backwards pass through the network as follows: Move sequentially backwards from the
Finish node to the Start node. At a given node, j, consider all activities ending at node j. For
each of these activities, i, compute:
• Latest Finish Time = the minimum of the latest start times beginning at node j. (For node
N, this is the project completion time.)
• Latest Start Time = (Latest Finish Time) - (Time to complete activity i ).
5.6 Project Scheduling with Uncertain Activity Times

An activity‟s mean completion time is:

t = (a + 4m + b)/6
An activity‟s completion time variance is:
s2 = ((b-a)/6)2
a = the optimistic completion time estimate
b = the pessimistic completion time estimate
m = the most likely completion time estimate

116
 Operations Research

In the three-time estimate approach, the critical path is determined as if the mean times for the
activities were fixed times. The overall project completion time is assumed to have a normal
distribution with mean equal to the sum of the means along the critical path and variance equal to
the sum of the variances along the critical path.

5.7 Project Cost and Crashing

Reduced project completion time is “crashing.” Crashing a project needs to balance shorten a
project duration and cost to shorten the project duration. Crashing a project requires you to know
crash time of each activity and crash cost of each activity.

 Procedure for crashing

 Crash the project one period at a time

 Only an activity on the critical path

 Crash the least expensive activity

 Multiple critical paths: find the sum of crashing the least expensive activity on
each critical path

Self-assessment Questions (SAQs) 5

1. The following represent activities in a major construction project. Draw the network to
represent this project.

Activity Immediate Predecessor

A -
B -
C A
D B
E B
F C, E
G D
H F, G

117
 Operations Research

Solution

2. Given the following Time Chart and Network Diagram, find the Critical Path.

Activity a m b t Variance
A 2 3 4 3 1/9
B 1 2 3 2 1/9
C 4 5 12 6 16/9
D 1 3 5 3 4/9
E 1 2 3 2 1/9
Solution

Critical path: ACDE = 14

Problem 3: What is the variance in completion time for the critical path found in Problem 2?

Total variance   variances of activities on critical path

118
 Operations Research

Total variance = 1/9 + 16/9 + 4/9 + 1/9 = 2 2/9 = 2.44

And σ = 2.44 = 1.6

3. A project has an expected completion time of 40 weeks and a standard deviation of 5 weeks. It
is
assumed that the project completion time is normally distributed.

(a) What is the probability of finishing the project in 50 weeks or less?

(b) What is the probability of finishing the project in 38 weeks or less?

(c) The due date for the project is set so that there is a 90% chance that the project will be
finished by this date. What is the date?

X  50  40
(a) Z   2
 5
Therefore: P(X  50)  P(Z  2)  0.97725
X 2
(b) Z    0.4
 5
Therefore: P(X  38)  P(Z  0.4)  0.34458
(c) 90%  Z  1.28  ( -  ) /     40 / 5
Therefore:   1.28*5  40  46.4weeks
4. Development of a new deluxe version of a particular software product is being considered.
The activities necessary for the completion of this project are listed in the table below along
with their costs and completion times in weeks.

Activity Normal Time Crash Time Normal Cost Crash Cost Immediate Predecessor
A 4 3 2,000 2,600 -
B 2 1 2,200 2,800 A
C 3 3 500 500 A
D 8 4 2,300 2,600 A
E 6 3 900 1,200 B, D
F 3 2 3,000 4,200 C, E
G 4 2 1,400 2,000 F
(a) What is the project expected completion date?

(b) What is the total cost required for completing this project on normal time?

119
 Operations Research

(c) If you wish to reduce the time required completing this project by 1 week, which activity
should be crashed, and how much will this increase the total cost?

Solution

(a)

Project completion time is therefore t A  t D  t E  t F  t G  4  8  6  3  4  25

(b) Total cost  $2, 000  $2200  $500  $2,300  $900  $3, 000  $1, 400  $12,300

$2,600  $2,300 $300

(c) Crash D 1 week at an additional cost of   $75
84 4

5. Why is CPM/PERT a popular and widely applied project scheduling technique?

6. What is the purpose of a CPM/PERT network?

7. Why are dummy activities used in a CPM/PERT network?

8. Describe the difference between activity-on-node and activity-on-arrow project networks.

9. What is the critical path and what is its importance in project planning?

10. What is slack and how is it computed?

120
 Operations Research

CHAPTER SIX
GAME THEORY

Introduction

Life is full of conflict and competition. Numerous examples involving adversaries in conflict
include parlor games, military battles, political campaigns, advertising and marketing campaigns
by competing business firms, and so forth. A basic feature in many of these situations is that the
final outcome depends primarily upon the combination of strategies selected by the adversaries.
Game theory is a mathematical theory that deals with the general features of competitive
situations like these in a formal, abstract way. It places particular emphasis on the decision
making processes of the adversaries.

Learning Outcomes
After studying this chapter, you will be able to
 Understand the basics of game theory
 Articulate the two-person game theory
 Articulate the zero-sum game theory

6.1 Two Person Zero-Sum Game

Game theory provides a mathematical framework for analyzing the decision-making processes
and strategies of adversaries (or players) in different types of competitive situations. The
simplest type of competitive situations is two-person, zero-sum games. These games involve
only two players; they are called zero-sum games because one player wins whatever the other
player loses.
Example: Odds and Evens
Consider the simple game called odds and evens. Suppose that player 1 takes evens and player 2
takes odds. Then, each player simultaneously shows either one finger or two fingers. If the
number of fingers matches, then the result is even, and player 1 wins the bet ($2). If the number
of fingers does not match, then the result is odd, and player 2 wins the bet ($2). Each player has

121
 Operations Research

two possible strategies: show one finger or show two fingers. The payoff matrix shown below
represents the payoff to player 1.

Basic Concepts of Two-Person Zero-Sum Games

This game of odds and evens illustrates important concepts of simple games.
 A two-person game is characterized by the strategies of each player and the payoff matrix.
 The payoff matrix shows the gain (positive or negative) for player 1 that would result from
each combination of strategies for the two players. Note that the matrix for player 2 is the
negative of the matrix for player 1 in a zero-sum game.
 The entries in the payoff matrix can be in any units as long as they represent the utility (or
value) to the player.
 There are two key assumptions about the behavior of the players. The first is that both
players are rational. The second is that both players are greedy meaning that they choose
their strategies in their own interest (to promote their own wealth).
To illustrate the basic characteristics of two-person, zero-sum games, consider the game called
odds and evens. This game consists simply of each player simultaneously showing either one
finger or two fingers. If the number of fingers matches, so that the total number for both players
is even, then the player taking evens (say, player 1) wins the bet (say, $1) from the player taking
odds (player 2). If the number does not match, player 1 pays $1 to player 2. Thus, each player
has two strategies: to show either one finger or two fingers. The resulting payoff to player 1 in
dollars is shown in the payoff table given in Table 14.1. In general, a two-person game is
characterized by (1) the strategies of player 1; (2) the strategies of player 2 and (3) the payoff
table.

122
 Operations Research

6.2 Pure Strategies: Game with Saddle Point

The fact that this game possesses a saddle point was actually crucial in determining how it
should be played. Because of the saddle point, neither player can take advantage of the
opponent‟s strategy to improve his own position. In particular, when player 2 predicts or learns
that player 1 is using strategy 2, player 2 would incur a loss instead of breaking even if he were
to change from his original plan of using his strategy 2. Similarly, player 1 would only worsen
his position if he were to change his plan. Thus, neither player has any motive to consider
changing strategies, either to take advantage of his opponent or to prevent the opponent from
taking advantage of him. Therefore, since this is a stable solution (also called an equilibrium
solution), players 1 and 2 should exclusively use their maximin and minimax strategies,
respectively. As the next variation illustrates, some games do not possess a saddle point, in
which case a more complicated analysis is required.

6.3 Mixed Strategies: Game without Saddle Point

What are the resulting consequences if both players plan to use the strategies just derived? It can
be seen that player 1 would win 2 from player 2, which would make player 2 unhappy. Because
player 2 is rational and can therefore foresee this outcome, he would then conclude that he can
do much better, actually winning 2 rather than losing 2, by playing strategy 2 instead. Because
player 1 is also rational, he would anticipate this switch and conclude that he can improve
considerably, from 2 to 4, by changing to strategy 2. Realizing this, player 2 would then consider
switching back to strategy 3 to convert a loss of 4 to a gain of 3. This possibility of a switch
would cause player 1 to consider again using strategy 1, after which the whole cycle would start
over again. Therefore, even though this game is being played only once, any tentative choice of a
strategy leaves that player with a motive to consider changing strategies, either to take advantage
of his opponent or to prevent the opponent from taking advantage of him.

In short, the originally suggested solution (player 1 to play strategy 1 and player 2 to play
strategy 3) is an unstable solution, so it is necessary to develop a more satisfactory solution. But
what kind of solution should it be? The key fact seems to be that whenever one player‟s strategy
is predictable, the opponent can take advantage of this information to improve his position.
Therefore, an essential feature of a rational plan for playing a game such as this one is that

123
 Operations Research

neither player should be able to deduce which strategy the other will use. Hence, in this case,
rather than applying some known criterion for determining a single strategy that will definitely
be used, it is necessary to choose among alternative acceptable strategies on some kind of
random basis. By doing this, neither player knows in advance which of his own strategies will be
used, let alone what his opponent will do. This suggests, in very general terms, the kind of
approach that is required for games lacking a saddle point. In the next section we discuss the
approach more fully. Given this foundation, the following two sections will develop procedures
for finding an optimal way of playing such games. This particular variation of the political
campaign problem will continue to be used to illustrate these ideas as they are developed.

6.4 The Rule of Dominance

Ordinal Scales are used in the rule of dominance (Pareto Principle). This rule states that one
alternative is more preferable than another if it has criterion levels that are not less preferable on
all attributes and is more preferable on at least one. This rule does not utilize criterion
importance and is not necessarily connected with an additive form of a value function but it
requires preferential independence of each separate criterion from all other criteria.

Rank Ordering of Criteria upon Importance does not provide any decision rule by itself. In
combination with ordinal scales and lexicographical criterion ranking, the rule for selection of
the best alternative may be as follows: first select alternatives with the best possible level upon
the most important criterion. From the resulting subset select alternatives with the best possible
level upon the next important criterion and so on. This rule is based on the assumption that in the
criterion ranking one attribute is more important than all the other attributes, which follow it in
the ranking. This preemptive rule does not necessarily imply the additive value function, but has
the obvious drawback of its non-compensatory nature, and is theoretically unpopular.

Self-assessment Questions (SAQs) 6

1. Define the game theory.

2. Discuss the application of game theory in business.

124