Maharashtra Board Class 12 Maths Part 2 Chapter 7 Miscellaneous 7 Solutions

Std 12 Maths 2 Miscellaneous Exercise 7 Solutions Commerce Maths

(I) Choose The Correct Alternative.

Question 1.In sequencing, an optimal path is one that minimizes __________
(a) Elapsed time
(b) Idle time
(c) Both (a) and (b)
(d) Ready time
Answer: (c) Both (a) and (b)
In simple words: An optimal path in sequencing aims to reduce both the total time taken to complete all tasks (elapsed time) and the time machines or resources spend waiting (idle time) for tasks to arrive.

🎯 Exam Tip: Understanding the objectives of sequencing problems, such as minimizing total elapsed time and idle time, is crucial for solving real-world production scheduling challenges effectively.

Question 2.If job A to D have processing times as 5, 6, 8, 4 on first machine and 4, 7, 9, 10 on second machine then the optimal sequence is:
(a) CDAB
(b) DBCA
(c) BCDA
(d) ABCD
Answer: (b) DBCA
In simple words: For a 2-machine, n-job sequencing problem, the optimal sequence minimizes the total elapsed time. This sequence is determined using methods like Johnson's algorithm, which helps arrange jobs efficiently.

🎯 Exam Tip: Johnson's algorithm is key for 2-machine sequencing problems. Remember to identify the smallest processing time and place the job accordingly at the beginning (for machine 1) or end (for machine 2) of the sequence.

Question 3.The objective of sequence problem is
(a) to find the order in which jobs are to be made
(b) to find the time required for the completing all the job on hand
(c) to find the sequence in which jobs on hand are to be processed to minimize the total time required for processing the jobs
(d) to maximize the cost
Answer: (c) to find the sequence in which jobs on hand are to be processed to minimize the total time required for processing the jobs
In simple words: The main goal of a sequencing problem is to arrange tasks in an order that achieves the most efficient outcome, typically by minimizing the overall time it takes to finish all jobs.

🎯 Exam Tip: Always identify the primary objective of a sequencing problem, which is almost always about minimizing some time-related factor (total elapsed time, idle time, etc.) rather than maximizing or just finding an order.

Question 4.If there are n jobs and m machines, then there will be __________ sequences of doing the jobs.
(a) mn
(b) m(n!)
(c) n^m
(d) (n!)^m
Answer: (d) (n!)^m
In simple words: For `n` jobs processed on `m` machines, where each job must go through each machine, the total number of possible sequences is calculated by `(n!)^m` because each job can be arranged in `n!` ways and this process is repeated across `m` machines.

🎯 Exam Tip: Remember this formula for calculating the total possible sequences. It highlights the complexity of scheduling as the number of jobs and machines increases.

Question 5.The Assignment Problem is solved by
(a) Simple method
(b) Hungarian method
(c) Vector method
(d) Graphical method
Answer: (b) Hungarian method
In simple words: The Hungarian method is a specialized and efficient algorithm used to find the optimal assignment of tasks to resources, minimizing total cost or maximizing total profit.

🎯 Exam Tip: The Hungarian method is the standard algorithm for solving assignment problems. Knowing its name and core purpose is essential.

Question 6.In solving 2 machine and n jobs sequencing problem, the following assumption is wrong
(a) No passing is allowed
(b) Processing times are known
(c) Handling times is negligible
(d) The time of passing depends on the order of machining
Answer: (d) The time of passing depends on the order of machining
In simple words: In most basic sequencing models, it is assumed that job processing times are fixed and independent of the order, and there are no delays or variations in the transfer of a job between machines.

🎯 Exam Tip: Be familiar with the key assumptions of sequencing problems, such as no passing of jobs, known processing times, and negligible handling/transfer times, as these simplify the problem for standard algorithms.

Question 7.To use the Hungarian method, a profit maximization assignments problem requires
(a) Converting all profit to opportunity losses
(b) A dummy person or job
(c) Matrix expansion
(d) Finding the maximum number of lines to cover all the zeros in the reduced matrix
Answer: (a) Converting all profit to opportunity losses
In simple words: For maximization problems using the Hungarian method, you must first transform the profit matrix into an opportunity loss matrix by subtracting all elements from the highest profit value in the matrix. This converts the problem into an equivalent minimization problem.

🎯 Exam Tip: For maximization problems in assignment, the crucial first step is to convert them into minimization problems by creating an opportunity loss matrix. This is done by subtracting each element from the largest element in the original profit matrix.

Question 8.Using the Hungarian method the optimal assignment obtained for the following assignment problem to minimize the total cost is:
ℹ️ चित्र व्याख्या (Diagram Explanation): यह एक लागत मैट्रिक्स है जिसमें चार एजेंट (1, 2, 3, 4) और चार कार्य (A, B, C, D) दिए गए हैं। मैट्रिक्स में प्रत्येक सेल एक विशिष्ट एजेंट द्वारा एक विशिष्ट कार्य को पूरा करने की लागत को दर्शाता है। इस मैट्रिक्स का उपयोग हंगेरियन विधि द्वारा कार्यों को एजेंटों को इस तरह से असाइन करने के लिए किया जाएगा जिससे कुल लागत न्यूनतम हो।

Agent	A	B	C	D
1	10	12	15	25
2	14	11	19	32
3	18	21	23	29
4	15	20	26	28

(a) 1 - C, 2 - B, 3 - D, 4 - A
(b) 1 - B, 2 - C, 3 - A, 4 - D
(c) 1 - A, 2 - B, 3 - C, 4 - D
(d) 1 - D, 2 - A, 3 - B, 4 - C
Answer: (a) 1 - C, 2 - B, 3 - D, 4 - A
In simple words: The Hungarian method is applied to the given cost matrix to find the assignment of agents to tasks that results in the lowest total cost, yielding the optimal pairing of 1 to C, 2 to B, 3 to D, and 4 to A.

🎯 Exam Tip: For assignment problems with a given cost matrix, apply the Hungarian method (row reduction, column reduction, covering zeros, creating assignments) carefully to derive the optimal assignment that minimizes total cost.

