Operation Research

UNIT -4
ASSIGNMENT MODEL

The assignment problem is a special type of linear programming problem, with the following
feature:-

OBJECTIVE: The objective is either to maximize profit or to minimize cost.

NATURE OF DATA: „ m‟ jobs / products are to be assigned to „n‟ persons/facilities. it is not

always necessary that m = n. if they are equal, data is said to balanced , otherwise ,data is said to
be unbalanced.

CONDITION: Assignment should be on a one-to-one basis {i.e., two jobs cannot be assigned to
the same persons ; and two persons cannot be assigned the same job}

ASSIGNMENT PROCEDURE:

STEP DESCRIPTION
1 Verify objective = minimisation. In case of profit matrix , i.e., maximisation
objective convert the same in to an opportunity loss matrix , by subtracting each
number from the highest number in the matrix.
2 Verify nature of data = balanced. Data is balanced if number of rows equal to
number of columns. in case of un balanced data , add a dummy row or column as
required , with all element being zero.

3 Row operation. subtract the smallest number in each row from all elements of
that row
4 Column operation. In the resultant matrix from step3, subtract the smallest
number in each column from all elements of the column.

5 Draw the minimum number of horizontal and vertical lines to cover all zeroes in
the matrix. Optimal assignment is possible only if number of lines = order of
matrix.
6
In case number of lines « order of the matrix, increase the number of zeroes as
under-
(A) Select the smallest number not covered by the lines. call this as least open
element
i.e. LOE
(B) Rewrite the matrix ,with the following adjustment-
• Open element - not covered by any line-previous element less LOE
• Covered element-covered by one line only -no change
• Junction element - covered by intersection of two lines - previous element
plus LOE
Repeat step 5 for such revised matrix till number of lines = order of matrix

45 | Page
 Operation Research

7 Optimal assignment is made in the following manner-

(a) Go row-wise, identify a row with only one zero.
(b) Select this zero as an assignment by drawing a box around it.
(c)Cancel all the zero in that column since the same job cannot be assigned to a
different facility
(d) Continue this procedure with columns and complete the assignment.
In case of multiple optimal solution or ties up to the last stage, arbitrary assignment can
be made.

Minimisation
Q 1. Find the optimal assignment schedule of the following cost matrix.
Marketing N E W S
A 14 20 11 19
B 12 10 15 9
C 16 19 18 15
D 17 13 15 14

Q 2. Four operators A, B, C & D are available to a manager who has to get four jobs J1, J2, J3 &
J4 done by assigning one job to each operator. The time needed by different operators for
different jobs are given in the matrix below - How should manager assign the jobs so that the total
time needed for all the jobs is minimum?
Operator/Job J1 J2 J3 J4
A 12 10 10 8
B 14 12 15 11
C 6 10 16 4
D 8 10 9 7

Q 3. A project consists of 4 major jobs, for which 4 contractors have been submitted tenders. The
tender amounts, in thousand of rupees, are given below :
Contractors Jobs
A B C D
1 120 100 80 90
2 80 90 110 70
3 110 140 120 100
4 90 90 80 90
Find the assignment, which minimizes the cost of the project. Each contractor has to be assigned
one job.

46 | Page
 Operation Research

Q 4. A production supervisor is considering, how they should assign five jobs that are to be
performed, to five mechanists working under him. He wants to assign the jobs to be mechanists
in such a manner that the aggregate cost to perform the jobs is the least. He has following
information about the wages paid to the mechanists for performing these jobs.

47 | Page
 Operation Research

Mechanists Jobs
1 2 3 4 5
A 10 3 3 2 8
B 9 7 8 2 7
C 7 5 6 2 4
D 3 5 8 2 4
E 9 10 9 6 10
Assign the jobs to the mechanists so that the aggregate cost is the least.

Q 5. An Electronic Data Processing (EDP) centre has three expert software professionals. The
centre wants three application software programs to be developed. The head of EDP centre
estimates the computer time in minutes required by the experts to Development of Application
software Programs as follow :
Software Programs Computer time (in min) Required by Software Professionals
A B C
1 100 85 70
2 50 70 110
3 110 120 130

Q 6. A repair shop has 6 technician & they are to be assigned to 5 jobs (Obviously one technician
remaining in excess). The time taken by each technician is as follows:
Technician Jobs
P Q R S T
A 10 11 18 10 18
B 7 8 10 8 12
C 11 9 11 11 10
D 13 11 11 12 10
E 10 9 10 8 10
F 8 11 10 10 10
Is it possible to assign 5 jobs to 5 technician in a manner to minimize the overall time?

