Optimization assignment problems

Questions where people/teams must be assigned to tasks/jobs/locations with numerical costs or scores in a table, requiring finding the optimal (minimum cost or maximum score) assignment using the Hungarian algorithm or similar methods.

57 questions

Edexcel D2 Q5
5. A travel company offers a touring holiday which stops at four locations, \(A , B , C\) and \(D\). The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below.
\multirow{2}{*}{}Stage
1234
A7856
\(B\)6965
C9857
D7766
Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.
(11 marks)
Edexcel D2 Q5
5. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances.
\multirow{2}{*}{}Stage
123
Alex1969168
Darren2264157
Leroy2072166
Suraj2366171
Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.
Edexcel D2 Q1
  1. A glazing company runs a promotion for a special type of window. As a result of this the company receives orders for 30 of these windows from business \(B _ { 1 } , 18\) from business \(B _ { 2 }\) and 22 from business \(B _ { 3 }\). The company has stocks of 20 of these windows at factory \(F _ { 1 } , 35\) at factory \(F _ { 2 }\) and 15 at factory \(F _ { 3 }\). The table below shows the profit, in pounds, that the company will make for each window it sells according to which factory supplies each business.
\cline { 2 - 4 } \multicolumn{1}{c|}{}\(B _ { 1 }\)\(B _ { 2 }\)\(B _ { 3 }\)
\(F _ { 1 }\)201417
\(F _ { 2 }\)181919
\(F _ { 3 }\)151723
The glazing company wishes to supply the windows so that the total profit is a maximum.
Formulate this information as a linear programming problem.
  1. State your decision variables.
  2. Write down the objective function in terms of your decision variables.
  3. Write down the constraints and state what each one represents.
Edexcel D2 Q3
3. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:
  • strip the wallpaper,
  • paint the woodwork and ceiling,
  • hang the new wallpaper,
  • replace the fittings and tidy up.
The table below shows the time, in hours, that each of the friends is likely to take to complete each job.
AliceBhavinCarlDieter
Strip wallpaper5354
Paint7564
Hang wallpaper8476
Replace fittings5323
As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.
  1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
    (6 marks)
  2. Hence, find the minimum time in which the friends can redecorate the lounge.
    (1 mark)
Edexcel D2 Q1
  1. A team of gardeners is called in to attend to the grounds of a stately home. The three gardeners will each be assigned to one of three areas, the lawns, the hedgerows and the flower beds. The table below shows the estimated time, in hours, it will take each gardener to do each job.
\cline { 2 - 4 } \multicolumn{1}{c|}{}LawnsHedgerowsFlower Beds
Alan44.56
Beth345
Colin3.556
The team wishes to complete the tasks in the least total time.
Formulate this information as a linear programming problem.
  1. State your decision variables.
  2. Write down the objective function in terms of your decision variables.
  3. Write down the constraints and explain what each one represents.
Edexcel D2 Q3
3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below.
FilmMusicalBalletConcert
Andrew5201218
Betty6181516
Carlos421915
Davina5161113
Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.
(10 marks)
OCR Further Discrete AS 2018 June Q3
3 In the pay-off matrix below, the entry in each cell is of the form \(( r , c )\), where \(r\) is the pay-off for the player on rows and \(c\) is the pay-off for the player on columns when they play that cell.
PQR
X\(( 1,4 )\)\(( 5,3 )\)\(( 2,6 )\)
Y\(( 5,2 )\)\(( 1,3 )\)\(( 0,1 )\)
Z\(( 4,3 )\)\(( 3,1 )\)\(( 2,1 )\)
  1. Show that the play-safe strategy for the player on columns is P .
  2. Demonstrate that the game is not stable. The pay-off for the cell in row Y , column P is changed from \(( 5,2 )\) to \(( y , p )\), where \(y\) and \(p\) are real numbers.
  3. What is the largest set of values \(A\), so that if \(y \in A\) then row Y is dominated by another row?
  4. Explain why column P can never be redundant because of dominance.