ABSTRACT
This
project is basically prepared on Assignment problems and its solution. There
are different ways of solving Assignment problem in operation research.
The
use of Hungarian method of solving assignment which is of great value in more
advance parts of operation research.
The
first part of this project is introduction which deals with origination of
assignment problems and some notable application in the problem. It also deals
with its relation to transportation problem, its characteristics.
Chapter
two deals with Hungarian method of solution and its procedures. Chapter three
deals with the special assignment problem which include the special
minimization problems. Chapter four shows the solution to the prohibited
assignment problems and examples. Chapter five deals with the conclusion on how
Assignment problems can be related to real life mathematics. This can be easily
described as a way of introducing real life solutions to our day to day
problems.
TABLE
OF CONTENT
TITLE PAGE …i
CERTIFICATION …ii
DEDICATION …iii
ACKNOWLEDGEMENT …iv-v
ABSTRACT …vi
TABLE OF CONTENT …vii-ix
CHAPTER
ONE
1.0 INTRODUCTION …1
1.1 DEFINITION …2
1.2
THE
ORIGIN OF OPERATION RESEARCH …3
1.2.1 TRAINING
FOR A CAREER IN OPERATION
RESEARCH
…5
1.2.2 THE IMPACT OF OPERATION RESEARCH …7
1.3 ASSIGNMENT PROBLEM AND
TRANSPORTATION
PROBLEM …9
1.3.1 TRANSPORTATION PROBLEM ...10
1.4 CHRACTERISTICS OF ASSIGNMENT PROBLEM ...10
1.5 SPECIAL ASSIGNMENT
PROBLEM …11
CHAPTER
TWO
2.1 ASSIGNMENT
PROBLEMS USING
HUNGARIAN
METHOD …13
2.2 MATHMATICS FORMULATION OF
THE ASSIGNMENT PROBLEM …14
2.3 HUNGARIAN METHOD PROCEDURE
MATRIC
INTERPRETATION …16
2.4 MINIMIZING ASSIGNMENT …21
2.5 MAXIMIZATIONN ASSSIGNMENT …29
CHAPTER
THREE
3.1 SPEICAL
ASSIGNMENT PROBLEMS …41
3.2 SPECIAL MINIZING
ASSIGNMENT PROBLEM …41
3.3 SPECIAL MAXIMIZING
ASSIGNMENT PROBLEM …47
CHAPTER
FOUR
4.1 PROHIBITED ASSIGNMENT …52
4.2 EXAMPLE …52
CHAPTER
FIVE
5.1 CONCLUSION …57
5.2 RECOMMENDATION …57
REFERENCES …58
CHAPTER ONE
1.0 INTRODUCTION
Imagine,
if in a printing press there is one machine and one operator is there to
operate, how you would employ the worker. Your immediate answer will be that
the available operator will operate the machine.
Again,
suppose there are two machines in the press and two operators are engaged at
different rates to operate them. Which operator should operate which machine
for maximizing profit?
Similarly,
if there are 
machines, available and persons are engaged at different rates to
operate them. Which operator should be assigned to which machine to ensure
maximum efficiency?
While
answering the above questions we have to think about the interest of the press,
so we have to find such an assignment by which the press gets maximum profit on
minimum investment. Such problems are known as "assignment problems".
This
project deals with an interesting method called the assignment technique which
is capable to a class of practical problems. The
objective of the assignment problem is to assign numbers of origin (job) to the
equal number of descriptions (persons) at a minimum cost or maximum profit.
1.1 DEFINITION
What
is an assignment problem: The assignment problem is one of the fundamental
{combination optimization problem} in the branch of optimization or operation
research in mathematics. It consists of finding a maximum weight in a {weighted
bipartite graph}.
In
its most general form, the problem is as follows. There are a number of agents
with a number of tasks. Any agent can be assigned to perform any task incusing some
cost that may vary depending on the agent task assignment. It is required to
perform all tasks by assigning exactly one agent to each in such a way that the
total cost of the assignment is minimized.
If
the number of agents and tasks are equal and the total cost of the assignment
for all tasks is equal to the sum of the costs for each agent {or the sum, this
case}. Then the problem is called the linear assignment problem. Commonly when
speaking of the assignment problem without any additional qualification then
the linear assignment problem is meant.
Suppose
there are jobs to be performed and persons are available for doing these jobs.
Assume that each person can do the job at a time, though with varying degree of
efficiency.
Let
M be the cost if the 5th person is assigned to the job. The problem is to find
an assignment (which total cost performing all jobs is minimum). Problems of
this kind are known as "assignment problem". The
assignment problem can be stated in the form of cost matrix of real number as giving in the following table.
1.2
THE ORIGIN OF OPERATION RESEARCH
Since
the advent of the industrial revolution, the world has seen a remarkable growth
in the size and complexity of organizations. The artisan’s small shops of an
earlier era have evolved into the dollar corporations of today. An integral
part of this revolutionary change has been a tremendous increase in the
division of labour 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 the best for one component frequently is detrimental to another, so
they 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 its available resources to its various activities in
a way that most effective for the organization as a whole. These kinds of
problems and the need to find a better way to resolve them provided the
environment for the emergence of operation research.
The
roots of operation research 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 operation research has generally
been attributed to the military services early in World War II.
1.2.1
TRAINING FOR A CAREER IN OPERATION RESEARCH
Because
of the great growth of operation research, career opportunities in this field
appear to be outstanding. The demand for trained people continues to far exceed
the supply, and both attractive starting positions and rapid advancement are
readily available. Because of the nature of their work, operations research
groups tend to have a prominent staff position, with access to higher level
management in the organization. The problems they work or tend to be important,
challenging and interesting. Therefore, any individual with a mathematics and
science orientation who is also interested in the practical management of
organization is likely to find a career in operations very rewarding.
Three
complementary types of academic training are particularly relevant for a career
in operation research. The first is a basic training in the fundamentals upon which
operation research is based. This includes the basic methodology of mathematics
and science as well as such topics as linear algebra and matrix theory,
probability theory and the behavioral sciences.
Second
important types of training is an operation research per se, including special
techniques of the field such as linear and non linear programming, dynamic programming,
inventory theory, network flow theory, quivering models, reliability, game
theory and simulation. It should also include an introduction to the
methodology of operation research where the various techniques and their role
in an operations research study involving specific problem areas would be
placed in perspective. Often courses covering certain of these topics are
offered in more than one department within a university, including Departments
of Business, Industrial Engineering, Mathematics, Statistics, Computer Science,
Economics and Electrical Engineering. This is a natural reflection of the board
scope of application of the field. Since it does spread across traditional
disciplinary lines, separate programs or departments in operations research
also are being established in some universities.
Finally,
it is also good to have specialized training in some field other than operations
research, for example, Mathematics, Statistics, Industrial engineering,
business or economics. This additional training provider one with an era of
special competence for applying operation research and it should make that
person a more valuable member of an operations research term.
The
early operations researchers were people were whose primary training and work
had been in some traditional field, such as Physics, Chemistry, Mathematics Engineering
or Economics. They tended to have little or no formal education in operation
research.
1.2.2 THE IMPACT OF OPERATION RESEARCH
Operations
research has had an increasingly great impact on the management of organization
in recent years. Both the number and the variety of its applications continue
to grow rapidly and no slowdown is in sight. Indeed, with the exception of
advent of the electronic computer, the extent of this impact seems to be
unrivaled by that of any other recent development.
After
their success with operations research during World War II, the British and
American military services continued to have active operations research groups,
often at different levels of command. As a result, there now exist a large
number of people called military operation researchers who are applying an
operation research approach to problems of national defense. For example, they
engage in tactical planning for requirements and use of weapons systems as well
as consider larger problems of the allocation and integration of effort. Some
of their techniques involve quite sophisticated ideas in political science,
Mathematics, Economics, Probability theory and Statistics.
Operations
research is also being used widely in other types of organizations, including
business and industry. Almost all the dozen or so largest cooperation’s in the
world and a sizeable proportion of the small industrial organization, have well
established operations research groups. Many industries including aircraft and
missile, automobile, communication, computer, electric power electronics, ford,
metallurgy, mining, paper, petroleum and transportation, have made widespread
use of operations research. Financial institutions, government agencies and
hospitals are rapidly increasing their use of operations research.
To
be more specific, consider some of the problems that have been solved by
particular techniques of operations research. Linear programming has been used
successfully in the solution of problems concerned with assignment of
personnel, blending of materials, distribution and transportation and
investment portfolios. Dynamic programming has been applied successfully to
such areas as planning advertising expenditures, sales effort and production
scheduling, design of dams, production scheduling and hospital operation. Other
techniques of operation research, such as inventory theory, game theory and
simulation, also have been successfully applied to a variety of contexts.
1.3 ASSIGNMENT PROBLEM AND TRANSPORTAION PROBLEM
This
has to do with assignment of a particular labour (usually machines, objects or
humans) to a particular task or job in order to optimize, the efficiency of the
system.
In
assignment problem, if k resources
are to be assigned, there must be k different
locations to receive these k resources; this based on the one-to-one
correspondence assumption that is basic to assignment problems.
In
assignment is of the principle of discrete entry, hence one-to-one
correspondence. For example, machines, men and objects are discrete entities.
This is because each of them has a unique identity, say one man, two men, five
machines, eight machines and not a half man or four and third machine.
1.3.1 TRANSPORTATION PROBLEM
This
is the effective and efficient way to move (i.e. transport goods (products,
humans, commodities and other moveable materials from two or more locations to
another (two or more) locations at the most optimize utilization of the medium
of transportation in order to get more profit to the person or object involved.
The
objective of transportation of any kind is to get more profit. That is, it is
either to maximize the cost that an individual will procure in transporting the
goods or commodities, the transporter will put in his best to maximize the
profit that will get to him in the process of transporting business.
1.4
CHARACTERISTICS OF ASSIGNMENT PROBLEM
It
must be observed that an assignment problem must be having associated with it a
square matrix before it can be solved. Otherwise, the non square matrix must be
made square by the introduction of dummy.
Therefore
for an assignment problem with k dimensions,
it must have i.e. (k functions)
possible arrangements for making assignment.
1.5 SPECIAL
ASSIGNMENT PROBLEMS
There
are two major cases of an assignment problem.
CASE 1
In
the case where the associated matrix is not a square matrix in which case this
matrix has to be made square by the introduction of dummies are assumed to be
catalyst that will aid the one-to-one correspondence assumption that is very
fundamental for all assignment problems. Usually the dummy will not carry any
weight as a result of the involvement in the process.
CASE 2:
The
second special case is a situation by an assignment problem aiming at
maximizing its benefit as opposed to the general believes that it is used from
maximization.
Generally,
both transportation and assignment problems are used for cost minimization and
most techniques that are developed to solve them around this area. This makes
any other case to be a special case.
Click “DOWNLOAD NOW” below to get the complete Projects
FOR QUICK HELP CHAT WITH US NOW!
+(234) 0814 780 1594
Login To Comment