Q 7. A building construction company has 5 heavy earth-moving equipments currently located

one each at construction sites, A, B, C, D & E. Over the week-end, these have to be transported
one each to new sites P, Q, R, S & T. The distance in kilometres from present location are given in
the matrix below :
P Q R S T
A 17 18 14 19 24
B 17 21 18 22 27
C 10 12 9 16 19
D 16 17 17 20 27
E 18 18 15 19 20

48 | Page
 Operation Research

The cost of transportation is a fixed sum of Rs.150/- per equipment & variable amount at the rate
of Rs.12/- per kilometre of travel involved. Find the optimal plan to transport the equipments
from current sites to the new sites & the overall cost thereof.

Q 8. A departmental stores agency runs 5 stores located at different parts of a city. Each store is
administrated by a manager appointed by the agency. The managers reside in different part of
the city. The agency reimburses the car travel expenses incurred by the managers in commuting
to work from their residence to the stores to which they are assigned. The basis of
reimbursement is :
Managers Stores (Distance in KM)
S1 S2 S3 S4 S5
A 4 10 12 18 17
B 7 16 16 22 18
C 8 6 9 19 21
D 11 12 15 12 13
E 9 14 19 18 14
A fixed sum of Rs.300/- per month for repair/maintenance. A variable amount at the rate of
Rs.1.60/KM of travel incurred during the month. All stores work for 25 days in a month. The
distance in KM from a manager‟s residence to the store is shown in the following matrix

Maximization

Q 1. Five lathes are to be allotted to five operators. The weekly output figures are given below :
Operator Weekly output in lathes
L1 L2 L3 L4 L5
P 20 22 27 32 36
Q 19 23 29 34 40
R 23 28 35 39 34
S 21 24 31 37 42
T 24 28 31 36 41
Profit per piece is Rs. 25. Find the maximum profit per week?

Q 2. A Methods Engineer wants to assign four new methods to three work centers. The
assignment of new methods will increase production, details of which are given below.
Determine the optimal assignment, if only one method can be assigned to each work centre.
Methods Increase in production (units) in work centers
A B C
1 10 7 8
2 8 9 7
3 7 12 6
4 10 10 8

49 | Page
 Operation Research

Q 3. Mitsubishi PLC within the framework of its corporate plan is considering the closure of on of
the UK factories. The cost of closure will be the same for each factory. Currently, it operates five
factories each of which can produce any of four products. It is envisaged that in the future,
individual factory will achieve production & other economies by concentrating on one product
alone. The production cost data for existing operations is summarized below:
F actory Production cost per unit (£) of product
N I P Q
1 71 78 93 76
2 69 78 87 74
3 72 80 89 76
4 73 80 86 78
5 65 84 92 72
Selling Price 80 90 100 85
The selling rice for each of the product is consistent, irrespective of the factory in which it is
produced: Required: Recommend to the board of Mitsubishi PLC which factory should be closed.

Q 4. A marketing manager has 5 salesmen & there are 5 sales districts. Considering the
capabilities of the salesmen & the nature of districts, the estimates made by the marketing
manager for the sales per month (in 1000 rupees) for each salesmen in each district would be as
follow :

A B C D E
1 32 38 40 28 40
2 40 24 28 21 36
3 41 27 33 30 37
4 22 38 41 36 36
5 29 33 40 35 39

Find the assignment.

Q 5. A management consulting firm has a backlog of 4 contractors. Wok on these contracts must
be started immediately. Three project leaders are available for assignment to the contracts.
Because of the varying work experience of the project leaders, the profit to the consulting firm
will vary based on the assignment as shown below. The unassigned contract can be completed
by subcontracting the work to an outside consultant. The profit on the subcontract is zero.
Project Leader Contract
1 2 3 4
A 13 10 9 11
B 15 17 13 20
C 6 8 11 7
Dummy 0 0 0 0
Find the optimal assignment. Note that the problem is basically not only un balances (through
now balanced by inclusion of dummy) but also a maximization one.

50 | Page
 Operation Research

Unbalanced Assignment Problem

Q 1. There are four jobs to be assigned to the machines. Only one job could be assigned to one
machine. The amount of time in hours required for the jobs in a machine are given in the
following matrix.
Job Machines
A B C D E
J1 4 3 6 2 7
J2 10 12 11 14 16
J3 4 3 2 1 5
J4 8 7 6 9 6
Find an optimum assignment of jobs to the machine to minimize the total processing time & also.
Find for which machine no job is assigned. What is the total processing time to complete all the
jobs.