Question 9.The assignment problem is said to be unbalanced if
(a) Number of rows is greater than the number of columns
(b) Number of rows is lesser than number of columns
(c) Number of rows is equal to the number of columns
(d) Both (a) and (b)
Answer: (d) Both (a) and (b)
In simple words: An assignment problem is considered unbalanced when the number of available tasks (columns) does not match the number of available resources or persons (rows), meaning the cost matrix is not square.

🎯 Exam Tip: An unbalanced assignment problem requires adding dummy rows or columns with zero costs to make the cost matrix square before applying the Hungarian method.

Question 10.The assignment problem is said to be balanced if
(a) Number of rows is greater than the number of columns
(b) Number of rows is lesser than number of columns
(c) Number of rows is equal to the number of columns
(d) If the entry of rows is zero
Answer: (c) Number of rows is equal to number of columns
In simple words: A balanced assignment problem is one where the number of tasks to be assigned is exactly equal to the number of assignees (e.g., jobs to machines, or people to tasks).

🎯 Exam Tip: A balanced assignment problem is characterized by a square cost matrix, which is a prerequisite for directly applying the Hungarian method.

Question 11.The assignment problem is said to be balanced if it is a
(a) Square matrix
(b) Rectangular matrix
(c) Unit matrix
(d) Triangular matrix
Answer: (a) Square matrix
In simple words: A balanced assignment problem is represented by a square matrix, where the number of rows (e.g., persons) is equal to the number of columns (e.g., tasks).

🎯 Exam Tip: The term "balanced" in assignment problems directly implies that the underlying cost or profit matrix is square, meaning equal rows and columns.

Question 12.In an assignment problem if the number of rows is greater than the number of columns then
(a) Dummy column is added
(b) Dummy row is added
(c) Row with cost 1 is added
(d) Column with cost 1 is added
Answer: (a) Dummy column is added
In simple words: If there are more tasks or resources (rows) than assignments available (columns), a dummy column is introduced to balance the matrix, typically with zero costs.

🎯 Exam Tip: To balance an assignment problem, if rows > columns, add dummy columns; if columns > rows, add dummy rows. Dummy entries always have zero cost (for minimization) or zero profit (for maximization after conversion).

Question 13.In a 3 machine and 5 jobs problem, the least of processing times on machines A, B, and C are 5, 1 and 3 hours and the highest processing times are 9, 5 and 7 respectively, then it can be converted to a 2 machine problem if the order of the machines is:
(a) B - A - C
(b) A - B - C
(c) C - B - A
(d) Any order
Answer: (b) A - B - C
In simple words: A 3-machine, n-job sequencing problem can be simplified into a 2-machine problem if the minimum processing time on the first machine (A) is greater than or equal to the maximum processing time on the middle machine (B), OR if the minimum processing time on the last machine (C) is greater than or equal to the maximum processing time on the middle machine (B). In this case, `min(A) = 5`, `max(B) = 5`, and `min(C) = 3`. Since `min(A) ≥ max(B)` (5 ≥ 5), the condition is met for sequence A-B-C.

🎯 Exam Tip: For converting a 3-machine to a 2-machine problem, recall Johnson's rule extension: `min(Machine 1) ≥ max(Machine 2)` OR `min(Machine 3) ≥ max(Machine 2)`. If either condition holds, the conversion is possible.

Question 14.The objective of an assignment problem is to assign
(a) Number of jobs to equal number of persons at maximum cost
(b) Number of jobs to equal number of persons at minimum cost
(c) Only the maximize cost
(d) Only to minimize cost
Answer: (b) Number of jobs to equal number of persons at minimum cost
In simple words: The primary goal of an assignment problem is to match each task to a unique resource (person or machine) in a way that minimizes the total cost or time involved.

🎯 Exam Tip: Unless explicitly stated as a maximization problem, assume the objective of an assignment problem is to minimize the total cost, time, or distance.

(II) Fill In The Blanks.

Question 1.An assignment problem is said to be unbalanced when __________
Answer: the number of rows is not equal to the number of columns
In simple words: An assignment problem is considered unbalanced if the number of rows and columns in its cost matrix are not equal.

🎯 Exam Tip: An unbalanced problem always requires the addition of dummy rows or columns to make it square before solving.

Question 2.When the number of rows is equal to the Number of columns then the problem is said to be __________ assignment problem.
Answer: balanced
In simple words: An assignment problem is called balanced when the number of items or resources to be assigned is exactly equal to the number of available tasks, resulting in a square matrix.

🎯 Exam Tip: A balanced problem has a square matrix, which means the Hungarian method can be applied directly without adding dummy elements.

Question 3.For solving assignment problem the matrix should be a __________
Answer: square matrix
In simple words: The Hungarian method, used to solve assignment problems, requires the input matrix to be square, meaning an equal number of rows and columns.

🎯 Exam Tip: Always ensure your assignment matrix is square before applying the core steps of the Hungarian method; add dummy rows or columns if necessary.

Question 4.If the given matrix is not a __________ matrix, the assignment problem is called an unbalanced problem.
Answer: square
In simple words: If the cost matrix in an assignment problem is not square (i.e., rows ≠ columns), the problem is classified as unbalanced.

🎯 Exam Tip: Recognizing an unbalanced matrix is the first step; balancing it by adding dummy rows/columns is necessary to proceed with the solution.

Question 5.A dummy row(s) or column(s) with the cost elements as __________ the matrix of an unbalanced assignment problem as a square matrix.
Answer: zero
In simple words: When balancing an assignment problem, dummy rows or columns are added, and their corresponding cost elements are set to zero to ensure they don't affect the optimal solution.

🎯 Exam Tip: Dummy costs are typically zero in minimization problems to ensure they do not influence the selection of actual assignments.

Question 6.The time interval between starting the first job and completing the last, job including the idle time (if any) in a particular order by the given set of machines is called __________
Answer: Total elapsed time
In simple words: Total elapsed time refers to the overall time taken from the start of the first job on the first machine to the completion of the last job on the last machine, including any idle time in between.

🎯 Exam Tip: Minimizing total elapsed time is a common objective in sequencing problems, as it represents the efficiency of the entire production schedule.

