Find an optimum assignment with the Hungarian algorithm

What should be decided before reducing an assignment table?

This trail network uses a vertex for each location and an edge for each direct two-way trail. What does the edge C–D mean?

Start with C eligible only for job 1, then enable C–2. Try choosing three edges without repeating a device or job. Verify both displayed counts by listing the possible complete assignments

Why is there no complete assignment before C–2 is enabled?

From a graph key to one-to-one allocation

The retained Year 10 check asks what an edge means. Here vertices are in two disjoint sets, devices and jobs, and edges mean eligibility. Graph connectedness or an edge at every vertex does not guarantee a complete matching. The later cost case permits every device-job pair and is a separate model from the restricted graph

1. 1Set the objective first For a maximum score, let M be the largest original entry and replace x by M minus x \(\displaystyle x'_{ij}=M-x_{ij}\)
2. 2Reduce each row Subtract the smallest entry in a row from every entry in that row \(\displaystyle \min(10,7,12)=7,\quad(10,7,12)-7=(3,0,5)\)
3. 3Reduce each column After row reduction, subtract the smallest entry in each column from that column \(\displaystyle \min(4,7,1)=1,\quad4-1=3\)
4. 4Select independent zeros Choose one zero in each row and column, then use the original entries for the total \(\displaystyle A\to J_2,\ B\to J_3,\ C\to J_1:\quad7+6+7=20\)

Construct and test an eligibility model

Three hypothetical devices A,B,C are to perform jobs 1,2,3, one job per device and one device per job. A can do any job; B can do only job 1; C can initially do only job 1. No numerical edge weight is specified. Later C becomes eligible for job 2 as well

1. 1Construct and explain Draw the labelled bipartite graph and a complete 0/1 eligibility table. Distinguish an available edge from a selected assignment. Determine the maximum matching size and whether a complete assignment exists in each state. Explain the original obstruction rather than merely reporting a failed search
2. 2Check all possibilities List the six permutations of three jobs, test each against the eligibility table and retain only those using eligible pairs. Explain why connectedness, drawing distances and having at least one edge at every vertex do not resolve the one-to-one constraint

Model response: Construct and test an eligibility model

Compare the complete construction and justification, not just the final number or chosen option

1. 1Original graph and table Rows A,B,C and columns 1,2,3 give eligibility rows (1,1,1),(1,0,0),(1,0,0). The edges are A–1,A–2,A–3,B–1,C–1. B and C together can use only job 1, so assigning both would repeat its endpoint. All six vertices have an edge, and this graph is connected, but a complete matching is impossible. A–2 and B–1 form a matching of size 2; size 3 is impossible, proving the maximum is 2.
2. 2Changed eligibility Enabling C–2 changes only that table entry to 1. B must receive job 1; C must then receive job 2; A receives job 3. Thus A–3,B–1,C–2 is the unique complete assignment and the maximum matching size is 3. Of the six permutations (123),(132),(213),(231),(312),(321), only (312), in device order A,B,C, passes all eligibility checks. The two-state explorer reports this bounded proof, not an algorithm for other graphs

Given information

\(\displaystyle A:\{1,2,3\},\quad B:\{1\},\quad C:\{1\}\)

Before C–2 is enabled, what is the maximum matching size?

Which statement about an eligibility edge is correct?

Construct a complete Hungarian solution

In a separate hypothetical processing model, every device-job pair is eligible. The processing-time matrix has rows A,B,C and columns 1,2,3, in minutes. Assign every job once and every device once to minimise total active machine-time. Times are fixed and additive; setup, availability, waiting and precedence constraints are excluded. These are invented planning values, not measurements

1. 1Construct the solution Build the labelled original matrix. Record row minima and row-reduced matrix, then column minima and column-reduced matrix. Cover all zeros with the fewest row/column lines and justify that number. If three independent zeros are not yet available, find the smallest uncovered entry and perform the complete adjustment. State all selected pairs and total their ORIGINAL values
2. 2Verify independently Enumerate all six permutations and their original totals, or retain an equivalent complete independent check. Explain why the row-minimum total 20 is not feasible, why reduced zeros do not mean zero processing time, and why minimising total active machine-time is not a claim about elapsed project completion
3. 3Produce an independent record Choose your representation and verification method before opening the model response. Save the complete labelled graph and tables, each reduction or adjustment, all selected row-column pairs, original-value totals, actual tool formulas or commands, changed cases and reasoned conclusion. These independent constructions and external-tool operations are self/teacher-reviewed, not automatically marked by the short checks

Model response: Construct a complete Hungarian solution

Compare the complete construction and justification, not just the final number or chosen option

1. 1Reductions and cover Row minima (5,8,7) sum to 20. Subtracting them gives rows (1,2,0),(0,4,1),(0,6,3). Column minima (0,2,0) sum to 2. Subtracting gives (1,0,0),(0,2,1),(0,4,3). Row A and column 1 cover every zero with two lines. No single row or column contains every zero, so two is minimal. Rows B and C have zeros only in column 1, preventing three independent zeros
2. 2Adjustment and allocation The uncovered entries are 2,1,4,3, with minimum 1. Subtract 1 from all uncovered entries, add 1 at the doubly covered entry A1, and leave singly covered entries unchanged. The adjusted rows are (2,0,0),(0,1,0),(0,3,2). Independent zeros select A2,B3,C1. The original total is 7+9+7=23 minutes of active machine-time. The two-line adjustment decreases every complete assignment total by exactly (3−2)×1=1, preserving comparisons
3. 3Independent certificate and interpretation In job-permutation order 123,132,213,231,312,321, original totals are 28,28,25,23,26,24. Thus A2,B3,C1 is uniquely optimal at 23. The row-minimum selection A3,B1,C1 repeats job 1 and is not a valid assignment. Row, column and adjustment offsets total 20+2+1=23, so the zero assignment in the final matrix corresponds to original total 23, not 0. Elapsed duration depends on concurrency and scheduling conditions not represented by this sum

Given information

\(\displaystyle (c_{B1},c_{B2},c_{B3})=(8,12,9)\)

What is the row minimum for device B?

Given information

\(\displaystyle (r_{A2},r_{B2},r_{C2})=(2,4,6)\)

After row reduction, what is the minimum of column 2?

Given information

\(\displaystyle \text{Uncovered entries: }2,1,4,3\)

What is the smallest entry not covered by row A and column 1?

Given information

\(\displaystyle c_{A2}=7,\quad c_{B3}=9,\quad c_{C1}=7\)

Give the minimum original total active machine-time, in minutes

A→job 3 costs 5, B→job 1 costs 8, and C→job 1 costs 7. Why is their total of 20 not a feasible assignment total?

Change the objective and interpret a dummy row

First maximise an invented additive benefit score. The benefit matrix P has rows A,B,C and columns 1,2,3, in points. Every pair is eligible and exactly three pairs are selected. Separately, suppose four jobs are optional and exactly three are to be completed by A,B,C. The time matrix T has rows A,B,C and columns 1,2,3,4, in minutes. The two cases are different models

1. 1Maximisation Convert the benefit matrix to a minimisation problem using M=13. Show why minimising the converted sum is equivalent to maximising the original score. Apply the reductions, state the selected pairs, and report both the converted optimum and original maximum
2. 2Rectangular allocation Add one dummy row of zeros to the four-job time model and solve the resulting square assignment. Interpret the dummy pair in words. Explain what fails if all four jobs must instead be completed in this period and every real device can do only one job
3. 3Produce an independent record Choose your representation and verification method before opening the model response. Save the complete labelled graph and tables, each reduction or adjustment, all selected row-column pairs, original-value totals, actual tool formulas or commands, changed cases and reasoned conclusion. These independent constructions and external-tool operations are self/teacher-reviewed, not automatically marked by the short checks

Model response: Change the objective and interpret a dummy row

Compare the complete construction and justification, not just the final number or chosen option

1. 1Maximisation transformation The original benefit rows A,B,C, with columns 1,2,3, are (12,11,13),(10,6,9),(11,5,8). Subtract every benefit from 13, giving rows (1,2,0),(3,7,4),(2,8,5). Any complete assignment uses exactly three entries, so converted sum=3×13−original sum. Minimising it maximises the original sum. Row minima are 0,3,2; after subtraction the rows are (1,2,0),(0,4,1),(0,6,3). Column reduction by (0,2,0) gives (1,0,0),(0,2,1),(0,4,3). Cover row A and column 1; the smallest uncovered entry is 1. Subtract 1 from uncovered entries and add 1 at their doubly covered intersection to give (2,0,0),(0,1,0),(0,3,2). Independent zeros select A2,B3,C1. Converted optimum is 2+4+2=8; original benefit is 11+9+11=31 points, also 39−8. Do not report 8 as the maximum benefit
2. 2Optional-job model With dummy row (0,0,0,0), consider whether C takes job 4. If C takes job 4 at 4 minutes, A costs at least 5 and B costs at least 8 on the remaining jobs, giving at least 17. A3=5 and B1=8 attain that bound, with dummy2=0. If C does not take job 4, A, B and C cost at least 5, 6 and 7 respectively, giving at least 18. Thus the unique minimum is 17 minutes. Dummy2 means job 2 is not completed; it does not mean a real device performs job 2 for free. This is permitted only because one job may be omitted and the model assigns no penalty for doing so
3. 3Required-job countercase If all four jobs are required in this period and each of three devices can do at most one, no feasible assignment exists. A dummy row does not supply an actual fourth device. Adding real capacity, allowing multiple jobs over time or changing the required set needs a new model. Penalties or priorities for omitted optional work also require explicit values, not automatic zero entries

Given information

\(\displaystyle M=13,\quad P_{A2}=11,\quad P_{B3}=9,\quad P_{C1}=11\)

Give the converted minimum for the benefit model

Given information

\(\displaystyle n=3,\quad M=13,\quad C_{\min}=8\)

Give the original maximum benefit, in points

Given information

\(\displaystyle c_{A3}=5,\quad c_{B1}=8,\quad c_{C4}=4,\quad c_{D2}=0\)

Give the minimum real total for the optional-job model, in minutes

Three devices perform three of four optional jobs; dummy D is assigned to job 2. What does that dummy assignment mean?

Investigate a changed entry and report the limit

Return to the time matrix with rows A,B,C and columns 1,2,3, in minutes. Increase only A2 from 7 to 7+δ minutes, with δ=0,1,2,3. Keep every other time and every one-to-one constraint unchanged

1. 1Recompute rather than assume For each δ, calculate all six assignment totals, identify every optimum and compare them. State the first value with a tie and the values where a different assignment becomes uniquely optimal. Do not hold the old allocation fixed
2. 2Select technology and communicate Choose a spreadsheet, calculator or short program, justify its suitability, and preserve actual formulas or commands and full output. Show how row/column uniqueness and eligibility are checked, not only how totals are added. Report the original and changed optima, distinguish total machine-time from elapsed duration, and state missing measurements and constraints before any practical recommendation
3. 3Produce an independent record Choose your representation and verification method before opening the model response. Save the complete labelled graph and tables, each reduction or adjustment, all selected row-column pairs, original-value totals, actual tool formulas or commands, changed cases and reasoned conclusion. These independent constructions and external-tool operations are self/teacher-reviewed, not automatically marked by the short checks

Model response: Investigate a changed entry and report the limit

Compare the complete construction and justification, not just the final number or chosen option

1. 1Complete changed-case record For permutations 123,132,213,231,312,321, totals are 28,28,25+δ,23+δ,26,24. At δ=0 the unique optimum is 23 with A2,B3,C1. At δ=1, A2,B3,C1 and A3,B2,C1 both total 24. At δ=2 and δ=3, A3,B2,C1 is uniquely optimal at 24; retaining the old assignment would cost 25 or 26. Re-solving is necessary because the preferred allocation changes
2. 2Reproducible tool record For a spreadsheet, place the original 3×3 costs in B2:D4 and list the six permutations as job numbers in F2:H7. Formula =INDEX($B$2:$D$4,1,F2)+INDEX($B$2:$D$4,2,G2)+INDEX($B$2:$D$4,3,H2) gives the first original total; fill down. Check each permutation contains 1,2,3 once. Put δ in J1 and change C2 to =7+$J$1. Preserve the six totals for each setting, including both tied rows, and compare with the independent record above. The stated integer inputs and all these totals are exact; no rounding is needed. A program that enumerates all permutations and sums cost[row][selectedColumn] is another suitable check; retain the actual inputs and output, not a claim that software was used
3. 3Qualified conclusion Under fixed additive processing times and full eligibility, A2,B3,C1 minimises original total active machine-time at 23 minutes. A one-minute rise in A2 gives two equally good allocations at 24; larger stated rises make A3,B2,C1 uniquely best at 24. These hypothetical totals alone do not establish elapsed completion time, operational feasibility or a purchasing decision. Verify real times, setup, eligibility, availability, required work, priorities and scheduling interactions before applying this model

Given information

\(\displaystyle \text{Totals: }28,28,26,24,26,24\)

At δ=1, how many complete assignments achieve the minimum?

Given information

\(\displaystyle \text{Totals: }28,28,28,26,26,24\)

At δ=3, give the new minimum total machine-time, in minutes

Which conclusion is justified by the time-sum model?