Q 2. The owner of a small machine shop has four mechanics available to assign job for the day.
Five jobs are offered with expected profit for each mechanic on each job which are as follow :
Job
J1 J2 J3 J4 J5
M1 62 78 50 111 82
Mechanic M2 71 84 61 73 59
M3 87 92 111 71 81
M4 48 64 87 77 80
Find by using assignment method, the assignment of mechanics to the job that will result in a
maximum profit. Which job should be declined?

Q 3. A company has 4 machines to do 3 jobs. Each job can be assigned to one & only one
machine.The cost of each job on each machine is given below.Determine the job assignments
which will minimise the total cost.
Machines
W X Y Z
A 18 24 28 32
Jobs B 13 17
8 18
C 10 15 19 22

51 | Page
 Operation Research

Prohibited Assignment
Q 1. The Secretary of a school is taking bids on the City‟s four School bus routes. Four companies
have made the bids as detailed in the following table :
Company Bids for Route (in RS.)
R1 R2 R3 R4
C1 4000 5000 - -
C2 - 4000 - 4000
C3 3000 - 2000 -
C4 - - 4000 5000

Q2. Solve the following assignment problem, given the cost information as :
C12 = 16, C13 = 4, C14 = 12, C23 = 6, C34 = 5, C25 = 8, C35 = 6, C45 = 20,
Cij = Cji, Cij = 00 for all values of i & j not given in the data.

Q 3 . Machine operators processes five types of items on his machine each week & choose a
sequence for them. The set-up cost per change depends on the items presently on the machine &
the set-up to be made according to the following table :
To item
A B C D E
A TO 4 7 3 4
From B 4 TO 6 3 4
item C 7 6 TO 7 5
D 3 3 7 TO 7
E 4 4 5 7 TO
If he processes each type of item once & only once in each week, how should he sequence the
items on his machine in order to minimise the total set-up cost?

Q 4. A travelling salesman has to visit 5 cities. He wishes to start from a particular city, visit each
city once & then return to his starting point. Cost of going from one city to another is shown
below. You are required to find the least cost route.
To City
A B C D E
A TO 4 10 14 2
From B 12 TO 6 10 4
City C 16 14 TO 8 14
D 24 8 12 TO 10
E 2 6 4 16 TO

52 | Page
 Operation Research

Conditional Assignment
Q 1. Four operators A, B, C & D are available to a manager who has to get four jobs J1, J2, J3 &
J4 done by assigning one job to each operator. The time needed by different operators for
different jobs are given in the matrix below - How should manager assign the jobs so that the total
time needed for all the jobs is
Operator/Job J1 J2 J3 J4
A 12 10 10 8
B 14 12 15 11
C 6 10 16 4
D 8 10 9 7
If the job J1 is to be assigned only to operator A, what should be the assignment & how much
additional total time will required ?

Q 2.The personnel manager of a medium sized company decides to recruit two employees D & E in
a particular section of the organization. The section has five fairly defined tasks 1, 2, 3, 4 & 5 & three
employees A, B & C are already employed in the section. Considering the rather specialized nature
of task 3 & the special qualification of D to recruit for task 3, the manager decides to assign task 3 to
employee D & then assign the remaining tasks to the remaining employee so as to maximize the
total effectiveness. The index of effectiveness of each employee of different tasks is as under.
Employee Tasks
1 2 3 4 5
A 25 55 60 45 30
B 45 65 55 35 40
C 10 35 45 55 65
D 40 30 70 40 60
E 55 45 40 55 10
Assign the tasks for maximizing total effectiveness. Critically examine whether the decision of
the manager to assign task 3 to employee D was correct.

Q 3. The Captain of Playwell Cricket team has to allot five middle order batting positions to five
batsmen. The average run scored by each batsman at these positions are as follows -
Batsman Batting position
I II III IV V
P 40 40 35 25 50
Q 42 30 16 25 27
R 50 48 40 60 50
S 20 19 20 18 25
T 58 60 59 55 53
1. Find the assignment of the batsman to positions, which would give the maximum number of
runs

.
53 | Page
oO

2. What will be the total runs scored if batsman T wants only the III position?
3. If another batsman U with the following average runs in batting positions as given below :
Batting I II II IV V
position
Average runs 45 52 38 50 49
Is added to the team, should he be include to play in the team? If so, who will be replaced by him?