Question 7.The time for which a machine j does not have a job to process to the start of job i is called __________
Answer: Idle time
In simple words: Idle time is the period during which a machine remains unoccupied, waiting for a job to be transferred or processed by a preceding machine.

🎯 Exam Tip: Calculating and minimizing idle time for each machine is an important aspect of optimizing sequencing problems, as it indicates resource utilization efficiency.

Question 8.The maximization assignment problem is transformed to minimization problem by subtracting each entry in the table from the __________ value in the table.
Answer: maximum
In simple words: To solve a maximization assignment problem using the Hungarian method, you must convert it into a minimization problem by subtracting every element from the highest value present in the entire matrix.

🎯 Exam Tip: Remember that for a maximization problem, you subtract all elements from the *largest* element in the matrix to create an opportunity loss matrix for minimization.

Question 9.When the assignment problem has more than one solution, then it is __________ optimal solution.
Answer: multiple
In simple words: If an assignment problem can yield several different task-to-resource pairings that all result in the same minimum total cost (or maximum total profit), it is said to have multiple optimal solutions.

🎯 Exam Tip: Multiple optimal solutions mean there are different assignment patterns that achieve the same best outcome. Any of these solutions is acceptable.

Question 10.The time required for printing four books A, B, C, and D is 5, 8, 10, and 7 hours. While its data entry requires 7, 4, 3, and 6 hrs respectively. The sequence that minimizes total elapsed time is __________
Answer: A-D-B-C
In simple words: Using Johnson's algorithm for two machines (printing and data entry), the optimal sequence for these books to minimize total elapsed time is A-D-B-C.

🎯 Exam Tip: For problems involving two stages of processing for multiple jobs, apply Johnson's rule by comparing processing times on the first and second machines to determine the optimal sequence.

(III) State Whether Each Of The Following Is True Or False.

Question 1.One machine – one job is not an assumption in solving sequencing problems.
Answer: False
In simple words: A fundamental assumption in most sequencing problems is that each machine can process only one job at a time, and each job requires only one machine at a time.

🎯 Exam Tip: A key assumption in sequencing is that machines can handle only one job at a time, simplifying the scheduling process and avoiding parallel processing complications on a single machine.

Question 2.If there are two least processing times for machine A and machine B, priority is given for the processing time which has the lowest time of the adjacent machine.
Answer: True
In simple words: When breaking a tie for the smallest processing time in Johnson's algorithm, if both Machine A and Machine B have the same minimum, the job associated with the smaller processing time on its *other* machine determines priority.

🎯 Exam Tip: Tie-breaking rules in Johnson's algorithm ensure a unique optimal sequence. Prioritize the job that minimizes the time on the *next* machine if ties occur on the first machine, or the *previous* machine if ties occur on the last machine.

Question 3.To convert the assignment problem into a maximization problem, the smallest element in the matrix is deducted from all other elements.
Answer: False
In simple words: To convert a maximization problem into a minimization one, all elements in the matrix are subtracted from the *largest* element in the matrix, not the smallest.

🎯 Exam Tip: The correct way to convert a maximization problem is to subtract all entries from the *highest* value in the matrix, creating an opportunity loss matrix which is then solved as a minimization problem.

Question 4.The Hungarian method operates on the principle of matrix reduction, whereby the cost table is reduced to a set of opportunity costs.
Answer: True
In simple words: The Hungarian method works by transforming the original cost matrix through row and column operations to create opportunity costs, aiming to identify optimal assignments where these costs are zero.

🎯 Exam Tip: The essence of the Hungarian method lies in reducing the cost matrix to reveal opportunity costs, making it easier to identify optimal assignments (zeros).

Question 5.In a sequencing problem, the processing times are dependent on the order of processing the jobs on machines.
Answer: False
In simple words: A standard assumption in basic sequencing problems is that the time it takes to process a job on a machine is fixed and does not change based on when that job is scheduled or what other jobs are processed around it.

🎯 Exam Tip: Always remember that processing times are considered independent of the job sequence in typical sequencing problem assumptions.

Question 6.The optimal assignment is made in the Hungarian method to cells in the reduced matrix that contain a Zero.
Answer: True
In simple words: In the Hungarian method, after reducing the matrix, optimal assignments are made by selecting cells that contain a zero, as these represent tasks that can be performed without any opportunity cost.

🎯 Exam Tip: The goal of the Hungarian method is to generate enough zeros in the reduced matrix to allow for an assignment without any opportunity cost, which signifies an optimal solution.

Question 7.Using the Hungarian method, the optimal solution to an assignment problem is fund when the minimum number of lines required to cover the zero cells in the reduced matrix equals the number of people.
Answer: True
In simple words: The condition for an optimal solution in the Hungarian method is met when the smallest number of horizontal or vertical lines needed to cover all the zeros in the reduced matrix is equal to the order (number of rows or columns) of the matrix.

