‘An Assignment Model is a probl costs/profits in such a vray thay at Sequites Pairing two sets of items given a set of pa ved. It was developed ang ornat, tne total cost/profit of the pairings is minimized or pe ician in 1955, Ped and published by Harold Kuhn (1925-2014) who was an American ae ‘ho gave the name "Hungarian method” because the algorithm was iangelY ean ae ee of two Hungarians mathematicians: Dénes K6nig (1884-1944) cH eeeticcin| 8 mathematician and Jend Egervary (1891-1958) was a Hungarian Hungarian Method ox Flood’s Technique is an algorithm used to determine an optimal solution to an assignment problem. The method is named after a Hungarian mathematician, : pénes Kénig. He proved a theorem required of the development of Hungarian method. The Hungarian method yields optimal solutions to the assignment model. The method is based on a zathematically proven algorithm for determining the optimal solution. ‘The Hungarian method is based on the concept of opportunity losses. This is related on the opportunity losses in the Vogels’ Approximation Method of the transportation problem. In the assignment model, the optimal solution gives zero opportunity losses. Any other solution with a higher cost gives an opportunity loss that is equivalent to its increase in cost over the minimum. cost resulted in the optimal solution. The basic idea in this method is to avoid opportunity losses. The assignment problem is a special case of transportation problem in which the objective is to assign a number of origins to the equal number of destinations at the minimum cost (or maximum profit). It involves assignment of people.to projects, jobs to machines, workers to jobs and teachers to classes etc., while minimizing the total assignment costs (or maximizing the total assignment profit). One of the important characteristics of assignment problem is that only one jab (or worker) is assigned to one machine (or project). Hence, the number of sources are equal the number of destinations and each requirement and capacity value is exactly one unit. A. Some Applications of Assignment Model Though assignment problem finds applicability in various diverse business situations, such 2 (a) in assigning machines to factory orders; (b) in assigning sales/marketing people to sales teritories; (c) in assigning contracts to bidders by systematic bid-evaluation; (d) in assigning teachers to classes; (e) in assigning accountants to accounts of the clients; and much more. There are simple steps to follow for the execution of the Hungarian Method as shown below: « Steps in Solving Assignment Model using Hungarian Method | 1 Determine the opportunity cost table. | a Subtract the lowest entry in each row/column of the given cost table from all entries in| that row/column for minimization problem. For maximization problem subtract each | entry in the row/column from the highest entry in each row/column. | . Subtract the lowest entry in each column/row of the table obtained in part from all | numbers in that column/row. 2 Determine whether an optimal assignment can be made. The procedure is to draw straight | lines (vertically and horizontally), using the least number of lines possible. (This can be | by covering first the row/column with the most number of imal | Santer 6; Assignment Model Page 217y assignment can be made when the number of lines equals the number of rows/columy. the number of lines drawn is fewer than the number of rows/columns, an Pty assignment cannot be made and the problem is not solved. 3. Revise the total opportunity-cost table. a. Select the smallest value of the uncovered line row/column and subtract this Dungy from all numbers not covered by a straight line. b. Add this same number to the numbers lying at the intersection of any two lines. ©. Copy the entries covered by a single line, then return to step 2._ Let us consider the example below to illustrate the solution of an assignment mod, minimization problem. Example: A plant has 4 operators to be assigned to four machines. The time (in minutes) requiy by each operator to produce a product on each machine is shown below. Machine Operator . ec 5 1 n_| 2 | 10 9 2 io | 5 7 3 n | “4 | 2 | 13 4 9 5 | 8 i Determine the optimal operator-machine assignment and compute for the total minimum time. Solution: In order to solve an assignment model it is necessary to follow the following steps. We ma apply a row reduction first or even start with a column reduction. In this particular example will apply a row reduction before a column reduction. Step 7: Identify the lowest value in each row and subtract it in each row from all va! appearing in that row. This will ensure a zero entry in each row of the tableau. We hat identified lowest values in each row: for the first row is 9, second row is 5, and third 1 is 11, and fourth row is 8. Tableau 1 Machine Row Operator a B Cc D Reducer 1 Et 12 10 9 9 2 8 10 5 7 & 3 n |. 12 13 n L 4 9 15 8 il 8 We can now subtract each of the lowest values of each row to every entries of each ™ as shown below. Page 218 Chapter 6: Assignment Mo! |asignment TABLEAU With ROW Reductions Tableau? Operator |} ml nfo fe fr |> w|r|rlolo} eo fro g,Select the minimum entry in each column and subtract it from every entry in that column. We have identified lowest entries column is 3, and third column is 0, the lowest values of in each column: for the first column is 0, second and fourth column is 0. We can now subtract each of each column to every entries of each column as shown below. tte Assignment Tableau with Column Reductions wien - Tableau 3 Machine hine Operator Operator Machin A B. c D A[s|[c {op eat 1 2 [0]|1 0 [2 > 2 3 [2 [0 2 3 3 0 0 1 2 L4 4 1 [4 0 3 Column Reducer 6p Determine if four unique assignments exist in Tableau 3 by drawing the minimum number of horizontal or vertical lines necessary to cross out all zeros through the rows and columns of the tableau. (This can be done covering first the row or column having the most number of zero entries.) The Opportunity Cost Tableau with the Line Test Tableau 3 : | Operator A Machin D 2 3 2 2 4 1 4 3 The three lines indicate that there are only three unique assignments, whereas four are "equired for an optimal solution since it is a 4 x 4 matrix. ter Gs Acs —— 6: Assignment Model Page 219Step 4 Identify the minimum value, which is 1. Tableau 3 Operator | — Mocs D | F 3 2 2 | 4 i 4 [3 | 8tep 5: Subtract 1 from all values in Tableau 3 that is not crossed out. Then add 1 to cells wig) intersecting lines intersect, and copy the rest of the values in the previous tablea) covered by a single line. Tableau 4 Tableau 4 : Machine Machine Operator a 5 a 5 Operaten [a Bc]. 1 2 0 +1 0 1 2 0 210 2 3-1 2-1 0 2-1 |> 2 2 1 0 1 3 0 0 1+1 2 3 0 0 2 [2 4 1-1 4-1 0 3-1 4 0 3 0 2 : Apply the line test again to determine if an optimal solution already exists. : The Second Iteration: The Opportunity Cost Tableau with the Line Test Tableau 4 Operator fachine A S D No matter how the lines are drawn, it will cover all zero entries using the least number! lines. Four lines are required to cross out all the zero entries. This indicates that the fou" unique assignments can be made and that an optimal solution has been reached. &tep 7: Identify the rows with zero entries in their respective columns, Operator [ Machine | Order of Assignment [Operator | Machine 1 B,D Fourth > 1 D 2 Cc First > 2 c 3 AB Third > 3 B 4 AC Second > 4 A~» Notice that row 2 has only 1 zero entry and the rest have two zero entries. In general We will select the least zero entry forthe first allocation. Then, allocate the rest of the rows t© complete the assignment, The first assignment is to assign Operator 2 to Machine C; the second is to assign Operator 4 to Machine A; the third is to assign Operator 3 to Machine B; and lastly to assign Operator 1 to Machine D. up % Make the assignments from the last tableau, [Operator | Machine | Time (in minutes) 1 D 9 2 c 5 3 B 4 4 A 9 L Total 37 The assignment distribution shown resulted to the most efficient distribution of job assignments of operators to machines | # Enrichment Exercise 6.2 ‘A municipal government wants to improve the efficiency of the local court system. It has} “collected data on the average length of time a particular judge requires to handle each type of| case. Given the composition of the types of cases scheduled on each docket (the official! | schedule of proceedings in lawsuits pending in a court of law), the times shown in the table| | rere estimated for each judge to process each different docket. Determine the assignment of| | judges to dockets to minimize the time required to complete all dockets. | Cn ee] | | | Judge x BTC D | | i | T B [7 | a @ | 2 20 | 15 | 15 15 | FZ is [a | ie | | 25 . copy es a] 7 19 ts 5 15 18 20 13 \ There is a slight difference between the solution set of a minimization problem and | ‘naximization problem, the difference is selecting the highest value in each row or column on the ! ital tableau. The rest of the procedure is the same with the Hungarian Method in minimization Problem. This section illustrates the solution of an assignment model in maximization problem. \ Sample: MSS Car Rental Agency plans to purchase five new automobiles to replace five older, | Whicles, The older vehicles ‘are to be sold at auction. The agency has solicited from five "dividuals, each of whom wishes to buy only one vehicle but has agreed to make a sealed bid on ‘ch of the five. The bids are as follows in terms of (P10,000): ; i, — 4LL Automobile = [Toyota | Mitsubishi | Ford Nise tz ia [12 20 10 2 [10 13, in 9 “ 5 6 “10 7 B 9 7 10 9 10 4 12 10 6 The agency wishes to determine which bid to accept from each of the five a 50 that each y them can buy one vehicle while the total of the five accepted bids is a maximum. Solution: Before we start the solution set, we will replace the names of the sutcmmobiles by A,B, So, and E for Toyota, Mitsubishi, Ford, Nissan, and Mazda, respectively for computation convenience on the application of the Hungarian method. Automobile Buyer AB ci[p/E 1 12_| 20 | 10 | 8 Zz 2 10 13 1 9 14 3 5 6 | wl 7 5 4 9 7 | wl[o [un 5 io | 14 | 12 | 10 | 6 In order to solve an assignment model itis necessary to follow the following steps. ‘tp 7: Identity the highest value in each row. Then, subtract each row value from the highs values, This will ensure a zero entry in each row of the tableau, Tableau Buyer Automobile Row Als C [TD] E | Reducer 1 122 | 20 | 10 8 7 20 2 {10 [3 [at [9 a4 4 - 4 9{7 09s Tn 1 5_| 10 | 14 | 12 [a0 1-6 14 The Assignment Tableau with Row Reductions Tableau 2 Tableau: = Automobile i . : = . ; Buyer | —__— Automobile ; A_[ 20-12 | 20-20 [20-10 | 30-8 | 30-7 1 8 ji Te 3 2 {14-10 [14-13 [44-17 | taco i414) | ste o 3_| 10-5 | 10-6 [20-70 | qo=7 10-5 3° [sla +t 3 4 {uno [ -7 [at-10 as ary 4 [2Ta rh wet 5_| 14-10 [14-14 [aa=19 [tant 14-6 | 5 4 To > i 8 4 Page 222 Chapter 6: Assignment Model ee2, Select the minimum en tr or Y in each column and subtract it from every entry in that column. Tableau 3 y Buyer a Automobile 1 8 B ¢ D E 2 a jo | 12 | 13 4p t's 5 | 0 p35 | 4 | 0 3 [5 : 2 A 2 0 - eee ome 2 4 8 ‘Column 2 a 0 2 0 The Assignment Tableau with Column Reductions Tableau 3 Tableau. fe ‘Automobile _ Automobile A B ce D yer [A TB [c|[DIE 1 8-2 | 0-0 | 10-0 | 12-2 | 13-0 1 6 0 10 10 13 2 4-2 1-0 3-0 5-2 o-0 |> 2 2 1 3 3 oO 3 5-2 | 4-0 0-0 3-2 5-0 3 3 4 0 1 5 4 2-2 | 4-0 1-0 2-2 0-0 4 0 4 z o 0 5 4-2 | 0-0 2-0 4-2 8-0 5 2 o 2 2 8 Susp 3: Determine if five uniqui number of horizontal or vertical lines necessary to cross and columns of the The Opportunity Profit Tableau Tableau 3 tableau. Buyer 2 ‘The four lines indi required for an opti 8% ¢, Identify the minimum value, icate that t mal solution. which is 1- Chapter 6: Assignment Model with the Line Test here are only four unique assi 1e assignments exists in Tableau 3 by drawing the minimum out all zeros through the rows ignments, whereas five are Page 223 wa waTableau 3 ‘Autofhobile Buyer | a . 1 6 10 2 [2 3 3 3 1 5 [2 2 Step 6: Subtract 1 from all values in Tableau 3 that is not crossed out. Then add 1 to cells wig intersecting lines, and copy the rest of the values in Tableau 3 covered by a single line, Tableau 4 Tableau 4 i ‘Automobile ] Buyer [“a_[ 8 eT E Buyer "a |B] c[ODTE 1 [6-1] 0 | 10 13 1 5 | o0]0]9 | = 2-1 1 3 0 = 2 1 1 3 2 Oo 3_|3-1, 4 | 0 5 3 2,4 ]/ofo]s) 4 0 [4+ifi+i] 0 [ori 4 o}s)]2fo]1 5 |2-1| 0 | 2 [2-1] 8 5 1/o[2lils Step 6: Apply the line test again to determine if an optimal solution already exists. ‘The Second Iteration: The Opportunity Profit Tableau with the Line Test Tableau 4 Buyer Automobile A c | D 1 5 1o_| 9 2: )1 3 2 5 il 2 1 There are only four lines which indicate only four unique assignments in Tableau 4 whereas we need five lines for an optimal solution. Thus, we will return to step 4. Otep 4: Identify the minimum value, which is 1. Tableau 4 : Buyer Automobile A c 1 5 10 9 2 i 3_[ 2 5 1 2 1 Se Page 224, Subtract 1 from all valu OF otersecting lines, and = es 4 that is not crossed out. Then add 1 to cells with 'Y the rest of the values in Tableau 4 covered by a single line, soneae ‘Automobile pye [a Tey c To Buyer ‘Automobile 71 5-1 [0 [ao-i pe x ALBlcl]DIE 1-1 1 ia ppt ea Po = 4 ots ts a o [5e1| 2 4 54+i 3 2[s5 [olfol|e ks f1-1[ 0° [2-17 ug 4 o |6 |2)]o|2 U—— =1| 8 5 ofol[i{fol|e 6: Apply the line test agai ined isp & Apply again to determine if an optimal solution already exists. Thi ion The Third Iteration: The Opportunity Profit Tableau with the Line Test Tableaa 5 Automobile Buyer 7m A clTDp]eE Hl 4 9 | 8 [13 We already made use of five lines to cover the zero entries in Tableau 5, thus this indicates that the optimal solution has been reached. {xp 7: Identify the rows with zero entries in their respective columns. Notice that Row 1 has only one zero entry, therefore we will select Row 1 for the first allocation. Then allocate the rest of the rows to complete the assignment. [Bayer [Automobile ] Order of Assignment [ Buyer _| Automobile { 1 |B First> [1 B 2 |AE Second>| 2 E 3 |cD Third>| 3 c 4 |AD Fourth>| 4 A 5 |ABD Fifth > |_5 D Sip & Make the assignments from the last tableau. Buyer | Automobile | Arhount 1 B—Mitsubishi | 200,000 2 E- Mazda 140,000 3 C-Ford a 4 A-Toyota » 90, 5 D- Nissan 100,000 Total P630,000 ‘hapter 6: Assignment Model Page 225The assignment distribution shown resulted to the most efficient assignments of buy, to automobiles. Alternative Optimal Solution: Buyer | Automobile | Order of Assignment | Buyer _| Automobile 1 |B First> | 1 B 2 |AE Second-+| 2 E 3 |coD Third> | 3 c 4 |A,D Fifth > 4 D, 5 |ABD Fourth > |_5 A Buyer | Automobile | Amount 1 B-Mitsubishi | P200,000 2 E-Mazda 140,000 3 C-Ford 100,000 4 D-Nissan P 100,000 5___| A-Toyota- P 90,000 Total 630,000 Notice that instead of assigning Buyer 4 to Automobile A and Buyer 5 to Automobile wwe made some re-assignment from Buyer 4 to Automobile D and Buyer 5 to Automobi A. Stil it will generate the same amount of P630,000. Page 226is section Will Tlusnee eae Probie lustrate ho Ww inimization problem. A du, to deal with unbalanced assignment model particularly a i my ro one relationship for an assignment Se column is being added to satisfy the one-to- , dummy will To understand it clearly let us see the exampl 7 ae tre eae imple, Cab Customer A | B c D E FE ut 7 | 5 8 2 [3/6 2 2 1 7 5 3 2 2 4 5 6 2 5 4 4 wo | 6 5 4 [8 3 5 7 | 6 5 5 [4 4 Determine the optimal assignments) that will minimize the total distance traveled. Solution: In order to solve an assignment model it is necessary to follow the following steps. typ 1: Introduce a dummy row to balance the number of rows and columns, since there are six columns and 5 rows to make it even to six-to-six. Tableau Customer Cab A | B c D E F 1 7 | 5 8 2 [3 6 2 2 1 7 5s | 3 | 2 3 4) 5 6 2 5 | 4 4 wo | 6 5 a S J 3 7 6 5 5 4 4 Dummy [0 | 0 0 0 o Lo 8p 2:Select the minimum entry in each row and subtract it from every entry in that row. ! ‘Customer Row Cab A Tec [DE] FE | Reducer T 7 5 8 2 3 6 2 2 7 p1[7{[st32 ; 3 aps fe t2{si4 ; 2 4 w fo |s{4}s 2 4 5 Z o fs {st 0 0 Dummy | o | o | % o 10 Page 227 hapter 6; Assignment Model-Customer. o-0 | 0-0 | 0-0 | 0-0 0-0 0-0 Cab The Assignment Tableau with Row Reductions 2 3 4 Step 3: Select the minimum entry in each column & subtract it from every entry in that colum, Customer: 0 Cab Tableau 2 Dummy 0 Column Reducer ductions The Assignment Tableau with Column Re Tableau 3 Tableaa3 “-s-- Customer alalo olefo < nolo 3 “P| . = oJefefeelo j af T/9/9/ 91 7/5 # +He[[[4) 2 fe elefelefafo] » F 18 wf T/TIS/SIS/T] B a afeymlwlofol 3 § olelelolelel 2 2 foltTUT19/9] BB BPlslafefAptls} o g| €. 8 z elelele| so Tattoo gly slaftjo] 2 2 2 elololo] & 0 ilait{t] a. B ofolals] 2 Bel 28 § elo] 2D < a) & 2 ole] < BS ¥ 2 8 a HirEPE &Notice that there 7 Aare only five ines, whereas six are required for an optimal solution. , Identify the mini on 5; Identify the minimum value, which is 1 Tableau 3 | cab {ep 6 Subtract 1 from all values in Tableau 3 that is not crossed out. Then add 1 to cells with intersecting lines, a ind copy the rest of the values in Tableau 3 covered by a single line. ‘anioan 4 Tableau low ‘Customer Cm \*Ta Te [clp]TelFr STayetc [pele fiis-1[3 [e-a[0 [1 [4 tlaf3{sfoli1|4 {2 fi-i1] 0 [o-i] 4 2 1 2tovto{s {a {2a [3 [2-1] 3 [4-1] 0 3 2|>[3 Tilt3aft3sfofs {2 [4 [o-1[ 3 [2-1] 7 5 o 4tol{3fififtsto 5 [3-1[ 2 [1-1] 7 0 o s [2{2fofiltoto | p] o [o+r] o [o+1 [o+i [o+r Di] Rosfeaaftos{ apa ae {%p 7: Apply the line test again to determine if an optimal solution already exists. The Second Iteration: The Opportunity Profit Tableau with the Line Test Tableau Cust cab A B ic E 1 4 3 5 1 } 3 1 3 3 3 4 3 1 5 There are only five lines which indicate five unique assignments in Tableau 4, whereas we need six for an optimal solution. Thus, we will return to step 5. 8496: Identify the minimum value, which is 1-Tableau 4 Cust b cl A B c B 1 4 3 5 1 3 i 3 e 4 6 3 1 . Step 6: Subtract 1 from all values in Tableau 4 that is not crossed out. Then aa Lito cals intersecting lines, and copy the rest of the values in Tableau 4 covered Py a single ling Tableau 5 - Tableau5 Cistimner b ‘Customer @CaTs Te] p Let Cb TA TB. CI]DIEI? 1_| 4-1] 3-1|5-1] o [1-1] 4 1 3 [2] 4 0 olg 2 0 0 5 [4+1] 2 [1+1]/>|2 [o ]o| 5 5 [2 [7 3_[1-1]3-1 [3-17 0 10) m2. 3 ,o{2]/2][o]{212 4 |6-1/3-1/i-1| 1 -1/ 0 4{/5{[2]o0]1]4[o 5 | 2 [2 [oo [asi] o [ort 5 }2{2]/o0 [201 D o 1 oO 1+1 1 1+1 D 0 1 0 2 1 2 Step 7: Apply the line test again to determine if an optimal solution already exists. The Third Iteration: The Opportunity Profit Tableau with the Line Test Tableau 5 ear stom: Bi F 1 2 4 3 2 2 2 1 Dummy 1 I No matter how the lines are drawn in Tableau 5, we will need at least six lines to o°8 out all the zero entries. This indicates that the six uni 5 i that an optimal solution has been reached, ‘Que assignments can be made rep & Identify the rows with zero entries in their respective columne Then allocate the rest of the rows to complete the assignment. : . ignment. Cab [Customer] Order of Assignment os 1 DE Third —» ' Customer 2 |AB Teele i DI 3. |AD Fourth c e : g ; Second -> 4 x Dumay | A.C Sixth 5 bs Fith > |_Dummy gE Chapter 6: Assignment oHthat all rows have 2 ze, oneness 70 entries but we can only allocat Column B. Then asocate the ain “ssignments using elimination method. See Row 2 gop * Make the assignments from the last tableau. Cab Customer | Di ti i " oP See istance (in km) 2 B ; 3 A 4 4 Ff 3 5 E 4 Dummy Cc 0 Total “4 Alternative Optimal Solution: Cab Customer. Order of Assignment Cab Customer 1 DE Third + 1 E 2 AB . First > 2 B 3 AD Fourth > 3 D 4 GF Second -> 4 F 5 GE Fifth > 5 c Dummy | A.C Sixth > |_Dummy A Cab_| Customer | Distance (in km) 1 E 3 2 B 1 3 D 2 4 F 3 5 c 5 Dummy, A o Total 14 | 7 enrichment Exercise 64 «| The National Bureau of Investigation has five NBI squad-agents available for assignment 9} six cases, The NBI Chief wishes to assign the squads so that the total time to conclude the| ‘ases is minimized. The average number of days, based on past performance, for each squad. tocomplete the case is as follows: | ‘Case Squad }—z B Cc D E | F j i) | 7 | a | i pe 5 | | 36 | 10 | 28 | 12 | | ie) a7 | 10 | [3] 30 | 9 9 | 20 | 26 | 0 5 33) 16 [a8 [8 | is [ai “pte 6: Assignment Model me ye| be effective in certain types of cases, _ by using the Hungarian method. _ In this section it will illustrate how to deal with w maximization problem. A dummy row or dui one relationship for an assignment model. The Example: A high school department head ha levels. All of the teachers have taught the diffe they may be almost u mmy column is < dummy will have zero entries. list and, as noted, whereas one squad may balanced assignment model ; being added to satisfy the one ‘seless in others. Solve the problem, s five teachers to be assigned to four different ye rent year levels in the past & have been evaluate by the students, The rating for each teacher for each year level is given in the following table. Year Level Teacher |~First_| Second | Third’ | Fourth 1 80 75 90 85 2 95 90 90 97 3 85 95 88 91 4 93 2 80 84 5 91 92 93. 88 The department head wants to know the optimal assignment of teachers to year levels that wil | maximize the overall average student evaluation rating. The teacher who is not assigned to tead | _ will be assigned as secretary. Solve this problem using the assignment method. Solution: In order to solve an assignment model it is necessary to follow the following steps. But befot we start the Hungarian method we will represent the year levels by A, B, C, ahd D for Fi Second, Third, and Fourth, respectively. Step 7: Introduce a dummy column to balance the number of rows and columns to 5 x 5 matti Tableau’ Teacher a 5 Year Level £ D | Dumm 1 80 B 90 5 0 ny | 2 95 90 90 97 a 3 85 9% 88. o a 4 93, Bt 80 aa 7 | 5 a1 92 3 a 5 | Step 2: Identify the highest value in each row. Then, subtract each row value from the hi values. This will ensure a zero entry in each row of the tableau. Page 232 i | i 4 Chapter 6: Assignment ModelTeacher |< Yearbevd ———] gy 7 B | cTp Dummy | Reducer 80 [75 [90 asp °0 z 23_| 90 | 90 [97 0 7 ee) ° 5 [1 [92 [93s t—> 3 spe Assignment Tableau with Row Reductions yonan Year Level 2 f vl YearLevel teachet [A B c D_| Dummy Teacher [AT Bc | D | Dummy fa 90-80 | 90-75 | 90-90 | 90-35 90-0 1 io} is |o|s5 wn | oA% a oo 7-97 | 97-0 . 2 7 710 mc =%5 | 95-88 [95-91 | 95-0] = [3 [oto [7 [4] 95 [a] 93-93 [93-91 | 93-80 | 99-84 | 93-0 « fot2}ste iB 33-91 | 93-92 | 93-93 | 93-88 | 93-0 s [2}ifo|s] {tp & Select the minimum entry in each column & subtract it from every entry in that column. Tableau 2 Year Level Teacher [A [8 [| c | D [Dummy 1 10 15 oO 5 90 2 2 7 7 } 97 3 10 oO 7 4 95 4 o 2 13 9 93 5 2/1[o0l[s| 9% ‘ Column «Og ee Reducer Tega Talon 3 Year Level Year Level Inte |p eB Teacher AT BC | D | Damm 1 fi0-0 | 15-0 | 0-0 | 5-0 | 90-9 1 wo {is [o|5 0 2 [2-0 [7-0 | 7-0 [0-0 | 7-9 2 [2|7|7]0o 7 3 Tio 0-0 | 7-0 [4-0] 5-0 |>[ 3 [wlot7|4 3 4 [0-0 | 2-0 | 13-0 | 9-0 | 93-90 4 lol2|nlo| 3 5 2-0 | 1-0 | 0-0 | 5-0 | 3-9 5 2{1ijo0j5 5 q "oper 6: Assignment Model ; Page 233Step 4 Apply the line test for optimality. ‘The Opportunity Value Tableau with the Line Test Tableau 3 Yel Level Teacher } <—— Dammy | [2 2 7 7 ae ee Cos 2 1 3 No matter how the lines are drawn in Tableau 3, at least five lines are required to out all the zero entries. This indicates that the five unique assignments can be made that an optimal solution has been reached. Step 5: Identify the rows with zero entries in their respective columns. Then, allocate the rest the rows to complete the assignment. Teacher | Year Level_] Order of Assignment [ Teacher | Year Level 1 |C Dummy Fifth > 1 Dummy 2 D First > 2 D 3 B Second + 3 B 4 iA Third > 4 A 5 [c Fourth>| 5 c Step 8: Make the assignments from the last tableau, { Teacher | Year Level Rating | | 1 Dummy 0 2 |D-Fouth v7 Thus, Teacher 1 will be 3 B~Second 95 assigned as secretary. | 4 A- First 93 5__|C~-Third 93 { Total 378 | The Human Resource Department has recentl i ly tested seven applicants for six jobs that aff | available at the AUS Call Center Agency. Each job has primary skill, and AUSs cyectve is | se Sh applicants whose aptitude test scores will maximize total performance. Only oM| | (Worker can be assigned to only one job. The aptitude test i Determifé Peretti deplored pt st scores are listed below. Dete Page 234 | Chapter 6; Assignment Mod!This section pastes how to solve degenerate case of assignment model. Degeneracy occurs if one or more destination has some restrictions in their assignment or destination. The next example will give light to the application of degeneracy in assignment model. Example: The WSS pharmaceutical firm has four salespersons, the firm wants to assign to four regions. Given their various previous contracts, the salespersons are able to cover the regions in different amounts of time. The amount of time (in days) required by each salesperson to cover each city is shown below, except for Salesperson 1 who refuse to be assigned in Region B with no time table. Which salesperson should be assigned to each region in order to minimize total time? Identify the total assignment and compute for total minimum time. Solution: typ 1: Select the minimum entry in each row and subtract it from every entry in that row. rion Seren awa a ¢ | D r 7 [| M | 64 | 60 2 54 58 55 52 3 | «4 | 58 | 56 4 70 67 62 60 Note that M is not used in any reduction, nor is any value added to it or subtracted from it during the course of the analysis. Region Salesperson tac Tey 1 7o_| M | 64 | 80 2 54 58 55 52. 3 68 64 58 a 70 | 67 | 62 | 60 “hapter 6: Assignment Model Page 235‘The Assignment Tableau with Row Reductions Tableau Tableau 2 : Year Level Salesperson Year Level 3 |e B Cc D Als cys 1 70-64 64-64 | 80-64 1 6 | MT] ote 2 54-52 | 58-52 | 55-52 | 52-52 | > 2 216} 375 s) 68-56 | 64-56 | 58-56 | 56-56 3 wi slaty 4 70-60 | 67-60 | 62-60 | 60-60 4 wo] 7 Tat Step 2: Select the minimum entry in each column é& subtract it from every entry in that Colum, Tableau 2 Region Salesperson -— ceo 1 6 [Mo [16 2 2 [6 | 3 0 3 zfs t2tfo 4 wo [7 | 2 0 Column 2 6 0 0 Reducer YY The Assignment Tableau with Column Reductions 3 Tableau 3 Year Level Year Level Salesperson person 2 A.B 7) ae ATs Ic ») 1 6-2 | M 0-0 | 16-0 1 4|M|o| 2 2-2 | 6-6 [3-0 | 0-0 | > 2 ojo} 3io 3 12-2 | 8-6 [2-0 | 0-0 3 jo] 2 [2 [0 4 10-2 | 7-6 [2-0 | 0-0 4 8 | 1f{2 {0 Step 3: Apply the line test for optimality, The Opportunity Value Tableau with the Line Test Tableau3 . Salesperson 3 1 4 [™M 3 io [2 4 8 1 Notice that there are only three lines in Tableau 3, whereas four ” are optimal solution, See? Page 236 Chapter 6; Assignment Modeiz entity the minimum value, which is 1 Tableau 3 lesperson. Regio salespe ia 1 4 ae 3 10 4 8 g Subtract 1 from all values in Tableau 3 that is not crossed out. Then add 1 to cells with intersecting lines, and copy the rest ofthe values in Tableau 3 covered by a single line- aueet— 5 Tableau 4 car Level ‘Year Level person salespet A B c 5 salesperson |=] cD. a 4-1 [| M 0 16 i 3. [mM] 0 | 16 2 0 0 3+1 [| o+1 |> 2 o}of4]1 10-1 2-1 js 2 0 3 9{i/2]|0 a Ca es! 2 0 4 71o0[2]0 up: Apply the line test again to determine if an optimal solution already exists. ‘The Second Iteration: The Opportunity Profit Tableau with the Line Test Tableau 4 Regio Salesperson | 73 1 3_[M 3 9 1 No matter how the lines are drawn in Tableau 4, we need at least 4 lines to cross out all the zero entries. This indicates that the 4 unique assignments, thus, an optimal solution i has been reached. usp 7: Identify the rows with zero entries in their respective columns. ‘Then allocate the rest of the rows to complete the assignment Galesperson | Region _| Order of ‘Assignment [Salesperson | Region 1 c First > 1 c 2 AB Fourth > 2 A 3 D Second > 3 D 4 B,D Third > 4 B ye one zero entries, thus we will start the assignment Observed that Row 1 and Row 3 ha emaining assignments using elimination method. with these rows. Then, allocate the re Chapter 6: Assignment Model Page 237Step 8: Make the assignments from the last tableau. Salesperson | Region | Days 1 c 64 2 A 54 3 D 56 4 B 67. Total | 241 # Enrichment Exercise 6.6 ‘An advertising company is trying to decide which of six account executives to assign to ead of six major clients. The estimated costs of each assignment for each executive are presented ix the table, except for Executive 4 and 5 who refuse to be assigned in Account D and ¢ respectively. Use Hungarian method to determine the optimal solution to this problem. State the value of the objective function. Clients ecutive ATT eS | DET FY T 3 |H| 0) ie | 2m) | 2 30 12 18 il 16 26 i “330 96 5. | 18 29) 4 | 4 ib [a |) M | im) 2 | 5 7 [9 | M | m@ | 2) 20 [6 2b lB [is [ay 2 Page 238 = ad