Dynamic programming resource allocation

7. Minty has \(\pounds 250000\) to allocate to three investment schemes. She will allocate the money to these schemes in units of \(\pounds 50000\). The net income generated by each scheme, in \(\pounds 1000\) s, is given in the table below. Minty wishes to maximise the net income. She decides to use dynamic programming to determine the optimal allocation, and starts the table shown in your answer book.

1. Complete the table in the answer book to determine the amount Minty should allocate to each scheme in order to maximise the income. State the maximum income and the amount that should be allocated to each scheme.
2. For this problem give the meaning of the table headings
   1. Stage,
   2. State,
   3. Action.

8. A factory can process up to five units of carrots each month. Each unit can be sold fresh or frozen or canned.
The profits, in \(\pounds 100\) s, for the number of units sold, are shown in the table.
The total monthly profit is to be maximised. Use dynamic programming to determine how many of the five units should be sold fresh, frozen and canned in order to maximise the monthly profit. State the maximum monthly profit.
(Total 12 marks)

7. Susie has hired a team of four workers who can make three types of toy. The total number of toys the team can produce will depend on which toys they make, and on how many workers are assigned to make each type of toy. The table shows how many of each toy would be made if different numbers of workers were assigned to make them. Each worker is to be assigned to make just one type of toy and all four workers are to be assigned. Susie wishes to maximise the total number of toys produced.

1. Use dynamic programming to determine the allocation of workers which maximises the total number of toys made. You should show your working in the table provided in the answer book.
   (12)
2. State the maximum total number of toys produced by this team.
   (1)
   (Total 13 marks)

6. Polly is a motivational speaker who is planning her engagements for the next four weeks. Polly will

• visit four different countries in these four weeks
• visit just one country each week
• leave from her home, S , and return there only after visiting the four countries
• travel directly from one country to the next

Polly wishes to determine a schedule of four countries to visit.
Table 1 shows the countries Polly could visit each week. \begin{table}[h] \end{table} Table 2 shows the speaker fee, in \(\pounds 100\) s, Polly would expect to earn in each country. \begin{table}[h] \end{table} Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the countries. \begin{table}[h] \end{table} Polly's expected income is the value of the speaker fee minus the cost of travel.
She wants to find a schedule that maximises her total expected income for the four weeks. Use dynamic programming to determine the optimal schedule. Complete the table provided in the answer book and state the maximum expected income.
(13)

7. A clothing manufacturer can export a maximum of five batches of shirts each year. Each exported batch contains just one type of shirt, the types being T-shirts, Rugby shirts and Polo shirts. The table below shows the profit, in £ 1000 s, for the number of each exported batch type. 2.

1. 	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   	1	2	3	4	Supply
   A					33
   B					21
   C					25
   Demand	21	17	28	13

   3.

   	B plays 1	B plays 2	B plays 3
   A plays 1	0	- 2	6
   A plays 2	3	4	1
   A plays 3	- 1	1	- 3

   4.

   	1	2	3	4
   A	53	84	-	20
   B	87	72	41	38
   C	70	51	52	25
   D	45	-	81	70

   5. (a)
2. You may not need to use all of these tableaux

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	15	- 2	3	1	0	0	180
   \(s\)	10	1	1	0	1	0	80
   \(t\)	1	6	- 2	0	0	1	100
   \(P\)	- 1	- 2	- 5	0	0	0	0

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

3. 
   6. (a) Value of initial flow
   (b) Capacity of cut \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-20_1931_1099_507_408} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{d5798c81-290a-4e4b-aa46-497b62ca899b-21_1874_953_653_589}
   7. You may not need to use all the rows of this table

   Stage	State	Action	Dest.	Value
   T-shirt

   Stage	State	Action	Dest.	Value

   Maximum annual profit £ \(\_\_\_\_\)

6. Jonathan is an author who is planning his next book tour. He will visit four countries over a period of four weeks. He will visit just one country each week. He will leave from his home, S , and will only return there after visiting the four countries. He will travel directly from one country to the next. He wishes to determine a schedule of four countries to visit. Table 1 shows the countries he could visit each week. \begin{table}[h] 2. 3.

1. You may not need to use all of these tables

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   4. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-18_1056_1572_1450_185} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} Maximum flow along SBET: \(\_\_\_\_\) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-19_1043_1572_1505_187} \captionsetup{labelformat=empty} \caption{Diagram 2}
   \end{figure} 5.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	- 2	- 6	1	1	0	0	40
   \(s\)	2	3	2	0	1	0	80
   \(t\)	1	2	2	0	0	1	50
   \(P\)	- 4	- 2	\(- k\)	0	0	0	0

   You may not need to use all of these tableaux

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   6.

   Stage	State	Action	Destination	Value
   0	I	IS	S	\(30 - 5 = 25 ^ { * }\)

   Stage	State	Action	Destination	Value

   END

7. A manufacturer can export five batches of footwear each year. Each exported batch contains just one type of footwear. The types of footwear are trainers, sandals or high heels. The table below shows the profit, in \(\pounds 1000\) s, for the number of batches of each type of footwear. 2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} 3. \begin{table}[h] \end{table} 4. .
5. \begin{figure}[h] \end{figure} 6. Player A \begin{table}[h] \end{table} 7.