🎯 Exam Tip: This statement describes the core condition for optimality in the Hungarian method (König's theorem). If the number of lines is less than the matrix order, further matrix modification is required.

Question 8.In an assignment problem, if a number of columns are greater than the number of rows, then a dummy column is added.
Answer: False
In simple words: If the number of columns (tasks) is greater than the number of rows (resources), a dummy *row* is added to balance the matrix, not a dummy column.

🎯 Exam Tip: To balance an assignment matrix, add dummy rows if there are more columns than rows, and dummy columns if there are more rows than columns. Always aim for a square matrix.

Question 9.The purpose of a dummy row or column in an assignment problem is to obtain a balance between a total number of activities and a total number of resources.
Answer: True
In simple words: Dummy rows or columns are added to an unbalanced assignment problem to create a square matrix, ensuring that the number of tasks matches the number of resources, which is necessary for applying the Hungarian method.

🎯 Exam Tip: Dummy elements serve to balance the problem, making it solvable by the Hungarian method, and represent unassigned resources or unperformed tasks with zero cost.

Question 10.One of the assumptions made while sequencing n jobs on 2 machines is: two jobs must be loaded at a time on any machine.
Answer: False
In simple words: A fundamental assumption in sequencing problems is that each machine can process only one job at a time, ensuring serial processing rather than parallel processing on a single machine.

🎯 Exam Tip: Remember the "one job at a time" rule for machines in sequencing problems, as it's a basic simplifying assumption.

(IV) Solve The Following Problems.

Part - I

Question 1.A plant manager has four subordinates, and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. This estimate of the times each man would take to perform each task is given in the effectiveness matrix below.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह एक प्रभावशीलता मैट्रिक्स है जो चार अधीनस्थ कर्मचारियों (A, B, C, D) और चार कार्यों (I, II, III, IV) के लिए लगने वाले समय को दर्शाता है। मैट्रिक्स में प्रत्येक सेल एक विशिष्ट अधीनस्थ द्वारा एक विशिष्ट कार्य को पूरा करने के लिए आवश्यक घंटों की संख्या को इंगित करता है। इस मैट्रिक्स का उपयोग हंगेरियन विधि द्वारा कार्यों को अधीनस्थ कर्मचारियों को इस तरह से असाइन करने के लिए किया जाएगा जिससे कुल मानव-घंटे न्यूनतम हों।

	I	II	III	IV
A	7	25	26	10
B	12	27	3	25
C	37	18	17	14
D	18	25	23	9

How should the tasks be allocated, one to a man, as to minimize the total man-hours?
Solution:
The hr matrix is given by

	I	II	III	IV
A	7	25	26	10
B	12	27	3	25
C	37	18	17	14
D	18	25	23	9

Subtracting row minimum from all values in that row we get

	I	II	III	IV
A	0	18	19	3
B	9	24	0	22
C	23	4	3	0
D	9	16	14	0

Subtracting column minimum from all values in that column we get

	I	II	III	IV
A	0	14	19	3
B	9	20	0	22
C	23	0	3	0
D	9	12	14	0

The minimum no. of lines covering ail the zeros (4) is equal to the order of the matrix (4)
.·. The assignment is possible.

	I	II	III	IV
A	0	14	19	3
B	9	20	0	22
C	23	0	3	X
D	9	12	14	0

The assignment is
A → I, B → III, C → II, D → IV
For the minimum hrs. take the corresponding value from the hr matrix.
Minimum hrs = 7 + 3 + 18 + 9 = 37 hrs
In simple words: By applying the Hungarian method (row and column reductions to find zeros, and then assigning tasks to minimize total hours), the optimal assignment is found as A to task I, B to task III, C to task II, and D to task IV, resulting in a minimum total of 37 man-hours.

🎯 Exam Tip: When performing assignments, make sure to cross-check the final assigned values with the original cost (or time) matrix to calculate the total minimum value accurately.

Question 2.A dairy plant has five milk tankers, I, II, III, IV & V. These milk tankers are to be used on five delivery routes A, B, C, D & E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.
ℹ️ चित्र व्याख्या (Diagram Explanation): यह एक दूरी मैट्रिक्स है जिसमें पांच दूध टैंकरों (I, II, III, IV, V) और पांच डिलीवरी मार्गों (A, B, C, D, E) के बीच की दूरी (किमी में) दर्शाई गई है। मैट्रिक्स में प्रत्येक सेल एक विशिष्ट टैंकर द्वारा एक विशिष्ट मार्ग पर जाने में लगने वाली दूरी को इंगित करता है। इस मैट्रिक्स का उपयोग हंगेरियन विधि द्वारा टैंकरों को मार्गों पर इस तरह से असाइन करने के लिए किया जाएगा जिससे तय की गई कुल दूरी न्यूनतम हो।

	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 centre so as to minimize the distance travelled?
Solution:
The distance matrix is given by

	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

Subtracting row minimum from all values in that row we get

	I	II	III	IV	V
A	30	0	55	60	80
B	15	0	10	40	55
C	30	0	45	60	75
D	0	0	30	30	60
E	20	0	35	45	70

Subtracting column minimum from each value in that column we get

	I	II	III	IV	V
A	30	0	45	30	25
B	15	0	0	10	0
C	30	0	35	30	20
D	0	0	20	0	5
E	20	0	25	15	15

The number of lines covering all the zeros (3) is less than the order of the matrix (5) so the assignment is not possible. The modification is required.
The minimum uncovered value (15) is subtracted from uncovered values and added to the values at the intersection. The numbers on the lines remain the same. We get

	I	II	III	IV	V
A	15	0	30	15	10
B	15	15	0	10	0
C	15	0	20	15	5
D	0	15	20	0	5
E	5	0	10	0	0

The minimum lines covering all the zeros (4) are less than the order of the matrix (5) so the assignment is not possible. The modification is required the minimum uncovered value (5) is subtracted from uncovered values and added to the values at the intersection. The numbers on the lines remain the same we get

	I	II	III	IV	V
A	10	0	25	10	X
B	15	25	0	10	X
C	10	X	15	10	0
D	0	20	20	X	5
E	5	5	10	0	X

The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) So assignment is possible.
The assignment is
A → II, B → III, C → V, D → I, E → IV
Total minimum distance is = 120 + 120 + 175 + 40 + 70 = 525 kms.
In simple words: By repeatedly applying row/column reductions and matrix modifications until an optimal assignment can be made (where 5 lines cover 5 zeros), the lowest total distance of 525 kms is achieved by assigning tanker A to route II, B to III, C to V, D to I, and E to IV.

🎯 Exam Tip: For large matrices, carefully track modifications, especially adding/subtracting values at intersections and uncovered cells. Ensure the number of covering lines equals the matrix order for optimality.

Question 3.Solve the following assignment problem to maximize sales:
ℹ️ चित्र व्याख्या (Diagram Explanation): यह एक बिक्री मैट्रिक्स है जो चार सेल्समैन (A, B, C, D) और पांच क्षेत्रों (I, II, III, IV, V) में अनुमानित बिक्री को दर्शाता है। मैट्रिक्स में प्रत्येक सेल एक विशिष्ट सेल्समैन द्वारा एक विशिष्ट क्षेत्र में की गई बिक्री का मूल्य इंगित करता है। यह एक अधिकतमकरण समस्या है, जिसे हंगेरियन विधि का उपयोग करके हल करने के लिए न्यूनतमकरण समस्या में परिवर्तित किया जाएगा, ताकि अधिकतम कुल बिक्री प्राप्त की जा सके।

