@Joseinnewworld just went off again tonight — picked up 7 more #NFTs like it’s a nightly ritual 🔥 At this point, he’s not collecting... he’s curating. Big love and respect, always 🙌 #NFTcollector #UnstoppableSupport #NFTMarketplace #NFTCollection #CryptoMarket #eCash $XEC pic.twitter.com/KW1CCb1Pj0
— NFToa (@nftoa_) July 10, 2025
Case Study 1
It is known that there is a problem with the assignment of Sicoco company's cake production, which is assisted by 4 employees including Paijo, Paijah, Wanto and Wanti, who will be empowered in the Dough, Cooking, Cutting / Forming and Packaging sections, with a detailed daily wage of Rp. 1000, - as follows:
Hungarian Method Practice Questions and Discussion / Solution
| Karyawan | Pekerjaan |
|----------|-----------|---------|----------|----------|
| | Adonan | Memasak | Memotong | Mengemas |
| Paijo | 65 | 50 | 60 | 70 |
| Paijah | 55 | 45 | 60 | 55 |
| Wanto | 50 | 60 | 75 | 70 |
| Wanti | 40 | 55 | 65 | 60 |Determine the optimal allocation of work to employees, in order to obtain the cheapest wage costs. Solve the assignment problem above using the Hungarian method!
Solution 1
Minimize
Step 1
Find the smallest cost for each row, then use it to subtract all costs in the same row. With this step, the result is obtained:
before,
after,
Step 2
Make sure all rows and columns have zero values. And it turns out that columns 4 and 5 do not have zero values. Thus, it is necessary to find the smallest value in the column to then be used to reduce all the values in the column (the same column). With this step, the results are obtained:
before,
after,
Step 3
Ensure or check the assignment table again, whether it has a zero value that corresponds to the number of resources, which is also reflected in the number of rows.
For example, if 4 employees are assigned, then 4 zero values must be found in different rows and columns. It is better to start from a row that only has one zero value. This step means that each employee can only hold one role / job.
Note! From the matrix above, it turns out that the zero values found in rows 3 and 4 (row Wanto and Row Wanti), although different rows but still in the same column, so it can be ascertained that the problem is not optimal and needs to be continued to the next step.
Step 4
Because it is not optimal, the next step is to draw a line connecting at least two zero values, as shown in the table below:
Step 5
Pay attention to the values that have not been touched by the line. Choose the smallest value (from the table above is the value 10), then the value 10 is used to reduce other values that have not been touched by the line, and use it to add the values that are touched by the double line. With this step, the results obtained are:
Step 6
Have zero values been found as many or as many resources? which is also reflected by the number of rows (starting from a row that only has one zero value). And it turns out that the assignment table above has successfully found 4 zero values (a number of employees to be assigned), which are in different rows and columns, meaning that the assignment table above is optimal.
Conclusion
Paijo, dialokasikan pada tugas Memotong = 60
Paijah, dialokasikan pada tugas Memasak = 45
Wanto, dialokasikan pada tugas Adonan = 50
Wanti, dialokasikan pada tugas Mengemas = 60
----------------------------------------------------------------- (+)
Total : 215So the optimal allocation of work to the 4 employees is, 215 x 1000 = Rp. 215,000,- / day.
Case Study 2
A Prima bakery company in marketing its products opens outlets in Malioboro Mall, Jogja City Mall, Galeria Mall, Amplaz Mall, which will be awaited by 4 employees including Agus, Budi, Cecep and Didi. With the details of wages (10,000,- / day) are as follows:
| Karyawan | Pekerjaan |
|----------|-----------|-----|----|----|
| | MM | JCM | GM | AM |
| Agus | 15 | 20 | 18 | 22 |
| Budi | 14 | 16 | 21 | 17 |
| Cecep | 25 | 20 | 23 | 20 |
| Didi | 17 | 18 | 18 | 16 |Determine the optimal allocation of work to employees, in order to obtain the cheapest wage cost per day. Solve the assignment problem above using the Hungarian method!
Solution 2
Minimize
Step 1 - Identify the Assignment Table
Find the smallest cost for each row, then use it to subtract all costs in the same row. With this step, the result is obtained:
before,
after,
Just a note: If #Maximize, then find the largest value in the same row, then subtract that value from each value in the same row. Example:
before,
after,
Step 2
Make sure all rows and columns have zero values. And it turns out that column 3 does not have zero values. Thus, it is necessary to find the smallest value in the column to then be used to reduce all the values in the column. With this step, the results are obtained:
before,
after,
Step 3
Ensure or check the assignment table again, whether it has a zero value that corresponds to the number of resources, which is also reflected in the number of rows.
For example, if 4 employees are assigned, then 4 zero values must be found in different rows and columns. It is better to start from a row that only has one zero value. This step means that each employee can only hold one role / job.
Note! From the matrix above, it turns out that the zero values found in rows 1 and 2 (Agus and Budi rows), although different rows but still in the same column, so it can be ascertained that the problem is not optimal and needs to be continued to the next step.
Step 4
Because it is not optimal, the next step is to draw a line connecting at least two zero values, as shown in the table below:
Step 5
Pay attention to the values that have not been touched by the line. Choose the smallest value (from the table above is the value 1), then the value 1 is used to reduce other values that have not been touched by the line, and use it to add the values that are touched by the double line. With this step, the results obtained are:
Step 6
Have zero values been found as many or as many resources? which is also reflected by the number of rows (starting from a row that only has one zero value). And it turns out that the assignment table above has successfully found 4 zero values (a number of employees to be assigned), which are in different rows and columns, meaning that the assignment table above is optimal.
Conclusion
Agus, dialokasikan pada tugas Galeria Mall = 18
Budi, dialokasikan pada tugas Malioboro Mall = 14
Cecep, dialokasikan pada tugas Jogja City Mall = 20
Didi, dialokasikan pada tugas Ambarukmo Plaza Mall = 16
----------------------------------------------------------------- (+)
Total : 68So the optimal allocation of employees to outlets is, 68 x 10,000 = Rp. 680,000,- / day .
Hungarian Method UTS Operations Research Questions Solution
Known Assignment Issues:
In making potato chips, the Kemripik Company is assisted by 4 employees who are given the job of peeling, slicing, frying, and packaging with a detailed daily wage (working hours 09.00 - 15.00) on a scale of Rp. 1000,- as follows:
Midterm Assignment - Operations Research Techniques
| Karyawan | Pekerjaan |
|----------|-----------|----------|------------|----------|
| | Mengupas | Mengiris | Menggoreng | Mengemas |
| Joko | 25 | 24 | 20 | 23 |
| Wati | 21 | 23 | 17 | 20 |
| Budi | 15 | 20 | 19 | 17 |
| Ani | 19 | 22 | 23 | 21 |Determine the optimal allocation of work to employees to obtain the least wage cost. Solve this assignment problem using the Hungarian method.
Completion
Step 1
Find the smallest cost for each row, then use it to subtract all costs in the same row. With this step, the result is obtained:
before,
after,
Step 2
Make sure all rows and columns have zero values. And it turns out that in this case there is still a clash or there is still a column that does not have zero, namely column 3. Thus it is necessary to find the smallest value in the column to then be used to reduce all the values in the column. With this step, the results are obtained:
before,
because in this matrix there are still columns that do not have zeros, then repeat step 1.
after,
Step 3
That is, to ensure or check the assignment table, whether it has a zero value that corresponds to the number of resources, which is also reflected in the number of rows.
For example, if 4 employees are assigned, then 4 zero values must be found in different rows and columns. It is better to start from a row that only has one zero value. This step means that each employee can only hold one role / job.
Note! From the matrix above, it turns out that the zero values found in rows 1 and 2, although in different rows but still in the same column, so it can be ascertained that the problem is not optimal and needs to be continued to the next step.
Step 4
Because it is not optimal, the next step is to draw a line connecting at least two zero values, as shown in the table below:
Step 5
Pay attention to the values that have not been touched by the line. Choose the smallest value (from the table above is the value 1), then the value 1 is used to reduce other values that have not been touched by the line, and use it to add the values that are touched by the double line. With this step, the results obtained are:
Step 6
Have zero values been found as many or as many resources? which is also reflected by the number of rows (starting from a row that only has one zero value). And it turns out that the assignment table above has successfully found 4 zero values (a number of employees to be assigned), which are in different rows and columns, meaning that the assignment table above is optimal.
Conclusion
Joko, dialokasikan pada tugas mengiris = 24
Wati, dialokasikan pada tugas menggoreng = 17
Budi, dialokasikan pada tugas mengemas = 17
Ani, dialokasikan pada tugas mengupas = 19
----------------------------------------------------------------- (+)
Total : 77So the optimal allocation of work to the 4 employees is 77 x 1000 = Rp. 77,000,- / day.
Hungarian Method of Operations Research Assignment
The problem of assignment is related to the company's desire to obtain an optimal division or allocation of tasks (assignments), in the sense of "if the assignment is related to profit, then how can the allocation of tasks or assignments provide maximum profit, and vice versa if it concerns costs.
Hungarian Method for Assignment Management in Operations Research Techniques
The solution of assignment problems is usually done using the Hungarian method which was developed in 1916 by a Hungarian mathematician named D. K. Onig. In general, the steps for solving normal assignment problems are:
1. Problem Identification and Simplification
Made in the form of an assignment table.
2.a. Minimize
For minimization cases, it is necessary to find the smallest value in each row, then use that smallest value to subtract all the values in the same row.
2.b. Maximize
For the maximization case, it is necessary to find the highest value of each row, then subtract the highest value from the values in the same row.
3. Ensure that all rows and columns have zero values.
If there are still rows or columns that do not have a zero value, then the smallest value in that row/column is searched for and then used to reduce all the values in that row/column.
4. Ensure There Is No Clash On Zero Values
In other words, does the zero value (which represents the assignment) conflict or become a contest for other resources? If so, then it still needs to be optimized.
After all rows and columns have zero values, the next step is to ensure or check whether the assignment table has successfully found as many zero values as resources (can be employees, machines, transportation, etc.) which are also reflected in the number of rows. For example, if 4 employees will be assigned, then 4 zero values must be found in different rows and columns. It is better to start from a row that only has one zero value. This step means that each employee can only be assigned to one job.
5. Draw a line connecting zero
If not, then the next step is to draw a line connecting at least two zero values in the assignment table.
6. Reduce Values Outside the Line and Increase Values Inside the Line
Next, look at the values that are not yet affected by the line. Choose the smallest value, then use it to subtract the values that are not yet affected by the line, and use it to add the values that are affected by the double line (twice).
7. Is it optimal?
From the results of step 6, have you obtained a zero value for a number of resources?, which is also reflected in the number of rows.
If so, then the assignment problem has been optimized, but if not, then please repeat the 5th solution step.
As a note, the assignment case is considered normal when the number of resources to be assigned and the number of jobs or goals are the same.
For more details, please pay attention to the case study below:
A. Minimization Problem (for normal case)
A company has 4 employees who have to complete 4 different jobs, because of the nature of the work and also the skills and characteristics of each employee, the costs arising from various assignment alternatives for the 4 employees are also different, as seen in the assignment table/matrix below:
| Karyawan | Pekerjaan |
|----------|-----------|----|-----|----|
| | i | ii | iii | iV |
| A | 15 | 20 | 18 | 22 |
| B | 14 | 16 | 21 | 17 |
| C | 25 | 20 | 23 | 20 |
| D | 17 | 18 | 18 | 16 |Note: the values in the table are in rupiah.
From the case study above, the solution steps are:
Step 1
Find the smallest cost for each row, then use it to subtract all costs in the same row. With this step, the result is obtained:
Step 2
Make sure all rows and columns have zero values. And it turns out that in this case there is still a clash or there is still a column that does not have zero, namely column 3. Thus it is necessary to find the smallest value in the column to then be used to reduce all the values in the column. With this step, the results are obtained:
Well, now that every row and column has a value of zero, the next step is,
Step 3
That is, to ensure or check the assignment table, whether it has a zero value that corresponds to the number of resources, which is also reflected in the number of rows.
For example, if 4 employees are assigned, then 4 zero values must be found in different rows and columns. It is better to start from a row that only has one zero value. This step means that each employee can only hold one role / job.
Note! From the matrix above, it turns out that the zero values found in rows 1 and 2, although in different rows but still in the same column, so it can be ascertained that the problem is not optimal and needs to be continued to the next step.
Step 4
Because it is not optimal, the next step is to draw a line connecting at least two zero values, as shown in the table below:
[
From the steps above, it can be seen that three lines were successfully created, leaving several values that were not affected by the lines.
Step 5
Pay attention to the values that have not been touched by the line. Choose the smallest value (from the table above is the value 1), then the value 1 is used to reduce other values that have not been touched by the line, and use it to add the values that are touched by the double line. With this step, the results obtained are:
Note! all values not touched by the line will be reduced by the smallest value (decreased by 1) from those not touched by the line. Meanwhile, the values 5 and 1 in column 1 will increase by the smallest value outside the line (increased by 1).
Step 6
Have zero values been found as many or as many resources? which is also reflected by the number of rows (starting from a row that only has one zero value). And it turns out that the assignment table above has successfully found 4 zero values (a number of employees to be assigned), which are in different rows and columns, meaning that the assignment table above is optimal.
So, conclusions can be drawn:
Karyawan A ditugaskan mengerjakan pekerjaan iii dengan biaya Rp 18,-
Karyawan B ditugaskan mengerjakan pekerjaan i dengan biaya Rp 14,-
Karyawan C ditugaskan mengerjakan pekerjaan ii dengan biaya Rp 20,-
Karyawan D ditugaskan mengerjakan pekerjaan iV dengan biaya Rp 16,-
--------------------------------------------------------------------------------------------------- (+)
Total biaya = Rp.68,-B. Maximization Problem (for normal case)
A company has 5 employees who must complete 5 different jobs, because of the nature of the work and also the skills, characteristics of each employee, the productivity or profits arising from various alternative assignments from the 5 employees are also different, as seen in the following assignment table/matrix:
| Karyawan | Pekerjaan |
|----------|-----------|----|-----|----|----|
| | i | ii | iii | iV | V |
| A | 10 | 12 | 10 | 8 | 15 |
| B | 14 | 10 | 9 | 15 | 13 |
| C | 9 | 8 | 7 | 8 | 12 |
| D | 13 | 15 | 8 | 16 | 11 |
| E | 10 | 13 | 14 | 11 | 17 |Note: the values in the table are in rupiah.
From the case study above, the solution steps are:
Step 1
Find the greatest productivity or profit of each row, then subtract that value from all productivity values in the same row. With this step, the results are obtained:
Step 2
Make sure all rows and columns have zero values, and it turns out that there is still a column that does not have a zero value, namely column 3. Thus, it is necessary to find the smallest value in that column to then be used to reduce all the values in that column, so that the results are obtained:
Well, now that every row and column has a value of zero, the next step is,
Step 3
Ensure or check whether the assignment table has successfully found as many zero values as resources (can be employees, machines, transportation, etc.) which are also reflected by the number of rows. For example, if 5 employees will be assigned, then 5 zero values must be found in different rows and columns. It is better to start from the row that has 1 zero value. This step means that each employee may only be assigned to one job.
Note! From the matrix above, it turns out that zero values are found in rows 1 and 3, although they are in different rows but are still in the same column, so it is certain that this problem is not optimal and needs to be continued to the next step.
Step 4
Draw a line connecting at least two zero values in the assignment table, as shown in the following table or matrix:
From the steps above, it can be seen that 4 lines were successfully created, leaving several values outside the line.
Step 5
Pay attention to the values outside the line! Among these values, choose the smallest (from the matrix above it falls on the value 2), then this value (2) is used to reduce the other values outside the line, and use it to add the values inside the double line. With this step, the following results are obtained:
Note! All values that are not touched by the line will be reduced by the smallest value (2). Meanwhile, the values 2, 5 and 0 in column 5 will increase by 2, because both values are touched by the line twice.
Step 6
Have you now successfully found the number of zero values or as many resources? which is also reflected by the number of rows (starting from the row that only has one zero value, namely the 5th row). From the matrix above, it turns out that 5 zero values have been successfully found in different rows and columns,
From the results above, it can be said that the assignment case has been optimal, with the assignment allocation as follows:
Karyawan A ditugaskan mengerjakan pekerjaan ii dengan biaya Rp 12,-
Karyawan B ditugaskan mengerjakan pekerjaan i dengan biaya Rp 14,-
Karyawan C ditugaskan mengerjakan pekerjaan V dengan biaya Rp 12,-
Karyawan D ditugaskan mengerjakan pekerjaan iV dengan biaya Rp 16,-
Karyawan E ditugaskan mengerjakan pekerjaan iii dengan biaya Rp 14,-
--------------------------------------------------------------------------------------------------- (+)
Total biaya = Rp.68,-However, other alternatives to the above assignment can also be chosen as shown in the matrix below:
Karyawan A ditugaskan mengerjakan pekerjaan V dengan biaya Rp 15,-
Karyawan B ditugaskan mengerjakan pekerjaan iV dengan biaya Rp 15,-
Karyawan C ditugaskan mengerjakan pekerjaan i dengan biaya Rp 9,-
Karyawan D ditugaskan mengerjakan pekerjaan ii dengan biaya Rp 15,-
Karyawan E ditugaskan mengerjakan pekerjaan iii dengan biaya Rp 14,-
--------------------------------------------------------------------------------------------------- (+)
Total biaya = Rp.68,-Thus, it can be concluded that, by using the Hungarian method, the assignment case in the company above can be completed at an optimal cost of Rp. 68,-
Notes:
In practice (daily life), not all assignment problems have a cost or benefit matrix like in the case study above. There are times when an employee cannot be allocated or assigned to a particular job (due to age, gender, skill, physical factors, etc.). Thus, employees with such limitations cannot be forced to do a job that is indeed impossible for them.
To overcome such a thing, then in the process of solving it is necessary to add a very large number, and called the number M (for minimization problems) and -M (for maximization problems). The next solution process can be done in the same way as in the case of normal assignments, only in the optimal decision will be avoided assigning employees to tasks that have the number M or -M.
Reference:
Operations Research Module, CHAPTER IV "Assignment Problems", compiled by Minawarti, ST.
Netizens
Comment 1
ZUL FAHMI 20 Dec 2017, 20:54:00 Sorry, in the second question, it seems that there is a slight error in Column reduction, why is the smallest value taken, while the problem is Maximization. Sorry if I'm wrong
Response 1
hii ZUL FAHMI, thank you for your participation. After we did a cross check again, it seems that there is nothing wrong. Actually, the difference between max and min in the Hungarian method is in step no. 2, the rest of the steps are the same until the final step. You can pay attention again to the rules of the game in steps 2a. and 2b. that is the theoretical basis that represents the problem solving process.
or if you feel unsatisfied, you can include a capture of the section in question and attach it to this comment using the shortcode syntax instructions.