Multiple optimum solutions

Q 1.An automobile dealer wishes to put four repairmen to four different jobs. The repairmen
have somewhat different kinds of skills & the exhibit different levels of efficiency from one
job to another. The dealer has estimated the number off man-hour that would be required for
each job-man combinations. This is given in the matrix form in adjacent table:
Man Job
A B C D
1 5 3 2 8
2 7 9 2 6
3 6 4 5 7
4 5 7 7 8
Find the optimum assignment that wi l result in minimum man-hours need ed.

Advanced Problem of Assignment

Q 1. There was a Miss Universe show at New York. The five judges appointed have to select the
top three beauties. Of the, more than 200 participants, they arrived at just 5 of them viz. Miss
India, Miss USA, Miss France, Miss Britain & Miss Brazil, but none of them agreed on top three.
There preference were as under :
JUDGE PREFERENCES
J1 J2 J3 J4 J5
Miss USA Miss USA Miss France Miss USA Miss India
Miss France Miss Britain Miss India Miss Brazil Miss USA
Miss Britain Miss Brazil Miss Britain Miss Britain Miss Britain
Miss India Miss Brazil Miss France
Miss USA
If the rankings were in the same order as given above & can be qualifies by numbers, find out
which judge preferred which beauty so that total preference ranking is a minimum.

54 | Page
 Operation Research

Q 2. A solicitor‟s firm employs typists on hourly price-rate basis for their daily work. There are
five typists for service & their charges & speed are different. According to an earlier
understanding only one job is given to one typist & the typist is paid for full hours even if he
works for a fraction of an hour. Find the least cost allocation fro the following data :

Typist Rate per hour (Rs.) No. of pages typed per hour Job No. of pages
A 5 12 P 199
B 6 14 Q 175
C 3 8 R 145
D 4 10 S 298
E 4 11 T 178

Q 3. XYZ airline operating 7 days a week has given the following timetable. Crews must have a
minimum layover of 5 hours between flights. Obtaining the pairing flights that minimizes
layover time away from home. For any given pairing the crew will be based at the city that results
in the smaller layover.
Chennai - Mumbai Mumbai - Chennai
Flight No. Depart. Arrive Flight No. Depart. Arrive
A1 6 AM 8 AM B1 8 AM 10 AM
A2 8 AM 10 AM B2 9 AM 11 AM
A3 2 PM 4 PM B3 2 PM 4 PM
A4 8 PM 10 PM B4 7 PM 9 PM

Q 4. An organization producing 4 different products viz. A, B, C & D having 4 operators viz. P,

Q, R & S, who are capable of producing any of the four products, works effectively 7 hours a day.
The time (in minutes) required fro each operator for producing each of the product are given in
the cells of the following matrix along with the profit (Rs. per unit).
Operator Product
A B C D
P 6 10 14 12
Q 7 5 3 4
R 6 7 10 10
S 20 10 15 15
Profit (Rs./unit) 3 2 4 1
Find out the assignment of the operators to products which will maximize the profit.

55 | Page
oO

Q 5. A manufacturer of complex electronic equipment has just received a sizable contract & plans
to subcontract part of the job. He has bids for 6 subcontracts from 4 firms. Each job is sufficiently
large that anyone firm can take on only one job. The table below shows the bids & the cost
estimates (Rs. in lacs) for doing the job internally. Note that no more than 2 jobs can be performed
internally.
Firms Jobs
1 2 3 4 5 6
1 48 72 36 52 50 65
2 44 67 41 53 48 64
3 46 69 40 55 45 68
4 43 73 37 51 44 62
Internal 50 65 35 50 46 63
How d o you complete this table so that the problem can be solved by the Hungarian
method?

Q 6. A firm produces 4 products. There are 4 operators who are capable of producing any of these
4 products. The processing times various from operator to operator. The firm records 8 hours a
day & allow 30 minutes for lunch. The processing time in minutes & the profit for each of the
products are given below :
Operator Product
A B C D
P 15 9 10 6
Q 10 6 9 6
R 25 15 15 9
S 15 9 10 10
Profit (Rs./unit) 8 6 5 4
Find the optimal assignment of the products to operator.

Q 7. A manufacturing company has 4 zones A, B, C, D & 4 sales engineers P, Q, R, S respectively

for assignment. Since the zones are not equally rich in sales potential, therefore it is estimated that
a particular engineer operating in a particular zone will bring the following sales :
Zones A B C D
Sales 4,20,000 3,36,000 2,94,000 4,62,000

