For

B.SC Semester – VI Examination 2023-24

In

MATHEMATICS (HONOURS)
BANKURA UNIVERSITY

BANKURA CHRISTIAN COLLEGE

BANKURA UNIVERSITY
2023-24
 ASSIGNMENT PROBLEM
Under the supervision of Dr. uttpal Samanta
Submitted By
Koyel Nandi

UID: 22013121035
Registration No. 00403 of 2022-23
Subject: Mathematics
Course Title: Project Work
Course ID: 62117
Course Code: SH/MTH/604/DSE-4
Examination: B.Sc Semester – VI Honours
Examination, 2024-25

BANKURA CHRISTIAN COLLEGE

BANKURA
2023-24
 CERTIFICATE
This is to certify that Koyel Nandi (UID: 22013121035, Registration No.: 00403 Of 2022-
23) of Department of Mathematics, Bankura Christian College, Bankura, has
successfully carried out this project work entitled “ASSIGNMENT PROBLEM” under my
supervision and guidance.

This project has been undertaken as a part of the Curriculum of Bankura University
(Semester – VI, Paper: DSE-4 (Project Work)) (Course ID: 62117) and for the partial
fulfillment for the degree of Bachelor of Science (Honours) in Mathematics of Bankura

University in 2024 – 25

Signature of Supervisor. Signature of Head of the Department

(Dept. of Mathematics, Bankura Christian College)

Name of the Supervisor

Department of Mathematics

Bankura Christian College

Submitted for UG Semester – VI Project Viva-voce Examination, 2023–

24 in Mathematics (Honours) (Paper: DSE-4 (Project Work)) held on ------------------------

Signature of Internal Examiner(s) Signature of the External Examiner

Date:- Date:-
 DECLARATION
hereby declare that my project, titled ‘Inner Product Space’, submitted by me to
Bankura University for the purpose of DSE-4 paper, in semester VI under the
guidance of my professor of Mathematics in Bankura Christian College, Dr. utpal
Samanta

I also declare that the project has not been submitted here by any other student.

Name: Koyel Nandi

UID Number: 22013121035

Semester: VI
 ACKNOWLEDGEMENT
First of all I am immensely indebted to my institution, Bankura Christian College under
Bankura University and it is my humble pleasure to acknowledge my deep senses of
gratitude to our principal sir, Dr. Fatik Baran Mandal, for the valuable suggestions and
encouragement that made this project successful. I am grateful to the HOD of our
Mathematics department, Dr. Utpal Kumar Samanta for always lending his helping hand in
every situation and whose guidance and valuable support has been instrumental in the
completion ofthis project work.
 CONTENTS
 Introducation
 Objectives & Importance
 Problem Statement and Scope of the
Project
 Methodology
 Expected Outcomes
 References
INTRODUCTION
Assignment problem Plays a major role in our real life. Problems related to
assignment arise in a range of fields, for example healthcare transportation,
education, sports e.t.c.

An assignment problem is a special type of linear programming problem where

the objective is to minimize the cost or time of completing a number of jobs by a
number of persons. One of the important characteristicsof assignment problem is
that only one job (or worker) is assigned to one machine (or project).

This method was developed by D. Koning, a Hungarian mathematician and is

therefore known as the Hungarian method of assignment problem. In order to use
this method, one needs to know only the cost of making all the possible
assignments. Each assignment problem has a Matrix (table) associated with it.
Normally, the objects (or people) one wishes to assignare expressed in rows,
where as the columns represent the tasks (or things) assigned to them.

The assignment problem deals with allocating various resources (items) to various
activities (receivers) on a one to one basis, i.e., the number of operations are to be
assigned to an equal number of operators where each operator performs only one
operation. For example, suppose an accounts officer has 4 subordinates and 4 tasks. The
subordinates differ in efficiency and take different time to perform each task. If one task
is to be assigned to one person in such a way that the total person hours are minimised,
the problem is called an assignment problem. Though the assignment problem is a
special case of transportation problem, it is not solved using the methods described in
Unit 4. We use another method called the Hungarian method for solving an assignment
problem. It is shorter and easier compared to any method of finding the optimal solution
of a transportation problem. In this unit, we discuss various types of assignment
problems, including travelling salesman problem and apply the Hungarian method for
solving these problems. In the next unit, we shall discuss the fundamental structure and
operating characteristics of a queueing system and explain a single server M/M/1
queueing model with Poisson input and exponential service time.

