Maharashtra Board Class 12 Maths Part 2 Chapter 7 Assignment Problem 7.1 Solutions

Question 1. A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R, and S. The processing cost of each job for each machine is given in the following table:

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी चार मशीनों (I, II, III, IV) पर चार विभिन्न कार्यों (P, Q, R, S) को संसाधित करने की लागत (Rs.) को दर्शाती है। यह असाइनमेंट समस्या का प्रारंभिक लागत मैट्रिक्स प्रस्तुत करती है, जिसका उद्देश्य न्यूनतम कुल प्रसंस्करण लागत ज्ञात करना है।

Find the optimal assignment to minimize the total processing cost.
Answer:
Solution: The cost matrix is given by

Subtracting row minimum from all the elements in that row we get

Subtracting column minimum from all the elements in that column we get the same matrix.
As all the rows and columns have single zeros the allotment can be done as follows.

As per the table, the job allotments are
P - II, Q - IV, R - I, S - III
The total minimum cost = 25 + 21 + 19 + 34 = Rs. 99
In simple words: The problem is solved using the Hungarian algorithm by first reducing the cost matrix to find zeros, then making assignments to minimize the total processing cost. The optimal assignment is P to II, Q to IV, R to I, and S to III, resulting in a total minimum cost of Rs. 99.

🎯 Exam Tip: When solving assignment problems, ensure all row and column minimum subtractions are accurate. Clearly identify and list the final optimal assignments and calculate the total cost from the *original* cost matrix.

Question 2. 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?

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी विभिन्न स्टेशनों (I, II, III, IV, V) पर पाँच वैगनों (1, 2, 3, 4, 5) के बीच की दूरी (माइलेज) को दर्शाती है। यह वैगनों के परिवहन की प्रारंभिक माइलेज मैट्रिक्स है, जिसका उद्देश्य कुल तय की गई दूरी को न्यूनतम करना है।

Answer:
Solution:
The mileage matrix is given by

Subtracting row minimum from all elements in that row we get

Subtracting column minimum from all elements in that column we get

Draw minimum lines covering all the zeros

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी पंक्ति और कॉलम न्यूनतम घटाने के बाद प्राप्त माइलेज मैट्रिक्स को दर्शाती है, जिसमें कुछ शून्य मानों को कवर करने के लिए न्यूनतम रेखाएं (यहाँ 3) खींची गई हैं। वैगन (1, 2, 3, 4, 5) को स्टेशन (I, II, III, IV, V) पर असाइनमेंट के लिए तैयारी की जा रही है।

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

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी असाइनमेंट मैट्रिक्स के पहले संशोधन को दर्शाती है। न्यूनतम लाइनों (3) द्वारा शून्य को कवर करने के बाद, असाइनमेंट संभव नहीं था, इसलिए न्यूनतम अनदेखे मान (1) को अनदेखे मानों से घटाया गया और प्रतिच्छेदन बिंदुओं पर जोड़ा गया।

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

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी असाइनमेंट मैट्रिक्स के दूसरे संशोधन को दर्शाती है। चूंकि पिछले चरण में भी असाइनमेंट संभव नहीं था (4 लाइनें), न्यूनतम अनदेखे मान (3) को फिर से अनदेखे मानों से घटाया गया और प्रतिच्छेदन बिंदुओं पर जोड़ा गया, जिससे असाइनमेंट के लिए एक उपयुक्त मैट्रिक्स तैयार हो सके।

No. of lines covering all the zeros (5) are equal to the order of the matrix so the assignment is possible.

ℹ️ चित्र व्याख्या (Diagram Explanation): यह अंतिम असाइनमेंट मैट्रिक्स है जहाँ न्यूनतम लाइनों की संख्या (5) मैट्रिक्स के क्रम (5) के बराबर है, जो दर्शाता है कि एक इष्टतम असाइनमेंट संभव है। इसमें वैगनों को स्टेशनों पर असाइन करने के लिए शून्य मानों का उपयोग किया गया है।

According to the table the assignment is
1 - I, 2 - III, 3 - IV, 4 - II, 5 - V
Total minimum mileage = 10 + 6 + 4 + 9 + 10 = 39 units
In simple words: This problem involves minimizing the total mileage for transporting five wagons to five stations. After multiple matrix reductions and modifications to cover all zeros with minimum lines, the optimal assignment is found as 1 to I, 2 to III, 3 to IV, 4 to II, and 5 to V, resulting in a total minimum mileage of 39 units.

🎯 Exam Tip: When the number of lines covering zeros is less than the matrix order, always apply the modification rule (subtract min uncovered value from uncovered, add to intersection) carefully. Repeat until the assignment is possible, then calculate the total cost from the *original* matrix.

