A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins)

Question

A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins) and the towers(destinations) where the customers are given in the following distance matrix.

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105

How should the cars be assigned to the customers so as to minimize the distance travelled?

Chart

Sum

Solution

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced.

Step 1: Select the smallest element in each row and subtract this from all the elements in its row.

		Depots
		a	b	c	d	e
	A	30	0	45	60	70
	B	15	0	10	40	55
Customers	C	30	0	45	60	75
	D	0	0	30	30	60
	E	20	0	35	45	70

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	20
	D	0	0	20	0	5
	E	20	0	25	15	15

Step 3: (Assignment)
Examine the rows with exactly one zero, mark the zero by □ mark other zeros, in its column by X

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	20
	D	0	0	20	0	5
	E	20	0	25	15	15

Step 4: Now Examine the rows with exactly one zero, mark the zero by □ mark other zeros, in its column by X

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	20
	D	0	0	20	0	5
	E	20	0	25	15	15

Step 5: Cover all the zeros of table 4 with three lives.

Since three assignments were made please note that check [✓] Row C and E which have no assignment.

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C✓	30	0	35	30	20
	D	0	0	20	0	5
	E✓	20	0	25	15	15

Step 6: Develop the new revised tableau. Examine those elements that are not covered by a line in Table 5.

Take the smallest element in each row and subtract from the uncovered cells, depots

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	0
	D	0	0	20	0	5
	E	20	0	25	0	0

Step 7: Go to step 3 and repeat the procedure until you arrive at an optimal assignments depots

Step 8: Determine an assignment

		Depots
		a	b	c	d	e
	A	30	0	35	30	15
	B	15	0	0	10	0
Customers	C	30	0	35	30	0
	D	0	0	20	0	5
	E	20	0	25	0	0

Here all the five assignments have been made.

The optimal assignment schedule and total distance is

Customers	Depots	Total Distances
A	b	130
B	c	130
C	e	185
D	a	50
E	d	80
Total		575

∴ The optimum Distance (minimum) is 575 kms.

shaalaa.com

Assignment Problem

Is there an error in this question or solution?

Q 5 Q 4 Q 6

Chapter 10: Operations Research - Miscellaneous problems [Page 262]

APPEARS IN

Samacheer Kalvi Business Mathematics and Statistics [English] Class 12 TN Board

Chapter 10 Operations Research
Miscellaneous problems | Q 5 | Page 262

RELATED QUESTIONS

Five wagons are available at stations 1, 2, 3, 4, and 5. These are required at 5 stations I, II, III, IV, and V. The mileage between various stations are given in the table below. How should the wagons be transported so as to minimize the mileage covered?

	I	II	III	IV	V
1	10	5	9	18	11
2	13	9	6	12	14
3	3	2	4	4	5
4	18	9	12	17	15
5	11	6	14	19	10

Choose the correct alternative :

The assignment problem is said to be balanced if it is a ______.

Fill in the blank :

When an assignment problem has more than one solution, then it is _______ optimal solution.

Solve the following problem :

A dairy plant has five milk tankers, I, II, III, IV and V. These milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.

	I	II	III	IV	V
A	150	120	175	180	200
B	125	110	120	150	165
C	130	100	145	160	175
D	40	40	70	70	100
E	45	25	60	70	95

How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?

State whether the following statement is True or False:

In assignment problem, if number of columns is greater than number of rows, then a dummy row is added

Give mathematical form of Assignment problem

A computer centre has got three expert programmers. The centre needs three application programmes to be developed. The head of the computer centre, after studying carefully the programmes to be developed, estimates the computer time in minitues required by the experts to the application programme as follows.

	Programmers
		P	Q	R
Programmers	1	120	100	80
	2	80	90	110
	3	110	140	120

Assign the programmers to the programme in such a way that the total computer time is least.

Choose the correct alternative:

Number of basic allocation in any row or column in an assignment problem can be

A natural truck-rental service has a surplus of one truck in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one truck in each of the cities 7, 8, 9, 10, 11 and 12. The distance(in kilometers) between the cities with a surplus and the cities with a deficit are displayed below:

		To
		7	8	9	10	11	12
From	1	31	62	29	42	15	41
	2	12	19	39	55	71	40
	3	17	29	50	41	22	22
	4	35	40	38	42	27	33
	5	19	30	29	16	20	33
	6	72	30	30	50	41	20

How should the truck be dispersed so as to minimize the total distance travelled?

A job production unit has four jobs P, Q, R, S which can be manufactured on each of the four machines I, II, III and IV. The processing cost of each job for each machine is given in the following table :

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	31	25	33	29
Q	25	24	23	21
R	19	21	23	24
S	38	36	34	40

Complete the following activity to find the optimal assignment to minimize the total processing cost.

Solution:

Step 1: Subtract the smallest element in each row from every element of it. New assignment matrix is obtained as follows :

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	6	0	8	4
Q	4	3	2	0
R	0	2	4	5
S	4	2	0	6

Step 2: Subtract the smallest element in each column from every element of it. New assignment matrix is obtained as above, because each column in it contains one zero.

Step 3: Draw minimum number of vertical and horizontal lines to cover all zeros:

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	6	0	8	4
Q	4	3	2	0
R	0	2	4	5
S	4	2	0	6

Step 4: From step 3, as the minimum number of straight lines required to cover all zeros in the assignment matrix equals the number of rows/columns. Optimal solution has reached.

Examine the rows one by one starting with the first row with exactly one zero is found. Mark the zero by enclosing it in (`square`), indicating assignment of the job. Cross all the zeros in the same column. This step is shown in the following table :

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	6	0	8	4
Q	4	3	2	0
R	0	2	4	5
S	4	2	0	6

Step 5: It is observed that all the zeros are assigned and each row and each column contains exactly one assignment. Hence, the optimal (minimum) assignment schedule is :

Job	Machine	Min.cost
P	II	`square`
Q	`square`	21
R	I	`square`
S	III	34

Hence, total (minimum) processing cost = 25 + 21 + 19 + 34 = ₹`square`

A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins)

Advertisements

Advertisements

Question

Advertisements

Solution

APPEARS IN

RELATED QUESTIONS

Select a course

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105

A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins)

Advertisements

Advertisements

Question

Advertisements

SolutionShow Solution

APPEARS IN

RELATED QUESTIONS

Select a course

Solution

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105