Linear Programming — practice questions

A joinery makes doors and window frames. A door needs 3 hours of machining and 2 hours of finishing; a frame needs 2 hours of machining and 4 hours of finishing. There are 60 machining hours and 80 finishing hours available. Doors sell at $180 profit, frames at $150. Formulate the linear programme.

An orchard packs two box types. A standard box holds 8 kg and takes 4 minutes to pack; a premium box holds 5 kg and takes 9 minutes. There is one shift of 6 hours of packing labour and 900 kg of fruit available. The orchard must pack at least twice as many standard boxes as premium ones, and has a contract for at least 20 premium boxes. Standard boxes return $6 each and premium $11. Formulate the model and explain how you translated the ratio and contract conditions.

A transport firm must move at least 500 tonnes of freight using small trucks (8 t, $220 per trip, 1 driver) and large trucks (20 t, $480 per trip, 2 drivers). At most 30 trips can be scheduled and at most 45 drivers are available. Formulate the model to minimise cost, and critically evaluate the four standard linear programming assumptions in this context.

Find all corners of the region defined by $x + 2y \leq 40$, $3x + y \leq 60$, $x \geq 0$, $y \geq 0$, checking each against every constraint.

A region is defined by $4x + 3y \geq 24$, $x + y \geq 7$, $x \leq 8$, $x \geq 0$, $y \geq 0$. Find its corners, state whether it is bounded, and explain what that means for maximising and for minimising a positive objective function over it.

Explain why the feasible region of a linear programme is always convex, and prove that a linear objective function attains its maximum at a corner of a bounded feasible region.

A feasible region has corners $(0,0)$, $(20,0)$, $(16,12)$ and $(0,20)$. Maximise $P = 5x + 7y$ and state which corner is optimal.

For the region with corners $(0,10)$, $(0,80)$, $(20,60)$, $(40,20)$, $(40,10)$, maximise $P = 30x + 30y$. Explain what you find, and describe how the sliding-line method reveals it.

For the dairy model (maximise $P = 40x + 30y$ subject to $2x + y \leq 100$, $x + y \leq 80$, $x \leq 40$, $y \geq 10$, $x \geq 0$), determine the range of Halloumi profit per tray for which $(20, 60)$ remains optimal, and analyse what happens outside that range.

A continuous optimum is at $(8.4,\ 3.7)$ with the constraints $2x + 3y \leq 28$ and $x + y \leq 12$, both variables counting whole items. Find the best whole-number plan for the objective $P = 15x + 20y$.

A bus company's optimum is 6.25 minibuses and 3.5 coaches, giving a continuous minimum cost of $4,850, subject to $30m + 55c \geq 380$ (seats) and $m + c \leq 10$ (drivers), with cost $C = 400m + 900c$. Find the best whole-number solution and explain the cost of integrality.

Explain why the optimal whole-number solution to a linear programme is not always the lattice point nearest the continuous optimum, construct an example demonstrating this, and describe a reliable procedure for finding the integer optimum in a two-variable problem.