Question 3. Five different machines can do any of the five required jobs, with different profits resulting from each assignment as shown below:

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी पाँच मशीनों (A, B, C, D, E) द्वारा पाँच विभिन्न कार्यों (1, 2, 3, 4, 5) को करने से होने वाले लाभ को दर्शाती है। यह असाइनमेंट समस्या का प्रारंभिक लाभ मैट्रिक्स प्रस्तुत करती है, जिसका उद्देश्य अधिकतम कुल लाभ ज्ञात करना है।

Find the optimal assignment schedule.
Answer:
Solution:
This profit matrix has to be reduced to cost matrix by subtracting all the values of the matrix from the largest value (62) we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह प्रारंभिक लाभ मैट्रिक्स को लागत मैट्रिक्स में बदलने के बाद का परिणाम है। प्रत्येक तत्व को मैट्रिक्स के अधिकतम मान (62) से घटाकर लागत मैट्रिक्स प्राप्त की जाती है, जो अधिकतम लाभ असाइनमेंट समस्या को न्यूनतम लागत असाइनमेंट समस्या में बदल देता है।

Subtracting row minimum value from all the elements in that column we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह लागत मैट्रिक्स को पंक्ति न्यूनतम घटाकर संशोधित करने के बाद का परिणाम है। प्रत्येक पंक्ति के न्यूनतम मान को उसकी पंक्ति के सभी तत्वों से घटाया गया है, जिससे मैट्रिक्स में शून्य की संख्या बढ़ जाती है और असाइनमेंट प्रक्रिया आसान हो जाती है।

Subtracting column minimum from all the elements in that column we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह लागत मैट्रिक्स को कॉलम न्यूनतम घटाकर संशोधित करने के बाद का परिणाम है। प्रत्येक कॉलम के न्यूनतम मान को उसके कॉलम के सभी तत्वों से घटाया गया है, जिससे असाइनमेंट के लिए और अधिक शून्य प्राप्त होते हैं।

Drawing minimum lines covering all zeros we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी असाइनमेंट मैट्रिक्स का एक चरण दर्शाती है जहां न्यूनतम पंक्तियों को सभी शून्यों को कवर करने के लिए खींचा गया है। यदि खींची गई रेखाओं की संख्या मैट्रिक्स के क्रम से कम है, तो आगे संशोधन की आवश्यकता होती है।

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

ℹ️ चित्र व्याख्या (Diagram Explanation): यह संशोधित लागत मैट्रिक्स है। चूंकि पिछली स्थिति में असाइनमेंट संभव नहीं था (4 लाइनें, 5 के ऑर्डर से कम), न्यूनतम अनदेखे मान (4) को अनदेखे तत्वों से घटाया गया और प्रतिच्छेदन बिंदुओं पर जोड़ा गया, ताकि एक वैध असाइनमेंट प्राप्त किया जा सके।

No. of lines (5) are equal to the order of the matrix (5). So assignments are possible
1 - C, 2 - E, 3 - A, 4 - D, 5 - B
For the minimum profit look at the corresponding in the profit matrix given.
Maximum profit = 40 + 36 + 40 + 36 + 62 = 214 units
In simple words: To maximize profit, the initial profit matrix is converted into a cost matrix. After applying row and column reductions and modifications based on covering zeros, the optimal assignment is determined. The final assignment yields a maximum profit of 214 units.

🎯 Exam Tip: For maximization problems, always convert the profit matrix to a cost matrix by subtracting all elements from the highest element. Then, apply the Hungarian algorithm steps as usual and calculate the final maximum profit from the *original* profit matrix.

Question 4. Four new machines M1, M2, M3, and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D, and E available. Because of limited space, machine M2 cannot be placed at C and M₁ cannot be placed at A. The cost matrix is given below.

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी चार मशीनों (M1, M2, M3, M4) को पाँच स्थानों (A, B, C, D, E) पर स्थापित करने की लागत को दर्शाती है। कुछ स्थानों पर प्रतिबंध भी हैं (M2 को C पर नहीं, M1 को A पर नहीं), जिससे यह एक प्रतिबंधात्मक असाइनमेंट समस्या बन जाती है।

Find the optimal assignment schedule.
Answer:
Solution:
This is a restricted assignment so we assign a very high cost '∞' to the prohibited all.
Also as it is an unbalanced problem we add a dummy row M5 with all values as '0' we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह प्रारंभिक लागत मैट्रिक्स का संशोधित रूप है। असंतुलित समस्या को संतुलित करने के लिए एक डमी पंक्ति M5 (सभी शून्य मानों के साथ) जोड़ी गई है, और प्रतिबंधित असाइनमेंट (M2 को C पर नहीं, M1 को A पर नहीं) को '∞' (असीमित लागत) से चिह्नित किया गया है।