• Objectives & Importance

It seems like you're looking for help with understanding the importance and objectives of
an assignment problem.

Assignment problems are a type of problem in operations research and management

science that involve assigning a set of agents (or resources) to a set of tasks in the most
efficient way possible. The goal is often to minimize cost, time, or maximize profit or
efficiency.
 Some key objectives of assignment problems include:

Optimal Resource Allocation: Assign tasks to agents in a way that optimizes the
use of resources.

Cost Minimization: Minimize the total cost of assigning tasks to agents.

Tme Optimization: Minimize the total time taken to complete all tasks.

Maximizing Efficiency: Maximize the overall efficiency of the assignment.

The importance of assignment problems lies in their wide range of applications,

including:

Resource Allocation: In manufacturing, logistics, and other industries, assignment

problems help allocate resources efficiently.

Scheduling: Assignment problems can be used to schedule tasks, jobs, or projects.

Supply Chain Management: Assignment problems can help manage supply chains by

mproved Decision-Making: By finding the optimal assignment, organizations can

make informed decisions about resource allocation, leading to better outcomes.

Increased Efficiency: Solving assignment problems can help reduce waste, lower
costs, and improve overall efficiency in various industries.

Enhanced Productivity: By assigning tasks to the most suitable resources,

organizations can maximize productivity and achieve better results.

 Problem Statement and Scope of the Project

The assignment problem refers to the analysis on how to assign objects to objects in the
best possible way (optimal way).

The assignment signifies underlying combinatorial structure, while the objective function
reflects the desires to be optimized as much as possible. The essential characteristics of
the assignment problem is that n resources are to be assigned to n activities such that
each resource is allocated to each activity and each activity is performed by one
resourceonly. The allocation is to be done in such a way that the resultant effectiveness
will be maximized

Matrix form of assignment problem:-

The assignment problem can be stated that in the form of 𝑚×𝑛

matrix 𝐶𝑖𝑗 called a Cost Matrix (or) Effectiveness Matrix where 𝐶𝑖𝑗 is

the cost of assigning 𝑖𝑡ℎ machine to 𝑗𝑡ℎ.

 MATHEMATICAL FORMULATION OF AN ASSIGNMENT
PROBLEM :-
Consider an assignment problem of assigning n jobs to n machines (one job to one
machine). Let 𝐶𝑖𝑗be the unit cost of assigning ith machine to the jth job and ,ith machine
to jth job.

Let xij= 1 , if jth job is assigned to ith machine.

xij= 0 , if jth job is not assigned to ith machine.

Minimize Z =Σ𝑛𝑖=1Σ𝑐𝑖𝑗 𝑛𝑗=1𝑋𝑖𝑗

subject to the constraints

Σ𝑋𝑖𝑗𝑛𝑖=1 =1 , j= 1,2,3,4,….., n

Σ𝑋𝑖𝑗𝑛𝑗=1 =1, I = 1,2, 3, ..,n

xij = 0 or 1

ASSIGMENT ALGORITHM (OR) HUNGARIAN

METHOD :-
First check whether the number of rows is equal to number ofcolumns, if it is so, the
assignment problem is said to be balanced.Then proceed to step 1. If it is not balanced, then
it should be balanced before applying the algorithm.

Step 1: Subtract the smallest cost element of each row from all theelements in the row of the
given cost matrix. See that each row contains at least one zero.

Step 2: Subtract the smallest cost element of each column from allthe elements in the
column of the resulting cost matrix obtained bystep 1 and make sure each column contains
at least one zero.

Step 3: (Assigning the zeros)