Salesmen	I	II	III	IV	V
A	11	16	18	15	15
B	7	19	11	13	17
C	9	6	14	14	7
D	13	12	17	11	13

Solution:
As it is a maximization problem so we need to convert it into a minimization problem.
Subtracting all the values from the maximum value (19) we get

	I	II	III	IV	V
A	8	3	1	4	4
B	12	0	8	6	2
C	10	13	5	5	12
D	6	7	2	8	6

Also, it is an unbalanced problem so we need to add a dummy row (E) with all values zero, we get

	I	II	III	IV	V
A	8	3	1	4	4
B	12	0	8	6	2
C	10	13	5	5	12
D	6	7	2	8	6
E	0	0	0	0	0

Subtracting row minimum from all values in that row we get

	I	II	III	IV	V
A	7	2	0	3	3
B	12	0	8	6	2
C	5	8	0	0	7
D	6	5	0	6	4
E	0	0	0	0	0

Subtracting column minimum from all values in that column we get the same matrix

	I	II	III	IV	V
A	7	2	0	3	3
B	12	0	8	6	2
C	5	8	0	0	7
D	4	3	0	6	4
E	0	0	0	0	0

The minimum number of lines covering all the zero (4) is less than the order of the matrix (5) So assignment is not possible. The modification is required. The minimum uncovered value (2) is subtracted from the uncovered values and added to the values at the intersection. The values on the lines remain the same. We get

	I	II	III	IV	V
A	5	2	0	1	1
B	10	0	8	4	0
C	5	10	2	0	7
D	2	5	0	4	2
E	0	2	0	0	0

The minimum number of lines covering all the zeros (4) is less than the order of the matrix (5) so the assignment is not possible. The modification is required. The minimum uncovered value (1) is subtracted from the uncovered value and added to the values at the intersection. The values on the lines remain the same. We get

	I	II	III	IV	V
A	4	1	0	0	0
B	10	0	9	4	0
C	5	10	3	0	7
D	1	4	0	3	1
E	0	2	0	0	0

The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) so the assignment is possible.

	I	II	III	IV	V
A	4	1	X	0	X
B	10	0	9	4	X
C	5	10	3	0	7
D	1	4	0	3	1
E	0	2	3	X	X

The assignment is
A → IV, B → II, C → V, D → III, E → I
No salesman goes to I as E is a dummy row.
For the maximum value take the corresponding values from the original matrix.
We get Maximum value = 15 + 19 + 14 + 17 + 0 = 65 units
In simple words: This maximization problem was converted to a minimization problem by creating an opportunity loss matrix, then balanced with a dummy row. After applying the Hungarian method and making necessary matrix modifications, the optimal assignment is A to IV, B to II, C to V, D to III, and E to I (dummy). This yields a maximum sales value of 65 units.

🎯 Exam Tip: When solving maximization problems, remember the initial conversion to an opportunity loss matrix is critical. Also, ensure you refer back to the *original* matrix values to calculate the final maximum profit/sales.

Question 4.The estimated sales (tons) per month in four different cities by five different managers are given below:
ℹ️ चित्र व्याख्या (Diagram Explanation): यह एक बिक्री मैट्रिक्स है जो पांच प्रबंधकों (I, II, III, IV, V) और चार शहरों (P, Q, R, S) में प्रति माह अनुमानित बिक्री (टन में) को दर्शाता है। मैट्रिक्स में प्रत्येक सेल एक विशिष्ट प्रबंधक द्वारा एक विशिष्ट शहर में की गई बिक्री को इंगित करता है। यह एक अधिकतमकरण समस्या है जिसे न्यूनतमकरण समस्या में परिवर्तित किया जाएगा और फिर हंगेरियन विधि का उपयोग करके हल किया जाएगा ताकि प्रबंधकों को शहरों में इस तरह से असाइन किया जा सके जिससे कुल बिक्री अधिकतम हो।

Manager	P	Q	R	S
I	34	36	33	35
II	33	35	31	33
III	37	39	35	35
IV	36	36	34	34
V	35	36	35	33

Find out the assignment of managers to cities in order to maximize sales.
Solution:
This is a maximizing problem. To convert it into minimizing problem subtract all the values of the matrix from the maximum (largest) value (39) we get

	P	Q	R	S
I	5	3	6	4
II	6	4	8	6
III	2	0	4	4
IV	3	3	5	5
V	4	3	4	6

Also as it is an unbalanced problem so we have to add a dummy column (T) with all the values as zero. We get

	P	Q	R	S	T
I	5	3	6	4	0
II	6	4	8	6	0
III	2	0	4	4	0
IV	3	3	5	5	0
V	4	3	4	6	0

Subtracting row minimum from all values in that row we get the same matrix Subtracting column minimum from all values in that column we get

	P	Q	R	S	T
I	3	3	2	0	0
II	4	4	4	6	0
III	0	0	0	0	0
IV	1	3	1	1	0
V	2	3	0	2	0

The minimum number of lines covering all the zeros (4) is less than the order of the matrix (5) so assignments are not possible. The modification is required. The minimum uncovered value (1) is subtracted from the uncovered values and added to the values at the intersection. The values on the lines remain the same. We get

	P	Q	R	S	T
I	2	2	2	0	0
II	3	3	4	6	0
III	0	0	1	1	1
IV	0	2	0	1	0
V	1	2	0	2	0

The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) so the assignment is possible.

	P	Q	R	S	T
I	2	2	2	0	X
II	3	3	4	6	0
III	X	0	1	1	1
IV	0	2	5	1	X
V	1	2	0	2	X

So I → S, II → T, III → Q, IV → P, V → R.
As T is dummy manager II is not given any city.
To find the maximum sales we take the corresponding value from the original matrix
Total maximum sales = 35 + 39 + 36 + 35 = 145 tons
In simple words: This maximization problem was converted to a minimization problem using the largest element, and then balanced by adding a dummy column. After applying the Hungarian method and making necessary matrix adjustments, the optimal assignment yields maximum sales of 145 tons, with manager II assigned to the dummy task (meaning not assigned to any city).