The engineers are having the different sales ability. Working under the same conditions, their
yearly sales are proportional to 14, 9, 11 & 8 respectively. The criteria of maximum expected
total sales is to be met by assigning the best engineer to the richest zone, the next best to the
second richest zone & so on.

56 | Page
 Operation Research

Q 8. Five swimmers are eligible to compete in a relay team which is to consist of 4 swimmers
swimming in 4 different swimming style: back stroke, breast stroke, free style & butterfly. The
time taken by the 5 swimmers - Anand, Bhaskar, Chandu, Dorai & Easwar - to cover a distance
of 100 meters in various swimming style are given below in minutes : second. Anand swims the
back stroke in 1 : 09, the breast stroke in 1:50 & has never compete in the free style or butterfly.
Bhaskar is a freestyle specialist averaging 1 : 01 for the 100 meters but can also swim the breast
stroke in 1 : 16 & butterfly in 1 : 20. Chandu swims all style back stroke 1 : 10, butterfly 1:12,
freestyle 1 : 05, & breast stroke 1 : 20, Dorai swims only the butterfly 1 : 11. While Easwar
swims the back stroke 1 : 20, the breast stroke 1 : 16, & butterfly 1 : 10. Which swimmers should
be assigned to which swimming style? Who will not be in the relay.

HUNGARIAN METHOD:
Find Solution of Assignment Problem
Here given problem is balanced...
The number of row = 5
The number of column = 5
J1 J2 J3 J4 J5
W1 10 5 13 15 16
W2 3 9 18 13 6
W3 10 7 2 2 2
W4 7 11 9 7 12
W5 7 9 10 4 12

Here given problem is balanced...

Find out the each row minimum element and subtract it from that row
J1 J2 J3 J4 J5
W1 5 0 8 10 11 (-5)
W2 0 6 15 10 3 (-3)
W3 8 5 0 0 0 (-2)
W4 0 4 2 0 5 (-7)
W5 3 5 6 0 8 (-4)

57 | Page
oO

Find out the each column minimum element and subtract it from that column...
J1 J2 J3 J4 J5
W1 5 0 8 10 11
W2 0 6 15 10 3
W3 8 5 0 0 0
W4 0 4 2 0 5
W5 3 5 6 0 8
(-0) (-0) (-0) (-0) (-0)
Rowwise & columnwise assignment - final assignment...

Assigned rows and columns

No of assignment = 4, Rows = 5
Which are not equal
Tick mark not allocated rows and allocated columns
J1 J2 J3 J4 J5
W1 5 [0] 8 10 11
W2 [0] 6 15 10 3 ✓
W3 8 5 [0]
W4 4 2 [0] 5 ✓
W5 3 5 6 8 ✓
✓ ✓

Minimum element :2

Now subtract 2 from each uncovered numbers and add it to numbers at the intersection of any
lines
J1 J2 J3 J4 J5
W1 7 0 8 12 11
W2 0 4 13 10 1
W3 10 5 0 2 0
W4 0 2 0 0 3
W5 3 3 4 0 6

Rowwise & columnwise assignment - final assignment...

Assigned rows and columns

No of assignment = 5, Rows = 5
Optimal assignments are
J1 J2 J3 J4 J5

58 | Page
 Operation Research

W1 7 [0] 8 12 11
W2 [0] 4 13 10 1
W3 10 5 2 [0]
W4 2 [0] 3
W5 3 3 4 [0] 6

Optimal solution is
Work Job Cost
W1 J2 5
W2 J1 3
W3 J5 2
W4 J3 9
W5 J4 4
Total 23

Find Solution of Travelling salesman problem

The number of rows = 4 and columns = 4

1 2 3 4
1 M 4 9 5
2 6 M 4 8
3 9 4 M 9
4 5 8 9 M

Here given problem is balanced.

Step-1: Find out the each row minimum element and subtract it from that row
1 2 3 4
1 M 0 5 1 (-4)
2 2 M 0 4 (-4)
3 5 0 M 5 (-4)
4 0 3 4 M (-5)

59 | Page
oO

Step-2: Find out the each column minimum element and subtract it from that column.
1 2 3 4
1 M 0 5 0
2 2 M 0 3
3 5 0 M 4
4 0 3 4 M
(-0) (-0) (-0) (-1)

Step-3: Make assignment in the opportunity cost table

(1) Rowwise cell (2,3) is assigned

