Optimization assignment problems

7 The diagram shows the locations of some schools. The number on each edge shows the distance, in miles, between pairs of schools.
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-14_1031_1231_428_392} Sam, an adviser, intends to travel from one school to the next until he has visited all of the schools, before returning to his starting school. The shortest distances for Sam to travel between some of the schools are shown in Table 1 opposite.

1. Complete Table 1.
2. 1. On the completed Table 1, use the nearest neighbour algorithm, starting from \(B\), to find an upper bound for the length of Sam's tour.
   2. Write down Sam's actual route if he were to follow the tour corresponding to the answer in part (b)(i).
   3. Using the nearest neighbour algorithm, starting from each of the other vertices in turn, the following upper bounds for the length of Sam's tour were obtained: 77, 77, 77, 76, 77 and 76. Write down the best upper bound. 7
3. 1. On Table 2 below, showing the order in which you select the edges, use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the schools \(A , B , C\), \(D , F\) and \(G\).
   2. Hence find a lower bound for the length of Sam's minimum tour.
   3. By deleting each of the other vertices in turn, the following lower bounds for the length of a minimum tour were found: \(50,48,52,51,56\) and 64 . Write down the best lower bound.
4. Given that the length of a minimum tour is \(T\) miles, use your answers to parts (b) and (c) to write down the smallest interval within which you know \(T\) must lie.
   (2 marks) \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 2}

   	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { F }\)	G
   A	-	2	6	4	16	27
   \(\boldsymbol { B }\)	2	-	8	3	15	26
   \(\boldsymbol { C }\)	6	8	-	10	22	32
   \(\boldsymbol { D }\)	4	3	10	-	12	23
   \(\boldsymbol { F }\)	16	15	22	12	-	20
   G	27	26	32	23	20	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-17_2486_1714_221_153}

8 Tony delivers paper to five offices, \(A , B , C , D\) and \(E\). Tony starts his deliveries at office \(E\) and travels to each of the other offices once, before returning to office \(E\). Tony wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the offices.

4 David, a tourist, wishes to visit five places in Rome: Basilica ( \(B\) ), Coliseum ( \(C\) ), Pantheon ( \(P\) ), Trevi Fountain ( \(T\) ) and Vatican ( \(V\) ). He is to start his tour at one of the places, visit each of the other places, before returning to his starting place. The table shows the times, in minutes, to travel between these places. David wishes to keep his travelling time to a minimum.

1. 1. Find the total travelling time for the tour TPVBCT.
   2. Find the total travelling time for David's tour using the nearest neighbour algorithm starting from \(T\).
   3. Explain why your answer to part (a)(ii) is an upper bound for David's minimum total travelling time.
2. 1. By deleting \(B\), find a lower bound for the total travelling time for the minimum tour.
   2. Explain why your answer to part (b)(i) is a lower bound for David's minimum total travelling time.
3. Sketch a network showing the edges that give the lower bound found in part (b)(i) and comment on its significance.

5 Angelo is visiting six famous places in Palermo: \(A , B , C , D , E\) and \(F\). He intends to travel from one place to the next until he has visited all of the places before returning to his starting place. Due to the traffic system, the time taken to travel between two places may be different dependent on the direction travelled. The table shows the times, in minutes, taken to travel between the six places.

1. Give an example of a Hamiltonian cycle in this context.
2. 1. Show that, if the nearest neighbour algorithm starting from \(F\) is used, the total travelling time for Angelo would be 95 minutes.
   2. Explain why your answer to part (b)(i) is an upper bound for the minimum travelling time for Angelo.
3. Angelo starts from \(F\) and visits \(E\) next. He also visits \(B\) before he visits \(D\). Find an improved upper bound for Angelo's total travelling time.
   
   \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-11_2484_1709_223_153}

8 Mrs Jones is a spy who has to visit six locations, \(P , Q , R , S , T\) and \(U\), to collect information. She starts at location \(Q\), and travels to each of the other locations, before returning to \(Q\). She wishes to keep her travelling time to a minimum. The diagram represents roads connecting different locations. The number on each edge represents the travelling time, in minutes, along that road.
\includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-16_524_866_612_587}

1. 1. Explain why the shortest time to travel from \(P\) to \(R\) is 40 minutes.
   2. Complete Table 1, on the opposite page, in which the entries are the shortest travelling times, in minutes, between pairs of locations.
