| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Easy -1.2 This is a routine dynamic programming table completion exercise requiring only mechanical application of the maximin algorithm. Students fill in missing values by taking the minimum of pairs and then the maximum across actions—a standard textbook procedure with no problem-solving or novel insight required. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Stage | State | Action | Working | Maximin |
| \multirow{4}{*}{1} | 0 | 0 | 10 | |
| 1 | 0 | 11 | ||
| 2 | 0 | 14 | ||
| 3 | 0 | 15 | ||
| \multirow{10}{*}{2} | \multirow{2}{*}{0} | 0 | (12, ) = | \multirow{2}{*}{} |
| 2 | \(( 10 , \quad ) =\) | |||
| \multirow{3}{*}{1} | 0 | \(( 13 , \quad ) =\) | \multirow{3}{*}{} | |
| 1 | \(( 10 , \quad ) =\) | |||
| 2 | (11, ) = | |||
| \multirow{3}{*}{2} | 1 | ( 9, ) = | \multirow{3}{*}{} | |
| 2 | (10, ) = | |||
| 3 | ( 7, ) = | |||
| \multirow{2}{*}{3} | 1 | ( 8, ) = | \multirow{2}{*}{} | |
| 3 | (12, ) = | |||
| \multirow{4}{*}{3} | \multirow{4}{*}{0} | 0 | \(( 15 , \quad ) =\) | \multirow{4}{*}{} |
| 1 | \(( 14 , \quad ) =\) | |||
| 2 | (16, ) = | |||
| 3 | (13, ) = |
1 Answer this question on the insert provided.
The table shows a partially completed dynamic programming tabulation for solving a maximin problem.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Working & Maximin \\
\hline
\multirow{4}{*}{1} & 0 & 0 & 10 & \\
\hline
& 1 & 0 & 11 & \\
\hline
& 2 & 0 & 14 & \\
\hline
& 3 & 0 & 15 & \\
\hline
\multirow{10}{*}{2} & \multirow{2}{*}{0} & 0 & (12, ) = & \multirow{2}{*}{} \\
\hline
& & 2 & $( 10 , \quad ) =$ & \\
\hline
& \multirow{3}{*}{1} & 0 & $( 13 , \quad ) =$ & \multirow{3}{*}{} \\
\hline
& & 1 & $( 10 , \quad ) =$ & \\
\hline
& & 2 & (11, ) = & \\
\hline
& \multirow{3}{*}{2} & 1 & ( 9, ) = & \multirow{3}{*}{} \\
\hline
& & 2 & (10, ) = & \\
\hline
& & 3 & ( 7, ) = & \\
\hline
& \multirow{2}{*}{3} & 1 & ( 8, ) = & \multirow{2}{*}{} \\
\hline
& & 3 & (12, ) = & \\
\hline
\multirow{4}{*}{3} & \multirow{4}{*}{0} & 0 & $( 15 , \quad ) =$ & \multirow{4}{*}{} \\
\hline
& & 1 & $( 14 , \quad ) =$ & \\
\hline
& & 2 & (16, ) = & \\
\hline
& & 3 & (13, ) = & \\
\hline
\end{tabular}
\end{center}
(i) Complete the last two columns of the table in the insert.\\
(ii) State the maximin value and write down the maximin route.
\hfill \mbox{\textit{OCR D2 2009 Q1 [9]}}