Basic requirements of linear programming

Linear programming (LP) is a mathematical technique for allocating limited resources (money, labour, machines, material) among competing activities in the best way, so as to maximise profit or minimise cost.

Basic requirements

1. Objective function: a clearly stated aim, to be maximised (profit) or minimised (cost, time), expressed as a linear function, e.g. $Z = c_1x_1 + c_2x_2$.
2. Decision variables: unknown quantities ($x_1, x_2, ...$) whose values are to be found; they are inter-related.
3. Constraints: limits on resources, expressed as linear inequalities or equations, e.g. $a_1x_1 + a_2x_2 \le b$.
4. Non-negativity: $x_j \ge 0$, as negative production is meaningless.
5. Alternative courses of action: more than one feasible solution must exist, from which the best is chosen.
6. Linearity, proportionality and additivity: objective and constraints are linear; total use of a resource is the sum of the use of each activity.
7. Divisibility and certainty: variables can take fractional values and all coefficients are known and constant.

Example

A contractor makes two jobs $x$ and $y$ with profit Rs 40 and Rs 30 per unit. Labour: $2x + y \le 100$; machine hours: $x + y \le 80$; $x, y \ge 0$.

$$\text{Maximise } Z = 40x + 30y$$

Corner points of the feasible region: $(0,0)$: $Z = 0$; $(50,0)$: $Z = 2000$; $(20,60)$: $Z = 2600$; $(0,80)$: $Z = 2400$.

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