Short note: Linear programming

Linear programming (LP) is a mathematical technique to find the best (maximum or minimum) value of a linear objective function, subject to linear constraints on limited resources. In project work it is used for optimum allocation of resources, time-cost trade-off (crashing) and product mix.

Components

• Decision variables: quantities to be decided ($x$, $y$).
• Objective function: to maximise profit or minimise cost.
• Constraints: limits on resources such as labour, machine hours, material.
• Non-negativity: $x, y \ge 0$.

Methods

Graphical method (two variables), simplex method (many variables), and software (Excel Solver).

Example

A contractor makes two products, $x$ and $y$, with profit $40 and $30 per unit. Maximise $Z = 40x + 30y$ subject to $2x + y \le 100$, $x + y \le 80$, $x \le 40$, $x, y \ge 0$.

Corner points of the feasible region and values of $Z$:

Answer: maximum $Z = 2600$ at $x = 20$, $y = 60$.

Assumptions and limits

Linearity, certainty of data, divisibility, and a single objective. Real project data are often uncertain.