Question

A company is faced with the problem of assigning six different machines

to five different jobs. The costs are estimated as follows in hundreds of

rupees. Assign the jobs to machines to minimize the total cost.

If the given matrix happens to be returns to the company by assigning a

particular job to a machine, then what will be the assignment? Will the

same assignment hold well? If not what will you do to get the new

solution. Also explain is traveling salesman problem an assignment

problem? If yes how? If not what are the differences between

assignment problem and traveling salesman problem.

Answer 1

a) In part a) these values are considered as a cost. Hence, the assignment problem is a minimization problem. We solve the given assignment problem in Excel as shown below. Since no. of Machines > No. of Jobs, there will be "<=" sign in case of constraint for no. of machines assigned.

Machines / Jobs 1 3 4 5 N M/C to assign 1 Actual assigned 1 0 0 1 1 2 0 1 1 0 0 0 0 3 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 4 1 o 1 1 1 0 0 0 0 5 6 1 0 0 0 0 1 1 1 1 1 1 Max. Jobs to be assigned Actual Assigned Total 20 1 1 1 1 1 Machines / Jobs 3 4 5 1 6 1 1 1.5 7 3 N 1 2.5 2 3 3.3 4 6 2 5 5 6.5 7 7 3 2 8 3 4 2 9 4.5 3 9 5 6 6 6 9 5 10

The assignment is shown in blue in the top table above.

The above solution in the form of formulas along with Excel Solver extract is shown below for better understanding and reference:

А - B с D E F G Н J K L M Machines / Jobs M/C to assign Actual assigned Solver Parameters 1 2 3 4 5 1 1 Set Objective: $H$8 1 1 =SUM(B2:F2) =SUM(B3:F3) =SUM(B4:F4) =SUM(B5:F5) =SUM(B6:F6) =SUM(B7:F7) To: Max O Min O Value of: 1 1 1 By Changing Variable Cells: $B$2:$F$7 1 Total =SUMPRODUCT(B2:F7,B12:F17) Subject to the constraints: $B$2:$F$7 = binary $B$9:$F$9 = $B$8:$F$8 $H$2:$H$7 <= $G$2:$G$7 Add Change Delete 2 1 0 0 0 0 1 32 0 1 0 0 0 4 3 0 0 O 1 0 5 4 0 0 1 0 0 6 5 1 0 0 0 0 7 6 0 0 0 0 0 Max. Jobs to be 8 assigned 1 1 1 9 Actual Assigned =SUM(B2:B7) =SUM(C2:07) =SUM(D2:07) =SUM(E2:E7) ESUM(F2:F7) 10 11 Machines / Jobs 1 2 3 4 5 12 1 2.5 5 1 6 1 13 2 2 5 1.5 7 3 14 3 3 6.5 2 8 3 15 4 3.3 7 2 9 4.5 16 5 4 7 3 9 6 17 6 6 9 5 10 6 18 19 20 21 22 23 24 25 26 27 Reset All Inna Load/Save Make Unconstrained variables Non-Negative Select a Solving Method: Simplex LP Options Solving Method Select the GRG Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth Help Solve Close

b) In part b), the values are considered as a return. We have to maximize the total return. Hence, the assignment problem becomes a maximization problem. The assignment in minimization problem above will change completely. The new solution is as follows:

Machines / Jobs 1 2 3 4 5 M/C to assign 1 1 0 0 0 0 0 0 0 Actual assigned 0 1 1 1 2 0 1 3 0 0 1 0 0 0 1 0 1 0 0 4 0 0 1 1 5 0 0 0 1 1 1 1 0 0 0 0 1 1 6 Max. Jobs to be assigned Actual Assigned 1 1 1 1 1 Total 29 1 1 1 1 1 4 5 Machines / Jobs 1 2 1 2 5 5 6.5 6 7 3 1 2.5 2 3 3.3 4 6 3 1 1.5 2 2 3 3 8 3 4 7 9 4.5 5 7 9 6 6 9 5 10 6

The optimum assignment is shown in blue above.

The formulas in excel remain the same. The only change will be in Solver, where the objective will be maximization. The above solution in the form of formulas along with Excel Solver extract is shown below for better understanding and reference:

А B с D E F H - K L M G M/C to assign Machines / Jobs Actual assigned Solver Parameters Х 1 1 2 3 4 5 0 0 0 0 0 1 2 1 32 0 0 1 0 0 1 Set objective: $H$8 4 3 0 1 0 0 0 1 =SUM(B2:F2) =SUM(B3:F3) =SUM(B4:F4) =SUM(B5:F5) =SUM(B6:F6) =SUM(B7:F7) To: Max O Min O Value of: 5 4 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 0 By Changing Variable Cells: $B$2:$F$7 0 1 Total 1 1 1 1 =SUM(B2:B7) =SUM(C2:07) =SUM(D2:07) =SUM(E2:E7) =SUM(F2:F7) =SUMPRODUCT(B2:F7,B12:F17) Subject to the Constraints: $B$2:$F$7 = binary $B$9:$F$9 = $B$8:$F$8 $H$2:$H$7 <= $G$2:$G$7 Add 1 2 3 4 5 Change 2.5 5 1 6 1 Delete 2 5 1.5 7 3 3 2 8 3 Reset All 3.3 2 9 4.5 6 5 7 6 Max. Jobs to be 8 assigned 9 Actual Assigned 10 11 Machines / Jobs 12 1 13 2 14 3 15 4 16 5 17 6 18 19 20 21 22 23 24 25 26 27 6.5 7 7 9 4 3 6 9 10 Load/Save 6 5 6 Make Unconstrained variables Non-Negative Select a Solving Method: Simplex LP Options Solving Method Select the GRG Nonlinear engine for Solver problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems, and select the Evolutionary engine for Solver problems that are non-smooth. Help Solve Close

-----------------------------------------------------------------------------------------------------------------------

In case of any doubt, please ask through the comment section before Upvote/downvote.

If you liked the answer, please give an upvote. This will be quite encouraging for me, thank-you!!!