🎯 Exam Tip: When managers are assigned to dummy tasks, it means they are not assigned to any real task/city. The sales for dummy assignments are always zero when calculating the total maximum sales.

 

P	Q	R	S	T
5	3	6	4	0
6	4	8	6	0
2	0	4	4	0
3	3	5	5	0
4	3	4	6	0

Subtracting row minimum from all values in that row we get the same matrix Subtracting column minimum from all values in that column we get

P	Q	R	S	T
3	3	2	0	0
4	4	4	6	0
0	0	0	0	0
1	3	5	1	0
2	3	0	2	0

The minimum number of lines covering all the zeros (4) is less than the order of the matrix (5) so assignments are not possible. The modification is required. The minimum uncovered value (1) is subtracted from the uncovered values and added to the values at the intersection. The values on the lines remain the same. We get

P	Q	R	S	T
2	2	2	0	0
3	3	4	6	0
0	0	1	1	1
0	2	5	1	0
1	2	0	2	0

The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) so the assignment is possible.

P	Q	R	S	T
2	2	2	0	X
3	3	4	6	0
X	0	1	1	1
0	2	5	1	X
1	2	0	2	X

So I - S, II - T, III - Q, IV - P, V - R.
As T is dummy manager II is not given any city.
To find the maximum sales we take the corresponding value from the original matrix
Total maximum sales = 35 + 39 + 36 + 35 = 145 tons
In simple words: This solution applies the Hungarian method to find the optimal assignment that maximizes sales. It converts the maximization problem to minimization, balances the matrix with a dummy column, and then iteratively reduces the matrix to find zero assignments, ensuring the total sales are maximized.

🎯 Exam Tip: Remember to convert a maximization problem to a minimization one by subtracting all elements from the highest value in the matrix. Also, ensure the matrix is balanced by adding dummy rows/columns with zero costs if needed.

 

Question 5. Consider the problem of assigning five operators to five machines. The assignment costs are given in the following table.

Operator	Machine
	1	2	3	4	5
A	6	6	-	3	7
B	8	5	3	4	5
C	10	4	6	-	4
D	8	3	7	8	3
E	7	6	8	10	2

Operator A cannot be assigned to machine 3 and operator C cannot be assigned to machine 4. Find the optimal assignment schedule.
Answer: Solution:
This is a restricted assignment problem, so we assign a very high cost (\( \infty \)) to the prohibited cells we get

	1	2	3	4	5
A	6	6	&infty;	3	7
B	8	5	3	4	5
C	10	4	6	&infty;	4
D	8	3	7	8	3
E	7	6	8	10	2

Subtracting row minimum from all values in that row we get.

	1	2	3	4	5
A	3	3	&infty;	0	4
B	5	2	0	1	2
C	6	0	2	&infty;	0
D	5	0	4	5	0
E	5	4	6	8	0

Subtracting column minimum from all values in that column we get

	1	2	3	4	5
A	0	3	&infty;	0	4
B	2	2	0	1	2
C	3	0	2	&infty;	0
D	2	0	4	5	0
E	2	4	6	8	0

As the minimum number of lines covering all the zeros (4) is equal to the order of the matrix (5) so the assignment is not possible. The modification is required. The minimum uncovered value (2) is subtracted from all the uncovered values and added to the values at the intersection. The values on the lines remain the same.
We get

	1	2	3	4	5
A	0	1	&infty;	0	6
B	2	2	0	1	4
C	1	0	0	&infty;	0
D	0	0	2	3	0
E	0	4	4	6	0

As the minimum number of lines covering all the zeros (5) is equal to the order of the matrix, assignment is the possible

	1	2	3	4	5
A	X	1	&infty;	0	6
B	2	4	0	1	4
C	1	0	X	&infty;	X
D	0	X	2	3	X
E	X	4	4	0	0

So A - 4, B - 3, C - 2, D - 1, E - 5
For the minimum cost take the corresponding values from the cost matrix we get
Total minimum cost = 3 + 3 + 4 + 3 + 7 = 20 units
In simple words: This assignment problem involves assigning operators to machines with certain restrictions. We model restricted assignments with a very high cost (infinity) and then use the Hungarian method, including row/column reduction and matrix modification, to find the optimal assignment that minimizes the total cost.

🎯 Exam Tip: For restricted assignment problems, assign an infinitely high cost (\(\infty\)) to cells where an assignment is not allowed. This ensures those cells are not chosen during the assignment process.

 

Question 6. A chartered accountant's firm has accepted five new cases. The estimated number of days required by each of their five employees for each case are given below, where-means that the particular employee can not be assigned the particular case. Determine the optimal assignment of cases of the employees so that the total number of days required to complete these five cases will be minimum. Also, find the minimum number of days.
Answer: Solution:
This is a restricted assignment problem so we assign a very high cost (\( \infty \)) to all the prohibited cells. The day matrix becomes

Employee	Cases
	I	II	III	IV	V
E1	6	4	5	7	8
E2	7	&infty;	8	6	9
E3	8	6	7	9	10
E4	5	7	&infty;	4	6
E5	9	5	3	10	&infty;

Subtracting row minimum from all values in that row we get

	I	II	III	IV	V
E1	2	0	1	3	4
E2	1	&infty;	2	0	3
E3	2	0	1	3	4
E4	1	3	&infty;	0	2
E5	6	2	0	7	&infty;

Subtracting column minimum from all values in that column we get

	I	II	III	IV	V
E1	1	0	1	3	2
E2	0	&infty;	2	0	1
E3	1	0	1	3	2
E4	0	3	&infty;	0	0
E5	5	2	0	7	&infty;

The minimum number of lines covering all the zeros (4) is less than the order of the matrix (5) so the assignment is not possible. The modification is required. The minimum uncovered value (1) is subtracted from all the uncovered values and added to the values at the intersection. The values on the lines remain the same, we get

	I	II	III	IV	V
E1	0	0	1	2	1
E2	0	&infty;	3	0	1
E3	0	0	1	2	1
E4	0	4	&infty;	0	0
E5	4	2	0	6	&infty;

