Question

This Question: 2 pts 52 of 64 (63 complete) This Test: 100 pts pos The Green Cab Company has a taxi waiting at each of four cabstands in Evanston, Illinois. Four customers have called and requested serv The distances, in miles, from the waiting taxis to the customers are given in the following table. Customer B C Cab Site Stand 1 Stand 2 Stand 3 Stand 4 O AWD AN The optimal assignment of taxis to customers that minimizes the distance is: Customer A Customer B Customer C Customer D The cumulative distance of the optimal assignment of taxis to customers = miles (enter your response as a whole number).

Answer 1

D Hungarian Method Cab site A Stand 1 5 Stand 2 3 Stand 3 4 Stand 4 6 Customer B C 1 2 2 4 5 1 4 5 mto 3 4 2 Row reduction - Subtract the smallest element in each row from every element in that row A B C D Stand 1 4 0 1 5 Stand 2 1 0 2 1 Stand 3 0 1 3 0 Stand 4 4 2 3 0 Column reduction - Subtract the smallest element in each column from every element in that column A B C D Stand 1 4 0 0 5 Stand 2 1 0 1 1 Stand 3 0 1 2 0 Stand 4 4 2 2 0 Now we test whether it is possible to make an assignment using only zero distances. (a) Starting with row 1 of the matrix, we examine rows one by one until a row containing exactly single zero elements are found. We make an experimental assignment to that cell. Then we cross all other zeros in the column in which the assignment was made. (b) When the set of rows has been completely examined an identical procedure is applied successively to columns. Starting with Column 1, we examine columns until a column containing exactly one remaining zero is found. We make an experimental assignment in that position and cross other zeros in the row in which the assignment was made. It is found that no additional assignments are possible. Thus, we have the complete Zero assignment A B C D 4 Stand 1 Stand 2 Stand 3 Stand 4 1 0 4 0 1 2 1 2 2 1 0

Optimal assignment of taxis to customers

Customer	Cab Site	Distance
Customer A	Stand 3	4
Customer B	Stand 2	2
Customer C	Stand 1	2
Customer D	Stand 4	2
Cumulative distance		10