Transportation and Assignment Problems - Linear Programming - Mathematics Previous Year Questions

1

2008 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2008

Let \(c_{ij} \ge 2\) be the cost of the \((i, j)^{th}\) cell of an assignment problem. If a new cost matrix is generated by the elements \(c'_{ij} = \frac{1}{2} c_{ij} + 1\), then

A

optimal assignment plan remains unchanged and cost of assignment decreases

B

optimal assignment plan changes and cost of assignment decreases

C

optimal assignment plan remains unchanged and cost of assignment increases

D

optimal assignment plan changes and cost of assignment increases

Open complete paper

2

2008 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2008

The cost matrix of a transportation problem is given by \[\begin{tabular}{|c|c|c|c|}\] \hline 1 & 2 & 3 & 4 \\ \hline 4 & 3 & 2 & 0 \\ \hline 0 & 2 & 2 & 1 \\ \hline \end{tabular} The following are the values of variables in a feasible solution. \(x_{12} = 6, x_{23} = 2, x_{24} = 6, x_{31} = 4, x_{33} = 6\) Then which of the following is correct?

A

The solution is degenerate and basic

B

The solution is non-degenerate and basic

C

The solution is degenerate and non-basic

D

The solution is non-degenerate and non-basic

Open complete paper

3

2009 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2009

Using the Hungarian method, the optimal value of the assignment problem whose cost matrix is given by

5	23	14	8
10	25	1	23
35	16	15	12
16	23	11	7

is

A

29

B

52

C

26

D

44

Open complete paper

4

2010 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2010

The following table gives the cost matrix of a transportation problem

4	5	6
3	2	2
1	1	2

The basic feasible solution given by \( x_{11} = 3, x_{13} = 1, x_{21} = 6, x_{32} = 2, x_{33} = 5 \) is

A

degenerate and optimal

B

optimal but not degenerate

C

degenerate but not optimal

D

neither degenerate nor optimal

Open complete paper

5

2011 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2011

We have to assign four jobs I, II, III, IV to four workers A, B, C and D. The time taken by different workers (in hours) in completing different jobs is given below:

	I	II	III	IV
A	5	3	2	8
B	7	9	2	6
C	6	4	5	7
D	5	7	7	8

The optimal assignment is as follows:
Job III to worker A; Job IV to worker B; Job II to worker C and Job I to worker D and hence the time taken by different workers in completing different jobs is now changed as:

	I	II	III	IV
A	5	3	2	5
B	7	9	2	3
C	4	2	3	2
D	5	7	7	5

Then the minimum time (in hours) taken by the workers to complete all the jobs is

A

10

B

12

C

15

D

17

Open complete paper

6

2011 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2011

The following table shows the information on the availability of supply to each warehouse, the requirement of each market and unit transportation cost (in rupees) from each warehouse to each market.

	Market \( M_1 \)	Market \( M_2 \)	Market \( M_3 \)	Market \( M_4 \)	Supply
Warehouse \( W_1 \)	6	3	5	4	22
Warehouse \( W_2 \)	5	9	2	7	15
Warehouse \( W_3 \)	5	7	8	6	8
Requirement	7	12	17	9

The present transportation schedule is as follows:
\( W_1 \) to \( M_2 \): 12 units; \( W_1 \) to \( M_3 \): 1 unit; \( W_1 \) to \( M_4 \): 9 units; \( W_2 \) to \( M_3 \): 7 units and \( W_3 \) to \( M_3 \): 1 unit. Then the minimum total transportation cost (in rupees) is

A

150

B

149

C

148

D

147

Open complete paper

7

2011 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2011

The fuel consumed by a motorcycle during a journey while traveling at various speeds is indicated in the graph below.
The distances covered during four laps of the journey are listed in the table below

Lap	Distance (kilometres)	Average speed (kilometres per hour)
P	15	15
Q	75	45
R	40	75
S	10	10

From the given data, we can conclude that the fuel consumed per kilometre was least during the lap

A

P

B

Q

C

R

D

S

Open complete paper

8

2012 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2012

The following table gives the unit transportation costs, the supply at each origin and the demand of each destination for a transportation problem.

	Destination
	D1	D2	D3	D4	Supply
Origin	O1	3	4	8	7	60
	O2	7	3	7	6	80
	O3	3	9	3	4	100
Demand		40	70	50	80

Let \( x_{ij} \) denote the number of units to be transported from origin \( i \) to destination \( j \). If the u-v method is applied to improve the basic feasible solution given by \( x_{12} = 60, \; x_{23} = 10, \; x_{33} = 50, \; x_{24} = 20, \; x_{31} = 40 \) and \( x_{34} = 60 \), then the variables entering and leaving the basis, respectively, are

A

\(x_{11} \) and \(x_{24} \)

B

\(x_{13} \) and \(x_{23} \)

C

\(x_{14} \) and \(x_{24} \)

D

\(x_{33} \) and \(x_{24} \)

Open complete paper

9

2017 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2017

Consider the following transportation problem. The entries inside the cells denote per unit cost of transportation from the origins to the destinations.

	Destination
	1	2	3	Supply
Origin	4	3	6	20
	7	10	5	30
	8	9	7	50
	10	30	60
Demand

The optimal cost of transportation equals ______.

Check answer

Open complete paper

10

2018 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2018

A certain commodity is produced by the manufacturing plants \(P_1\) and \(P_2\) whose capacities are 6 and 5 units, respectively. The commodity is shipped to markets \(M_1, M_2, M_3\) and \(M_4\) whose requirements are 1, 2, 3 and 5 units, respectively. The transportation cost per unit from plant \(P_i\) to market \(M_j\) is as follows: \[ \[\begin{array}{c|cccc}\] & M_1 & M_2 & M_3 & M_4 \\ \hline P_1 & 1 & 3 & 5 & 6 \\ P_2 & 2 & 5 & 6 & 7 \\ \hline & 1 & 2 & 3 & 5 \end{array} \] Then the optimal cost of transportation is __________ .

Check answer

Open complete paper

11

2019 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2019

For a balanced transportation problem with three sources and three destinations where costs, availabilities and demands are all finite and positive, which one of the following statements is FALSE?

A

The transportation problem does not have unbounded solution

B

The number of non-basic variables of the transportation problem is 4

C

The dual variables of the transportation problem are unrestricted in sign

D

The transportation problem has at most 5 basic feasible solutions

Open complete paper

12

2019 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2019

Consider the following cost matrix of assigning four jobs to four persons:

	J1	J2	J3	J4
P1	5	8	6	10
P2	2	5	4	8
P3	6	7	6	9
P4	6	9	8	10

Then the minimum cost of the assignment problem subject to the constraint that job \(J_4\) is assigned to person \(P_2\), is ______.

Check answer

Open complete paper

13

2022 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2022

Three companies \(C_1, C_2\) and \(C_3\) submit bids for three jobs \(J_1, J_2\) and \(J_3\). The costs involved per unit are given in the table below:

	\(J_1\)	\(J_2\)	\(J_3\)
\(C_1\)	10	12	8
\(C_2\)	9	15	10
\(C_3\)	15	10	9

Then, the cost of the optimal assignment is __________

Check answer

Open complete paper

14

2022 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2022

A certain product is manufactured by plants \(P_1\), \(P_2\) and \(P_3\) whose capacities are 15, 25 and 10 units, respectively. The product is shipped to markets \(M_1\), \(M_2\), \(M_3\) and \(M_4\), whose requirements are 10, 10, 10 and 20, respectively. The transportation costs per unit are given in the table below.

	\(M_1\)	\(M_2\)	\(M_3\)	\(M_4\)
\(P_1\)	1	3	1	3	15
\(P_2\)	2	2	4	1	25
\(P_3\)	2	1	1	2	10
	10	10	10	20

Then the cost corresponding to the starting basic solution by the Northwest-corner method is __________.

Check answer

Open complete paper

15

2023 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2023

Consider the transportation problem between five sources and four destinations as given in the cost table below. The supply and demand at each of the source and destination are also provided:

SOURCES	DESTINATIONS				Supply
	P	Q	R	S
1	13	8	12	9	20
2	10	7	5	20	10
3	3	19	5	12	50
4	4	9	7	15	30
5	14	0	1	7	40
Demand	60	10	20	60

Let \(C_N\) and \(C_L\) be the total cost of the initial basic feasible solution obtained from the North-West corner method and the Least-Cost method, respectively. Then \(C_N - C_L\) equals ________.

Check answer

Open complete paper

16

2025 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2025

Consider the balanced transportation problem with three sources \(S_1, S_2, S_3\), and four destinations \(D_1, D_2, D_3, D_4\), for minimizing the total transportation cost whose cost matrix is as follows:

	\(D_1\)	\(D_2\)	\(D_3\)	\(D_4\)	Supply
\(S_1\)	2	6	20	11	\(\alpha + 10\)
\(S_2\)	12	7	4	10	\(\alpha + \lambda + 10\)
\(S_3\)	8	14	16	11	5
Demand	\(\alpha + 5\)	10	\(\lambda + 5\)	\(\alpha + \lambda\)

where \(\alpha, \lambda > 0\). If the associated cost to the starting basic feasible solution obtained by using the North-West corner rule is 290, then which of the following is/are correct?

A

\(\alpha^2 + \lambda^2 = 100\)

B

\(\alpha^2 + \alpha\lambda = 150\)

C

The optimal cost of the transportation problem is 260

D

The optimal cost of the transportation problem is 290

Check answer

Open complete paper

17

2007 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2007

Consider a transportation problem with two warehouses and two markets. The warehouse capacities are \(a_1 = 2\) and \(a_2 = 4\) and the market demands are \(b_1 = 3\) and \(b_2 = 3\). Let \(x_{ij}\) be the quantity shipped from warehouse \(i\) to market \(j\) and \(c_{ij}\) be the corresponding unit cost. Suppose that \(c_{11} = 1, c_{21} = 1\) and \(c_{22} = 2\). Then \((x_{11}, x_{12}, x_{21}, x_{22}) = (2, 0, 1, 3)\) is optimal for every

A

\(c_{12} \in [1, 2]\)

B

\(c_{12} \in [0, 3]\)

C

\(c_{12} \in [1, 3]\)

D

\(c_{12} \in [2, 4]\)

Open complete paper

18

2026 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2026

Consider the following assignment problem where \(X, Y, Z\) are tasks, \(P, Q, R\) are agents and the cost matrix is given by

	\(X\)	\(Y\)	\(Z\)
\(P\)	4	2	8
\(Q\)	2	3	7
\(R\)	3	1	6

Which of the following statements is/are TRUE for an optimal assignment?

A

The cost is 9.

B

Agent \(P\) is assigned to task \(Y\).

C

Agent \(Q\) is assigned to task \(X\).

D

Agent \(R\) is assigned to task \(Y\).

Check answer

Open complete paper

19

2026 · Mathematics · Linear Programming · Transportation and Assignment Problems

Mathematics (MA) 2026

For a transportation problem, let \(c_{ij}\) denote the unit cost of the cell \((i,j)\). Assume that \(c_{11} = 10\), \(c_{12} = 12\), \(c_{21} = 11\) and \(c_{22} = 13\). Let \(\alpha_i\) and \(\beta_j\), \(i,j = 1,2,3\), represent the simplex multipliers associated with any basis corresponding to the unit cost \(c_{ij}\). Assume that \(\alpha_1 = x\), \(\alpha_2 = x + 1\), \(\beta_1 = y\) and \(\beta_2 = y + 2\). The relative cost coefficient \(d_{ij}\) is the difference between the current solution and the new improved solution. If \(x = 4\), \(c_{13} = 19\) and \(\beta_3 = y + 5\), then which one of the following is TRUE?

A

\(y = 6\) and \(d_{13} = 7\)

B

\(y = 6\) and \(d_{13} = 4\)

C

\(y = 5\) and \(d_{13} = 7\)

D

\(y = 5\) and \(d_{13} = 4\)

Open complete paper