Consider a computer-controlled factory where a CAM system automatically routes jobs through their next processing step. Several different workstations might be able to perform the needed operation. However, these workstations differ in location, and might also differ in the amount of processing time they require for the job. The CAM system currently is considering assigning 6 jobs to 6 available workstations. We assume that each job can be assigned to only one workstation, and that each workstation can only handle one job. Table 1 describes the transportation and processing times needed to perform the next processing step of each of the identified jobs. In this table, "-" is used to represent the fact that the next processing step of the job cannot be performed by the corresponding workstation. Workstations (1) Jobs (0) 1 2 3 4 5 6 1 20 15 10 2 10 18 20 3 4 14 13 5 4 9 9 14 5 8 12 6 6 14 4 Table 1: Data for assignment problem Clearly, 12 this problem can be formulated as the following integer program: min tijd i=1 j=1 6 (P) s.t. Wij = 1, Vj = 1,...,6 i=1 6 tij = 1, Vi = 1,...6 j=1 Bij > 0 Tij EZ, Vi, j = 1,...,6 Vi, j = 1,...,6 1. In the above model, describe the meaning of variable Xij, and of the parameter tije 2. Apply the Hungarian algorithm to solve the problem. Report the different steps of the algorithm. 3. Write down the dual problem to (P) assuming that all variables are continuous. 4. Verify that the solution (uy) where u1 = 7,u2 = 9,43 = 4,24 = 9,u5 = -1,45 = 8 and v1 = 11,va = 1,63 = -3,74 = 0,V5 = -2,V6 = 5 is feasible for the dual of (P) (where u are dual variables on the first set of constraints, and v are dual variables on the second set of constraints). Is this solution optimal for the dual