# HUNGARIAN METHOD AND SOLUTION TO SOLVING ASSIGNMENT

## Content

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

Page

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 avaliable 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.

Jobs

1         2         3       …j        …n

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.