(a) Examine the rows successively until a row with exactly one unmarked zero is found.
Make an assignment to this single unmarked zero by encircling it. Cross all other zeros in
the column of this encircled zero, as these will not be considered for any future assignment.
Continue in this way until all the rows have been examined.

(b) Examine the columns successively until a column with exactly one unmarked zero is
found. Make an assignment to this single unmarked zero by encircling it and cross any other
zero in its row. Continue until all the columns have been examined.

Step 4: (Apply Optimal Test)

(a) If each row and each column contain exactly one encircled zero,then the current
assignment is optimal.
(b) (b) If atleast one row or column is without an assignment (i.e., if there is atleast one
row or column is without one encircled zero), then the current assignment is not
optimal. Go to step 5. Subtract the smallest cost element of each column from all the
elements in the column of the resulting cost matrix obtained by step 1 and make sure
each column contains atleast one zero.

Step 5: Cover all the zeros by drawing a minimum number of straight lines as follows:

(a) Mark the rows that do not have assignment.

(b) Mark the columns (not already marked) that have zeros in markedrows.

(c) Mark the rows (not already marked) that have assignments inmarked columns.

(d) Repeat (b) and (c) until no more marking is required.

(e) Draw lines through all unmarked rows and marked columns. If the number of these
lines is equal to the order of the matrix, then it is anoptimum solution otherwise not.

Step 6: Determine the smallest cost element not covered by thestraight lines. Subtract
this smallest cost element from all theuncovered elements and add this to all those
elements which are lyingin the intersection of these straight lines and do not change
theremaining elements which lie on the straight lines.

Step 7: Repeat steps (1) to (6), until an optimum assignment is obtained

VARIATION IN ASSIGNMENT PROBLEM:-

The structure of the assignment problem may be extended in the following cases.

1. MAXIMIZATION PROBLEM: In some situations the assignment problem may call for
maximization of profit, revenue etc. as the objective. For dealing with such problems, we
first change it into an equivalent minimization Problem. This is achieved by subtracting
each of the elements of the given pay-off matrix from a constant value (say K) usually
the larges of all values in the given matrix is located and them each one of the values is
Subtracted from it such
Here the largest element is 9. The operation is Performed as stated and we get the
modified cost matrix.

Then the problem is solved the same way as the minimization problem.

ii) Unbalanced problem: If number of rows ≠Number of columns, then the problem will
be unbalanced problem and in this case we adda fictitious row or column, which ever
has deficiency with zero cost.

(III) Negative cost: If the cost matrixcontain some negative cost then we add to each
element of the row or column. a quantity, sufficient to make all the cell- elements non-
negative.

Then we proceed with the usual assignment algorithm.

iv) Impossible assignment (vacant cell): If some assignment be Impossible, that is,

if some job cannot be performed by some particular facility, then we avoid this effectively
by putting a large cast in that cell which prevents that particular assignment from being
effective in the optimal solution.

Note: -An assignment problem may have morethan one solution having the same
minimum cost .

Example of Assignment problem:-

Problem 1: Solve the following assignment problem shown in Table using Hungarian
method. The matrix entries are processing time of each man in hours.

Solution: The given problem is balanced with 5 job and 5 men

Subtract the smallest cost element of each row from all the elements in the row of the
given cost matrix. See that each row contains at least one zero.

Subtract the smallest cost element of each column from all the
elements in the column of the given cost matrix. See that each
column contains at least one zero.

Assigning the zeros, we have the following A=

Since each row and each column contain exactly one encircled zero, then the current
assignment is optimal.

Where the optimal assignment is as 1 to II, 2 to IV, 3 to I, 4 to V and 5 to III .

The optimal z = 15+14+21+20+16 = 86 hours

Problem 2 :- The personal manager of ABC company wants to assign Mr. X, Mr.Y and
Mr.Z to regional offices as per the assignment table given below. But the form also has
an opening in its Chennai offices and would send one of the three to that branch if it
were more economical than a move to Delhi, Mumbai or Kolkata. It will cost Rs. 2000 to
relocate Mr. X to Chennai, Rs 1600 to relocate Mr. Y there, and Rs 3000 to Mr. Z. what
is the optimum assignment of personnel to offices
 Table – 2