Subtracting row minimum from all the elements in that row, we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह संशोधित लागत मैट्रिक्स को पंक्ति न्यूनतम घटाकर प्राप्त हुआ परिणाम है। प्रत्येक पंक्ति के न्यूनतम मान को उसकी पंक्ति के सभी तत्वों से घटाया गया है, जिससे असाइनमेंट के लिए और अधिक शून्य प्राप्त होते हैं।

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

ℹ️ चित्र व्याख्या (Diagram Explanation): यह संशोधित लागत मैट्रिक्स को कॉलम न्यूनतम घटाकर प्राप्त हुआ परिणाम है। प्रत्येक कॉलम के न्यूनतम मान को उसके कॉलम के सभी तत्वों से घटाया गया है, जिससे असाइनमेंट के लिए अधिकतम शून्य प्राप्त होते हैं।

As minimum no. of lines covering all zeros (5) is equal to the order of the matrix, Assignment is possible

ℹ️ चित्र व्याख्या (Diagram Explanation): यह अंतिम असाइनमेंट मैट्रिक्स है जहाँ न्यूनतम लाइनों की संख्या (5) मैट्रिक्स के क्रम (5) के बराबर है, जो दर्शाता है कि एक इष्टतम असाइनमेंट संभव है। इसमें मशीनों को स्थानों पर असाइन करने के लिए शून्य मानों का उपयोग किया गया है, साथ ही प्रतिबंधित स्थानों को भी ध्यान में रखा गया है।

The assignment is
M1 - A, M2 - B, M3 - E, M₄ - D, M5 - C
As M5 is dummy, no machine is installed at C.
The minimum cost is found by taking the corresponding values in the cost matrix
Minimum cost = 4 + 4 + 2 + 2 = 12 (in hundred Rs.)
In simple words: This problem involves assigning four machines to five places with restrictions and an unbalanced matrix. A dummy row M5 is added, and restricted assignments are marked with infinite cost. After applying the Hungarian algorithm, the optimal assignment of machines to places is found, resulting in a minimum cost of 12 (in hundred Rs.).

🎯 Exam Tip: For restricted assignments, use '∞' (or a very large number) for prohibited cells. For unbalanced problems, add dummy rows or columns with zero costs. Remember to always calculate the final cost from the *original* cost matrix.

Question 5. A company has a team of four salesmen and there is four districts where the company wants to start its business. After taking into account the capabilities of salesmen and the nature of districts, the company estimates that the profit per day in rupees for each salesman in each district is as below:

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी चार सेल्समैन (A, B, C, D) को चार जिलों (1, 2, 3, 4) में असाइन करने से होने वाले दैनिक लाभ (रुपये में) को दर्शाती है। यह असाइनमेंट समस्या का प्रारंभिक लाभ मैट्रिक्स प्रस्तुत करती है, जिसका उद्देश्य अधिकतम कुल लाभ ज्ञात करना है।

Find the assignments of a salesman to various districts which will yield maximum profit.
Answer:
Solution:
The profit matrix has to be reduced to the cost matrix. Subtracting all the values from the maximum value (16) we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह प्रारंभिक लाभ मैट्रिक्स को लागत मैट्रिक्स में बदलने के बाद का परिणाम है। प्रत्येक तत्व को मैट्रिक्स के अधिकतम मान (16) से घटाकर लागत मैट्रिक्स प्राप्त की जाती है, जो अधिकतम लाभ असाइनमेंट समस्या को न्यूनतम लागत असाइनमेंट समस्या में बदल देता है।

Subtracting row minimum from all values in that row we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह लागत मैट्रिक्स को पंक्ति न्यूनतम घटाकर संशोधित करने के बाद का परिणाम है। प्रत्येक पंक्ति के न्यूनतम मान को उसकी पंक्ति के सभी तत्वों से घटाया गया है, जिससे असाइनमेंट के लिए और अधिक शून्य प्राप्त होते हैं।

Subtracting column minimum from each column we get the same matrix

ℹ️ चित्र व्याख्या (Diagram Explanation): यह लागत मैट्रिक्स को कॉलम न्यूनतम घटाकर संशोधित करने के बाद का परिणाम है। प्रत्येक कॉलम के न्यूनतम मान को उसके कॉलम के सभी तत्वों से घटाया गया है, जिससे असाइनमेंट के लिए अधिकतम शून्य प्राप्त होते हैं।

As minimum no. of lines covering all zeros (4) is equal to the order of the matrix (4)
Assignment is possible

