Linear Programming Ignore the Solver part of the questions I

Linear Programming

-Ignore the Solver part of the questions. I will have to try and figure that out on my own.

Thank you for any assistance!

Solution

The assignment problem is a linear programming problem .The assignment problem has the property that when you solve the problem ignoring the integer constraints you still get integer solutions. This means that the simplex algorithm solves assignment problems. One of the algorithms, called the Hungarian method to solve assignment problem.Below are the steps to solve the above problem :

Step 1 : Original Matrix

This array describes an assignment problem with three people (labeled A, B and C) and four jobs (1, 2, 3, 4,5,6). The first person has a cost 3 if assigned to the first job; a cost 2 if assigned to the second job; etc. The goal is to assign people to jobs in a way that minimizes total cost.

The algorithm uses a simple observation and one trick. The observation is that you can subtract a constant from any row or column without changing the solution to the problem. Take the first row (the costs associated with A). All of these numbers are at least two. Since you must assign person A to some job, you must pay at least two no matter what. If you\'d like, think of that as a fixed cost and further costs as variable costs depending on the job assigned to the first person. Hence if I reduce all of the entries in the first row by two, I do not change the optimal assignment (I lower the total cost by two). Doing so leaves this table:

I\'m not done using this observation yet. Just as I can subtract a constant from any row, I can subtract a constant from any column. Take the first column. It says that no matter who you assign to the second job, it will cost at least 1. Treat the 1 as a fixed cost and subtract it. Since it cannot be avoided it does not influence your solution (it does influence the value of the solution). Once you make this reduction you get:

This is the end of what we can do with the simple observation. Now it is time to use the observation. The last table is simpler that the original one. It has the property that there is a zero in every row and in every column. All of the entries are non-negative. Since you want to find an assignment that minimizes total cost, it would be ideal if you could nd an assignment that only pairs people to jobs when the associated cost is zero. Keep this in mind: The goal of the computation is to write the table in a way that is equivalent (has the same solution) as the original problem and has a zero-cost assignment. I have just finished the step in which you reduce the costs so that there is at least one zero in  every row and every column.

The beauty of this table is that it again is non-negative. It turns out that using this matrix it is possible to make another minimum cost assignment. In fact, using this table, we can come up with an optimal assignment with cost zero. It agrees with our intuition (A to 1; B to 2; C to 3; D to 6). You can go back to the original matrix of costs to figure out what the total cost is: 12=3+3+6.