# Question 5:

## Part (a) - Initial Simplex Tableau

| Answer | Marks | Guidance |
|--------|-------|----------|
| Introduce slack variables $s_1, s_2, s_3$ to give: $x + y + z + s_1 = 16$, $x - 2y + 2z + s_2 = 17$, $2x - y + 2z + s_3 = 19$ | B1 | Correct equations with slack variables |
| $P - x + 2y - 3z = 0$ | B1 | Correct objective row |

**Initial Tableau:**

| BV | $x$ | $y$ | $z$ | $s_1$ | $s_2$ | $s_3$ | RHS |
|----|-----|-----|-----|--------|--------|--------|-----|
| $s_1$ | 1 | 1 | 1 | 1 | 0 | 0 | 16 |
| $s_2$ | 1 | −2 | 2 | 0 | 1 | 0 | 17 |
| $s_3$ | 2 | −1 | 2 | 0 | 0 | 1 | 19 |
| $P$ | −1 | 2 | −3 | 0 | 0 | 0 | 0 |

## Part (b)(i) - Identify Pivot

| Answer | Marks | Guidance |
|--------|-------|----------|
| Pivot is $2$ in row $s_2$ (or $s_3$) | B1 | Correct pivot identified |
| $z$-column chosen as most negative entry in $P$-row; row chosen by minimum ratio test: $16/1=16$, $17/2=8.5$, $19/2=9.5$, minimum is $8.5$ so $s_2$-row | B1 | Must justify both column and row selection |

## Part (b)(ii) - First Iteration

| Answer | Marks | Guidance |
|--------|-------|----------|
| New $s_2$ row (pivot row) $\div 2$: $\frac{1}{2}, -1, 1, 0, \frac{1}{2}, 0 \mid \frac{17}{2}$ | M1 | Dividing pivot row by pivot element |
| Correct elimination for $s_1$ row: $\frac{1}{2}, 2, 0, 1, -\frac{1}{2}, 0 \mid \frac{15}{2}$ | A1 | |
| Correct elimination for $s_3$ row: $1, 1, 0, 0, -1, 1 \mid 2$ | A1 | |
| Correct $P$ row: $\frac{1}{2}, -1, 0, 0, \frac{3}{2}, 0 \mid \frac{51}{2}$ | A1 | |

**Tableau after iteration 1:**

| BV | $x$ | $y$ | $z$ | $s_1$ | $s_2$ | $s_3$ | RHS |
|----|-----|-----|-----|--------|--------|--------|-----|
| $s_1$ | $\frac{1}{2}$ | 2 | 0 | 1 | $-\frac{1}{2}$ | 0 | $\frac{15}{2}$ |
| $z$ | $\frac{1}{2}$ | −1 | 1 | 0 | $\frac{1}{2}$ | 0 | $\frac{17}{2}$ |
| $s_3$ | 1 | 1 | 0 | 0 | −1 | 1 | 2 |
| $P$ | $\frac{1}{2}$ | −1 | 0 | 0 | $\frac{3}{2}$ | 0 | $\frac{51}{2}$ |

## Part (c)(i) - Second Iteration

| Answer | Marks | Guidance |
|--------|-------|----------|
| $y$-column selected (most negative in $P$-row); ratio test: $\frac{15/2}{2}=\frac{15}{4}$, $\frac{17/2}{-1}$ (negative, ignore), $\frac{2}{1}=2$; pivot is $1$ in $s_3$ row | M1 | Correct pivot selection |
| New $s_3$ row unchanged: $1, 1, 0, 0, -1, 1 \mid 2$ | A1 | |
| New $s_1$ row: $-\frac{3}{2}, 0, 0, 1, \frac{3}{2}, -2 \mid \frac{11}{2}$ | A1 | |
| New $z$ row: $\frac{3}{2}, 0, 1, 0, -\frac{1}{2}, 1 \mid \frac{21}{2}$ | A1 | |
| New $P$ row: $\frac{3}{2}, 0, 0, 0, \frac{1}{2}, 1 \mid \frac{53}{2}$ | A1 | |

**Tableau after iteration 2:**

| BV | $x$ | $y$ | $z$ | $s_1$ | $s_2$ | $s_3$ | RHS |
|----|-----|-----|-----|--------|--------|--------|-----|
| $s_1$ | $-\frac{3}{2}$ | 0 | 0 | 1 | $\frac{3}{2}$ | $-2$ | $\frac{11}{2}$ |
| $z$ | $\frac{3}{2}$ | 0 | 1 | 0 | $-\frac{1}{2}$ | 1 | $\frac{21}{2}$ |
| $y$ | 1 | 1 | 0 | 0 | −1 | 1 | 2 |
| $P$ | $\frac{3}{2}$ | 0 | 0 | 0 | $\frac{1}{2}$ | 1 | $\frac{53}{2}$ |

## Part (c)(ii) - Interpretation

| Answer | Marks | Guidance |
|--------|-------|----------|
| All entries in $P$-row non-negative, so optimal solution reached | B1 | |
| $P = \frac{53}{2} = 26.5$ when $x = 0$, $y = 2$, $z = \frac{21}{2}$ | B1 | |
| Slack variable $s_1 = \frac{11}{2}$: first constraint not tight (slack of $\frac{11}{2}$) | B1 | |
| $s_2 = 0$, $s_3 = 0$: second and third constraints are binding (active) | B1 | |

---