Games, inventory and transport · Linear programming & operations research

Two-person games

A payoff matrix shows what the row player $A$ wins for each pair of strategies (the column player $B$ loses the same). $A$ wants large numbers; $B$ wants small ones.

Maximin: the largest of the row minima (the best $A$ can guarantee).
Minimax: the smallest of the column maxima (the best $B$ can guarantee).

Maximin and minimaxmaximin = largest row minimum; minimax = smallest column maximum

If maximin = minimax, that entry is a saddle point: each player keeps to one strategy and the value of the game is that entry. If not, each player mixes their strategies. For the matrix $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ , $A$ plays row 1 with probability $p$ chosen so that $B$ ‘s two columns give the same result.

A 2 × 2 gameSet the payoffs to player A

2maximin3minimax5/2value of the game

row 1, col 1 = 4row 1, col 2 = 1row 2, col 1 = 2row 2, col 2 = 3

Maximin 2 ≠ minimax 3: no saddle point, so mix. A plays row 1 with p where 4p + 2(1 − p) = p + 3(1 − p): p = 1/4. B plays column 1 with q = 1/2. The value is (4 × 3 − 1 × 2) ÷ 4 = 5/2.

Worked example · NECO 2023

NECO 2023 · Paper 2 · Q15 (a)

The payoff matrix of players $A$ and $B$ in a game is $\begin{pmatrix} 3 & 4 \\ 5 & 1 \end{pmatrix}$ . Find the (i) maximin value; (ii) minimax value; (iii) mixed strategies of $A$ and $B$ ; (iv) value of the game.

Maximin and minimax
- Row minima: 3 and 1, so the maximin value is ${3}$ .
- Column maxima: 5 and 4, so the minimax value is ${4}$ . They differ: no saddle point.
A's mixed strategy
- ${3p + 5(1 - p) = 4p + 1(1 - p)}$ , so ${5 - 2p = 1 + 3p}$ and ${p = \frac45}$ .
- $A$ plays ${\left(\frac45, \frac15\right)}$ .
Think first. Make B's two columns give A the same result.
B's mixed strategy and the value
- ${3q + 4(1 - q) = 5q + 1(1 - q)}$ , so ${4 - q = 1 + 4q}$ and ${q = \frac35}$ : $B$ plays ${\left(\frac35, \frac25\right)}$ .
- Value ${= 3\left(\frac45\right) + 5\left(\frac15\right) = \frac{17}{5} = 3.4}$ .

More: games

NECO 2023 · Paper 1 · Q48If the payoff matrix of a game is $\begin{pmatrix} 3 & 6 \\ 4 & 2 \end{pmatrix}$ , find the maximin value of the game.

The economic order quantity

A shop that orders stock pays an ordering cost each time it orders and a holding cost for keeping stock. Large orders mean few ordering costs but high holding costs. The total is least at the economic order quantity:

Balancing the two costsEOQ = √(2 × demand × ordering cost ÷ holding cost per unit)

\text{EOQ} = \sqrt{\frac{2DC_o}{C_h}}

where $D$ is the yearly demand, $C_o$ the cost of one order and $C_h$ the yearly holding cost of one unit. The number of orders a year is $D \div \text{EOQ}$ .

Worked example · NECO 2023

NECO 2023 · Paper 2 · Q14 (b)

The annual demand for a product is 800 units and the unit price is ₦2.00. If the ordering cost is ₦5.00 and the holding cost is $10\%$ of the unit price, calculate the total variable cost per annum (₦).

The holding cost
- ${C_h = 10\% \text{ of } 2 = 0.20}$ .
Think first. 10% of the unit price.
The EOQ
- ${\text{EOQ} = \sqrt{\frac{2 \times 800 \times 5}{0.2}} = \sqrt{40\,000} = 200}$ units.
The total variable cost
- Ordering: ${\frac{800}{200} \times 5 = 20}$ . Holding: ${\frac{200}{2} \times 0.20 = 20}$ .
- Total: ${20 + 20 = 40}$ naira a year.

The north-west corner rule

A transport problem sends goods from suppliers to destinations. The north-west corner rule gives a first plan: start in the top-left cell and send as much as possible. When a destination is satisfied, move right; when a supplier runs out, move down.

Filling the tableStart top-left; move right or down as each total is used up

Worked example · NECO 2023

NECO 2023 · Paper 2 · Q8

A company has three production facilities $P_1$ , $P_2$ and $P_3$ with capacities of 8, 10 and 19 units (in hundreds) per week. The units are shipped to four warehouses $A_1$ – $A_4$ requiring 6, 8, 8 and 15 units (in hundreds) per week. The transportation cost (in hundreds of naira) is given below.

	$A_1$	$A_2$	$A_3$	$A_4$	Capacity
$P_1$	19	30	50	10	8
$P_2$	70	30	40	60	10
$P_3$	40	8	70	20	19
Demand	6	8	8	15

Using the north-west corner rule:

obtain the initial basic transportation plan;

calculate the total cost of this plan.

Fill from the top-left
- $P_1$ : 6 to $A_1$ , then its last 2 to $A_2$ .
- $P_2$ : 6 more to $A_2$ (now 8), then 4 to $A_3$ .
- $P_3$ : 4 more to $A_3$ (now 8), then 15 to $A_4$ .
Think first. P₁ has 8; A₁ needs 6.
The cost
- ${6(19) + 2(30) + 6(30) + 4(40) + 4(70) + 15(20)}$ .
- ${= 114 + 60 + 180 + 160 + 280 + 300 = 1094}$ .
Think first. Multiply each amount by its cost and add.

Your turn

NECO 2023 · Paper 1 · Q50

Linear programming & operations research

The annual demand for a product is 12,500 units, the annual holding cost is ₦50.00 per unit and the cost of placing an order is ₦500.00. Find the number of orders per annum.

Worked solution (try it first)

The economic order quantity is $\text{EOQ} = \sqrt{\dfrac{2DC_o}{C_h}}$ , with $D = 12\,500$ , $C_o = 500$ and $C_h = 50$ .
$\text{EOQ} = \sqrt{\dfrac{2 \times 12\,500 \times 500}{50}}$
$= \sqrt{250\,000}$ , which is 500 units.
The number of orders a year is $\dfrac{12\,500}{500} = 25$ , option D.

Report a problem with this question