Linear Programming Formulation: From Intuition to Precision

Imagine you run a small factory that makes two products: chairs and tables. Each chair gives you ₹200 profit, each table gives you ₹300 profit. You have limited wood (240 units) and limited labour hours (100 hours). A chair needs 2 units of wood and 1 hour of labour; a table needs 4 units of wood and 3 hours of labour. You can't make negative chairs or tables. How many of each should you produce to maximise your profit?

This is the kind of problem Linear Programming (LP) is built to solve. The word "programming" here doesn't mean computer programming — it's an old term for "planning". So linear programming is about planning with linear relationships.

The Core Intuition

Every LP problem has three ingredients:

1. Decision variables — the quantities you control (how many chairs, how many tables)
2. An objective — what you want to maximise (profit) or minimise (cost)
3. Constraints — the limits you must respect (wood, labour, non-negativity)

The "linear" part means everything — the profit, the resource usage — adds up in straight-line proportions. Double the chairs, double the wood needed. No fancy curves, no discounts for bulk.

The Precise Statement

A Linear Programming problem is an optimisation problem of the following form:

Let's decode this piece by piece.

Decision Variables

$x_1, x_2, \dots, x_n$ are the variables you control. In our factory: let $x_1$ = number of chairs, $x_2$ = number of tables.

Objective Function

$Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n$ is what you want to optimise. The $c_j$ are coefficients — profit per unit or cost per unit. For our factory: $Z = 200x_1 + 300x_2$ (profit to maximise).

Constraints

Each constraint is a linear inequality (or equality) that limits the variables. The $a_{ij}$ are the resource usage per unit of product $j$ for resource $i$. The $b_i$ are the available amounts of each resource.

For our factory:

• Wood: $2x_1 + 4x_2 \leq 240$
• Labour: $1x_1 + 3x_2 \leq 100$

Non-negativity

$x_j \geq 0$ for all $j$. You can't produce negative chairs. This is almost always present in real problems.

The Complete Formulation for Our Example

subject to:

That's it. This is a complete LP formulation. Every LP problem, no matter how complex, follows this same skeleton.

Why "Linear"?

The objective and every constraint are linear functions — they involve only first powers of variables, no $x^2$, no $\sin x$, no $x_1 x_2$. This linearity is what makes LP problems solvable efficiently (using the Simplex method or interior-point methods). If you have products of variables or powers, it's not linear programming anymore — it becomes nonlinear programming, which is much harder. …