(2) Rowwise cell (3,2) is assigned, so cell (1,2) crossed off in this column.

(3) Rowwise cell (4,1) is assigned

(4) Columnwise cell (1,4) is assigned

Rowwise & columnwise assignment shown in table

1 2 3 4
1 M 5 [0]
2 2 M [0] 3
3 5 [0] M 4
4 [0] 3 4 M

Step-4: Number of assignments = 4, number of rows = 4

The solution gives the sequence : 1→4,4→1

The above solution is not a solution to the travelling salesman problem as he visits each city only
once.

The next best solution can be obtained by bringing the minimum non-zero element, i.e., 2 into the
solution.
The cost 2 occurs at 1 places. We will consider all the cases separately until the acceptable
solution is obtained.

Case: 1 of 1 for minimum non-zero element 2

Make the assignment in the cell (2,1) and repeat Step-3.
Step-3: Make assignment in the opportunity cost table

60 | Page
 Operation Research

(1) Rowwise cell (2,1) is assigned, so cell (4,1),(2,3) crossed off in this column.

(2) Rowwise cell (3,2) is assigned, so cell (1,2) crossed off in this column.

(3) Columnwise cell (1,4) is assigned

Rowwise & columnwise assignment shown in table

1 2 3 4
1 M 5 [0]
2 [2] M 3
3 5 [0] M 4
4 3 4 M

Step-4: Number of assignments = 3, number of rows = 4

Which is not equal, so solution is not optimal.

Step-5: Cover the zeros with minimum number of lines

(1)Mark(✓) row 4 since it has no assignment

(2)Mark(✓) column 1 since row 4 has zero in this column

(3)Mark(✓) row 2 since column 1 has an assignment in row 2.

(4)Mark(✓) column 3 since row 2 has zero in this column

(5) Since no other rows or columns can be marked, therefore draw straight lines through the
unmarked rows 1,3 and marked columns 1,3

Tick mark not allocated rows and allocated columns

1 2 3 4
1 M 5 [0]
2 [2] M 3 ✓
3 5 [0] M 4
4 3 4 M✓
✓ ✓

Step-6: Develop the new revised table by selecting the smallest element, among the cells not
covered by any line (say k = 3)
Subtract k = 3 from every element in the cell not covered by a line.
Add k = 3 to every element in the intersection cell of two lines.

61 | Page
oO

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

Repeat steps 3 to 6 until an optimal solution is obtained.

Step-3: Make assignment in the opportunity cost table

(1) Row wise cell (3,2) is assigned, so cell (1,2),(4,2) crossed off in this column.

(2) Row wise cell (4,1) is assigned, so cell (2,1) crossed off in this column.

(3) Column wise cell (2,3) is assigned, so cell (2,4) crossed off in this row.

(4) Column wise cell (1,4) is assigned

Rowwise & columnwise assignment shown in table

1 2 3 4
1 M 8 [0]
2 M [0]
3 8 [0] M 4
4 [0] 4 M

Step-4: Number of assignments = 4, number of rows = 4

The solution gives the sequence : 1→4,4→1

The above solution is not a solution to the travelling salesman problem as he visits each city only
once.

The next best solution can be obtained by bringing the minimum non-zero element, i.e., 4 into the
solution.
The cost 4 occurs at 2 places. We will consider all the cases separately until the acceptable
solution is obtained.

Case: 1 of 2 for minimum non-zero element 4

Make the assignment in the cell (3,4) and repeat Step-3.

62 | Page
 Operation Research

Step-3: Make assignment in the opportunity cost table

(1) Rowwise cell (3,4) is assigned, so cell (1,4),(2,4),(3,2) crossed off in this column.

(2) Rowwise cell (1,2) is assigned, so cell (4,2) crossed off in this column.

(3) Rowwise cell (2,3) is assigned, so cell (4,3) crossed off in this column.

(4) Rowwise cell (4,1) is assigned, so cell (2,1) crossed off in this column.

Rowwise & columnwise assignment shown in table

1 2 3 4
1 M [0] 8
2 M [0]
3 8 M [4]
4 [0] M

Step-4: Number of assignments = 4, number of rows = 4

The solution gives the sequence : 1→2,2→3,3→4,4→1
So solution is optimal
Optimal assignments are
1 2 3 4
1 M [0] 8
2 M [0]
3 8 M [4]
4 [0] M

Optimal solution is
Work Job Cost
1 2 4
2 3 4
3 4 9
4 1 5
Total 22

63 | Page