2. 1. Use the nearest neighbour algorithm on Table 1, starting at \(Q\), to find an upper bound for the minimum travelling time for Mrs Jones's tour.
   2. Mrs Jones decides to follow the route given by the nearest neighbour algorithm. Write down her route, showing all the locations through which she passes.
3. By deleting \(Q\) from Table 1, find a lower bound for the travelling time for Mrs Jones's tour. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 1}

   	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)
   \(P\)	-	25
   \(Q\)	25	-	20	21	23	11
   \(\boldsymbol { R }\)		20	-
   \(\boldsymbol { S }\)		21		-
   \(T\)		23			-	12
   \(\boldsymbol { U }\)		11			12	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-18_2486_1714_221_153}

7 Rupta, a sales representative, has to visit six shops, \(A , B , C , D , E\) and \(F\). Rupta starts at shop \(A\) and travels to each of the other shops once, before returning to shop \(A\). Rupta wishes to keep her travelling time to a minimum. The table shows the travelling times, in minutes, between the shops.

4 Sarah is a mobile hairdresser based at \(A\). Her day's appointments are at five places: \(B , C , D , E\) and \(F\). She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at \(A\). The following table shows the times, in minutes, that it takes to travel between the six places.

1. Sarah decides to visit the places in the order \(A B C D E F A\). Find the travelling time of this tour.
2. Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
3. Use the nearest neighbour algorithm, starting from \(A\), to find another upper bound for the minimum travelling time of Sarah's tour.
4. By deleting \(A\), find a lower bound for the minimum travelling time of Sarah's tour.
5. Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.

4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.

1. Use Prim's algorithm on the table in the insert to find a minimum spanning tree. Start by crossing out row \(A\). Show which entries in the table are chosen and indicate the order in which the rows are deleted. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
3. Explain why the team cannot use the arc \(A C\).
4. Explain why the team must use the arc \(E F\).
5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.

4

1. ↓
   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
   A	0	4	5	3	2	5	6
   \(B\)	4	0	1	2	4	7	6
   C	5	1	0	3	4	6	7
   \(D\)	3	2	3	0	2	6	4
   \(E\)	2	4	4	2	0	6	6
   \(F\)	5	7	6	6	6	0	10
   \(G\)	6	6	7	4	6	10	0

   Order in which rows were deleted: \(\_\_\_\_\) \(A\) Minimum spanning tree: A
   • \(D\)
   F
   B E
   \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_33_28_1302_1101} III
   o D C
   \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-10_38_38_1297_1491}
   • G Total weight: \(\_\_\_\_\)
2. \(\_\_\_\_\)
3. \(\_\_\_\_\)
   Lower bound: \(\_\_\_\_\)
4. Tour: \(\_\_\_\_\)
   Upper bound: \(\_\_\_\_\)

3 This diagram shows a network.
\includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-2_693_744_1307_694}

1. Obtain a minimum connector for this network. Draw your minimum connector, state the order in which the arcs were chosen and give their total weight.
2. Use the nearest neighbour method, starting from vertex \(A\), to find a cycle that passes through every vertex. The network represents a cubical die, with vertices labelled \(A\) to \(H\), and faces numbered from 1 to 6 in such a way that the numbers on each pair of opposite faces add up to 7 . When two faces meet in an edge, the sum of the numbers on the two faces is recorded as the weight on that edge.
3. (a) List the vertices of each of the two faces that meet in the edge \(A G\).
   (b) What number is on the face \(A C E G\) ?
   (c) Which face is numbered 3?

7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( \(Q\) ), Royal Albert Hall ( \(R\) ), Statue of Eros ( \(S\) ), Tower Bridge ( \(T\) ), Westminster Abbey ( \(W\) ), St Paul's Cathedral ( \(X\) ), York House ( \(Y\) ) and Museum of Zoology ( \(Z\) ). The table below shows the travel times, in minutes, from each of the eight places to each of the other places.

1. Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at \(Y\). Write down the route and give the time in minutes.
2. The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
3. (a) Vertex \(Q\) and all arcs joined to \(Q\) are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices \(R , S , T , W , X , Y\) and \(Z\).
   (b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at \(Y\). The tour guide allows for a 5 -minute stop at each of \(S\) and \(Y\), a 10 -minute stop at \(T\) and a 30 -minute stop at each of \(Q , R , W , X\) and \(Z\). The tour guide wants to find a route, starting and ending at \(Y\), in which the tour (including the stops) can be completed in five hours (300 minutes).
4. Use the nearest neighbour method, starting at \(Q\), to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.

5 [Answer this question on the insert provided.]
\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.

1. The diagram on the insert shows the result of deleting vertex \(F\) and all the arcs joined to \(F\). Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km . The corresponding lower bounds by deleting each of the other vertices are: $$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$ The route \(A - B - C - D - E - F - A\) has length 47 km .
2. Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?
3. By considering the orders in which vertices \(C , D\) and \(E\) can be visited, find the best upper bound given by a route of the form \(A - B - \ldots - F - A\).

4 Table 4 shows the butter and sugar content in two recipes. The first recipe is for 1 kg of toffee and the second is for 1 kg of fudge. \begin{table}[h] \section*{Table 6.1} (ii) Specify an efficient rule for using one-digit random numbers to simulate the time taken at the till by customers purchasing fuel. Table 6.2 shows the distribution of time taken at the till by customers who are not buying fuel. \section*{Table 6.2} (iii) Specify an efficient rule for using two-digit random numbers to simulate the time taken at the till by customers not buying fuel. What is the advantage in using two-digit random numbers instead of one-digit random numbers in this part of the question? The table in the insert shows a partially completed simulation study of 10 customers arriving at the till.
(iv) Complete the table using the random numbers which are provided.
(v) Calculate the mean total time spent queuing and paying.

5 Viola and Orsino are arguing about which striker to include in their fantasy football team. Viola prefers Rocinate, who creates lots of goal chances, but is less good at converting them into goals. Orsino prefers Quince, who is not so good at creating goal chances, but who is better at converting them into goals. The information for Rocinate and Quince is shown in the tables.

1. Give an efficient rule for using 2-digit random numbers to simulate the number of chances created by Rocinate in a match.
2. Give a rule for using 2-digit random numbers to simulate the conversion of chances into goals by Rocinate.
3. Your Printed Answer Book shows the result of simulating the number of goals scored by Rocinate in nine matches. Use the random numbers given to complete the tenth simulation, showing which of your simulated chances are converted into goals.
4. Give an efficient rule for using 2-digit random numbers to simulate the number of chances created by Quince in a match.
5. Your Printed Answer Book shows the result of simulating the number of goals scored by Quince in nine matches. Use the random numbers given to complete the tenth simulation, showing which of your simulated chances are converted into goals.
6. Which striker, if any, is favoured by the simulation? Justify your answer.
7. How could the reliability of the simulation be improved?

5 John is reviewing his lifestyle, and in particular his leisure commitments. He enjoys badminton and squash, but is not sure whether he should persist with one or both. Both cost money and both take time. Playing badminton costs \(\pounds 3\) per hour and playing squash costs \(\pounds 4\) per hour. John has \(\pounds 11\) per week to spend on these activities. John takes 0.5 hours to recover from every hour of badminton and 0.75 hours to recover from every hour of squash. He has 5 hours in total available per week to play and recover.

1. Define appropriate variables and formulate two inequalities to model John's constraints.
2. Draw a graph to represent your inequalities. Give the coordinates of the vertices of your feasible region.
3. John is not sure how to define an objective function for his problem, but he says that he likes squash "twice as much" as badminton. Letting every hour of badminton be worth one "satisfaction point" define an objective function for John's problem, taking into account his "twice as much" statement.
4. Solve the resulting LP problem.
5. Given that badminton and squash courts are charged by the hour, explain why the solution to the LP is not a feasible solution to John's practical problem. Give the best feasible solution.
6. If instead John had said that he liked badminton more than squash, what would have been his best feasible solution?

5 [Figure 3, printed on the insert, is provided for use in this question.]
A landscape gardener has three projects, \(A , B\) and \(C\), to be completed over a period of 4 months: May, June, July and August. The gardener must allocate one of these months to each project and the other month is to be taken as a holiday. Various factors, such as availability of materials and transport, mean that the costs for completing the projects in different months will vary. The costs, in thousands of pounds, are given in the table. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from August, to find the project schedule that minimises total costs. State clearly which month should be taken as a holiday and which project should be undertaken in which month.

2 A farmer has five fields. He intends to grow a different crop in each of four fields and to leave one of the fields unused. The farmer tests the soil in each field and calculates a score for growing each of the four crops. The scores are given in the table below. The farmer's aim is to maximise the total score for the four crops.

1. 1. Modify the table of values by first subtracting each value in the table above from 20 and then adding an extra row of equal values.
   2. Explain why the Hungarian algorithm can now be applied to the new table of values to maximise the total score for the four crops.
2. 1. By reducing rows first, show that the table from part (a)(i) becomes

      2	6	10	0	\(p\)
      0	5	12	4	8
      8	7	5	0	\(q\)
      1	8	2	4	0
      0	0	0	0	0

      State the values of the constants \(p\) and \(q\).
   2. Show that the zeros in the table from part (b)(i) can be covered by one horizontal and three vertical lines, and use the Hungarian algorithm to decide how the four crops should be allocated to the fields.
   3. Hence find the maximum possible total score for the four crops.

2 A team with five members is training to take part in a quiz. The team members, Abby, Bob, Cait, Drew and Ellie, attempted sample questions on each of the five topics and their scores are given in the table. For the actual quiz, each topic must be allocated to exactly one of the team members. The maximum total score for the sample questions is to be used to allocate the different topics to the team members.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(35 - x\).
2. Form a new table by subtracting each number in the table above from 35 . Hence show that, by reducing rows first then columns, the resulting table of values is as below, stating the values of the constants \(p\) and \(q\).

   8	6	8	0	4
   0	11	\(p\)	4	4
   10	4	6	0	12
   \(q\)	2	0	4	0
   0	0	6	6	0

3. Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. 1. Hence find the possible allocations of topics to the five team members so that the total score for the sample questions is maximised.
   2. State the value of this maximum total score.

3 Four pupils, Wendy, Xiong, Yasmin and Zaira, are each to be allocated a different memory coach from five available coaches: Asif, Bill, Connie, Deidre and Eric. Each pupil has an initial training session with each coach, and a test which scores their improvement in memory-recall produces the following results.

2 Five students attempted five different games, and penalty points were given for any mistakes that they made. The table shows the penalty points incurred by the students. Using the Hungarian algorithm, each of the five students is to be allocated to a different game so that the total number of penalty points is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   2	4	0	2	3
   4	2	0	1	1
   5	0	1	\(k\)	0
   1	1	0	4	2
   0	2	0	0	3

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with three lines, and use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five students to the five games with the minimum total of penalty points.
4. Find the minimum possible total of penalty points.
   \includegraphics[max width=\textwidth, alt={}]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-05_2484_1709_223_153}