Now we draw minimum number of horizontal and vertical lines in table 2 to cover all
zeros. this is done by drawing a horizontal line through the fourth row and a vertical line
through the first column. Since the number of lines =2 ≠order of cost matrix (4), so
optimality is not reached. To improve the cost matrix, subtract smallest uncovered
number 400 from all uncovered elements and add it to the element where two lines
intersect. This is shown in table 3.

Table – 3

Again, we draw minimum number of horizontal and vertical lines to cover all zeros in
table 3. Since the number of lines =3 ≠order of the cost matrix (4), optimal condition is
not reached. To improve this cost matrix, subtract uncovered number 200 from all
uncovered elements and add it to the elements where to lines intersect. this revised table
is shown in table 4 below.

Table –4

In Table -4, we see that minimum number of lines =3 ≠ order of cost matrix. Thus,
optimal condition is not reached. Again, we have to improve the cost matrix by
subtracting the smallest uncovered number 200 following the rule as done in table-2 and
Table-3 . The revised matrix is shown in Table-5 below.
 Table -5

, In Table -5, we draw minimum number of lines to cover all zeros. It is seen that the
number of lines=4=order of cost matrix .Hence, optimal condition is reached at this
stage. Assignments are done to the elements having zero cost.

Optimal assignments are

Mr. X→ Mumbai

Mr. Y→ Chennai

Mr. Z→ Delhi

Minimum cost = Rs. (2200+1600+1000) = Rs. 4800

 Methodology:-

The methodology for solving an Assignment Problem typically involves the following
steps:

Step 1: Define the Problem

1. Identify the agents: Determine the entities that will perform the tasks (e.g., workers,
machines).

2. Identify the tasks: Determine the jobs or activities that need to be completed.

3. Determine the cost matrix: Create a table that shows the cost or efficiency of each
agent performing each task.

Step 2: Prepare the Cost Matrix

1. Create a square matrix: Ensure the number of rows (agents) is equal to the number of
columns (tasks).

2. Fill in the costs: Populate the matrix with the costs or efficiencies associated with each
agent-task pair.

Step 3: Choose a Solution Method

1. Hungarian Algorithm: A popular method for solving assignment problems.

2. Linear Programming: Can be used to formulate and solve assignment problems.

Step 4: Apply the Solution Method

1. Hungarian Algorithm: Follow the steps of the algorithm to find the optimal assignment.

- Step 1: Subtract the minimum value from each row.

- Step 2: Subtract the minimum value from each column.

- Step 3: Cover all zeros with lines.

- Step 4: Find the smallest uncovered value and subtract it from all uncovered
elements.

- Step 5: Repeat steps 3-4 until an optimal assignment is found.

2. Linear Programming: Formulate the problem as a linear program and solve using a
suitable method (e.g., simplex method).

Step 5: Interpret the Results

1. Optimal assignment: Determine the optimal assignment of tasks to agents.

2. Total cost or efficiency: Calculate the total cost or efficiency of the optimal assignment.

By following these steps, you can solve an Assignment Problem and find the optimal
assignment of tasks to agents.

• Expected Outcomes:-
The assignment problem is a well-known optimization problem in operations research
and mathematical optimization. It involves assigning a set of tasks to a set of agents in
such a way that the overall cost or benefit is minimized or maximized, depending on the
objective. It is very important to choose the right approaches in solving the problem, so
as to obtain an optimal or near optimal depending on the complexity of the problem. This
research may open up different paths associated with real life problems.

• References:-
1. Linear programming &game theory Dr. Nani Gopal mandal Biswadip pal

2. Linear programming &game theory Chakrabarty &Ghosh

3. Wikipedia https://en.wikipedia.org/wiki/Assignment_problem x

4. Linear programming & game theory --Dc Sanyal , K. Das