Luckily, there is a great formula for figuring this type of problem out.
I’m going to be using something called the Hungarian Method.
After completing step 2 we can see that each row and each column have a zero, which leaves us with the challenge of allocating the appropriate jobs to each contractor.
From here, we’ll select only row or column values of zero.
In deciding between Flooring or Painting for Susan, we can see that if we select Flooring for Susan, we eliminate row 4, which leaves us with no alternative zero for column 1.
With that, the only possible solution is Diego for Flooring and Susan for Painting, allowing us to pick a zero for each row and column.This would be more beneficial in two ways: By using this strategy, we would minimize our time, by spreading the work over 4 contractors, but we also minimize our cost, by hiring contractors per repair item.Despite how simple this may appear, it could get quite difficult to calculate if we had a much larger pool of contractors to choose from, or had many more repairs to consider.The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods.It was developed and published in 1955 by Harold Kuhn, who gave the name “Hungarian method” because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.However, another solution might be to break down what we need done into individual items.Then we could get prices from our contractors per repair item.The minimum row value represents the minimum price we will have to pay each contractor, and similarly, setting it to zero allows us to subtract it from the other values in the row.Let’s take a look at how this method could be applied to our current problem: Here, we can see that each column has a zero.Here, I’ve updated column 1, subtracting the lowest value, 70, from the remaining column values, leaving us with 15, 30, and 80: Now, we’ll notice that each column contains a zero.However, only rows 1, 3 and 4 have a zero, with row for having 2 of them. We cycle through the rows now, and convert the lowest value in each row to a zero, only if the row doesn’t currently have a zero.