# Transform an assignment problem to use the Hungarian algorithm

I have this assignement problem:

There are three machines to perform four tasks. The costs of assigning to a machine each of the tasks are given by the following matrix:

$$\begin{pmatrix} 2 & 6 & 4 & 4\\ 3&4&4&3\\ 2&5&6&5 \end{pmatrix}$$ $a)$ Determine an optimal assignement assuming that each machine must perform exactly one task and therefore, one of the tasks will not be performed.

$b)$ determine an optimal assigement assuming that each machine can perform at the most two tasks and that every task must be performed.

So far, the assignement problems I've been asked to solve have a square matrix as the cost matrix, and each agent was required to perform exactly one task in a way that all tasks were performed and I would use the Hungarian algorithm to solve them. However, the algorithm works only for $n \times n$ matrix and I don't know how to proceed. So my question is:

How do I transform this problem so I can use the Hungarian Algorithm to solve it?

• @Paul Thank you! So when the algorithm stops (the number of lines covering the zeros is equal to the number of rows), in the first problem I need to consider the row with costs of $0$ to construct the matching. But in the second problem I don't how adding a column with costs of 0 solves it. Since I can make a machine perform two tasks, wouldn't the same argument (adding a $0$ row) work too? I just need to mark two zeros on a single row so that each $0$ is in a different column, right? – user313212 May 16 '16 at 18:06
• @Paul If I add only one row, I get a $4 \times 4$ matrix, and then each machine performs exactly one task. But I need a machine to perform two tasks so that the other two machines perform exactly one. So I add a new row and a new column to get a $5 \times 5$ matrix. But I can't see why I must add a new row... – user313212 May 17 '16 at 16:01