2 The times taken, in minutes, for five people, \(A , B , C , D\) and \(E\), to complete each of five different puzzles are recorded in the table below. Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.

1. By reducing the columns first and then the rows, show that the new table of values is

   3	1	0	4	1
   0	\(k\)	0	1	3
   1	0	3	1	2
   2	3	2	0	0
   0	5	1	2	1

   State the value of the constant \(k\).
2. 1. Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
   2. Use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
4. Find the minimum total time for completing the five puzzles.
5. Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.

3 The table shows the times taken, in minutes, by five people, \(A , B , C , D\) and \(E\), to carry out the tasks \(V , W , X , Y\) and \(Z\). Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.

1. By reducing the columns first, and then the rows, show that the new table of values is

   0	12	13	2	0
   14	21	0	\(k\)	9
   3	10	0	6	23
   0	2	6	20	0
   0	0	0	0	7

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
4. Find the minimum total time.

1. A theme park has four sites, A, B, C and D, on which to put kiosks. Each kiosk will sell a different type of refreshment. The income from each kiosk depends upon what it sells and where it is located. The table below shows the expected daily income, in pounds, from each kiosk at each site.

Reducing rows first, use the Hungarian algorithm to determine a site for each kiosk in order to maximise the total income. State the site for each kiosk and the total expected income. You must make your method clear and show the table after each stage.
(Total 13 marks)

5. Four salesperson \(A , B , C\) and \(D\) are to be sent to visit four companies \(1,2,3\) and 4 . Each salesperson will visit exactly one company, and all companies will be visited. Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.

1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
2. State the value of the maximum sales.
3. Show that there is a second allocation that maximises the sales.
   (Total 15 marks)

6. Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, \(A , B , C\) and \(D\). Each salesperson must attend just one fair and each fair must be attended by just one salesperson. The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown in the table below.

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the total expected sales from the four salespersons. You must make your method clear and show the table after each stage.
2. State all possible optimal allocations and the optimal total value.
   (4)(Total 14 marks)