ℹ️ चित्र व्याख्या (Diagram Explanation): यह अंतिम असाइनमेंट मैट्रिक्स है जहाँ न्यूनतम लाइनों की संख्या (4) मैट्रिक्स के क्रम (4) के बराबर है, जो दर्शाता है कि एक इष्टतम असाइनमेंट संभव है। इसमें सेल्समैन को जिलों पर असाइन करने के लिए शून्य मानों का उपयोग किया गया है।

∴ A - 1, B - 3, C - 2, D - 4
For maximum profit, we take the corresponding values in the profit matrix. We get
Maximum profit = 16 + 15 + 15 + 15 = Rs. 61
In simple words: To maximize the profit from assigning salesmen to districts, the profit matrix is converted to a cost matrix by subtracting all values from the maximum profit. After applying row and column reduction, the optimal assignments are made to the cells with zeros, leading to a maximum total profit of Rs. 61.

🎯 Exam Tip: In maximization problems, converting to a cost matrix is crucial. Always verify that the number of lines covering zeros equals the matrix order before making final assignments. Calculate the total profit using the *original* profit values.

Question 6. In the modification of a plant layout of a factory four new machines M1, M2, M3, and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D, and E available. Because of limited space, machine M2 can not be placed at C and M3 can not be placed at A the cost of locating a machine at a place (in hundred rupees) is as follows.

ℹ️ चित्र व्याख्या (Diagram Explanation): यह सारणी चार मशीनों (M1, M2, M3, M4) को पाँच स्थानों (A, B, C, D, E) पर स्थापित करने की लागत (सौ रुपये में) को दर्शाती है। इसमें कुछ प्रतिबंध हैं (M2 को C पर नहीं, M3 को A पर नहीं), जो इसे एक प्रतिबंधात्मक असाइनमेंट समस्या बनाते हैं।

Find the optimal assignment schedule.
Answer:
Solution:
This is an unbalanced problem so we add a dummy row M5 with all values as '0'.
Also, this is on restricted assignment problem. So we assign a very high-cost W to the prohibited cells we have

ℹ️ चित्र व्याख्या (Diagram Explanation): यह प्रारंभिक लागत मैट्रिक्स का संशोधित रूप है। असंतुलित समस्या को संतुलित करने के लिए एक डमी पंक्ति M5 (सभी शून्य मानों के साथ) जोड़ी गई है, और प्रतिबंधित असाइनमेंट (M2 को C पर नहीं, M3 को A पर नहीं) को '∞' (असीमित लागत) से चिह्नित किया गया है।

Subtracting row minimum from all values in that row we get

ℹ️ चित्र व्याख्या (Diagram Explanation): यह संशोधित लागत मैट्रिक्स को पंक्ति न्यूनतम घटाकर प्राप्त हुआ परिणाम है। प्रत्येक पंक्ति के न्यूनतम मान को उसकी पंक्ति के सभी तत्वों से घटाया गया है, जिससे असाइनमेंट के लिए और अधिक शून्य प्राप्त होते हैं।

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

ℹ️ चित्र व्याख्या (Diagram Explanation): यह संशोधित लागत मैट्रिक्स को कॉलम न्यूनतम घटाकर प्राप्त हुआ परिणाम है। प्रत्येक कॉलम के न्यूनतम मान को उसके कॉलम के सभी तत्वों से घटाया गया है, जिससे असाइनमेंट के लिए अधिकतम शून्य प्राप्त होते हैं।

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

ℹ️ चित्र व्याख्या (Diagram Explanation): यह अंतिम असाइनमेंट मैट्रिक्स है जहाँ न्यूनतम लाइनों की संख्या (5) मैट्रिक्स के क्रम (5) के बराबर है, जो दर्शाता है कि एक इष्टतम असाइनमेंट संभव है। इसमें मशीनों को स्थानों पर असाइन करने के लिए शून्य मानों का उपयोग किया गया है, साथ ही प्रतिबंधित स्थानों और डमी पंक्ति को भी ध्यान में रखा गया है।

The assignment is
M1 - A, M2 - B, M3 - E, M₄ - D, M5 - C
As M5 is dummy, no machine is installed at C.
The minimum cost is found by taking the corresponding values in the cost matrix
Minimum cost = 9 + 9 + 7 + 7 + 0 = 32 (in hundred Rs.)
In simple words: This problem involves assigning four machines to five places with specific restrictions and is unbalanced. A dummy row M5 is added, and impossible assignments are given infinite costs. After applying the Hungarian method, the optimal assignments are M1 to A, M2 to B, M3 to E, and M4 to D, with M5 being a dummy. The total minimum cost is 32 (in hundred Rs.).

🎯 Exam Tip: When dealing with restricted assignments, ensure prohibited cells are correctly marked with '∞'. For unbalanced matrices, always add a dummy row/column with zero costs. The final cost calculation should use the *original* cost values corresponding to the optimal assignments.