The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) so the assignment is possible.

	I	II	III	IV	V
E1	X	0	1	2	1
E2	X	&infty;	3	0	1
E3	X	0	1	2	1
E4	X	4	&infty;	X	0
E5	4	2	0	6	&infty;

So E1 - I, E2 - IV, E3 - II, E4 - V, E5 - III
To find the minimum number of days we take the corresponding values from the day matrix.
Total minimum number of days = 6 + 6 + 6 + 6 + 3 = 27 days
In simple words: This problem involves assigning cases to employees with certain restrictions (employees cannot be assigned specific cases). We use a very high cost for restricted assignments and then apply the Hungarian method to find the optimal assignment that minimizes the total number of days, resulting in a minimum of 27 days.

🎯 Exam Tip: When solving restricted assignment problems, replace "not allowed" entries with an extremely large value (infinity) to prevent them from being chosen in the optimal solution.

 

Part - II

 

Question 1. A readymade garments manufacture has to process 7 items through two stages of production, namely cutting and sewing. The time taken in hours for each of these items in different stages are given below:

Items	1	2	3	4	5	6	7
Time for Cutting	5	7	3	4	6	7	12
Time for Sewing	2	6	7	5	9	5	8

Find the sequence in which these items are to be processed through these stages so as to minimize the total processing time. Also, find the idle time of each machine.
Answer: Solution:
Let A = cutting and B = sewing. So we have

Items	1	2	3	4	5	6	7
A	5	7	3	4	6	7	12
B	2	6	7	5	9	5	8

Observe min {A, B} = 2 for item 1 for B.

1

The problem reduces to

Items	2	3	4	5	6	7
A	7	3	4	6	7	12
B	6	7	5	9	5	8

Now min {A, B} = 3 for item 3 for A

3

1

The problem reduces to

Items	2	4	5	6	7
A	7	4	6	7	12
B	6	5	9	5	8

New min {A, B} = 4 for item 4 for A.

3

4

1

The problem reduces to

Items	2	5	6	7
A	7	6	7	12
B	6	9	5	8

Now min{A, B} = 5 for item 6 for B

3

4

6

1

The problem reduces to

Items	2	5	7
A	7	6	12
B	6	9	8

Now min {A, B} = 6 for item 5 for A and item 2 for B

3

4

5

2

6

1

Now only 7 is left
The optimal sequence is

3

4

5

7

2

6

1

Worktable

Items	A		B		Idle time for B
	In	Out	In	Out
3	0	3	3	10	3
4	3	7	10	15
5	7	13	15	24
7	13	25	25	33	1
2	25	32	33	39
6	32	39	39	44
1	39	44	44	46	4

Total elapsed time = 46 hrs
Idle time for A (cutting) = 46 – 44 = 2 hrs
Idle time for B (Sewing) = 4 hrs
In simple words: This solution uses Johnson's algorithm to find the optimal sequence for processing 7 items through two machines (cutting and sewing) to minimize total time. By prioritizing jobs with shorter processing times on the first machine (cutting) or shorter processing times on the second machine (sewing) at the end, the sequence is determined, and then a worktable calculates the total elapsed time and idle times for both machines.

🎯 Exam Tip: For 2-machine sequencing problems, apply Johnson's algorithm: pick the smallest processing time. If it's on the first machine, schedule the job first. If on the second machine, schedule it last. Repeat this until all jobs are sequenced, then construct the worktable for idle times.

 

Question 2. Five jobs must pass through a lathe and a surface grinder, in that order. The processing times in hours are shown below. Determine the optimal sequence of the jobs. Also, find the idle time of each machine.

Job	I	II	III	IV	V
Lathe	4	1	5	2	5
Surface grinder	3	2	4	3	6

Answer: Solution:
Let A = lathe and B = surface grinder. We have

Job	I	II	III	IV	V
A	4	1	5	2	5
B	3	2	4	3	6

Observe min {A, B} = 1 for job II for A

II

The problem reduces to

Job	I	III	IV	V
A	4	5	2	5
B	3	4	3	6

Now min {A, B} = 2 for job IV for A

II

IV

The problem reduces to

Job	I	III	V
A	4	5	5
B	3	4	6

Now min {A, B} = 3 for job I for B

II

IV

I

The problem reduces to

Job	III	V
A	5	5
B	4	6

Now min {A, B} = 5 for jobs III and V for A
We have two options

II

IV

V

III

I

or

II

IV

III

V

I

We take the first one.
Worktable

Job	A		B		Idle time for B
	In	Out	In	Out
II	0	1	1	3	1
IV	1	3	3	6
V	3	8	8	14	2
III	8	13	14	18
I	13	17	18	21	3

Total elapsed time = 21 hrs
Idle time for A (lathe) = 21 – 17 = 4 hrs
Idle time for B (surface grinder) = 3 hrs
In simple words: This problem uses Johnson's algorithm to determine the best sequence for five jobs processed on two machines (lathe and surface grinder) to minimize total time. By repeatedly selecting the shortest processing time and sequencing jobs accordingly, an optimal sequence is found, and a worktable is constructed to calculate the overall time and individual machine idle times.

🎯 Exam Tip: When multiple jobs have the minimum processing time on the same machine (e.g., job III and V on machine A), any order among them is acceptable in the sequence. Calculate idle times accurately using the "in" and "out" times from the worktable.

 

Question 3. Find the sequence that minimizes the total elapsed time to complete the following jobs. Each job is processed in order AB.

	Jobs (Processing times in minutes)
	I	II	III	IV	V	VI	VII
Machine A	12	6	5	11	5	7	7
Machine B	7	8	9	4	7	6	3

Determine the sequence for the jobs so as to minimize the processing time. Find the total elapsed time and the idle time for both machines.
Answer: Solution:
Observe min {A, B} = 3 for job VII on B.

VII

The problem reduces to

Job	I	II	III	IV	V	VI
A	12	6	5	11	5	7
B	7	8	9	4	7	6

Now min {A, B} = 4 for job IV on B.

IV

VII

The problem reduces to

