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.

A Quick Checklist for Formulating Any LP

When you see a word problem, ask yourself in order:

1. What are the decisions? → Define variables with units.
2. What is the goal? → Maximise or minimise? Write the objective.
3. What are the limits? → Each limit becomes a constraint. Check units match.
4. Are there hidden constraints? → Non-negativity is standard. Sometimes you need integer constraints (but that's Integer Programming, not LP).

What LP Cannot Do

LP assumes everything is continuous — you can produce 3.7 chairs. If you need whole numbers (you can't sell half a chair), you need Integer Programming. LP also assumes certainty — if wood supply is random, you need stochastic programming. But for a first meeting, LP is the foundation that all these advanced topics build upon.

Linear Programming Formulation is the opening skill taught in the NCERT Class 12 Mathematics chapter on Linear Programming, matching searches like "linear programming problem formulation examples" or "LPP important questions class 12 maths". Correctly translating a word problem into an objective function and constraints is a heavily weighted, scoring-friendly topic in CBSE Class 12 board exams.