Job	I	II	III	V	VI
A	12	6	5	5	7
B	7	8	9	7	8

Now min {A, B} = 5 for job III & V on A. we have two options

III

V

IV

VII

or

V

III

IV

VII

We take the first one.
The problem reduces to

Job	I	II	VI
A	12	6	7
B	7	8	8

Now min {A, B} = 5 for job II on A

III

V

II

IV

VII

The problem reduces to

Job	I	VI
A	12	7
B	7	8

Now min {A, B} = 7 for a job I on B and for job VI on A
The optional sequence is

III

V

II

VI

I

IV

VII

Worktable

Job	A		B		Idle time for B
	In	Out	In	Out
III	0	5	5	14	5
V	5	10	14	21
II	10	16	21	29
VI	16	23	29	37
I	23	35	37	44
IV	35	46	46	50	2
VII	46	52	52	55	2

Total elapsed time = 55 units
Idle time for A = 55 – 52 = 3 units
Idle time for B = 9 units.
In simple words: This problem uses Johnson's algorithm to sequence seven jobs on two machines (A and B) to minimize the total completion time. By selecting jobs with the smallest processing times on either machine A (scheduled first) or machine B (scheduled last) iteratively, an optimal sequence is built, and a worktable is then used to calculate the total elapsed time and the idle time for each machine.

🎯 Exam Tip: When applying Johnson's algorithm, remember that if the minimum time is common to both machines, schedule it on machine A first. If there's a tie for the minimum on one machine, the order among those tied jobs doesn't affect the total elapsed time, but it's crucial to be consistent.

 

Question 4. A toy manufacturing company has five types of toys. Each toy has to go through three machines A, B, C in the order ABC. The time required in hours for each process is given in the following table.

Type	1	2	3	4	5
Machine A	16	20	12	14	22
Machine B	10	12	4	6	8
Machine C	8	18	16	12	10

Solve the problem for minimizing the total elapsed time.
Answer: Solution:
Min A = 12, Max B = 12
As min A ≥ max B.
The problem can be converted into two machine problems.
Let G and H be two fictitious machines such that G = A + B and H = B + C, We get

Type	1	2	3	4	5
G	26	32	16	20	30
H	18	30	20	18	18

Now min {G, H} = 16 for type 3 on G

3

The problem reduces to

Type	1	2	4	5
G	26	32	20	30
H	18	30	18	18

Min {G, H} = 18 for type 1, 4 & 5 on H
We have more than one option, we take

3

4

5

1

Now only type 2 is left.
The optional sequence is

3

2

4

5

1

Worktable

Type	A		B		Idle time For B	C		Idle time For C
	In	Out	In	Out		In	Out
3	0	12	12	16	12	16	32	16
2	12	32	32	44	16	44	62	12
4	32	54	54	62	10	62	72
5	54	68	68	74	6	74	86	2
1	68	84	84	94	10	94	102	8

Total elapsed time = 102 hours
Idle time for A = 102 – 84 = 18 hours
Idle time for B = 54 + (102 – 94) = 62 hours
Idle time for C = 38 hours
In simple words: This problem involves sequencing jobs through three machines (A, B, C). It's converted into a two-machine problem (G = A+B, H = B+C) using Johnson's extension rule because the minimum processing time on machine A is greater than or equal to the maximum processing time on machine B. Johnson's algorithm is then applied to machines G and H to find the optimal sequence, which is used to construct a worktable and calculate total elapsed time and idle times for each of the original three machines.

🎯 Exam Tip: For n-jobs, 3-machine sequencing problems (A-B-C order), always check if min(A) ≥ max(B) or min(C) ≥ max(B). If either condition holds, convert to a 2-machine problem with G = A+B and H = B+C, then apply Johnson's algorithm. If neither condition holds, a graphical solution or other heuristic might be needed (not covered here).

 

Question 5. A foreman wants to process 4 different jobs on three machines: a shaping machine, a drilling machine, and a tapping, the sequence of operations being shaping-drilling-tapping. Decide the optimal sequence for the four jobs to minimize the total elapsed time. Also, find the total elapsed time and the idle time for every machine.

Job	Shaping	Drilling	Trapping
	(minutes)	(minutes)	(Minutes)
1	13	3	18
2	18	8	4
3	8	6	13
4	23	6	8

Answer: Solution:
The time matrix is

Job	1	2	3	4
Shaping (A)	13	18	8	23
Drilling (B)	3	8	6	6
Trapping(C)	18	4	13	8

Min A = 8, Max B = 8, as min A ≥ max B.
The problem can be converted into a two-machine problem.
Let G and H be two fictitious machines such that
G = A + B and H = B + C we get

Job	1	2	3	4
G	16	26	14	29
H	21	12	19	14

Observe min {G, H} = 12 for job 2 on H

2

The problem reduces to

Job	1	3	4
G	16	14	29
H	21	19	14

Now min {G, H} = 14 for job 3 on G and job 4 on H

3

4

2

Now only job 1 is left.
The optimal sequence is

3

1

4

2

Worktable

Job	A		B		Idle time For B	C		Idle time For C
	In	Out	In	Out		In	Out
3	0	8	8	14	8	14	27	14
1	8	21	21	24	7	27	45
4	21	44	44	50	20	50	58	5
2	44	62	62	70	12	70	74	12

Total elapsed time = 74 min
Idle time for A (shaping) = 74 – 62 = 12 min
Idle time for B (Drilling) = 47 + (74 – 70) = 51 min
Idle time for C (trapping) = 31 min
In simple words: This solution tackles a 3-machine sequencing problem (Shaping, Drilling, Tapping) by first checking if it can be simplified to a 2-machine problem using Johnson's extension rules (min(A) ≥ max(B) holds). After transforming it into a G-H two-machine problem (G = A+B, H = B+C), Johnson's algorithm is applied to find the optimal job sequence. Finally, a detailed worktable is constructed to calculate the total elapsed time and the individual idle times for each of the original three machines.

🎯 Exam Tip: When calculating idle time for intermediate machines (like Machine B in A-B-C sequence), remember to sum up the idle time at the start (if any) and any idle periods that occur when the machine is waiting for a job to complete on the previous machine.